Yggdrasil (Mesh)

Yggdrasil — an encrypted IPv6 network running in the <code>200::/7</code> address range. It is an experimental/toy network, so failure is acceptable, as long as it's instructive to see how it breaks if/when everything falls apart.
IP addresses are derived from cryptographic keys, to reduce the need for public key infrastructure. A form of locator/identifier separation (similar in goal to LISP) is used to map static identifiers (IP addresses) onto dynamic routing information (locators), using a distributed hash table (DHT). Locators are used to approximate the distance between nodes in the network, where the approximate distance is the length of a real worst-case-scenario path through the network. This is (arguably) easier to secure and requires less information about the network than commonly used routing schemes.
While not technically a compact routing scheme, tests on real-world networks suggest that routing in this style incurs stretch comparable to the name-dependent compact routing schemes designed for static networks. Compared to compact routing schemes, Yggdrasil appears to have smaller average routing table sizes, works on dynamic networks, and is name-independent. It currently lacks the provable bounds of compact routing schemes, and there's a serious argument to be made that it cheats by stretching the definition of some of the above terms, but the main point to be emphasized is that there are trade-offs between different concerns when trying to route traffic, and we'd rather make every part good than try to make any one part perfect. In that sense, Yggdrasil seems to be competitive, on what are supposedly realistic networks, with compact routing schemes.
Addressing
Yggdrasil uses a truncated version of a <code>NodeID</code> to assign addresses. An address is assigned from the <code>200::/7</code> prefix, according to the following:
# Begin with <code>0x02</code> as the first byte of the address, or <code>0x03</code> if it's a <code>/64</code> prefix.
# Count the number of leading <code>1</code> bits in the NodeID.
# Set the second byte of the address to the number of leading <code>1</code> bits in the NodeID (8 bit unsigned integer, at most 255).
# Append the NodeID to the remaining bits of the address, truncating the leading <code>1</code> bits and the first <code>0</code> bit, to a total address size of 128 bits.
The last bit of the first byte is used to flag if an address is for a router (<code>200::/8</code>), or part of an advertised prefix (<code>300::/8</code>), where each router owns a <code>/64</code> that matches their address (except with the eight bit set to 1 instead of 0). This allows the prefix to be advertised to the router's LAN, so unsupported devices can still connect to the network (e.g. network printers).
The NodeID is a sha512sum of a node's public encryption key. Addresses are checked that they match NodeID, to prevent address spoofing. As such, while a 128 bit IPv6 address is likely too short to be considered secure by cryptographer standards, there is a significant cost in attempting to cause an address collision. Addresses can be made more secure by brute force generating a large number of leading <code>1</code> bits in the NodeID.
When connecting to a node, the IP address is unpacked into the known bits of the NodeID and a matching bitmask to track which bits are significant. A node is only communicated with if its <code>NodeID</code> matches its public key and the known <code>NodeID</code> bits from the address.
It is important to note that only <code>NodeID</code> is used internally for routing, so the addressing scheme could in theory be changed without breaking compatibility with intermediate routers. This has been done once, when moving the address range from the <code>fd00::/8</code> ULA range to the reserved-but-deprecated <code>200::/7</code> range. Further addressing scheme changes could occur if, for example, an IPv7 format ever emerges.

Main Menu

See Also

Main Menu