3. Virtual Snake

The virtual snake provides the name-independent identifier routing which efficiently provides robust routing for overlay traffic. It works by effectively arranging all of the nodes on the network into a line, ordered by their public keys, and building paths between keyspace neighbours.

Ascending and descending paths

Each node in the topology has a reference to an ascending and a descending path. The ascending path is the path on the network that leads to the closest public key to our own in the ascending direction (the next highest key), and the descending path is the path on the network that leads to the next closest public key to our own in the descending direction (the next lowest key).

There are only two exceptions to this rule: the node with the highest key on the network will have only a descending path (as there is no higher key to build an ascending path to) and the node with the lowest key on the network will have only an ascending path (as there is no lower key to build a descending path).

For the ascending and descending paths, a node should store the following information:

1. The Path public key and Path ID, as exchanged during bootstrap/path setup;
2. The Origin public key, noting which node initiated the path creation;
3. The Source port, where the Bootstrap ACK message arrived from (for descending path entries);
4. The Destination port, where the Path Setup message was forwarded to next (for ascending path entries);
5. The Last seen time, noting when the entry was populated;
6. The Root public key and Root sequence that the path was set up with.

Bootstrapping

Bootstrapping is the process of joining the snake topology. Bootstrapping takes place in three steps:

1. The bootstrapping node sends a bootstrap message into the network, with their own public key as the “target” key, which will be routed to the nearest keyspace neighbour;
2. The nearest keyspace neighbour will respond to the bootstrap message by sending back a Bootstrap ACK;
3. The bootstrapping node will respond to the Bootstrap ACK by sending a Path Setup message to the nearest keyspace neighbour.

Nodes bootstrap when they do not have an ascending path — that is, they do not know who the next highest public key belongs to. The descending path is populated passively by another node bootstrapping and building a path to that node.

The bootstrap message contains the following fields:

Source coordinates
Path public key	Path ID
Root public key	Root sequence
Source signature

The combination of the Path public key and the Path ID uniquely identify a path. While the Path public key is predetermined by the public key of the bootstrapping node, the Path ID must be generated randomly by the bootstrapping node and should not be reused.

The Source signature is an ed25519 signature covering both the Path public key and Path ID by concatenating them together and signing the result. This enables the remote side to verify that the bootstrap was genuinely initiated by the sending node and has not been forged.

Bootstraps will travel through the network, forwarded using SNEK routing with bootstrap rules, towards the target key, until they arrive at the node that is closest to the target key. The forwarding logic specifically will not deliver bootstrap messages to the actual target key, so the bootstrap message will eventually arrive at a “dead end” at the next closest key.

Handling bootstrap messages

Once the bootstrap message arrives at a dead end, the node will respond using tree routing back to the node with a Bootstrap ACK message.

Before doing anything, the node must ensure that the signature in the Source signature field is valid by checking against the Destination public key. If the signature is invalid, the bootstrap message should be silently dropped and not processed any further.

Additionally, the node should ensure that the Root public key and Root sequence of the bootstrap message match those of the most recent root announcement from our chosen parent, if any, or the node’s own public key and sequence number if the node is currently acting as a root node. If this is not true, the bootstrap message should be silently dropped and not processed any further.

A Bootstrap ACK message contains the following fields:

Destination coordinates	Source coordinates
Destination public key	Source public key
Path ID
Root public key	Root sequence
Source signature	Destination signature

The responding node should:

1. Copy the bootstrap Source coordinates into the Destination coordinates field;
2. Copy the bootstrap Path public key into the Destination public key field;
3. Copy the bootstrap Path ID into the Path ID field;
4. Copy the bootstrap Source signature into the Source signature field;
5. Populate the node’s own current coordinates into the Source coordinates field;
6. Populate the node’s own public key into the Source public key field;
7. Copy their own parent’s last root announcement Root public key and Root sequence fields into the corresponding fields;
8. Add the Destination signature, as below.

The Destination signature is a signature that covers the Source signature, Path public key and Path ID fields by concatenating all three values together and then signing the result. It enables any node on the network to verify that the acknowledging node accepted a specific bootstrap for a specific path.

Note that the Source signature is copied and preserved from the original packet without modification. This is so that the bootstrap ACK contains signatures from both ends of the bootstrap.

Handling bootstrap ACK messages

