Merkle-дерево: как проверять целостность больших объёмов данных

Прямой ответ

Merkle-дерево (хеш-дерево) — структура, в которой каждый узел содержит хеш от объединения хешей своих потомков. Листья содержат хеши блоков данных, внутренние узлы — хеши пар дочерних хешей, корень — один хеш, называемый Merkle root.

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

Как строится:

1. Данные делятся на блоки фиксированного или переменного размера.
2. Каждый блок хешируется — получаются листья.
3. Пары соседних хешей конкатенируются и хешируются — получается следующий уровень.
4. Процесс повторяется до одного корневого хеша. При нечётном числе узлов последний обычно дублируют.

Стоимость операций:

Третья строка — Merkle proof: чтобы убедить проверяющего, что конкретный блок входит в набор, достаточно передать сам блок и log n «соседних» хешей по пути к корню. Проверяющий вычисляет корень и сравнивает с известным.

import hashlib

def merkle_root(leaves: list[bytes]) -> bytes:
    level = [hashlib.sha256(x).digest() for x in leaves]
    while len(level) > 1:
        if len(level) % 2:
            level.append(level[-1])
        level = [hashlib.sha256(a + b).digest() for a, b in zip(level[::2], level[1::2])]
    return level[0]

Практика: где это используется и как применять

1. Git. Каждый объект в Git — это содержимое вместе с заголовком, продублированное через SHA-1 или SHA-256; коммит ссылается на хеш дерева, дерево — на хеши blob-объектов. Изменение одного файла меняет хеш дерева и, следовательно, хеш коммита. Отсюда свойство: история, на которую ссылается общий хеш, идентична побайтово.

2. Файловые системы. ZFS и Btrfs хранят хеши блоков и проверяют их при чтении. Это обнаруживает «тихую порчу» данных, которую контрольные суммы на уровне тома не ловят.

3. Anti-entropy в распределённых БД. В Cassandra реплики периодически сравнивают Merkle-деревья по диапазонам ключей: совпадающие поддеревья пропускаются, расхождения ремонтируются. Без этого пришлось бы сравнивать все данные.

4. Резервные копии и синхронизация. Инструменты вроде rsync и restic используют хеши блоков, чтобы передавать только изменившиеся части. Проверка восстановленной копии по корневому хешу — надёжнее сравнения размеров и дат, см. резервное копирование.

5. Верифицируемые журналы. Журнал аудита можно строить как дерево: каждая партия записей добавляет новый корень. Расхождение между сохранёнными корнями показывает подмену, см. журнал действий.

Рекомендации:

1. Выбирайте размер блока под задачу. Мелкие блоки дают точную локализацию изменений, но увеличивают объём метаданных. Для файлов типично 4–64 КБ.
2. Фиксируйте алгоритм и способ конкатенации. Разные реализации по-разному обрабатывают нечётное число узлов и порядок аргументов; без явной спецификации деревья не совпадут.
3. Храните корни отдельно от данных. Корень, лежащий рядом с данными, не защищает от их одновременной подмены.
4. Разделяйте контроль целостности и конфиденцильность. Хеш-дерево показывает, что данные изменились, но не скрывает их; защита содержимого — отдельная задача, см. шифрование в покое.
5. Проверяйте при чтении, а не по расписанию. Обнаружение порчи в момент использования позволяет взять данные из другой реплики, а не спустя недели.

Практический сценарий: расхождение реплик без явных ошибок

Контекст: две реплики набора данных отдавали разные результаты по одному и тому же запросу. Ошибок в логах не было.

1. Гипотеза. Данные разошлись из-за частично потерянных записей при сбое: часть операций подтвердилась на одной реплике и не дошла до другой.
2. Проверка «в лоб». Побайтовое сравнение таблиц объёмом 400 ГБ заняло бы часы и создало бы нагрузку на продакшен.
3. Решение. Построили Merkle-дерево по диапазонам первичного ключа: листья — хеши батчей по 10 тысяч строк, далее уровни до корня. Сравнение корней показало расхождение.
4. Локализация. Спуск по расходящимся ветвям сузил область до трёх диапазонов; внутри них сравнение батчей дало 214 строк, отсутствующих на одной реплике.
5. Исправление. Недостающие строки перенесли из источника, добавили регулярную сверку корней раз в сутки и алерт на расхождение.

Вывод: хеш-дерево превращает задачу «сравнить два больших набора» из линейной в логарифмическую. Это же свойство делает возможным регулярную сверку, которая без него была бы слишком дорогой.

FAQ

Чем Merkle-дерево отличается от простого хеша всего файла? Простой хеш отвечает «данные изменились или нет», но не показывает, где именно, и требует полного перечитывания для любой проверки. Дерево даёт локализацию за log n операций и позволяет проверять отдельные блоки.

Можно ли по корневому хешу восстановить данные? Нет. Хеш-функция необратима; корень служит только для сравнения. Потеря данных при сохранённом корне означает их безвозвратную утрату.

Какой алгоритм хеширования выбрать? Для контроля целостности достаточно SHA-256. Если нужна устойчивость к преднамеренной подмене, выбирают криптографически стойкий алгоритм и хранят корни в защищённом месте.

Зачем дублировать последний узел при нечётном числе? Чтобы сохранить парность на каждом уровне и однозначность построения. Альтернатива — поднимать одиночный хеш без изменения, но тогда способ обработки должен быть явно зафиксирован в спецификации.

Источники: Git internals, Apache Cassandra docs, Wikipedia (Merkle tree) — ссылки в шапке.