Дерево Меркла

Хеши транзакций объединяют в пары, хешируют каждую пару и повторяют, пока не останется один хеш. Это единственное значение попадает в заголовок блока, а для доказательства того, что транзакция входит в него, нужны только хеши вдоль одного пути: одиннадцать из них, 352 байта, для блока с 2000 платежами. Именно поэтому кошелек на смартфоне может проверить, что ваши биткоины пришли, не скачивая блок.

Как это работает

Дерево Меркла превращает список в пирамиду, попарно хешируя соседние элементы уровень за уровнем, пока не останется один хеш.

Листья дерева представляют собой идентификаторы транзакций в том порядке, в каком их разместил майнер. Биткоин объединяет каждую пару, конкатенируя два значения по 32 байта и дважды применяя SHA-256 к результату. Когда на уровне оказывается нечетное число элементов, последний объединяют с его копией, что сохраняет простоту алгоритма и однажды вызвало реальные проблемы: уязвимость, каталогизированная как CVE-2012-2459, раскрытая в мае 2012 года и исправленная в том же месяце, использовала это дублирование, чтобы построить блок, который узлы считали недействительным, хотя сами транзакции были в порядке.

Выигрыш логарифмический. Удвоение числа транзакций добавляет один уровень, а не один хеш на транзакцию. Блоку с 1024 платежами нужно десять хешей, чтобы доказать принадлежность, то есть 320 байт. Блоку с четырьмя тысячами девяноста шестью нужно двенадцать, то есть 384 байта. Тот, кто проверяет доказательство, пересчитывает путь вверх и сравнивает результат с корнем, которому он уже доверяет по заголовку, и подделать путь, не сломав SHA-256, невозможно.

Ничто из этого не возникло в биткоине. Ральф Меркл описал эту конструкцию в патентной заявке, которая стала патентом US 4 309 569, поданной в 1979 году и выданной в январе 1982 года. Белая книга цитирует его работу и находит для дерева два применения: обрезка израсходованных транзакций из старых блоков для экономии места на диске, в разделе 7, и проверка платежа клиентом, который хранит только заголовки, в разделе 8.

Где это встречается

Деревья Меркла встречаются везде, где системе нужно доказать, что один элемент принадлежит большому набору, не передавая сам набор.

Внутри биткоина каждый заголовок блока несет вершину такого дерева. Узел заново строит дерево из полученных транзакций и отвергает блок, если результат не совпадает. Bitcoin Core предоставляет этот механизм напрямую: gettxoutproof создает сериализованное доказательство того, что транзакция включена в блок, а verifytxoutproof проверяет его, и это практичный способ передать кому-либо подтверждение платежа, не давая ему кошелек.

В других местах биткоина Taproot строит второе дерево: альтернативные условия расходования выхода Taproot организованы в виде дерева, поэтому раскрытие использованной ветви ничего не сообщает о ветвях, которые не использовались. За пределами биткоина та же форма лежит в основе истории коммитов Git, журналов Certificate Transparency, которые выявляют неправомерно выданные веб-сертификаты, и проверок целостности данных в файловой системе ZFS.

Для пользователя кошелька видимое следствие невелико и полезно. Легкий клиент, который хранит несколько десятков мегабайт заголовков, может подтвердить, что ваша транзакция находится в конкретном блоке на конкретной глубине, и получит ложный ответ только в том случае, если кто-то создал действительное доказательство работы на поддельной цепи, а это стоит реальных денег.

Дерево Меркла vs корень Меркла

Дерево Меркла является рабочей структурой; корень Меркла представляет собой единственное значение, которое сохраняется после. Узел строит всю пирамиду в памяти во время проверки блока, а затем отбрасывает ее, сохраняя только 32 байта, оказавшиеся на вершине, потому что все, что ниже, можно восстановить из транзакций. Когда обозреватель блоков показывает вам поле под названием корень Меркла, это и есть сохранившееся значение. Дерево никто не хранит, и в этом нет необходимости.