Kademlia

Kademlia é uma tabela hash distribuída para rede de computadores peer-to-peer descentralizada projetada por Petar Maymounkov e David Mazières em 2002.^[1][2] Ela especifica a estrutura da rede e a troca de informações por meio de pesquisas de nó. Os nós Kademlia se comunicam entre si usando UDP. Uma rede virtual ou rede sobreposta é formada pelos nós participantes. Cada nó é identificado por um número ou ID de nó. O ID de nó não serve apenas como identificação, o algoritmo Kademlia usa o ID de nó para localizar valores (geralmente hash de arquivos ou palavras-chave). Na verdade, o ID de nó fornece um mapa direto para hashes de arquivo e esse nó armazena informações sobre onde obter o arquivo ou recurso.

Ao pesquisar algum valor, o algoritmo precisa conhecer a chave associada e explorar a rede em várias etapas. Cada etapa localizará nós que estão mais próximos da chave até que o nó contatado retorne o valor ou nenhum nó mais próximo seja encontrado. Isso é muito eficiente: como muitos outros DHTs, o Kademlia contata apenas nós O(\log(n)) durante a busca em um total de n nós no sistema.

Outras vantagens são encontradas particularmente na estrutura descentralizada, o que aumenta a resistência contra um ataque de negação de serviço. Mesmo que todo um conjunto de nós seja inundado, isso terá um efeito limitado na disponibilidade da rede, uma vez que a rede se recuperará ao tecer a rede em torno desses "buracos".

A implementação do Kademlia pela I2P foi modificada para mitigar vulnerabilidades do Kademlia, como ataques Sybil.^[3]

Detalhes do sistema

A primeira geração de redes de compartilhamento de arquivos ponto-a-ponto, como o Napster, dependia de um banco de dados central para coordenar as pesquisas na rede. Redes ponto-a-ponto de segunda geração, como Gnutella, usavam inundação para localizar arquivos, pesquisando todos os nós da rede. Redes ponto a ponto de terceira geração usam tabelas de hash distribuídas para pesquisar arquivos na rede. Tabelas hash distribuídas armazenam recursos de localizações em toda a rede. Um dos principais critérios para esses protocolos é localizar os nós desejados rapidamente.

Kademlia usa um cálculo de "distância" entre dois nós. Essa distância é calculada como ou exclusivo (XOR) dos dois IDs de nó, tomando o resultado como um inteiro sem sinal. Chaves e IDs de nó têm o mesmo formato e comprimento, então a distância pode ser calculada entre eles exatamente da mesma maneira. O ID de nó é normalmente um grande número aleatório que é escolhido com o objetivo de ser exclusivo para um nó específico (veja UUID). Pode acontecer, e acontece, que nós geograficamente muito distantes - da Alemanha e da Austrália, por exemplo - sejam "vizinhos" se tiverem escolhido IDs de nós aleatórios semelhantes.

O ou exclusivo foi escolhido porque atua como uma função de distância entre todos os IDs de nó. Especificamente:

• a distância entre um nó e ele mesmo é zero;
• é simétrico: as "distâncias" calculadas entre A e B são iguais entre B e A;
• segue a desigualdade triangular: dados A, B e C como vértices (pontos) de um triângulo, então a distância entre A e B é menor que (ou igual a) a soma da distância entre A e C mais a distância entre C e B.

Essas três condições são suficientes para garantir que o ou exclusivo capture todas as características essenciais e importantes de uma função de distância "real", sendo barato e simples de calcular.^[1]

Cada iteração de pesquisa Kademlia chega um pouco mais perto do alvo. Uma rede Kademlia básica com 2ⁿ nós levará apenas n passos (no pior caso) para encontrar esse nó.

Tabelas de roteamento de tamanho fixo

Esta seção é simplificada para usar um único bit; veja a seção pesquisas aceleradas para mais informações sobre as tabelas de roteamento reais.

Tabelas de roteamento de tamanho fixo foram apresentadas na versão de pré-procedimentos do artigo original e são usadas na versão posterior apenas para algumas provas matemáticas. Uma implementação real do Kademlia não tem uma tabela de roteamento de tamanho fixo, mas sim de tamanho dinâmico.

