XOR-trie based routing table

[petar]

Implement RT using XOR tries (from github.com/libp2p/go-libp2p-xor). Wins:

• Allows for more flexible changes in RT policies (e.g. different bucket sizes)
• Simplifies reasoning about the RT
• Simplifies parity with other language implementations (they just need to implement the XOR tries)

[aarshkshah1992]

@petar Please do post some slides explaining this when you get the time.

[aarshkshah1992]

Here's a comment by @Stebalien explaining how to visualize a Routing Table as a binary Tree for a given local node. Use the image from Kad paper(though it visualizes the whole network and not the Routing Table for a peer, but the idea is the same) for reference.

"As far as i know, It will be a binary tree based on the xor distance between the local peer and arbitrary target keys. The local peer will be all the way on the left at 000000... Then, starting from the root, traversing down to the left towards the local peer, each branch to the right will represent a bucket. The peers on the first branch will have no bits in common, the peers on the second branch will have one bit in common, etc."

[petar]

Here's some slides, mostly saying the same thing: https://docs.google.com/presentation/d/1CN4hh2TtmK8YZN0i3iCtbor3fnnixdz9Cw0wASh6HVw/edit?usp=sharing

[aarshkshah1992]

@Stebalien What's the priority of this ?

Would it be fair to say that Accelerated Lookups depends on this ?

[Stebalien]

Yes, accelerated lookups depends on this.