Kademlia: el protocolo XOR que organiza las DHT de BitTorrent e IPFS

Lo esencial

• Kademlia es un protocolo de tabla hash distribuida (DHT) publicado en 2002 por Petar Maymounkov y David Mazières.
• Cada nodo tiene un ID de 160 bits y mide la distancia a otros nodos con la operación XOR.
• BitTorrent usa Kademlia en su extensión mainline DHT (BEP 5) para encontrar peers sin tracker central.
• IPFS implementa Kademlia en go-libp2p-kad-dht para localizar qué nodo guarda un bloque de contenido.
• Las búsquedas resuelven en O(log n) saltos gracias a las k-buckets que organizan contactos por distancia XOR.
• Cada nodo guarda hasta k contactos (típicamente k=20) por cada rango de distancia en su tabla de enrutamiento.
• El algoritmo tolera nodos que se desconectan sin avisar: no depende de un coordinador único.

Qué es Kademlia

BitTorrent no depende de un tracker central para saber quién tiene un archivo: desde 2005 usa una red de nodos que se localizan entre sí gracias a Kademlia. El protocolo lo diseñaron Petar Maymounkov y David Mazières en 2002, en un paper publicado en Lecture Notes in Computer Science, como una tabla hash distribuida que reparte la responsabilidad de guardar datos entre todos los nodos de la red.

Una DHT funciona como un diccionario gigante repartido entre miles de máquinas: cada una guarda solo una porción de las claves y valores, y el protocolo define cómo encontrar quién tiene la clave que buscás. Kademlia resuelve ese problema midiendo la distancia entre nodos con la operación XOR sobre sus identificadores.

La distancia XOR: la métrica central

Cada nodo recibe un identificador aleatorio de 160 bits, el mismo tamaño que produce el hash SHA-1. La distancia entre dos nodos A y B no es geográfica ni de latencia: es el resultado de la operación A XOR B, interpretado como un número entero.

Esta métrica tiene una propiedad clave: es simétrica (la distancia de A a B es igual a la de B a A) y cumple la desigualdad triangular, lo que permite construir una tabla de enrutamiento coherente. Cuantos más bits iniciales comparten dos IDs, más cerca están en el espacio XOR, sin importar en qué parte del mundo esté cada máquina.

Cómo se organizan los nodos: k-buckets

Cada nodo mantiene una tabla de enrutamiento dividida en 160 k-buckets, uno por cada bit de distancia posible. El bucket i guarda hasta k contactos (el valor original del paper es k=20) cuyos IDs difieren del propio en el bit i.

Esta división logarítmica explica por qué Kademlia escala: un nodo no necesita conocer a todos los demás, solo mantiene más contactos cercanos que lejanos. Cuando un bucket se llena, se pinga primero al contacto más antiguo; si sigue activo, el contacto nuevo se descarta, porque en la práctica los nodos con más tiempo en línea rara vez desaparecen.

Cómo funciona una búsqueda: FIND_NODE paso a paso

Buscar un nodo o un valor arranca con el mensaje FIND_NODE: quien busca le pide a sus contactos más cercanos, según distancia XOR, los contactos que ellos conocen que estén aún más cerca del objetivo. Cada ronda acerca la búsqueda a la mitad del espacio de IDs restante.

Por eso una búsqueda en una red de n nodos toma en promedio log2(n) saltos: en una red de un millón de nodos bastan unas 20 rondas para llegar al destino. El nodo que arranca la búsqueda consulta en paralelo a varios contactos (el parámetro α, normalmente 3) para tolerar que algunos no respondan.

Ejemplo práctico: calcular la distancia XOR

Calcular la distancia XOR entre dos IDs es aritmética simple. Este fragmento en Python simula el cálculo que hace cada nodo al decidir a quién preguntarle primero:

def xor_distance(id_a: int, id_b: int) -> int:
    return id_a ^ id_b

nodo_local = 0b1010110001
nodo_objetivo = 0b1010110111

distancia = xor_distance(nodo_local, nodo_objetivo)
print(f"{distancia:010b}")  # 0000000110: comparten 7 bits iniciales

Cuantos más ceros aparecen al inicio del resultado, más cerca está el nodo objetivo. Un nodo real repite este cálculo contra cada entrada de su tabla de enrutamiento para elegir a quién reenviarle la consulta.

Kademlia en BitTorrent: la mainline DHT

BitTorrent formalizó su implementación en la especificación BEP 5. Ahí se define la mainline DHT: cada cliente BitTorrent es también un nodo Kademlia, y el infohash de un torrent funciona como la clave que hay que localizar.

Cuando un cliente quiere descargar un torrent sin tracker, ejecuta get_peers sobre el infohash: la búsqueda XOR lo acerca a los nodos que anunciaron tener ese infohash con announce_peer. Esto es lo que permite descargar torrents magnet sin depender de ningún servidor central.

Kademlia en IPFS: encontrar quién tiene un bloque

IPFS usa una variante de Kademlia implementada en go-libp2p-kad-dht, dentro de la pila de libp2p. Ahí la clave que se busca no es un infohash sino el CID (identificador de contenido) de cada bloque de datos.

La diferencia frente a BitTorrent es que IPFS separa el descubrimiento de peers del transporte de datos: Kademlia solo responde qué nodos anunciaron tener ese CID, y después libp2p negocia la conexión y la transferencia por un protocolo aparte.

Limitaciones: cuándo Kademlia no conviene

Kademlia asume que los identificadores se distribuyen al azar; si un atacante genera muchos IDs cercanos al de un dato objetivo (un ataque Sybil dirigido), puede rodear ese dato y censurarlo o vigilar quién lo pide. Ninguna DHT pública resuelve esto sin mecanismos adicionales de reputación o costo computacional sobre el ID.

Tampoco conviene para datos que cambian con frecuencia: cada actualización implica volver a anunciar la clave en toda la red, y mientras tanto los nodos que cachearon la versión vieja siguen respondiendo con ella. Para ese caso conviene un directorio con dueño único, no una DHT.

Conclusión

Kademlia resolvió en 2002 un problema que otras DHT de la época, como Chord y Pastry, atacaban con estructuras más rígidas: usar la misma operación XOR tanto para medir distancia como para enrutar, sin coordinador central. Dos de las redes P2P más usadas del mundo, BitTorrent e IPFS, siguen corriendo sobre esa idea dos décadas después.

📖 Versión extendida con más detalle: https://elsolitario.org/2026/08/31/kademlia-tabla-hash-distribuida-dht/?utm_source=telegraph&utm_medium=instant_view&utm_campaign=programacion