As tabelas de roteamento Kademlia consistem em uma lista para cada bit do ID de nó(por exemplo, se um ID de nó consiste em 128 bits, um nó manterá 128 dessas listas). Uma lista possui muitas entradas. Cada entrada em uma lista contém os dados necessários para localizar outro nó. Os dados em cada entrada da lista são normalmente o endereço IP, porta e ID de nó de outro nó. Cada lista corresponde a uma distância específica do nó. Os nós que podem entrar na n^ésima lista devem ter um n^ésimo bit diferente do ID de nó; os primeiros n-1 bits do ID candidato devem corresponder aos do ID de nó. Isso significa que é muito fácil preencher a primeira lista, já que metade dos nós da rede são candidatos distantes. A próxima lista pode usar apenas um quarto dos nós da rede(um bit mais próximo do que o primeiro), etc.

Com um ID de 128 bits, cada nó da rede classificará outros nós em uma das 128 distâncias diferentes, uma distância específica por bit.

Conforme os nós são encontrados na rede, eles são adicionados às listas. Isso inclui operações de armazenamento e recuperação e até mesmo ajudar outros nós a encontrar uma chave. Cada nó encontrado será considerado para inclusão nas listas. Portanto, o conhecimento que um nó tem da rede é muito dinâmico. Isso mantém a rede constantemente atualizada e adiciona resiliência a falhas ou ataques.

Na literatura Kademlia, as listas são referenciadas como k-buckets. k é um número amplo do sistema, como 20. Todo k-bucket é uma lista contendo até k entradas dentro; ou seja, para uma rede com k = 20, cada nó terá listas contendo até 20 nós para um determinado bit (uma distância particular de si mesmo).

Uma vez que os nós possíveis para cada k-bucket diminuem rapidamente (porque haverá muito poucos nós que estão tão próximos), o bit inferior k-buckets mapeará totalmente todos os nós nessa seção da rede . Visto que a quantidade de IDs possíveis é muito maior do que qualquer população de nós pode ser, alguns dos k-buckets correspondentes a distâncias muito curtas permanecerão vazios.

Partição de rede para o nó 110

Considere a rede simples à direita. O tamanho da rede é 2^3 ou oito chaves e nós no máximo. Existem sete nós participantes; os pequenos círculos na parte inferior. O nó em consideração é o nó seis(binário 110) em preto. Existem três k-buckets para cada nó nesta rede. Os nós zero, um e dois(binários 000, 001 e 010) são candidatos para o k-bucket mais distante. O nó três (binário 011, não mostrado) não está participando da rede. No k-bucket intermediário, são colocados os nós quatro e cinco(binários 100 e 101). Finalmente, o terceiro k-bucket pode conter apenas o nó sete(binário 111). Cada um dos três k-buckets estão dentro de um círculo cinza. Se o tamanho do k-bucket era dois, então o 2-bucket mais distante só pode conter dois dos três nós. Por exemplo, se o nó seis tem o nó um e dois no 2-bucket mais distante, ele teria que solicitar uma pesquisa de ID de nó para esses nós para encontrar a localização(endereço IP) do nó zero. Cada nó conhece bem sua vizinhança e tem contato com alguns nós distantes, o que pode ajudar a localizar outros nós distantes.

É sabido que nós que estiveram conectados por um longo tempo em uma rede provavelmente permanecerão conectados por um longo tempo no futuro.^[4][5] Por causa dessa distribuição estatística, o Kademlia seleciona nós com longos tempos conectados para permanecer armazenados nos k-buckets. Isso aumenta o número de nós válidos conhecidos em algum momento no futuro e fornece uma rede mais estável.

Quando um k-bucket está cheio e um novo nó é descoberto para aquele k-bucket, ao nó menos visto recentemente no k-bucket é enviado um PING. Se o nó ainda estiver ativo, o novo nó será colocado em uma lista secundária, um cache de substituição. O cache de substituição é usado apenas se um nó no k-bucket parar de responder. Em outras palavras: novos nós são usados somente quando os nós mais antigos desaparecem.

Mensagens de protocolo

Kademlia tem quatro mensagens.

