Дерево Меркла (также называемое бинарным хеш-деревом) — это структура данных, используемая в блокчейнах для эффективного обобщения и проверки больших наборов данных. Каждый листовой узел содержит хеш блока данных (транзакции), каждый нелистовой узел содержит хеш своих дочерних узлов, а корень — Корень Меркла — это единый хеш, представляющий все транзакции во всем блоке.
И Bitcoin, и Ethereum используют деревья Меркла для организации транзакций внутри каждого блока. Корень Меркла хранится в заголовке блока, что позволяет Доказательства Меркла — Математические доказательства включения конкретной транзакции в блок с использованием лишь небольшого количества хешей (O(log n)), а не с требованием загрузки всех транзакций. Это позволяет осуществлять упрощенную проверку для SPV и облегченных клиентов без загрузки всего блокчейна.
Структура дерева Меркла
4 transactions in a block: Tx1, Tx2, Tx3, Tx4
Step 1: Hash each transaction (Bitcoin uses double SHA-256)
H1 = SHA256(SHA256(Tx1)) = "abc..."
H2 = SHA256(SHA256(Tx2)) = "def..."
H3 = SHA256(SHA256(Tx3)) = "ghi..."
H4 = SHA256(SHA256(Tx4)) = "jkl..."
Step 2: Hash pairs of child nodes
H12 = SHA256(SHA256(H1 + H2)) = "mno..."
H34 = SHA256(SHA256(H3 + H4)) = "pqr..."
Step 3: Hash to root
Merkle Root = SHA256(SHA256(H12 + H34)) = "stu..."
Tree structure:
Merkle Root (stu...)
/ \
H12 (mno...) H34 (pqr...)
/ \ / \
H1(abc) H2(def) H3(ghi) H4(jkl)
| | | |
Tx1 Tx2 Tx3 Tx4
Merkle Proof for Tx3 (prove Tx3 is in block):
Provide: H4, H12
Verifier computes:
H3 = hash(Tx3) ← from the transaction itself
H34 = hash(H3 + H4) ← H4 provided
Root = hash(H12 + H34) ← H12 provided
If computed Root matches block header Root → Tx3 confirmed ✓
Data required: 2 hashes (not all 4 transactions)
For a block with 4,096 transactions:
Proof requires only 12 hashes — not 4,096
For 1,000,000 transactions: ~20 hashesПримечание по поводу нестандартного количества транзакций: Если блок содержит нечётное количество транзакций, хеш последней транзакции дублируется для образования пары — это известная особенность реализации дерева Меркла в Биткоине.
Применение деревьев Меркла
| Области применения | Как используются деревья Меркла |
|---|---|
| Биткоин-блоки | Корневой блок транзакций Меркла хранится в заголовке блока; позволяет использовать SPV-доказательства для облегченных кошельков. |
| Состояние Ethereum | Для хранения данных, состояний учетных записей и записей о транзакциях/поступлениях используется дерево Меркла-Патриции (MPT); в качестве обновления планируется использование деревьев Веркла. |
| Условия участия в аирдропе | Доказательства Меркла проверяют отдельные адреса в блокчейне без хранения полного списка получателей в контракте. |
| ZK пруфы | Доказательства Меркла можно проверить внутри схем ZK для доказательств компактного включения. |
| Git (контроль версий) | Git использует ориентированный ациклический граф (DAG) объектов с адресацией по содержимому — структуру, вдохновленную деревьями Меркла и тесно с ними связанную. |
| Прозрачность сертификата | Журналы Меркла, содержащие только добавление данных, позволяют проводить публичный аудит всех выданных TLS-сертификатов. |
| Клиенты без гражданства | Доказательства Меркла/Веркла позволяют узлам проверять блоки без хранения полного состояния. |
FAQ
В: Как в DeFi-аирдропах используются деревья Меркла?
Аирдропы используют деревья Меркла для подтверждения права на участие в блокчейне без хранения всех подходящих адресов в контракте, что было бы непомерно дорого в больших масштабах. Протокол создает дерево Меркла из всех подходящих адресов и сумм, а корневое дерево хранится в блокчейне. Подходящие пользователи предоставляют свой адрес и доказательство Меркла — небольшой набор хешей. Контракт проверяет доказательство по сохраненному корневому дереву и, если оно действительно, выдает заявку. Это позволяет эффективно проверять миллионы подходящих адресов с помощью всего лишь одного 32-байтового корневого дерева Меркла, хранящегося в блокчейне.
В: Что такое триада Меркла-Патриции?
В Ethereum используется более сложный вариант, называемый Меркле Патрисия Три (MPT) — сочетание дерева Меркла (криптографическое хеширование для проверки целостности) с префиксным деревом Патрисии (префиксно-сжатая структура для эффективного поиска по ключу). Ethereum поддерживает три отдельных MPT для каждого блока: государственное испытание (все остатки на счетах и хранение по контракту), дерево транзакций (все транзакции в блоке), и попытка получения (результаты выполнения транзакций и журналы). Это позволяет эффективно подтверждать состояние — доказывать баланс любого счета или любое значение хранилища в любом историческом блоке. В план развития Ethereum входит переход от MPT к Веркле Деревья, которые позволяют получать еще более компактные доказательства и обеспечивают работу клиентов без сохранения состояния.
В: Как доказательства Меркла помогают облегченным клиентам (SPV-кошелькам)?
Лёгкий кошелек — например, мобильный биткоин-кошелек — не загружает весь блокчейн, а только заголовки блоков (по 80 байт каждый). Для подтверждения транзакции он запрашивает доказательство Меркла у полного узла: небольшой набор хешей, подтверждающих включение транзакции в конкретный блок. Для биткоин-блока с тысячами транзакций это доказательство требует примерно 20 хешей вместо загрузки всех транзакций. Это позволяет проверять транзакции с помощью килобайтов данных, а не гигабайтов, что делает мобильные криптокошельки практичными.
В: Что произойдет, если у дерева Меркла будет нечетное количество листьев?
В реализации Биткоина, если количество транзакций нечетное, хеш последней транзакции дублируется, чтобы его можно было сопоставить и хешировать. Это известная особенность оригинальной архитектуры дерева Меркла Биткоина, и на практике она не имеет последствий для безопасности, хотя исследователи протокола отмечают ее неэлегантность.
В: Чем деревья Меркла отличаются от деревьев Веркла?
Деревья Веркле — это предлагаемый преемник деревьев Меркле Патрисии в Ethereum. Они используют векторные обязательства (на основе криптографии эллиптических кривых) вместо обязательств, основанных на хешировании, что приводит к значительному уменьшению размера доказательств. Доказательство Веркла для большого числа листьев может быть в разы меньше по размеру, чем эквивалентное доказательство Меркла — критически важное свойство для обеспечения возможности использования безсостоятельных клиентов Ethereum, которым не нужно хранить полное состояние.
Связанные условия
SHA-256 · Криптографическая хеш-функция · Bitcoin · Ethereum · Light Client (SPV) · Airdrop · ЗК Доказательство · Дерево Веркла · Меркл Патрисия Три
Совет от UPay: Деревья Меркла объясняют, почему верификация в блокчейне эффективна, а не просто теоретически полна. Когда вы подтверждаете транзакцию на Etherscan, вы фактически проверяете доказательство Меркла. Когда вы получаете аирдроп, отправляя транзакцию в блокчейне, вы предоставляете доказательство Меркла, подтверждающее ваше право на участие. Когда мобильный кошелек подтверждает платеж в биткоинах без загрузки всей цепочки, он использует SPV с доказательствами Меркла. Понимание деревьев Меркла помогает оценить, почему верификация в блокчейне является одновременно криптографически доказуемой и практически эффективной — вам никогда не нужно загружать все данные, чтобы что-либо проверить.
Предупреждение: Данная информация предназначена исключительно для образовательных целей и не является финансовой консультацией.
