Kryptografische Werkzeuge 101 – Hashfunktionen und Merkle-Bäume erklärt

Worum geht es in diesem Artikel?

Blockchains ermöglichen es Menschen, sich ohne Vermittler auf Dinge zu einigen. Statt auf Vertrauen setzen Blockchains auf kryptografische Beweise. Kryptografische Primitive liefern diese Beweise. Aber was sind sie?

In diesem Artikel betrachten wir zwei kryptografische Primitive, die für kryptografische Beweise auf Blockchains unverzichtbar sind: Hashfunktionen und Merkle-Bäume. Wir untersuchen die grundlegende Funktionsweise von Hashfunktionen, zeigen ihre Bedeutung für Blockchains und erklären Hashzeiger. Anschließend betrachten wir klassische und nebenläufige Merkle-Bäume und erläutern ihre Bedeutung für Solana.

Was ist ein kryptografisches Primitiv?

Ein kryptografisches Primitiv ist eine Operation oder ein Algorithmus, der als Grundlage für kryptografische Protokolle und Systeme dient. Kryptografische Primitive verhalten sich zu kryptografischen Protokollen wie Atome zu Molekülen: Sie sind die Bausteine für komplexere Lösungen. Zufallszahlengeneratoren, Commitment-Verfahren und Public-Key-Kryptografie sind Beispiele für kryptografische Primitive.

Für sich genommen sind kryptografische Primitive recht begrenzt. Kombiniert stellen sie grundlegende Sicherheitsfunktionen wie Authentifizierung, Vertraulichkeit und Integrität bereit. Das Kombinieren kryptografischer Primitive ist ein nuancierter Prozess. Er erfordert sorgfältige Planung und ein tiefes Verständnis dafür, wie die einzelnen Primitive miteinander interagieren. Dabei musst du die Sicherheitsaspekte im Hinblick auf deine angestrebten Sicherheitsziele berücksichtigen. Die Methoden zum Kombinieren kryptografischer Primitive lassen sich grob wie folgt einteilen:

• Sequenzielle Komposition: Ein Primitiv nach dem anderen anwenden (z. B. Hashverkettung)
• Parallele Komposition: Primitive gleichzeitig und unabhängig voneinander verwenden (z. B. Daten gleichzeitig verschlüsseln und hashen)
• Hierarchische Komposition: Ein kryptografisches Primitiv innerhalb eines anderen verwenden (z. B. Merkle-Bäume)

Wenn du verstehst, was kryptografische Primitive sind, wie sie funktionieren und welche Feinheiten ihre Kombination mit sich bringt, kannst du sichere und effiziente Systeme verstehen und entwerfen. Eines der am häufigsten verwendeten und kombinierten kryptografischen Primitive ist die Hashfunktion.

Was ist eine Hashfunktion?

Eine Hashfunktion ist eine kryptografische Funktion, die Daten beliebiger Größe entgegennimmt und einen Wert fester Größe zurückgibt. Der zurückgegebene Wert wird als Digest oder Hash bezeichnet. Zu den bekannten Hashalgorithmen gehören SHA-1, SHA-2, SHA-3, MD5 und Argon2. Hashfunktionen kommen überall in Blockchains zum Einsatz. Deshalb ist es entscheidend, dass du verstehst, was sie sind und wie sie funktionieren.

Eine einfache Analogie

Stell dir vor, du backst eine aufwendige Schokoladentorte. Die Torte hat mehrere Schichten, für die jeweils eigene Zutaten verwendet werden. Während du backst, schreibt dir ein Freund und fragt, was du gerade machst. Ihm ausführlich zu erklären, wie du die Torte gebacken und welche Zutaten du verwendet hast, wäre ziemlich umständlich. Stattdessen schickst du ihm ein Bild der Schokoladentorte.

Das Bild der Torte dient hier als Hash: Es ist eine einfache, kompakte Darstellung von etwas viel Komplexerem. Dein Freund kennt damit zwar nicht jede einzelne Zutat der Torte, hat aber eine gute Vorstellung davon, was du gerade gebacken hast. Angenommen, auf deiner Schokoladentorte liegen Himbeeren. Wenn du sie entfernst oder durch Erdbeeren ersetzt, unterscheidet sich das Bild deiner Torte vollständig vom Endprodukt. Genauso erzeugt jede Änderung an den gehashten Daten einen neuen Hashwert.

