Блокчейн

Merkle Trees: дерево доверия

Цели урока

  • Объяснять, как Merkle Tree сворачивает тысячи транзакций в один корневой хеш
  • Строить Merkle Proof и понимать, почему его размер O(log N)
  • Сравнивать полную ноду и SPV-клиент по объёму данных и уровню безопасности
  • Называть применения Merkle Trees за пределами блокчейна

Предварительные знания

  • Hash Functions: the foundation of blockchain

Блок Bitcoin содержит ~2500 транзакций. Ethereum обрабатывает 1+ миллион транзакций в день. Мобильный кошелёк хранит 60 МБ вместо 500 ГБ и при этом криптографически верифицирует каждую транзакцию. Не доверяет - доказывает. Ответ: структура данных, запатентованная в 1979 году - за 30 лет до Bitcoin. Рецензенты тогда её не поняли.

  • **Bitcoin SPV** - мобильные кошельки проверяют транзакции через Merkle Proof, храня 60 МБ вместо 500+ ГБ
  • **Git** - каждый коммит содержит Merkle Tree файлов проекта. `git diff` работает эффективно именно благодаря этой структуре
  • **Amazon DynamoDB** - использует Merkle Trees для синхронизации реплик (anti-entropy protocol)

Ральф Меркл - больше чем дерево

