Kademlia

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

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

В реализации протокола Kademlia для I2P предусмотрены меры против возможных уязвимостей протокола, в частности — против Sybil-атак^[3].

Пиринговые сети строятся на основе узлов, использующих разные протоколы обмена и поиска информации. Протоколы совершенствовались с поколениями: в первой волне (например, Napster) использовалась центральная база для координации поиска, во второй, например, Gnutella, применялся механизм массовой рассылки, а современные сети наподобие BitTorrent используют распределённые хеш-таблицы. В РХТ расположение ресурсов распределено по всей сети.

В Kademlia «расстояние» между двумя узлами рассчитывается как исключающее ИЛИ их идентификаторов, интерпретируемых как неотрицательные целые числа одинаковой длины. Такой подход позволяет считать узлы с близкими номерами «соседями», даже если они физически далеки друг от друга. Обычно идентификаторы выбираются случайно и с целью максимальной уникальности.

Оператор XOR был выбран как метрический — он обладает необходимыми свойствами «расстояния»: расстояние до самого себя равно нулю, функция симметрична и удовлетворяет неравенству треугольника. Такие свойства делают вычисление расстояния простым и дешёвым^[1].

В каждом шаге поиска Kademlia приближается к цели на 1 бит; базовая сложность поиска составляет ${\displaystyle O(\log _{2}n)}$: для сети с ${\displaystyle 2^{n}}$ узлов потребуется не более ${\displaystyle n}$ шагов.

Первоначальный вариант Kademlia предполагал маршрутные таблицы фиксированного размера, представленные в пре-принт версии статьи^[4]. На практике наиболее распространённые реализации используют динамические таблицы.

Маршрутная таблица состоит из набора списков, по одному на каждый бит идентификатора узла. Каждый список хранит адрес, порт и node ID удалённого узла, причём каждый k-бакет соответствует множеству узлов на определённом расстоянии. В n-ый список помещаются те узлы, чей n-ый бит отличается от n-го бита текущего узла, а предыдущие n-1 бит совпадают. Таким образом, списки для наиболее далёких расстояний наиболее заполнены, а для ближних — могут быть пусты или содержать единичные записи.

Формируя список контактов, узел добавляет обнаруженных соседей при любых операциях. В каждом бакете поддерживается до k (=20) записей. Если новый кандидат претендует на место, а бакет уже заполнен, то его помещают в запасной список — и в основной попадает только при выбытии старого элемента. Такой механизм повышает устойчивость и обновляемость маршрутизации.

В демонстрационной сети размером 2^3 (8 узлов) каждый участник имеет 3 ведра (k-бакета), содержащих адреса опрошенных ранее соседей при разных значениях битов, распределённых по расстояниям.

Замечено, что узлы с большим временем жизни в сети, скорее всего, будут доступны и в будущем^[5][6], поэтому Kademlia по возможности удерживает такие контакты в таблице, что положительно сказывается на устойчивости сети.

В Kademlia определено 4 типа сообщений:

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

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

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

При необходимости узлы могут учитывать RTT, индивидуализируя таймауты запросов.

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

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

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

Для подключения к сети новый узел использует процедуру bootstrapping — необходим адрес хотя бы одного участника сети. После генерации уникального node ID и обнаружения bootstrap-узла, новичок выполняет поисковый запрос на собственный идентификатор, пополняя тем самым свою таблицу и оповещая других о своём наличии. По мере заполнения k-бакетов ведра могут делиться, если в них попадают как более дальние, так и более близкие к собственному node ID значения.

Метрика XOR позволяет группировать биты идентификатора, определяя множество ведер не по каждой отдельной позиции, а по префиксу длины m. Это снижает теоретически максимальное количество итераций поиска с log₂n до log_{2^m}n.

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

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

Рассмотрим сеть Kademlia из ${\displaystyle n}$ узлов с идентификаторами ${\displaystyle x_{1},\ldots ,x_{n}}$, каждый длины ${\displaystyle d}$ бит, интерпретируя их структуру как дерево префиксов (trie), где каждый лист — уникальный узел. Заполнение i-го ведра каждого x производится случайным выбором k контактов из множества узлов, совпадающих по префиксу длиной d–i бит.

Маршрутизация сводится к последовательным «прыжкам» по дереву, максимально приближая ID к цели.

Доказано, что при детерминированном распределении идентификаторов и в худшем случае: ${\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}}}}$, где H_k — k-е гармоническое число. Для больших k среднее количество прыжков ограничено ${\displaystyle \log _{k}n}$.

Если идентификаторы выбираются случайно, то: ${\displaystyle T_{xy}{\xrightarrow {p}}{\frac {\log n}{c_{k}}}}$, а среднее также приближается к ${\displaystyle {\frac {\log n}{c_{k}}}}$, где c_k зависит только от k^[7]. Это объясняет эффективность поиска: нужно опросить лишь ${\displaystyle \Theta (\log n)}$ участников.

Протокол активно применяется в файлообменных сетях. Через ключевые поисковые запросы по Kademlia можно находить информацию для скачивания.

В центральной базы файлов нет — каждый клиент отвечает за фрагмент индекса: при публикации файла рассчитывается его хэш, который становится ключом в DHT; клиент-наблюдатель ищет узлы, чьи идентификаторы близки к хэшу, и передаёт им IP-адрес издателя. Таким образом, узлы с ближайшими к хэшу идентификаторами хранят списки IP-адресов источников файла.

Пользователю достаточно знать только хэш файла, например, из magnet-ссылки или индекса, чтобы начать поиск и затем запросить список источников.

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

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

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

• I2P — анонимная оверлей-сеть^[8].
• Kad network — разработана сообществом eMule для замены серверной архитектуры eDonkey network.
• Ethereum — протокол поиска узлов в стеке блокчейна Ethereum построен на модифицированной Kademlia (нет хранения значений, взаимная верификация точек контакта и поддержка множества подпротоколов)^[9].
• Overnet — прекратившая существование сеть, для которой разрабатывалась библиотека KadC.
• Mainline DHT — DHT-сеть для BitTorrent (без трекеров, протокол основан на Kademlia).
• Osiris — для управления анонимными распределёнными веб-порталами.
• Retroshare — F2F децентрализованная коммуникационная платформа (VoIP, обмен сообщениями, файлами и др.).
• Tox — полностью распределённая система обмена сообщениями, голосом и видеозвонками.
• Gnutella DHT — изначально разработана для LimeWire^[10][11] и в дальнейшем поддерживалась другими gnutella-клиентами^[12].
• IPFS — p2p-файловая система на основе libp2p^[13].
• TeleHash — mesh-протокол, использующий Kademlia для маршрутизации соединений^[14].
• iMule — файлообменная утилита для I2P.
• OpenDHT — библиотека Kademlia, используется в Jami и др^[15].
• GNUnet — стек для построения защищённых приватных p2p-приложений; реализует рандомизированную версию Kademlia (R5N)^[16].
• Dat — p2p-сервис обмена файлами на базе Hypercore Protocol^[17].