Дерево Меркла: как git, биткоин и Cassandra сверяют данные одним хешем

Дерево Меркла простыми словами: как строится корень, что такое доказательство включения за O(log n), как устроены объекты git, SPV в биткоине и синхронизация реплик. Код на Python.

14 мин чтенияструктуры данных · хеширование · системный дизайн · python

Коротко

ОперацияСложностьЧто нужно передать
Построить дерево из n блоковO(n)O(n) хешей—
Проверить, что набор данных не изменилсяO(1)O(1)один корневой хеш
Доказать, что блок входит в наборO(log⁡n)O(\log n)⌈log⁡2n⌉\lceil \log_2 n \rceil хешей
Найти d различающихся блоков у двух копийO(dlog⁡n)O(d \log n) сравнений хешейхеши по пути
  • Идея: хешируем блоки данных, потом попарно хешируем хеши, и так до одного корня. Корень — отпечаток всего набора: изменился любой бит в любом блоке, изменился корень.
  • Зачем не один хеш на всё: плоский хеш говорит «что-то не так», дерево — «не так вот здесь» и позволяет доказать включение блока, не пересылая остальные.
  • Где встречается: объекты git, заголовки блоков в биткоине, anti-entropy repair в Cassandra и Dynamo, Certificate Transparency, BitTorrent v2, IPFS, ZFS.
  • На собеседовании: в system design — синхронизация реплик и файлов; в алгоритмической секции — как вариация на тему дерева, хранящегося в массиве.

Задача, из которой всё растёт

Есть два сервера, у каждого копия одних и тех же данных — скажем, 100 ГБ, разбитых на миллион блоков. Нужно убедиться, что копии совпадают, а если нет — найти, какие блоки разошлись.

Наивные варианты:

  1. Переслать всё и сравнить. 100 ГБ по сети ради ответа «да, совпадают». Нет.
  2. Посчитать один хеш от всех данных и сравнить хеши. Передаём 32 байта — отлично, пока копии совпадают. Если не совпадают, мы знаем только, что где-то есть расхождение. Где — неизвестно, придётся опять гонять всё.
  3. Посчитать хеш каждого блока и сравнить списки. Найдём расхождения точно, но список из миллиона SHA-256 весит 32 МБ, и пересылать его надо при каждой сверке, даже когда всё совпадает.

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

Как устроено дерево

Берём блоки данных D0,D1,…,Dn−1D_0, D_1, \dots, D_{n-1}:

  1. Листья — хеши блоков: Li=H(Di)L_i = H(D_i).
  2. Внутренний узел — хеш конкатенации детей: N=H(left ∥ right)N = H(\text{left} \,\|\, \text{right}).
  3. Повторяем, пока не останется один узел — корень Меркла (Merkle root).
                 root = H(H01 || H23)
                /                    \
       H01 = H(L0 || L1)      H23 = H(L2 || L3)
        /          \            /          \
   L0 = H(D0)  L1 = H(D1)  L2 = H(D2)  L3 = H(D3)

Хеш-функция криптографическая (SHA-256, SHA-1, Keccak): по ней практически невозможно подобрать другой вход с тем же выходом. Отсюда главное свойство: если корень совпал, то с подавляющей вероятностью совпали все листья, а значит, и все данные. Изменение одного байта в D2D_2 меняет L2L_2, затем H23H_{23}, затем корень — по цепочке длиной log⁡2n\log_2 n.

Реализация на Python

import hashlib def h(data: bytes) -> bytes: return hashlib.sha256(data).digest() def leaf_hash(data: bytes) -> bytes: return h(b'\x00' + data) def node_hash(left: bytes, right: bytes) -> bytes: return h(b'\x01' + left + right) def build_levels(blocks: list[bytes]) -> list[list[bytes]]: """Возвращает все уровни дерева: levels[0] — листья, levels[-1] — [корень].""" level = [leaf_hash(b) for b in blocks] levels = [level] while len(level) > 1: nxt = [] for i in range(0, len(level), 2): if i + 1 < len(level): nxt.append(node_hash(level[i], level[i + 1])) else: nxt.append(level[i]) # непарный узел поднимаем без изменений level = nxt levels.append(level) return levels def merkle_root(blocks: list[bytes]) -> bytes: return build_levels(blocks)[-1][0] blocks = [b'tx-a', b'tx-b', b'tx-c', b'tx-d', b'tx-e'] print(merkle_root(blocks).hex()[:16]) # 80c0d4e7c8991cc7 blocks[2] = b'tx-C' print(merkle_root(blocks).hex()[:16]) # fce121a58ded430e

