Kademlia

Материал из Википедии — свободной энциклопедии
Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 1 мая 2025 года; проверки требуют 8 правок.
Перейти к навигации Перейти к поиску
Kad
Название Kademlia
Семейство распределённая хеш-таблица
Создан в 2002
Назначение протокола файлообменная сеть
Основные реализации Kad Network, NeoKad
Основные реализации (клиенты) aMule, eMule, iMule, MLDonkey, Tribler, Vuze
Основные реализации (серверы) децентрализованная сеть
Разработчик Петр Маймунков и Давид Мазьер
Логотип Викисклада Медиафайлы на Викискладе

Kademlia — это протокол одноранговой связи на основе протокола UDP, разновидность распределённой хеш-таблицы (DHT)[1], разработанная Петром Маймунковым и Давидом Мазьером (David Mazières)[2]. Kademlia является естественным продолжением и развитием сети ED2K.[3] Его отличительной особенностью является использование XOR в качестве метрики.[1]

Характеристики

[править | править код]

Протокол Kademlia определяет структуру сети, регулирующей связь между узлами, и способ обмена информацией в ней. Узлы сети, работающей по протоколу Kademlia, общаются между собой по протоколу UDP. Узлы Kademlia хранят данные посредством распределённых хеш-таблиц (DHT). В итоге над существующей LAN/WAN (как интернет) создаётся новая виртуальная или оверлейная сеть, в которой каждый узел обозначается специальным номером («Node ID»). Этот номер также выполняет и другие функции.

Узел, который хочет присоединиться к сети, обязан пройти «загрузочную» процедуру (bootstrap process). В этот момент узел должен знать адрес другого узла (полученный от пользователя или взятый из списка), который уже входит в оверлейную сеть. Если подключаемый узел ещё не входил в эту сеть, то происходит расчет случайного значения ID, которое ещё не принадлежит никакому узлу. ID используется до момента выхода из сети.

Алгоритм Kademlia базируется на расчете «расстояния» между узлами путём применения операции исключающее ИЛИ к ID этих узлов.

Эта «дистанция» не имеет никакого отношения к географическому положению. К примеру, узлы из Германии и Австралии могут быть «соседними» в оверлейной сети.

Информация в Kademlia хранится в так называемых «значениях» (values). Каждое «значение» привязано к «ключу» (key).

При поиске соответствующего ключу значения алгоритм исследует сеть в несколько шагов. Каждый шаг приближает к искомому узлу до полного нахождения «значения» либо до отсутствия таких узлов. Количество контактируемых узлов зависит от размера сети логарифмически: при увеличении количества участников (number of participants) вдвое количество запросов увеличится всего на один.

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

[править | править код]

Kad Network

[править | править код]

Kad — оверлейная децентрализованная файлообменная сеть, реализация протокола одноранговой связи «Kademlia» (Кадемлия)[1].

Сеть Kad состоит из нескольких взаимодействующих узлов, которые взаимодействуют друг с другом и хранят информацию друг для друга. Каждый узел имеет NodeID, квазиуникальный двоичный номер, который идентифицирует его в сети. Важно, чтобы идентификаторы узлов были равномерно распределены; на это опирается дизайн сети. Хотя протокол этого не требует, есть возможные преимущества в том, что узел использует один и тот же NodeID всякий раз, когда он подключается к сети, вместо того, чтобы генерировать новый, зависящий от сеанса NodeID[4].

