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

За три дня, с 13 по 16 октября 2026 года, в коде этого сайта изменилось 64 файла из 4224. Как найти их, не сравнивая все файлы по одному? Git хранит каждую папку как список её содержимого и даёт ей имя — хеш этого списка. Если внутри папки что-то изменилось, изменился её список, а значит, и имя; если нет — имя то же. Ниже два настоящих снимка репозитория этого сайта. Спускайтесь от корня: папку с тем же хешем открывать незачем.

Пять корневых папок — пять сравнений, все пять различаются: за три дня работа шла везде. Но уже на втором уровне большая часть совпадает, и за каждой совпавшей папкой — сотни файлов, которые не нужно смотреть. Всего спуск сравнивает 758 хешей из 4703 и находит все 64 файла: 30 изменённых, 32 новых и 2 удалённых. Так работает git diff между коммитами, и поэтому он мгновенный даже в огромных репозиториях.

Идея

Разложим данные по листьям дерева и в каждом листе запишем хеш его данных, а в каждом внутреннем узле — хеш хешей его детей. Корень тогда — отпечаток всего набора: криптографический хеш нельзя подобрать так, чтобы два разных набора дали один корень. Два свойства делают дерево полезным. Сравнивая корни, узнаём, совпадают ли копии целиком; спускаясь только в различающиеся поддеревья, находим расхождения. А чтобы доказать, что конкретный лист есть в наборе с известным корнем, достаточно хешей соседей на пути от листа к корню — по одному на уровень.

Обычная хеш-сумма файла тоже отпечаток, но она отвечает только «да или нет». Дерево отвечает подробнее: где именно разошлось и как доказать, что элемент на месте, не пересылая остальных. Цена — хранить хеши узлов, примерно столько же, сколько листьев.

Почему подделать нельзя

Отсюда и надёжность доказательства включения: чтобы предъявить для чужого листа путь, который сходится к настоящему корню, нужно найти коллизию хотя бы на одном уровне. Для SHA-256 это никому не удалось. Git до сих пор по умолчанию пользуется SHA-1, для которой коллизию построили в 2017 году, и с версии 2.29 умеет хранить репозиторий на SHA-256.

Доказательство из log n хешей

Возьмём все 4222 файла нового снимка и построим над ними двоичное дерево, как в RFC 6962 — стандарте журналов прозрачности сертификатов. Чтобы доказать, что файл в дереве, достаточно соседей на пути к корню: на каждом уровне — хеш поддерева, с которым наше объединяется. Выберите любой файл. Полоски над списком — какие отрезки файлов покрывают эти соседи: вместе с самим файлом они покрывают все 4222.

Хешей в доказательстве 13: ⌈log₂ 4222⌉. Проверяющему не нужен ни один файл, кроме проверяемого, — только эти 13 чисел и корень, который он знает заранее. Поставьте «подменить файл»: изменится одна буква идентификатора, и на каждом уровне получится другой хеш, вплоть до корня. Обратите внимание на верхний уровень: соседом справа служат файлы 4097–4222, всего 126. В RFC 6962 левое поддерево всегда берёт наибольшую степень двойки, меньшую числа листьев, — здесь 4096, — а правое остаток, поэтому дерево неполное, и проверка доказательства должна это учитывать. Вторая задача в конце статьи как раз про это.

Зачем листу и узлу разные префиксы

В RFC 6962 хеш листа — SHA-256(0x00 ‖ данные), а хеш узла — SHA-256(0x01 ‖ левый ‖ правый). Без префиксов дерево можно обмануть. Внутренний узел — это хеш 64 байт, двух хешей детей. Если бы лист хешировался так же, то эти 64 байта можно было бы предъявить как «данные листа»: хеш получится тот же, что у узла, и доказательство для дерева поменьше — без нижнего уровня — сойдётся к настоящему корню. Проверяющий поверит, что в наборе есть «лист» из двух хешей, которого туда никто не клал. Разные префиксы делают хеши листьев и узлов несравнимыми.