Поменяли одну букву в одном блоке — корень стал совершенно другим.

Две детали, которые легко упустить.

Префиксы 0x00 и 0x01. Лист и внутренний узел хешируются с разными префиксами. Без этого возможна атака второго прообраза: злоумышленник берёт внутренний узел — это просто 64 байта left || right — и выдаёт его за лист с такими «данными». Корень сойдётся, хотя такого блока в наборе не было. Префиксы разводят два пространства хешей, и подделка перестаёт работать. Так сделано в Certificate Transparency (RFC 6962).

Нечётное число узлов. Если на уровне нечётное количество узлов, последнему не хватает пары. Вариантов два:

  • поднять его на уровень выше без изменений, как в коде выше. Такая схема даёт ровно тот же корень, что и RFC 6962, где дерево делится на левую часть размером в наибольшую степень двойки и остаток — мы проверили это на всех n до 300;
  • продублировать последний узел и захешировать его с самим собой. Так делает биткоин, и у этого есть цена: списки [a, b, c] и [a, b, c, c] дают один и тот же корень. В 2012 году это стало уязвимостью CVE-2012-2459 — блок с продублированной транзакцией имел тот же корень, что и корректный, и узлы можно было запутать. Исправили на уровне проверки блоков, а не формата дерева.

Мораль: если проектируете своё дерево, не дублируйте узлы и включайте в хеш тип узла.

Доказательство включения (Merkle proof)

Самая полезная возможность дерева. Допустим, у клиента есть только корень (32 байта), полученный из надёжного источника. Сервер утверждает: «блок tx-777 входит в набор». Как проверить, не скачивая весь набор?

Сервер присылает путь аутентификации — хеши соседей на каждом уровне от листа до корня. Клиент сам хеширует блок, по очереди склеивает с соседями и сравнивает результат с корнем.

                 root
                /    \
            H01        [H23]  ← сосед на уровне 1
           /   \
        [L0]    L1           ← сосед на уровне 0
                ↑
         проверяем D1

Чтобы доказать D1D_1, нужны L0L_0 и H23H_{23}: H(H(L0∥H(D1))∥H23)=?rootH(H(L_0 \| H(D_1)) \| H_{23}) \stackrel{?}{=} \text{root}. Порядок склейки важен, поэтому для каждого соседа запоминаем, слева он или справа.

def make_proof(levels: list[list[bytes]], index: int) -> list[tuple[bytes, bool]]: """Список (хеш соседа, сосед_справа) от листа к корню.""" proof = [] for level in levels[:-1]: sibling = index ^ 1 if sibling < len(level): proof.append((level[sibling], sibling > index)) index //= 2 return proof def verify(block: bytes, proof: list[tuple[bytes, bool]], root: bytes) -> bool: acc = leaf_hash(block) for sibling, is_right in proof: acc = node_hash(acc, sibling) if is_right else node_hash(sibling, acc) return acc == root blocks = [f'tx-{i}'.encode() for i in range(1000)] levels = build_levels(blocks) root = levels[-1][0] proof = make_proof(levels, 777) print(len(proof)) # 10 print(verify(b'tx-777', proof, root)) # True print(verify(b'tx-778', proof, root)) # False

index ^ 1 — индекс соседа: у чётного сосед справа, у нечётного слева. index //= 2 — переход к родителю. Если соседа нет (непарный узел, который мы подняли), уровень пропускается: узел перешёл наверх без изменений, хешировать нечего.

Для тысячи блоков доказательство — 10 хешей, 320 байт. Для миллиона — 20 хешей, 640 байт. Растёт как log⁡2n\log_2 n, а не как nn.

Важно понимать, что именно доказывает proof: «этот блок входит в набор с таким корнем». Доверие к самому корню должно прийти откуда-то ещё — из подписи, из цепочки блоков, из публичного журнала. Если злоумышленник подменил и данные, и корень, дерево не поможет.

Git: дерево Меркла, которым вы пользуетесь каждый день

Каждый объект в git адресуется хешем своего содержимого. По умолчанию это SHA-1; поддержка SHA-256 появилась в Git 2.29 как опция --object-format=sha256, и сообщество постепенно готовит переход на неё.

