Что такое Merkle Tree?
Merkle Tree: это структура данных, которая сжимает большой набор записей в один короткий отпечаток. Она позволяет доказать, что элемент находится в очень большом списке, проверив лишь несколько небольших частей, а не всё целиком. Представьте древо, где каждый родительский узел является сводкой по своим детям, и всё сводится к одному общему предку.
Говорят, что Merkle Tree «хранит» все транзакции. Не совсем так. Она хранит только компактные отпечатки транзакций, а дерево можно восстановить из исходных записей при необходимости.
Как работает Merkle Tree
Представьте блок платежей, которому нужен быстрый проверяемый итог. Вот как Merkle Tree работает простыми словами:
- Шаг 1: Начните со списка элементов, например транзакций, каждый из которых является листом дерева.
- Шаг 2: Превратите каждый элемент в короткий отпечаток с помощью функции хеширования.
- Шаг 3: Соседние отпечатки объединяют попарно, каждая пара смешивается и снова хешируется, чтобы получить родительский узел.
- Шаг 4: Повторяйте процесс попарного объединения и хеширования, пока не останется один верхний отпечаток. Это корень Merkle для этого набора.
- Шаг 5: Чтобы доказать, что элемент принадлежит набору, нужен только сам элемент и короткий путь из соседних отпечатков. Быстро и компактно.
Идея в том, что доказательства малы, а уверенность велика.
Почему Merkle Tree важен
Сжимая большие объёмы данных транзакций в один компактный отпечаток, Merkle Tree делает проверку быстрой и недорогой.
- Преимущество: Можно проверить включение без загрузки всего блока, экономя время и трафик.
- Комментарий: Это отражение текущего подхода в интернете: доверяй, но проверяй; от роскоши до публичных форумов.
- Актуальность: Вы встретите это в блоках Bitcoin, в квитанциях Ethereum, в allowlist для NFT, в раздачах токенов и в решениях типа rollup.
Если число листьев нечётное, во многих схемах последний элемент дублируют перед вычислением хешей по дереву. Также внимательно проверьте точный процесс хеширования, который использует ваша цепочка или библиотека, так как мелкие различия в правилах могут менять доказательства.
Основные характеристики Merkle Tree
Вот что делает её полезной и удобной:
- Эффективность: Доказательства остаются небольшими даже при росте объёма данных, поэтому лёгкие клиенты остаются лёгкими.
- Целостность: Измените один байт в листе, и изменение отразится наверху, что делает подделку очевидной.
- Корень: Всё сводится к одному Merkle root, который можно сохранить или подписать для последующей проверки.
Варианты
У Merkle Tree есть несколько распространённых вариантов, с которыми вы можете столкнуться:
- Двоичное: Классическое дерево на парах, используемое в блоках Bitcoin.
- Merkle Patricia: Подход на основе префиксного дерева для данных ключей и значений, применяемый в состоянии и квитанциях Ethereum.
- Разреженное: Большое индексированное дерево, где большинство листьев пусты, отлично подходит для компактных доказательств наличия и отсутствия элементов.
- Verkle: Более молодой родственник с более короткими доказательствами при широкой ветвистости, рассматривается для возможных будущих обновлений.
Доказательства Merkle Tree надёжны только настолько, насколько надёжен заголовок или контрольная точка, которой вы доверяете. Если вы принимаете неверный корень, даже самое аккуратное доказательство ничего не доказывает.
Пример
Лёгкий кошелёк в стиле Bitcoin может проверить ваш платёж, проверив короткий путь хешей от вашей транзакции до заголовка блока, без загрузки всей истории транзакций.
Интересный факт
Ральф Меркл набросал эту идею в конце семидесятых как студенческий проект, и она ещё долго оставалась в академических кругах, прежде чем Сатоши использовал её в Bitcoin. Доказательство того, что хорошие идеи сохраняют ценность со временем.
Итог
Вывод: Merkle Tree даёт быстрые компактные доказательства того, что элемент принадлежит большому набору, без лишней нагрузки и без загрузки всего содержимого.