Расстояние Kademlia XOR как целое число

В статье Kademlia упоминается использование XOR из NodeID, интерпретируемых как целое число. Давайте представим, что мой NodeID1 — это aaf4c61ddcc5e8a2dabede0f3b482cd9aea9434d, а мой NodeID2 — это ab4d8d2a5f480a137067da17100271cd176607a1. Как правильно интерпретировать это как целое число для сравнения NodeID1 и NodeID2? Могу ли я преобразовать их в BigInt и XOR этих двух BigInt? Я видел это в одной реализации. Могу ли я также просто преобразовать каждое NodeID в десятичное и XOR эти значения?

Я нашел этот вопрос, но я пытаюсь лучше понять как именно это работает.

Примечание. Это не для реализации, я просто пытаюсь понять, как работает целочисленная интерпретация.


encoding p2p xor kademlia
person aroooo    schedule 04.11.2018    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Для базовой реализации kademlia вам нужны только 2-битные арифметические операции с идентификаторами: xor и сравнение. В обоих случаях идентификатор концептуально представляет собой 160-битное целое число без знака с переполнением, то есть арифметику по модулю 2 ^ 160. Его можно разложить в массив размером 20 байт или 5×u32, предполагая правильное преобразование порядка следования байтов в последнем случае. Наиболее распространенным порядком байтов для сетевых протоколов является обратный порядок байтов, поэтому байт 0 будет содержать самые значащие 8 бит из 160.

Затем xor или сравнения могут быть применены к субъединице за субъединицей. т.е. xor - это просто xor для всех байтов, сравнение - это сравнение двоичного массива.

Использование библиотечных функций bigint, вероятно, достаточно для реализации, но не является оптимальным, поскольку они имеют накладные расходы на размер и подписание по сравнению с реализацией необходимого преобразования битов в массивах фиксированного размера.

Для более полной реализации могут также потребоваться некоторые дополнительные арифметические и служебные функции.

Могу ли я также просто преобразовать каждый NodeID в десятичный и XOR этих значений?

Учитывая размер десятичного представления чисел, это не особенно полезно. Для человека-читателя шестнадцатеричные или отдельные биты более полезны, а компьютеры работают с двоичными и практически никогда с десятичными.

person the8472    schedule 05.11.2018