Kademlia

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Kademlia es una tabla hash distribuida para redes informáticas descentralizadas peer-to-peer diseñada por Petar Maymounkov y David Mazières en 2002. Especifica la estructura de la red y el intercambio de información mediante búsquedas de nodos.. Los nodos de Kademlia se comunican entre sí mediante UDP. Los nodos participantes forman una red virtual o superpuesta. Cada nodo se identifica mediante un número o ID de nodo. El ID de nodo sirve no solo como identificación, sino que el algoritmo de Kademlia utiliza el ID de nodo para localizar valores (normalmente hashes de archivos o palabras clave).

Para buscar el valor asociado con una clave dada, el algoritmo explora la red en varios pasos. Cada paso encontrará nodos que están más cerca de la clave hasta que el nodo contactado devuelve el valor o no se encuentran más nodos más cercanos. Esto es muy eficiente: como muchos otros DHTs, Kademlia contacts only ${displaystyle O(log n)}$ nodos durante la búsqueda de un total de ${displaystyle n}$ nodos en el sistema.

Otras ventajas se encuentran especialmente en la estructura descentralizada, que aumenta la resistencia contra un ataque de denegación de servicio. Incluso si se inunda un conjunto completo de nodos, esto tendrá un efecto limitado en la disponibilidad de la red, ya que la red se recuperará entrelazándose alrededor de estos "agujeros".

La implementación de Kademlia por parte de I2P se modifica para mitigar las vulnerabilidades de Kademlia, como los ataques Sybil.

Detalles del sistema

Las redes peer-to-peer están hechas de nodos, por diseño. Los protocolos que utilizan estos nodos para comunicarse y localizar información se han vuelto más eficientes con el tiempo. Las redes de intercambio de archivos peer-to-peer de primera generación, como Napster, dependían de una base de datos central para coordinar las búsquedas en la red. Las redes peer-to-peer de segunda generación, como Gnutella, utilizaban inundaciones para localizar archivos, buscando en cada nodo de la red. Las redes peer-to-peer de tercera generación, como Bittorrent, utilizan tablas hash distribuidas para buscar archivos en la red. Las tablas hash distribuidas almacenan ubicaciones de recursos en toda la red.

Kademlia utiliza una opción de "distancia" cálculo entre dos nodos. Esta distancia se calcula como el exclusivo o (XOR) de los dos ID de nodo, tomando el resultado como un número entero sin signo. Las claves y los ID de nodo tienen el mismo formato y longitud, por lo que la distancia se puede calcular entre ellos exactamente de la misma manera. El ID del nodo suele ser un número aleatorio grande que se elige con el objetivo de que sea único para un nodo en particular (consulte UUID). Puede suceder, y sucede, que nodos geográficamente lejanos (de Alemania y Australia, por ejemplo) puedan ser "vecinos" si han elegido ID de nodos aleatorios similares.

Se eligió

XOR porque actúa como una función de distancia entre todos los ID de nodo. Específicamente:

la distancia entre un nodo y sí mismo es cero
es simétrico: las "distancias" calculadas de A a B y de B a A son las mismas
sigue la desigualdad del triángulo: dado A, B y C son vértices (puntos) de un triángulo, entonces la distancia de A a B es más corta que (o igual a) la suma de la distancia de A a C y la distancia de C a B.

Estas tres condiciones son suficientes para garantizar que XOR capture todas las características esenciales e importantes de un sistema "real". función de distancia, siendo barato y sencillo de calcular.

