Most hash tables have a table.

Kademlia has strangers.

A node wants a key. It does not know the owner. It knows a few other nodes, arranged by how their IDs differ from its own ID. It asks the closest strangers it knows. They return closer strangers. The search keeps tightening until the frontier stops improving.

That sounds like folklore until you notice the metric.

Kademlia’s distance is:

distance(x, y) = x XOR y

interpreted as an unsigned integer.

The first differing bit dominates the distance. If two IDs share many leading bits, their XOR has many leading zeros, and the integer is small. Closeness is a prefix contract.

That one choice makes the routing table feel almost inevitable.

The Metric Is Weird in Useful Ways

The original Kademlia paper by Maymounkov and Mazieres frames the system around the XOR topology.1 The paper points out three properties that are easy to underestimate:

d(x, x) = 0
d(x, y) = d(y, x)
for any x and distance delta > 0, there is exactly one y with d(x, y) = delta

Symmetry means that the nodes you query are drawn from the same kind of neighborhoods that belong in your own routing table. A received query is also fresh routing information.

Unidirectionality means lookups for the same key tend to converge along the same path, which makes caching along that path meaningful. If two people ask for the same hot key, their searches are likely to collide with the same useful intermediate nodes.

The distance is not geographic.

It is a shadow cast by bits.

Buckets Are Prefix Ranges

For a 160-bit ID space, Kademlia stores contacts in buckets indexed by distance range:

bucket i: contacts whose XOR distance is in [2^i, 2^(i+1))

In the original paper, each node keeps a k-bucket for every such range; each bucket stores up to k contacts and is ordered by time last seen.2 The least-recently seen contact is not thrown away just because a new contact appears. Kademlia first checks whether the old contact is still alive. If it is, the old live contact stays.

That policy is not only sentimentality for elders. The paper uses measurements from peer-to-peer systems to motivate the idea that nodes with longer current uptime are more likely to remain online. In that environment, an old live peer is a good thing.

There is a second benefit: a flood of new node IDs does not automatically flush your routing table. The table has a memory.

BitTorrent’s Mainline DHT keeps the same core idea in a production protocol: node IDs live in the same 160-bit space as infohashes, XOR defines closeness, and a node iteratively asks the closest nodes it knows for closer contacts.3

The Lab

The lab below uses a small 16-bit ID space so the structure is visible. It is not a BitTorrent implementation. It is a microscope:

generate live and stale nodes
build XOR k-buckets for every node
start from one source node
query up to alpha closest unqueried candidates per round
audit against the true globally closest live node

The default setting is intentionally imperfect: patchy neighborhoods, k=4, alpha=2, and 35% stale contacts. The highlighted lookup succeeds, but the bucket-size sweep shows that k=2 fails in many nearby seeds while larger buckets recover.

The lab uses 16-bit IDs for legibility. Real Kademlia-style systems commonly use much larger ID spaces, richer peer records, timeouts, refresh logic, provider records, validation, and implementation-specific termination rules.

The linear ID-space trace is a little misleading on purpose. It shows where IDs sit numerically, because that is easy to draw. But the lookup is not minimizing ordinary numeric distance. It is minimizing XOR distance to the target.

That is why a node can look far away on the line and still be a better prefix match.

The Lookup Is a Candidate Race

The modern libp2p Kademlia spec describes the lookup state in almost the same language as the lab: maintain a set of already queried peers and a set of next query candidates sorted by XOR distance to the key; query up to alpha candidate peers; add closer peers from responses; terminate after enough close peers have answered.4

That is a race between candidates.

candidate set: what I have heard of
queried set:   what I have already asked
frontier:      closest candidates not yet exhausted

When a queried node is live, it returns the closest contacts it knows. When a queried contact is stale, the lookup spends a timeout and learns nothing. The whole reason to query several candidates at once is to make a stale contact a delay, not a stop sign.

