Дерево Меркла: как git, биткоин и Cassandra сверяют данные одним хешем
Дерево Меркла простыми словами: как строится корень, что такое доказательство включения за O(log n), как устроены объекты git, SPV в биткоине и синхронизация реплик. Код на Python.
Коротко
| Операция | Сложность | Что нужно передать |
|---|---|---|
| Построить дерево из n блоков | хешей | — |
| Проверить, что набор данных не изменился | один корневой хеш | |
| Доказать, что блок входит в набор | хешей | |
| Найти d различающихся блоков у двух копий | сравнений хешей | хеши по пути |
- Идея: хешируем блоки данных, потом попарно хешируем хеши, и так до одного корня. Корень — отпечаток всего набора: изменился любой бит в любом блоке, изменился корень.
- Зачем не один хеш на всё: плоский хеш говорит «что-то не так», дерево — «не так вот здесь» и позволяет доказать включение блока, не пересылая остальные.
- Где встречается: объекты git, заголовки блоков в биткоине, anti-entropy repair в Cassandra и Dynamo, Certificate Transparency, BitTorrent v2, IPFS, ZFS.
- На собеседовании: в system design — синхронизация реплик и файлов; в алгоритмической секции — как вариация на тему дерева, хранящегося в массиве.
Задача, из которой всё растёт
Есть два сервера, у каждого копия одних и тех же данных — скажем, 100 ГБ, разбитых на миллион блоков. Нужно убедиться, что копии совпадают, а если нет — найти, какие блоки разошлись.
Наивные варианты:
- Переслать всё и сравнить. 100 ГБ по сети ради ответа «да, совпадают». Нет.
- Посчитать один хеш от всех данных и сравнить хеши. Передаём 32 байта — отлично, пока копии совпадают. Если не совпадают, мы знаем только, что где-то есть расхождение. Где — неизвестно, придётся опять гонять всё.
- Посчитать хеш каждого блока и сравнить списки. Найдём расхождения точно, но список из миллиона SHA-256 весит 32 МБ, и пересылать его надо при каждой сверке, даже когда всё совпадает.
Дерево Меркла объединяет плюсы второго и третьего варианта: сначала сравниваем один корень, и только если он отличается, спускаемся ниже — но лишь в те ветки, где хеши разошлись. Ральф Меркл описал эту конструкцию в 1979 году для схем цифровой подписи, а сегодня она живёт в каждой системе, где нужно дёшево проверять целостность больших данных.
Как устроено дерево
Берём блоки данных :
- Листья — хеши блоков: .
- Внутренний узел — хеш конкатенации детей: .
- Повторяем, пока не останется один узел — корень Меркла (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): по ней практически невозможно подобрать другой вход с тем же выходом. Отсюда главное свойство: если корень совпал, то с подавляющей вероятностью совпали все листья, а значит, и все данные. Изменение одного байта в меняет , затем , затем корень — по цепочке длиной .
Реализация на 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
Чтобы доказать , нужны и : . Порядок склейки важен, поэтому для каждого соседа запоминаем, слева он или справа.
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 байт. Растёт как , а не как .
Важно понимать, что именно доказывает 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, и внутри строятся именно деревья Меркла.
Схема такая:
- Пространство ключей делим на фиксированное число бакетов по хешу ключа — это будут листья.
- Лист — хеш от отсортированного содержимого бакета.
- Реплики строят деревья одинаковой формы и обмениваются хешами сверху вниз: корень совпал — расходимся, не совпал — сравниваем детей, и так до листьев.
- Синхронизируем только бакеты, чьи листья различаются.
Дерево удобно хранить в массиве, как двоичную кучу или дерево отрезков: корень в 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, сравнений будет порядка , а не . Когда реплики совпадают (а это обычный случай), хватает одного сравнения корня.
Компромиссы, которые стоит проговорить
- Глубина дерева. Больше листьев — точнее локализуем расхождение, но больше памяти и сетевых раундов. Мало листьев — каждый бакет крупный, и из-за одного изменённого ключа пересылаем много лишнего. Cassandra ограничивает глубину дерева (исторически 2^15 листьев на диапазон), поэтому на больших диапазонах бакеты получаются крупными и repair бывает тяжёлым.
- Пересчёт при записи. Изменение ключа меняет лист и весь путь до корня — хешей. Можно поддерживать дерево инкрементально, а можно строить заново перед сверкой. Cassandra строит дерево при repair, читая данные с диска, — это дорогая операция, поэтому repair гоняют по расписанию, а не непрерывно.
- Одинаковая форма. Сравнивать деревья по узлам можно, только если обе реплики разбивают ключи на бакеты одинаково. Поэтому разбиение идёт по хешу ключа и фиксированным диапазонам, а не по порядку вставки. Как ключи распределяются по узлам, разобрано в статье про консистентное хеширование.
Ещё несколько мест, где живёт дерево Меркла
- Certificate Transparency. Все выпущенные TLS-сертификаты записываются в публичные журналы, устроенные как дерево Меркла только на добавление (RFC 6962). Браузер может проверить, что сертификат действительно залогирован, а аудитор — что журнал не переписывали задним числом (consistency proof: старый корень — префикс нового дерева).
- BitTorrent v2. Каждый файл в торренте разбит на куски по 16 КБ, хеши собраны в дерево Меркла на SHA-256. Кусок можно проверить сразу после скачивания, не дожидаясь соседних.
- IPFS. Контент-адресация: файл режется на блоки, блоки связываются в Merkle DAG, адрес файла — хеш корня. Одинаковые блоки у разных файлов хранятся один раз — как в git.
- ZFS и Btrfs. Контрольная сумма блока хранится не рядом с блоком, а в указателе на него у родителя. Получается дерево Меркла на всю файловую систему: тихую порчу данных на диске можно обнаружить, а при наличии зеркала — исправить.
Сложность
Пусть n блоков, хеш вычисляется за на блок фиксированного размера.
| Что | Время | Память / трафик |
|---|---|---|
| Построение | хешей в памяти | |
| Обновление одного блока | — | |
| Proof включения | хешей | |
| Проверка proof | — | |
| Сверка двух деревьев, d различий | хешей |
Число узлов в двоичном дереве из n листьев — , так что память на хеши примерно вдвое больше, чем на один список хешей листьев. Обычно это незаметно на фоне самих данных.
Типичные ошибки
- Один и тот же хеш для листьев и узлов. Открывает атаку второго прообраза. Добавляйте префикс типа узла.
- Дублирование последнего узла. Списки разной длины дают одинаковый корень — тот самый CVE-2012-2459. Поднимайте непарный узел наверх или храните количество листьев рядом с корнем.
- Перепутанный порядок в proof. . Если не хранить, с какой стороны сосед, проверка будет ломаться на половине индексов — или, что хуже, кто-то додумается сортировать пару перед хешированием и откроет возможность для подделок.
- Доверие к корню, пришедшему вместе с данными. Proof доказывает включение в набор с данным корнем, но не то, что корень правильный. Корень должен быть подписан, зафиксирован в блокчейне или получен из независимого источника.
- Разная форма деревьев у реплик. Если реплики разбивают ключи на бакеты по-разному, сравнение узлов бессмысленно — любое расхождение раздуется до всего дерева.
- Некриптографический хеш. CRC32 или
hash()из Python годятся для хеш-таблицы, но не для проверки целостности против злоумышленника: коллизию к ним подобрать легко. Для сверки реплик внутри доверенного кластера быстрый некриптографический хеш допустим, но это сознательный компромисс, а не умолчание.
Как это спрашивают на собеседованиях
System design. Дерево Меркла почти никогда не вопрос само по себе, но это сильный ход в нескольких типовых задачах:
- распределённое key-value хранилище — как реплики находят расхождения после сбоя (anti-entropy, read repair, hinted handoff — и где тут дерево Меркла);
- синхронизация файлов в духе Dropbox — как понять, какие куски файла изменились, и не гонять файл целиком;
- репликация в целом и проверка консистентности копий.
Хороший ответ звучит примерно так: «Для фоновой сверки реплик построим дерево Меркла по диапазонам ключей. Если корни совпали — реплики консистентны, стоило 32 байта трафика. Если нет — спускаемся по разошедшимся веткам и синхронизируем только изменённые диапазоны». Дальше интервьюер может спросить про глубину дерева и стоимость пересчёта — компромиссы выше.
Алгоритмическая секция. Встречаются задачи, где нужно быстро сравнивать поддеревья: например, найти одинаковые поддеревья в двоичном дереве (LeetCode 652. Find Duplicate Subtrees) или проверить, является ли одно дерево поддеревом другого (LeetCode 572. Subtree of Another Tree). Приём тот же: каждому поддереву сопоставляем хеш от значения узла и хешей детей, а дальше сравниваем хеши вместо обхода. Это та же идея, что и в полиномиальном хешировании строк: заменить сравнение больших объектов сравнением коротких отпечатков.
Вопросы на понимание, которые стоит уметь ответить за минуту:
- Сколько хешей в доказательстве включения для n блоков? — .
- Почему нельзя просто взять хеш от конкатенации всех блоков? — Не локализует расхождения и не даёт короткого доказательства включения.
- Чем дерево Меркла отличается от фильтра Блума? — Фильтр Блума отвечает «возможно, есть / точно нет» и не защищён от злоумышленника; дерево Меркла даёт криптографическое доказательство включения, но требует знать корень и получить путь.
- Почему изменение старого коммита в git меняет хеши всех последующих? — Хеш коммита включает хеш родителя, это цепочка Меркла.