Ein Merkle Tree verbindet kryptografische Fingerabdrücke von Daten schrittweise zu einem Ergebnis. In Bitcoin entsteht so die Merkle root im Blockheader. Mit wenigen zusätzlichen Fingerabdrücken lässt sich prüfen, ob eine bestimmte Transaktion zu dieser Wurzel passt, ohne alle anderen Transaktionen zu übertragen.
Die Wallet zeigt an, dass Ihre Zahlung in einen Block aufgenommen wurde. Wie lässt sich das prüfen, ohne dessen gesamten Inhalt herunterzuladen? Dabei hilft der Merkle Tree. Transaktionen werden zunächst durch Hashes vertreten, also kurze kryptografische Fingerabdrücke. Diese werden schrittweise zu einem gemeinsamen Fingerabdruck zusammengeführt, der Wurzel. Der Blockheader enthält diese Merkle root und bindet den Block so an seine Transaktionen. Die Wurzel ist kein Archiv, aus dem man sämtliche Zahlungen herauslesen könnte. Sie dient dazu, vorgelegte Daten zu prüfen. [1] [2]
Stellen Sie sich vier Transaktionen A, B, C und D vor. Ihre Fingerabdrücke werden paarweise verbunden: Aus A und B berechnen wir den neuen Hash AB, aus C und D den Hash CD. Schließlich verbinden wir AB mit CD und berechnen die Wurzel. Die Buchstaben benennen hier nur Transaktionen und Zwischenergebnisse; sie sind keine echten Hashes. Das Verfahren ähnelt einem umgedrehten Baum: Viele Blätter laufen über Äste zu einer Wurzel zusammen. Bei mehr Transaktionen kommen Ebenen hinzu, das Prinzip bleibt gleich. [3]
Für die Prüfung von B haben Sie dessen Daten und berechnen den Fingerabdruck. Zusätzlich brauchen Sie nur den Fingerabdruck von A und den gemeinsamen Fingerabdruck CD samt ihrer korrekten Reihenfolge. Aus A und B bilden Sie AB, dann aus AB und CD die Wurzel und vergleichen sie mit der Wurzel im Header. Dieser ergänzende Pfad heißt Merkle proof. Der Inhalt von A, C und D ist nicht nötig. In einem balancierten Baum mit 1024 Transaktionen umfasst der Pfad 10 benachbarte Hashes. Mit wachsendem Block wächst der Nachweis also deutlich langsamer als die vollständige Transaktionsliste. [2] [3]
Passt der Nachweis zur Wurzel, darf man dem vorgelegten Header deshalb noch nicht blind vertrauen. Auch der Proof of Work muss stimmen: Erfüllt das Ergebnis der Mining-Berechnung die geforderte Schwierigkeit? Außerdem muss der Header mit der entsprechenden Kette verbunden sein. Selbst dann kontrolliert ein Merkle proof nicht alle Signaturen und Regeln sämtlicher Transaktionen im Block. Das übernimmt ein Full Node. Die im Whitepaper beschriebene vereinfachte Zahlungsprüfung SPV beruht daher auf anderen Sicherheitsannahmen als die vollständige Validierung. Durch eine Reorganisation kann der Block zudem aus dem aktiven Zweig herausfallen: Sein Inhalt bleibt nachweisbar, aber die Stellung der Zahlung in der aktuellen Transaktionshistorie kann sich ändern. [2]
Im gewöhnlichen Bitcoin-Baum sind die Blätter txid-Kennungen in der Transaktionsreihenfolge des Blocks, beginnend mit der Coinbase Transaction, der besonderen Transaktion, mit der der Miner die Blockbelohnung beansprucht. Paare werden als Bytes verbunden und zweimal mit SHA-256 gehasht. Bleibt auf einer Ebene ein letzter Hash ohne Partner, wird er für diese Berechnung verdoppelt. Es entsteht keine zusätzliche Zahlung. Bei nur einer Transaktion ist deren txid unmittelbar die Wurzel. Die Verdopplung erfordert sorgfältige Duplikatprüfungen in der Implementierung. Die Protokollverbesserung SegWit trennt außerdem Witness-Daten wie Signaturen ab. Ein weiterer kryptografischer Fingerabdruck in der Coinbase Transaction bindet diese Daten an den Block. Er wird witness commitment genannt. Der gewöhnliche txid-Baum darf deshalb nicht mit dem Witness-Baum verwechselt werden. [3] [4]
Für ein möglichst vollständiges Bild lies diesen Eintrag zusammen mit Block, Transaktion, Block Header. Auf diesen Eintrag verweisen außerdem Block Header, Hash, SHA-256, Bestätigung.