Merkle-Baum (Blockchain Hash Tree)

Was ist ein Merkle-Baum?

Ein Merkle-Baum oder Hash-Baum (engl. Merkle tree oder hash tree) ist eine in der Kryptografie, bei Blockchains und einigen Kryptowährungen verwendete Datenstruktur zur Überprüfung der Integrität von Datenelementen innerhalb eines größeren Datensatzes.

Merkle-Bäume bestehen aus Datenblöcken, von denen jeder in einen eindeutigen Hashwert umgewandelt wird.

Die einzelnen Hashes werden dann gepaart und erneut gehasht – ein Vorgang, der als Verkettung bekannt ist. Dieser Prozess wird fortgesetzt, bis nur noch ein einziger Hash, die Merkle-Root, übrig bleibt.

Die Wurzel bietet einen einzigen Bezugspunkt für den gesamten Datensatz.

Merkle-Baum einfach erklärt

Der Baum hat eine hierarchische Datenstruktur, die eine übergeordnete Beziehung zwischen den Knoten aufweist.

Im Laufe der Zeit hat sich die Darstellung von Baumstrukturen in der Informatik als Standard etabliert, indem die Wurzeln eines Baumes an den Anfang eines Diagramms gestellt werden.

Der Grund für die umgekehrte Ausrichtung ist auf historische Konventionen bei der Erstellung von Diagrammen zurückzuführen.

Zum Beispiel werden viele hierarchische Darstellungen, wie Organigramme, naturgemäß von oben nach unten gelesen.

Wie werden Merkle-Bäume erstellt?

Merkle-Bäume werden mithilfe kryptografischer Hash-Funktionen erstellt, die Eingabedaten in Zeichenketten fester Größe, so genannte Hashes, umwandeln.

Jeder Hash im Baum repräsentiert ein bestimmtes Datenelement oder einen Block von Datenelementen.

Während der Baum von unten nach oben aufgebaut wird (Blattebene des Baums), stellt jeder nachfolgende Hash eine Kombination der Hashes der untergeordneten Hashes dar, bis der oberste Hash, die Merkle-Wurzel, tatsächlich die Gesamtheit der Eingabedaten bildet.

Zum Aufbau eines Merkle-Baums wird der gesamte Datensatz zunächst in kleinere Segmente, sogenannte Blöcke, unterteilt.

Gibt es keine gerade Anzahl von Blöcken, wird der letzte Block dupliziert, um Parität zu erreichen. Jedem Block wird dann ein Hash zugewiesen, der zu einem Blattknoten des Baums wird.

Zur Bildung der Baumhierarchie werden zwei benachbarte Blattknoten-Hashes kombiniert (verkettet). Das verbundene Paar wird dann gehasht, um einen übergeordneten Knoten zu erzeugen, der sich über den beiden ursprünglichen Blattknoten befindet.

Die Verknüpfung und das Hashing werden Schicht für Schicht fortgesetzt, bis nur noch ein Hash an der Spitze des Baumes steht.

Der letzte Hash, der als Merkle-Wurzel oder Root-Hash bezeichnet wird, fasst den gesamten Datensatz zusammen.

Merkle-Bäume zur Datenüberprüfung

Mit Merkle-Bäumen können bestimmte Datenelemente, die Teil eines großen Datensatzes sind, schnell und effizient verifiziert werden, indem eine Teilmenge der Hashes des Baums untersucht wird.

Im Wesentlichen wird dabei der Pfad vom fraglichen Datenblock zur Merkle-Wurzel überprüft.

Im Folgenden wird der Überprüfungsprozess vereinfacht dargestellt:

• Zunächst wird der Hash des zu überprüfenden Datenblocks ermittelt.
• Weiter nach oben im Baum. Auf jeder Ebene des Baums sucht man den benachbarten (geschwisterlichen) Hash zum aktuellen Hash, verkettet (kombiniert) ihn mit seinem „Geschwister“ und hasht die resultierende Kombination.
• Man vergleicht den neu berechneten Hash-Wert mit dem des übergeordneten Knotens im Baum. Bei Übereinstimmung wird der Vorgang fortgesetzt, bis die Merkle-Wurzel erreicht ist.

Solange die neu berechneten Hashes mit den Hashes der übergeordneten Knoten im ursprünglichen Baum übereinstimmen, kann die Integrität des betreffenden Datenblocks überprüft werden.

Jede Veränderung der Daten würde zu Diskrepanzen in den Pfad-Hashes oder der Merkle-Wurzel führen.

Merkle-Bäume bei Blockchains und Bitcoin

Merkle-Bäume dienen der Überprüfung von Inkonsistenzen und der Validierung von Blockchains.

Durch die Organisation von Transaktionshashes in einem Merkle-Baum kann jeder Blockchain-Knoten schnell und effizient verifizieren, ob eine bestimmte Transaktion innerhalb eines Blocks existiert.

Diese Struktur hilft zudem bei der Sicherstellung der Integrität der Daten in einem bestimmten Block.

Ändert sich nur eine einzige Transaktion, so ändert sich auch die Merkle-Wurzel (der oberste Hash des Baums), wodurch Inkonsistenzen erkennbar werden.

Wenn im Bitcoin-Protokoll ein neuer Block zur Blockchain hinzugefügt wird, enthält jeder Block die Merkle-Wurzel eines Merkle-Baums im Header.

So entsteht automatisch ein „Proof-of-Inclusion“ für jede Bitcoin-Transaktion.

Mit dem Proof-of-Inclusion lässt sich nachweisen, dass eine bestimmte Transaktion Teil eines Blocks ist, ohne dass alle Transaktionen in diesem Block offengelegt oder überprüft werden müssen.

Dieser Nachweis ist besonders wichtig für leichtgewichtige SPV-Wallets (Simplified Payment Verification), die nicht die gesamte Blockchain zur Verifizierung von Transaktionen herunterladen.

Darüber hinaus spielen Merkle-Bäume eine Rolle beim „Proof-of-Reserves“. Proof-of-Reserves ist eine Methode, die von Kryptobörsen und Wallet-Anbietern zum Nachweis ausreichender Mittel zur Deckung der Guthaben ihrer Kunden verwendet wird.