Eigenschaften einer guten kryptografischen Hashfunktion

Zugegeben, die zuvor genannte Definition einer Hashfunktion ist irreführend. Eine Hashfunktion könnte einen Hash variabler Größe zurückgeben. Sie könnte auch für zwei unterschiedliche Eingaben denselben Hash liefern. Außerdem könnte es extrem einfach sein, aus dem Hash die ursprüngliche Eingabe zu rekonstruieren. Die frühere Definition bezog sich auf eine gute kryptografische Hashfunktion. Doch was macht eine kryptografische Hashfunktion zu einer guten kryptografischen Hashfunktion?

Eine gute Hashfunktion ist deterministisch: Dieselbe Eingabe erzeugt immer dieselbe Ausgabe. Wenn ich die Eingabe „baseball“ hashe, gibt diese Hashfunktion unabhängig vom System jedes Mal denselben Hash aus. Das bedeutet teilweise auch, dass der Hash unabhängig von der Größe der Eingabe immer gleich groß ist. Das ist wichtig für eine effiziente Verarbeitung und Datenspeicherung. Wenn eine eindeutige Eingabe immer eine eindeutige Ausgabe erzeugt und diese Ausgaben stets eine feste Größe haben, deutet das klar auf eine gute kryptografische Hashfunktion hin.

Eine gute Hashfunktion ist resistent gegen Urbildangriffe. Das bedeutet, dass es rechnerisch nicht praktikabel ist, den Eingabewert anhand seines Hashs zu rekonstruieren. Wenn dir also jemand einen Hash gibt, solltest du nicht herausfinden können, welche Daten diesen Hash erzeugen. Daraus folgt auch, dass zwei unterschiedliche Datensätze nicht denselben Hash erzeugen sollten. Eine gute Hashfunktion gilt als kollisionsresistent, wenn zwei beliebige Eingaben niemals denselben Hash erzeugen.

Eine gute Hashfunktion folgt dem Lawineneffekt: Eine kleine Änderung an der Eingabe sollte zu einem drastisch anderen Hash führen. Selbst die Änderung eines einzigen Zeichens sollte einen völlig anderen Hash erzeugen. Eine Hashausgabe sollte daher weder Informationen über die Eingabe preisgeben noch erkennbare Muster enthalten. Beachte die unterschiedlichen Hashes in der Abbildung oben. Der rote Fuchs, der „rennt“, erzeugt einen grundlegend anderen Hash als der rote Fuchs, der „geht“. Außerdem deutet nichts darauf hin, dass diese beiden Hashes nahezu identische Informationen enthalten.

Eine gute Hashfunktion sollte sich schnell berechnen lassen. Langsame Hashfunktionen sind für Berechnungen in Echtzeit oder nahezu in Echtzeit, etwa bei der Verifizierung von Transaktionen, nicht praktikabel. Eine langsame Hashfunktion könnte zu einem erheblichen Engpass werden und sowohl den Durchsatz als auch die Netzwerkleistung begrenzen. Eine schnelle Hashfunktion ist für einen effizienten und sicheren Betrieb auf der Blockchain erforderlich.

Warum ist das für Blockchains wichtig?

Eine Blockchain ist ein dezentrales, verteiltes Hauptbuch, das Transaktionen in ihrem Netzwerk aufzeichnet. Diese Transaktionen werden in Blöcken gruppiert, die über eine gute Hashfunktion sicher miteinander verknüpft sind. Jeder Block enthält Transaktionsdaten, einen Zeitstempel und den Hash des vorherigen Blocks. Da der Hash jedes Blocks vom Hash des vorherigen Blocks abhängt, würde jede Änderung am Inhalt eines Blocks dessen Hash verändern und alle nachfolgenden Blöcke ungültig machen. Dieser Prozess, bei dem vorherige Hashes zur Erzeugung eines neuen Hashs verwendet werden, wird als Hashverkettung bezeichnet.

