Decentralised NAT Signalling

[tegefaulkes]

Requirements of this design

1. Maintaining active connections between nodes to form a 'strongly connected' network.
2. Decentralised connection forming and NAT punching.
3. Decentralised message relaying.
4. Possibly caching known connection chains to speed up connection forming.

Additional context

• Testnet Deployment #326 (comment)
• Testnet Deployment #326 (comment)
• Testnet Deployment #326 (comment)
• Testnet Deployment #326 (comment)

Specification

We need to be able to hole punch a connection to the target node in a decentralised way. This can happen in stages.

1. Holding connections to form a strongly connected graph.
2. Discovery of a connected path.
3. Forming a direct connection using a connected path.

Holding connections

To ensure that a connection path is available we need to have an environment where a chain of connections to the target is likely to exist. To do this each node needs to hold active connections to other nodes. the distribution of these connections needs to ensure that the overall network is strongly connected. Bonus points for minimising the number of hops.

Using the kademlia structure we can maintain active connections to the N closest nodes. but we can also hold connections between other nodes across the network. The closest nodes should maintain strong connections locally in the network while the extra connections will form shortcuts between parts of the network that are not closely related. Note I mean close the kademlia sense of closeness.

Discovery

The discovery process is very similar to the Kademlia FIND_NODE process. the difference here is that we only search over the active connections Proxy connections. Using this process we should be able to find a chain of connections that reaches our target Node.

Generally the idea is that we are walking the graph of active connections to find a chain of connections that leads to our target. Naively this would be a pretty expensive and exhaustive search but utilising the Kademlia structure we can ensure that we only walk closer to our target at each step of the search.

Forming direct connections

Given a chain of connections A>B>C>D we should be able to form a direct connection of A>B. We can form incrementally closer connections by using each step of the chain as a signaller to punch a connection to the next part of the chain. I will refer to this increasingly closer connection as a Feeler.

With the Chain A>B>C>D we can start by requesting B to signal a hole punch between A and C. If the hole-punch is successful then we now have a connection chain of A>C>D. We can then repeat the step use C as the new signaller to form a connection between A and D thus completing the desired direct connection.

    
 ┌─┐     ┌─┐     ┌─┐     ┌─┐    This is the existing connection chain.
 │A├─────►B├─────►C├─────►D│    We start out by asking Node B to signal
 └─┘     └─┘     └─┘     └─┘    hole punching to node C thus creating a
                                connection between A and C.


 ┌─┐     ┌─┐     ┌─┐     ┌─┐
 │A├─────►B├─────►C├─────►D│    With an active connection to C we can use
 └┬┘     └─┘     └▲┘     └─┘    C to act as a signaller to form a connection
  │    Feeler     │             A and D.
  └───────────────┘

 ┌─┐     ┌─┐     ┌─┐     ┌─┐    We now have a direct connection through
 │A├─────►B├─────►C├─────►D│    the NAT between A and D.
 └┬┘     └─┘     └─┘     └▲┘
  │         Feeler        │
  └───────────────────────┘

At each step the 'signalling' node is directly connected to both nodes and thus is aware of the 'NAT-ified' ports and addresses. It can easily coordinate a hole-punch between the two nodes. So long as we can find a connection chain we can form a connection between two nodes through NATs without a centralised signaller.

If we fail to form a more direct connection then an alternative chain will need to be found. Given a graph that is sufficiently connected then there should be multiple routes to the target. If for some reason a direct connection can't be formed but the target node is holding a connection. This process should ideally connect us with a node that IS holding an active connection to the target node and can act as a relay for said node. It's possible that not all nodes will like to act as a data relay so we may need a way to negotiate with the target node to connect to a relay node that will relay data.

Full process

We can combine the discovery and connection forming to create increasing closer connections to our target. the process will look something like this.

1. get list of active connections sorted by distance to target.
2. Pick N out of that list in order of closeness to target.
3. form a direct connection with the newly found nodes using the previous connections as a signaller.
4. repeat from step 1.

Eventually this should form a direct connection to our target. We at any point in time concurrently have alpha Feelers walking closer to the target during this process.

If we had existing discovery knowledge about the network such as know connection chains that lead to the target then that can be used to greatly speed up the process. if we had knowledge of an existing connection chain that leads to the target then we could just do the connection forming process without doing any discovery. Likewise if we had a partial chain that we know leads closer to our target then we can use that as a starting point and reduce how much we need to search.

