15.03.2021

Beitragsreihe Blockchain Deep Dives: Hashing und Merkle Trees für datenschutzgerechte Dokumentation

Das Interesse am Einsatz der Blockchain-Technologie in der Energiewirtschaft ist nach wie vor hoch. Nach der ersten Beitragsserie zum Thema „Blockchain in der Energiewirtschaft – Eine Einführung“ möchten wir in dieser neuen Serie etwas tiefer in die Grundlagen und technischen Komponenten einsteigen. Zum Einsatz der Blockchain und insbesondere bei der dezentralen Datenspeicherung und -verarbeitung sind einige Punkte zu beachten und verschiedene technologische Lösungen zu berücksichtigen, die wir hier inkl. Anwendungsbeispielen vorstellen möchten.

Im Rahmen des Projektes InDEED wird der Einsatz von Zero Knowledge Proofs zum Beweis von Dateneigenschaften und korrekter Berechnung gemeinsam mit dem Fraunhofer Blockchain-Labor an der Universität Bayreuth umgesetzt und technisch erprobt.

Übersicht über die Beitragsserie zum Thema Blockchain Deep Dives

  1. Hashing und Merkle Trees für datenschutzgerechte Dokumentation
  2. Zero Knowledge Proofs für den sicheren Beweis ohne Offenlegung der Daten
  3. Komplexe Berechnungen und dezentralisierte Optimierung der Blockchain-Architekturen

Kryptografische Hashfunktionen

Eine Hashfunktion (von engl. „hash“: zerhacken) ist eine mathematische Funktion, die in der Lage ist, einen beliebigen Eingabewert unbestimmter Größe zu einem Ausgabewert mit fester, meist deutlich kleinerer Größe umzuwandeln. Ein solcher Ausgabewert wird in der Umgangssprache häufig ebenfalls als Hash oder als Digest bezeichnet. Der Zusatz „kryptografisch“ deutet an, dass weitere Eigenschaften vorhanden sind, die eine praktische Anwendung der Hashfunktion zur Absicherung vertraulicher Daten ermöglichen.

Eigenschaften

Betrachten wir zunächst drei Eigenschaften, die allen Hashfunktionen zugrunde liegen: Allen voran sollte die Berechnung eines Hashwerts deterministisch ablaufen, also dieselbe Eingabe immer wieder zur selben Ausgabe führen. Andernfalls wäre die Hashfunktion für den praktischen Gebrauch untauglich. Darüber hinaus sollte eine kleine Änderung an den Eingabedaten eine große Änderung am resultierenden Hashwert verursachen, da sonst auf Ähnlichkeiten zurückgeschlossen werden könnte (vgl. Abbildung 1). Zu guter Letzt ist es wünschenswert, dass die Berechnung auch effizient ist. So müssen Anwendungen nicht sparsam mit ihrem Gebrauch umgehen.

Abbildung 1: Anwendung einer kryptographischen Hashfunktion auf unterschiedlichen Eingabetexten

Neben den genannten informellen Hash-Funktionen existieren drei weitere formelle Kriterien, die die Grundlage für kryptografische Hashfunktionen bilden.

  • Einwegfunktion: Es ist nicht möglich, die Ausgangsdaten für einen gegebenen Hash zu finden.
  • Schwache Kollisionsresistenz: Für einen gewählten Ausgangstext ist es nicht möglich, einen zweiten Text zu finden, der auf denselben Hashwert abbildet.
  • Starke Kollisionsresistenz: Es ist generell nicht möglich, zwei Ausgangstexte zu finden, die auf denselben Hashwert abbilden.

Für alle Eigenschaften gilt: Unmöglichkeit im Sinne von „nicht in absehbarer Zeit berechenbar“.

 

Implementierungen

Über die Jahre hinweg hat sich eine Vielzahl von Implementierungen aufgetan. Die wohl bekannteste unter ihnen ist die SHA-2 Familie von Hashfunktionen.Sowohl SHA-2 als auch ihr Nachfolger SHA-3 finden häufig Anwendung in modernen IT-Systemen. Alle Mitglieder dieser Familie wurden vom National Institute of Standards and Technology standardisiert und sind öffentlich einsehbar [1]. SHA ersetzt heute weitgehend die frühere Hasfunktion MD5, deren Sicherheit in einer Studie widerlegt wurde [2].

