Дерево Меркла, также известное как хеш-дерево, представляет собой иерархическую структуру данных, в которой каждый листовой узел содержит криптографический хеш блока данных, а каждый нелистовой (родительский) узел содержит криптографический хеш конкатенации хешей своих дочерних узлов. Эта бинарная древовидная структура позволяет с исключительной эффективностью проверять целостность и согласованность больших наборов данных — вместо проверки каждого отдельного фрагмента данных проверяющему достаточно изучить небольшое количество хешей вдоль одной ветви от листа к корню. Единственный хеш, расположенный на вершине дерева, называемый корнем Меркла, служит уникальным идентификатором для всего набора данных под ним. Если изменяется хотя бы один бит данных в любом месте дерева, изменение распространяется вверх по всем родительским хешам, пока не изменится сам корень Меркла, мгновенно сигнализируя о том, что данные были изменены.
В технологии блокчейн деревья Меркла лежат в основе того, как блоки хранят и проверяют транзакции. Каждый заголовок блока в Bitcoin, Ethereum и практически во всех других протоколах блокчейна содержит корень Меркла, который суммирует все транзакции, включенные в этот блок. Такая конструкция позволяет легковесным клиентам — часто называемым узлами упрощенной проверки платежей (SPV) — подтверждать включение конкретной транзакции в блок без загрузки всего содержимого блока. Клиенту нужен только заголовок блока (который содержит корень Меркла) и короткая последовательность хешей соседних блоков, называемая доказательством Меркла или путем Меркла. Для блока, содержащего 4,096 транзакций, это доказательство требует всего 12 хешей, а не всех 4,096 хешей транзакций — логарифмическое сокращение, которое делает мобильные кошельки и устройства с ограниченными ресурсами жизнеспособными участниками сети.
Помимо простого включения транзакций, деревья Меркла лежат в основе некоторых из самых передовых конструкций в криптовалютной экосистеме. Ethereum использует модифицированную версию, называемую деревом Меркла-Патриции, для хранения всего своего состояния — каждого баланса счета, слота хранения смарт-контракта и фрагмента кода. В роллапах с нулевым разглашением деревья Меркла используются для фиксации пакетов внесетевых транзакций в единый корневой элемент в блокчейне. Контракты распределения аирдропов используют деревья Меркла, позволяя тысячам адресов получать токены с минимальным объемом данных в блокчейне. Элегантность структуры заключается в ее простоте: рекурсивное применение хеширования, которое преобразует произвольно большой набор данных в единое фиксированное по размеру обязательство, проверяемое за логарифмическое время.
Происхождение и история
1979 год: Ральф Меркл впервые описал хеш-деревья в своей докторской диссертации в Стэнфорде и впоследствии запатентовал эту концепцию (патент США № 4 309 569, заявка подана 5 сентября 1979 года, патент выдан 5 января 1982 года). Меркл разработал эту структуру в рамках своей новаторской работы по криптографии с открытым ключом и цифровым подписям, стремясь найти эффективный метод аутентификации больших структур данных.
1987–1988: В статье, представленной на конференции CRYPTO '87 и опубликованной в материалах конференции в 1988 году, Меркл объединил свою структуру хеш-дерева со схемами одноразовых подписей, опираясь на более раннюю конструкцию одноразовой подписи Лампорта-Диффи. Эта комбинация, теперь известная как схема подписи Меркла, продемонстрировала, что одно хеш-дерево может аутентифицировать множество пар одноразовых ключей с помощью одного открытого ключа, эффективно управляя большим количеством криптографических ключей.
Конец 1990-х: С появлением одноранговых систем обмена файлами стали применяться хэш-деревья, позволяющие узлам независимо проверять целостность загруженных сегментов файлов, обнаруживая поврежденные или вредоносные данные без повторной загрузки целых файлов. Эта модель впоследствии была формализована в таких спецификациях, как формат Tree Hash Exchange (THEX).
2008 год: Сатоши Накамото интегрировал деревья Меркла в протокол Bitcoin. В разделе 7 «Белой книги Bitcoin» («Освобождение дискового пространства») описывается, как деревья Меркла позволяют удалять старые данные транзакций, сохраняя при этом компактный корневой хеш. В разделе 8 («Упрощенная проверка платежей») отдельно объясняется, как та же структура позволяет легковесным клиентам подтверждать включение транзакции в блок, используя только заголовок блока и доказательство Меркла.
2009 год: Сеть Биткойн была запущена с корнями Меркла, встроенными в заголовок каждого блока. Генезисный блок (Блок 0) содержал одну транзакцию с корнем Меркла, равным хешу этой транзакции, устанавливая шаблон для всех последующих блоков.
2015 год: Ethereum был запущен с тремя различными вариантами дерева Меркла в заголовке каждого блока — деревом транзакций, деревом квитанций и деревом состояний — все они были реализованы как деревья Меркла Патрисии. Такая конструкция расширила функциональность дерева Меркла от простой проверки транзакций до полной аутентификации состояния мира.
2017–2019: Деревья Меркла стали центральным элементом в разработке решений для масштабирования второго уровня. В цепочках Plasma использовались обязательства Меркла для привязки состояния дочерних цепочек к основной сети Ethereum, а в ранних проектах роллапа использовались корни Меркла для объединения сотен транзакций в одно доказательство в блокчейне.
2020–2024: Системы доказательства с нулевым разглашением, такие как zkSync и StarkNet, внедрили специализированные варианты деревьев Меркла, включая разреженные деревья Меркла на основе хеша Посейдона, оптимизированные для эффективных вычислений внутри схем с нулевым разглашением. Контракты аирдропа Меркла стали стандартным шаблоном для распределения токенов в сети Ethereum.
«Хеш-дерево позволяет проверять любую ветвь хеш-дерева независимо, без необходимости хранения узлами полного набора данных».
Простыми словами
Представьте себе турнирную сетку спортивного турнира. В каждой игре первого раунда определяется победитель. Эти победители объединяются в пары для второго раунда, и так далее, пока на вершине не останется один чемпион. Дерево Меркла работает аналогично – только вместо спортивных команд вы начинаете с блоков данных, и вместо игр вы объединяете пары данных с помощью криптографического хеширования, пока не получите на вершине один «хеш чемпиона», называемый корнем Меркла.
Представьте это как генеалогическое древо в обратном порядке. Внизу находятся сотни отдельных членов семьи (блоки данных). Каждая пара братьев и сестер объединяется, чтобы представить своих родителей. Эти родители объединяются, чтобы образовать бабушек и дедушек, и так далее, пока вы не дойдете до одного предка наверху. Если какой-либо член семьи меняется, то все поколения выше него также меняются, вплоть до предка наверху.
Представьте себе систему каталогизации библиотеки. Вместо того чтобы проверять каждую книгу на каждой полке, чтобы убедиться, что ничего не пропало, библиотекарь ведет сводку по каждой полке, объединяет сводки по полкам в сводки по рядам, сводки по рядам в сводки по этажам и хранит одну общую сводку для всей библиотеки. Чтобы проверить наличие одной книги, достаточно проверить сводки по ее пути от полки до общей сводки — а не каждую вторую книгу.
Представьте себе, что вы запечатываете улики в судебном процессе. Каждая улика помещается в отдельный конверт с защитой от вскрытия. Пары конвертов помещаются в большие конверты, которые, в свою очередь, помещаются в еще большие конверты, пока все не окажется внутри одного общего конверта с одной печатью. Если кто-либо попытается вскрыть какую-либо улику, на всех конвертах над ней появятся следы вскрытия, и печать на общем конверте будет нарушена.
Важно: деревья Меркла обеспечивают доказательство включения и целостности данных, но они не шифруют данные и не гарантируют конфиденциальность. Любой, кто имеет доступ к дереву, может видеть данные — дерево лишь гарантирует, что данные не были изменены. Кроме того, безопасность дерева Меркла полностью зависит от надежности базовой хеш-функции; если хеш-функция взломана, целостность дерева гарантирует его разрушение.
Основные технические характеристики
Бинарная хеш-структура
Листовые узлы содержат хэши отдельных блоков данных (например, транзакций).
Внутренние узлы содержат хеш, полученный путем конкатенации хешей двух их дочерних узлов: H(parent) = Hash(H(left) || H(right))
Дерево всегда находится в равновесии; если число листьев нечетное, последний лист дублируется, чтобы образовать пару.
Глубина дерева log2(n) в котором n — это количество листовых узлов.
Корневой хеш (корень Меркла) представляет собой отпечаток фиксированного размера всего набора данных независимо от размера набора данных.
Как работает проверка доказательства Меркла
Проверяющий хочет подтвердить, что конкретная транзакция... Tx_k включен в блок
Верификатор получает заголовок блока, содержащий корень Меркла.
Доказывающая программа предоставляет хеш Tx_k а также доказательство Меркла — последовательность хешей соседних узлов на пути от листа к корню.
Хэши верификатора Tx_kзатем объединяет его с хешем первого соседа, используя ту же хеш-функцию.
Полученный результат объединяется с хешем следующего за ним элемента, и так далее, поднимаясь по дереву уровень за уровнем.
Если итоговый вычисленный хеш совпадает с корнем Меркла в заголовке блока, транзакция подтверждается как включенная.
Для дерева с n листья, только log2(n) Для проверки одной транзакции из 1 048 576 требуется хэш-таблиц – например, 20 хэшей необходимы для подтверждения одной транзакции.
Merkle Patricia Trie (Ethereum)
Ethereum расширяет базовое дерево Меркла до префиксного дерева Патриции (радиксного дерева), которое сопоставляет ключи со значениями.
В структуре данных storage trie 256-битные ячейки хранения сопоставляются с их значениями для каждого смарт-контракта.
Сжатие путей уменьшает накладные расходы на хранение данных за счет объединения цепочек с одним дочерним звеном в узлы расширения.
Три типа узлов: узлы ветвления (16 дочерних узлов + значение), узлы расширения (общий префикс + следующий узел), листовые узлы (оставшийся путь + значение).
Разреженные деревья Меркла для доказательств с нулевым разглашением
Разреженные деревья Меркла (SMT) — это деревья Меркла, у которых большинство листьев пусты (хеш-значение по умолчанию).
Используется в ZK-роллапах для представления состояний учетных записей с эффективными доказательствами членства и нечленства.
Для вычислений, удобных для схем ZK, используются оптимизированные хеш-функции, такие как Посейдон и Педерсен.
SMT-модуляция глубиной 256 может представлять все возможные 256-битные ключи, оставаясь при этом вычислительно приемлемой.
Доказательство невключения сводится к простому доказательству того, что лист в данной позиции содержит значение по умолчанию.
Преимущества недостатки
Преимущества
Недостатки
Логарифмическая верификация: масштаб размера доказательства и времени верификации. O(log n)что позволяет эффективно проверять даже миллионы транзакций.
Затраты на хранение: Для хранения всех промежуточных хешей требуется приблизительно 2n - 1 узлы для n Листовые узлы, что примерно вдвое увеличивает требования к хранению исходных данных.
Обнаружение несанкционированного доступа: любое изменение в любом листовом узле распространяется вверх, изменяя корень Меркла и немедленно выявляя повреждение или манипуляцию данными.
Стоимость перерасчета: Обновление одного листового узла требует пересчета всех хешей на пути к корню. O(log n) хеш-операций на каждое обновление
Упрощенная поддержка клиентов: узлы SPV могут проверять включение транзакций, используя только заголовки блоков и доказательства Меркла, что позволяет использовать мобильные и встроенные кошельки.
Зависимость от хеш-функции: вся модель безопасности зависит от устойчивости к коллизиям выбранной хеш-функции; некорректная хеш-функция разрушает дерево.
Эффективность использования полосы пропускания: доказательства Меркла передают только log2(n) Вместо полного набора данных используются хеши, что значительно снижает пропускную способность сети для проверки.
Требование балансировки: Стандартные бинарные деревья Меркла требуют четного числа листьев; для наборов данных с нечетным числом листьев требуется дублирование, что может привести к неочевидным ошибкам реализации.
Компонуемость: деревья Меркла могут быть вложенными — корень Меркла может быть листом в дереве более высокого уровня — что позволяет использовать многоуровневые схемы фиксации данных в агрегированных и сегментированных данных.
Сложность деревьев Меркла: деревья Меркла (как в Ethereum) значительно сложнее в реализации, чем базовые бинарные деревья Меркла, с несколькими типами узлов и кодированием пути.
Параллельное построение: хэши листьев могут вычисляться независимо и параллельно, что делает построение дерева Меркла легко распараллеливаемым на современном оборудовании.
Раздувание состояния: В блокчейнах с сохранением состояния дерево Меркла разрастается с каждой новой учетной записью и слотом хранения, что способствует раздуванию состояния в долгосрочной перспективе и увеличивает время синхронизации.
Стандартизированная и проверенная в боевых условиях: десятилетия академических исследований и внедрения в производство (биткойн с 2009 года) обеспечивают высокую степень уверенности в безопасности этой структуры.
Масштабирование размера доказательств: Хотя размер доказательств логарифмически высок, он все же увеличивается с размером набора данных; для очень больших деревьев (миллиарды листьев) размер доказательств может стать нетривиальным.
Управление рисками
Риск уязвимости хэш-функций
Деревья Меркла наследуют свойства безопасности своей базовой хеш-функции (обычно SHA-256 для Bitcoin, Keccak-256 для Ethereum).
Если атаки с использованием коллизий станут осуществимыми против хеш-функции, злоумышленник сможет создать два разных набора данных с одним и тем же корнем Меркла.
Меры по смягчению последствий: отслеживайте криптографические исследования на предмет прогресса в борьбе с SHA-256 и Keccak-256; блокчейн-сообщества могут провести хардфорк для обновления хэш-функций при необходимости.
Квантовые вычисления представляют собой долгосрочную угрозу безопасности хэш-функций, хотя текущие оценки показывают, что SHA-256 останется безопасным в течение десятилетий.
Риск ошибки при реализации
Незначительные ошибки в реализациях деревьев Меркла, такие как некорректная обработка нечетных листьев, ошибки смещения на единицу в путях доказательства или несоответствие порядка байтов, могут создавать уязвимости, которые можно использовать.
Разделение Bitcoin Cash в 2018 году выявило нестандартные ситуации при проверке дерева Меркла во время верификации блоков.
Меры по смягчению последствий: использовать проверенные библиотеки с открытым исходным кодом (например, MerkleProof.sol от OpenZeppelin для Solidity); проводить формальную верификацию критически важных реализаций.
Проведите тестирование с использованием состязательных входных данных, включая пустые деревья, деревья с одним листом и деревья максимальной глубины.
Риск атаки, связанной с неопределенностью типов
В простом дереве Меркла злоумышленник потенциально может создать мошеннический внутренний узел, который будет конфликтовать с легитимным листовым узлом.
Это более точно называется атакой на неопределенность типов или межузловой атакой, и ее можно предотвратить, добавив перед хешированием разделитель доменов (0x00 для листьев, 0x01 для внутренних узлов).
В реализации дерева Меркла в Биткоине используется хеширование с двойным SHA-256, что обеспечивает дополнительную устойчивость.
Меры по снижению рисков: Всегда различайте хеширование конечных и внутренних узлов; следуйте установленным стандартам, таким как RFC 6962 (Прозрачность сертификата).
Риски роста и эффективности государства
В сети Ethereum дерево состояний (state trie) растет с каждым новым слотом для хранения учетных записей и контрактов, что со временем увеличивает стоимость генерации и проверки доказательств.
Время полной синхронизации узлов сильно зависит от размера дерева состояний (сотни гигабайт).
Меры по смягчению последствий: Предложения по истечению срока действия состояния (EIP-4444, деревья Веркла) направлены на удаление исторического состояния; исследования клиентов без сохранения состояния сосредоточены на предоставлении доказательств состояния для каждого блока.
Культурная значимость
Деревья Меркла занимают уникальное место в криптовалютной культуре как одна из немногих структур данных, получивших известность за пределами кругов компьютерных наук. Фраза «доказательство Меркла» часто используется на серверах Discord, в ветках обсуждений в Twitter и на форумах управления, зачастую участниками, которые, возможно, не до конца понимают лежащую в основе математику, но осознают значимость этого термина.
«Деревья Меркла — это незамеченные герои блокчейна. Каждый раз, когда вы подтверждаете транзакцию, благодарите Ральфа Меркла».
Концепция получила широкое распространение в криптокультуре во время краха FTX в 2022 году, когда фраза «доказательство резервов» вошла в публичный дискурс. Такие биржи, как Binance и Kraken, внедрили системы доказательства резервов на основе дерева Меркла, позволяющие пользователям самостоятельно проверять, включены ли их средства в заявленные биржей активы. Фраза «доказательство резервов на основе дерева Меркла» стала сигналом доверия в пост-FTX среде, демонстрируя, как изобретение 1979 года в области компьютерных наук стало культурным ориентиром финансовой подотчетности.
В сообществах NFT и аирдропов термин «аирдроп Меркла» стал стандартным. Такие проекты, как Uniswap, ENS и Optimism, использовали контракты распределения на основе дерева Меркла, которые позволяли соответствующим адресам получать токены, предоставляя доказательство Меркла, подтверждающее их включение в список распределения. Этот шаблон, популяризированный библиотекой OpenZeppelin, был воспроизведен сотнями проектов и теперь является де-факто стандартом для распределения токенов в блокчейне.
В сообществе разработчиков регулярно обсуждаются преимущества деревьев Меркла по сравнению с более новыми альтернативами, такими как деревья Веркла (предложенные для дорожной карты Ethereum по отказу от состояния), что отражает, насколько глубоко эта структура укоренилась в дискуссиях об архитектуре блокчейна.
Примеры из реального мира
Верификация биткоин-кошелька SPV
Ситуация: Пользователь, использующий мобильный биткоин-кошелек на смартфоне с ограниченным объемом памяти, хочет проверить легитимность полученного платежа в размере 0.5 BTC, не загружая при этом весь блокчейн объемом более 500 ГБ.
Реализация: SPV-кошелек загружает только заголовки блоков (по 80 байт каждый, что в сумме составляет примерно 60 МБ для всей истории блокчейна). Когда пользователь получает платеж, кошелек запрашивает доказательство Меркла у полного узла — набор из 10-12 хешей соседних узлов, которые отслеживают путь от транзакции до корня Меркла в заголовке блока.
Результат: Кошелек проверяет включение транзакции в блок, пересчитывая хеши до корня Меркла, подтверждая легитимность платежа. Это занимает миллисекунды и использует килобайты данных, что делает Bitcoin пригодным для использования на мобильных устройствах с ограниченными ресурсами. Это именно тот вариант использования, который Сатоши описал в разделе 8 технического документа Bitcoin.
Аирдроп токенов UNI на Uniswap (2020)
Ситуация: Uniswap необходимо распределить 150 миллионов токенов UNI примерно между 250 000 пользователями, которые ранее использовали эту платформу. Хранение всех 250 000 адресов в блокчейне обойдется в миллионы долларов в виде комиссий за транзакции.
Реализация: Инженеры Uniswap построили дерево Меркла, где каждый подходящий адрес и сумма, которую можно получить, являлись листовыми узлами. В контракте дистрибьютора в блокчейне хранился только один корень Меркла (32 байта). Каждый пользователь мог получить свои токены, предоставив доказательство Меркла (приблизительно 18 хешей для 250 000 адресов), подтверждающее его включение в дерево.
Результат: Контракт на раздачу токенов потреблял минимальное количество места в блокчейне, позволяя любому подходящему пользователю получать токены без разрешения. Стоимость газа за одну заявку составляла приблизительно 80 000–100 000 единиц, по сравнению с миллионами долларов, которые потребовались бы для предварительной загрузки всех адресов в блокчейн. С тех пор эта схема стала отраслевым стандартом для распределения токенов.
Доказательство резервов Binance (после FTX, 2022 г.)
Ситуация: После краха FTX компания Binance столкнулась с неотложным давлением, требующим доказать полную безопасность средств клиентов. Биржа хранила активы для очень большого количества пользовательских счетов, что делало раскрытие информации на уровне отдельных счетов нецелесообразным и нарушающим конфиденциальность.
Реализация: Binance внедрила систему подтверждения резервов на основе дерева Меркла, где баланс счета каждого пользователя хешировался как листовой узел. Пользователи могли проверить включение резервов в свою учетную запись, войдя в систему и запросив свое персональное подтверждение Меркла, которое они могли независимо проверить, сравнив его с опубликованным корневым узлом Меркла. Сторонние аудиторы подтвердили, что общие резервы соответствуют обязательствам, зафиксированным в корневом узле Меркла.
Результат: Пользователи смогли подтвердить включение своих учетных записей в дерево резервов, что восстановило определенный уровень доверия к централизованным биржам. Этот подход, хотя и не идеален (он не доказывает отсутствие обязательств), утвердил прозрачность на основе дерева Меркла как широко распространенный стандарт подотчетности бирж.
Проверка состояния Ethereum для протоколов DeFi
Сценарий: Протоколу DeFi-кредитования на Ethereum необходимо проверить текущий баланс залогового обеспечения учетной записи пользователя в рамках роллаппа второго уровня перед обработкой ликвидации.
Реализация: Rollup отправляет свой корневой узел состояния (корень Меркла всех балансов счетов) в основную сеть Ethereum. Контракт ликвидации в Ethereum принимает доказательство Меркла, демонстрирующее баланс залогового обеспечения пользователя в дереве состояний Rollup. Доказательство содержит приблизительно 20-30 хешей для разреженного дерева Меркла, представляющего очень большое пространство возможных счетов.
Результат: Межуровневая ликвидация выполняется без необходимости доверять каким-либо оракулам или мостовым ретрансляторам. Доказательство Меркла криптографически связывает состояние роллапа с контрактом основной сети, обеспечивая совместимость между уровнями L1 и L2 без ущерба для безопасности. Этот общий шаблон используется в ряде проектов роллапов и межсетевого кредитования.
Сравнительная таблица
Характеристика
Дерево Меркла (бинарное)
Merkle Patricia Trie (Ethereum)
Дерево Веркл (предложенное)
Структура:
Бинарное дерево хешей
Порядковое префиксное дерево с хеш-обязательствами
Дерево с векторными обязательствами
Размер пробы
O(log n) хеши (примерно по 32 байта каждый)
O(log n) но больше из-за коэффициента ветвления 16
O(log n) но меньше, чем доказательства Меркла
Основное использование
Включение транзакции (биткоин)
Полное хранилище мирового состояния (Ethereum)
Проверка подлинности клиента без сохранения состояния (будущий Ethereum)
Ключевое сопоставление
Позиционный (на основе индекса)
Ключ-значение (адрес-состояние)
Ключ-значение (адрес-состояние)
Стоимость обновления
O(log n) перефразирование
O(log n) но с учетом дополнительных расходов на реструктуризацию.
O(log n) с более дешевыми обязательствами
Проверка доказательств
Простой пересчет хеша
Более сложная система (с несколькими типами узлов)
Требуются операции с эллиптическими кривыми.
Раздувание государства
Минимальный (списки транзакций ограничены)
Жесткое (состояние растет безгранично)
Снижено за счет меньшего объема подтверждающих документов.
Квантовое сопротивление
Хэш-основанная (относительно квантово-безопасная)
Хэш-основанная (относительно квантово-безопасная)
Основан на эллиптических кривых (квантово-уязвимых).
Срок погашения
Внедряется с 2009 года (биткоин)
Внедряется с 2015 года (Ethereum)
Этап исследований/внедрения (EIP-6800)
Связанные условия
Хэш-функция – Математическая функция, преобразующая входные данные в выходные данные фиксированного размера, являющаяся основным строительным блоком каждого узла в дереве Меркла.
Упрощенная проверка платежа (SPV) – Метод проверки транзакций Bitcoin с использованием только заголовков блоков и доказательств Меркла, позволяющий создавать легковесные клиенты, полностью полагающиеся на эффективность дерева Меркла.
Корень Меркла — это единственный хеш в вершине дерева Меркла, который служит криптографическим подтверждением всех данных, хранящихся в дереве, и включается в заголовок каждого блока блокчейна.
Заголовок блока – Раздел метаданных блока блокчейна, содержащий корень Меркла, хеш предыдущего блока, метку времени и другие поля, специфичные для протокола.
Patricia Trie – оптимизированное по объему префиксное дерево (три), используемое Ethereum в сочетании с хешированием Меркла для создания дерева Merkle Patricia Trie для хранения состояния.
Дерево Веркла — предлагаемый преемник деревьев Меркла в Ethereum, использующий векторные обязательства вместо обязательств на основе хешей, что позволяет уменьшить размер доказательств.
Доказательство с нулевым разглашением – Криптографический метод, позволяющий одной стороне доказать знание факта, не раскрывая сам факт, часто с использованием деревьев Меркла для подтверждения состояния в ZK-роллапах.
Подтверждение резервов (Proof of Reserves) — это метод аудита, при котором криптовалютные биржи используют деревья Меркла для подтверждения того, что депозиты клиентов полностью обеспечены активами в блокчейне.
Выброска десанта – Событие распределения токенов, в котором обычно используются смарт-контракты на основе дерева Меркла, позволяющие соответствующим получателям получать токены путем предоставления доказательств Меркла.
State Trie – дерево Меркла-Патриции в Ethereum, которое сопоставляет каждый адрес учетной записи с его текущим состоянием, образуя основу архитектуры хранения данных Ethereum.
Бинарное дерево — фундаментальная структура данных в информатике, в которой каждый узел имеет не более двух дочерних узлов, служащая структурной основой для стандартных деревьев Меркла.
Подтверждение транзакции (Transaction Receipt) – структура данных, генерируемая после выполнения транзакции в Ethereum и хранящаяся в отдельном дереве Меркла внутри каждого блока для эффективной проверки подтверждения транзакции.
FAQ
В: Что такое дерево Меркла и почему оно важно для блокчейна? Дерево Меркла — это структура данных, которая организует данные в бинарное дерево криптографических хешей, создавая единый корневой хеш, представляющий весь набор данных. Оно имеет решающее значение для блокчейна, поскольку обеспечивает эффективную проверку транзакций — легковесный клиент может подтвердить включение транзакции в блок, проверив лишь небольшое доказательство Меркла (логарифмического размера), вместо загрузки каждой транзакции.
В: Как работает доказательство Меркла? Доказательство Меркла состоит из хешей соседних узлов вдоль пути от конкретного листового узла к корню Меркла. Для проверки вы хешируете целевые данные, объединяете их с первым хешем соседнего узла, хешируете результат, объединяете его со следующим соседним узлом и повторяете до тех пор, пока не достигнете корня. Если вычисленный корень совпадает с известным корнем Меркла, данные подтверждаются как включенные в дерево. Для дерева с 1 миллионом листьев для этого требуется всего около 20 хешей.
В: В чем разница между деревом Меркла и деревом Патриции Меркла? Стандартное дерево Меркла — это простое бинарное хеш-дерево, используемое для упорядоченных списков данных (например, транзакций в блоке Bitcoin). Дерево Патриции Меркла, используемое в Ethereum, представляет собой более сложную структуру, которая сочетает в себе префиксное дерево (radix trie) с хешированием Меркла для создания хранилища типа «ключ-значение» с доказуемой целостностью.
В: Что такое деревья Веркла и заменят ли они деревья Меркла? Деревья Веркла — это предлагаемое обновление для Ethereum (EIP-6800), которое заменяет хеш-основанные обязательства полиномиальными (векторными) обязательствами, что позволяет создавать более мелкие доказательства, важные для плана развития Ethereum по созданию безсостоятельных клиентов. Однако деревья Веркла основаны на криптографии на эллиптических кривых, которая потенциально уязвима для квантовых компьютеров, в то время как хеш-основанные деревья Меркла считаются более устойчивыми к квантовым атакам.
В: Как используются деревья Меркла в аирдропах NFT и токенов? Проекты строят дерево Меркла, используя в качестве листьев адреса кошельков, на которые можно претендовать (и суммы, которые можно получить). В блокчейне хранится только корень дерева Меркла, что позволяет экономить на транзакциях. Каждый подходящий пользователь может получить токены, предоставив доказательство Меркла — небольшой набор хешей, подтверждающих наличие его адреса в дереве. Этот шаблон, популяризированный библиотекой MerkleProof от OpenZeppelin, используется Uniswap, ENS, Optimism и сотнями других проектов.
В: Можно ли использовать деревья Меркла для обеспечения конфиденциальности? Стандартные деревья Меркла не обеспечивают конфиденциальность — все данные видны. Однако в системах, сохраняющих конфиденциальность, используются специализированные варианты. Доказательства Меркла с нулевым разглашением позволяют доказывать включение без раскрытия данных листьев, что обеспечивает конфиденциальные транзакции и проверку конфиденциального состояния.
В: Что произойдет, если два разных набора данных дадут один и тот же корень Меркла? Это будет считаться коллизией хешей — два разных входных значения дадут одинаковый результат от хеш-функции. При использовании SHA-256 (применяется в Биткоине) обнаружение такой коллизии потребует приблизительно 2^128 операций, что вычислительно невыполнимо при современных и прогнозируемых технологиях.
Источники
Меркле, Р. К. «Цифровая подпись, основанная на традиционной функции шифрования»
Белая книга Биткоина, разделы 7-8: Освобождение дискового пространства / Упрощенная проверка платежей – https://bitcoin.org/bitcoin.pdf