Das Hinzufügen eines neuen Blocks zu einer Blockchain wird als Bestätigung bezeichnet. Eine Bestätigung verifiziert und sichert alle Transaktionen im neuen Block sowie alle vorherigen Blöcke. Denn mit jeder neuen Bestätigung wird es schwieriger, vorherige Blöcke zu verändern. Um einen vorherigen Block zu verändern, müsste ein Angreifer alle nachfolgenden Hashes neu berechnen. Die Hashverkettung sorgt daher dafür, dass eine Änderung der Blockchain nicht praktikabel ist, sobald ein Block eine beträchtliche Anzahl von Bestätigungen aufweist.

Einfach gesagt ist eine Blockchain eine Kette von Blöcken, die durch Hashfunktionen gesichert wird. Aber wie verweisen wir genau von einem Block auf einen anderen? Ja, eine kryptografische Hashfunktion verkettet die Blöcke miteinander. Doch wie können wir die Daten vorheriger Blöcke einsehen? Eine gute kryptografische Hashfunktion sollte doch resistent gegen Urbildangriffe sein.

Was ist ein Hashzeiger?

Ein Zeiger ist eine Variable, die den Speicherort bestimmter Daten enthält. Auf die Daten an dieser Speicheradresse lässt sich einfach zugreifen, da der Zeiger auf ihren Speicherort „zeigt“. Ein Hashzeiger ist eine Datenstruktur, die einem Zeiger ähnelt, aber zusätzlich einen kryptografischen Hash der referenzierten Daten enthält. Ein Hashzeiger zeigt dir somit, wo du auf bestimmte Daten zugreifen kannst, und ermöglicht dir, die Integrität der abgerufenen Daten zu prüfen.

Die Struktur einer Blockchain lässt sich genauer als verkettete Liste beschreiben, die Hashzeiger verwendet. Der Hash des vorherigen Blocks ist ein Hashzeiger, der auf eine Reihe von Transaktionen und einen Hash all dieser Transaktionen verweist. Hashzeiger ermöglichen die Verknüpfung von Blöcken, sichern die Integrität jedes Blocks und helfen zu prüfen, ob neu hinzugefügte Blöcke korrekt auf die vorherigen Blöcke folgen.

Hashzeiger verketten Blöcke effizient miteinander. Aber was ist mit den Transaktionen im Block? Wenn ein Block tausend Transaktionen enthält, wäre es dann nicht teuer, diese Transaktionen einzeln zu verifizieren?

Was ist ein Merkle-Baum?

Ein Merkle-Baum ist eine Datenstruktur zum Organisieren und Verifizieren großer Datenmengen. Die Daten werden in einer baumartigen Struktur organisiert, in der jedes Blatt beziehungsweise jeder Knoten mit dem Hash eines Datensatzes gekennzeichnet ist. Jeder Knoten, der kein Blatt ist, enthält einen Hash seiner untergeordneten Knoten. Merkle-Bäume werden verwendet, um Transaktionen zu verifizieren, die in bestimmten an die Blockchain weitergegebenen Blöcken enthalten sind. Wie funktioniert das also?

Transaktionen werden in einer Liste gebündelt und bilden einen Block. Jede Transaktion in der Liste wird mit einer guten Hashfunktion gehasht. Diese Hashes dienen als Blattknoten. Die Blattknoten werden paarweise zusammen gehasht, um eine neue Ebene von Hashes zu erzeugen. Dieser Prozess wird iterativ fortgesetzt, bis nur noch ein einzelner Hash übrig ist: die Merkle-Wurzel. Die Merkle-Wurzel wird im Header des Blocks gespeichert und dient als digitaler Fingerabdruck aller Transaktionen in diesem Block. Wir können die Merkle-Wurzel auch als Hash des Blocks bezeichnen. Wenn wir also sagen, dass ein neuer Block über den Blockhash des vorherigen Blocks mit diesem verknüpft ist, bedeutet das, dass der neue Block die Merkle-Wurzel des vorherigen Blocks als Teil seines Hashs verwendet.

