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

зберігання

Просунутий рівень

Орі Померанц

30 грудня 2021 р.

9 хвилин на читання

Вступ

В ідеалі ми хотіли б зберігати все у сховищі Етеріуму, яке розподілене між тисячами комп'ютерів і має надзвичайно високу доступність (дані не можуть бути піддані цензурі) та цілісність (дані не можуть бути змінені несанкціонованим чином), але зберігання 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

Функції встановлення та отримання для кореня Меркла. Дозволяти всім оновлювати корінь Меркла — це вкрай погана ідея у виробничій системі. Я роблю це тут заради простоти прикладу коду. Не робіть цього в системі, де цілісність даних дійсно має значення.

    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.

Більше моїх робіт можна знайти тут (opens in a new tab).