Деревья Меркла

Зачем это нужно в блокчейне

Каждый заголовок блока Bitcoin содержит Merkle Root — единственный 32-байтный хеш, фиксирующий ВСЕ транзакции блока. Как 2000 транзакций превратить в один хеш? Дерево Меркла.

Этот хеш подобен печати нотариуса: если кто-то попытается изменить хотя бы одну транзакцию, Merkle Root изменится и подделка будет обнаружена. При этом проверка отдельной транзакции требует всего ~11 хешей вместо полной загрузки блока.

Интуитивное объяснение

Представьте, что вам нужно подписать 1000 документов одной подписью. Можно подписать каждый отдельно, но это долго. Вместо этого:

1. Берем хеш каждого документа (вспомните SHA-256 из урока 4)
2. Объединяем попарно и хешируем пары
3. Повторяем, пока не останется один хеш

Это и есть дерево Меркла (Merkle tree) — двоичное дерево хешей, где:

• Листья = хеши данных (транзакций)
• Внутренние узлы = хеш конкатенации двух дочерних узлов
• Корень (Root) = единственный хеш, фиксирующий все данные

Построение дерева: пошаговая анимация

Нажимайте “Далее”, чтобы увидеть, как строится дерево Меркла снизу вверх:

Алгоритм построения

1. Хешируем каждую транзакцию -> получаем листья
2. Если нечетное количество листьев -> дублируем последний
3. Попарно конкатенируем и хешируем -> получаем следующий уровень
4. Повторяем шаг 2-3 пока не останется один узел -> Merkle Root

Структура дерева

Обратите внимание на цветовую кодировку:

• Зеленые — листья (хеши исходных данных)
• Синие — внутренние узлы (хеши пар)
• Фиолетовый — корень (Merkle Root)

Свойство обязательства (Commitment)

Merkle Root — это обязательство (commitment) по отношению ко всем данным в дереве. Изменение любого листа неизбежно меняет корень:

Это свойство делает Merkle Root идеальным для заголовка блока: невозможно подменить транзакцию, не изменив корень, а значит, и заголовок блока, и всю цепочку.

Алгоритмический уровень

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

Вспомните SHA-256 из урока 4 — деревья Меркла строятся на основе хеш-функций.

import hashlib

def sha256(data: bytes) -> bytes:
    """SHA-256 хеш для дерева Меркла."""
    return hashlib.sha256(data).digest()

def build_merkle_tree(leaves: list[bytes]) -> list[list[bytes]]:
    """Строит дерево Меркла, возвращает все уровни.

    Args:
        leaves: Список хешей листьев (байты).

    Returns:
        Список уровней от листьев (индекс 0) до корня (последний).
    """
    if not leaves:
        return []

    tree = [leaves[:]]  # Копия листьев
    level = leaves[:]

    while len(level) > 1:
        # Дублируем последний при нечетном количестве (конвенция Bitcoin)
        if len(level) % 2 == 1:
            level.append(level[-1])

        next_level = []
        for i in range(0, len(level), 2):
            parent = sha256(level[i] + level[i + 1])
            next_level.append(parent)

        tree.append(next_level)
        level = next_level

    return tree

# Пример: 4 транзакции
txs = [b"Alice->Bob: 1 BTC", b"Bob->Carol: 0.5 BTC",
       b"Dave->Eve: 2 BTC", b"Eve->Alice: 0.1 BTC"]

leaves = [sha256(tx) for tx in txs]
tree = build_merkle_tree(leaves)

print(f"Листьев: {len(tree[0])}")
print(f"Уровней: {len(tree)}")
print(f"Merkle Root: {tree[-1][0].hex()[:16]}...")

Обработка нечетного числа листьев

В Bitcoin, если на каком-то уровне нечетное количество узлов, последний узел дублируется. Это стандартная конвенция:

# Если 5 транзакций:
# [tx1, tx2, tx3, tx4, tx5]
# -> [tx1, tx2, tx3, tx4, tx5, tx5]  # tx5 дублируется
# -> Далее попарное хеширование

Математический уровень

Для дерева с n листьями:

Для Bitcoin блока с 2000 транзакциями:

• Высота = ceil(log2(2000)) = 11
• Всего узлов = ~4000
• Merkle Root = всегда 32 байта

Где используются деревья Меркла

Практика

Закрепите знания в Jupyter notebook: 09-merkle-trees.ipynb

В нем вы:

• Реализуете build_merkle_tree с нуля
• Построите дерево из 8 транзакций
• Увидите, как изменение одного листа меняет корень
• Симулируете Merkle Root для блока Bitcoin

Итоги

• Дерево Меркла — двоичное дерево хешей с корнем, фиксирующим все данные
• Построение идет снизу вверх: листья -> попарное хеширование -> корень
• Высота = ceil(log2(n)), что обеспечивает эффективные доказательства (следующий урок)
• Merkle Root — обязательство: изменение любого листа меняет корень
• Bitcoin использует Merkle Root в каждом заголовке блока