Докази Меркла для цілісності даних в автономному режимі

сховище

Для досвідчених користувачів

Ori Pomerantz

30 грудня 2021 р.

9 читається за хвилину

Вступ

В ідеалі ми хотіли б зберігати все в сховищі 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")

Ми використовуємо хеш-функцію з пакета ethersopens 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 xoropens 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
Показати все

Ця функція «підіймається» на один рівень у дереві Меркла, хешуючи пари значень на поточному рівні. Зауважте, що це не найефективніша реалізація. Ми могли б уникнути копіювання вхідних даних і просто додати empty, коли це доречно в циклі, але цей код оптимізовано для читабельності.

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

Ончейн-код

Нарешті ми маємо код, який перевіряє доказ. Ончейн-код написано на Solidityopens in a new tab. Оптимізація тут набагато важливіша, оскільки газ відносно дорогий.

1//SPDX-License-Identifier: Public Domain
2pragma solidity ^0.8.0;
3
4import "hardhat/console.sol";

Я написав це за допомогою середовища розробки Hardhatopens in a new tab, яке дозволяє нам отримувати консольний вивід із Solidityopens 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, можливо, вдасться зберігати дані як значення bytes32opens 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))...)))`. Цей код реалізує його.

Докази Меркла та ролапи не поєднуються

Докази Меркла погано працюють з ролапами. Причина в тому, що rollups записують всі дані транзакції на L1, але обробляють на L2. Вартість відправки доказу Меркла з транзакцією в середньому становить 638 газів на шар (наразі байт даних виклику коштує 16 газів, якщо він не дорівнює нулю, і 4, якщо він дорівнює нулю). Якщо у нас є 1024 слова даних, доказ Меркла вимагає десяти шарів, або загалом 6380 газів.

Наприклад, якщо подивитися на Optimismopens in a new tab, запис на L1 коштує близько 100 gwei газу, а на L2 — 0,001 gwei (це звичайна ціна, яка може зростати при перевантаженні мережі). Отже, на вартість одного газу L1 ми можемо витратити сто тисяч газу на перероблювання L2. Якщо припустити, що ми не перезаписуємо сховище, це означає, що ми можемо написати близько п’яти слів для зберігання на L2 за ціною одного газу L1. Для одного доказу Меркла ми можемо записати всі 1024 слова до сховища (якщо припустити, що їх можна обчислити ончейн, а не надавати в транзакції), і при цьому у нас залишиться більша частина газу.

Висновок

У реальному житті ви ніколи не зможете реалізувати дерева Меркла самостійно. Існують добре відомі та перевірені бібліотеки, які ви можете використовувати, і, загалом кажучи, краще не реалізовувати криптографічні примітиви самостійно. Але я сподіваюся, що тепер ви краще розумієте докази Меркла і зможете вирішити, коли їх варто використовувати.

Зауважте, що хоча докази Меркла зберігають цілісність, вони не зберігають доступність. Знання того, що ніхто інший не може забрати ваші активи, є невеликою втіхою, якщо сховище даних вирішить заборонити доступ, ви також не зможете створити дерево Merkle для доступу до них. Тому дерева Меркла найкраще використовувати з якимось децентралізованим сховищем, таким як IPFS.

Більше моїх робіт дивіться тутopens in a new tab.

Останні оновлення сторінки: 18 грудня 2025 р.