Kademlia

Kademlia – El algoritmo que descentralizó la búsqueda en redes P2P

Kademlia es un protocolo de tabla hash distribuida (DHT) diseñado para redes peer-to-peer (P2P) descentralizadas. Fue creado por Petar Maymounkov y David Mazières en 2002 en la Universidad de Nueva York. A diferencia de sistemas como Napster (centralizado) o Gnutella (inundación de red), Kademlia destaca por su eficiencia para localizar nodos y recursos en redes masivas con un coste logarítmico, lo que lo hace ideal para aplicaciones como redes de intercambio de archivos (eMule, BitTorrent), criptomonedas (Ethereum) o sistemas de archivos distribuidos (IPFS).

¿Qué problema resuelve Kademlia?

En una red descentralizada, no existe un «directorio central» que indique dónde se encuentra un archivo o un usuario. Kademlia resuelve esto organizando a los participantes (nodos) en una estructura lógica. Cada nodo recibe un ID único (generalmente un hash de 128 o 256 bits) y el protocolo define una forma matemática de calcular la «distancia» entre esos IDs.

Cuando un nodo busca algo (un archivo o la ubicación de otro nodo), Kademlia no «pregunta a todos», sino que redirige la consulta hacia los nodos más cercanos al objetivo, convergiendo rápidamente al resultado.

El secreto: La Distancia XOR

El corazón matemático de Kademlia es el uso de la función XOR (OR exclusivo) para medir la distancia lógica entre dos IDs.

• Simetría: distancia(A, B) == distancia(B, A).
• Identidad: distancia(A, A) == 0.
• Desigualdad triangular: La distancia directa es siempre la más corta.

Esta distancia no tiene relación con la ubicación geográfica o la latencia de red, sino que opera sobre el espacio de IDs. Esto permite a la red calcular qué nodos están «cerca» de una clave de búsqueda de forma puramente matemática.

La Estructura: Tablas de Enrutamiento (K-Buckets)

Cada nodo en Kademlia mantiene una tabla de enrutamiento organizada en K-Buckets. Estos son contenedores que almacenan información de otros nodos.

¿Cómo se organizan?
Se basan en la distancia XOR al propio nodo:

• Bucket 0: Almacena nodos que difieren en el primer bit (los más lejanos).
• Bucket 1: Almacena nodos que coinciden en el primer bit pero difieren en el segundo.
• Bucket n: Almacena nodos que coinciden en los primeros n bits.

Parámetros clave:

• k: Número máximo de contactos por bucket (típicamente 20).
• α (alfa): Factor de paralelismo, número de consultas simultáneas (típicamente 3).

Cuando un bucket está lleno y llega un nuevo nodo, el sistema hace un PING al nodo menos visto recientemente (LRU). Si no responde, es reemplazado.

Las 4 Operaciones Esenciales

Kademlia define cuatro RPCs (Llamadas a Procedimiento Remoto) principales que los nodos utilizan para comunicarse:

1. PING: Verifica si un nodo sigue activo.
2. STORE: Solicita a un nodo que almacene un par (clave, valor).
3. FIND_NODE: Dada una clave, el nodo destino devuelve los k contactos en sus tablas más cercanos a esa clave.
4. FIND_VALUE: Funciona como FIND_NODE, pero si el nodo destino posee la clave, devuelve el valor asociado.

¿Cómo se Encuentra un Nodo? (Lookup)

El proceso de búsqueda es iterativo y asíncrono:

1. El nodo iniciador selecciona α (3) nodos de sus k-buckets más cercanos a la clave objetivo.
2. Les envía peticiones FIND_NODE en paralelo.
3. Los nodos contactados devuelven los nodos que ellos conocen aún más cercanos al objetivo.
4. El iniciador actualiza su lista de candidatos con los nuevos nodos recibidos.
5. Repite los pasos 2-4, contactando siempre a los nodos no consultados más cercanos.
6. El bucle termina cuando los k nodos más cercanos encontrados ya han sido consultados.

La convergencia es logarítmica: en una red de n nodos, se necesitan O(log n) saltos.

Almacenamiento y Recuperación de Recursos

Almacenar:
Para guardar un valor asociado a una clave, el nodo realiza una búsqueda para localizar los k nodos más cercanos a esa clave y les envía un RPC STORE.

Recuperar:
Para obtener un valor, se realiza una búsqueda FIND_VALUE. Si un nodo intermedio tiene el valor, lo devuelve directamente, deteniendo la búsqueda.

Ventajas Clave del Algoritmo

• Escalabilidad Masiva: El costo de encontrar un nodo es O(log n). Si la red crece al doble, solo se necesita un paso más.
• Tolerancia a Fallos: La red es autocurativa. Si un nodo falla, otros nodos en el mismo k-bucket pueden suplirlo o se descubren nuevos mediante las búsquedas.
• Resistencia a Ataques: Dificulta los ataques de denegación de servicio (DDoS) al no depender de un punto central.

Implementaciones Famosas en el Mundo Real

Kademlia es la base tecnológica de muchos sistemas descentralizados que usas a diario:

• eMule (Kad Network): La red «Kad» de eMule es una implementación de Kademlia.
• BitTorrent (Mainline DHT): Usa una DHT basada en Kademlia para encontrar pares cuando el tracker está caído.
• Ethereum: Para el descubrimiento de nodos en la red blockchain.
• IPFS: Para localizar peers que contienen contenido específico.
• libp2p: Implementación de referencia utilizada por proyectos como Filecoin e IPFS.

Variantes y Adaptaciones (Forwarding Kademlia)

Algunas implementaciones modernas, como la de Swarm (Ethereum), introducen el concepto de Forwarding Kademlia:

• Iterativo (Original): El iniciador contacta directamente a cada nodo (recibe IPs y vuelve a consultar).
• Forwarding: Cada nodo reenvía la consulta al siguiente nodo más cercano. El resultado viaja de vuelta por la misma cadena, preservando el anonimato del iniciador.

Conclusión

Kademlia revolucionó las redes P2P al demostrar que se podía buscar en una red masiva sin un servidor central de forma rápida (O(log n)), eficiente y robusta. Su elegante uso de la distancia XOR y las tablas de enrutamiento por k-buckets sentó las bases técnicas para el ecosistema descentralizado actual, desde el intercambio de archivos hasta las criptomonedas y la Web3.