Kademlia

Kademlia — это распределённая хеш-таблица (DHT), используемая в одноранговых (P2P) компьютерных сетях для децентрализованного хранения и поиска данных. Kademlia обеспечивает эффективный механизм нахождения узлов и значений в сети без центрального сервера, основываясь на метрике расстояния между идентификаторами узлов (обычно 160-битными числами), вычисляемой с помощью исключающего ИЛИ (XOR). Протокол был впервые описан в 2002 году американскими исследователями Петаром Маймунковым и Дэвидом Мазьером из Массачусетского технологического института.

История

Идея распределённых хеш-таблиц возникла в начале 2000-х годов как ответ на проблемы масштабируемости и отказоустойчивости в P2P-сетях. Предшественники Kademlia, такие как Chord и Pastry, использовали другие метрики расстояния (например, разность идентификаторов по модулю) и требовали более сложных алгоритмов маршрутизации. Маймунков и Мазьер в своей работе 2002 года «Kademlia: A Peer-to-Peer Information System Based on the XOR Metric» предложили использовать XOR-расстояние, что позволило упростить логику маршрутизации и повысить устойчивость к атакам. Первая реализация протокола появилась в сети eDonkey2000, а затем в BitTorrent (через библиотеку libtorrent). На сегодняшний день Kademlia является одной из наиболее распространённых DHT-технологий, используемой в таких проектах, как BitTorrent, Ethereum, I2P (Invisible Internet Project) и ряде криптовалют.

Принцип работы

Идентификаторы и расстояние

Каждый узел в сети Kademlia имеет уникальный идентификатор (Node ID) — обычно 160-битное число, генерируемое случайным образом или на основе хеша IP-адреса. Расстояние между двумя узлами с идентификаторами \( a \) и \( b \) определяется как XOR-значение: \( d(a, b) = a \oplus b \). Чем меньше результат XOR, тем «ближе» узлы друг к другу. Эта метрика обладает свойством симметричности (расстояние от A до B равно расстоянию от B до A) и транзитивности (если A близок к B, а B близок к C, то A, скорее всего, близок к C).

Маршрутизация и k-корзины

Kademlia не хранит информацию обо всех узлах сети. Вместо этого каждый узел поддерживает структуру данных, называемую k-корзиной (k-bucket). Для каждого бита идентификатора (от 0 до 159) существует одна k-корзина, которая содержит записи об узлах, находящихся на определённом XOR-расстоянии. Параметр k (обычно 20) определяет максимальное количество узлов, хранящихся в каждой корзине. Когда узел получает запрос от другого узла, он обновляет свои k-корзины, добавляя или заменяя записи. Если корзина заполнена, старые или неотвечающие узлы вытесняются.

Поиск узлов и значений

Для поиска узла с заданным идентификатором или значения (ключа) узел использует итеративный алгоритм. Он выбирает из своих k-корзин несколько узлов, наиболее близких к целевому идентификатору (по XOR-расстоянию), и отправляет им параллельные запросы. Получив ответы, узел обновляет список ближайших узлов и повторяет процесс, пока не найдёт целевой узел или не получит от него запрошенные данные. Этот процесс напоминает «спуск» по дереву идентификаторов: на каждом шаге расстояние до цели сокращается вдвое. В среднем для нахождения узла в сети из N узлов требуется \( O(\log N) \) шагов.

Хранение и репликация данных

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

K-корзины и управление ими

Структура k-корзины

Каждая k-корзина представляет собой список записей вида (IP-адрес, порт, идентификатор узла). Записи сортируются по времени последнего контакта: самые свежие — в конце списка. При получении запроса от узла, который уже есть в корзине, его запись перемещается в конец. Если узел отсутствует, а корзина не заполнена, он добавляется в конец. Если корзина заполнена, узел проверяет, жив ли самый старый узел в корзине (отправляет ping). Если старый узел не отвечает, он удаляется, а новый добавляется. Если старый узел отвечает, новый узел игнорируется (или помещается в отдельный буфер).

Параметр k

Значение k выбирается так, чтобы обеспечить баланс между устойчивостью к атакам и накладными расходами. Типичное значение — 20. Чем больше k, тем больше узлов хранится в каждой корзине, что повышает надёжность, но увеличивает объём служебного трафика. Малое k (например, 8) снижает нагрузку, но делает сеть более уязвимой к выборочным атакам.

