Kademlia — это протокол одноранговой связи на основе протокола UDP, разновидность распределённой хеш-таблицы (DHT), разработанная Петром Маймунковым (из Нью-Йорка) и Давидом Мазьером (David Mazières). Kademlia является естественным продолжением и развитием сети ED2K. Его отличительной особенностью является использование XOR в качестве метрики.
Характеристики
Протокол Kademlia определяет структуру сети, регулирующей связь между узлами, и способ обмена информацией в ней. Узлы сети, работающей по протоколу Kademlia, общаются между собой по протоколу UDP. Узлы Kademlia хранят данные посредством распределённых хеш-таблиц. В итоге над существующей LAN/WAN (как интернет) создаётся новая виртуальная или оверлейная сеть, в которой каждый узел обозначается специальным номером («Node ID»). Этот номер также выполняет и другие функции.
Узел, который хочет присоединиться к сети, обязан пройти «загрузочную» процедуру (bootstrap process). В этот момент узел должен знать адрес другого узла (полученный от пользователя или взятый из списка), который уже входит в оверлейную сеть. Если подключаемый узел ещё не входил в эту сеть, то происходит расчет случайного значения ID, которое ещё не принадлежит никакому узлу. ID используется до момента выхода из сети.
Алгоритм Kademlia базируется на расчете «расстояния» между узлами путём применения операции исключающее ИЛИ к ID этих узлов.
Эта «дистанция» не имеет никакого отношения к географическому положению. К примеру, узлы из Германии и Австралии могут быть «соседними» в оверлейной сети.
Информация в Kademlia хранится в так называемых «значениях» (values). Каждое «значение» привязано к «ключу» (key).
При поиске соответствующего ключу значения алгоритм исследует сеть в несколько шагов. Каждый шаг приближает к искомому узлу до полного нахождения «значения» либо до отсутствия таких узлов. Количество контактируемых узлов зависит от размера сети логарифмически: при увеличении количества участников (number of participants) вдвое количество запросов увеличится всего на один.
Использование в файлообменных сетях
Kad Network Kad — оверлейная децентрализованная файлообменная сеть, реализация протокола одноранговой связи «Kademlia» (Кадемлия).
Сеть Kad состоит из нескольких взаимодействующих узлов, которые взаимодействуют друг с другом и хранят информацию друг для друга. Каждый узел имеет NodeID, квазиуникальный двоичный номер, который идентифицирует его в сети. Важно, чтобы идентификаторы узлов были равномерно распределены; на это опирается дизайн сети. Хотя протокол этого не требует, есть возможные преимущества в том, что узел использует один и тот же NodeID всякий раз, когда он подключается к сети, вместо того, чтобы генерировать новый, зависящий от сеанса NodeID.
При инициировании передачи файла клиенты подключаются друг к другу напрямую. Этот трафик подвержен атаке Сивиллы, заражению руткитом TDSS, используемым для создания ботнетов. Как и все децентрализованные сети, сеть Kad не нуждается в официальных или общих серверах, поэтому ее нельзя отключить, отключив определенную основную группу узлов. В то время как децентрализация сети предотвращает её отключение, анализ трафика и глубокая проверка пакетов позволяют легче идентифицировать трафик из-за высокой пропускной способности пакетов с переменным назначением. Большой объем пакетов, а также тот факт, что узлы постоянно взаимодействуют друг с другом, обычно приводит к сокращению доступных ресурсов ЦП и/или сети, обычно связанных с трафиком P2P. Для подключения к этой сети требуются IP-адрес и порт любого клиента, уже подключённого к сети, а также Bootstrap (самонастройка). Как только происходит соединение с сетью, клиент опрашивает других клиентов, чтобы определить, можно ли с ними соединиться.
Задача хранения индексов файлов в сети Kad раскладывается на всех участников сети. Если узел хочет «расшарить» файл, он обрабатывает его, получая хеш, который идентифицирует этот файл в сети. Затем узел ищет несколько узлов, ID которых близки к хешу (размеры хешей и идентификаторов узлов должны совпадать), при этом на эти узлы отдается информация об адресе этого узла. Клиент при поиске ищет ID узла, который имеет наименьшую дистанцию к хешу файла и извлекает из него адреса узлов, которые имеют этот файл. Контакты, хранимые в сети, всегда находятся в постоянном изменении, так как узлы постоянно подключаются и отключаются. Для отказоустойчивости эти контакты реплицируются по нескольким узлам.
Поиск в Kad
Каждый узел отвечает за хранение различных типов информации. Во-первых, каждый узел хранит исходную карту, то есть информацию о членах сети, которые готовы поделиться определенным файлом. Карта представляет собой хэш файла в качестве ключа и список источников в качестве значения. Исходная карта узла содержит контактную информацию о хэшах всех файлов, хэш которых соответствует идентификатору узла или близок к нему (с использованием метрики XOR). Например, с помощью хеша файла можно найти узлы с ID, близкими к хэшу файла и запросить у них список источников для загрузки файла. Во-вторых, если нет хэша файла, можно искать его по ключевым словам. Для этого имя опубликованного файла разбивается на несколько последовательных слов, и каждое слово хешируется отдельно. Для поиска по этим ключевым словам у каждого узла есть вторая карта, которая содержит хэши слов, близких к ID узла в качестве ключей и хэши файлов и их имена в качестве значений.
Ищущий узел выбирает одно из ключевых слов, соединяется с узлом, чей ID самый близкий к хешу ключа и запрашивает у него список файлов для этого ключа. Так как каждый файл в списке имеет свой хеш, имя файла легко вычисляется.
Форки Существует множество ответвлений Кадемлии. eDonkey и eMule, в частности, пользуются огромным успехом у пользователей. Однако их реализации довольно сильно отличаются от исходного протокола.
Существует также ответвление Кадемлии под названием NeoKad, целью которого является развитие гибкости и анонимности. NeoKad может обрабатывать произвольные полезные нагрузки, это достигается за счет запуска скриптового движка на каждом узле и предоставления скриптам возможности обрабатывать полезную нагрузку, при необходимости сценарии отправляются вместе с запросом на поиск. Маршрутизация в NeoKad реализована таким образом, чтобы обеспечить анонимность и правдоподобное отрицание любого конкретного узла. Как и, например, в случае IPv4 и IPv6, когда сеть разделена на 3 группы узлов: те, которые имеют только IPv4, те, которые имеют IPv4 и IPv6, и те, которые имеют только IPv6, конструкция рекурсивного поиска позволяет любому узлу связываться с любым другим узлом, даже если прямое соединение не может быть установлено. Очевидным расширением было добавление возможностей маршрутизации пакетов, чтобы с помощью NeoKad вы могли не только публиковать данные в сети, и получать их, но и создавать надежные потоковые туннели между двумя анонимными объектами. Конечно, все данные шифруются с помощью надежного сквозного шифрования, и в дополнение к этому существует также уровень нечеткости, который предотвращает фильтрацию на уровне интернет-провайдера.
Использование в программном обеспечении Код протокола Kademlia используется в следующем программном обеспечении: BitTorrent — в протоколе BitTorrent. Эфириум — в платформе для создания децентрализованных сервисов на базе блокчейна. IIP — модификация Kademlia DHT. IPFS — в одноранговом гипермедийном протоколе связи. Mainline Kademlia DHT — в протоколе. MLDonkey — в клиенте. NeoKad Network — в одноранговой файлообменной сети. Overnet — в одноранговой файлообменной сети. В свободных BitTorrent клиентах для файлообменных сетей: aMule, eMule, iMule (анонимный клиент), MLDonkey, Tribler и Vuze (с поддержкой анонимного обмена данными). В клиенте RevConnect (для частично централизованной файлообменной сети «Direct Connect») и StrongDC++.
См. также Оверлейная сеть Одноранговая связь Распределённая хеш-таблица Overnet UDP
Примечания
Литература
Ссылки Kademlia: A Design Specification
Атаки на сеть Kad
Категория:Анонимные сети Категория:Анонимные файлообменные сети Категория:Интернет-протоколы Категория:Протоколы маршрутизации Категория:Распределённое хранение данных Категория:Сетевые протоколы Категория:Файлообменные протоколы Категория:Файлообменные сети