Was sind Merkle Trees und warum sind sie wichtig?

Ein Merkle Tree, benannt nach dem Wissenschaftler Ralph Merkle und auch als Merkle-Baum oder Hash-Baum bekannt, ist eine Hash-basierte Datenstruktur, die in der Kryptographie und Informatik verwendet wird.

Erinnerst du dich daran, wie du in Lektion 19 der Bitpanda Academy für Fortgeschrittene über Hash-Funktionen gelernt hast? Hash-Funktionen werden verwendet, um die Länge von Inhalten zu vereinheitlichen, diese Inhalte sicher zu machen sowie für das Identifizieren von Transaktionen in der Blockchain. 

Was ist ein Merkle Tree (Merkle-Baum)?

Im Bitcoin-Netzwerk werden Merkle Trees für die effiziente Datenüberprüfung verwendet, da anstelle einer vollständigen Informationsdatei Hashes verwendet werden. Ein Merkle Tree ist eine Baumstruktur aus gehashten Werten, wie in der Abbildung unten dargestellt:

Die blauen Kästchen am unteren Rand - "m0”, “m1”, “m2” und “m3" - stellen Daten dar. Diese Daten "m" werden nicht als Teil des Merkle-Baums betrachtet. Wenn nun der Wert in einem solchen Kästchen -– mit einem Kleinbuchstaben "m" – gehasht wird, erhalten wir einen gehashten Wert, der in dem gelben Kästchen oben mit einem Großbuchstaben "M" angegeben ist. 

Root Node and Leaf Nodes (Wurzelknoten und Blattknoten)

Die gelben Kästen in der Infografik stellen Leaf Nodes ("Blattknoten") dar und zeigen Daten an, die gehasht wurden. Die beiden Werte "M0" und "M1" werden (angezeigt durch ein "+"-Zeichen) angehängt und wie im dunkelgrauen Kästchen dargestellt gemeinsam gehasht. Das Ergebnis ist ein weiterer gehashter Wert, der die “child node values” (“Werte des Kindknotens”) enthält. Schließlich werden diese Werte angehängt und gehasht, was zu einer einzigen "Wurzel" führt, die auch “Merkle Root” ("Merkle-Wurzel") genannt wird. 

Die beiden Knoten unter einem übergeordneten Knoten sind die "Kindknoten" dieses übergeordneten Knotens. 

Der Root-Hash ist der oberste Hash in der hashbasierten Datenstruktur. Was für uns hier wichtig ist, ist der Bezug zu Bitcoin, in dessen Aufbau diese Wurzel ein Teil des Block-Headers ist. Sie stellt sicher, welche Transaktionen vorhanden sind.

Ein Merkle Tree verwendet eine spezielle Art von beschreibender Terminologie, um die Beziehung zwischen Nodes (“Knoten”) und den Ebenen der Nodes zu beschreiben, wie sie beispielsweise auch im Zahlungsüberprüfungsprozess der Simplified Payment Verification (SPV) verwendet wird.

Eine Node (Knoten), die die Werte der beiden unter ihr liegenden Knoten enthält, ist der "Elternknoten" dieser beiden Knoten. Wenn jeder Knoten höchstens zwei "Unterknoten" oder "Kinder" hat, spricht man von einem binären (lat. für “doppelt”) Hash-Baum. Die beiden Knoten unter einem Elternknoten sind die "Kindknoten" dieses Elternknotens. Ein Kindknoten neben einem anderen Kindknoten ist der "Bruderknoten" dieses Kindknotens. Alle Knoten am unteren Ende, die keine "Kinder" haben, werden Leaf Nodes ("Blattknoten") genannt, sie befinden sich alle auf der gleichen Ebene.  

Wie du sehen kannst, ist der Name Hash-Baum auf eine baumähnliche Struktur zurückzuführen, bei der jede Leafnode ein Hash-Wert eines Datenblocks ist. Merkle Trees verwenden in der Regel eine binäre Baumstruktur, es kann aber auch eine höhere Ausgabestufe verwendet werden. Ein perfekter Merkle Tree ist so aufgebaut, dass die Anzahl der Leaves (“Blätter”) immer 2n beträgt, wobei der Wert "n" 1, 2, 3 usw. entspricht. Jeder Knoten hat entweder gar keinen Kindknoten oder zwei davon. 

