Inhalt

• Was ist ein Merkle-Baum?

• Wie funktionieren Merkle-Bäume?

• Warum werden Merkle-Wurzeln in Bitcoin verwendet?

  • Bergbau

  • Überprüfung

• Abschließende Gedanken

Was ist ein Merkle-Baum?

Die Idee eines Merkle-Baums entstand in den frühen 1980er Jahren von Ralph Merkle – einem Informatiker, der vor allem für seine Arbeit auf dem Gebiet der Public-Key-Kryptographie bekannt ist.

Ein Merkle-Baum ist eine Struktur, mit der die Integrität von Daten in einem bestimmten Datensatz effektiv überprüft werden kann. Er ist besonders wichtig im Kontext von Peer-to-Peer-Netzwerken, in denen Teilnehmer Informationen unabhängig voneinander austauschen und überprüfen müssen.

Hash-Funktionen sind ein wesentlicher Bestandteil von Merkle-Baumstrukturen. Wir empfehlen daher, den Artikel „Was ist Hash?“ zu lesen. Bevor Sie diesen Artikel weiterlesen.

Wie funktionieren Merkle-Bäume?

Nehmen wir an, Sie möchten eine große Datei herunterladen. Bei Open-Source-Software möchten Sie in der Regel überprüfen, ob der Hash-Wert der heruntergeladenen Datei mit dem Wert übereinstimmt, den die Entwickler öffentlich zugänglich gemacht haben. Wenn dies der Fall ist, wissen Sie, dass die Datei, die Sie auf Ihrem Computer haben, mit ihrer übereinstimmt.

Wenn die Hashwerte nicht übereinstimmen, liegt ein Problem vor. Entweder haben Sie eine Malware-Datei heruntergeladen, die sich als das Programm ausgibt, oder der Download war nicht erfolgreich, sodass es nicht funktioniert. Wenn der Download nicht erfolgreich ist, werden Sie wahrscheinlich nicht glücklich sein, wenn Sie eine Weile warten müssen, bis die Datei heruntergeladen ist. Anschließend müssen Sie den Vorgang von vorne beginnen und hoffen, dass es dieses Mal gut verläuft.

Sie denken in diesem Fall vielleicht, wenn es nur einen einfacheren Weg gäbe, dies zu tun. Glücklicherweise kommt hier der Merkle-Baum ins Spiel. Mithilfe dieses Baums wird die Datei in Teile unterteilt. Wenn die Dateigröße 50 GB beträgt, können Sie sie möglicherweise in 100 Teile mit einer Größe von jeweils 0,5 GB aufteilen und Stück für Stück herunterladen. Dies ist im Grunde das, was Sie tun, wenn Sie Torrent-Dateien verwenden.

In diesem Fall stellt Ihnen die Dateiquelle einen Hash-Wert zur Verfügung, der als Merkle-Root bekannt ist. Dieser einzelne Wert ist eine Darstellung jedes Datenelements, aus dem Ihre Datei besteht, aber der Merkle-Stamm macht es viel einfacher, die Daten zu überprüfen.

Der Einfachheit halber sehen wir uns dieses Beispiel an, in dem wir eine 8-GB-Datei verwenden, die in 8 Teile unterteilt ist, und diese verschiedenen Teile mit den Buchstaben A bis H kennzeichnen. Anschließend durchläuft jeder Teil eine Hash-Funktion. Daraus ergeben sich 8 verschiedene Hashwerte.

Wir werden jeden der acht Teile durch eine Hash-Funktion leiten, um ihre Hash-Werte zu erhalten.

Nun, jetzt haben wir etwas, das etwas sinnvoller ist. Wir haben die Hash-Werte aller Teile. Wenn also einer davon falsch ist, wissen Sie das, indem Sie ihn mit dem Quell-Hash-Wert vergleichen, oder? Vielleicht, aber das ist auch äußerst ineffizient. Wenn die Datei aus Tausenden von Teilen besteht, werden Sie sie dann wirklich alle partitionieren und die Ergebnisse dann so sorgfältig vergleichen?

