К основному содержанию
T TON Adoption
EN
← Словарь
NODE/03 · Term

Дерево Меркла

Бинарное дерево, в котором листья — хэши данных, а каждый внутренний узел — хэш конкатенации двух дочерних. В TON используется для merkle-proof: lite-клиент может доказать факт без скачивания всего состояния.

Синонимы: merkle tree, дерево меркла, merkle-дерево

Дерево Меркла (Merkle tree) — структура данных, изобретённая Ральфом Мерклом в 1979 году. Листья — это хэши блоков данных, каждый внутренний узел — хэш своих детей. На вершине — один корневой хэш (Merkle root), компактно представляющий весь набор данных.

Зачем это нужно

Главное свойство: можно компактно доказать, что элемент входит в дерево, не предоставляя само дерево. Доказательство (merkle proof) — это путь от листа до корня: O(log N) хэшей вместо O(N) данных.

Это критично для блокчейнов:

  • Lite-клиент на телефоне не хранит весь блокчейн TON, но хочет проверить, что его транзакция включена в блок. Сервер присылает merkle proof — несколько хэшей. Клиент пересчитывает корень и сверяет с known-good корнем блока. Если совпало — транзакция точно в блоке.
  • Мост между блокчейнами проверяет состояние одного чейна на другом, оперируя только корневыми хэшами.

В TON

TON активно использует merkle-структуры в нескольких местах:

  • State. Состояние всего блокчейна организовано как одно гигантское дерево хэшированных ячеек. Корневой хэш state входит в хэш блока.
  • Pruned cells. Ячейка, чьи дети заменены на их хэши, — это обрезанная ветвь дерева. Lite-сервер так возвращает merkle proof: основные данные есть, остальное — pruned.
  • Merkle update / merkle proof cells. Специальные типы ячеек в TVM для встраивания доказательств в transactions.

Простой пример

Допустим, есть транзакции T1, T2, T3, T4. Дерево:

        Root
       /    \
     H12    H34
    /  \    /  \
  H1   H2  H3   H4

Каждый Hx — это хэш транзакции, H12 = hash(H1 ‖ H2), Root = hash(H12 ‖ H34).

Чтобы доказать включение T1, достаточно прислать H2, H34 и сам T1. Получатель пересчитывает: H1’ = hash(T1), H12’ = hash(H1’ ‖ H2), Root’ = hash(H12’ ‖ H34). Если Root’ = известному Root — доказательство верное.

Прикладные следствия

Merkle-деревья — основа всех «компактных доказательств» в крипте: SPV-клиенты Bitcoin, ZK-rollups, кросс-чейн bridges, IBC в Cosmos. В TON это конкретно lite-протокол, на котором работают Tonkeeper, Tonscan, Tonviewer и любой неполный клиент.

См. также