Merkle-Beweise für Offline Datenintegrität

storage

Fortgeschritten

Ori Pomerantz

30. Dezember 2021

10 Minuten Lesedauer

Einführung

Idealerweise möchten wir alles in einem Ethereum Speicher ablegen, der auf Tausenden von Computern gespeichert ist und eine extrem hohe Verfügbarkeit (die Daten können nicht zensiert werden) und Integrität (die Daten können nicht unbefugt verändert werden) aufweist, aber die Speicherung eines 32-Byte-Wortes kostet normalerweise 20.000 Gas. Während ich das schreibe, entsprechen diese Kosten 6,60 USD. Mit 21 Cent pro Byte ist das für viele Anwendungen zu teuer.

Um dieses Problem zu lösen, hat das Ethereum-Ökosystem viele alternative Wege entwickelt, um Daten dezentral zu speichern. In der Regel muss dabei ein Kompromiss zwischen Verfügbarkeit und Preis eingegangen werden. Die Integrität ist jedoch in der Regel gewährleistet.

In diesem Artikel erfahren Sie, wie Sie die Datenintegrität gewährleisten, ohne die Daten auf der Blockchain zu speichern, indem Sie Merkle-Beweiseopens in a new tab verwenden.

Wie funktioniert das?

Theoretisch könnten wir einfach den Hash der Daten onchain speichern und alle Daten in Transaktionen senden, die sie benötigen. Allerdings ist das immer noch zu teuer. Ein Byte Daten zu einer Transaktion kostet etwa 16 Gas, derzeit etwa einen halben Cent, oder etwa 5 USD pro Kilobyte. Mit 5000 USD pro Megabyte ist dies für viele Anwendungen immer noch zu teuer, selbst ohne die zusätzlichen Kosten für das Hashing der Daten.

Die Lösung ist, verschiedene Teilmengen der Daten wiederholt zu hashen, so dass Sie für die Daten, die Sie nicht zu senden brauchen, nur einen Hash senden können. Dazu verwenden Sie einen Merkle Tree, eine Baum Datenstruktur, bei der jeder Knoten ein Hash der darunter liegenden Knoten ist:

Der Root-Hash ist der einzige Teil, der onchain gespeichert werden muss. Um einen bestimmten Wert zu beweisen, geben Sie alle Hashes an, die damit kombiniert werden müssen, um die Wurzel (Hash-Root) zu erhalten. Um zum Beispiel C zu beweisen, stellen Sie D, H(A-B) und H(E-H) zur Verfügung.

Implementierung

Der Beispielcode wird hier zur Verfügung gestelltopens in a new tab.

Offchain-Code

In diesem Artikel verwenden wir JavaScript für die Offchain-Berechnungen. Die meisten dezentralisierten Anwendungen haben ihre Offchain-Komponente in JavaScript.

Erstellen der Merkle-Root

Als erstes müssen wir die Merkle-Wurzel für die Chain bereitstellen.

1const ethers = require("ethers")

Wir verwenden die Hash-Funktion aus dem Ethers-Paketopens in a new tab.

1// Die Rohdaten, deren Integrität wir überprüfen müssen. Die ersten beiden Bytes
2// sind eine Benutzerkennung, und die letzten beiden Bytes sind die Menge der Tokens, die
3// der Benutzer derzeit besitzt.
4const dataArray = [
5  0x0bad0010, 0x60a70020, 0xbeef0030, 0xdead0040, 0xca110050, 0x0e660060,
6  0xface0070, 0xbad00080, 0x060d0091,
7]

Die Kodierung jedes Eintrags in eine einzelne 256-Bit-Integerzahl führt zu weniger lesbarem Code als z. B. die Verwendung von JSON. Allerdings bedeutet dies einen deutlich geringeren Verarbeitungsaufwand für die Abfrage der Vertragsdaten und damit deutlich niedrigere Gaskosten. Man kann JSON onchain lesenopens in a new tab, es ist nur eine schlechte Idee, wenn es vermeidbar ist.

1// Das Array der Hash-Werte als BigInts
2const hashArray = dataArray

In diesem Fall handelt es sich bei unseren Daten um 256 Bit-Werte, so dass keine Verarbeitung erforderlich ist. Wenn wir eine kompliziertere Datenstruktur verwenden, wie z. B. Strings, müssen wir sicherstellen, dass wir die Daten zuerst hashen, um ein Array von Hashes zu erhalten. Das liegt auch daran, weil es uns nicht interessiert, ob Benutzer die Informationen anderer Benutzer kennen. Andernfalls hätten wir einen Hash verwenden müssen, damit Benutzer 1 den Wert für Benutzer 0 nicht kennt, Benutzer 2 den Wert für Benutzer 3 nicht kennt usw.

1// Konvertieren zwischen dem String, den die Hash-Funktion erwartet, und dem
2// BigInt, das wir überall sonst verwenden.
3const hash = (x) =>
4  BigInt(ethers.utils.keccak256("0x" + x.toString(16).padStart(64, 0)))

