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

  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.

Slide05

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

Screen-Shot-2019-02-06-at-5.49.05-PM

EtherWorld's collection of Good Read on Blockchain & Cryptocurrency.

____________________________________________________________________________________________________

Follow us at Twitter, Facebook, Googe+, Medium and Steemit.

For weekly round up on Ethereum and other blockchain news, technology and projects, subscribe EtherWorld's Blockchain Weekly .

____________________________________________________________________________________________________

Subscribe to EtherWorld.co