15 сентября 2022

Дерево Меркла: вот почему Optimistic Rollups будут безопасными

Анонс доказательств Меркла прошел незаметно: в описании обновления Jakarta им уделили одну строчку, а в документации — страницу про формат доказательств. Поэтому мы расскажем обо всем по порядку.

Что такое дерево Меркла

Основа дерева Меркла — хеширование данных. Хеширование — это преобразование информации по специальному алгоритму, в результате которого получается уникальная строка определенной длины. Если повторно хешировать ту же информацию, то результат — хеш или чек-сумма — будет одинаковым. Если в файле изменился хоть один бит информации, то хеш тоже изменится.

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

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

Самый эффективный способ доказать, что все фрагменты соответствуют оригиналу — рекурсивно хешировать их в парах. Сначала хешировать отдельные фрагменты, затем — сумму хешей соседних пар, и повторять, пока не получится хеш всего множества. Эта структура называется деревом хешей или деревом Меркла. Если один фрагмент битый, то нода быстро его выявит через сравнение хешей в каждой последующей ветке.

Дерево Меркла состоит из трех элементов:

  • листья — изначальные фрагменты данных (DATA A, DATA B…);
  • ветки или узлы дерева (не путать с узлами блокчейна) — хеши предыдущих пар листьев или веток (ABC, BDE);
  • корень — хеш всего дерева (DFA).

Ноды в блокчейн-протоколе хранят в дереве Меркла все блоки и их хеши. Корень соответствует текущему состоянию всего блокчейна, то есть в нем захешированы балансы всех пользователей. В Tezos он называется Context Hash, и бейкеры включают его в заголовок каждого добытого блока.

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

Но это упрощенное объяснение. На деле структура Tezos более сложная и включает большое количество веток для оптимизации поиска и работы с данными.

Почему дерево Меркла важно для Optimistic Rollups

С помощью дерева Меркла можно быстро доказать, что какой-то фрагмент данных входит в указанный набор данных без раскрытия всех других фрагментов — это называется доказательством Меркла (Merkle Proof).

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

По расчетам команды Tarides, такое доказательство Меркла для 100 операций вмещается в 46 КБ, в то время как «реальное» доказательство со всеми транзакциями и балансами пользователей займет 3,4 ГБ.

Доказательство Меркла нужно для работы роллапов, так как оно позволяет L1-ноде за секунды убедиться в валидности операций в L2-чейне, даже если у L1-ноды нет полного L2-чейна. Или наоборот, доказать, что транзакция в L2-чейне ошибочна, и оператор роллапа пытается всех обмануть.

Вот так дерево Меркла сделает роллапы безопасными и честными для пользователей.

Подписывайтесь на социальные сети Tezos Ukraine, чтобы ничего не пропустить:

  1. Telegram-канал
  2. Facebook
  3. Twitter на русском и украинском
  4. Twitter на английском
  5. YouTube-канал
  6. Instagram
  7. LinkedIn

Изначально мы опубликовали этот материал в блоге Tezos Ukraine.