Merkleho důkazy pro integritu dat mimo blockchain

Úvod

V ideálním případě bychom chtěli vše ukládat do úložiště Etherea, které je uloženo na tisících počítačů a má extrémně vysokou dostupnost (data nelze cenzurovat) a integritu (data nelze neoprávněně upravovat), ale uložení 32bajtového slova obvykle stojí 20 000 gas. V době psaní tohoto článku se tato cena rovná 6,60 USD. Při 21 centech za bajt je to pro mnoho využití příliš drahé.

K vyřešení tohoto problému vyvinul ekosystém Etherea mnoho alternativních způsobů, jak ukládat data decentralizovaným způsobem. Obvykle zahrnují kompromis mezi dostupností a cenou. Integrita je však obvykle zajištěna.

V tomto článku se dozvíte, jak zajistit integritu dat bez jejich ukládání na blockchain pomocí Merkleho důkazůopens in a new tab.

Jak to funguje?

Teoreticky bychom mohli pouze uložit haš dat na blockchainu a odeslat všechna data v transakcích, které je vyžadují. To je však stále příliš drahé. Jeden bajt dat v transakci stojí asi 16 gas, což je v současnosti asi půl centu, neboli asi 5 USD za kilobajt. Při ceně 5 000 USD za megabajt je to pro mnoho použití stále příliš drahé, a to i bez dodatečných nákladů na hašování dat.

Řešením je opakovaně hašovat různé podmnožiny dat, takže pro data, která nemusíte odesílat, můžete odeslat pouze haš. To se provádí pomocí Merkleho stromu, stromové datové struktury, kde každý uzel je hašem uzlů pod ním:

Kořenový haš je jedinou částí, která musí být uložena na blockchainu. K prokázání určité hodnoty poskytnete všechny haše, které je třeba s ní zkombinovat, abyste získali kořen. Například k prokázání C poskytnete D, H(A-B) a H(E-H).

Implementace

Ukázkový kód je k dispozici zdeopens in a new tab.

Kód mimo blockchain

V tomto článku používáme pro výpočty mimo blockchain JavaScript. Většina decentralizovaných aplikací má svou komponentu mimo blockchain v JavaScriptu.

Vytvoření Merkleho kořene

Nejprve musíme poskytnout Merkleho kořen do řetězce.

1const ethers = require("ethers")

Používáme hašovací funkci z balíčku ethersopens in a new tab.

1// Hrubá data, jejichž integritu musíme ověřit. První dva bajty
2// jsou identifikátor uživatele a poslední dva bajty jsou množství tokenů, které
3// uživatel v současnosti vlastní.
4const dataArray = [
5  0x0bad0010, 0x60a70020, 0xbeef0030, 0xdead0040, 0xca110050, 0x0e660060,
6  0xface0070, 0xbad00080, 0x060d0091,
7]

Kódování každé položky do jediného 256bitového celého čísla vede k méně čitelnému kódu než například použití JSON. To však znamená výrazně menší zpracování pro načtení dat ve smart kontraktu, tedy mnohem nižší náklady na gas. Můžete číst JSON na blockchainuopens in a new tab, ale je to špatný nápad, pokud je to možné se mu vyhnout.

1// Pole hašovacích hodnot jako BigInts
2const hashArray = dataArray

V tomto případě jsou naše data na začátku 256bitové hodnoty, takže není nutné žádné zpracování. Pokud použijeme složitější datovou strukturu, například řetězce, musíme se ujistit, že data nejprve hašujeme, abychom získali pole hašů. Všimněte si, že je to také proto, že nám nevadí, když uživatelé znají informace ostatních uživatelů. Jinak bychom museli hašovat, aby uživatel 1 neznal hodnotu pro uživatele 0, uživatel 2 neznal hodnotu pro uživatele 3 atd.

1// Převod mezi řetězcem, který očekává hašovací funkce, a
2// BigInt, který používáme všude jinde.
3const hash = (x) =>
4  BigInt(ethers.utils.keccak256("0x" + x.toString(16).padStart(64, 0)))

Hašovací funkce ethers očekává, že dostane řetězec JavaScriptu s hexadecimálním číslem, například 0x60A7, a odpoví jiným řetězcem se stejnou strukturou. Pro zbytek kódu je však snazší použít BigInt, takže převádíme na hexadecimální řetězec a zase zpět.

