## 1. Project Overview & Quickstart (yggdrasil-network/configuration.html) # configuration.html Open-source repository yggdrasil-network/configuration.html ### Repository Details - **Repository:** [yggdrasil-network/configuration.html](https://github.com/yggdrasil-network/configuration.html) - **Primary Language:** Code *Note: High-volume repository documentation is actively indexed and synchronized by YakaAI.* ## 2. Official Technical Reference & Guides (yggdrasil-network/yggdrasil-network.github.io) ## File: _config.yml name: Yggdrasil title: Yggdrasil Network End-to-end encrypted IPv6 networking to connect worlds theme: jekyll-theme-primer plugins: - jekyll-feed - jekyll-seo-tag - jekyll-sitemap - jekyll-redirect-from defaults: - scope: path: "_posts/*.md" values: sitemap: true --- ## File: about.md --- sitemap: true logo: iconoir/sparks.svg --- # About Yggdrasil is an experimental software router and routing protocol for building effortless multi-hop computer networks. It is a **fully decentralised** design and only requires a small amount of state to work. It is predominanently a shortest-path routing scheme, whereby the network will attempt to find the most direct path from source to destination. With support for a number of operating systems, it can be installed on everyday computers or devices. Every network node is a router capable of forwarding traffic and connect to each other using **peering connections** which carry network traffic. Peerings can be set up over any IP network — whether that's a direct wired or wireless link, a local area network or even the Internet. In some cases, peerings can also be set up automatically by nearby devices on the same network using multicast discovery, making it as simple as connecting devices together with an Ethernet cable or connecting to the same Wi-Fi network. Yggdrasil nodes automatically pass traffic to help it get closer to its destination where possible. This means that, even in a network that is only sparsely connected, **all nodes will be reachable** by all other nodes on that network. It doesn't even matter if a node is behind a NAT — once a peering is established, traffic flows in both directions over that peering, making it reachable to other network nodes. Yggdrasil is also designed to tolerate changes in the network. For example, if a link fails, the network will quickly self-heal and use other links to route traffic where available. This makes it **suitable for use in mesh networks**, where links go up and down frequently and the network topology often changes. Each node on the network has a location-independent **cryptographic identity** and, in our [current experimental implementation](implementation.md), stable IPv6 addresses are generated from this key. This allows IPv6-supporting applications to work over Yggdrasil largely without modification. The address is fully mobile and stays with the node as it moves around the network. ### Why Yggdrasil? Many networks that exist today are hierarchical in nature, require extensive manual configuration and often rely on a certain degree of centralisation in order to scale. This often makes it difficult or impractical to set up networks quickly on an ad-hoc basis and so most people are heavily reliant on their Internet Service Providers (ISPs). On the other hand, Yggdrasil requires **very little configuration** in order to work and full multi-hop networks can be built up very quickly and easily using Yggdrasil. Nodes do not need to be assigned an address from a centralised authority; they can **generate their own cryptographic identity** and, more importantly, they can keep this address as they roam. Once peering connections are established, routing information is propagated quickly and automatically throughout the network. This ability to provide full end-to-end routability between all network nodes means that Yggdrasil is potentially an enabling technology for true edge computing scenarios, as well as real-world mesh networks. Most importantly, **does not rely on the Internet to function**, therefore it can be used to rapidly build networks in places with little or no existing infrastructure. ### How does Yggdrasil compare to other projects? Yggdrasil is often compared to other projects attempting to create anonymous overlays, such as Tor, I2P, Lokinet and others. These projects are very different to Yggdrasil, in part because they try to guarantee anonymity. Yggdrasil does not aim to provide and **does not guarantee anonymity**. These projects are also intentionally overlay-by-design rather than by convenience, whereas Yggdrasil only exists as an overlay network today because it is an easy way to test the design. Yggdrasil is frequently compared with VPN projects such as Wireguard, Tailscale, Nebula and Zerotier. Although it is possible to use Yggdrasil to build up private networks and/or point-to-point VPN links, this isn't explicitly our primary goal. It's also important to understand that connecting any single node of a private network to another network (such as a public peer) will result in **both networks being bridged together**. Finally, Yggdrasil has **no native exit nodes**, nor does it have any concept of exit nodes, for providing access to the public Internet or to other networks. This can be achieved using proxies or other tunnelling solutions on top of Yggdrasil but this is not something we explicitly aim to provide. ### What is the status of the project? Yggdrasil is currently an **alpha-level research project**, with on-going development but actively maintained. Our expectation is that a future beta-quality release should know enough to be compatible in the face of wire format changes, and reasonably feature complete. A “stable” 1.0 release, if it ever happens, would probably be feature complete, with no expectation of future wire format changes, and free of known critical bugs. The primary goal of this project at this stage is to test the scalability of the Yggdrasil routing scheme and we are doing so with our [overlay network implementation](implementation.md). Studying the behaviour of the network in the real world is most easily achieved with a large number of participants running the software and joining the public test network. We've done our best to support [as many platforms as possible](installation.md) and have a number of [public peers](https://github.com/yggdrasil-network/public-peers) that you can connect to in order to join the test network, so please feel free to experiment. That said, as an alpha project, it may be dangerous to rely solely on Yggdrasil for any life-or-death workloads. There may be failure modes that we don't yet know about yet! As we see it, the project is likely to reach a number of possible outcomes: 1. The project may end up working perfectly even as the network grows, in which case we will look to standardise it and write better-optimised implementations and/or moving the important parts into other projects 1. The project may reach a reasonably stable state but never attract a large enough number of users 1. The project may attract a large enough number of users but reveal inherent design flaws in the process (a learning exercise for a future project or protocol version perhaps) --- ## File: admin.md --- tags: dontlink sitemap: true --- # Admin API The admin socket provides an interface to query and configure Yggdrasil during runtime. By default, Yggdrasil listens for admin connections on `localhost:9001`. ## Control Utility The `yggdrasilctl` utility provides a human-friendly CLI interface to the Yggdrasil admin socket. It can connect to both local and remote Yggdrasil instances, and accepts the same verbs as below. Every field is specified in the `field=value` format. Examples include: ``` yggdrasilctl getDHT yggdrasilctl getPeers ```` To get a list of supported commands: ``` yggdrasilctl list ``` To perform an action on a remote Yggdrasil node, specify the `-endpoint` parameter: ``` yggdrasilctl -endpoint=tcp://10.0.0.1:9001 getPeers yggdrasilctl -endpoint=unix:///var/run/yggdrasil.sock getDHT ``` To get the JSON response body instead of a "friendly" output, specify the `-json` parameter: ``` yggdrasilctl -json getPeers ``` ## Admin Socket The Yggdrasil admin socket uses JSON for request and response formats. A request must be: - A complete JSON stanza - Followed by a newline `\n` character Once a valid request is received, the response stanza is returned. ### Request The structure of a typical request is as below: ``` { "request": "XXX", "foo": "bar", "baz": "qux" } ``` A request: - *Must* have a `"request"` (`string`) field - a value containing the verb of the request - *Can* have a `"keepalive"` (`bool`) field - a `true` or `false` value stating whether the connection should be kept alive for further requests (if not specified, Yggdrasil will close the admin connection after returning a response) - *Must* have any other required fields for the request - *Can* have any other optional fields for the request ### Response A typical response is structured like this: ``` { "request": { "request": "XXX", "foo": "bar", "baz": "qux" }, "response": { }, "status": "success" } ``` A response: - *Always* has a `"request"` (`string`) field, which contains the body of the original request - *Always* has a `"status"` (`string`) field, which is either `"success"` or `"error"` - *Optionally* has a `"response"` section, which contains the response data from the request - *Optionally* has an `"error"` (`string`) field, which contains error text ### Request Types The `"request"` field contains a verb that describes which request to perform. #### `getDHT` Expects no additional request fields. Returns known nodes in the DHT. - `key` (`string`) contains the `PublicKey` of the remote node - `port` (`int`) - `rest` (`int`) #### `getPeers` Expects no additional request fields. Returns one or more records containing information about active peer sessions. The first record typically refers to the current node. For each IPv6 address: - `key` (`string`) contains the `PublicKey` of the remote node - `port` (`uint8`) contains the local switch port number for that peer - `coords` (`[]int`) contains the coordinates of the node on the spanning tree - `remote` (`string`) contains the peering URI of the remote peer #### `getSelf` Expects no additional request fields. Returns exactly one record containing information about the current Yggdrasil node. For the current IPv6 address: - `key` (`string`) contains the `EncryptionPublicKey` of the current node - `build_name` (`string`) contains the build name, if available (e.g. `yggdrasil`, `yggdrasil-develop`) - `build_version` (`string`) contains the build version, if available (e.g. `0.3.0`, `0.2.7-0091`) - `coords` (`[]int`) contains the coordinates of the node on the spanning tree - `subnet` (`string`) contains the routed IPv6 subnet for this host #### `getSessions` Expects no additional request fields. Returns zero or more records containing information about open sessions between the current Yggdrasil node and other nodes. Open sessions indicate that traffic has been exchanged with the remote node recently. For each IPv6 address: - `key` (`string`) contains the `EncryptionPublicKey` of the remote node #### `getTunTap` Expects no additional request fields. Returns exactly one record containing information about the current node's TUN/TAP adapter. For each adapter: - `mtu` (`uint8`) contains the MTU of the local TUN/TAP adapter #### `getMulticastInterfaces` Expects no additional request fields. Returns zero or more strings containing the enabled multicast peering interfaces. If zero strings are returned then it is implied that multicast peering is not allowed on any interface. #### `getNodeInfo` Expects: - `key=` `string`, hex-encoded public key of the remote node to ping, in the same format as e.g. verbose output from a `getDHT` response Asks a remote node to respond with their nodeinfo. Returns a `nodeinfo` section with the nodeinfo. This can be in any format, containing any keys. --- ## File: advanced-peering.md --- sitemap: true tags: dontlink --- # Advanced Peerings This document contains information on more advanced peering setups. ### Multi-homed outbound peerings On a machine that has multiple network interfaces, where more than one interface can be used to reach a given peer (or the Internet), the `InterfacePeers` option can be used instead of the `Peers` option to create peerings over specific interfaces. It is possible to connect to the **same peer multiple times** using different interfaces, creating a highly-available peering configuration: ``` InterfacePeers: { "eth0": [ tls://a.b.c.d:e ] "eth1": [ tls://a.b.c.d:e ] } ``` ### Prioritised listeners Like in the above multi-homed example, the machine may have two or more network interfaces. An example may be a Wi-Fi interface and a wired ethernet interface. If you want to accept incoming peering connections on both, but to specifically prefer sending traffic over one or other link whenever possible, you can use the `priority` field in the peering URI. Lower numbers are better. In this example, the `a.b.c.d` IP address belongs to the wired ethernet adapter and the `f.g.h.i` IP address belongs to the Wi-Fi adapter. Peerings to the priority 1 peering port will be used whenever possible, therefore if another node peers to both interfaces, the wired peering will be preferred over wireless one: ``` tls://a.b.c.d:e?priority=1 tls://f.g.h.i:e?priority=2 ``` Note that the `priority` field only influences traffic between two peerings to the same node. It does not affect routing decisions across different nodes and cannot be used, for example, to avoid sending traffic to one remote peer over another. ### Prioritised multicast interfaces If like above you have multiple network interfaces but are using multicast peers, but want to prefer one network interface over the other, you can specify the `Priority` for a given multicast interface. Lower numbers are better. In this example, peerings that are automatically discovered and established over `eth0` will be preferred over peerings to the same node made over `eth1`: ``` MulticastInterfaces: [ { Regex: eth0 Beacon: true Listen: true Priority: 1 }, { Regex: eth1 Beacon: true Listen: true Priority: 2 } ] ``` Note that the `priority` field only influences traffic between two peerings to the same node. It does not affect routing decisions across different nodes and cannot be used, for example, to avoid sending traffic to one remote peer over another. ### Multiple outbound Tor circuits Peering over Tor is possible using the SOCKS proxy support, although it is typically discouraged as Tor peerings are often slow and fragile. Most notably, Tor circuits can be broken at any time, taking down your Yggdrasil peering connection with it. To mitigate this, enable the `IsolateSOCKSAuth ` option in Tor and then establish **multiple connections to the same peer** using different SOCKS usernames and passwords. The usernames and passwords can be anything, but these unique pairs will force Tor to use a separate circuit for each peering connection, providing redundancy against one of those circuits breaking: ``` Peers: [ socks://one:one@localhost:9050/a.b.c.d:e socks://two:two@localhost:9050/a.b.c.d:e socks://three:three@localhost:9050/a.b.c.d:e ] ``` For more information, see the Tor manual for `IsolateSOCKSAuth`. ### Multicast peerings in combination with a host firewall If your device has a firewall enabled, multicast discovery of peers through `MulticastInterfaces` may not work by default. To get this to work, perform the following three steps: 1. Under `MulticastInterfaces`, set `Port` to a fixed TCP port number; 2. Allow inbound TCP connectivity to this chosen port number through your firewall — this allows inbound peering connections from other devices; 3. Allow inbound UDP connectivity on port 9001 (optionally with a destination address of `ff02::114`) through your firewall — this enables your device to hear multicast beacons from other devices. --- ## File: blog.md --- sitemap: true logo: iconoir/post.svg --- # Blog You can subscribe to our blog [using RSS](https://yggdrasil-network.github.io/feed.xml). {% for post in site.posts %} {% if post.unlisted != true %} {{ post.date | date: "%-d" }} {{ post.date | date: "%B %Y" }} [{{ post.title }}]({{ post.url }}) {{ post.excerpt | strip_html }} {% endif %} {% endfor %} --- ## File: builds.md --- tags: dontlink sitemap: true --- # Latest Builds Builds are no longer linked from this page — please visit the [GitHub Releases](https://github.com/yggdrasil-network/yggdrasil-go/releases) instead. --- ## File: configuration.md --- sitemap: true tags: dontlink --- # Configuration Yggdrasil can run in one of two modes: with a configuration file, or in autoconfigure mode. A static configuration file simplifies most setups as it allows you to keep the same keypair (and therefore IP address), maintain a list of peers and so on. For most users this will be the recommended configuration. Most Yggdrasil distribution packages will generate an `yggdrasil.conf` configuration file automatically, although you will likely need to add peers to the configuration file yourself before Yggdrasil will be usable. See the "Manually Connecting to Peers" section below. However, autoconfigure mode allows you to quickly start Yggdrasil using sane-ish default settings, with `yggdrasil -autoconf`. In this mode, Yggdrasil will automatically attempt to peer with other nodes on the same subnet but **will not attempt to connect to public peers by default**. It also generates a random set of keys each time it is started, and therefore a random IP address each time. Yggdrasil supports configuration in either HJSON or JSON format. HJSON is the default preferred format, as it has comments, although JSON support is available due to ease of manipulation. ### Configuration reference Information about the various options in the configuration file [can be found here](configurationref.md). ### Generating a new config file If you installed Yggdrasil through one of the platform packages (i.e. macOS, Debian, RPM) then a default configuration file may already exist. It is likely located in either `/etc/yggdrasil.conf` or `/etc/yggdrasil/yggdrasil.conf` depending on your platform. Otherwise, you can generate a configuration file in the following ways: | **Generate HJSON**: | `yggdrasil -genconf > /etc/yggdrasil.conf` | | **Generate JSON**: | `yggdrasil -genconf -json > /etc/yggdrasil.conf` | ### Using a config file Yggdrasil can accept a configuration file either through `stdin` or by being given a path on the filesystem to a configuration file: | **Using stdin**: | `yggdrasil -useconf < /etc/yggdrasil.conf` | | **Using file:** | `yggdrasil -useconffile /etc/yggdrasil.conf` | ### Normalising a config file If you want to see the original format of the configuration file, or convert between HJSON and JSON formats, you can use the `-normaliseconf` option, e.g. | **Convert from HJSON to JSON**: | `yggdrasil -normaliseconf -useconffile /etc/yggdrasil.conf -json` | | **Convert from JSON to HJSON**: | `yggdrasil -normaliseconf -useconffile /etc/yggdrasil.conf` | Normalising the configuration also adds any missing configuration items with their default values. This can be useful when upgrading to a newer version of Yggdrasil that adds new configuration options. Many of our distribution packages normalise the configuration automatically during upgrade. ### Exporting keys to external files You can export the private key from an existing configuration file to a separate file: | **Export private key**: | `yggdrasil -useconffile /etc/yggdrasil.conf -exportkey > yggdrasil.key` | Once exported, you can remove the `PrivateKey` line from your configuration file and add a `PrivateKeyPath` entry pointing to the exported key file instead. ### Manually Connecting to Peers Yggdrasil can be configured to connect to other peers by adding entries into the `Peers` configuration section. At startup, Yggdrasil will attempt to open a connection to these peers. A peering URI will look similar to one of the following: | **Direct TCP connection**: | `tcp://hostname:port` | | **Direct TCP+TLS connection**: | `tls://hostname:port` | | **Direct QUIC connection**: | `quic://hostname:port` | | **Via a SOCKS proxy**: | `socks://proxyhostname:proxyport/hostname:port` | By default, only link-local auto-peering is enabled. This connects devices that are connected directly to each other at layer 2, including devices on the same LAN, directly connected by ethernet or configured to use the same ad-hoc wireless network. As the network uses ordinary TCP, it is possible to connect over other networks, such as the Internet or WAN links, provided that the connecting node knows the address and port to connect to and that the connection is not blocked by a NAT or firewall. If the node resides behind a NAT, then port forwarding may be required in order to accept incoming connections. If you are unable to find nodes in the nearby area, a best effort is made to maintain a list of [Public Peers](https://github.com/yggdrasil-network/public-peers) for new users looking to join or test the network. ### Advertising a Prefix While it is generally encouraged that nodes run the software locally, to provide end-to-end cryptographic sessions and participate in routing, this is not always practical. The device may not have the resources to run the software or may not be able to run user code. To that end, Yggdrasil also provides each node with a routed `/64` subnet in addition to their IPv6 address. A node running Yggdrasil that acts as a router may advertise this prefix to other devices just as they would any other ordinary IPv6 network. This may be best illustrated by example. Suppose a node has generated the address: `200:1111:2222:3333:4444:5555:6666:7777`. Then the node may also use addresses from the prefix: `300:1111:2222:3333::/64` (note the `200` changed to `300`, a separate `/8` is used for prefixes, but the rest of the first 64 bits are the same). You can find your routed subnet by running `yggdrasilctl getSelf` and finding the `IPv6 subnet`. It is also logged at Yggdrasil startup. On Linux, something like the following should be sufficient to advertise a prefix and a route to `200::/7` using radvd to a network attached to the `eth0` interface: 1. Enable IPv6 forwarding (e.g. `sysctl -w net.ipv6.conf.all.forwarding=1` or add it to `sysctl.conf`) 2. `ip addr add 300:1111:2222:3333::1/64 dev eth0` or similar — replacing `300:1111:2222:3333::` with your routed subnet from `yggdrasilctl getSelf` — to assign an address for the router to use in that prefix, where the LAN is reachable through `eth0` 3. Install/run `radvd` with something like the following in `/etc/radvd.conf` — again, replacing the `300:1111:2222:3333::` with your routed subnet: ``` interface eth0 { AdvSendAdvert on; prefix 300:1111:2222:3333::/64 { AdvOnLink on; AdvAutonomous on; }; route 200::/7 {}; }; ``` Note that a `/64` prefix has fewer bits of address space available to check against the node's ID, which in turn means hash collisions are more likely. As such, it is unwise to rely on addresses as a form of identity verification for the `300::/8` address range. ### Generating Stronger Addresses (and Prefixes) While 128 bits is long enough to make collisions technically impractical, if not outright impossible, it's not unreasonable to think that 64 bits may be attackable at some point if not now. Without going too far into the details, addresses are a truncated hash of a node's public key, with leading `1` bits accumulated and suppressed (along with the inevitable first `0` bit). Thanks to the accumulator, it is possible to brute force generate keys which include more bits of the node's ID in the node's IPv6 address, thereby making collisions more difficult. This can partially mitigate the fact that IPv6 addresses are only 128 bits long, and, more importantly, that prefixes are a mere 64 bits, 16 bits of which are sacrificed to the `200::/7` prefix and 1-byte accumulator in either case. In short, if you plan to advertise a prefix, or if you want your address to be exceptionally difficult to collide with, then it is strongly advised that you burn some CPU cycles generating a harder-to-collide set of keys, using the following tool: ``` go run ./cmd/genkeys ``` This continually generates new keys and prints them out each time a new best set of keys is discovered. These keys may then be manually added to the configuration file. --- ## File: configurationref.md --- sitemap: true tags: dontlink --- # Configuration Reference The configuration file contains the following options: ### `Peers` A list of outbound peering connections to make. Peers are specified in URL format. The following types of peers are supported: * `tcp://1.1.1.1:1234` (TCP) * `tls://1.1.1.1:1234` (TCP+TLS) * `quic://1.1.1.1:1234` (QUIC+TLS) * `socks://2.2.2.2:2345/1.1.1.1:1234` (TCP via SOCKS, i.e. `tcp://1.1.1.1:1234` via the proxy at `2.2.2.2:2345`) * `sockstls://2.2.2.2:2345/1.1.1.1:1234` (TCP+TLS via SOCKS, i.e. `tls://1.1.1.1:1234` via the proxy at `2.2.2.2:2345`) * `unix:///path/to/sock.sock` (UNIX) * `ws://1.1.1.1:1234` or `ws://1.1.1.1:1234/path` (WebSockets, Yggdrasil 0.5.7 or later only) * `wss://1.1.1.1:1234` or `wss://1.1.1.1:1234/path` (WebSockets+TLS, Yggdrasil 0.5.7 or later only) Additional settings can optionally be added as query-string parameters to the end of the URL: * `password=PASSWORD` — set this only for peers that require a shared secret/password to connect, the password must match the remote side or the connection will fail, limited to 64 characters * `key=PUBLICKEY` — pin the specified public key for this peer, this will cause the connection to fail if the remote side's public key does not match what you expect * `maxbackoff=DURATION` — control what the maximum backoff/retry time will be if the peering goes down, format like `30s` for seconds or `1m` for minutes * `sni=domainname.com` - set the Server Name Indication (SNI) for TLS peering connections to a different name (TLS and QUIC only) ### `InterfacePeers` Like `Peers` above, but sorted into sections representing the outbound network interface used to establish the peering connection. This is only useful on hosts that require a special multi-homed configuration, otherwise you should use `Peers` instead. ### `Listen` A list of listeners to open for accepting incoming connections. Instead of supplying the remote address, you should instead supply a bind address. This would either be `0.0.0.0` for IPv4, `::` for IPv4+IPv6 or the IP address of a network interface on your machine. The following listener types are supported: * `tcp://[::]:1234` (TCP) * `tls://[::]:1234` (TCP+TLS) * `quic://[::]:1234` (QUIC+TLS) * `unix:///path/to/sock.sock` (UNIX) * `ws://[::]:444` (WebSockets, Yggdrasil 0.5.7 or later only) Additional settings can optionally be added as query-string parameters to the end of the URL: * `password=PASSWORD` — optionally require a password to connect to this listener, the connecting node's password must match or the connection will fail, limited to 64 characters ### `MulticastInterfaces` Controls which interfaces to enable or disable multicast peer discovery on. The default varies by platform. Each multicast interface block has the following options: * `Regex` — match the names of specific interfaces, i.e. `eth.*` for matching all network interfaces starting with `eth` * `Beacon` — controls whether this node should advertise its presence to nearby devices * `Listen` — controls whether this node should attempt to connect to other nearby nodes that are advertising their presence * `Port` — sets the port number for the TLS listener that is automatically opened for each matched interface, or `0` for a random port * `Password` — optionally sets a password, only other nodes that have the same password configured will discover and connect to each other automatically * `Priority` — controls whether peerings made to a node over this interface should take predecence over peerings made *to the same node* over other interfaces, lower numbers are higher priority, i.e. for preferring ethernet over Wi-Fi ### `AllowedPublicKeys` A list of public keys from which your node will allow incoming peering connections. If public keys are specified, whitelisting is enabled and only nodes with those public keys will be able to peer. If no public keys are specified in this section then peering connections will be allowed as per the `Listen` and/or `MulticastInterfaces` configuration. **NOTE:** This is not a firewall and does not control who can send you traffic over the Yggdrasil Network or reach open ports and services on your machine. For that you need an IPv6 firewall. ### `GroupPassword` Introduced in Yggdrasil 0.5.14, the group password allows forming a closed network on top of the wider network. When the group password is set, session traffic can only be exchanged with other nodes that have the same group password configured. Traffic to or from other Yggdrasil nodes that don't share a group password is dropped. Longer passwords are better from a security perspective, but the password is hashed and used as a handshake salt, it is never sent over the wire. Peering connections are not affected by the group password. Nodes continue to act as routers and will forward traffic for other nodes regardless. When the group password is set, you will no longer be able to reach services on the public testnet. ### `IfName` Determines which TUN interface to use. The default is set to `auto` which will try to set up a TUN automatically. If set to `none`, TUN will be disabled and the node will run in headless router-only mode. On Linux, you can use this setting to give your Yggdrasil TUN interface a unique/persistent name, i.e. `ygg0`, if desired. ### `IfMTU` The MTU of the interface. ### `NodeInfoPrivacy` Whether or not the node info should automatically include build information, i.e. the operating system and architecture and the Yggdrasil build version. If privacy is enabled, the node info will not contain this information. ### `PrivateKey` The private key for this node, specified as a hexadecimal string. If not specified, a random private key will be generated on startup. ### `PrivateKeyPath` The path to a file containing the private key for this node. This allows storing the private key in an external file instead of embedding it directly in the configuration file. If both `PrivateKey` and `PrivateKeyPath` are specified, `PrivateKeyPath` takes precedence. A key or keypair can be generated with: ``` openssl genpkey -algorithm Ed25519 -out private.key -outpubkey public.key ``` ### `NodeInfo` A free-form section that the node operator can use to put JSON-formatted metadata that may be made available to other nodes. --- ## File: developers.md --- sitemap: true tags: dontlink --- # Developers Yggdrasil is written in Go. All of our source code is [available on GitHub](https://github.com/yggdrasil-network/yggdrasil-go). The codebase is fairly small and easy to navigate. We welcome contributions, either in the form of [Pull Requests](https://github.com/yggdrasil-network/yggdrasil-go/pulls) or [Issues](https://github.com/yggdrasil-network/yggdrasil-go/issues). As this is a largely hobbyist project at this stage, it may take some time for us to get around to reviewing PRs/issues. ## Platforms Yggdrasil has been tested on a number of platforms (including Linux, Windows, macOS, FreeBSD, OpenBSD and Ubiquiti EdgeRouter). There are also packages available for a number of distributions/platforms. --- ## File: documentation.md --- sitemap: true logo: iconoir/book.svg --- # Documentation The following pages will help to get started with Yggdrasil: ### [ Install the router software](installation.md) ### [ Generating and editing a configuration file](configuration.md) ### [ Configuration file reference](configurationref.md) ### [ Find public peers](https://publicpeers.neilalexander.dev) ### [ Try public services](services.md) ### [ Advanced peering information](advanced-peering.md) --- ## File: faq.md --- sitemap: true logo: iconoir/chat-bubble-question.svg --- # FAQ ### Why Yggdrasil? Yggdrasil was created in order to build a decentralised routing scheme for mesh networks that can potentially operate at a global scale, motivated in particular by significant performance and scaling issues that were present in [cjdns](https://github.com/cjdelisle/cjdns) at the time. However, Yggdrasil is not a fork — it is a separate standalone project. See the [About](about.md) page for more information around the problems we are trying to solve. ### Is Yggdrasil safe? All traffic sent across the Yggdrasil Network is encrypted end-to-end, such that it cannot be decrypted or read by any intermediate nodes and can only be decrypted by the recipient for which it was intended. However, it is still a public network, therefore you should take adequate precautions when using Yggdrasil, such as using a firewall and not exposing services you do not want others to be able to reach. We also feel that it is important to highlight that, even though Yggdrasil is using industry-standard cryptographic implementations from the Go standard library, our codebase has not been officially externally audited. ### Is Yggdrasil stable? Yggdrasil is relatively stable and very rarely crashes, although our official stance is that it is still alpha software and comes with all of the usual warnings. You should expect things to not be wholly smooth in all cases and therefore you should probably not run any mission-critical or life-and-death workloads over Yggdrasil at this time. You should also make sure that you stay up-to-date as often as possible with the latest versions to ensure that your node continues to be compatible as we make protocol changes. ### Is Yggdrasil anonymous? No, it is not a goal of the Yggdrasil project to provide anonymity. Direct peers over the Internet will be able to see your IP address and may be able to use this information to determine your location or identity. Multicast-discovered peerings on the same network will typically expose your device MAC address. Other nodes on the network may be able to discern some information about which nodes you are peered with due to debug information currently exposed on the network, although the protocol design does not depend upon much of this. ### Will my machine be exposed to other users of the network? Typically yes, you will be routable from other nodes on the network. If you want to restrict incoming connections to your machine, you should use an IPv6 firewall. The steps for this will vary from platform to platform. #### Linux Assuming your TUN/TAP adapter is named `tun0`: ##### with `ip6tables` ``` ip6tables -A INPUT -i tun0 -m conntrack --ctstate ESTABLISHED,RELATED -j ACCEPT ip6tables -A INPUT -i tun0 -m conntrack --ctstate INVALID -j DROP ip6tables -A INPUT -i tun0 -j DROP ``` ##### with `ufw` ``` # The default of ufw is to block all incoming connections # The following blocks incoming connections if the default has been set to allow by: # ufw default allow ufw deny in on tun0 proto ipv6 ``` #### Windows (with Windows Firewall) Windows, by default, should classify the TAP adapter as a "Public Network". Configure Windows Firewall to prevent incoming connections on Public networks. #### macOS (with built-in firewall) macOS has an application firewall, therefore any firewall policies applied on other interfaces will also apply to the Yggdrasil interface. ### Can I run an Yggdrasil router without a TUN interface? Yes, you can set the `IfName` configuration setting to `"none"`. This will prevent Yggdrasil from creating a TUN interface. You will be able to create and accept peering connections and will continue to route traffic on behalf of your peers, but you will not be reachable from within the Yggdrasil Network, nor will you be able to send traffic into the network either. In this mode, other users on the network will receive no response if they try to reach or ping your node's Yggdrasil IPv6 addresses. ### Does Yggdrasil require IPv6? Your system must be IPv6-enabled in order to send or receive traffic to/from the Yggdrasil Network, which just about all modern operating systems are. While Yggdrasil does transport only IPv6 traffic internally, you do not need an IPv6 internet connection to peer with other Yggdrasil users. You can peer with other Yggdrasil nodes over either IPv4 or IPv6. ### Will my node route traffic on behalf of other nodes? If you have peerings to more than one node, your node can potentially route traffic on behalf of other network users. If you have only peerings to a single node, you will typically not route traffic, although you may still handle some occasional protocol messages. Keep this in mind if you are restricted by data usage caps. ### Will Yggdrasil conflict with my network routing? Yggdrasil uses the `0200::/7` range, which is a range deprecated by the IETF. It has been deprecated since 2004, pending changes to an RFC which simply never materialised all these years later. It was decided to use this range instead of `fc00::/7` (which is more typically allocated to private networks) in order to prevent conflicts with existing ULA ranges. As long as you are not using this deprecated address range on your network, you will not experience any routing conflicts. ### Can the network be crawled? Currently it is possible to crawl the network by querying the debug query handlers of remote nodes. This is how the [network map](http://51.15.204.214) and popularity contest are generated today, allowing us to observe how the network scales. However, these endpoints are not required for the network to operate and will definitely be removed in a future version — certainly before a potential version 1.0 release. ### I've just installed Yggdrasil and I can't ping anyone. What have I missed? Yggdrasil requires that you configure either a static peer to another Yggdrasil node, or that you discover another Yggdrasil node *on the same subnet* using multicast discovery (which is enabled by default). Without peers, you will be isolated from the rest of the network. If you have not added or discovered any peers, you will not be able to reach beyond your own node. You can check if you have any peers by running `yggdrasilctl getPeers` - peer on port 0 is your own node, ports 1 and above are your active peers. Stuck for peers? Try adding a [public peer](https://github.com/yggdrasil-network/public-peers). ### Does Yggdrasil add or remove peerings automatically? Peerings may be automatically established to nodes on the same subnet if multicast peering is enabled on both nodes, however, Yggdrasil will never add or remove remote peerings automatically over other networks like the Internet. ### I've installed the Yggdrasil Debian package and now I can't find the logs The Debian package installs the Yggdrasil service into systemd, therefore you can query systemd for the logs: - `systemctl status yggdrasil` - `journalctl -u yggdrasil` ### I've modified the configuration file but nothing has changed Yggdrasil only loads the configuration at startup. Restart the Yggdrasil process or service to load the new configuration. If you are troubleshooting peering connections, check the logging output and/or examine the output of `yggdrasilctl getPeers` to see if any peers are connected. ### I'm running Yggdrasil on a machine that is directly reachable from the Internet. Does this mean anyone can peer with me? The default Yggdrasil configuration does not listen on any external ports for incoming peering connections. In order to accept peering connections from other nodes, you must add a listener entry to the `Listen` section of the configuration file. You can bind to any TCP port of your choosing in either plain TCP (e.g. `tcp://[::]:12345`) or in TLS (e.g. `tls://[::]:54321`) mode. You can either limit incoming connections to your host using a firewall by limiting or denying connections to the port specified in your `Listen` configuration option. This is useful if you want to limit peerings from certain IP ranges or on certain interfaces. Alternatively, you can limit who can peer with you by modifying the `AllowedPublicKeys` option in your Yggdrasil configuration. When this list is populated, only the nodes with the specified public keys will be able to establish a peering connection with your node. This is useful if you want to ensure that you can only peer from your own devices or to allow peerings from certain users. When this list is empty, any remote node is allowed to peer with you. ### I am running Yggdrasil from behind a NAT. Will this affect my connectivity? To accept incoming peerings, you will probably need to configure port forwarding on your router/gateway. Yggdrasil listens on the port number specified in the `Listen` setting, so forward this port to the machine that runs Yggdrasil. To use outbound peerings, that is, static peers that have been configured in your `Peers` setting, you will likely not need to change anything. Regardless of whether your peering connections are inbound or outbound, you will be able to accept incoming connections on your Yggdrasil IPv6 addresses. This makes Yggdrasil an effective way to accept incoming connections when you reside behind NATs that you do not control, i.e. carrier-grade NATs (CGNAT). ### Why does my Yggdrasil adapter have an unusually high MTU? Yggdrasil peerings are typically stream-based and therefore don't suffer from fragmentation issues when pushing large amounts of data. By using the largest possible MTU supported by a platform, we can send much more data in each write and the TCP connection will take care of the rest. This also helps somewhat in the reduction of TCP-over-TCP amplification, as there are less control messages to be amplified. This also uses less CPU, as we can send more data for every system call on the TUN/TAP adapter or network socket. System calls often result in context switches by the operating system and are expensive operations, therefore by using an MTU of up to 65535, we can save as many as 42 context switches for each packet - a substantial performance improvement! ### Does Yggdrasil work alongside an existing VPN? Yes, Yggdrasil will work alongside many VPNs on most platforms. Please note that some VPN software (for example, [Mullvad VPN](https://mullvad.net/en/help/using-mullvad-vpn-app/#killswitch) and Cloudflare WARP) tries to prevent traffic leaking by adding firewall rules or blackhole routing table entries. This can interfere with Yggdrasil in some cases. You will need to reconfigure your VPN software to not drop traffic in this way or contact the vendor of the VPN software for support, as we are unable to prevent this from within Yggdrasil. ### Does Yggdrasil work with networks like Tor or I2P? Yggdrasil can peer over Tor or I2P. See [/public-peers/tree/master/other](https://github.com/yggdrasil-network/public-peers/tree/master/other) for public peers. ### Is there any benefit to being the "root node" of the network spanning tree? No. At worst, the root node may be used in worst-case-scenario paths between other nodes in the absence of being able to determine better routes, but this is not advantageous. --- ## File: implementation.md --- sitemap: true tags: dontlink --- # Implementation The public Yggdrasil Network is a testbed overlay network running the Yggdrasil routing protocol. All network nodes are userspace software routers that run under a single process. The router optionally provides a virtual TUN adapter to the host operating system which allows sending and receiving IPv6 traffic over the Yggdrasil Network. Peering connections between these nodes are established over local area networks, point-to-point links or the Internet using mainly TCP/TLS connections. There are a number of [Public Peers](https://publicpeers.neilalexander.dev) that can be used to join the public network. Implementing Yggdrasil as an overlay network allows us to test the protocol and routing scheme at scale relatively easily, as the user-space router can easily run on most computers. Users also do not need to be physically close to one another in order to join or test the network. Users can just download the software and establish some peerings over the Internet or other networks. However, the Yggdrasil design does not constrain it to only being implemented as an overlay network — it could also be implemented as a native routing protocol with physical links instead. ### How is Yggdrasil secured? In order to ensure that traffic is private as it is routed across other network nodes, all traffic is end-to-end encrypted at all times. Even plain-text application traffic will be encrypted using the destination node's public key, ensuring that intermediate nodes cannot snoop on the contents of traffic being forwarded through the network. It is possible for anyone to join the public Yggdrasil Network and it should therefore be considered as an untrusted network, similar to a public Wi-Fi network or a direct Internet connection. An IPv6-capable firewall that blocks unexpected incoming traffic is highly recommended in order to prevent services on your machine from being accidentally exposed to all users of the Yggdrasil Network. ### How do nodes peer with each other? Network nodes establish peerings either in one of two ways: 1. Manually by the user. Any node can be configured to accept peering connections and can establish outbound connections to other listening nodes. These are referred to as "static peerings" in that they are present in the configuration file and do not typically change at runtime. 2. Link-local multicast discovery. Nodes can optionally advertise their presence on the local network to other listening nodes, which will then attempt to establish peerings automatically. For the most part, this allows any two nodes that are connected together with an IP link to automatically discover each other and create a peering connection in a "plug and play" fashion. It is important to note that Yggdrasil nodes **never** establish new peerings with remote (that is, non-multicast-discovered) nodes automatically. Yggdrasil intentionally has no concept of peer exchange, as is often found in other overlay and DHT designs, and we have no plans at this time to add it. This is because it is the goal of the Yggdrasil protocol to find the best possible paths using only the set of links that are already available. It is therefore essential that we strictly do not make any assumptions about the network topology underneath the peerings, nor do we assume that any two nodes would be able to establish a direct link on demand. In real-world networks with physical links, automatic establishment of new peering links between arbitrary pairs of nodes would simply not be possible. ### How are nodes identified? In the Yggdrasil design, a node's true identity is its public key. The current overlay implementation generates an IPv6 address based on the truncated public key. Translation between IPv6 addresses and partial public keys, as well as searching the network based on those keys, is performed transparently by the Yggdrasil router, therefore all you need to know in order to communicate with a remote node is the IPv6 address it has generated. Domain Name System (DNS) and other name/service lookup mechanisms are specifically out of scope for the project and there is no "official" DNS system that is endorsed for use on the Yggdrasil Network, although some third-party projects attempting to solve this problem are indeed available. ### Which problems exist today? The Internet doesn't conform to a well-defined topology. This has largely happened over time - as the Internet has grown, more and more networks have been "bolted together" with peering arrangements between service providers. This gives us some unavoidable problems: 1. The routing tables that hold a "map" of the Internet are huge and inefficient, as every provider has to relay information about IP prefixes belonging to all other providers 1. There isn't really any way for a computer to know where it is located on the Internet relative to anything else — most machines are only aware of a "default gateway" 1. It's difficult to examine where a packet will go on its journey from source to destination without actually sending it These problems have been somewhat mitigated (but not really solved) through centralisation. Rather than your computers at home holding a copy of the global routing table, your service provider does so on your behalf. Your computers and network devices are configured just to "send traffic upstream" and to let your provider decide where it goes from there. ISP networks are also typically structured in design and often hierarchical in nature, and as a result, many existing routing protocols have been designed with this in mind. Some optimisations such as prefix aggregation are used to try and reduce the number of routing entries that a provider must send out into the world. These protocols are usually not suitable for use in a network where the topology is not well defined or changes frequently — a wireless mesh network, for example, therefore it has been very difficult in the past for communities to build their own wireless mesh infrastructure on an ad-hoc basis. ### What does Yggdrasil do differently? Yggdrasil takes a very different approach to sharing routing knowledge. Rather than distributing address ranges as paths through centrally assigned autonomous systems, Yggdrasil instead builds up a single distributed global network topology. A spanning tree is used to provide synchronisation and to allow nodes to allocate themselves a set of tree coordinates, which are used to exchange and establish bootstrap and path setup messages. Nodes then exchange bloom filters which contain information about which keyspace neighbours are reachable through each node. Intermediate nodes then populate their routing tables with these paths, enabling nodes to forward packets closer to their destination public key. In addition, nodes can pathfind using the spanning tree routing to establish a path that is likely shorter than the path through keyspace. The typically more direct source route will continue to be used for as long as it is available and will fall back to keyspace routing if the tree-routed path breaks. Cryptographic signatures are used to secure protocol messages against tampering or forgery. ### What are the benefits? There are a number of benefits to a routing scheme such as this: 1. Devices need to only maintain a comparatively small amount of state in order to function and to be able to forward packets — there is no need for any Yggdrasil node to maintain "full routing tables" like in BGP, and most nodes only have a handful of routing table entries in total 1. Paths are discovered and built through the network automatically, so manual configuration of routing entries is not required — the only configuration needed is the peering connections between nodes themselves 1. The network can setup and tear down paths quickly without needing to discard all routing state, which helps significantly in handling node mobility events without dropping many packets if at all 1. We can bridge reliable/static networks very easily with dynamic/non-static networks without needing to flood large amounts of state 1. Networks automatically form when any two or more Yggdrasil nodes are connected to each other, even if those connections are entirely ad-hoc in nature, which allows building true wireless mesh networks 1. Sparse routing knowledge and only small amounts of protocol traffic should mean that Yggdrasil is able to efficiently scale to very large networks ### Does Yggdrasil have link metrics? As a decentralised routing protocol design, we believe it is important that routing decisions are only ever made using information that can be securely and independently verified by any given node in a low-cost fashion. We therefore consider most interactive link quality metrics to be out-of-scope at this time, although this will likely change in the future as the protocol becomes more mature. We are aware of the fact that this, combined with the ability to freely and easily create peerings over the Internet, means that suboptimal peerings are likely to appear on the public Yggdrasil testbed network. Network congestion is managed automatically at each node using a form of fair packet queuing. This attempts to balance traffic flows between different nodes equally where possible, as well as ensuring that single nodes cannot saturate all available link bandwidth over a given peering or set of peerings. This also helps to keep overall network latency down where possible. --- ## File: index.md --- tags: dontlink sitemap: true --- Yggdrasil is a new experimental compact routing scheme. It is designed to be a future-proof and decentralised alternative to the structured routing protocols commonly used today on the Internet, as well as an enabling technology for future large-scale mesh networks. Yggdrasil is: Scalable Supports large, complex or even Internet-scale topologies Self-healing Network responds quickly to connection failures or mobility events Encrypted Traffic sent across the network is always fully end-to-end encrypted Peer-to-peer Works entirely ad-hoc by design with no built-in points of centralisation Cross-platform Supported on Linux, macOS, Windows, iOS, Android and more The [current implementation](implementation.md) of Yggdrasil is a lightweight userspace software router which is easy to configure and supported on a wide range of platforms. It provides end-to-end encrypted IPv6 routing between all network participants. Peerings between nodes can be configured using TCP/TLS connections over local area networks, point-to-point links or the Internet. Even though the Yggdrasil Network provides IPv6 routing between nodes, peering connections can be set up over either IPv4 or IPv6 networks. This is still an alpha-stage project and there may be some breaking changes in the future. Despite that, Yggdrasil is generally stable enough for day-to-day use and a small number of users have been using and stress-testing Yggdrasil quite heavily for a variety of use cases. If you are interested in or would like to get involved in the Yggdrasil project, start below: [Install](installation.md) and [configure](configuration.md) Yggdrasil on your own computer or router to join the network. Explore the [internal services](services.md) available on the network operated by our users. Visit our [developers](developers.md) page and our [GitHub](https://github.com/yggdrasil-network/yggdrasil-go). Report bugs and problems to us as [GitHub Issues](https://github.com/yggdrasil-network/yggdrasil-go/issues). --- ## File: installation-ios-app.md --- tags: dontlink sitemap: true --- # Installing on iOS Yggdrasil is supported on iOS but there are currently no prebuilt releases available. The source code is [available here](https://github.com/yggdrasil-network/yggdrasil-ios). --- ## File: installation-linux-deb.md --- tags: dontlink sitemap: true --- # Installing on Debian, Ubuntu, elementaryOS, Linux Mint and similar **These instructions apply to any Debian-based distribution with `systemd`.** Yggdrasil is supported on Debian Linux. Debian binary packages exist to simplify the installation of Yggdrasil. These will also work on any Debian-based distribution, e.g. elementaryOS. ## One-off installation Debian packages are built and are available in the [GitHub Releases](https://github.com/yggdrasil-network/yggdrasil-go/releases). Install the package using `dpkg -i filename.deb`. ## Package install from the S3 repository **NOTE!** The Debian repository below was issued with a new key `1840CDAC6011C5EA` on 2025-11-11. On some platforms, e.g. Raspberry Pi, you may need to start by installing `dirmngr` if it is not already available: ``` sudo apt-get install dirmngr ``` Then import the repository key to your `gpg` keyring and export it to your `apt` keyring: ``` sudo mkdir -p /usr/local/apt-keys gpg --fetch-keys https://neilalexander.s3.dualstack.eu-west-2.amazonaws.com/deb/key.txt gpg --export 1C5162E133015D81A811239D1840CDAC6011C5EA | sudo tee /usr/local/apt-keys/yggdrasil-keyring.gpg > /dev/null ``` Add the repository into your `apt` sources: ``` echo 'deb [signed-by=/usr/local/apt-keys/yggdrasil-keyring.gpg] http://neilalexander.s3.dualstack.eu-west-2.amazonaws.com/deb/ debian yggdrasil' | sudo tee /etc/apt/sources.list.d/yggdrasil.list sudo apt-get update ``` **Note**: The repository also works over HTTPS - you will need to `sudo apt-get install apt-transport-https` and then edit the above URL so that it starts with `https://` instead of `http://` in `/etc/apt/sources.list.d/yggdrasil.list`. Install Yggdrasil: ``` sudo apt-get install yggdrasil ``` ## Package install from your distribution Some Debian-based distributions may have an `yggdrasil-go` package available in their repositories: ``` sudo apt-get install yggdrasil ``` ⚠️ **WARNING**: Distribution packages are often out-of-date! If you are unable to connect to peers, this is probably due to a minor (0.x) version mismatch. Use `apt show yggdrasil` to verify the package version against the latest [GitHub Releases](https://github.com/yggdrasil-network/yggdrasil-go/releases). ## After installation Configuration will be generated automatically into `/etc/yggdrasil.conf` when the package is installed, and the Yggdrasil service will automatically be installed into `systemd`. Enable and start the service after install/upgrade: ``` sudo systemctl enable yggdrasil sudo systemctl start yggdrasil ``` To make configuration changes, modify the `/etc/yggdrasil.conf` file and then restart the Yggdrasil daemon: ``` systemctl restart yggdrasil ``` Read the [Linux platform page](configuration.md) page for further information about Linux platform support. --- ## File: installation-linux-edgeos.md --- tags: dontlink sitemap: true --- # Installing on Ubiquiti EdgeOS Yggdrasil is supported on the Ubiquiti EdgeRouter using the [vyatta-yggdrasil](https://github.com/neilalexander/vyatta-yggdrasil) package. Please note that the package only supports EdgeOS 2.x. Perform installation steps over SSH by connecting to the EdgeRouter as the `ubnt` user, e.g. `ssh ubnt@192.168.1.1`, or another admin-level user if configured. ## Notes - Although your Yggdrasil configuration will persist, the Yggdrasil package itself **does not** survive an upgrade of the EdgeRouter firmware. You must re-add the repository GPG key and re-install the `vyatta-yggdrasil` package after a system upgrade. - After upgrading firmware and reinstalling Yggdrasil, use `load` to reload your configuration and then `commit` to make it effective again. Do not run `save` until after you have reloaded your configuration. ## Install the package Download and copy the package onto the router. Once done, log into the router via SSH and use `dpkg` to install it: ``` sudo dpkg -i vyatta-yggdrasil-x.x.xxx-mipsel.deb ``` ## Generate configuration Configuration for Yggdrasil is generated automatically when you create an interface, e.g. as `tun0`: ``` configure set interfaces yggdrasil tun0 commit save ``` At this point, Yggdrasil will start running using default configuration, which includes automatic peer discovery of other Yggdrasil nodes on the same network using multicast. ## Configuration Once you have generated a configuration file, as above, then you should make configuration changes (like [adding peers](https://github.com/yggdrasil-network/public-peers)) by editing the `/config/yggdrasil.tun0.conf` file. For example, if using `tun0`: ``` vi /config/yggdrasil.tun0.conf ``` To make configuration changes effective, restart Yggdrasil: ``` restart yggdrasil tun0 ``` ## Masquerade If you want to allow other IPv6 hosts on your network to communicate through yggdrasil, you can configure an IPv6 masquerade rule. All traffic sent from other hosts on the network through the Yggdrasil interface will be NAT'd. For example: ``` configure set interfaces yggdrasil tun0 masquerade from xxxx:xxxx:xxxx::/48 commit save ``` If you have multiple IPv6 subnets, then they can be configured individually by setting multiple `masquerade from` source ranges. Both private/ULA and public IPv6 subnets are acceptable. ## Default Firewall Config Use this as an example firewall configuration, which will allow outgoing connections but prevent unexpected incoming ones, with the exception of ICMPv6 which will be allowed, e.g. if using `tun0`: ``` configure set firewall ipv6-name YGG_IN default-action drop set firewall ipv6-name YGG_LOCAL default-action drop set firewall ipv6-name YGG_IN rule 10 action accept set firewall ipv6-name YGG_IN rule 10 state established enable set firewall ipv6-name YGG_IN rule 10 state related enable set firewall ipv6-name YGG_IN rule 20 action drop set firewall ipv6-name YGG_IN rule 20 state invalid enable set firewall ipv6-name YGG_IN rule 30 action accept set firewall ipv6-name YGG_IN rule 30 protocol icmpv6 set firewall ipv6-name YGG_LOCAL rule 10 action accept set firewall ipv6-name YGG_LOCAL rule 10 state established enable set firewall ipv6-name YGG_LOCAL rule 10 state related enable set firewall ipv6-name YGG_LOCAL rule 20 action drop set firewall ipv6-name YGG_LOCAL rule 20 state invalid enable set firewall ipv6-name YGG_LOCAL rule 30 action accept set firewall ipv6-name YGG_LOCAL rule 30 protocol icmpv6 set interfaces yggdrasil tun0 firewall in ipv6-name YGG_IN set interfaces yggdrasil tun0 firewall local ipv6-name YGG_LOCAL commit save ``` --- ## File: installation-linux-gentoo.md --- tags: dontlink sitemap: true --- # Installing on Gentoo Linux Yggdrasil is hosted in the Gentoo GURU repository as the [net-p2p/yggdrasil-go](https://gitweb.gentoo.org/repo/proj/guru.git/tree/net-p2p/yggdrasil-go) package. ## Package install from the GURU repository The GURU repository has to be enabled using `eselect repository`. ``` sudo eselect repository enable guru ``` And then synchronized with `emerge`: ``` sudo emerge --sync ``` Now, the `net-p2p/yggdrasil-go` package is masked and marked as unstable using the `~amd64` keyword. So we have to unmask it by accepting the keyword, there are two alternatives. 1. If `/etc/portage/package.accept_keywords` is a directory: ``` echo "net-p2p/yggdrasil-go ~amd64" | sudo tee /etc/portage/package.accept_keywords/yggdrasil-go ``` 2. If `/etc/portage/package.accept_keywords` is a file: ``` echo "net-p2p/yggdrasil-go ~amd64" | sudo tee -a /etc/portage/package.accept_keywords ``` Now `net-p2p/yggdrasil-go` can be merged and installed with: ``` sudo emerge --ask net-p2p/yggdrasil-go ``` And you're good to go! ## Making configuration changes Modify the `/etc/yggdrasil.conf` file and then either reload the config: 1. OpenRC ``` rc-service yggdrasil reload ``` 2. systemd ``` systemctl reload yggdrasil ``` ... or restart the Yggdrasil daemon altogether: 1. OpenRC ``` rc-service yggdrasil restart ``` 2. systemd ``` systemctl restart yggdrasil ``` ## After installation Read the [Linux platform page](configuration.md) page for further information about Linux platform support. --- ## File: installation-linux-openwrt.md --- tags: dontlink sitemap: true --- # Installing on OpenWrt `yggdrasil` v0.4+ packages are available in OpenWRT since 17.01! To configure Yggdrasil with the LuCI web interface, install the package `luci-proto-yggdrasil`. ## Configuration Use the LuCI web interface to configure Yggdrasil, see the "Network" section. Alternatively, you can configure Yggdrasil with just a command line. To show currently configured options, run the following command: ``` uci show yggdrasil ``` To add a new peer: ``` uci add yggdrasil peer uci set yggdrasil.@peer[-1].uri='tcp://1.2.3.4:5678' uci commit /etc/init.d/yggdrasil restart ``` ## OpenWrt Yggdrasil on Matrix Please stop by `#yggdrasil-openwrt:matrix.org` to join the community development channel. ## NodeInfo enabled by default The Yggdrasil daemon will provide some basic NodeInfo information to the mesh by default. This can be disabled by configuring the section in `/etc/config/yggdrasil` or LuCI admin. This means the following example can be queried by others in the network: ``` "NodeInfo": { "kernel": "4.14.123", "hostname": "OpenWrt", "model": "Globalscale Marvell ESPRESSOBin Board", "board_name": "globalscale,espressobin" } ``` --- ## File: installation-linux-other.md --- tags: dontlink sitemap: true --- # Installing manually on Linux Yggdrasil is supported on Linux. ## Build from source Linux has most of the tools needed to build Yggdrasil from source - you just need to install the Go toolchain. Yggdrasil requires Go 1.11 as a minimum. - Install [the latest version of Go](https://golang.org/dl/) for your platform - Using [godeb](https://github.com/niemeyer/godeb) to install Go is recommended for Debian-based distributions Clone the repository and build: ``` cd /path/to git clone https://github.com/yggdrasil-network/yggdrasil-go ``` Build Yggdrasil: ``` cd /path/to/yggdrasil-go ./build ``` The build will produce `yggdrasil` and `yggdrasilctl` binaries - copy these into a suitable location: ``` sudo cp {yggdrasil,yggdrasilctl} /usr/local/bin ``` #### Debug builds You can create a debug build by running `./build -d` instead of `./build`. Debug builds contain profiling code as well as additional debugging symbols. They are likely to be larger files as a result. ## Install systemd service systemd service scripts are included in the `contrib/systemd/` folder so that it runs automatically in the background (using `/etc/yggdrasil.conf` for configuration). Create the `yggdrasil` group on your system - the `systemd` service will run with this group: ``` sudo groupadd --system yggdrasil ``` Copy the service files: ``` sudo cp contrib/systemd/yggdrasil.service /etc/systemd/system sudo systemctl daemon-reload ``` Enable and start Yggdrasil: ``` sudo systemctl enable yggdrasil sudo systemctl start yggdrasil ``` Once installed as a systemd service, you can read the `yggdrasil` output using `systemctl` or `journalctl`: ``` systemctl status yggdrasil journalctl -u yggdrasil ``` ## Generate configuration Generate an initial Yggdrasil configuration file: ``` sudo yggdrasil -genconf > /etc/yggdrasil.conf ``` You can make changes to this file as described in the [Configuration](configuration.md) page. ## After installation Read the [Linux platform page](configuration.md) page for further information about Linux platform support. --- ## File: installation-linux-rpm.md --- tags: dontlink sitemap: true --- # Installing on Red Hat Enterprise Linux, Fedora, CentOS and similar **These instructions apply to any RPM-based distribution with `systemd`.** RPM binary packages exist to simplify the installation of Yggdrasil. These will also work on any other RPM-based distribution. ## Install RPM package from COPR repository There's a [Fedora COPR repository](https://copr.fedorainfracloud.org/coprs/neilalexander/yggdrasil-go/) available, which provides recent versions of Yggdrasil for some RPM-based distributions. ### Fedora Installation on Fedora is easy as: ```bash dnf copr enable neilalexander/yggdrasil-go dnf install yggdrasil ``` ... and you're ready to go! ## Making configuration changes Modify the `/etc/yggdrasil.conf` file and then either restart the Yggdrasil daemon: ``` systemctl restart yggdrasil ``` ## After installation Read the [Linux platform page](configuration.html) page for further information about Linux platform support. --- ## File: installation-macos-other.md --- tags: dontlink sitemap: true --- # Installing manually on macOS Yggdrasil is supported on macOS. ## Build from source macOS has most of the tools needed to build Yggdrasil from source - you just need to install the Go toolchain. Yggdrasil requires Go 1.11 as a minimum. - Install [the latest version of Go](https://golang.org/dl/) for your platform Clone the repository and build: ``` cd /path/to git clone https://github.com/yggdrasil-network/yggdrasil-go ``` Build Yggdrasil: ``` cd /path/to/yggdrasil-go ./build ``` The build will produce `yggdrasil` and `yggdrasilctl` binaries. System Integrity Protection in macOS prevents you from copying files into `/usr/bin`, therefore you should install into `/usr/local/bin`: ``` sudo cp {yggdrasil,yggdrasilctl} /usr/local/bin ``` #### Debug builds You can create a debug build by running `./build -d` instead of `./build`. Debug builds contain profiling code as well as additional debugging symbols. They are likely to be larger files as a result. ## Install launchd service launchd service scripts are included in the `contrib/macos/` folder so that it runs automatically in the background (using `/etc/yggdrasil.conf` for configuration). Copy the service files: ``` sudo cp contrib/macos/yggdrasil.plist /Library/LaunchDaemons/ ``` Enable and start Yggdrasil: ``` sudo launchctl load /Library/LaunchDaemons/yggdrasil.plist sudo launchctl start /Library/LaunchDaemons/yggdrasil.plist ``` Once installed as a launchd service, you can read the `yggdrasil` output in the following files: ``` tail -f /tmp/yggdrasil.stdout.log tail -f /tmp/yggdrasil.stderr.log ``` ## Generate configuration Generate an initial Yggdrasil configuration file: ``` sudo yggdrasil -genconf > /etc/yggdrasil.conf ``` You can make changes to this file as described in the [Configuration](configuration.md) page. --- ## File: installation-macos-pkg.md --- tags: dontlink sitemap: true --- # Installing using the macOS installer Yggdrasil is supported on macOS. Download the macOS `.pkg` file from [GitHub Releases](https://github.com/yggdrasil-network/yggdrasil-go/releases). ## Install using Finder Locate the downloaded `.pkg` installer in Finder. Right-click it and click Open. Step through the installer as usual. Once completed, the Yggdrasil configuration will have automatically been generated, the `launchd` service will have been installed and the service will be running. ## Install using Terminal Open Terminal.app and install the package: ``` sudo installer -pkg /path/to/yggdrasil-xxx-macos.pkg -target / ``` Once completed, the Yggdrasil configuration will have automatically been generated, the `launchd` service will have been installed and the service will be running. ## Managing the Yggdrasil service Yggdrasil runs under `launchd` so it will run automatically at startup and will restart if the process is killed. To stop the service or prevent it from starting automatically, use `launchctl` to unload the service: ``` sudo launchctl unload /Library/LaunchDaemons/yggdrasil.plist ``` To start it again, load the service: ``` sudo launchctl load /Library/LaunchDaemons/yggdrasil.plist ``` --- ## File: installation-windows.md --- tags: dontlink sitemap: true --- # Installing using the Windows installer Yggdrasil is supported on Windows on a **best effort basis only**. You can [download the latest installer from GitHub](https://github.com/yggdrasil-network/yggdrasil-go/releases). On Windows 7 and Server 2008 R2, you must install hotfix KB2921916 before installing Yggdrasil: - [KB2921916 for 64-bit systems](https://download.wireguard.com/windows-toolchain/distfiles/Windows6.1-KB2921916-x64.msu) - [KB2921916 for 32-bit systems](https://download.wireguard.com/windows-toolchain/distfiles/Windows6.1-KB2921916-x86.msu) ## Warning The Windows port does not currently have a maintainer and is therefore not as well tested or developed as other platforms. ## TUN driver Starting with version 0.3.13, Yggdrasil on Windows uses the Wireguard TUN driver. If this is not installed on the system already, it will be installed automatically by the Yggdrasil installer. For this reason, it is important that you use the correct installer for your architecture - make sure to use the `x64` installer on 64-bit Windows and the `x86` installer on 32-bit Windows. Please note that the OpenVPN TAP driver is **no longer supported**. Once Yggdrasil is started, a new virtual network adapter will be created called `Yggdrasil` by default, although this can be renamed using the `IfName` option in the configuration file (below). The virtual network adapter will _not_ be visible on the system when Yggdrasil is not running. ## Configuration The Yggdrasil installer will automatically generate an `yggdrasil.conf` configuration file, if one does not exist, in: ``` %ALLUSERSPROFILE%\Yggdrasil\yggdrasil.conf ``` ## Windows Service Yggdrasil is installed as a Windows service that starts automatically with Windows. You can start, stop and restart Yggdrasil using the Services MMC snap-in (`services.msc`) or, in more recent versions of Windows, the "Services" tab in Task Manager. You will need to restart the Yggdrasil service after each change to the configuration file. ## Windows Firewall Windows Firewall may prompt for the Yggdrasil process to allow incoming or outgoing connections. If so, you should allow this or Yggdrasil may not be able to establish peerings correctly. Note that Yggdrasil, by default, does allow incoming traffic over the `Yggdrasil` virtual adapter, therefore you may wish to designate the `Yggdrasil` virtual network adapter as a public network in the Windows Firewall so that unexpected incoming connections are blocked automatically. If you do, pay particular attention to ensure that file sharing (SMB), remote procedure call (RPC) or remote desktop (RDP) services are not allowed on public networks unless you explicitly need them to be accessible from remote Yggdrasil hosts. ## yggdrasilctl The `yggdrasilctl` utility is also installed into the same location above. You can query Yggdrasil's runtime state using this tool using a Command Prompt or PowerShell command line, e.g. ``` "C:\Program Files\Yggdrasil\yggdrasilctl.exe" getPeers ``` --- ## File: installation.md --- sitemap: true tags: dontlink --- # Installation Yggdrasil can be downloaded for major platforms from our [GitHub Releases](https://github.com/yggdrasil-network/yggdrasil-go/releases) page. Additionally, installation guides are available for the following platforms/distributions. --- 🚨 **Please remember to check for Yggdrasil updates regularly.** 🚨 Yggdrasil does not have a built-in method of notifying you when new versions are available. You may want to subscribe to the [GitHub Releases Atom feed](https://github.com/yggdrasil-network/yggdrasil-go/releases.atom) or consider [watching the GitHub repository](https://github.com/yggdrasil-network/yggdrasil-go) (a "Custom" watch can be used to subscribe to release notifications only). --- ### Linux Yggdrasil is well supported on Linux. There are a number of distribution packages and additional installation instructions available: - [Debian, Ubuntu, elementaryOS, Linux Mint and similar](installation-linux-deb.md) - [Red Hat Enterprise Linux, Fedora, CentOS and similar](installation-linux-rpm.md) - [Gentoo Linux](installation-linux-gentoo.md) - [OpenWrt](installation-linux-openwrt.md) - [Manual install or build from source](installation-linux-other.md) ### macOS Yggdrasil is well supported on macOS. The preferred installation method is the `.pkg` installer: - [macOS `.pkg` installer](installation-macos-pkg.md) - [Manual install or build from source](installation-macos-other.md) ### Windows Yggdrasil works on Windows and [an MSI installer is available](installation-windows.md), but the installer is supported on a best-effort basis only and is not well tested. ### iOS Yggdrasil is supported on iOS with the following applications: - [Yggdrasil for iOS on TestFlight](https://testflight.apple.com/join/jZNsIkRr) ([source code](https://github.com/yggdrasil-network/yggdrasil-ios)) ### Android Yggdrasil is supported on Android with the following applications: - [Yggdrasil for Android](https://github.com/yggdrasil-network/yggdrasil-android/releases) ([source code](https://github.com/yggdrasil-network/yggdrasil-android)) ### FreeBSD Yggdrasil is well supported on FreeBSD and [an official `net/yggdrasil` port](https://www.freshports.org/net/yggdrasil/) is available. ### Ubiquiti EdgeRouter Yggdrasil is well supported on EdgeOS 2.x and [packages are available](installation-linux-edgeos.md). --- ## File: nodeinfo.md --- tags: dontlink --- # NodeInfo Yggdrasil supports advertising a small amount of information publicly to the network. The entire stanza should not exceed 16KB. You should not publish any information that you do not want to be collected by network crawlers or deem to be private. NodeInfo can take any format, although this document outlines some common types for interoperability - please stick to these formats where possible. If your configuration file is in HJSON format (as is standard), then you should specify your NodeInfo in HJSON format and it will be converted to JSON automatically by Yggdrasil when requested. If your configuration file is in JSON format, then you should also specify your NodeInfo in JSON format. The below examples are all in HJSON format. ## Well-known types #### Node build tags These options are automatically populated into NodeInfo therefore you do not need to configure them. These can be unshared by setting the `NodeInfoPrivacy` configuration setting to `true` or by configuring the below values to `null`. ``` NodeInfo: { buildname: yggdrasil buildversion: 0.3.3 buildplatform: darwin buildarch: amd64 } ``` #### Node name A friendly name for the node, which may be displayed on the maps or in GUI clients. This is often specified in fully-qualified domain name (FQDN) format, although this is not essential and free-flowing text can be used instead. ``` NodeInfo: { name: some-name.net } ``` #### Public peering details If you wish to advertise your node as a public node, then you can provide information about how other users can peer with it over other networks. The first level of the `"public"` key should contain the network class, and then each network class should be a list of connection strings in Yggdrasil configuration format. ``` NodeInfo: { public: { internet: [ tcp://a.b.c.d:e tcp://[a:b:c::d]:e ] tor: [ socks://localhost:a/b.c.d.e:f ] } } ``` Currently known classes are `"internet"`, `"tor"`, `"i2p"` and `"cjdns"`. --- ## File: privacy.md --- sitemap: true tags: dontlink --- # Privacy In order to release Yggdrasil on certain platforms, we are obliged to release a Privacy Policy which discusses information usage within Yggdrasil. This document was last updated on the 14th December 2021. ### Overview Yggdrasil is a decentralised application with no central point of registration or communication. You **do not** need to register an account to use Yggdrasil, nor do you need to supply any personal information to the application or to the developers. Yggdrasil deploys **end-to-end encryption** for all traffic crossing the network. This ensures that your traffic will not be readable or modifiable by third parties, including by any other node that is carrying traffic on your behalf. The integrity of this encryption is guaranteed only if you take suitable precautions to protect your private key, which is typically stored in your Yggdrasil configuration file. You must not share it with anyone. ### Network Identity Your identity on the Yggdrasil Network is derived from your cryptographic keypair, which is generated and stored locally on your device. The public key is used to derive your network IPv6 address, which will be used whenever you send or receive any IP traffic across the Yggdrasil Network. You can discard your network IPv6 address/network identity and assume a new one at any time by discarding your keypair and generating a new one. ### Node Information Yggdrasil supports publishing node information by means of the `NodeInfo` section in the configuration file. Node information can be queried by any remote node on the network, even if that remote node is not otherwise exchanging IP traffic with your node. By default, the `NodeInfo` may also contain information about the version of Yggdrasil being run as well as the operating system and processor architecture. You can choose not to publish this information by setting the `NodeInfoPrivacy` option in your configuration file. Otherwise, `NodeInfo` is entirely optional and you can leave it empty. On iOS, this is shown under "Node Info" in the Settings page. You are not obliged to share anything via node information. Any information entered into this section is publicly accessible and may be stored by network crawlers or by any other network user. You should therefore not publish any sensitive information in your `NodeInfo`. ### Peerings When you establish a peering, your node's IPv6 address and public key are made visible to any peers to which you are directly connected. If peering over the Internet or another network, the remote peer may also be able to see your real IP address, and these may be logged by the remote node. If you are concerned about the storage or collection of logging information on a public node, you should contact the operator of that node. If you are in any way concerned about the safety of a public node, or whether a given public node is administered in good faith, you should not attempt to connect to it. ### Yggdrasil for iOS With regards to our iOS application when distributed via TestFlight or the App Store specifically, information collected through TestFlight or the App Store pertaining to usage demographics and/or crash analytics may be made available to the developers of the iOS application by Apple, as outlined in [Apple's own Privacy Policy](https://www.apple.com/uk/legal/privacy/en-ww/). No other information is collected. The Yggdrasil application itself, as well as the accompanying VPN network extension, will not collect any personal or analytic information whatsoever. --- ## File: services.md --- tags: dontlink sitemap: true --- # Services The following services are available on the Yggdrasil Network, courtesy of our community users. If you host a service on the Yggdrasil Network or find that a service is no longer available, please feel free to [open a pull request on GitHub](https://github.com/yggdrasil-network/yggdrasil-network.github.io/edit/master/services.md) ---- ## Commercial services ### IT consultancies - [Thingylabs GmbH](https://yyy.thingylabs.io/) - An IT consultancy for Web, Cloud, and Apps. - `https://yyy.thingylabs.io/` - `http://[22a:bd80:1588:5365:e467:c5fa:6123:5018]/` - [IncogNET LLC](https://incognet.io/) - Privacy and Free Speech Focused ISP - 5Gbps AMD Epyc VPS, Domain Registrar, WireGuard VPN, Etc. - `http://ygg.incognet.io/` - `http://[202:7f4c:a4fe:e85b:4410:21f4:7b8c:99c]/` ---- ## Websites - [Yggdrasil Web directory](http://[21e:a51c:885b:7db0:166e:927:98cd:d186]/) - `http://[21e:a51c:885b:7db0:166e:927:98cd:d186]/` - [Yggdrasil Image-Video-Music Hosting](http://[201:1592:3bff:105:b35f:c25b:4d3:c056]/) - `http://201:1592:3bff:105:b35f:c25b:4d3:c056]/` - `https://imgdump.lol` For Clearnet - [Yggdrasil Map](227:bc24:9a82:e290:7f4a:f992:2ef6:5b34]/) - `http://[227:bc24:9a82:e290:7f4a:f992:2ef6:5b34]/` - [deavmi's homepage](http://[203:75b7:45af:ecca:d641:cd42:38dc:4788]/) - `http://[203:75b7:45af:ecca:d641:cd42:38dc:4788]/` - [HowTo Ygg: Yggdrasil wiki](http://[222:a8e4:50cd:55c:788e:b0a5:4e2f:a92c]/) - `http://[222:a8e4:50cd:55c:788e:b0a5:4e2f:a92c]/` - [Acetone's site mirror](http://[324:71e:281a:9ed3::ace]/) - `http://[324:71e:281a:9ed3::ace]/` - [Nikat's homepage](https://[302:a2a5:dead:ded::a2a5]/) - `https://[302:a2a5:dead:ded::a2a5]/` - [Yggdrasil Forum](http://[21a:34aa:c782:3ad2:1bf8:73f8:141:66e8]) - Forum in yggdrasil, about yggdrasil - `http://[21a:34aa:c782:3ad2:1bf8:73f8:141:66e8]` - [IP and Port Checker](http://[200:56bd:a9e9:c1fa:8f99:1d3c:3c84:6507]) - `http://[200:56bd:a9e9:c1fa:8f99:1d3c:3c84:6507]` - [Services by it's port number](http://[220:73c5:19cd:3cba:de5d:b065:807f:8b67]) - `http://[220:73c5:19cd:3cba:de5d:b065:807f:8b67]` - [Yggdrasil search engine](http://[200:b48d:469e:c7c7:3e13:c41d:ba4d:d2b8]) - `http://[200:b48d:469e:c7c7:3e13:c41d:ba4d:d2b8]` - [Ukrainian community forums](http://[202:68d0:f0d5:b88d:1d1a:555e:2f6b:3148]) - `http://[202:68d0:f0d5:b88d:1d1a:555e:2f6b:3148]` - [Yggdrasil project homepage](http://[300:8101:e046:d91e::5]) - `http://[300:8101:e046:d91e::5]` ---- ## BitTorrent - Yggdrasil-only torrent tracker, operated by jeff: - With DNS: `http://yggtracker.i2p.rocks/` (statistics at `http://yggtracker.i2p.rocks/stats`) - Without DNS: `http://[200:1e2f:e608:eb3a:2bf:1e62:87ba:e2f7]/announce` (statistics at `http://[200:1e2f:e608:eb3a:2bf:1e62:87ba:e2f7]/stats`) - Filters out non-Yggdrasil IP addresses automatically from announcements - Yggdrasil-only torrent tracker: - `udp://[202:68d0:f0d5:b88d:1d1a:555e:2f6b:3148]:6969` - announce - `http://[202:68d0:f0d5:b88d:1d1a:555e:2f6b:3148]:6969` - stats ---- ## Proxy services - Community-driven proxy catalog with configuration examples by [YGGverse](https://github.com/YGGverse/YGGbro): - `http://[316:c51a:62a3:8b9::4]/YGGverse/YGGbro` ### Tor bridges *Note:* If you modified your `torrc` file to exclude groups of non-exit nodes (e.g. using `ExcludeNodes` with country codes, using `ExcludeExitNodes` is fine), Tor will strictly follow the constraints. However because Yggdrasil addresses are not and will not be listed in any IP-to-country databases, Tor cannot guarantee that bridge you entered falls under whatever exclusion policies you specified and will refuse to connect to bridge. In that case you can add `GeoIPExcludeUnknown 0` to your `torrc`. - `Bridge [218:4feb:a509:9db2:2b34:6e7e:e071:5dee]:1991 F805F6B4E5E203EFE2A7FFB1E5042AFE8BD986B4` operated by Marek Küthe ([homepage](https://mk16.de/tor/), [metrics](https://metrics.torproject.org/rs.html#details/F805F6B4E5E203EFE2A7FFB1E5042AFE8BD986B4)) - `Bridge [220:f022:cd6c:22a9:5285:79e2:2e19:b66a]:1991 6580023D474DD3C06920027530C3B5E39B89DC03` operated by Marek Küthe ([homepage](https://mk16.de/tor/), [metrics](https://metrics.torproject.org/rs.html#details/6580023D474DD3C06920027530C3B5E39B89DC03)) - `Bridge [219:a32f:307b:8372:25d3:e1d0:c8fb:d2f6]:1991 49A53936AF2895A1612603AAA3C1CF8A01830157` operated by Marek Küthe ([homepage](https://mk16.de/tor/), [metrics](https://metrics.torproject.org/rs.html#details/49A53936AF2895A1612603AAA3C1CF8A01830157)) - `obfs4 [200:ba50:4b2c:8dc9:9529:38de:5677:57a0]:7917 79F9F7CBD0E2A4458F11B7874008D783BCF5C523 cert=3ues7AA498O9YrQ1wsdWyz3/n3YBXN88wXP8mppkE0lTw1YB6FSlDMkm3Ry6jXlj0phzMg iat-mode=0` or `[200:ba50:4b2c:8dc9:9529:38de:5677:57a0]:7918 79F9F7CBD0E2A4458F11B7874008D783BCF5C523` operated by ValeriusN ([telegram](https://t.me/valeriusN)) - `obfs4 [200:a48e:101d:c12a:b859:ee0e:3b83:382c]:8082 1677AE8B9E02457ED382CCDF80DF26554CD95597 cert=9Rf3PQu2zgcnRPEQd1VSA22X/9MMVpB6n1K9h/OIpvBGHuYj4jpxy2ISlvKdkIujJSzpIg iat-mode=0` operated by biley929 ([GitHub](https://github.com/biley929)) ---- ## IRC ### BonoboNET - Accessible via Yggdrasil at the following servers: - **Preferred:** `y.irc.bnet.eu.org` port `6667` (round-robin DNS entry for all servers listed below) - `219:3cf0:dd1d:47b9:555e:75ac:2ab5:493b` port `6667` - `204:fb3e:d9e:9f20:7af1:27ab:6aed:df32` port `6667` - `200:6f99:2afe:41fd:fc3b:b1f7:af9d:f3a0` port `6667` - Notable channels are `#general`, `#networking` and `#programming` - More information can be found at the [BonoboNET homepage](http://[203:75b7:45af:ecca:d641:cd42:38dc:4788]/projects/bonobonet/) - we're using unrealircd and open to peering ### benisnet - Accessible via Yggdrasil at the following servers: - `203:b00a:1684:860d:880f:ea9c:92dc:fabb` port `6667` ### YGGverse - `202:68d0:f0d5:b88d:1d1a:555e:2f6b:3148` port `6667` - `http://[202:68d0:f0d5:b88d:1d1a:555e:2f6b:3148]:6680` - ZNC bouncer for Yggdrasil, Mycelium, I2P, or Tor channels ### sid - No LIST, very limited commands, focused on privacy and a simple chatting experience. Modeless channels only, prefixed with + as opposed to #. No channel history or logs are kept. - `ygg.strcat.su` port `6667` - `200:a754:c7aa:3f12:5ab:d078:d8d4:b59c` port `6667` ---- ## DNS - `302:db60::53` port `53`, hosted by [Revertron](https://t.me/Revertron), Praha, Czechia - [Alfis](https://github.com/Revertron/Alfis), [AdGuard DNS](https://github.com/AdguardTeam/AdGuardHome) - `300:6223::53` port `53`, hosted by [Revertron](https://t.me/Revertron), Bratislava, Slovakia - [Alfis](https://github.com/Revertron/Alfis), [AdGuard DNS](https://github.com/AdguardTeam/AdGuardHome) - `302:7991::53` port `53`, hosted by [Revertron](https://t.me/Revertron), Saint Petersburg, Russia - [Alfis](https://github.com/Revertron/Alfis), [AdGuard DNS](https://github.com/AdguardTeam/AdGuardHome) - `202:1d4e:724e:de52:8273:e2b5:4988:a9ba` port `53`, non-filtering, hosted by [strcat.su](https://strcat.su) - `[300:7c75:d590:c5d8::100]`, port `53`, hosted by [evasil](https://github.com/evasil/), Melbourne, Australia. Alfis and clearnet, no filters. ---- ## Code Forges ### [Radicle](https://radicle.xyz) Nodes Note: do not use square brackets in host! - `z6MkocYY4dgMjo2YeUEwQ4BP4AotL7MyovzJCPiEuzkjg127@202:f094:502b:1b03:9e0:2c3d:bc8b:428b:8776` ([web](http://[202:f094:502b:1b03:9e0:2c3d:bc8b:428b])), hosted by [Lorenz](https://lorenz.leutgeb.xyz) on a VPS in Germany. - `z6Mkvky2mnSYCTUMKRdAUoZXBXLLKtnWEkWeYQcGjjnmobAU@202:68d0:f0d5:b88d:1d1a:555e:2f6b:3148:8776` * [Selective](https://radicle.xyz/guides/seeder#a-selective-seeding-policy) seed, [mention](https://mastodon.social/@yggverse) to add an exception! - `http://[202:68d0:f0d5:b88d:1d1a:555e:2f6b:3148]:8788` - JSON/API - `http://[202:68d0:f0d5:b88d:1d1a:555e:2f6b:3148]:8780` - Web explorer ### Gitea and Forgejo - [Deavmi's Personal Gitea](http://ygg.old.git.deavmi.assigned.network) - `http://[300:8101:e046:d91e::2]` - [Deavmi's Personal Forejo](http://ygg.new.git.deavmi.assigned.network) - `http://[300:8101:e046:d91e::3]` ---- ## NTP - `202:a2a5:dead:ded:9a54:4ab5:6aa7:1645` port `123`, hosted by [nikat](https://[302:a2a5:dead:ded::a2a5]/) - `223:180a:b95f:6a53:5c70:e704:e9fc:8b8f` port `123`, hosted by mkb2191 - `200:8ce3:6def:9d4d:a976:9dfb:f0a6:91ce` port `123`, hosted by [Unkn0wnCat](https://kevink.dev), stratum 2, [NTP Pool Monitored](https://www.ntppool.org/scores/45.9.61.155) - `201:72f6:9b56:e977:2d40:c7da:667b:f7a0` port `123`, hosted by [lcharles123](https://github.com/lcharles123), Located in US - `ygg.nerdvm.mywire.org` - `200:ee1d:70c7:13ee:3395:2255:6bf0:9c30` port `123`, hosted by [Octopixel](https://github.com/Octopixel40), Located in EU - `205:f771:de8a:d89d:12d4:9263:7902:201a` port `123`, hosted by [Octopixel](https://github.com/Octopixel40), Located in EU ---- ## Minecraft ### Java Edition - `228:39cf:5792:fbd1:d5c7:a750:7ab9:4389` **26.1.2** - Vanilla survival server with minimal mods. The only rule is to not grief. - `201:92e3:d9df:4932:ca24:586a:4475:6e8b` or `mc.ygg.at` **1.21.1** - Vanilla survival server. Minimal rules and plugins. Fight with mobs, build beautiful buildings. Have a good time with your friends. And leave a trace in the history of this server with other users yggdrasil! Site: [web.mc.ygg](http://web.mc.ygg.at) - `203:b2b2:24a0:2e7d:a851:3786:3566:a0a3` **1.21.11** - Vanilla survival server, overworld is desert only. Site is [here](http://[203:b2b2:24a0:2e7d:a851:3786:3566:a0a3]/minecraft/) - `mc.spectresmp.srv` **Java Edition** - SpectreSMP. Online since 2023. Available on Yggdrasil and clearnet. - **SMP** - Classic survival multiplayer with grief protection. Build, explore, and trade knowing your builds are safe. Grief protection enabled, land claiming. - **SMP2** - No protection, but hacked clients are not allowed. ### Minetest - `[203:e93b:9902:9064:5efe:575b:3284:e1d2]:30000` Minetest server hosted by [mittwerk](mittwerk@yggdrasil.link) ---- ## Half-Life [Xash3D / FWGS](https://github.com/FWGS/xash3d-fwgs) servers by [lost+skunk](http://[222:a8e4:50cd:55c:788e:b0a5:4e2f:a92c]/user:skunky) ### Master - `[300:dee4:d3c0:953b::2019]:27010` ### Game servers - `[300:eaff:7fab:181b::e949]:7588` - `[301:f137:d1ac:920e::2019]:27015` - 9 bots, Yggdrasil only ---- ## Hytale - Bivrost — US-East (Residential FTTH) — No mods — Cross-overlay — Best-effort support — Simple rule(s): Minimal griefing. - `202:79eb:f1b7:799a:f8be:8683:1abd:5338` ---- ## Xonotic - Bivrost — US-East (Ashburn VA) — Clearnet and Cross-overlay — Best-effort support - Press **`** within Xonotic and type or paste: **connect [201:ac2f:89eb:2afe:5f3d:9db9:a7e9:2f75]:26000** ---- ## NNCP - `203:5096:b2e:5bf3:b3c8:194a:a64f:dd0d` port `5400`. This is the [quux.org NNCP public relay](https://www.complete.org/quux-org-nncp-public-relay) hosted by [jgoerzen](https://www.complete.org/john-goerzen/). ---- ## iPerf3 for speedtests - [ygg.thingylabs.io/speedtest.html](https://ygg.thingylabs.io/speedtest.html) sponsored by [Thingylabs](https://www.thingylabs.io/) - `iperf3 -6 -c ygg-only.thingylabs.io` - `iperf3 -4 -c ygg-uplink.thingylabs.io` ---- ## Monero Nodes - [XMR.GD](https://xmr.gd/) - Public (Mainnet) Monero Node available on Yggdrasil (And clearnet, Tor, and I2P). Sponsored by [IncogNET](https://incognet.io/) - `ygg.xmr.gd:18089` - `201:2d47:2607:ecaf:2909:2dc5:926d:a8df:18089` ---- ## Reticulum nodes - `y.worcester.rns.novasredes.network` (`300:3dfd:cdb:5b45::8`) port `4242` TCP - [more...](https://github.com/markqvist/Reticulum/wiki/Community-Node-List#yggdrasil) ---- ## nostr - `ws://[31b:6f20:c7f2:3ddf::3221]/` - Yggdrasil only nostr relay ---- ## Blossom - `http://[302:68d0:f0d5:b88d::bdb]/` - request write access by mention [@YGGverse](https://mastodon.social/@YGGverse) or PR to [whitelist](https://codeberg.org/YGGverse/server/src/branch/main/mnt/sdb1/blossom/whitelist.txt) ---- ## Iroh - `http://[202:68d0:f0d5:b88d:1d1a:555e:2f6b:3148]:3340` - public relay ---- ## Rust ### Kellnr The registry for Rust crates * `http://[202:68d0:f0d5:b88d:1d1a:555e:2f6b:3148]:8180` ## Music - [Byteback Music Studio](https://bytebackmusic.org) - `http://[200:16b8:aa57:ab3c:e47e:4bc2:cdb2:a67c]/index.html` --- ## File: _posts/2018-07-13-about-mtu.md --- layout: post title: "About huge MTUs in Yggdrasil" date: 2018-07-13 10:24:00 +0100 author: Neil Alexander --- ### That's a very big MTU! You might have noticed that Yggdrasil doesn't conform to the standard MTUs you might have seen elsewhere. Most Ethernet networks sit somewhere around the 1500 byte mark. Less if VPN tunnels are involved due to the overheads of those VPN protocols. So you might have been surprised to see an interface MTU as high as 65535 bytes in your `yggdrasil.conf`! In fact, this is not a mistake. It is very deliberate. The MTU is a configurable option which determines how big a packet should be before you should break out into a new packet. In addition to that, the operating system maintains a link MTU setting for each network adapter - effectively a value that says "packets equal to or smaller than this number of bytes are safe to send on this link in one piece". Any larger than that and the operating system will have to fragment the packet down into smaller ones before sending out onto the wire. With a smaller MTU, you will be forced to re-send the IP headers (and possibly other headers) far more often with every single packet. Those are not only wasted bytes on the wire, but every packet likely requires a new set of system calls to handle. In the case of Yggdrasil, we rely on system calls not just for socket operations but also for TUN/TAP. Each system call requires a context switch, which is a slow operation. On embedded platforms, this can be a real killer for performance - in fact, on an EdgeRouter X, context switching for the TUN/TAP adapter is a greater bottleneck than the cryptographic algorithms themselves! ### Selecting TCP instead of UDP Therefore it is reasonable to surmise that less context switches and less packet headers are better. Using an MTU of 65535 over 1500 packs in almost 43 times more data before the next set of headers. That's almost 1680 bytes saved from IP headers alone over 65535 bytes! But sending a 65535 byte Yggdrasil packet over a link with an MTU of 1500 would require the packet to be fragmented 43 times, right? Instead, Yggdrasil uses TCP connections for peerings. This not only allows us to take advantage of SOCKS proxies (and Tor) in a way that we cannot with UDP, but it also gives us stream properties on our connections instead of being manually forced to chunk UDP packets. In fact, we did this in the past, and it was ugly, and actually worse than TCP performance-wise in many cases. TCP will adjust the window size to match the lower link - in this case a probable 1500 MTU - and will stream the large packet in chunks until it arrives at the remote side in a single piece. For this reason, Yggdrasil never has to care about the MTU of the real link between you and your peers. It just receives a packet up to 65535 bytes, which it then processes and hands off to the TUN/TAP adapter. ### But... TCP over TCP? But that means that you are tunnelling TCP over TCP, I hear you cry. That's crazy talk, surely? The big problem with TCP-over-TCP is that in the event of congestion or packet loss, TCP will attempt to retransmit the failed packets, but if TCP control packets from the inner connection are retransmitted, reordered etc. by the encapsulating TCP connection, this results in a substantial performance drop whilst the operating system throttles down that inner TCP connection to cope with what it believes to be congestion. However, by using large MTUs, and therefore larger window sizes on the inner TCP connection, we send far less TCP control messages over the wire - possibly up to as many as 43 times less - therefore there are far less opportunities for control messages on the inner connection to be affected or amplified by retransmission. This helps to stabilise performance on the inner TCP connections. There are also some other clever things taking place at the Yggdrasil TCP layer. In particular, LIFO queues are used for session traffic, which results in reordering at almost the first sign of any congestion on the encapsulating link. TCP very eagerly backs off in this instance, which helps to deal with real congestion on the link in a sane manner. ### Agreeing on an MTU A big problem we came across was that different operating systems have different maximum MTUs. Linux, macOS and Windows all allow maximum MTUs of 65535 bytes, but FreeBSD only allows half that at 32767 bytes, OpenBSD lower again at 16384 bytes and NetBSD only allowing up to a paltry 9000 bytes! Not to mention that there might also be good reasons for adjusting the MTU by hand, hence the `IfMTU` option in `yggdrasil.conf`. We need a way for any two Yggdrasil nodes to agree on a suitable MTU that works for both parties. To get around this, each node sends its own MTU to the remote side when establishing an encrypted traffic session. Knowing both your own MTU and the MTU of the remote side allows you to select the lower of the two MTUs, as the lower of the two MTUs is guaranteed to be safe for both parties. In fact, you can even see what the agreed MTU of a session is by using `yggdrasilctl getSessions` or by sending a `getSessions` request to the admin socket. ### Using ICMPv6 to signal userspace So what happens if you establish a session with someone who has a smaller MTU configured than yourself? The session negotiation and MTU exchange will allow Yggdrasil to select a lower MTU for the session, but your TUN/TAP adapter on your own side still has the larger of the two MTUs. How do we tell userspace about the new MTU? IPv6 implements a `Packet Too Big` packet type which is designed to facilitate Path MTU Discovery on standard IPv6 networks. If you send a large packet, a node en-route (like a router) can send back an ICMPv6 `Packet Too Big` message to the sender, signifying that the packet that you sent exceeds the largest supported packet size (effectively an upstream link MTU). The sending node can then fragment the packet and resend it in smaller chunks so that it matches that lower MTU on the path. Yggdrasil takes advantage of this behaviour by generating `Packet Too Big` control messages and sending them back to the TUN/TAP adapter when it detects that you have tried to send a packet across an Yggdrasil session that is larger than the agreed MTU. This causes the operating system to fragment the packets down to the MTU size supported by the session and resend them. In addition, the operating system caches this newly discovered MTU for the future so that it fragments correctly for that destination from that point forward. In effect, Yggdrasil "tricks" the operating system into thinking that Path MTU Discovery is *really* taking place on the link. ### Conclusion You will see that Yggdrasil performs a number of tricks to allow flexible MTUs between nodes, and takes advantage of the stream nature of TCP to provide the greatest level of performance and flexibility. There are a number of moving parts to this - the session negotiation, ICMPv6 message generation and the choice of TCP over UDP for peering connections. However, I hope this demystifies some of our choices and why we have encouraged the use of larger MTUs on our traffic sessions. --- ## File: _posts/2018-07-15-remote-access.md --- layout: post title: "Using Yggdrasil for remote access" date: 2018-07-15 22:40:00 +0100 author: Neil Alexander --- ### Replacing the traditional VPN One of my favourite and most common use-cases for Yggdrasil to date has been reaching back to my own machines from remote locations, like from work or wherever I happen to have taken my laptop on a given day. My main point of interest lately has been connecting to my iMac at home using VNC - which happens to be built into macOS - over Yggdrasil. I have found Yggdrasil to be an excellent tool for the job and it effectively replaces my need for a traditional VPN entirely. Some of the benefits of using Yggdrasil for remote access are: 1. End-to-end encryption, which provides transport security for protocols that are normally not very secure out of the box (like VNC or FTP) 1. Superior TCP-over-TCP performance - remarkably better than over OpenVPN or SSH forwarding! 1. Source verifiability, for being able to whitelist based on source IPv6 address and firewall everyone else out 1. Routable from anywhere on the network #### End-to-end encryption All tunnelled traffic over Yggdrasil takes place within encrypted "sessions". A session is established between you and a remote node when you attempt to send traffic to that node. As a part of the session handshake, your public encryption keys are exchanged, which are used to provide complete end-to-end encryption of all encapsulated network traffic. Even plain-text protocols will appear to be encrypted in transit across the Yggdrasil network, ensuring that no intermediate routers or adversaries can spy on your traffic, and making it much safer to use protocols like VNC which may not be robustly secure by themselves. It also means that it is possible to send and receive traffic over Yggdrasil with confidence, without worrying so much about the security of the network in a given location. Open Wi-Fi networks in public places are particularly a nightmare for any kind of connection security, as they are often not protected with wireless encryption, but this is less of a concern with Yggdrasil. #### TCP-over-TCP performance In the past I had tried using OpenVPN and SSH tunnelling as a method of reaching back home by terminating the VPN connection on my EdgeRouter X. The network at my workplace allows outbound TCP connection on a small number of ports and seemingly drops UDP at the internet boundary altogether, therefore I was restricted to using OpenVPN in TCP mode rather than UDP mode. For transferring small amounts of information, this turned out to be functional but certainly not exceptional. OpenVPN doesn't perform any kind of optimisation on TCP traffic, therefore the performance on anything latency-sensitive was awful - VNC back to my iMac was simply unusable. SSH forwarding was no better. Instead, I installed Yggdrasil onto my EdgeRouter X and used this as a gateway to route to my home machines directly (a topic for a future blog post). Every Yggdrasil node has a routed /64 subnet which, in my case, was `NETMAP`'d using `iptables` to my home IPv6 ULA range. This effectively makes my entire home network routable on the Yggdrasil network (even devices that are not Yggdrasil-aware or do not have it installed), subject to some firewall restrictions which I will discuss shortly. The main benefits here are that Yggdrasil uses a LIFO queue for session traffic and also takes advantage of huge MTUs (as discussed in my previous blog post) to lessen the effect of TCP control message amplification and improved congestion handling. This results in a much more usable and stable connection when tunnelling TCP over a TCP Yggdrasil peering - the stability and the responsiveness of VNC proved to be much improved in this setup than over OpenVPN or SSH. #### Firewalls and source verifiability Of course, there are other people on the Yggdrasil network and you can't be certain who they are or if they may or may not be malicious. Therefore just like on the Internet, it is wise to make use of a firewall. Source verifiability comes in particularly useful here as it makes it quite easy to allow only specific machines to send traffic through your firewall and to keep everyone else out. In Yggdrasil, your IPv6 address is directly associated with your encryption keypair, therefore any changes to your keypair result in your IPv6 address changing with it. When you generate a configuration (using `yggdrasil -genconf`) then you are effectively deriving a new IPv6 address. As long as you continue to use the same Yggdrasil configuration with the same encryption keypair on a given machine, then that machine will keep the same Yggdrasil IPv6 address forever. This meant that I could create a whitelist on my EdgeRouter firewall to drop connection headed towards my network unless it came from a specific list of Yggdrasil IPv6 addresses known to me already, i.e. my work computer and my laptop. Any other unexpected connections from addresses outside of this whitelist are dropped, hiding my machines from anyone else on the network. An example of how I achieved this on my EdgeRouter X: ``` set firewall group ipv6-address-group YGG_TRUSTED ipv6-address 'xxxx:xxxx:xxxx:xxxx:xxxx:xxxx:xxxx:xxxx' set firewall group ipv6-network-group YGG_TRUSTEDNETS ipv6-network 'xxx:xxx:xxx::/48' set firewall ipv6-name YGG_IN default-action drop set firewall ipv6-name YGG_IN rule 10 action accept set firewall ipv6-name YGG_IN rule 10 state established enable set firewall ipv6-name YGG_IN rule 10 state related enable set firewall ipv6-name YGG_IN rule 20 action drop set firewall ipv6-name YGG_IN rule 20 state invalid enable set firewall ipv6-name YGG_IN rule 30 action accept set firewall ipv6-name YGG_IN rule 30 source group ipv6-address-group YGG_TRUSTED set firewall ipv6-name YGG_IN rule 40 action accept set firewall ipv6-name YGG_IN rule 40 source group ipv6-network-group YGG_TRUSTEDNETS set firewall ipv6-name YGG_LOCAL default-action drop set firewall ipv6-name YGG_LOCAL rule 10 action accept set firewall ipv6-name YGG_LOCAL rule 10 state established enable set firewall ipv6-name YGG_LOCAL rule 10 state related enable set firewall ipv6-name YGG_LOCAL rule 20 action drop set firewall ipv6-name YGG_LOCAL rule 20 state invalid enable set firewall ipv6-name YGG_LOCAL rule 30 action accept set firewall ipv6-name YGG_LOCAL rule 30 source group ipv6-address-group YGG_TRUSTED set interfaces yggdrasil tun0 firewall in ipv6-name YGG_IN set interfaces yggdrasil tun0 firewall local ipv6-name YGG_LOCAL ``` #### Routable from the whole network You don't need to be directly peered to a node to be able to remotely access it - you can route traffic from anywhere on the Yggdrasil network. It is preferable to always peer with nodes that are geographically close to your own location, as this helps to reduce latency across the network. You can, however, set up in a new location (for example, with a laptop) and connect to your nearest Yggdrasil node and still be able to reach your machines like before. ### Conclusion Yggdrasil has proven to be a more-than-capable method for remotely accessing my home network and very much normalises the idea that all network traffic should be encrypted and treated as if it is private, even in locations where connection security would not otherwise be guaranteed. --- ## File: _posts/2018-07-17-world-tree.md --- layout: post title: "The World Tree" date: 2018-07-17 00:00:00 -0500 author: Arceliar --- ### Taboo Trade-offs I spent a long time thinking about what to write for my first contribution to this blog. It makes sense for me to cover the gritty details, to try to explain why and how this thing works under the hood, but there's a lot to go over. Still, we have to start somewhere, and this seems as good a place as any. There are things we ideally want a network to do. We want to find the shortest path between any two nodes in a network. We want to use as little resources as possible. We want latency to be as low as possible. We want as much bandwidth as possible. We want to minimize packet loss. We want the network to be fault tolerant, and re-converge as quickly as possible if/when disruptions do occur. We want security. We want simplicity. The list goes on. Unfortunately, some of these things involve fundamental trade-offs. Mathematicians have proven, from a pretty inescapable information theory argument, that there's a trade-off between memory and the efficiency of the paths you can find: If you want to guarantee memory usage below `~O(n^(1/k))`, you must accept stretch as high as `2k-1`. Similarly, if you want more bandwidth, they you must sometimes use higher-latency paths, and both can get in the way of reliability / low packet loss. Yggdrasil is an experimental implementation of a number of different ideas. In this blog post, and likely my next several, I'll try to go over some of them, but at the end of the day, it's all about trade-offs. When seeking to improve performance in one area, we must sometimes make sacrifices in another. Today's blog post focuses on Yggdrasil's routing logic. On realistic network topologies, we achieve polylogarithmic memory scaling by sacrificing something held sacred in most other routing schemes: shortest path routing. To explain how and why, I think it's best if we first review how things are done elsewhere. ### Hard CIDR Networks today are built around hierarchically allocated addressing and [classless inter-domain routing](https://en.wikipedia.org/wiki/Classless_Inter-Domain_Routing) (CIDR). The basic idea is to allocate addresses in a network from a contiguous address range, often as small as a `/64` for IPv6 addresses (a block of addresses with the first 64 bits in common, e.g. `1111:2222:3333:4444::/64` denotes all addresses from `1111:2222:3333:4444:0000:0000:0000:0000` to `1111:2222:3333:4444:ffff:ffff:ffff:ffff`). A gateway node `G` in network `A`, with a connection to another network `B`, can advertise to network `A` a route to the address range of network `B`, and vice versa. This allows nodes in network `A` and `B` to communicate with each other by routing through gateway node `G`. This system of gateways, often between a hierarchy of networks with progressively smaller address ranges, is meant to keep routing tables small. Within a particular network, each node must be able to find a path to every other node within that network. Virtually all routing schemes in use today are a form of shortest path routing, wherein each node knows the shortest path to every other node in the network, for some definition of path length (such as the number of network hops, latency, some function of bandwidth usage, or often the [expected transmission count](https://en.wikipedia.org/wiki/Expected_transmission_count) in mesh networks). A notable exception to this is Ethernet, which has historically used the [spanning-tree protocol](https://en.wikipedia.org/wiki/Spanning_Tree_Protocol) (STP) to reduce a network to a tree topology, in an effort to eliminate routing loops, but newer protocols (such as [shortest path bridging](https://en.wikipedia.org/wiki/IEEE_802.1aq)) aim to improve this. Typically, shortest path routing is implemented either via a proactive protocol, wherein every node in a network maintains a local routing table with information about every other node in the network, or via a reactive protocol using broadcast lookup traffic, wherein routes are found by broadcasting lookups through the entire network. There are things about this approach which can be problematic. The main issue, for the purposes of this post, is scalability. For a large network to scale, it must be subnetted into smaller, more easily manageable networks, which then must in turn be networked together (to form a network of networks from inter-network connections, i.e. the internet). This requires some level of expertise and planning to do, and tends to favor hierarchies wherein small networks are largely at the mercy of a larger network (e.g. the only connection your LAN has to another network is your connection to an ISP, and "peering" or directly connecting to your neighbor's LAN is virtually unheard of). If you don't subnet efficiently, then large networks can become overloaded by protocol traffic alone. What's worse, the kinds of network topologies that show up in practice (small-world / scale-free networks) are among the topologies for which hierarchical addressing and CIDR are least effective at aggregating routes, which contributes to (and I dare say, *causes*) very large [BGP](https://en.wikipedia.org/wiki/Border_Gateway_Protocol) routing tables in the [DFZ](https://en.wikipedia.org/wiki/Default-free_zone). ### Compact Routing So, what if we didn't do that? [Compact routing](https://arxiv.org/abs/0708.2309) is the study of the fundamental trade-off between the stretch of a routing scheme (the length of the paths it finds, relative to the shortest paths in the network) vs the size of the routing table required to find a path. Essentially, compact routing proposes that, rather than require each node in the network be able to find the *best* path, we only require that they find a *good* path. In doing so, it becomes possible to reduce the size of each node's routing table. To skip over the details, there are basically two aspects to consider that are relevant to this post. First, compact routing schemes can be name-dependent or name-independent. Name-dependent routing schemes assign an address (of some kind, not necessarily a familiar IP address) based on a node's location in the network. Name-independent routing schemes place no requirements on a node's address, and treat it as some opaque identifier in a flat (i.e. non-subnetted) address space. Secondly, compact routing schemes can either be a universal scheme, with strong guarantees on all possible network types, or they can be specific to certain network topologies. On paper, compact routing is essentially a solved problem: universal name-dependent routing schemes are known with worst case scenario performance guarantees that are basically equal to the best case scenario lower bounds proven by the mathematicians who do that sort of thing. Furthermore, name-independent routing schemes are known with the same performance guarantees, albeit much worse observed performance *in practice* (still better than the guaranteed worst cases, but not by as much). However, practical compact routing has yet to be realized. Although the schemes themselves are known, in the sense that someone with a full view of the network can figure out who needs to know what to route packets effectively, a distributed algorithm suitable for dynamic networks is still a topic of ongoing work, and no publicly available implementation. ### Greedy Embedded Routing So, what if we didn't do that? [Greedy embedded](https://en.wikipedia.org/wiki/Greedy_embedding) routing algorithms take a slightly different approach. Instead of a routing table about some remote subset of the network, each node knows information about itself and its directly connected (one-hop) neighbors, which we refer to as "peers" in Yggdrasil. In particular, each node knows the location of itself, and its peers, in some metric space. For example: consider the case of a two-dimensional square grid, with no gaps, holes, or other irregularities that could obstruct the flow of traffic. Every node's "address" is simply the X and Y coordinates of the node in the network. Because there are no gaps in this example, every node can route traffic simply by forwarding it to any neighbor which is closer to the destination's X-Y coordinates than itself. This is called a greedy routing strategy, and coordinate systems where this strategy is guaranteed to work are called greedy embeddings. While there is no finite dimensional Euclidean space for which a greedy embedding exists on all possible graphs, so the dimension of Euclidean embeddings need to be changed due to network size and topology, which complicates things, it turns out that [the hyperbolic plane admits a greedy embedding of any network](http://www.cs.cornell.edu/~rdk/papers/pgr.pdf). Furthermore, this can be done with small addresses, and produces low stretch in realistic network topologies -- this is basically everything we want! However, the most common approach to implementing such an embedding, which can be done via a distributed algorithm, consist of constructing a spanning tree of the network, and then embedding the spanning tree instead of the original network graph. ### The World Tree So, what if we didn't do that? Here's an observation for you to consider: that strategy for greedy hyperbolic embedding just sounds like a tree embedding with extra steps. Yggdrasil, named after [the mythical world tree of Norse cosmology](https://en.wikipedia.org/wiki/Yggdrasil), uses a form of greedy embedded routing for the "switch" layer. Instead of embedding a spanning tree into the hyperbolic plane, the spanning tree is used directly to define the metric space: the distance between two nodes in the space is simply their distance apart on the tree, which trivially leads to a greedy embedding. It must be emphasized that this is not the same as *routing* on the tree, as in STP flavor of Ethernet, because every link is available to forward traffic. The spanning tree itself is constructed using a STP-like distributed algorithm, but with cryptographically secured advertisements (to prevent forgery-based route hijacking attacks). This has a number of effects. First and foremost, as with compact and greedy routing schemes, Yggdrasil is not guaranteed to find the shortest path when routing a packet. Instead, it merely tries to guarantee that it can find *some* path for any network, and we observe that it tends to find a *good* path (i.e. usually the shortest path, or only slightly longer, on par with the compact routing schemes) for the special case of small-world / scale-free networks (the only kind that ever seems to grow large enough that we need to worry about scaling). The main benefit is that the amount of maintenance traffic needed by the network is greatly reduced, with the tree requiring something like `O(p*log(n))` state for a node with `p` peers in a network with `n` nodes. This is in contrast to [distance-vector](https://en.wikipedia.org/wiki/Distance-vector_routing_protocol) or [link-state](https://en.wikipedia.org/wiki/Link-state_routing_protocol) protocols, where each node needs at least `O(n*log(n))` state in their local routing table (e.g. `n` routing table entries, each at least as long as the `log(n)` bits needed for unique node identifiers). The goal here is that, as the network grows, the resource cost devoted to protocol traffic should scale at a negligible rate -- you never want to stop adding nodes to the network because it costs the rest of the network too much resources to deal with them. If this strategy works, and it seems to on paper, and in simulation, and it's looking that way from our early tests on real hardware, then there's no longer a requirement that the network subnet the address space for scalability reasons. This would make it trivial to bridge networks together: you simply need to add links between them, and the protocol takes care of the rest, without requiring any expert knowledge or centralized coordination to partition the address space. These can be physical links, such as an ethernet or fiberoptic cable, wireless links, such as open wifi in ad-hoc mode, or virtual links tunneled across existing networks, such as connecting to a public node via the internet (to bridge networks that are not within a convenient range for real links). ### Conclusion I hope that sheds some light on what is arguably the most important part of Yggdrasil. Of course, there's more to Yggdrasil than just the tree. It was written to test not only the above greedy routing scheme, but a number of other ideas that I thought would be too experimental to try out in e.g. [cjdns](https://github.com/cjdelisle/cjdns) without prototyping elsewhere first. I plan to go into more detail about other parts of Yggdrasil in my next few posts, including name-dependent routing with cryptographically self-assigned addresses, ongoing work to add a form of backpressure routing for congestion control, and likely some performance studies to show what the effects of some of these trade-offs. --- ## File: _posts/2018-07-20-more-platforms.md --- layout: post title: "Bringing Yggdrasil to more platforms" date: 2018-07-20 19:10:00 +0100 author: Neil Alexander --- ### Write once... When I first joined the Yggdrasil project, it only targeted a single platform - Linux. For proving a concept, this is fine, but it was never going to be reasonable to expect everyone who may want to run Yggdrasil to also run Linux. Yggdrasil is a project which cares very deeply about scale. Born out of the lack of scalability in cjdns, the routing scheme is designed to work well even on very large networks with lots of users or nodes, but testing this without real users is actually very difficult. Of course we can run simulations and model the sorts of behaviour we might expect, but ideally we need to be able to examine how the routing scheme behaves in the wild - with real people, on real computers over real networks. We need to meet our users where they are. ### ... Run anywhere? I made it my mission to bring Yggdrasil to as many platforms as possible. It started with macOS support because I wanted to be able to run Yggdrasil on my own computers at home. From there I branched out to OpenBSD, FreeBSD and NetBSD, and even to Windows. I even spent some time trying to simplify the installation process on Debian Linux by producing Debian packages. Since then we've been able to convert those same packages to RPMs with some success. We've targeted ARM and MIPS platforms as well, including the Ubiquiti EdgeRouter - another device I happen to own and like. The use of the Go programming language actually helped a lot here, because as it turns out, Google have gone through great lengths to make Go code relatively portable across platforms and architectures. It bundles a custom standard library, and the Go compiler can cross-compile effortlessly for a wide range of platforms and architectures by simply passing in environment variables like `GOARCH` and `GOOS` to the compiler. There's no tinkering about with architecture-specific toolchains - it's built-in for free. Cross-compiling, however, is only part of the battle. Every platform comes with unique behaviours and interfaces which need to be accounted for in our code. The most troublesome part was by far the TUN/TAP adapter, a crucial component for allowing the node to actually communicate with the Yggdrasil network instead of just being a passive router. ### Reuse, reuse, reuse Admittedly, we didn't write all of the TUN/TAP code ourselves. Instead we made use of a library called [Water](https://github.com/songgao/water) which exposes a much simpler interface. However, this library is certainly not without inadequacies - it was necessary for us to fork this library to add platform support for BSD, interface name support for Windows and to fix a deadlock bug with closing the TUN/TAP adapter on macOS. (Apparently the author is not terribly receptive to pull requests, so to this day, we continue to use our own fork.) Of course, a couple of fixed bugs and introduced features in Water wasn't all that remained to be done... ### macOS Getting Yggdrasil to work on macOS was actually relatively straight-forward. TUN adapters on macOS are a little different to on other platforms - they are implemented through a `utun` interface. Luckily, Water already had support for this, but Yggdrasil didn't have a mechanism for configuring the interface address, prefix or MTU. On macOS, all of this is possible by using an `AF_SYSTEM` socket, so I wrote code that would fill this gap, plagiarising a number of structs from the XNU source code in the process. The macOS `utun` driver only supports creating TUN (Layer 3) devices and has no support whatsoever for TAP (Layer 2) devices. There is an open-source `tuntaposx` driver which implements both, but this would rely on the driver being installed when `utun` does the job perfectly out of the box. Therefore, Yggdrasil will only allow TUN mode when run on macOS. ### BSD In many ways, Darwin (the operating system which underpins macOS) is not dissimilar to BSD at all. In fact, there are many user-space components which were derived or imported directly from BSD. It made sense that adding support for FreeBSD, NetBSD and OpenBSD would be relatively simple as a result. However, Water didn't have support for BSD, so at this point we started to modify the Water library to include support for it. TUN/TAP on BSD is actually much simpler than on macOS - rather than having to request a new `utun` device from within the process, you can simply open a read/write descriptor to one of the TUN or TAP nodes in `/dev`. The changes needed to Water were actually [very simple](https://github.com/yggdrasil-network/water/blob/master/syscalls_bsd.go) in the end, but did end up being really quite different from macOS. Originally I anticipated that setting the interface address, prefix and MTU would be just like macOS too, but this turned out not to be the case. Whereas macOS uses an `AF_SYSTEM` socket, BSD expects you to simply perform syscalls directly onto the TUN/TAP device node. More code for BSD was born. However, like all system calls, these are difficult to debug, and I haven't yet figured out the secret formula to getting these `ioctl` calls to work right. I was forced to implement an ugly workaround - when the `ioctl` fails, it simply falls back to calling `ifconfig` to do the work for us. Hardly ideal, but at least functional. The MTU proved troublesome too. Whereas Linux and macOS both support a maximum MTU of 65535 on TUN devices (65521 for Linux TAP devices to make way for the 14-byte Ethernet header), the maximum supported MTUs on the BSDs were much lower. FreeBSD managed only half of the above MTU with a maximum of 32767 bytes. OpenBSD was half of that again with a maximum of 16384. NetBSD, just in the spirit of being awkward, is different again, with a mere 9000 byte maximum. I assume there are historical and possibly important reasons for the varying defaults, but they remain a mystery to me at the moment. One final place that caught me out is that, in TUN mode, OpenBSD and FreeBSD (but *not* NetBSD) both include a "Protocol Information" header to all traffic going in and out of the TAP adapter. Incidentally, macOS does not do this, and on Linux, this behaviour can be disabled. Nevertheless, on OpenBSD and FreeBSD, this behaviour seems to be mandatory. Yggdrasil would need to recognise and strip this header, although at this time, this remains an [unfixed problem](https://github.com/yggdrasil-network/yggdrasil-go/issues/31) as it will require additional changes in the Water library. Currently, the library is not aware of this and simply fails to process the packets as it believes they are malformed. As a workaround, these operating systems were later supported through TAP mode, which was only introduced when we added support for... ### Windows Yes, Windows. The real outlier, sharing almost nothing in common with Linux, macOS or BSD, apart from some very historic POSIX compliance in the early incarnations of Windows NT which have almost certainly since lapsed. Windows actually presented a rather unique challenge. Through the help of the OpenVPN developers, there is an NDIS-compliant TAP driver available for Windows, and Water even had support for it too, but it is the only platform out of our current supported list that actually only supports TAP and doesn't support TUN. Whereas TUN adapters typically emulate a Layer 3 routed interface, like those used with VPNs and encapsulated tunnels, TAP adapters actually mimic a real Layer 2 network interface - Ethernet and all. These adapters behave almost as if the program responsible for them is connected by a virtual network cable, requiring that every frame sent in and out is a valid Ethernet frame, with MAC address and all. Yggdrasil, up until this point, had not made any particular accommodation for TAP devices, but that would not be sufficient on Windows. I was faced with two new challenges. #### Ethernet frames Given that the TAP adapter would feed us entire Ethernet frames instead of just IP packets, I started by writing code that would be dissect the Ethernet headers and to unwrap the IP packet within, and also encapsulate any IP packets received across the Yggdrasil network within a new Ethernet frame. Critically, Yggdrasil never transports Ethernet headers across our encrypted sessions - only raw IP packets, therefore the Ethernet encapsulation needs to be dealt with at the endpoint itself. Encapsulation and decapsulation takes place transparently if Water reports that the adapter is a TAP device. Yggdrasil must take a note of the MAC address of the frames coming from the TAP adapter and must create headers for the response frames too with a MAC address of its own (a rather arbitrarily-chosen `02:00:00:00:00:02` if you were wondering), which allows the host to believe that the traffic coming in from the TAP adapter was sent from a real Ethernet device. But this alone is not enough to encourage Windows to send traffic over the TAP adapter. #### ICMPv6 Because the prefix length on the adapter address covers the entire Yggdrasil address space, this leads the host to believe that the entire network is reachable within a single broadcast domain. In the real world, this would be like every other host being directly attached to the same switch. This is obviously not the case, but in order to avoid having to add additional static routes (which may be fragile or even difficult to automatically add or remove, especially on Windows) we instead lie to the host to make it believe that every other node is directly connected. When a packet is sent towards an Yggdrasil IP address, a request is sent out on the Ethernet interface to ask which MAC address holds that IP address. In IPv4, this happens using Address Resolution Protocol (ARP), but in IPv6, this is actually a feature of ICMPv6 called Neighbour Discovery (ND). Windows (or any other platform, for that matter) won't actually send any real traffic to a Layer 2 interface for the destination until it is received a suitable ARP or ND response for the destination. Windows starts by sending out an ND request for the destination address, therefore Yggdrasil must respond. I wrote code that would do exactly that - we check if the destination address matches our address space (`0200::/7`) and if it does, we send back an ND message claiming that the destination address is reachable at `02:00:00:00:00:02` (our virtual MAC address from before). At this point, Windows starts sending traffic towards that MAC address and all is good. Now that Yggdrasil can understand Ethernet headers, and it can sufficiently lie to the host operating system to make it believe that an Yggdrasil address is directly connected, we can now exchange traffic over a TAP adapter. Doing this actually opened up TAP support properly on Linux and BSD too! ### Ubiquiti EdgeRouter There is nothing particularly remarkable about the EdgeOS platform - it's just a modified Debian distribution, but instead, running on a MIPS CPU instead of an x86-based CPU. This meant that cross-compiling Yggdrasil for MIPS Linux was largely sufficient to get Yggdrasil to work on the EdgeRouter. However, EdgeOS also comes with an overlay configuration system (the Vyatta configuration system, in fact). For friendliness, it made sense to create a Vyatta configuration wrapper for Yggdrasil so that it can be configured in the same way as everything else on the EdgeRouter. These wrappers are merely scripts that either modify the `yggdrasil.conf` file or start/stop the Yggdrasil process. The work for this is in a [separate repository](https://github.com/neilalexander/vyatta-yggdrasil) but this results in a single `.deb` package that can provide EdgeOS support. ### Conclusion That concludes the journey that I have taken to bring Yggdrasil to a wider range of platforms. Of course there are still platforms that are still to be targeted, and some platforms are better tested than others, but it is a significant step for the project to be able to run on more operating systems than just Linux. We would really appreciate if you can provide us with any feedback you have about running Yggdrasil on your own systems - as always, issues can be raised on our [GitHub repository](https://github.com/yggdrasil-network/yggdrasil-go/issues). --- ## File: _posts/2018-07-28-addressing.md --- layout: post title: "Addressing and Name-Independent Routing" date: 2018-07-28 18:00:00 -0500 author: Arceliar --- ### By any other name In an earlier post, I talked about Yggdrasil's use of a tree-based metric space for name-dependent routing. The purpose of this post is to explain how Yggdrasil's name-independent routing is implemented. Name-dependent routing means that addressing follows network topology: if the state of the network changes, then a machine's address can change. For example, in the CIDR-based internet, at least if you're the kind of person who reads random blogs about experimental routing schemes, then you've probably run into the dynamic addressing problem. If you're offline for too long, or your ISP does any non-trivial maintenance or upgrade work on their network, or sometimes for no visible reason, IP addresses tend to change. Sure, you can pay extra for a static address, but this is one of the cases where ISPs have a genuinely good excuse to charge extra: assigning a static IP may require the ISPs routers to keep an additional route to you, which would consume excessive resources if everyone needed static addresses. If addresses are dynamic, and you want to host some kind of service, then you probably want to attach a static identifier to the host. This usually means [Dynamic DNS](https://en.wikipedia.org/wiki/Dynamic_DNS). This *also* tends to wrap the problem up with the separate problem of assigning human-readable identifiers and securing this layer of abstraction [complicates things](https://en.wikipedia.org/wiki/Domain_Name_System_Security_Extensions). The real issue is that we simultaneously use an IP address as an *address*, specifying *where* we want to send a packet, and as a *name*, specifying *who* the packet is for. ### Addressing in Yggdrasil So, what if we didn't do that? Yggdrasil uses name-independent routing, which means identifiers (IPv6 addresses) and network state are independent. As a consequence, we can treat addresses as some flat / opaque identifier. Yggdrasil uses the `200::/7` region of the IPv6 network space. This region was set aside for [NSAP](https://en.wikipedia.org/wiki/NSAP_address)-mapped IPv6 addresses in [RFC1888](https://tools.ietf.org/html/rfc1888), which was (AFAIK) never used and eventually deprecated in [RFC4048](https://tools.ietf.org/html/rfc4048) (with further explanation in [RFC4548](https://tools.ietf.org/html/rfc4548)). The address space is currently unused and, we believe, unlikely to be reassigned for the foreseeable future. As such, we think it's reasonable to use this address space for Yggdrasil, to avoid conflicts with existing use of the more obvious [ULA](https://en.wikipedia.org/wiki/Unique_local_address) range (which we used previously). Within `200::/7`, we partition the network into `200::/8` and `300::/8`. Each node running Yggdrasil as assigned a `/128` address in `200::/8`, and an optional matching `/64` prefix in `300::/8`. Other than the change of 1 bit for `2->3`, the rest of the first 64 bits of the address and prefix are identical. Having a `/64` address range allows a Yggdrasil node to operate as a router, where it advertises a route (using normal IPv6 tools, like radvd) allowing the rest of its LAN to reach Yggdrasil without needing to run the code. This allows unsupported and legacy devices (phones, network printers, game consoles, old OSs, etc.) to reach the network, or low-power / battery-powered devices (IoT) to off-load cryptography and routing logic onto something with fewer constraints. A node's address is constructed from its `NodeID`, described in the next section, but for now just think of it as a 512-bit unsigned integer. The process is pretty simple: the first byte is always `0x02` (or `0x03` for a `/64` prefix), to fall within the allowed address range. The next byte is an unsigned 8 bit integer, and equals the number of leading `1` bits in the `NodeID` (if you brute force a `NodeID` with many leading 1 bits, this number will be larger). The rest of the address (or `/64` prefix) is equal to the `NodeID`, but with the leading `1` bits and the first leading `0` bit removed (since you know the first bit after the last `1` must be a `0`), and truncated to a maximum of `/128` bits for an address (or `/64` for a prefix). By optionally brute-forcing a large number of leading `1` bits, a node can increase the difficulty of address and prefix collisions. This is basically a workaround for the fact that 128 bit IPv6 addresses (and much moreso, 64-bit prefixes) are too short *really* to be immune to collisions. Fixing that is on my wish-list for IPv7, if for some reason that ever happens. ### NodeIDs and locators Other than when packets enter and leave the network, Yggdrasil is oblivious to IPv6 addresses. The untruncated equivalent, a `NodeID`, is used instead. A node's `NodeID` is equal to a sha512sum of the node's curve25519 public cryptographic key. Traffic, including protocol traffic, is encrypted in Yggdrasil, so spoofing an ID is equivalent to generating a private key for which the derived public key happens to hash to the right `NodeID` -- presumably a somewhat harder problem than finding a sha512sum collision. This is mostly influenced by [cjdns](https://github.com/cjdelisle/cjdns)'s use of a double-sha512sum truncated to 128 bits as an addressing scheme, but with a single round of sha512 and a more complicated truncation rule. Meanwhile, to actually route a packet through the network, we need to know not only *to whom* it is going, but *where* it is going -- name-independent routing implies some form of locator identifier separation (similar in purpose to [LISP](https://en.wikipedia.org/wiki/Locator/Identifier_Separation_Protocol)). In Yggdrasil, a locator consists of a node's position in the spanning tree. This includes two parts: the root of the tree, and a path from the root to the destination node. Since the same root is implied, only the path portion, referred to as `coords` in the code, needs to be attached to each packet. This path is represented by a list of interface numbers. Each node assigns an interface to each of their peers, with 0 corresponding to their self in the current implementation, which are stored as a list of 64-bit unsigned integers. This list is then encoded as a list of 8-bit unsigned integers, with each 64-bit integer represented by a [variable-length quantity](https://en.wikipedia.org/wiki/Variable-length_quantity) -- in practice, this means 1 byte per hop in the path from the root to the destination. These `coords` are then used as distance labels, wherein the `coords` of any two nodes are sufficient to compute their distance apart on the tree. ### DHT FTW Now that each node has a `NodeID` and a locator with a set of `coords`, we need a way to use them. Specifically, when given a node's `200::/7` IPv6 address, we need to figure out the node's coords. To do that, we first unpack the IPv6 address into a `NodeID` and a bitmask signifying which bits of the `NodeID` are known (since some were truncated away when compressing it into an IPv6 address). Then, to map a `NodeID` onto `coords`, we use a [Distributed Hash Table](https://en.wikipedia.org/wiki/Distributed_hash_table) (DHT). In particular, we use a [Kademlia](https://en.wikipedia.org/wiki/Kademlia)-like DHT with no proper key:value store -- we only store information about nodes in each keyspace bucket. In practice, what this means is the following. Each node has a 512-bit `NodeID`. For each number of possible bits that could match in the address (0 to 511), the node stores a list of other nodes (called a bucket), which includes node keys (to derive `NodeID`s) and `coords` (so you can actually send packets to them). These buckets store information about nodes for which exactly that number of leading bits match, so bucket 3 stores info about nodes where exactly the first 3 bits match. More generally, we can define the distance between `NodeID`s, in some abstract keyspace, as being the `xor` of the two `NodeID`s, and each bucket covers some range of keyspace, but it turns out to be easiest to align these things so the bucket edges match bits of the `NodeID`s. Then, for every possible `NodeID` that *could* be in the network, either a node has that `NodeID`, or else it should know someone closer to that `NodeID` in one of its buckets. Nodes can then search for a given `NodeID` by iteratively asking nodes they know about for a list of nodes that are closer to the destination in keyspace. Like any good Kademlia-based DHT, this requires a logarithmic number of steps, and uses a logarithmic amount of memory for each node's local table. The leading `1` suppression from address generation tends to lead to some additional steps, as it encourages nodes to cluster in the same region of keyspace, which acts as a form of sybil attack mitigation (it becomes computationally more expensive to become a keyspace neighbor any particular node -- let alone *all* the keyspace neighbors of that node -- if everyone's address starts with a bunch of extra `1` bits.). The currently implementation's bucket size is 2 nodes, plus any directly connected peers (always tracking all peers helps from a bootstrapping perspective, and we know about them already from the switch layer, so we can include them in the DHT at basically no cost). It's important to note that packets are routed based on `coords`, with no regard to the structure of the DHT. This is in contrast to [cjdns](https://github.com/cjdelisle/cjdns)'s old dht-based pathfinder, where source routing and switch label splicing [cause the path a packet takes to mirror the path followed in the DHT](https://github.com/cjdelisle/cjdns/blob/cjdns-v20.2/dht/dhtcore/ReplySerializer.c#L75-L78) (and if the DHT learns paths from other DHT entires, then extra stretch may compound as the network grows). ### The connection handshake Once a node learns the destination's `coords` and key from the DHT lookup, it can initiate a session exchange. The session exchange involves sending a session ping packet the destination, which includes the sender's public key, `coords`, and an ephemeral session public key (used for [forward secrecy](https://en.wikipedia.org/wiki/Forward_secrecy)). The destination then responds with a pong, in the same format. The nodes cache this information, and use the cached `coords` and ephemeral derived secret key to communicate. So full connection process looks something like the following: 1. A node wants to send a packet to a node, which is addressed to `A`. 2. The node unpacks the address to get an approximate `NodeID` and bitmask. 3. The node creates a search for the `NodeID`, and initially fills it with information from the node's own portion of the DHT. 4. The node repeatedly sends a lookup to the closest node in the search, adding any responses to the search, until it reaches the closest node to the destination `NodeID` (or hits a dead end). 5. The node checks that the destination `NodeID` and bitmask match the `NodeID` of the closest node (if not, then it means the destination node doesn't exist / is offline / is unreachable while the network re-converges due some disruption). 6. The node sends a session ping to the destination. 7. The node receives a session pong from the destination, learning their public ephemeral key. 8. The nodes can now send regular IPv6 traffic to each other, encrypted with the ephemeral shared secret, using the session's cached `coords` to avoid future lookups (unless the session is unresponsive for too long, in which case any new sends will also trigger a ping, or a new DHT lookup if the pings fail). ### Conclusion Yggdrasil provides name-independent routing with cryptographically generated addresses. Static addressing means you can keep the same address as long as you want, even if you move to a new location, or generate a new address (by generating new keys) whenever you want. Cryptographically generated addressing means it's impractical (if not outright impossible) to spoof addresses, so you get end-to-end encryption, with automatic key exchange and forward secrecy, and with some degree of collision resistance, without any dependence on public key infrastructure. This also means [reflection](https://en.wikipedia.org/wiki/Denial-of-service_attack#Reflected_/_spoofed_attack) and [amplification](https://en.wikipedia.org/wiki/Denial-of-service_attack#Amplification) attacks, which are only possible [because of IP address spoofing](https://blog.cloudflare.com/the-root-cause-of-large-ddos-ip-spoofing/), or attacks based on [route hijacking](https://blog.cloudflare.com/bgp-leaks-and-crypto-currencies/), should be at least as hard as finding a truncated sha512sum collision or breaking the cryptographic primitives. Oh, and the routing tables are ridiculously small -- we could exhaust the entire `200::/8` part of the address space and the average routing table would only be ~240 nodes + directly connected peers. The main cost you pay for this is an extra delay during the initial DHT lookup, which is sort-of like having a slower (because it's `O(log(n))`-ish steps) DNS lookup, except the names aren't human readable. The DHT takes a little while to converge, so *incoming* connections also tend to fail immediately after node startup, until your keyspace neighbors have a chance to hear about you, but the lookups for *outgoing* connections tend to work almost immediately. Also, while the current DHT *should* be fine for peer-to-peer type applications, I wouldn't want to be the keyspace neighbor of an especially popular server, as this would mean a large number of DHT lookups would go through my node. A caching DHT could, in principle, be able to address that issue without changes to the protocol, but that's not a very high priority given the size of the current network. Lastly, IPv6 anycast *may* work with the current implementation, but which anycast node the lookup directs you to probably has nothing to do with the network topology, so it would make sense to add an extra lookup at the end of a search to return all `coords` where a particular `NodeID` can be found. This would require slightly the DHT to include identical `NodeIDs`, and adding an additional DHT lookup step at the end to get a list of all `coords` (presumably selecting the closest `coords` returned by the lookup). I'm not certain if this can be done in a backwards compatible way, so this will require further investigation at some point. --- ## File: _posts/2018-08-18-congestion-control.md --- layout: post title: "Congestion Control" date: 2018-08-18 22:10:00 -0500 author: Arceliar --- ### Why can't I, hold all these packets? Earlier blog posts have explained, to some extent, how we know where a packet in Yggdrasil needs to go. As G. I. Joe taught me as a child, knowing is half the battle. Now we need to deal with the other half. [Packet switch](https://en.wikipedia.org/wiki/Packet_switching) networks allow links to be used by multiple unrelated streams of traffic at the same time, to better utilize network links. That's what makes them ~~better than~~ different from [circuit switch](https://en.wikipedia.org/wiki/Circuit_switching) networks like the [Public Switched Telephone Network](https://en.wikipedia.org/wiki/Public_switched_telephone_network). This leads to a problem: what do we do if we receive multiple packets that need to be sent over the same link? How do we decide which one to send first? What do we do with the rest of them? It seems like we should start sending the first packet we process, since at that point we don't *know* that the other packets need to use the same link. If we drop them, then that's the end of the story, and this would be a much shorter post. What we actually do is buffer them, to better utilize the available bandwidth of the link, but that just leads to further questions: what does the buffer look like? How large is it? What do we do if it's already full (assuming some concept of full is well defined)? This post attempts to explain Yggdrasil's congestion control mechanism, why past approaches were abandoned, and our possible future plans are. ### FIFO, LIFO, front or tail drop? The first thing to try is not to implement any explicit buffering in Yggdrasil. Packets are received from a socket, we look up where the packet needs to go next, and then we send on that socket. This immediately leads to blocking network operations and poor performance, so we need separate read and write threads (goroutines, in our case). Initially, we used buffered channels and non-blocking channel sends. This means that, instead of the reader goroutine writing to the socket to send, it would pass it to a channel which a dedicated writer goroutine would read from. The problem with this approach is that Go channels with non-blocking sends are [FIFO](https://en.wikipedia.org/wiki/FIFO_(computing_and_electronics)) and [tail dropped](https://en.wikipedia.org/wiki/Tail_drop). This means traffic continues to flood the channel until it fills up, and then begins dropping. TCP doesn't notice the dropped packets until later traffic gets sent, which has to first wait for the entire go channel to empty (in addition to the OS's TCP buffers). This is just [bufferbloat](https://en.wikipedia.org/wiki/Bufferbloat) appearing in another part of the network stack. So instead, we switched to having the writer goroutine first read packets out of the channel and put them into a local slice, which it uses as a [LIFO stack](https://en.wikipedia.org/wiki/Stack_(abstract_data_type)) with head drop. This means the newest packets are always sent first, and if the stack grows too large, then the oldest packets are dropped. This kills two birds with one stone. First, latency goes back to being something reasonable -- packets tend to either get sent quickly, or get burred in the stack so long that they drop (either because the stack drops them, or because they arrive at the destination so far out-of-order that the session layer drops them). Secondly, LIFO order causes congestion to reorder packets, which reasonable applications recognize as a sign of congestion, and throttle down in response. There are, however, a couple of down sized to the LIFO stack approach. A malicious or stupid node can continue to flood traffic, which will force packets from other streams to the bottom of the stack and cause them to drop, so a single stack per peer connection isn't a great long-term strategy. Secondly, single traffic streams that *do* play nice have trouble utilizing the full bandwidth of a link. Connecting two machines with GbE, I observe a line rate of about 928 Mbps, but running a benchmark over Ygg with LIFO stacks gives an unstable value around 850 Mbps. Third, there's some weird behavior if we have multiple connections (e.g. over different interfaces) to the same physical peer node. When we add a packet to the queue for one interface or another, we're committed to sending to that interface, even if another one sits idle. This means we usually use one interface, and ignore the others, which is bad if we happen to pick a stupid interface to use (e.g. we send over ad-hoc wifi with a weak signal, instead of GbE). That's how things behaved by the start of the v0.2 release cycle, but a lot of changes have occurred since then. ### The only winning move We can try to game theory our way out of this one. What we want is for multiple streams of traffic to be handled independently, to the extent that we can do so, given that the OS still manages TCP buffers out of our reach. Then, we can reward different traffic streams to prioritize based on lowest bandwidth (i.e. size of queue / age of oldest packet in queue, with a separate queue per traffic stream). Now we let traffic streams compete for bandwidth. The winning strategy, to get more bandwidth during times of congestion, is to attempt to use *less* bandwidth, which I argue is exactly the behavior we want to encourage. Streams of traffic that play nice get a fair share of bandwidth, which includes pretty much every sane TCP implementation, and streams that flood go to timeout. ### Yggdrasil's congestion control The current congestion control mechanism in Yggdrasil is back to using FIFO queues, with one queue per `coords`+`sessionHandle` pair (which translates to a separate queue per pair of communicating nodes), and a fixed total queue size of 4 MB (just to give it some kind of maximum). The packet forwarding procedure is then broken into two parts. The first part, when a packet is received, is: 1. Packets are received from a peer over a TCP connection and sent to a centralized switch worker goroutine. 2. The switch checks that there's at least 1 peer which is closer to the destination than we are. If not, then it passes the packet to the router (which either accepts it, if it's addressed to us, or drops the packet). 3. The switch iterates over *idle* peer connections and forwards to the one that's closest to the destination, as long as it's closer to the destination than we are. 4. If no closer peers have an idle connection, then the packet is queued (in FIFO order), with each stream of traffic (identified by destination coords, which currently embed the IPv6 flow ID field) getting its own queue. 5. If the total size of all queues is greater than the allowed maximum (currently hard-coded at 4 MB), then a random byte is selected. The first packet from the queue which contains this byte is dropped -- so front drops occur with odds proportional to the relative size of queues. This is repeated until the total queue size falls below the allowed maximum. A queue is deleted if the last packet is dropped. Then, whenever a peer connection finishes sending a packet, the following procedure is used: 1. The connection notifies the switch that it's idle. 2. The switch iterates over queues, skipping ones for which the peer is not closer to the destination, and finds the queue for which `/` is highest (i.e. the bandwidth it's trying to use is lowest). 3. If a queue was selected, then the oldest packet from this queue is sent. If the queue is now empty, then it is deleted. 4. If no queue was found, then the connection is added to the switch's idle list, so it can be considered immediately for incoming packets (the first part of the procedure, above). In my tests, this is sufficient to e.g. have a VoIP conversation or stream live video over a link that another node pair is flooding (via iperf3 or similar). If there are multiple connections to one peer, then traffic is sent over whichever one happens to be free (which is more likely in proportion to the speed of the link). My (admittedly limited) tests have seen this give about the same performance as if only the fastest link was used. As before, connecting two devices by ethernet, the hardware gets 928 Mbps. Yggdrasil manages about 926 Mbps after these changes, so overhead and unnecessary throttling from congestion control *should* be negligible compared to the tree's added stretch, which itself *should* be negligible in large networks, when compared to the cost of protocol traffic that would be needed by most other routing schemes. I can live with this. ### Future work: backpressure Yggdrasil's congestion control mechanism wasn't designed arbitrarily, there's somewhere I want to go with this. [Backpressure routing](https://en.wikipedia.org/wiki/Backpressure_routing) as a utility-maximizing routing scheme based entirely around queue sizes. If nodes communicate changes in queue sizes with their neighbors (at some point, e.g. whenever another packet or keep-alive traffic is sent), then we can use a combination of the tree distance metric + queue sizes (in packets) to *route around congestion*. Furthermore, if tuned properly, backpressure routing is [basically optimal](https://arxiv.org/abs/1008.4895) in terms of the latency/bandwidth trade-off. This means low-bandwidth traffic from low-latency applications could take the most direct route available, while bulk data transfers would use multiple and/or longer routes. It's difficult to overstate how nice this would be, *if* this doesn't confuse existing applications, but I'm not certain how well it will really work. It is entirely possible that real applications, like anything using TCP, may hate the way backpressure routed traffic looks, and throttle down in response. Then we're back to everything using the shortest route it can find, where low-bandwidth traffic is already given priority, so all we'd accomplish by sending queues sizes around is wasting bandwidth. Still, because we won't really know without trying, adding the required new packet types and testing backpressure is tentatively planned for a future release. ### Conclusion Yggdrasil has gone through a number of different congestion control mechanisms since the TCP link layer was introduced. The current congestion control mechanism rewards traffic streams which utilize less bandwidth by prioritizing them higher than streams using more bandwidth. Cooperative streams obtain a fair share of bandwidth, while streams which attempt to use more than their fair share are given lower priority, and are forced to throttle down as a result. When packet drops become necessary, a random drop mechanism is used which penalizes large queues the most, which should signal congestion to the worst offenders. Much of this is a precursor to backpressure routing, which, if it works out in practice as well as it does on paper, should give the network a nearly-optimal latency/bandwidth trade-off. Of course, you shouldn't just take my word for any of this. Every good experiment is reproducible. In an upcoming post, I plan to go over some performance studies, to show off some of the areas of Yggdrasil described so far, with instructions for how to reproduce the tests, and comparisons to other approaches where possible. --- ## File: _posts/2018-11-06-crypto-key-routing.md --- layout: post title: "Crypto-Key Routing" date: 2018-11-06 23:00:00 -0000 author: Neil Alexander unlisted: true --- ### Tunnelling over Yggdrasil Up until now, Yggdrasil has worked entirely using internal addressing from the `0200::/7` range. These addresses are cryptographically bound and allow end-to-end communication between any two given nodes. However, this approach is somewhat limiting in that it assumes an Yggdrasil node is, at most, a gateway for a single /64 IPv6 subnet. This therefore meant that it is very difficult to route between or bridge two networks without using another encapsulation protocol such as GRE. It also meant that it was very difficult to provide access to networks like the Internet internally. Today I created a pull request which implements Crypto-Key Routing (CKR), which you may already be familiar with if you have used Wireguard. The premise behind CKR is that it allows you to define routes stating that specific subnets should be routed to a given node on the network, identified by their public encryption key. The traffic is encrypted end-to-end, as normal, and sent to the specified node, otherwise completely unmodified. This gives us effectively the ability to run VPNs over the Yggdrasil network without the need for additional software. ### Configuration The new CKR module proposes the addition of some new configuration options. They are summarised below, although may be subject to change at the point that v0.3 is released: ``` TunnelRouting: { Enable: false IPv6RemoteSubnets: {} IPv6LocalSubnets: [] IPv4RemoteSubnets: {} IPv4LocalSubnets: [] } ``` The `IPv6RemoteSubnets` and `IPv4RemoteSubnets` options are used to specify crypto-key routes. The subnet refers to an encryption public key of another node, for example: ``` IPv6RemoteSubnets: { "fd64:642b:1a20::/48": "ef78da7fc983c6c210609529921a701ca3e43fa5cfd79f5f20cc67bf66e45c1a", "fd25:8a33:9311:a53b::/64": "417fd0a66a104f050ae3544b3bc03eeb3648dded4a8c1fb085d65ffa25e83d6e" } ``` As with a typical routing table, more specific routes are preferred. The `IPv6LocalSubnets` and `IPv4LocalSubnets` options are used to specify which source addresses are eligible to be routed across a tunnel. These options are mandatory. ### Bridging networks Assume that node A is `a.a.a.a/24` and `aaaa:aaaa:aaaa:aaaa::/64` and node B is `b.b.b.b/24` and `bbbb:bbbb:bbbb:bbbb::/64`. On node A, use the following `TunnelRouting` configuration: ``` Enable: true IPv6RemoteSubnets: { "bbbb:bbbb:bbbb:bbbb::/64": "xxxxxxxxxxxxxx" } IPv6LocalSubnets: { aaaa:aaaa:aaaa:aaaa::/64 } IPv4RemoteSubnets: { "b.b.b.b/24": "xxxxxxxxxxxxxx" } IPv4LocalSubnets: { a.a.a.a/24 } ``` On node B, use the reverse `TunnelRouting` configuration: ``` Enable: true IPv6RemoteSubnets: { "aaaa:aaaa:aaaa:aaaa::/64": "xxxxxxxxxxxxxx" } IPv6LocalSubnets: { bbbb:bbbb:bbbb:bbbb::/64 } IPv4RemoteSubnets: { "a.a.a.a/24": "xxxxxxxxxxxxxx" } IPv4LocalSubnets: { b.b.b.b/24 } ``` The Yggdrasil TUN/TAP adapters on each side can now be used to tunnel between `a.a.a.a/24` and `b.b.b.b/24` in IPv4 and `aaaa:aaaa:aaaa:aaaa::/64` and `bbbb:bbbb:bbbb:bbbb/64` in IPv6. ### Conclusion It is my hope that this will be merged into the `develop` branch soon, and will be a feature targeted for general release in v0.3. With this, Yggdrasil is able to take on more advanced routing tasks and will hopefully be more useful in a wider range of scenarios. --- ## File: _posts/2018-12-12-announcing-v0-3.md --- layout: post title: "Announcing Yggdrasil Network v0.3" date: 2018-12-12 00:00:00 -0000 author: Neil Alexander, Arceliar --- ### It's finally here At the end of 2017, Yggdrasil's first commit was uploaded to GitHub - a project to explore whether it was possible to build a decentralised, end-to-end encrypted and scalable compact routing scheme modelled around the concept of a global spanning tree. Many concept routing schemes that we have seen to date seem to have problems with scalability - after the network exceeds a certain size, they either fail to perform or they start to rely on centralised points in order to consolidate routing information. We want to figure out how to build something that would not be subject to these limitations, and to maintain decentralisation as far as possible, and the best way to test our ideas is to build that network. To our knowledge, this hasn't quite been achieved before. Throughout the course of 2018, Yggdrasil has gone from being a very early-stage project supporting only a single platform to a feature-strong and relatively stable project which now runs on many supported platforms. Although we currently still haven't advanced from the "alpha" label, our network has grown to exceed 70 nodes across the world (and growing slowly but steadily), with a good portion of these users coming on-board and contributing their own [services](https://yggdrasil-network.github.io/services.html) to the network and using the network for their own purposes. We've even had a small amount of publicity - [Toronto Mesh](https://tomesh.net) have been exploring using Yggdrasil on their city-wide mesh net, and even [presented some Yggdrasil fundamentals](https://www.nuug.no/aktiviteter/20181009-mesh/) to the Norwegian Unix User Group (NUUG) back in October. So far, we believe that Yggdrasil is well on track to delivering on its promises to build a fully end-to-end encrypted, self-arranging IPv6 network. We also believe that Yggdrasil should be scalable on paper; we have somewhat proven this in simulations, but the real proof will come in how the Yggdrasil Network scales up in the real world, on real hardware, across real links. Having users helping us to test brings us closer to our goal and enhances our understanding of how our software will behave on large-scale network graphs. Version 0.3 has been quite some time coming - we released version 0.2.7 on the 13th October and we have been working since then on what will make it into this release. Even though it feels in some ways that version 0.3 is a relatively small evolutionary release, it's actually by far our biggest release yet. We've included quite a large list of fixes, changes and even new features and over 2000 lines of code changed. We've taken a lot of feedback from our users about their use-cases and pain points, and we've collected topographical data from various contributor nodes to try and get a good view of what the network looks like. We've even experienced some rather large topology changes and enjoyed relatively good network stability throughout. For much of the time that we were developing v0.3, we had thought that there would end up being protocol-breaking changes and that this would render v0.3 incompatible with nodes running previous versions. I am happy to announce that we have **not** needed to introduce breaking changes at this stage and currently the network has been running a mix of both older and newer developmental nodes without any particular issues. ### Features You can see the full list of modifications that have been made in our [changelog](https://yggdrasil-network.github.io/changelog.html). Perhaps the largest user-visible change is the introduction of Crypto-Key Routing for traffic tunnelling, allowing you to effectively use Yggdrasil as a VPN for both IPv4 and IPv6 traffic between any two given points on the network. This tunnelled traffic enjoys the same benefits as regular Yggdrasil IPv6 traffic in that it is end-to-end encrypted and our many optimisations assist in preventing TCP-over-TCP anomalies that often arise in other solutions. I wrote an introductory [blog post](https://yggdrasil-network.github.io/2018/11/06/crypto-key-routing.html) back at the beginning of November about CKR, which explains some more about how to configure it and how it works. In the background, we've made a substantial change from using a Kademlia-based DHT to a Chord-based DHT. The Chord-based approach allows us to do lookups with `O(1)` (constant) state, and only depends on additional (`O(logn)`) state as a performance optimisation, which allows us to bootstrap more quickly after changes. We also believe that using Chord can help us to reduce some idle DHT chatter on the network in the future, which will save a little bandwidth, and may be helpful on battery-powered devices. The spanning tree is now constructed a little differently. Previously, in a stable network, each node would select a new parent only if this reduced the length of the path to the root of the tree, measured by the number of other Yggdrasil nodes in the path. This has the virtue of simplicity, but it sometimes leads to poor performance when a node replaces a few low-latency/high-bandwidth local links with a comparatively high-latency/low-bandwidth link over the internet (or an anonymous overlay like [Tor](https://github.com/yggdrasil-network/public-peers/blob/master/other/tor.md) or [I2P](https://github.com/yggdrasil-network/public-peers/blob/master/other/i2p.md)). Starting with this release, nodes will switch to a new parent if it provides a consistency lower latency path to the root, and its less eager to immediately switch again after having just changed parents. This should lead to lower latency in stable networks, and better reliability in unstable ones. We've fixed a reasonable number of bugs and crashes, including in the DHT, switch and ICMPv6 code, and have made a number of additions to the admin socket in order to support new functionality and to make parameter naming more consistent throughout. ### Upgrading Our CI pipeline automatically produces builds for all supported platforms and these will become available on our [Builds page](https://yggdrasil-network.github.io/builds.html). In addition, our S3 repository for Debian and RPM-based distributions will also be updated with the new package releases. New macOS .pkg installers are now available as a part of the v0.3 release too, so installing and upgrading on macOS is now significantly easier than before. You can find these installers on the [Builds page](https://yggdrasil-network.github.io/builds.html) also. On other platforms, simply download the latest binary for your platform and drop it into place. Remember to take a backup of your configuration and normalise it, which will add any new options for features in v0.3: ``` cp /path/to/yggdrasil.conf /var/backups/yggdrasil.conf yggdrasil -useconffile /var/backups/yggdrasil.conf -normaliseconf > /path/to/yggdrasil.conf ``` ### What's next? Our work is far from over. We still have a list of things that can potentially be rolled into future releases and we will be looking to see what we should prioritise for our next version. A big thanks to our contributors, particularly those who have worked on creating packages for Yggdrasil and bringing it to their distributions of choice, and to all of the users who use Yggdrasil, contributing services and providing feedback to us on a regular basis! --- ## File: _posts/2019-01-08-history.md --- layout: post title: "History of the World Tree, Part I" date: 2019-01-08 23:00:00 -0600 author: Arceliar --- ### How did Yggdrasil get started? On a few occasions I've been asked about how Yggdrasil was started, or what motivated certain things about the design. I've talked about the motivation and technical details in other blog posts, but I haven't talked about the history before, so I thought it's about time. ### B.A.T.M.A.N. begins The first time I can recall hearing about mesh networks, as a concept, was some time in late 2010 or early 2011, when [B.A.T.M.A.N.](https://www.open-mesh.org) [reached the mainline Linux kernel](https://kernelnewbies.org/Linux_2_6_38#B.A.T.M.A.N._mesh_protocol). I liked the idea, but since I obsess over how things scale, I was worried about the network's ability to cope with an internet-like number of users. In B.A.T.M.A.N., as in most other protocols, nodes must either rely on some externally configured (and coordinated) subnetting, or else every node in a network must know about every other node in the network. In particular, each node periodically sends a broadcast packet through the network, which allows the rest of the network to find a path back to the originating node. Other approaches, such as [AODV](https://en.wikipedia.org/wiki/Ad_hoc_On-Demand_Distance_Vector_Routing), only search for routes when they're needed, but the same `~O(n)` cost applies for each node in a network with `n` nodes. At a certain point, particularly in a shared medium wireless network, the cost of protocol traffic can become larger than the resources available to the network, and so the network no longer has room to route any traffic for the user. ### CJDNS I came across [cjdns](https://github.com/cjdelisle/cjdns) in the summer of 2012. The thing about cjdns that caught my attention was how it used a [Distributed Hash Table](https://en.wikipedia.org/wiki/Distributed_hash_table) to allow each node to look up a path to any other node, instead of relying on broadcast traffic. The idea being, if you can use a DHT instead of broadcast traffic, then you can just throw the whole network into one large subnet, with "flat" identifiers (IP addresses) that have nothing to do with the position of a node in the network. Then, since you still need some way to assign addresses, you can derive them from a hash of a node's public encryption key. That simultaneously addresses the protocol overhead issue, address assignment, and lets you do end-to-end encryption without depending on public key infrastructure. What could go wrong? Well, the best short example I can give, is to imagine that Alice wants to deliver a package to Carol, and they live in a world without maps or addresses, and where you can't rely on directions like "go North by any route until you reach X", so everyone needs to memorize any roads or routes that they care about. Alice doesn't know where Carol lives, but she knows where Bob lives, and she has reason to believe that Bob knows where Carol lives. So, Alice visits Bob and asks for directions to Carol. Bob tells Alice how to get from Bob's house to Carol's house, and Alice memorizes this. Now, any time Alice wants to deliver a package to Carol, she travels form her house to Bob's house, and then from Bob's house to Carol's house. If anyone asks Alice for a path to Carol, she will give them the path from herself to Carol, including the unnecessary detour past Bob. If someone knows enough about the layout of the streets to recognize the detours, or otherwise know that there's a shorter path between two points somewhere on the route, then they could improve upon this path, but *in general* this doesn't happen, because nobody knows enough about the layout of things to see the big picture of where everything is. That's basically how cjdns routing worked before supernodes were introduced. Supernodes keep a (centralized) view of the full network, and then other nodes can ask a supernode (instead of doing DHT lookups) for a path. Ignoring any technical complaints I may have about that approach, it sidesteps the problem I'm interested in solving, so I stopped actively contributing to cjdns once the decision was made to go that route, and started looking for other ways to solve the routing problems cjdns had faced. ### Just like the simulations By around the middle of 2015, I had thrown together a basic skeleton of a network simulator in python, so I could compare the paths that different routing schemes find to the shortest paths through the same networks. Having studied up on the latest and greatest academic works at the time, I had initially been thinking that something resembling Thorup and Zwick's universal compact routing scheme made the most sense, but I had issues finding a way to implement that *securely* as a distributed algorithm running on a dynamic network. To make a long story short, I ultimately took the most inspiration from [Robert Kleinberg](https://en.wikipedia.org/wiki/Robert_Kleinberg)'s approach, which is to use a [greedy embedding](https://en.wikipedia.org/wiki/Greedy_embedding#Hyperbolic_and_succinct_embeddings). Here's the thing, the Kleinberg approach grows a spanning tree of a (static) network, and embeds the tree in the hyperbolic plane, then proves that this embedding is always greedy (meaning, if you just forward to the point in the metric space closest to the destination, you'll never hit a dead end). The only real difference is that Yggdrasil doesn't bother to embed the tree in the hyperbolic plane. Instead, each node remembers the path from the root to itself, and we use these paths to calculate distance apart on the tree. This saves us the trouble of embedding, and we'd need to know the per-hop tree information *anyway* to securely build the tree, so this saves us some complexity. Using a DHT, we can look up *who* we want to talk to (specified by an IPv6 "address", which is a flat identifier / hash of a key, as in cjdns), we can learn *where* they are on the spanning tree. Then, when a node needs to forward a packet, it checks the tree location of each of its peers and forwards to whichever one is closest to the destination (+- a few caveats about congestion control). This is explained in more detail in earlier blog posts, if you're not familiar with how Yggdrasil routes and care to read more. In our package delivery example, imagine if the streets in Alice's town were laid out in a grid, and then named and numbered systematically by blocks, with street signs to label where any off-grid bypasses go. Alice and friends still haven't bought maps, but they know each other's *addresses* instead. So, if Alice wants to contact Carol, she first travels to Bob's house and asks him for Carol's address. Now, when she wants to deliver a package to Carol, she can simply follow the block structure of the town until she arrives on Carol's block, and she has the option to take any bypass she happens to come across if it brings her closer to Carol's place. That's basically how routing on the tree, or taking an off-tree shortcut, work in Yggdrasil's greedy routing scheme, except with a tree instead of a grid (which, in addition to working everywhere, seems to work *well* in the places we care about). I had most of the important parts of this working, in simulations, by mid September of 2015. Initially, I also included off-tree distance-vector like routes to nodes where the on-tree path would be too long, but I abandoned this once I saw that it added relatively little (except protocol overhead) for the kinds of networks that tend to show up in practice, including some internet topology maps from CAIDA and DIMES. In particular, it seems to work well any time the network diameter is small and the number of triangles in the network is large, since the former limits the worst case scenario paths that the network can use, and the latter adds many opportunities for off-tree shortcuts. ### Going public Having (mostly) finished simulation tests by about spring of 2016, I sat on the idea for a while, trying to work up the motivation to do anything with it. I eventually sat down one weekend and worked through [gobyexample](https://gobyexample.com/). The language seemed fast enough for a reasonable prototype, easy enough to learn/read that other people could pick it up quickly if they want to contribute, and generally made multithreading/multiprocessing bearable for me. Since I wanted to continue playing with the language, and I'd been meaning to implement my routing scheme for a while, I ultimately resolved to rewrite my sim in Go, refactor the important parts into the library, and then add the missing pieces to make it more-or-less a cjdns clone with different routing. Most of the work happened over a couple of long weekends, and I released the first working prototype on GitHub just before the end of 2017. Changes since then are mostly documented in the `git log`, GitHub issues and pull requests, and discussions in our public matrix channel. Neil joined and started adding support for other platforms, and we started to roll out public nodes and attract more users. As of writing, a year or so after the first public release, there are around 130-140 nodes in the network, depending on the time of day, with maybe half of them having joined in the last few months. --- ## File: _posts/2019-03-24-peering.md --- layout: post title: "Practical peering" date: 2019-03-24 23:00:00 -0500 author: Arceliar --- ### How many peers do I need, and which ones? Perhaps the most common questions we receive are about peering. If you're not familiar with how Yggdrasil works, or even if you are but you haven't tested things carefully, then it's sometimes easy to do things which seem like they should work right, but lead to higher latency and lower bandwidth for you or nodes that depend on you in the network. This post is meant to explain what happens when the wrong peers are selected, and what you can do to avoid it. ### The problem When building a physical network, the cost of adding a link between two nodes, as well as the benefits that having that link would give, play a role in deciding which nodes are ultimately linked. That cost often correlates with the cost of using the link -- long links are more expensive to create and have higher latency than short links of the same type, for example, and there's no point in adding a link to another node unless it's worth the cost. Yggdrasil is designed to work well on the kinds of networks we see in the real world, and makes implicit assumptions which benefit from the relationship between the higher cost to both create and use a long link. However, when peering Yggdrasil nodes over the internet, the performance difference between two links can be dramatic, but the cost of creating them is always the same: there is no difference between adding a link over the internet to a node if it's 1 km away or 1000. As a result, it's easy to add links over the internet which would make no sense if deploying dedicated infrastructure, and can violate some of Yggdrasil's assumptions as a result. This can lead to worse performance for not only the two linked nodes, but other nodes in their area. ### Rules of thumb In an effort to clarify how nodes should connect to public peers, and how public peers should connect to each other, I think it's helpful if we establish some rules of thumb: 1. When deciding if to connect to another node, you should only connect to the ones that are "good enough" to be worth the effort. Here, "good enough" means that they have as much (approximately) at least as much bandwidth as your own. A fast node shouldn't decide to connect to a slow node, instead the slow node should decide if it wants to connect to the fast one. 2. When connecting to nodes, start with the "closest" (lowest latency) nodes, subject to the above constraint, and work your way out. Try not to skip over (equal or better) nodes if there's no reason to. While this may not be the only way to fix the problem, following these rules of thumb should approximate the kinds of constraints that real networks need to deal with. Nodes tend to connect to whoever is closest, and better nodes tend to skip over worse ones to establish a long range "backbone" connection between remote points. In addition, the number of peers you want to add depends on what you want to do. If you only want to connect to the network, then 1 (better connected) peer is technically enough, but this acts as a single point of failure. Two to four peers adds some redundancy, but keep in mind that you may end up routing traffic between these peers if that ends up being the best route they can find. If your goal is to set up a public peer that can route traffic for the network, and you have enough bandwidth to spare, then keep adding peers. Generally speaking, an asymmetric home internet connection shouldn't try to route traffic. And, wherever possible, replace internet links with real connections over directional wifi or similar -- to avoid having multiple peers share bandwidth over a shared link. ### What happens when things go wrong Let's imagine we have some nodes in New York, and initially they follow the peering rules outlined above. Now suppose that two of these nodes decide that they want to add connections to London. In Yggdrasil, nodes tend to select parents that minimize latency to the root, which happens to be a node in Paris at the time I'm writing this. As a result, both of the NY nodes are likely to select their respective London peers as their parents. If the nodes are following the peering rules, then at least one of them has also decided to peer with the other, so they have a shortcut they can use to talk to each-other (or any descendants in the tree). However, if they ignore the peering rules and *don't* peer with each other, then they are likely to route through London instead of communicating over their local mesh network. A shorter path exists, through their local mesh network, but it's not one that the network *must* know about for routing to work, so they won't necessarily know about it. As a result, the latency between these two nodes (or decedents thereof) will likely be an order of magnitude more than it needs to be (and probably lower bandwidth as well). ### Conclusion Yggdrasil was designed with scalability in mind, and to that end, it makes some assumptions about how nodes in the network are connected to avoid communicating unnecessary information. Peering over the internet allows you to violate these assumptions. When this happens, it's possible for network performance to suffer unintended consequences when adding new links. If you prioritize adding new links the same way as you would when building physical links, you can expect lower latency and, in many cases, higher bandwidth, compared to adding peers at random. --- ## File: _posts/2019-08-03-release-v0-3-6.md --- layout: post title: "Version 0.3.6" date: 2019-08-03 08:00:00 -0000 author: Neil Alexander --- ### New release! It's been nearly five months since we released version 0.3.5 of Yggdrasil. In that time we've seen the node count rise to over 400 nodes on the public network at times (over 80% of which are running the latest released version) and we've gained valuable insight to the kinds of challenges that our users have. We've worked to fix a number of bugs and to improve Yggdrasil. In terms of lines of code changed, version 0.3.6 is the biggest release of Yggdrasil to date, with several thousands of lines of code affected. It represents a massive refactoring exercise in which we've broken up and modularised the code, dividing core Yggdrasil functionality, TUN/TAP, admin socket and multicast features into their own respective Go packages. ### Fixes Most of the user-facing changes in this release are fairly minimal, however some bugs have been corrected. A complete list is available in the [changelog](/changelog.html). Highlights include peers now being added correctly even when one or more configured peers are unavailable or unreachable. Multicast interfaces are also being evaluated more frequently now, which can help if an interface becomes available or goes down after Yggdrasil has already started. A number of bugs have been fixed in the TUN/TAP and IP-specific code, including problems that affected ICMPv6 and Neighbour Discovery in TAP mode specifically. This helps reliability on platforms where TAP mode is used more commonly, e.g. on BSD platforms or on Windows, although this also improves TAP support on Linux too. ### Refactoring and API Around the previous release, it became obvious to us that our codebase was turning into a monolith. We had pretty much all of the necessary behaviour in a single `yggdrasil` package to run a single node, but this made our codebase inflexible and difficult to maintain and extend. It also meant that Yggdrasil was virtually impossible to integrate into other applications. Our refactoring efforts in version 0.3.6 mean that our codebase is now easier to manage and to understand. It also includes the first taste of our API! The API makes it possible to take the Yggdrasil core, drop it into your own Go application and use the Yggdrasil network as a fully end-to-end encrypted and distributed transport layer. We've also moved all of the IP-specific code into the TUN/TAP module, which means that Yggdrasil's core now provides a completely protocol-agnostic transport. Documentation on how to use the API to integrate Yggdrasil into your own applications will follow soon—watch this space! In the meantime, [`godoc` can be used to examine our new API functions](https://godoc.org/github.com/yggdrasil-network/yggdrasil-go/src/yggdrasil). Please note though that **API functions are not yet finalised and may be subject to change** in future versions. Yggdrasil is still alpha-grade software at this point so all of the usual warnings apply. ### Platform Support We enjoy great support from our community in bringing and packaging Yggdrasil on new platforms. Since the release of version 0.3.5, the following third-party packages have cropped up, and we are very grateful to the maintainers: - A [new RPM build](https://copr.fedorainfracloud.org/coprs/leisteth/yggdrasil/) for Red Hat, Fedora, CentOS etc. - An [AUR package](https://aur.archlinux.org/packages/yggdrasil-git/) for Arch Linux - A [Void package](https://github.com/void-linux/void-packages/tree/master/srcpkgs/yggdrasil) for Void Linux - A [MacPorts package](https://github.com/macports/macports-ports/blob/master/net/yggdrasil-go/Portfile) for macOS We expect that any third-party packages which have not yet been updated for v0.3.6 will be updated soon! We are aware of a few outstanding issues with Windows, which are largely related to one or two bugs in the [Water](https://github.com/songgao/water) library which we use for TUN/TAP support. We are hoping to address these problems with the maintainer of this library soon. Using Yggdrasil in router-only mode does work as expected, but some bugs when using the TAP adapter still remain. In the meantime, we'd certainly welcome any assistance in maintaining the Windows port of Yggdrasil. The iOS build has been largely neglected due to API changes, although hopefully a new TestFlight build for version 0.3.6 will be available before too long. ### Upgrading We recommend that all Yggdrasil users always run the latest version of the code wherever possible, so please upgrade as soon as it is convenient. New downloads are available from our [Builds](/builds.html) page and [Neil](https://github.com/neilalexander)'s S3 repositories are up-to-date for Debian and EdgeRouter installs. If you have installed through a package manager, you should be able to upgrade in-place as soon as the new packages are available. On macOS, you can simply install the new `.pkg` from the builds page over the top of the old one. On Windows, and on any installation where the binary was installed by hand, you can simply replace the `yggdrasil` and `yggdrasilctl` binaries with the newly released builds. Building from source is simple if you have Git and Go 1.11 or later installed: ``` git clone https://github.com/yggdrasil-network/yggdrasil-go cd yggdrasil-go ./build ``` ### Feedback We always welcome feedback, so please do feel free to join us either in our [Matrix channel](https://riot.im/app/#/room/%23yggdrasil:matrix.org) or on IRC in `#yggdrasil` on Freenode. You can also raise bug reports and issues in [our GitHub repository](https://github.com/yggdrasil-network/yggdrasil-go/issues). --- ## File: _posts/2019-08-19-awdl.md --- layout: post title: "Meshing using Apple Wireless Direct Link (AWDL)" date: 2019-08-19 08:00:00 -0000 author: Neil Alexander --- ### Wireless without borders I was mostly prompted to write this post in response to a [Hacker News thread](https://news.ycombinator.com/item?id=20735462) recently, which announced the release of an open-source AirDrop implementation called [OpenDrop](https://github.com/seemoo-lab/opendrop), from the same team at Seemoo Lab who produced an open-source implementation of Apple Wireless Direct Link (AWDL) protocol called [OWL](https://github.com/seemoo-lab/owl). AWDL is the secret sauce behind AirDrop, peer-to-peer AirPlay and some other Apple wireless technologies. Even though everything covered in this post was done some time ago, I have never spent the time to document it. With a few exceptions, most wireless networks in the world operate in "infrastructure mode" which is where a wireless access point serves one or more wireless clients. Think of your Wi-Fi at home, at work or in a coffee shop. However, as implied by the name, reliable and usable infrastructure Wi-Fi is often only available in certain physical locations with "good infrastructure". If you wanted to connect some devices together anywhere not served by an infrastructure Wi-Fi network, or in a location where you can't suddenly plug in a wireless access point, you may not have many options (Bluetooth aside). AWDL is designed to avoid this problem by extending the 802.11 wireless standard to allow client devices to communicate directly with each other, without the help of the central wireless access point. You can walk out into a field with a couple of iPhones or Macs and they can use AWDL to discover each other and exchange data, peer-to-peer. Even better is that nearby devices that are connected to different infrastructure Wi-Fi networks can still communicate with each other using AWDL! ### The science Normally, when connected to a wireless access point, wireless clients remain locked to the specific radio channel that the AP is using. AWDL works by instructing the wireless adapter in the device to "hop" between channels so that it can not only remain connected to the wireless access point, but can also listen to other nearby devices. Devices announce their presence and information about their services on a "social channel" for other devices to hear, effectively creating peer-to-peer service discovery. Once two devices have decided that they want to communicate directly, they agree to jump to another channel for real data exchange so that they don't interrupt existing Wi-Fi networks or, indeed, the social channel. These "hops" between wireless channels happen so quickly that there's very little disruption to what the user is doing with their Wi-Fi connection already (except for some minor wireless performance degradation - to be covered later). A number of papers have been published by the OWLink team on the inner workings of the AWDL protocol, which can be [found here](https://owlink.org/publications/). In particular, [this paper](https://arxiv.org/pdf/1808.03156.pdf) from Mobicom 2018 contains a significant amount of detail about the AWDL protocol itself, channel hopping techniques and security considerations, amongst other things. ### Mesh opportunities Yggdrasil is designed to create a mesh network automatically out of interconnected nodes - the idea being that all nodes can route to all other nodes on the mesh network by routing through other nodes. Today, many of these connections happen between nodes across the Internet, since the community is still relatively small and geographically dispersed. A node joining the Yggdrasil network needs to only peer with a single device that is already connected to the wider network in order to participate in the fully-routable mesh. However, it's not the goal of Yggdrasil to remain something that we just toy with over the Internet. We want to build a protocol that can scale globally and work ad-hoc, even in places where infrastructure might not be particularly strong otherwise. We think that one of Yggdrasil's greatest strengths is that it is very close to zero-configuration, beyond giving it a very small number of configuration options, and it should scale well too in principle. Yggdrasil can already discover potential peers on the same network segment by using multicast service discovery, which sounds a lot like what AWDL does on the social channel. You can configure which interfaces Yggdrasil beacons on with the `MulticastInterfaces` configuration directive. I wanted to know if we could blend the two so that Yggdrasil could automatically discover other nearby devices and initiate peering connections with them using AWDL. ### Getting started Macs are a good target for developing and testing AWDL-aware applications as AWDL is exposed to userspace through a network adapter called `awdl0`. It sits there with a link-local IPv6 address, you can run `tcpdump` or Wireshark on it to listen to AWDL traffic and you can even ping multicast group addresses on the interface and get responses from other nearby devices, e.g. using `ping6 ff02::1%awdl0`! However, Apple devices don't always keep AWDL alive and listening all of the time. On macOS, the AWDL driver is only woken up when either AirDrop is being actively used in Finder, or where a `NetService` has been created (usually through Objective-C or Swift) which requests peer-to-peer networking. AWDL is normally kept alive long enough to satisfy connectivity for these sessions and then will be sent back to sleep after a period of idleness. On iOS, the story is somewhat similar to above, except that AWDL is often woken up as soon as the device is unlocked if AirDrop is enabled. The `NetService` API otherwise functions the same way. tvOS is the outlier in that it seems to wake up and listen to AWDL randomly, even when the device is otherwise asleep, presumably because it is advertising the ability to receive incoming AirPlay sessions to nearby devices. From a user perspective, the `awdl0` interface looks entirely unremarkable. It behaves largely like any other ethernet interface, carrying regular IPv6 traffic. In the background it's a bit more complicated, as the AWDL driver performs traffic filtering for security reasons, namely, to stop someone sat next to you in the airport from browsing your file shares. Regular listening sockets won't accept connections over AWDL unless a specific socket option was configured on the socket before it started listening. Multicast traffic, however, does largely get passed through the filter untouched. Bingo. ### Waking up AWDL The `NetService` API is effectively a wrapper around multicast DNS-SD, which in Apple's colourful language, is affectionately known as Bonjour. The API has the added benefit of being able to tell the operating system to wake up the AWDL driver pretty much on demand on behalf of "peer-to-peer" services. So all we would need to do to wake up AWDL is to call the `NetService` API, publish a service that requests peer-to-peer functionality and let the operating system do the hard work for us. Yggdrasil, being written in Go, didn't have any concept of `NetService` but thankfully we were able to use Cgo to do this instead. We wrote a Cgo function which calls the NetService API and advertises our new fake service, `_yggdrasil._tcp`, which causes the operating system to wake up the AWDL driver. Amazingly this worked. Yggdrasil doesn't actually use DNS-SD - we currently use a custom-formatted multicast beacon on a different multicast group. It is planned to eventually migrate to something more standard, like DNS-SD, for service discovery. However, in this instance, registering a fake DNS-SD service was just enough to wake up AWDL. ### Peering automatically Once the driver is active, the regular Yggdrasil multicast beacons on the `ff02::114` multicast group address seem to be passed through to the driver normally and the Yggdrasil nodes running on each machine start to hear each other's calls. The only thing that remained to be done was to configure the sockets with the aforementioned socket option to allow them to communicate over the AWDL interface. This socket option is called `SO_RECV_ANYIF` and is defined in `sys/socket.h` on Darwin as `0x1104`. We configure the socket option on our TCP peering socket: ``` err = unix.SetsockoptInt(int(fd), syscall.SOL_SOCKET, 0x1104, 1) if err != nil { ... } ``` Now that the Yggdrasil nodes can hear each other's advertisements over the `awdl0` interface, the regular automatic peering process kicks in and a TCP session is opened between the two devices, creating a peering. The net result? AWDL peerings! ``` $ sudo yggdrasilctl getSwitchPeers bytes_recvd bytes_sent coords endpoint ip port proto 1 244278 313907 [3 5 5 2 1] fe80::xxxx:xxxx:xxxx:xxxx%awdl0 xxxx:xxxx:xxxx:xxxx:xxxx:xxxx:xxxx:xxxx 1 tcp ``` To further cement the experiment, we can actually disconnect the two devices from each other, or connect to different Wi-Fi networks automatically, and the peering over the `awdl0` interface still continues to function! An `iperf3` test over Yggdrasil using the new AWDL link looks fairly good - the devices are sat next to each other: ``` [ ID] Interval Transfer Bandwidth [ 5] 0.00-1.00 sec 15.4 MBytes 129 Mbits/sec [ 5] 1.00-2.00 sec 16.9 MBytes 141 Mbits/sec [ 5] 2.00-3.00 sec 15.9 MBytes 133 Mbits/sec [ 5] 3.00-4.00 sec 17.6 MBytes 147 Mbits/sec [ 5] 4.00-5.00 sec 16.8 MBytes 141 Mbits/sec [ 5] 5.00-6.00 sec 16.2 MBytes 136 Mbits/sec [ 5] 6.00-7.00 sec 12.5 MBytes 105 Mbits/sec [ 5] 7.00-8.00 sec 12.7 MBytes 106 Mbits/sec [ 5] 8.00-9.00 sec 14.9 MBytes 125 Mbits/sec [ 5] 9.00-10.00 sec 13.5 MBytes 113 Mbits/sec ``` ### Observations and iOS As the `iperf3` test above shows, the link performance is actually quite good! It routinely exceeds 100mbps, although this is between only two devices. I have not been able to test this with Yggdrasil nodes running over AWDL in any particular density due to only having a limited number of Macs to hand. One thing that I did notice though is that, while AWDL is active, my wireless connection to my home Wi-Fi network does reduce in speed somewhat. This is to be expected, given that the wireless chipset is hopping between channels rather than spending all of its time on a single channel. Sadly we weren't able to reproduce this test using iOS Testflight builds of Yggdrasil. On iOS, we implement Yggdrasil as a VPN service which is subject to a number of probably reasonable restrictions imposed by the OS, which presumably exist to stop VPN extensions from spying on you. We were able to create a `NetService` from within the VPN extension and the service beacons were advertised as expected, however, we weren't able to initiate any other kind of connections over the `awdl0` interface. After a chat with an engineer at Apple, it turns out that the `awdl0` interface isn't scoped for use within a VPN extension, thus squashing our hopes and dreams of being able to sprinkle this kind of magic onto our iOS port of Yggdrasil. We have a feature request radar open with Apple in the hope that they may be able to change this restriction in the future. But we were able to get this to work on macOS and that, itself, is quite awesome. ### Conclusion Yggdrasil doesn't enable AWDL by default because of the reduction in wireless performance that AWDL being active can cause. Therefore, to enable AWDL peering, you must add the `awdl0` interface specifically into the `MulticastInterfaces` configuration option in `yggdrasil.conf`. However, we do have working support for connecting Macs together and meshing automatically using AWDL, and you can enable it very easily if you wish to experiment! We'd love to hear if you are peering Yggdrasil nodes using AWDL, or have performed any more extensive tests of how it performs in real-world scenarios - join us on our Matrix channel. --- ## File: _posts/2019-09-01-actors.md --- layout: post title: "Acting out" date: 2019-09-01 21:00:00 +0000 author: Arceliar --- ### Overture We've recently rewritten much of Yggdrasil's internals to change from Go's native [communicating sequential processes](https://en.wikipedia.org/wiki/Communicating_sequential_processes) (goroutine+channel) style to using an asynchronous [actor model](https://en.wikipedia.org/wiki/Actor_model) approach to concurrency. While this change should be invisible to the average user, it dramatically changes what we developers need to think about when working on the code. I thought it would be useful to explain a little about the motivation for rewriting things this way, and what the consequences are. Caution: theatre puns and references throughout, because `Actor`s. ### Exposition Yggdrasil is written in the Go programming language. Go makes it easy to start a function running concurrently, and gives developers the tools they need to make concurrently executing functions communicate, but it's not always easy to use them correctly. To be clear, the things I'm about to rant about are all fixable. Working around them is a normal thing to do in Go. More importantly, it's a case where doing things the obvious way (which is sometimes even safe in isolation) leads to *wrong* behavior in a larger program. I prefer models where the obvious thing is still correct, and non-obvious things are only needed as a performance optimization. #### Composition There's a common pattern that has emerged many times in the Yggdrasil code base. We'll have a `struct` with some mutable fields that need reading or updating, such as information about a particular cryptographic session, or the switch's table of idle peers and buffered traffic. Since shared mutable state is hard, and Go is all about "[Share Memory By Communicating](https://blog.golang.org/share-memory-by-communicating)", we'll have packets get passed to a dedicated worker goroutine that "owns" that particular `struct`. The worker uses information from the packet and the owned `struct` to do whatever it is needs to do, updates these things accordingly, and passes the packet along to the next goroutine in the pipeline. This often results in a "`for select`" pattern, where goroutines sit in an infinite `for` loop and `select` on several channels, to wait for packets to process or various types of signals from other goroutines. There are a few ways around it (with heavy use of `reflect` or `chan interface{}`, for example), but in most cases, every `select` statement needs to fully enumerate every behavior that the goroutine may need to engage in at that point in the code. If there's a common set of `case`s that always need to be handled, and then a few exceptional `case`s that may or may not matter (possibly when the associated `struct`s the workers are using are similar but not exactly the same types, or as the state of a `struct`'s fields change), then that typically involves multiple `select` statements with only the addition or modification of one or two `case`s. Go embraces composition in its type system, but `select` statements (and channel operations in general) make execution resistant to composition. #### Deadlocks The "`for select`" pattern is safe, as far as I know, if the flow of messages through the program form a directed acyclic graph. However, in our case, cycles emerge if we try to handle things in the obvious way. For example, a cryptographic session needs to somehow get outbound encrypted traffic to the switch, but incoming encrypted traffic also needs to make it from the switch to the sessions for decryption (via the router, which is responsible for, among other things, identify which session is associated with the traffic). When cycles of goroutines naively pass messages over channels, deadlocks are all but inevitable. There are a few ways to address this, but they're not always appropriate. Ideally, we would change the design to remove cycles, but this is not always possible, and may require significant changes to the workflow in cases where it is possible. In practice, what we'd actually do is either buffer messages (having some dedicated reader goroutine to take the message, add it to a slice, and then pass it to the real destination ASAP) or drop messages entirely (with a `select` statement that aborts and does cleanup in a `default` case, or by having a dedicated reader that drops messages more intelligently, such as from the front of the queue, under the assumption that older messages are less useful). #### Leaks Typically, when a goroutine is started, it continues to run until either the function returns or the program exits. For this reason, if a goroutine executes any statements which can block (such as a channel operation), it's important to include some `case` which signals that it's time to return. Forgetting to do this can result in goroutine leaks. [Never start a goroutine without knowing how it will stop](https://dave.cheney.net/2016/12/22/never-start-a-goroutine-without-knowing-how-it-will-stop), or so the experts say. This is sometimes harder than it needs to be. To be blunt, the single producer N consumer cases are fine, you just close the channel and have all the consumers take this as a signal to exit. Anything involving multiple producers requires some sort of signaling to indicate that all producers have exited. Since you're using a channel already, the obvious option is a `select` statement with another channel that closes to signal shutdown, and then something like e.g. a [`sync.WaitGroup`](https://golang.org/pkg/sync/#WaitGroup) to wait for all producers to exit before closing the channel. Until your number of producers needs to change at runtime, and you realize that this races if you start to `Wait` before `Add`ing everything to the group, so you need to implement a custom counter, and be careful that additions and subtractions can also race and cause it to shut down early. And have fun solving it, because with how much `select` resists composition and code reuse, you're going to be implementing the same patterns over, and over, and over, and over... It's not that this is some impossible problem to solve, it's just that Go's take on the [CSP](https://en.wikipedia.org/wiki/Communicating_sequential_processes), combined with the rest of the tools the language gives you, makes it easy and concise to run thing the *wrong* way, and leads to comparatively complex and delicate code when trying to run it the right way. At least, that's my personal view of it based on my experience so far, but it probably varies some based on the problem the code is trying to solve. ### Rising action The [actor model](https://en.wikipedia.org/wiki/Actor_model) is another programming paradigm that embraces concurrency with a "share memory by communicating" philosophy. For our purposes, an actor is basically a data type with a few special properties: 1. It has an inbox where messages to the actor are placed. 2. It has an associated unit of execution, such as a thread, which processes messages from the inbox one at a time. 3. Rather than exposing ordinary functions for other code to call, the actor exposes *behaviors*. A behavior is a function which has no return value, and is executed only for its side effects. When an actor `A` calls a behavior of an actor `B`, what really happens is that `A` places a message in `B`'s inbox, and `B` processes that message by executing some code. Different implementations differ on details after that, such as what order messages are processed in, if actors are allowed to wait for a particular type of message before continuing, whether actors run locally or are distributed across a cluster, etc., but they tend to all include some version of the broad strokes above. ### Turing point I'm particularly fond of the [pony](https://ponylang.io) programming language's take on the actor model. I really can't say enough nice things about their approach, and fully describing it is beyond the scope of this blog post, but if you come out of here with an interest in the actor model, then I highly recommend checking out that language. Maybe watch a few of the talks from the developers that have been posted to YouTube, or read their papers about what is *easily* the most promising approach to garbage collection I've ever come across. Anyway, I don't actually work on anything written in pony, but I like their version of the actor model so much that I decided to see if I could trick Go's runtime into faking it. The result is [`phony`](https://github.com/Arceliar/phony), which manages to do most of what I want in under 70 lines of code. When we write code using this asynchronous message passing style, instead of ordinary goroutines+channels, the implications are pretty significant: 1. There are no deadlocks. Message sends always succeed, and are quite fast (it doesn't even require [CAS](https://en.wikipedia.org/wiki/Compare-and-swap) instructions in the normal case). 2. Inbox sizes stay small due to backpressure: if the sender sees that the receiver's inbox has too many pending messages, it will schedule itself to stop at some deadlock-free safe point in the future, to wait until the receiver signals that it's handled the message. 3. `Actor`s are *shockingly* lightweight: on a modern 64-bit processor, an idle `Actor`'s only resources are 24 bytes for an empty `Inbox`, some of which is padding that may not apply if embedded into a struct. In particular, an idle `Actor` with an empty `Inbox` has no associated goroutine, so it requires no stack. 4. The lack of a goroutine also means that idle `Actor`s, even cycles of `Actor`s, can be garbage collected automatically. 5. Any `struct` that embeds an `Inbox` satisfies the `Actor` interface. Since `Actor`s encapsulate their own unit of execution, it means the range of behaviors that unit of execution can engage in are encoded into the type system and can even be abstracted through `interface` types. In my opinion, the resulting code is cleaner, easier to read and understand, and far easier to reuse or extend than the `for select` pattern from goroutine+channel use. ### Falling action I'm happy enough with the current state of `phony` that I decided to start migrating the `yggdrasil-go` code base to use it. This is still work in progress (there are some non-`Actor` goroutines around the edges of the code, mostly in main `Accept` loops and that sort of thing), but the hot paths are now `Actor` based. Most of this was done in a weekend and came together with surprisingly little pain. I had exactly 2 crashes the entire time (1 accidental `nil` pointer deference and 1 legitimate bug I needed to fix in `phony`), and more importantly, 0 deadlocks. Most things just worked as intended the first time they compiled. There were a few bugs to work out when I was rewriting the `link` code, but nothing compared to the mess I had to deal with when writing the old code (which was a couple of horrifying interdependent `for select` loops to build a state machine). So by now you're probably wondering what any of this looks like in practice. Just to give a generic example, suppose we have some struct with an exported function that needs to run code on a worker goroutine. We could end up with something like the following when writing Go in the CSP style: ```Go // This is the function we want the worker to run. func (n *NonActorStruct) theFunction(arg1 Type1, arg2 Type2) { // this is where the code we actually care about goes, the rest is basically boilerplate } // This is the struct that we want the worker to own and manipulate. type NonActorStruct struct { inputForTheFunction chan argsForTheFunction // fields we care about, plus maybe more channels for other things } // Needed to initialize the channel to a working state func NewNonActorStruct() *NonActorStruct { n := NonActorStruct{ inputForTheFunction: make(chan argsForTheFunction), } return &n } // This is just a helper struct to carry arguments for the function. type argsForTheFunction struct { Arg1 Type1 Arg2 Type2 } // This is the function we export. func (n *NonActorStruct) RunTheFunction(arg1 Type1, arg2 Type2) { n.inputForTheFunction<-argsForTheFunction{arg1, arg2} } // This is needed to start the worker, otherwise things block. func (n *NonActorStruct) Start() { go func() { for { select{ // cases for other things we may need to do would also be here // presumably at least one is involved in safely shutting down case args := <-n.inputForTheFunction: // We could possibly have a switch statement here // Then switch on the arg type to pick which function to run n.theFunction(args.Arg1, args.Arg2) } } }() } // This is needed to stop the worker when we're done. func (n *NonActorStruct) Stop() { // Actual implemenation depends on what else the worker does in its loop, // but it probably just sends a specific message and/or closes some channel. } // Then to use the code, we have something like: myStruct := NewNonActorStruct() myStruct.Start() defer myStruct.Stop() // Or arrange this to happen somewhere else myStruct.RunTheFunction(arg1, arg2) ``` When migrating to the actor model, the basic pattern that emerged was to embed a `phony.Inbox` into any `struct` we wanted to make into a `phony.Actor`, and then define functions of the struct like so: ```Go // This is the function we want the worker to run. func (a *ActorStruct) theFunction(arg1 Type1, arg2 Type2) { // this is where the code we actually care about goes, the rest is basically boilerplate } // This is the struct that we want the worker to own and manipulate. type ActorStruct struct { phony.Inbox // This defines the Act function, satisfying the Actor interface // fields we care about } // This is the function we export. func (a *ActorStruct) RunTheFunction(from phony.Actor, arg1 Type1, arg2 Type2) { a.Act(from, func() { a.theFunction(arg1, arg2) }) } // And then to use it, an Actor x would run something like: myActor := new(ActorStruct) myActor.RunTheFunction(x, arg1, arg2) ``` And that's about it. The first argument to `myActor.RunTheFunction` also `nil`able, if we have non-`Actor` code that needs to send a message, it just means there's no backpressure to slow down the non-`Actor` code if it's sending messages faster than the `Actor` can handle them. A `phony.Block` function exists to help non-`Actor`s wait for an `Actor` to process a message before continuing, since this seems like a common enough use case (especially when a package wants to export a non-`Actor` interface that uses `Actor` code internally). What's great is that we don't need to think about starting or stopping workers, deadlocks and leaks are not possible outside of blocking operations (e.g. I/O), and we can add or reuse behaviors just as easily as any function. I find the code easier to read and reason about too. I/O is one rough spot, since an `Actor` can block on a `Read` or a `Write` and not process incoming messages as a result. This isn't really any worse than working with normal Go code, and the pattern we've adopted is to have separate `Actor`s for `Read` and `Write`, where one mostly just sits in a `Read` loop and sends the results (and/or error) somewhere whenever a `Read` finishes. These two workers can be children of some parent `Actor`, which is the only one the rest of the code needs to know about, and then all we need to remember to do is close the `ReadWriteCloser` (e.g. socket) at some point when we're done. This is the sort of thing that we'll eventually want to write a standard `struct` for, update our code everywhere to use it, and then never have to think about it again. In the meantime, we have a couple of very similar implementations for working with sockets or the tun/tap device. ### Dénouement The Go language makes concurrency easy, but for some problems it can be difficult to do safely out-of-the-box. However, the language provides the tools needed to implement an actor model approach very easily. While I won't claim that the actor model is a panacea for all development woes, Yggdrasil by its very nature requires us to think about networks of nodes communicating asynchronously, so it makes sense to use a programming paradigm that lets us model that approach more explicitly in our code base. Outside of a couple of corner cases (namely blocking I/O for the network sockets and the tun/tap device), we expect this to obviate any need to even thing about deadlocks, make development easier moving forward, and generally lead to a better user experience as a result. The code migration is still a work in progress, but `Actor`s have replace `for select` workers along the hot paths through the code (minus 1 crypto worker pool in the session code) and will slowly replace synchronization primitives in the remaining code base. The current code has been merged into our `develop` branch, and I'm quite excited to see it land in Yggdrasil `v0.3.9`, along with the usual bug fixes and incremental improvements, which we plan to release in the near future. --- ## File: _posts/2020-02-21-release-v0-3-13.md --- layout: post title: "Release v0.3.13" date: 2020-02-21 09:00:00 +0000 author: Neil Alexander --- ### Release time! Our last Yggdrasil release, v0.3.12, was merged a couple of months ago at the end of November. For the most part we have seen good stability with the v0.3.12 builds, not to mention good adoption (with the crawler showing over 500 nodes running it). Today we are releasing our next version, v0.3.13. Many of our releases tend not to warrant blog post entries, especially given that the changelog documents the changes. However, there's some fairly big news points associated with this version therefore this post aims to discuss them in a bit more detail. #### TUN adapter changes The first big talking point is that this is the first Yggdrasil release that departs entirely from the Water library and replaces it with the Wireguard TUN library. There are a few reasons why we decided to switch from Water to the Wireguard library, but one of the most prominent is that it gives us better TUN support across all platforms and allows us to finally remove TAP support altogether. At a high-level, TUN interfaces are effectively emulating "Layer 3" interfaces - they deal only in IP packets - whereas TAP interfaces are emulating "Layer 2" full-fat Ethernet interfaces. To run in TAP mode, Yggdrasil not only had to add and remove Ethernet headers for each packet, but it also has to implement an entire NDP implementation and track MAC addresses in order to trick the host operating system into believing that there was a real Ethernet domain on the other end of the adapter. Needless to say, the amount of boilerplate code in order to make TAP mode work correctly was significant and much of that code was very fragile. Although we implemented NDP, we did not ever get around to implementing ARP, which also meant that sending tunnel-routed IPv4 traffic over TAP interfaces invariably did not work either. We have now been able to remove much of this code and simplify the TUN code massively, closing the gaps between some of our supported platforms. There is one platform that is negatively impacted by this change and that's NetBSD. The Wireguard TUN package that we are using currently has **no support for NetBSD**, so we are also removing NetBSD as a supported target until the necessary code appears upstream. To our knowledge, we don't have a base of NetBSD users anyway, but we will aim to re-add this soon. The `IfTAPMode` configuration option has now been removed from Yggdrasil entirely and it will be ignored if specified. **If you are using TAP mode today, then this will affect you**. Please make sure to check your Yggdrasil configuration since this may result in interface naming changes and you may have to update network settings in your host operating system. Initially we added TAP support into Yggdrasil as it was the only way to support Windows, since the OpenVPN driver that we used at the time only supported TAP mode. Thankfully, this is no longer a problem, as the Wireguard project have also released [Wintun](https://wintun.net), which is supported by the Wireguard TUN library. The net result is that we gain TUN support on Windows and the performance is _far_ better than the buggy OpenVPN driver, which is a nice segue into... #### Windows installer and performance We have spent a lot of time trying to improve the installation and setup experience on Windows. This mostly falls into two areas. The first is that using the Wintun driver has _massively_ improved performance, in some cases by hundreds of MB/s, and starting the Yggdrasil process is now much more reliable too - it should no longer be necessary to restart Yggdrasil due to cases of the TAP adapter not being set up or configured correctly. The second is that we now automatically generate Windows `.msi` installers using Appveyor, which means that installing or upgrading Yggdrasil is now simpler than ever. It is no longer necessary to create directories, copy files and register Windows services by hand - a marked improvement! The installer also bundles the Wintun driver and it is installed automatically if required, therefore there is no longer a need to hunt down and install the OpenVPN TAP driver separately. We hope that these changes will help to encourage adoption of Yggdrasil on Windows platforms by significantly reducing the barrier to entry. As in the previous section, Yggdrasil on Windows has gone from supporting TAP mode only to now supporting TUN mode only. **This may mean that you need to review your configuration**. If you no longer need the OpenVPN TAP driver on your system, it is best to entirely uninstall it. It is also important to make sure that the `IfName` configuration option in your `yggdrasil.conf` does not specify the same name as an existing OpenVPN TAP interface or Yggdrasil may fail to start. #### End of the v0.3 release cycle Generally we try, where possible, to avoid make any changes which would damage backward compatibility with previous versions. The last version that had breaking changes was v0.2.1 - over a year and a half ago. However, maintaining backward compatibility so tightly also prevents us from improving the Yggdrasil design in various ways. Therefore, unless any serious bugs or security vulnerabilities appear, it is very likely that this version will be the last in the v0.3 release cycle. Instead, we will start working on the v0.4 release, which is likely to include a number of breaking protocol changes and will be incompatible with v0.3 releases as a result. More information will be announced on the types of changes in v0.4 as they happen - expect to see more blog posts and chatter in the Matrix channel on this subject - but we will aim to give as much notice as possible before releases occur that contain breaking changes. #### Final mentions In addition to the release notes above, I'd like to relay the message that [@mwarning](https://github.com/mwarning) has a proposal open for a Google Summer of Code (GSoC) project under the Freifunk umbrella, comparing a number of mesh routing protocols including Yggdrasil. More information about the proposal is available [here](https://projects.freifunk.net/#/projects?project=freifunk_meshnet_protocol_evaluation&lang=en). If you are interested, please reach out! --- ## File: _posts/2021-06-19-preparing-for-v0-4.md --- layout: post title: "Preparing for Yggdrasil v0.4" date: 2021-06-19 21:00:00 +0000 author: Neil Alexander, Arceliar --- ### Version 0.4 is coming soon In the coming weeks, we will be preparing to release Yggdrasil v0.4. This is a significant change from the v0.3 branch with an all-new protocol implementing an improved routing scheme. This release brings some new and significant benefits: - **Improved mobility performance** — For nodes that move around or change peerings frequently. This was largely impractical with v0.3 as the sessions would have to time out and a new search repeated. - **Spanning tree changes are now less disruptive** — Previously it was common for sessions to fail or for traffic to be dropped if the root or parent coordinates changed. This is no longer the case as tree routing is largely only used for bootstrapping DHT paths and determining source routes. - **Opportunistic source routing** — Session traffic will now use source routing if available, to ensure that the overall connection quality of sessions is preserved. If a source-routed path fails, the traffic will revert to DHT forwarding seamlessly. However, there are also a number of user-impacting changes coming in this release to be aware of, as we have worked to simplify the codebase and reduce complexity. #### Protocol changes Yggdrasil v0.4 contains a number of breaking changes to the protocol. That means that v0.4 nodes **will not** peer with v0.3 nodes. We will be wiping the public peers list around the time of release as a result and asking users to re-submit their information once they have upgraded their public nodes. #### IPv6 address changes In v0.3, IPv6 addresses on the network were generated as a hash of your curve25519 keys (the `EncryptionPublicKey` configuration option). This was made possible due to the iterative search nature of the DHT. In v0.4, the new DHT is based on ed25519 keys instead and therefore we have had to switch to generating IPv6 addresses from the ed25519 keys instead. This is sadly unavoidable. We understand that this is a rather disruptive change, especially for those who operate public services. However, we believe that the added robustness of the new routing scheme and DHT is more than worth the disruption. We will also be clearing the public services list and asking service operators to re-submit their details after upgrading. #### Session firewall deprecated We decided to remove the session firewall from Yggdrasil v0.4. It's no longer straight-forward to implement in the new codebase and we believe that it often lulled users into a false sense of security. While it may have given the impression of being stateful, it was much more rudimentary. For example, if the user allowed only outbound connections, it would still be possible for the remote side to send traffic back to you for the length of the session. It was also possible to extend this window just by sending more session traffic. With the new version, the `SessionFirewall` options are no longer present in the configuration and will not take effect. You should look to use your operating system firewall instead if you need to control traffic coming to your node. If you intend to operate a node solely as an Yggdrasil router and do not need to send/receive Yggdrasil traffic from that node directly, you can also disable the TUN adapter by setting `IfName` to `"none"` in the configuration file. #### Tunnel routing deprecated We also took the decision to remove tunnel routing from v0.4. We know that this has been a somewhat popular feature with some users, but it ultimately was the source of a significant number of bugs within v0.3. It increased the complexity of the TUN module substantially and often also didn't behave in the way that users expected, particularly those who were used to configuring Wireguard already. With the new version, the `TunnelRouting` configuration options are no longer present and will not take effect either. It's still possible to tunnel over Yggdrasil by using a number of other technologies: GRE, IPIP, Wireguard and others, using the Yggdrasil IPs as endpoint addresses for the tunnels. We recommend tunnelling one of these protocols over Yggdrasil instead. #### Release candidates There are [release candidate builds available](https://github.com/yggdrasil-network/yggdrasil-go/releases) if you want to try out v0.4 today. We recommend though that you take a backup of your configuration before upgrading or installing any packages and be aware that you will not be able to peer with or access services from the v0.3 network. At this point the release candidates are using a developmental protocol number. We will bump the protocol version on the final release candidate, but until then, any nodes running v0.4 release candidates should be considered to be experimental only. #### Technical Details ##### Routing The core routing logic has been redesigned and written into a [separate library](https://github.com/Arceliar/ironwood). This began as a toy hard-state reimplementation of Yggdrasil's routing logic to test a new DHT design, but it eventually became a soft-state implementation using generational hard state -- basically, nodes periodically set up a new network and throw away the old one, but everything acts like a hard-state protocol within the life of any one generation of the network. Similar tree and DHT structures were reimplemented in [pinecone](https://github.com/matrix-org/pinecone), so if you [grok](https://en.wikipedia.org/wiki/Grok) the [SNEK](https://matrix.org/blog/2021/05/06/introducing-the-pinecone-overlay-network) then this should seem very familiar. ###### Treespace The spanning tree works largely the same way as before. The only significant differences are with the root selection and updates: the root is the node with the lowest ed25519 public key, rather than the highest sha512sum hash of the public key, and the root updates the timestamp for its spanning tree announcements every 30 _minutes_ (previously 30 seconds) with a timeout after 60 _minutes_ (previously 60 seconds). Parent selection uses whatever non-looping path has advertised the best root & timestamp combination the longest, i.e. the path that sent the update the fastest, unless that path was unstable, in which case any flapping should push the network towards the fastest stable path. As before, each node uses the path from the root to itself as the node's distance label. Given the distance labels of two nodes, the distance between them can easily be calculated (it's the sum of the distance from each of them to their last common ancestor in the tree). This is used to do greedy routing in a metric space, but this is only used to find paths for protocol traffic. User traffic uses one of the following two routing schemes. ###### Keyspace Each node need to be able to contact any other node given only the node's IPv6 address (in the Yggdrasil address range). To do that, we use a distributed hash table (DHT). The new DHT for v0.4 is very different from the old DHT (which was based on Chord). The new DHT takes advantage of the fact that node identifiers are simply ed25519 public keys, and that the root of the tree is the node with the lowest key. Since every node knows a path to the root, and the root is at one of the edges of keyspace, we don't need to wrap keyspace to form a Chord-like ring. So the new DHT is simply a line of nodes, ordered from the lowest key to the highest key, beginning with the root of the tree. Each node is responsible for setting up a path from itself to its predecessor in the line. The predecessor uses that path to route traffic to the node. In addition to this, intermediate nodes store a routing table entry for the path. So if node B sets up a path to node A, which node A uses to forward traffic to B, then every node in the path A->B also has a routing table entry for a path that routes traffic towards B. If a link in the path times out, then the nodes on either end of the broken link send an explicit notification that the path is broken, which is what allows the DHT to quickly detect and react to mobility events. Packets are forwarded towards the key that's highest without being higher than the destination ("The Price Is Right" rules). These routing decisions are made by any node along a path, not only the nodes at the endpoints of a path. So if A is the predecessor of B, then A need not handle traffic to B — traffic which happens to cross any node on the path A->B will flow towards B without reaching A. The root, as well as all peers and all ancestors of peers, act as additional DHT paths that nodes know about "for free" (since they were learned by necessity as part of the spanning tree setup). To discover their keyspace neighbors, nodes with no predecessor (or with a predecessor based on an outdated version of the tree) periodically send a bootstrap packet. The bootstrap packet is routed via the DHT until it hits a dead end — at the node's predecessor. The bootstrap contains the sender's treespace distance label, which the predecessor uses to send a bootstrap acknowledgement message. The acknowledgement includes the predecessors treespace distance label, which the original node uses to set up a path for the DHT. Because the new DHT rules are based around forwarding, rather than lookups, DHT searches (and the crawling operations that come with them) are no longer part of the network. Instead of looking up a path to a node, nodes simply forward traffic towards the destination key via the DHT. While establishing a session, the nodes set up a source route and transparently switch to it in the background. To figure out how many DHT entries are needed in the network, consider the following: 1. Each node sets up at most 1 DHT path to other nodes (its predecessor). 2. Each path has 1 DHT entry in the routing table of each node in the path. 3. The longest possible path between two nodes is one which goes through the root. 4. In a stable network, nodes select a parent which minimizes the latency of the path from the root. 5. If we assume latency is proportional to hop count, then this minimizes the hop count. 6. This means the longest path we expect on the tree is equal to at most the diameter of the network `d`. 7. This means the longest possible path between two nodes via treespace is `2d`. 8. Therefore, in an `n`-node network, there are `O(nd)` DHT entries across all nodes, or an average of `O(d)` entries per node (but with no bounds on how that's distributed across nodes). 9. Internet-like (scale-free) graphs are observed to have a diameter that scales slowly with network size, most likely `d~logn` (or possibly `d~loglogn`). 10. Therefore, we expect `O(nlogn)` total DHT routing table entries in a large internet-like network, or `O(logn)` average state per node (with no bounds on the variance). That works out to the same average state per node as in most popular DHT implementations, so this may scale OK in practice. However, we expect that distribution to be skewed, with a large number of nodes having very few entries, which plausibly could mean that some small fraction of nodes have `O(n)` routing table entries in the worst case. These nodes are the same nodes that would need to carry per-path keep-alive traffic if intermediate nodes did not store routing state, so in reality we're trading one resource for another (possibly higher memory use in exchange for lower bandwidth consumption). ###### Source routing The DHT seems quite reliable in benchmarks (using e.g. [meshnet-lab](https://github.com/mwarning/meshnet-lab)), but it is not efficient: paths through the DHT keyspace typically have higher stretch than paths through treespace. In addition, while coord flapping and node join/leave events cause less disruption for the new DHT, that's not the same as no disruption. To combat this, nodes transparently switch to source routing, and fall back to routing on the DHT only when no source route is known or when a source route reaches a dead end. To be specific, when a node A sends traffic to node B, A adds B to a list of nodes it cares about. If B also cares about A, then when B receives traffic from A, B sends a notification packet back to A (containing B's treespace distance label). If A receives a notification from a node they care about (in this case, B), then A sends a pathfinding packet via the tree. At each hop along the way, nodes along the path add the port number to the previous node to a reverse route at the end of the packet. When B receives the pathfinding packet, they send an acknowledgement back to A, using the reverse route back to A as a source route. The acknowledgement builds up its own reverse route, which represents a path back to B. When A receives the acknowlegement, A stores the reverse route as its source route to B. Subsequent traffic is sent to B via that source route, with infrequent (1/minute) checks for a new source route. The same process occurs in reverse, with A sending a notification to B, when A receives DHT-routed traffic from B. If node A's source routed traffic to B hits a dead end, due to e.g. a link failure in the network, then the source route is stripped from the packet, and the packet is routed the rest of the way over the DHT. When B receives the DHT-routed packet from A, this immediately and automatically causes B to send a new notify (possibly with B's new treespace distance label) back to A, which leads to A discovering a new source route to B. This gives us the best of both worlds. In a stable network, traffic is source routed along the familiar treespace routes from v0.3.X and earlier. If the path between A and B is stable, but the network is not, then the source route continues to work while the tree and DHT try to catch up to changes in network state. If the destination node is mobile, then source routed traffic gets as far as it can before falling back to the DHT, which often puts the packet close to the destination (minimizing the stretch added by the DHT fallback). ##### Encryption The encryption and session logic has seen some minor changes as well. Since node IDs are now based on ed25519 keys, we no longer have permanent curve25519 keys to use for the Diffie–Hellman key exchange. Also, in older versions, we would perform one ephemeral key exchange, and then keep using the same key pair for the life of the session. The new version uses a ratcheting system, where keys are rotated after each round trip (or whenever a sender nonce overflows). This should offer better forward secrecy than the previous code, though it's still subject to change in future versions (if we find something off-the-shelf that we're happier with). #### Conclusion We are looking forward to releasing Yggdrasil v0.4 and are optimistic that the benefits will significantly outweigh any disruption caused at this stage. We've also made a number of other fixes and developed both iOS and Android apps, which we will talk more about soon. We will be continuing to perfect the release candidates and will make announcements both in our >Matrix channel and on the blog around the time of the release. Please stay tuned for updates! As always, please bear in mind that Yggdrasil is not production-grade software and we ask you to continue to [report problems to us on GitHub](https://github.com/yggdrasil-network/yggdrasil-go/issues).