Schritt 11: Hashfunktionen in der Realität

Vom Datenvergleich und dem Erstellen von Berechnungsaufgaben

In Schritt 10 haben wir kryptographische Hashfunktionen vorgestellt und unterschiedliche Schemata zum Anwenden von Hashfunktionen auf Daten behandelt. Vielleicht sind Ihnen diese Ausführungen als recht trockene gedankliche Übung erschienen, tatsächlich sind sie jedoch von hoher praktischer Relevanz. Im vorliegenden Schritt konzentrieren wir uns auf die Anwendung von Hashfunktionen und Hashwerten in der Realität. Hier werden die wichtigsten Anwendungsfälle für Hashfunktionen im echten Leben betrachtet und die Idee dahinter erläutert. Es wird auch umrissen, warum diese Anwendungsfälle wie geplant funktionieren. Und schließlich lernen Sie in diesem Schritt, wo in der Blockchain Hashwerte verwendet werden.

Vergleichen von Daten

Das Vergleichen von Daten anhand ihrer Hashwerte ist der gängigste Anwendungsfall für Hashwerte, daher wird er hier zuerst betrachtet.

Das Ziel

Das Ziel​ besteht darin, Daten (zum Beispiel Dateien oder Transaktionsdaten) zu vergleichen, ohne dafür jedes einzelne Inhaltsbit gegenüberstellen zu müssen. Es soll auch möglich sein, Daten ungeachtet ihrer Art, ihrer Größe und ihres Inhalts so einfach miteinander abzugleichen wie zwei simple Zahlen.

Die Idee​

Statt Daten durch den stückweisen Abgleich der Inhalte gegenüberzustellen, werden die kryptographischen Hashwerte verglichen.

Funktionsweise

Sie berechnen und vergleichen den kryptographischen Hashwert aller untersuchten Daten. Sofern sich die kryptographischen Hashwerte voneinander unterscheiden, weisen auch die untersuchten Daten Unterschiede auf. Sind zwei oder mehr kryptographische Hashwerte identisch, sind auch die zugehörigen Eingabedaten identisch.[1]

Warum das funktioniert

Das Vergleichen von Daten anhand des Vergleichs der zugehörigen kryptographischen Hashwerte funktioniert aufgrund der Kollisionsresistenz oder Kollisionssicherheit der kryptographischen Hashfunktionen.

Erkennen von Änderungen an Daten

Die Idee​, Daten anhand ihrer Hashwerte zu vergleichen, lässt sich problemlos auf das Erkennen von Änderungen erweitern.

Das Ziel

Das Ziel​ besteht darin, zu erkennen, ob Daten (zum Beispiel eine Datei oder Transaktionsdaten), die unverändert bleiben sollen, nach einem bestimmten Datum oder nach dem Speichern in einer Datenbank geändert wurden.

Die Idee

Das Vergleichen des in der Vergangenheit erstellten kryptographischen Hashwerts der betrachteten Daten mit einem neu erzeugten kryptographischen Hashwert derselben Daten ist der Schlüssel zum Erkennen von Änderungen. Sind beide Hashwerte identisch, wurden die Daten nach dem Erzeugen des alten Hashwerts nicht geändert.

Funktionsweise

Sie erzeugen den kryptographischen Hashwert der Daten, die nicht verändert werden sollen. Um zu einem späteren Zeitpunkt zu prüfen, ob die Daten dennoch geändert wurden, führen Sie eine weitere Hashwerterzeugung dieser Daten durch. Anschließend vergleichen Sie den neuen Hashwert mit dem zuvor erzeugten. Sind sie identisch, wurden die Daten nach dem Erzeugen des ersten Hashwerts nicht verändert – andernfalls war dies zwischenzeitlich doch der Fall. Dieselbe Idee lässt sich auch auf das Übermitteln von Daten an andere Personen anwenden. Wenn Sie vor dem Senden der Daten einen Hashwert erzeugen und der Empfänger einen Hashwert für die empfangenen Daten erzeugt, können Sender und Empfänger die beiden erzeugten Hashwerte miteinander vergleichen. Sind dann beide Hashwerte identisch, wurden die Daten auf dem Übertragungsweg nicht geändert.

Warum das funktioniert

