Дерево Меркла: проверка целостности данных

Зачем нужно дерево Меркла?

Представьте, вы скачиваете 50-гигабайтный торрент от сотен незнакомцев. Как убедиться, что никто не подменил данные? Ожидать полной загрузки — рискованно. Дерево Меркла — криптографическая структура, которая проверяет целостность данных по частям, не дожидаясь конца загрузки.

Что такое дерево Меркла?

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

Как построить дерево Меркла на Python

Разберём пошагово с кодом. Для хеширования используем SHA-256.

import hashlib

# Шаг 1: разбиваем файл на блоки (здесь — строки)
chunks = [b"block1", b"block2", b"block3", b"block4"]

# Шаг 2: хешируем каждый блок
hashes = [hashlib.sha256(chunk).hexdigest() for chunk in chunks]
print("Хеши блоков:", hashes)

# Шаг 3-4: попарно хешируем, пока не останется один корень
def build_merkle_tree(hashes):
    if len(hashes) == 1:
        return hashes[0]
    new_hashes = []
    for i in range(0, len(hashes), 2):
        left = hashes[i]
        right = hashes[i+1] if i+1 < len(hashes) else left  # если нечётное — дублируем
        combined = left + right
        new_hash = hashlib.sha256(combined.encode()).hexdigest()
        new_hashes.append(new_hash)
    return build_merkle_tree(new_hashes)

root = build_merkle_tree(hashes)
print("Корневой хеш:", root)

Что если блок повреждён?

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

Почему не хешировать весь файл сразу?

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

Где ещё применяется?

• Git — для отслеживания версий файлов.
• Блокчейн — для проверки транзакций без загрузки всей цепочки.
• Распределённые системы — для синхронизации данных.

Важно

Дерево Меркла не шифрует данные, а только проверяет их целостность. Хеши — односторонние функции, но содержимое файла остаётся открытым.

Практический вывод

Попробуйте реализовать дерево Меркла для проверки целостности любого файла на диске. Разбейте его на блоки по 1 КБ, постройте дерево и сохраните корневой хеш. При следующем запуске сравните — это даст вам понимание, как работают торренты и блокчейн.