Nein, stattdessen nehmen wir jedes Paar Hashwerte, addieren sie und hashen sie dann. Wir hashen also hA + hB, hC + hD, hE + hF und hG + hH, sodass wir am Ende 4 Hash-Werte erhalten. Dann führen wir eine weitere Hash-Runde für diese Werte durch und erreichen schließlich 2 Hash-Werte. Schließlich hashen wir die verbleibenden zwei Werte, um den Haupt-Hash-Wert zu erhalten – den Merkle-Root (oder Root-Hash-Wert).

Die Struktur sieht aus wie ein umgedrehter Baum, wobei wir in der letzten Reihe die Blätter haben, die zusammenkommen, um die Knoten und schließlich die Wurzel zu bilden.

Wir haben jetzt das Merkle-Stammverzeichnis, das die heruntergeladene Datei darstellt. Dieser Root-Hash-Wert kann mit dem von der Quelle bereitgestellten verglichen werden, und wenn sie übereinstimmen, ist das großartig! Wenn die Hash-Werte jedoch unterschiedlich sind, können wir sicher sein, dass die Daten geändert wurden, das heißt, ein oder mehrere Teile haben einen anderen Hash-Wert erzeugt, sodass jede einfache Änderung der Daten zu einer völlig anderen Merkle-Wurzel führt .

Glücklicherweise gibt es für uns alle eine einfache Möglichkeit, zu überprüfen, welcher Teil falsch ist. Nehmen wir in diesem Fall an, dieser Teil sei hE. Fragen Sie zunächst einen Peer nach den beiden Hash-Werten, die die Merkle-Wurzel erzeugt haben (hABCD und hEFGH). Ihr hABCD-Wert sollte mit seinem übereinstimmen, da in diesem Teilbaum kein Fehler vorliegt. Dies gilt jedoch nicht für den Wert hEFGH, daher sollten Sie diesen Wert überprüfen. Anschließend erfragen Sie die hEF- und hGH-Werte und vergleichen diese mit Ihren eigenen Werten. Sie werden feststellen, dass der hGH-Wert in Ordnung ist, und dann wird Ihnen klar, dass der hEF-Wert der Grund für das Problem ist. Abschließend vergleichen Sie die Hashwerte von hE und hF. Jetzt wissen Sie, dass hE falsch ist, sodass Sie dieses Fragment erneut herunterladen können.

Kurz gesagt, ein Merkle-Baum entsteht durch die Aufteilung der Daten in mehrere Teile, die dann iterativ gehasht werden, um eine Merkle-Wurzel zu bilden. So können Sie effektiv prüfen, ob bei den Daten ein Fehler aufgetreten ist. Wie wir im nächsten Abschnitt sehen werden, gibt es noch einige andere interessante Anwendungen.

Möchten Sie mit dem Handel mit digitalen Währungen beginnen? Jetzt Bitcoin (BTC) auf Binance kaufen!

Warum werden Merkle-Wurzeln in Bitcoin verwendet?

Es gibt einige 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 andere Kryptowährungen von großer Bedeutung. Es stellt einen Hauptbestandteil jedes Blocks dar, da es sich in den Blockspeicherpartitionen befindet. Um auf die Blätter des Baums zuzugreifen, verwenden wir den Transaktions-Hash (Transaktions-ID) jeder Transaktion im Block.

In diesem Fall dient die Merkle-Wurzel mehreren Zwecken, und im Folgenden werden wir ihre Anwendungen beim Kryptowährungs-Mining und bei der Transaktionsüberprüfung untersuchen.

Bergbau

Ein Bitcoin-Block besteht aus zwei Teilen. Der erste Teil ist die Blockspeicherpartition, ein Teil mit fester Größe, der Metadaten für den Block enthält. Der zweite Teil ist eine Liste von Transaktionen variabler Größe, die jedoch normalerweise viel größer ist als die Blockspeicherpartition.

