Доказательства Меркла для целостности офчейн-данных
Введение
В идеале мы хотели бы хранить все в хранилище Эфириума, которое распределено по тысячам компьютеров и обладает чрезвычайно высокой доступностью (данные не могут быть подвергнуты цензуре) и целостностью (данные не могут быть изменены несанкционированным образом), но хранение 32-байтового слова обычно стоит 20 000 газа. На момент написания этой статьи эта стоимость эквивалентна $6,60. При цене 21 цент за байт это слишком дорого для многих вариантов использования.
Чтобы решить эту проблему, экосистема Эфириума разработала множество альтернативных способов децентрализованного хранения данных. Обычно они предполагают компромисс между доступностью и ценой. Однако целостность, как правило, гарантируется.
В этой статье вы узнаете, как обеспечить целостность данных без их хранения в блокчейне, используя доказательства Меркла (opens in a new tab).
Как это работает?
В теории мы могли бы просто хранить хеш данных ончейн и отправлять все данные в транзакциях, которые этого требуют. Однако это все еще слишком дорого. Один байт данных в транзакции стоит около 16 газа, что в настоящее время составляет около половины цента, или около $5 за килобайт. При цене $5000 за мегабайт это по-прежнему слишком дорого для многих целей, даже без учета дополнительных затрат на хеширование данных.
Решение заключается в многократном хешировании различных подмножеств данных, поэтому для данных, которые вам не нужно отправлять, вы можете просто отправить хеш. Вы делаете это с помощью дерева Меркла — древовидной структуры данных, где каждый узел является хешем узлов, находящихся под ним:
Корневой хеш — это единственная часть, которую необходимо хранить ончейн. Чтобы доказать определенное значение, вы предоставляете все хеши, которые нужно объединить с ним для получения корня. Например, чтобы доказать C, вы предоставляете D, H(A-B) и H(E-H).
Реализация
Пример кода представлен здесь (opens in a new tab).
Офчейн-код
В этой статье мы используем JavaScript для офчейн-вычислений. Большинство децентрализованных приложений имеют свой офчейн-компонент на JavaScript.
Создание корня Меркла
Сначала нам нужно предоставить корень Меркла в цепь.
const ethers = require("ethers")
Мы используем хеш-функцию из пакета ethers (opens in a new tab).
// Сырые данные, целостность которых мы должны проверить. Первые два байта — э
// то идентификатор пользователя, а последние два байта — количество токенов, которыми
// пользователь владеет в настоящее время.
const dataArray = [
0x0bad0010, 0x60a70020, 0xbeef0030, 0xdead0040, 0xca110050, 0x0e660060,
0xface0070, 0xbad00080, 0x060d0091,
]
Кодирование каждой записи в одно 256-битное целое число делает код менее читаемым, чем, например, при использовании JSON. Однако это означает значительно меньший объем обработки для извлечения данных в контракте, а значит, гораздо меньшие затраты газа. Вы можете читать JSON ончейн (opens in a new tab), но это плохая идея, если этого можно избежать.
// Массив значений хешей в виде BigInt
const hashArray = dataArray
В данном случае наши данные изначально представляют собой 256-битные значения, поэтому никакая обработка не требуется. Если мы используем более сложную структуру данных, например строки, нам нужно сначала хешировать данные, чтобы получить массив хешей. Обратите внимание, что это также связано с тем, что нас не волнует, знают ли пользователи информацию других пользователей. В противном случае нам пришлось бы выполнять хеширование так, чтобы пользователь 1 не знал значение для пользователя 0, пользователь 2 не знал значение для пользователя 3 и т. д.
// Преобразование между строкой, которую ожидает хеш-функция, и
// BigInt, который мы используем везде.
const hash = (x) =>
BigInt(ethers.utils.keccak256("0x" + x.toString(16).padStart(64, 0)))
Хеш-функция ethers ожидает получить строку JavaScript с шестнадцатеричным числом, например 0x60A7, и возвращает другую строку с такой же структурой. Однако для остальной части кода проще использовать BigInt, поэтому мы преобразуем данные в шестнадцатеричную строку и обратно.
// Симметричный хеш пары, поэтому нам будет неважно, если порядок будет обратным.
const 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') было равно известному значению (следующей ветви на пути к корню), что намного сложнее.
// Значение, обозначающее, что определенная ветвь пуста, не
// имеет значения
const empty = 0n
Когда количество значений не является целой степенью двойки, нам нужно обрабатывать пустые ветви. В этой программе это делается путем подстановки нуля в качестве заполнителя.
// Вычисление на один уровень вверх по дереву массива хешей путем получения хеша
// каждой пары последовательно
const oneLevelUp = (inputArray) => {
var result = []
var inp = [...inputArray] // Чтобы избежать перезаписи ввода // Добавляем пустое значение при необходимости (нам нужно, чтобы все листья были // парными)
if (inp.length % 2 === 1) inp.push(empty)
for (var i = 0; i < inp.length; i += 2)
result.push(pairHash(inp[i], inp[i + 1]))
return result
} // oneLevelUp
Эта функция «поднимается» на один уровень в дереве Меркла путем хеширования пар значений на текущем уровне. Обратите внимание, что это не самая эффективная реализация: мы могли бы избежать копирования входных данных и просто добавлять hashEmpty в цикле там, где это необходимо, но этот код оптимизирован для читаемости.
const getMerkleRoot = (inputArray) => {
var result
result = [...inputArray] // Поднимаемся вверх по дереву, пока не останется только одно значение, то есть // корень. // // Если слой имеет нечетное количество записей, // код в oneLevelUp добавляет пустое значение, поэтому, если у нас есть, например, // 10 листьев, у нас будет 5 ветвей на втором слое, 3 // ветви на третьем, 2 на четвертом, а корень будет пятым
while (result.length > 1) result = oneLevelUp(result)
return result[0]
}
Чтобы получить корень, поднимайтесь вверх, пока не останется только одно значение.
Создание доказательства Меркла
Доказательство Меркла — это значения, которые нужно хешировать вместе с доказываемым значением, чтобы получить корень Меркла. Доказываемое значение часто доступно из других данных, поэтому я предпочитаю предоставлять его отдельно, а не как часть кода.
// Доказательство Меркла состоит из значения списка записей для
// хеширования с ним. Поскольку мы используем симметричную хеш-функцию, нам не
// нужно знать расположение элемента для проверки доказательства, только для его создания
const getMerkleProof = (inputArray, n) => {
var result = [], currentLayer = [...inputArray], currentN = n
// Пока мы не достигнем вершины
while (currentLayer.length > 1) {
// Нет слоев нечетной длины
if (currentLayer.length % 2)
currentLayer.push(empty)
result.push(currentN % 2
// Если currentN нечетное, добавляем вместе со значением перед ним в доказательство
? currentLayer[currentN-1]
// Если оно четное, добавляем значение после него
: currentLayer[currentN+1])
Мы хешируем (v[0],v[1]), (v[2],v[3]) и т. д. Таким образом, для четных значений нам нужно следующее, а для нечетных — предыдущее.
// Переход на следующий уровень вверх
currentN = Math.floor(currentN/2)
currentLayer = oneLevelUp(currentLayer)
} // while currentLayer.length > 1
return result
} // getMerkleProof
Ончейн-код
Наконец, у нас есть код, который проверяет доказательство. Ончейн-код написан на Solidity (opens in a new tab). Оптимизация здесь намного важнее, потому что газ стоит относительно дорого.
//SPDX-License-Identifier: Public Domain
pragma solidity ^0.8.0;
import "hardhat/console.sol";
Я написал это, используя среду разработки Hardhat (opens in a new tab), которая позволяет нам получать вывод в консоль из Solidity (opens in a new tab) во время разработки.
contract MerkleProof {
uint merkleRoot;
function getRoot() public view returns (uint) {
return merkleRoot;
}
// Крайне небезопасно, в рабочем коде доступ к
// этой функции ДОЛЖЕН БЫТЬ строго ограничен, вероятно, для
// владельца
function setRoot(uint _merkleRoot) external {
merkleRoot = _merkleRoot;
} // setRoot
Функции установки (set) и получения (get) для корня Меркла. Позволять всем обновлять корень Меркла — крайне плохая идея в рабочей системе. Я делаю это здесь ради простоты примера кода. Не делайте этого в системе, где целостность данных действительно имеет значение.
function hash(uint _a) internal pure returns(uint) {
return uint(keccak256(abi.encode(_a)));
}
function pairHash(uint _a, uint _b) internal pure returns(uint) {
return hash(hash(_a) ^ hash(_b));
}
Эта функция генерирует хеш пары. Это просто перевод на Solidity кода JavaScript для hash и pairHash.
Примечание: Это еще один случай оптимизации для читаемости. Судя по определению функции (opens in a new tab), возможно, было бы лучше хранить данные как значение bytes32 (opens in a new tab) и избежать преобразований.
// Проверка доказательства Меркла
function verifyProof(uint _value, uint[] calldata _proof)
public view returns (bool) {
uint temp = _value;
uint i;
for(i=0; i<_proof.length; i++) {
temp = pairHash(temp, _proof[i]);
}
return temp == merkleRoot;
}
} // MarkleProof
В математической нотации проверка доказательства Меркла выглядит так: H(proof_n, H(proof_n-1, H(proof_n-2, ... H(proof_1, H(proof_0, value))...))). Этот код реализует ее.
Доказательства Меркла и роллапы плохо сочетаются
Доказательства Меркла плохо работают с роллапами. Причина в том, что роллапы записывают все данные транзакции на уровень 1 (l1), но обрабатывают их на уровне 2 (l2). Стоимость отправки доказательства Меркла с транзакцией в среднем составляет 638 газа на уровень (в настоящее время байт в данных вызова стоит 16 газа, если он не равен нулю, и 4, если равен нулю). Если у нас есть 1024 слова данных, доказательство Меркла требует десяти уровней, или в общей сложности 6380 газа.
Если посмотреть, например, на Optimism (opens in a new tab), запись газа на уровне 1 (l1) стоит около 100 Gwei, а газ на уровне 2 (l2) стоит 0,001 Gwei (это нормальная цена, она может расти при перегрузке сети). Таким образом, по цене одной единицы газа на уровне 1 (l1) мы можем потратить сто тысяч единиц газа на обработку на уровне 2 (l2). При условии, что мы не перезаписываем хранилище, это означает, что мы можем записать около пяти слов в хранилище на уровне 2 (l2) по цене одной единицы газа на уровне 1 (l1). Вместо одного доказательства Меркла мы можем записать все 1024 слова в хранилище (при условии, что они изначально могут быть вычислены ончейн, а не предоставлены в транзакции), и при этом у нас останется большая часть газа.
Заключение
В реальной жизни вы, возможно, никогда не будете реализовывать деревья Меркла самостоятельно. Существуют хорошо известные и проверенные библиотеки, которые вы можете использовать, и, вообще говоря, лучше не реализовывать криптографические примитивы самостоятельно. Но я надеюсь, что теперь вы лучше понимаете доказательства Меркла и можете решить, когда их стоит использовать.
Обратите внимание, что хотя доказательства Меркла сохраняют целостность, они не сохраняют доступность. Знание того, что никто другой не может забрать ваши активы, служит слабым утешением, если хранилище данных решит запретить доступ, и вы также не сможете построить дерево Меркла для доступа к ним. Поэтому деревья Меркла лучше всего использовать с каким-либо децентрализованным хранилищем, таким как IPFS.