Cada ruta de búsqueda de Kademlia se acerca un poco más al objetivo. A básicos El algoritmo de búsqueda de Kademlia tiene complejidad $O(log) 2 n)$ , eso significa red con ${textstyle 2^{n}$ nodos que tomará a la mayoría ${displaystyle n}$ pasos para encontrar ese nodo.

Tablas de enrutamiento de tamaño fijo

Las tablas de enrutamiento de tamaño fijo se presentaron en la versión previa al procedimiento del artículo original y se utilizan en la versión posterior solo para algunas pruebas matemáticas. Una implementación real de Kademlia no tiene una tabla de enrutamiento de tamaño fijo, sino una de tamaño dinámico.

Las tablas de enrutamiento de Kademlia constan de una lista para cada bit del ID del nodo (por ejemplo, si un ID de nodo consta de 128 bits, un nodo mantendrá 128 listas de este tipo).) Cada entrada en una lista contiene los datos necesarios para localizar otro nodo. Los datos de cada entrada de lista suelen ser la dirección IP, el puerto y el ID de nodo de otro nodo. Cada lista corresponde a una distancia específica del nodo. Los nodos que pueden ir en la n^ésima lista deben tener un n^ésimo bit diferente del ID del nodo; Los primeros n-1 bits del ID del candidato deben coincidir con los del ID del nodo. Esto significa que es muy fácil completar la primera lista ya que la mitad de los nodos de la red son candidatos lejanos. La siguiente lista puede utilizar sólo 1/4 de los nodos de la red (un poco más cerca que el primero), etc.

Con un ID de 128 bits, cada nodo de la red clasificará otros nodos en una de 128 distancias diferentes, una distancia específica por bit.

A medida que se encuentran nodos en la red, se agregan a las listas. Esto incluye operaciones de almacenamiento y recuperación e incluso ayudar a otros nodos a encontrar una clave. Cada nodo encontrado será considerado para su inclusión en las listas. Por tanto, el conocimiento que tiene un nodo de la red es muy dinámico. Esto mantiene la red constantemente actualizada y agrega resiliencia ante fallas o ataques.

En la literatura de Kademlia, las listas se denominan k-buckets. k es un número para todo el sistema, como 20. Cada k-bucket es una lista que tiene hasta k entradas. adentro; es decir, para una red con k=20, cada nodo tendrá listas que contienen hasta 20 nodos para un bit particular (a una distancia particular de sí mismo).

Dado que los posibles nodos para cada k-bucket disminuyen rápidamente (porque habrá muy pocos nodos que estén tan cerca), el bit inferior k-buckets se reducirá por completo. mapear todos los nodos en esa sección de la red. Dado que la cantidad de ID posibles es mucho mayor de lo que puede ser cualquier población de nodos, algunos de los k-cubos correspondientes a distancias muy cortas permanecerán vacíos.

Considere la red simple de la derecha. El tamaño de la red es 2^3 u ocho claves y nodos como máximo. Hay siete nodos participando; los pequeños círculos en la parte inferior. El nodo considerado es el nodo seis (binario 110) en negro. Hay tres k-buckets para cada nodo en esta red. Los nodos cero, uno y dos (binario 000, 001 y 010) son candidatos para el k-bucket más lejano. El nodo tres (011 binario, no se muestra) no participa en la red. En el k-bucket del medio, se colocan los nodos cuatro y cinco (binarios 100 y 101). Finalmente, el tercer k-bucket solo puede contener el nodo siete (binario 111). Cada uno de los tres k-buckets está encerrado en un círculo gris. Si el tamaño del k-bucket era dos, entonces el 2-bucket más lejano solo puede contener dos de los tres nodos. Por ejemplo, si el nodo seis tiene el nodo uno y dos en los 2 depósitos más lejanos, tendría que solicitar una búsqueda de ID de nodo en estos nodos para encontrar la ubicación (dirección IP) del nodo cero. Cada nodo conoce bien su vecindario y tiene contacto con algunos nodos lejanos, lo que puede ayudar a localizar otros nodos lejanos.

Se sabe que los nodos que han estado conectados durante mucho tiempo en una red probablemente permanecerán conectados durante mucho tiempo en el futuro. Debido a esta distribución estadística, Kademlia selecciona nodos conectados durante mucho tiempo para permanecer almacenados en los k-buckets. Esto aumenta el número de nodos válidos conocidos en algún momento en el futuro y proporciona una red más estable.

Cuando un k-bucket está lleno y se descubre un nuevo nodo para ese k-bucket, el nodo visto menos recientemente en el k-bucket recibe PING. Si se descubre que el nodo todavía está vivo, el nuevo nodo se coloca en una lista secundaria, una caché de reemplazo. La caché de reemplazo se usa solo si un nodo en el k-bucket deja de responder. En otras palabras: los nodos nuevos se utilizan sólo cuando los nodos más antiguos desaparecen.