Gesonderte Erwähnung verdienen Hashfunktionen zur Sicherung von Passwörtern. Entgegen der zuvor genannten Definition ist hier eine möglichst langsame Ausführung wünschenswert. Dies verhindert, dass Angreifer durch zufälliges Ausprobieren ein Passwort in absehbarer Zeit erraten können. „Langsam“ bedeutet hier eine Zeit von wenigen Sekunden. Diesem Umstand wird beispielsweise von der Argon2 Konstruktion Rechnung getragen, die wiederum auf der Blake2 Hashfunktion aufbaut.

Hash-Bäume

Hash-Bäume sind ein beliebter Anwendungsfall von kryptografischen Hashfunktionen. Sie wurden im Jahr 1979 von Ralph Merkle entwickelt [3] und werden deshalb in der Praxis häufig auch als „Merkle Trees“ bezeichnet. Die dahinter liegende Logik ermöglicht es, große Datenmengen einfacher überprüfbar zu machen und sicher zu speichern. Im Prinzip ermöglicht die Verwendung eines Hash-Baums eine Integritätsprüfung von Teildaten, ohne dass hierfür der gesamte Datensatz vorhanden sein muss. Dies geschieht durch eine intelligente Aufteilung und bruchstückhafte Verarbeitung der gesamten Datenstruktur. Im Ergebnis bleibt so die Überprüfung auch im Fall von sehr großen Datensätzen effizient. Dies stellt eine erhebliche Verbesserung gegenüber vorherigen Lösungen, wie zum Beispiel Hash-Listen, dar.

Im Kontext der Blockchain werden die Hashes einzelner Transaktionen eines Blocks sukzessive zu einem einzigen Hash kombiniert. Diese Logik ermöglicht es, Rechenleistung zu sparen und die zu versendende Datenmenge so gering wie möglich zu halten [3]. Der Vorteil ist dabei, dass einzelne Transaktionen problemlos transparent im Nachgang überprüft werden können. Statt die gesamte Information (z. B. alle Transaktionen) überprüfen zu müssen, ist es ausreichend, den Ast der zu überprüfenden Transaktion zu validieren.

Die folgende Abbildung 2 zeigt die schematische Darstellung eines Merkle Baums.

Abbildung 2: Schematische Darstellung eines Hash-Baumes

Im Regelfall handelt es sich bei Hash-Bäumen um sogenannte Binärbäume, das heißt eine Verkettung aus Knoten, bei dem von einem einzelnen Wurzelknoten immer jeweils zwei weitere Unterknoten (Kinder) ausgehen. Dabei enthält jeder Knoten den kombinierten Hashwert seiner beiden Kinder. Die Knoten der untersten Ebene (Blätter) wiederum halten jeweils den Hashwert eines Teilabschnitts des zugrundeliegenden Datensatzes. Bezogen auf die Eigenschaften von Hashfunktionen bedeutet dies, dass selbst eine kleine Veränderung in einem Teilabschnitt eine drastische Veränderung seines Hashwerts nach sich zieht. In der vorgestellten Konstruktion werden solche Veränderungen zusätzlich durch den gesamten Baum propagiert und sind somit bereits am Wurzelknoten erkennbar.

Zur Prüfung eines einzelnen Teilabschnitts genügt es daher, eine „Kette“ zum Wurzelknoten zu bilden. Das heißt, um beispielsweise den Abschnitt A aus der Darstellung zu verifizieren, werden lediglich die Hashwerte AB und B benötigt. Bei Fortsetzung des Prinzips halbiert sich folglich der Anteil der benötigten Hashwerte mit jeder weiteren Ebene des Baums. Man spricht daher auch von einer logarithmischen Laufzeit der Verifizierung.

Im Vergleich zu bisherigen Hash-basierten Überprüfungsverfahren ermöglicht eine solche bruchstückhafte Rekonstruktion beispielsweise ein sequenzielles oder gar verteiltes Vorgehen. Da ein bestimmter Teilabschnitt bereits mit einer nur kleinen Anzahl von Hashwerten verifiziert werden kann, ist es niemals nötig, den gesamten Datensatz zu besitzen.

Literatur:

[1]  L. G. M, “Device for and method of one-way cryptographic hashing,” 6829355, 2004.

[2] T. Xie, F. Liu, and D. Feng, “Fast collision attack on MD5,” IACR ePrint archive Report, vol. 104, p. 17, 2006, [Online: http://crppit.epfl.ch/documentation/Hash_Function/Examples/Code_Project/Documentation/104.pdf.

[3] R. C. Merkle, “A Digital Signature Based on a Conventional Encryption Function,” in Advances, 1988, pp. 369–378.http://crppit.epfl.ch/documentation/Hash_Function/Examples/Code_Project/Documentation/104.pdf.