Dovezile Merkle pentru integritatea datelor off-line

Introducere

Ideal ar fi să stocăm totul în memoria Ethereum, stocată pe mii de computere, cu o mare accesibilitate (adică datele nu pot fi cenzurate) și integritate (adică datele nu pot fi modificate într-un mod neautorizat), dar stocarea unui cuvânt de 32 de octeți costă de obicei 20.000 de gaz. Acum, când scriu aceste rânduri, acest cost este echivalentul a 6,60 dolari. La 21 de cenți pe octet, acest preț este prea mare pentru mulți utilizatori.

To solve this problem the Ethereum ecosystem developed many alternative ways to store data in a decentralized fashion. Acestea implică de obicei un compromis între disponibilitate și preț. Cu toate acestea, este asigurată de obicei integritatea.

În acest articol veți învăța cum să asigurați integritatea datelor fără a stoca datele pe blockchain, folosind dovezile Merkle(opens in a new tab).

Cum funcționează?

În teorie, am putea stoca hash-ul datelor pe lanț și trimite toate datele în tranzacțiile care le solicită. Totuși, și acest lucru rămâne prea scump. Un octet de date la o tranzacție costă aproape 16 gaz, actualmente cam jumătate de cent, sau circa 5 dolari pe kilooctet. La 5.000 de dolari pe megaoctet, acest lucru este tot prea scump pentru mulți utilizatori, chiar și fără costul suplimentar al hashing-ului de date.

Soluția este de a genera în mod repetat hash-uri pentru diferite subseturi de date, deci pentru datele pe care nu este nevoie să le trimiteți, puteți trimite doar hash-ul lor. Aceasta se poate face utilizând un arbore Merkle, o structură de date arborescentă în care fiecare nod este hash-ul nodurilor de sub el:

Hash-ul rădăcină este singura parte care trebuie să fie stocată în lanț. Pentru a dovedi o anumită valoare, furnizați toate hash-urile care trebuie combinate cu aceasta pentru a obține rădăcina. De exemplu, pentru a dovedi C furnizați D, H(A-B) și H(E-H).

Implementarea

Exemplul de cod este furnizat aici(opens in a new tab).

Codul off-chain

În acest articol folosim JavaScript pentru calculele off-chain. Majoritatea aplicațiilor descentralizate îşi au componenta off-chain în JavaScript.

Crearea rădăcinii Merkle

Mai întâi trebuie să furnizăm rădăcina Merkle lanțului.

1const ethers = require("ethers")

Vom utiliza funcția hash din pachetul ethers(opens in a new tab).

1// The raw data whose integrity we have to verify. The first two bytes a
2// are a user identifier, and the last two bytes the amount of tokens the
3// user owns at present.
4const dataArray = [
5  0x0bad0010, 0x60a70020, 0xbeef0030, 0xdead0040, 0xca110050, 0x0e660060,
6  0xface0070, 0xbad00080, 0x060d0091,
7]

Codificarea fiecărui set de date introduse într-o valoare întreagă de 256 de biți conduce la un cod mai puțin lizibil decât utilizând JSON, de exemplu. Dar aceasta înseamnă semnificativ mai puține procesări pentru preluarea datelor din contract, deci costuri de gaz mai mici. Puteți citi JSON on chain(opens in a new tab), însă nu este o idee bună, evitați-o dacă se poate.

1// The array of hash values, as BigInts
2const hashArray = dataArray

În acest caz, datele noastre inițiale sunt constituite de valori pe 256 de biți, deci nu este nevoie de nicio procesare. Dar dacă folosim o structură de date mai complexă, cum ar fi șirurile de caractere, trebuie să generăm mai întâi hash-ul datelor pentru a obține o matrice de hash-uri. Rețineți că lucrul acesta se datorează și faptului că nu ne pasă dacă utilizatorii cunosc informațiile altor utilizatori. Altfel, ar trebui să generăm un hash astfel încât utilizatorul 1 să nu cunoască valoarea utilizatorului 0, utilizatorul 2 să nu cunoască valoarea utilizatorului 3 etc.

