Кадемлия

Kademlia — это распределенная хеш-таблица для децентрализованных одноранговых компьютерных сетей, разработанная Петром Маймунковым и Дэвидом Мазьером в 2002 году. Он определяет структуру сети и обмен информацией посредством поиска узлов . Узлы Kademlia общаются между собой с помощью UDP . Виртуальная или оверлейная сеть формируется узлами-участниками. Каждый узел идентифицируется номером или идентификатором узла . Идентификатор узла служит не только для идентификации: алгоритм Kademlia использует идентификатор узла файлов для поиска значений (обычно хэшей или ключевых слов).

Чтобы найти значение, связанное с данным ключом, алгоритм исследует сеть в несколько этапов. На каждом шаге будут найдены узлы, находящиеся ближе к ключу, пока контактный узел не вернет значение или пока не будут найдены более близкие узлы. Это очень эффективно: как и многие другие DHT s, только контакты Kademlia $O(\log n)$ узлов во время поиска из общего числа $n$ узлы в системе.

Дополнительные преимущества заключаются, в частности, в децентрализованной структуре, которая повышает устойчивость к атакам типа «отказ в обслуживании» . Даже если целый набор узлов будет затоплен, это окажет ограниченное влияние на доступность сети, поскольку сеть восстановится сама, сплетая сеть вокруг этих «дыр».

Реализация Kademlia в I2P модифицирована для смягчения уязвимостей Kademlia, таких как атаки Сивиллы .

Детали системы

Одноранговые сети по своей конструкции состоят из узлов. Протоколы, которые эти узлы используют для связи и поиска информации, со временем стали более эффективными. Одноранговые сети обмена файлами первого поколения, такие как Napster , полагались на центральную базу данных для координации поиска в сети. Одноранговые сети второго поколения, такие как Gnutella , использовали лавинную рассылку для поиска файлов, выполняя поиск в каждом узле сети. Одноранговые сети третьего поколения, такие как Bittorrent , используют распределенные хэш-таблицы для поиска файлов в сети. Распределенные хеш-таблицы хранят расположение ресурсов по всей сети.

Кадемлия использует расчет «расстояния» между двумя узлами. Это расстояние вычисляется как исключающее ИЛИ (XOR) двух идентификаторов узла, при этом результат принимается как целое число без знака . Ключи и идентификаторы узлов имеют одинаковый формат и длину, поэтому расстояние между ними можно рассчитать одинаково. Идентификатор узла обычно представляет собой большое случайное число, которое выбирается с целью сделать его уникальным для конкретного узла (см. UUID ). Может случиться и действительно случается, что географически удаленные узлы – например, из Германии и Австралии – могут быть «соседями», если они выбрали одинаковые случайные идентификаторы узлов.

XOR был выбран потому, что он действует как функция расстояния между всеми идентификаторами узлов. Конкретно:

• расстояние между узлом и самим собой равно нулю
• он симметричен: рассчитанные «расстояния» от А до Б и от Б до А одинаковы
• отсюда следует неравенство треугольника : если A, B и C являются вершинами (точками) треугольника, то расстояние от A до B короче (или равно) суммы как расстояния от A до C, так и расстояния от С к Б.

Этих трех условий достаточно, чтобы гарантировать, что XOR уловит все основные и важные особенности «реальной» функции расстояния, будучи при этом дешевым и простым в расчете.

Каждая итерация поиска Kademlia приближается к цели на один шаг. Базовый , что означает , алгоритм поиска Kademlia имеет сложность O(log ₂ (n)) что для сети с ${\textstyle 2^{n}}$ узлов это займет не более $n$ шаги, чтобы найти этот узел.

Таблицы маршрутизации фиксированного размера

Этот раздел упрощен и теперь использует один бит ; см . в разделе #Ускоренный поиск. дополнительную информацию о реальных таблицах маршрутизации

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

Таблицы маршрутизации Kademlia состоят из списка для каждого бита идентификатора узла (например, если идентификатор узла состоит из 128 бит, узел будет хранить 128 таких списков .) Каждая запись в списке содержит необходимые данные для поиска другого узла. Данные в каждой записи списка обычно представляют собой IP-адрес , порт и идентификатор другого узла. Каждый список соответствует определенному расстоянию от узла. Узлы, которые могут войти в n ^й список должен иметь другое n ^й бит из идентификатора узла; первые n-1 бит идентификатора кандидата должны совпадать с битами идентификатора узла. Это означает, что заполнить первый список очень легко , поскольку половина узлов сети являются далекими кандидатами. Следующий список может использовать только 1/4 узлов сети (на один бит ближе, чем первый) и т.д.

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

