Hashbaum / Merkle Tree

Falls ihr noch nie von Merkle Trees bzw. Hashbäumen gehört habt, wird es Zeit. Dieses kryptographische Konzept ist unverzichtbar, um Bitcoin zu verstehen.

Erfunden wurden die Merkle Trees vom deutschen Mathematiker Ralph Merkle. Ein Hashbaum erlaubt es, die Authentizität großer Datenmengen mit einer einzigen Hash zu prüfen. Wir veranschaulichen das durch dieses Bild:

Das ist ein Merkle-Tree. Die untere Reihe mit den Blöcken 01-07 sind die Hashes von Datensätzen. Man nennt sie auch “Blätter”. In einem ersten Schritt werden jeweils zwei Hashes von Transaktionen verbunden und erneut gehasht. Das sind dann die Blöcke 08-11. Im nächsten Schritt werden diese Blöcke ebenfalls in Zweierpaaren verbunden und gehasht. Das geht solange weiter, bis nur noch ein einziger Hash übrig bleibt. Den nennt man die “Merkle Root”, sozusagen die Wurzel des Baumes. Mit dieser Wurzel hat man nun eine sehr kompakte Datenmenge, durch die man alle “Blätter” des Baums validieren kann.

Wozu ist das nützlich? Ein Beispiel ist Bitcoin. Ohne den Merkle Tree gäbe es Bitcoin nicht. Denn die Miner nehmen die Transaktionen, die sie bestätigen, und hashen sie als Blatt in den Merkle Tree ein. Die Wurzel dieses Hashbaums der Transaktionen ist dann Teil der Daten eines gültigen Blockheaders. So beweist eine einzige Hash, dass der Miner sämtliche Transaktionen aufgenommen hat.

Das ist nicht nur praktisch, um zu minen, sondern auch, weil man dadurch die alten Transaktionen wieder wegwerfen kann. Das erklärt Satoshi im Whitepaper:

Sobald die letzte Transaktion eines Coins unter ausreichend Blöcken begraben ist, können die verbrauchten Transaktionen davor gelöscht werden, um Speicherplatz zu sparen. Um dies zu ermöglichen, ohne den Hash des Blocks zu brechen, werden die Transaktionen in einem Merkle-Tree gehasht, und lediglich die Root in die Hash des Blocks aufgenommen. Alte Blöcke können dann komprimiert werden, indem Zweige des Baumes gekappt werden. Die internen Hashes müssen nicht gespeichert werden.

Dass Bitcoin eine Merkle Root anstatt aller Transaktionen für den Blockheader verwendet, hat noch einen weiteren Vorteil: Man kann dadurch auch Zahlungen mit sogenannten SPV-Nodes validieren. Solche Nodes haben niemals die komplette Blockchain heruntergeladen. Satoshi erklärt dies ebenfalls im Whitepaper:

Ein Nutzer muss lediglich eine Kopie der Blockheader der längsten Proof-of-Work-Kette aufbewahren, die er erhalten kann, indem er andere Netzwerk-Knoten solange abfragt, bis er überzeugt ist, dass er die längste Kette hat, und den Merkle-Zweig beziehen, der die Transaktion mit dem Block verknüpft, durch den sie einen Zeitstempel erhalten hat. Er kann die Transaktion nicht selbst prüfen, aber indem er sie mit einer Stelle in der Kette verknüpft, kann er sehen, dass sie von einem Netzwerk-Node akzeptiert wurde, und Blöcke, die danach angefügt wurden, bestätigen weiter, dass sie vom Netzwerk akzeptiert wurde.

Seit dem Taproot-Upgrade stecken Hashbäume bzw. ihre Wurzel aber nicht nur in Blöcken, sondern auch in jeder einzelnen Adresse. Eine Taproot-Adresse enthält die Wurzel eines Hashbaumes, was es erlaubt, eine Vielfalt von Daten, Logiken und Operationen in ihr unterzubringen. Die Hasbäume in Taproot-Transaktionen wurden zur Grundlage der Ordinals-NFTs, der BRC20-Token, der Taproot-Assets sowie der BitVM.