Was ist ein Merkle-Tree?

Kurze Zusammenfassung

✔️ Ein Merkle tree teilt Daten auf, erstellt Hash-Werte dieser Daten und fügt sie in einer Baumstruktur zusammen, was eine effiziente Überprüfung und Übertragung ermöglicht.

✔️ Der Merkle tree wurde von Ralph Merkle erfunden und ist ein Baumdiagramm, das für die Datenintegrität verwendet wird.

✔️ Merkle tree werden häufig in Blockchain-Technologien wie Bitcoin und Ethereum verwendet, wo sie helfen, Transaktionen zu validieren und den Datenaufwand zu reduzieren.

Was ist ein Merkle tree?

Das Konzept des Merkle tree wurde von dem amerikanischen Mathematiker Ralph Merkle erfunden und 1979 patentiert. Der deutsche Ex-Bundeskanzler hat also nichts damit zu tun. Es wurde in dem paper "A certified digital signature" beschrieben.

Im Namen Merkle tree steht der letzte Teil für tree. Das ist nicht ohne Grund, denn es handelt sich um ein Baumdiagramm oder ein Verzweigungsmodell, bei dem immer mehr Äste zu einem Hauptzweig führen. Es ist vergleichbar mit dem Verzweigungsmodell eines Stammbaums.

Ein anderer Name für den Merkle tree ist Hash tree. Ein Hash ist eine algorithmische Ableitung einer Eingabe, d.h. man kann mit Hilfe eines bestimmten Systems von Algorithmen einen Hash (Ableitung) aus z.B. einem Wort (Eingabe) ziehen.

Ein sehr bekanntes System ist SHA (Secure Hash Algorithm) 256. Dabei wird aus einer gegebenen Eingabe ein Hash von 256 Bits gebildet. Das Ergebnis (Output) ist dann eine Zeichenfolge aus 64 Ziffern und Buchstaben.

Ein typisches SHA 256 Hash Derivat:

"Anycoindirect" hat als Ausgabe, wenn du SHA 256 darauf anwendest:

98948d20dc70322d424ea5bbf37970e20b6aafa90c498116779ea964042c2c64

"anycoindirect" hat als Ausgabe:

a730a577d61512581afdd9c74e68abb2c43b0f7db3c70a92583464277b7abc81

Du siehst, dass ein einziger Großbuchstabe schon alles verändert. Aus Hashes wie diesem wird ein Baum erstellt. Genau wie an Weihnachten, oder?

Wie funktioniert ein Merkle tree?

Angenommen, du möchtest eine Nachricht oder eine Datei an eine andere Person schicken, aber du möchtest nicht, dass andere sie sehen können. Dabei kann es sich um geheime Informationen wie ein Passwort handeln, aber auch um die Weitergabe einer Datei mit wichtigen Informationen. In diesem Fall kannst du SHA 256 verwenden, um die Nachricht zu verschlüsseln.

Eine Nachricht wird in Teile zerlegt und in einen Hash verwandelt. Jeder Hash erscheint in einem Tree, wobei die Wurzel ganz oben im Tree steht. Dies ist die vollständige Nachricht oder Datei. Ein großer Vorteil dabei ist, dass die Nachricht in kleine Stücke aufgeteilt werden kann. Das bedeutet, dass riesige Dateien nicht komplett von einem einzigen Computer übermittelt werden müssen und es viel schneller geht.

Der Baum wird also von unten nach oben aufgebaut, ganz ähnlich wie bei Bittorrent. Jeder hat dann ein kleines Stück der Datei (Peer-to-Peer-Netzwerke) und beim Endnutzer werden alle kleinen Stücke wieder zusammengesetzt, woraufhin der Baum wieder vollständig ist. Dann kann der Endnutzer mit seinem Merkle tree berechnen, ob alle Stücke original sind (die Hashes, die berechnet werden können, müssen dann mit seiner Tabelle übereinstimmen).

