ÐΞVp2p Wire Protocol (Kademlia Distributed Hash Table)

This article is an attempt to look into Ethereum ÐΞVp2p protocol. I will break this into multiple parts. In this article I am going to cover Kademlia Distributed Hash Table. Kademlia distributed hash table was designed by Petar Maymounkov and David Mazières in 2002 for decentralized peer-to-peer computer networks. Ethereum ÐΞVp2p uses Kadmelia distributed hash table to maintain a list of peers.

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

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.
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

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 ..

Screenshot-from-2019-01-26-15-43-10

If you find this article helpful, you may show your appreciation by sharing it. Also, you may reach me at hello.bitwarrior@gmail.com with your comments, questions or suggestions of any other topic that you would want to be covered at EtherWorld.co.

Read more articles