Dowody Merkle'a dla integralności danych offline

przechowywanie

Zaawansowany

Ori Pomerantz

30 grudnia 2021

10 minut czytania

Wprowadzenie

W idealnym przypadku chcielibyśmy przechowywać wszystko w pamięci masowej Ethereum, która jest rozproszona na tysiącach komputerów i charakteryzuje się niezwykle wysoką dostępnością (dane nie mogą być cenzurowane) oraz integralnością (dane nie mogą być modyfikowane w nieautoryzowany sposób), ale przechowywanie 32-bajtowego słowa kosztuje zazwyczaj 20 000 gazu. W momencie pisania tego tekstu koszt ten jest równy 6,60 USD. Przy cenie 21 centów za bajt jest to zbyt drogie dla wielu zastosowań.

Aby rozwiązać ten problem, ekosystem Ethereum opracował wiele alternatywnych sposobów na zdecentralizowane przechowywanie danych. Zazwyczaj wiążą się one z kompromisem między dostępnością a ceną. Jednak integralność jest zazwyczaj zapewniona.

W tym artykule dowiesz się, jak zapewnić integralność danych bez przechowywania ich na blockchainie, wykorzystując dowody Merkle'a (opens in a new tab).

Jak to działa?

W teorii moglibyśmy po prostu przechowywać hash danych onchain i wysyłać wszystkie dane w transakcjach, które tego wymagają. Jednak to wciąż jest zbyt drogie. Bajt danych w transakcji kosztuje około 16 gazu, co obecnie wynosi około pół centa, czyli około 5 USD za kilobajt. Przy cenie 5000 USD za megabajt jest to nadal zbyt drogie dla wielu zastosowań, nawet bez dodatkowych kosztów haszowania danych.

Rozwiązaniem jest wielokrotne haszowanie różnych podzbiorów danych, dzięki czemu dla danych, których nie musisz wysyłać, możesz po prostu wysłać hash. Robi się to za pomocą drzewa Merklego, struktury danych w postaci drzewa, w której każdy węzeł jest hashem węzłów znajdujących się poniżej:

Hash korzenia to jedyna część, która musi być przechowywana onchain. Aby udowodnić określoną wartość, dostarczasz wszystkie hashe, które muszą zostać z nią połączone, aby uzyskać korzeń. Na przykład, aby udowodnić C, dostarczasz D, H(A-B) oraz H(E-H).

Implementacja

Przykładowy kod jest dostępny tutaj (opens in a new tab).

Kod pozałańcuchowy

W tym artykule używamy języka JavaScript do obliczeń pozałańcuchowych. Większość zdecentralizowanych aplikacji ma swój komponent pozałańcuchowy w języku JavaScript.

Tworzenie korzenia drzewa Merklego

Najpierw musimy dostarczyć korzeń drzewa Merklego do łańcucha.

const ethers = require("ethers")

Używamy funkcji skrótu z pakietu ethers (opens in a new tab).

// Surowe dane, których integralność musimy zweryfikować. Pierwsze dwa bajty s
// ą identyfikatorem użytkownika, a ostatnie dwa bajty to liczba tokenów, które
// użytkownik obecnie posiada.
const dataArray = [
  0x0bad0010, 0x60a70020, 0xbeef0030, 0xdead0040, 0xca110050, 0x0e660060,
  0xface0070, 0xbad00080, 0x060d0091,
]

Kodowanie każdego wpisu jako pojedynczej 256-bitowej liczby całkowitej skutkuje mniej czytelnym kodem niż na przykład użycie JSON. Oznacza to jednak znacznie mniej przetwarzania w celu odzyskania danych w kontrakcie, a co za tym idzie, znacznie niższe koszty gazu. Możesz odczytywać JSON onchain (opens in a new tab), ale jest to po prostu zły pomysł, jeśli można tego uniknąć.

// Tablica wartości hash, jako BigInty
const hashArray = dataArray

W tym przypadku nasze dane to od samego początku wartości 256-bitowe, więc żadne przetwarzanie nie jest potrzebne. Jeśli użyjemy bardziej skomplikowanej struktury danych, takiej jak ciągi znaków, musimy upewnić się, że najpierw zhaszujemy dane, aby uzyskać tablicę hashów. Zauważ, że wynika to również z faktu, że nie zależy nam na tym, czy użytkownicy znają informacje innych użytkowników. W przeciwnym razie musielibyśmy użyć haszowania w taki sposób, aby użytkownik 1 nie znał wartości dla użytkownika 0, użytkownik 2 nie znał wartości dla użytkownika 3 itd.

// Konwersja między ciągiem znaków, którego oczekuje funkcja skrótu, a
// BigIntem, którego używamy wszędzie indziej.
const hash = (x) =>
  BigInt(ethers.utils.keccak256("0x" + x.toString(16).padStart(64, 0)))