Die Ethers-Hash-Funktion erwartet einen JavaScript-String mit einer hexadezimalen Zahl, wie z. B. 0x60A7, und gibt einen anderen String mit der gleichen Struktur zurück. Für den Rest des Codes ist es jedoch einfacher, BigInt zu verwenden, also konvertieren wir es in einen hexadezimalen String und wieder zurück.

1// Symmetrischer Hash eines Paares, sodass die umgekehrte Reihenfolge keine Rolle spielt.
2const pairHash = (a, b) => hash(hash(a) ^ hash(b))

Diese Funktion ist symmetrisch (Hash von a xoropens in a new tab b). Das bedeutet, dass wir uns bei der Überprüfung des Merkle-Beweises keine Gedanken darüber machen müssen, ob wir den Wert aus dem Beweis vor oder nach dem berechneten Wert setzen sollen. Die Überprüfung von Merkle-Beweisen wird onchain durchgeführt. Je weniger wir dort tun müssen, desto besser.

Warnung: Kryptographie ist schwieriger als es aussieht. Die ursprüngliche Version dieses Artikels hatte die Hash-Funktion hash(a^b). Das war eine schlechte Idee, denn es bedeutete, dass man, wenn man die legitimen Werte von a und b kannte, b' = a^b^a' verwenden konnte, um einen beliebigen a'-Wert zu beweisen. Mit dieser Funktion müsste man b' so berechnen, dass hash(a') ^ hash(b') gleich einem bekannten Wert ist (der nächste Zweig auf dem Weg zur Root), was viel schwieriger ist.

1// Der Wert, der anzeigt, dass ein bestimmter Zweig leer ist und keinen
2// Wert hat
3const empty = 0n

Wenn die Anzahl der Werte keine ganzzahlige Zweierpotenz ist, müssen wir leere Zweige behandeln. Bei diesem Programm wird die Null als Platzhalter eingesetzt.

