Introduction

Every time you download a torrent, your client has to find the peers who hold the pieces you want — without any central server to ask. The network can have millions of nodes. Yet your client locates the right peers in a handful of messages. The algorithm that makes this possible is Kademlia, introduced by Petar Maymounkov and David Mazières in 2002.

The core insight is a peculiar definition of distance between nodes. Instead of geographic or network distance, Kademlia uses the bitwise XOR of two node IDs. This arithmetic distance has a remarkable property: it organises the network into a binary prefix tree, so that each hop towards a target cuts the remaining distance in half — and the lookup terminates in at most O(log⁡2N)O(\log_{2} N) steps no matter how large the network grows.

Kademlia is not just a theoretical curiosity. It is the live routing substrate of BitTorrent's DHT (the system that tracks who has what without a tracker), the peer discovery layer of Ethereum, and the backbone of IPFS. Understanding Kademlia means understanding how decentralised systems find anything without anyone in charge.

Try It: XOR Routing in Action

The network below has 16 nodes, each with a 4-bit ID (0000 to 1111). Pick any target key and press Find to watch the lookup hop through the network using XOR distance. The searcher always contacts the known node whose ID is closest to the target under XOR — each hop halves the remaining distance, so the lookup finishes in at most 4 hops.

<div class="hint">A 16-node Kademlia network with <b>k-bucket routing tables</b> (k=2). Each node only knows O(log N) peers — one bucket per bit position. XOR is the distance metric. Pick a target and watch the lookup converge in ≤ 4 hops.</div>
<div class="controls">
  <label>Target key: <select id="target"></select></label>
  <label>Start: <select id="startNode"></select></label>
  <button id="findBtn" type="button">Find</button>
  <button id="resetBtn" type="button" class="ghost">Reset</button>
</div>
<div class="network-wrap">
  <svg id="network" viewBox="0 0 340 280" xmlns="http://www.w3.org/2000/svg"></svg>
