Wichtigste Erkenntnisse

• Ein Merkle-Baum ist eine kryptografische Datenstruktur, die Daten in Paare von Hashwerten organisiert und diese nach oben kombiniert, bis ein einzelner Hashwert, die Merkle-Wurzel, den gesamten Datensatz repräsentiert.

• Merkle-Wurzeln ermöglichen es Blockchain-Netzwerken, zu überprüfen, ob eine Transaktion in einem Block enthalten ist, ohne den gesamten Block herunterzuladen. Dies geschieht mithilfe eines kompakten Merkle-Beweises, der logarithmisch mit der Anzahl der Transaktionen skaliert.

• Bitcoin bettet die Merkle-Wurzel in jeden Block-Header ein, wodurch schlanke Clients Transaktionen nur anhand der Block-Header und nicht anhand der gesamten Blockchain verifizieren können.

• Ethereum verwendet einen komplexeren Merkle Patricia Trie zur Speicherung von Kontoständen und Smart Contract-Zuständen, wodurch Zustandsnachweise für Light Clients und Layer-2-Rollups möglich werden.

Einführung

Merkle-Bäume gehören zu den grundlegenden Konzepten, die Blockchain-Systeme effizient und skalierbar machen. Sie ermöglichen es Netzwerken, ganze Datensätze in einem einzigen kryptografischen Fingerabdruck zusammenzufassen und gleichzeitig nachzuweisen, dass eine bestimmte Transaktion oder Information enthalten ist. Um zu verstehen, warum Merkle-Bäume im Blockchain-Design so wichtig sind, betrachten wir ihre Funktionsweise, ihre Verwendung in verschiedenen Netzwerken und mögliche zukünftige Verbesserungen durch neuere Strukturen wie Verkle-Bäume.

Wie Merkle-Bäume funktionieren

Ein Merkle-Baum, benannt nach dem Informatiker Ralph Merkle, der das Konzept 1979 patentierte, ist eine Datenstruktur, die zur effizienten Zusammenfassung und Überprüfung der Integrität großer Datensätze dient. In einer Blockchain komprimieren Merkle-Bäume Tausende von Transaktionen zu einem einzigen kompakten Wert, der im Block-Header gespeichert wird.

Der Baum wird mithilfe kryptografischer Hashfunktionen von unten nach oben aufgebaut. Jeder Blattknoten enthält den Hashwert eines einzelnen Datenelements, beispielsweise einer Transaktion. Diese Blatt-Hashwerte werden dann paarweise zugeordnet: Der Hashwert jedes Paares wird berechnet, indem die Hashwerte der beiden Kindknoten verkettet und das Ergebnis gehasht wird. Dieser Prozess wiederholt sich Schicht für Schicht nach oben, bis an der Spitze, der Merkle-Wurzel, nur noch ein einziger Hashwert übrig bleibt.

Da jeder Elternknoten von seinen beiden Kindern abhängt, führt jede Änderung an einem einzelnen Blatt zu einer Kaskade nach oben und erzeugt eine völlig andere Merkle-Wurzel. Diese Eigenschaft macht Merkle-Bäume zu einem effektiven Werkzeug zur Erkennung von Manipulationen: Wenn zwei Kopien eines Datensatzes dieselbe Merkle-Wurzel erzeugen, sind die Datensätze mit extrem hoher Wahrscheinlichkeit identisch.

Merkle-Wurzeln

Der Merkle-Root ist ein Hash fester Größe, typischerweise 32 Byte (256 Bit) in Blockchain-Anwendungen, der als digitaler Fingerabdruck für den gesamten Datensatz dient. Block-Header in den meisten Blockchain-Netzwerken enthalten den Merkle-Root zusammen mit anderen Metadaten wie Zeitstempeln und dem Hash des vorherigen Blocks. Dadurch bleiben die Header klein, während gleichzeitig alle Transaktionen innerhalb des Blocks kryptografisch gesichert werden.

Zur Veranschaulichung betrachten wir eine 8 GB große Datei, die in acht Teile aufgeteilt ist. Nennen wir die verschiedenen Fragmente A bis H. Jedes Fragment wird dann durch eine Hash-Funktion geleitet, wodurch wir acht verschiedene Hashwerte erhalten.