Funkcja skrótu z pakietu ethers oczekuje ciągu znaków JavaScript z liczbą szesnastkową, takiego jak 0x60A7, i odpowiada innym ciągiem znaków o tej samej strukturze. Jednak w pozostałej części kodu łatwiej jest używać BigInt, więc konwertujemy na ciąg szesnastkowy i z powrotem.

// Symetryczny hash pary, dzięki czemu nie będzie nas obchodzić, czy kolejność jest odwrócona.
const pairHash = (a, b) => hash(hash(a) ^ hash(b))

Ta funkcja jest symetryczna (hash z a xor (opens in a new tab) b). Oznacza to, że podczas sprawdzania dowodu Merkle'a nie musimy się martwić, czy umieścić wartość z dowodu przed, czy po obliczonej wartości. Sprawdzanie dowodu Merkle'a odbywa się onchain, więc im mniej musimy tam zrobić, tym lepiej.

Ostrzeżenie: Kryptografia jest trudniejsza, niż się wydaje. Początkowa wersja tego artykułu zawierała funkcję skrótu hash(a^b). To był zły pomysł, ponieważ oznaczało to, że znając prawidłowe wartości a i b, można było użyć b' = a^b^a' do udowodnienia dowolnej pożądanej wartości a'. Przy użyciu tej funkcji musiałbyś obliczyć b' w taki sposób, aby hash(a') ^ hash(b') było równe znanej wartości (kolejnej gałęzi w drodze do korzenia), co jest znacznie trudniejsze.

// Wartość oznaczająca, że dana gałąź jest pusta, nie
// ma wartości
const empty = 0n

Gdy liczba wartości nie jest całkowitą potęgą dwójki, musimy obsłużyć puste gałęzie. Ten program robi to, wstawiając zero jako symbol zastępczy.

// Oblicz jeden poziom w górę drzewa tablicy hash, obliczając hash
// każdej pary po kolei
const oneLevelUp = (inputArray) => {
  var result = []
  var inp = [...inputArray] // Aby uniknąć nadpisania danych wejściowych // Dodaj pustą wartość, jeśli to konieczne (potrzebujemy, aby wszystkie liście były // sparowane)

  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

Ta funkcja „wspina się” o jeden poziom w drzewie Merklego, haszując pary wartości na bieżącej warstwie. Zauważ, że nie jest to najbardziej wydajna implementacja; moglibyśmy uniknąć kopiowania danych wejściowych i po prostu dodać hashEmpty w odpowiednim miejscu w pętli, ale ten kod został zoptymalizowany pod kątem czytelności.

const getMerkleRoot = (inputArray) => {
  var result

  result = [...inputArray] // Wspinaj się w górę drzewa, aż zostanie tylko jedna wartość, czyli // korzeń. // // Jeśli warstwa ma nieparzystą liczbę wpisów, // kod w oneLevelUp dodaje pustą wartość, więc jeśli mamy na przykład // 10 liści, będziemy mieli 5 gałęzi w drugiej warstwie, 3 // gałęzie w trzeciej, 2 w czwartej, a korzeń jest piąty

  while (result.length > 1) result = oneLevelUp(result)

  return result[0]
}

Aby uzyskać korzeń, wspinaj się, aż pozostanie tylko jedna wartość.

Tworzenie dowodu Merkle'a

Dowód Merkle'a to wartości, które należy zhaszować razem z udowadnianą wartością, aby odzyskać korzeń drzewa Merklego. Wartość do udowodnienia jest często dostępna z innych danych, więc wolę podawać ją oddzielnie, a nie jako część kodu.

// Dowód Merkle'a składa się z wartości z listy wpisów do
// haszowania. Ponieważ używamy symetrycznej funkcji skrótu, nie
// potrzebujemy lokalizacji elementu, aby zweryfikować dowód, a jedynie do jego utworzenia
const getMerkleProof = (inputArray, n) => {
    var result = [], currentLayer = [...inputArray], currentN = n

    // Aż dotrzemy na sam szczyt
    while (currentLayer.length > 1) {
        // Brak warstw o nieparzystej długości
        if (currentLayer.length % 2)
            currentLayer.push(empty)

        result.push(currentN % 2
               // Jeśli currentN jest nieparzyste, dodaj wartość przed nim do dowodu
            ? currentLayer[currentN-1]
               // Jeśli jest parzyste, dodaj wartość po nim
            : currentLayer[currentN+1])

Haszujemy (v[0],v[1]), (v[2],v[3]) itd. Zatem dla wartości parzystych potrzebujemy następnej, a dla nieparzystych – poprzedniej.

        // Przejdź do następnej warstwy w górę
        currentN = Math.floor(currentN/2)
        currentLayer = oneLevelUp(currentLayer)
    }   // while currentLayer.length > 1

    return result
}   // getMerkleProof

Kod onchain

Na koniec mamy kod, który sprawdza dowód. Kod onchain jest napisany w języku Solidity (opens in a new tab). Optymalizacja jest tutaj znacznie ważniejsza, ponieważ gaz jest stosunkowo drogi.

//SPDX-License-Identifier: Public Domain
pragma solidity ^0.8.0;

import "hardhat/console.sol";

Napisałem to przy użyciu środowiska programistycznego Hardhat (opens in a new tab), które pozwala nam na wyświetlanie danych w konsoli z poziomu Solidity (opens in a new tab) podczas programowania.


contract MerkleProof {
    uint merkleRoot;

    function getRoot() public view returns (uint) {
      return merkleRoot;
    }

    // Niezwykle niebezpieczne, w kodzie produkcyjnym dostęp do
    // tej funkcji MUSI BYĆ ściśle ograniczony, prawdopodobnie do
    // właściciela
    function setRoot(uint _merkleRoot) external {
      merkleRoot = _merkleRoot;
    }   // setRoot

Funkcje ustawiające (set) i pobierające (get) dla korzenia drzewa Merklego. Pozwolenie każdemu na aktualizację korzenia drzewa Merklego to niezwykle zły pomysł w systemie produkcyjnym. Robię to tutaj dla uproszczenia przykładowego kodu. Nie rób tego w systemie, w którym integralność danych ma rzeczywiste znaczenie.

    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));
    }

