Zero-Knowledge-Beweise

Ein Zero-Knowledge-Beweis ermöglicht es einem Beweisführer, einen Prüfer davon zu überzeugen, dass eine Aussage wahr ist, während nichts über die Tatsache ihrer Wahrheit hinaus offenbart wird – eine kontraintuitive Fähigkeit mit breiten kryptographischen Anwendungen.

Definition

Ein Zero-Knowledge-Beweis ist ein interaktives (oder nicht-interaktives) Protokoll, bei dem ein Beweisführer einen Prüfer davon überzeugt, dass eine Aussage wahr ist, so dass der Prüfer nichts außer der Gültigkeit der Aussage erfährt, formalisiert durch einen Simulator, der die Ansicht des Prüfers ohne den Zeugen reproduziert.

Scope

Dieses Thema behandelt interaktive Beweissysteme und ihre Zero-Knowledge-Varianten: die definierenden Eigenschaften von Vollständigkeit, Korrektheit und Zero-Knowledge; das Simulationsparadigma; Wissensbeweise; die Fiat-Shamir-Transformation zu nicht-interaktiven Beweisen; und moderne prägnante Systeme (zk-SNARKs und zk-STARKs). Es befasst sich mit Anwendungen in der Authentifizierung und der datenschutzfreundlichen Verifizierung. Ausgeschlossen sind die breitere Komplexitätstheorie interaktiver Beweise und die Protokolle (MPC), die Zero-Knowledge als Unterkomponente verwenden.

Core questions

• Wie kann ein Beweis die Überzeugung von der Wahrheit vermitteln, ohne andere Informationen preiszugeben?
• Was garantieren Vollständigkeit, Korrektheit und die Zero-Knowledge-Eigenschaft jeweils?
• Wie erfasst die Existenz eines Simulators das 'Nichts lernen'?
• Wie werden interaktive Beweise über die Fiat-Shamir-Transformation nicht-interaktiv gemacht?
• Wie machen prägnante Beweise (SNARKs, STARKs) Zero-Knowledge in großem Maßstab praktisch?

Key concepts

• interaktives Beweissystem
• Vollständigkeit und Korrektheit
• Zero-Knowledge-Eigenschaft
• Simulator
• Wissensbeweis
• Fiat-Shamir-Transformation
• nicht-interaktives Zero-Knowledge (NIZK)
• zk-SNARKs und zk-STARKs
• Verpflichtungsschemata

Key theories

Das Simulationsparadigma

Ein Protokoll ist Zero-Knowledge, wenn es für jeden Prüfer einen effizienten Simulator gibt, der ohne Zugriff auf den geheimen Zeugen ein Transkript erstellt, das von einer realen Interaktion nicht zu unterscheiden ist – dies formalisiert die Idee, dass der Prüfer nichts lernt.

Vollständigkeit, Korrektheit und Wissensbeweise

Ein interaktiver Beweis ist vollständig, wenn ehrliche Beweisführer ehrliche Prüfer überzeugen, und korrekt, wenn falsche Aussagen mit hoher Wahrscheinlichkeit abgelehnt werden; ein Wissensbeweis garantiert zusätzlich über einen Wissensextraktor, dass der Beweisführer den Zeugen tatsächlich besitzt.

Mechanisms

Ein kanonisches Drei-Schritt- (Sigma-) Protokoll sieht vor, dass der Beweisführer eine Verpflichtung sendet, der Prüfer eine zufällige Herausforderung sendet und der Beweisführer antwortet; die Korrektheit ergibt sich aus der Unfähigkeit des Beweisführers, alle Herausforderungen ohne den Zeugen zu beantworten, und Zero-Knowledge aus der Fähigkeit des Simulators, Transkripte zu fälschen, indem er die Herausforderung zuerst wählt. Die Fiat-Shamir-Transformation ersetzt die Herausforderung des Prüfers durch einen Hash der Verpflichtung, was zu einem nicht-interaktiven Beweis führt. Prägnante Systeme verwenden polynomiale Verpflichtungen und arithmetische Schaltungen, um kurze, schnell zu verifizierende Beweise zu erstellen.

Clinical relevance

Zero-Knowledge-Beweise ermöglichen Datenschutz und Skalierbarkeit in implementierten Systemen: Datenschutzfreundliche Kryptowährungen (Zcash) verbergen Transaktionsdetails, während sie die Gültigkeit beweisen; Blockchain-Rollups verwenden prägnante Beweise zur Komprimierung von Berechnungen; anonyme Anmeldeinformationen und digitale Identitätssysteme beweisen Attribute (Alter, Staatsbürgerschaft), ohne sie offenzulegen; und Authentifizierungsschemata beweisen den Besitz eines Geheimnisses, ohne es preiszugeben.

Evidence & guidelines

Zero-Knowledge-Konstruktionen sind ein aktives Standardisierungsgebiet (die ZKProof Community Standards Effort). Produktionssysteme verlassen sich auf gut überprüfte SNARK- und STARK-Bibliotheken, obwohl SNARKs, die ein vertrauenswürdiges Setup erfordern, eine sorgfältige Zeremoniegestaltung verlangen, während STARKs ein vertrauenswürdiges Setup auf Kosten größerer Beweise vermeiden. Die Korrektheit hängt von kryptographischen Annahmen und, für Fiat-Shamir, dem Random-Oracle-Modell ab.

History

Goldwasser, Micali und Rackoff führten 1985 interaktive Beweise und Zero-Knowledge ein, wobei die Journalversion 1989 erschien. Goldreich, Micali und Wigderson zeigten, dass jede NP-Aussage einen Zero-Knowledge-Beweis hat (1987). Die Fiat-Shamir-Transformation (1986) machte Beweise nicht-interaktiv. Die 2010er Jahre brachten prägnante nicht-interaktive Argumente (zk-SNARKs) und transparente STARKs, die Zero-Knowledge von der Theorie in Blockchain- und Datenschutzprodukte überführten.

Key figures

• Shafi Goldwasser
• Silvio Micali
• Charles Rackoff
• Oded Goldreich
• Amos Fiat
• Adi Shamir

Seminal works

• goldwasser1989
• katz2020
• goldreich2001

Frequently asked questions

Was ist eine einfache Intuition für Zero-Knowledge?

Stellen Sie sich vor, Sie beweisen, dass Sie zwei optisch identische Objekte unterscheiden können, indem Sie wiederholt identifizieren, welches Objekt eine versteckte Partei ausgetauscht hat: Jede richtige Antwort erhöht das Vertrauen, dass Sie sie unterscheiden können, aber der Prüfer erfährt nie, wie. Die Wiederholung einer Herausforderung-Antwort viele Male macht Betrug astronomisch unwahrscheinlich, während kein Geheimnis enthüllt wird.

Erfordern Zero-Knowledge-Beweise Interaktion?

Die ursprüngliche Definition ist interaktiv, aber die Fiat-Shamir-Transformation und dedizierte nicht-interaktive Konstruktionen (NIZKs, SNARKs, STARKs) erzeugen eine einzelne Beweiszeichenkette, die jeder ohne Interaktion verifizieren kann, was sie auf Blockchains nutzbar macht.