По мере обнаружения узлов в сети они добавляются в списки . Сюда входят операции хранения и поиска и даже помощь другим узлам в поиске ключа. Каждый встреченный узел будет рассматриваться на предмет включения в списки . Следовательно, знания узла о сети очень динамичны. Это обеспечивает постоянное обновление сети и повышает устойчивость к сбоям или атакам.

В литературе Кадемлии списки называются k-ведрами . k — общесистемное число, например 20. Каждый k -ведро представляет собой список, содержащий до k записей внутри; т.е. для сети с k=20 каждый узел будет иметь списки, содержащие до 20 узлов для определенного бита (определенного расстояния от себя).

Поскольку количество возможных узлов для каждого k-корзины быстро уменьшается (потому что будет очень мало узлов, находящихся так близко), k-корзины с младшим битом будут полностью отображать все узлы в этом разделе сети. Поскольку количество возможных идентификаторов намного больше, чем может быть любая популяция узлов, некоторые из k -корзин, соответствующих очень коротким расстояниям, останутся пустыми.

Сетевой раздел для узла 110

Рассмотрим простую сеть справа. Размер сети составляет 2^3 или восемь максимальных ключей и узлов. Участвуют семь узлов; маленькие кружочки внизу. Рассматриваемый узел — шестой узел (двоичный номер 110), выделенный черным цветом. имеется три k-корзины Для каждого узла в этой сети . Ноль, один и два узла (двоичные 000, 001 и 010) являются кандидатами на самый дальний k-корзину . Третий узел (двоичный 011, не показан) не участвует в сети. В средней k-корзине размещаются узлы четыре и пять (двоичные 100 и 101). Наконец, третий k-корзин может содержать только седьмой узел (двоичный номер 111). Каждый из трех k-ведров заключен в серый круг. Если размер k-корзины равен двум, то самая дальняя 2-корзина может содержать только два узла из трех. Например, если у шестого узла есть первый и второй узлы в самом дальнем 2-корзине, ему придется запросить поиск идентификатора узла в этих узлах, чтобы найти местоположение (IP-адрес) нулевого узла. Каждый узел хорошо знает свое окружение и имеет контакт с несколькими удаленными узлами, что может помочь найти другие узлы, находящиеся далеко.

Известно, что узлы, которые долгое время были подключены к сети, вероятно, будут оставаться подключенными еще долгое время в будущем. Из-за такого статистического распределения Кадемлия выбирает узлы с длинным соединением, которые остаются храниться в k-корзинах. Это увеличивает количество известных действительных узлов в какой-то момент в будущем и обеспечивает более стабильную сеть.

Когда k-корзина заполнена и для нее обнаружен новый узел , последний обнаруженный узел в k-корзине подвергается проверке PING. Если обнаруживается, что узел все еще жив, новый узел помещается во вторичный список, замещающий кэш. Кэш замены используется только в том случае, если узел в k-ведре перестает отвечать. Другими словами: новые узлы используются только тогда, когда старые узлы исчезают.

Протокольные сообщения

У Кадемлии четыре послания.

• PING — используется для проверки работоспособности узла.
• STORE — хранит пару (ключ, значение) в одном узле.
• FIND_NODE — Получатель запроса вернет k узлов в своих сегментах, которые являются наиболее близкими к запрошенному ключу.
• FIND_VALUE — То же, что и FIND_NODE, но если получатель запроса имеет запрошенный ключ в своем хранилище, он вернет соответствующее значение.

Каждое сообщение RPC включает случайное значение от инициатора. Это гарантирует, что при получении ответа он будет соответствовать ранее отправленному запросу (см. Magic Cookie ).

Расположение узлов

Поиск узлов может выполняться асинхронно. Количество одновременных поисков обозначается α и обычно составляет три. Узел инициирует запрос FIND_NODE, опрашивая узлы α в своих k-корзинах , которые являются наиболее близкими к желаемому ключу. Когда эти узлы-получатели получат запрос, они просматривают свои k-корзины и возвращают k ближайших узлов к желаемому ключу, который им известен. Запрашивающая сторона обновит список результатов полученными результатами (идентификаторами узлов), сохранив k лучших из них ( k узлов, которые находятся ближе к искомому ключу), которые отвечают на запросы. Затем запрашивающая сторона выберет эти k лучших результатов, выдаст им запрос и повторит этот процесс снова и снова. Поскольку каждый узел лучше знает свое окружение, чем любой другой узел, полученными результатами будут другие узлы, которые каждый раз оказываются все ближе и ближе к искомому ключу. Итерации продолжаются до тех пор, пока не будут возвращены узлы, находящиеся ближе, чем лучшие предыдущие результаты. Когда итерации прекращаются, лучшими k узлами в списке результатов являются те узлы во всей сети, которые наиболее близки к желаемому ключу.

