Доказательства Меркла для целостности офлайн-данных

Введение

В идеале мы хотели бы хранить все в месте хранения Ethereum, которое распределено по тысячам компьютеров и обладает чрезвычайно высокой доступностью (данные не могут быть подвергнуты цензуре) и целостностью (данные не могут быть изменены несанкционированным образом), но хранение 32-байтового слова обычно стоит 20 000 единиц газа. На момент написания этой статьи эта стоимость эквивалентна 6,60 долларам США. При цене 21 цент за байт это слишком дорого для многих вариантов использования.

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

В этой статье вы узнаете, как обеспечить целостность данных, не храня их в блокчейне, с помощью доказательств Меркла (opens in a new tab).

Как это работает?

Теоретически мы могли бы просто хранить хэш данных в сети (он-чейн) и отправлять все данные в требующих их транзакциях. Однако это все еще слишком дорого. Байт данных в транзакции стоит около 16 единиц газа, что в настоящее время составляет около половины цента или около 5 долларов за килобайт. При цене 5000 долларов за мегабайт это все еще слишком дорого для многих вариантов использования, даже без учета дополнительных затрат на хэширование данных.

Решение заключается в многократном хэшировании различных подмножеств данных, поэтому для данных, которые вам не нужно отправлять, вы можете просто отправить хэш. Это делается с помощью дерева Меркла, древовидной структуры данных, в которой каждый узел представляет собой хэш узлов, расположенных под ним:

Корневой хэш — единственная часть, которую необходимо хранить в сети (он-чейн). Чтобы доказать определенное значение, вы предоставляете все хэши, которые необходимо объединить с ним для получения корневого хэша. Например, чтобы доказать C, вы предоставляете D, H(A-B) и H(E-H).

Реализация

Пример кода приведен здесь (opens in a new tab).

Код вне сети (офф-чейн)

В этой статье мы используем JavaScript для вычислений вне сети (офф-чейн). Большинство децентрализованных приложений имеют свой компонент вне сети (офф-чейн), написанный на JavaScript.

Создание корня Меркла

Сначала нам нужно предоставить корень Меркла в сеть.

1const ethers = require("ethers")

Мы используем хэш-функцию из пакета ethers (opens in a new tab).

1// Необработанные данные, целостность которых мы должны проверить. Первые два байта
2// — это идентификатор пользователя, а последние два байта — количество токенов, которыми
3// пользователь владеет в настоящее время.
4const dataArray = [
5  0x0bad0010, 0x60a70020, 0xbeef0030, 0xdead0040, 0xca110050, 0x0e660060,
6  0xface0070, 0xbad00080, 0x060d0091,
7]

Кодирование каждой записи в одно 256-битное целое число приводит к менее читаемому коду, чем, например, при использовании JSON. Однако это означает значительно меньшую обработку для извлечения данных в контракте и, следовательно, гораздо более низкие затраты на газ. Вы можете считывать JSON в сети (он-чейн) (opens in a new tab), но это плохая идея, если этого можно избежать.

1// Массив хэш-значений в виде BigInts
2const hashArray = dataArray

В данном случае наши данные изначально представляют собой 256-битные значения, поэтому обработка не требуется. Если мы используем более сложную структуру данных, например строки, нам нужно сначала хэшировать данные, чтобы получить массив хэшей. Обратите внимание, что это также связано с тем, что нам неважно, знают ли пользователи информацию о других пользователях. В противном случае нам пришлось бы выполнить хэширование, чтобы пользователь 1 не знал значение для пользователя 0, пользователь 2 не знал значение для пользователя 3 и т. д.

1// Преобразование между строкой, которую ожидает хэш-функция, и
2// BigInt, который мы используем во всем остальном коде.
3const hash = (x) =>
4  BigInt(ethers.utils.keccak256("0x" + x.toString(16).padStart(64, 0)))

Хэш-функция ethers ожидает получить строку JavaScript с шестнадцатеричным числом, например 0x60A7, и возвращает другую строку с той же структурой. Однако для остальной части кода проще использовать BigInt, поэтому мы преобразуем его в шестнадцатеричную строку и обратно.

