Kademlia

Kademlia (укр. Кадемлія) — це протокол комунікації для децентралізованих оверлейних однорангових мереж. Kademlia заснована на метриці XOR і є варіацією розподіленої геш-таблиці (тобто зберігання інформації в розподіленій мережі)^[1][2].

Kademlia була створена Петром Маймунковим та Девідом Мазьєром у 2002 році^[3][4] і вважається початком третього покоління протоколів обчислень з плоскою ієрархією^[5].

Огляд протоколу

Протокол Kademlia складається з чотирьох віддалених викликів процедур (RPC): PING (перевіряє, чи є вузол в мережі), STORE (дає вказівку вузлу зберегти пару [ключ, значення] для подальшого пошуку), FIND_NODE (приймає 160-бітний ключ як аргумент), і FIND_VALUE. Одержувач RPC FIND_NODE повертає кортеж (IP-адреса, UDP-порт, ідентифікатор вузла) для кожного з k вузлів, найближчих до ідентифікатора призначення. RPC FIND_VALUE поводиться подібно до FIND_NODE, повертаючи k вузлів, найближчих до ідентифікатора призначення, за одним винятком: якщо одержувач RPC отримав STORE для заданого ключа, він повертає збережене значення^[6][7].

Кожен вузол і ключ Kademlia ідентифікується 160-бітовим ідентифікатором, кожне значення зберігається на k вузлах, чиї ідентифікатори вузлів найближчі до ідентифікатора ключа. Відстань між двома ідентифікаторами id1 та id2 визначається як id1 XOR id2^[1].

Kad Network

Kad Network (Kad) — це децентралізована, оверлейна, однорангова файлообмінна мережа, реалізація однорангового протоколу зв'язку Kademlia. «Kad» є природним продовженням і розвитком мережі ED2K^[8]. Його відмінною рисою є використання XOR як метрики^[9][2].

Огляд мережі

У Kad кожен клієнт користувача також є вузлом, через який проходять пошукові запити та службова інформація. Всі клієнти користувачів у мережі також є серверами і мають однаковий ранг (звідси значення «однорангової мережі»).

Kademlia визначає структуру мережі та обмін інформацією через пошук вузлів. Вузли Kademlia спілкуються між собою за допомогою UDP. Віртуальна мережа або оверлейна мережа формується вузлами-учасниками. Кожен вузол ідентифікується номером або ідентифікатором вузла. Ідентифікатор вузла слугує не лише для ідентифікації, алгоритм Kademlia використовує ідентифікатор вузла для пошуку значень (зазвичай хешів файлів або ключових слів). Фактично, ідентифікатор вузла надає пряме посилання на хеші файлів, і цей вузол зберігає інформацію про те, де можна отримати файл або ресурс.

Специфікація

Бінарне дерево мережі Kademlia

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

Пошук

Приклад пошуку вузла в мережі Kademlia

Кожен вузол відповідає за зберігання різних типів даних. По-перше, кожен вузол зберігає вихідну карту, тобто інформацію про учасників мережі, які готові поділитися певним файлом. Карта являє собою хеш файлу в якості ключа і список джерел в якості значення. Вихідна карта вузла містить контактну інформацію про хеші всіх файлів, хеш яких відповідає ідентифікатору вузла або близький до нього (з використанням метрики XOR). Наприклад, за допомогою хешу файлу можна знайти вузли з ID, близькими до хешу файлу і запросити у них список джерел для завантаження файлу. По-друге, якщо немає хешу файлу, можна шукати його за ключовими словами. Для цього ім'я опублікованого файлу розбивається на кілька послідовних слів, і кожне слово хешується окремо. Для пошуку за цими ключовими словами у кожного вузла є друга карта, яка містить хеші слів, близьких до ID вузла в якості ключів і хеші файлів та їх імена в якості значень^[11].

Уразливості

Мережа Kad вразлива до атаки Сивілли^[12][13] та зараження руткітом TDSS(інші мови), який створює ботнети^[14].

Відгалуження

Існує багато відгалужень мережі Кадемлія. Однак їх реалізації досить сильно відрізняються від оригінального протоколу^[2].

OpenKad — реалізація Kademlia DHT на Java, яка перебувала в розробці до березня 2013 року^[15][16].

Anonymous Kad (A-Kad) — анонімний протокол на основі мережі Kad, який забезпечує повну конфіденційність і безпеку для провайдерів і запитувачів файлів^[17].

NeoKad^[18] — відгалуження мережі Кадемлія, метою якого є розвиток гнучкості та анонімності. Мережа загального призначення NeoKad може обробляти довільні корисні навантаження, це досягається за рахунок запуску скриптового движка на кожному вузлі і надання скриптам можливості обробляти корисне навантаження, при необхідності сценарії відправляються разом із запитом на пошук. Маршрутизація в NeoKad реалізована таким чином, щоб забезпечити анонімність і правдоподібне заперечення будь-якого конкретного вузла^[19]. Як і, наприклад, у випадку з IPv4 та IPv6, коли мережа розділена на 3 групи вузлів: ті, що мають лише IPv4, ті, що мають IPv4 та IPv6, і ті, що мають лише IPv6, конструкція рекурсивного пошуку дозволяє будь-якому вузлу спілкуватися з будь-яким іншим вузлом, навіть якщо пряме з'єднання неможливо встановити. Очевидним розширенням було додавання можливостей маршрутизації пакетів, щоб за допомогою NeoKad ви могли не тільки публікувати дані в мережі, а потім отримувати їх, але й створювати надійні потокові тунелі між двома анонімними об'єктами. Звичайно, всі дані шифруються за допомогою надійного наскрізного шифрування, і на додаток до цього існує також рівень затуманення, який запобігає фільтруванню на рівні інтернет-провайдера^[20][21].

Зокрема, користуються величезним успіхом у користувачів eMule та eDonkey^[2].

Клієнти мережі Kad

• aMule (клієнт для мереж eDonkey2000 та Kad)^[22];
• eMule (починаючи з версії 0.50a, навіть невелика локальна мережа Kad з 2 вузлів добре працює без жодних проблем з налаштуванням);
• iMule(інші мови) (P2P-клієнт, заснований на aMule, який дозволяє анонімно обмінюватися файлами);
• MLDonkey(інші мови) (програма для обміну файлами, яка може отримувати доступ до різних мереж: BitTorrent, Direct Connect, eDonkey2000, FastTrack, Kademlia, Overnet, Soulseek);
• Mule on Android (клієнт для платформи Android)^[23];
• Tribler;
• Vuze(інші мови) (BitTorrent-клієнт з підтримкою анонімного обміну даними);
• RevConnect (клієнт, сумісний з мережею Direct Connect)^[24];
• Деякі інші вільні BitTorrent-клієнти для мереж обміну файлами також підтримують мережу Kad.

Використання протоколу Kademlia

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

• BitTorrent — в Mainline DHT(інші мови), що використовується клієнтами BitTorrent для пошуку однорангових вузлів, що використовують протокол BitTorrent^[25].
• Етеріум — в платформі для створення децентралізованих сервісів на базі блокчейна^[5].
• IPFS — в одноранговому гіпермедійному протоколі зв'язку^[5][26].

Код Kademlia є основою багатьох розгалужень, а також часто використовується в різноманітному програмному забезпеченні для файлообмінних мереж^[27].

Див. також

• Атака Сивілли
• Розподілена геш-таблиця
• Peer-to-peer
• StrongDC++(інші мови)