При инициировании передачи файла клиенты подключаются друг к другу напрямую. Этот трафик подвержен атаке Сивиллы[5][6][7], заражению руткитом TDSS, используемым для создания ботнетов[8]. Как и все децентрализованные сети, сеть Kad не нуждается в официальных или общих серверах, поэтому ее нельзя отключить, отключив определенную основную группу узлов[2]. В то время как децентрализация сети предотвращает её отключение, анализ трафика и глубокая проверка пакетов позволяют легче идентифицировать трафик из-за высокой пропускной способности пакетов с переменным назначением. Большой объем пакетов, а также тот факт, что узлы постоянно взаимодействуют друг с другом, обычно приводит к сокращению доступных ресурсов ЦП и/или сети, обычно связанных с трафиком P2P. Для подключения к этой сети требуются IP-адрес и порт любого клиента, уже подключённого к сети, а также Bootstrap (самонастройка). Как только происходит соединение с сетью, клиент опрашивает других клиентов, чтобы определить, можно ли с ними соединиться.

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

Поиск в Kad

[править | править код]

Каждый узел отвечает за хранение различных типов информации. Во-первых, каждый узел хранит исходную карту, то есть информацию о членах сети, которые готовы поделиться определенным файлом. Карта представляет собой хэш файла в качестве ключа и список источников в качестве значения. Исходная карта узла содержит контактную информацию о хэшах всех файлов, хэш которых соответствует идентификатору узла или близок к нему (с использованием метрики XOR). Например, с помощью хеша файла можно найти узлы с ID, близкими к хэшу файла и запросить у них список источников для загрузки файла. Во-вторых, если нет хэша файла, можно искать его по ключевым словам. Для этого имя опубликованного файла разбивается на несколько последовательных слов, и каждое слово хешируется отдельно. Для поиска по этим ключевым словам у каждого узла есть вторая карта, которая содержит хэши слов, близких к ID узла в качестве ключей и хэши файлов и их имена в качестве значений[9].

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

Форки

[править | править код]

Существует множество ответвлений Кадемлии. eDonkey и eMule, в частности, пользуются огромным успехом у пользователей. Однако их реализации довольно сильно отличаются от исходного протокола.[1]

Существует также ответвление Кадемлии под названием NeoKad[10], целью которого является развитие гибкости и анонимности. NeoKad может обрабатывать произвольные полезные нагрузки, это достигается за счет запуска скриптового движка на каждом узле и предоставления скриптам возможности обрабатывать полезную нагрузку, при необходимости сценарии отправляются вместе с запросом на поиск. Маршрутизация в NeoKad реализована таким образом, чтобы обеспечить анонимность и правдоподобное отрицание любого конкретного узла. Как и, например, в случае IPv4 и IPv6, когда сеть разделена на 3 группы узлов: те, которые имеют только IPv4, те, которые имеют IPv4 и IPv6, и те, которые имеют только IPv6, конструкция рекурсивного поиска позволяет любому узлу связываться с любым другим узлом, даже если прямое соединение не может быть установлено. Очевидным расширением было добавление возможностей маршрутизации пакетов, чтобы с помощью NeoKad вы могли не только публиковать данные в сети, и получать их, но и создавать надежные потоковые туннели между двумя анонимными объектами. Конечно, все данные шифруются с помощью надежного сквозного шифрования, и в дополнение к этому существует также уровень нечеткости, который предотвращает фильтрацию на уровне интернет-провайдера.[11][12][13]

Использование в программном обеспечении

[править | править код]

Код протокола Kademlia используется в следующем программном обеспечении:

См. также

[править | править код]

Примечания

