Was ist ein Merkle-Baum? Einsteigerleitfaden zu dieser Blockchain-Komponente

Merkle Trees sind ein grundlegender Bestandteil von Blockchains, der deren Funktionalität untermauert. Sie ermöglichen eine effiziente und sichere Verifizierung großer Datenstrukturen und im Fall von Blockchains potenziell grenzenloser Datensätze.

Die Implementierung von Merkle-Bäumen in Blockchains hat mehrere Auswirkungen. Es ermöglicht ihnen eine Skalierung und bietet gleichzeitig die Hash-basierte Architektur zur Aufrechterhaltung der Datenintegrität und eine einfache Möglichkeit, die Integrität von Daten zu überprüfen.

Kryptografische Hash-Funktionen sind die zugrunde liegende Technologie, die das Funktionieren von Merkle-Bäumen ermöglicht. Daher ist es zunächst wichtig zu verstehen, was kryptografische Hash-Funktionen sind.

Schnelles Urteil: Merkle-Bäume sind Datenstrukturen aus kryptografischen Hashes, die eine effiziente Integritätsüberprüfung und Zuordnung großer Datensätze ermöglichen und sie zu einem integralen Bestandteil von Systemen wie Blockchains und verteilter Versionskontrolle machen.

Fakten

Kryptografische Hash-Funktionen

Einfach ausgedrückt ist eine Hash-Funktion jede Funktion, die verwendet wird, um Daten einer beliebigen Größe (Eingabe) einer Ausgabe mit fester Größe zuzuordnen. Auf die Dateneingabe wird ein Hashing-Algorithmus angewendet und die resultierende Ausgabe fester Länge wird als Hash bezeichnet.

Viele Hashing-Algorithmen sind weithin öffentlich verfügbar und können je nach Bedarf ausgewählt werden.

Der resultierende Hash aus der willkürlichen Eingabe hat nicht nur eine feste Länge, er ist auch völlig einzigartig für die Eingabe und die Funktion selbst ist deterministisch. Das heißt, egal wie oft Sie die Funktion für dieselbe Eingabe ausführen, die Ausgabe ist immer dieselbe.

Wenn Sie beispielsweise die folgenden Datensätze als Eingabe haben, sind die resultierenden Ausgaben für jede Eingabe eindeutig. Beachten Sie, dass im zweiten und dritten Beispiel die resultierenden Ausgaben völlig unterschiedlich sind, obwohl der Unterschied der Eingaben nur ein Wort beträgt.

Dies ist sehr wichtig, da es das „Fingerabdrucken“ von Daten ermöglicht.

Eine kryptografische Hash-Funktion, Bild aus Wikipedia

Da die Ausgabelänge (im Beispiel die Hash-Summe) immer mit der Länge des verwendeten Hashing-Algorithmus übereinstimmt, können große Datenmengen allein über den resultierenden Hash identifiziert werden.

Bei Systemen, die riesige Datenmengen enthalten, können die Vorteile der Speicherung und Identifizierung von Daten mit einer Ausgabe fester Länge zu enormen Speichereinsparungen führen und zur Effizienzsteigerung beitragen.

Innerhalb von Blockchains werden Hashing-Algorithmen verwendet, um den Zustand der Blockchain zu ermitteln.

Blockchains sind verknüpfte Listen, die Daten und einen Hash-Zeiger enthalten, der auf den vorherigen Block zeigt und so eine Kette verbundener Blöcke erstellt, daher der Name „Blockchain“.

Jeder Block ist über einen Hash-Zeiger miteinander verbunden. Dabei handelt es sich um den Hash der Daten im vorherigen Block zusammen mit der Adresse des vorherigen Blocks. Durch die Verknüpfung von Datenblöcken in diesem Format stellt jeder resultierende Hash des vorherigen Blocks den gesamten Zustand der Blockchain dar, da alle gehashten Daten der vorherigen Blöcke in einem Hash gehasht werden.

Dies wird (im Fall des SHA-256-Algorithmus) durch eine Ausgabe (Hash) wie diese dargestellt:

b09a57d476ea01c7f91756adff1d560e579057ac99a28d3f30e259b30ecc9dc7

Der obige Hash ist der Fingerabdruck des gesamten Zustands der Blockchain davor. Der Zustand der Blockchain vor dem neuen Block (als gehashte Daten) ist die Eingabe und der resultierende Hash ist die Ausgabe.

