Деревья Меркла и доказательства: как проверять миллионы данных одним хешем

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

Как строится дерево

Возьмём четыре элемента: A, B, C, D.

1. Посчитаем хеш каждого: H(A), H(B), H(C), H(D). Это листья.
2. Соединим соседей парами и хешируем: H(AB) = H(H(A) ‖ H(B)), H(CD) = H(H(C) ‖ H(D)).
3. Повторим для пар: Root = H(H(AB) ‖ H(CD)).

            Root
          /      \
      H(AB)      H(CD)
      /   \      /   \
   H(A)  H(B)  H(C)  H(D)

Корень (root) - один хеш на весь набор. Изменение любого элемента меняет цепочку хешей вплоть до корня. Если число листьев нечётное, последний элемент дублируют или переносят наверх (способ зависит от реализации).

Доказательство вхождения

Допустим, нужно доказать, что C входит в набор с известным корнем. Не нужно показывать все элементы. Достаточно ветки:

• H(D) (сосед листа C);
• H(AB) (сосед на следующем уровне).

Проверяющий:

1. считает H(C);
2. объединяет с H(D) → H(CD);
3. объединяет H(AB) с H(CD) → получает корень;
4. сравнивает с известным корнем.

Совпало - значит, C действительно входит в набор. Размер доказательства растёт как логарифм числа листьев: для миллиона элементов нужно всего 20 хешей (около 640 байт), а не миллион.

Проверка в Solidity

Контракту достаточно хранить только корень (32 байта). Проверку делает библиотека:

bytes32 public merkleRoot;

function claim(uint256 amount, bytes32[] calldata proof) external {
    bytes32 leaf = keccak256(bytes.concat(keccak256(abi.encode(msg.sender, amount))));
    require(MerkleProof.verify(proof, merkleRoot, leaf), "not in list");
    require(!claimed[msg.sender], "already claimed");
    claimed[msg.sender] = true;
    // ... выплата
}

Список из миллиона адресов обходится в хранении одним слотом (хранилище). Пользователь предъявляет доказательство, а сайт вычисляет его заранее и отдаёт кошельку.

Где применяется

• Airdrop и белые списки. Проект раздаёт токены тысячам адресов, не записывая каждый в блокчейн.
• Блоки Bitcoin и Ethereum. В заголовке блока лежит корень Меркла транзакций. Лёгкий клиент проверяет вхождение транзакции по короткому доказательству, не скачивая блок целиком.
• Состояние Ethereum. «Мировое состояние» хранится в дереве Меркла-Патриции, а его корень входит в каждый блок (аккаунты и состояние).
• Роллапы и мосты. Данные переносят с одной сети на другую, доказывая их вхождение в зафиксированный корень (роллапы изнутри, мосты).
• Целостность данных. Раздача больших файлов, хранилища, системы контроля версий.

Деревья Меркла и условия сделок

В нашем сервисе условия сделки закрепляются хешем (хеш условий). Если бы условий было много (например, договор из сотен пунктов), можно было бы закрепить корень Меркла и отдельно доказывать каждый пункт. Для обычной сделки достаточно одного хеша.

Атаки и подводные камни

Подмена узла и листа. Нужно отличать лист от промежуточного узла. Иначе злоумышленник может выдать конкатенацию двух хешей за «лист» и подобрать доказательство для не существующего элемента. Защита - двойное хеширование листьев (как в примере выше) или добавление префиксов.

Порядок пар. Библиотеки часто сортируют пару хешей перед объединением, чтобы доказательству не нужно было нести «направление». Тогда порядок не имеет значения для проверки.

Повторное использование. Доказательство подтверждает только вхождение. Чтобы нельзя было получить награду дважды, контракт ведёт отметку claimed (каталог уязвимостей).

Утечка списка. Корень скрывает набор, но не защищает от того, что тот, кто составил дерево, знает все элементы.

Мини-пример

Список «получателей награды»: Анна - 100, Борис - 250, Вера - 40, Глеб - 75.

1. Организатор считает листья H(Анна, 100) и т. д.
2. Строит дерево и публикует корень в контракте.
3. Борис заходит на сайт: тот выдаёт ему доказательство из двух хешей.
4. Борис вызывает claim(250, proof). Контракт восстанавливает корень и сверяет с сохранённым - успех.
5. Глеб пытается заявить 7500 вместо 75: корень не совпадает - отказ.

Что почитать дальше

Узнайте, как контракты получают данные из внешнего мира: проблема оракулов. Или как строится масштабирование: роллапы изнутри.