Was ist ein Merkle-Baum?
Das Konzept eines Merkle-Baums wurde Anfang der 80er Jahre von Ralph Merkle vorgeschlagen, einem Informatiker, der für seine Arbeit zur Public-Key-Kryptographie bekannt ist.
Ein Merkle-Baum ist eine Struktur, mit der die Integrität von Daten in einem Satz effizient überprüft werden kann. Merkle-Bäume sind besonders im Kontext von Peer-to-Peer-Netzwerken interessant, in denen die Teilnehmer Informationen austauschen und unabhängig voneinander validieren müssen.
Hash-Funktionen bilden den Kern von Merkle-Baumstrukturen. Wir empfehlen Ihnen daher, sich vor dem Fortfahren den Abschnitt „Was ist Hashing?“ anzusehen.
Wie funktionieren Merkle-Bäume?
Angenommen, Sie möchten eine große Datei herunterladen. Bei Open-Source-Software möchten Sie normalerweise überprüfen, ob der Hash der heruntergeladenen Datei mit einem von den Entwicklern veröffentlichten Hash übereinstimmt. Wenn dies der Fall ist, wissen Sie, dass die Datei auf Ihrem Computer genau mit der des Entwicklers übereinstimmt.
Wenn die Hashes nicht übereinstimmen, liegt ein Problem vor. Entweder haben Sie eine schädliche Datei heruntergeladen, die sich als Software ausgibt, oder sie wurde nicht richtig heruntergeladen und funktioniert daher nicht. Wenn Letzteres der Fall ist, werden Sie wahrscheinlich nicht sehr erfreut sein, wenn Sie einige Zeit auf den Download der Datei warten mussten. Jetzt müssen Sie den Vorgang neu starten und hoffen, dass er nicht erneut beschädigt wird.
Wenn es doch nur einen einfacheren Weg gäbe, denken Sie. Zum Glück gibt es da die Merkle-Bäume. Mit einem dieser Bäume können Sie Ihre Datei in mehrere Teile aufteilen. Eine 50 GB große Datei könnten Sie in hundert Teile aufteilen, von denen jeder 0,5 GB groß ist. Dann würden Sie sie Stück für Stück herunterladen. Das ist im Wesentlichen das, was Sie tun, wenn Sie Torrent-Dateien herunterladen.
In diesem Fall hat Ihnen Ihre Quelle einen Hash bereitgestellt, der als Merkle-Wurzel bezeichnet wird. Dieser einzelne Hash ist eine Darstellung jedes Datenblocks, aus dem Ihre Datei besteht. Mit der Merkle-Wurzel ist es jedoch viel einfacher, die Daten zu überprüfen.
Um es einfach zu halten, nehmen wir ein Beispiel, bei dem wir eine 8 GB große Datei verwenden, die in acht Teile zerlegt ist. Nennen Sie die verschiedenen Fragmente A bis H. Jedes Fragment wird dann durch eine Hash-Funktion geleitet, wodurch wir acht verschiedene Hashes erhalten.
Wir leiten jedes unserer acht Fragmente durch eine Hash-Funktion, um ihre Hashes zu erhalten.
Okay, wir haben also etwas, das ein bisschen mehr Sinn ergibt. Wir haben den Hash aller Fragmente, also wenn eines fehlerhaft ist, wissen wir es, indem wir es mit dem der Quelle vergleichen, richtig? Möglich, aber das ist auch unglaublich ineffizient. Wenn Ihre Datei Tausende von Fragmenten hat, werden Sie dann wirklich alle hashen und die Ergebnisse akribisch vergleichen?
Nein. Stattdessen nehmen wir jedes Hashpaar, kombinieren sie und hashen sie dann zusammen. Wir hashen also hA + hB, hC + hD, hE + hF und hG + hH. Am Ende haben wir vier Hashes. Dann machen wir eine weitere Hashrunde mit diesen, um am Ende zwei zu haben. Schließlich hashen wir die verbleibenden zwei, um zu unserem Master-Hash zu gelangen – der Merkle-Wurzel (oder dem Root-Hash).
Die Struktur sieht aus wie ein umgedrehter Baum. In der unteren Reihe befinden sich die Blätter, die zusammen die Knoten und schließlich die Wurzel bilden.
Wir haben jetzt die Merkle-Wurzel, die die heruntergeladene Datei darstellt. Wir können diesen Wurzel-Hash mit dem von der Quelle gelieferten vergleichen. Wenn er übereinstimmt, perfekt! Aber wenn die Hashes unterschiedlich sind, können wir sicher sein, dass die Daten verändert wurden. Mit anderen Worten, ein oder mehrere Fragmente haben einen anderen Hash erzeugt. Jede noch so kleine Veränderung der Daten führt also zu einer völlig anderen Merkle-Wurzel.
Glücklicherweise gibt es eine praktische Möglichkeit, um zu prüfen, welches Fragment fehlerhaft ist. In unserem Fall ist es beispielsweise hE. Sie würden zunächst einen Peer nach den beiden Hashes fragen, die die Merkle-Wurzel erzeugt haben (hABCD und hEFGH). Ihr Wert hABCD sollte mit dem Peer übereinstimmen, da dieser Teilbaum keinen Fehler enthält. Bei hEFGH ist dies jedoch nicht der Fall, sodass Sie wissen, dass Sie dort nachsehen müssen. Anschließend fordern Sie hEF und hGH an und vergleichen sie mit Ihren. Bei hGH sieht alles in Ordnung aus, sodass Sie wissen, dass hEF der Übeltäter ist. Zuletzt vergleichen Sie die Hashes von hE und hF. Sie wissen nun, dass hE falsch ist, sodass Sie diesen Block erneut herunterladen können.
Zusammenfassend lässt sich sagen, dass ein Merkle-Baum dadurch entsteht, dass Daten in viele Teile aufgeteilt werden, die dann wiederholt gehasht werden, um die Merkle-Wurzel zu bilden. Sie können dann effizient überprüfen, ob mit einem Datenteil etwas schiefgelaufen ist. Wie wir im nächsten Abschnitt sehen werden, gibt es auch andere interessante Anwendungen.
Möchten Sie mit Kryptowährungen beginnen? Kaufen Sie Bitcoin auf Binance!
Warum werden in Bitcoin Merkle-Wurzeln verwendet?
Es gibt eine Handvoll Anwendungsfälle für Merkle-Bäume, aber hier konzentrieren wir uns auf ihre Bedeutung in Blockchains. Merkle-Bäume sind für Bitcoin und viele andere Kryptowährungen unverzichtbar. Sie sind ein integraler Bestandteil jedes Blocks und sind dort in den Blockheadern zu finden. Um die Blätter für unseren Baum zu erhalten, verwenden wir den Transaktions-Hash (die TXID) jeder im Block enthaltenen Transaktion.
Die Merkle-Wurzel dient in diesem Fall mehreren Zwecken. Werfen wir einen Blick auf ihre Anwendungen beim Kryptowährungs-Mining und bei der Transaktionsüberprüfung.
Bergbau
Ein Bitcoin-Block besteht aus zwei Teilen. Der erste Teil ist der Blockheader, ein Segment mit fester Größe, das Metadaten für den Block enthält. Der zweite Teil ist eine Liste von Transaktionen, deren Größe variabel ist, aber in der Regel viel größer als der Header ist.
Miner müssen Daten wiederholt hashen, um eine Ausgabe zu erzeugen, die bestimmte Bedingungen erfüllt, um einen gültigen Block zu minen. Sie können Billionen von Versuchen unternehmen, bevor sie einen finden. Bei jedem Versuch ändern sie eine Zufallszahl im Blockheader (den Nonce), um eine andere Ausgabe zu erzeugen. Aber ein Großteil des Blocks bleibt gleich. Es kann Tausende von Transaktionen geben, und Sie müssen sie trotzdem jedes Mal hashen.
Eine Merkle-Wurzel rationalisiert den Prozess erheblich. Wenn Sie mit dem Mining beginnen, ordnen Sie alle Transaktionen, die Sie einschließen möchten, an und erstellen einen Merkle-Baum. Den resultierenden Root-Hash (32 Bytes) fügen Sie in den Blockheader ein. Wenn Sie dann mit dem Mining beginnen, müssen Sie nur den Blockheader hashen, statt den ganzen Block.
Das funktioniert, weil es manipulationssicher ist. Sie fassen alle Transaktionen des Blocks effektiv in einem kompakten Format zusammen. Sie können keinen gültigen Blockheader finden und später die Transaktionsliste ändern, da dies die Merkle-Wurzel ändern würde. Wenn der Block an andere Knoten gesendet wird, berechnen diese die Wurzel aus der Transaktionsliste. Wenn sie nicht mit der im Header übereinstimmt, lehnen sie den Block ab.
Überprüfung
Es gibt noch eine weitere interessante Eigenschaft von Merkle-Roots, die wir nutzen können. Diese betrifft die Light-Clients (Knoten, die keine vollständige Kopie der Blockchain besitzen). Wenn Sie einen Knoten auf einem Gerät mit begrenzten Ressourcen ausführen, möchten Sie nicht alle Transaktionen eines Blocks herunterladen und hashen. Stattdessen können Sie einfach einen Merkle-Beweis anfordern – einen vom vollständigen Knoten bereitgestellten Beweis, der belegt, dass sich Ihre Transaktion in einem bestimmten Block befindet. Dies wird allgemein als vereinfachte Zahlungsüberprüfung oder SPV bezeichnet und wurde von Satoshi Nakamoto im Bitcoin-Whitepaper ausführlich beschrieben.
Zur Überprüfung von hD benötigen wir lediglich die rot dargestellten Hashes.
Stellen Sie sich das Szenario vor, in dem wir Informationen über die Transaktion mit der TXID hD wissen möchten. Wenn uns hC zur Verfügung gestellt wird, können wir hCD berechnen. Dann benötigen wir hAB, um hABCD zu berechnen. Schließlich können wir mit hEFGH überprüfen, ob die resultierende Merkle-Wurzel mit der aus dem Blockheader übereinstimmt. Wenn dies der Fall ist, ist dies ein Beweis dafür, dass die Transaktion im Block enthalten war – es wäre nahezu unmöglich, denselben Hash mit unterschiedlichen Daten zu erstellen.
Im obigen Beispiel mussten wir nur dreimal hashen. Ohne einen Merkle-Beweis hätten wir es siebenmal tun müssen. Da Blöcke heutzutage Tausende von Transaktionen enthalten, sparen wir durch die Verwendung von Merkle-Beweisen viel Zeit und Rechenressourcen.
Abschließende Gedanken
Merkle-Bäume haben sich in zahlreichen Informatikanwendungen als äußerst nützlich erwiesen – wie wir gesehen haben, sind sie in Blockchains unglaublich wertvoll. In verteilten Systemen ermöglichen Merkle-Bäume eine einfache Überprüfung von Informationen, ohne das Netzwerk mit unnötigen Daten zu überfluten.
Ohne Merkle-Bäume (und Merkle-Wurzeln) wären die Blöcke von Bitcoin und anderen Kryptowährungen nicht annähernd so kompakt wie heute. Und während Light-Clients in puncto Datenschutz und Sicherheit Mängel aufweisen, können Benutzer mit Merkle-Beweisen mit minimalem Aufwand überprüfen, ob ihre Transaktionen in einen Block aufgenommen wurden.