Mensajes de protocolo

Kademlia tiene cuatro mensajes.

PING — Se utiliza para verificar que un nodo sigue vivo.
STORE — Almacena un par (key, valor) en un nodo.
FIND_NODE — El destinatario de la solicitud devolverá los nudos k en sus propios cubos que son los más cercanos a la clave solicitada.
FIND_VALUE — Igual que FIND_NODE, pero si el destinatario de la solicitud tiene la clave solicitada en su tienda, devolverá el valor correspondiente.

Cada mensaje RPC incluye un valor aleatorio del iniciador. Esto asegura que cuando se reciba la respuesta corresponda a la solicitud enviada anteriormente (ver cookie mágica).

Localización de nodos

Las búsquedas de nodos pueden realizarse de forma asincrónica. La cantidad de búsquedas simultáneas se denota por α y suele ser tres. Un nodo inicia una solicitud FIND_NODE consultando a los nodos α en sus propios k-buckets que son los más cercanos a la clave deseada. Cuando estos nodos destinatarios reciban la solicitud, buscarán en sus k-buckets y devolverán los k nodos más cercanos a la clave deseada que conocen. El solicitante actualizará una lista de resultados con los resultados (ID de nodo) que recibe, manteniendo los k mejores (los k nodos que están más cerca de la clave buscada) que responden a consultas. Luego, el solicitante seleccionará estos k mejores resultados, les emitirá la solicitud y repetirá este proceso una y otra vez. Debido a que cada nodo tiene un mejor conocimiento de su propio entorno que cualquier otro nodo, los resultados recibidos serán otros nodos que están cada vez más cerca de la clave buscada. Las iteraciones continúan hasta que no se devuelven nodos que estén más cerca que los mejores resultados anteriores. Cuando las iteraciones se detienen, los mejores k nodos en la lista de resultados son los de toda la red que están más cerca de la clave deseada.

La información del nodo se puede aumentar con tiempos de ida y vuelta o RTT. Esta información se utilizará para elegir un tiempo de espera específico para cada nodo consultado. Cuando se agota el tiempo de espera de una consulta, se puede iniciar otra consulta, sin superar nunca las consultas α al mismo tiempo.

Localización de recursos

La información se localiza asignándola a una clave. Normalmente se utiliza un hash para el mapa. Los nodos almacenadores tendrán información debido a un mensaje TIENDA previo. La localización de un valor sigue el mismo procedimiento que la localización de los nodos más cercanos a una clave, excepto que la búsqueda finaliza cuando un nodo tiene el valor solicitado en su almacén y devuelve este valor.

Los valores se almacenan en varios nodos (k de ellos) para permitir que los nodos vayan y vengan y aún tengan el valor disponible en algún nodo. Periódicamente, un nodo que almacena un valor explorará la red para encontrar los k nodos que están cerca del valor clave y replicar el valor en ellos. Esto compensa los nodos desaparecidos.

Además, para valores populares que pueden tener muchas solicitudes, la carga en los nodos de almacenamiento se reduce al hacer que un recuperador almacene este valor en algún nodo cerca, pero fuera de, los k más cercanos. Este nuevo almacenamiento se llama caché. De esta forma, el valor se almacena cada vez más lejos de la clave, dependiendo de la cantidad de solicitudes. Esto permite que las búsquedas populares encuentren un almacén más rápidamente. Debido a que el valor se devuelve desde nodos más alejados de la clave, esto alivia los posibles "puntos calientes". Los nodos de almacenamiento en caché reducirán el valor después de un cierto tiempo dependiendo de su distancia de la clave.

Algunas implementaciones (por ejemplo, Kad) no tienen replicación ni almacenamiento en caché. El propósito de esto es eliminar rápidamente la información antigua del sistema. El nodo que proporciona el archivo actualizará periódicamente la información en la red (realice mensajes FIND_NODE y STORE). Cuando todos los nodos que tienen el archivo se desconectan, nadie actualizará sus valores (fuentes y palabras clave) y la información eventualmente desaparecerá de la red.

