Kademlia DHT

Kademlia

https://en.bitcoinwiki.org/wiki/Kademlia

Kademlia (DHT) 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 fact, the node ID provides a direct map to file hashes and that node stores information on where to obtain the file or resource.

When searching for some value, the algorithm needs to know the associated key and 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  nodes during the search out of a total of  nodes in the system.

Further advantages are found particularly in the decentralized structure, which increases the resistance against a denial-of-service attack (DDoS). 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".

https://etherworld.co/2019/01/30/dksvp2p-wire-protocol-kademlia-distributed-hash-table/

Following are some details of Kadmealia DHT which will help you understand the concept better.

1. Every peer/node in Ethereum network has an Id (64 byte wide) which is nothing but a public key derived form a random 256 bit number. Kadmelia normally has 160 bit wide NodeId but for Ethereum network it is 64 byte wide which is width of public key.
2. Every node/peer maintains an instance of Kadmealia DHT which is implemented in form of a binary tree. Peers are stored at leaves. There is notion of distance of one peer from another which is represented as x^y(x XOR Y) where "x" and "y" are Node Ids of the two different peers.

To make it more clear, lets consider the following tree which stores peers with 3 bit wide NodeId.

Now lets say another peer with node id 100(4) ask this node to return 5 closest peer, as per below XOR table it will return peers with Id 4,5,6,7 and 1

Decimal	Binary	XOR distance
4^0	100^000	4
4^1	100^001	5
4^2	100^010	6
4^3	100^011	7
4^4	100^100	0
4^5	100^101	1
4^6	100^110	2
4^7	100^111	3

3. By design it will store more numbers of peers close to own NodeId address space, which is very beautifully explained here, (page number 71-105).

Here is GitHub link, I've checked-in simple code to see things in action. It's creating a node of one byte id with Node Id "00000000" then adding 7 peers with Ids ranging from 1 to 7 to simulate 7 Ethereum network peers and then look for nearest peers respect to peer 4.

const node = new KBucket({
    localNodeId: Buffer.alloc(1,0)
})

And add seven peers..

const peer1 = new Uint8Array([1]) 
const peer2 = new Uint8Array([2])
const peer3 = new Uint8Array([3])
const peer4 = new Uint8Array([4])
const peer5 = new Uint8Array([5])
const peer6 = new Uint8Array([6])
const peer7 = new Uint8Array([7])

// Add all the peers to KDT 
node.add({"id":peer1})
node.add({"id":peer2})
node.add({"id":peer3})
node.add({"id":peer4})
node.add({"id":peer5})
node.add({"id":peer6})
node.add({"id":peer7})

and look for closest nodes ..