Kademlia Distributed Hash Table

Kademlia is a distributed hash table and routing system: given a fixed-length key, a node finds the small set of peers whose identifiers are closest to it without any central directory. BitTorrent, IPFS-derived systems, and Ethereum's discovery v4 use Kademlia or a Kademlia-like design for discovery; it is not the blockchain consensus protocol.

XOR is the organizing metric #

Node IDs and keys are $b$-bit strings. Distance is

$$d(x,y)=x\oplus y$$

interpreted as an integer. Small distance means a long shared binary prefix. XOR is symmetric, $d(x,y)=d(y,x)$, and for any $x$ and distance value there is exactly one $y$ at that distance. Those properties make request and response routes learn useful contacts in both directions.

Each node keeps k-buckets for exponentially increasing distance ranges: peers one bit away, two bits away, and so on. A bucket holds up to $k$ contacts, ordered least-recently seen first. The table therefore keeps fine detail near the local ID and progressively coarser coverage farther away.

Iterative lookup #

A node begins with the closest contacts it knows and queries up to $\alpha$ of them in parallel. Replies return contacts closer to the target. The search repeats until no newly discovered contact is closer or the closest $k$ have all been queried.

flowchart TB
  A["start with local routing table"] --> B["query α closest unqueried peers<br/>with FIND_NODE(target)"]
  B --> D["merge returned contacts"]
  D --> E{"closer peer found?"}
  E -- yes --> B
  E -- no --> F["closest k peers reached"]

Every useful response also refreshes routing knowledge. Because each hop normally gains at least one matching prefix bit, expected routing takes $O(\log n)$ hops.

Why old contacts are retained #

When a full bucket sees a new contact, the original design pings the least-recently seen incumbent and evicts it only if unresponsive. Long-lived peers have already demonstrated stability, so this policy resists routing-table churn and prevents a burst of newcomers from displacing an entire working neighborhood.

Keys are replicated at the $k$ closest live nodes and republished. This gives availability under churn, not consensus: simultaneous writers need an application-specific conflict rule.

Security boundary #

Plain Kademlia assumes node IDs are not cheaply attacker-chosen. On an open network, an adversary can manufacture identities near a target (Sybil attack) and eclipse a victim's routing view. Defenses bind identity to a public key, constrain ID derivation, diversify buckets by network location, rate-limit admission, and use trusted bootstrapping—but none is supplied by XOR geometry itself.