Schritt 10: Anwenden von Hashfunktionen auf Daten

Identifizieren von Daten anhand ihres digitalen Fingerabdrucks

Dieser Schritt erläutert eine der wichtigsten Basistechnologien der Blockchain: die Hashwerte. Auf den folgenden Seiten werden die wichtigen Eigenschaften kryptographischer Hashfunktionen​ behandelt und Schemata zum Anwenden von Hashfunktionen auf Daten vorgestellt.

Die Metapher​

Fingerabdrücke​ sind Abdrücke der Papillarleisten aller oder einiger Finger der menschlichen Hand. Man geht davon aus, dass sich damit jeder Mensch eindeutig identifizieren lässt. Sie kommen bei der Aufklärung von Verbrechen, der Identifizierung von Straftätern und zum Entlasten von Unschuldigen zum Einsatz. Dieser Schritt stellt ein Konzept zur Identifizierung von Daten vor, das als digitales Gegenstück der Fingerabdrücke betrachtet werden kann. Es wird als kryptographischer Hashwert​ bezeichnet und in der Blockchain umfassend verwendet. Das Verständnis der kryptographischen Hashfunktionen​ ist für das Verständnis der Blockchain unerlässlich.

Das Ziel​

In einem verteilten Peer-to-Peer-System haben Sie es mit einer gewaltigen Menge von Transaktionsdaten zu tun, die Sie eindeutig identifizieren und vergleichen können müssen – und das so schnell und einfach wie möglich. Das Ziel besteht also darin, Transaktionsdaten bzw. nach Möglichkeit jede Art von Daten anhand ihrer digitalen Fingerabdrücke eindeutig zu identifizieren.

Funktionsweise

Hashfunktionen sind kleine Computerprogramme, die beliebige Daten ungeachtet des Umfangs der Eingabedaten als eine Zahl mit fester Länge abbilden. [1] Hashfunktionen nehmen zu einem bestimmten Zeitpunkt jeweils nur einen Datensatz als Eingabe entgegen und erzeugen auf der Grundlage der Bits und Bytes in diesen Daten einen Hashwert​. Hashwerte können führende Nullen aufweisen, um die erforderliche Länge zu erreichen. Es gibt viele verschiedene Hashfunktionen, die sich in Bezug auf die Länge des erzeugten Hashwerts voneinander unterscheiden. Eine wichtige Gruppe davon wird als kryptologische oder kryptographische Hashfunktionen bezeichnet, welche digitale Fingerabdrücke für beliebige Daten erzeugen. Kryptographische Hashfunktionen zeichnen sich durch die folgenden Eigenschaften aus. Sie ...[2]

Schnelle Bereitstellung von Hashwerten für beliebige Daten

Diese Eigenschaft ist eigentlich eine Kombination von zwei Eigenschaften: Erstens ist die Hashfunktion in der Lage, Hashwerte für beliebige Daten zu berechnen, und zweitens führt sie diese Berechnung schnell aus. Diese Eigenschaften sind wichtig, denn ganz sicher können wir keine Fehlermeldungen der Hashfunktion gebrauchen und möchten auch nicht unnötig lange auf die Ergebnisse warten.

Deterministisch

Deterministisch​​ bedeutet, dass die Hashfunktion für identische Eingabedaten identische Hashwerte liefert. Jede beobachtete Diskrepanz der Hashwerte für Daten darf also ausschließlich durch Diskrepanzen in den Eingabedaten verursacht werden, nicht durch die Hashfunktion selbst.

Pseudozufällig

Pseudozufällig​​ bedeutet, dass sich der von der Hashfunktion zurückgegebene Hashwert​ auf unvorhersehbare Weise ändert, wenn sich die Eingabedaten ändern. Wird auch nur ein Bit der Eingabedaten modifiziert, muss der resultierende Hashwert auf unvorhersehbare Weise vom vorherigen Wert abweichen. Anders ausgedrückt: Der Hashwert der geänderten Daten muss stets überraschend ausfallen. Es darf nicht möglich sein, den Hashwert anhand der Eingabedaten vorherzusagen.

Einwegfunktion

Eine Einwegfunktion​​ bietet keine Möglichkeit, aus den Ausgaben auf die Eingabewerte zu schließen – Einwegfunktionen können also nicht in der Gegenrichtung verwendet werden. Anders ausgedrückt: Es ist unmöglich, die ursprünglichen Daten anhand des Hashwerts wiederherzustellen. Das bedeutet, dass die Hashwerte nichts über den Inhalt der Eingabedaten verraten – wie auch ein einzelner Fingerabdruck Ihnen nichts darüber verrät, welche Person ihn hinterlassen hat. Einwegfunktionen werden auch als unumkehrbar bezeichnet.