Информация об узле может быть дополнена временем прохождения туда и обратно или RTT. Эта информация будет использоваться для выбора тайм-аута, конкретного для каждого консультируемого узла. Когда время запроса истекает, может быть инициирован другой запрос, никогда не превосходящий одновременно α-запросы.

Поиск ресурсов

Информация находится путем сопоставления ее с ключом. . хэш Для карты обычно используется Узлы хранилища будут иметь информацию из предыдущего сообщения STORE. Поиск значения выполняется по той же процедуре, что и поиск ближайших к ключу узлов, за исключением того, что поиск завершается, когда узел имеет запрошенное значение в своем хранилище и возвращает это значение.

Значения хранятся в нескольких узлах (из них k), что позволяет узлам приходить и уходить, сохраняя при этом значение, доступное в каком-то узле. Периодически узел, хранящий значение, исследует сеть, чтобы найти k узлов, близких к значению ключа, и реплицировать в них это значение. Это компенсирует исчезнувшие узлы.

Кроме того, для популярных значений, которые могут иметь много запросов, нагрузка на узлы хранилища уменьшается за счет того, что получатель сохраняет это значение в каком-либо узле рядом, но за пределами k ближайших узлов. Это новое хранилище называется кэшем. Таким образом, значение сохраняется все дальше и дальше от ключа, в зависимости от количества запросов. Это позволяет популярным поискам быстрее найти продавца. Поскольку значение возвращается из узлов, находящихся дальше от ключа, это устраняет возможные «горячие точки». Узлы кэширования сбросят значение через определенное время в зависимости от их расстояния от ключа.

Некоторые реализации (например, Kad ) не имеют ни репликации, ни кэширования. Целью этого является быстрое удаление старой информации из системы. Узел, предоставляющий файл, будет периодически обновлять информацию в сети (выполнять сообщения FIND_NODE и STORE). Когда все узлы, имеющие файл, перейдут в автономный режим, никто не будет обновлять его значения (источники и ключевые слова), и информация в конечном итоге исчезнет из сети.

Присоединение к сети

Узел, который хочет присоединиться к сети, должен сначала пройти процесс начальной загрузки . На этом этапе присоединяющемуся узлу необходимо знать IP-адрес и порт другого узла — узла начальной загрузки (полученного от пользователя или из сохраненного списка), — который уже участвует в сети Kademlia. Если присоединяющийся узел еще не участвовал в сети, он вычисляет случайный идентификационный номер, который, поскольку он является очень большим случайным числом, весьма вероятно, что еще не был назначен какому-либо другому узлу. Он использует этот идентификатор до выхода из сети.

Присоединяющийся узел вставляет узел начальной загрузки в один из своих k-корзин . Затем присоединяющийся узел выполняет поиск узла по своему идентификатору по узлу начальной загрузки (единственному известному ему узлу). «Самопоиск» заполнит k-корзины присоединяющегося узла заполнит других узлов новым идентификатором узла, а k-корзины узлами на пути между ним и узлом начальной загрузки. После этого соединительный узел обновляет все k-корзины, расположенные дальше, чем k-корзина, в которую попадает узел начальной загрузки. Это обновление представляет собой просто поиск случайного ключа, находящегося в пределах этого диапазона k-корзины .

Изначально узлы имеют один k-bucket . Когда k-ведро заполнится, его можно разделить. Разделение происходит, если диапазон узлов в k-корзине охватывает собственный идентификатор узла (значения слева и справа в двоичном дереве). Кадемлия ослабляет даже это правило для одного «ближайшего узла» k-bucket , потому что обычно один единственный сегмент будет соответствовать расстоянию, на котором находятся все узлы, ближайшие к этому узлу, они могут быть больше k , и мы этого хотим. знать их всех. Может оказаться, что рядом с узлом существует сильно несбалансированное двоичное поддерево. Если k равно 20, имеется более 21 узла с префиксом «xxx0011.....» и новый узел — «xxx0000 11001 », новый узел может содержать несколько k-корзин для остальных 21+ узлов. Это гарантирует, что сеть знает обо всех узлах в ближайшем регионе.

