Kademlia

Kademlia is a peer-to-peer distributed hash table (DHT) protocol designed to locate data and peers in decentralized networks. Introduced by Maymounkov and Mazieres in 2002, it uses the XOR distance between node identifiers and keys to determine proximity and routing. Each node in a Kademlia network has a unique 160-bit identifier, and the DHT assigns responsibility for keys to nodes whose IDs are near the key in XOR space.

Nodes maintain a routing table organized into k-buckets. Each bucket covers a range of distances from the node’s own ID and holds up to a fixed number of contact entries for other nodes. A typical bucket size k is around 20. The protocol uses a parallelism parameter, alpha, which controls how many nodes are queried simultaneously during lookups. This design enables efficient routing with logarithmic scaling relative to the number of nodes in the network.

For lookups, a node searches for the k closest nodes to a target key, querying multiple known contacts in parallel. Lookups can be conducted iteratively or recursively, continuing until the closest nodes are found or the value is retrieved. Values can be stored with replication on the k closest nodes to a key to improve durability and availability, and the network maintains information about both keys and associated values.

Kademlia is resilient to churn but relies on the integrity of its routing tables. It faces security considerations such as Sybil attacks, which are mitigated through identity, reputation, or other constraints in specific implementations. The protocol has been widely adopted and adapted in various systems, including BitTorrent’s Mainline DHT and IPFS, which use a Kademlia-inspired DHT to locate resources in a decentralized manner.