Zum Erkennen von Änderungen oder Manipulationen an Daten werden deren kryptographische Hashwerte vor und nach bestimmten Ereignissen miteinander verglichen. Das kann zum Beispiel nach einer gewissen Zeitspanne geschehen, wenn die Daten in einer Datenbank abgelegt oder daraus abgerufen werden, oder nachdem sie in einem Netzwerk übertragen wurden. Das Erkennen von Änderungen an Daten, die unverändert bleiben sollen, funktioniert aufgrund der Kollisionsresistenz bzw. Kollisionssicherheit der kryptographischen Hashfunktionen.

Veränderungssensitive Referenzen​ auf Daten

Das Vergleichen von Daten und das Erkennen von Änderungen anhand der Hashwerte sind grundlegende Anwendungsfälle der Hashwerterzeugung. Ein etwas fortschrittlicherer Anwendungsfall sind dagegen Hashreferenzen, die wir nachfolgend behandeln.

Das Ziel

Das Ziel besteht hierbei darin, auf Daten (zum Beispiel Transaktionsdaten) zu verweisen (diese zu referenzieren), die an einem anderen Ort gespeichert sind (zum Beispiel auf einer Festplatte oder in einer Datenbank), und sicherzustellen, dass diese Datenbestände unverändert sind.

Die Idee

Die Idee besteht darin, die kryptographischen Hashwerte der gespeicherten Daten mit Informationen zum Speicherort der Daten zu kombinieren. Falls die Daten verändert wurden, sind die beiden Angaben nicht mehr konsistent und somit wird die Hashreferenz ungültig​.

Funktionsweise

Referenzen​ auf Daten sind das digitale Gegenstück zu Garderobenmarken​, die den physischen Standort angeben, an dem sich Ihr Mantel in der Garderobe befindet. Mit der Garderobenmarke können Sie den Mantel später wieder abholen. Referenzen auf Daten in Computern funktionieren genauso: Es handelt sich um Daten, die auf andere Daten verweisen. Computerprogramme nutzen Referenzen, um sich den Speicherort von Daten zu merken und diese später wieder abzurufen. Hashreferenzen sind eine spezielle Art von Verweis und nutzen die Macht der kryptographischen Hashwerte. Aus Gründen der Einfachheit können Sie sich Hashreferenzen als Garderobenmarken vorstellen, die einen Hashwert anstelle einer einfachen Zahl anzeigen.

Hashreferenzen verweisen auf andere Daten und prüfen zusätzlich, ob diese Daten, die referenziert werden (das Verweisziel), seit dem Erzeugen der Referenz nicht geändert wurden. Falls das Verweisziel geändert wurde, können die entsprechenden Daten nicht mehr mit der Referenz abgerufen werden. Die Hashreferenz gilt dann als beschädigt oder ungültig. Auf unser Beispiel übertragen, ähnelt dies einer Garderobenmarke, die auf einen Mantelhaken verweist, an dem kein Mantel mehr hängt – in einem solchen Fall kann Ihnen an der Garderobe kein Mantel mehr aushändigt werden.

Die ganze Idee der Hashreferenzen dient dem Schutz der Anwender, damit diese keine Daten abrufen, die versehentlich oder aufgrund von technischen Fehlern oder absichtlich durch andere Personen geändert wurden, ohne dass die Anwender darüber informiert worden sind. Daher werden Hashreferenzen in allen Fällen verwendet, in denen Daten nach dem Erstellen unverändert bleiben sollen.

Eine schematische Darstellung

Die Blockchain beruht in weiten Teilen auf Hashreferenzen. Daher ist eine umfassende Kenntnis dieser Komponente für das Verständnis der Blockchain und der weiteren Schritte in diesem Buch so wichtig. Die nächsten drei Abbildungen erfüllen einen zweifachen Zweck: Einerseits stellen sie die Funktionsweise von Hashreferenzen schematisch dar. Und andererseits führen sie eine bildhafte Darstellung der Hashreferenzen ein, die in den folgenden Schritten zum Darstellen der Funktionsweise der Blockchain-Datenstruktur verwendet wird.

Abbildung 11.1 illustriert die Funktionsweise von Hashreferenzen schematisch anhand einer gültigen Hashreferenz. Der mit R1 beschriftete graue Kreis stellt eine gültige Hashreferenz dar. Der weiße Kasten steht für Daten, die nicht verändert werden sollen. Und der Pfeil vom Kreis zum Kasten ist die Funktion der Hashreferenz. Er weist von der Referenz auf die referenzierten Daten.

