libp2p / js-libp2p

The JavaScript Implementation of libp2p networking stack.
https://libp2p.github.io/js-libp2p/
Apache License 2.0
2.34k stars 446 forks source link

fix: grow routing table trie towards node kad-id #2747

Open achingbrain opened 1 month ago

achingbrain commented 1 month ago

Instead of having a balance trie, grow the routing table towards the current node's kad-id.

This gives a better knowledge of the network as we get closer to our own kad-id.

The previous behaviour can be replicated by setting prefixLength and selfPrefixLength to the same value.

Change checklist

achingbrain commented 1 month ago

Need to verify if this actually makes any difference.

Because we have a prefix-trie, the trie only grows deeper if the kad-ids encountered share growing prefixes. There will be plenty of peers encountered that have xor-closer kad ids to the root node but will be omitted because the shared bytes are not in the prefix.

That is, given the kad id:

000000

All of these are equally xor-distanced, but only the first would be included in the deeper section of the trie due to the shared bit being in the prefix:

011111
101111
110111
111011
111101
111110

Using a prefix is probably good enough to ensure a reasonable starting point for a query for an arbitrary kad-id, but it may not help when trying to discover more of the kad-space local to the node's peer id.