Kollisionsresistent

Eine Hashfunktion wird als kollisionsresistent​​ bezeichnet, wenn es sehr schwer ist, zwei oder mehr Datensätze zu finden, aus denen derselbe Hashwert berechnet wird. Anders ausgedrückt: Wenn die Wahrscheinlichkeit, für unterschiedliche Datensätze denselben Hashwert zu berechnen, gering ist, dann ist die Hashfunktion kollisionsresistent (oder kollisionssicher). In diesem Fall können Sie die von der Hashfunktion erzeugten Hashwerte als eindeutig und somit zum Identifizieren von Daten geeignet betrachten. Wenn Sie einen identischen Hashwert für unterschiedliche Daten erhalten, spricht man von einer ​Hashkollision. Sie ist das digitale Gegenstück zu zwei Menschen mit identischen Fingerabdrücken. Damit Hashwerte als digitale Fingerabdrücke dienen können, müssen sie unbedingt kollisionsresistent sein. Die interne Funktionsweise von kollisionsresistenten Hashfunktionen sprengt den Rahmen dieses Buchs, aber seien Sie versichert, dass große Bemühungen unternommen worden sind, um das Risiko von Hashkollisionen so gering wie möglich zu halten.

Ausprobieren

Dieser Abschnitt hilft Ihnen mittels eines einfachen Beispiels, sich mit dem Anwenden von Hashfunktionen vertraut zu machen. Hierzu empfiehlt sich ein Besuch der englischen Website zum Buch, auf der Sie ein Tool zum Erzeugen von Hashwerten für einfache Textdaten finden:
http://www.blockchain-basics.com/HashFunctions.html.

Wenn Sie die Webseite​ in Ihrem Browser aufrufen, werden ein Eingabe- (INPUT) und ein Ausgabefeld (OUTPUT) angezeigt (vgl. Abbildung 10.1). Geben Sie den Text Hello World! in das Eingabefeld ein, und klicken Sie dann auf die Schaltfläche Calculate Hash Value (Hashwert berechnen) unter dem Textfeld. Achten Sie darauf, Hello World! ganz genau wie hier gezeigt einzugeben (ohne Anführungszeichen), da sich die Ergebnisse ansonsten von denen aus Abbildung 10.1 unterscheiden.

Abb. 10.1: Berechnen der Hashwerte für einen kurzen Text

Nachdem Sie auf die Schaltfläche geklickt haben, werden im Ausgabefeld die mit vier verschiedenen Hashfunktionen berechneten Hashwerte für den eingegebenen Text angezeigt. Hashwerte verwenden nicht nur die Ziffern von 0 bis 9, sondern auch die Buchstaben A bis F, die im Hexadezimalsystem für die Zahlen 10 bis 15 stehen. Man spricht auch von Hexadezimalwerten. Informatiker lieben diese aus Gründen, die an dieser Stelle nicht erörtert werden sollen. Beachten Sie, dass sich die Hashwerte aufgrund der unterschiedlichen Implementierung der verwendeten Hashfunktionen voneinander unterscheiden. Bei diesen Werten müssen Sie mir einfach vertrauen, denn die Implementierung von Hashfunktionen ist ein weites Feld, das den Rahmen dieses Buches sprengen würde.

Kryptographische Hashwerte sind relativ lang und daher mit dem menschlichen Auge schwer zu erfassen oder zu vergleichen. Allerdings vergleichen Sie in diesem Schritt unterschiedliche Arten zum Anwenden von Hashfunktionen, sodass Sie um das Lesen und Vergleichen von Hashwerten nicht herum kommen. Kryptographische Hashwerte sind da sehr lästig, deshalb kommt im weiteren Verlauf dieses Schritts aus didaktischen Gründen eine verkürzte Version aus dem SHA256-Algorithmus zum Einsatz. Sie können sämtliche Hashwerte mit dem Tool auf der Website selbst erzeugen: www.blockchain-basics.com/Hashing.html.