• PING - usado para verificar se um nó ainda está ativo.
• STORE - Armazena um par (chave, valor) em um nó.
• FIND_NODE - O destinatário da solicitação retornará os k nós em seus próprios depósitos que são os mais próximos da chave solicitada.
• FIND_VALUE - O mesmo que FIND_NODE, mas se o destinatário da solicitação tiver a chave solicitada em seu armazenamento, ele retornará o valor correspondente.

Cada mensagem RPC inclui um valor aleatório do iniciador. Isso garante que, ao ser recebida, a resposta corresponda à solicitação enviada anteriormente. (veja Cookie mágico)

Localizando nós

As pesquisas de nó podem prosseguir de forma assíncrona. A quantidade de pesquisas simultâneas é denotada por α e normalmente é três. Um nó inicia uma solicitação FIND_NODE consultando os nós α em seus próprios k-buckets que são os mais próximos da chave desejada. Quando esses nós destinatários recebem a solicitação, eles verificam em seus k-buckets e retornam, como resposta, os nós k que conhecem mais próximos à chave desejada. O solicitante irá atualizar uma lista de resultados com os resultados (IDs de nó) que ele recebe, mantendo os melhores nós k (os nós k que estão mais próximos da chave pesquisada) que respondem às consultas. Em seguida, o solicitante selecionará esses melhores resultados, emitirá uma solicitação para eles e repetirá esse processo várias vezes. Como cada nó tem um conhecimento melhor de seu ambiente do que qualquer outro nó, os resultados recebidos serão outros nós que estão cada vez mais próximos da chave pesquisada. As iterações continuam até que nenhum nó seja retornado mais próximo do que os melhores resultados anteriores. Quando as iterações param, os melhores nós na lista de resultados são aqueles em toda a rede que estão mais próximos da chave desejada.

As informações de nó podem ser aumentadas com RTT. Essas informações serão utilizadas para escolher um tempo limite específico para cada nó consultado. Quando uma consulta atinge o tempo limite, outra consulta pode ser iniciada, nunca ultrapassando as consultas α ao mesmo tempo.

Localizando recursos

As informações são localizadas mapeando-as para uma chave. Um hash é normalmente usada para o mapa. Os nós de armazenamento terão informações devido a uma mensagem STORE anterior. Localizar um valor segue o mesmo procedimento que localizar os nós mais próximos de uma chave, exceto que a pesquisa termina quando um nó tem o valor solicitado em seu armazenamento e retorna esse valor.

Os valores são armazenados em vários nós (do tipo k) para permitir que os nós entrem e saiam e ainda tenham o valor disponível em algum nó. Periodicamente, um nó que armazena um valor irá explorar a rede para encontrar os nós k que estão próximos ao valor da chave e replicar o valor neles. Isso compensa os nós desaparecidos

Além disso, para valores populares que podem ter muitas solicitações, a carga nos nós do armazenador é diminuída pelo fato de um recuperador armazenar esse valor em algum nó próximo, mas fora dos k mais próximos. Esse novo armazenamento é chamado de cache. Desta forma, o valor é armazenado cada vez mais longe da chave, dependendo da quantidade de solicitações. Isso permite que pesquisas populares encontrem um armazenador mais rapidamente. Como o valor é retornado de nós mais distantes da chave, isso alivia possíveis "pontos críticos". Os nós de cache descartam o valor após um certo tempo, dependendo de sua distância da chave.

Algumas implementações (por exemplo, Kad) não possuem replicação nem cache. O objetivo é remover informações antigas rapidamente do sistema. O nó que está fornecendo o arquivo atualizará periodicamente as informações na rede (com mensagens FIND_NODE e STORE). Quando todos os nós que possuem o arquivo ficarem offline, ninguém estará atualizando seus valores (fontes e palavras-chave) e as informações eventualmente desaparecerão da rede.

Entrando na rede

Um nó que gostaria de se juntar à rede deve primeiro passar por um processo de bootstrap. Nesta fase, o nó que se junta precisa saber o endereço IP e a porta de outro nó - um nó de bootstrap (obtido do usuário ou de uma lista armazenada) - que já está participando da rede Kademlia. Se o nó que se junta ainda não participou da rede, ele calcula um número de ID aleatório que supostamente ainda não foi atribuído a nenhum outro nó. Ele usa esse ID até sair da rede.

