Описание работы DHT

About dht

Одним из краеугольных протоколов децентрализованных сетей без преувеличения является DHT (Distributed Hash Table). Он был изобретен в конце 90-х годов для решения задачи индексации и поиска среди большого количества данных. Несмотря на то, что сами данные (файлы и т.д) могут храниться на разных серверах, таблица ссылок на данные потенциально может быть бесконечно большой, что исключает вариант ее хранения в одном месте. Кроме того, важной задачей была защита от атак на центральный узел-справочник. Как раз для решения этих двух проблем был разработан DHT.

DHT решает проблему поиска контента (информации) по его хеш значению (InfoHash).

Условия, в которых работает протокол:

  1. участники друг друга не идентифицируют (между ними нет доверия);
  2. участников может быть неограниченное количество;
  3. отсутствует центральный сервер;
  4. контент хранится у самих участников (заранее не известно у каких именно);
  5. каждый участник может поддерживать связь (открыть сетевое соединение и вести обмен сообщениями) только с ограниченным количеством других участников.

Для участника, который ищет данные, задача состоит в том, чтобы получить сетевой адрес другого участника, который хранит порцию контента с определенным InfoHash.

Среда, в которой контент хранится, и по которой выполняется поиск, получается полностью распределенной — множество компьютеров, которые запустили определенную версию протокола DHT и ведут независимый обмен сообщениями.

В соответствии с протоколом, каждый участник имеет глобально уникальный идентификатор. Этот идентификатор представляет собой число такой же размерности как InfoHash (обычно 160 бит и больше). Причем этот идентификатор участник выбирает себе сам, поскольку центр принятия решений отсутствует, а все участники независимы. Для того, чтобы начать работу, новому участнику нужно иметь программу с реализацией протокола, и сетевой адрес как минимум еще одного активного участника (необходимо для подключения к существующей сети).

В соответствии с правилами протокола каждый участник выделяет память (5-50 МБ) для таблицы. В этой таблице он хранит соответствия между InfoHash и контентом, а также между идентификаторами участников и их сетевыми адресами. Все записи в этой таблице отсортированы по первому столбцу (идентификатор или InfoHash) и она постоянно обновляется по следующим правилам:

  1. Если данный участник в ходе общения с другими узнает о новом для него участнике (идентификатор + сетевой адрес), то эта запись вносится в таблицу.
  2. Если участник скачивает или генерирует контент, то от этого контента вычисляется хеш значение (InfoHash) и это соответствие также вносится в таблицу.
  3. Если таблица по размеру приближается к пределу выделенной памяти, то из нее удаляются те строки идентификатор, которых больше всего отличается от идентификатора самого участника.

Таким образом, удаление осуществляется только самых верхних и самых нижних в таблице строк. Через определенный промежуток времени после начала работы участником будет сформирована собственная таблица, в которой будут храниться идентификаторы, максимально приближенные (т.к. они отсортированы в порядке увеличения) к его собственному идентификатору. Соответственно, каждый участник хранит список идентификаторов участников (и ссылки на контент), которые максимально приближены к его собственному идентификатору.

Key (Node ID or InfoHash) Data (IP address or content)
44444444444441 Content #23
55555555555551 202.xx.xx.xx
55555555555552 154.xx.xx.xx
55555555555557 — self Node ID Self IP address
55555555555559 24.xx.xx.xx
55555555555577 98.xx.xx.xx
55555555555588 Content #93
77777777777711 76.xx.xx.xx
Пример таблицы хэшей, которую хранит конкретный участник.
Ее содержимое может присутствовать и у других участников.

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

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

DHT

Для повышения надежности и скорости поиска запросы выполняются параллельно по нескольким приближенным участникам сети. На практике такой механизм поиска обладает достаточно высокой степенью надежности, не поддается цензуре и хорошо масштабируется. Количество участников в сети и количество порций хранимого контента практически не ограничено. Существует дюжина модифицированных версий данного протокола, нацеленных на повышение различных его свойств, таких как скрытность поиска, увеличенный объем хранимых данных, устойчивость к атакам (sybil attack), ускоренный поиск популярного контента, обеспечение целостности запросов и ответов.

Протоколы DHT являются незаменимым компонентом многих популярных проектов: I2P, IPFS, GNUnet, Bittorrent, Tox.

До появления DHT подобную задачу поиска контента решали с использованием централизованных сервисов или группы централизованных сервисов, которые синхронизируются между собой. Также у них реализован публичный API для запросов и, как правило зарегистрировано доменное имя. По сути такие сервисы хранят полные таблицы соответствия между InfoHash и сетевыми адресами, которые по объему получались значительно больше чем 50 МБ. Примером такого сервиса является Torrent Tracker, как известно, такие трекеры легко поддаются цензуре и даже блокированию.

Самая распространенная атака на протоколы DHT заключается в том, что злоумышленник может почти полностью заблокировать один конкретный контент. Для этого ему необходимо запустить несколько десятков специально модифицированных узлов. Модификация заключается в том, что в качестве идентификатора участника выбирается не случайное число, а число близкое к целевому InfoHash (контент который нужно заблокировать). Также эти узлы иначе реагируют на запросы поиска по этому InfoHash, отдавая в ответ не существующие сетевые адреса. Тогда получается, что большое количество фейковых участников “окружают” целевой контент, за счет чего к ним обращаются практически все участники которые ищут этот контент. Таким образом доступ к одному конкретному контенту можно временно заблокировать.

Illustration by Katerina Krashtapuk
Bohdan SkriabinCryptographer, analyst at Distributed Lab