Merkle-Bäume ermöglichen die effiziente Verifizierung einzelner Transaktionen innerhalb eines Blocks. Traditionell müsstest du jede Transaktion verifizieren, um eine bestimmte Transaktion zu prüfen. Das ist teuer und zeitaufwendig. Merkle-Bäume stellen für diesen Verifizierungsprozess eine kryptografische „Abkürzung“ bereit, den sogenannten Merkle-Beweis. Ein Merkle-Beweis ist ein Pfad vom Blattknoten der Transaktion bis hinauf zur Merkle-Wurzel. In der obigen Abbildung kannst du ihn dir als Pfad von Daten A zur Merkle-Wurzel vorstellen. Dieser Pfad umfasst auch die Geschwisterknoten: die Blätter, die an jeden Knoten des Pfads angrenzen, aber selbst nicht Teil des Pfads sind. Ein Verifizierer kann mithilfe des Beweispfads einen Hash berechnen und prüfen, ob dieser mit der Merkle-Wurzel übereinstimmt. Stimmen die Hashes überein, kann der Verifizierer davon ausgehen, dass die Transaktion legitim ist und nicht manipuliert wurde.

Ein Blatt lässt sich ändern, indem die neuen Daten des Blatts gehasht und die Merkle-Wurzel neu berechnet werden. Diese neue Merkle-Wurzel dient zur Verifizierung der neuen Änderungen und macht den vorherigen Beweis ungültig. In einem Netzwerk mit hohem Durchsatz wie Solana können Validatoren in schneller Folge Änderungsanfragen für On-Chain-Merkle-Bäume empfangen, zum Beispiel innerhalb desselben Slots. Jede Datenänderung müsste sequenziell neu berechnet werden. Andernfalls würde jede nachfolgende Änderungsanfrage durch die vorherige, im selben Slot vorgenommene Änderungsanfrage ungültig. Blattdaten zu ändern und eine neue Merkle-Wurzel zu berechnen, ist bei Blockchains sehr üblich. Wie gehen wir also mit schnellen Änderungen um?

Was ist ein nebenläufiger Merkle-Baum?

Ein nebenläufiger Merkle-Baum ist ein Merkle-Baum, der für nebenläufige Lese- und Schreibvorgänge optimiert ist. Er speichert ein sicheres Änderungsprotokoll der neuesten Änderungen, deren Wurzel-Hash und den Beweis, mit dem er sich ableiten lässt. Dieses Änderungsprotokoll wird On-Chain in einem baumspezifischen Account gespeichert. Es legt die maximale Anzahl von Änderungen fest, die am Baum vorgenommen werden können, während die Merkle-Wurzel weiterhin gültig bleibt. Diese maximale Anzahl von Änderungen wird als maxBufferSize bezeichnet. Wenn ein Validator in schneller Folge Änderungsanfragen für einen On-Chain-Merkle-Baum erhält, kann er dieses Änderungsprotokoll als zuverlässige Datenquelle verwenden. So sind im selben Slot bis zu maxBufferSize Änderungen am Baum möglich.

Nebenläufige Merkle-Bäume verbessern klassische Merkle-Bäume und eignen sich damit für Umgebungen mit hohem Durchsatz wie Solana. Wenn du auf Solana einen nebenläufigen On-Chain-Merkle-Baum erstellst, beeinflussen drei Eigenschaften die Größe des Baums, die Kosten für seine Erstellung und die Anzahl nebenläufiger Änderungen:

• Maximale Tiefe
• Maximale Puffergröße
• Canopy-Tiefe

Die maximale Tiefe bezeichnet die maximale Anzahl von Schritten, die nötig sind, um von einem beliebigen Blatt zur Merkle-Wurzel zu gelangen. maxDepth bestimmt die maximale Anzahl der im Baum gespeicherten Knoten. Du kannst sie mit folgender Formel berechnen: numberOfNodes = 2 ^ maxDepth. Die Tiefe eines Baums muss bei seiner Erstellung festgelegt werden. Verwende deshalb diese Formel, um zu bestimmen, wie viele Datenelemente der Baum speichern soll.

