2

I am currently trying to understand the node discovery protocol in ethereum. I found a few docs, where one of it is: https://github.com/ethereum/devp2p/blob/master/discv4.md

It says, that the distance between node is determined the following way

distance(n₁, n₂) = keccak256(n₁) XOR keccak256(n₂)

where n is the node ID.

Next, the information about neighbors is stored in a routing table consisting of 'k-buckets'.

What I don't understand is the following sentence: 

For each 0 ≤ i < 256, every node keeps a k-bucket for nodes of distance between 2^i and 2^(i+1) from itself.

Let's say we have n1 = 0x80 and n2 = 0xF0. To keep it simple, we don't hash but use just the id. So we get the following distance: d = 0x70. The MSB differs now. In which bucket do I store the information now?

Improve this question

1 Answer 1

Reset to default
1

You must understand that the distant it can be simple interpret as the different of bit. Let's say n1 = 0x80 which in bit is 1000 0000. So the distant for each ith is this routing table:

0th 1000 0000
1th 1000 000x
2th 1000 00xx
3th 1000 0xxx
...

With each row ith contain k peers which contain information about said peer such as their peer address, network address, ... But in the paper it is call k-buckets.

In your example n1 want to communicate with n2 then it will check its routing table and see that the distant is:

7th 1xxx xxxx

then it will send the message to the k-bucket which in this case just n2 so it will send it direct to n2.

For more information i suggest you see this video: https://www.youtube.com/watch?v=w9UObz8o8lY. Or maybe you want to dig deep then this paper: https://pdos.csail.mit.edu/~petar/papers/maymounkov-kademlia-lncs.pdf

Improve this answer
5
  • Thanks for the resources. So far I understand the Kademlia protocol and the table with the distances :) Thanks for illustrating it. You are saying, that in my example, the entry of n2 is in the 7th bucket. So where do we use the keccak function then?
    – Donut
    Mar 23, 2019 at 17:17
  • @Donut sorry i just make it simple and plain by not adding keccak256 but in reality you must do keccak256 and check on the same table the distant. But in general the idea is the same
    – haxerl
    Mar 23, 2019 at 23:44
  • Let me just sum it up to see if I understand your answer: Each Node has a node ID, which is 256 bits long. In order to get the distance between two nodes, each node ID is hashed and the XOR function is applied on the hashes. The result is the distance. The distance represents the bucket, into which the information is put. Do I understand it correct?
    – Donut
    Mar 24, 2019 at 11:36
  • 1
    After summarizing I found the following slides: kth.se/social/upload/516479a5f276545d6a965080/3-kademlia.pdf Actually, the slides helped me to understand it better.
    – Donut
    Mar 24, 2019 at 11:52
  • sorry my answer didnt add keccak in it but you have to do keccak256 then check the table the value distant and see who to send
    – haxerl
    Mar 24, 2019 at 12:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.