Skip to content
Here Be Dragons

Kademlia DHT

Kademlia is a distributed hash table (DHT) protocol that lets thousands of nodes collectively store and retrieve key-value pairs with no central coordinator. You give any node a key; it routes the request hop by hop across the network until it lands at the small cluster of nodes closest to that key, measured by XOR distance.

Published by Maymounkov and Mazieres in 2002, Kademlia became the backbone of BitTorrent’s mainline DHT (the global tracker-free peer discovery system), IPFS content routing, and Ethereum’s devp2p peer discovery. At its peak, BitTorrent’s mainline DHT had over 20 million active nodes.

The XOR metric

Every node and every key is a random 160-bit integer. Distance between any two IDs is their bitwise XOR:

distance(A, B) = A XOR B

XOR distance has useful properties that Euclidean distance lacks:

  1. Symmetric: d(A,B) = d(B,A), because XOR is commutative
  2. Triangle inequality: d(A,C) <= d(A,B) + d(B,C), so routing converges
  3. Closest-on-path: on any route from A to B, each hop gets closer to B in the XOR metric

The most important consequence: in a 160-bit ID space, there is exactly one node closest to any key. “Closest” has a concrete meaning that all nodes agree on, without any coordination.

IDs (8-bit example):
  Node A: 0b01000010  (66)
  Node B: 0b01000111  (71)
  Key K:  0b01000011  (67)


  d(A, K) = 66 XOR 67 = 0b00000001 = 1
  d(B, K) = 71 XOR 67 = 0b00000100 = 4


  Node A is closer to K than Node B is.

K-buckets

Each node maintains a routing table organized as 160 k-buckets, one per bit position. Bucket i covers the set of nodes whose XOR distance from the owner falls in the range [2^i, 2^(i+1)).

In practice: bucket i holds nodes that share the first (159-i) bits with the owner but differ on bit i. The closer the range, the fewer nodes the network has there (since fewer nodes share many high-order bits with you).

Routing table (simplified, 8-bit IDs, K=2):


  Owner: 01000010 (66)


  bucket 0: [nodes at distance 1: 67]
  bucket 1: [nodes at distance 2-3: 64, 65]
  bucket 2: [nodes at distance 4-7: 70, 71]
  ...
  bucket 7: [nodes at distance 128-255: 130, 200]

K-bucket eviction policy: buckets have a maximum size K (20 in production). When a bucket is full and a new node is seen, Kademlia pings the oldest (least-recently-seen) entry. If it responds, it stays and the new node is dropped. If it does not respond, the new node replaces it. This makes routing tables prefer long-lived nodes, improving stability over time. Nodes that have been online for one hour have a 50% chance of staying up for another hour.

The four RPCs

Kademlia defines exactly four remote procedure calls:

RPCArgumentsReturns
PINGnodeIDPONG (liveness check)
FIND_NODEtarget nodeIDK closest nodes to target (from recipient’s table)
FIND_VALUEkeyvalue (if stored) or K closest nodes to key
STOREkey, value(ack)

All responses include the responder’s nodeID, allowing the caller to update its routing table from every interaction.

Iterative node lookup

The core operation is iterative FIND_NODE. To find the K nodes closest to a target:

1. Initialize shortlist with alpha closest nodes from own routing table
   (alpha = 3 in production, a concurrency parameter)


2. Loop:
   a. For each uncontacted node in shortlist, send FIND_NODE(target)
   b. Each responder returns K nodes it knows closest to target
   c. Add returned nodes to shortlist, deduplicate, sort by distance
   d. Keep only K closest in shortlist
   e. If shortlist did not change: stop


3. Return shortlist (K closest nodes found)

Why iterative instead of recursive? The initiating node sees every intermediate result. It can continue if a contacted node goes offline mid-lookup. Recursive routing (send the whole request along) loses visibility and cannot recover from partial failures.

A lookup in a 20-million-node network contacts roughly log(20M) / log(K) nodes, around 10-15 hops, each hop cutting the distance to the target roughly in half in XOR space.

Lookup convergence (visualized):


  Start: distance 2^159 from target
  Hop 1: closest known at 2^155  (4 bits closer)
  Hop 2: closest known at 2^151
  Hop 3: closest known at 2^147
  ...
  Hop 10: nodes within distance 1 of target

