Кадемлия - Kademlia

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

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

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

I2P реализация Kademlia изменена, чтобы уменьшить уязвимости Kademlia, такие как Сибил атакует.^[3]

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

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

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

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

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

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

Каждая итерация поиска Kademlia приближается к цели на один бит. А базовый Сеть Kademlia с 2^п узлы займут только п шаги (в худшем случае), чтобы найти этот узел.

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

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

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

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

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

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

Сообщения протокола

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \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}}},}$

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

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

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

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

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

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

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

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

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

Реализации

Сети

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

• I2P - анонимный оверлейная сеть слой.^[8]
• Kad Network - изначально разработан eMule сообщество, чтобы заменить серверную архитектуру eDonkey2000 сеть.
• Ethereum - Протокол обнаружения узлов в сетевом стеке цепочки блоков Ethereum основан на слегка измененной реализации Kademlia.^[9]
• Сеть Overnet: С KadC доступна библиотека C для работы с Kademlia. (разработка Overnet прекращена)
• BitTorrent Использует DHT, основанный на реализации алгоритма Kademlia, для торрентов без трекера.
• Osiris sps (вся версия): используется для управления распределенным и анонимным веб-порталом.
• Retroshare - Децентрализованная коммуникационная платформа F2F с безопасным VOIP, мгновенным обменом сообщениями, передачей файлов и т. Д.
• Tox - Полностью распределенная платформа обмена сообщениями, VoIP и видеочата
• Гнутелла DHT - Первоначально автор LimeWire^[10][11] для расширения протокола Gnutella для поиска альтернативных расположений файлов, которые теперь используются другими клиентами gnutella.^[12]
• IPFS - Одноранговая распределенная файловая система на основе libp2p.^[13]
• TeleHash представляет собой протокол ячеистой сети, который использует Kademlia для разрешения прямых соединений между сторонами.^[14]
• iMule - обмен файлами служебное программное обеспечение за I2P.
• OpenDHT - библиотека, обеспечивающая реализацию Kademlia, используемая Джами и другие.
• GNUnet - альтернативный сетевой стек для создания безопасных, децентрализованных и сохраняющих конфиденциальность распределенных приложений. Использует рандомизированную версию Kademlia под названием R5N^[15]

Смотрите также

• Сеть с адресацией по содержанию
• Аккорд (DHT)
• Гобелен (DHT)
• Кондитерские изделия (DHT)
• Koorde

Рекомендации

1. *Kademlia: одноранговая информационная система, основанная на метрике XOR.
2. «Статьи Давида Мазьера». www.scs.stanford.edu.
3. «Сетевая база данных - I2P».
4. Стефан Сароиу, П. Кришна Гуммади и Стивен Д. Гриббл. Изучение измерений одноранговых систем обмена файлами. Технический отчет UW-CSE-01-06-02, Вашингтонский университет, факультет компьютерных наук и инженерии, июль 2001 г.
5. Даниэль Штутцбах и Реза Реджаи. Понимание оттока в одноранговых сетях Раздел 5.5 «Предсказуемость времени безотказной работы», Конференция по измерениям в Интернете, Рио-де-Жанейро, октябрь 2006 г.
6. Cai, X. S .; Деврое, Л. (2013). «Вероятностный анализ сетей Kademlia». Алгоритмы и вычисления. Конспект лекций по информатике. 8283: 711. arXiv:1309.5866. Дои:10.1007/978-3-642-45030-3_66. ISBN  978-3-642-45029-7.
7. Цай, Син Ши; Деврой, Люк (2015). «Анализ кадемли на случайные идентификаторы». Интернет-математика. 11: 1–16. arXiv:1402.1191. Дои:10.1080/15427951.2015.1051674. ISSN  1542-7951.
8. «Вступление - I2P». geti2p.net.
9. "GitHub - ethereum / wiki: Ethereum Wiki". 25 марта 2019 г. - через GitHub.
10. "Slyck News - LimeWire восстанавливает позицию в топе Download.com". www.slyck.com.
11. «Мохито - LimeWire». wiki.limewire.org. Архивировано из оригинал 17 февраля 2009 г.
12. "Журнал изменений Gtk-gnutella". sourceforge.net. Архивировано из оригинал 23 июля 2011 г.. Получено 23 января 2010.
13. «IPFS Paper» (PDF).
14. "# 7: Джереми Миллер - TeleHash". Получено 2016-03-12.
15. «R5N: рандомизированная рекурсивная маршрутизация для сетей с ограниченным маршрутом» (PDF).

внешняя ссылка

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