Unirse a la red

Un nodo que desee unirse a la red primero debe pasar por un proceso de arranque. En esta fase, el nodo que se une necesita conocer la dirección IP y el puerto de otro nodo (un nodo de arranque (obtenido del usuario o de una lista almacenada)) que ya participa en la red Kademlia. Si el nodo que se une aún no ha participado en la red, calcula un número de identificación aleatorio que, al ser un número aleatorio muy grande, es muy probable que no esté asignado a ningún otro nodo. Utiliza este ID hasta salir de la red.

El nodo de unión inserta el nodo de arranque en uno de sus k-buckets. El nodo que se une luego realiza una búsqueda de nodo de su propia ID en el nodo de arranque (el único otro nodo que conoce). La "autobúsqueda" poblará otros nodos' k-buckets con el nuevo ID de nodo y completará los k-buckets del nodo de unión con los nodos en la ruta entre este y el nodo de arranque. Después de esto, el nodo que se une actualiza todos los k-buckets más alejados que el k-bucket en el que se encuentra el nodo de arranque. Esta actualización es solo una búsqueda de una clave aleatoria que es dentro de ese rango k-bucket.

Inicialmente, los nodos tienen un k-bucket. Cuando el k-bucket se llena, se puede dividir. La división ocurre si el rango de nodos en el k-bucket abarca la propia identificación del nodo (valores a la izquierda y a la derecha en un árbol binario). Kademlia relaja incluso esta regla para los "nodos más cercanos" k-bucket, porque normalmente un solo depósito corresponderá a la distancia donde están todos los nodos más cercanos a este nodo, pueden ser más que k, y nosotros Quiero que los conozca todos. Puede resultar que exista un subárbol binario altamente desequilibrado cerca del nodo. Si k es 20 y hay más de 21 nodos con el prefijo "xxx0011....." y el nuevo nodo es "xxx000011001", el nuevo nodo puede contener múltiples k-buckets para los otros 21+ nodos. Esto es para garantizar que la red conozca todos los nodos en la región más cercana.

Búsquedas aceleradas

Kademlia utiliza una métrica XOR para definir la distancia. Se aplica XOR a dos ID de nodo o un ID de nodo y una clave y el resultado es la distancia entre ellos. Para cada bit, la función XOR devuelve cero si los dos bits son iguales y uno si los dos bits son diferentes. Las distancias en la métrica XOR satisfacen la desigualdad del triángulo: dado que A, B y C son vértices (puntos) de un triángulo, entonces la distancia de A a B es más corta (o igual a) la suma de las distancias de A a C y de C a B.

La métrica XOR permite a Kademlia extender las tablas de enrutamiento más allá de los bits individuales. Se pueden colocar grupos de bits en k-buckets. El grupo de bits se denomina prefijo. Para un prefijo m-bit, habrá 2^m-1 k-buckets. El k-bucket que falta es una extensión adicional del árbol de enrutamiento que contiene el ID del nodo. Un prefijo m-bit reduce el número máximo de búsquedas de log₂ n a log_{2^{m< /sup>}} n. Estos son valores máximos y el valor promedio será mucho menor, lo que aumenta la posibilidad de encontrar un nodo en un k-bucket que comparta más bits que solo el prefijo con el objetivo. llave.

Los nodos pueden utilizar combinaciones de prefijos en su tabla de enrutamiento, como la red Kad utilizada por eMule. La red Kademlia podría incluso ser heterogénea en las implementaciones de tablas de enrutamiento, a expensas de complicar el análisis de las búsquedas.

Importancia académica

Si bien la métrica XOR no es necesaria para comprender Kademlia, es fundamental en el análisis del protocolo. La aritmética XOR forma un grupo abeliano que permite un análisis cerrado. Otros protocolos y algoritmos DHT requieren simulación o análisis formal complicado para predecir el comportamiento y la corrección de la red. El uso de grupos de bits como información de enrutamiento también simplifica los algoritmos.