Abb. 11.1: Schematische Darstellung einer gültigen Hashreferenz

Abbildung 11.2 illustriert die symbolische Darstellung einer beschädigten oder ungültigen Hashreferenz.

Abb. 11.2: Schematische Darstellung einer ungültigen Hashreferenz

Der schwarze Kasten enthält eine veränderte Begrüßung und stellt somit die nach dem Erstellen der Referenz geänderten Daten dar. Der graue Kreis stellt nach wie vor die ursprünglich erzeugte Hashreferenz dar. Und der gezackte Pfeil, der vom Kreis auf den geänderten Kasten zeigt, steht für eine beschädigte Hashreferenz R1: Es ist kein Abruf der Daten mehr möglich, da diese in der Zwischenzeit geändert worden sind.

Abbildung 11.3 veranschaulicht die Situation für den Fall, dass nach dem Ändern der Daten eine neue Hashreferenz erzeugt wurde. Der schwarze Kasten steht für die veränderten Daten, der schwarze Kreis für die neu erzeugte Hashreferenz und der gerade Pfeil weist von der neu erzeugten Referenz auf die Daten.

Abb. 11.3: Schematische Darstellung einer neu erzeugten Hashreferenz nach dem Ändern der Daten, auf die verwiesen wird

Warum das funktioniert

Der entscheidende Punkt bei den Hashreferenzen ist der Umstand, dass sie kryptographische Hashwerte nutzen, die als eindeutige Fingerabdrücke​ von Daten betrachtet werden können. Es ist also sehr unwahrscheinlich, dass es zwei unterschiedliche Datensätze gibt, die einen identischen Hashwert aufweisen – und dementsprechend wird eine beschädigte Hashreferenz als Beweis für eine Änderung an den Daten nach dem Erzeugen der Hashreferenz angesehen.

Veränderungssensitives Speichern von Daten

Die Idee, anhand ihrer Hashwerte auf Daten zu verweisen, lässt sich noch weiter ausbauen. Wie von selbst ergibt sich die Möglichkeit, Daten auf veränderungssensitive Weise zu speichern.

Das Ziel

Das Ziel​ besteht darin, eine große Datenmenge zu speichern, zum Beispiel Transaktionsdaten, die unverändert bleiben sollen. Jede Änderung an diesen Daten soll schnell und problemlos erkannt werden.

Die Idee​

Garderobenmarken verweisen auf Mantelhaken, an denen Kleidungsstücke hängen. Das ist ganz einfach und logisch. Aber was hindert Sie daran, eine Garderobenmarke in die Tasche eines anderen Mantels zu legen und auch diesen Mantel an der Garderobe abzugeben? Somit erhalten Sie mit der Garderobenmarke für den zweiten Mantel Zugriff auf den Mantel, der eine Garderobenmarke für einen anderen Mantel enthält. Auf diese Weise könnten Sie sehr lange und komplizierte Mantelketten bilden, bei denen in jeder Manteltasche Garderobenmarken liegen, die auf andere Mäntel verweisen, die wiederum Garderobenmarken enthalten und so weiter und so fort. Ebenso können Daten gemeinsam mit Hashreferenzen gespeichert werden, die auf andere Daten verweisen, die wiederum Hashreferenzen enthalten, die auf wieder andere Daten verweisen und so weiter und so fort. Wenn jedoch auch nur einer dieser Datensätze oder eine dieser Hashreferenzen nach dem Erstellen verändert wurde, sind alle Hashreferenzen beschädigt. Und da beschädigte Hashreferenzen als Beweis für eine Änderung der Daten nach dem Erzeugen der Referenz dienen, sind mit diesem Konstrukt sämtliche Daten veränderungssensitiv gespeichert.

Funktionsweise

Es gibt zwei klassische Schemata für die Verwendung von Hashreferenzen beim veränderungssensitiven Speichern von Daten​​:

  • Kette

  • Baum

Die Kette

