问题标签 [kademlia]

在 Kademlia 论文中，它提到使用XOR解释NodeID为整数的 。让我们假设 my NodeID1isaaf4c61ddcc5e8a2dabede0f3b482cd9aea9434d和 my NodeID2is ab4d8d2a5f480a137067da17100271cd176607a1。将其解释为用于比较NodeID1和的整数的适当方法是NodeID2什么？我会将这些转换为BigInt那XOR两个BigInts 吗？我在一个实现中看到了这一点。我也可以将每个转换NodeID为十进制和XOR那些值吗？

我发现了这个问题，但我试图更好地理解它是如何工作的。

注意：这不是为了实现，我只是想了解整数解释是如何工作的。

我试图更好地掌握 Kademlia 的 XOR 距离度量，所以我编写了一个小的虚拟程序来尝试更好地理解。我在这里也没有使用 160 位数字作为我的密钥，而是使用某个用户标识符的 sha256 哈希。

这是我的异或距离函数。这或多或少是正确的？我对每个字节进行异或运算——将其附加到缓冲区rawBytes并将该字节缓冲区转换为整数。

我的理解是 IPFS 和 Bittorrent Mainline DHT 是建立在分布式哈希表 (Kademlia) 之上的。他们使用文件哈希作为 Kademlia 密钥来查找可能具有此文件的对等点列表。

1-我不明白的是，这是否都是分散的，从不再托管文件内容的 DHT 对等方中删除？

2- 是什么阻止有人在 DHT 内免费存储大量数据？

3-通过为流行文件添加大量无效对等方来防止某人破坏网络。

4- 是什么阻止了不良参与者加入 DHT 环并且不遵循路由协议，从而阻止发现消息到达正确的节点。

我想确认我对 Kademlia DHT 中存储桶的理解。Kademlia 有m 个 k-buckets，其中m是以比特为单位的网络大小，k是每个桶存储的键值对的数量。例如，假设m=4我们可以有2^4节点，即从 0 到 15。

每个节点都有0位匹配、1位匹配、2位匹配等的路由表，这就是m桶。此外，对于每个存储桶，它将存储k代表而不是单个 NodeId。因此，如果我们说 k=2，节点 0101 的路由表将类似于：

我的假设正确吗？

它说：

我们从一些定义开始。对于覆盖距离范围 2i,2i+1 的 k-bucket，将 bucket 的索引定义为 i。将节点的深度 h 定义为 160 - i，其中 i 是非空桶的最小索引。将节点 y 在节点 x 中的桶高度定义为 x 将插入 y 的桶的索引减去 x 的最低有效空桶的索引。由于节点 ID 是随机选择的，因此不太可能出现高度不均匀的分布。因此，对于具有 n 个节点的系统，任何给定节点的高度以压倒性的概率将在 log n 的常数内。此外，与第 k 个最近节点中的 ID 最近的节点的桶高度可能在 log k 的常数内。

我可以理解桶高的定义，但我不知道为什么我们需要这个定义，我不明白该段的最后一句。

更新：我还认为该论文有一个错字：桶高度应该是包含 y 的桶的索引减去 x 的最不重要的“非”空桶的索引。我错了吗？

我正在研究 Mainline DHT，但我不了解其中的细微差别。

此处：https ://www.bittorrent.org/beps/bep_0005.html写道：““距离度量”用于比较两个节点 ID 或节点 ID 和“接近度”的信息哈希。

还写道：“宣布控制查询节点的对等点正在端口上下载种子。announce_peer 有四个参数：“id”包含查询节点的节点 ID，“info_hash”包含种子的信息哈希， “端口”包含作为整数的端口，以及为响应先前的 get_peers 查询而收到的“令牌”。”

因此，例如，我们有一个 ID 为 223456789zxcvbnmasdf 的对等点，其 IP 为 86.23.145.714，端口为：7853 我知道该对等点下载了 2 个带有信息哈希的种子文件：023456789zxcvbnmasdf 和 123456789zxcvbnmasdf。

那么我的 k-bucket 记录应该是什么样子的呢？像这样：

或者 torrent 文件是否应该像 k-buckets 中的“等效”记录（具有重复的 ips 和端口）以及对等点：

我问是因为这不仅仅是实现的细微差别。因为“k”在所有客户端中通常是 20 或其他整数。因此，如果我使用 k-buckets 将 torrent 文件存储为完全权限成员，我将有更少的空间来存储真实的对等数据。

感谢您的回答！

Kademlia 论文指出，节点被分配了随机的 160 位 ID 以及密钥。这是严格的限制吗？如果对我来说足够好，我还能继续使用 128 位密钥空间吗？

在 Kademlia 中，节点存储的所有（键、值）对，除了当前节点本身最初发布的对，都有一个基于当前节点相对于键的位置的过期时间。如果当前节点是离该键最近的 k 个节点，则 (key, value) 对将在其从最初发布时的 24 小时后过期。如果不是 k-closest 节点，则过期时间为

与当前节点和ID最接近key ID的节点之间的节点数成反比

根据 Kademlia 论文。论文还说

这个数字可以从当前节点的桶结构中推断出来。

计算当前节点和给定节点之间的节点似乎有两种截然不同的方法，我不确定哪一种是正确的。我们接下来假设平面数组路由表实现，一个预先分配了 160 个桶的数组。

