Basic DHT bootstrap process

Question

Can someone clarify to me the expression from the mainline DHT specification?

When inserting the first node into its routing table and when starting after that, the node should try to find the closest nodes in DHT for itself. It does this by displaying find_node messages closer and closer to the nodes until it can find them closer.

What does it mean “until he can find closer”?

When my program starts sending find_node messages, it has an empty set of nodes. Each response to find_node returns about 8 dht nodes. My program collects them in a list.

When will my program stop sending node messages?

I think he should stop sending when he receives a set of dht nodes, all of whose elements are in the list of already assembled nodes?

I'm right?

Thanks in advance.

Answer 1

Mainline DHT is an implementation of kademlia, see the document for more information.

From the 8 nodes you received, sort them by node -id proximity to your own identifier, and then send find_node to the top 3 (3 closest to you). Then you get another 8 x more nodes, paste them into your node list, still sorted by how narrow the nodes are to you. Keep sending find_node messages to the top 3 nodes (ignoring the messages you have already sent) until the nodes you return are already in your list. that is, the termination condition is that you sent a message to all 8 nodes closest to you (at the top of the list).

As explained in the article, the XOR distance metric. To calculate how far your node-ID is from another node, you XOR node-IDs. The lower the result, the closer the nodes are to each other.

In real life, you can make this a little more complicated by storing 3 outstanding queries at any given time and temporarily opening more outstanding queries halfway through timeouts.