Merkle Tree

Ein Merkle Tree ist eine Datenstruktur, die eine große Menge von Elementen in einem einzigen Hash zusammenfasst, indem wiederholt Paare gebildet und gehasht werden: Jede Transaktion wird gehasht, die Hashes werden paarweise zusammengefasst und gemeinsam gehasht, diese Ergebnisse werden wieder paarweise gehasht und so weiter, bis ein einziger Wert übrig bleibt – die Merkle Root. Blockchains speichern diese Root im Header jedes Blocks und legen sich damit mit nur 32 Bytes auf jede Transaktion im Block fest.

Die Stärke der Struktur liegt im effizienten Nachweis. Um zu zeigen, dass eine bestimmte Transaktion in einem Block enthalten ist, braucht man nicht den ganzen Block – nur die Transaktion und die wenigen benachbarten Hashes entlang ihres Pfads zur Root, genannt Merkle Proof. Ein Verifizierer berechnet den Pfad neu und prüft, ob er die bekannte Root ergibt; bei einem Block mit Tausenden Transaktionen umfasst der Nachweis nur etwa ein Dutzend Hashes. So bestätigt zum Beispiel eine schlanke Bitcoin-Wallet auf dem Smartphone, dass sie bezahlt wurde: Sie speichert nur Block-Header, fragt einen Full Node nach dem Merkle Proof ihrer Transaktion und prüft die Mathematik selbst – der Node kann die Aufnahme nicht fälschen, denn das würde das Brechen der Hash-Funktion erfordern.

Ein verbreiteter Irrtum ist, Merkle Trees speicherten oder schützten die Transaktionsdaten selbst; sie legen sich nur darauf fest – die Daten liegen anderswo, und der Baum macht Manipulation erkennbar, nicht unmöglich zu versuchen. Varianten erweitern die Idee: Ethereum nutzt Merkle-Patricia-Tries, um sich auf den gesamten Kontozustand festzulegen, und neuere Designs wie Verkle Trees wollen Nachweise weiter verkleinern, was wichtig ist, damit die Verifikation der Blockchain leichter wird.