1// Symetrický haš páru, takže nám nebude vadit, pokud bude pořadí obrácené.
2const pairHash = (a, b) => hash(hash(a) ^ hash(b))

Tato funkce je symetrická (haš a xoropens in a new tab b). To znamená, že při kontrole Merkleho důkazu se nemusíme starat o to, zda hodnotu z důkazu umístit před nebo za vypočtenou hodnotu. Kontrola Merkleho důkazu se provádí na blockchainu, takže čím méně toho tam musíme dělat, tím lépe.

Upozornění: Kryptografie je složitější, než se zdá. Původní verze tohoto článku měla hašovací funkci hash(a^b). To byl špatný nápad, protože to znamenalo, že pokud jste znali legitimní hodnoty a a b, mohli jste použít b' = a^b^a' k prokázání jakékoli požadované hodnoty a'. S touto funkcí byste museli vypočítat b' tak, aby haš(a') ^ haš(b') byl roven známé hodnotě (další větev na cestě ke kořeni), což je mnohem těžší.

1// Hodnota pro označení, že určitá větev je prázdná, nemá
2// žádnou hodnotu
3const empty = 0n

Když počet hodnot není celočíselnou mocninou dvou, musíme řešit prázdné větve. Tento program to řeší tak, že jako zástupný symbol vloží nulu.

