Merkle tree

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

История

Концепция хеш-дерева была предложена американским криптографом Ральфом Мерклом в 1979 году и запатентована в 1982 году (патент США № 4309569). Первоначально идея была разработана для создания эффективной схемы цифровой подписи, позволяющей подписывать большое количество сообщений одним мастер-ключом. Впоследствии метод был адаптирован для верификации целостности данных в распределённых системах, где доверие к центральному узлу отсутствует. Широкую известность деревья Меркла получили благодаря публикации в 2008 году статьи Сатоши Накамото, описывающей протокол биткоина, где они используются для компактного представления транзакций в блоках.

Принцип работы

Дерево Меркла строится снизу вверх. Процесс включает следующие шаги:

1. Разбиение данных: Исходный массив данных (например, список транзакций) делится на блоки фиксированного размера. Каждый блок хешируется с помощью криптографической хеш-функции (например, SHA-256 в биткоине). Полученные хеши становятся листьями дерева.
2. Построение уровней: Если количество листьев нечётное, последний лист дублируется (этот процесс называется «сбалансированное дерево»). Каждая пара соседних хешей (левый и правый дочерние узлы) конкатенируется (объединяется) и хешируется. Результат становится родительским узлом.
3. Рекурсия: Процесс повторяется для каждого нового уровня, пока не останется один узел — корень дерева (корневой хеш, или корень Меркла). Корень является уникальным цифровым отпечатком всего набора данных.

Пример

Пусть есть четыре блока данных: A, B, C, D.

• Листья: Hash(A), Hash(B), Hash(C), Hash(D).
• Уровень 1: Hash( Hash(A) + Hash(B) ), Hash( Hash(C) + Hash(D) ).
• Корень: Hash( Hash( Hash(A)+Hash(B) ) + Hash( Hash(C)+Hash(D) ) ).

Изменение любого из блоков (например, A на A') приведёт к изменению его хеша, что повлечёт за собой изменение всех вышестоящих узлов и, в конечном счёте, корня. Таким образом, корень Меркла служит криптографическим свидетельством неизменности всего набора данных.

Свойства и характеристики

• Целостность: Любое изменение хотя бы одного блока данных приводит к изменению корневого хеша. Это позволяет быстро обнаружить подделку или повреждение данных.
• Эффективность проверки: Для доказательства того, что конкретный блок данных (например, транзакция) содержится в наборе, не нужно загружать весь набор. Достаточно предоставить так называемый «путь Меркла» — последовательность хешей от листа до корня. Для набора из N блоков длина пути составляет O(log N). Например, для набора из 1024 блоков требуется всего 10 хешей для доказательства.
• Параллелизм: Деревья Меркла могут строиться параллельно, так как хеширование каждого блока независимо.
• Типы: Различают полные (сбалансированные) деревья, где все листья находятся на одном уровне, и неполные деревья, где уровни могут различаться.

Применение

Криптовалюты

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

• Компактное хранение: Полные узлы хранят весь блок, но лёгкие (SPV) клиенты хранят только заголовки блоков. Для проверки включения своей транзакции SPV-клиент запрашивает у полного узла только путь Меркла, а не весь блок.
• Проверка целостности: Любой участник сети может проверить, что транзакция действительно была включена в блок, сравнив предоставленный путь с корнем в заголовке блока.
• Защита от подделки: Злоумышленник не может изменить транзакцию в блоке, не изменив корень Меркла, что потребует пересчёта всех последующих блоков.

Распределённые файловые системы

В системах, таких как IPFS (InterPlanetary File System), деревья Меркла используются для адресации и верификации контента. Каждый файл разбивается на блоки, которые хешируются и связываются в дерево. Идентификатор файла (CID) является корнем этого дерева. Это обеспечивает дедупликацию (одинаковые блоки хранятся один раз) и возможность проверки целостности при загрузке.

Системы контроля версий

В Git, одной из самых популярных систем контроля версий, используется структура, близкая к дереву Меркла. Каждый коммит содержит хеши своего дерева (состояния файлов) и родительского коммита. Это позволяет однозначно идентифицировать состояние репозитория и проверять историю изменений.

Базы данных

Некоторые распределённые базы данных (например, Cassandra, DynamoDB) используют деревья Меркла для обнаружения рассинхронизации между репликами. Периодически узлы обмениваются корнями своих деревьев; если корни различаются, они рекурсивно спускаются по дереву, чтобы найти конкретные различающиеся блоки данных, минимизируя объём передаваемой информации.

Цифровые подписи

В схеме подписи Меркла (MSS) одноразовый ключ подписи используется для подписи одного сообщения. Дерево Меркла позволяет объединить множество таких одноразовых ключей в один мастер-ключ (корень), что даёт возможность подписывать до 2^n сообщений с помощью одного открытого ключа.

Критика и ограничения

• Вычислительные затраты: Построение дерева Меркла для очень больших наборов данных (миллиарды блоков) может быть ресурсоёмким, хотя и хорошо параллелится.
• Сложность обновления: Если данные часто изменяются, требуется пересчёт всех узлов, ведущих к корню. В системах с высокой частотой обновлений это может быть узким местом.
• Уязвимость к коллизиям: Безопасность дерева Меркла полностью зависит от стойкости используемой хеш-функции. Если найдена коллизия (два разных блока дают одинаковый хеш), безопасность рушится. На практике используются надёжные функции, такие как SHA-256.
• Размер доказательства: Хотя путь Меркла имеет логарифмическую длину, для очень больших деревьев (например, с 2^32 листьями) путь может составлять 32 хеша, что может быть значительным для некоторых приложений.

Интересные факты

• В протоколе биткоина для построения дерева Меркла используется двойное хеширование SHA-256 (SHA-256(SHA-256(data))), что повышает устойчивость к атакам.
• Существуют модификации деревьев Меркла, такие как «Patricia Merkle Tree» (используется в Ethereum), которые позволяют работать не только с массивами, но и с ассоциативными массивами (ключами).
• Термин «Merkle tree» часто используется как синоним «хеш-дерева», хотя Ральф Меркл предложил несколько вариантов, включая «Merkle DAG» (направленный ациклический граф).

Источники

• Ральф Меркл. «A Digital Signature Based on a Conventional Encryption Function» (1979).
• Сатоши Накамото. «Bitcoin: A Peer-to-Peer Electronic Cash System» (2008).
• Дэвид Вуд, Гэвин Вуд. «Ethereum: A Secure Decentralised Generalised Transaction Ledger» (2014).
• Стандарт NIST FIPS 180-4 (Secure Hash Standard).