Wenn Sie die Webseite​ in Ihrem Browser aufrufen, werden ein Eingabefeld für einfache Texte (INPUT) und ein Ausgabefeld (OUTPUT) sowie eine Pfeilschaltfläche angezeigt (vgl. Abbildung 10.2). Klicken Sie auf den Pfeil, wird im Ausgabefeld der verkürzte Hashwert des Eingabetextes angezeigt.

Abb. 10.2: Berechnen des verkürzten Hashwerts für einen Text

Schemata zum Anwenden von Hashfunktionen auf Daten

Bisher haben Sie gelernt, dass Daten als Eingabewert für eine Hashfunktion dienen können, die daraus einen Hashwert berechnet. Das impliziert, dass für jeden eigenständigen Datensatz ein eindeutiger kryptographischer Hashwert existiert. Aber was, wenn Sie einen einzelnen Hashwert für eine Reihe unabhängiger Datensätze angeben sollen? Hashfunktionen können schließlich immer nur einen Datensatz gleichzeitig verarbeiten. Es gibt keine Hashfunktion, die mehrere unabhängige Daten gleichzeitig akzeptiert, aber in der Realität werden oft einzelne Hashwerte für eine große Datensammlung benötigt. Insbesondere die Blockchain-Datenstruktur muss viele Transaktionsdaten gleichzeitig handhaben und für all diese Daten einen einzelnen Hashwert ermitteln. Wie funktioniert das?

Die Antwort besteht im Einsatz der folgenden Schemata beim Anwenden von Hashfunktionen auf Daten:

Unabhängiges Anwenden von Hashfunktionen

Beim ​​unabhängigen Anwenden von Hashfunktionen wird die Hashfunktion unabhängig voneinander auf jeden einzelnen Datensatz angewendet. Abbildung 10.3 verdeutlicht dieses Konzept durch das unabhängige Berechnen der verkürzten Hashwerte für zwei einzelne Wörter.

Abb. 10.3: Schematische Darstellung für das unabhängige Anwenden von Hashfunktionen auf unterschiedliche Daten

Die weißen Kästen mit den Wörtern stellen die Eingabedaten für die Hashfunktion dar, die grauen Kreise die zugehörigen Hashwerte. Die Pfeile zwischen Kästen und Kreisen stehen schematisch für die Umwandlung der Daten in Hashwerte. Wie Sie in Abbildung 10.3 erkennen können, resultieren unterschiedliche Wörter in verschiedenen Hashwerten.

Wiederholtes Anwenden von Hashfunktionen

Sie haben gelernt, dass Hashfunktionen jeden beliebigen Datensatz in einen Hashwert umwandeln. Auch ein Hashwert selbst kann einen Datensatz darstellen. Insofern sollte es möglich sein, einen Hashwert als Eingabewert für eine Hashfunktion zu verwenden und für diesen Hashwert einen weiteren Hashwert zu berechnen. Und das funktioniert in der Tat! Das wiederholte ​​Anwenden von Hashfunktionen bedeutet, dass eine Hashfunktion wiederholt auf ihr eigenes Ergebnis angewendet wird. Abbildung 10.4 verdeutlicht das Konzept durch wiederholtes Berechnen des verkürzten Hashwerts. Der Text Hello World! ergibt den Hashwert 7F83B165, der wiederum in dem verkürzten Hashwert 45A47BE7 resultiert.

Abb. 10.4: Wiederholtes Berechnen von Hashwerten

Kombiniertes Anwenden von Hashfunktionen

Beim ​​kombinierten Anwenden von Hashfunktionen wird ein einzelner Hashwert für mehrere Datensätze auf einmal gesucht. Dazu werden die unabhängigen Datensätze zu einem Datensatz zusammengeführt, und anschließend wird der Hashwert dieses kombinierten Datensatzes berechnet. Das ist besonders hilfreich, wenn Sie einen einzelnen Hashwert für eine zu einem bestimmten Zeitpunkt vorhandene Datensammlung erzeugen möchten. Da das Kombinieren der Daten Rechenleistung, Zeit und Speicherplatz kostet, sollte ein kombiniertes Anwenden von Hashfunktionen nur erfolgen, wenn die einzelnen Datensätze klein sind. Ein weiterer Nachteil besteht darin, dass die Hashwerte der einzelnen Datensätze nicht verfügbar sind, da nur die kombinierten Daten an die Hashfunktion übergeben werden.

