Merkle Tree последовательно объединяет криптографические отпечатки данных в один результат. В Bitcoin так получается Merkle root, записанный в заголовке блока. Несколько дополнительных отпечатков позволяют проверить соответствие транзакции этому корню без передачи всех остальных транзакций.
Кошелёк показывает, что платёж включён в блок. Как проверить это, не скачивая всё содержимое? Здесь помогает Merkle Tree. Транзакции сначала представляют хешами — короткими криптографическими отпечатками. Их постепенно объединяют в один общий отпечаток, корень. Заголовок содержит этот Merkle root и связывает блок с его транзакциями. Корень не архив, из которого можно прочитать все платежи; он служит для проверки предъявленных данных. [1] [2]
Представьте четыре транзакции A, B, C и D. Берём их отпечатки, соединяем A с B и вычисляем новый хеш AB. Так же из C и D получаем CD. Наконец, объединяем отпечатки AB и CD и вычисляем корень. Буквы лишь обозначают транзакции и промежуточные результаты, а не настоящие хеши. Процесс похож на перевёрнутое дерево: множество листьев через ветви сходится к одному корню. Больше транзакций добавляет уровни, но принцип остаётся тем же. [3]
Чтобы проверить B, вы берёте её данные и вычисляете отпечаток. Достаточно получить отпечаток A и общий отпечаток CD с их правильным порядком. Из A и B строите AB, затем из AB и CD вычисляете корень и сравниваете с корнем в заголовке. Этот дополнительный путь называется Merkle proof. Содержимое A, C и D знать не нужно. Для сбалансированного дерева из 1024 транзакций путь содержит 10 соседних хешей. Поэтому доказательство растёт гораздо медленнее полного списка транзакций. [2] [3]
Совпадение доказательства с корнем не означает, что можно слепо доверять предъявленному заголовку. Нужно проверить Proof of Work: соответствует ли результат майнинговых вычислений требуемой сложности? Также проверяют связь заголовка с соответствующей цепочкой. Даже тогда Merkle proof не проверяет все подписи и правила всех транзакций блока. Это делает Full Node. Поэтому описанная в whitepaper упрощённая проверка платежей SPV имеет иные предположения о безопасности, чем полная валидация. Реорганизация также может вывести блок из активной ветви: его содержимое по-прежнему можно доказать, но положение платежа в текущей истории может измениться. [2]
В обычном дереве Bitcoin листья — идентификаторы txid в порядке транзакций блока, начиная с Coinbase Transaction — особой транзакции, через которую майнер получает награду за блок. Пары соединяют как байты и дважды хешируют SHA-256. Если на уровне остаётся последний хеш без пары, для расчёта его удваивают; дополнительный платёж не создаётся. У единственной транзакции её txid сразу является корнем. Удвоение требует тщательных проверок дубликатов в реализации. Обновление протокола SegWit также отделяет данные witness, например подписи. С блоком их связывает ещё один криптографический отпечаток, записанный в Coinbase Transaction. Этот отпечаток называется witness commitment. Поэтому обычное дерево txid нельзя путать с деревом witness. [3] [4]
Для полной картины прочитайте эту статью вместе с Block, Транзакция, Block Header. На эту статью также ссылаются Block Header, Hash, SHA-256, Подтверждение.