search

ethereum / devp2p

Ethereum peer-to-peer networking specifications
984 stars 275 forks source link

discv5: lookup by distance question #115

Closed jannikluhn closed 4 years ago

jannikluhn commented 5 years ago

How does the recursive lookup with distances instead of a target node id work? The spec still describes it with a target node id:

The lookup initiator starts by picking α closest nodes to the target it knows of.

In particular, if the node with ID N has chosen to refresh bucket for log distance log2(d) and sends a FindNode message to node M what log distance do they ask for? I guess the naive way would be log2(abs(distance(N, M) - d)), but I have the feeling that something is off there mathematically.

Also:

If a round of FINDNODE queries fails to return a node any closer than the closest already seen

What does "closer" in the stopping condition refer to now? Closest distance to the center of the bucket we've chosen? Or do we pick a random point in the bucket and use that as the reference?

fjl commented 4 years ago

Related issue where we previously discussed this: #79

fjl commented 4 years ago

I guess the naive way would be log2(abs(distance(N, M) - d)), but I have the feeling that something is off there mathematically.

Your intuition is right and we considered this a lot. We ended up with the current FINDNODE definition because it's easy to implement on the 'server' side (just return some nodes in the given k-bucket) and the response is easy to verify by the caller (just check if all results are at the requested distance from the callee). But it's obviously imperfect. To make lookups converge, the client may need to request nodes at multiple distances.

In Go, I use log2(distance(target, dest)) for FINDNODE calls on node ID dest in a lookup for target. If this doesn't yield enough nodes FINDNODE is repeated for adjacent buckets on the same dest node, i.e. if log2(distance(target, dest)) is 255, it also tries with 256 and 254.

fjl commented 4 years ago

What does "closer" in the stopping condition refer to now? Closest distance to the center of the bucket we've chosen? Or do we pick a random point in the bucket and use that as the reference?

It still means that you should stop when no nodes closer to the ones you already know have been found.