Merkle- и Verkle-деревья являются важнейшими элементами инфраструктуры блокчейна.
- Merkle-деревья (деревья Меркла) идеально подходят для легких криптокошельков, верификации транзакций и минимизации нагрузки на пользователей.
- Verkle-деревья (деревья Веркла) — это следующий шаг в развитии криптографии и масштабируемости Ethereum, обеспечивающий более быстрые и компактные доказательства при обработке больших объемов данных.
Зачем нужны Merkle- и Verkle-деревья в блокчейне:
- Деревья Меркла активно применяются в блокчейне Bitcoin и других криптовалютах для защиты целостности данных.
- Деревья Веркла становятся особенно актуальными для масштабируемости Ethereum и внедрения обновлений, связанных с снижением размера доказательств.
Что такое Merkle-деревья и как они работают?
Merkle-дерево — это бинарное дерево, использующее криптографические хэш-алгоритмы.
Хэш-дерево, также известное как дерево Меркла, содержит помеченные листовые узлы с хэшами блоков данных. Узлы, не являющиеся листьями, содержат хэши, вычисленные на основе хэшей дочерних узлов.
Каждый узел в Merkle-дереве формирует хэш, который рекурсивно зависит от всех характеристик в поддереве, исходящем из этого узла. Листья дерева вычисляют хэши на основе собственных данных, а родительские узлы — на основе конкатенации хэшей дочерних узлов слева направо.
Структура Merkle-дерева
Merkle-деревья разработал Ральф Меркл* в 1988 году для создания более надежных цифровых подписей. Merkle-деревья позволяют эффективно проверять целостность и достоверность данных при минимальных требованиях к памяти для верификации. К тому же они занимают гораздо меньше места на диске по сравнению с другими структурами данных, что является одним из главных преимуществ Merkle-деревьев.
*Ральф Чарльз Меркл — американский учёный-компьютерщик, криптограф, математик, специалист в области информатики, изобретатель, известный работами в области криптосистем с открытым ключом и хеширования, один из изобретателей криптографии с открытым ключом.
Разработал алгоритм для создания надёжных цифровых подписей, который назван его именем. На этом принципе основаны блокчейны криптовалют и другие криптографические конструкции. Первым придумал математически безопасный обмен криптографическими ключами по открытому каналу. Автор фундаментального труда «Кинематика самовоспроизводящихся машин».
Merkle-деревья в Ethereum
Блокчейн Ethereum применяет особый тип дерева Меркла — Merkle Patricia Trie. Это структура данных, позволяющая хранить все пары (ключ, значение) и проверять их криптографически.
В Ethereum все основные данные, включая состояние смарт-контрактов, хранятся в глобальном состоянии через Merkle Patricia Trie. Каждая транзакция в блоке записывается в отдельное дерево транзакций, а подтверждения — в отдельное дерево квитанций. Эти структуры обновляются при каждом новом блоке.
Признаки Merkle-дерева
Merkle-дерево состоит из трёх ключевых компонентов: листовых узлов, внутренних узлов и корня Merkle. В блокчейне в листьях дерева находятся хэши транзакций (TXID), видимые через блок-эксплорер. Над листами находятся промежуточные узлы, хранящие хэши пар нижестоящих узлов.
С каждым уровнем дерево сужается: число узлов уменьшается вдвое, пока не останется два, образующих последний хэш — корень Merkle. Сравнивая этот корень в блоке и заголовке, можно быстро определить факт манипуляции.
Доказательства Merkle (Merkle proof) содержат значение и набор хэшей, необходимых для восстановления корня. Они применяются в SPV-верификации (Simple Payment Verification), позволяя подтверждать транзакции без загрузки всего блокчейна. Это используется в мобильных криптокошельках и легких нодах.
Что такое Verkle-деревья и как они работают?
Verkle-деревья, как и Merkle-деревья, используются для хранения большого объема данных в структуре, где можно быстро создать компактное доказательство (witness) подлинности данных, проверяемое через корень дерева.
Главное преимущество Verkle-деревьев заключается в эффективности размера доказательства. Например, чтобы доказать существование элемента в дереве с миллиардами записей, Verkle-дерево требует менее 150 байт, тогда как традиционное Merkle-дерево — около 1 килобайта. Это достигается благодаря применению многочленов и схем Polynomial Commitments, описывающих данные с помощью полиномиальных функций.
Кто разработал Verkle-деревья
Verkle-деревья были предложены Джоном Кузмаулом* в 2018 году. Они позволяют значительно сократить размер криптографических доказательств (доказательств включения) путем использования полиномиальных обязательств. В проверке данных это часто в 6–8 раз эффективнее Merkle‑деревьев и в десятки раз эффективнее Merkle Patricia Trie, применяемых в Ethereum.
Несмотря на высокую технологичность, они пока не так широко известны, как другие криптографические структуры.
Структура дерева Веркла схожа с Merkle Patricia Trie, применяемым в Ethereum. Каждый узел может быть:
- пустым;
- листом с ключом и значением;
- промежуточным узлом с фиксированным числом дочерних элементов (шириной дерева).
*Джон Кузмаул (John Kuszmaul) — молодой учёный, специализирующийся на алгоритмах и криптографии, один из авторов концепции Verkle trees, используемой для повышения эффективности доказательств состояния блокчейн-сетей. Сейчас проводит исследования в MIT CSAIL, входит в группы по алгоритмам, криптографии, теориям сложности, распределённым системам и машинному обучению.
Соавтор нескольких важных статей на ведущих конференциях: PODC'24, STOC'22, SPA'22 и Sosa'24. В их числе: Fully Energy-Efficient Randomised Backoff, The Optimal Time/Space Trade-Off for Hash Tables и Modern Hashing Simplified.
Структура Verkle-дерева
Хэш промежуточного узла рассчитывается на основе значений всех дочерних узлов.
Главное отличие от Merkle-деревьев в том, что Verkle-деревья могут быть более широкими, что делает доказательства короче. Однако чрезмерное увеличение ширины может увеличить время их генерации, поэтому важно соблюдать баланс.
Преимущества Verkle-деревьев в сравнении с Merkle-деревьями
Verkle-деревья обеспечивают значительно меньшие размеры доказательств при больших объемах данных, чем Merkle-деревья. Это существенно снижает нагрузку на сеть.
Verkle-доказательство позволяет подтвердить достоверность большого объема данных через корень дерева. Вместо передачи всех «сестринских» узлов, как в Merkle-деревьях, Verkle-доказательство требует лишь указания пути и небольшого дополнительного объема информации. Это делает их в 6–8 раз компактнее Merkle-доказательств и более чем в 20–30 раз меньше, чем доказательства на базе Patricia-три в Ethereum.
В Verkle-деревьях провайдер доказательства демонстрирует связи между узлами от листа к корню через единую цепочку, без необходимости в передаче всей структуры дерева.
Сравнение Merkle- и Verkle-деревьев
Существует множество различий между этими структурами данных:
- В Merkle-деревьях для доказательства требуется полный набор «сестринских» узлов.
- В Verkle-деревьях достаточно лишь пути от листа до корня и минимального набора информации.
- Verkle-деревья используют векторные коммитменты вместо хэшей, что существенно снижает объем данных.
- Merkle-доказательства проще обновлять по частям, а Verkle-доказательства требуют изменения всей полиномиальной функции.
- Verkle-деревья более эффективны при широких ветвлениях, что улучшает масштабируемость блокчейна Ethereum.
Развитие и внедрение Verkle-деревьев в Ethereum обещает сделать сеть более эффективной, масштабируемой и доступной для миллионов пользователей по всему миру.