1// Berechnet eine Ebene im Baum eines Hash-Arrays, indem der Hash
2// jedes Paares in der Sequenz genommen wird
3const oneLevelUp = (inputArray) => {
4  var result = []
5  var inp = [...inputArray] // Um das Überschreiben der Eingabe zu vermeiden // Fügt bei Bedarf einen leeren Wert hinzu (wir benötigen alle Blätter // als Paare)
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
Alles anzeigen

Diese Funktion "klettert" eine Ebene im Merkle-Baum hoch, indem sie die Wertepaare auf der aktuellen Ebene hasht. Beachten Sie, dass dies nicht die effizienteste Implementierung ist. Wir hätten das Kopieren der Eingabe vermeiden und einfach hashEmpty an der entsprechenden Stelle in der Schleife hinzufügen können, aber dieser Code ist auf Lesbarkeit optimiert.

1const getMerkleRoot = (inputArray) => {
2  var result
3
4  result = [...inputArray] // Klettere den Baum hinauf, bis es nur noch einen Wert gibt, das ist die // Root. // // Wenn eine Ebene eine ungerade Anzahl von Einträgen hat, fügt der // Code in oneLevelUp einen leeren Wert hinzu. Wenn wir also zum Beispiel // 10 Blätter haben, haben wir 5 Zweige in der zweiten Ebene, 3 // Zweige in der dritten, 2 in der vierten und die Root ist die fünfte
5
6  while (result.length > 1) result = oneLevelUp(result)
7
8  return result[0]
9}
Alles anzeigen

Um die Wurzel zu bekommen, mache so lange, bis nur noch ein Wert übrig ist.

Erstellen eines Merkle-Beweises

Ein Merkle-Beweis besteht aus den Werten, die zusammen mit dem zu beweisenden Wert gehasht werden müssen, um die Merkle-Wurzel zu erhalten. Der zu beweisende Wert ist oft aus anderen Daten verfügbar, daher ziehe ich es vor, ihn separat und nicht als Teil des Codes bereitzustellen.

1// Ein Merkle-Beweis besteht aus dem Wert der Liste der Einträge, mit denen
2// gehasht werden soll. Da wir eine symmetrische Hash-Funktion verwenden, benötigen wir
3// den Speicherort des Elements nicht, um den Beweis zu verifizieren, sondern nur, um ihn zu erstellen
4const getMerkleProof = (inputArray, n) => {
5    var result = [], currentLayer = [...inputArray], currentN = n
6
7    // Bis wir die Spitze erreichen
8    while (currentLayer.length > 1) {
9        // Keine Ebenen mit ungerader Länge
10        if (currentLayer.length % 2)
11            currentLayer.push(empty)
12
13        result.push(currentN % 2
14               // Wenn currentN ungerade ist, füge den Wert davor zum Beweis hinzu
15            ? currentLayer[currentN-1]
16               // Wenn es gerade ist, füge den Wert danach hinzu
17            : currentLayer[currentN+1])
18
Alles anzeigen

Wir hashen (v[0],v[1]), (v[2],v[3]) usw. Für gerade Werte benötigen wir also den nächsten, für ungerade Werte den vorherigen Wert.

1        // Auf die nächste Ebene aufsteigen
2        currentN = Math.floor(currentN/2)
3        currentLayer = oneLevelUp(currentLayer)
4    }   // while currentLayer.length > 1
5
6    return result
7}   // getMerkleProof

Onchain-Code

Schließlich haben wir den Code, der den Beweis überprüft. Der Onchain-Code ist in Solidityopens in a new tab geschrieben. Die Optimierung ist hier sehr viel wichtiger, weil Gas relativ teuer ist.

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

Ich habe dies mit der Hardhat-Entwicklungsumgebungopens in a new tab geschrieben, die es uns ermöglicht, während der Entwicklung Konsolenausgaben von Solidityopens in a new tab zu haben.

1
2contract MerkleProof {
3    uint merkleRoot;
4
5    function getRoot() public view returns (uint) {
6      return merkleRoot;
7    }
8
9    // Äußerst unsicher, im Produktionscode muss der Zugriff auf
10    // diese Funktion STRENG limitiert sein, wahrscheinlich auf einen
11    // Besitzer
12    function setRoot(uint _merkleRoot) external {
13      merkleRoot = _merkleRoot;
14    }   // setRoot
Alles anzeigen

Set- und Get-Funktionen für die Merkle-Wurzel. Jeden die Merkle-Root aktualisieren zu lassen, ist eine extrem schlechte Idee in einem Produktionssystem. Ich tue es hier der Einfachheit halber für den Beispielcode. Tun Sie das nicht auf einem System, bei dem die Datenintegrität wirklich wichtig ist.

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    }

Diese Funktion erzeugt einen Paar-Hash. Es ist nur die Solidity-Übersetzung des JavaScript-Codes für hash und pairHash.

Hinweis: Dies ist ein weiterer Fall der Optimierung auf Lesbarkeit. Basierend auf der Funktionsdefinitionopens in a new tab wäre es möglich, die Daten als bytes32opens in a new tab-Wert zu speichern und die Konvertierungen zu vermeiden.

1    // Überprüfen eines Merkle-Beweises
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
Alles anzeigen

In mathematischer Notation sieht die Verifizierung eines Merkle-Beweises so aus: H(proof_n, H(proof_n-1, H(proof_n-2, ... H(proof_1, H(proof_0, value))...)))`. Dieser Code implementiert sie.

Merkle-Beweise und Rollups vertragen sich nicht

Merkle-Beweise funktionieren nicht gut mit Rollups. Der Grund dafür ist, dass Rollups alle Transaktionsdaten auf L1 schreiben, aber auf L2 verarbeiten. Die Kosten für die Übermittlung eines Merkle-Beweises mit einer Transaktion belaufen sich auf durchschnittlich 638 Gas pro Ebene (derzeit kostet ein Byte in Call Data 16 Gas, wenn es nicht Null ist, und 4, wenn es Null ist). Bei einer Datenmenge von 1024 Wörtern sind für einen Merkle-Beweis zehn Ebenen erforderlich, also insgesamt 6380 Gas.

Wenn man sich zum Beispiel Optimismopens in a new tab ansieht, kostet das Schreiben von L1-Gas etwa 100 Gwei und L2-Gas 0,001 Gwei (das ist der normale Preis, er kann bei Überlastung steigen). Für die Kosten von einem L1 Gas können wir also hunderttausend Gas für die L2 Verarbeitung ausgeben. Wenn wir davon ausgehen, dass wir den Speicher nicht überschreiben, bedeutet das, dass wir für den Preis von einem L1 Gas etwa fünf Wörter in den L2 Speicher schreiben können. Für einen einzelnen Merkle-Beweis können wir die gesamten 1024 Wörter in den Speicher schreiben (vorausgesetzt, sie können von Anfang an onchain berechnet werden, anstatt in einer Transaktion bereitgestellt zu werden) und haben immer noch den größten Teil des Gases übrig.

Fazit

Im echten Leben werden Sie Merkle-Bäume vielleicht nie selbst implementieren. Es gibt bekannte und geprüfte Bibliotheken, die Sie verwenden können, wobei es im Allgemeinen nicht ratsam ist, kryptographische Primitive selbst zu implementieren. Aber ich hoffe, dass Sie jetzt die Merkle-Beweise besser verstehen und entscheiden können, wann es sich lohnt, sie einzusetzen.

Beachten Sie, dass Merkle-Beweise zwar die Integrität, nicht aber die Verfügbarkeit erhalten. Zu wissen, dass niemand sonst Ihre Assets nehmen kann, ist ein schwacher Trost, wenn der Datenspeicher beschließt, den Zugriff zu verweigern, und Sie auch keinen Merkle-Baum erstellen können, um darauf zuzugreifen. Merkle-Bäume werden daher am besten mit einer Art dezentralem Speicher wie IPFS verwendet.

Hier finden Sie mehr von meiner Arbeitopens in a new tab.

Seite zuletzt aktualisiert: 18. Dezember 2025