Дерево Меркла

Что такое дерево Меркла?

Дерево Меркла — это криптографическая структура данных, которая организует множество фрагментов данных в дерево хешей.

В криптовалютах деревья Меркла помогают блокчейнам эффективно проверять транзакции, балансы, аккаунты, значения хранилища, права на получение токенов, белые списки NFT и другие большие наборы данных.

Дерево Меркла также называют хеш-деревом, поскольку каждый его уровень строится на основе криптографических хеш-значений.

В нижнем уровне находятся отдельные элементы данных, называемые листьями.

Каждый лист хешируется, объединяется в пару с другим хешем и хешируется повторно, формируя следующий уровень.

Процесс продолжается, пока наверху не останется один итоговый хеш.

Этот итоговый хеш называется корнем Меркла.

В руководстве для разработчиков Bitcoin объясняется, что хеши транзакций попарно объединяются и многократно хешируются, пока в заголовке блока не останется один корень Меркла.

Основная идея проста: один небольшой корень может представлять большой набор данных.

Если изменится любой элемент набора, изменятся и расположенные выше хеши, а вместе с ними — корень Меркла.

Как работает дерево Меркла

Дерево Меркла строится на основе исходных данных, например транзакций, адресов кошельков, записей аккаунтов или записей о получении токенов.

Каждый элемент обрабатывается криптографической хеш-функцией, в результате чего образуется хеш листа.

Два хеша листьев объединяются и хешируются, формируя родительский хеш.

Затем родительские хеши попарно объединяются и хешируются, формируя хеши следующего уровня.

Процесс продолжается, пока не останется один хеш.

Этот итоговый хеш — корень Меркла.

Корень Меркла служит компактным цифровым отпечатком всего набора данных.

Если данные не менялись, один и тот же метод построения дерева должен давать одинаковый корень.

Если изменится транзакция, адрес, баланс или сумма для получения токенов, итоговый корень тоже должен измениться.

Зачем нужны деревья Меркла в криптовалютах

Деревья Меркла важны, поскольку блокчейнам нужно проверять большие объемы данных, не заставляя каждого пользователя постоянно обрабатывать их целиком.

В блоке блокчейна может содержаться множество транзакций.

В раздаче токенов могут участвовать тысячи или миллионы подходящих кошельков.

База данных состояния блокчейна может включать аккаунты, балансы, хранилище смарт-контрактов и код.

Деревья Меркла позволяют системам зафиксировать большие наборы данных с помощью одного корня и при этом позднее проверять отдельные элементы.

Это повышает эффективность, масштабируемость и целостность данных.

Кроме того, во многих криптовалютных приложениях сокращаются требования к хранению данных и пропускной способности.

Без деревьев Меркла или похожих аутентифицированных структур данных многие задачи проверки в блокчейне выполнялись бы медленнее, требовали бы больше ресурсов и обходились бы дороже.

Корень Меркла

Корень Меркла — это итоговый хеш в верхней части дерева Меркла.

Он представляет все данные, расположенные ниже.

В блоке блокчейна корень Меркла может обобщать все транзакции, включенные в этот блок.

В контракте раздачи токенов корень Меркла может обобщать адреса всех подходящих кошельков и суммы, которые им полагаются.

В дереве состояния корень может представлять множество аккаунтов или значений хранилища.

Сам по себе корень не раскрывает весь набор данных.

Он лишь служит криптографическим обязательством в отношении этого набора.

Чтобы подтвердить включение отдельного элемента в дерево, пользователю все еще нужны правильное доказательство и правила проверки.

Листья и ветви дерева Меркла

Листья — это хеши нижнего уровня в дереве Меркла.

Обычно каждый лист представляет один элемент данных.

Например, лист может представлять хеш транзакции, адрес кошелька, запись о получении токенов, разрешение на выпуск NFT или значение аккаунта.

Ветви — это промежуточные хеши между листьями и корнем.

Ветви связывают отдельные листья с итоговым корнем Меркла.

Доказательство Меркла использует хеши ветвей, чтобы подтвердить принадлежность одного листа дереву.

Благодаря такой структуре для проверки не нужно показывать или загружать все остальные листья.

Доказательства Меркла

Доказательство Меркла — это набор хешей соседних элементов, необходимый, чтобы подтвердить принадлежность листа дереву с известным корнем.

Проверяющая сторона берет нужный лист и объединяет его с хешами из доказательства в правильном порядке.

Если вычисленный итоговый хеш совпадает с доверенным корнем, доказательство действительно.

Если вычисленный итоговый хеш не совпадает с доверенным корнем, доказательство недействительно.

