⏱️ Lectura: 14 min
BitTorrent finds the node that has a file among millions of peers without asking any central server. The answer arrives in just a few hops thanks to Kademlia, a 2002 algorithm that also underpins the IPFS network and node discovery on Ethereum.
📑 En este artículo
- TL;DR
- What Kademlia Is and Why It Matters
- How It Works: XOR Distance and k-buckets
- Practical Examples: Implementing Kademlia in Miniature
- Getting Started: Running a Real Kademlia Node
- Real-World Use Cases
- Common Mistakes and Best Practices
- Comparison: Kademlia vs. Other DHTs
- Going Deeper: Why the XOR Metric Is the Key Piece
- Frequently Asked Questions
- References
Kademlia solves a classic distributed systems problem: how to locate a piece of data, or a node, in a network with no central coordinator and participants constantly appearing and disappearing. Its trick is a distance metric based on XOR that reduces routing to a simple binary table.
TL;DR
- You’ll understand what a distributed hash table (DHT) is and why it replaces a central index server.
- You’ll calculate the XOR distance between two node IDs, the foundation of all routing in Kademlia.
- You’ll see how a k-bucket table is built and why the value k=20 isn’t arbitrary.
- You’ll simulate an iterative node lookup in Python, step by step.
- You’ll identify Sybil and eclipse attacks, and how Kademlia defends against them.
- You’ll compare Kademlia against Chord and Pastry to choose the right DHT for your use case.
What Kademlia Is and Why It Matters
A distributed hash table (DHT) is a key-value dictionary spread across thousands of computers, with no single node knowing the complete map. Each node stores a portion of the keys and knows who to ask for the rest.
Kademlia, described in 2002 by Petar Maymounkov and David Mazières, is the most widely used DHT design in practice. BitTorrent adopted it in 2005 as the DHT Protocol (BEP 5) to eliminate dependence on a central tracker: if a torrent’s tracker went down, the network could still find peers on its own.
The same design, with variations, now runs inside libp2p, the networking layer of IPFS and Filecoin, and in Ethereum’s node discovery protocol. The reason for its success is simple: the routing logic fits into a single arithmetic operation, XOR, which makes it easy to implement and reason about.
How It Works: XOR Distance and k-buckets
The XOR Metric
Every node and every key in Kademlia has a 160-bit identifier, derived from SHA-1 in the original design. The distance between two identifiers isn’t geographic or based on network hops: it’s the result of applying a bitwise XOR between the two numbers.
# XOR distance between two node IDs (8-bit IDs for this example)
node_a = 0b10110010
node_b = 0b10100001
distancia = node_a ^ node_b
print(bin(distancia)) # 0b00010011 -> 19 in decimalThis operation has a key property: it’s a valid mathematical metric (it satisfies symmetry and the triangle inequality) and it’s also unidirectional. For any given ID there’s exactly one node at each possible distance, so there’s no ambiguity about who’s closest.
k-buckets: The Routing Table
Each node organizes its known neighbors into a list of k-buckets. Bucket i holds up to k nodes whose XOR distance to the local node falls within the range [2^i, 2^(i+1)). With 160-bit IDs there are 160 possible buckets, though almost none fill up in practice.
The value k that Maymounkov and Mazières propose in the original paper is 20. It isn’t arbitrary: it models how many simultaneous node failures a bucket can tolerate before losing contact with that region of the ID space.
flowchart TD
Root["Local node"] --> B0["Bucket 0: distance [1,2)"]
Root --> B1["Bucket 1: distance [2,4)"]
Root --> B2["Bucket 2: distance [4,8)"]
Root --> B3["Bucket ...159: far distance"]
B0 --> N1["up to k=20 nodes"]
B1 --> N2["up to k=20 nodes"]
B2 --> N3["up to k=20 nodes"]The Protocol’s Four RPC Messages
Kademlia defines only four types of messages between nodes. PING checks that a node is still alive. STORE asks a node to save a key-value pair. FIND_NODE requests the k nodes closest to a given ID. FIND_VALUE works like FIND_NODE, but if the queried node already has the requested value stored, it returns it directly instead of a list of neighbors.
This minimal set of messages is another reason for the design’s popularity: implementing Kademlia in full requires no more than four network handlers and the k-bucket logic already covered.
How a Node Is Found: Iterative FIND_NODE
To locate a node, or a key, Kademlia doesn’t forward the request down a chain like a recursive protocol. The searching node queries the α (alpha) closest nodes it knows, typically α = 3, in parallel, and asks each for its own closest neighbors to the target.
With each response, the searcher builds an increasingly precise list and repeats the process against the new candidates, until no round produces a node closer than the best one already known. This converges in O(log n) hops for a network of n nodes.
sequenceDiagram
participant A as Searching node
participant B as Nearby node 1
participant C as Nearby node 2
A->>B: FIND_NODE(target)
B-->>A: list of closest neighbors
A->>C: FIND_NODE(target)
C-->>A: list of closest neighbors
Note over A: repeats with the new candidates until it convergesPractical Examples: Implementing Kademlia in Miniature
Let’s build, in simplified Python, the minimal pieces of a Kademlia node: the XOR distance, insertion into a k-bucket, and a toy iterative lookup over an in-memory simulated network.
Step 1: Distance and Closeness Ordering
def distancia_xor(id_a, id_b):
return id_a ^ id_b
def mas_cercanos(id_objetivo, candidatos, k=20):
return sorted(candidatos, key=lambda nid: distancia_xor(id_objetivo, nid))[:k]
# example with 8-bit IDs to keep it simple
objetivo = 0b01100110
red = [0b01100000, 0b11111111, 0b01100111, 0b10000000]
print(mas_cercanos(objetivo, red, k=2))
# returns the 2 IDs with the smallest XOR distance to the targetThis function is the heart of the whole algorithm: any node can sort any set of candidates by closeness without coordinating with anyone else.
Step 2: Inserting Into a k-bucket
class KBucket:
def __init__(self, k=20):
self.k = k
self.nodos = [] # ordered list: most recent at the end
def insertar(self, nodo_id):
if nodo_id in self.nodos:
self.nodos.remove(nodo_id)
self.nodos.append(nodo_id) # moved to the end: still alive
elif len(self.nodos) < self.k:
self.nodos.append(nodo_id)
else:
# bucket full: ping the oldest one (self.nodos[0])
# if it doesn't respond, drop it and add the new node
passThe replacement rule is deliberate: Kademlia favors older nodes over new ones, because a node that has been connected for a while is statistically more reliable than one just seen. This makes the network more resistant to an attacker flooding it with short-lived nodes.
Step 3: Full Iterative Lookup (Simulation)
def buscar(id_objetivo, mi_bucket, red_simulada, alpha=3, k=20):
consultados = set()
mejores = mas_cercanos(id_objetivo, mi_bucket.nodos, k)
while True:
candidatos = [n for n in mejores if n not in consultados][:alpha]
if not candidatos:
break
nuevos = []
for nodo in candidatos:
consultados.add(nodo)
nuevos.extend(red_simulada.get(nodo, []))
combinados = list(set(mejores + nuevos))
actualizados = mas_cercanos(id_objetivo, combinados, k)
if actualizados == mejores:
break # no round improved: converged
mejores = actualizados
return mejoresThe loop stops when a full round doesn’t get any closer to the target, the same convergence condition used in the real algorithm. In a network of thousands of nodes this takes only a few iterations, because each round reduces the XOR distance significantly.
Getting Started: Running a Real Kademlia Node
To experiment without writing the protocol from scratch, the Python kademlia library implements the full algorithm on top of asyncio.
pip install kademliaimport asyncio
from kademlia.network import Server
async def main():
servidor = Server()
await servidor.listen(8468)
await servidor.bootstrap([("127.0.0.1", 8469)]) # seed node for the network
await servidor.set("example-key", "value-stored-in-the-dht")
resultado = await servidor.get("example-key")
print(resultado) # "value-stored-in-the-dht"
servidor.stop()
asyncio.run(main())The bootstrap() method is the only real external dependency: a new node needs to know at least one node already connected to the network to start populating its routing table. From there, set() and get() distribute reads and writes among the nodes closest to the key, calculated with the same XOR distance from the earlier example.
💡 Tip: to test with more than one node on your machine, run several processes on different ports and use 127.0.0.1 as the bootstrap address for each one.
Real-World Use Cases
BitTorrent was the first large-scale deployment. Before 2005, every torrent depended on a central HTTP tracker that listed who had the file. If the tracker went down, the torrent was orphaned even if thousands of peers were still connected. The Mainline DHT (BEP 5) fixed that: today any BitTorrent client participates in a single global DHT shared across all torrents.
IPFS and Filecoin use the Kademlia implementation inside libp2p for two different purposes: finding which node holds the content for a content hash (content routing) and discovering another node’s network address (peer routing).
Ethereum uses a variant of Kademlia in its discv5 protocol so nodes can find each other on the P2P network, even before they start syncing blocks or transactions.
Common Mistakes and Best Practices
The most cited criticism against Kademlia-style DHTs is the Sybil attack: an attacker creates thousands of fake identities to surround a specific key and censor or intercept traffic toward it. Kademlia doesn’t solve this by design; mitigating it requires external layers, such as node IDs derived from proof that’s expensive to generate in bulk.
A second risk is the eclipse attack: surrounding a specific node, not a key, with malicious nodes to isolate it from the real network and show it a fake view. The practical defense is diversifying bootstrap sources and periodically refreshing buckets instead of relying on a single static routing table.
It’s also common to underestimate churn: on a public network, a large share of nodes disconnect within minutes. That’s why the algorithm periodically pings inactive buckets and prioritizes older nodes over new ones, as we saw in step 2 of the example. Skipping bucket refresh is the most frequent implementation mistake: a routing table that doesn’t get updated goes blind to a large part of the network within hours.
A detail that surprises first-time Kademlia implementers: key-value pairs stored with STORE expire on their own, typically after 24 hours. The originating node must republish them before they expire, or the value disappears from the network even if the node that created it is still connected.
Comparison: Kademlia vs. Other DHTs
Before choosing a DHT design, it helps to consider the context of use: a public network with thousands of anonymous participants is not the same as an internal cluster controlled by a single operator.
| Design | When to Use It | Advantage | Limitation |
|---|---|---|---|
| Kademlia | Public P2P networks with high churn (BitTorrent, IPFS) | Simple O(log n) routing, tolerates failures without coordination | Vulnerable to Sybil/eclipse attacks without extra layers |
| Chord | Academic systems or controlled ring topologies | Formal proof of convergence, very simple design | Worse tolerance to simultaneous failures than Kademlia |
| Pastry | Networks that need routing aware of real network proximity | Optimizes physical latency, not just logical distance | More complex to implement and debug |
| Centralized tracker | Small networks or those controlled by a single operator | Total simplicity, instant queries | Single point of failure and censorship |
Going Deeper: Why the XOR Metric Is the Key Piece
The choice of XOR as a distance metric isn’t cosmetic. XOR is symmetric (d(a,b) = d(b,a)), satisfies the triangle inequality, and unlike other possible metrics, is unidirectional: for any reference point and any distance, there’s exactly one point at that exact distance.
That unidirectionality means information learned during one lookup is always useful in the next one: when node A learns about node C while searching for B, that information is useful both if A searches for B again and if it searches for any other target close to C. With ambiguous metrics, like Chord’s modular ring distance, that reuse of information is more limited.
💭 Key point: XOR’s unidirectional property means two nodes are never at the same distance from a third one unless they’re the same node, so the routing table never has ambiguity about who to ask first.
The other fine detail is the difference between iterative lookup, the one implemented above, where the searching node controls each round, and recursive lookup, where each node forwards the request to the next one. Kademlia uses iterative lookup because it gives the searcher full control over the parallelism and timeout of each hop, at the cost of more messages across the network than a recursive chain. The typical value α=3 balances latency and network traffic: raising it speeds up convergence but multiplies the parallel messages; lowering it saves bandwidth at the cost of more rounds.
flowchart LR
subgraph Centralizado["Model with a central tracker"]
T["Tracker"] --- P1["Peer 1"]
T --- P2["Peer 2"]
T --- P3["Peer 3"]
end
subgraph DHT["Kademlia model"]
N1["Node 1"] --- N2["Node 2"]
N2 --- N3["Node 3"]
N1 --- N3
end📖 Summary on Telegram: View summary
Your next step: install the kademlia library with pip install kademlia and spin up two local nodes on different ports to see bootstrap() and set()/get() working between them.
Frequently Asked Questions
Does Kademlia need a central server to start?
It doesn’t need a permanent server, but it does need a seed (bootstrap) node to connect to the first time. That node can be any other active member of the network, not a server with special privileges.
What happens if the node I’m looking for is no longer connected?
The iterative lookup still converges: it returns the live nodes closest to the target ID, which in a key-value storage DHT are the ones responsible for holding that key according to XOR distance.
Why 160-bit IDs and not fewer?
160 bits corresponds to the size of a SHA-1 hash, which is what the original design uses to generate identifiers with virtually no chance of collision between nodes.
Is Kademlia the same thing as blockchain?
No. Kademlia is a distributed routing and storage structure, with no consensus or total ordering of events. A blockchain can use Kademlia, as discv5 does in Ethereum, just to let nodes find each other, not to agree on state.
Can Kademlia be used for a private, non-public P2P application?
Yes. Any system that needs to locate data across many nodes without a central index can adopt the design, though in small, trusted networks the cost of addressing Sybil or eclipse attacks often isn’t justified compared to a simple centralized directory.
References
- Kademlia: A Peer-to-peer Information System Based on the XOR Metric: the original paper by Maymounkov and Mazières, 2002.
- BEP 5: DHT Protocol: the specification of the Mainline DHT used by BitTorrent.
- Kademlia DHT in libp2p: official documentation for the implementation used by IPFS and Filecoin.
- bmuller/kademlia: reference implementation in Python on top of asyncio, used in this article’s examples.
- Kademlia on Wikipedia: general overview of the algorithm and its history.
📱 Enjoy this content? Follow @programacion on Telegram for daily tech content in Spanish: quick summaries, fresh content every day.
Imagen destacada: Foto de GuerrillaBuzz en Unsplash
0 Comments