Дерево Меркла (Merkle tree) — двоичное дерево, в котором каждый лист — фрагмент данных, каждый узел выше — криптографический хеш двух дочерних, а один корневой хеш фиксирует состояние всего дерева. Это одна из базовых структур данных Bitcoin и основа подтверждения резервов (Proof of Reserves). Названо в честь Ральфа Меркла, запатентовавшего эту структуру в 1979 году. В Bitcoin используется с самого первого блока 2009 года.
Что даёт эта структура
Для криптовалют важны два свойства.
Компактная фиксация данных. Один 32-байтовый корневой хеш представляет сколь угодно большой объём данных: дерево Меркла над миллионом транзакций всё равно даёт один 32-байтовый корень.
Быстрое доказательство принадлежности. Чтобы доказать, что конкретная транзакция входит в дерево, достаточно пути от листа к корню — обычно 20–32 хеша даже для деревьев с миллионами листьев. Проверяющий хеширует свои данные вдоль этого пути; если вычисленный корень совпал с опубликованным, принадлежность доказана.
Где деревья Меркла встречаются в вашей схеме хранения
Три конкретных примера.
Подтверждение резервов на биржах. Многие биржи публикуют подтверждение резервов на основе дерева Меркла. Баланс каждого пользователя — лист дерева, а опубликованный корень фиксирует общую сумму. Любой пользователь может сам проверить, что его баланс учтён, пройдя путь от своего листа к опубликованному корню. Без деревьев Меркла такое проверяемое раскрытие в масштабах биржи было бы невозможно.
Устройство блока Bitcoin. Каждый блок содержит корень дерева Меркла всех своих транзакций. Лёгкие клиенты (SPV, simplified payment verification) с его помощью доказывают, что транзакция входит в подтверждённый блок, не скачивая блок целиком. В white paper Bitcoin этой конструкции посвящён целый раздел.
Раздача аирдропов. Многие аирдропы публикуют список получателей в виде дерева Меркла: каждый адрес с причитающейся суммой — лист, а корень записан в смарт-контракт аирдропа. Чтобы получить токены, пользователь предъявляет путь, доказывающий, что его адрес есть в дереве. Так можно раздать токены миллионам адресов, не раздувая пропорционально стоимость хранения данных в блокчейне.
Как проверить свой баланс в подтверждении резервов биржи
Общий порядок (названия разделов у бирж разные):
- Войдите в аккаунт биржи и откройте раздел Proof of Reserves.
- На странице будут ID вашего аккаунта, хеш вашего листа и путь соседних хешей от листа к корню.
- Сравните показанный хеш корня с корнем на публичной странице подтверждения резервов этой биржи.
- Если они совпадают, ваш баланс проверяемо учтён в опубликованной сумме.
Математика такая: хеш вашего листа вместе с первым соседним хешем даёт хеш следующего уровня; он вместе со следующим соседом — хеш уровнем выше, и так до вершины, где результат должен совпасть с опубликованным корнем. Современные инструменты подтверждения резервов делают эту проверку автоматически; если на бирже лежит ощутимая для вас сумма, проверять раз в квартал — полезная привычка.
Чего корень дерева Меркла не доказывает
Дерево Меркла фиксирует данные на момент построения. Оно не доказывает, что данные верны (биржа могла внести неправильные балансы), что соответствующие активы действительно существуют (для этого нужны отдельные подтверждения обязательств и резервов) и что в дереве учтены все аккаунты (биржа могла какие-то просто пропустить).
Поэтому убедительное подтверждение резервов сочетает дерево Меркла по обязательствам с отдельным криптографическим подтверждением адресов с резервами и независимым аудитом. Дерево Меркла необходимо, но одного его недостаточно.
Дополнительное чтение: Подтверждение резервов, CEX.