更好地理解Kademlia的XOR整数度量

Question

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

这是我的xor距离函数，它是否更加正确？我对每个字节进行XOR运算，将其添加到缓冲区“rawBytes”中，并将该字节缓冲区转换为整数。

func XorDistance(node string, otherNode string) uint64 {
    var rawBytes [32]byte
    for i := 0; i < 32; i++ {
        rawBytes[i] = node[i] ^ otherNode[i]
    }
    distance, _ := binary.Uvarint(rawBytes[:])
    return distance
}

- aroooo

Answer 1

这不正确，因为：

• binary.Uvarint() 只能解码64位以内的数字，而你的 rawBytes 有256位
• “varint”编码（在 https://golang.org/src/encoding/binary/varint.go 中注释）基本上与原始字节不兼容。

你需要使用 math/big 包进行此类操作。以下是我修改后代码片段的版本：

func xorDistance(node string, otherNode string) *big.Int {
    var rawBytes [32]byte
    for i := 0; i < 32; i++ {
        rawBytes[i] = node[i] ^ otherNode[i]
    }
    return big.NewInt(0).SetBytes(rawBytes[:])
}

- Chang Qian

---

有趣的是，当两个标识符不同时，UvarInt()实际上返回了一个值。这可能只是使用了截断的前64位吗？ - aroooo

@arooo 我进行了更多的研究，并发现Uvarint()(以及它的有符号版本)使用一种描述在https://developers.google.com/protocol-buffers/docs/encoding中的独特编码(也在`encoding/binary`包的源代码中)，该编码将最不显著位放在前面，并且每个字节只有7个数据位(而不是8个)。因此，在尝试解释字节切片中的任意数据时，它将给出意外的结果。回答已更新。 - Chang Qian

@arooo 另外，建议您添加对 node 和 otherNode 长度的检查，并返回类型为 error 的相应返回值，以避免出现 index out of range 错误。 - Chang Qian