Upon receipt of a Bootstrap ACK packet, the bootstrapping node now is considered to have “found” a potential ascending node candidate.

The Bootstrap ACK packet will contain two signatures: the Source signature and the Destination signature. Both of these signatures should be verified to ensure authenticity. The Source signature must be verified using the node’s own public key and the Destination signature must be verified using the Source public key. If either signature is invalid, the packet should be dropped and not processed any further.

If the signature is valid, the following checks should be made to see if it is suitable:

1. Drop the update and do not process further if any of the following are true:
   1. If the Source public key is the same as the node’s own public key, implying that the node somehow received a Bootstrap ACK from itself;
   2. If the Root public key does not match that of our chosen parent’s last announcement;
   3. If the Root sequence does not match that of our chosen parent’s last announcement;
2. If the node already has an ascending entry, and it has not expired:
   1. If the Source public key is the same as the existing ascending entry’s public key, and the Path ID is different to the existing ascending entry’s path ID, accept the update;
   2. If the ordering Node public key ＜ Source public key ＜ Ascending origin public key is true, that is that the public key that the Bootstrap ACK came from is closer to us in keyspace than our previous ascending node, accept the update;
3. If the node does not have an ascending entry, or the node has an expired ascending entry:
   1. If the Source public key is greater than the node’s own public key, accept the update.

If the update has not been accepted, it should be dropped. There is no new path to tear down and it is not necessary to respond to the bootstrapping node.

If the update has been accepted, a Path Setup message is constructed. A Path Setup message contains the following fields:

Destination public key	Destination coordinates
Source public key
Path ID
Root public key	Root sequence
Source signature	Destination signature

The responding node should:

1. Copy the bootstrap ACK Source public key into the Destination public key field;
2. Copy the bootstrap ACK Source coordinates into the Destination coordinates field;
3. Populate the node’s own public key into the Source public key field;
4. Copy the bootstrap ACK’s Path ID into the Path ID field;
5. Copy their own parent’s last root announcement Root public key and Root sequence fields into the corresponding fields;
6. Copy the bootstrap ACK’s Source signature into the Source signature field;
7. Copy the bootstrap ACK’s Destination signature into the Destination signature field.

Path setup messages are routed using tree routing — that is, the Destination coordinates are the prominent field when making routing decisions. The Destination public key field is used to confirm that the setup has reached its intended destination.

Each path setup message will contain both a Source signature and a Destination signature. The Source signature must be verified using the Source public key and the Destination signature must be verified using the Destination public key. If either of the signatures is invalid, the setup message should be dropped and a teardown must be sent back for the new path to the port that the setup message was received on.

The node should attempt to look up the next hop for the message and then attempt to forward the Path Setup onto the first hop. If this fails, either because there is no suitable next-hop identified or because the packet was not successfully deliverable to the first hop, the setup message should be dropped and a teardown must be sent back for the new path to the port that the setup message was received on.

The path is only useful if we can assert that it arrived at the intended destination and was set up correctly at all intermediate nodes without being torn down at any point. Since no routing information has been installed yet, there is nothing to tear down, so dropping is sufficient to abort the path setup altogether.

If the Path Setup was successfully forwarded, the node’s ascending reference should be populated to point to the node from which the Bootstrap ACK arrived from:

1. Copy the bootstrap ACK Destination public key into the Path public key field;
2. Copy the bootstrap ACK Path ID into the Path ID field;
3. Copy the bootstrap ACK Source public key into the Origin public key field;
4. Copy the bootstrap ACK Root public key and Root sequence into the appropriate fields;
5. Populate the Last seen time with the current time;
6. Populate the Source port with a reference to the port that the bootstrap ACK was received from;
7. Populate the Destination port with a reference to the chosen next-hop port, from above.

Finally, the node must then iterate through the routing table and search for all entries where the Source port refers to nowhere/the local node, and the Path public key does not match the bootstrap ACK Source public key, sending teardowns for each of these paths and removing them from the routing table. This ensures that any stale paths from other nodes are torn down, but it will not remove paths from the newly bootstrapping node until it has received the Path Setup and torn down the path itself, avoiding a race condition. Teardowns are described in a later section.

Handling path setup messages

