Merkle-Bäume & Blockchains
Erstmal einfach — Was ist ein Merkle-Baum?
Ein Stammbaum aus Hashes. Du hasht jede Transaktion einzeln (die Blätter), dann hasht du je zwei Hashes zusammen (die Äste), und immer so weiter — bis ganz oben ein einziger Hash steht, die Wurzel.
Magie: ändert sich irgendwas an irgendeiner Transaktion, ändert sich die Wurzel. Sie ist ein Fingerabdruck der gesamten Datenmenge — nur 32 Bytes lang.
Live: Merkle-Baum aus 4 Transaktionen
Warum eigentlich? — Wofür der ganze Aufwand?
- Effiziente Beweise: Will jemand zeigen „Transaktion X ist Teil dieses Blocks", braucht er nur einen Merkle-Beweis — log₂(n) Hashes. Bei 1 Million Transaktionen: 20 Hashes statt 1 Million. Light-Clients (z. B. Bitcoin auf dem Handy) machen genau das.
- Integrität großer Datenmengen: Statt eine ganze Datenbank zu vergleichen, vergleichen zwei Knoten nur ihre Wurzeln. Bei Unterschied: rekursiv nach unten, bis die abweichende Stelle gefunden ist.
- Inhalts-Adressierung: Git, IPFS, Docker-Layers — alle adressieren Daten über ihren Hash. Merkle-Strukturen erlauben das effizient für ganze Verzeichnisbäume.
Tiefer rein — Blockchain = Merkle-Baum + Hash-Kette
Eine Blockchain besteht aus zwei Hash-Strukturen:
- Innerhalb eines Blocks: Die Transaktionen werden zu einem Merkle-Baum verdichtet. Im Block-Header steht nur die Wurzel.
- Zwischen Blöcken: Jeder Block-Header enthält den Hash des vorigen Blocks. Eine simple verkettete Liste — aber kryptografisch.
Folge: ändert ein Angreifer eine alte Transaktion, ändert sich deren Block-Hash, also auch der Verweis im nächsten Block, also dessen Hash, etc. — die gesamte Kette ab da müsste neu berechnet werden. Bei Bitcoin kommt dann noch Proof-of-Work obendrauf, was das praktisch unmöglich macht.
Geschichte — Wer hat das erfunden?
Ralph Merkle, 1979 in seiner Stanford-Doktorarbeit — eigentlich als Mittel für effiziente digitale Signaturen (Merkle-Signatures, eines der ersten Public-Key-Verfahren überhaupt). Die Datenstruktur fand erst Jahrzehnte später Anwendung in Git (2005) und Bitcoin (2008).
Ironie der Geschichte: Merkle-Signaturen sind heute wieder hochaktuell — als Post-Quantum-Verfahren, weil sie nur Hashes brauchen und gegen Shor's Algorithmus immun sind.