Key Question

Where does Kademlia show up in real decentralized systems?

Deep Dive

BitTorrent Mainline DHT (~50M+ nodes)

The largest deployed DHT. Every BitTorrent client (uTorrent, Transmission, qBittorrent, etc.) can join the DHT and find peers without a tracker.

Without DHT:                    With DHT (Mainline):
  Client → Tracker → Peer list    Client → DHT → Peer list
             ↑                         ↑
         (centralized)           (fully distributed)

When you add a torrent, you announce yourself to the DHT using the infohash as key. When someone else searches for that infohash, the DHT returns your IP. No tracker required. The Mainline DHT uses a slightly modified Kademlia (8-byte IDs instead of 20-byte, k=8 instead of 20).

IPFS (InterPlanetary File System)

IPFS uses S/Kademlia — a security-hardened variant. Two key differences from vanilla Kademlia:

1. Proof-of-Work Node IDs: Generating a node ID requires finding a hash with leading zero bits. This prevents Sybil attacks where an attacker generates millions of IDs to surround a target.

2. Disjoint Path Routing: Instead of asking the k closest nodes, S/Kademlia sends lookups along d disjoint paths. Even if an attacker controls nodes on some paths, one path may be clean.

Vanilla Kademlia:          S/Kademlia:
All queries converge       Queries follow d
on the same k nodes        independent paths
     ┌──┐                        ┌──┐
     │Q │──────→target            │Q │─┬─→Path A
     └──┘                        └──┘ ├─→Path B
                                       └─→Path C
If attacker controls         Attacker must control
the close nodes →            all d paths →
false results.               harder to exploit.

Ethereum devp2p Discovery

Ethereum’s node discovery protocol (discv4, discv5) uses Kademlia-like routing. Each node maintains a k-bucket table. When a new peer is discovered via UDP, it’s added to the appropriate bucket. The FIND_NODE mechanism works identically to Kademlia’s.

I2P

The “Invisible Internet Project” uses Kademlia-inspired DHT for its garlic routing network, combined with a structured overlay for hiding user identities.

Real-World Challenges

Check Your Understanding

1. Why does IPFS use proof-of-work for node ID generation?
2. How does the Mainline DHT differ from standard Kademlia?
3. What advantage does disjoint path routing provide against adversarial nodes?

The “So What?”

Kademlia isn’t just academic — it’s running on your machine right now if you’ve used BitTorrent or joined an IPFS swarm. The Mainline DHT is the largest distributed system on the planet by node count, and it runs on a protocol designed in 2002 with almost zero modification.

✏️ Exercises

Exercises: DHTs & Kademlia

Exercise 1

In Kademlia with 8-bit IDs, what is the XOR distance between node IDs 11001010 and 11011010?

Exercise 2

Why does Kademlia use parallel queries (α > 1) instead of sequential queries (α = 1)? What’s the trade-off?

Exercise 3

What problem does S/Kademlia’s disjoint path routing solve, and how does it protect against an attacker who controls ~30% of the network?

Exercise 4 (Challenge)

In a Kademlia network with N = 100,000 nodes and k = 20, assume each node has a fully populated routing table. How many distinct nodes can a single node know about (maximum)? How many hops should a lookup take in the worst case?

  11001010
⊕ 11011010
──────────
  00010000  = 16