Основные выводы
Дерево Меркла — это криптографическая структура данных, которая организует данные в пары хешей, объединяя их вверх по иерархии до тех пор, пока один хеш, корень Меркла, не будет представлять весь набор данных.
Доказательство Меркла позволяет сетям блокчейна проверять, включена ли транзакция в блок, без загрузки всего блока, используя компактное доказательство Меркла, масштабируемое логарифмически с количеством транзакций.
В Bitcoin в каждый заголовок блока встроен корень Меркла, что позволяет легковесным клиентам проверять транзакции, используя только заголовки блоков, а не весь блокчейн.
В Ethereum используется более сложная структура Merkle Patricia Trie для хранения балансов счетов и состояния смарт-контрактов, что делает возможным доказательство состояния для облегченных клиентов и агрегированных данных второго уровня.
Введение
Деревья Меркла — одна из основополагающих идей, обеспечивающих эффективность и проверяемость блокчейн-систем в масштабах. Они позволяют сетям обобщать целые наборы данных в единый криптографический отпечаток, сохраняя при этом возможность доказать, что конкретная транзакция или фрагмент информации включены в него. Чтобы понять, почему деревья Меркла важны в проектировании блокчейна, давайте рассмотрим, как они работают, как их используют различные сети и как новые структуры, такие как деревья Веркла, могут улучшить их в будущем.
Как работают деревья Меркла
Дерево Меркла, названное в честь учёного-компьютерщика Ральфа Меркла, запатентовавшего эту концепцию в 1979 году, — это структура данных, используемая для эффективного обобщения и проверки целостности больших наборов данных. В блокчейне деревья Меркла сжимают тысячи транзакций в одно компактное значение, хранящееся в заголовке блока.
Дерево строится снизу вверх с использованием криптографических хеш-функций. Каждый листовой узел содержит хеш отдельного элемента данных, например, транзакции. Затем эти листовые хеши объединяются в пары: хеш каждой пары вычисляется путем конкатенации двух дочерних хешей и хеширования результата. Этот процесс повторяется вверх, слой за слоем, пока на вершине не останется один хеш — корень Меркла.
Поскольку каждый родительский узел зависит от обоих своих дочерних узлов, любое изменение одного листа вызовет цепную реакцию вверх и приведет к образованию совершенно другого корня Меркла. Это свойство делает деревья Меркла эффективным инструментом для обнаружения изменений: если две копии набора данных образуют один и тот же корень Меркла, то с чрезвычайно высокой вероятностью эти наборы данных идентичны.
корни Меркла
Корень Меркла — это хеш фиксированного размера, обычно 32 байта (256 бит) в блокчейн-приложениях, который выступает в качестве цифрового отпечатка для всего набора данных. Заголовки блоков в большинстве блокчейн-сетей включают корень Меркла наряду с другими метаданными, такими как метки времени и хеш предыдущего блока, что позволяет уменьшить размер заголовков, но при этом криптографически гарантировать полный набор транзакций внутри блока.
Для простоты иллюстрации рассмотрим файл размером 8 ГБ, разбитый на восемь частей. Назовем эти фрагменты A, B, H и H. Каждый фрагмент затем обрабатывается хеш-функцией, в результате чего мы получаем восемь различных хешей.
Если вы вычислите хеш всех фрагментов, то, сравнив его с хешем исходного файла, вы узнаете, верно? Возможно, но это также может быть невероятно неэффективно. Если ваш файл содержит тысячи фрагментов, будете ли вы хешировать их все и тщательно сравнивать результаты?
Корень Меркла предлагает более элегантное решение. Возьмите каждую пару хешей, объедините их, а затем выполните хеширование. Вы получите хеши hA + hB, hC + hD, hE + hF и hG + hH, и в итоге получите четыре хеша.
Затем, после еще одного раунда хеширования, вы получите два результата: hABCD и hEFGH. Наконец, хешируйте оставшиеся два результата, чтобы получить главный хеш, и вы получите корень Меркла (или корневой хеш): hABCDEFGH.
Доказательства Меркла и верификация
Одной из наиболее практичных особенностей деревьев Меркла является возможность доказать принадлежность конкретного фрагмента данных к набору данных, не раскрывая весь набор данных. Это называется доказательством Меркла. Для проверки включения транзакции в блок облегченному клиенту достаточно самой транзакции, небольшого набора хешей соседних элементов вдоль пути к корню и корня Меркла из заголовка блока. Верификатор пересчитывает хеши вдоль пути и проверяет, совпадает ли результат с известным корнем. Если совпадает, транзакция математически доказывается как часть блока.
Рассмотрим сценарий, в котором необходимо проверить транзакцию, TXID которой равен hD. Если указан hC, можно вычислить hCD. Затем, используя hAB, вычислите hABCD. Наконец, с помощью hEFGH проверьте, совпадает ли полученный корень Меркла с корнем из заголовка блока. Если совпадает, это доказывает, что транзакция была включена в блок. Создать одинаковый хеш с разными данными практически невозможно.
В приведенном выше примере вам потребуется выполнить хеширование всего три раза. Без доказательства Меркла вам пришлось бы сделать это семь раз. Поскольку блоки в настоящее время содержат тысячи транзакций, использование доказательств Меркла значительно экономит время и вычислительные ресурсы.
Размер доказательства увеличивается логарифмически с количеством листьев: для миллиона транзакций (бинарное дерево глубиной 20) требуется всего около 20 хешей, что составляет примерно 640 байт. Именно это позволяет легковесным узлам, иногда называемым клиентами упрощенной проверки платежей (SPV), проверять транзакции без загрузки всего блокчейна, процесс, который в противном случае потребовал бы сотен гигабайт данных.
Деревья Меркла в блокчейн-сетях
Биткоины и проверка транзакций
В Биткоине заголовок каждого блока содержит 32-байтовый корень Меркла, который подтверждает все транзакции в этом блоке. Майнеры Биткоина строят дерево Меркла из включенных в него транзакций, и полученный корень встраивается в заголовок блока вместе с решением Proof of Work. Такая конструкция означает, что заголовка блока, обычно около 80 байт, достаточно для проверки того, что любая конкретная транзакция была включена в блок, без необходимости проверки других транзакций.
В предложении MAST (Merkelized Abstract Syntax Trees) Bitcoin также использует деревья Меркла, что позволяет представлять сложные условия расходования средств в скриптах Bitcoin в виде дерева Меркла. Раскрывать нужно только исполняемую ветвь скрипта, сохраняя неиспользуемые условия в тайне и уменьшая размер транзакции.
Эфириум и доказательства состояния
В Ethereum используется более сложный вариант, называемый деревом Меркла-Патриции, — гексаарная (16-сторонняя) древовидная структура, которая хранит балансы счетов, код контрактов и данные хранилища. В отличие от простого бинарного дерева Меркла, используемого для транзакций Bitcoin, дерево Меркла-Патриции предназначено для поддержки частых обновлений состояния: при изменении баланса счета необходимо пересчитать только путь от этого листа к корню, а не перестраивать все дерево.
Доказательства состояния, генерируемые на основе дерева Меркла-Патриции, позволяют облегченным клиентам Ethereum и роллапам второго уровня проверять балансы счетов и хранилище контрактов без запуска полного узла. Эти доказательства также необходимы для кроссчейн-мостов, которым необходимо проверять события в одной цепочке из другой.
Ограничения и перспективы развития
Хотя деревья Меркла обеспечивают эффективную проверку, размеры доказательств все же растут логарифмически с увеличением объема данных. В случае Ethereum, по мере роста состояния, количество свидетелей блока — доказательств, необходимых для проверки блока, — может достигать нескольких мегабайт. Это создает проблему масштабируемости для клиентов без состояния, которым необходимо получать и проверять эти доказательства для каждого блока.
Деревья Веркла, использующие векторные обязательства на основе полиномиальных (Кейт-Заверуча-Голдберг, или KZG) обязательств вместо традиционного хеширования, предлагают потенциальное решение. Группируя множество дочерних узлов под каждым узлом (коэффициент ветвления 256), деревья Веркла создают доказательства, размер которых практически постоянен, примерно 170 байт, независимо от размера набора данных. Ethereum активно разрабатывает интеграцию деревьев Веркла, и ожидается, что она будет внедрена в одном из будущих обновлений. Этот переход значительно снизит нагрузку на легкие клиенты и улучшит масштабируемость сети в целом.
Часто задаваемые вопросы
Что такое дерево Меркла простыми словами?
Дерево Меркла — это способ организации данных, при котором один небольшой фрагмент информации, корень Меркла, может представлять большой набор данных. Оно работает путем многократного хеширования пар данных до тех пор, пока не останется только один хеш, что позволяет проверить, принадлежит ли какой-либо конкретный элемент к множеству, не проверяя каждый элемент по отдельности.
Что такое корень Меркла?
Корень Меркла — это единственный хеш в вершине дерева Меркла. Он служит компактным цифровым отпечатком для всех данных, находящихся ниже него. В сетях блокчейна корень Меркла хранится в заголовке блока и подтверждает каждую транзакцию в этом блоке, что позволяет эффективно проверять, является ли транзакция частью блока.
Как работает доказательство Меркла?
Доказательство Меркла предоставляет транзакцию вместе с минимальным набором хешей соседних элементов, необходимых для пересчета пути от этой транзакции до корня Меркла. Верификатор хеширует транзакцию, объединяет ее с предоставленными соседними элементами в правильном порядке и проверяет, совпадает ли конечный результат с известным корнем Меркла в заголовке блока. Если совпадает, транзакция считается включенной в доказательство.
Почему деревья Меркла важны для блокчейна?
Деревья Меркла позволяют сетям блокчейна отделять заголовки блоков от полных данных транзакций. Легкий клиент может загрузить только заголовки блоков, примерно 80 байт на блок, и при этом проверить наличие транзакции, используя компактное доказательство Меркла. Без деревьев Меркла проверка транзакции потребовала бы загрузки всего блока или всей цепочки.
В чём разница между деревом Меркла и деревом Веркла?
Оба являются криптографическими аккумуляторами, используемыми для доказательства принадлежности к данным, но они используют разные математические методы. Деревья Меркла используют хеш-функции и создают доказательства, размер которых растет логарифмически с размером набора данных (O(log n)). Деревья Веркла используют полиномиальные (KZG) обязательства и создают доказательства, размер которых практически постоянен, составляя несколько сотен байт независимо от размера набора данных, что делает их более подходящими для доказательств состояния блокчейна в больших масштабах.
Заключительные мысли
Деревья Меркла являются краеугольным камнем архитектуры блокчейна, обеспечивая верификацию без необходимости доверия в масштабе. Сжимая весь блок транзакций в один 32-байтовый хеш, они позволяют участникам проверять данные, не загружая всё целиком, — принцип, лежащий в основе всего, от SPV-кошельков Bitcoin до доказательств состояния Ethereum и кроссчейн-мостов. По мере роста блокчейн-сетей новые криптографические структуры, такие как деревья Веркла, могут в конечном итоге дополнить или заменить деревья Меркла, но лежащая в их основе концепция — эффективная целостность данных на основе хеширования — вероятно, останется фундаментальным строительным блоком распределенных систем на долгие годы вперед.
Дополнительная литература
Что такое алгоритм консенсуса в блокчейне?
История криптографии
Решения для масштабирования блокчейна на уровне 1 и уровне 2.
Что такое шардинг и как он работает?
Отказ от ответственности: Данный контент предоставляется вам «как есть» исключительно в информационных и образовательных целях, без каких-либо заверений или гарантий. Он не должен рассматриваться как финансовая, юридическая или иная профессиональная консультация, а также не предназначен для рекомендации покупки какого-либо конкретного продукта или услуги. Вам следует обратиться за консультацией к соответствующим профессиональным консультантам. В тех случаях, когда контент предоставлен сторонним автором, обратите внимание, что выраженные в нем мнения принадлежат этому автору и не обязательно отражают точку зрения Binance Academy. Цены на цифровые активы могут быть волатильными. Стоимость ваших инвестиций может как расти, так и падать, и вы можете не вернуть вложенную сумму. Вы несете полную ответственность за свои инвестиционные решения, и Binance Academy не несет ответственности за любые убытки, которые вы можете понести. Для получения дополнительной информации см. наши Условия использования, Предупреждение о рисках и Условия Binance Academy.