STORE and FIND_VALUE

To store a key-value pair:

  1. Run FIND_NODE(key) to get the K closest nodes to the key
  2. Send STORE(key, value) to each of those K nodes

To retrieve:

  1. Run iterative lookup using FIND_VALUE instead of FIND_NODE
  2. Each contacted node either returns the value (if it has it) or its K closest nodes to the key
  3. The first FIND_VALUE response that returns a value terminates the lookup

Kademlia does not guarantee persistence. Values should be re-published periodically (every hour in BitTorrent’s DHT, which stores peer lists for infohashes). Nodes that have the value but are not among the K closest to its key should also drop it over time.

Joining the network

A new node needs one bootstrap contact to join:

1. Node N picks a random 160-bit ID
2. N contacts a known bootstrap node B
3. N does FIND_NODE(N's own ID)  -- populates N's routing table
4. N is now reachable at its ID

The self-lookup populates N’s k-buckets because every node N contacts during the lookup learns N’s ID and adds N to its own routing tables in the appropriate bucket.

Production parameters

ParameterValueMeaning
k20k-bucket size; replication factor for stored values
alpha3Lookup concurrency; parallel FIND_NODE calls per round
ID space160 bitsSHA-1 of public key or random bytes
Republish1 hourHow often stored values are re-announced
Expire24 hoursHow long a value lives without republication
Bucket refresh1 hourHow often unused buckets trigger a random lookup

Real-world deployments

BitTorrent mainline DHT: stores (infohash, peer_list) mappings. When you open a torrent without a tracker, your client queries the DHT for peers that have announced the infohash. Over 20 million nodes at peak activity.

IPFS: uses a Kademlia variant (libp2p-kad-dht) to route content-addressed blocks. The key is the SHA-256 CID; the value is the set of provider peer IDs that have the block.

Ethereum devp2p: the discovery protocol (discv4 and discv5) uses Kademlia to find peers for the P2P network layer. Node IDs are derived from ECDSA public keys; the network uses 256-bit XOR IDs.

Storj: decentralized cloud storage uses a Kademlia-based routing layer to locate storage nodes that hold specific object shards.

Attacks and mitigations

Eclipse attack: an attacker fills your routing table with malicious nodes to isolate you from the honest network. Mitigation: Ethereum discv5 requires that bucket entries pass an ENR (Ethereum Node Record) identity proof; identity is derived from a signing key that cannot be chosen to target a specific bucket position.

Sybil attack: attacker generates many IDs close to a target key to dominate the K-closest-nodes set. Mitigation: require ID proof-of-work (puzzle based on IP address) so generating many IDs is expensive. Used in S/Kademlia.

Lookup poisoning: malicious nodes return bad peer lists during lookup. Mitigation: contact more than alpha nodes per round (S/Kademlia) and cross-validate results across independent lookup paths.

Value poisoning: STORE semantics do not authenticate who can write a key. Applications must authenticate values at the application layer (e.g., sign the stored data with the publisher’s keypair) rather than relying on DHT integrity.

Minimally functional implementation

The implementations below use an 8-bit ID space (instead of 160-bit) and K=3 (instead of K=20) for clarity. The network is simulated in memory: RPC calls are direct method invocations rather than UDP packets. The core logic (XOR routing, k-bucket management, iterative lookup, put/get) is fully functional.

idle 
Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

What the implementation does not cover

The minimal implementation above omits:

  • Network transport: real Kademlia uses UDP with a request/response correlation table and timeout handling
  • Bucket refresh: unused buckets should trigger a periodic random lookup to keep them populated
  • Value republication: stored values need periodic re-STORE to survive node churn
  • Concurrent alpha lookups: production implementations send up to alpha FIND_NODEs in parallel per round, not sequentially
  • Proof-of-work IDs: S/Kademlia adds a CPU puzzle requirement to mitigate Sybil attacks
  • Signed values: application-layer signing to prevent value poisoning

References

  • Consistent Hashing, another distributed key-to-node mapping approach, used in databases rather than P2P
  • Distributed Cryptography, cryptographic protocols that also rely on distributed key spaces
  • CAP Theorem, DHTs are AP systems: available and partition-tolerant, with eventual consistency
  • Graph Theory, Kademlia routing forms an overlay graph over the XOR metric space
Why the name "Here Be Dragons"?