Ta funkcja generuje hash pary. Jest to po prostu tłumaczenie na Solidity kodu JavaScript dla hash i pairHash.

Uwaga: To kolejny przypadek optymalizacji pod kątem czytelności. Opierając się na definicji funkcji (opens in a new tab), możliwe byłoby przechowywanie danych jako wartości bytes32 (opens in a new tab) i uniknięcie konwersji.

    // Weryfikacja dowodu Merkle'a
    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

W notacji matematycznej weryfikacja dowodu Merkle'a wygląda następująco: H(proof_n, H(proof_n-1, H(proof_n-2, ... H(proof_1, H(proof_0, value))...))). Ten kod to implementuje.

Dowody Merkle'a i rollupy nie idą w parze

Dowody Merkle'a nie współpracują dobrze z rollupami. Powodem jest to, że rollupy zapisują wszystkie dane transakcji na warstwie 1 (L1), ale przetwarzają je na warstwie 2 (L2). Koszt wysłania dowodu Merkle'a wraz z transakcją wynosi średnio 638 gazu na warstwę (obecnie bajt w danych wywołania kosztuje 16 gazu, jeśli nie jest zerem, i 4, jeśli jest zerem). Jeśli mamy 1024 słowa danych, dowód Merkle'a wymaga dziesięciu warstw, czyli łącznie 6380 gazu.

Patrząc na przykład na Optimism (opens in a new tab), zapis gazu na L1 kosztuje około 100 gwei, a gaz na L2 kosztuje 0,001 gwei (jest to normalna cena, która może wzrosnąć w przypadku przeciążenia sieci). Zatem za koszt jednego gazu na L1 możemy wydać sto tysięcy gazu na przetwarzanie na L2. Zakładając, że nie nadpisujemy pamięci masowej, oznacza to, że możemy zapisać około pięciu słów do pamięci na L2 w cenie jednego gazu na L1. W przypadku pojedynczego dowodu Merkle'a możemy zapisać całe 1024 słowa do pamięci masowej (zakładając, że można je od początku obliczyć onchain, a nie dostarczać w transakcji) i nadal pozostanie nam większość gazu.

Wnioski

W prawdziwym życiu prawdopodobnie nigdy nie będziesz samodzielnie implementować drzew Merklego. Istnieją dobrze znane i zbadane biblioteki, z których możesz skorzystać, i ogólnie rzecz biorąc, najlepiej nie implementować prymitywów kryptograficznych na własną rękę. Mam jednak nadzieję, że teraz lepiej rozumiesz dowody Merkle'a i potrafisz zdecydować, kiedy warto ich użyć.

Zauważ, że chociaż dowody Merkle'a zachowują integralność, nie zachowują dostępności. Świadomość, że nikt inny nie może przejąć Twoich aktywów, jest marnym pocieszeniem, jeśli magazyn danych zdecyduje się zablokować dostęp, a Ty również nie będziesz w stanie skonstruować drzewa Merklego, aby uzyskać do nich dostęp. Dlatego drzewa Merklego najlepiej sprawdzają się w połączeniu z jakimś rodzajem zdecentralizowanego przechowywania danych, takim jak IPFS.

Zobacz tutaj więcej moich prac (opens in a new tab).