O nó de junção insere o nó de bootstrap em um de seus k-buckets. O nó que se junta então executa uma pesquisa de nó de seu próprio ID contra o nó de bootstrap (o único outro nó que ele conhece). A auto-pesquisa preencherá outros nós k-buckets com o novo ID do nó e preencherá os k-buckets do nó de junção com os nós no caminho entre ele e o nó de bootstrap. Depois disso, o nó de junção atualiza todos os k-buckets mais distantes do que o k-bucket do nó de bootstrap. Esta atualização é apenas uma pesquisa de uma chave aleatória que está dentro do intervalo k-bucket.

Inicialmente, os nós têm um k-bucket. Quando o k-bucket fica cheio, pode ser dividido. A divisão ocorre se o intervalo de nós no k-bucket abrange o próprio id do nó (valores à esquerda e à direita em uma árvore binária). Kademlia relaxa até mesmo esta regra para o nó k-bucket mais próximo, porque normalmente um único intervalo corresponderá à distância onde estão todos os nós que estão mais próximos a este nó, eles podem ser mais do que k, e queremos conhecê-los todos. Pode ser que exista uma subárvore binária altamente desequilibrada próxima ao nó. Se k for 20, e houver mais de 21 nós com um prefixo xxx0011... e o novo nó for xxx000011001, o novo nó pode conter vários k-buckets para os outros 21+ nós. Isso é para garantir que a rede conheça todos os nós da região mais próxima.

Pesquisas aceleradas

O Kademlia usa uma métrica XOR para definir a distância. Dois IDs de nó ou um ID de nó e uma chave são armazenados e o resultado é a distância entre eles. Para cada bit, a função XOR retorna zero se os dois bits forem iguais e um se os dois bits forem diferentes. As distâncias métricas XOR mantêm a desigualdade triangular: dados A, B e C como vértices (pontos) de um triângulo, então a distância entre A e B é menor que (ou igual) a soma da distância entre A e C mais a distância entre C e B.

A métrica XOR permite ao Kademlia estender as tabelas de roteamento além de bits únicos. Grupos de bits podem ser colocados em k-buckets. O grupo de bits é denominado prefixo. Para um prefixo m-bit, haverá 2^m-1 k-buckets. O k-bucket ausente é uma extensão adicional da árvore de roteamento que contém o ID do nó. Um prefixo m-bit reduz o número máximo de pesquisas de log₂n para log_2^mn. Esses são os valores máximos. O valor médio será muito menor, aumentando a chance de encontrar um nó em um k-bucket que compartilha mais bits do que apenas o prefixo com a chave de destino.

Os nós podem usar misturas de prefixos em sua tabela de roteamento, como a Kad network usada pelo eMule. A rede Kademlia pode até ser heterogênea em implementações de tabelas de roteamento, ao custo de complicar a análise de pesquisas.

Significância acadêmica

Embora a métrica XOR não seja necessária para entender Kademlia, ela é crítica na análise do protocolo. A aritmética XOR forma um grupo abeliano permitindo uma análise fechada. Outros protocolos e algoritmos DHT requerem simulação ou uma análise formal complicada para prever o comportamento e a correção da rede. Usar grupos de bits como informações de roteamento também simplifica os algoritmos.

Uso em redes de compartilhamento de arquivos

O Kademlia é usado em redes compartilhamento de arquivos. Fazendo buscas por palavras-chave Kademlia, pode-se encontrar informações na rede de compartilhamento de arquivos para que possam ser baixados. Como não há uma instância central para armazenar um índice de arquivos existentes, esta tarefa é dividida igualmente entre todos os clientes: Se um nó deseja compartilhar um arquivo, ele processa o conteúdo do arquivo, calculando a partir dele um número (hash) que identificará esse arquivo na rede de compartilhamento de arquivos. Os hashes e os IDs de nó devem ter o mesmo comprimento. Em seguida, ele procura vários nós cujo ID está próximo ao hash e tem seu próprio endereço IP armazenado nesses nós. Ou seja, ele se publica como uma fonte para este arquivo. Um cliente de pesquisa usará o Kademlia para pesquisar na rede o nó cujo ID tem a menor distância até o hash do arquivo e, em seguida, recuperará a lista de fontes armazenada nesse nó.

