Kademlia is a distributed hash table for decentralized peer-to-peer computer networks designed by Petar Maymounkov and David Mazières in 2002. It specifies the structure of the network and the exchange of information through node lookups. Kademlia nodes communicate among themselves using UDP. A virtual or overlay network is formed by the participant nodes. Each node is identified by a number or node ID. The node ID serves not only as identification, but the Kademlia algorithm uses the node ID to locate values (usually file hashes or keywords). In order to look up the value associated with a given key, the algorithm explores the network in several steps. Each step will find nodes that are closer to the key until the contacted node returns the value or no more closer nodes are found. This is very efficient: like many other DHTs, Kademlia contacts only log n {\displaystyle \log n} nodes during the search out of a total of n {\displaystyle n} nodes in the system. Further advantages are found particularly in the decentralized structure, which increases the resistance against a denial-of-service attack. Even if a whole set of nodes is flooded, this will have limited effect on network availability, since the network will recover itself by knitting the network around these "holes". I2P's implementation of Kademlia is modified to mitigate Kademlia's vulnerabilities, such as Sybil attacks. According to Petar Maymounkov, Kademlia is named after a mountain peak in Bulgaria and a Turkish word meaning "lucky man".
System details Peer-to-peer networks are made of nodes, by design. The protocols that these nodes use to communicate, and locate information, have become more efficient over time. The first generation peer-to-peer file sharing networks, such as Napster, relied on a central database to co-ordinate lookups on the network. Second generation peer-to-peer networks, such as Gnutella, used flooding to locate files, searching every node on the network. Third generation peer-to-peer networks, such as Bittorrent, use distributed hash tables to look up files in the network. Distributed hash tables store resource locations throughout the network. Kademlia uses a "distance" calculation between two nodes. This distance is computed as the exclusive or (XOR) of the two node IDs, taking the result as an unsigned integer number. Keys and node IDs have the same format and length, so distance can be calculated among them in exactly the same way. The node ID is typically a large random number that is chosen with the goal of being unique for a particular node (see UUID). It can and does happen that geographically far nodes – from Germany and Australia, for instance – can be "neighbors" if they have chosen similar random node IDs. XOR was chosen because it acts as a distance function between all the node IDs. Specifically:
the distance between a node and itself is zero it is symmetric: the "distances" calculated from A to B and from B to A are the same it follows the triangle inequality: given A, B and C are vertices (points) of a triangle, then the distance from A to B is shorter than (or equal to) the sum of both the distance from A to C and the distance from C to B. These three conditions are enough to ensure that XOR captures all of the essential, important features of a "real" distance function, while being cheap and simple to calculate. Each Kademlia search iteration comes one bit closer to the target. A basic Kademlia search algorithm has complexity of O(log2 (n)), that means for network with 2 n {\textstyle 2^{n}} nodes it will take at most n {\displaystyle n} steps to find that node.
Fixed-size routing tables
Fixed-size routing tables were presented in the pre-proceedings version of the original paper and are used in the later version only for some mathematical proofs. An actual Kademlia implementation does not have a fixed-size routing table, but a dynamically sized one. Kademlia routing tables consist of a list for each bit of the node ID (e.g. if a node ID consists of 128 bits, a node will keep 128 such lists.) Every entry in a list holds the necessary data to locate another node. The data in each list entry is typically the IP address, port, and node ID of another node. Every list corresponds to a specific distance from the node. Nodes that can go in the nth list must have a differing nth bit from the node's ID; the first n-1 bits of the candidate ID must match those of the node's ID. This means that it is very easy to populate the first list as 1/2 of the nodes in the network are far away candidates. The next list can use only 1/4 of the nodes in the network (one bit closer than the first), etc. With an ID of 128 bits, every node in the network will classify other nodes in one of 128 different distances, one specific distance per bit. As nodes are encountered on the network, they are added to the lists. This includes store and retrieval operations and even helping other nodes to find a key. Every node encountered will be considered for inclusion in the lists. Therefore, the knowledge that a node has of the network is very dynamic. This keeps the network constantly updated and adds resilience to failures or attacks. In the Kademlia literature, the lists are referred to as k-buckets. k is a system wide number, like 20. Every k-bucket is a list having up to k entries inside; i.e. for a network with k=20, each node will have lists containing up to 20 nodes for a particular bit (a particular distance from itself). Since the possible nodes for each k-bucket decreases quickly (because there will be very few nodes which are that close), the lower bit k-buckets will fully map all nodes in that section of the network. Since the quantity of possible IDs is much larger than any node population can ever be, some of the k-buckets corresponding to very short distances will remain empty.
… excerpt ends here. Continue reading the full article.
