Kurz erklärt: Ein Merkle Tree (auch Hash-Baum) ist eine 1979 von Ralph Merkle patentierte Datenstruktur, in der Datensätze paarweise über Hash-Funktionen zu einem einzigen Wurzel-Hash (Merkle Root) zusammengefasst werden. Er erlaubt es, die Integrität großer Datenmengen effizient und mit minimalem Datenaufwand zu überprüfen und ist ein zentraler Baustein vieler Blockchains.
Herkunft und Grundidee
Der Merkle Tree geht auf den Kryptografen Ralph Merkle zurück und wird seit Jahrzehnten in verteilten Systemen, Dateisystemen und Versionsverwaltungen eingesetzt. Die Grundidee: Statt jeden einzelnen Datensatz separat abzusichern, werden die Hash-Werte hierarchisch verdichtet, bis ein einziger Wert die Gesamtheit aller Daten repräsentiert.
Aufbau
Der Baum wird von unten nach oben aufgebaut:
- Blattknoten: Jeder Datensatz (etwa eine Transaktion) wird gehasht.
- Innere Knoten: Jeweils zwei benachbarte Hashes werden zusammengefügt und erneut gehasht.
- Merkle Root: Dieser Vorgang wiederholt sich, bis nur noch ein einziger Hash uebrig bleibt, die Wurzel des Baums.
Ändert sich auch nur ein einzelnes Datenbit in einem Blatt, ändert sich der Merkle Root vollständig. Damit lässt sich mit einem einzigen Vergleich feststellen, ob ein Datenbestand unverändert ist.
Nutzen in Blockchains
In Bitcoin und vielen anderen Netzwerken fasst jeder Block die enthaltenen Transaktionen in einem Merkle Tree zusammen; nur der Merkle Root wird im Block-Header gespeichert. Das hat mehrere Vorteile:
- Der kompakte Header repräsentiert alle Transaktionen des Blocks.
- Über einen sogenannten Merkle-Proof lässt sich beweisen, dass eine bestimmte Transaktion in einem Block enthalten ist, ohne den gesamten Block herunterzuladen.
- Dies ermöglicht leichtgewichtige Wallets (Simplified Payment Verification), die nur Header und Beweispfade prüfen, statt jeder Node die vollständige Kette zu speichern.
Auch Ethereum nutzt eine erweiterte Variante (Merkle-Patricia-Trie), um neben Transaktionen auch Konto- und Zustandsdaten abzusichern.
Sicherheit und Grenzen
Die Sicherheit eines Merkle Tree hängt vollständig von der verwendeten Hash-Funktion ab. Solange diese kollisionsresistent ist, kann kein Datensatz unbemerkt ausgetauscht werden. Der Merkle-Proof wächst nur logarithmisch mit der Zahl der Datensätze, was die Verifikation auch bei sehr großen Datenmengen effizient hält. Merkle Trees liefern jedoch keine Vertraulichkeit; die zugrunde liegenden Transaktionen bleiben für die On-Chain-Analyse auswertbar.
Häufige Fragen
Was ist der Merkle Root?
Der oberste Hash-Wert des Baums, der durch wiederholtes paarweises Hashen aller Datensätze entsteht. Er repräsentiert den gesamten Datenbestand in einem einzigen Wert.
Wofür werden Merkle Trees in Blockchains genutzt?
Sie fassen alle Transaktionen eines Blocks zusammen, sodass nur der Merkle Root im Block-Header gespeichert werden muss und Zugehörigkeitsbeweise für einzelne Transaktionen möglich sind.
Was ist ein Merkle-Proof?
Eine kompakte Kette von Hash-Werten, mit der sich beweisen lässt, dass ein bestimmter Datensatz Teil des Baums ist, ohne alle Daten offenzulegen oder zu laden.
Erfand Bitcoin den Merkle Tree?
Nein. Das Konzept stammt von Ralph Merkle aus dem Jahr 1979 und wird in vielen Systemen genutzt. Bitcoin verwendet es lediglich zur Absicherung der Transaktionen je Block.
Woran hängt die Sicherheit eines Merkle Tree?
An der Kollisionsresistenz der verwendeten Hash-Funktion. Ist diese sicher, kann kein Datensatz unbemerkt verfälscht werden, da sich sonst der Merkle Root ändern würde.
Zusammenfassung
Ein Merkle Tree ist eine 1979 von Ralph Merkle eingeführte Hash-Baumstruktur, die große Datenmengen über paarweises Hashen zu einem einzigen Wurzel-Hash verdichtet. In Blockchains fasst er die Transaktionen eines Blocks zusammen und ermöglicht effiziente Integritäts- und Zugehörigkeitsbeweise. Seine Sicherheit beruht vollständig auf der verwendeten Hash-Funktion.
Weiterführende Quellen
- Wikipedia: Hash-Baum (Merkle Tree): de.wikipedia.org
- Bitcoin Developer Guide: Block Chain / Merkle Trees: developer.bitcoin.org