Хеш файла (объекта blob) — SHA-1 от заголовка blob <размер>\0 и содержимого:

import hashlib def git_blob_hash(content: bytes) -> str: header = f'blob {len(content)}\0'.encode() return hashlib.sha1(header + content).hexdigest() print(git_blob_hash(b'hello\n')) # ce013625030ba8dba906f756967f9e9ca394464a

Результат совпадает с printf 'hello\n' | git hash-object --stdin — можно проверить у себя в терминале.

Директория — объект tree: список записей «режим, имя, хеш дочернего объекта», и хеш дерева считается уже от этого списка:

def git_tree_hash(entries: list[tuple[str, str, str]]) -> str: """entries: (mode, имя, sha1-hex) — как в `git ls-tree`.""" body = b'' for mode, name, sha in sorted(entries, key=lambda e: e[1]): body += f'{mode} {name}\0'.encode() + bytes.fromhex(sha) header = f'tree {len(body)}\0'.encode() return hashlib.sha1(header + body).hexdigest() print(git_tree_hash([('100644', 'hello.txt', 'ce013625030ba8dba906f756967f9e9ca394464a')])) # aaa96ced2d9a1c8e72c56b253a0e2fe78393feb7 — то же, что выдаёт `git write-tree`

(Упрощение: настоящий git при сортировке считает, что имя директории оканчивается на /. Для файлов без поддиректорий это неважно.)

Получается ровно дерево Меркла, только не двоичное: у узла столько детей, сколько записей в директории. Коммит хранит хеш корневого tree и хеши родительских коммитов, поэтому вся история — это Merkle DAG (ориентированный ациклический граф). Что это даёт на практике:

  • Хеш коммита фиксирует всё состояние проекта и всю историю до него. Поменять старый коммит незаметно нельзя: поменяются хеши всех потомков. Именно поэтому rebase создаёт новые коммиты, а не правит старые.
  • git status и git diff между коммитами работают быстро. Если хеши двух tree совпадают, git не заходит внутрь — поддиректория идентична целиком. Сравнение двух снимков огромного репозитория сводится к обходу только изменённых веток.
  • Дедупликация бесплатно. Один и тот же файл в ста коммитах хранится один раз: одинаковое содержимое — одинаковый хеш — один объект.
  • git fetch передаёт только недостающее. Клиент и сервер обмениваются хешами коммитов, сервер находит общую историю и отправляет только объекты, которых у клиента нет.

Подробнее о повседневной работе с git — в статье про команды git.

Биткоин: SPV и корень в заголовке блока

Каждый блок биткоина содержит заголовок размером 80 байт, и в нём — корень Меркла всех транзакций блока (хеш — двойной SHA-256). Сам блок может весить мегабайты, а цепочка заголовков за всю историю сети занимает меньше сотни мегабайт.

На этом построен лёгкий клиент (SPV, Simplified Payment Verification, описан ещё в оригинальной статье Сатоши Накамото). Кошелёк на телефоне не хранит блокчейн целиком, только заголовки. Чтобы убедиться, что его транзакция попала в блок, он просит у полного узла Merkle proof: в блоке на 4000 транзакций это 12 хешей, меньше 400 байт. Кошелёк сверяет путь с корнем из заголовка, а заголовок защищён proof-of-work всей цепочки.

Ethereum пошёл дальше и использует Merkle Patricia Trie — гибрид дерева Меркла и префиксного дерева. В нём хранится не только список транзакций, но и состояние всех аккаунтов, и можно доказать, например, баланс конкретного адреса.

Синхронизация реплик: anti-entropy в Cassandra и Dynamo

Вернёмся к исходной задаче про две копии данных. В распределённых хранилищах типа Amazon Dynamo (статья 2007 года), Cassandra и Riak реплики одного диапазона ключей со временем расходятся: запись не дошла до узла из-за сетевого сбоя, узел перезапускался, hinted handoff не сработал. Фоновый процесс anti-entropy находит и чинит расхождения. В Cassandra он запускается командой nodetool repair, и внутри строятся именно деревья Меркла.

Схема такая:

  1. Пространство ключей делим на фиксированное число бакетов по хешу ключа — это будут листья.
  2. Лист — хеш от отсортированного содержимого бакета.
  3. Реплики строят деревья одинаковой формы и обмениваются хешами сверху вниз: корень совпал — расходимся, не совпал — сравниваем детей, и так до листьев.
  4. Синхронизируем только бакеты, чьи листья различаются.