Eine Kette von miteinander verknüpften Daten wird auch verkettete Liste​ genannt. [2] Sie wird gebildet, wenn jedes »Datenglied« gleichzeitig eine Hashreferenz auf ein anderes Datenglied enthält. Eine solche Struktur ist beim Speichern und Verknüpfen von Daten nützlich, wenn diese Daten nicht alle gleichzeitig verfügbar sind, sondern kontinuierlich nach und nach eingehen. Abbildung 11.4 verdeutlicht diese Idee anhand der oben vorgestellten Symbole. Das Erstellen einer solchen Kette beginnt mit dem ersten Datenglied Daten 1 und dem Erzeugen der Hashreferenz R1. Da Daten 1 das erste Glied der Kette ist, enthält es keine Hashreferenz. Sobald neue Daten eingehen, werden sie mit der Hashreferenz kombiniert, die auf das Glied Daten 1 verweist. Die Hashreferenz R2 verweist auf die neu hinzugekommenen Daten und die Hashreferenz R1. Die Hashreferenz R3, die auf das Glied Daten 3 und die Hashreferenz R2 verweist, wird auf ähnliche Weise erzeugt.

Abb. 11.4: In Form von Kettengliedern verknüpfte Daten

Für den Zugriff auf sämtliche Daten in der Kette (in umgekehrter Reihenfolge des Hinzufügens) benötigen Sie lediglich die Hashreferenz R3. Diese wird auch als Listenkopf oder Listenanker bezeichnet, da sie auf das zuletzt hinzugefügte Datenglied verweist. Verwechseln Sie den Begriff »Kopf« (das zuletzt hinzugefügte Datenglied) bitte nicht mit dem Begriff »Header«, den Sie bei der Behandlung der Blockchain-Datenstruktur in Schritt 14 noch kennenlernen werden.

Der Baum

Abbildung 11.5 zeigt, wie Transaktionsdaten samt Hashreferenzen in einer Baumstruktur​ miteinander verknüpft werden können.

Abb. 11.5: In einer Baumstruktur verknüpfte Daten

Eine solche Struktur wird auch als Hashbaum​​[3] oder im englischen Sprachraum nach ihrem Entdecker, dem Informatiker Ralph Merkle, als Merkle Tree bezeichnet. Sie ähnelt einem auf den Kopf gestellten Baum und eignet sich besonders gut zum Gruppieren vieler einzelner Datenteile, wenn diese gleichzeitig verfügbar sind und über eine einzelne Hashreferenz abrufbar sein sollen. Um den in Abbildung 11.5 dargestellten Baum zu erstellen, beginnen Sie mit den vier Transaktionsdaten (Kästen unten in der Abbildung). Zunächst werden die Hashreferenzen für die einzelnen Transaktionsdaten erzeugt (R1 bis R4), die dann wiederum paarweise gruppiert werden. Anschließend wird für jedes Hashreferenz-Paar eine neue Hashreferenz erzeugt (R12 und R34). Dieser Vorgang wird wiederholt, bis eine einzelne Hashreferenz entsteht, die gleichzeitig die Wurzel des Hashbaums​​ darstellt (mit dem Buchstaben R gekennzeichnet).

Warum das funktioniert

Die aufgezeigten Datenstrukturen speichern Daten auf veränderungssensitive Weise, da sie diese mithilfe von Hashreferenzen verbinden und kombinieren. Diese Referenzen werden beschädigt, wenn irgendwelche Daten, auf die sie verweisen, nach dem Erzeugen der Referenzen geändert werden. Somit beweist eine beschädigte Referenz in einem solchen Konstrukt, dass einige der Daten nach dem Erstellen der Struktur geändert wurden – andernfalls kann geschlossen werden, dass das gesamte Konstrukt seit der Erstellung nicht geändert wurde.

Verursachen zeitaufwendiger Berechnungen

Hashwerte sind nicht nur für grundlegende Dateioperationen wie das sichere und effiziente Vergleichen, Referenzieren und Speichern von Daten nützlich. Sie können auch dazu dienen, Computer von anderen Computern mit komplizierten Aufgaben herausfordern zu lassen. Dies mag nun zunächst etwas seltsam klingen, Sie werden aber gleich sehen, dass diese Form der Verwendung von Hashwerten eins der wichtigsten Konzepte der Blockchain darstellt.

Das Ziel

