ZKP-Intuition: Die Höhle von Ali Baba

Ein Zero-Knowledge-Beweis (ZKP) ermöglicht es einem Beweiser, einen Verifizierer davon zu überzeugen, dass er ein Geheimnis kennt (oder dass eine Aussage wahr ist), ohne das Geheimnis selbst offenzulegen. Drei Eigenschaften: Vollständigkeit, Korrektheit und Zero-Knowledge.

Wenn der Beweiser das Geheimnis kennt, kann er den Verifizierer immer überzeugen. Ein ehrlicher Beweiser, der dem Protokoll folgt, hat mit Wahrscheinlichkeit 1 (oder überwältigender Wahrscheinlichkeit) Erfolg. Der Verifizierer wird einen gültigen Beweis nicht ablehnen.

Ein betrügerischer Beweiser (der das Geheimnis nicht kennt) kann den Verifizierer nur mit vernachlässigbarer Wahrscheinlichkeit überzeugen. Jede Interaktionsrunde verringert die Wahrscheinlichkeit eines Betrugs – nach k Runden beträgt die Erfolgswahrscheinlichkeit eines Betrügers höchstens 2^{-k}.

Der Verifizierer erfährt nichts über die Tatsache hinaus, dass die Aussage wahr ist. Formal bedeutet dies: Es existiert ein Simulator, der ohne Kenntnis des Geheimnisses ein Protokoll erzeugt, das von einer echten Interaktion zwischen Beweiser und Verifizierer nicht zu unterscheiden ist. Der Verifizierer gewinnt keinerlei zusätzliche Erkenntnisse.

Eine Höhle verfügt über einen ringförmigen Gang mit einer magischen Tür in der Mitte. Die Beweiserin (Alice) behauptet, das Passwort zu kennen. Der Verifizierer (Bob) wartet draußen. Alice geht hinein und nimmt den linken oder rechten Weg. Bob ruft, auf welcher Seite sie herauskommen soll. Wenn Alice das Passwort kennt, kommt sie immer auf der richtigen Seite heraus. Die Betrugswahrscheinlichkeit pro Runde beträgt 1/2.

Nach 20 Runden hat eine betrügerische Person eine Erfolgswahrscheinlichkeit von 2^{-20}, also ungefähr 1 zu einer Million. Alice (die das Passwort kennt) hat jedes Mal Erfolg. Bob erfährt das Passwort nie – er sieht nur, dass Alice auf der angeforderten Seite herauskommt. Das ist Zero-Knowledge.

Interaktive ZKPs erfordern einen Austausch zwischen Beweiser und Verifizierer. Nicht interaktive ZKPs (NIZKs) verwenden die Fiat-Shamir-Transformation: Die zufällige Herausforderung des Verifizierers wird durch einen Hash des Commitments ersetzt (Hash = Random Oracle). Dadurch entsteht eine einzige Beweiszeichenfolge, die jeder verifizieren kann.

Ein ZKP ist ein Wissensbeweis (PoK), wenn aus der Strategie des Beweisers folgt, dass er das Geheimnis extrahieren könnte. Dies ist stärker, als lediglich die Wahrheit einer Aussage zu beweisen. ECDSA- und Schnorr-Signaturen sind nicht interaktive Wissensbeweise für den privaten Schlüssel.

Passwortauthentifizierung, ohne das Passwort zu senden. Altersverifikation, ohne das Geburtsdatum offenzulegen. Bereichsbeweise (Ihr Gehalt liegt in einem bestimmten Bereich), ohne das Gehalt offenzulegen. Blockchain: Beweisen, dass Sie eine gültige Transaktion kennen, ohne die Transaktion offenzulegen.

Perfektes Zero-Knowledge: Die Ausgabe des Simulators ist mit dem echten Transkript identisch. Statistisches ZK: Die Ausgaben sind bis auf eine vernachlässigbare Wahrscheinlichkeit nicht unterscheidbar. Computational ZK: Für Verifizierer mit polynomieller Laufzeit sind die Ausgaben nicht unterscheidbar. Schwächere Garantien ermöglichen effizientere Beweise.

Die Höhle ist ein Protokoll mit drei Schritten: Commitment → Challenge → Response. Formal wird es als Sigma-Protokoll bezeichnet. Die meisten praktischen ZKPs (Schnorr, Pedersen, Fiat-Shamir) sind Sigma-Protokolle oder Kombinationen daraus. Der Name leitet sich von der Form Σ des Nachrichtenflussdiagramms ab.

Nach wie vielen Runden des Ali-Baba-Höhlenprotokolls liegt die Erfolgswahrscheinlichkeit eines Betrügers unter 1/1000?

ZKPs weisen nach, dass jemand ein Geheimnis kennt, ohne es offenzulegen. Drei Eigenschaften: Vollständigkeit, Korrektheit und Zero-Knowledge. Die Ali-Baba-Höhle veranschaulicht ein interaktives ZKP. Als Nächstes folgen Sigma-Protokolle und die Schnorr-Identifikation.