В документации OpenZeppelin MerkleProof описаны инструменты для смарт-контрактов, позволяющие проверить, можно ли доказать принадлежность листа дереву Меркла, определенному корнем.

Поэтому деревья Меркла полезны для белых списков, получения токенов, вознаграждений и проверки доступа в блокчейне.

Деревья Меркла в Bitcoin

Bitcoin использует деревья Меркла для организации транзакций в блоках.

Каждая транзакция хешируется, затем хеши транзакций объединяются попарно и хешируются вверх по дереву, пока не образуется один корень Меркла.

Корень Меркла сохраняется в заголовке блока.

Это помогает нодам Bitcoin обнаруживать изменения в данных транзакций.

Кроме того, такая структура позволяет проверять транзакции на легких клиентах.

Легкий клиент может с помощью доказательства Меркла проверить включение транзакции в блок, не загружая все транзакции этого блока.

Это обеспечивает упрощенную проверку платежей, которую часто называют SPV.

SPV обеспечивает менее полную проверку, чем проверка полной нодой, но эффективнее работает на устройствах и кошельках с ограниченными ресурсами.

Деревья Меркла в Ethereum

Ethereum использует связанную аутентифицированную структуру данных, которая называется деревом Меркла — Патриции.

В документации Ethereum о дереве Меркла — Патриции объясняется, что структура Ethereum детерминирована и поддается криптографической проверке.

Она помогает Ethereum представлять состояние аккаунтов, хранилище и другие данные в формате «ключ — значение».

Если состояние меняется, меняется и корень состояния.

Благодаря этому клиенты и приложения Ethereum могут проверять данные состояния относительно известного корня.

Стандарт EIP-1186 eth_getProof описывает RPC-метод получения доказательств Меркла для аккаунтов и значений хранилища Ethereum.

Структура Ethereum отличается от простого бинарного дерева Меркла, но использует тот же основной принцип проверки с помощью связанных хешей.

Деревья Меркла в раздачах токенов

В раздачах криптовалют часто используют деревья Меркла для управления большими списками участников.

Проект может сформировать список подходящих адресов кошельков и сумм токенов.

Каждая пара «адрес — сумма» становится листом дерева Меркла.

В смарт-контракте проекта хранится только корень Меркла.

Чтобы получить токены, пользователь отправляет доказательство Меркла.

Контракт проверяет, входят ли кошелек и сумма в дерево, представленное сохраненным корнем.

Это экономит средства на газ, поскольку контракту не нужно хранить в блокчейне адрес каждого подходящего кошелька.

Кроме того, благодаря этому проще проводить масштабные кампании по раздаче токенов.

Деревья Меркла в белых списках NFT

NFT-проекты часто используют деревья Меркла для белых списков, предварительных продаж и раннего доступа к выпуску NFT.

Вместо того чтобы хранить в контракте адрес каждого одобренного кошелька, проект сохраняет один корень Меркла.

Каждый одобренный кошелек получает доказательство того, что он входит в белый список.

Во время выпуска NFT смарт-контракт проверяет доказательство относительно сохраненного корня.

Если доказательство действительно, кошелек может выпустить NFT согласно правилам белого списка.

Это позволяет снизить расходы на хранение данных в блокчейне и эффективнее проверять белые списки.

Пользователям все равно следует убедиться, что страница выпуска NFT, адрес контракта и корень Меркла взяты из официальных источников.

Деревья Меркла в легких клиентах

Легкие клиенты используют компактные способы проверки, чтобы сократить объем данных блокчейна, которые им нужно загружать.

Деревья Меркла помогают легким клиентам проверять отдельные транзакции или данные состояния относительно доверенных заголовков блоков или корней.

Это полезно для мобильных кошельков, браузеров и устройств с ограниченным объемом памяти или пропускной способностью.

Модель безопасности легкого клиента отличается от модели полностью проверяющей ноды.

Однако проверка на основе Меркла может быть надежнее, чем безоговорочное доверие одному поставщику данных.

Поэтому деревья Меркла — важный элемент более доступной криптовалютной инфраструктуры.

Деревья Меркла в блокчейн-играх и приложениях метавселенной

Блокчейн-игры и приложения метавселенной могут использовать деревья Меркла для проверки больших списков активов, вознаграждений, игроков или разрешений.

Игра может использовать корень Меркла, чтобы зафиксировать право на получение вознаграждений за игровой сезон.

Приложение метавселенной может использовать корень Меркла для проверки права получить значки за участие в событиях или разрешений на виртуальную землю.