Anhand des Hashwerts aller Fragmente lässt sich ein fehlerhaftes Fragment durch Vergleich mit dem Hashwert der Quelldatei erkennen, richtig? Möglich, aber das kann auch extrem ineffizient sein. Wenn Ihre Datei Tausende von Fragmenten enthält, würden Sie wirklich alle hashen und die Ergebnisse mühsam vergleichen?

Die Merkle-Wurzel bietet eine elegantere Lösung. Man nimmt jeweils zwei Hashwerte, kombiniert sie und berechnet dann den resultierenden Hashwert. Man erhält die Hashwerte hA + hB, hC + hD, hE + hF und hG + hH und am Ende vier Hashwerte.

Nach einer weiteren Hash-Runde erhält man zwei Hashwerte: hABCD und hEFGH. Schließlich werden die beiden verbleibenden Hashwerte gehasht, um den Master-Hash zu erhalten. Dieser Merkle-Root (oder Root-Hash) lautet: hABCDEFGH.

Merkle-Beweise und Verifikation

Eine der praktischsten Eigenschaften von Merkle-Bäumen ist die Möglichkeit, die Zugehörigkeit eines bestimmten Datenelements zu einem Datensatz nachzuweisen, ohne den gesamten Datensatz offenzulegen. Dies wird als Merkle-Beweis bezeichnet. Um zu überprüfen, ob eine Transaktion in einem Block enthalten ist, benötigt ein Light Client lediglich die Transaktion selbst, eine kleine Menge von Hashwerten benachbarter Transaktionen entlang des Pfades zur Wurzel sowie die Merkle-Wurzel aus dem Blockheader. Der Verifizierer berechnet die Hashwerte entlang des Pfades neu und prüft, ob das Ergebnis mit der bekannten Wurzel übereinstimmt. Stimmt dies zu, ist mathematisch bewiesen, dass die Transaktion Teil des Blocks ist.

Betrachten wir ein Szenario, in dem Sie eine Transaktion mit der Transaktions-ID hD verifizieren möchten. Wenn hC angegeben ist, können Sie hCD berechnen. Anschließend verwenden Sie hAB, um hABCD zu ermitteln. Abschließend überprüfen Sie mit hEFGH, ob der resultierende Merkle-Root mit dem aus dem Blockheader übereinstimmt. Ist dies der Fall, ist dies der Beweis, dass die Transaktion im Block enthalten war. Es wäre nahezu unmöglich, denselben Hash mit anderen Daten zu erzeugen.

Im obigen Beispiel müssen Sie den Hash nur dreimal berechnen. Ohne Merkle-Beweis wären sieben Hash-Berechnungen nötig. Da Blöcke heutzutage Tausende von Transaktionen enthalten, spart die Verwendung von Merkle-Beweisen viel Zeit und Rechenressourcen.

Die Größe des Beweises wächst logarithmisch mit der Anzahl der Blätter: Für eine Million Transaktionen (ein Binärbaum der Tiefe 20) werden nur etwa 20 Hashes benötigt, was ungefähr 640 Byte entspricht. Dadurch können Lightweight-Nodes, auch SPV-Clients (Simplified Payment Verification) genannt, Transaktionen verifizieren, ohne die gesamte Blockchain herunterzuladen – ein Vorgang, der andernfalls Hunderte von Gigabyte an Daten erfordern würde.

Merkle-Bäume in Blockchain-Netzwerken

Bitcoin und Transaktionsverifizierung

In Bitcoin enthält jeder Blockheader eine 32 Byte große Merkle-Wurzel, die alle Transaktionen im Block bestätigt. Bitcoin-Miner erstellen aus den enthaltenen Transaktionen einen Merkle-Baum, dessen Wurzel zusammen mit dem Proof-of-Work-Verfahren in den Blockheader eingebettet wird. Dadurch genügt der Blockheader (typischerweise etwa 80 Byte), um zu überprüfen, ob eine bestimmte Transaktion im Block enthalten ist, ohne dass die anderen Transaktionen benötigt werden.

