Beitragsreihe Blockchain Deep Dives: Zero Knowledge Proofs

Der dritte Teil der Beitragsserie „Blockchain – Deep Dives“ beschäftigt sich mit Zero-Knowledge-Proofs (ZKP). Dahinter versteckt sich ein relativ neues Verfahren in der Kryptographie, welches es ermöglicht, einem Dritten zu beweisen, dass eine gewisse Information bekannt ist oder ein Computerprogramm ordnungsgemäß ausgeführt wurde, ohne Informationen über Inputs, Vorgänge oder Outputs preisgeben zu müssen. Dies ist theoretisch für viele Anwendungen von großem Nutzen, wurde aber bisher in der Praxis aufgrund des relativ hohen Aufwands wenig eingesetzt.

Im Rahmen des Projektes InDEED wird der Einsatz gemeinsam mit dem Fraunhofer Blockchain-Labor an der Universität Bayreuth umgesetzt und technisch erprobt.

Übersicht über die Beitragsserie zum Thema Blockchain Deep Dives

Hashing und Merkle Trees für datenschutzgerechte Dokumentation
- Grundlagen zu Hash-Funktionen und Hash-Bäumen
- Anwendung zum Nachweis der Existenz und Integrität von Daten
Zero Knowledge Proofs für den sicheren Beweis ohne Offenlegung der Daten
- Grundlagen zu Zero Knowledge Proofs
- Anwendung zum Beweis der Dateneigenschaften oder korrekter Berechnung
Komplexe Berechnungen und dezentralisierte Optimierung der Blockchain-Architekturen

Grundlagen von Zero-Knowledge-Proofs

Bei den sogenannten Zero-Knowledge–Proofs handelt es sich um eine Reihe von Verfahren, mit denen man in der Lage ist, die Kenntnis über eine bestimmte Tatsache nachzuweisen (proof) ohne die Tatsache selbst bekannt zu geben (zeroknowledge). Moderne Umsetzungen fußen häufig auf neuesten Erkenntnissen aus der Kryptografie, jedoch lassen sich simple Zero-Knowledge–Proofs auch bereits mit relativ wenig Aufwand erzeugen. Im Folgenden werden wir versuchen, das Konzept anhand einer solchen „Low-Tech“–Variante näher zu erläutern.

Abbildung 1: Illustrierendes Beispiel mit Hilfe von Alibabas Höhle

Die Illustration ist aus dem Artikel „How to Explain Zero-Knowledge Protocols to Your Children” [1] entliehen. Man stelle sich eine ringförmige Höhle mit einem einzigen Eingang vor. Am entfernten Ende der Höhle befindet sich eine magische Tür, die sich nur bei Benutzung des richtigen Passworts öffnet. Peggy (P) ist im Besitz des Passworts und möchte Victor (V) ihre Kenntnis beweisen, ohne ihm das Passwort selbst zu verraten.

Hierzu verschließt V zunächst die Augen und P wählt zufällig einen der beiden Pfade zur Tür (1). Nun öffnet V die Augen wieder und wählt ebenfalls zufällig einen der beiden Pfade. Diesen teilt er P per Zuruf mit (2). P trifft nun die nötigen Vorkehrungen, um auf dem von V gewählten Pfad zum Eingang zurückzukehren. Ist sie bereits auf demselben Pfad in die Höhle gelangt, so kehrt sie einfach um. Wurde der andere Pfad gewählt, so tritt sie mithilfe des Passworts durch die magische Tür und setzt den Weg bis zum Eingang fort (3). Auf diese Weise gelingt es P in jedem Fall, auf dem von V gewählten Pfad die Höhle zu verlassen.

Wird dieses Experiment wiederholt, so halbiert sich die Wahrscheinlichkeit, dass P anfangs denselben Pfad einschlägt, den später auch V wählen wird, mit jeder erneuten Durchführung. Sollte P also tatsächlich nicht im Besitz des Passworts sein, so verdoppelt sich die Chance, dass sie nicht in der Lage ist, die Tür zu öffnen und auf dem falschen Weg die Höhle verlassen muss. Bei ausreichend häufiger Durchführung des Experiments entsteht bei V demnach eine statistische Sicherheit, dass P das Passwort kennt oder eben nicht.

Formale Definition

Im Allgemeinen muss ein System für Zero-Knowledge-Proofs die folgenden drei Eigenschaften besitzen:

Vollständigkeit: Besitzt der Beweisende Kenntnis über die zu beweisende Tatsache, so muss er in der Lage sein, dies einem beliebigen Prüfer zweifelsfrei darzulegen.
Zuverlässigkeit: Besitzt der Beweisende die Kenntnis nicht, so muss dies vom Prüfer auch erkannt werden.
Zero-Knowledge-Eigenschaft: Die zu beweisende Tatsache darf während des gesamten Vorgangs nicht offenbart werden.

Bei Anwendung dieser Definition auf unser vorhergehendes Beispiel erkennt man, dass 1) der Beweis für jedes beliebige Passwort geführt werden kann, 2) bei ausreichender Wiederholung eine Nicht-Kenntnis durch V erkannt wird und 3) das Passwort zu keinem Zeitpunkt enthüllt wird. Es handelt sich deshalb auch im formalen Sinne um einen Zero-Knowledge-Proof.

Die erste Anwendung im Blockchain-Umfeld war die Kryptowährung „Zcash“, welche vollständige Anonymität der Transaktionen verspricht. Zero-Knowledge-Beweise werden in diesem Fall dafür eingesetzt, eine Validierung von Transaktionen durch die Blockchain zu ermöglichen, ohne die Details dieser Transaktion zu übertragen. Die technische Umsetzung basiert dabei auf zk-SNARK (zero-knowledge Succinct Non-interactive ARgument of Knowledge), wodurch der Aufwand im Vergleich zu klassischen Zero-Knowledge-Protokollen deutlich verringert werden kann.

Zero-Knowledge-Proofs sind also kryptographische Verfahren, die Korrektheit und Validität einer Handlung (hier: in einer Blockchain) zu bestätigen, ohne Inhalte der Handlung offenlegen zu müssen. Dadurch wird die Integrität und Manipulationssicherheit der Technologie bei gleichzeitig hohem Datenschutz gewährleistet. Die Lösungen sind heute jedoch noch ressourcenintensiv und haben noch einen negativen Effekt auf die Skalierbarkeit.

Eine Weiterentwicklung der zk-SNARKs sind die 2018 vorgestellten zk-STARKs (zero-knowledge Succinct Transparent ARguments of Knowledge). Während erstere aus technischer Sicht nicht vollständig transparent sind, da sie auf einem geheimen public-/private-Schlüsselpaar aufbauen, ist dies bei zk-STARKS nicht mehr notwendig. zk-STARKs sind ca. 1.000 mal länger und verbrauchen dadurch mehr Speicherplatz/Datenvolumen als zk-SNARKs, sind aber nach Angaben der Entwickler quantencomputersicher und transparenter als ihre Vorgänger. Die Entwicklung dieser Technologie befindet sich jedoch noch in einem sehr frühen Stadium. [2]

Weitere Informationen:

Quellen:

[1] J.-J. Quisquater et al., “How to Explain Zero-Knowledge Protocols to Your Children,” in Advances in Cryptology — CRYPTO’ 89 Proceedings, New York, NY: Springer New York, 1998, pp. 628–631.
[2] Ben-Sasson, Eli et al.: Scalable, transparent, and post-quantum secure computational integrity. Haifa, Israel: Zerocash, 2018.