Understanding Kademlia find_node and adding nodes to the routing table

Question

I'm reading through the Kademlia white paper and trying to implement the routing table piece.

I'm using a 160bit address space and have an array of 160 k-buckets. From what I understand this implementation would store node ids in the buckets by how many leading zeros bits the node id has. I.e. bucket[0] would have node ids with 160 leading zeros (only 1 node) and bucket[159] would have nodes with no leading zeros (50% of the entire address space).

Question Using this implementation, when finding the closest k-nodes to a target nodeId would I just count the leading zeros for the target and return everything in that k-bucket?

Using this implementation I see no place/need to use the XOR that Kademlia is built off of so I don't think my implementation is correct.

Those should be two separate questions, one is conceptual and the other one is how to implement something in C# — the8472, Jun 25 '18 at 05:47
@the8472 Updated to ask the more important conceptual question. — user3953989, Jun 25 '18 at 14:00

score 1 · Accepted Answer · answered Jun 26 '18 at 18:50

First a headsup: the paper you are linking to is the pre-proceedings version only containing the basic sketch without later refinements. The 160-bucket array routing table layout is a simplified approached for the proof of the paper, later revisions introduce a more sophisticated tree-based table.

I.e. bucket[0] would have node ids with 160 leading zeros (only 1 node) and bucket[159] would have nodes with no leading zeros (50% of the entire address space).

Well, you can do it this way, but it's simpler to just count the leading zeros in the xor distance and use that as index. I.e. 0 shared prefix bits = no (0) leading zeroes = buckets[0] = bucket furthest from your own ID.

Question Using this implementation, when finding the closest k-nodes to a target nodeId would I just count the leading zeros for the target and return everything in that k-bucket?

The following is assuming that your're asking how to answer a remote node's queries.

The buckets in the flat routing table layout are organized with respect to your own node ID. When answering queries for some arbitrary target ID then this is not necessarily aligned with the closeness towards that target. So the simplest approach is to just scan all populated buckets in your routing table and calculate the N closest nodes relative to the query's target address and then return those as a response. Avoiding a full scan would involve some arithmetic on the xor metric to find the correct local buckets, but I have only done that for the tree-based layout, not the flat layout.

Understanding Kademlia find_node and adding nodes to the routing table

1 Answers1