Лучшее понимание целочисленной метрики XOR Kademlia

Я пытаюсь лучше понять метрику расстояния XOR Kademlia, поэтому я написал небольшую фиктивную программу, чтобы попытаться лучше понять. Я также не использую здесь 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
}

go p2p distributed xor kademlia
person aroooo    schedule 06.11.2018    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Это неправильно, потому что

  • 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[:])
}
person Chang Qian    schedule 06.11.2018
comment
Интересно: функция UvarInt() фактически возвращала значение, когда два идентификатора различались. Вероятно, это было просто использование первых 64 бит, усеченных тогда? - person aroooo; 06.11.2018
comment
@arooo Я провел дополнительное исследование и обнаружил, что Uvarint() (и его подписанный брат) используют уникальную кодировку, описанную в developers.google.com/protocol-buffers/docs/encoding (также в исходном коде пакета encoding/binary), который ставит младшие биты первыми и 7 бит данных (вместо 8) на байт. Таким образом, это даст неожиданные результаты, пытаясь интерпретировать произвольные данные в байтовых срезах. Ответ обновлен. - person Chang Qian; 07.11.2018
comment
@arooo Также рекомендуется добавить проверку длины node и otherNode и соответствующее возвращаемое значение типа error, чтобы избежать паники index out of range. - person Chang Qian; 07.11.2018