Похожая беда была в Bitcoin. Там на уровне с нечётным числом узлов последний узел дублируется, и из-за этого два разных списка транзакций — с повторённой последней транзакцией и без — дают один корень. В 2012 году это описали как уязвимость CVE-2012-2459: узел, получивший испорченный вариант блока, считал недействительным и настоящий блок с тем же корнем. Неполные уровни нужно определять так, чтобы разные наборы листьев не могли дать одинаковое дерево; правило RFC 6962 — неравные поддеревья, без дублирования — устроено именно так.

Код

Программа читает те же два снимка кода сайта. Сначала сверка сверху вниз, как в git, с подсчётом сравнений. Потом двоичное дерево по RFC 6962 над файлами нового снимка, доказательство для routes/web.php и его проверка — честная и с подменённым файлом.

Проверка повторяет RFC 9162 почти дословно. Она знает только номер листа и размер дерева и по ним на каждом уровне решает, слева сосед или справа. Самое тонкое место — последнее поддерево неполного уровня: у него нет соседа справа, и оно поднимается выше без изменений. Корень 70268604… совпадает с тем, что показывает сцена выше, — хеши считал ваш браузер, а здесь Python и Go.

Сколько это стоит

Построение — O(n) хеширований: листьев n, внутренних узлов n − 1. Доказательство включения — O(log n) хешей, проверка — столько же хеширований. Изменение одного листа пересчитывает только его путь до корня, O(log n). Сверка двух копий с d расхождениями сравнивает O(d log n) пар хешей: каждое расхождение тянет за собой путь от корня, а общие верхние части путей сравниваются один раз. Если различается всё, сравнений 2n − 1 — больше, чем при простом сравнении листьев, так что дерево выгодно, когда расхождений мало.

В git узел — не двоичный, а целая папка: сравнение папки с сотней файлов стоит сотню сравнений. Поэтому спуск по нашим двум снимкам обошёлся в 758 сравнений, а по двоичному дереву над теми же файлами — в 423, это первая задача. Зато путь в git короче: глубина папок здесь семь уровней, а в двоичном дереве — тринадцать.

Где работает

Git. Идентификатор файла — хеш его содержимого, папки — хеш списка её файлов и подпапок, коммита — хеш корневой папки, родителей и описания. Подменить один байт в истории, не изменив все идентификаторы выше, нельзя, и поэтому идентификатор коммита гарантирует всё содержимое репозитория на тот момент.

Журналы прозрачности сертификатов. Удостоверяющие центры записывают каждый выданный сертификат для HTTPS в публичные журналы — деревья Меркла по RFC 6962 (с 2021 года — RFC 9162). Браузер может проверить, что сертификат в журнале, по нескольким десяткам хешей, а наблюдатели — что журнал только дописывается и ничего не теряет.

Блокчейны. В заголовке блока Bitcoin хранится корень дерева его транзакций. Лёгкому клиенту, который не хранит блоки целиком, достаточно заголовков и пути от своей транзакции к корню — так описана «упрощённая проверка платежей» в статье Сатоши Накамото 2008 года.

Базы данных. В Amazon Dynamo (2007) и Apache Cassandra реплики сверяют данные деревьями Меркла по диапазонам ключей: сначала корни, потом только различающиеся поддеревья. Чем меньше разошлось, тем меньше пересылать.

История

Ральф Меркл придумал хеш-деревья в 1979 году, чтобы строить цифровые подписи из одной только хеш-функции. Одноразовую подпись можно сделать на хешах, но каждую — только для одного сообщения; дерево позволяет опубликовать один корень и подписывать тысячи сообщений, прикладывая к подписи путь до корня. Патент на этот способ он получил в 1982 году. Подписи Меркла долго оставались курьёзом, а теперь возвращаются: хеш-подписи устойчивы к квантовым компьютерам, и на дереве Меркла построен стандарт SPHINCS+, принятый NIST в 2024 году как SLH-DSA.

Задачи

В первой задаче нужно сосчитать, во сколько сравнений хешей обойдётся сверка двух реплик, и среди тестов — те же два снимка кода сайта. Во второй — проверить доказательство включения, в том числе для деревьев из 10¹⁸ листов, где «по битам номера» ошибается на последних поддеревьях.