Анонс доказательств Меркла прошел незаметно: в описании обновления 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, чтобы ничего не пропустить:
- Telegram-канал
- Twitter на русском и украинском
- Twitter на английском
- YouTube-канал
Изначально мы опубликовали этот материал в блоге Tezos Ukraine.