Kademlia 最小子树的距离与高度关系

Question

我在看Kademlia的论文，遇到了一个我无法理解的问题。

In a fully-populated binary tree of 160-bit IDs, the magnitude of the distance between two IDs is the height of the smallest subtree containing them both.

d(101,010) = 5 ^ 2 = 7
but Lowest Common Ancestor height is 4:Count from one or 3:Count from zero (root)

这个结果显然是错误的，我一定有问题，那么我该如何解释这句话 我期待您的回复。谢谢你

Kademlia P2P 中的伪可靠广播 系统

Kademlia 反过来将其节点组织成二叉树。 （深入探讨内部机制 Kademlia，请参考[2]。）节点之间的距离为 使用 XOR（异或）函数计算，其中 本质上捕捉了二叉树拓扑的思想。为了 任意节点 A 和 B，它们的距离大小 d(A,B)=AB，例如d 的最高有效非零位是 包含两者的最小子树的高度。

Kademlia：点对点信息系统 基于 XOR 度量

我们接下来注意到，XOR 捕获了我们基于二叉树的系统草图中隐含的距离概念。在 160 位 ID 的完全填充二叉树中， 两个ID之间距离的大小是最小的高度 包含它们的子树。当一棵树没有完全填充时，最接近的 ID x 的叶子是其ID 共享x 的最长公共前缀的叶子。如果 树上有空树枝，可能有不止一片叶子 最长公共前缀。在这种情况下，距离 x 最近的叶子将是最近的叶子 通过翻转 x 中对应于空分支的位来生成 ID x~ 树的。

Answer 1

那句话说的是距离的大小，而不是确切的距离。确切的距离只是两个地址之间的 XOR。

在 101 和 010 的特殊情况下，距离为 111，即最大可能距离，因此除了整个树本身之外，它们不共享公共子树，因此大小为 3 位（假设 3 位密钥空间），这也是最大距离高度。 CIDR 子网划分中的等效项是 /0 掩码，即 0 个共享前缀位。

Answer 2

我最近有同样的问题，上面的答案对我来说不够清楚，我发现这篇博客文章解释了 XOR 和最小子树的高度等之间的关系..

为什么 Kademlia 使用 XOR 作为距离度量

引用帖子：

一个超级方便的属性是，两个键之间的 XOR 输出中的第一个高位告诉您这两个键公共的最小子树的高度。

换句话说。如果 XOR(A,B) = 0010...，第一个高位位于位置 3，这意味着您的路径首先在从根开始的第三个分支处分叉。此属性使 Kademlia 可以有效地利用子树来路由其查询。