o problema
Por volta de 2001 o roteamento distribuído por identificador já estava resolvido no papel. O trabalho de Plaxton mostrou como levar uma busca até o nó responsável por uma chave em um número logarítmico de saltos; Chord e Pastry transformaram aquilo em sistemas peer-to-peer de verdade. O que nenhum deles tratou bem foi o regime em que essas redes de fato rodam: máquinas domésticas que entram e saem o tempo todo, e onde um salto para o nó errado custa um timeout inteiro.
Dois defeitos concretos. Primeiro, a métrica de distância desses sistemas não é simétrica. A distância de A até B não é a distância de B até A, então o nó que recebe uma consulta não aprende nada aproveitável sobre quem a mandou: a tabela de rotas precisa ser mantida por um tráfego de manutenção separado do tráfego útil. Segundo, a tabela é rígida — para cada salto existe exatamente um nó certo. Se ele estiver fora do ar, você descobre por timeout, e não há um segundo candidato equivalente para tentar em paralelo nem para escolher por latência. Chord ainda precisa de um mecanismo à parte, a lista de sucessores, para os últimos saltos.
a ideia
Definir a distância entre dois identificadores de 160 bits como o XOR deles, lido como inteiro sem sinal. É só isso.
Parece truque de implementação e não é. XOR é uma métrica no sentido estrito: d(x,x) = 0, d(x,y) > 0 para x diferente de y, d(x,y) = d(y,x), e vale a desigualdade triangular, que sai de (x⊕y)⊕(y⊕z) = x⊕z somado ao fato de que a+b nunca é menor que a⊕b. Com isso, toda a estrutura de roteamento por prefixo sobre uma árvore binária de IDs continua valendo — e vêm duas propriedades de graça.
A simetria é a que muda o sistema. Como a distância é a mesma nos dois sentidos, o conjunto de nós que consulta você é exatamente o conjunto que você deveria estar guardando na tabela. A informação de configuração se espalha como efeito colateral das buscas.
A segunda é a unidirecionalidade: fixados um ponto e uma distância, existe um único ponto àquela distância. Todas as buscas pela mesma chave convergem para o mesmo caminho, independentemente de onde começaram — o que faz cachear o par no caminho de volta ser útil em vez de ser desperdício.
como funciona
Cada nó tem um ID de 160 bits no mesmo espaço das chaves. Para cada i entre 0 e 159, o nó guarda uma lista de até k triplas (endereço IP, porta UDP, ID) de nós cuja distância a ele está entre 2^i e 2^(i+1). São os k-buckets. k é escolhido de modo que seja improvável que k nós falhem todos dentro de uma mesma hora.
Cada bucket é ordenado por último contato: o menos recentemente visto na cabeça, o mais recente na cauda. Quando chega qualquer mensagem, o nó atualiza o bucket correspondente. Se o remetente já está lá, vai para a cauda. Se não está e há espaço, entra na cauda. Se o bucket está cheio, o nó dá PING no contato mais antigo: se ele responde, o contato novo é descartado; só se ele não responde é que é despejado. Isso inverte a política usual e é deliberado — quanto maior o uptime de um nó, maior a chance de ele continuar no ar. De quebra, um atacante não consegue lavar a tabela de rotas de um nó inundando a rede com identidades novas.
O protocolo tem quatro RPCs sobre UDP: PING, STORE, FIND_NODE e FIND_VALUE. FIND_NODE recebe um ID de 160 bits e devolve as triplas dos k nós mais próximos que o destinatário conhece. FIND_VALUE é igual, exceto que devolve o valor direto se o nó tiver recebido um STORE para aquela chave. Cada mensagem carrega um ID de RPC aleatório que a resposta precisa ecoar, o que dificulta forjar endereço.
A busca é iterativa e paralela. O iniciador pega os nós mais próximos que conhece, dispara α consultas simultâneas, usa o que voltar para escolher os próximos α, e repete até não conseguir mais chegar perto. α é um parâmetro de concorrência do sistema. Como há k candidatos equivalentes a cada passo, um nó morto não trava a busca: as outras consultas em voo já estão andando.
o que isso custou
O próprio paper enquadra α como uma troca explícita: você gasta um fator constante a mais de banda para comprar seleção de salto por menor latência e recuperação de falha sem esperar timeout. Quem opera a rede paga essa banda em toda busca, inclusive nas que teriam funcionado no primeiro chute.
A política de preferir o contato velho tem o outro lado óbvio: um nó novo e saudável pode demorar a entrar nas tabelas alheias enquanto os antigos continuarem respondendo. E ela protege contra inundação de identidades, não contra um nó antigo e hostil — o paper resolve roteamento, não autenticidade de conteúdo.
As garantias são probabilísticas, não determinísticas. A correção depende de haver k nós próximos vivos, o que se sustenta na hipótese de falhas pouco correlacionadas dentro de uma hora. Pares (chave, valor) também não são permanentes: dependem de republicação periódica e expiram sem ela.
Há ainda um caso feio que o paper admite e conserta na mão. Em árvores muito desbalanceadas, um nó pode acabar sem k-bucket para uma região do espaço e nunca aprender os nós que moram lá — perdendo buscas para chaves daquela faixa. A correção é guardar todos os contatos válidos de uma subárvore de tamanho pelo menos k, mesmo que isso obrigue a dividir buckets que não contêm o próprio ID do nó. Funciona, mas é complexidade que a descrição limpa da árvore não sugeria. Na mesma linha, dá para reduzir saltos tratando b bits por vez em vez de um, ao custo de uma tabela de rotas exponencialmente maior em b.
onde isso aparece hoje
Kademlia virou a DHT padrão da internet pública. A DHT mainline do BitTorrent — a que permite torrent sem tracker — é Kademlia, assim como a rede Kad do eMule. O kad-dht do libp2p, usado pelo IPFS, é Kademlia, e tem implementações mantidas em Go e em Rust; se você mexe com libp2p, os k-buckets e o α estão expostos na configuração. A descoberta de nós do Ethereum também é derivada de Kademlia.
O que veio depois foi principalmente endurecimento. Ataques de eclipse e Sybil contra tabelas de roteamento por XOR renderam uma linha inteira de trabalho sobre como restringir a geração de node IDs e como diversificar buckets — problemas que o paper de 2002 não se propôs a resolver, e que aparecem sempre que alguém coloca dinheiro em cima de uma DHT.