Bitcoin verwendet in seinem MAST-Vorschlag (Merkelized Abstract Syntax Trees) ebenfalls Merkle-Bäume. Dadurch lassen sich komplexe Ausgabenbedingungen in Bitcoin-Skripten als Merkle-Baum darstellen. Es muss lediglich der ausgeführte Zweig des Skripts offengelegt werden, wodurch ungenutzte Bedingungen geheim bleiben und die Transaktionsgröße reduziert wird.

Ethereum und Zustandsnachweise

Ethereum verwendet eine komplexere Variante namens Merkle-Patricia-Trie, eine hexadezimale (16-gliedrige) Baumstruktur, die Kontostände, Smart Contracts und Speicherdaten speichert. Im Gegensatz zum einfachen binären Merkle-Baum, der für Bitcoin-Transaktionen verwendet wird, ist der Merkle-Patricia-Trie für häufige Zustandsaktualisierungen ausgelegt: Ändert sich ein Kontostand, muss lediglich der Pfad von diesem Blatt zur Wurzel neu berechnet werden, anstatt den gesamten Baum neu aufzubauen.

Die aus dem Merkle Patricia Trie generierten Zustandsnachweise ermöglichen es Ethereum Light Clients und Layer-2-Rollups, Kontostände und Vertragsspeicher zu verifizieren, ohne einen vollständigen Knoten betreiben zu müssen. Diese Nachweise sind auch für Cross-Chain-Bridges unerlässlich, die Ereignisse einer Blockchain von einer anderen aus verifizieren müssen.

Einschränkungen und zukünftige Entwicklungen

Merkle-Bäume ermöglichen zwar eine effiziente Verifizierung, die Größe der Beweise wächst jedoch weiterhin logarithmisch mit dem Datensatz. Bei Ethereum können die Blockzeugen – die zur Validierung eines Blocks benötigten Beweise – mit zunehmendem Zustand mehrere Megabyte erreichen. Dies stellt eine Skalierungsherausforderung für zustandslose Clients dar, die diese Beweise für jeden Block empfangen und verifizieren müssten.

Verkle-Bäume, die Vektor-Commitments auf Basis polynomialer (Kate-Zaverucha-Goldberg- oder KZG-)Commitments anstelle herkömmlicher Hash-Algorithmen verwenden, bieten eine mögliche Lösung. Durch die Gruppierung vieler Kindknoten unter jedem Knoten (Verzweigungsfaktor 256) erzeugen Verkle-Bäume Beweise von nahezu konstanter Größe (etwa 170 Byte), unabhängig von der Größe des Datensatzes. Ethereum arbeitet aktiv an der Integration von Verkle-Bäumen; die Implementierung wird in einem zukünftigen Update erwartet. Dieser Übergang würde die Datenlast auf Light Clients deutlich reduzieren und die Skalierbarkeit des Netzwerks insgesamt verbessern.

Häufig gestellte Fragen

Was ist ein Merkle-Baum in einfachen Worten?

Ein Merkle-Baum ist eine Methode zur Datenorganisation, bei der ein einzelnes kleines Informationselement, die Merkle-Wurzel, einen großen Datensatz repräsentieren kann. Er funktioniert, indem Datenpaare wiederholt gehasht werden, bis nur noch ein Hashwert übrig bleibt. Dadurch lässt sich überprüfen, ob ein bestimmtes Element zum Datensatz gehört, ohne jedes Element einzeln prüfen zu müssen.

Was ist eine Merkle-Wurzel?

Die Merkle-Wurzel ist der einzelne Hashwert an der Spitze eines Merkle-Baums. Sie dient als kompakter digitaler Fingerabdruck für alle darunter liegenden Daten. In Blockchain-Netzwerken wird die Merkle-Wurzel im Block-Header gespeichert und in jede Transaktion dieses Blocks übernommen. Dies ermöglicht eine effiziente Überprüfung, ob eine Transaktion Teil eines Blocks ist.

Wie funktioniert ein Merkle-Beweis?