1const pairHash = (a, b) =>
2  BigInt(ethers.utils.keccak256("0x" + (a ^ b).toString(16).padStart(64, 0)))

Funcția hash a pachetului ethers așteaptă să primească un șir JavaScript cu un număr hexazecimal, cum ar fi 0x60A7, și răspunde cu un alt șir cu aceeași structură. Totuși, pentru restul codului este mai ușor să folosim BigInt, așa că facem conversia la un șir hexazecimal și înapoi.

Această funcție este simetrică (hash de a xor(opens in a new tab) b). Prin urmare, atunci când verificăm dovada Merkle, nu este nevoie să ne preocupăm dacă valoarea din dovadă trebuie pusă înainte sau după valoarea calculată. Verificarea dovezii Merkle se face în lanț, de aceea, cu cât avem treabă mai puţin acolo, cu atât mai bine.

1// The value to denote that a certain branch is empty, doesn't
2// have a value
3const empty = 0n

Când numărul de valori nu este o putere întreagă a lui doi, trebuie să ne ocupăm de ramurile goale. Modul în care o face programul este de a pune zero ca substituent.

1// Calculate one level up the tree of a hash array by taking the hash of
2// each pair in sequence
3const oneLevelUp = (inputArray) => {
4  var result = []
5  var inp = [...inputArray] // To avoid over writing the input
6
7  // Add an empty value if necessary (we need all the leaves to be
8  // paired)
9  if (inp.length % 2 === 1) inp.push(empty)
10
11  for (var i = 0; i < inp.length; i += 2)
12    result.push(pairHash(inp[i], inp[i + 1]))
13
14  return result
15} // oneLevelUp
Afișează tot

Această funcție „urcă” un nivel în arborele Merkle prin hash-ul perechilor de valori de la nivelul curent. Trebuie remarcat că nu este cea mai eficientă implementare, am fi putut evita să copiem intrarea și doar să adăugăm hashEmpty în buclă atunci când era cazul, dar acest cod este optimizat pentru lizibilitate.

1const getMerkleRoot = (inputArray) => {
2  var result
3
4  result = [...inputArray]
5
6  // Climb up the tree until there is only one value, that is the
7  // root.
8  //
9  // If a layer has an odd number of entries the
10  // code in oneLevelUp adds an empty value, so if we have, for example,
11  // 10 leaves we'll have 5 branches in the second layer, 3
12  // branches in the third, 2 in the fourth and the root is the fifth
13  while (result.length > 1) result = oneLevelUp(result)
14
15  return result[0]
16}
Afișează tot

Pentru a obține rădăcina, urcați până când rămâne doar o singură valoare.

Crearea unei dovezi Merkle

O dovadă Merkle reprezintă valorile de la care împreună se va genera un hash și valoarea care trebuie dovedită pentru a obține înapoi rădăcina Merkle. Valoarea de dovedit este adesea disponibilă din alte date, așa că prefer să o furnizez separat decât făcând parte din cod.