1. Xlattice Kademlia 设计规范页面说，您应该找到给定节点将落入的存储桶索引 j 并计算存储桶 0..j 中的节点，计算 0..j-1 中的所有节点并仅计算更接近的节点比最终桶 j 中的 key 到当前节点。

2. Bruno Spori 的“Kademlia 分布式哈希表的实现”学期论文（“中间节点数的计算”部分）计算当前节点与给定节点之间的距离，并仅计算距离较小的桶中的节点或等于当前节点和给定节点之间的距离。

这两种方法对我来说似乎都是正确的，但它们完全不同并且产生不同的结果。第一种方法根据当前节点与桶中其他节点之间的距离计算当前节点与给定节点之间的节点。第二种方法根据给定节点与桶中其他节点之间的距离计算当前节点和给定节点之间的节点。

例如，如果当前节点具有 ID 0001_0100（为了示例，我们假设 8 位 id），则只有 8 个存储桶包含具有以下前缀的节点： 0001_0101, 0001_011x, 0001_00xx, 0001_1xxx, 0000_xxxx, 001x_xxxx, 01xx_xxxx, 1xxx_xxxx。假设我们要计算 key 的过期时间1010_0010。当前节点和给定节点之间的距离是 182 ( 0001_0100 xor 1010_0010 = 182)。

使用第一种方法，我们将计算存储桶 0..6 中的所有节点以及存储桶 7 中比给定 ID 更接近当前节点的节点。这是有效的，因为当前节点和所有桶之间的距离是：1、2、4、12、20、52、84、148。您可以通过将我们的 ID 与桶覆盖的范围进行异或来找到它们（我将 x 替换为0 以获得最小但不一定是最接近的 ID 将落入该桶），例如0001_0100 xor 0001_0101 = 1和0001_0100 xor 1000_0000 = 148。直到最后一个节点的所有节点都将具有距离当前节点 <= 182（当前节点和给定 ID 之间的距离）的节点。最后一个桶可以有更远的节点。所以我们计算所有 8 个存储桶中的节点数（部分计算最后一个）。

使用第二种方法，我们计算存储桶 1、2、4、5 和 7 中的所有节点。我们不计算存储桶 0、3、6。这是有效的，因为给定 ID 和存储桶之间的距离为：183、180、 178, 186, 162, 130, 226, 34。您可以通过将给定 ID 与存储桶覆盖的范围异或来找到它们（我将 x 替换为 0 以获得最小但不一定是最接近的 ID）桶），例如1010_0010 xor 0001_0101 = 183和1010_0010 xor 1000_0000 = 34。只有桶 1、2、4、5 和 7 的节点相对于给定 ID 的距离小于 182（当前节点与给定 ID 之间的距离）。所以我们只计算 8 个桶中的 5 个桶中的节点。

计算 8/8 桶和 5/8 桶中的节点是一个很大的区别。哪种方法是正确的？两者似乎都在计算当前节点和给定键之间的节点数，但结果却如此不同。

请注意，xor 度量在这里成立，这里似乎没有任何错误。例如，当前节点与位于最后一个桶的节点之间的距离为0001_0100 xor 1000_0000 = 148。给定节点与最后一个桶中的同一节点之间的距离为1010_0010 xor 1000_0000 = 34。148 xor 34 = 182，所以d(a, b) = d(a, c) xor d(c, b)成立。

第一种方法似乎计算了当前节点知道的距离当前节点小于 182 的所有节点。第二种方法似乎计算了当前节点知道的距离给定节点比 182 更近的所有节点。

我认为第二种方法更正确，因为我们想知道我们是否是给定键的 k-closest 节点。当查找接近给定 ID 的节点时，即FIND_NODERPC，您可以使用类似于第二种方法的过程来识别哪些桶包含最接近给定 ID 的节点，例如在给定的示例中，这些节点将是桶 7、5、4 , 2, 1, 0, 3, 6 - 以最接近的顺序排列。

但是话又说回来，第一种方法也很有意义，因为我们最了解自己的周围环境。我们知道距离当前节点比 182 更近的全部 8 个节点桶，而我们只知道距离给定 key 比 182 更近的大约 5 个节点桶。

我重新设计了使用 k-buckets 的“平面模型”构建的系统（P2P 应用程序）——每个距离都有自己的 k-backet。距离是标识符的长度减去共享前缀的长度 (XOR)。这里一切都很清楚。

现在我们想使用二叉树来保存桶（如上一个 Kadelmia 文档）。当我们“寻找桶”以放入新联系人时，树方法不会“直接”处理距离。这让我感到困惑，因为论文说如果新节点更接近本地然后 K-closest，则应该拆分 k-bucket节点。

我的问题：在这种情况下如何计算距离？它不能是桶的前缀（路径），因为桶可能包含具有不同前缀的节点。

找到K-最近节点的便捷方法是什么？

提前致谢。

我正在对基于 Kademlia 的去中心化网络进行一些研究。在引导一个新节点之后，不是将消息广播到最近的节点，而是可以将消息发送到由其 ID 标识的特定节点吗？（即使这意味着在到达目的地之前将消息中继给多个对等方）。