ÐΞ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

______________________________________________________________________

Disclaimer: The information contained on this web page is for education purpose only. Readers are suggested to conduct their own research, review, analyze and verify the content before relying on them.

To publish press releases, project updates and guest posts with us, please email at contact@etherworld.co.