1// A merkle proof consists of the value of the list of entries to
2// hash with. Because we use a symmetrical hash function, we don't
3// need the item's location to verify the proof, only to create it
4const getMerkleProof = (inputArray, n) => {
5    var result = [], currentLayer = [...inputArray], currentN = n
6
7    // Until we reach the top
8    while (currentLayer.length > 1) {
9        // No odd length layers
10        if (currentLayer.length % 2)
11            currentLayer.push(empty)
12
13        result.push(currentN % 2
14               // If currentN is odd, add with the value before it to the proof
15            ? currentLayer[currentN-1]
16               // If it is even, add the value after it
17            : currentLayer[currentN+1])
18
Afișează tot

Obținem hash-ul valorilor (v[0],v[1]), `(v[2],v[3]) etc. Deci, pentru valorile pare avem nevoie de următoarea, iar pentru valorile impare de cea anterioară.

1        // Move to the next layer up
2        currentN = Math.floor(currentN/2)
3        currentLayer = oneLevelUp(currentLayer)
4    }   // while currentLayer.length > 1
5
6    return result
7}   // getMerkleProof

Codul on-chain

În sfârșit, avem codul care verifică dovada. Codul on-chain este scris în Solidity(opens in a new tab). Optimizarea este mult mai importantă aici, deoarece gazul este relativ scump.

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

Am scris codul folosind mediul de dezvoltare Hardhat(opens in a new tab), care ne permite să avem o ieșire de consolă din Solidity(opens in a new tab) în timp ce dezvoltăm.

1
2contract MerkleProof {
3    uint merkleRoot;
4
5    function getRoot() public view returns (uint) {
6      return merkleRoot;
7    }
8
9    // Extremely insecure, in production code access to
10    // this function MUST BE strictly limited, probably to an
11    // owner
12    function setRoot(uint _merkleRoot) external {
13      merkleRoot = _merkleRoot;
14    }   // setRoot
Afișează tot
 Copiați

Funcțiile „set” și „get” pentru rădăcina Merkle. Letting everybody update the Merkle root is an extremely bad idea in a production system. Am făcut-o aici de dragul simplității, pentru a da doar un exemplu de cod. Nu trebuie să o faceți într-un sistem în care integritatea datelor contează cu adevărat.

1    function pairHash(uint _a, uint _b) internal pure returns(uint) {
2      return uint(keccak256(abi.encode(_a ^ _b)));
3    }
 Copiați

Această funcție generează o pereche de hash-uri. Este doar traducerea în Solidity a codului JavaScript pentru pairHash.

Observaţie: Acesta este un alt caz de optimizare pentru lizibilitate. În baza definiției funcției(opens in a new tab), ar fi posibilă stocarea datelor ca o valoare bytes32(opens in a new tab) și evitarea conversiilor.

1    // Verify a Merkle proof
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
Afișează tot
 Copiați

În limbaj matematic, verificarea dovezilor Merkle arată astfel: H(proof_n, H(proof_n-1, H(proof_n-2, ... H(proof_1, H(proof_0, value))...))). Acest cod îl pune în aplicare.

Dovezile Merkle și rollup-urile nu se potrivesc

Merkle proofs don't work well with rollups. Motivul este că rollup-urile scriu toate datele tranzacției pe L1, dar le procesează pe L2. Prețul trimiterii unei dovezi Merkle cu o tranzacție este în medie de 638 de gaz pe nivel (în prezent, un octet în datele de apel costă 16 gaz dacă nu este zero și 4 dacă este zero). Presupunând că avem 1024 de cuvinte de date, o dovadă Merkle necesită zece niveluri, adică un total de 6380 de gaz.

Privind, de exemplu, la Optimism(opens in a new tab), scrierea gazului L1 costă în jur de 100 gwei, iar gazul L2 costă 0,001 gwei (acesta este prețul normal și poate crește odată cu congestia). Așadar, pentru costul unui gaz L1 putem cheltui o sută de mii de gaz pentru procesarea L2. Considerând că nu suprascriem stocarea, putem scrie aproximativ cinci cuvinte în L2 pentru prețul unui gaz L1. Pentru o singură dovadă Merkle, putem scrie toate cele 1024 de cuvinte în memorie (presupunând că acestea pot fi calculate în lanț pentru început, și nu furnizate într-o tranzacție) și ne rămâne încă cea mai mare parte din gaz.

Concluzie

În lumea reală, probabil că nu veți implementa niciodată arbori Merkle pe cont propriu. Pot fi folosite biblioteci binecunoscute și auditate și este în general preferabil să nu implementați primitive criptografice pe cont propriu. Acum sper că înțelegeți mai bine dovezile Merkle și puteți decide când merită să fie folosite.

Note that while Merkle proofs preserve integrity, they do not preserve availability. Știind că nimeni nu vă poate lua bunurile vă consolează prea puţin dacă depozitul de date decide să interzică accesul la ele și nici nu puteți construi un arbore Merkle pentru a le accesa. De aceea, arborii Merkle sunt cel mai bine utilizați cu un fel de stocare descentralizată, precum IPFS.