Распределённые хеш-таблицы (DHT)

Введение в курс

О чём этот курс

Этот курс — про распределённые хеш-таблицы (DHT, Distributed Hash Table), одну из ключевых технологий, на которых держатся современные децентрализованные системы: BitTorrent, IPFS, Ethereum, мессенджеры без центрального сервера и многое другое.

DHT решает фундаментальную задачу: как миллионы компьютеров, не имея общего «начальника», могут быстро находить друг друга и нужные данные. Без DHT (или чего-то похожего) децентрализованные сети просто не работали бы на масштабе.

Зачем изучать DHT

Есть несколько причин разобраться в этой теме.

Практическая. DHT — не академическая абстракция. Прямо сейчас десятки миллионов узлов BitTorrent DHT работают по протоколу Kademlia. IPFS строит на DHT глобальную файловую систему. Ethereum использует Kademlia-подобный протокол для обнаружения узлов. Если вы работаете с P2P-системами, блокчейнами или распределёнными хранилищами — DHT вам встретится неизбежно.

Архитектурная. DHT — это красивый пример того, как из простых правил возникает сложное поведение. Каждый узел знает лишь о нескольких десятках соседей, но вместе они образуют структуру, способную найти любой ключ за 20 шагов среди миллиона участников. Понимание DHT развивает мышление о распределённых системах в целом.

Образовательная. В DHT сходятся несколько важных тем из информатики: хеш-функции, деревья, графы, маршрутизация, криптография, устойчивость к отказам и атакам. Это хорошая точка входа для тех, кто хочет глубже разобраться в устройстве сетевых протоколов.

Для кого этот курс

Курс рассчитан на разработчиков, которые:

• знакомы с основами программирования и структурами данных (массивы, хеш-таблицы, деревья);
• хотят понять, как устроены P2P-сети изнутри;
• планируют использовать или реализовывать DHT в своих проектах.

Специальных знаний о распределённых системах или сетевых протоколах не требуется — мы начинаем с нуля и объясняем все термины по ходу дела.

Язык примеров

Примеры кода написаны на языке Nim. Выбор не случаен: на Nim написаны несколько серьёзных реализаций DHT и P2P-протоколов — nim-eth (Ethereum Discovery v5), nim-libp2p, nwaku. Синтаксис Nim при этом достаточно читаемый, чтобы быть понятным разработчикам на Python, Go или других языках.

Если вы не знаете Nim, не переживайте — код в курсе снабжён комментариями, а логика алгоритмов объяснена текстом отдельно от кода. В темах 10 и 12 приведены ссылки на библиотеки на Python, Go, Rust, C++, JavaScript, Java и Erlang.

Структура курса

Курс построен от простого к сложному и состоит из двух частей.

Основной курс (темы 1–8)

Последовательное погружение: от вопроса «зачем это нужно» до реальных систем и их ограничений.

Дополнительные темы (9–12)

Углублённый материал для тех, кто хочет перейти от понимания к практике.

Как проходить

Темы 1–8 лучше читать последовательно — каждая опирается на предыдущие. Темы 9–12 можно изучать в любом порядке, выбирая то, что интереснее.

В каждой теме есть:

• объяснение концепций простым языком;
• примеры кода на Nim с комментариями;
• таблица ключевых терминов;
• ссылки на первоисточники, библиотеки и дополнительные материалы.

Тема 1. P2P-сети и проблема поиска

Что такое P2P-сеть

P2P (peer-to-peer, «равный к равному») — это архитектура сети, в которой нет выделенного центрального сервера. Каждый участник (узел, node) одновременно выступает и клиентом, и сервером: может запрашивать данные у других и отдавать свои.

Примеры P2P-систем, которые вы наверняка встречали:

• BitTorrent — обмен файлами без центрального хранилища;
• IPFS (InterPlanetary File System) — распределённая файловая система;
• Bitcoin и другие криптовалюты — узлы сети совместно поддерживают блокчейн;
• Waku — децентрализованный протокол обмена сообщениями.

В отличие от классической клиент-серверной архитектуры, P2P-сеть не ломается от выхода из строя одного узла. Зато возникает фундаментальная задача: как найти нужные данные или нужного участника, если никто не знает всех?

Наивный подход: флудинг

Самый простой способ поиска в P2P — флудинг (flooding): когда узел хочет что-то найти, он рассылает запрос всем своим соседям, те пересылают дальше, и так далее по всему графу.

Узел A ищет файл X:
A → B, C, D       (A спрашивает своих соседей)
B → E, F           (B пересылает дальше)
C → G, H           (C пересылает дальше)
D → I, J           (D пересылает дальше)
...                 (и так по всей сети)

Так работала, например, ранняя версия Gnutella. Проблемы очевидны:

1. Трафик растёт взрывообразно. Каждый запрос порождает лавину сообщений. При N узлах в сети и средней связности k число сообщений может достигать O(N * k).
2. DoS самих себя. Большое количество узлов, отправляющих запросы одновременно, легко перегружает сеть.
3. Не масштабируется. Для сотен участников ещё терпимо, для миллионов — невозможно.

Что нужно вместо этого

Нужен алгоритм, который позволяет:

• найти ответственного за данные узла за малое число шагов (в идеале — логарифмическое от размера сети);
• не требовать от каждого узла знания обо всех остальных;
• работать при постоянном изменении состава участников (узлы приходят и уходят).

Именно эту задачу решают структурированные оверлейные сети и, в частности, распределённые хеш-таблицы (DHT). О них — в следующей теме.

Пример на Nim: модель простого P2P-узла

Чтобы понять структуру, начнём с минимальной модели узла. Пока без сети — просто типы данных.

import std/[hashes, strutils, sequtils]

type
  NodeId = array[20, byte]  # 160 бит — как SHA-1

  PeerInfo = object
    id: NodeId
    address: string          # например, "192.168.1.5:8000"
    port: uint16

  Message = object
    sender: NodeId
    kind: MessageKind
    payload: string

  MessageKind = enum
    mkPing        # проверка «жив ли узел»
    mkFindNode    # «кто ближе к этому ключу?»
    mkFindValue   # «есть ли у тебя это значение?»
    mkStore       # «сохрани это значение»

proc `$`(id: NodeId): string =
  ## Печатаем ID как шестнадцатеричную строку.
  result = ""
  for b in id:
    result.add(b.toHex(2))

Здесь NodeId — это массив из 20 байт (160 бит). Именно такие идентификаторы используются в Kademlia. Каждый узел и каждый ключ в DHT имеют идентификатор одинаковой длины.

Ключевые термины

Что почитать

• Distributed Hash Table — статья в Wikipedia с общим обзором.
• DHT в IPFS — как DHT используется в реальной системе.
• MIT 6.824: Distributed Hash Tables — лекция MIT по распределённым системам.
• Princeton COS 418: P2P and DHTs — слайды лекции по DHT.

Тема 2. Хеш-таблицы и концепция DHT

Обычная хеш-таблица: напоминание

Хеш-таблица — одна из самых полезных структур данных в программировании. Принцип работы прост:

1. Берём ключ (строку, число, что угодно).
2. Пропускаем через хеш-функцию — получаем число (индекс).
3. По этому индексу кладём или находим значение в массиве.

Среднее время вставки и поиска — O(1). Именно так работают dict в Python, HashMap в Java, Table в Nim.

import std/tables

var storage = initTable[string, string]()
storage["cat"] = "мяу"
storage["dog"] = "гав"

echo storage["cat"]  # => мяу

Всё просто, пока таблица живёт в памяти одного процесса. Но что делать, когда данных слишком много для одной машины, или когда машин тысячи и они разбросаны по миру?

Идея DHT: «размазать» таблицу по сети

Распределённая хеш-таблица (DHT, Distributed Hash Table) — это та же идея «ключ → значение», но реализованная поверх множества узлов сети.

Основные свойства DHT:

• ключи распределены между узлами — каждый узел отвечает за подмножество ключей;
• по любому ключу можно найти ответственный узел за O(log N) шагов, где N — число узлов;
• нет единой точки отказа — если один узел уходит, его ключи переходят к соседям;
• нет центрального сервера — всё работает через взаимодействие равноправных узлов.

Как это выглядит интуитивно

Представьте себе числовую ось от 0 до 2^160 (огромное число). Каждый узел сети и каждый ключ получают идентификатор — 160-битное число, обычно через хеш-функцию (SHA-1 или SHA-256).

0 ───────────────────── 2^160
     ↑    ↑    ↑    ↑
    Узел  Узел Узел Узел
     A     B    C    D

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

Как узел получает свой идентификатор

Идентификатор узла (Node ID) — это хеш от чего-нибудь уникального: публичного ключа, IP-адреса, случайного числа. Главное — он должен быть:

• фиксированной длины (обычно 160 или 256 бит);
• равномерно распределён по пространству идентификаторов.

import std/sha1

proc generateNodeId(data: string): array[20, byte] =
  ## Генерируем 160-битный NodeId из произвольных данных.
  let digest = secureHash(data)
  # secureHash возвращает Sha1Digest — преобразуем в массив байт
  let hex = $digest
  for i in 0 ..< 20:
    result[i] = fromHex[byte](hex[i*2 .. i*2+1])

let nodeA = generateNodeId("node-alpha-secret-key")
let nodeB = generateNodeId("node-beta-secret-key")

Хеш-функция обеспечивает, что даже похожие входные данные дают совершенно разные идентификаторы. Это важно для равномерного распределения узлов по пространству.

Две ключевые операции DHT

Любая DHT поддерживает как минимум две операции:

1. put(key, value) — сохранить значение по ключу. DHT находит узел, ответственный за этот ключ, и передаёт ему данные.
2. get(key) — найти значение по ключу. DHT маршрутизирует запрос к ответственному узлу и возвращает результат.

В реальных реализациях операций больше, но эти две — фундамент.

type
  DhtNode = object
    id: array[20, byte]
    localStore: Table[string, string]    # данные, за которые отвечает этот узел
    routingTable: seq[PeerInfo]          # известные соседи

proc put(node: var DhtNode, key, value: string) =
  ## Упрощённая версия: если ключ «наш», сохраняем локально.
  ## В реальности — маршрутизируем к ответственному узлу.
  node.localStore[key] = value

proc get(node: DhtNode, key: string): string =
  ## Упрощённая версия: ищем локально.
  ## В реальности — маршрутизируем запрос по сети.
  if key in node.localStore:
    return node.localStore[key]
  else:
    return ""

Почему O(log N) — это хорошо

В сети из миллиона узлов (N = 1 000 000) логарифм по основанию 2 равен примерно 20. Это значит, что для поиска любого ключа достаточно около 20 сетевых запросов — независимо от того, где находится ключ.

Для сравнения:

Разница колоссальная. Именно за счёт умной организации таблицы маршрутизации DHT добивается такой эффективности.

Разные DHT — разные подходы

Существует несколько алгоритмов DHT, каждый по-своему организует пространство идентификаторов и маршрутизацию:

Все они дают O(log N) шагов поиска, но отличаются топологией, метрикой расстояния и деталями реализации. В этом курсе мы подробно разберём Kademlia — самый популярный алгоритм на практике, а затем сравним его с остальными.

Ключевые термины

Что почитать

• Distributed Hash Table — Wikipedia — общий обзор с историей.
• What is a DHT? — короткое объяснение концепции.
• UC Berkeley CS 268: DHTs — слайды лекции Ion Stoica (автора Chord).
• Stanford Code the Change: Kademlia Guide — пошаговое руководство.
• GeeksforGeeks: DHT with Kademlia — обзорная статья.

Тема 3. Kademlia — XOR-метрика и k-бакеты

Откуда взялась Kademlia

Kademlia — протокол DHT, предложенный Петаром Маймунковым и Давидом Мазьером в 2002 году. На практике это самый популярный алгоритм DHT: на нём работают BitTorrent DHT, IPFS, Ethereum Discovery и ряд других крупных P2P-систем.