Ein Merkle-Beweis liefert eine Transaktion zusammen mit der minimalen Menge an Hashes von Geschwistertransaktionen, die benötigt werden, um den Pfad von dieser Transaktion bis zur Merkle-Wurzel zu berechnen. Der Verifizierer berechnet den Hash der Transaktion, kombiniert ihn mit den angegebenen Geschwistertransaktionen in der korrekten Reihenfolge und prüft, ob das Endergebnis mit der bekannten Merkle-Wurzel im Blockheader übereinstimmt. Stimmt es überein, ist die Transaktion als enthalten bewiesen.

Warum sind Merkle-Bäume für die Blockchain wichtig?

Merkle-Bäume ermöglichen es Blockchain-Netzwerken, Block-Header von den vollständigen Transaktionsdaten zu trennen. Ein Light Client kann lediglich die Block-Header herunterladen (ca. 80 Byte pro Block) und dennoch mithilfe eines kompakten Merkle-Beweises verifizieren, dass eine Transaktion enthalten war. Ohne Merkle-Bäume würde die Verifizierung einer Transaktion das Herunterladen des gesamten Blocks oder der gesamten Blockchain erfordern.

Worin besteht der Unterschied zwischen einem Merkle-Baum und einem Verkle-Baum?

Beide sind kryptografische Akkumulatoren, die zum Nachweis der Datenzugehörigkeit verwendet werden, basieren aber auf unterschiedlichen mathematischen Verfahren. Merkle-Bäume nutzen Hashfunktionen und erzeugen Nachweise, deren Größe logarithmisch mit dem Datensatz wächst (O(log n)). Verkle-Bäume hingegen verwenden polynomiale (KZG-)Commitments und erzeugen Nachweise von nahezu konstanter Größe (einige hundert Bytes unabhängig von der Datensatzgröße), wodurch sie sich besser für den Nachweis des Zustands großer Blockchains eignen.

Schlussgedanken

Merkle-Bäume sind ein Eckpfeiler der Blockchain-Architektur und ermöglichen vertrauenslose Verifizierung in großem Umfang. Indem sie einen gesamten Transaktionsblock in einen einzigen 32-Byte-Hash komprimieren, erlauben sie den Teilnehmern, Daten zu verifizieren, ohne alles herunterladen zu müssen – ein Prinzip, das von Bitcoin-SPV-Wallets über Ethereum-State-Proofs bis hin zu Cross-Chain-Bridges alles untermauert. Mit dem weiteren Wachstum von Blockchain-Netzwerken könnten neuere kryptografische Strukturen wie Verkle-Bäume Merkle-Bäume zwar ergänzen oder ersetzen, doch das zugrundeliegende Konzept der effizienten, Hash-basierten Datenintegrität wird voraussichtlich noch viele Jahre ein fundamentaler Baustein verteilter Systeme bleiben.

Weiterführende Literatur

• Was ist ein Blockchain-Konsensalgorithmus?

• Geschichte der Kryptographie

• Blockchain-Layer-1- vs. Layer-2-Skalierungslösungen

• Was ist Sharding und wie funktioniert es?

Haftungsausschluss: Diese Inhalte werden Ihnen ohne Gewähr und ausschließlich zu allgemeinen Informations- und Bildungszwecken zur Verfügung gestellt. Es wird keinerlei Zusicherung oder Gewährleistung übernommen. Sie stellen keine Finanz-, Rechts- oder sonstige professionelle Beratung dar und sind nicht als Empfehlung für den Kauf bestimmter Produkte oder Dienstleistungen zu verstehen. Bitte lassen Sie sich von entsprechenden Fachleuten beraten. Sofern die Inhalte von Dritten beigetragen wurden, beachten Sie bitte, dass die darin geäußerten Ansichten die Meinung des jeweiligen Dritten widerspiegeln und nicht notwendigerweise die der Binance Academy. Die Preise digitaler Vermögenswerte können stark schwanken. Der Wert Ihrer Anlage kann steigen oder fallen, und Sie erhalten möglicherweise nicht den vollen Anlagebetrag zurück. Sie tragen die alleinige Verantwortung für Ihre Anlageentscheidungen, und die Binance Academy haftet nicht für etwaige Verluste. Weitere Informationen finden Sie in unseren Nutzungsbedingungen, Risikohinweisen und den Nutzungsbedingungen der Binance Academy.