Read

DHT / Kademlia Lookup

Trackers are a single point of failure and coordination for a torrent's swarm. The Distributed Hash Table (DHT, specified for BitTorrent in BEP 5) lets peers find each other without a tracker at all, using the Kademlia algorithm. This lesson implements the mathematical core of Kademlia: XOR distance, routing buckets, and closest-node lookup.

Node IDs and XOR distance

Every node (and every torrent's infohash) lives in the same 160-bit address space — the same size as a SHA-1 hash, which is exactly what BitTorrent already uses for infohashes and piece hashes. Kademlia's key trick is defining "distance" between two ids not with subtraction but with bitwise XOR, interpreted as a number:

distance(a, b) = a XOR b

XOR distance has properties a metric needs: distance(a, a) = 0, it's symmetric (distance(a,b) = distance(b,a)), and it satisfies the triangle inequality. It's also cheap to compute and — critically for the algorithm's structure — unidirectional: for any node a and any target distance d, there is exactly one node at that distance from a (a XOR d). That uniqueness is what makes Kademlia's routing table converge predictably.

In this exercise, ids are given as 40-character hex strings (160 bits). Computing XOR distance is just: parse both as big integers, XOR them, and format back to a zero-padded 40-char hex string.

Buckets: organizing what you know by distance

A real Kademlia node can't remember every other node in the network — it keeps a routing table of up to 160 "k-buckets," one per possible number of shared leading bits with its own id. Bucket i holds nodes whose id shares exactly i leading bits with yours (equivalently, whose XOR distance to you has its highest set bit at position 159 - i). A node identical to yours would be bucket 160 (unreachable in practice, but well-defined).

The reason for bucketing by prefix length rather than storing a flat list: nodes "close" to you (many shared prefix bits) are rare and valuable to track precisely, while nodes "far" from you (few shared bits) are numerous — you only need a representative sample of them, since any of them is roughly equally far. This gives Kademlia its O(log N) lookup routing performance without every node needing global knowledge.

Closest-node lookup

Finding the peers closest to a target id (e.g., a torrent's infohash, to discover who's likely storing/announcing for it) is just: compute every known node's XOR distance to the target, sort ascending, and take the smallest k.

In a real DHT this lookup is iterative and recursive across the network — you ask your closest-known nodes for their closest-known nodes to the target, repeating until nobody returns anyone closer — but the local, in-memory version you're building here is the primitive that recursive search is built on. Understanding "given a target and a set of nodes, who's closest" is the foundation everything else in Kademlia stacks on top of.

Edge cases

• Distance from a node to itself is all zero bits — shared_prefix_bits returns 160 in that case, a sentinel meaning "identical."
• Ties in distance during closest-node lookup should be broken deterministically (e.g., by node id) so results are reproducible.
• Requesting more closest nodes than you actually know about should just return everything you have, not error.