Блокчейн/Уровень II · Механика/2.3 Блоки и цепочка/Урок 2
Деревья Меркла
32-байтовый отпечаток, связывающий тысячи транзакций
МатериалыЭксплорер блоков с визуализацией ветвей МерклаЧетыре короткие буквенно-цифровые метки (A, B, C, D)Инструмент двойного хеширования SHA-256
Любопытство
- Как одно значение хеша может подтверждать включение четырёх тысяч разных транзакций?
- Почему Сатоши решил объединять одинокий последний элемент в пару с самим собой и чего стоил этот выбор?
- Какую именно уязвимость правило дублирования пар внесло в раннюю реализацию Bitcoin?
Исследование
- Ральф Меркл подал заявку на патент на двоичное дерево хешей в 1979 году (патент выдан в 1982-м) — структуру данных для эффективного компактного представления больших наборов данных. В Bitcoin эта архитектура сводит тысячи идентификаторов транзакций к одному 32-байтовому значению — корню Меркла. Этот корень записывается непосредственно в 80-байтовый заголовок блока и тем самым создаёт неизменяемую криптографическую фиксацию каждой транзакции в этом блоке.
- Построение идёт рекурсивно снизу вверх. Идентификаторы транзакций попарно объединяются и хешируются двойным SHA-256, образуя родительские узлы. Такое попарное объединение продолжается уровень за уровнем, пока не останется один корневой хеш. Если на каком-либо уровне нечётное число элементов, последний элемент объединяется в пару с самим собой, чтобы сохранить двоичную структуру и обеспечить правильную балансировку дерева на каждом этапе.
- Логарифмический характер этой структуры делает возможной упрощённую проверку платежей (SPV). Лёгкий клиент не загружает полные блоки — вместо этого он запрашивает у полной ноды ветвь Меркла. Эта ветвь состоит только из соседних хешей на пути от конкретной транзакции к корню. Для блока с 4 000 транзакций такое доказательство требует примерно двенадцати значений хешей — ничтожной доли общего объёма данных.
- Объединяя хеш своей транзакции с полученными соседними хешами, лёгкий клиент заново вычисляет корень Меркла и сравнивает его со значением в загруженном заголовке блока. Если они совпадают, включение транзакции подтверждено криптографически — без хранения всей цепочки. Благодаря этому механизму мобильные кошельки могут безопасно работать на устройствах с ограниченными памятью и вычислительной мощностью.
- Segregated Witness (SegWit), активированный в августе 2017 года, ввёл вторую структуру дерева Меркла. Исходное дерево фиксирует идентификаторы транзакций, а witness-дерево — witness-идентификаторы транзакций. Корень второго дерева не хранится в заголовке: он фиксируется в выходе OP_RETURN coinbase-транзакции, который старые ноды воспринимают как обычные данные, что сохраняет совместимость.
- Правило объединения элемента с самим собой скрывало уязвимость (CVE-2012-2459). Поскольку одинокий последний элемент объединяется в пару с самим собой, список транзакций, оканчивающийся продублированной парой, даёт тот же корень Меркла, что и список без дубликата. Злоумышленник мог распространять такую искажённую версию валидного блока; ноды, отклонившие её, могли пометить хеш настоящего блока как недействительный и рассинхронизироваться с сетью. Исправление 2012 года научило ноды распознавать этот шаблон, а не кешировать блок как недействительный.
Ключевые факты
- Корень Меркла — это единственный 32-байтовый хеш в заголовке блока, который фиксирует все транзакции этого блока.
- Bitcoin использует двойное хеширование SHA-256 на каждом уровне построения дерева Меркла.
- Нечётное количество элементов на любом уровне обрабатывается так: последний элемент объединяется в пару с самим собой.
- Доказательство Меркла для транзакции в большом блоке обычно требует около двенадцати соседних хешей.
- SegWit добавил второе дерево Меркла, построенное из witness-идентификаторов транзакций и зафиксированное в coinbase-транзакции.
- CVE-2012-2459 — это баг, связанный с логикой обработки дублирующихся пар в ранних версиях Bitcoin Core.
Упражнение девять, шесть, три, один
9СобратьПеречислите 9 реально существующих систем или протоколов, которые используют деревья хешей для проверки целостности данных.
6СгруппироватьСгруппируйте 9 элементов в 6 групп по тому, что они защищают: файлы, пакеты программного обеспечения, сертификаты, базы данных, блокчейны или другое.
3Выделить главноеСведите 6 групп к 3 основным причинам, по которым для больших наборов данных логарифмическая структура доказательств предпочтительнее линейного перебора.
1КристаллизоватьНапишите одно предложение о том, как изменение одного бита в листовом узле меняет весь корневой хеш.
Проверка фактов
Даты, цифры и утверждения были проверены по приведенным ниже опубликованным источникам.