Деревья Меркла: целостность транзакций в большом масштабе

Блок Биткоина содержит около 2000 транзакций. Чтобы доказать включение транзакции T, не загружая все 2000 транзакций, нужно компактное доказательство. Деревья Меркла решают эту задачу: размер доказательства равен O(log n) хешей вместо O(n) транзакций.

Листья: SHA256d (двойной SHA256) каждой транзакции. Родительский узел: SHA256d(left_child_hash || right_child_hash). Повторяйте процесс, пока не останется один корневой хеш. Если число узлов нечётное, продублируйте последний узел. Корень — это корень Меркла, сохранённый в заголовке блока (32 байта).

import hashlib def sha256d(x): return hashlib.sha256(hashlib.sha256(x).digest()).digest() def merkle_root(txids): if len(txids)%2: txids.append(txids[-1]) while len(txids)>1: txids=[sha256d(txids[i]+txids[i+1]) for i in range(0,len(txids),2)] return txids[0].hex()

Чтобы доказать, что транзакция T находится на позиции i, предоставьте хеши соседних узлов на каждом уровне — от листа T до корня (O(log n) хешей). Проверяющий пересчитывает корень по T и пути соседних узлов. Если вычисленный корень совпадает с корнем Меркла в заголовке блока, включение T доказано.

1024 транзакции → доказательство Меркла = 10 хешей = 320 байт. Полный блок = ~1 MB. Клиенты SPV загружают только заголовок размером 80 байт и 320-байтовое доказательство Меркла для каждой интересующей их транзакции — экономия пропускной способности 99.97% по сравнению с загрузкой полного блока.

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

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

Диапазон гор Меркла (MMR) — это добавляемая структура Меркла для данных, организованных подобно журналу. Новые элементы добавляются в конец, а вершины (корни поддеревьев размера, равного степени двойки) поддерживаются в актуальном состоянии. Используется в Grin/MimbleWimble и ZCash для эффективных компактных доказательств над журналом, в который можно только добавлять записи.

Согласно плану развития Эфириума, деревья Веркле заменят деревья Меркла (EIP-6800): вместо хешей используются векторные обязательства (полиномиальные обязательства KZG). Размер доказательства: O(1) вместо O(log n) у Меркла. Это позволяет клиентам без состояния проверять состояние, не храня полное префиксное дерево.

Certificate Transparency (RFC 6962) использует журнал Меркла, в который можно только добавлять записи: каждый сертификат, выданный CA, является листом. Доказательства включения подтверждают, что сертификат был занесён в журнал. Доказательства согласованности подтверждают, что журнал допускает только добавление записей, без удаления или вставки. Браузеры проверяют подписанные отметки сертификатов через этот журнал.

Деревья Git (снимки каталогов) являются деревьями Меркла: каждый узел дерева хеширует объекты содержимого файлов и поддеревья. Хеш коммита однозначно идентифицирует состояние всей кодовой базы. Поэтому команда git checkout всегда восстанавливает ровно те же файлы.

Сколько хешей требуется в доказательстве Меркла, чтобы доказать включение элемента в дерево с 1024 листьями?

Деревья Меркла обеспечивают доказательства включения размера O(log n). Биткоин хранит корень Меркла в заголовках блоков, а клиенты SPV используют доказательства. Эфириум расширяет этот подход до префиксных деревьев Меркла — Патрисия. Деревья Веркле заменят деревья Меркла и обеспечат доказательства размера O(1). Далее: майнинг с доказательством выполнения работы и сложность.