Das Konzept eines Merkle-Trees wurde in den frühen 80er Jahren von Ralph Merkle vorgeschlagen – einem Informatiker, der für seine Arbeiten zur
Public-Key-Kryptographie bekannt ist.
Ein Merkle-Tree ist eine Struktur, die verwendet wird, um die Integrität von Daten in einem Satz effizient zu überprüfen. Sie sind besonders interessant im Zusammenhang mit
Peer-to-Peer-Netzwerken, in denen die Teilnehmer Informationen austauschen und unabhängig voneinander validieren müssen.
Hash-Funktionen sind das Kernstück von Merkle-Treestrukturen, daher empfehlen wir Ihnen, sich mit
Was ist Hashing? vertraut zu machen, bevor Sie fortfahren.
Angenommen, Sie möchten eine große Datei herunterladen. Bei
Open-Source-Software möchten Sie normalerweise überprüfen, ob der Hash-Wert der Datei, die Sie heruntergeladen haben, mit einem von den Entwicklern veröffentlichten Hash-Wert übereinstimmt. Wenn dies der Fall ist, wissen Sie, dass die Datei, die Sie auf Ihrem Computer haben, genau mit der ihren übereinstimmt.
Wenn die Hashes nicht übereinstimmen, haben Sie ein Problem. Entweder haben Sie eine bösartige Datei heruntergeladen, die sich als die Software ausgibt, oder sie wurde nicht korrekt heruntergeladen und funktioniert daher nicht. Wenn Letzteres der Fall ist, werden Sie wahrscheinlich nicht allzu glücklich sein, wenn Sie einige Zeit warten mussten, bis die Datei heruntergeladen wurde. Jetzt müssen Sie den Prozess neu starten und hoffen, dass er nicht wieder korrumpiert wird.
Wenn es doch nur einen einfacheren Weg gäbe, denken Sie. Glücklicherweise ist das der Punkt, an dem die Merkle-Trees ins Spiel kommen. Mit einem von diesen würden Sie Ihre Datei in Stücke zerlegen lassen. Wenn es eine 50-GB-Datei wäre, könnten Sie sie in hundert Stücke teilen, so dass jedes 0,5 GB groß ist. Dann würde sie Stück für Stück heruntergeladen werden. Dies ist im Wesentlichen das, was Sie tun, wenn Sie Torrents herunterladen.
In diesem Fall wird Ihnen Ihre Quelle einen Hash, den sogenannten Merkle-Root, zur Verfügung gestellt haben. Dieser einzelne Hash ist eine Darstellung jedes Datenblocks, aus dem Ihre Datei besteht. Die Merkle-Root macht 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. Rufen Sie die verschiedenen Fragmente A bis H auf. 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 erhalten, das ein bisschen mehr Sinn ergibt. Wir haben den Hash-Wert aller Fragmente. Wenn also eines davon fehlerhaft ist, erkennen wir das, indem wir es mit dem der Quelle vergleichen, richtig? Möglicherweise, aber das ist auch unglaublich ineffizient. Wenn Ihre Datei Tausende von Fragmenten enthält, werden Sie dann wirklich alle Hashes durchführen und die Ergebnisse sorgfältig vergleichen?
Nein. Stattdessen werden wir jedes Paar von Hashes nehmen, sie kombinieren und dann erneut hashen. Wir haben also hA + hB, hC + hD, hE + hF und hG + hH gehasht. Am Ende haben wir vier Hashes. Dann machen wir eine weitere Runde von Hashes mit diesen, um am Ende zwei zu erhalten. Schließlich nehmen wir die verbleibenden zwei Hashes, um zu unserem Master-Hash zu gelangen - dem Merkle-Root (oder Root Hash).
Die Struktur sieht wie ein auf dem Kopf stehender Baum aus. In der unteren Reihe haben wir die Blätter, die kombiniert werden, um die Knoten und schließlich die Wurzel zu erzeugen.
Jetzt haben wir die Merkle-Root, die die Datei darstellt, die wir heruntergeladen haben. Wir können diesen Root 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 geringfügige Änderung der Daten wird uns also eine völlig andere Merkle-Root liefern.
Glücklicherweise gibt es eine praktische Methode, mit der wir überprüfen können, welches Fragment fehlerhaft ist. In unserem Fall sagen wir, es ist hE. Sie würden damit beginnen, einen Peer nach den beiden Hashes zu fragen, die die Merkle-Root erzeugt haben (hABCD und hEFGH). Ihr Wert hABCD sollte mit dem ihren übereinstimmen, da es in diesem Unterbaum keinen Fehler gibt. Aber hEFGH wird es nicht tun, also wissen Sie, dass Sie dort nachschauen müssen. Sie fordern dann hEF und hGH an und vergleichen sie mit Ihrem. hGH wird gut aussehen, so dass Sie wissen, dass hEF unser Übeltäter ist. Zuletzt vergleichen Sie die Hashes von hE und hF. Sie wissen jetzt, dass hE fehlerhaft ist, also müssen Sie dieses Fragment erneut herunterladen.
Zusammenfassend lässt sich sagen, dass ein Merkle-Tree entsteht, indem man Daten in viele Fragmente teilt, die dann wiederholt gehasht werden, um die Merkle-Root zu bilden. Sie können dann effizient überprüfen, ob mit einem Datenfragment etwas schief gelaufen ist. Wie wir im nächsten Abschnitt sehen werden, gibt es auch andere interessante Anwendungen.
Wollen Sie Krypto-Währungen ausprobieren? Kaufen Sie Bitcoin auf Binance!
Es gibt eine Handvoll Anwendungsfälle für Merkle-Roots, aber hier werden wir uns auf ihre Bedeutung in
Blockchains konzentrieren. Merkle-Trees sind in
Bitcoin und vielen anderen Kryptowährungen von wesentlicher Bedeutung. Sie sind ein integraler Bestandteil eines jeden
Blocks, wo sie in dem
Block-Header zu finden sind. Um die Blätter für unseren Baum zu erhalten, verwenden wir den Transaktionshash (die
TXID) jeder im Block enthaltenen Transaktion.
Die Merkle-Root dient in diesem Fall mehreren Zwecken. Werfen wir einen Blick auf ihre Anwendungen im Mining von Kryptowährungen und in der Transaktionsverifizierung.
Mining
Ein Bitcoin-Block besteht aus zwei Teilen. Der erste Teil ist der Block-Header, ein Segment 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 tendenziell viel größer als der Header ist.
Um einen gültigen Block zu minen, müssen Miner wiederholt Daten hashen, um eine Ausgabe zu erzeugen, die bestimmten Bedingungen entspricht. Sie können Billionen von Versuchen unternehmen, bevor sie einen finden. Bei jedem Versuch ändern sie eine Zufallszahl im Block-Header (die
Nonce), um eine andere Ausgabe zu erzeugen. Der Großteil des Blocks bleibt jedoch gleich. Es kann Tausende von Transaktionen geben, und Sie müssten sie trotzdem jedes Mal hashen.
Ein Merkle-Root vereinfacht den Prozess erheblich. Wenn Sie mit dem Mining beginnen, reihen Sie alle Transaktionen, die Sie einbeziehen möchten, aneinander und bauen einen Merkle-Tree auf. Den resultierenden Root-Hash (32 Bytes) fügen Sie in den Block-Header ein. Dann brauchen Sie beim Mining nur den Block-Header zu hashen, anstatt den gesamten Block.
Dies funktioniert, weil es manipulationssicher ist. Sie fassen effektiv alle Transaktionen des Blocks in einem kompakten Format zusammen. Sie können keinen gültigen Block-Header finden und später die Transaktionsliste ändern, weil dies die Merkle-Root ändern würde. Wenn der Block an andere Nodes gesendet wird, berechnen diese die Root aus der Transaktionsliste. Wenn sie nicht mit der im Header übereinstimmt, lehnen sie den Block ab.
Verifizierung
Es gibt eine weitere interessante Eigenschaft der Merkle-Roots, die wir nutzen können. Diese betrifft die Light-Clients (Nodes, die keine vollständige Kopie der Blockchain enthalten). Wenn Sie einen Node auf einem Gerät mit begrenzten Ressourcen betreiben, möchten Sie nicht alle Transaktionen eines Blocks herunterladen und hashen. Was Sie stattdessen tun können, ist einfach einen Merkle-Proof anfordern – einen Beweis, der vom Full-Node geliefert wird und beweist, dass sich Ihre Transaktion in einem bestimmten Block befindet. Dies wird üblicherweise als Simplified Payment Verification (Vereinfachte Zahlungsüberprüfung) oder SPV bezeichnet und wurde von
Satoshi Nakamoto im Bitcoin-Whitepaper ausführlich beschrieben.
Um hD zu überprüfen, benötigen wir nur die rot markierten Hashes.
Betrachten wir das Szenario, in dem wir Informationen über die Transaktion, deren TXID hD ist, wissen wollen. Wenn uns hC zur Verfügung gestellt wird, können wir hCD ausarbeiten. Dann brauchen wir hAB, um hABCD zu berechnen. Schließlich können wir mit hEFGH überprüfen, ob der resultierende Merkle-Root mit dem aus dem Block-Header übereinstimmt. Wenn dies der Fall ist, ist dies der Beweis dafür, dass die Transaktion in den Block aufgenommen wurde – es wäre nahezu unmöglich, denselben Hash mit unterschiedlichen Daten zu erstellen.
Im obigen Beispiel mussten wir den Hash nur dreimal erstellen. Ohne einen Merkle-Proof hätten wir es sieben Mal tun müssen. Da Blöcke heutzutage Tausende von Transaktionen enthalten, spart uns die Verwendung von Merkle-Proofs eine Menge Zeit und Rechenressourcen.
Merkle-Trees haben sich in einer Reihe von Informatikanwendungen als sehr nützlich erwiesen – wie wir gesehen haben, sind sie in Blockchains unglaublich wertvoll. In verteilten Systemen ermöglichen Merkle-Trees die einfache Überprüfung von Informationen, ohne das Netzwerk mit unnötigen Daten zu überfluten.
Ohne Merkle-Trees (und Merkle-Roots) wären die Blöcke von
Bitcoin und anderen
Kryptowährungen nicht annähernd so kompakt wie heute. Und obwohl Light-Clients bezüglich Datenschutz und Sicherheit nicht vollständig überzeugen, ermöglichen Merkle-Proofs den Anwendern mit minimalem Aufwand zu überprüfen, ob ihre Transaktionen in einen Block aufgenommen wurden.
