Ein Merkle Tree ist eine Methode zur Strukturierung von Daten, mit der eine große Menge an Informationen äußerst schnell und effizient auf ihre Richtigkeit überprüft werden kann. Jeder Merkle-Baum führt zu einer einzelnen Datenzeichenfolge, die als Merkle-Wurzel bezeichnet wird. Mit der Merkle-Wurzel und einigen anderen Daten kann jeder Computer alle anderen Einträge im Merkle-Baum effizient validieren. In der Blockchain-Technologie handelt es sich bei diesen Einträgen um Transaktionsidentifikationsnummern.

Wenn Sie in der Welt der Blockchain tätig sind, ist Ihnen der Begriff „Merkle Tree“ vielleicht schon einmal begegnet. Auch wenn Merkle-Bäume kein weithin verstandenes Konzept sind, sind sie auch nicht besonders kompliziert. Dieser Beitrag erklärt Merkle-Bäume im Klartext und hilft Ihnen zu verstehen, wie sie die Blockchain-Technologie ermöglichen.

Alles über Merkle-Bäume

Die Geschichte von Merkle Trees beginnt im Jahr 1979 mit einem Mann namens Ralph Merkle. Während ihres Studiums an der Stanford University verfasste Merkle eine wissenschaftliche Arbeit mit dem Titel „ A Certified Digital Signature“. In diesem Aufsatz beschrieb Merkle eine Methode zur Erstellung digitaler Signaturen und etablierte eine neue, äußerst effiziente Methode zur Erstellung kryptografischer Beweise. Mit anderen Worten: Er entwarf einen Prozess zur Verifizierung von Daten, der es Computern ermöglichen würde, ihre Arbeit viel, viel schneller als je zuvor zu erledigen.

Merkle nannte seine Idee „Tree Signatures“ oder „Tree Authentication“. Heutzutage ist diese Idee besser bekannt als Merkle Tree, benannt nach dem Erfinder.

Man kann ohne Übertreibung sagen, dass Merkle Trees die Welt der Kryptographie und damit auch die Funktionsweise verschlüsselter Computerprotokolle revolutioniert hat. Tatsächlich werden Merkle Trees wiederholt in Satoshi Nakamotos Aufsatz aus dem Jahr 2008 erwähnt, der Bitcoin der Welt vorstellte. Sie werden im Bitcoin-Protokoll häufig verwendet.

Was genau ist ein Merkle Tree? Lass es uns herausfinden.

Zunächst ist es wichtig, das Konzept einer kryptografischen Hash-Funktion zu verstehen. Einfach ausgedrückt sind Hash-Funktionen irreversible mathematische Funktionen, die eine Eingabe beliebiger Länge – von einem Zeichen bis zum Text einer ganzen Reihe von Enzyklopädien – entgegennehmen und eine zufällige Ausgabe fester Länge erzeugen. Da die Ausgabe zufällig erscheint und eine feste Länge hat, hat ein Angreifer keine Ahnung, welche Eingabe eine bestimmte Ausgabe erzeugt hat. Hash-Funktionen sind außerdem deterministisch, sodass dieselbe Eingabe immer dieselbe Ausgabe erzeugt. Schließlich sind Hash-Funktionen irreversibel, sodass es absolut keine Möglichkeit gibt, eine Eingabe allein aus der Kenntnis der Ausgabe zu ermitteln.

Alle diese Eigenschaften ermöglichen Hash-Funktionen, elektronische Fingerabdrücke einer bestimmten Eingabe zu erstellen. Mithilfe von Hash-Funktionen erstellen Blockchain-Netzwerke einen kryptografischen Hash – einen elektronischen Fingerabdruck – jeder Transaktion. Der kryptografische Hash einer Transaktion wird einfach als Transaktions-ID bezeichnet. Bei fast jedem Blockchain-Protokoll ist jede Transaktions-ID eine alphanumerische Datenfolge mit 64 Zeichen (256 Bit).

Wenn man bedenkt, dass Blockchains typischerweise aus Hunderttausenden Blöcken bestehen, wobei jeder Block mehrere Tausend Transaktionen enthält, kann man sich vorstellen, wie schnell die Überprüfung von Transaktionen rechentechnisch schwierig werden kann. Daher ist es optimal, bei der Verarbeitung und Überprüfung von Transaktionen so wenig Daten wie möglich zu verwenden. Dadurch werden die CPU-Verarbeitungszeiten minimiert und gleichzeitig ein Höchstmaß an Sicherheit gewährleistet.

Genau das tun Merkle Trees. Um es ganz einfach auszudrücken: Merkle Trees nehmen eine große Anzahl von Transaktions-IDs, strukturieren sie auf eine bestimmte Weise und verwenden kryptografische Hash-Funktionen, um eine einzelne alphanumerische Zeichenfolge mit 64 Zeichen abzuleiten, die als elektronischer Fingerabdruck für den gesamten Datenbestand fungiert .