Path Setup messages are responsible for populating the routing table, in addition to updating the reference to the descending node when the message reaches its final destination. They are different to Bootstrap and Bootstrap ACK messages in that they must be processed by all intermediate nodes on the path before being forwarded.

Importantly, if a node decides that it wants to reject a setup message for any reason, it must send a teardown for the new path to ensure that it is cleaned up, as it will have possibly been installed into the routing table of other nodes on the path. This includes if the setup message cannot be forwarded to its destination due to reaching a dead end.

If the setup message has reached its intended destination, that is that the Destination public key matches the node’s public key, then the responding node should decide whether or not to update their descending reference to the new path.

If an entry in the routing table already exists with the Destination public key and the Path ID, the routing entry is a duplicate:

1. The new path must be torn down;
2. The old path must be torn down;
3. The update must be rejected and not processed any further.

Arrived at intended destination

If the Destination public key is equal to the node’s public key, the update is considered to have arrived at its intended destination, therefore the following checks should be performed as to whether or not to update the descending node reference:

1. Drop the update and do not process further if any of the following are true:
   1. If the Root public key does not match that of our chosen parent’s last announcement;
   2. If the Root sequence does not match that of our chosen parent’s last announcement;
   3. The Source public key is not less than the node’s own public key;
2. If the node already has a descending entry, and it has not expired:
   1. If the Source public key is the same as the existing descending entry’s public key, and the Path ID is different to the existing descending entry’s Path ID, accept the update;
   2. If the ordering Descending public key ＜ Source public key ＜ Node public key is true, that is that the public key that the setup came from is closer to us in keyspace than our previous descending node, accept the update;
3. If the node does not have a descending entry, or the node has an expired descending entry:
   1. If the Source public key is less than the node’s own public key, accept the update.

If the update has not been accepted, a teardown of the new path must be sent back via the receiving port and the update should be dropped.

If the update has been accepted, the node’s descending reference should be populated to point to the node from which the Setup message arrived from:

1. Copy the setup Source public key into both the Path public key and Origin public key fields;
2. Copy the setup Path ID into the Path ID field;
3. Copy the setup Root public key and Root sequence into the appropriate fields;
4. Populate the Last seen time with the current time;
5. Populate the Source port with a reference to the port that the setup message was received from;
6. Leave the Destination port empty, as there should be no next-hop once the setup message has been processed at its intended destination.

Then proceed into the next section to install the route into the routing table.

Install route into routing table

Regardless of whether the setup message is considered to have arrived at its intended destination (the node’s public key matches the Destination public key) or not, a setup message should result in the route being installed into the routing table of each node handling the message.

In the event that the setup message is due to be forwarded (i.e. the setup message has not yet reached its intended destination), installing the routing table entry should be done after the message has been forwarded.

By doing this, all transitive nodes on a given setup path will contain routing information for the newly built path. There is one of three possible outcomes:

1. The intended destination for the setup message will accept the route, therefore the route will remain up;
2. The intended destination will reject the route, sending back a teardown along the path, causing the routing table entry to be deleted;
3. The setup message will never arrive at the intended destination, instead hitting a dead end, with the node at the dead end sending back a teardown along the path, causing the routing table entry to be deleted.

To install the route into the routing table, the node should create a new entry and:

1. Copy the setup Source public key into both the Path public key and Origin public key fields;
2. Copy the setup Path ID into the Path ID field;
3. Copy the setup Root public key and Root sequence into the appropriate fields;
4. Populate the Last seen time with the current time;
5. Populate the Source port with a reference to the port that the setup message was received from;
6. Populate the Destination port with a reference to the chosen next-hop port, unless the setup message has reached its intended destination, in which case this field should remain empty.

Path teardown

A teardown is a special type of protocol message that signals to a node that a path is no longer valid and should be removed. A teardown message contains the following fields:

Path public key

Path ID

If the teardown message arrived from any port that was not the Source port or the Destination port, the teardown must be dropped and ignored. A valid teardown will only ever arrive from the same ports as the original path was built on.

Upon receipt of a path teardown message that matches a routing table entry and arrives from either the Source port or the Destination port, the node should clear any routing table, ascending or descending path entries that match the Path public key and Path ID.

Once the teardown has been actioned, it must be forwarded based on the following rules:

1. If the teardown arrived via the Source port, and the Destination port is not empty, forward it to the Destination port;
2. If the teardown arrived via the Destination port, and the Source port is not empty, forward it to the Source port.