Análisis matemático del algoritmo

Para analizar el algoritmo, considere una red de Kademlia ${displaystyle n}$ nodos con IDs ${displaystyle x_{1},ldotsx_{n}$ , cada uno de los cuales es una cadena de longitud ${displaystyle d}$ que consiste en sólo uno y ceros. Se puede modelar como un trie, en el que cada hoja representa un nodo, y el camino etiquetado de la raíz a una hoja representa su ID. Para un nodo ${displaystyle xin {x_{1},ldotsx_{n}}}}$ , vamos ${fnMicrosoft Sans Serif}$ ser el conjunto de nodos (IDs) que comparten un prefijo con ${displaystyle x}$ de longitud ${displaystyle d-i}$ . Luego llenando el ${displaystyle i}$ -el cubo de ${displaystyle x}$ puede ser modelado como añadir punteros de la hoja ${displaystyle x}$ a ${displaystyle k}$ hojas (IDs) elegidas uniformemente al azar ${fnMicrosoft Sans Serif}$ . Por lo tanto, el enrutamiento se puede ver como saltar entre las hojas a lo largo de estos punteros, de tal manera que cada paso va hacia la identificación de destino tanto como sea posible, es decir, de manera codictiva.

Vamos ${displaystyle T_{xy}$ ser número de saltos necesarios para ir de la hoja ${displaystyle x}$ a un ID objetivo ${displaystyle y}$ . Suponiendo que ${displaystyle x_{1},ldotsx_{n}$ son elegidos deterministamente ${displaystyle {0,1}} {d}}$ , se ha demostrado que

{displaystyle sup _{x_{1},ldotsx_{n},sup _{xin {x_{1},ldotsx_{n}},sup _{yin {0,1}d}mthbbbb} [T_{xy]leq (1+o(1)){frac {log.

Donde ${displaystyle H_{k}$ es ${displaystyle k}$ - el número armónico. Desde ${displaystyle H_{k}/log kto 1}$ como ${displaystyle kto infty}$ , cuando ${displaystyle k}$ es grande ${displaystyle mathbb {E} T_{xy}$ está obligado de arriba por alrededor ${displaystyle log _{k}n}$ , sin embargo los IDs y el objetivo son elegidos. Esto justifica la intuición de que en Kademlia sólo ${displaystyle O(log n)}$ los nodos son contactados en busca de un nodo objetivo.

Para acercar el modelo a las redes reales de Kademlia, ${displaystyle x_{1},ldotsx_{n}$ también se puede suponer que se elija uniformemente al azar sin reemplazarlo ${displaystyle {0,1}} {d}}$ . Entonces se puede probar que para todos ${displaystyle xin {x_{1},ldotsx_{n}}}}$ y ${displaystyle yin {0,1} {d}}$ ,

{displaystyle {begin{aligned} {fnK} {fnMicroc} {fnMicroc} {fnMicroc}} {fnMicroc} {fnMicroc}} {fnMicroc} {fnK}} {f}} {f}} {fnMicroc}} {fnMicroc}}} {f}}} {f} {f}f}}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}fnMicrocfnf}fnf}f}f}f}fnf}f}f}f}f}fnMicrocf}f}fnf}f}f}f}f}f ################## {c_{k}}\\\\\\\\fnMithbb {E} [T_{xy]to {frac {log n}{c_{k}end{aligned}}}