Abbildung 10.5 verdeutlicht das Konzept des kombinierten Anwendens von Hashfunktionen. Die einzelnen Wörter werden zunächst zu einer Wortfolge mit Leerzeichen dazwischen kombiniert; anschließend wird die Hashfunktion für die resultierende Phrase verwendet. Der so entstehende Hashwert in Abbildung 10.5 ist folgerichtig identisch mit dem ersten Hashwert aus Abbildung 10.4. Beachten Sie, dass der Hashwert der kombinierten Daten wesentlich davon abhängt, wie die Daten kombiniert wurden. In Abbildung 10.4 wurden die beiden Wörter mit einem Leerzeichen dazwischen notiert, sodass das Ergebnis der Kombination Hello World! lautet. Manchmal werden bestimmte Symbole wie das Pluszeichen (+) oder der Hashtag (#) verwendet, um die Verbindungsstelle der Daten zu markieren. Dadurch ändert sich natürlich der resultierende Hashwert.

Abb. 10.5: Kombinieren von Daten mit anschließendem Berechnen des Hashwerts

Sequenzielles Anwenden von Hashfunktionen

Das Ziel beim ​​sequenziellen Anwenden von Hashfunktionen besteht darin, einen Hashwert beim Eintreffen neuer Daten inkrementell zu aktualisieren. Dazu werden das kombinierte und das wiederholte Anwenden von Hashfunktionen gleichzeitig eingesetzt. Der vorhandene Hashwert wird mit den neuen Daten kombiniert und anschließend an die Hashfunktion übergeben, um einen aktualisierten Hashwert zu ermitteln. Das sequenzielle Anwenden von Hashfunktionen ist besonders hilfreich, wenn Sie über die gesamte Dauer hinweg einen einzelnen Hashwert beibehalten möchten, der beim Eintreffen neuer Daten aktualisiert wird. Ein Vorteil bei dieser Anwendung der Hashfunktion besteht darin, dass Sie zu jedem Zeitpunkt einen Hashwert besitzen, dessen Entstehung bzw. Veränderung auf das Eintreffen neuer Daten zurückgeführt werden kann.

Abbildung 10.6 veranschaulicht das Konzept der sequenziellen Anwendung von Hashfunktionen. Zu Beginn wird das Wort Hello einzeln an die Hashfunktion übergeben; daraus entsteht der verkürzte Hashwert 185F8DB3. Sobald neue Daten vorliegen (in diesem Fall das Wort World!), werden diese mit dem vorhandenen Hashwert kombiniert und dann an die Hashfunktion übergeben. Der Hashwert 5795A986 ist der verkürzte Hashwert der Eingabe World! 185F8DB3.

Abb. 10.6: Sequenzielles Berechnen von Hashwerten

Hierarchisches Anwenden von Hashfunktionen

Abbildung 10.7 verdeutlicht das Konzept des ​​hierarchischen Anwendens von Hashfunktionen.

Abb. 10.7: Hierarchisches Berechnen von Hashwerten

Die kombinierte Anwendung der Hashfunktion auf ein Paar von Hashwerten führt zu einer kleinen Hierarchie von Hashwerten mit einem einzelnen Wert an der Spitze. Ähnlich wie beim kombinierten Anwenden von Hashfunktionen besteht auch beim hierarchischen Anwenden von Hashfunktionen die Idee darin, einen einzelnen Hashwert für eine Datensammlung zu erzeugen. Das hierarchische Anwenden von Hashfunktionen ist effizienter, weil es Hashwerte von stets fester Länge kombiniert, und nicht die ursprünglichen Daten beliebiger Größe. Außerdem werden beim hierarchischen Anwenden von Hashfunktionen in jedem Schritt nur zwei Hashwerte miteinander kombiniert, wohingegen beim kombinierten Anwenden von Hashfunktionen so viele Daten kombiniert werden, wie Sie möchten.

Ausblick

Dieser Schritt war dem Konzept der Hashfunktionen gewidmet. Schritt 11 zeigt, wie Hashwerte in der Realität und in der Blockchain verwendet werden.

Zusammenfassung

[1] Weisstein, Eric W. Hash function. Von MathWorld: http://mathworld.wolfram.com/HashFunction.html.

[2] Rogaway, Phillip und Shrimpton, Thomas. Cryptographic hash-function basics: definitions, implications, and separations for preimage resistance, second-preimage resistance, and collision resistance. In B. Roy und W. Meier (Hrsg.), Fast software encryption. FSE 2004. Lecture Notes in Computer Science, Band 3017. International Workshop on Fast Software Encryption. Berlin Heidelberg: Springer, 2004.