Как реализовать дерево Меркла в Solidity

Дерево Меркла — это двоичное дерево, которое позволяет эффективно и безопасно проверять содержимое больших структур данных. Идея этого дерева была предложена и запатентована в 1982 году американским криптографом Ральфом Мерклем.

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

Теория

Изначально имеется набор данных, никак не связанных друг с другом. Для каждого блока данных (в контексте блокчейна транзакций) нам необходимо вычислить хэш блока. Количество блоков данных должно быть 2^N , поскольку при построении дерева предыдущие блоки хэшируются попарно на каждой итерации. Затем пара хешей группируется и на их основе создается новый хэш. Хеширование будет продолжаться до тех пор, пока на каждом уровне есть что группировать, и прекратится, когда останется только одна пара, из которой получается корневой хеш — корень Меркла.

H(1-2) = keccak256(H(1) + H(2))

H(3-4) = keccak256(H(3) + H(4))

H(5-6) = keccak256(H(5) + H(6))

H(7-8) = keccak256(H(7) + H(8))

H(1-2-3-4) = keccak256(H(1-2) + H(3-4))

H(5-6-7-8) = keccak256(H(5-6) + H(7-8))

H(1-2-3-4-5-6-7-8) = keccak256(H(1-2-3-4) + H(5-6-7-8))

Получив корень, мы можем проверить данные. Если корневой хеш совпадает с исходным хэшем, все в порядке, данные действительны. Также можно эффективно проверить, присутствуют ли определенные данные в древовидной структуре.

Допустим, мы хотим проверить наличие хеша H2 в дереве. Доказательством будет массив данных: H1 , H3-4 , H5-6-7-8 . Благодаря этим хешам мы можем восстановить корневой хеш:

H(1-2-3-4-5-6-7-8) = keccak256(keccak256(keccak256(H(1) + H(2)) + H(3-4)) + H(5-6-7-8))

Затем сравниваем полученный хеш с исходным. Если они совпадают, значит, в дереве присутствует хеш H2 .

Упражняться

Давайте теперь посмотрим, как реализовать дерево Меркла и проверку данных в Solidity.

Для простоты мы запишем массив транзакций непосредственно в блокчейн, а также массив хэшей. Поскольку мы будем использовать встроенную функцию keccak256 , которая возвращает хэш размером 32 байта, тип данных массива хешей будет bytes32 . Массив также будет иметь динамическую длину. В общем, длина массива хэшей не будет такой же, как длина массива транзакций, поскольку он будет содержать созданные хэши. Мы могли бы заранее вычислить длину, но ради упрощения кода не будем этого делать. Если хотите, вы можете сделать каждый из этих массивов public и читать хэши транзакций.

Мы будем производить hashes в конструкторе. Первым шагом является подсчет хэшей блоков с transactions в цикле. Затем на каждом уровне дерева количество хэшей уменьшается в 2 раза. Поскольку мы будем хранить хеши в массиве хешей, смещения индексов необходимо хранить отдельно. Итератор во внутреннем цикле увеличивается на 2, потому что при вычислении и добавлении хешей мы будем брать пару элементов. В abi.encodePacked на этот раз добавим по 2 хеша, каждому из которых правильно зададим индексы: для левого элемента — значение текущего смещения сдвига + индекс на текущем уровне дерева, а для правого элемента — то же самое + 1.

Итак, дерево мы построили, но интерес состоит в проверке данных. Для этого напишем функцию validateTransaction , которая принимает транзакцию и ее индекс. К сожалению, в Solidity нет метода find для массивов, поэтому проще просто передать индекс транзакции.

Для начала давайте посчитаем хеш транзакции и создадим массив доказательств. Мы находим количество доказательств в зависимости от длины массива транзакций и устанавливаем proofsIndexes . После этого на каждом уровне дерева находим необходимый элемент в зависимости от индекса, беря правый или левый элемент, учитывая смещения в hashes . Затем мы проходим по массиву индексов доказательства, проверяя индекс на четность и вычисляя хэш в зависимости от того, левый или правый элемент в паре. Наконец, мы сравниваем полученный хэш с корневым хешем и возвращаем результат.

Приложение

В блокчейне есть несколько применений дерева Меркла.

• Хранение транзакций . Например, в Биткойне блок транзакций хранит только merkle_root своих транзакций. Это уменьшает размер блока и нагрузку на сеть. После накопления определенного количества транзакций можно удалить старые транзакции для экономии места, но сами блоки остаются неизменными, поскольку в них хранится только корень дерева.
• Майнинг : Блок биткойнов состоит из двух частей — заголовка блока и списка транзакций. Чтобы избежать необходимости каждый раз пересчитывать хеши транзакций, они выстраиваются в дерево Меркла, после чего хэшируется заголовок блока, а не весь блок, и берется случайное число nonce. При отправке блока другим узлам вычисляется корень списка транзакций, и если он не соответствует корню в заголовке, блок отклоняется.
• Верификация : Суть верификации заключается в аудите без необходимости загрузки всей цепочки блоков. Этот процесс значительно упрощается, а также позволяет подтверждать существование данных без раскрытия информации о данных, что может быть полезно для проверки конфиденциальной информации.

Краткое содержание

Без деревьев Меркла блокчейны были бы слишком громоздкими, а доказательства Меркла позволяют экономически эффективно проверять подлинность данных.

Деревья Меркла активно используются в блокчейнах (например, Биткойн, Эфириум) для эффективного хранения транзакций, но это не единственное применение. Например, после краха биржи FTX многие биржи внедрили механизм подтверждения резерва, который использует дерево Меркла.