S/Kademlia Considerations (security enhancements to vanilla Kademlia)

As we design this network I believe it is important to secure the routing protocol (Kademlia) to prevent against some common threats. Fortunately methods for defending against bad actors deploying Sybil, Eclipse, and churn attacks are commonplace in many modern kademlia P2P systems, which use a set of extensions to kademlia loosely called S/Kademlia:

https://www.researchgate.net/publication/4319659_SKademlia_A_practicable_approach_towards_secure_key-based_routing

In particular, I think it would be important to keep the following things in mind from the start

(1) Generating a large number of valid clients IDs should be difficult

(2) Verification of routing information should be done where possible

For (1) this is solved in the paper's article 4.1 "Secure nodeid assignment", I propose using the dynamic version of the "crypto puzzle signature" solution, as using the static method greatly limits our keyspace and introduces complexity into the crypto system that we shouldn't need to worry about now.

TL;DR we select an integer X which we transmit in addition to the client ID (public key). X is chosen such that HASH(X ⊕ Client ID) has a certain number of leading zeros (this is a parameter known to the whole network). On receipt, verify that this condition holds, and if it does not then simply do not forward the request.

For (2) we can look to section 4.4 "Lookup over disjoint paths". This approach will also greatly reduce latency, as we can run these lookups in parallel:

Instead of querying α many nodes and merging the responses as in vanilla Kademlia (hence introducing more latency for each increase of α because we must wait on responses), select k many nodes which are closest to the destination node and query them in parallel, only using any given node once to ensure the lookup path will be disjoint. Disjointedness is important and allows us to "validate" the received responses reliably well, as we have not queried any single malicious node more than once.

I'd be interested in developing a relatively "standalone" library we could use in PeerNet. It should expose a simple API to PeerNet's core components and should make using the DHT simple / straightforward for developers. It should also be highly parallelizable so that the client can continue with other network tasks while the lookup is running. Of course, the development of this library will be dictated ultimately by functionality we seek in PeerNet, so it will not be entirely "standalone" of course 🙂

I will play around with this in my free moments in the coming days.