Две ключевые идеи, которые отличают Kademlia от остальных DHT:

1. XOR-метрика — простой и математически удобный способ измерять «расстояние» между узлами.
2. k-бакеты — компактная структура таблицы маршрутизации, где информация о дальних узлах хранится «крупными мазками», а о ближних — подробно.

Разберём обе идеи.

XOR-метрика: как измерить «близость» в пространстве ID

В Kademlia каждый узел и каждый ключ имеют идентификатор одинаковой длины — обычно 160 бит. Расстояние между двумя идентификаторами определяется через операцию XOR (исключающее «или»):

distance(A, B) = A XOR B

XOR — побитовая операция: для каждого бита результат равен 1, если биты различаются, и 0, если совпадают.

A = 1 0 1 1 0
B = 1 0 0 1 1
──────────────
    0 0 1 0 1  →  результат = 5 (в десятичной)

Чем меньше результат XOR, тем ближе два идентификатора. Если A XOR B = 0, значит A = B.

Почему именно XOR

XOR как метрика обладает важными математическими свойствами:

• d(A, A) = 0 — расстояние от узла до самого себя равно нулю;
• d(A, B) = d(B, A) — метрика симметрична (это свойство уникально для Kademlia среди DHT);
• d(A, B) + d(B, C) >= d(A, C) — неравенство треугольника выполняется.

Симметричность важна на практике: если узел A считает B близким, то и B считает A близким. Это упрощает поддержание таблиц маршрутизации — информация о маршрутах «взаимна».

Реализация на Nim

type
  NodeId = array[20, byte]  # 160 бит

proc xorDistance(a, b: NodeId): NodeId =
  ## Вычисляем XOR-расстояние между двумя идентификаторами.
  for i in 0 ..< a.len:
    result[i] = a[i] xor b[i]

proc `<`(a, b: NodeId): bool =
  ## Сравнение ID как больших чисел (побайтово, от старшего к младшему).
  for i in 0 ..< a.len:
    if a[i] < b[i]: return true
    if a[i] > b[i]: return false
  return false  # равны

proc isCloser(candidate, current, target: NodeId): bool =
  ## Проверяем: candidate ближе к target, чем current?
  let distCandidate = xorDistance(candidate, target)
  let distCurrent = xorDistance(current, target)
  return distCandidate < distCurrent

Логарифмическое расстояние

На практике нас интересует не точное значение XOR, а порядок расстояния. Для этого используют понятие логарифмического расстояния — номер старшего ненулевого бита в результате XOR.