Применение

BitTorrent

В протоколе BitTorrent DHT на основе Kademlia используется для децентрализованного поиска пиров (трекеров). Каждый торрент-файл содержит хеш-сумму, которая служит ключом в DHT. Узлы, загружающие или раздающие файл, регистрируют себя как «хранители» этого ключа. Другие узлы могут найти их, запросив DHT по этому ключу. Эта технология позволяет обходиться без центральных трекеров.

Ethereum

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

I2P

Анонимная сеть I2P использует Kademlia в качестве основы для своей DHT-сети (netDB). Узлы I2P хранят информацию о маршрутизаторах и сервисах (например, адреса скрытых сайтов). XOR-расстояние вычисляется на основе хеша адреса узла.

Криптовалюты

Некоторые криптовалюты, такие как BitTorrent (BTT) и другие, используют Kademlia для децентрализованного хранения блоков транзакций или метаданных. В частности, в протоколе BitTorrent Speed Kademlia применяется для поиска пиров, которые могут подтверждать транзакции.

Преимущества и недостатки

Преимущества

• Децентрализация: отсутствие единой точки отказа; сеть продолжает работать при выходе из строя многих узлов.
• Масштабируемость: сложность поиска \( O(\log N) \), что позволяет сети расти до миллионов узлов.
• Устойчивость к атакам: алгоритм сложно обмануть, так как расстояние вычисляется объективно; злоумышленник не может произвольно приближать или удалять узлы.
• Простота реализации: XOR-метрика и k-корзины легко программируются.

Недостатки

• Зависимость от стабильности узлов: частые уходы и приходы узлов (churn) увеличивают трафик на обновление k-корзин и репликацию данных.
• Уязвимость к Sybil-атакам: злоумышленник может создать множество подставных узлов, чтобы исказить маршрутизацию или блокировать доступ к данным. Для защиты обычно используют верификацию через IP-адреса или криптографические подписи.
• Отсутствие гарантий доставки: если все узлы, хранящие данные, вышли из сети, данные теряются безвозвратно.
• Нагрузка на сеть: для поддержания k-корзин требуется периодический обмен служебными сообщениями (ping, find_node).

Безопасность

Kademlia, как и любая DHT, подвержена ряду атак. Наиболее известные:

• Eclipse-атака: злоумышленник заполняет k-корзины жертвы своими узлами, изолируя её от остальной сети. Защита — проверка подлинности узлов и ограничение на количество узлов с одного IP-адреса.
• Routing table poisoning: внесение ложных записей в k-корзины, что приводит к неверной маршрутизации. Для борьбы используются криптографические подписи и проверка соответствия идентификатора узла его IP-адресу.
• Denial of Service (DoS): массовая отправка запросов на узлы с целью их перегрузки. Частично решается ограничением частоты запросов.

Реализации

Существует множество реализаций Kademlia на различных языках программирования:

• libtorrent (C++) — используется в BitTorrent-клиентах (qBittorrent, uTorrent).
• Kademlia (Python) — простая реализация для образовательных целей.
• Go Kademlia — реализация на Go, используемая в некоторых блокчейн-проектах.
• I2P — собственная реализация на Java.

Интересные факты

• Название «Kademlia» происходит от слова «кадавр» (лат. cadaver) — отсылка к идее «мёртвого» централизованного сервера, который заменяется децентрализованной сетью.
• В оригинальной статье Маймунков и Мазьер доказали, что Kademlia устойчива к атакам, в которых злоумышленник контролирует до 50% узлов сети.
• XOR-метрика позволяет узлам «забывать» о дальних узлах, что снижает нагрузку на память и сеть.
• В сети BitTorrent DHT используется модифицированная версия Kademlia, где k=8, а не 20, для уменьшения служебного трафика.

Источники

• Maymounkov, P., & Mazières, D. (2002). «Kademlia: A Peer-to-Peer Information System Based on the XOR Metric». Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS).
• Loewenstern, A., & Norberg, A. (2008). «DHT Protocol» (BEP 5). BitTorrent Enhancement Proposal.
• Ziese, J., & Schiller, J. (2010). «A Survey of Distributed Hash Tables». Technical Report, Freie Universität Berlin.
• «Kademlia». Wikipedia, The Free Encyclopedia.