Uma vez que uma chave pode corresponder a muitos valores, por exemplo, muitas fontes do mesmo arquivo, cada nó de armazenamento pode ter informações diferentes. Em seguida, as fontes são solicitadas de todos os nós próximos à chave.

O hash do arquivo é geralmente obtido de um link magnético da Internet especialmente formado, encontrado em outro lugar, ou incluído em um arquivo de indexação obtido de outras fontes.

As pesquisas de nomes de arquivos são implementadas usando palavras-chave. O nome do arquivo é dividido em suas palavras constituintes. Cada uma dessas palavras-chave é transformada em hash e armazenada na rede, junto com o nome do arquivo e o hash de arquivo correspondentes. Uma pesquisa envolve a escolha de uma das palavras-chave, contatando o nó com um ID mais próximo a esse hash de palavra-chave e recuperando a lista de nomes de arquivo que contém a palavra-chave. Visto que cada nome de arquivo na lista tem seu hash anexado, o escolhido pode ser obtido da maneira normal.

Implementações

Redes

Redes públicas que usam o algoritmo Kademlia (essas redes são incompatíveis entre si):

• I2P - uma camada anônima de rede sobreposta.^[6]
• Rede Kad - desenvolvida originalmente pela comunidade eMule para substituir a arquitetura baseada em servidor da rede eDonkey2000.
• Ethereum - O protocolo de descoberta de nós na pilha de rede blockchain do Ethereum é baseado em uma implementação ligeiramente modificada do Kademlia.^[7]
• Rede overnet: Com o KadC, uma biblioteca C para lidar com seu Kademlia está disponível. (o desenvolvimento de Overnet foi descontinuado).
• BitTorrent Usa um DHT baseado em uma implementação do algoritmo Kademlia, para torrents sem rastreador.
• Osiris sps (todas as versões): usado para gerenciar portais web distribuídos e anônimos.
• Retroshare - Plataforma de comunicação descentralizada F2F com VOIP seguro, mensagens instantâneas, transferência de arquivos, etc.
• Tox - Uma plataforma de mensagens, VoIP e chat de vídeo totalmente distribuída.
• Gnutella DHT - Originalmente desenvolvido pelo LimeWire^[8][9] para aumentar a capacidade do protocolo Gnutella de encontrar locais de arquivo alternativos, agora em uso por outros clientes gnutella.^[10]
• IPFS - Um sistema de arquivos distribuído ponto a ponto baseado em libp2p.^[11]
• TeleHash é um protocolo de rede em malha que usa o Kademlia para resolver conexões diretas entre as partes.^[12]
• iMule - file sharing utility software for I2P.
• OpenDHT - biblioteca que fornece uma implementação do Kademlia, usada por Jami e outros.
• GNUnet - pilha de rede alternativa para construir aplicativos distribuídos seguros, descentralizados e que preservam a privacidade. Usa uma versão aleatória do Kademlia chamada R5N.^[13]

1. *Kademlia: A Peer-to-peer information system based on the XOR Metric
2. «Papers by David Mazières». www.scs.stanford.edu 
3. «The Network Database - I2P» 
4. Stefan Saroiu, P. Krishna Gummadi and Steven D. Gribble. A Measurement Study of Peer-to-Peer File Sharing Systems. Technical Report UW-CSE-01-06-02, University of Washington, Department of Computer Science and Engineering, July 2001.
5. Daniel Stutzbach and Reza Rejaie. Understanding Churn in Peer-to-Peer Networks Section 5.5 Uptime Predictability, Internet Measurement Conference, Rio de Janeiro, October, 2006.
6. «Intro - I2P». geti2p.net 
7. «GitHub - ethereum/wiki: The Ethereum Wiki.». 25 de março de 2019 – via GitHub 
8. «Slyck News - LimeWire Regains Top Download.com Position». www.slyck.com 
9. «Mojito - LimeWire». wiki.limewire.org. Cópia arquivada em 17 de fevereiro de 2009 
10. «Gtk-gnutella changelog». sourceforge.net. Consultado em 23 de janeiro de 2010. Arquivado do original em 23 de julho de 2011 
11. «IPFS Paper» (PDF) 
12. «#7: Jeremie Miller - TeleHash». Consultado em 12 de março de 2016 
13. «R5N: Randomized Recursive Routing for Restricted-Route Networks» (PDF)