Ускоренный поиск

Кадемлия использует XOR метрику для определения расстояния. Два идентификатора узла или идентификатор узла и ключ объединяются с помощью операции XOR, и результатом становится расстояние между ними. Для каждого бита функция XOR возвращает ноль, если два бита равны, и единицу, если два бита различны. Расстояния в метрике XOR удовлетворяют неравенству треугольника : если A, B и C являются вершинами (точками) треугольника, то расстояние от A до B короче (или равно) суммы расстояний от A до C и от С до Б.

Метрика XOR позволяет Kademlia расширять таблицы маршрутизации за пределы отдельных битов. Группы битов можно размещать в k-корзинах . Группа битов называется префиксом. Для m-битного префикса будет 2 ^м -1 тыс. ведер . Отсутствующий k-бакет является дальнейшим расширением дерева маршрутизации, которое содержит идентификатор узла. Префикс m-бит уменьшает максимальное количество поисков с log ₂ n до log _{2. ^м} н . Это максимальные значения, а среднее значение будет намного меньше, что увеличивает вероятность найти узел в k-корзине , который имеет больше битов, чем просто префикс с целевым ключом.

Узлы могут использовать смеси префиксов в своей таблице маршрутизации, например сеть Kad, используемая eMule . Сеть Kademlia может даже быть неоднородной в реализации таблицы маршрутизации за счет усложнения анализа запросов.

Академическое значение

Хотя метрика XOR не нужна для понимания Kademlia, она имеет решающее значение для анализа протокола. Арифметика XOR образует абелеву группу, позволяющую закрытый анализ. Другие протоколы и алгоритмы DHT требуют моделирования или сложного формального анализа для прогнозирования поведения и правильности сети. Использование групп битов в качестве информации маршрутизации также упрощает алгоритмы.

Математический анализ алгоритма

Для анализа алгоритма рассмотрим сеть Кадемлии, состоящую из $n$ узлы с идентификаторами $x_{1},\ldots ,x_{n}$, каждая из которых представляет собой строку длины $d$ состоящее только из единиц и нулей. Его можно смоделировать как дерево , в котором каждый лист представляет собой узел, а помеченный путь от корня до листа представляет его идентификатор. Для узла $x\in \{x_{1},\ldots ,x_{n}\}$, позволять ${\mathcal {D}}_{i}(x)$ быть набором узлов (идентификаторов), которые имеют общий префикс с $x$ длины $d-i$. Затем заполнив $i$-е ведро $x$ можно смоделировать как добавление указателей из листа $x$ к $k$ листья (ID), выбранные равномерно случайным образом из ${\mathcal {D}}_{i}(x)$. Таким образом, маршрутизацию можно рассматривать как переход между листьями вдоль этих указателей, так что каждый шаг максимально приближается к целевому идентификатору, т. е. жадным способом.

Позволять $T_{xy}$ количество прыжков, необходимое, чтобы сойти с листа $x$ к целевому идентификатору $y$.Предполагая, что $x_{1},\ldots ,x_{n}$ выбираются детерминированно из $\{0,1\}^{d}$,было доказано, что

$\sup _{x_{1},\ldots ,x_{n}}\,\sup _{x\in \{x_{1},\ldots ,x_{n}\}}\,\sup _{y\in \{0,1\}^{d}}\mathbb {E} [T_{xy}]\leq (1+o(1)){\frac {\log n}{H_{k}}},$

где $H_{k}$ это $k$-й номер гармоники . С $H_{k}/\log k\to 1$ как $k\to \infty$, когда $k$ большой $\mathbb {E} T_{xy}$ ограничено сверху примерно $\log _{k}n$, однако идентификаторы и цель выбраны. Это подтверждает интуитивное предположение, что только в Кадемлии $O(\log n)$ узлы связываются при поиске целевого узла.

Чтобы приблизить модель к реальным сетям Кадемлии, $x_{1},\ldots ,x_{n}$ также можно считать выбранным равномерно случайным образом без замены из $\{0,1\}^{d}$. Тогда можно доказать, что для всех $x\in \{x_{1},\ldots ,x_{n}\}$ и $y\in \{0,1\}^{d}$,

${\begin{aligned}&T_{xy}{\xrightarrow {p}}{\frac {\log n}{c_{k}}},\\&\mathbb {E} [T_{xy}]\to {\frac {\log n}{c_{k}}},\end{aligned}}$