Additional Resources

• https://github.com/dusk-network/kadcast
• https://medium.com/@minikiraniamayadharmasiri/micromouse-from-scratch-algorithm-maze-traversal-shortest-path-floodfill-741242e8510
• https://pdos.csail.mit.edu/~petar/papers/maymounkov-kademlia-lncs.pdf
• https://stackoverflow.com/questions/25751928/kademlia-xor-metric-properties-purposes
• https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search - THIS ALGO might be what we are looking for
• https://en.wikipedia.org/wiki/A*_search_algorithm - relevant?
• https://kelseyc18.github.io/kademlia_vis/basics/1/

Sub-Issues & Sub-PRs created

1. Decentralized Signalling #618
2. MDNS integration and NodeGraph structure expansion #537

[tegefaulkes]

There are a few things that come to mind need to be addressed for this.

1. Separate hold punching out of NodeConnection/Manager and just have the Proxy handle it.
2. Proxy needs to maintain a minimum of active connections as a super set of the NodeConnections to maintain network connectivity.
3. Out Kademlia implementation needs to be modified slightly to support discovery over active connections.
4. Implement connection forming across a chain. What do we call this? 'Chain collapsing'? 'Chain reducing'?

[tegefaulkes]

This will need a bit of discussion to refine the idea some more but I think we have a good basis here. For a start I think some refactoring work needs to be done for hole-punching and related messaging.

[CMCDragonkai]

A diagram here would help understand what the problem is.

Compare:

1. Using gossip/kademlia-driven casting to flood the network with the relay message.
2. Using 1-hop point to point hole punching, and thus combining the "resolving query" with the "relay query".

[CMCDragonkai]

Also the difference between closest node connections vs closest node entries in NodeGraph and the difference between NodeConnection and Proxy ConnectionForward.

[tegefaulkes]

To maintain the network connectivity we need to maintain a bunch of open connections for each node. It raises some questions.

1. How many concurrent connections can we have before we're using too many resources?
2. How many connections does each node need to maintain strong connectivity of the network? is there a point where the network 'percolates'?
3. If an existing connection is required to start the hole-punch process then is there any value in storing information in the node Graph for nodes we're not currently connected to?
4. If only existing connections are useful is there any point in having the NodeGraph be persistent in the DB?

The main one is there any point in distinguishing entries in the node Graph are active connections or not? what can we do with the host/port information without having an active connection to it? If there is no use for this information if we're not connected to the node then shouldn't we only store information about nodes we're actively connected to?

[tegefaulkes]

The other approach we considered was to use a kademlia to gossip/broadcast a hole-punch relay message to the target we are trying to connect to. if we picked N nodes out of the nodes we were connected to that are the closest to the target node and we asked them to relay a hole-punch message. If each node receiving this message relayed it to the n of it's connected nodes that were closest to the target node. Then we would eventually get the message to the target node.

This message has some disavantages.

1. no control over when the message reaches the target node thus we can't coordinate timing on the hole punching very well.
2. This method has a multiplying affect on the message creating more messages at each stage with each message pointing towards the target. Possibly DDOSing the target.
3. we would still need some way to get the proper port information that we need to punch through the NAT.

[tegefaulkes]

It may not be useful to store the addrees:port information of NodeIds that are not currently connected in the NodeGraph. But what would be extremely useful is storing the previously seen connection chains. If during the discovery process we can obtain information about previously seen connection chains to our target then we can greatly speed up the process.

Keeping the previously seen address:port can also be useful if the target node can be connected to directly. either in the cases;

1. target has a public facing IP address.
2. target's ports were manually forwarded.
3. target automatically negotiated port forwarding using either, PCP, NAT-PMP, UPnP-IGD or others?

[tegefaulkes]

There is a node library for negotiating port mappings with the NAT. This will be very useful for avoiding hole punching in the first place as well as reducing the amount of keep alive packets we may have to send.

https://github.com/freedomjs/freedom-port-control

[CMCDragonkai]

Persistent connections that are needed to maintain "NAT reachability" will need to be maintained at the NCM level, not at the proxy connections. Because once we have composed a proxy connection, when we terminate the GRPC client, we cannot be sure that GRPC server will handle this correctly without also receiving a TCP FIN packet. At the same time, this avoids adding additional complexity to the connection management at the proxy connection level.

Note that "NAT reachability" is the ability for a node to be reachable behind a NAT even while idle.