Überblick
Merkle Trees – auch Hash-Bäume genannt – sind eine fundamentale Datenstruktur in der Informatik. In Bitcoin spielen sie eine zentrale Rolle: Sie ermöglichen es, alle Transaktionen eines Blocks in einem einzigen Hash zusammenzufassen und gleichzeitig einzelne Transaktionen effizient zu verifizieren. Ohne Merkle Trees wäre Simplified Payment Verification (SPV) nicht möglich, und Light Clients könnten nicht existieren.
Was ist ein Merkle Tree?
Ein Merkle Tree ist eine Baumstruktur aus kryptografischen Hashes. Die unterste Ebene – die Blätter des Baums – besteht aus den Hashes der einzelnen Datensätze. In Bitcoin sind das die Transaktions-Hashes (TXIDs). Jeweils zwei benachbarte Hashes werden konkateniert und erneut gehasht, um einen Elternknoten zu bilden. Dieser Prozess wiederholt sich nach oben, bis nur noch ein einzelner Hash übrig bleibt: die Merkle Root.
Die Struktur erinnert an einen umgekehrten Baum. Ganz unten stehen viele Blätter (die Transaktions-Hashes), und nach oben hin wird der Baum immer schmaler, bis an der Spitze die Wurzel steht. Jede Veränderung an einer einzigen Transaktion verändert den gesamten Pfad nach oben – und damit auch die Merkle Root.
Schritt für Schritt
Nehmen wir ein einfaches Beispiel mit vier Transaktionen (TX A, TX B, TX C, TX D):
- Blätter erzeugen: Jede Transaktion wird mit SHA-256 doppelt gehasht. Das ergibt Hash A, Hash B, Hash C und Hash D.
- Erste Ebene: Hash A und Hash B werden konkateniert und erneut gehasht → Hash AB. Ebenso Hash C und Hash D → Hash CD.
- Merkle Root: Hash AB und Hash CD werden konkateniert und gehasht → Merkle Root.
Bei einer ungeraden Anzahl von Transaktionen wird der letzte Hash dupliziert, damit jede Ebene eine gerade Anzahl hat. Bitcoin verwendet durchgehend Double-SHA-256 (SHA-256 zweimal hintereinander angewendet) für diese Berechnungen.
Wichtig: Ändert sich auch nur ein einziges Byte in einer einzigen Transaktion, verändert sich ihr Hash – und damit kaskadenartig alle darüberliegenden Hashes bis zur Merkle Root. Das macht die Struktur manipulationssicher.
Merkle Root im Block Header
Der Block Header enthält nur sechs Felder und ist stets 80 Bytes gross. Eines dieser Felder ist die Merkle Root – ein 32-Byte-Hash, der sämtliche Transaktionen des Blocks repräsentiert. Egal ob ein Block 1 oder 4'000 Transaktionen enthält: Die Merkle Root ist immer 32 Bytes gross.
Beim Mining wird der Block Header gehasht, nicht die vollständige Transaktionsliste. Das bedeutet, dass die Merkle Root als kompakte Zusammenfassung aller Transaktionen dient. Miner müssen den Merkle Tree einmal berechnen und können dann den Header effizient durchiterieren.
SPV und Merkle Proofs
Satoshi Nakamoto beschrieb im Whitepaper (Kapitel 8) eine Methode namens Simplified Payment Verification (SPV). Die Idee: Ein leichtgewichtiger Client muss nicht die gesamte Blockchain herunterladen, um eine Transaktion zu verifizieren. Er benötigt nur die Block Header und einen sogenannten Merkle Proof.
Ein Merkle Proof besteht aus den Hash-Werten entlang des Pfades von der gesuchten Transaktion bis zur Merkle Root. Für eine bestimmte Transaktion in einem Block mit 1'024 Transaktionen braucht der Proof nur 10 Hashes (log₂(1024) = 10), nicht alle 1'024 Transaktions-Hashes.
Der Light Client nimmt den Merkle Proof, berechnet die Hashes Ebene für Ebene nach oben und prüft, ob das Ergebnis mit der Merkle Root im Block Header übereinstimmt. Stimmt es überein, ist die Transaktion nachweislich im Block enthalten.
Merkle Trees in der Praxis
Die logarithmische Effizienz von Merkle Trees ist entscheidend für die Skalierbarkeit von Bitcoin. Die Verifikation erfordert nur log₂(n) Hash-Berechnungen statt n. Ein paar Beispiele:
- 256 Transaktionen: Nur 8 Hashes im Proof nötig
- 4'096 Transaktionen: Nur 12 Hashes im Proof nötig
- 65'536 Transaktionen: Nur 16 Hashes im Proof nötig
Diese Effizienz ermöglicht es mobilen Wallets und anderen ressourcenbeschränkten Geräten, Transaktionen sicher zu verifizieren. Ohne Merkle Trees müssten Light Clients den gesamten Block herunterladen – bei einer durchschnittlichen Blockgrösse von 1–2 MB wäre das auf mobilen Verbindungen unpraktisch.
Merkle Trees finden auch ausserhalb von Bitcoin Verwendung: Git nutzt sie für die Versionskontrolle, IPFS für dezentrale Dateispeicherung und Ethereum für seinen State-Tree. Die grundlegende Idee – grosse Datenmengen in einem einzigen Hash zusammenzufassen und einzelne Elemente effizient nachzuweisen – ist eine effiziente Datenstruktur der Kryptografie.
Quellen
- Bitcoin Whitepaper, Kapitel 8 – Simplified Payment Verification
- Bitcoin Wiki – Merkle Tree
- Ralph C. Merkle – US Patent 4,309,569: Method of providing digital signatures, 1979