So implementieren Sie einen Merkle Tree in Solidity

Ein Merkle-Baum ist ein Binärbaum, der es ermöglicht, den Inhalt großer Datenstrukturen effizient und sicher zu überprüfen. Das Konzept dieses Baums wurde 1982 von Ralph Merkle, einem amerikanischen Kryptographen, vorgeschlagen und patentiert.

Die Länge des Hash bleibt für jede Menge Eingabedaten gleich. Blattscheitelpunkte enthalten Hashes aus Datenblöcken, während innere Scheitelpunkte Hashes aus der Addition von Werten in zwei untergeordneten Scheitelpunkten enthalten. Der Root-Vertex wiederum umfasst den Hash des gesamten Datensatzes.

Theorie

Zunächst handelt es sich um einen Datensatz, der in keiner Beziehung zueinander steht. Für jeden Datenblock (im Kontext einer Transaktionsblockchain) müssen wir einen Hash des Blocks berechnen. Die Anzahl der Datenblöcke sollte 2^N betragen, da beim Aufbau des Baums die vorherigen Blöcke bei jeder Iteration paarweise gehasht werden. Anschließend wird ein Hash-Paar gruppiert und darauf basierend ein neuer Hash erstellt. Das Hashing wird so lange fortgesetzt, wie auf jeder Ebene etwas zu gruppieren ist, und es wird gestoppt, wenn nur noch ein Paar übrig ist, von dem der Root-Hash – die Merkle-Wurzel – erhalten wird.

H(1-2) = keccak256(H(1) + H(2))

H(3-4) = keccak256(H(3) + H(4))

H(5-6) = keccak256(H(5) + H(6))

H(7-8) = keccak256(H(7) + H(8))

H(1-2-3-4) = keccak256(H(1-2) + H(3-4))

H(5-6-7-8) = keccak256(H(5-6) + H(7-8))

H(1-2-3-4-5-6-7-8) = keccak256(H(1-2-3-4) + H(5-6-7-8))

Sobald wir die Wurzel haben, können wir die Daten validieren. Wenn der Root-Hash mit dem Original-Hash übereinstimmt, ist alles in Ordnung, die Daten sind gültig. Außerdem ist es möglich, effizient zu prüfen, ob bestimmte Daten in der Baumstruktur vorhanden sind.

Nehmen wir an, wir möchten überprüfen, ob der H2 Hash im Baum vorhanden ist. Der Beweis wird ein Array von Daten sein: H1 , H3-4 , H5-6-7-8 . Dank dieser Hashes können wir den Root-Hash rekonstruieren:

H(1-2-3-4-5-6-7-8) = keccak256(keccak256(keccak256(H(1) + H(2)) + H(3-4)) + H(5-6-7-8))

Dann vergleichen wir den resultierenden Hash mit dem Original. Wenn sie übereinstimmen, bedeutet dies, dass der Hash H2 im Baum vorhanden ist.

Üben

Sehen wir uns nun an, wie man einen Merkle-Baum und eine Datenvalidierung in Solidity implementiert.

Der Einfachheit halber schreiben wir das Array der Transaktionen sowie das Array der Hashes direkt in die Blockchain. Da wir die integrierte Funktion keccak256 verwenden, die einen Hash von 32 Bytes zurückgibt, ist der Datentyp des Hashes-Arrays bytes32 . Das Array wird auch eine dynamische Länge haben. Im Allgemeinen entspricht die Länge des Hashes-Arrays nicht der Länge des Transaktions-Arrays, da es die erzeugten Hashes enthält. Wir könnten die Länge im Voraus berechnen, tun dies aber aus Gründen der Code-Vereinfachung nicht. Wenn Sie möchten, können Sie jedes dieser Arrays public machen und die Hashes der Transaktionen lesen.