Дерево удобно хранить в массиве, как двоичную кучу или дерево отрезков: корень в tree[1], дети узла v — в 2v и 2v + 1, листья в правой половине массива.

import hashlib BUCKETS = 16 # число листьев, степень двойки def h(data: bytes) -> bytes: return hashlib.sha256(data).digest() def bucket_of(key: str) -> int: return int.from_bytes(h(key.encode())[:4], 'big') % BUCKETS def build_tree(store: dict[str, str]) -> list[bytes]: """Дерево в массиве, как куча: tree[1] — корень, листья в tree[BUCKETS:].""" buckets = [[] for _ in range(BUCKETS)] for key, value in store.items(): buckets[bucket_of(key)].append(f'{key}={value}') tree = [b''] * (2 * BUCKETS) for i, items in enumerate(buckets): tree[BUCKETS + i] = h('\n'.join(sorted(items)).encode()) for v in range(BUCKETS - 1, 0, -1): tree[v] = h(tree[2 * v] + tree[2 * v + 1]) return tree def diff_buckets(a: list[bytes], b: list[bytes]) -> tuple[list[int], int]: """Номера различающихся бакетов и сколько хешей пришлось сравнить.""" result, compared = [], 0 stack = [1] while stack: v = stack.pop() compared += 1 if a[v] == b[v]: continue # поддерево совпало — пропускаем целиком if v >= BUCKETS: result.append(v - BUCKETS) else: stack += [2 * v + 1, 2 * v] return sorted(result), compared replica1 = {f'user:{i}': f'v{i}' for i in range(10_000)} replica2 = dict(replica1) replica2['user:42'] = 'v42-new' del replica2['user:7'] t1, t2 = build_tree(replica1), build_tree(replica2) buckets, compared = diff_buckets(t1, t2) print(buckets, compared) # [11, 14] 13 stale = [k for k in replica1.keys() | replica2.keys() if bucket_of(k) in buckets and replica1.get(k) != replica2.get(k)] print(sorted(stale)) # ['user:42', 'user:7']

Из 31 узла дерева пришлось сравнить 13, а из 16 бакетов пересылать нужно только 2. На реальных объёмах выигрыш намного больше: если различаются d бакетов из n, сравнений будет порядка dlog⁡nd \log n, а не nn. Когда реплики совпадают (а это обычный случай), хватает одного сравнения корня.

Компромиссы, которые стоит проговорить

  • Глубина дерева. Больше листьев — точнее локализуем расхождение, но больше памяти и сетевых раундов. Мало листьев — каждый бакет крупный, и из-за одного изменённого ключа пересылаем много лишнего. Cassandra ограничивает глубину дерева (исторически 2^15 листьев на диапазон), поэтому на больших диапазонах бакеты получаются крупными и repair бывает тяжёлым.
  • Пересчёт при записи. Изменение ключа меняет лист и весь путь до корня — O(log⁡n)O(\log n) хешей. Можно поддерживать дерево инкрементально, а можно строить заново перед сверкой. Cassandra строит дерево при repair, читая данные с диска, — это дорогая операция, поэтому repair гоняют по расписанию, а не непрерывно.
  • Одинаковая форма. Сравнивать деревья по узлам можно, только если обе реплики разбивают ключи на бакеты одинаково. Поэтому разбиение идёт по хешу ключа и фиксированным диапазонам, а не по порядку вставки. Как ключи распределяются по узлам, разобрано в статье про консистентное хеширование.

Ещё несколько мест, где живёт дерево Меркла

  • Certificate Transparency. Все выпущенные TLS-сертификаты записываются в публичные журналы, устроенные как дерево Меркла только на добавление (RFC 6962). Браузер может проверить, что сертификат действительно залогирован, а аудитор — что журнал не переписывали задним числом (consistency proof: старый корень — префикс нового дерева).
  • BitTorrent v2. Каждый файл в торренте разбит на куски по 16 КБ, хеши собраны в дерево Меркла на SHA-256. Кусок можно проверить сразу после скачивания, не дожидаясь соседних.
  • IPFS. Контент-адресация: файл режется на блоки, блоки связываются в Merkle DAG, адрес файла — хеш корня. Одинаковые блоки у разных файлов хранятся один раз — как в git.
  • ZFS и Btrfs. Контрольная сумма блока хранится не рядом с блоком, а в указателе на него у родителя. Получается дерево Меркла на всю файловую систему: тихую порчу данных на диске можно обнаружить, а при наличии зеркала — исправить.

