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:
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.
Comments
-
Cool will read about it. In our case the peer ID = public key (secp256k1) and peers implicitly proof ownership by their packets (they are all signed with their private key).
So we already have secure node assignment (a peer cannot pretend to be somebody else, unless he obtains the corresponding private key).
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
We'll definitely need and have some type of challenge (hashcash or captcha) for certain operations to establish trust and incur costs to dishonest/fraudulent/spam peers.
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.
Agree. I plan to make a core package available that can be used by anyone. I will share the initial code in the upcoming days.
-
I'm looking at some implementations of Kademlia.
- Bunch listed here: https://libs.garden/go/search?q=kademlia
- https://github.com/prettymuchbryce/kademlia
- https://github.com/cfromknecht/kademlia
- https://github.com/pdelong/Kademlia (https://medium.com/princeton-systems-course/implementing-kademlia-in-go-65ec9e3c1735)
- http://blog.notdot.net/2009/11/Implementing-a-DHT-in-Go-part-1and http://blog.notdot.net/2009/11/Implementing-a-DHT-in-Go-part-2
- https://github.com/libp2p/go-libp2p-kad-dht
- https://github.com/mh-cbon/dht
- https://github.com/nictuku/dht
I'm going to evaluate those and more later.
-
Currently working on forking https://github.com/prettymuchbryce/kademlia. Trying to get the DHT code into a sub-package so that it can be improved (replaced) separately.
-
Here are links of how over-invested IPFS does the routing:
Howdy, Stranger!