proc logDistance(a, b: NodeId): int =
  ## Возвращает номер старшего различающегося бита (0..159).
  ## Чем больше значение, тем «дальше» узлы друг от друга.
  for i in 0 ..< a.len:
    let diff = a[i] xor b[i]
    if diff != 0:
      # Находим номер старшего бита в этом байте.
      var bit = 7
      while bit >= 0:
        if (diff and (1'u8 shl bit)) != 0:
          return (a.len - 1 - i) * 8 + bit
        dec bit
  return 0  # идентификаторы совпадают

Логарифмическое расстояние определяет, в какой k-бакет попадает узел.

K-бакеты: структура таблицы маршрутизации

Таблица маршрутизации каждого узла Kademlia состоит из набора k-бакетов (k-buckets). Каждый бакет хранит информацию об узлах на определённом «расстоянии».

Для 160-битного пространства есть 160 бакетов:

• Бакет 0 — узлы, отличающиеся от нас в самом младшем бите (расстояние 1).
• Бакет 1 — расстояние от 2 до 3.
• Бакет i — расстояние от 2^i до 2^(i+1) - 1.
• Бакет 159 — узлы, отличающиеся в старшем бите (половина всего пространства).

Наш ID: 1010...
                                      Бакет 159
                                    (половина сети)
                                   /
Бакет 0 ─── Бакет 1 ─── ... ─── /
(1-2 узла)  (1-2 узла)         (много узлов)
   ↑
  самые
 близкие

Каждый бакет хранит до k узлов (типичное значение k = 20). Параметр k — это ширина таблицы маршрутизации, он определяет, сколько контактов мы помним на каждом масштабе расстояния.

Ключевое наблюдение

Бакеты с малыми номерами (близкие узлы) покрывают маленькие участки пространства ID — в них мало узлов, и мы знаем почти всех. Бакеты с большими номерами покрывают огромные участки — в них много узлов, но мы знаем лишь k представителей.

Это как если бы вы хорошо знали всех соседей по улице, нескольких людей из района, пару человек из города и одного из каждой страны. При поиске кого-то конкретного вы бы быстро нашли нужное направление.

Реализация на Nim

const
  IdBits = 160
  K = 20  # максимальное число узлов в одном бакете

type
  KBucket = object
    nodes: seq[PeerInfo]     # до K узлов, упорядоченных по «свежести»

  RoutingTable = object
    selfId: NodeId
    buckets: array[IdBits, KBucket]

proc bucketIndex(rt: RoutingTable, nodeId: NodeId): int =
  ## Определяем, в какой бакет попадает узел.
  return logDistance(rt.selfId, nodeId)

proc addNode(rt: var RoutingTable, peer: PeerInfo) =
  ## Добавляем узел в соответствующий k-бакет.
  let idx = rt.bucketIndex(peer.id)

  # Проверяем, нет ли уже этого узла в бакете.
  for i, existing in rt.buckets[idx].nodes:
    if existing.id == peer.id:
      # Узел уже есть — перемещаем в конец (он «свежий»).
      rt.buckets[idx].nodes.delete(i)
      rt.buckets[idx].nodes.add(peer)
      return

  # Узел новый.
  if rt.buckets[idx].nodes.len < K:
    # Бакет не полон — просто добавляем.
    rt.buckets[idx].nodes.add(peer)
  else:
    # Бакет полон — проверяем, жив ли самый «старый» узел (первый в списке).
    # Если нет — заменяем его. Если да — отбрасываем нового.
    # (Упрощённая версия — в реальности тут ping.)
    discard

proc findClosest(rt: RoutingTable, target: NodeId, count: int): seq[PeerInfo] =
  ## Находим `count` узлов из таблицы маршрутизации,
  ## наиболее близких к target по XOR.
  var all: seq[PeerInfo]
  for bucket in rt.buckets:
    for node in bucket.nodes:
      all.add(node)
  # Сортируем по расстоянию до target.
  all.sort do (a, b: PeerInfo) -> int:
    let da = xorDistance(a.id, target)
    let db = xorDistance(b.id, target)
    if da < db: -1
    elif da == db: 0
    else: 1
  # Возвращаем первые count.
  if all.len <= count:
    return all
  else:
    return all[0 ..< count]

Политика замены в k-бакетах

Важная деталь: когда бакет полон и приходит новый узел, Kademlia не вытесняет старых узлов автоматически. Вместо этого:

1. Проверяем, жив ли самый давно виденный узел (ping).
2. Если жив — оставляем его, нового отбрасываем.
3. Если не отвечает — заменяем на нового.

Эта стратегия называется «предпочтение старожилам» (least-recently seen eviction). Она основана на эмпирическом наблюдении: узлы, которые давно в сети, с большей вероятностью останутся и дальше.

Размер таблицы маршрутизации

Каждый узел хранит не более K * 160 = 20 * 160 = 3200 записей. На практике — значительно меньше, поскольку ближние бакеты часто полупустые (в мелком диапазоне просто не так много узлов).

Итого: при миллионе узлов в сети каждый хранит информацию лишь о нескольких сотнях или тысячах других. Это вполне умещается в памяти даже встраиваемого устройства.

Ключевые термины

Что почитать

• Kademlia: A Peer-to-peer Information System Based on the XOR Metric — оригинальная статья Маймункова и Мазьера (2002).
• Kademlia — Wikipedia — подробная статья с описанием структуры.
• Kademlia Visualization — интерактивная визуализация алгоритма.
• Хабр: Kademlia — распределённая хеш-таблица — статья на русском.
• Исходный код routing_table.nim в nim-eth: github.com/status-im/nim-eth/…/routing_table.nim — реальная реализация k-бакетов на Nim.

Тема 4. Алгоритм поиска в Kademlia

Четыре операции протокола

Kademlia определяет четыре RPC-операции (Remote Procedure Call — удалённый вызов процедуры), через которые узлы общаются друг с другом:

Все остальные операции DHT строятся на этих четырёх примитивах. Самая интересная — FIND_NODE, потому что именно через неё работает итеративный поиск.

Итеративный поиск: основной алгоритм

Допустим, узел U хочет найти данные по ключу K (или просто найти узлы, ближайшие к K). Алгоритм работает так:

Шаг 1. Начальный набор кандидатов

Узел U выбирает из своей таблицы маршрутизации α узлов, наиболее близких к K по XOR-метрике. Параметр α (alpha) — это степень параллелизма, обычно α = 3.

Шаг 2. Параллельные запросы

U отправляет этим α узлам запрос FIND_NODE(K).

Шаг 3. Обработка ответов

Каждый опрошенный узел отвечает списком из k узлов, которые он считает ближайшими к K. Узел U добавляет эти новые узлы в свой список кандидатов.

Шаг 4. Повтор

Из обновлённого списка U выбирает ещё не опрошенных узлов, ближайших к K, и отправляет им запросы. Процесс повторяется.

Шаг 5. Завершение

Алгоритм завершается, когда k ближайших к K узлов уже опрошены, и ни один из ответов не дал более близких кандидатов.

Шаг 1:  U знает {A, B, C} — ближайших к K
        U → A: FIND_NODE(K)
        U → B: FIND_NODE(K)
        U → C: FIND_NODE(K)

Шаг 2:  A отвечает: {D, E}  — ещё ближе к K!
        B отвечает: {D, F}
        C отвечает: {E, G}

Шаг 3:  U теперь знает {A, B, C, D, E, F, G}
        D и E — ближайшие к K, ещё не опрошены
        U → D: FIND_NODE(K)
        U → E: FIND_NODE(K)

Шаг 4:  D отвечает: {H}  — H ещё ближе!
        E отвечает: {H}

Шаг 5:  U → H: FIND_NODE(K)
        H отвечает: {}  — никого ближе нет
        → Поиск завершён: H — ближайший к K

Аналогия с телефонной книгой

Представьте, что вы ищете специалиста по редкой теме. Вы спрашиваете знакомых — каждый из них знает кого-то, кто разбирается в теме чуть лучше. С каждым звонком вы приближаетесь к эксперту. За 20 звонков (при миллионе человек) вы находите нужного — это и есть O(log N).

Реализация на Nim

import std/[algorithm, sets]

const
  Alpha = 3  # степень параллелизма
  K = 20     # размер k-бакета

type
  NodeId = array[20, byte]

  PeerInfo = object
    id: NodeId
    address: string

  FindNodeResult = object
    nodes: seq[PeerInfo]

proc xorDistance(a, b: NodeId): NodeId =
  for i in 0 ..< 20:
    result[i] = a[i] xor b[i]

proc `<`(a, b: NodeId): bool =
  for i in 0 ..< 20:
    if a[i] < b[i]: return true
    if a[i] > b[i]: return false
  return false

proc sortByDistance(nodes: var seq[PeerInfo], target: NodeId) =
  nodes.sort do (a, b: PeerInfo) -> int:
    let da = xorDistance(a.id, target)
    let db = xorDistance(b.id, target)
    if da < db: -1
    elif db < da: 1
    else: 0

proc sendFindNode(peer: PeerInfo, target: NodeId): FindNodeResult =
  ## Заглушка: в реальности — UDP/TCP-запрос к узлу.
  ## Узел отвечает списком k ближайших к target.
  discard

proc iterativeFindNode(
    selfId: NodeId,
    target: NodeId,
    routingTable: RoutingTable
): seq[PeerInfo] =
  ## Итеративный поиск k узлов, ближайших к target.

  # 1. Начальный набор кандидатов из нашей таблицы маршрутизации.
  var candidates = findClosest(routingTable, target, K)
  var queried: HashSet[NodeId]     # уже опрошенные
  var best: seq[PeerInfo]          # лучшие k результатов

  best = candidates
  sortByDistance(best, target)

  while true:
    # 2. Выбираем до Alpha ещё не опрошенных, ближайших к target.
    var toQuery: seq[PeerInfo]
    for c in candidates:
      if c.id notin queried:
        toQuery.add(c)
        if toQuery.len >= Alpha:
          break

    if toQuery.len == 0:
      break  # все кандидаты опрошены

    # 3. Отправляем запросы (в реальности — параллельно).
    var improved = false
    for peer in toQuery:
      queried.incl(peer.id)
      let response = sendFindNode(peer, target)

      for newPeer in response.nodes:
        # Добавляем новых кандидатов.
        var found = false
        for existing in candidates:
          if existing.id == newPeer.id:
            found = true
            break
        if not found:
          candidates.add(newPeer)

    # 4. Пересортируем и проверяем, улучшился ли результат.
    sortByDistance(candidates, target)

    let newBest = candidates[0 ..< min(K, candidates.len)]
    if newBest.len > 0 and best.len > 0:
      let oldClosest = xorDistance(best[0].id, target)
      let newClosest = xorDistance(newBest[0].id, target)
      if newClosest < oldClosest:
        improved = true

    best = newBest

    if not improved:
      break  # сошлись — ближе никого нет

  return best

FIND_VALUE: поиск данных

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

type
  FindValueResult = object
    found: bool
    value: string              # если found = true
    closerNodes: seq[PeerInfo] # если found = false

proc iterativeFindValue(
    selfId: NodeId,
    key: NodeId,
    routingTable: RoutingTable
): string =
  ## Ищем значение по ключу. Логика та же, что в findNode,
  ## но прерываемся, как только кто-то вернул значение.
  var candidates = findClosest(routingTable, key, K)
  var queried: HashSet[NodeId]

  while true:
    var toQuery: seq[PeerInfo]
    for c in candidates:
      if c.id notin queried:
        toQuery.add(c)
        if toQuery.len >= Alpha:
          break

    if toQuery.len == 0:
      return ""  # не нашли

    for peer in toQuery:
      queried.incl(peer.id)
      # let response = sendFindValue(peer, key)
      # if response.found:
      #   return response.value
      # else:
      #   candidates.add(response.closerNodes)
      discard

    sortByDistance(candidates, key)

  return ""

STORE: сохранение данных

Чтобы сохранить пару (ключ, значение) в DHT:

1. Узел выполняет FIND_NODE(ключ), находя k узлов, ближайших к ключу.
2. Отправляет каждому из них STORE(ключ, значение).

Данные реплицируются на k узлов — если один из них уйдёт, остальные всё ещё хранят копию.

proc storeToDht(
    selfId: NodeId,
    key: NodeId,
    value: string,
    routingTable: RoutingTable
) =
  ## Сохраняем значение в DHT: находим k ближайших и отправляем STORE.
  let closest = iterativeFindNode(selfId, key, routingTable)
  for peer in closest:
    discard # sendStore(peer, key, value)

Параметры Kademlia

Три параметра определяют поведение системы:

Увеличение k повышает надёжность (больше реплик), но увеличивает трафик. Увеличение α ускоряет поиск (больше параллелизма), но тоже растёт нагрузка.

Ключевые термины

Что почитать

• Kademlia Paper (PDF) — раздел 2.3 описывает алгоритм поиска.
• The Kademlia Protocol Succinctly — бесплатная книга Марка Клифтона с пошаговым разбором.
• Notes on Kademlia DHT — компактный конспект ключевых алгоритмов.
• Хабр: Kademlia — разбор с примерами на русском.
• libp2p DHT Guide — как поиск работает в libp2p (IPFS).

Тема 5. Хранение данных и устойчивость к churn

Что такое churn

Churn (чёрн) — это постоянная смена состава участников сети. В P2P-сетях узлы не работают непрерывно: люди закрывают ноутбуки, у кого-то обрывается интернет, кто-то перезапускает клиент. Одновременно подключаются новые участники.

В типичной BitTorrent DHT-сети за час может смениться 20–30 % узлов. Kademlia должна сохранять работоспособность в таких условиях.

Где хранятся данные в DHT

Когда узел вызывает STORE(key, value), данные сохраняются на k узлах, ближайших к key по XOR-метрике. Почему не на одном:

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

const K = 20

proc storeValue(selfId: NodeId, key: NodeId, value: string,
                rt: RoutingTable) =
  ## Находим k ближайших узлов к ключу и отправляем каждому STORE.
  let closest = iterativeFindNode(selfId, key, rt)
  for peer in closest[0 ..< min(K, closest.len)]:
    # Отправляем STORE(key, value) каждому из k ближайших.
    sendStore(peer, key, value)

Переиздание данных (republishing)

Данные в Kademlia не хранятся вечно. У каждой записи есть время жизни (TTL, Time to Live). Чтобы данные не пропали, узел, который их «публиковал», периодически повторяет операцию STORE — это называется переиздание (republishing).

Кроме того, существует репликация (replication): узлы, хранящие данные, периодически пересылают их ближайшим соседям, чтобы покрыть случаи, когда пришёл новый узел, ставший ещё ближе к ключу.

const
  RepublishInterval = 3600    # секунд (1 час)
  ExpireInterval = 86400      # секунд (24 часа)

type
  StoredItem = object
    key: NodeId
    value: string
    publishedAt: float         # время первой публикации
    lastRepublish: float       # время последнего переиздания

proc shouldRepublish(item: StoredItem, now: float): bool =
  return (now - item.lastRepublish) >= RepublishInterval

proc isExpired(item: StoredItem, now: float): bool =
  return (now - item.publishedAt) >= ExpireInterval

Жизненный цикл узла

Подключение нового узла

Когда новый узел N присоединяется к сети:

1. N должен знать хотя бы один bootstrap-узел — адрес входной точки, через которую можно попасть в сеть.
2. N выполняет FIND_NODE(собственный_ID) — ищет «самого себя». Это позволяет:
   • заполнить свои k-бакеты узлами, близкими к нему;
   • «представиться» другим узлам (они добавляют N в свои таблицы).
3. N обновляет все свои бакеты, делая дополнительные запросы FIND_NODE для разных диапазонов.

proc bootstrap(self: var DhtNode, bootstrapAddr: string) =
  ## Подключение к сети через bootstrap-узел.

  # 1. Связываемся с bootstrap-узлом.
  let bootstrapPeer = connectTo(bootstrapAddr)
  self.routingTable.addNode(bootstrapPeer)

  # 2. Ищем «самого себя» — заполняем таблицу маршрутизации.
  let closest = iterativeFindNode(self.id, self.id, self.routingTable)
  for peer in closest:
    self.routingTable.addNode(peer)

  # 3. Обновляем бакеты: для каждого бакета ищем случайный ID из его диапазона.
  for i in 0 ..< IdBits:
    let randomTarget = randomIdInBucket(self.id, i)
    let found = iterativeFindNode(self.id, randomTarget, self.routingTable)
    for peer in found:
      self.routingTable.addNode(peer)

Поддержание таблицы маршрутизации

Узлы периодически обновляют свои k-бакеты:

• Ping неактивных — если бакет не обновлялся больше часа, узел выбирает случайный ID из диапазона этого бакета и выполняет FIND_NODE. Это обновляет содержимое бакета.
• Проверка «старожилов» — при попытке добавить узел в полный бакет отправляется PING самому старому узлу. Если не отвечает — заменяем.

const RefreshInterval = 3600.0  # 1 час

type
  KBucketMeta = object
    nodes: seq[PeerInfo]
    lastRefreshed: float

proc refreshStalesBuckets(self: var DhtNode, now: float) =
  ## Обновляем бакеты, которые давно не обновлялись.
  for i in 0 ..< IdBits:
    if (now - self.bucketMeta[i].lastRefreshed) > RefreshInterval:
      let randomTarget = randomIdInBucket(self.id, i)
      let found = iterativeFindNode(self.id, randomTarget, self.routingTable)
      for peer in found:
        self.routingTable.addNode(peer)
      self.bucketMeta[i].lastRefreshed = now

Отключение узла

Когда узел уходит из сети, ничего специального не происходит. Его соседи рано или поздно обнаружат, что он не отвечает на PING, и удалят его из своих бакетов. Данные, которые он хранил, уже реплицированы на других ближайших узлах.

Это одно из преимуществ Kademlia — отсутствие явной процедуры отключения. Узел может просто «исчезнуть», и система адаптируется.

Пример: жизненный цикл записи

Допустим, Алиса хочет сохранить в DHT запись hash("cat.jpg") → "ip:port":

1. Алиса вычисляет key = SHA1("cat.jpg").
2. Выполняет FIND_NODE(key), находит 20 узлов, ближайших к key.
3. Отправляет STORE(key, "ip:port") каждому из них.
4. Раз в час повторяет шаги 2–3 (переиздание).

Боб хочет найти cat.jpg:

1. Боб вычисляет тот же key = SHA1("cat.jpg").
2. Выполняет FIND_VALUE(key).
3. Итеративный поиск приводит его к одному из 20 узлов-хранителей.
4. Получает значение "ip:port" и связывается с Алисой напрямую.

Устойчивость на практике

Исследования и опыт эксплуатации показывают, что Kademlia сохраняет работоспособность при значительном уровне churn. Ключевые факторы устойчивости:

• Параметр k = 20 — даже если 19 из 20 хранителей уйдут, данные не потеряются.
• Предпочтение старожилам — долгоживущие узлы статистически надёжнее новых.
• Симметричная метрика — узлы, близкие друг к другу, взаимно обновляют таблицы.
• Периодическое переиздание — данные «освежаются» даже при сменяющемся составе узлов.

Ключевые термины

Что почитать

• Kademlia Paper — раздел 2.5 о процедурах обновления.
• Analysis of Kademlia Protocol Under Churn — исследование устойчивости к churn.
• IPFS DHT Documentation — как IPFS обрабатывает churn.
• libp2p Kademlia Spec — спецификация с деталями bootstrap и refresh.
• Исходный код protocol.nim в nim-eth: github.com/status-im/nim-eth/…/protocol.nim — реализация bootstrap и refresh на Nim.

Тема 6. DHT в реальных системах

BitTorrent DHT (Mainline DHT)

BitTorrent — пожалуй, самый массовый пользователь Kademlia. В ранних версиях BitTorrent для поиска пиров (узлов, раздающих файл) был нужен централизованный трекер — сервер, который хранил список infohash → пиры. Если трекер падал — загрузка останавливалась.

Mainline DHT (описана в спецификации BEP 5) заменила трекер распределённой хеш-таблицей на основе Kademlia. Теперь каждый BitTorrent-клиент является узлом DHT.

Как это работает

1. Каждый торрент-файл имеет infohash — 160-битный хеш метаданных файла.
2. Клиент, раздающий файл, делает announce_peer(infohash) — сообщает DHT: «я раздаю этот файл, мой адрес такой-то».
3. Клиент, желающий скачать файл, делает get_peers(infohash) — спрашивает DHT: «кто раздаёт файл с этим хешем?».
4. DHT маршрутизирует запрос к узлам, ближайшим к infohash, и возвращает список пиров.

Особенности реализации

BitTorrent DHT использует KRPC (Kademlia RPC) — бинарный протокол поверх UDP. Сообщения кодируются в формате Bencode (тот же формат, что и .torrent-файлы).

Четыре RPC-операции:

import std/tables

type
  KrpcMessage = object
    ## Упрощённая модель KRPC-сообщения BitTorrent DHT.
    transactionId: string  # "t" — идентификатор запроса
    msgType: string        # "q" (query), "r" (response), "e" (error)
    queryName: string      # "ping", "find_node", "get_peers", "announce_peer"
    args: Table[string, string]

proc newGetPeersQuery(infohash: array[20, byte], nodeId: array[20, byte]): KrpcMessage =
  result.transactionId = "aa"
  result.msgType = "q"
  result.queryName = "get_peers"
  # В реальности args содержат бинарные данные в Bencode-формате.

Масштаб

Mainline DHT — одна из крупнейших распределённых систем в мире. По оценкам, в ней одновременно участвуют десятки миллионов узлов. Несмотря на масштаб, поиск занимает считанные секунды.

IPFS и libp2p

IPFS (InterPlanetary File System) — это распределённая файловая система, где каждый файл адресуется по хешу его содержимого (content addressing). Для поиска узлов и контента IPFS использует Kademlia-подобную DHT, реализованную в библиотеке libp2p.

Ключевые отличия от BitTorrent DHT

• Протокол: вместо UDP и Bencode — TCP/QUIC и Protobuf.
• Идентификаторы: 256 бит (SHA-256), а не 160 бит.
• Безопасность: используется модифицированный протокол S/Kademlia с криптографическими проверками ID.
• Множественность функций: DHT отвечает не только за поиск пиров, но и за обнаружение провайдеров контента, публикацию IPNS-записей и маршрутизацию.

Amino DHT

Основная публичная DHT в IPFS называется Amino DHT. Все узлы IPFS, подключённые к этой DHT, используют протокол /ipfs/kad/1.0.0.

# Пример: идентификация peer-а в libp2p-стиле
type
  PeerId = object
    ## В libp2p PeerId — это хеш публичного ключа.
    multihash: seq[byte]   # multihash-encoded SHA-256

  MultiAddr = object
    ## Адрес узла в формате multiaddr: /ip4/1.2.3.4/tcp/4001/p2p/QmPeer...
    raw: string

  ContentId = object
    ## CID — идентификатор контента в IPFS.
    hash: seq[byte]
    codec: uint64
    version: uint8

Библиотеки libp2p

libp2p реализована на нескольких языках:

Ethereum Discovery v5

Ethereum использует модифицированную версию Kademlia для поиска узлов в своей P2P-сети. Протокол называется Discovery v5 (discv5) и имеет ряд отличий от классической Kademlia:

• 256-битные ID на основе публичного ключа.
• ENR (Ethereum Node Record) — структурированная запись с информацией об узле.
• Шифрование: все сообщения шифруются с использованием сессионных ключей.
• TALKREQ/TALKRESP — дополнительные RPC для расширяемости протокола.

Реализация на Nim: nim-eth

Проект nim-eth от Status содержит полную реализацию Discovery v5 на Nim:

# Пример инициализации Discovery v5 узла (из nim-eth).
import
  eth/keys,
  eth/p2p/discoveryv5/[protocol, routing_table]

let
  rng = newRng()
  privKey = PrivateKey.random(rng[])
  # Создаём протокол с приватным ключом, IP и портами.
  d = newProtocol(privKey,
    bindIp = parseIpAddress("0.0.0.0"),
    bindPort = Port(9000),
    rng = rng)

d.open()  # начинаем слушать

Ключевые файлы:

• routing_table.nim — k-бакеты и таблица маршрутизации;
• protocol.nim — основной протокол;
• kademlia.nim — более ранняя реализация Kademlia для devp2p.

Waku

Waku — децентрализованный протокол обмена сообщениями, разработанный организацией Vac/Status. Использует libp2p для транспорта и обнаружения узлов, включая Kademlia DHT.

Реализация на Nim — nwaku: github.com/waku-org/nwaku.

Другие применения DHT

DHT находит применение за пределами файлообмена:

• Децентрализованные хранилища (Storj, Sia) — хранение фрагментов файлов с адресацией через DHT.
• Мессенджеры (Tox, Briar) — поиск контактов без центрального сервера.
• DNS-альтернативы (Namecoin, ENS) — распределённые системы именования.
• Криптовалютные сети — обнаружение пиров, маршрутизация транзакций.

Сводная таблица

Ключевые термины

Что почитать

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

• BEP 5 — DHT Protocol — спецификация BitTorrent DHT.
• BEP 44 — Storing Arbitrary Data in the DHT — расширение для хранения произвольных данных.
• libp2p Kademlia DHT Spec — спецификация libp2p DHT.
• IPFS Kademlia DHT Spec — спецификация IPFS Amino DHT.
• Ethereum Discovery v5 — discv5 — документация Discovery v5.

Библиотеки на Nim

• nim-eth — Ethereum P2P-протоколы, включая Kademlia и Discovery v5.
• nim-libp2p — реализация libp2p на Nim.
• nwaku — реализация протокола Waku на Nim.
• nimbus-eth2 — Ethereum Beacon Chain клиент на Nim.

Тема 7. Другие алгоритмы DHT

Зачем знать альтернативы

Kademlia — не единственный алгоритм DHT. В начале 2000-х почти одновременно появились четыре ключевых протокола: Chord, CAN, Pastry и Tapestry. Каждый решает ту же задачу — эффективный поиск в распределённой среде — но с разной топологией и метрикой.

Знать их полезно по нескольким причинам:

• понимание альтернатив помогает глубже осознать выбор, стоящий за Kademlia;
• в некоторых системах используются идеи из нескольких DHT;
• на собеседованиях и в научных работах часто спрашивают именно о Chord.

Chord: кольцо и пальцевая таблица

Основная идея

Chord (2001, авторы Ion Stoica и др., MIT) организует узлы в логическое кольцо по модулю 2^m, где m — длина идентификатора в битах. Каждый узел отвечает за ключи между ним и его предшественником (predecessor) по кольцу.

         Узел 1
        /       \
    Узел 56     Узел 8
      |           |
    Узел 42     Узел 14
        \       /
         Узел 21

Ключ K=17 → ответственный: Узел 21 (первый по часовой стрелке после 17)

Преемник и предшественник

Каждый узел знает своего преемника (successor) — следующего по кольцу. Наивный поиск: передаём запрос по цепочке преемников, пока не дойдём до ответственного узла. Но это O(N) шагов.

Пальцевая таблица (Finger Table)

Для ускорения поиска каждый узел хранит пальцевую таблицу — m записей, где i-я запись указывает на узел, ответственный за точку (selfId + 2^i) mod 2^m.

Для узла с ID=1, m=7 (пространство 0..127):
Finger[0] → successor(1 + 1)   = successor(2)    → Узел 8
Finger[1] → successor(1 + 2)   = successor(3)    → Узел 8
Finger[2] → successor(1 + 4)   = successor(5)    → Узел 8
Finger[3] → successor(1 + 8)   = successor(9)    → Узел 14
Finger[4] → successor(1 + 16)  = successor(17)   → Узел 21
Finger[5] → successor(1 + 32)  = successor(33)   → Узел 42
Finger[6] → successor(1 + 64)  = successor(65)   → Узел 56

При поиске узел выбирает из пальцевой таблицы запись, ближайшую к ключу, но не перескакивающую через него. За O(log N) шагов запрос доходит до ответственного узла.

Реализация на Nim

const M = 160  # длина ID в битах

type
  ChordNode = object
    id: NodeId
    predecessor: PeerInfo
    successor: PeerInfo
    fingerTable: array[M, PeerInfo]

proc findSuccessor(node: ChordNode, key: NodeId): PeerInfo =
  ## Упрощённый поиск преемника ключа.
  ## В реальности — итеративный/рекурсивный запрос по сети.
  if isInRange(key, node.id, node.successor.id):
    return node.successor
  else:
    # Ищем в пальцевой таблице узел, ближайший к key,
    # но не перепрыгивающий через него.
    let closest = closestPrecedingFinger(node, key)
    # Рекурсивно спрашиваем этот узел.
    return sendFindSuccessor(closest, key)

proc closestPrecedingFinger(node: ChordNode, key: NodeId): PeerInfo =
  ## Из пальцевой таблицы выбираем узел,
  ## максимально близкий к key, но перед ним.
  for i in countdown(M - 1, 0):
    if isInRange(node.fingerTable[i].id, node.id, key):
      return node.fingerTable[i]
  return PeerInfo(id: node.id)

Плюсы и минусы Chord

Pastry: маршрутизация по префиксу

Основная идея

Pastry (2001, авторы Antony Rowstron и Peter Druschel) использует маршрутизацию по совпадающему префиксу. Идентификаторы интерпретируются как числа в системе счисления с основанием 2^b (обычно b=4, то есть шестнадцатеричные цифры).

На каждом шаге маршрутизации запрос передаётся узлу, у которого на одну цифру больше совпадает с искомым ключом.

Наш ID:    10233102
Ключ:      10234230

Шаг 1: мы знаем узел 1023xxxx → совпадение 4 цифры
Шаг 2: тот знает 10234xxx → совпадение 5 цифр
Шаг 3: тот знает 102342xx → совпадение 6 цифр
Шаг 4: тот знает 1023423x → совпадение 7 цифр
→ найден ближайший

Таблица маршрутизации Pastry

Каждый узел хранит три структуры:

1. Routing table — строки по уровням совпадения префикса. На уровне l хранятся узлы с l совпадающими цифрами, но различающейся (l+1)-й цифрой.
2. Leaf set — L ближайших узлов по числовому расстоянию (аналог successor/predecessor в Chord).
3. Neighborhood set — узлы, ближайшие по сетевой задержке (не по ID).

const
  Base = 16  # 2^b, b=4

type
  PastryRoutingRow = array[Base, PeerInfo]  # 16 записей

  PastryNode = object
    id: NodeId
    routingTable: seq[PastryRoutingRow]  # log_{16}(N) строк
    leafSet: seq[PeerInfo]               # L ближайших по ID
    neighborhoodSet: seq[PeerInfo]       # ближайшие по задержке

Плюсы Pastry

• Учитывает сетевую близость (locality) — маршруты физически короче.
• Среднее число хопов ≈ log_{2^b}(N), что при b=4 в 4 раза меньше, чем log_2(N).

CAN: многомерное пространство

Основная идея

CAN (Content Addressable Network, 2001, авторы Sylvia Ratnasamy и др.) организует пространство ключей как d-мерный тор (многомерное координатное пространство, «завёрнутое» на себя). Каждый узел «владеет» участком (зоной) этого пространства.

2D-пространство CAN:
┌────────┬────────┐
│ Узел A │ Узел B │
│        │        │
├────────┼────────┤
│ Узел C │ Узел D │
│        │        │
└────────┴────────┘

Ключ с координатами (0.7, 0.3) → попадает в зону Узла B.
Маршрутизация: перепрыгиваем от соседа к соседу по координатам.

Особенности

• Каждый узел знает только своих непосредственных соседей по каждому измерению.
• Число хопов: O(d * N^(1/d)), где d — число измерений.
• При малых d это хуже, чем O(log N), но при d = log N совпадает.
• Интересен для задач с многомерными ключами.

Tapestry: исторический родственник Pastry

Tapestry (2001, автор Ben Zhao и др., UC Berkeley) — алгоритм, похожий на Pastry по принципу префиксной маршрутизации, но разработанный независимо. Tapestry использует похожую таблицу маршрутизации с «суффиксной» навигацией. На практике используется реже, чем Pastry и тем более Kademlia, но исторически важен.

Сводная таблица

Почему победила Kademlia

На практике Kademlia оказалась самой популярной из всех DHT. Причины:

1. Симметричность метрики — упрощает поддержание таблиц, так как узлы взаимно обновляют информацию друг о друге при каждом контакте.
2. Одна операция lookup решает все задачи — не нужны отдельные протоколы стабилизации, как в Chord.
3. Устойчивость к churn — эмпирически лучше, чем у Chord, благодаря k-бакетам и предпочтению старожилам.
4. Простота реализации — четыре RPC, понятная структура данных.

Ключевые термины

Что почитать

Оригинальные статьи

• Chord: A Scalable Peer-to-peer Lookup Protocol — Stoica et al., 2001.
• Pastry: Scalable, Decentralized Object Location and Routing — Rowstron, Druschel, 2001.
• A Scalable Content-Addressable Network (CAN) — Ratnasamy et al., 2001.
• Kademlia Paper — Maymounkov, Mazieres, 2002.

Лекции и обзоры

• Princeton COS 418: DHT & Chord — слайды лекции.
• UCL: Distributed Hash Tables — Chord — лекция Brad Karp.
• Cornell CS 6410: Chord and DHT Routing Geometry — слайды.
• Кадемлия, Chord, Pastry — Medium — сравнительный обзор.

Тема 8. Ограничения и проблемы DHT

DHT — не серебряная пуля

DHT красиво решает задачу поиска в распределённой среде, но у неё есть серьёзные ограничения. Реальные системы сталкиваются с проблемами, которые в академических статьях часто опускаются или упоминаются вскользь.

Атака Sybil

Суть

Атака Sybil — злоумышленник создаёт множество узлов с поддельными идентификаторами. В Kademlia генерация ID обычно дешёвая (хеш случайных данных), поэтому ничто не мешает создать тысячи «фейковых» узлов.

Последствия

• Атакующий может занять значительную часть пространства ID.
• Его узлы попадают в k-бакеты честных участников.
• Маршрутизация запросов начинает проходить через узлы злоумышленника.

# Пример: злоумышленник генерирует ID, близкие к целевому ключу.
proc generateTargetedIds(targetKey: NodeId, count: int): seq[NodeId] =
  ## Создаём ID, максимально близкие к целевому ключу,
  ## чтобы стать «ответственными» за него.
  var result: seq[NodeId]
  for i in 0 ..< count:
    var fakeId = targetKey
    # Меняем только последние байты — остаёмся «близкими».
    fakeId[19] = byte(i and 0xFF)
    fakeId[18] = byte((i shr 8) and 0xFF)
    result.add(fakeId)
  return result

Защита

• Криптографическая привязка ID — ID вычисляется как хеш публичного ключа, создание ключей требует вычислительных затрат. Используется в S/Kademlia и libp2p.
• Proof-of-Work — для регистрации в сети нужно решить вычислительную задачу.
• Ограничение по IP — не более n узлов с одного IP-адреса в одном k-бакете.

Атака Eclipse

Суть

Атака Eclipse — частный случай Sybil-атаки, цель которой — окружить конкретный узел поддельными соседями. Если все записи в k-бакетах жертвы заменены на узлы атакующего, жертва оказывается полностью изолированной от реальной сети.

Последствия

• Жертва не может найти реальные данные.
• Все её запросы перехватываются.
• Атакующий может отдавать жертве поддельные данные.

Нормальная ситуация:
Жертва → [A, B, C, D, E] → реальная сеть

После Eclipse-атаки:
Жертва → [X1, X2, X3, X4, X5] → все узлы злоумышленника

Защита

• Предпочтение старожилам в k-бакетах (уже встроено в Kademlia) — новые узлы не вытесняют старых, пока те живы.
• Верификация маршрутов — проверка, что ответы FIND_NODE содержат реальные узлы.
• Множественные bootstrap-узлы — не полагаться на один источник начальных контактов.
• Disjoint path lookups (S/Kademlia) — поиск по нескольким независимым путям одновременно.

Отравление маршрутизации

Злоумышленный узел может намеренно возвращать некорректные данные в ответ на FIND_NODE: давать ID узлов, которые не являются ближайшими к запрошенному ключу, или вообще указывать на несуществующие узлы.

Это замедляет поиск или направляет его в тупик.

Защита

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

NAT и реальная сетевая инфраструктура

Проблема

Большинство домашних и мобильных устройств находятся за NAT (Network Address Translation) — маршрутизатором, который не пропускает входящие соединения. В Kademlia предполагается, что узлы могут отправлять друг другу UDP-пакеты, но NAT это усложняет.

Типы NAT

Решения

• UPnP / NAT-PMP — автоматическое открытие портов на маршрутизаторе.
• Hole punching — техника «пробивания» NAT через координирующий сервер.
• Relay-узлы — промежуточные узлы, пересылающие трафик.
• STUN/TURN серверы — стандартные протоколы обхода NAT.

type
  NatType = enum
    natFullCone
    natRestrictedCone
    natPortRestricted
    natSymmetric
    natUnknown

  NatInfo = object
    natType: NatType
    externalIp: string
    externalPort: uint16
    upnpAvailable: bool

proc canReceiveIncoming(info: NatInfo): bool =
  ## Можем ли мы принимать входящие соединения?
  return info.natType == natFullCone or info.upnpAvailable

Неравномерное распределение ID

В идеальной модели ID узлов распределены равномерно по пространству. На практике:

• Некоторые реализации не используют достаточно случайные ID.
• Злоумышленники могут намеренно выбирать ID.
• Естественная дисперсия приводит к «пустым» и «густым» участкам.

Это создаёт дисбаланс нагрузки: узлы в «густых» участках хранят мало ключей, а одинокие узлы в «пустых» — много.

Горячие ключи

Некоторые ключи запрашиваются значительно чаще других (например, популярный торрент-файл). Узлы, ответственные за эти ключи, испытывают непропорционально высокую нагрузку.

Решения

• Кэширование на пути — узлы, через которые проходит запрос, кэшируют результат и отдают его при следующих запросах.
• Расширенная репликация — популярные данные реплицируются на большее число узлов.

Задержки и асинхронность

DHT предполагает, что сообщения доставляются за разумное время. Реальная сеть добавляет:

• Задержки — от миллисекунд до секунд.
• Потери пакетов — UDP не гарантирует доставку.
• Таймауты — нужно решать, когда считать узел «мёртвым».

Всё это усложняет реализацию и требует тщательной настройки параметров (таймаутов, числа повторных попыток).

Гибридные подходы

Многие современные системы не используют «чистую» DHT, а комбинируют её с другими механизмами:

• Bootstrap-узлы — полуцентрализованные точки входа. Без них новый узел не сможет присоединиться.
• Gossip-протоколы — для быстрого распространения информации о новых узлах и событиях.
• Централизованные координаторы — для начальной настройки, мониторинга, обновлений.

Это компромисс: чистая децентрализация красива, но практическая надёжность требует некоторых централизованных элементов.

Ключевые термины

Что почитать

• S/Kademlia: A Practicable Approach Towards Secure Key-Based Routing — расширение Kademlia с защитой от Sybil и Eclipse.
• Analysis of Kademlia Under Churn — исследование устойчивости.
• RFC 6940 — RELOAD — стандарт P2P-оверлея с NAT-traversal.
• IPFS DHT Security — практические решения проблем безопасности в IPFS.
• Kademlia Visualization — визуализация помогает понять маршрутизацию и увидеть, как атаки влияют на структуру.

Тема 9. Пошаговый разбор Kademlia с кодом на Nim

Эта тема — первая из четырёх дополнительных, расширяющих основной курс. Здесь мы последовательно реализуем ключевые структуры Kademlia на Nim: от генерации ID до полного цикла FIND_NODE.

Общая архитектура

Kademlia-узел состоит из нескольких компонентов:

┌──────────────────────────────────────┐
│           Kademlia Node              │
│                                      │
│  ┌────────────┐  ┌────────────────┐  │
│  │  Node ID   │  │ Routing Table  │  │
│  │ (160 бит)  │  │ (k-бакеты)    │  │
│  └────────────┘  └────────────────┘  │
│                                      │
│  ┌────────────┐  ┌────────────────┐  │
│  │ Data Store │  │  RPC Layer     │  │
│  │ key→value  │  │ UDP/TCP        │  │
│  └────────────┘  └────────────────┘  │
└──────────────────────────────────────┘

Разберём каждый компонент.

Шаг 1. Идентификаторы

Идентификатор — массив из 20 байт (160 бит). Нам понадобятся операции сравнения, XOR и преобразования в строку.

import std/[random, strutils, hashes, algorithm]

type
  NodeId* = array[20, byte]

proc randomId*(rng: var Rand): NodeId =
  ## Генерируем случайный 160-битный идентификатор.
  for i in 0 ..< 20:
    result[i] = byte(rng.rand(255))

proc fromHexString*(hex: string): NodeId =
  ## Создаём NodeId из шестнадцатеричной строки (40 символов).
  assert hex.len == 40, "Hex string must be 40 characters"
  for i in 0 ..< 20:
    result[i] = fromHex[uint8](hex[i*2 .. i*2+1])

proc toHex*(id: NodeId): string =
  ## Преобразуем NodeId в шестнадцатеричную строку.
  result = ""
  for b in id:
    result.add(b.toHex(2).toLowerAscii())

proc `$`*(id: NodeId): string =
  ## Сокращённое представление для отладки: первые 4 байта.
  id.toHex()[0 ..< 8] & "..."

proc `==`*(a, b: NodeId): bool =
  for i in 0 ..< 20:
    if a[i] != b[i]: return false
  return true

proc `<`*(a, b: NodeId): bool =
  ## Побайтовое сравнение — от старших к младшим.
  for i in 0 ..< 20:
    if a[i] < b[i]: return true
    if a[i] > b[i]: return false
  return false

Шаг 2. XOR-расстояние

proc xorDist*(a, b: NodeId): NodeId =
  ## XOR-расстояние между двумя идентификаторами.
  for i in 0 ..< 20:
    result[i] = a[i] xor b[i]

proc isZero*(id: NodeId): bool =
  ## Проверяем, является ли ID нулевым.
  for b in id:
    if b != 0: return false
  return true

proc leadingZeros*(id: NodeId): int =
  ## Число ведущих нулевых бит — определяет «порядок» расстояния.
  result = 0
  for b in id:
    if b == 0:
      result += 8
    else:
      # Считаем ведущие нули в байте.
      var mask = 0x80'u8
      while (b and mask) == 0:
        inc result
        mask = mask shr 1
      return

proc logDist*(a, b: NodeId): int =
  ## Логарифмическое расстояние: 159 - leadingZeros(a XOR b).
  ## Результат от 0 (самые близкие) до 159 (самые далёкие).
  let d = xorDist(a, b)
  if d.isZero: return 0
  return 159 - d.leadingZeros

Проверим

var rng = initRand(42)
let a = rng.randomId()
let b = rng.randomId()
echo "A = ", a
echo "B = ", b
echo "dist(A,B) = ", xorDist(a, b)
echo "logDist   = ", logDist(a, b)
echo "dist(A,A) = ", xorDist(a, a)  # нулевой — расстояние до себя = 0

Шаг 3. Информация об узле

import std/times

type
  PeerInfo* = object
    id*: NodeId
    ip*: string
    port*: uint16
    lastSeen*: Time  # когда последний раз отвечал на запросы

proc newPeer*(id: NodeId, ip: string, port: uint16): PeerInfo =
  result.id = id
  result.ip = ip
  result.port = port
  result.lastSeen = getTime()

proc touch*(peer: var PeerInfo) =
  ## Обновляем время последнего контакта.
  peer.lastSeen = getTime()

Шаг 4. K-бакет

K-бакет — упорядоченный список до k узлов. Самые давно виденные — в начале, самые свежие — в конце.

const
  K* = 20  # максимум узлов в бакете

type
  KBucket* = object
    nodes*: seq[PeerInfo]

  AddResult* = enum
    arAdded       # узел добавлен
    arUpdated     # узел уже был, обновлён
    arFull        # бакет полон, нужен ping старожила
    arSelf        # попытка добавить самого себя

proc len*(b: KBucket): int = b.nodes.len
proc isFull*(b: KBucket): bool = b.nodes.len >= K

proc findIndex*(b: KBucket, id: NodeId): int =
  ## Ищем узел в бакете по ID. Возвращаем -1, если не нашли.
  for i, peer in b.nodes:
    if peer.id == id: return i
  return -1

proc addOrUpdate*(b: var KBucket, peer: PeerInfo): AddResult =
  ## Пытаемся добавить узел в бакет.
  let idx = b.findIndex(peer.id)

  if idx >= 0:
    # Узел уже есть — перемещаем в конец (обновляем).
    var updated = b.nodes[idx]
    updated.touch()
    b.nodes.delete(idx)
    b.nodes.add(updated)
    return arUpdated

  if b.isFull:
    # Бакет полон — возвращаем arFull.
    # Вызывающий код должен сделать ping самому старому узлу.
    return arFull

  # Есть место — добавляем.
  b.nodes.add(peer)
  return arAdded

proc replaceLeastRecent*(b: var KBucket, newPeer: PeerInfo) =
  ## Заменяем самый старый узел (первый в списке) на нового.
  if b.nodes.len > 0:
    b.nodes.delete(0)
  b.nodes.add(newPeer)

proc oldest*(b: KBucket): PeerInfo =
  ## Самый давно виденный узел (первый в списке).
  assert b.nodes.len > 0
  return b.nodes[0]

Шаг 5. Таблица маршрутизации

const
  IdBits* = 160

type
  RoutingTable* = object
    selfId*: NodeId
    buckets*: array[IdBits, KBucket]

proc newRoutingTable*(selfId: NodeId): RoutingTable =
  result.selfId = selfId
  # Бакеты инициализируются пустыми по умолчанию.

proc bucketFor*(rt: RoutingTable, nodeId: NodeId): int =
  ## Определяем индекс бакета для данного ID.
  return logDist(rt.selfId, nodeId)

proc addNode*(rt: var RoutingTable, peer: PeerInfo): AddResult =
  ## Добавляем узел в таблицу маршрутизации.
  if peer.id == rt.selfId:
    return arSelf  # не добавляем самого себя

  let idx = rt.bucketFor(peer.id)
  return rt.buckets[idx].addOrUpdate(peer)

proc findClosest*(rt: RoutingTable, target: NodeId, count: int = K): seq[PeerInfo] =
  ## Находим `count` узлов, ближайших к target, из нашей таблицы.
  var all: seq[PeerInfo]
  for bucket in rt.buckets:
    for node in bucket.nodes:
      all.add(node)

  all.sort do (a, b: PeerInfo) -> int:
    let da = xorDist(a.id, target)
    let db = xorDist(b.id, target)
    if da < db: -1
    elif db < da: 1
    else: 0

  let n = min(count, all.len)
  return all[0 ..< n]

proc totalNodes*(rt: RoutingTable): int =
  ## Общее число узлов в таблице.
  for bucket in rt.buckets:
    result += bucket.len

Шаг 6. Хранилище данных

type
  StoredValue* = object
    value*: string
    publishedAt*: Time
    expiresAt*: Time

  DataStore* = object
    data*: Table[NodeId, StoredValue]

proc store*(ds: var DataStore, key: NodeId, value: string,
            ttl: Duration = initDuration(hours = 24)) =
  let now = getTime()
  ds.data[key] = StoredValue(
    value: value,
    publishedAt: now,
    expiresAt: now + ttl
  )

proc get*(ds: DataStore, key: NodeId): (bool, string) =
  if key in ds.data:
    let item = ds.data[key]
    if getTime() < item.expiresAt:
      return (true, item.value)
  return (false, "")

proc removeExpired*(ds: var DataStore) =
  ## Удаляем просроченные записи.
  let now = getTime()
  var toRemove: seq[NodeId]
  for key, item in ds.data:
    if now >= item.expiresAt:
      toRemove.add(key)
  for key in toRemove:
    ds.data.del(key)

Шаг 7. Итеративный FIND_NODE

Полная реализация итеративного поиска с состоянием:

import std/sets

type
  LookupState = object
    target: NodeId
    candidates: seq[PeerInfo]     # все известные кандидаты
    queried: HashSet[NodeId]      # уже опрошенные
    responded: HashSet[NodeId]    # ответившие
    failed: HashSet[NodeId]       # не ответившие

proc initLookup(target: NodeId, seeds: seq[PeerInfo]): LookupState =
  result.target = target
  result.candidates = seeds
  # Сортируем по расстоянию до target.
  result.candidates.sort do (a, b: PeerInfo) -> int:
    let da = xorDist(a.id, target)
    let db = xorDist(b.id, target)
    if da < db: -1
    elif db < da: 1
    else: 0

proc nextToQuery(state: LookupState, count: int): seq[PeerInfo] =
  ## Выбираем до `count` ближайших ещё не опрошенных кандидатов.
  for c in state.candidates:
    if c.id notin state.queried:
      result.add(c)
      if result.len >= count:
        break

proc addResults(state: var LookupState, from_id: NodeId, nodes: seq[PeerInfo]) =
  ## Добавляем результаты ответа от узла.
  state.responded.incl(from_id)
  for node in nodes:
    if node.id notin state.queried:
      var exists = false
      for c in state.candidates:
        if c.id == node.id:
          exists = true
          break
      if not exists:
        state.candidates.add(node)
  # Пересортируем.
  state.candidates.sort do (a, b: PeerInfo) -> int:
    let da = xorDist(a.id, state.target)
    let db = xorDist(b.id, state.target)
    if da < db: -1
    elif db < da: 1
    else: 0

proc isComplete(state: LookupState): bool =
  ## Поиск завершён, если k ближайших уже опрошены.
  var count = 0
  for c in state.candidates:
    if c.id in state.responded:
      inc count
      if count >= K:
        return true
    elif c.id notin state.failed:
      return false  # есть неопрошенный кандидат, ближе чем k-й
  return true

proc bestResults(state: LookupState): seq[PeerInfo] =
  ## Возвращаем k ближайших ответивших.
  for c in state.candidates:
    if c.id in state.responded:
      result.add(c)
      if result.len >= K:
        break

Шаг 8. Сценарий STORE

proc storeInDht(selfId: NodeId, key: NodeId, value: string,
                rt: RoutingTable) =
  ## Полный цикл сохранения данных в DHT.

  # 1. Находим k ближайших к ключу узлов.
  let seeds = rt.findClosest(key, K)
  var state = initLookup(key, seeds)

  # 2. Итеративный поиск (в реальности — с сетевыми вызовами).
  while not state.isComplete():
    let batch = state.nextToQuery(Alpha)
    if batch.len == 0: break
    for peer in batch:
      state.queried.incl(peer.id)
      # let response = sendFindNode(peer, key)
      # state.addResults(peer.id, response.nodes)

  # 3. Отправляем STORE каждому из k ближайших.
  let targets = state.bestResults()
  for peer in targets:
    discard # sendStore(peer, key, value)

Собираем всё вместе: структура узла

type
  KademliaNode* = object
    id*: NodeId
    ip*: string
    port*: uint16
    routingTable*: RoutingTable
    dataStore*: DataStore

proc newKademliaNode*(ip: string, port: uint16): KademliaNode =
  var rng = initRand(epochTime().int64)
  result.id = rng.randomId()
  result.ip = ip
  result.port = port
  result.routingTable = newRoutingTable(result.id)

Сопоставление с реальными реализациями

Наш код — учебный. Вот как то же самое выглядит в промышленных реализациях на Nim:

Ключевые термины

Что почитать

• nim-eth: kademlia.nim — реальная реализация Kademlia на Nim, включая все структуры данных.
• nim-eth: routing_table.nim — современная версия таблицы маршрутизации (Discovery v5).
• The Kademlia Protocol Succinctly — бесплатная книга с пошаговой реализацией (C#, но логика переносима).
• bmuller/kademlia (Python) — чистая реализация на Python для сравнения.
• prettymuchbryce/kademlia (Go) — реализация на Go по оригинальной статье.

Тема 10. Практический гайд — реализация узла Kademlia

В предыдущей теме мы разобрали структуры данных. Теперь добавим сетевой слой: UDP-транспорт, формат сообщений, таймауты и процедуру bootstrap. Результат — минимальный, но работающий узел Kademlia.

Архитектура сетевого слоя

┌────────────────────────────────────┐
│          Application Layer         │
│  iterativeFindNode, store, get     │
├────────────────────────────────────┤
│           RPC Layer                │
│  encodePing, encodeFindNode, ...   │
│  handleRequest, handleResponse     │
├────────────────────────────────────┤
│          Transport Layer           │
│  UDP socket: send / receive        │
└────────────────────────────────────┘

Kademlia обычно работает поверх UDP — это быстрее TCP и проще для задач, где отдельные запросы невелики (десятки-сотни байт). Потеря отдельных пакетов обрабатывается на уровне приложения через таймауты и повторные попытки.

Формат сообщений

В учебной реализации определим простой бинарный формат. Каждое сообщение начинается с заголовка:

type
  MessageType* = enum
    mtPing = 0
    mtPong = 1
    mtFindNode = 2
    mtFindNodeReply = 3
    mtFindValue = 4
    mtFindValueReply = 5
    mtStore = 6

  MessageHeader* = object
    msgType*: MessageType
    transactionId*: uint32   # для сопоставления запроса и ответа
    senderId*: NodeId

  PingMessage* = object
    header*: MessageHeader

  FindNodeMessage* = object
    header*: MessageHeader
    targetId*: NodeId

  FindNodeReply* = object
    header*: MessageHeader
    nodes*: seq[PeerInfo]    # до k ближайших узлов

  StoreMessage* = object
    header*: MessageHeader
    key*: NodeId
    value*: string

Сериализация

В реальных системах используют Bencode (BitTorrent), Protobuf (libp2p) или RLP (Ethereum). Для учебных целей напишем минимальный вариант:

import std/streams

proc writeNodeId(s: Stream, id: NodeId) =
  s.write(id)

proc readNodeId(s: Stream): NodeId =
  discard s.readData(addr result, 20)

proc writePeerInfo(s: Stream, peer: PeerInfo) =
  s.writeNodeId(peer.id)
  s.write(uint16(peer.ip.len))
  s.write(peer.ip)
  s.write(peer.port)

proc readPeerInfo(s: Stream): PeerInfo =
  result.id = s.readNodeId()
  let ipLen = s.readUint16()
  result.ip = s.readStr(int(ipLen))
  result.port = s.readUint16()

proc encodeFindNode(txId: uint32, senderId, targetId: NodeId): string =
  let s = newStringStream()
  s.write(uint8(mtFindNode))
  s.write(txId)
  s.writeNodeId(senderId)
  s.writeNodeId(targetId)
  s.setPosition(0)
  return s.readAll()

proc encodeFindNodeReply(txId: uint32, senderId: NodeId,
                         nodes: seq[PeerInfo]): string =
  let s = newStringStream()
  s.write(uint8(mtFindNodeReply))
  s.write(txId)
  s.writeNodeId(senderId)
  s.write(uint16(nodes.len))
  for node in nodes:
    s.writePeerInfo(node)
  s.setPosition(0)
  return s.readAll()

UDP-транспорт

Nim предоставляет асинхронный ввод-вывод через модули asyncdispatch (стандартная библиотека) или chronos (используется в nim-eth и nim-libp2p). Здесь покажем оба варианта.

Вариант 1: стандартный asyncdispatch

import std/[asyncdispatch, asyncnet, nativesockets]

type
  UdpTransport = object
    socket: AsyncSocket
    bindAddress: string
    bindPort: uint16

proc newUdpTransport(address: string, port: uint16): UdpTransport =
  result.socket = newAsyncSocket(AF_INET, SOCK_DGRAM, IPPROTO_UDP)
  result.socket.bindAddr(Port(port), address)
  result.bindAddress = address
  result.bindPort = port

proc send(t: UdpTransport, data: string, address: string, port: uint16) {.async.} =
  await t.socket.sendTo(address, Port(port), data)

proc receiveLoop(t: UdpTransport,
                 handler: proc(data: string, fromAddr: string,
                               fromPort: uint16) {.async.}) {.async.} =
  ## Бесконечный цикл приёма сообщений.
  while true:
    let (data, addr_, port) = await t.socket.recvFrom(65535)
    await handler(data, addr_, uint16(port))

Вариант 2: chronos (используется в nim-eth)

# chronos — асинхронная библиотека от Status.
# Устанавливается через nimble: nimble install chronos
#
# import chronos
# import chronos/transports/datagram
#
# proc startNode(address: string, port: int) {.async.} =
#   let ta = initTAddress(address, port)
#   let dgram = newDatagramTransport(proc(transp: DatagramTransport,
#                                         remote: TransportAddress) {.async.} =
#     let msg = transp.getMessage()
#     # обработка сообщения...
#   , local = ta)

Обработка запросов

proc handleMessage(node: var KademliaNode, data: string,
                   fromAddr: string, fromPort: uint16) {.async.} =
  if data.len < 1: return

  let msgType = MessageType(data[0].uint8)
  let s = newStringStream(data)
  s.setPosition(1)  # пропускаем тип

  case msgType
  of mtPing:
    let txId = s.readUint32()
    let senderId = s.readNodeId()
    # Обновляем информацию об отправителе в таблице маршрутизации.
    let peer = newPeer(senderId, fromAddr, fromPort)
    discard node.routingTable.addNode(peer)
    # Отвечаем Pong.
    let reply = encodePong(txId, node.id)
    await node.transport.send(reply, fromAddr, fromPort)

  of mtFindNode:
    let txId = s.readUint32()
    let senderId = s.readNodeId()
    let targetId = s.readNodeId()
    # Обновляем отправителя в таблице.
    let peer = newPeer(senderId, fromAddr, fromPort)
    discard node.routingTable.addNode(peer)
    # Находим k ближайших к target.
    let closest = node.routingTable.findClosest(targetId, K)
    let reply = encodeFindNodeReply(txId, node.id, closest)
    await node.transport.send(reply, fromAddr, fromPort)

  of mtStore:
    let txId = s.readUint32()
    let senderId = s.readNodeId()
    let key = s.readNodeId()
    let valueLen = s.readUint16()
    let value = s.readStr(int(valueLen))
    # Сохраняем данные.
    node.dataStore.store(key, value)
    # Обновляем отправителя.
    let peer = newPeer(senderId, fromAddr, fromPort)
    discard node.routingTable.addNode(peer)

  else:
    discard

Таймауты и управление запросами

Каждый исходящий запрос должен ожидать ответа не бесконечно. Используем Future с таймаутом:

import std/tables

const
  RequestTimeout = 5000  # миллисекунды

type
  PendingRequest = object
    future: Future[FindNodeReply]
    sentAt: int64

  RequestManager = object
    pending: Table[uint32, PendingRequest]  # txId → ожидающий запрос
    nextTxId: uint32

proc newTxId(rm: var RequestManager): uint32 =
  result = rm.nextTxId
  inc rm.nextTxId

proc sendFindNodeAsync(node: var KademliaNode, peer: PeerInfo,
                        target: NodeId): Future[FindNodeReply] =
  let txId = node.requestManager.newTxId()
  let data = encodeFindNode(txId, node.id, target)

  let fut = newFuture[FindNodeReply]("findNode")
  node.requestManager.pending[txId] = PendingRequest(
    future: fut,
    sentAt: epochTime().int64
  )

  # Отправляем запрос.
  asyncCheck node.transport.send(data, peer.ip, peer.port)

  # Устанавливаем таймаут.
  addTimer(RequestTimeout, oneshot = true) do (fd: AsyncFD) -> bool:
    if txId in node.requestManager.pending:
      node.requestManager.pending[txId].future.fail(
        newException(IOError, "Request timed out"))
      node.requestManager.pending.del(txId)

  return fut

Процедура bootstrap

proc bootstrap(node: var KademliaNode,
               bootstrapNodes: seq[(string, uint16)]) {.async.} =
  ## Подключение к сети через bootstrap-узлы.

  # 1. Добавляем bootstrap-узлы в таблицу.
  for (ip, port) in bootstrapNodes:
    # Сначала ping, чтобы узнать их ID.
    let txId = node.requestManager.newTxId()
    let pingData = encodePing(txId, node.id)
    await node.transport.send(pingData, ip, port)
    # Ответ придёт асинхронно и обработается в handleMessage.

  # 2. Ждём немного, чтобы ответы пришли.
  await sleepAsync(2000)

  # 3. Ищем самого себя — заполняем таблицу.
  let selfLookup = await node.iterativeFindNodeAsync(node.id)
  echo "Bootstrap: нашли ", selfLookup.len, " узлов рядом с нами"

  # 4. Обновляем бакеты.
  for i in 0 ..< IdBits:
    if node.routingTable.buckets[i].len == 0:
      let randomTarget = randomIdInBucket(node.id, i)
      discard await node.iterativeFindNodeAsync(randomTarget)

  echo "Bootstrap завершён. Узлов в таблице: ",
       node.routingTable.totalNodes()

Периодические задачи

Узел должен регулярно выполнять фоновые задачи:

proc maintenanceLoop(node: var KademliaNode) {.async.} =
  ## Цикл обслуживания: обновление бакетов, очистка данных.
  while true:
    await sleepAsync(60_000)  # раз в минуту

    # 1. Удаляем просроченные данные.
    node.dataStore.removeExpired()

    # 2. Обновляем «протухшие» бакеты.
    let now = getTime()
    for i in 0 ..< IdBits:
      let bucket = node.routingTable.buckets[i]
      if bucket.len > 0:
        # Проверяем самого старого в бакете.
        let oldest = bucket.oldest()
        if (now - oldest.lastSeen) > initDuration(minutes = 15):
          # Пингуем — если не отвечает, удалим при следующем addNode.
          asyncCheck node.sendPingAsync(oldest)

    # 3. Переиздаём наши данные.
    # (Каждый час — повторяем STORE для своих ключей.)

Запуск узла

proc startNode(ip: string, port: uint16,
               bootstrapAddrs: seq[(string, uint16)]) {.async.} =
  var node = newKademliaNode(ip, port)
  echo "Узел запущен: ", node.id, " на ", ip, ":", port

  # Запускаем транспорт.
  node.transport = newUdpTransport(ip, port)

  # Запускаем приём сообщений.
  asyncCheck node.transport.receiveLoop(
    proc(data: string, fromAddr: string, fromPort: uint16) {.async.} =
      await node.handleMessage(data, fromAddr, fromPort)
  )

  # Bootstrap.
  if bootstrapAddrs.len > 0:
    await node.bootstrap(bootstrapAddrs)

  # Запускаем фоновые задачи.
  asyncCheck node.maintenanceLoop()

  # Узел работает — ждём.
  echo "Узел готов к работе."
  runForever()

# Пример запуска:
# waitFor startNode("0.0.0.0", 8000, @[("1.2.3.4", 8000'u16)])

Библиотеки для реальной реализации на Nim

Если вы хотите строить на основе существующего кода, а не с нуля:

Библиотеки на других языках

Если вы предпочитаете другой язык, вот наиболее зрелые реализации:

Ключевые термины

Что почитать

• BEP 5 — DHT Protocol — полная спецификация BitTorrent DHT с форматом сообщений.
• nim-eth Discovery v5 documentation — как инициализировать и запустить узел на Nim.
• Nim asyncdispatch — документация стандартного асинхронного I/O.
• chronos — асинхронная библиотека, используемая в nim-eth.
• Implementing Kademlia — Medium — пошаговый рассказ о реализации.

Тема 11. Безопасность DHT

Эта тема посвящена угрозам, с которыми сталкиваются DHT-сети, и механизмам защиты. Разберём атаки на уровне протокола, их последствия и конкретные контрмеры.

Модель угроз

В P2P-сети любой участник может быть злоумышленником. У нас нет центрального сервера, который проверяет «честность» узлов. Основные угрозы:

Атака Sybil: подробный разбор

Механизм

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

Целевая Sybil-атака

Более изощрённый вариант: атакующий генерирует ID, близкие к конкретному ключу. Тогда его узлы становятся «ответственными» за этот ключ и могут:

• блокировать доступ к данным (не отвечать на FIND_VALUE);
• отдавать поддельные данные;
• отслеживать, кто запрашивает этот ключ.

proc targetedSybilIds(targetKey: NodeId, count: int,
                       prefixBits: int): seq[NodeId] =
  ## Генерируем ID, совпадающие с ключом в первых prefixBits битах.
  var rng = initRand(42)
  for _ in 0 ..< count:
    var fakeId = targetKey
    # Меняем биты после prefixBits.
    let startByte = prefixBits div 8
    for j in startByte ..< 20:
      fakeId[j] = byte(rng.rand(255))
    result.add(fakeId)

Защита: привязка ID к криптографии

S/Kademlia (Baumgart & Mies, 2007) предлагает:

1. Node ID = hash(public_key) — ID привязан к криптографическому ключу. Нельзя выбрать произвольный ID, не сгенерировав подходящий ключ.
2. Crypto puzzle — для получения «хорошего» ID нужно решить вычислительную задачу. Это делает массовую генерацию ID дорогой.

import nimcrypto/sha2

proc generateSecureNodeId(publicKey: seq[byte]): NodeId =
  ## ID = SHA-256(publicKey), обрезанный до 160 бит.
  ## Привязка к ключу не позволяет выбирать ID произвольно.
  let hash = sha256.digest(publicKey)
  for i in 0 ..< 20:
    result[i] = hash.data[i]

proc verifyCryptoPuzzle(nodeId: NodeId, difficulty: int): bool =
  ## Проверяем, что ID удовлетворяет crypto puzzle:
  ## первые `difficulty` бит хеша ID должны быть нулями.
  let hash = sha256.digest(nodeId)
  var zeroBits = 0
  for b in hash.data:
    if b == 0:
      zeroBits += 8
    else:
      var mask = 0x80'u8
      while (b and mask) == 0:
        inc zeroBits
        mask = mask shr 1
      break
  return zeroBits >= difficulty

Дополнительные меры

• Ограничение по IP — в одном k-бакете не более n узлов с одного IP (или подсети /24). Реализовано в nim-eth.
• Proof-of-Work при регистрации — новый узел должен решить задачу, прежде чем его примут.
• Социальная верификация — в закрытых сетях узлы добавляются только по приглашению.

Атака Eclipse: подробный разбор

Механизм

Eclipse — это Sybil-атака, нацеленная на конкретную жертву. Цель — заполнить все k-бакеты жертвы поддельными узлами, чтобы полностью контролировать её взаимодействие с сетью.

Почему Kademlia частично устойчива

Стратегия «предпочтения старожилам» в k-бакетах — встроенная защита: если бакет полон и все узлы в нём живы, новый узел (даже поддельный) не будет добавлен. Атакующий должен дождаться, пока старые узлы сами уйдут.

Усиление защиты

Disjoint path lookups (S/Kademlia) — при поиске запускаются несколько независимых маршрутов. Каждый маршрут начинается с разных узлов из разных бакетов. Даже если атакующий контролирует один путь, другие приведут к реальным узлам.

const DisjointPaths = 3  # число независимых путей

proc disjointLookup(node: KademliaNode, target: NodeId): seq[PeerInfo] =
  ## Запускаем несколько независимых поисков из разных начальных точек.
  var allResults: seq[PeerInfo]

  # Берём начальные узлы из разных бакетов.
  let closest = node.routingTable.findClosest(target, K * DisjointPaths)

  # Делим на DisjointPaths непересекающихся групп.
  for path in 0 ..< DisjointPaths:
    var seeds: seq[PeerInfo]
    for i in countup(path, closest.len - 1, DisjointPaths):
      seeds.add(closest[i])

    # Каждый путь ищет независимо.
    let pathResult = iterativeFindNode(node.id, target, seeds)
    allResults.add(pathResult)

  # Объединяем и сортируем результаты.
  allResults.sort do (a, b: PeerInfo) -> int:
    let da = xorDist(a.id, target)
    let db = xorDist(b.id, target)
    if da < db: -1
    elif db < da: 1
    else: 0

  # Убираем дубликаты и возвращаем k лучших.
  var seen: HashSet[NodeId]
  for peer in allResults:
    if peer.id notin seen:
      seen.incl(peer.id)
      result.add(peer)
      if result.len >= K:
        break

Отравление контента

Злоумышленник может ответить на FIND_VALUE поддельными данными. Без дополнительной проверки запрашивающий узел не отличит подделку от настоящих данных.

Защита: content addressing

Самый надёжный способ — адресация по содержимому: ключ является хешем данных. При получении значения запрашивающий может проверить: hash(value) == key. Если не совпадает — данные подделаны.

proc verifyContent(key: NodeId, value: string): bool =
  ## Проверяем, что значение соответствует ключу (content addressing).
  let computedKey = sha1Hash(value)
  return computedKey == key

Так работают BitTorrent (infohash — хеш метаданных) и IPFS (CID — хеш содержимого).

Подписанные записи

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

Пример: BEP 44 в BitTorrent DHT определяет хранение mutable-данных с подписью Ed25519.

Шифрование транспорта

В классической Kademlia сообщения передаются открытым текстом по UDP. Это позволяет:

• прослушивать запросы (узнать, кто что ищет);
• подменять ответы (MitM-атака).

Решения

• Ethereum Discovery v5 шифрует все сообщения с использованием сессионных ключей (AES-GCM). Перед обменом данными узлы выполняют рукопожатие (handshake).
• libp2p использует Noise Protocol или TLS 1.3 для шифрования соединений.

# Пример: структура зашифрованного сообщения в Discovery v5.
type
  DiscV5Packet = object
    maskingIv: array[16, byte]    # IV для маскирования заголовка
    maskedHeader: seq[byte]       # зашифрованный заголовок
    messageData: seq[byte]        # зашифрованные данные (AES-GCM)
    authTag: array[16, byte]      # тег аутентификации

IP-ограничения в таблице маршрутизации

Простая, но действенная мера: ограничить число узлов с одного IP-адреса (или подсети) в таблице маршрутизации.

import std/tables

type
  IpLimiter = object
    bucketLimit: int          # макс. узлов с одного IP в бакете
    tableLimit: int           # макс. узлов с одного IP во всей таблице
    bucketCounts: Table[string, int]
    tableCounts: Table[string, int]

proc canAdd(limiter: IpLimiter, ip: string, bucketIdx: int): bool =
  ## Проверяем, не превышены ли лимиты.
  let subnet = ip.rsplit('.', 1)[0]  # /24 subnet
  let bucketKey = $bucketIdx & ":" & subnet
  let bucketCount = limiter.bucketCounts.getOrDefault(bucketKey, 0)
  let tableCount = limiter.tableCounts.getOrDefault(subnet, 0)
  return bucketCount < limiter.bucketLimit and
         tableCount < limiter.tableLimit

Эта техника реализована в nim-eth routing_table.nim через ipLimitInc.

Сводная таблица защитных механизмов

Ключевые термины

Что почитать

• S/Kademlia: A Practicable Approach Towards Secure Key-Based Routing (PDF) — оригинальная статья с описанием crypto puzzles и disjoint lookups.
• BEP 44 — Storing Arbitrary Data in the DHT — mutable/immutable данные с подписями в BitTorrent DHT.
• libp2p Kademlia DHT Spec — спецификация с мерами безопасности.
• Sybil Attack — Wikipedia — общее описание атаки.
• Eclipse Attacks on Overlay Networks — академическая работа об Eclipse-атаках.
• nim-eth routing_table.nim — реализация IP-ограничений на Nim.

Тема 12. Сравнение DHT-алгоритмов

Заключительная тема курса. Здесь мы сравним четыре основных алгоритма DHT — Chord, Kademlia, Pastry и CAN — по ключевым характеристикам: число хопов, размер таблицы маршрутизации, устойчивость к churn, сложность реализации и практическое применение.

Критерии сравнения

Для объективного сравнения DHT-алгоритмов используют несколько ключевых метрик:

1. Число хопов при поиске — сколько сетевых запросов нужно, чтобы найти ключ.
2. Размер таблицы маршрутизации — сколько записей хранит каждый узел.
3. Устойчивость к churn — насколько хорошо работает при частой смене узлов.
4. Латентность — реальное время поиска (зависит от числа хопов и задержек сети).
5. Учёт сетевой близости — учитывает ли алгоритм физическую топологию сети.
6. Сложность реализации — насколько трудно написать корректную реализацию.

Chord

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

Сильные стороны

• Математическая элегантность — простая модель, легко анализировать формально.
• Хорошо изучен — сотни академических работ, подробные доказательства свойств.
• Гарантированное время поиска — строго O(log N) в стабильной сети.

Слабые стороны

• Асимметричная метрика — если A знает B, B не обязательно знает A. Это усложняет обновление таблиц.
• Протокол стабилизации — требует отдельного фонового протокола для поддержания кольца при churn.
• Линейная стоимость ухода узла — при уходе узла нужно обновить пальцевые таблицы нескольких других узлов.

Моделирование на Nim

type
  ChordNode = object
    id: uint64
    m: int                          # число бит в ID
    successor: ptr ChordNode
    predecessor: ptr ChordNode
    fingerTable: seq[ptr ChordNode] # m записей

proc inRange(id, start, finish: uint64, m: int): bool =
  ## Проверяем, что id ∈ (start, finish] на кольце mod 2^m.
  let modulo = 1'u64 shl m
  if start < finish:
    return id > start and id <= finish
  else:
    # Перекрытие через 0.
    return id > start or id <= finish

proc chordLookupHops(ring: seq[ChordNode], startIdx: int,
                      key: uint64): int =
  ## Считаем, сколько хопов нужно для поиска ключа на кольце.
  var hops = 0
  var current = startIdx
  while not inRange(key, ring[current].id,
                    ring[current].successor.id, ring[current].m):
    # Ищем ближайший finger, не перепрыгивающий через key.
    var best = ring[current].successor
    for i in countdown(ring[current].m - 1, 0):
      let finger = ring[current].fingerTable[i]
      if inRange(finger.id, ring[current].id, key, ring[current].m):
        best = finger
        break
    inc hops
    # Переходим к best (в реальности — сетевой запрос).
    current = findIndex(ring, best.id)
  return hops

Pastry

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

Сильные стороны

• Учёт сетевой близости — neighborhood set содержит физически близкие узлы, маршруты короче в реальной сети.
• Меньше хопов — при b=4 число хопов в 4 раза меньше, чем в Chord (log₁₆ N vs log₂ N).
• Leaf set — обеспечивает надёжную маршрутизацию даже при потере части таблицы.

Слабые стороны

• Большая таблица — при b=4 каждая строка содержит 16 записей, общий размер таблицы ≈ 16 · log₁₆ N + L.
• Сложнее реализовать — нужно поддерживать и таблицу маршрутизации, и leaf set, и neighborhood set.
• Менее распространён — мало production-реализаций.

type
  PastryNode = object
    id: string                      # hex-строка, например "10ab3f..."
    routingTable: seq[array[16, PeerInfo]]  # строки по уровням
    leafSet: seq[PeerInfo]          # L ближайших по числовому ID
    neighborhoodSet: seq[PeerInfo]  # ближайшие по задержке

proc sharedPrefixLen(a, b: string): int =
  ## Длина общего префикса двух hex-строк.
  result = 0
  for i in 0 ..< min(a.len, b.len):
    if a[i] == b[i]:
      inc result
    else:
      break

proc pastryRoute(node: PastryNode, key: string): PeerInfo =
  ## Один шаг маршрутизации Pastry.
  let l = sharedPrefixLen(node.id, key)

  # Если ключ в leaf set — маршрутизируем напрямую.
  for leaf in node.leafSet:
    if leaf.id.toHex() == key:
      return leaf

  # Иначе — ищем в строке l таблицы маршрутизации.
  let digit = fromHex[int](key[l .. l])  # l-я цифра ключа
  let entry = node.routingTable[l][digit]
  if entry.id != default(NodeId):
    return entry

  # Fallback: ищем в leaf set узел ближе, чем мы.
  for leaf in node.leafSet:
    if sharedPrefixLen(leaf.id.toHex(), key) > l:
      return leaf

  return PeerInfo()  # не нашли (ошибка)

CAN (Content Addressable Network)

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

Сильные стороны

• Маленькая таблица — каждый узел знает только 2d соседей (по два на каждое измерение).
• Естественно масштабируется — разбиение пространства при добавлении узла — простое деление зоны.
• Интересен для многомерных данных — если ключи имеют естественные координаты.

Слабые стороны

• Больше хопов — O(d · N^(1/d)) хуже, чем O(log N), при малых d. Для N=1 000 000 и d=2: ~2000 хопов vs ~20 у Kademlia.
• Балансировка зон — при уходе узла его зона «наследуется» соседом, со временем зоны становятся неравномерными.
• Мало используется на практике.

Kademlia

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

Сильные стороны

• Симметричная метрика — если A ↔ B близки, то оба обновляют информацию друг о друге. Нет нужды в отдельном протоколе стабилизации.
• Устойчивость к churn — k-бакеты и предпочтение старожилам дают высокую живучесть.
• Единый алгоритм lookup — FIND_NODE решает все задачи маршрутизации.
• Проверена практикой — BitTorrent DHT, IPFS, Ethereum.

Слабые стороны

• Большая таблица — k · 160 ≈ 3200 записей (на практике меньше, но больше, чем у Chord).
• Не учитывает физическую топологию — в отличие от Pastry.

Количественное сравнение

Число хопов при N = 1 000 000 узлов

Pastry даёт меньше всего хопов, но ценой большей таблицы маршрутизации. CAN требует высокой размерности для конкурентоспособности.

Размер таблицы маршрутизации при N = 1 000 000

Сравнение на Nim: симуляция

import std/[math, strformat]

proc compareHops(n: int) =
  ## Сравниваем ожидаемое число хопов для разных DHT при N узлах.
  let chord = log2(n.float) / 2.0
  let kademlia = log2(n.float)
  let pastry4 = log2(n.float) / log2(16.0)
  let can2 = 2.0 * pow(n.float, 1.0 / 2.0)
  let can10 = 10.0 * pow(n.float, 1.0 / 10.0)

  echo fmt"N = {n}:"
  echo fmt"  Chord:       {chord:.1f} хопов"
  echo fmt"  Kademlia:    {kademlia:.1f} хопов"
  echo fmt"  Pastry(b=4): {pastry4:.1f} хопов"
  echo fmt"  CAN(d=2):    {can2:.0f} хопов"
  echo fmt"  CAN(d=10):   {can10:.1f} хопов"

compareHops(1_000)
compareHops(1_000_000)
compareHops(10_000_000)

Вывод:

N = 1000:
  Chord:       5.0 хопов
  Kademlia:    10.0 хопов
  Pastry(b=4): 2.5 хопов
  CAN(d=2):    63 хопов
  CAN(d=10):   20.0 хопов

N = 1000000:
  Chord:       10.0 хопов
  Kademlia:    20.0 хопов
  Pastry(b=4): 5.0 хопов
  CAN(d=2):    2000 хопов
  CAN(d=10):   39.8 хопов

N = 10000000:
  Chord:       11.6 хопов
  Kademlia:    23.3 хопов
  Pastry(b=4): 5.8 хопов
  CAN(d=2):    6325 хопов
  CAN(d=10):   50.1 хопов

Устойчивость к churn

Исследования показывают различную устойчивость алгоритмов к постоянной смене узлов:

Где что используется