Ральф Меркл опубликовал идею хеш-дерева в докторской диссертации в Стэнфорде. Это была часть более широкой работы по **криптографии с открытым ключом** - Меркл независимо от Диффи и Хеллмана предложил протокол обмена ключами (Merkle's Puzzles). Первая научная статья была **отклонена** рецензентами - не поняли идею. Меркл стал одним из пионеров нанотехнологий и крионики.

Без Merkle Trees блокчейн был бы непрактичным: каждая проверка транзакции требовала бы скачивания всего блока.

Merkle Root: один хеш для всех данных

1979 год. Ральф Меркл защищает диссертацию в Стэнфорде. Рецензенты отклоняют статью - не понимают идею. 2009 год. Сатоши Накамото вставляет дерево Меркла в Bitcoin. 2024 год. Мобильные кошельки проверяют транзакции на телефоне, не скачивая 500 ГБ блокчейна. Идея, которую не поняли в 1979-м, стала фундаментом цифровой экономики.

SHA-256 создаёт «отпечаток» данных. Но как создать отпечаток **тысяч транзакций** сразу, при этом сохраняя возможность проверить **каждую по отдельности**? **Merkle Tree** сворачивает любое количество элементов в **один хеш** - **Merkle Root**. Этот корневой хеш записывается в заголовок блока. 80 байт обнимают тысячи транзакций.

Построение снизу вверх: 1. Хешируем каждую транзакцию - получаем листья дерева 2. Попарно хешируем листья - получаем следующий уровень 3. Повторяем, пока не останется **один хеш** - корень

**В Bitcoin** каждый блок содержит Merkle Root всех транзакций. Заголовок блока - всего **80 байт**, но через Merkle Root он «обнимает» тысячи транзакций.

Блок содержит 2048 транзакций. Сколько уровней будет в Merkle Tree?

Proof of Inclusion: проверка без скачивания

Главная суперсила Merkle Tree - возможность **доказать**, что конкретная транзакция входит в блок, **не раскрывая остальные транзакции** и не скачивая весь блок. Это как доказать, что конкретное дерево в лесу - не вырубая весь лес, а показав путь к нему.

**Merkle Proof** (или Merkle Path) - набор «соседних» хешей на пути от листа к корню. Имея proof, возможно самостоятельно вычислить Merkle Root и сравнить его с записанным в заголовке блока.

**Эффективность:** в блоке с 4096 транзакциями Merkle Proof состоит из **12 хешей** (log₂(4096) = 12). Это 12 * 32 = **384 байта** вместо скачивания всего блока (~1-2 МБ).

Блок содержит 1 000 000 транзакций. Сколько хешей нужно в Merkle Proof для проверки одной транзакции?

Бинарное дерево хешей: почему именно дерево?

Почему именно **бинарное дерево**, а не конкатенация и хеширование всех транзакций? Можно вычислить `SHA256(Tx1 + Tx2 + ... + TxN)` - один хеш, задача решена. Проблема: при наивном хешировании **невозможно доказать** включение отдельной транзакции без раскрытия всех остальных. Для проверки пришлось бы скачать **все транзакции**.

ПодходРазмер proofПроверка одной Tx
Наивный хеш всех TxO(N) - все транзакцииСкачать весь блок
Merkle TreeO(log N) - path от листа к корню~20 хешей для 1M транзакций
Без хешаO(N) - все транзакцииСкачать весь блок + проверить подписи

**Почему бинарное?** Каждый узел объединяет ровно два дочерних хеша. Это даёт: - **Минимальную высоту** дерева: $\log_2 N$ - **Простую навигацию**: на каждом уровне - left или right - **Эффективное обновление**: замена одной транзакции требует пересчёта $\log_2 N$ хешей

Обновление транзакции в Merkle Tree

Что происходит при изменении одного листа

Допустим, Tx C изменилась. Нужно пересчитать: 1. H(C) - новый хеш листа 2. Hash(CD) - родитель изменился 3. Merkle Root - корень изменился Итого: 3 пересчёта для дерева из 4 листьев. Для дерева из 1 000 000 листьев: ~20 пересчётов. Вся остальная структура остаётся нетронутой.

**Вариации:** кроме бинарных, существуют **Patricia Trie** (Ethereum использует Modified Merkle Patricia Trie для хранения состояния) и **Verkle Trees** (готовятся для Ethereum 2.0, ещё компактнее).

Почему Merkle Tree лучше наивного хеширования всех транзакций (SHA256(Tx1+Tx2+...+TxN))?

Лёгкие клиенты (SPV)

Полная нода Bitcoin хранит **всю** историю блокчейна - более **500 ГБ** данных. Именно здесь Merkle Tree превращает теорию в реальный продукт. **SPV (Simplified Payment Verification)** - метод из оригинальной статьи Сатоши Накамото. SPV-клиент скачивает только **заголовки блоков** (80 байт каждый) и запрашивает Merkle Proof для нужных транзакций.

Как работает SPV: 1. Скачивает все заголовки блоков (содержат Merkle Root) 2. Когда нужно проверить транзакцию - запрашивает Merkle Proof у полной ноды 3. Верифицирует proof самостоятельно - вычисляет путь до Root 4. Сравнивает с Merkle Root из заголовка - если совпадает, транзакция валидна

Ethereum и лёгкие клиенты

Как Merkle Trees используются за пределами Bitcoin

Ethereum хранит в Merkle Trie не только транзакции, но и: - State Trie - балансы и данные всех аккаунтов - Storage Trie - данные смарт-контрактов - Receipts Trie - результаты выполнения транзакций Лёгкий клиент Ethereum может запросить: «Какой баланс у адреса 0xABC?» с Merkle Proof, не скачивая всю базу состояний (~200 ГБ).

**Ограничение SPV:** лёгкий клиент доверяет полной ноде в том, что та не скроет данные. SPV может проверить включение транзакции, но не может убедиться, что нода показала **все** транзакции. Для полной безопасности нужна полная нода.

Merkle Tree нужен только для блокчейна

Merkle Trees используются в Git (деревья объектов), BitTorrent (проверка фрагментов), Amazon DynamoDB (anti-entropy), ZFS (целостность данных), Certificate Transparency (SSL-сертификаты) и многих других системах.

Merkle Tree - универсальная структура данных для эффективной верификации. Ральф Меркл запатентовал её в 1979 году - за 30 лет до Bitcoin. Блокчейн лишь сделал её знаменитой.

Почему мобильный Bitcoin-кошелёк может работать без скачивания 500 ГБ блокчейна?

Ключевые идеи

  • **Merkle Root** - один хеш, который «обнимает» все транзакции блока через бинарное дерево хешей. Заголовок блока 80 байт - но корень знает о тысячах транзакций
  • **Merkle Proof** - набор из ~20 хешей для проверки одной транзакции среди миллиона (O(log N)). Именно это позволяет мобильному кошельку работать без сотен гигабайт данных
  • **Бинарное дерево** даёт логарифмическую сложность proof и эффективное обновление при изменении транзакции
  • **SPV-клиенты** скачивают только заголовки блоков (~60 МБ) и используют Merkle Proof для верификации. 500 ГБ -> 60 МБ - разница в 8000 раз

Связанные темы

Merkle Trees связывают криптографию с эффективными структурами данных:

  • Хеш-функции — SHA-256 - строительный блок каждого узла Merkle Tree
  • P2P-сети — Merkle Trees позволяют верифицировать данные от недоверенных пиров
  • Ethereum State — Modified Merkle Patricia Trie хранит всё состояние Ethereum

Вопросы для размышления

  • Если Merkle Tree так эффективен, почему не все базы данных используют его?
  • Что произойдёт, если в дереве нечётное количество транзакций - как построить бинарное дерево?
  • Как использовать Merkle Tree для синхронизации файлов между двумя компьютерами?

Связанные уроки

  • bc-02-hashing — SHA-256 - строительный блок каждого узла Merkle Tree
  • bc-04-p2p — P2P-сети используют Merkle Proof для верификации данных от недоверенных пиров
  • alg-08 — Деревья как структуры данных - общая база для понимания Merkle Tree
  • alg-02 — O(log N) поиск в бинарных деревьях - та же логика что Merkle Proof
  • ds-14 — Distributed storage использует Merkle Trees для anti-entropy синхронизации
  • sec-03 — Certificate Transparency Log основан на Merkle Trees
  • crypto-19-hash-functions
  • alg-12-bfs
Merkle Trees: дерево доверия

0

1

Войти