1

I'm new in P2P networking and currently I try to understand some basic things specified by Kademlia papers. The main thing that I cannot understand is Kademlia distance metric. All papers define the distance as XOR of two IDs. The ID size is 160 bits, so the result is also has 160 bits. The question: what is a convenient way to represent this distance as integer? Some implementations, that I checked, use the following: distance = 160 - prefix length (where prefix length is number of leading zeros). Is it correct approach?

bw_dev
  • 775
  • 1
  • 7
  • 17
  • It is an integer already (a 160 bit integer). Are you trying to fit 160 bit number into an integer as defined by a particular programming language? – David Soroko Feb 03 '18 at 21:42
  • Yes (I write in java). Since distance is used as index of k-bucket – bw_dev Feb 03 '18 at 22:06
  • Well, unless you know something about those IDs , e.g they have a common prefix/suffix , or some other structure that will allow you to "compress" them, there is no way to fit arbitrary 160 bit number into 32 bits – David Soroko Feb 03 '18 at 22:18

1 Answers1

1

Some implementations, that I checked, use the following: distance = 160 - prefix length (where prefix length is number of leading zeros). Is it correct approach?

That approach is based on an early revision of the kademlia paper and is insufficient to implement some of the later chapters of the final paper.

A full-fledged implementation should use a tree-like routing table that orders buckets by their absolute position in the keyspace which can be resized when bucket splitting happens.

The ID size is 160 bits, so the result is also has 160 bits. The question: what is a convenient way to represent this distance as integer?

The distance metrics are 160bit integers. You can use a big-integer class or roll your own based on arrays. To get shared prefix bit counts you just have to count the leading zeroes, which scale logarithmically with the network size and should normally fit in much smaller integers once you're done.

the8472
  • 40,999
  • 5
  • 70
  • 122