Donde ${displaystyle C_{k}$ es una constante dependiendo sólo de ${displaystyle k}$ con ${displaystyle C_{k}/H_{k}to 1}$ como ${displaystyle kto infty}$ . Así pues, ${displaystyle k}$ grande, ${displaystyle mathbb {E} T_{xy}/log ¿Qué?$ converge a una constante cercanía ${displaystyle 1}$ . Esto implica que el número de nodos necesitan ser contactados en busca de un nodo objetivo es en realidad ${displaystyle Theta (log n)}$ en promedio.

Uso en redes de intercambio de archivos

Kademlia se utiliza en redes para compartir archivos. Al realizar búsquedas de palabras clave en Kademlia, se puede encontrar información en la red de intercambio de archivos para poder descargarla. Dado que no existe una instancia central para almacenar un índice de archivos existentes, esta tarea se divide equitativamente entre todos los clientes: si un nodo quiere compartir un archivo, procesa el contenido del archivo y calcula a partir de él un número (hash) que identificar este archivo dentro de la red de intercambio de archivos. Dado que los hash de archivos y los ID de nodo tienen la misma longitud, el cliente puede usar la función de distancia XOR para buscar varios nodos cuya ID esté cerca del hash e indica a esos nodos que almacenen la dirección IP del editor en una implementación. manera definida. Por lo tanto, los nodos con ID más cercanos al hash del archivo tendrán una lista de direcciones IP de pares/editores de este archivo, desde la cual un cliente puede descargar el archivo de una manera definida por la implementación.

Los clientes que deseen descargar el archivo de este editor no necesitan conocer la dirección IP del editor (puede haber muchos editores), sino sólo el hash del archivo. Un cliente de búsqueda utilizará Kademlia para buscar en la red el nodo cuyo ID tenga la distancia más pequeña al hash del archivo, luego recuperará la lista de fuentes almacenada en ese nodo.

Dado que una clave puede corresponder a muchos valores, p.e. muchas fuentes del mismo archivo, cada nodo de almacenamiento puede tener información diferente. Luego, las fuentes se solicitan de todos los k nodos cercanos a la clave, siendo k el tamaño del depósito.

El hash del archivo generalmente se obtiene a partir de un enlace magnético de Internet especialmente formado que se encuentra en otro lugar, o se incluye dentro de un archivo de indexación obtenido de otras fuentes.

Las búsquedas de nombres de archivos se implementan mediante palabras clave. El nombre del archivo se divide en las palabras que lo constituyen. Cada una de estas palabras clave tiene un hash y se almacena en la red, junto con el nombre de archivo y el hash de archivo correspondientes. Una búsqueda implica elegir una de las palabras clave, contactar el nodo con una ID más cercana al hash de esa palabra clave y recuperar la lista de nombres de archivos que contienen la palabra clave. Dado que cada nombre de archivo en la lista tiene su hash adjunto, el archivo elegido se puede obtener de la forma normal.

Implementaciones

Redes

Redes públicas que utilizan el algoritmo Kademlia (estas redes son incompatibles entre sí):

I2P: una capa de red anónimo.
Red Kad: desarrollada originalmente por la comunidad eMule para reemplazar la arquitectura basada en servidor de la red eDonkey.
Ethereum: el protocolo de descubrimiento de nodos en la pila de red Ethereum blockchain se basa en una implementación ligeramente modificada de Kademlia.
Overnet: Con KadC está disponible una biblioteca C para manejar su Kademlia. (Se suspende el desarrollo de Overnet)
Mainline DHT: un DHT para BitTorrent basado en la implementación del algoritmo Kademlia, para torrentes sin rastreo.
Osiris (toda la versión): utilizado para gestionar portal web distribuido y anónimo.
Retroshare: F2F plataforma de comunicación descentralizada con VOIP seguro, mensajería instantánea, transferencia de archivos, etc.
Tox: una plataforma de mensajería totalmente distribuida, VoIP y video chat
Gnutella DHT: originalmente por LimeWire para aumentar el protocolo Gnutella para encontrar ubicaciones de archivos alternativas, ahora en uso por otros clientes de gnutella.
IPFS: un sistema de archivos distribuido entre pares basado en libp2p.
TeleHash: un protocolo de red de malla que utiliza Kademlia para resolver las conexiones directas entre las partes.
iMule: software de uso compartido de archivos para I2P.
OpenDHT: biblioteca que proporciona una implementación de Kademlia, utilizada por Jami y otros.
GNUnet: pila de red alternativa para construir aplicaciones distribuidas seguras, descentralizadas y de reserva de privacidad. Utiliza la versión aleatorizada de Kademlia llamada R5N.
Dat: una herramienta de intercambio de archivos entre pares basada en el Protocolo Hypercore.

Más resultados...