NFT-проект может использовать дерево Меркла для управления раскрытием характеристик NFT или доступом по белому списку.

Это позволяет приложениям хранить большие наборы данных вне блокчейна и при этом проверять отдельные записи в блокчейне.

В результате можно сократить расходы и повысить масштабируемость.

Компромисс заключается в том, что построение дерева вне блокчейна должно быть прозрачным и корректным.

Деревья Меркла и целостность данных

Деревья Меркла защищают целостность данных, позволяя легко обнаружить изменения.

Если меняется один лист, меняется его хеш.

Это меняет родительский хеш, затем следующий родительский хеш и в итоге — корень Меркла.

Поэтому проверяющая сторона может сравнить корни и определить, совпадают ли наборы данных.

Деревья Меркла не мешают кому-либо создать ложный набор данных.

Они помогают проверить, соответствуют ли данные конкретному зафиксированному корню.

Поэтому корень должен поступать из доверенного источника или источника, проверенного механизмом консенсуса.

Дерево Меркла и список хешей

Список хешей — это простой перечень хешей.

Дерево Меркла — это упорядоченная структура хешей, которая позволяет создавать компактные доказательства.

Для проверки одного элемента по списку хешей может потребоваться больше данных из всего списка.

Для проверки по дереву Меркла обычно достаточно проверяемого листа и небольшого количества соседних хешей.

Благодаря этому деревья Меркла эффективнее работают с большими наборами данных.

По мере роста набора данных преимущество в эффективности становится еще заметнее.

Дерево Меркла и дерево Меркла — Патриции

Дерево Меркла — это общее название структуры данных в виде хеш-дерева.

Дерево Меркла — Патриции — более специализированная структура для данных в формате «ключ — значение».

Ethereum использует модифицированное дерево Меркла — Патриции для эффективного хранения и проверки состояния.

Простые деревья Меркла часто применяются для проверки включения транзакций, белых списков NFT и получения токенов в раздачах.

Trie лучше подходит для поиска данных по ключам, например по адресам аккаунтов или слотам хранилища.

В обеих структурах используются криптографические хеши, позволяющие обнаруживать подмену данных.

Дерево Меркла и дерево Веркла

Дерево Веркла — это более новая аутентифицированная структура данных, в которой используются векторные обязательства, а не только пары хешей.

Деревья Веркла часто рассматривают как возможное будущее усовершенствование систем состояния блокчейна, поскольку они позволяют уменьшить размер некоторых доказательств.

В документации Ethereum отмечается, что в будущем Ethereum планирует перейти от текущей структуры дерева Меркла — Патриции к дереву Веркла.

Это не означает, что деревья Меркла устарели.

Они по-прежнему широко используются, поскольку просты, надежны и хорошо изучены.

Для многих задач, например раздач токенов и белых списков, деревья Меркла остаются практичным и эффективным решением.

Преимущества деревьев Меркла

Первое преимущество — эффективная проверка.

Пользователи могут проверить один элемент, не загружая весь набор данных.

Второе преимущество — целостность данных.

Любое изменение исходных данных меняет расположенные выше хеши.

Третье преимущество — снижение расходов на хранение данных в блокчейне.

Вместо множества отдельных записей смарт-контракты могут хранить один корень.

Четвертое преимущество — масштабируемость.

Большие наборы данных можно представить одним компактным корнем.

Пятое преимущество — частичная конфиденциальность.

Пользователь может подтвердить включение элемента, не раскрывая остальные элементы набора данных.

Риски и ограничения деревьев Меркла

Первый риск — недостоверный корень.

Доказательство Меркла подтверждает только включение элемента в набор данных, представленный этим корнем, поэтому корень должен быть доверенным или проверенным.

Второй риск — неправильное построение дерева.

Если проект использует неверный метод хеширования, формат данных, правило сортировки или формат листа, доказательства могут не пройти проверку или оказаться небезопасными.

Третий риск — повторное использование доказательства или получение токенов дважды из-за ошибки.

Если каждый пользователь может получить токены только один раз, контракт должен отслеживать, использовал ли кошелек свое доказательство.

Четвертый риск — фишинг.

Мошенники могут создавать поддельные сайты для получения токенов, которые имитируют использование доказательств Меркла, но просят пользователей подписать вредоносные транзакции.

Пятый риск — неверное понимание принципа работы.

Дерево Меркла подтверждает включение данных, но не гарантирует, что проект заслуживает доверия, представляет ценность или безопасен.

Как оценить систему на основе дерева Меркла

Для начала проверьте, получен ли корень Меркла из официального источника или источника, проверенного механизмом консенсуса.