Wie bereits erwähnt, bezeichnet die maximale Puffergröße die maximale Anzahl von Änderungen, die an einem Baum vorgenommen werden können, während seine Merkle-Wurzel weiterhin gültig bleibt.

Die Canopy-Tiefe bezeichnet einen Teil des Merkle-Baums, der On-Chain gespeichert wird. Diese zwischengespeicherten Beweise dienen dazu, einen Hash mit der On-Chain-Merkle-Wurzel abzugleichen. Beim Schreiben in ein Blatt muss der vollständige Beweispfad verwendet werden, um dessen ursprünglichen Besitz zu verifizieren. Du würdest beispielsweise in den Baum schreiben, wenn du ein NFT überträgst. Mit dem Canopy kannst du den Beweis verkleinern und vermeiden, für die Verifizierung des Baums eine Beweisgröße von maxDepth verwenden zu müssen. Ein Baum mit einer maxDepth von 20 würde eine Beweisgröße von 20 erfordern. Mit einem Canopy von 15 muss pro Schreibtransaktion nur eine Beweisgröße von 5 übermittelt werden. Eine größere Canopy-Tiefe verursacht somit höhere Anfangskosten, ermöglicht dir später aber die Übermittlung kleinerer Beweise.

Die Canopy-Tiefe ist einer der wichtigsten Kostenfaktoren beim Erstellen eines Baums. Denn je größer die Canopy-Tiefe ist, desto größer muss der Account sein. Entwickler können mit dem @solana/spl-account-compression-Paket den erforderlichen Speicherplatz für eine bestimmte Baumgröße und die Kosten für dessen On-Chain-Zuweisung berechnen. Mit der Funktion getConcurrentMerkleTreeAccountSize können Entwickler anhand der Parameter eines Accounts den erforderlichen Speicherplatz berechnen. Anschließend können sie getMinimumBalanceForRentExemption auf den benötigten Speicherplatz anwenden, um die endgültigen Kosten in Lamports zu ermitteln.

Solana nutzt nebenläufige Merkle-Bäume für die Zustandskomprimierung. Bei der Zustandskomprimierung wird ein Hash von Off-Chain-Daten erstellt und zur sicheren Verifizierung On-Chain gespeichert. Der bekannteste Anwendungsfall für die Zustandskomprimierung sind komprimierte NFTs, da sie die Minting-Kosten drastisch senken. So würde das Minten von einer Milliarde NFTs auf Solana 507 $SOL kosten, verglichen mit 12 000 000 $SOL bei „regulären“ NFTs. Da du nun Hashing und Merkle-Bäume gut verstehst, befassen wir uns in einem kommenden Artikel mit komprimierten NFTs!

Fazit

Glückwunsch! In diesem Artikel haben wir Hashfunktionen und Merkle-Bäume analysiert, zwei für Blockchains unverzichtbare kryptografische Primitive. Blockchains zu verstehen, ist keine Kleinigkeit. Sie sind komplexe verteilte Systeme, die ein breites technisches Verständnis erfordern. Bei durchschnittlichen Entwicklern, Nutzern oder Investoren wird dieses Wissen häufig vorausgesetzt. Dieser Artikel setzt keine Vorkenntnisse über kryptografische Primitive voraus. Stattdessen beginnen wir mit den Grundlagen und gehen anschließend zu komplexeren Erläuterungen klassischer und nebenläufiger Merkle-Bäume über. Dieses grundlegende Verständnis ist entscheidend, wenn wir uns mit komplexeren Themen wie komprimierten NFTs beschäftigen. Mit diesem neuen Wissen bist du besser darauf vorbereitet, dich in Codebasen oder Diskussionen über kryptografische Primitive und komplexere kryptografische Lösungen zurechtzufinden.

Wenn du bis hierher gelesen hast, Anon: Danke!

Zusätzliche Ressourcen und weiterführende Literatur

• Ausführliches Buchkapitel über kryptografische Primitive
• Artikel zum Vergleich sicherer Hashalgorithmen
• Hashalgorithmen und Sicherheit – YouTube-Video von Computerphile
• Kurzes YouTube-Video über Merkle-Bäume
• NFT-Komprimierung auf Solana erkunden