Merkle-Trees und Merkle-Roots erklärt
Startseite
Artikel
Merkle-Trees und Merkle-Roots erklärt

Merkle-Trees und Merkle-Roots erklärt

Fortgeschritten
Veröffentlicht Jul 6, 2020Aktualisiert Dec 27, 2022
7m

Was ist ein Merkle-Tree?

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.


Wie funktionieren Merkle-Trees?

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!



Warum werden Merkle-Roots in Bitcoin verwendet?

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.


Fazit

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.
Beitrag teilen
Eröffne ein Konto
Setze dein Wissen in die Praxis um und eröffne noch heute ein Binance-Konto.