Wie werden Merkle Trees in der Blockchain-Technologie verwendet und warum?

Im Bitcoin-Netzwerk fasst ein Merkle Tree alle Transaktionen innerhalb eines Blocks zusammen, indem er einen digitalen Fingerabdruck des gesamten Transaktionssatzes erstellt. Auf diese Weise kann ein Benutzer überprüfen, ob eine Transaktion in einem Block enthalten ist oder nicht.

Alle Nodes in der baumartigen Struktur des Merkle Trees sind Teil-Repräsentationen der darunter liegenden gehashten Daten. 

Nun fragst du dich vielleicht, warum ein Hash-Baum erforderlich ist, um dies zu beweisen? Wäre es nicht möglich, alle Nachrichten (die ursprünglichen Daten) zu hashen, die gehashten Werte in eine einzige Zeichenkette zu packen und auf diese Weise den Wert des Wurzel-Hashes zu erhalten? Warum machen Merkle Trees uns das Leben leichter?

Eine Frage des Vertrauens

Stell dir ein Leben ohne Merkle Trees vor. Anstelle der Merkle-Wurzel würden wir einen Hash aller Transaktionen aus der Blockchain im Block-Header speichern. Das bedeutet: Um nur eine einzige Transaktion zu verifizieren, müssten wir die Daten sämtlicher Transaktionen herunterladen. 

Merkle Trees verringern die Menge der für die Überprüfung benötigten Daten. Nehmen wir an, Marie möchte Lukas beweisen, dass die Transaktion "m6" nicht manipuliert wurde. Lukas könnte den Root-Hash von einer vertrauenswürdigen Quelle erhalten und verifizieren, dass dies tatsächlich so ist. 

Würden Marie und Lukas keinen Merkle Tree hinzuziehen, müsste Marie Lukas sämtliche gehashte Transaktionen vorlegen, um zu beweisen, dass "m6" nicht manipuliert wurde. Ein Merkle Tree ist hier eine viel bessere Möglichkeit, um das zu überprüfen. Auch hier erhält Lukas die Wurzel von einer Quelle, der er vertraut. Wenn Marie nun beweisen will, dass "m6" nicht manipuliert wurde, muss sie nur wie in der folgenden Grafik dargestellt die Nachricht und vier gehashte Werte (in der Grafik in lila) an Lukas senden:

Alle Nodes in der baumartigen Struktur des Merkle Trees sind Teildarstellungen der gehashten Daten in der Stufe darunter. Die Blätter im Merkle Tree sind Hashes (verkürzte Informationen) der einzelnen Transaktionen.

Die Überprüfung auf Widersprüche

In verteilten Peer-to-Peer-Netzwerken wie der Bitcoin-Blockchain sind auf jedem Computer im Peer-to-Peer-Netzwerk dieselben Daten vorhanden. Jedes Mal, wenn die Blockchain durch das Hinzufügen einer Transaktion geändert wird, werden die Änderungen gleichzeitig auf jedem Computer im gesamten Netzwerk wiedergegeben. 

Lukas kann nun den entsprechenden Teil des Merkle Trees rekonstruieren, um die Merkle Root zu finden. Damit kann er die gehashten Werte aus einer nicht vertrauenswürdigen Quelle überprüfen. Wenn der rekonstruierte Root Hash mit dem Root Hashwert aus der vertrauenswürdigen Quelle übereinstimmt, kann er die Werte akzeptieren. Es ist einfacher, einen Teil eines Merkle Tree neu zu erstellen als die Daten anhand aller gehashten Daten zu überprüfen – und genauso sicher.  

Kurz gesagt beschleunigt die Verwendung eines Merkle Trees in der Überprüfung von Inkonsistenzen den Validierungsprozess erheblich, da nur Hashes und Dateien, die noch nicht vollständig sind, über ein Netzwerk gesendet werden. Das macht diesen Prozess nicht nur bequemer, sondern beansprucht auch viel weniger Speicherplatz auf einem Computer.