Описание работы хеш аблицы TON DHT

miron

New member
TON DHT - распределённая хеш-таблица. Описание принципа работы


Блокчейн TON предполагает реализацию DHT - распределённой хеш-таблицы. DHT таблица является Kademlia-подобной.

6

В абстрактном смысле, DHT ставит в соответствие 256-битным ключам некие бинарные значения произвольной длины. При этом ключи в таблице — это хеши от определённой TL-структуры (сами структуры тоже хранятся вместе с DHT). Это очень похоже на формирование адресов узлов — и они действительно могут присутствовать в DHT (например, по такому ключу может находиться IP-адрес узла соответствующего заданному абстрактному адресу, если он не скрывает его). Но в общем случае, «прообразы ключей» (их описания, key descriptions) — это метаданные, которые указывают на «владельца» записи в хеш таблице (то есть публичный ключ какого-то узла), тип хранимого значения и правила, по которым эта запись может впоследствии изменяться. Например, правило может разрешать изменять значение только владельцу — или запрещать изменение значения в меньшую сторону (чтобы защититься от replay-атак).

Кроме 256-битных ключей вводится понятие DHT-адресов. Разница с обычными адресами узлов в том, что DHT-адрес обязательно привязан к IP-адресу. Если узел не скрывает своего IP, он может использовать обычный адрес для DHT. Но чаще для нужд DHT будет заводиться отдельный, «полу-постоянный» адрес.


Над ключами и DHT-адресами вводится понятие расстояния — в этом всё совпадает с таблицами Kademlia— расстояние между ключами равно XOR (побитовому исключающему ИЛИ) от них. Как и в таблицах Kademlia, значение, соответствующее некоему ключу, должно храниться на s узлах, имеющих наименьшее расстояние до этого ключа (s тут — относительно небольшое число).

7

Для того, чтобы узел DHT мог взаимодействовать с другими такими узлами, он держит в памяти таблицу маршрутизации DHT — DHT- и IP-адреса узлов, с которыми он взаимодействовал до этого, сгруппированные по расстоянию до них. Таких групп 256 (они соответствуют старшему выставленному биту в значении расстояния — то есть узлы на расстоянии от 0 до 255 попадут в одну группу, от 256 до 65535 — в следующую, и
т.д.). Внутри каждой группы хранится ограниченное число «лучших» узлов (в плане пинга до них).


8


Каждый узел должен поддерживать несколько операций: сохранение значения для ключа, поиск узлов и поиск значений. Поиск узлов подразумевает выдачу по заданному ключу ближайших к нему узлов из таблицы маршрутизации; поиск значений — то же самое, за исключением ситуации, когда узлу известно значение для ключа (тогда он просто возвращает его). Соответственно, если узел хочет найти в DHT значение по ключу, он посылает запросы небольшому числу ближайших к этому ключу узлов из своей таблицы маршрутизации. Если среди их ответов нет искомого значения, но есть другие адреса узлов, то запрос повторяется уже к ним.


TON DHT может использоваться для различных целей, например — для реализации торрент-подобного хранилища файлов; для определения адресов узлов, реализующих определённые сервисы; для хранения информации о владельцах аккаунтов в блокчейне. Но самое важное применение — обнаружение узлов по их абстрактным адресам. Для этого адрес используется в качестве ключа, значение которого нужно найти. В результате запроса либо найдётся сам узел (если искомый адрес был его полу-постоянным DHT-адресом), либо значением окажется IP-адрес и порт для подключения — или же другой адрес, который следует использовать в качестве тоннеля-посредника
 
Последнее редактирование модератором:

cryptobro

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

Если я правильно понимаю идею, то TON DHT может применяться и для совершения сделок между двумя объектами внутри TON. По идее не нужно будет получать подтверждение от участников сети, и записывать его в блокчейн. Для этого можно создать собственную цепочку и проводить платежи внутри нее.
 
Последнее редактирование:
Сверху