</div>
<div id="log" class="log"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .85rem; color: #444; margin-bottom: .6rem; line-height: 1.45; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; align-items: center; margin-bottom: .6rem; }
label { font-size: .85rem; }
select { font-size: .85rem; padding: .2rem .35rem; border: 1px solid #aaa; border-radius: 5px; }
button { font: 600 13px system-ui; padding: .35rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.network-wrap { width: 100%; overflow: hidden; }
svg { width: 100%; height: auto; display: block; }
.log { font-size: .82rem; line-height: 1.6; color: #333; margin-top: .5rem;
       background: #f5f7fa; border-radius: 7px; padding: .5rem .7rem;
       min-height: 2rem; max-height: 130px; overflow-y: auto; }
.log .hop { color: #1d3557; }
.log .found { color: #0a7d33; font-weight: 700; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Kademlia XOR routing — 16 nodes (4-bit IDs), k-bucket routing tables (k=2).
// Each node stores only O(log N) peers: one bucket per bit position.
// Lookup: greedily move to the known node closest to the target under XOR.
const N = 16, K = 2;
const ids = Array.from({length: N}, (_, i) => i);

// Highest set bit of xor (bucket index)
function highestBit(xor) {
  if (xor === 0) return -1;
  let b = 0;
  while ((1 << (b + 1)) <= xor) b++;
  return b;
}

// Build routing table for one node: buckets[bitPos] = [up to K node IDs]
function buildRT(nodeId) {
  const buckets = {};
  ids.forEach(id => {
    if (id === nodeId) return;
    const bit = highestBit(id ^ nodeId);
    if (!buckets[bit]) buckets[bit] = [];
    if (buckets[bit].length < K) buckets[bit].push(id);
  });
  return buckets;
}

const routingTables = {};
ids.forEach(id => { routingTables[id] = buildRT(id); });

// Greedy XOR lookup using routing tables
function kademliaLookup(start, target) {
  const path = [start];
  const visited = new Set([start]);
  let current = start;
  while (current !== target) {
    const known = Object.values(routingTables[current]).flat();
    let best = -1, bestDist = current ^ target; // must strictly improve
    known.forEach(id => {
      if (!visited.has(id)) {
        const d = id ^ target;
        if (d < bestDist) { bestDist = d; best = id; }
      }
    });
    if (best === -1) break; // stuck — target not reachable with strict improvement
    visited.add(best);
    path.push(best);
    current = best;
  }
  return path;
}

// SVG layout — nodes on a circle
const CX = 170, CY = 140, R = 112;
function nodePos(id) {
  const angle = (id / N) * 2 * Math.PI - Math.PI / 2;
  return { x: CX + R * Math.cos(angle), y: CY + R * Math.sin(angle) };
}

const svgEl = document.getElementById('network');
const ns = 'http://www.w3.org/2000/svg';

function el(tag, attrs) {
  const e = document.createElementNS(ns, tag);
  Object.entries(attrs).forEach(([k, v]) => e.setAttribute(k, v));
  return e;
}

function drawNetwork(path) {
  while (svgEl.firstChild) svgEl.removeChild(svgEl.firstChild);
  const target = parseInt(document.getElementById('target').value);

  // Draw path edges
  for (let i = 0; i + 1 < path.length; i++) {
    const a = nodePos(path[i]), b = nodePos(path[i + 1]);
    svgEl.appendChild(el('line', {
      x1: a.x, y1: a.y, x2: b.x, y2: b.y,
      stroke: '#e63946', 'stroke-width': '2', 'stroke-dasharray': '5 3'
    }));
    // Arrow tip
    const dx = b.x - a.x, dy = b.y - a.y;
    const len = Math.sqrt(dx * dx + dy * dy) || 1;
    const ux = dx / len, uy = dy / len;
    const tx = b.x - ux * 15, ty = b.y - uy * 15;
    const px = -uy * 5, py = ux * 5;
    const pts = (tx + px) + ',' + (ty + py) + ' ' + b.x + ',' + b.y + ' ' + (tx - px) + ',' + (ty - py);
    svgEl.appendChild(el('polygon', { points: pts, fill: '#e63946' }));
  }

  // Draw nodes
  ids.forEach(id => {
    const pos = nodePos(id);
    const bin = id.toString(2).padStart(4, '0');
    const inPath = path.includes(id);
    const isStart = path.length > 0 && path[0] === id;
    const isEnd = path.length > 0 && path[path.length - 1] === id;
    const isTarget = id === target;

    let fill = '#dce8f5', stroke = '#a8c4d8', sw = '1.3', textFill = '#1d3557', sd = '';
    if (isEnd && isTarget) { fill = '#0a7d33'; stroke = '#065c25'; textFill = '#fff'; }
    else if (isStart) { fill = '#1d3557'; stroke = '#0d2035'; textFill = '#fff'; }
    else if (inPath) { fill = '#457b9d'; stroke = '#1d3557'; textFill = '#fff'; }
    else if (isTarget) { fill = '#fff'; stroke = '#e63946'; sw = '2'; sd = '3 2'; }

    const g = document.createElementNS(ns, 'g');
    const c = el('circle', { cx: pos.x, cy: pos.y, r: 14, fill, stroke, 'stroke-width': sw });
    if (sd) c.setAttribute('stroke-dasharray', sd);
    g.appendChild(c);
    g.appendChild(el('text', {
      x: pos.x, y: pos.y, 'text-anchor': 'middle', 'dominant-baseline': 'central',
      'font-size': '9', 'font-family': 'ui-monospace,monospace', 'font-weight': '700', fill: textFill
    })).textContent = bin;
    svgEl.appendChild(g);
  });
}

let animTimer = null;

function runLookup() {
  if (animTimer) { clearTimeout(animTimer); animTimer = null; }
  const target = parseInt(document.getElementById('target').value);
  const start = parseInt(document.getElementById('startNode').value);
  const path = kademliaLookup(start, target);
  // Build log
  const logEl = document.getElementById('log');
  logEl.innerHTML = '';
  path.forEach((id, i) => {
    const bin = id.toString(2).padStart(4, '0');
    const xorDist = id ^ target;
    const xorBin = xorDist.toString(2).padStart(4, '0');
    if (i === 0) {
      logEl.innerHTML += fmt('<span class="hop">Start node %id% (%bin%): XOR to target = %xorBin% (%xorDist%)</span><br>', { id: id, bin: bin, xorBin: xorBin, xorDist: xorDist });
    } else if (id === target) {
      logEl.innerHTML += fmt('<span class="found">Hop %i%: arrived at target %id% (%bin%) — done in %i% hop%v%!</span>', { i: i, id: id, bin: bin, v: i !== 1 ? 's' : '' });
    } else {
      logEl.innerHTML += fmt('<span class="hop">Hop %i%: node %id% (%bin%): XOR to target = %xorBin% (%xorDist%)</span><br>', { i: i, id: id, bin: bin, xorBin: xorBin, xorDist: xorDist });
    }
  });
  if (path[path.length - 1] !== target) {
    logEl.innerHTML += '<span style="color:#c92f3c">Could not reach target from this start node with strict XOR improvement.</span>';
  }
  // Animate step by step
  let step = 0;
  function animate() {
    drawNetwork(path.slice(0, step + 1));
    if (step < path.length - 1) { step++; animTimer = setTimeout(animate, 650); }
  }
  animate();
}

// Populate selects
const targetSel = document.getElementById('target');
const startSel = document.getElementById('startNode');
ids.forEach(id => {
  const bin = id.toString(2).padStart(4, '0');
  [targetSel, startSel].forEach((sel, idx) => {
    const o = document.createElement('option');
    o.value = id;
    o.textContent = id + ' (' + bin + ')';
    sel.appendChild(o);
  });
});
targetSel.value = 11;
startSel.value = 0;

document.getElementById('findBtn').addEventListener('click', runLookup);
document.getElementById('resetBtn').addEventListener('click', () => {
  if (animTimer) { clearTimeout(animTimer); animTimer = null; }
  drawNetwork([]);
  document.getElementById('log').innerHTML = '';
});

drawNetwork([]);
Result
Console

Notice the pattern: the first hop fixes the most-significant bit of the XOR difference, the second fixes the next bit, and so on. Each step peels off one binary digit of uncertainty. With N = 242^{4} = 16 nodes, 4 hops always suffice — and with a billion nodes (2302^{30}), only 30 hops would be needed.

The Real Complexity

Status: solved — Kademlia lookup is proven to run in O(log⁡N)O(\log N) network hops, where N is the number of nodes. This was established by Maymounkov and Mazières in their 2002 paper and has been implemented at internet scale.

The proof rests on two pillars:

  • XOR is a valid metric. It satisfies the identity, symmetry, and triangle inequality axioms required for a distance function. This means you can reason about Kademlia routing the same way you reason about navigating a map.
  • Each hop halves the distance. Node IDs are b-bit integers (typically 160 bits for SHA-1 based networks). When a node contacts the closest known peer to the target, the XOR distance to the target drops by at least half. After at most b steps, the distance is 0 and the target has been found — giving O(b)O(b) = O(log⁡N)O(\log N) hops.

K-buckets are the data structure that makes this concrete: each node divides remote peers into b buckets, one per bit position, each holding up to k peers at that XOR distance. A lookup message reaches the right bucket in O(1)O(1) and converges in O(log⁡N)O(\log N) messages total.

Compare this to a naive approach: a flat list of all peers would require O(N)O(N) storage and O(N)O(N) messages to search. Kademlia achieves O(log⁡N)O(\log N) for both storage per node and lookup hops — a fundamental improvement that makes the protocol viable at internet scale.

Kademlia also handles churn gracefully: because multiple nodes are stored per bucket, the network continues to function even when a large fraction of nodes go offline simultaneously. This is the practical reason BitTorrent's DHT — with tens of millions of simultaneous nodes — can withstand the constant join-and-leave behaviour of home computers.

For related ideas on how distributed systems reach agreement despite failures, see the article on P vs NP and on PageRank.

Where It Matters

Kademlia is not a textbook algorithm kept in a drawer. It runs right now inside systems used by hundreds of millions of people:

  • BitTorrent DHT: the mainline DHT that lets you download a torrent without any tracker. Every peer announces what it has and uses Kademlia to find other peers — today the network sustains tens of millions of simultaneous nodes.
  • Ethereum: the devp2p discovery protocol (based on Kademlia) that lets Ethereum nodes find each other before they begin syncing the blockchain.
  • IPFS: the InterPlanetary File System uses a Kademlia variant (libp2p-kad-dht) to locate which peers store each content-addressed block.
  • Kad network (eMule/eDonkey): an early large-scale deployment that validated the protocol at millions of nodes before BitTorrent adopted it.
  • Academic research into structured P2P: Kademlia's clean XOR metric makes it a standard reference point for analysing routing overlay networks, fault tolerance, and eclipse attacks.

The deeper lesson is about decentralised indexing: any time you need to find a resource in a network with no central registry, a DHT with O(log⁡N)O(\log N) routing is the standard solution. Kademlia's specific design — symmetric XOR distance, k-buckets, parallel α-queries — has proven robust enough to outlast most of the P2P systems of its era.

Conclusion

Kademlia's elegance is its distance function. By defining distance as XOR rather than latency or hops, Maymounkov and Mazières turned a routing problem into a binary search — each step peels off one bit of uncertainty, and the lookup collapses from O(N)O(N) to O(log⁡N)O(\log N).

The next time a BitTorrent client finds a peer in seconds, or an Ethereum node discovers the network in a handful of messages, you are seeing Kademlia at work. A 21-year-old algorithm, forged from one clever arithmetic trick, still carries a significant fraction of the world's decentralised traffic.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/kademlia/Content licensed under CC BY-NC 4.0.