A teardown that originates locally must be forwarded to all related ports — that is, if both the Destination port and Source port are known, a teardown must be sent to each port.

If a received teardown message does not match any routing table entries and/or the ascending or descending entry, the teardown should be ignored and dropped, and must not be forwarded.

In the case that the teardown message results in the ascending path being torn down, the node should then re-bootstrap by sending a new bootstrap message into the network.

Next-hop calculation

When using SNEK routing to route towards a certain public key, a number of rules apply in order to calculate the next-hop.

These rules slightly differ based on whether the frame is considered to be a “bootstrap” message. Only “Bootstrap” frames follow the bootstrap rules (but not “Bootstrap ACK”, “Path setup” etc frames, which are routed using tree routing instead).

1. Start with a best key set to the node’s public key, and a best candidate set to the node’s own router port;
2. If the Destination public key is equal to the node’s own public key and the frame is not a bootstrap message, handle the packet locally without forwarding;
3. If the node has a chosen parent (i.e. is not a root node) and an announcement has been received from that parent:
   1. If the frame is a bootstrap message and the best key still equals the node’s public key, which should always be the case to begin with, ensure that a worst-case route up to the root is chosen:
      • Set the best key to the chosen parent’s root public key;
      • Set the best candidate to the port through which the parent is reachable;
   2. If the ordering Best key ＜ Destination public key ＜ Root public key is true, implying that the target is higher in keyspace than our own key, ensure that a worst-case route up to the root is chosen:
      • Set the best key to the chosen parent’s root public key;
      • Set the best candidate to the port through which the parent is reachable;
   3. For each of the node’s ancestors — that is, public keys that appear in the Signatures section of the last received root update from the chosen parent:
      1. If the frame is not a bootstrap message, the candidate ancestor key equals the Destination public key and the best key does not equal the Destination public key, meaning that we know that the target is one of our ancestors:
         • Set the best key to the ancestor key;
         • Set the best candidate to the port through which the parent is reachable;
      2. If the ordering Destination public key ＜ Ancestor key ＜ Best key is true, meaning that we believe one of our ancestors takes us closer to the target:
         • Set the best key to the ancestor key;
         • Set the best candidate to the port through which the parent is reachable;
4. For each of the node’s directly connected peers (first loop):
   1. For each of the connected peer’s ancestors — that is, public keys that appear in the Signatures section of the last received root update from this peer:
      1. If the frame is not a bootstrap message, the candidate peer ancestor key equals the Destination public key and the best key does not equal the Destination public key, meaning that we believe that the target is one of our direct peer’s ancestors:
         • Set the best key to the ancestor key;
         • Set the best candidate to the port through which the peer is reachable;
5. For each of the node’s directly connected peers (second loop):
   1. If the best key equals the connected peer’s public key, i.e. we have previously found the peer’s key as an ancestor of another node but not using the most direct port, we can now refine the path to use the direct connection to that peer instead:
      • Set the best key to the peer’s public key;
      • Set the best candidate to the port through which the peer is reachable;
6. For each of our routing table entries, to look for any transitive paths that may take the packet closer to the target than any of our direct peering knowledge has provided us:
   1. Skip the routing table entry if either of the following conditions are true:
      • The routing table entry has expired;
      • The Source port of the routing table entry refers to the local router;
   2. If the frame is not a bootstrap message, the Path public key is equal to the Destination public key and the best key is not equal to the Destination public key:
      • Set the best key to the Path public key;
      • Set the best candidate to the Source port from the entry;
   3. If the ordering Destination public key ＜ Path public key ＜ Best key is true:
      • Set the best key to the Path public key;
      • Set the best candidate to the Source port from the entry.

If none of the above conditions have matched for the given Destination public key, then it is expected that the best candidate will still refer to the local router port, in which case the node is expected to handle the traffic as if it was destined for the local node.

Routine maintenance

At a specified interval, typically every 1 second, the node should run the following checks:

1. If the descending node entry has expired, that is, the time since the Last seen entry has passed 1 hour, tear down the path;
2. If the ascending node entry has expired, that is, the time since the Last seen entry has passed 1 hour, tear down the path;
3. If the ascending node entry is empty, either before or after step 2, send a bootstrap message into the network.