Merkle-Baum
Was ist ein Merkle-Baum?
Ein Merkle-Baum ist eine Datenstruktur, die in Informatikanwendungen verwendet wird. In Bitcoin und anderen Kryptowährungen dienen Merkle-Bäume dazu, Blockchain-Daten effizienter und sicherer zu verschlüsseln.
Sie werden auch als „binäre Hashbäume“ bezeichnet.
Den Merkle-Baum abbauen
In der Blockchain von Bitcoin wird ein Transaktionsblock durch einen Algorithmus ausgeführt, um einen Hash zu generieren, bei dem es sich um eine Folge von Zahlen und Buchstaben handelt, mit der überprüft werden kann, ob ein bestimmter Datensatz mit dem ursprünglichen Transaktionssatz identisch ist, aber den ursprünglichen Satz von Transaktionen nicht zu erhalten. Die Bitcoin-Software führt jedoch nicht den gesamten Transaktionsdatenblock – der durchschnittlich Transaktionen im Wert von 10 Minuten darstellt – gleichzeitig über die Hash-Funktion aus. Vielmehr wird jede Transaktion gehasht, dann wird jedes Transaktionspaar verkettet und zusammen gehasht und so weiter, bis es einen Hash für den gesamten Block gibt. (Bei einer ungeraden Anzahl von Transaktionen wird eine Transaktion verdoppelt und ihr Hash mit sich selbst verkettet.)
Visualisiert ähnelt diese Struktur einem Baum. Im Diagramm unten bezeichnet „T“ eine Transaktion, „H“ einen Hash. Beachten Sie, dass das Bild stark vereinfacht ist; ein durchschnittlicher Block enthält über 500 Transaktionen, nicht acht.
Die Hashes in der unteren Reihe werden als „Blätter“, die dazwischenliegenden Hashes als „Zweig“ und der Hash ganz oben als „Wurzel“ bezeichnet. Die Merkle-Wurzel eines bestimmten Blocks wird im Header gespeichert: Die Merkle-Wurzel des Blocks # 482819 lautet beispielsweise e045b18e7a3d708d686717b4f44db2099aabcad9bebf968de5f7271b458f71c8. Die Wurzel wird mit anderen Informationen (der Softwareversion, dem Hash des vorherigen Blocks, dem Zeitstempel, dem Schwierigkeitsziel und der Nonce) kombiniert und dann eine Hash-Funktion durchlaufen, um den einzigartigen Hash des Blocks zu erzeugen: 000000000000000000bfc767ef8bf28c42cbd4bdbafd9aa1b5c3c33c2b0895482819. Dieser Hash ist eigentlich nicht im entsprechenden Block enthalten, sondern im nächsten; es unterscheidet sich von der Merkle-Wurzel.
Der Merkle-Baum ist nützlich, da er es Benutzern ermöglicht, eine bestimmte Transaktion zu überprüfen, ohne die gesamte Blockchain (über 130 Gigabyte Ende August 2017) herunterzuladen. Angenommen, Sie möchten überprüfen, ob die Transaktion T D im Block im obigen Diagramm enthalten ist. Wenn Sie die Root – Hash (H haben ABCDEFGH ), ist der Prozess, wie ein Spiel von Sudoku: Sie das Netzwerk über H abfragen D, und es kehrt H C, H AB, und H EFGH. Der Hash-Baum ermöglicht, dass alles zu überprüfen ist, für drei Hashes entfielen: H gegeben AB, H C, H EFGH, und die Wurzel H ABCDEFGH, H D (die einzigen fehlende hash) hat, die in den Daten.
Merkle-Bäume sind nach Ralph Merkle benannt, der sie 1987 in einem Papier mit dem Titel „ A Digital Signature Based on a Conventional Encryption Function “ vorgeschlagen hat. Merkle erfand auch das kryptographische Hashing.