Diese als Merkle Root bezeichnete Datenfolge ist äußerst wichtig, da sie es jedem Computer ermöglicht, schnell und so effizient wie möglich zu überprüfen, ob eine bestimmte Transaktion in einem bestimmten Block stattgefunden hat.

Was ist eine Merkle-Wurzel?

Die einzelne 256-Bit-Zeichenfolge, die ein Merkle-Baum erzeugt, wird Merkle-Wurzel genannt. Jeder Block in einer Blockchain hat genau einen. Und wie wir gerade erwähnt haben, ist die Merkle-Wurzel ein entscheidendes Datenelement, da sie es Computern ermöglicht, Informationen mit unglaublicher Geschwindigkeit und Effizienz zu überprüfen.

Lassen Sie uns etwas tiefer eintauchen. Wie wird eine Merkle-Wurzel hergestellt? Der erste Schritt besteht darin, alle Dateneingaben zu organisieren, in diesem Fall Transaktions-IDs. Merkle Trees gruppieren von Natur aus immer alle Eingaben in Paaren. Bei einer ungeraden Anzahl von Eingängen wird der letzte Eingang kopiert und dann mit sich selbst gepaart. Dies gilt für alle Transaktions-IDs, die in einen Block einer Blockchain geschrieben werden.

Nehmen wir zum Beispiel an, dass ein einzelner Block insgesamt 512 Transaktionen enthält. Der Merkle Tree würde zunächst diese 512 Transaktions-IDs in 256 Paare gruppieren. Dann würden diese 256 Paare von Transaktions-IDs einen mathematischen Prozess durchlaufen – die Hashing-Funktion oder den Hashing-Algorithmus, wie sie manchmal genannt wird – und wir hätten 256 neue kryptografische Hashes mit 64 Zeichen.

Der exakt gleiche Vorgang wiederholt sich erneut. Diese 256 neuen Hashes würden gepaart und in 128 Hashes umgewandelt. Der Vorgang wird wiederholt, wobei die Anzahl der Hashes jedes Mal halbiert wird, bis nur noch ein einziger Hash übrig bleibt. Dieser einzelne Hash ist unser Merkle Root.

Ein einfaches Beispiel für einen Merkle-Baum

Um dieses Konzept zu verdeutlichen, schauen wir uns ein sehr einfaches Beispiel eines Merkle Tree an. Stellen Sie sich vor, dass in einem bestimmten Block 8 Transaktionen durchgeführt wurden. In Wirklichkeit sind Transaktions-IDs 64 Zeichen lang, der Einfachheit halber gehen wir jedoch davon aus, dass sie nur 8 Zeichen lang sind. Um die Sache noch einfacher zu machen, verwenden wir nur Zahlen (und ignorieren Buchstaben ganz).

In diesem Beispiel lauten unsere acht Transaktions-IDs also:

• 11111111
• 22222222
• 33333333
• 44444444
• 55555555
• 66666666
• 77777777
• 88888888

Nehmen wir nun an, dass die Methode zum Zusammenfassen von Transaktions-IDs darin besteht, die erste, dritte, fünfte und siebte Ziffer von jeder der beiden kombinierten IDs zu nehmen und diese Zahlen dann einfach zusammenzufügen, um einen neuen, 8-stelligen Code zu bilden.

Natürlich ist die Mathematik hinter Hashing-Algorithmen in Wirklichkeit weitaus komplizierter. Aber für diese einfache Demonstration wird dieses elementare System ausreichen.

So würde unser Merkle Tree aussehen:

Beachten Sie, dass die Anzahl der Codes bei jedem Schritt im Merkle-Baum halbiert wird. Wir beginnen mit 8 Transaktions-IDs und landen nach nur 3 Schritten bei einem einzigen Code – dem Merkle Root. In diesem Beispiel ist unser Merkle Root der Code im unteren Feld: 12345678.

Der Hauptvorteil von Merkle Trees besteht darin, dass sie eine extrem schnelle Überprüfung von Daten ermöglichen. Wenn wir eine einzelne Transaktions-ID validieren möchten, müssten wir nicht jede einzelne Transaktion im Block noch einmal überprüfen. Vielmehr müssten wir nur diesen bestimmten „Zweig“ unseres Merkle-Baums überprüfen.

Effizienz und Geschwindigkeit: Die Vorteile von Merkle Trees

Nehmen wir an, dass wir in unserem aktuellen Beispiel eine Transaktions-ID validieren möchten. Bob sagt, dass er Alice einen bestimmten Betrag an Bitcoin gezahlt hat und teilt uns mit, dass die Transaktions-ID 88888888 lautet. Er sendet uns auch 3 Hashes: 77777777, 55556666 und 11223344. Das sind alle Informationen, die gesendet oder empfangen werden müssen, um Bobs Zahlung an Alice zu verifizieren.