Obwohl es möglich ist, kryptografische Hashes ohne Merkle-Bäume zu verwenden, ist dies äußerst ineffizient und nicht skalierbar. Die Verwendung von Hashes zum Speichern von Daten in einem Block in einem Serienformat ist zeitaufwändig und umständlich.

Wie Sie sehen werden, ermöglichen Merkle-Bäume eine triviale Lösung der Datenintegrität sowie die Abbildung dieser Daten im gesamten Baum mithilfe von Merkle-Beweisen.

Merkle-Bäume und Merkle-Beweise

Benannt nach Ralph Merkle, der das Konzept 1979 patentieren ließ, handelt es sich bei Merkle-Bäumen im Wesentlichen um Datenstrukturbäume, bei denen jeder Nicht-Blattknoten ein Hash seiner jeweiligen untergeordneten Knoten ist.

Die Blattknoten sind die unterste Knotenebene im Baum. Auf den ersten Blick mag es schwierig klingen, es zu verstehen, aber wenn Sie sich die häufig verwendete Abbildung unten ansehen, wird es viel einfacher, es zu verstehen.

Ein Beispiel für einen binären Hash-Baum, Bild aus Wikipedia

Beachten Sie vor allem, dass die Nicht-Blattknoten oder „Zweige“ (dargestellt durch Hash 0-0 und Hash 0-1) auf der linken Seite Hashes ihrer jeweiligen untergeordneten Knoten L1 und L2 sind. Beachten Sie außerdem, dass Zweig-Hash 0 der Hash seiner verketteten Kinder, Zweige Hash 0-0 und Hash 0-1, ist.

Das obige Beispiel ist die häufigste und einfachste Form eines Merkle-Baums, der als binärer Merkle-Baum bekannt ist. Wie Sie sehen können, gibt es einen Top-Hash, der der Hash des gesamten Baums ist und als Root-Hash bezeichnet wird. Merkle-Bäume sind im Wesentlichen eine Datenstruktur, die „n“ Hashes aufnehmen und diese durch einen einzigen Hash darstellen kann.

Die Struktur des Baums ermöglicht eine effiziente Zuordnung beliebig großer Datenmengen und ermöglicht eine einfache Identifizierung, wo Änderungen in diesen Daten auftreten. Dieses Konzept ermöglicht Merkle-Beweise, mit denen jemand überprüfen kann, ob das Hashing der Daten über den gesamten Baum hinweg konsistent ist und sich an der richtigen Position befindet, ohne sich tatsächlich den gesamten Hash-Satz ansehen zu müssen.

Stattdessen können sie überprüfen, ob ein Datenblock mit dem Root-Hash übereinstimmt, indem sie nur eine kleine Teilmenge der Hashes und nicht den gesamten Datensatz überprüfen.

Solange der Root-Hash öffentlich bekannt und vertrauenswürdig ist, kann jeder, der eine Schlüsselwertsuche in einer Datenbank durchführen möchte, einen Merkle-Proof verwenden, um die Position und Integrität eines Datenelements in einer Datenbank zu überprüfen eine bestimmte Wurzel.

Wenn der Root-Hash verfügbar ist, kann der Hash-Baum von jeder nicht vertrauenswürdigen Quelle empfangen und jeweils ein Zweig des Baums mit sofortiger Überprüfung der Datenintegrität heruntergeladen werden, auch wenn der gesamte Baum noch nicht verfügbar ist.

Einer der wichtigsten Vorteile der Merkle-Baumstruktur ist die Möglichkeit, beliebig große Datenmengen durch einen ähnlichen Hashing-Mechanismus zu authentifizieren, der zur Überprüfung viel kleinerer Datenmengen verwendet wird.

Der Baum ist vorteilhaft für die Aufteilung großer Datensätze in überschaubare kleinere Teile, bei denen die Hürde für die Überprüfung der Integrität trotz der insgesamt größeren Datengröße erheblich verringert wird.

Der Root-Hash kann als Fingerabdruck für einen gesamten Datensatz, einschließlich einer gesamten Datenbank, verwendet werden oder den gesamten Zustand einer Blockchain darstellen. In den folgenden Abschnitten werden wir diskutieren, wie Bitcoin und andere Systeme Merkle-Bäume implementieren.

Merkle-Bäume in Bitcoin

