Although we've had a couple of mentions on HN in the past, Yggdrasil has not really had a formal introduction here - we were keen to introduce Yggdrasil as a project rather than as a couple of version point releases. With that in mind, I'd like to introduce our project - the Yggdrasil Network (https://yggdrasil-network.github.io) - a proof-of-concept network to explore how we can build a decentralised IP network without the traditional scaling problems that other protocols tend to face.
There are plenty of mesh routing schemes out in the wild that have come before us - as an example B.A.T.M.A.N was merged into the Linux kernel back in 2011 - and many of them with different design goals, but one thing that many mesh routing schemes have in common is that they often have an upper size limit on the size of the network that they can practically support. In a protocol dependent upon external subnetting, especially where subnets may not practically map to physical locations (limiting the effectiveness of route aggregation), routing tables will become unmanageably large, cumbersome to replicate and difficult to keep up-to-date across the network.
CJDNS experimented with the idea of using a Distributed Hash Table (DHT) to look up the location of nodes on the network, which had two primary effects. First of all, nodes could be identified by their public keys rather than relying on external subnetting, which meant that it was possible to "flatten" the network down into a single address space (or key space) and IP addresses could be derived using a function of the node's public key. Secondly, nodes would not need to store entire copies of the routing table - instead they would just store small pieces of information that they care about, and the collective knowledge of the network enables two given hosts to find a path to one another. However, CJDNS is source-routed and often suffered from problems in that the network was not always capable of determining the most optimal paths - nodes on the path were not able to use a better route or take shortcuts if available. This eventually lead to the introduction of "supernodes". These supernodes would keep a full view of the network and allow other nodes to delegate path lookups but would require you to trust the supernodes and decreasing decentralisation in the process.
Inspired by CJDNS, Yggdrasil was born - a compact routing scheme implementation which would keep some of the useful features of CJDNS but attempt to solve the scalability issue without depending on supernodes. Nodes would still be identified by their public keys (and IPv6 addresses would be generated from them), a DHT would still be used to assist in locating nodes on the network but nodes on the network would be arranged onto a globally-agreed spanning tree. The "root" of the spanning tree is elected by a function of the node's signing keys (although apart from being designated as the "root", there are no other benefits) and all other nodes are given locators relative to the root of the node. This allows Yggdrasil to route greedily - the sending node only needs to know the locator coordinates of the remote node, and then each other node on the path can simply pass the packets on in the correct direction without being source-routed. This allows us to take shortcuts as a node on the path may know of a better route, or may know to avoid certain links as a result of congestion control. It also means that each node does not need to know much about the state of the network - they need to know their own locator and a path to the root, and other information is supplementary.
Around the middle of 2015, we had a barebones network simulator and eventually a prototype codebase written in Golang was released at the end of 2017. Just over a year later, we've released a number of alpha releases, added support for many platforms (including Linux, Windows, macOS and BSDs) and fixed a number of bugs. There are also on-going efforts to port Yggdrasil to iOS (lead by myself) and with plans to eventually support Android also. The Yggdrasil network currently sits today at around 130 nodes with a few members of our community running public services for consumption by network users. Our goal is to bring Yggdrasil to as many devices and places as possible, as ultimately what we need is to be able to test at scale, identifying and fixing problems if and when they arise.
Anyone is able to download Yggdrasil and join the network, and we welcome anyone who would like to join us in our channels or who would like to test or contribute.
- Our channels: #yggdrasil:matrix.org on Matrix or #yggdrasil on Freenode
I really like the look of this. I have often wondered how one might approach implementing self organising networks for use within isolated communities or the 3rd world.
There are still many places where there is either no internet access at all, or internet access is only provided by a single vendor that is next to useless. The hardware exists that would allow communities with limited technical knowledge to build their own networks, but I have yet to find the software.
Obviously in the civilised world we defer to our ISPs and their technical knowledge to maintain our connectivity, but why must it be like this? Why can't we just throw a bunch of old computers together along with some NICs, switches and cabling to make a self organising, self healing wide area network (an internet) that could be used by anyone.
There is plenty of old but perfectly functional hardware out there and already communities trying their best to make use of it. Maybe it could be made easy for them with a zero-conf USB bootable Linux distro that could run the nodes on one of these networks?
Add to the mix other new technologies like IPFS, and the whole of human knowledge could be made available to even the poorest communities, and there would be little to no congestion.
Am I dreaming here? Is there anything about the above that is unrealistic? Would love to hear opinions on this!
I'm personally rather hopeful that Yggdrasil, or something similar to it, could be used to provide connectivity in harder-to-reach places. I don't think it's a bad dream to want to localise networking more.
One project that comes to mind is the the OLPC project - they had a go at meshing their devices with 802.11s but, like most other routing protocols, it wouldn't scale up as far as it needs to.
Wireless meshing is something we are definitely interested in though. I am hopeful that with the iOS port that we may be able to experiment with true meshing over Multipeer Connectivity/AWDL (if Apple allow us to...) and there have also been efforts by the Toronto Mesh community to adopt and test Yggdrasil.
This seems to have built on top of a lot of accepted ideas that were floating around in the academic peer to peer space in the early 2000s. Glad to see some of them getting traction in the wild aside from, you know, old school music pirating networks.
Finally got around to looking at this and had a couple questions if you're still checking this thread.
Your 0.3 announcement mentioned switching from Kademlia to Chord for the DHT but doesn't go into much details. The lookups are consistently fast, and maybe consume less storage? But Kademlia seems from a topology point of view to more closely match your network and seems to have significant advantages for networks that have ephemeral nodes.
A bit less technical but is there an overall goal for the project? Was this trying to solve a specific issue (such as consistent mobility addresses?) or is this more of a project to test out a combination of findings from research papers?
It occurred to me reading the headline that you could simulate all of the nodes in a virtual environment.
So kind of a general question, but: could you or do you have a way to like, run a VM on your computer where you could ssh in have a big open area to turn on nodes and play around with various network topologies, or the software running in each node? Other people could ssh in and pretend to be a node too.
That way we could try running it on our computers and debug the stack in each node, and then if it works, we could download the stack into our own routers and devices and run it in the real world.
We have a special simulator build which can run several nodes in a single process, and this has been used in the past to test different topologies and network graphs.
But yes, there's absolutely no reason that you couldn't stand up a whole load of VMs or containers and run Yggdrasil in each of them to play about.
Your address stays with you, as it is derived from your public key, but your coordinates/locator on the tree changes. Another node wanting to speak to you would send out a DHT request asking "where are you now?" and, knowing your new locator, can send the traffic to you.
We have a kind of switch/router separation in the codebase where the spanning tree and locator switching is handled in the virtual switch. In our case, instead of MAC addresses, the switch deals in spanning tree locators/coordinates.
Would it be possible to embed or import the yggdrasil codebase into my own golang project, so that I could opporate my software project in its own namespace or keyspace?
That's something we're working on - right now it's possible to link against Yggdrasil but there isn't much to separate IP traffic from your own custom traffic. Soon we will have the ability to separate the two and we will publish a better-defined API with which to do it.
There are plenty of mesh routing schemes out in the wild that have come before us - as an example B.A.T.M.A.N was merged into the Linux kernel back in 2011 - and many of them with different design goals, but one thing that many mesh routing schemes have in common is that they often have an upper size limit on the size of the network that they can practically support. In a protocol dependent upon external subnetting, especially where subnets may not practically map to physical locations (limiting the effectiveness of route aggregation), routing tables will become unmanageably large, cumbersome to replicate and difficult to keep up-to-date across the network.
CJDNS experimented with the idea of using a Distributed Hash Table (DHT) to look up the location of nodes on the network, which had two primary effects. First of all, nodes could be identified by their public keys rather than relying on external subnetting, which meant that it was possible to "flatten" the network down into a single address space (or key space) and IP addresses could be derived using a function of the node's public key. Secondly, nodes would not need to store entire copies of the routing table - instead they would just store small pieces of information that they care about, and the collective knowledge of the network enables two given hosts to find a path to one another. However, CJDNS is source-routed and often suffered from problems in that the network was not always capable of determining the most optimal paths - nodes on the path were not able to use a better route or take shortcuts if available. This eventually lead to the introduction of "supernodes". These supernodes would keep a full view of the network and allow other nodes to delegate path lookups but would require you to trust the supernodes and decreasing decentralisation in the process.
Inspired by CJDNS, Yggdrasil was born - a compact routing scheme implementation which would keep some of the useful features of CJDNS but attempt to solve the scalability issue without depending on supernodes. Nodes would still be identified by their public keys (and IPv6 addresses would be generated from them), a DHT would still be used to assist in locating nodes on the network but nodes on the network would be arranged onto a globally-agreed spanning tree. The "root" of the spanning tree is elected by a function of the node's signing keys (although apart from being designated as the "root", there are no other benefits) and all other nodes are given locators relative to the root of the node. This allows Yggdrasil to route greedily - the sending node only needs to know the locator coordinates of the remote node, and then each other node on the path can simply pass the packets on in the correct direction without being source-routed. This allows us to take shortcuts as a node on the path may know of a better route, or may know to avoid certain links as a result of congestion control. It also means that each node does not need to know much about the state of the network - they need to know their own locator and a path to the root, and other information is supplementary.
Around the middle of 2015, we had a barebones network simulator and eventually a prototype codebase written in Golang was released at the end of 2017. Just over a year later, we've released a number of alpha releases, added support for many platforms (including Linux, Windows, macOS and BSDs) and fixed a number of bugs. There are also on-going efforts to port Yggdrasil to iOS (lead by myself) and with plans to eventually support Android also. The Yggdrasil network currently sits today at around 130 nodes with a few members of our community running public services for consumption by network users. Our goal is to bring Yggdrasil to as many devices and places as possible, as ultimately what we need is to be able to test at scale, identifying and fixing problems if and when they arise.
Anyone is able to download Yggdrasil and join the network, and we welcome anyone who would like to join us in our channels or who would like to test or contribute.
- Our channels: #yggdrasil:matrix.org on Matrix or #yggdrasil on Freenode
- Our blog with some more interesting posts: https://yggdrasil-network.github.io/blog.html
- Our latest builds from CircleCI: https://yggdrasil-network.github.io/builds.html