1// Симметричный хэш пары, поэтому нам неважно, обратный ли порядок.
2const pairHash = (a, b) => hash(hash(a) ^ hash(b))

Эта функция симметрична (хэш от a xor (opens in a new tab) b). Это означает, что при проверке доказательства Меркла нам не нужно беспокоиться о том, ставить ли значение из доказательства до или после вычисленного значения. Проверка доказательства Меркла выполняется в сети (он-чейн), поэтому чем меньше нам нужно там делать, тем лучше.

Предупреждение: Криптография сложнее, чем кажется. В первоначальной версии этой статьи была хэш-функция hash(a^b). Это была плохая идея, поскольку она означала, что если вы знаете допустимые значения a и b, вы можете использовать b' = a^b^a', чтобы доказать любое желаемое значение a'. С этой функцией вам пришлось бы вычислять b' так, чтобы hash(a') ^ hash(b') равнялось известному значению (следующей ветви на пути к корню), что намного сложнее.

1// Значение, обозначающее, что определенная ветвь пуста, то есть
2// не имеет значения
3const empty = 0n

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

1// Вычислить один уровень вверх по дереву массива хэшей, взяв хэш
2// каждой пары в последовательности
3const oneLevelUp = (inputArray) => {
4  var result = []
5  var inp = [...inputArray] // Чтобы избежать перезаписи входных данных // При необходимости добавьте пустое значение (нам нужно, чтобы все листья были // объединены в пары)
6
7  if (inp.length % 2 === 1) inp.push(empty)
8
9  for (var i = 0; i < inp.length; i += 2)
10    result.push(pairHash(inp[i], inp[i + 1]))
11
12  return result
13} // oneLevelUp
Показать все

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

1const getMerkleRoot = (inputArray) => {
2  var result
3
4  result = [...inputArray] // Поднимаемся по дереву до тех пор, пока не останется только одно значение, которое и является // корнем. // // Если слой содержит нечетное количество записей, // код в oneLevelUp добавляет пустое значение, поэтому, если у нас, например, // 10 листьев, то на втором слое будет 5 ветвей, 3 // ветви на третьем, 2 на четвертом и корень на пятом
5
6  while (result.length > 1) result = oneLevelUp(result)
7
8  return result[0]
9}
Показать все

Чтобы получить корень, поднимайтесь вверх, пока не останется только одно значение.

Создание доказательства Меркла

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

1// Доказательство Меркла состоит из списка значений, которые нужно
2// хэшировать. Поскольку мы используем симметричную хэш-функцию, для проверки
3// доказательства нам не требуется позиция элемента, она нужна только для его создания.
4const getMerkleProof = (inputArray, n) => {
5    var result = [], currentLayer = [...inputArray], currentN = n
6
7    // Пока не достигнем вершины
8    while (currentLayer.length > 1) {
9        // Не допускаются слои нечетной длины
10        if (currentLayer.length % 2)
11            currentLayer.push(empty)
12
13        result.push(currentN % 2
14               // Если currentN нечетное, добавить в доказательство значение перед ним
15            ? currentLayer[currentN-1]
16               // Если четное, добавить значение после него
17            : currentLayer[currentN+1])
18
Показать все

Мы хэшируем (v[0],v[1]), (v[2],v[3]) и т. д. Так, для четных значений нам нужно следующее, а для нечетных — предыдущее.

1        // Переход на следующий слой вверх
2        currentN = Math.floor(currentN/2)
3        currentLayer = oneLevelUp(currentLayer)
4    }   // пока currentLayer.length > 1
5
6    return result
7}   // getMerkleProof

Код в сети (он-чейн)

Наконец, у нас есть код, который проверяет доказательство. Код в сети (он-чейн) написан на Solidity (opens in a new tab). Здесь оптимизация гораздо важнее, потому что газ относительно дорог.

1//SPDX-License-Identifier: Public Domain
2pragma solidity ^0.8.0;
3
4import "hardhat/console.sol";
Копировать

Я написал это с помощью среды разработки Hardhat (opens in a new tab), которая позволяет нам получать вывод консоли из Solidity (opens in a new tab) во время разработки.