где $c_{k}$ является постоянной величиной, зависящей только от $k$ с $c_{k}/H_{k}\to 1$ как $k\to \infty$. Таким образом, для $k$ большой, $\mathbb {E} T_{xy}/\log _{k}n$ сходится к постоянному закрытию $1$. Это означает, что количество узлов, с которыми необходимо связаться при поиске целевого узла, на самом деле равно $\Theta (\log n)$ в среднем.

Использование в файлообменных сетях

Kademlia используется в файлообменных сетях. Выполняя поиск по ключевым словам Kademlia, можно найти информацию в сети обмена файлами и загрузить ее.Поскольку не существует центрального экземпляра для хранения индекса существующих файлов, эта задача поровну разделена между всеми клиентами: если узел хочет поделиться файлом, он обрабатывает содержимое файла, вычисляя на основе него число ( хэш ), которое будет идентифицировать этот файл в файлообменной сети. Поскольку хэши файлов и идентификаторы узлов имеют одинаковую длину, клиент может использовать функцию расстояния XOR для поиска нескольких узлов, идентификатор которых близок к хешу, и инструктирует эти узлы хранить IP-адрес издателя способом, определяемым реализацией. Таким образом, узлы с идентификаторами, наиболее близкими к хэшу файла, будут иметь список IP-адресов одноранговых узлов/издателей этого файла, с которых клиент может загрузить файл способом, определяемым реализацией.

Клиентам, желающим загрузить файл от этого издателя, не обязательно знать IP-адрес издателя (издателей может быть много), а только хэш файла. Клиент поиска будет использовать Kademlia для поиска в сети узла, идентификатор которого имеет наименьшее расстояние от хеша файла, а затем получит список источников, хранящийся в этом узле.

Поскольку ключ может соответствовать множеству значений, например, множеству источников одного и того же файла, каждый узел хранения может иметь разную информацию. Затем источники запрашиваются со всех k узлов, близких к ключу, где k — размер сегмента.

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

Поиск по имени файла реализован с использованием ключевых слов . Имя файла делится на составляющие его слова. Каждое из этих ключевых слов хешируется и сохраняется в сети вместе с соответствующим именем файла и хешем файла. Поиск включает в себя выбор одного из ключевых слов, обращение к узлу с идентификатором, ближайшим к этому хешу ключевого слова, и получение списка имен файлов, содержащих это ключевое слово. Поскольку к каждому имени файла в списке прикреплен хэш, выбранный файл можно получить обычным способом.

Реализации

Сети

Kademlia Публичные сети, использующие алгоритм (эти сети несовместимы между собой):

• I2P : анонимный оверлейный сетевой уровень.
• Сеть Kad : изначально разработана сообществом eMule для замены серверной архитектуры сети eDonkey .
• Ethereum : протокол обнаружения узлов в сетевом стеке блокчейна Ethereum основан на слегка модифицированной реализации Kademlia.
• Overnet : с KadC доступна библиотека C для обработки Kademlia. (разработка Overnet прекращена)
• Mainline DHT : DHT для BitTorrent , основанный на реализации алгоритма Kademlia, для торрентов без отслеживания.
• Osiris (все версии): используется для управления распределенным и анонимным веб-порталом.
• Retroshare : децентрализованная коммуникационная платформа F2F с безопасным VOIP, обменом мгновенными сообщениями, передачей файлов и т. д.
• Tox : полностью распределенная платформа для обмена сообщениями, VoIP и видеочата.
• Gnutella DHT: первоначально от LimeWire для расширения протокола Gnutella для поиска альтернативных местоположений файлов, который теперь используется другими клиентами Gnutella.
• IPFS : одноранговая распределенная файловая система на основе libp2p.
• TeleHash : протокол ячеистой сети, который использует Kademlia для разрешения прямых соединений между сторонами.
• iMule: обмена файлами утилита для I2P .
• OpenDHT : библиотека, предоставляющая реализацию Kademlia, используемую Джами и другими.
• GNUnet : альтернативный сетевой стек для создания безопасных, децентрализованных и сохраняющих конфиденциальность распределенных приложений. Использует рандомизированную версию Кадемлии под названием R5N.
• Dat : инструмент для однорангового обмена файлами на основе по протоколу Hypercore.

См. также

• Контентно-адресуемая сеть
• Аккорд (одноранговая сеть)
• Гобелен (DHT)
• Кондитерские изделия (DHT)
• Шнуры

Внешние ссылки

• Проекты Xlattice Kademlia Спецификация и определения.