Things Not Implemented

There are a few items from the specification not implemented here.

UDP dropouts

From the spec:

“A related problem is that because Kademlia uses UDP, valid contacts will sometimes fail to respond when network packets are dropped. Because packet loss often indicates network congestion, Kademlia locks unresponsive contacts and avoids sending them any further RPCs for an exponentially increasing backoff interval. Because at most stages Kademlia’s lookup only needs to hear from one of k nodes, the system typically does not retransmit dropped RPCs to the same node.

When a contact fails to respond to 5 RPCs in a row, it is considered stale. If a fe-bucket is not full or its replacement cache is empty, Kademlia merely flags stale contacts rather than remove them. This ensures, among other things, that if a node’s own network connection goes down temporarily, the node won’t completely void all of its k-buckets.”

This is true not just for UDP packets but any connection—it may go down for a while. This algorithm is somewhat entangled with delayed eviction. In delayed eviction, the spec state “any unresponsive ones can be evicted.” It is the spec’s description of UDP dropouts that actually defines what “unresponsive” actually means.

Accelerated lookups

Again, from the spec:

“When a contact fails to respond to 5 RPCs in a row, it is considered stale. If a fe-bucket is not full or its replacement cache is empty, Kademlia merely flags stale contacts rather than remove them. This ensures, among other things, that if a node’s own network connection goes down temporarily, the node won’t completely void all of its k-buckets.

Another optimization in the implementation is to achieve fewer hops per lookup by increasing the routing table size. Conceptually, this is done by considering IDs b bits at a time instead of just one bit at a time. As previously described, the expected number of hops per lookup is log2n. By increasing the routing table’s size to an expected 2^b log₂^b n k-buckets, we can reduce the number of expected hops to log₂^b n.”

In this implementation we have bucket ranges rather than a bucket per prefix bits in the key space; therefore, the accelerated lookup optimization is irrelevant, because the bucket ranges typically span many prefix bits.

Sybil attacks

Peer-to-peer networks are vulnerable to Sybil attacks:

“In a Sybil attack, the attacker subverts the reputation system of a peer-to-peer network by creating a large number of pseudonymous identities, using them to gain a disproportionately large influence. A reputation system’s vulnerability to a Sybil attack depends on how cheaply identities can be generated, the degree to which the reputation system accepts inputs from entities that do not have a chain of trust linking them to a trusted entity, and whether the reputation system treats all entities identically.”[18]

In the current implementation, if the peer network is already well populated (most k-buckets are full) a Sybil attack would not replace “good,” known peers—the attack would simply place the attempt into the DHT’s pending contact buffer. In a mostly unpopulated network (most k-buckets have room for more peers), the subsequent failure to get a response from a peer would result in its eventual eviction. The piggyback ping approach is also a means for the recipient of the RPC call to verify the sender.