1// Vypočítá o jednu úroveň výše strom hašovacího pole tím, že vezme haš
2// každého páru v pořadí.
3const oneLevelUp = (inputArray) => {
4  var result = []
5  var inp = [...inputArray] // Aby se zabránilo přepsání vstupních dat // V případě potřeby přidejte prázdnou hodnotu (potřebujeme, aby všechny listy byly spárovány)
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
Zobrazit vše

Tato funkce „vystoupá“ o jednu úroveň v Merkleho stromu hašováním párů hodnot na aktuální vrstvě. Všimněte si, že se nejedná o nejefektivnější implementaci, mohli jsme se vyhnout kopírování vstupu a pouze přidat hashEmpty v příslušném místě cyklu, ale tento kód je optimalizován pro čitelnost.

1const getMerkleRoot = (inputArray) => {
2  var result
3
4  result = [...inputArray] // Stoupejte stromem, dokud nezbude jen jedna hodnota, což je // kořen. // // Pokud má vrstva lichý počet položek, // kód v oneLevelUp přidá prázdnou hodnotu, takže pokud máme například // 10 listů, budeme mít 5 větví ve druhé vrstvě, 3 // větve ve třetí, 2 ve čtvrté a kořen je pátý
5
6  while (result.length > 1) result = oneLevelUp(result)
7
8  return result[0]
9}
Zobrazit vše

Chcete-li získat kořen, stoupejte, dokud nezbude pouze jedna hodnota.

Vytvoření Merkleho důkazu

Merkleho důkaz jsou hodnoty, které se mají hašovat spolu s prokazovanou hodnotou, aby se vrátil Merkleho kořen. Hodnota, která se má prokázat, je často k dispozici z jiných dat, takže ji raději poskytuji samostatně než jako součást kódu.

1// Merkleho důkaz se skládá z hodnoty seznamu položek, se kterými
2// se má hašovat. Protože používáme symetrickou hašovací funkci, nepotřebujeme
3// polohu položky k ověření důkazu, pouze k jeho vytvoření.
4const getMerkleProof = (inputArray, n) => {
5    var result = [], currentLayer = [...inputArray], currentN = n
6
7    // Dokud nedosáhneme vrcholu
8    while (currentLayer.length > 1) {
9        // Žádné vrstvy s lichou délkou
10        if (currentLayer.length % 2)
11            currentLayer.push(empty)
12
13        result.push(currentN % 2
14               // Pokud je currentN liché, přidejte k důkazu hodnotu před ním
15            ? currentLayer[currentN-1]
16               // Pokud je sudé, přidejte hodnotu za ním
17            : currentLayer[currentN+1])
18
Zobrazit vše

Hašujeme (v[0],v[1]), (v[2],v[3]) atd. Takže pro sudé hodnoty potřebujeme následující, pro liché hodnoty předchozí.

1        // Přesun na další vyšší vrstvu
2        currentN = Math.floor(currentN/2)
3        currentLayer = oneLevelUp(currentLayer)
4    }   // while currentLayer.length > 1
5
6    return result
7}   // getMerkleProof

Kód na blockchainu

Nakonec máme kód, který kontroluje důkaz. Kód na blockchainu je napsán v jazyce Solidityopens in a new tab. Optimalizace je zde mnohem důležitější, protože gas je relativně drahý.

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

Napsal jsem to pomocí vývojového prostředí Hardhatopens in a new tab, které nám umožňuje mít výstup z konzole ze Solidityopens in a new tab během vývoje.

1
2contract MerkleProof {
3    uint merkleRoot;
4
5    function getRoot() public view returns (uint) {
6      return merkleRoot;
7    }
8
9    // Extrémně nezabezpečené, v produkčním kódu MUSÍ BÝT přístup k
10    // této funkci přísně omezen, pravděpodobně pouze na
11    // vlastníka
12    function setRoot(uint _merkleRoot) external {
13      merkleRoot = _merkleRoot;
14    }   // setRoot
Zobrazit vše
Kopírovat

Funkce Set a get pro Merkleho kořen. Povolit každému aktualizovat Merkleho kořen je v produkčním systému extrémně špatný nápad. Dělám to zde pro zjednodušení ukázkového kódu. Nedělejte to v systému, kde na integritě dat skutečně záleží.

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    }
Kopírovat

Tato funkce generuje párový haš. Je to jen překlad JavaScriptového kódu pro hash a pairHash do jazyka Solidity.

Poznámka: Toto je další případ optimalizace pro čitelnost. Na základě definice funkceopens in a new tab by bylo možné ukládat data jako hodnotu bytes32opens in a new tab a vyhnout se převodům.

1    // Ověřit Merkleho důkaz
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
Zobrazit vše
Kopírovat

V matematické notaci vypadá ověření Merkleho důkazu takto: H(proof_n, H(proof_n-1, H(proof_n-2, ... H(proof_1, H(proof_0, value))...)))`. Tento kód to implementuje.

Merkleho důkazy a rollupy se nemíchají

Merkleho důkazy nefungují dobře s rollupy. Důvodem je, že rollupy zapisují všechna transakční data na L1, ale zpracovávají je na L2. Náklady na odeslání Merkleho důkazu s transakcí činí v průměru 638 gas za vrstvu (v současnosti stojí bajt v datech volání 16 gas, pokud není nulový, a 4, pokud je nulový). Pokud máme 1024 slov dat, Merkleho důkaz vyžaduje deset vrstev, neboli celkem 6380 gas.

Když se podíváme například na Optimismopens in a new tab, zápis gas na L1 stojí asi 100 gwei a gas na L2 stojí 0,001 gwei (to je normální cena, při přetížení se může zvýšit). Takže za cenu jednoho L1 gas můžeme utratit sto tisíc gas za zpracování na L2. Za předpokladu, že nepřepisujeme úložiště, znamená to, že za cenu jednoho L1 gas můžeme na L2 zapsat do úložiště asi pět slov. Pro jediný Merkleho důkaz můžeme zapsat celých 1024 slov do úložiště (za předpokladu, že mohou být vypočtena na blockchainu, nikoli poskytnuta v transakci) a stále nám zbude většina gas.

Závěr

V reálném životě možná nikdy nebudete sami implementovat Merkleho stromy. Existují známé a auditované knihovny, které můžete použít, a obecně platí, že je nejlepší neimplementovat kryptografické primitivy sami. Ale doufám, že nyní lépe rozumíte Merkleho důkazům a můžete se rozhodnout, kdy se vyplatí je použít.

Všimněte si, že zatímco Merkleho důkazy zachovávají integritu, nezachovávají dostupnost. Vědět, že nikdo jiný nemůže vzít vaše aktiva, je malou útěchou, pokud se úložiště dat rozhodne zakázat přístup a vy nemůžete sestavit Merkleho strom, abyste k nim měli přístup. Merkleho stromy se tedy nejlépe používají s nějakým druhem decentralizovaného úložiště, jako je IPFS.

Více z mé práce najdete zdeopens in a new tab.