Diese drei Hashes sind zusammen mit der betreffenden Transaktions-ID und dem Merkle Root dieses bestimmten Blocks die einzigen Daten, die benötigt werden, um Bobs Zahlung an Alice zu verifizieren. Das sind weitaus weniger Daten, als zur Verifizierung des gesamten Merkle-Baums erforderlich wären. Dadurch ist der Verifizierungsprozess für alle viel schneller und weitaus effizienter.

So funktioniert das. Wir haben bereits die Merkle-Wurzel des Blocks, also muss Bob uns diese nicht schicken. Er sendet uns seine Transaktions-ID und die drei oben aufgeführten zusätzlichen Hashes. Er sendet auch eine kleine Information über die Reihenfolge und Platzierung, in der die Hashes verwendet werden sollen. Jetzt müssen wir nur noch den Hashing-Algorithmus für den von Bob bereitgestellten Datensatz ausführen.

Wir beginnen mit dem Hashing des ersten Codes 77777777 mit der Transaktions-ID 88888888, was uns das Ergebnis 77778888 ergibt. Bob hat uns diesen Code nicht geschickt, aber das war auch nicht nötig, da wir denselben Hashing-Algorithmus wie er verwenden. Daher erhalten wir genau die gleichen Ergebnisse.

Dann nehmen wir den zweiten Code, den Bob uns geschickt hat, 55556666, und hashen ihn mit dem neuen Code 77778888, den wir gerade abgeleitet haben. Dies ergibt natürlich die Zahl 55667788.

Schließlich hashen wir den dritten Code, den Bob uns gegeben hat, 11223344, mit dem anderen neuen Code, den wir erhalten haben, 55667788, und am Ende erhalten wir den richtigen Merkle Root: 12345678.

Beachten Sie, dass wir nur drei Codes von Bob benötigen und den Hashing-Algorithmus nur dreimal ausführen mussten, um zu sehen, dass Bobs Transaktion gültig ist. Das bedeutet, dass unser Computer weniger als die Hälfte der Arbeit erledigt hat, die zur Überprüfung des gesamten Merkle-Baums erforderlich gewesen wäre. Das ursprüngliche Merkle-Tree-Diagramm hat 15 Zahlen und der Hashing-Algorithmus muss siebenmal ausgeführt werden. Aber mehr als die Hälfte dieses Baums ist nicht erforderlich, um Bobs Transaktion zu verifizieren!

Validierungsverfahren leicht gemacht mit Merkle Tree

Dieses Verfahren reicht aus, um zu verifizieren, dass Bob Alice tatsächlich diesen bestimmten Bitcoin-Betrag gezahlt hat, da wir Zahlen abgeleitet haben, die, wenn sie mit den anderen Codes, die Bob uns geschickt hat, gehasht wurden, denselben Merkle Root ergaben, von dem wir bereits wussten, dass er wahr ist diesen bestimmten Block.

Bob kann keine Transaktion fälschen, da dies das Finden einer gefälschten Transaktions-ID und eines zusätzlichen Satzes gefälschter Codes erfordern würde, die, wenn sie die Hashing-Funktion durchlaufen, die wahre Merkle-Wurzel ergeben würden. Die Wahrscheinlichkeit, dass dies geschieht, ist so astronomisch gering, dass wir getrost sagen können, dass es unmöglich ist.

In diesem einfachen Beispiel scheinen die Einsparungen an Rechenleistung nicht wesentlich zu sein. Wenn man jedoch bedenkt, dass Blöcke in einer Blockchain mehrere tausend Transaktionen enthalten können, ist es leicht zu erkennen, wie Merkle Trees die Effizienz so dramatisch steigert.

Kurz gesagt, das ist der Hauptvorteil eines Merkle Tree. Es ermöglicht Computern, Informationen äußerst effizient und mit weit weniger Daten zu überprüfen, als ohne den Merkle Tree erforderlich wären.

Merkle Trees sind auch das Grundkonzept der Komodo-Plattform zur Lösung des Blockchain-Skalierbarkeitsproblems. Die Skalierungslösung von Komodo ermöglicht eine vollständige Blockchain-Interoperabilität und wird es Komodo ermöglichen, Transaktionen schneller als jeder andere Zahlungsabwicklungsdienst auf dem Planeten abzuwickeln. Derzeit verarbeitet Komodos neue Skalierungstechnologie in einer Testumgebung über 20.000 Transaktionen pro Sekunde.

Haftungsausschluss:

1. Dieser Artikel wurde von [komodo] nachgedruckt. Alle Urheberrechte liegen beim ursprünglichen Autor [Delton Rhodes]. Wenn Sie Einwände gegen diesen Nachdruck haben, wenden Sie sich bitte an das Gate Learn- Team, das sich umgehend darum kümmern wird.
2. Haftungsausschluss: Die in diesem Artikel geäußerten Ansichten und Meinungen sind ausschließlich die des Autors und stellen keine Anlageberatung dar.
3. Übersetzungen des Artikels in andere Sprachen werden vom Gate Learn-Team durchgeführt. Sofern nicht anders angegeben, ist das Kopieren, Verbreiten oder Plagiieren der übersetzten Artikel verboten.