[править | править код]
  1. ↑ 1 2 3 4 Kademlia. xlattice.sourceforge.net. Дата обращения: 18 марта 2025.
  2. ↑ 1 2 3 Strygul, Iev (23 июля 2021). Kademlia: the P2P System Behind Ethereum and BitTorrent Networks. Medium (англ.). Архивировано 19 сентября 2024. Дата обращения: 2 июня 2025.
  3. ↑ FAQ eD2k-Kademlia-ru - AMule Project FAQ. web.archive.org (23 апреля 2012). Дата обращения: 19 марта 2025.
  4. ↑ Kademlia: A Design Specification. xlattice.sourceforge.net. Дата обращения: 18 марта 2025.
  5. ↑ Peng Wang, James Tyra, Eric Chan-Tin, Tyson Malchow, Denis Foo Kune, Nicholas Hopper, Yongdae Kim. Attacking the Kad network // Proceedings of the 4th international conference on Security and privacy in communication netowrks. — New York, NY, USA: Association for Computing Machinery, 2008-09-22. — С. 1–10. — ISBN 978-1-60558-241-2. — doi:10.1145/1460877.1460907. Архивировано 11 марта 2014 года.
  6. ↑ ; Thibault Cholez, Isabelle Chrisment, Olivier Festor.: . Evaluation of Sybil Attacks Protection Schemes in KAD. ResearchGate GmbH (2009). Архивировано 20 марта 2025 года.
  7. ↑ 1 2 BitTorrent Mainline DHT Measurement. www.cl.cam.ac.uk. Дата обращения: 2 июня 2025.
  8. ↑ TDL4 – Top Bot (амер. англ.). securelist.com (27 июня 2011). Дата обращения: 20 марта 2025.
  9. ↑ Как работает поиск в Kad Network. Хабр (22 июля 2013). Дата обращения: 19 марта 2025.
  10. ↑ NeoLoader, NeoLoader - Next Feneration P2P File Sharing, 18 марта 2025, Дата обращения: 21 марта 2025
  11. ↑ NeoLoader — NeoKad Network. neoloader.com. Дата обращения: 21 марта 2025.
  12. ↑ NeoLoader — Screenshots. neoloader.com. Дата обращения: 21 марта 2025.
  13. ↑ 1 2 NeoLoader — Full Feature List. neoloader.com. Дата обращения: 21 марта 2025.
  14. ↑ bep_0005.rst_post. www.bittorrent.org. Дата обращения: 19 марта 2025.
  15. ↑ Soo Hoon Maeng, Meryam Essaid, Sejin Park, Hongtaek Ju. Discovery of Ethereum Topology Through Active Probing Approach // 2021 22nd Asia-Pacific Network Operations and Management Symposium (APNOMS). — 2021-09. — С. 309–312. — doi:10.23919/APNOMS52696.2021.9562654.
  16. ↑ Will. The “Mainline Kademlia” protocol – Will Scott (амер. англ.) (7 февраля 2010). Дата обращения: 2 июня 2025.
  17. ↑ Juan Pablo Timpanaro, Thibault Cholez, Isabelle Chrisment, Olivier Festor. BitTorrent's Mainline DHT Security Assessment // 2011 4th IFIP International Conference on New Technologies, Mobility and Security. — 2011-02. — С. 1–5. — doi:10.1109/NTMS.2011.5721044.
  18. ↑ RevConnect. web.archive.org (9 декабря 2015). Дата обращения: 19 марта 2025.

Литература

[править | править код]
  • Klaus Wehrle, Mesut Günes, James Gross. Modeling and Tools for Network Simulation. — Springer Science & Business Media, 2010. — P. 454–. — ISBN 978-3-642-12331-3.
  • Cai, X. S., Devroye, L. A Probabilistic Analysis of Kademlia Networks (англ.). — 2013. — Vol. 8283. — P. 711. — doi:10.1007/978-3-642-45030-3_66.
  • Juenemann, Konrad. Confidential Data-Outsourcing and Self-Optimizing P2P-Networks: Coping with the Challenges of Multi-Party Systems. — KIT Scientific Publishing, 2015. — P. 81–. — ISBN 978-3-7315-0328-6.
  • Maymounkov, Petar and Mazières, David (2002). Kademlia: A Peer-to-Peer Information System Based on the XOR Metric. Revised Papers from the First International Workshop on Peer-to-Peer Systems. IPTPS '01. Springer-Verlag. pp. 53–65. Дата обращения: 6 декабря 2013.{{cite conference}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка)

Ссылки

[править | править код]
Источник — https://ru.wikipedia.org/w/index.php?title=Kademlia&oldid=145639992