Aus Gründen, die Sie im Laufe des Buchs noch verstehen werden, kann es notwendig sein, eine Rechenaufgabe zu stellen, für deren Lösung Berechnungsressourcen eingesetzt werden müssen. Es darf nicht möglich sein, diese Aufgaben aufgrund von Wissen oder irgendwo gespeicherten Daten oder durch einfaches Schlussfolgern zu lösen (wie es bei einem IQ- oder Wissenstest der Fall ist). Der einzige Lösungsweg führt über reine Rechenleistung und aufwendige Berechnungen.

Die Idee

Ein Zahlenschloss​​ lässt sich erst öffnen, wenn eine bestimmte Ziffernfolge eingestellt wurde. Wer diese Ziffernfolge nicht kennt, kann systematisch alle möglichen Kombinationen ausprobieren, bis er irgendwann die für das Schloss gewählte Kombination findet. Auf diese Weise kann das Schloss garantiert geöffnet werden, allerdings ist der Weg dorthin recht zeitraubend. Beim systematischen Durchprobieren aller möglichen Kombinationen sind weder umfangreiches Wissen noch Geistesleistungen oder Schlussfolgerungen gefragt – nur Fleiß und harte Arbeit führen zum offenen Schloss. Hashpuzzles sind Berechnungsaufgaben, die das digitale Gegenstück zum Öffnen eines Zahlenschlosses nach der Trial-and-Error-Methode (Versuch und Irrtum) darstellen. Diese Berechnungsaufgaben werden auch Proof-of-Work oder Computational Puzzle genannt.

Funktionsweise

Die Elemente​ eines Hashpuzzles sind:[4]

  • Vorhandene Daten, die unverändert bleiben müssen

  • Frei veränderbare Daten, genannt Nonce

  • Die zu verwendende Hashfunktion

  • Beschränkungen bezüglich des Hashwerts der kombinierten Hashfunktion, auch als Schwierigkeitsgrad​ bezeichnet

Abbildung 11.6 zeigt den grundlegenden Aufbau eines Hashpuzzles. Die kombinierte Hashfunktion wird auf die Daten und die Nonce angewendet. Der resultierende Hashwert muss bestimmten Auflagen – den Beschränkungen – entsprechen.

Abb. 11.6: Schematische Darstellung eines Hashpuzzles

Hashpuzzles können nur durch Versuch und Irrtum gelöst werden. Dazu müssen eine Nonce geraten, der Hashwert der kombinierten Daten mit der erforderlichen Hashfunktion berechnet und der resultierende Hashwert anhand der Beschränkungen bewertet werden. Falls der Hashwert die Auflagen erfüllt, haben Sie das Hashpuzzle gelöst – falls nicht, müssen Sie mit einer anderen Nonce fortfahren, bis das Puzzle irgendwann gelöst ist. Die ​Nonce, die in Kombination mit den vorhandenen Daten einen Hashwert ergibt, der die Beschränkungen einhält, wird Lösung genannt. Um zu belegen, dass Sie ein Hashpuzzle gelöst haben, müssen Sie stets die entsprechende Nonce liefern.

Ein anschauliches Beispiel

Betrachten wir ein echtes Hashpuzzle, um den Ablauf zu verdeutlichen. In Schritt 10 haben Sie gesehen, dass der verkürzte Hashwert für Hello World! der Wert 7F83B165 ist. Aber welche Daten würden in Kombination mit Hello World! einen verkürzten Hashwert mit drei führenden Nullen ergeben? Unser Hashpuzzle lautet also: Finde die Nonce, die in Kombination mit Hello World! einen verkürzten Hashwert ergibt, der mit drei führenden Nullen beginnt.

Also, Ärmel hochgekrempelt und los geht’s. Tabelle 11.1 führt die Nonce, den Text für die Hashfunktion sowie den resultierenden verkürzten Hashwert auf. Sie sehen, dass die Nonce 614 das Hashpuzzle löst. Würden wir also mit der Nonce 0 beginnen und den Zähler jedes Mal um den Wert 1 erhöhen, benötigten wir 615 Versuche bis zur Lösung. Wäre stattdessen ein Hashwert mit lediglich einer führenden Null gefragt, ist die Aufgabe bereits nach vier Schritten gelöst, denn Hello World! 3 ergibt einen Hashwert mit einer führenden Null.

Nonce

Text für die Hashfunktion

Ausgabe

0

Hello World! 0

4EE4B774

1

Hello World! 1