Изучите способ кодирования листьев.

Узнайте, какая хеш-функция используется.

Уточните, сортируются ли пары в дереве или порядок слева направо задан заранее.

Проверьте, создаются ли доказательства официальными инструментами или кодом с открытым исходным кодом.

Для смарт-контрактов изучите функцию проверки доказательств и логику учета получений.

Перед отправкой доказательства или подписанием транзакции при участии в раздаче токенов или использовании белого списка NFT проверьте официальный адрес контракта.

В хорошо спроектированной системе на основе дерева Меркла должны быть понятны корень, правила и процесс проверки.

Распространенные заблуждения о деревьях Меркла

Одно из распространенных заблуждений — будто дерево Меркла хранит все данные в блокчейне.

Во многих криптовалютных приложениях в блокчейне хранится только корень Меркла, а весь набор данных формируется и хранится вне блокчейна.

Другое заблуждение — будто корень Меркла раскрывает весь набор данных.

Корень — это только криптографическое обязательство, которое само по себе не показывает все листья.

Третье заблуждение — будто действительное доказательство Меркла подтверждает, что пользователь морально или юридически заслужил вознаграждение.

Оно подтверждает только включение отправленных данных в набор, представленный корнем.

Четвертое заблуждение — будто все деревья Меркла строятся одинаково.

В разных системах могут использоваться разные хеш-функции, методы кодирования, правила сортировки и структуры деревьев.

FAQ

Что такое дерево Меркла простыми словами?

Дерево Меркла — это дерево хешей, позволяющее с помощью небольшого доказательства проверить один элемент в большом наборе данных.

Что такое корень Меркла?

Корень Меркла — это итоговый хеш в верхней части дерева Меркла, который служит компактным цифровым отпечатком всего набора данных.

Зачем блокчейны используют деревья Меркла?

Деревья Меркла позволяют блокчейнам эффективно проверять большие наборы данных, сокращать объем необходимых данных и обнаруживать изменения транзакций или данных состояния.

Как Bitcoin использует деревья Меркла?

Bitcoin использует деревья Меркла для обобщения транзакций в блоках, а корень Меркла хранится в заголовке блока.

Как Ethereum использует структуры Меркла?

Ethereum использует модифицированное дерево Меркла — Патриции для хранения и проверки состояния аккаунтов и данных хранилища смарт-контрактов.

Что такое доказательство Меркла?

Доказательство Меркла — это набор хешей соседних элементов, подтверждающий принадлежность конкретного листа дереву с известным корнем Меркла.

Как деревья Меркла используют в раздачах токенов?

Контракты раздач могут хранить один корень Меркла и проверять заявки пользователей с помощью доказательств, вместо того чтобы хранить в блокчейне адрес каждого подходящего кошелька.

Как деревья Меркла используют в белых списках NFT?

NFT-проекты могут использовать корень Меркла для представления списка одобренных кошельков и проверять каждый кошелек с помощью доказательства при выпуске NFT.

Обеспечивают ли деревья Меркла конфиденциальность?

Деревья Меркла могут обеспечивать частичную конфиденциальность: пользователи могут подтвердить включение элемента, не раскрывая весь набор данных.

Являются ли деревья Меркла доказательствами с нулевым разглашением?

Нет. Деревья Меркла подтверждают включение данных в зафиксированный набор, а доказательства с нулевым разглашением могут подтверждать более общие утверждения без раскрытия конфиденциальных входных данных.

Заключение

Дерево Меркла — базовая криптографическая структура данных, упрощающая проверку больших наборов данных.

Оно объединяет множество элементов данных в дерево хешей и формирует один итоговый корень Меркла.

Этот корень может представлять транзакции, балансы, адреса, права на получение активов, значения хранилища и другие данные блокчейна.

Деревья Меркла важны, поскольку они обеспечивают эффективную проверку, сокращают расходы на хранение данных и поддерживают легкие клиенты, раздачи токенов, белые списки NFT и доказательства состояния блокчейна.

Bitcoin использует деревья Меркла для обобщения транзакций в блоках.

Ethereum использует связанную структуру — дерево Меркла — Патриции — для хранения состояния аккаунтов и хранилища.

Криптовалютные приложения используют деревья Меркла, когда им нужно подтвердить, что отдельный элемент входит в большой набор данных, не размещая весь набор в блокчейне.

Деревья Меркла эффективны, но требуют корректного хеширования, безопасного кодирования, доверенных корней и надежной проверки доказательств.

При правильном использовании они делают криптовалютные системы легче, дешевле и удобнее для проверки.