0

I am trying to implement a Kademlia distributed hash table in rust and I am wondering if there is a mistake with the way im implementing find_node_bucket_index in the routing table. Correct me if im wrong, but the way that I understood how nodes are placed in the routing table is:

  1. you get the distance of the two nodes using the xor metric (distance function below).
  2. then do the xor for the distance found and the node id using the same distance function.
  3. Then, you find the prefix length of the matching bits between the node Id and the distance using the result of step 2.

Hopefully that made sense, if not, here is the code:

distance function:

    fn distance_from(&self, b: &Self) -> [u8; GUID_LEN] {
        let mut res = [0; GUID_LEN];
        for (i, val) in self.0.iter().enumerate() {
            res[i] = val ^ b.0[i]
        }

        res
    }

find bucket index function:

    pub fn find_index(id: &GUID, node_id: &GUID) -> usize {
        let dist = node_id.distance_from(id);
        let diff = dist.distance_from(&node_id.0);

        for i in 0..GUID_LEN {
            for j in (0..8).rev() {
                let bit = diff[i] & (1 << j);
                if bit != 0 {
                    return 8 * i + j;
                }
            }
        }

        GUID_LEN * 8 - 1
    }
Nawaf
  • 87
  • 1
  • 2
  • 6
  • What's the problem? Does your code fail to compile? → add the full error message. Does your code compile, but crash when run? → add any output you get when running, plus indications of how far the code gets before crashing. Does your code run but give incorrect output? → add a sample of input, expected output and the output you get instead. – Jmb May 16 '22 at 09:23
  • 1
    Note that the actual kademlia routing table [is a tree](https://stackoverflow.com/a/51161732/1362755) without fixed indices, the index-baed approach was used for a theoretical sketch from an earlier version of the paper. – the8472 May 16 '22 at 11:00
  • rust-libp2p maintainer here. In case this is rust-libp2p specific, best to open an issue on the GitHub repository. – mxinden May 16 '22 at 12:58
  • @the8472 thanks for letting me know. I saw many implementations in rust on GitHub using the list approach so I thought I'd try to use that. However, I'll definitely try to implement the tree based approach. I'm also wondering what are the differences between the two approaches? – Nawaf May 17 '22 at 03:27
  • 1
    I think the question covered that to some extent? If not it certainly should be a separate question, comments aren't the right format for that. – the8472 May 17 '22 at 12:34

0 Answers0