3345B9A3

2

Hello World! 2

72040842

3

Hello World! 3

02307D5F
 

...

  

613

Hello World! 613

E861901E

614

Hello World! 614

00068A3C

615

Hello World! 615

5EB7483F

Tabelle 11.1: Nonces zum Lösen eines Hashpuzzles

Sie können das auch selbst ausprobieren:
www.blockchain-basics.com/HashPuzzle.html

Der Schwierigkeitsgrad​

Das zentrale Anliegen des Hashpuzzles besteht folglich darin, dem Hashwert eine bestimmte Beschränkung aufzuerlegen. Insofern sind weder die Beschränkung selbst noch deren Beschreibung beliebig. Stattdessen ist die für Hashpuzzles verwendete Art der Beschränkung standardisiert, damit Computer andere Computer mit Hashpuzzles herausfordern können. In diesem Kontext werden die Beschränkungen häufig auch als Schwierigkeit oder Schwierigkeitsgrad bezeichnet. Die Schwierigkeit wird als natürliche Zahl ausgedrückt und gibt an, wie viele führende Nullen der Hashwert mindestens haben muss. Bei einer Schwierigkeit von 1 muss er (mindestens) eine führende Null aufweisen, bei einer Schwierigkeit von 10 muss der Hashwert mindestens 10 führende Nullen aufweisen und so weiter. Je höher der Schwierigkeitsgrad, desto mehr führende Nullen sind erforderlich und desto komplizierter ist das Hashpuzzle. Und je komplizierter das Hashpuzzle ist, desto mehr Rechenleistung oder Zeit wird für die Lösung benötigt.

Warum das funktioniert

Die Funktionsweise von Hashpuzzles hängt wesentlich davon ab, dass Hashfunktionen Einwegfunktionen sind. Es ist nicht möglich, ein Hashpuzzle durch Untersuchung der Beschränkungen für den Hashwert zu lösen, indem anschließend die Hashfunktion in umgekehrter Richtung angewendet wird. Der Weg vom gewünschten Ergebnis zur erforderlichen Eingabe bleibt also verwehrt. Hashpuzzles können nur durch Versuch und Irrtum gelöst werden – und das kostet viel Rechenleistung und somit viel Zeit und Energie. Der Schwierigkeitsgrad wirkt sich direkt auf die Anzahl der Versuche aus, die im Schnitt zum Finden der Lösung nötig sind. Damit lässt sich eine Aussage über die für die Lösung benötigten Berechnungsressourcen und die Zeit treffen.

Hashfunktionen sind deterministisch​​ und können sehr schnell Hashwerte für beliebige Daten liefern. Sobald also eine Lösung gefunden wurde, kann sehr leicht überprüft werden, ob die Daten in Kombination mit der Nonce tatsächlich einen Hashwert liefern, der die Beschränkungen einhält. Erfüllt der berechnete Wert die Beschränkung nicht, liegt kein Fehler der Hashfunktion vor, denn die Abweichung wird ausschließlich dadurch verursacht, dass das Puzzle nicht gelöst wurde.

Hinweis

Im Kontext der Blockchain werden Hashpuzzles oft als Arbeitsnachweis oder Proof-of-Work bezeichnet, denn die Lösung weist nach, dass jemand die dafür erforderliche Arbeit investiert hat.

Verwenden von Hashfunktionen in der Blockchain

In der Blockchain werden Hashfunktionen wie folgt verwendet:

Ausblick

In diesem Schritt wurden die wichtigsten Anwendungsfälle für Hashwerte dargestellt und deren Nutzung in der Blockchain umrissen. Die nächsten Schritte beschäftigen sich detaillierter mit Hashfunktionen in der Blockchain.

Zusammenfassung

[1] Tsudik, Gene. Message authentication with one-way hash functions. In ACM SIGCOMM Computer Communication Review 22.5 (1992):29–38.

[2] Cormen, Thomas H. Algorithmen – Eine Einführung (4. überarbeitete Auflage). De Gruyter Oldenbourg, 2013.

[3] Merkle, Ralph C. Protocols for Public Key Cryptosystems. In IEEE Symposium on Security and Privacy 122 (1980).

[4] Back, Adam. Hashcash—a denial of service counter-measure. 2002. http://www.hashcash.org/papers/hashcash.pdf.