Die Wurzel hat ein bestimmtes Ergebnis. Wenn du sie also kennst, weißt du auch, ob die Nachricht oder die Datei original sind. Sobald das nicht der Fall ist, wird ein erneuter Versuch unternommen, das Original zu erhalten. Wenn der Root Tree und die Ausgabe in deinem Fall übereinstimmen, hast du die richtigen Informationen erhalten.

Oben haben wir erklärt, wie man einen hash erstellt. Im Baumdiagramm werden einige dieser Ausgaben zusammengeführt und mit der gleichen Methode in einen neuen Hash eingefügt. Je weiter du also in der Baumstruktur nach oben kommst, desto mehr Informationen werden in einem höheren Hash erscheinen. Bis du ganz oben angekommen bist und alle Hashes des Baums zu einem Hash zusammengeführt hast.

Dem Empfänger der Nachricht wird der Root Tree mitgeteilt und er beginnt mit dem Herunterladen der Zweige, der Hashes. Diese Zweige können aus mehreren Quellen stammen. Danach beginnt er, alle Hashes des Baums zu rekonstruieren. Jeder Teil des Tree muss korrekt sein. Sobald das nicht der Fall ist, ist auch der Root Tree nicht korrekt, aber durch die Rekonstruktion kann er feststellen, welcher Teil nicht korrekt ist. Er versucht dann in der Regel, den gesamten Baum erneut herunterzuladen.

Da diese Merkle tree mit binären Daten arbeiten, werden sie auch binäre trees genannt.

Wofür werden Merkle tree in crypto verwendet?

Da du nun weißt, dass du zur Überprüfung der Korrektheit eines Hashes eigentlich nur den Root Tree kennen musst, könntest du dir vorstellen, dass es Systeme gibt, die sich dies zunutze machen.

Eine wichtige Blockchain, die sich dies zunutze macht, ist Bitcoin. Bei dieser Blockchain müssen viele Informationen in einem Block verarbeitet werden. Je weniger Informationen du überprüfen und in einen solchen Block einfügen musst, desto besser.

Da ein Merkle tree eine ganze Menge Daten in einer einzigen Zahl zusammenfassen kann, ist dies beim Aufbau eines Blocks sehr nützlich.

Angenommen, du hast als Miner in den letzten 10 Minuten 200 Transaktionen verarbeitet (etwa alle 10 Minuten wird dem Bitcoin-Netzwerk ein neuer Block hinzugefügt). Dann macht sich der Merkle tree an die Arbeit und reduziert all diese Transaktionen in einen einzigen Root Tree.

Die Validatoren im Bitcoin-Netzwerk müssen den Status der Blockchain im Auge behalten, Transaktionen validieren und neue Münzen hinzufügen. Wenn sie nur eine Sequenz auf ihre Korrektheit überprüfen müssen, sind sie nicht nur viel schneller, sondern ein Block ist auch viel kleiner. Wenn 51% dieser Miner zustimmen, dass der Root Tree korrekt ist, kann der Block hinzugefügt werden.

Dieser Root Tree Hash wird an den Anfang des nächsten Blocks gesetzt, so dass alle Miner den Wert des Hashs des vorherigen Blocks kennen. Wenn sie also einen neuen Block erstellen, setzen sie den gesamten Zustand des Netzwerks mit einer einzigen Chiffrierzeichenfolge fest. Dann werden neue Transaktionen hinzugefügt, die denselben Prozess durchlaufen und so weiter. Wenn der Root Tree nicht korrekt ist, weil zum Beispiel abtrünnige Datensätze darunter sind, können sich die Miner auch nicht einigen und suchen nach einem Merkle tree mit dem richtigen Root Tree. Ethereum verwendet ebenfalls einen Merkle tree, aber natürlich haben sie wieder etwas Besonderes erfunden: den Merkle Patricia tree.

Würden Netzwerke keine Merkle tree verwenden, müssten alle Daten übertragen werden und du kannst dir vorstellen, was das für die Geschwindigkeit bedeuten würde, ganz zu schweigen von der Sicherheit.