Die von Bitcoin verwendete kryptografische Hash-Funktion ist der SHA-256-Algorithmus. Dies steht für „Secure Hashing Algorithm“, dessen Ausgabe eine feste Länge von 256 Bit hat. Die Grundfunktion von Merkle-Bäumen in Bitcoin besteht darin, Transaktionen in jedem Block zu speichern und schließlich zu bereinigen.

Wie bereits erwähnt, sind Blöcke in einer Blockchain durch Hashes des vorherigen Blocks verbunden. Bei Bitcoin enthält jeder Block alle Transaktionen innerhalb dieses Blocks sowie den Blockheader, der aus Folgendem besteht:

• Blockversionsnummer
• Vorheriger Block-Hash
• Timestamp
• Ziel für den Schwierigkeitsgrad „Bergbau“.
• Nonce
• Merkle Root Hash

Das Bild unten stammt aus dem Bitcoin-Whitepaper und zeigt, wie der Merkle-Baum in jeden Block passt.

Die Transaktionen werden von Minern in Blöcke eingefügt und als Teil eines Merkle-Baums gehasht, was zur Merkle-Wurzel führt, die im Block-Header gespeichert ist. Dieses Design bietet eine Reihe deutlicher Vorteile.

Wie im Whitepaper dargelegt, ermöglicht dies vor allem die Existenz von SPV-Knoten (Simple Payment Verification), auch bekannt als „Lightweight Clients“. Diese Knoten müssen nicht die gesamte Bitcoin-Blockchain herunterladen, sondern nur die Blockheader der längsten Kette.

SPV-Knoten können dies erreichen, indem sie ihre Peer-Knoten abfragen, bis sie überzeugt sind, dass die gespeicherten Blockheader, mit denen sie arbeiten, Teil der längsten Kette sind. Ein SPV-Knoten ist dann in der Lage, den Status einer Transaktion zu bestimmen, indem er den Merkle-Proof verwendet, um die Transaktion einem bestimmten Merkle-Baum zuzuordnen, wobei der Root-Hash dieses jeweiligen Merkle-Baums in einem Blockheader enthalten ist, der Teil der längsten Kette ist.

Darüber hinaus ermöglicht die Implementierung von Merkle-Bäumen durch Bitcoin das Beschneiden der Blockchain, um Platz zu sparen. Dies liegt daran, dass nur der Root-Hash im Block-Header gespeichert wird. Daher können alte Blöcke beschnitten werden, indem unnötige Zweige des Merkle-Baums entfernt werden, während nur diejenigen erhalten bleiben, die für den Merkle-Beweis benötigt werden.

Implementierung von Merkle Trees in anderen Blockchains und Systemen

Obwohl Bitcoin die erste Blockchain war, die Merkle-Bäume implementierte, implementieren viele andere Blockchains ähnliche Merkle-Baumstrukturen oder sogar komplexere Versionen.

Darüber hinaus ist die Implementierung des Merkle-Baums nicht nur auf Blockchains beschränkt, sondern wird auch auf eine Vielzahl anderer Systeme angewendet.

Ethereum, die andere bekannteste Kryptowährung, ist auch ein großartiges Beispiel für eine andere Merkle-Tree-Implementierung. Da Ethereum als Plattform für die Erstellung viel komplexerer Anwendungen vollständig ist, verwendet es eine komplexere Version des Merkle-Baums namens Merkle-Patricia-Baum, bei dem es sich tatsächlich um drei separate Merkle-Bäume handelt, die für drei Arten von Objekten verwendet werden. Mehr über diese Bäume erfahren Sie hier.

Schließlich sind Merkle-Bäume ein wichtiger Bestandteil verteilter Versionskontrollsysteme wie Git und IPFS. Ihre Fähigkeit, die Integrität von Daten, die zwischen Computern im P2P-Format ausgetauscht werden, einfach sicherzustellen und zu überprüfen, macht sie für diese Systeme von unschätzbarem Wert.

Zusammenfassung

Merkle-Bäume sind ein integraler Bestandteil von Blockchains und ermöglichen ihnen effektiv, mit nachweisbarer Unveränderlichkeit und Transaktionsintegrität zu funktionieren.

Das Verständnis der Rolle, die sie in verteilten Netzwerken spielen, und der ihnen zugrunde liegenden Technologie der kryptografischen Hash-Funktionen ist entscheidend für das Verständnis der grundlegenden Konzepte innerhalb von Kryptowährungen, während diese sich immer weiter zu größeren und komplexeren Systemen entwickeln.