Kademlia es una tabla hash distribuida para redes informáticas peer-to-peer descentralizadas diseñada por Petar Maymounkov y David Mazières en 2002. [1] [2] Especifica la estructura de la red y el intercambio de información a través de búsquedas de nodos . Los nodos de Kademlia se comunican entre sí mediante UDP . Una red virtual o superpuesta está formada por los nodos participantes. Cada nodo se identifica mediante un número o ID de nodo . El ID de nodo no solo sirve como identificación, sino que el algoritmo Kademlia usa el ID de nodo para localizar valores (normalmente hashes de archivos o palabras clave).
Para buscar el valor asociado a 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 devuelva el valor o no se encuentren más nodos más cercanos. Esto es muy eficiente: como muchos otros DHT , Kademlia contacta solo nodos durante la búsqueda de un total de nodos en el sistema.
Otras ventajas se encuentran, sobre todo, en la estructura descentralizada, que aumenta la resistencia a 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á tejiendo la red alrededor de estos "agujeros".
La implementación de Kademlia de I2P se modifica para mitigar las vulnerabilidades de Kademlia, como los ataques Sybil . [3]
Las redes peer-to-peer están formadas por nodos, por diseño. Los protocolos que estos nodos utilizan para comunicarse y localizar información se han vuelto más eficientes con el tiempo. Las redes peer-to-peer de intercambio de archivos 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 la inundación 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 las ubicaciones de los recursos en toda la red.
Kademlia utiliza un cálculo de "distancia" entre dos nodos. Esta distancia se calcula como la operación exclusiva o (XOR) de los dos identificadores de nodo, tomando el resultado como un número entero sin signo . Las claves y los identificadores de nodo tienen el mismo formato y longitud, por lo que la distancia entre ellos se puede calcular exactamente de la misma manera. El identificador de nodo es normalmente 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 identificadores de nodo aleatorios similares.
Se eligió XOR porque actúa como una función de distancia entre todos los identificadores de nodo. Específicamente:
Estas tres condiciones son suficientes para garantizar que XOR capture todas las características esenciales e importantes de una función de distancia "real", al mismo tiempo que sea económico y simple de calcular. [1]
Cada iteración de búsqueda de Kademlia se acerca un poco más al objetivo. Un algoritmo de búsqueda básico de Kademlia tiene una complejidad de O(log 2 (n)) , lo que significa que, para una red con nodos, se necesitarán como máximo pasos para encontrar ese nodo.
Las tablas de enrutamiento de tamaño fijo se presentaron en la versión preliminar del artículo original [4] 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 consisten en una lista para cada bit del ID de nodo (por ejemplo, si un ID de nodo consta de 128 bits, un nodo mantendrá 128 listas de este tipo ). Cada entrada de una lista contiene los datos necesarios para localizar otro nodo. Los datos de cada entrada de la 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 lista n -ésima deben tener un bit n -ésimo 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 solo 1/4 de los nodos de la red (un bit más cerca que la primera), etc.
Con una ID de 128 bits, cada nodo de la red clasificará a otros nodos en una de 128 distancias diferentes, una distancia específica por bit.
A medida que se encuentran nodos en la red, se van añadiendo a las listas . Esto incluye operaciones de almacenamiento y recuperación e incluso ayuda a otros nodos a encontrar una clave. Cada nodo encontrado se tendrá en cuenta para su inclusión en las listas . Por tanto, el conocimiento que un nodo tiene de la red es muy dinámico. Esto mantiene la red constantemente actualizada y añade resiliencia a fallos o ataques.
En la literatura de Kademlia, las listas se denominan k-buckets . k es un número de todo el sistema, como 20. Cada k -bucket es una lista que tiene hasta k entradas en su interior; es decir, para una red con k=20, cada nodo tendrá listas que contienen hasta 20 nodos para un bit en particular (una distancia particular de sí mismo).
Dado que los nodos posibles para cada k-bucket disminuyen rápidamente (porque habrá muy pocos nodos que estén tan cerca), los k-buckets de bits más bajos mapearán por completo todos los nodos en esa sección de la red. Dado que la cantidad de posibles identificadores es mucho mayor que la que puede llegar a tener cualquier población de nodos, algunos de los k -buckets correspondientes a distancias muy cortas permanecerán vacíos.
Considere la red simple a la derecha. El tamaño de la red es 2^3 u ocho claves y nodos como máximo. Hay siete nodos participantes; los círculos pequeños en la parte inferior. El nodo en consideración 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 (binario 011, no se muestra) no participa en la red. En el k-bucket del medio , se colocan los nodos cuatro y cinco (binario 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 los nodos uno y dos en el grupo de 2 más alejado, tendría que solicitar una búsqueda de ID de nodo a 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 que pueden 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. [5] [6] Debido a esta distribución estadística, Kademlia selecciona nodos conectados durante mucho tiempo para que permanezcan almacenados en los k-buckets. Esto aumenta la cantidad 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 , se hace ping al nodo menos visto recientemente en el k-bucket . Si se descubre que el nodo sigue activo, el nuevo nodo se coloca en una lista secundaria, un caché de reemplazo. El caché de reemplazo se usa solo si un nodo en el k-bucket deja de responder. En otras palabras: los nuevos nodos se usan solo cuando desaparecen los nodos más antiguos.
Kademlia tiene cuatro mensajes.
Cada mensaje RPC incluye un valor aleatorio del iniciador. Esto garantiza que cuando se reciba la respuesta, esta se corresponde con la solicitud enviada previamente (ver cookie mágica ).
Las búsquedas de nodos pueden realizarse de forma asincrónica. La cantidad de búsquedas simultáneas se denota por α y normalmente es 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 receptores reciben 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, conservando los k mejores (los k nodos que están más cerca de la clave buscada) que responden a las consultas. Luego, el solicitante seleccionará estos k mejores resultados y les emitirá la solicitud, e iterará 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 devuelvan 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 aquellos en toda la red que están más cerca de la clave deseada.
La información de los nodos se puede ampliar con los tiempos de ida y vuelta (RTT). Esta información se utilizará para elegir un tiempo de espera específico para cada nodo consultado. Cuando una consulta expira, se puede iniciar otra consulta, sin superar nunca α consultas al mismo tiempo.
La información se localiza asignándola a una clave. Normalmente se utiliza un hash para el mapa. Los nodos del almacén tendrán información debido a un mensaje STORE anterior. 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 entren y salgan 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 los valores populares que pueden tener muchas solicitudes, la carga en los nodos de almacenamiento se reduce al tener un recuperador que almacena este valor en algún nodo cercano, pero fuera de, los k más cercanos. Este nuevo almacenamiento se llama caché. De esta manera, 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 almacenador 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é eliminará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 información antigua rápidamente del sistema. El nodo que proporciona el archivo actualizará periódicamente la información en la red (ejecutará mensajes FIND_NODE y STORE). Cuando todos los nodos que tienen el archivo se desconecten, nadie actualizará sus valores (fuentes y palabras clave) y la información eventualmente desaparecerá de la red.
Un nodo que desee unirse a la red debe pasar primero 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 está participando 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, por ser un número aleatorio muy grande, es extremadamente probable que no esté asignado a ningún otro nodo. Utiliza este ID hasta que abandona la red.
El nodo que se une inserta el nodo de arranque en uno de sus k-buckets . A continuación, el nodo que se une realiza una búsqueda de nodo de su propia ID en comparación con el nodo de arranque (el único otro nodo que conoce). La "autobúsqueda" llenará los k-buckets de otros nodos con la nueva ID de nodo y llenará los k-buckets del nodo que se une con los nodos en la ruta entre él 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 se encuentra dentro de ese rango de 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 el propio id del nodo (valores a la izquierda y derecha en un árbol binario). Kademlia relaja incluso esta regla para el k-bucket de "nodos más cercanos" , porque normalmente un solo bucket corresponderá a la distancia donde están todos los nodos que están más cerca de este nodo, pueden ser más de k , y queremos que los conozca a todos. Puede resultar que exista un subárbol binario altamente desequilibrado cerca del nodo. Si k es 20, y hay 21+ nodos con un prefijo "xxx0011....." y el nuevo nodo es "xxx0000 11001 ", el nuevo nodo puede contener múltiples k-bucket para los otros 21+ nodos. Esto es para garantizar que la red conozca todos los nodos en la región más cercana.
Kademlia utiliza una métrica XOR para definir la distancia. Se realiza la operación XOR entre dos identificadores de nodo o entre un identificador 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 triangular : 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 que (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. Los grupos de bits se pueden colocar en k-buckets . El grupo de bits se denomina prefijo. Para un prefijo de m bits , habrá 2 m -1 k-buckets . El k-bucket faltante es una extensión adicional del árbol de enrutamiento que contiene el ID del nodo. Un prefijo de m bits reduce la cantidad máxima de búsquedas de log 2 n a log 2 m 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 la clave de destino.
Los nodos pueden utilizar mezclas de prefijos en su tabla de enrutamiento, como la red Kad utilizada por eMule . [ cita requerida ] La red Kademlia podría incluso ser heterogénea en las implementaciones de la tabla de enrutamiento, a expensas de complicar el análisis de las búsquedas.
Si bien la métrica XOR no es necesaria para comprender Kademlia, es fundamental para 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 un 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.
Para analizar el algoritmo, considere una red Kademlia de nodos con IDs , cada uno de los cuales es una cadena de length que consta solo de unos y ceros. Puede modelarse como un trie , en el que cada hoja representa un nodo, y la ruta etiquetada desde la raíz hasta una hoja representa su ID. Para un nodo , sea el conjunto de nodos (IDs) que comparten un prefijo con de length . Luego, llenar el -ésimo contenedor de puede modelarse como agregar punteros desde la hoja a hojas (IDs) elegidas uniformemente al azar de . Por lo tanto, el enrutamiento puede verse como saltar entre las hojas a lo largo de estos punteros de modo que cada paso vaya hacia el ID objetivo tanto como sea posible, es decir, de manera codiciosa.
Sea el número de saltos necesarios para ir desde la hoja hasta un ID de destino . Suponiendo que se eligen de forma determinista a partir de , se ha demostrado que
donde es el -ésimo número armónico . Dado que como , cuando es grande está limitado desde arriba por aproximadamente , sin embargo, se eligen los identificadores y el objetivo. [7] Esto justifica la intuición de que en Kademlia solo se contacta a los nodos al buscar un nodo objetivo.
Para que el modelo se acerque más a las redes Kademlia reales, también se puede suponer que se eligen de manera uniforme al azar sin reemplazo de . Entonces se puede demostrar que para todos y ,
donde es una constante que depende únicamente de con como . Por lo tanto, para valores grandes, converge a una constante cercana a . Esto implica que la cantidad de nodos que se deben contactar para buscar un nodo objetivo es en realidad en promedio. [8]
Kademlia se utiliza en redes de intercambio de 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 hay una instancia central para almacenar un índice de los archivos existentes, esta tarea se divide equitativamente entre todos los clientes: si un nodo desea compartir un archivo, procesa el contenido del archivo, calculando a partir de él un número ( hash ) que identificará este archivo dentro de la red de intercambio de archivos. Dado que los hashes de archivo y los ID de nodo tienen la misma longitud, el cliente puede utilizar la función de distancia XOR para buscar varios nodos cuyo ID sea cercano al hash, e instruye a esos nodos para que almacenen la dirección IP del editor de una manera definida por la implementación. 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 saber la dirección IP del editor (puede haber muchos editores), sino solo el hash del archivo. Un cliente que busque utilizará Kademlia para buscar en la red el nodo cuyo ID tenga la menor distancia con el hash del archivo y luego recuperará la lista de fuentes que se almacena en ese nodo.
Dado que una clave puede corresponder a muchos valores, por ejemplo, muchas fuentes del mismo archivo, cada nodo de almacenamiento puede tener información diferente. Luego, las fuentes se solicitan a todos los k nodos cercanos a la clave, donde k es el tamaño del contenedor.
El hash del archivo generalmente se obtiene a partir de un enlace magnético de Internet especialmente creado 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 archivo se implementan utilizando palabras clave . El nombre de archivo se divide en las palabras que lo constituyen. Cada una de estas palabras clave se codifica 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 al nodo con un ID más cercano a ese hash de palabra clave y recuperar la lista de nombres de archivo 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 manera normal.
Redes públicas que utilizan el algoritmo Kademlia (estas redes son incompatibles entre sí):
![{\displaystyle \sup_{x_{1},\ldots ,x_{n}}\,\sup_{x\in \{x_{1},\ldots ,x_{n}\}}\,\sup_{y\in \{0,1\}^{d}}\mathbb {E} [T_{xy}]\leq (1+o(1)){\frac {\log n}{H_{k}}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/45c858fed0fa63cee23b58ab815118ac52bac762)
![{\displaystyle {\begin{aligned}&T_{xy}{\xrightarrow {p}}{\frac {\log n}{c_{k}}},\\&\mathbb {E} [T_{xy}]\to {\frac {\log n}{c_{k}}},\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8969828abb25d0d320d069d57b607e60dbaec030)
