Merkle-Bäume: Transaktionsintegrität im großen Maßstab

Ein Bitcoin-Block enthält etwa 2000 Transaktionen. Um nachzuweisen, dass die Transaktion T enthalten ist, ohne alle 2000 Transaktionen herunterzuladen, benötigen wir einen kompakten Beweis. Merkle-Bäume lösen dieses Problem: Die Beweisgröße beträgt O(log n) Hashes statt O(n) Transaktionen.

Blätter: SHA256d (doppeltes SHA-256) jeder Transaktion. Elternknoten: SHA256d(left_child_hash || right_child_hash). Wiederholen Sie dies, bis nur noch eine Root übrig ist. Bei einer ungeraden Anzahl von Knoten wird der letzte Knoten dupliziert. Die Root ist die im Blockheader gespeicherte Merkle-Root (32 Byte).

import hashlib def sha256d(x): return hashlib.sha256(hashlib.sha256(x).digest()).digest() def merkle_root(txids): if len(txids)%2: txids.append(txids[-1]) while len(txids)>1: txids=[sha256d(txids[i]+txids[i+1]) for i in range(0,len(txids),2)] return txids[0].hex()

Um zu beweisen, dass sich die Transaktion T an Position i befindet: Geben Sie die Hashes der Geschwisterknoten auf jeder Ebene vom Blatt von T bis zur Root an (O(log n) Hashes). Der Verifizierer berechnet die Root aus T und dem Geschwisterpfad neu. Wenn die berechnete Root mit der Merkle-Root im Blockheader übereinstimmt, ist T nachgewiesen.

1024 Transaktionen → Merkle-Beweis = 10 Hashes = 320 Byte. Vollständiger Block = ~1 MB. SPV-Clients laden nur den 80-Byte-Header + den 320-Byte-Merkle-Beweis für jede für sie relevante Transaktion herunter – 99,97 % Bandbreite werden gegenüber dem Herunterladen des vollständigen Blocks eingespart.

Wenn sich eine Transaktion im Baum ändert, ändert sich ihr Blatthash, und diese Änderung setzt sich bis zur Merkle-Root fort. Die veränderte Root stimmt nicht mehr mit dem Blockheader überein (der durch PoW abgesichert ist). Jede Änderung lässt sich erkennen, indem die Root aus den Transaktionen berechnet wird.

Ethereum erweitert Merkle-Bäume um Tries (Patricia-Merkle-Trie): einen hexadezimalpräfixcodierten Radix-Trie, bei dem jeder Knoten per Merkle-Hash gehasht wird. Verwendet für: State-Trie (Kontostände), Transaktions-Trie, Receipt-Trie. Dies ermöglicht einen effizienten Nachweis des Kontostands ohne die Daten eines vollständigen Nodes.

Eine Merkle-Mountain-Range (MMR) ist eine nur erweiterbare Merkle-Struktur für protokollartige Daten. Neue Elemente werden angehängt; Peaks (Roots von Teilbäumen mit Größen von Zweierpotenzen) werden verwaltet. Sie wird in Grin/MimbleWimble und ZCash für effiziente kompakte Beweise über ein nur erweiterbares Protokoll verwendet.

Verkle-Bäume ersetzen Merkle-Bäume in der Ethereum-Roadmap (EIP-6800): Sie verwenden Vektor-Commitments (KZG-Polynom-Commitments) statt Hashes. Beweisgröße: O(1) statt O(log n) bei Merkle-Bäumen. Dadurch können zustandslose Clients den Zustand verifizieren, ohne den vollständigen Trie zu speichern.

Certificate Transparency (RFC 6962) verwendet ein nur erweiterbares Merkle-Log: Jedes von einer CA ausgestellte Zertifikat ist ein Blatt. Inklusionsbeweise weisen nach, dass ein Zertifikat protokolliert wurde. Konsistenzbeweise weisen nach, dass das Log nur erweitert wurde (keine Löschungen oder Einfügungen). Browseranbieter verifizieren SCTs mithilfe dieses Logs.

Git-Bäume (Verzeichnissnapshots) sind Merkle-Bäume: Jeder Baumknoten hasht seine Datei-Blobs und Unterbäume. Ein Commit-Hash identifiziert den gesamten Zustand der Codebasis eindeutig. Deshalb liefert git checkout immer genau dieselben Dateien.

Merkle-Bäume ermöglichen Inklusionsbeweise mit O(log n). Bitcoin speichert die Merkle-Root in Blockheadern; SPV-Clients verwenden Beweise. Ethereum erweitert dies zu Patricia-Merkle-Tries. Verkle-Bäume werden Merkle-Bäume für Beweise mit O(1) ersetzen. Als Nächstes: Proof-of-Work-Mining und Schwierigkeit.