1
2contract MerkleProof {
3    uint merkleRoot;
4
5    function getRoot() public view returns (uint) {
6      return merkleRoot;
7    }
8
9    // Крайне небезопасно, в рабочем коде доступ к
10    // этой функции ДОЛЖЕН БЫТЬ строго ограничен, вероятно, только для
11    // владельца
12    function setRoot(uint _merkleRoot) external {
13      merkleRoot = _merkleRoot;
14    }   // setRoot
Показать все
Копировать

Функции установки и получения для корня Меркла. Разрешение всем обновлять корень Меркла — крайне плохая идея в производственной системе. Я делаю это здесь для простоты примера кода. Не делайте этого в системе, где целостность данных действительно важна.

1    function hash(uint _a) internal pure returns(uint) {
2      return uint(keccak256(abi.encode(_a)));
3    }
4
5    function pairHash(uint _a, uint _b) internal pure returns(uint) {
6      return hash(hash(_a) ^ hash(_b));
7    }
Копировать

Эта функция генерирует хэш пары. Это просто перевод кода JavaScript для hash и pairHash на Solidity.

Примечание: это еще один случай оптимизации для удобочитаемости. Основываясь на определении функции (opens in a new tab), возможно, можно хранить данные как значение bytes32 (opens in a new tab) и избежать преобразований.

1    // Проверка доказательства Меркла
2    function verifyProof(uint _value, uint[] calldata _proof)
3        public view returns (bool) {
4      uint temp = _value;
5      uint i;
6
7      for(i=0; i<_proof.length; i++) {
8        temp = pairHash(temp, _proof[i]);
9      }
10
11      return temp == merkleRoot;
12    }
13
14}  // MarkleProof
Показать все
Копировать

В математической нотации проверка доказательства Меркла выглядит так: H(proof_n, H(proof_n-1, H(proof_n-2, ... H(proof_1, H(proof_0, value))...)))`. Этот код реализует это.

Доказательства Меркла и ролл-апы несовместимы

Доказательства Меркла плохо работают с ролл-апами. Причина в том, что ролл-апы записывают все данные транзакций на уровне L1, но обрабатывают их на L2. Стоимость отправки доказательства Меркла с транзакцией составляет в среднем 638 единиц газа на слой (в настоящее время байт в данных вызова стоит 16 единиц газа, если он не равен нулю, и 4, если он равен нулю). Если у нас есть 1024 слова данных, доказательство Меркла потребует десять слоев, или в общей сложности 6380 единиц газа.

На примере Optimism (opens in a new tab) можно увидеть, что запись газа на L1 стоит около 100 gwei, а газ на L2 — 0,001 gwei (это обычная цена, которая может расти при перегрузках). Таким образом, за стоимость одной единицы газа L1 мы можем потратить сто тысяч единиц газа на обработку L2. Если предположить, что мы не перезаписываем хранилище, это означает, что мы можем записать около пяти слов в хранилище на L2 по цене одной единицы газа L1. Для одного доказательства Меркла мы можем записать все 1024 слова в хранилище (при условии, что они могут быть вычислены в сети (он-чейн) с самого начала, а не предоставлены в транзакции), и при этом у нас останется большая часть газа.

Заключение

В реальной жизни вам, возможно, никогда не придется реализовывать деревья Меркла самостоятельно. Существуют хорошо известные и проверенные библиотеки, которые можно использовать, и, вообще говоря, лучше не реализовывать криптографические примитивы самостоятельно. Но я надеюсь, что теперь вы лучше понимаете доказательства Меркла и можете решить, когда их стоит использовать.

Обратите внимание, что, хотя доказательства Меркла сохраняют целостность, они не сохраняют доступность. Знание того, что никто другой не может забрать ваши активы, — слабое утешение, если хранилище данных решит запретить доступ и вы также не сможете построить дерево Меркла для доступа к ним. Поэтому деревья Меркла лучше всего использовать с каким-либо децентрализованным хранилищем, например IPFS.

Больше моих работ смотрите здесь (opens in a new tab).

Последнее обновление страницы: 18 декабря 2025 г.

l (opens in a new tab)

q (opens in a new tab)

w (opens in a new tab)

+5

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