The lab’s default run finds the true owner in two rounds:

rounds:   2
queries:  4
timeouts: 1

That timeout is not decorative. It is why alpha exists.

What k Buys

The bucket-size frontier sweeps k while keeping the same scenario family. It does not claim a universal law. It is a local stress test.

In this default setup:

k = 2  succeeds in about 61% of nearby seeds
k = 4  succeeds in about 94%
k >= 6 succeeds in this sweep

The shape is the point. A larger bucket is not merely “more memory.” It is more redundant evidence in each prefix range. If one contact is stale, another may still bridge the next prefix gap.

Kademlia’s original k=20 example was chosen to make simultaneous failure of the relevant contacts unlikely over the refresh interval.2 The exact number is not sacred. The product requirement is:

enough contacts per range
fresh enough under churn
cheap enough to maintain

The Security Problem Is ID Choice

The clean mental model assumes random node IDs. That assumption is doing serious work.

If an attacker can cheaply choose many IDs near a target key, the prefix game becomes an eclipse game. The attacker does not need to break XOR. It can try to occupy the neighborhood the lookup is trying to reach.

S/Kademlia was one practical response: use public-key-derived identities, crypto puzzles, sibling lists, and multiple disjoint lookup paths to reduce the damage from Sybil and eclipse attacks.5 The paper is a useful reminder that Kademlia’s elegant routing table is not, by itself, a complete security model.

That distinction matters in real deployments:

the metric gives you a routing geometry
the admission rules decide who gets to place points in it

If node IDs are free to mint and free to choose, the geometry can be crowded by an adversary.

The Shape I Keep

A Kademlia lookup is a distributed nearest-neighbor search in a discrete metric space.

Every useful response should do one of two things:

move the frontier closer to the target
prove that a candidate path is stale

The XOR metric makes “closer” a prefix statement. The k-buckets make sure a node does not need to know the whole network, only representatives at exponentially wider distance ranges. The alpha parameter lets the lookup spend a little extra bandwidth to avoid waiting for a single dead contact.

This is the compact design:

prefix geometry
bounded memory
iterative discovery
parallel doubt

The table is not the hash table.

The table is the rumor network that lets the hash table exist.

Reproducibility Notes

The executable artifact is assets/js/kademlia-xor-lab.js.

The implementation builds:

16-bit node IDs
XOR distance and bucket indexing
per-node k-buckets with stale contacts
alpha-parallel iterative FIND_NODE-style lookup
global nearest-live-node audit
bucket-size success frontier across nearby seeds

The audit checks:

XOR symmetry and unidirectionality
bucket index boundaries
contacts placed in matching source buckets
FIND_NODE-style responses capped at k and sorted by XOR distance
best seen distance never increases during lookup
perfect small tables find the true owner

The real systems have more machinery. This toy keeps the part that I think is worth holding in your head:

XOR distance turns a network lookup into a prefix race.

  1. Petar Maymounkov and David Mazieres, “Kademlia: A Peer-to-peer Information System Based on the XOR Metric”, IPTPS 2002. The Springer page is “A Peer-to-Peer Information System Based on the XOR Metric”. ↩

  2. Maymounkov and Mazieres, “Kademlia,” Section 2.1, on k-buckets, least-recently seen ordering, and keeping old live contacts. ↩ ↩2

  3. Andrew Loewenstern and Arvid Norberg, “BEP 5: DHT Protocol”, BitTorrent Enhancement Proposals. The overview describes node IDs, XOR distance, iterative lookup, and token-based announce protection. ↩

  4. libp2p, “Kademlia DHT specification”, especially the definitions of k, XOR distance, alpha, and the iterative peer-routing process. The IPFS specialization is documented at “IPFS Kademlia DHT”. ↩

  5. Ingmar Baumgart and Sebastian Mies, “S/Kademlia: A Practicable Approach Towards Secure Key-Based Routing”, 2007. ↩