Miner müssen Daten wiederholt hashen, um eine Ausgabe zu erzeugen, die bestimmten Bedingungen für das Mining eines gültigen Blocks entspricht. Sie können Billionen Versuche unternehmen, bevor sie den richtigen Block finden. Bei jedem Versuch ändern sie eine Zufallszahl im Speicherbereich des Blocks (den privaten Code), um eine andere Ausgabe zu erzeugen. Ein großer Teil der Masse bleibt jedoch gleich. Die Anzahl der Transaktionen kann Tausende von Transaktionen betragen, und Sie müssen sie jedes Mal hashen.

Der Merkle-Wurzel macht den Prozess viel einfacher. Wenn Sie mit dem Mining beginnen, fügen Sie eine Reihe aller Transaktionen ein, die Sie einbeziehen möchten, und erstellen einen Merkle-Baum. Anschließend platzieren Sie den resultierenden Root-Hash-Wert (32 Byte) in der Blockspeicherpartition. Beim Mining müssen Sie dann nur noch die Blockspeicherpartition und nicht den gesamten Block hashen.

Diese Methode funktioniert, weil sie nicht manipuliert werden kann und alle Blocktransaktionen effektiv in einem kompakten Format zusammenfasst. Und Sie können keine gültige Blockspeicherpartition finden und später die Transaktionsliste ändern, da dies das Merkle-Stammverzeichnis ändern würde. Wenn der Block an andere Knoten gesendet wird, berechnet er die Wurzel aus der Liste der Transaktionen. Wenn sie nicht mit den Angaben im Blockspeicherabschnitt übereinstimmt, wird der Block abgelehnt.

Überprüfung

Es gibt noch eine weitere interessante Eigenschaft der Merkle-Wurzeln, die wir uns zunutze machen können. Diese Funktion ist für einfache Knotensoftware wichtig (Knoten, die nicht die vollständige Kopie der Blockchain-Kette enthalten). Wenn Sie einen Knoten auf einer Maschine mit eingeschränkten Ressourcen betreiben, möchten Sie nicht alle Transaktionen des Blocks herunterladen und hashen. Stattdessen können Sie einen Merkle-Beweis anfordern – einen Beweis, der vom gesamten Knoten bereitgestellt wird und beweist, dass eine Transaktion vorliegt existiert in einem bestimmten Block. Dies wird oft als vereinfachte Zahlungsverifizierung (SPV) bezeichnet und wurde von Satoshi Nakamoto im technischen Bitcoin-Bericht ausführlich erläutert.

Zur Verifizierung von hD benötigen wir lediglich die rot dargestellten Hashwerte.

Betrachten wir zum Beispiel ein Szenario, in dem wir Informationen über eine Transaktion mit der Transaktions-ID hD wissen möchten. Wenn wir den Wert hC zur Verfügung haben, können wir hCD finden. Dann benötigen wir hAB, um hABCD zu berechnen. Schließlich können wir im Fall von hEFGH überprüfen, ob der resultierende Merkle-Stamm mit dem in der Blockspeicherpartition übereinstimmt. Wenn es übereinstimmt, ist dies ein Beweis dafür, dass die Transaktion im Block existierte – da es nahezu unmöglich wäre, denselben Hashwert mit unterschiedlichen Daten zu generieren.

Im vorherigen Beispiel mussten wir den Hash nur dreimal durchführen, und ohne Merkles Beweis hätten wir ihn sieben Mal durchführen müssen. Da Blöcke heute Tausende von Transaktionen enthalten, spart die Verwendung des Merkle-Beweises viel Zeit und Rechenressourcen.

Abschließende Gedanken

Merkle-Bäume haben sich in einer Reihe von Informatikanwendungen als äußerst nützlich erwiesen – und wie wir gesehen haben, sind sie für Blockchains von enormer Bedeutung. In verteilten Systemen erleichtern Merkle-Bäume die Überprüfung von Informationen, ohne das Netzwerk mit einer Flut unnötiger Daten zu überfluten.

Ohne Merkle-Bäume (und Merkle-Wurzeln) wären die Bitcoin- und anderen Kryptowährungsblöcke nicht so klein wie heute. Während es bei einfacher Vertragssoftware an Datenschutz und Sicherheit mangelt, können Benutzer mit Merkle's Proof zu minimalen Kosten überprüfen, ob ihre Transaktionen einem Block beigetreten sind.