Файл: Аннотация Цель данной работы предоставить первое описание блокчейнплатформы ton (The Open Network) и связанных с ней технологий одноранговых сетей, распределенного хранилища и хостинга..pdf

64 3.2. TON DHT: Распределенная хеш-таблица, подобная Kademlia
Например, клиент, желающий зафиксировать транзакцию в шардчейне, может захотеть найти валидатора или коллатора этого шардчейна или хотя бы какой-нибудь узел, который мог бы передать транзакцию клиента коллатору. Это можно сделать, посмотрев специальный ключ в TON DHT. Еще одно важное применение TON DHT состоит в том, что его можно использовать для быстрого заполнения таблицы соседних элементов нового узла (см. 3.1.7) просто путем поиска случайного ключа или адреса нового узла. Если узел использует проксирование и туннелирование для своих входящих датаграмм, он публикует идентификатор туннеля и его точку входа
(например, IP-адрес и порт UDP) в TON DHT; тогда все узлы, желающие отправить датаграммы на этот узел, сначала получат эту контактную информацию от DHT.
TON DHT является членом семейства распределенных хеш-таблиц, подобных
Kademlia [10].
3.2.1. Ключи TON DHT. Ключи TON DHT - это просто 256-битные целые числа. В большинстве случаев они вычисляются как SHA256 TL-сериализированного объекта
(см. 2.2.5), называемого прообразом ключа или описанием ключа. В некоторых случаях абстрактные адреса узлов сети TON (см. 3.1.1) также могут использоваться в качестве ключей TON DHT, потому что они также являются 256-битными, и они также являются хэшами TL-сериализированных объектов. Например, если узел не боится публиковать свой IP-адрес, его может найти любой, кто знает его абстрактный адрес, просто просмотрев этот адрес в виде ключа в DHT.
3.2.2. Значения DHT. Значения, присвоенные этим 256-битным ключам, по сути, представляют собой произвольные байтовые строки ограниченной длины.
Интерпретация таких байтовых строк определяется прообразом соответствующего ключа; обычно это известно как узлу, который ищет ключ, так и узлу, который хранит ключ.
3.2.3. Узлы DHT. Полупостоянные сетевые идентификаторы. Сопоставление ключа и значения TON DHT хранится на узлах DHT, по сути, всех участников сети TON. С этой целью любой узел Сеть TON (возможно, за исключением некоторых очень легких узлов), помимо любого количества эфемерных и постоянных абстрактных адресов, описанных в 3.1.1, имеет как минимум один полупостоянный адрес, который идентифицирует ее как члена TON DHT. Этот полупостоянный или DHT-адрес не их следует менять слишком часто, иначе другие узлы не смогли бы найти ключи, которые они ищут. Если узел не хочет раскрывать свою истинную личность, он генерирует отдельный абстрактный адрес, который будет использоваться только с целью участия в DHT. Однако этот абстрактный адрес должен быть общедоступным, поскольку он будет связан с IP-адресом и портом узла.
3.2.4. Расстояние Kademlia. Теперь у нас есть как 256-битные ключи, так и 256- битные (полупостоянные) адреса узлов. Мы вводим так называемое расстояние XOR или расстояние Kademlia dK на наборе 256-битных последовательностей, заданное формулой которое интерпретируется как 256-битное целое число без знака.
Здесь обозначает побитовое исключающее ИЛИ (XOR) двух битовых последовательностей одинаковой длины.
Расстояние Kademlia представляет собой метрику набора 2 256
всех 256-битных последовательностей. В частности, d
K
(x, y) = 0 тогда и только тогда, когда x = y, d
K
(x, y) = d
K
(y, x) и d
K
(x, z)
≤
dK (x, y) + dK (y, z). Другое важное свойство состоит в