Сложность

Пусть n блоков, хеш вычисляется за O(1)O(1) на блок фиксированного размера.

ЧтоВремяПамять / трафик
ПостроениеO(n)O(n)O(n)O(n) хешей в памяти
Обновление одного блокаO(log⁡n)O(\log n)—
Proof включенияO(log⁡n)O(\log n)O(log⁡n)O(\log n) хешей
Проверка proofO(log⁡n)O(\log n)—
Сверка двух деревьев, d различийO(dlog⁡n)O(d \log n)O(dlog⁡n)O(d \log n) хешей

Число узлов в двоичном дереве из n листьев — 2n−12n - 1, так что память на хеши примерно вдвое больше, чем на один список хешей листьев. Обычно это незаметно на фоне самих данных.

Типичные ошибки

  1. Один и тот же хеш для листьев и узлов. Открывает атаку второго прообраза. Добавляйте префикс типа узла.
  2. Дублирование последнего узла. Списки разной длины дают одинаковый корень — тот самый CVE-2012-2459. Поднимайте непарный узел наверх или храните количество листьев рядом с корнем.
  3. Перепутанный порядок в proof. H(a∥b)≠H(b∥a)H(a \| b) \ne H(b \| a). Если не хранить, с какой стороны сосед, проверка будет ломаться на половине индексов — или, что хуже, кто-то додумается сортировать пару перед хешированием и откроет возможность для подделок.
  4. Доверие к корню, пришедшему вместе с данными. Proof доказывает включение в набор с данным корнем, но не то, что корень правильный. Корень должен быть подписан, зафиксирован в блокчейне или получен из независимого источника.
  5. Разная форма деревьев у реплик. Если реплики разбивают ключи на бакеты по-разному, сравнение узлов бессмысленно — любое расхождение раздуется до всего дерева.
  6. Некриптографический хеш. CRC32 или hash() из Python годятся для хеш-таблицы, но не для проверки целостности против злоумышленника: коллизию к ним подобрать легко. Для сверки реплик внутри доверенного кластера быстрый некриптографический хеш допустим, но это сознательный компромисс, а не умолчание.

Как это спрашивают на собеседованиях

System design. Дерево Меркла почти никогда не вопрос само по себе, но это сильный ход в нескольких типовых задачах:

Хороший ответ звучит примерно так: «Для фоновой сверки реплик построим дерево Меркла по диапазонам ключей. Если корни совпали — реплики консистентны, стоило 32 байта трафика. Если нет — спускаемся по разошедшимся веткам и синхронизируем только изменённые диапазоны». Дальше интервьюер может спросить про глубину дерева и стоимость пересчёта — компромиссы выше.

Алгоритмическая секция. Встречаются задачи, где нужно быстро сравнивать поддеревья: например, найти одинаковые поддеревья в двоичном дереве (LeetCode 652. Find Duplicate Subtrees) или проверить, является ли одно дерево поддеревом другого (LeetCode 572. Subtree of Another Tree). Приём тот же: каждому поддереву сопоставляем хеш от значения узла и хешей детей, а дальше сравниваем хеши вместо обхода. Это та же идея, что и в полиномиальном хешировании строк: заменить сравнение больших объектов сравнением коротких отпечатков.

Вопросы на понимание, которые стоит уметь ответить за минуту:

  • Сколько хешей в доказательстве включения для n блоков? — ⌈log⁡2n⌉\lceil \log_2 n \rceil.
  • Почему нельзя просто взять хеш от конкатенации всех блоков? — Не локализует расхождения и не даёт короткого доказательства включения.
  • Чем дерево Меркла отличается от фильтра Блума? — Фильтр Блума отвечает «возможно, есть / точно нет» и не защищён от злоумышленника; дерево Меркла даёт криптографическое доказательство включения, но требует знать корень и получить путь.
  • Почему изменение старого коммита в git меняет хеши всех последующих? — Хеш коммита включает хеш родителя, это цепочка Меркла.

Потренироваться в спокойной обстановке

Все задачи