Wir werden im Konstruktor hashes erzeugen. Der erste Schritt besteht darin, die Hashes für Blöcke mit transactions in der Schleife zu zählen. Dann wird auf jeder Ebene des Baums die Anzahl der Hashes um den Faktor 2 reduziert. Da wir die Hashes im Hashes-Array speichern, müssen die Index-Offsets separat gespeichert werden. Der Iterator in der inneren Schleife wird um 2 erhöht, da wir beim Berechnen und Hinzufügen von Hashes einige Elemente verwenden. In abi.encodePacked fügen wir dieses Mal jeweils 2 Hashes hinzu, denen wir die Indizes korrekt setzen: für das linke Element – den Wert des aktuellen Verschiebungsoffsets + den Index auf der aktuellen Baumebene, und für das rechte Element – dasselbe + 1.

Wir haben also den Baum erstellt, aber das Interesse besteht in der Validierung der Daten. Dazu schreiben wir eine validateTransaction -Funktion, die eine Transaktion und ihren Index entgegennimmt. Leider verfügt Solidity nicht über eine find für Arrays, daher ist es einfacher, einfach den Transaktionsindex zu übergeben.

Berechnen wir zunächst den Hash der Transaktion und erstellen eine Reihe von Beweisen. Wir ermitteln die Anzahl der Beweise in Abhängigkeit von der Länge des Transaktionsarrays und legen die Länge von proofsIndexes fest. Danach finden wir auf jeder Ebene des Baums das erforderliche Element, je nach Index, wobei wir das rechte oder linke Element nehmen und dabei die Offsets in den hashes berücksichtigen. Dann gehen wir das Array der Beweisindizes durch, überprüfen den Index auf Parität und berechnen den Hash abhängig davon, ob das Element links oder rechts im Paar steht. Abschließend vergleichen wir den resultierenden Hash mit dem Root-Hash und geben das Ergebnis zurück.

Anwendung

Es gibt mehrere Anwendungen eines Merkle-Baums in der Blockchain.

• Transaktionsspeicherung : Bei Bitcoin beispielsweise speichert ein Transaktionsblock nur die merkle_root seiner Transaktionen. Dies reduziert die Größe des Blocks und die Belastung des Netzwerks. Nach der Ansammlung einer bestimmten Anzahl von Transaktionen ist es möglich, alte Transaktionen zu löschen, um Platz zu sparen. Die Blöcke selbst bleiben jedoch unverändert, da sie nur die Wurzel des Baums speichern.
• Mining : Ein Bitcoin-Block besteht aus zwei Teilen – dem Blockheader und der Liste der Transaktionen. Um zu vermeiden, dass die Transaktions-Hashes jedes Mal neu berechnet werden müssen, werden sie in einem Merkle-Baum angeordnet. Anschließend wird der Block-Header und nicht der gesamte Block gehasht und eine zufällige Nonce-Nummer verwendet. Wenn der Block an andere Knoten gesendet wird, wird die Wurzel der Transaktionsliste berechnet. Wenn sie nicht mit der Wurzel im Header übereinstimmt, wird der Block abgelehnt.
• Verifizierung : Das Wesentliche der Verifizierung ist die Prüfung, ohne dass die gesamte Blockchain heruntergeladen werden muss. Der Prozess wird erheblich vereinfacht und ermöglicht auch die Bestätigung der Existenz von Daten, ohne Informationen über die Daten preiszugeben, was für die Überprüfung sensibler Informationen nützlich sein kann.

Zusammenfassung

Ohne Merkle-Bäume wären Blockchains zu umständlich und Merkle-Proofs ermöglichen eine kostengünstige Überprüfung der Datenauthentizität.

Merkle-Bäume werden aktiv in Blockchains (z. B. Bitcoin, Ethereum) verwendet, um Transaktionen effizient zu speichern, aber dies ist nicht die einzige Anwendung. Beispielsweise führten viele Börsen nach dem Zusammenbruch der FTX-Börse einen Proof-of-Reserve-Mechanismus ein, der einen Merkle-Baum nutzt.