65 3.2. TON DHT: Распределенная хеш-таблица, подобная Kademlia том, что на любом заданном расстоянии от x есть только одна точка: d
K
(x, y) = d
K
(x, y') подразумевает y = y'.
3.2.5. DHT, подобные Kademlia, и DHT TON. Мы говорим, что распределенная хеш- таблица (DHT) с 256-битными ключами и 256-битными адресами узлов является распределенной хеш-таблицей, подобной Kademlia, если ожидается, что она сохранит значение ключа K на s Kademlia - ближайших к K узлах (т. е. s узлов с наименьшим расстоянием Kademlia от их адресов до K).
Здесь s - небольшой параметр, скажем s = 7, необходимый для повышения надежности
DHT (если мы будем хранить ключ только на одном узле, ближайшем к K, значение этого ключа будет потеряно, если этот единственный узел переходит в автономный режим).
Согласно этому определению, TON DHT - это таблица DHT, подобная Kademlia. Она будет реализована по протоколу ADNL, описанному в п. 3.1.
3.2.6. Таблица маршрутизации Kademlia. Любой узел, участвующий в DHT, подобном Kademlia, обычно поддерживает таблицу маршрутизации Kademlia. В случае TON DHT он состоит из n = 256 шардчейнов, пронумерованных от 0 до n - 1. i-й сегмент будет содержать информацию о некоторых известных узлах
(фиксированное количество t «лучших» узлов и, возможно, некоторые дополнительные кандидаты), которые лежат на расстоянии Kademlia от 2
i до 2
i+1
- 1 от адреса узла a
32
. Эта информация включает их (полупостоянные) адреса, IP-адреса и порты UDP, а также некоторую информацию о доступности, такую как время и задержка последнего пинга.
Когда узел Kademlia узнает о любом другом узле Kademlia в результате некоторого запроса, он включает его в подходящую корзину своей таблицы маршрутизации, сначала в качестве кандидата. Затем, если некоторые из «лучших» узлов в этом сегменте выходят из строя (например, не отвечают на запросы проверки связи в течение длительного времени), они могут быть заменены некоторыми из кандидатов.
Таким образом, таблица маршрутизации Kademlia остается всегда заполненной.
Новые узлы из таблицы маршрутизации Kademlia также включаются в таблицу соседних узлов ADNL, описанную в 3.1.7. Если часто используется «лучший» узел из группы таблицы маршрутизации Kademlia, для облегчения шифрования датаграмм может быть установлен канал, описанный в 3.1.5.
Особенностью TON DHT является то, что таблица пытается выбрать узлы с наименьшими задержками приема-передачи в качестве «лучших» узлов для шардчейнов таблицы маршрутизации Kademlia.
3.2.7. (Сетевые запросы Kademlia). Узел Kademlia обычно поддерживает следующие сетевые запросы:
• PING - проверяет доступность узла.
• STORE (ключ, значение) — просит узел сохранить значение в качестве значения для ключа key. Для TON DHT запросы STORE немного сложнее (см.
3.2.9).
• FIND_NODE(key, l) - просит узел вернуть l ближайших к Kademlia известных узлов (из его таблицы маршрутизации Kademlia) ключу.
• FIND_VALUE(key, l) — То же, что и выше, но если узел знает значение, соответствующее ключу key, он просто возвращает это значение.
Когда какой-либо узел хочет найти значение ключа K, он сначала создает набор S из s' узлов (для некоторого небольшого значения s', скажем, s'= 5), ближайших к K
32
Если в сегменте достаточно много узлов, его можно дополнительно разделить, скажем, на восемь подсегментов в зависимости от четырех старших битов расстояния Kademlia. Это ускорит поиск DHT.

66 3.2. TON DHT: Распределенная хеш-таблица, подобная Kademlia относительно расстояния Kademlia среди всех известных узлов (т. е. они взяты из таблицы маршрутизации Kademlia). Затем каждому из них отправляется запрос
FIND_VALUE, и узлы, упомянутые в ответах, включаются в S. Затем узлам s из S, ближайшим к K, также отправляется запрос FIND_VALUE, если это не было сделано ранее, и процесс продолжается до тех пор, пока не будет найдено значение или пока множество S не перестанет расти. Это своего рода «направленный поиск» узла, ближайшего к K по отношению к расстоянию Kademlia.
Если необходимо установить значение некоторого ключа K, та же процедура выполняется для s'
≥
s с запросами FIND_NODE вместо FIND_VALUE, чтобы найти s ближайших узлов к K. После этого всем этим узлам отправляются запросы STORE.
В реализации подобной Kademlia таблицы DHT есть некоторые менее важные детали
(например, любой узел должен искать ближайшие к себе узлы, скажем, один раз в час, и повторно публиковать все сохраненные ключи к ним с помощью запросов STORE).
Мы пока будем игнорировать эти детали.
3.2.8. Загрузка узла Kademlia. Когда узел Kademlia подключается к сети, он сначала заполняет свою таблицу маршрутизации Kademlia, просматривая свой собственный адрес. Во время этого процесса он определяет s ближайших к себе узлов. Он может загружать из них все известные им пары (ключ, значение) для заполнения своей части
DHT.
3.2.9. Сохранение значений в TON DHT. Хранение значений в TON DHT немного отличается от обычной Kademlia-подобной таблицы DHT. Если необходимо сохранить значение, должен быть предоставлен не только сам ключ K для запроса
STORE, но и его прообраз, то есть TL-сериализированная строка (с одним из нескольких предопределенных TL-конструкторов в начале), содержащую «описание» ключа. Это описание ключа позже сохраняется в узле вместе с ключом и значением.
Описание ключа описывает «тип» сохраняемого объекта, его «владельца» и соответствующие «правила обновления» в случае будущих обновлений. Владелец обычно идентифицируется открытым ключом, включенным в описание ключа. Если он включен, обычно будут приниматься только обновления, подписанные соответствующим закрытым ключом. «Тип» хранимого объекта - это обычно просто байтовая строка. Однако в некоторых случаях он может быть более сложным - например, описание входного туннеля (см. 3.1.6) или набор адресов узлов.
«Правила обновления» тоже могут быть разными. В некоторых случаях они просто разрешают замену старого значения новым значением, при условии, что новое значение подписано владельцем (подпись должна быть сохранена как часть значения, которое позже проверяется любыми другими узлами после того, как они получат значение этого ключа). В других случаях старое значение так или иначе влияет на новое значение. Например, оно может содержать порядковый номер, а старое значение перезаписывается только в том случае, если новый порядковый номер больше (для предотвращения атак повторного воспроизведения).
3.2.10. Распространение «торрент-трекеров» и «сетевых специализированных
групп» в TON DHT. Еще один интересный случай, когда значение содержит список узлов - возможно, с их IP-адресами и портами или просто с соответствующими абстрактными адресами, - а «правило обновления» заключается во включении запрашивающей стороны в этот список при условии, что она может подтвердить свою идентичность.
Этот механизм можно использовать для создания распределенного «торрент- трекера», где все узлы, заинтересованные в определенном «торренте» (т. е. в определенном узле), могут найти другие узлы, которые заинтересованы в этом же торренте или уже имеют соответствующую копию.

67 3.2. TON DHT: Распределенная хеш-таблица, подобная Kademlia
TON Storage (см. 4.1.7) использует эту технологию для поиска узлов, у которых есть копия требуемого файла (например, зафиксированный снимок состояния шардчейна или старого блока). Однако более важная задача - создание «оверлейных подсетей многоадресной рассылки» и «сетевых специализированных групп» (см. 3.3). Идея состоит в том, что только некоторые узлы заинтересованы в обновлениях определенного шардчейна. Если количество шардчейнов становится очень большим, поиск даже одного узла, заинтересованного в одном и том же шарде, может стать сложным. Этот «распределенный торрент-трекер» предоставляет удобный способ поиска некоторых из этих узлов. Другой вариант - запросить их у валидатора, однако этот подход исключает масштабирование, и валидаторы могут решить не отвечать на такие запросы, поступающие от произвольных неизвестных узлов.