Entdecken Sie die wahren Gründe für die Entstehung zeitloser Innovationen bei wissensfreien Beweisen

Geschrieben von: LambdaClass ) sind Eine Art leistungsstarkes kryptografisches Primitiv, das es einem Prüfer ermöglicht, einen Prüfer von der Richtigkeit einer Aussage zu überzeugen, ohne über die Aussage hinausgehende Informationen preiszugeben. zk-SNARKs haben aufgrund ihrer Anwendungen in überprüfbaren privaten Berechnungen, dem Nachweis der Korrektheit der Ausführung von Computerprogrammen und Blockchain-Erweiterungen große Aufmerksamkeit erhalten. Wir glauben, dass zk-SNARKs, wie wir sie in unserem Artikel beschreiben, einen erheblichen Einfluss auf die Gestaltung der Welt haben werden. zk-SNARKs decken verschiedene Arten von Beweissystemen ab und verwenden unterschiedliche polynomiale Verpflichtungsschemata, arithmetische Schemata, interaktive Orakelbeweise oder probabilistisch überprüfbare Beweise. Diese grundlegenden Ideen und Konzepte reichen jedoch bis in die Mitte der 1980er Jahre zurück.

Die Entwicklung von zk-SNARKs hat sich seit der Einführung von Bitcoin und Ethereum aufgrund ihrer Skalierbarkeit durch den Einsatz wissensfreier Beweise (oft als Gültigkeitsnachweise für diesen speziellen Anwendungsfall bezeichnet) stark beschleunigt. zk-SNARKs spielen eine entscheidende Rolle bei der Skalierbarkeit der Blockchain. Wie Ben-Sasson beschreibt, kam es in den letzten Jahren zu einer kambrischen Explosion bei kryptografischen Beweisen. Jedes Proofsystem hat Vor- und Nachteile und ist unter Berücksichtigung spezifischer Kompromisse konzipiert. Fortschritte bei Hardware, Algorithmen, neuen Beweisen und Werkzeugen verbessern weiterhin die Leistung und führen zur Schaffung neuer Systeme. Viele dieser Systeme sind bereits im Einsatz und wir erweitern weiterhin die Grenzen. Werden wir ein universelles Proofsystem haben, das für alle Anwendungen funktioniert, oder wird es mehrere Systeme geben, die für unterschiedliche Anforderungen geeignet sind? Wir halten es aus folgenden Gründen für sehr unwahrscheinlich, dass ein Beweissystem alle anderen Systeme dominiert: 1) Vielfalt der Anwendungen.

2) Verschiedene Arten von Einschränkungen (bezüglich Speicher, Überprüfungszeit, Beweiszeit).

3) Das Bedürfnis nach Robustheit (wenn ein Beweissystem kaputt ist, gibt es andere Beweissysteme). Obwohl Beweissysteme erheblichen Änderungen unterliegen können, haben sie dennoch eine wichtige Eigenschaft gemeinsam: die schnelle Überprüfbarkeit von Beweisen. Die mit dem Wechsel von Basisschichten wie Ethereum verbundenen Schwierigkeiten werden in einer Schicht gelöst, die Beweise verifizieren und sich leicht an neue Beweissysteme anpassen kann. Dieser Artikel gibt einen kurzen Überblick über die verschiedenen Eigenschaften von SNARKs.

1) Kryptografische Annahmen: kollisionsresistente Hash-Funktion, diskretes Logarithmusproblem auf elliptischer Kurve, Kenntnis des Exponenten.

2) Transparente vs. vertrauenswürdige Einstellungen.

3) Beweislänge: linear vs. superlinear.

4) Validatorzeit: konstante Zeit, logarithmisch, sublinear, linear.

5) Proof-Größe.

6) Leicht rekursiv.

7) Arithmetisches Schema.

8) Univariables Polynom vs. multivariables Polynom.

In diesem Artikel werden die Ursprünge von SNARKs, einige grundlegende Bausteine ​​und der Aufstieg (und Fall) verschiedener Beweissysteme untersucht. Dieser Artikel ist nicht dazu gedacht, eine erschöpfende Analyse von Beweissystemen bereitzustellen. Konzentrieren Sie sich stattdessen nur auf diejenigen, die einen Einfluss auf uns haben. Natürlich waren diese Entwicklungen nur durch die großartige Arbeit und Ideen von Pionieren auf diesem Gebiet möglich.

2. Grundkenntnisse

Zero-Knowledge-Beweise sind nicht neu. Definitionen, Grundlagen, wichtige Theoreme und sogar wichtige Protokolle wurden ab Mitte der 1980er Jahre entwickelt. Einige der Schlüsselideen und Protokolle zum Bau moderner SNARKs wurden in den 1990er Jahren vorgeschlagen (Sumcheck-Protokoll), noch bevor Bitcoin existierte (GKR im Jahr 2007). Die Hauptprobleme bei der Nutzung hängen mit dem Mangel an starken Anwendungsfällen (das Internet wurde in den 1990er Jahren noch nicht entwickelt) und der erforderlichen Rechenleistung zusammen.

1) Wissensfreier Beweis: Origins (1985/1989).

Das Gebiet der wissensfreien Beweise tauchte in der wissenschaftlichen Literatur mit dem Aufsatz „The Knowledge Complexity of Interactive Proof Systems“ von Goldwasser, Micali und Rackoff auf. Für eine Diskussion der Ursprünge schauen Sie sich das Video ZKP MOOC Lecture 1: Introduction and History of ZKP vom Januar 2023 an. In diesem Artikel werden die Konzepte Ploidie, Zuverlässigkeit und Nullwissen vorgestellt und die Konstruktion quadratischer Residuosität und quadratischer Nicht-Residuosität bereitgestellt.

2) Sumcheck-Protokoll (1992).

Das Sumcheck-Protokoll wurde 1992 von Lund, Fortnow, Karloff und Nisan im Artikel „Algebraic Methods for Interactive Proof Systems“ vorgeschlagen. Es ist einer der wichtigsten Bausteine ​​prägnanter interaktiver Beweise. Es hilft uns, die Anforderung einer multivariaten polynomialen Auswertungssummierung auf eine einzige Auswertung zufällig ausgewählter Punkte zu reduzieren.

3) Goldwasser-Kalai-Rothblum (GKR) (2007).

Das GKR-Protokoll (siehe den Artikel Delegating Computation: Interactive Proofs for Muggles) ist ein interaktives Protokoll, bei dem der Beweiser linear mit der Anzahl der Gatter im Schaltkreis und der Prüfer sublinear mit der Größe des Schaltkreises arbeitet. Im Protokoll einigen sich der Prüfer und der Verifizierer auf die Fan-in-Two-Operationsschaltung des endlichen Feldes mit der Tiefe d dd, wobei Schicht d dd der Eingabeschicht und Schicht 0 00 der Ausgabeschicht entspricht. Das Protokoll beginnt mit einer Aussage über den Ausgang der Schaltung, die auf eine Aussage über den Wert der vorherigen Schicht reduziert wird. Mittels Rekursion kann dies in eine Deklaration der Eingänge der Schaltung umgewandelt werden, die leicht überprüft werden kann. Diese Reduzierungen werden über das Sumcheck-Protokoll umgesetzt.

4) KZG-Polynom-Commitment-Schema (2010).

Kate, Zaverucha und Goldberg haben im Jahr 2010 „Constant-Size Commitments to Polynomials and Their Applications“ ein Polynom-Commitment-Schema unter Verwendung bilinearer Paarungsgruppen eingeführt. Ein Commitment besteht aus einem einzelnen Gruppenelement, und der Committer eröffnet effektiv ein Commitment für jede korrekte Auswertung des Polynoms. Darüber hinaus können dank der Batch-Technologie mehrere Auswertungen geöffnet werden. Das KZG-Engagement stellt einen der Grundbausteine ​​für mehrere effiziente SNARKs wie Pinocchio, Groth16 und Plonk dar. Es ist auch der Kern von EIP-4844. Um die Batch-Technologie intuitiv zu verstehen, lesen Sie die Mina-zu-Ethereum-ZK-Brücke.

3. Praktische SNARKs mit elliptischen Kurven

Die erste praktische Konstruktion von SNARKs erschien im Jahr 2013. Diese Konstruktionen erfordern Vorverarbeitungsschritte zur Generierung von Beweisen und Verifizierungsschlüsseln und sind programm-/schaltungsspezifisch. Diese Schlüssel können sehr groß sein und von geheimen Parametern abhängen, die allen Beteiligten unbekannt sind; andernfalls können Beweise gefälscht werden. Um Code in beweisbaren Code umzuwandeln, muss der Code in ein System polynomialer Einschränkungen kompiliert werden. Dies musste zunächst manuell erfolgen, was zeitaufwändig und fehleranfällig war. Fortschritte auf diesem Gebiet versuchen, einige große Probleme zu beseitigen:

1) Effizientere Prüfer.

2) Reduzieren Sie den Vorverarbeitungsaufwand.

3) Verwenden Sie Setups, die allgemein und nicht schaltungsspezifisch sind.

4) Vermeiden Sie vertrauenswürdige Einstellungen.

5) Entwickeln Sie Möglichkeiten zur Beschreibung von Schaltkreisen mithilfe von Hochsprachen, anstatt manuell Polynombeschränkungen zu schreiben.

Derzeit sind praktische SNARKs-Lösungen mit elliptischen Kurven:

1) Pinocchio (2013)

2) Groth 16 (2016)

3) Bulletproofs & IPA (2016)

4) Sonic, Marlin, and Plonk (2019)

5) Lookups (2018/2020)

6) Spartan (2019)

7) HyperPlonk (2022)

8) Faltschemata (2008/2021)

3.1 Pinocchio (2013)

Pinocchio (siehe den Aufsatz „Pinocchio: Nearly Practical Verifiable Computation“) ist der erste praktische und verwendbare zk-SNARK. SNARK basiert auf quadratischen Arithmetikprogrammen (QAP). Die Proofgröße beträgt zunächst 288 Byte. Die Toolchain von Pinocchio bietet einen Compiler vom C-Code über arithmetische Schaltkreise bis hin zur weiteren Übersetzung in QAP. Das Protokoll erfordert, dass der Verifizierer schaltungsspezifische Schlüssel generiert. Es verwendet elliptische Kurvenpaare, um Gleichungen zu überprüfen. Die asymptotische Asymptotik für die Beweiserstellung und Schlüsseleinstellung skaliert linear mit der Berechnungsgröße, und die Verifizierungsdauer skaliert linear mit der Größe der öffentlichen Ein- und Ausgänge. 3.2 Groth 16 (2016) Es verfügt über eine minimale Beweisgröße (nur drei Gruppenelemente) und eine schnelle Verifizierung mit drei Paarungen. Es umfasst auch Vorverarbeitungsschritte, um eine Reihe strukturierter Referenzen zu erhalten. Der Hauptnachteil besteht darin, dass jedes zu zertifizierende Programm eine andere vertrauenswürdige Einrichtung erfordert, was unpraktisch ist. Groth16 wurde in ZCash verwendet. Einzelheiten finden Sie auch im Blog Ein Überblick über das Groth 16-Proof-System.

3.3 Bulletproofs & IPA (2016)

Eine der Schwächen von KZG PCS besteht darin, dass es eine vertrauenswürdige Einrichtung erfordert. Das Papier „2016 Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting“ von Bootle et al. stellte ein effizientes Zero-Knowledge-Argumentsystem für Pedersen-Verpflichtungsöffnungen vor, das die innere Produktbeziehung erfüllt. Systeme zum Nachweis innerer Produkte verfügen über einen linearen Prüfer mit logarithmischer Kommunikation und Interaktion, jedoch mit linearer Dauerüberprüfung. Außerdem wurde ein Polynom-Commitment-Schema entwickelt, das kein vertrauenswürdiges Setup erfordert. Sowohl Halo 2 als auch Kimchi übernehmen die IPA PCS-Idee.

3.4 Sonic, Marlin und Plonk (2019)

Sonic, Plonk und Marlin lösen das Problem der Vertrauenseinstellungen für jedes Programm in Groth16, indem sie eine gemeinsame und aktualisierbare strukturierte Referenzzeichenfolge einführen. Marlin bietet ein Beweissystem basierend auf R1CS, dem Kern von Aleo.

Plonk führte ein neues arithmetisches Schema (später Plonkish genannt) ein und verwendete eine Gesamtproduktprüfung für Kopierbeschränkungen. Plonkish erlaubt auch die Einführung spezieller Türen für bestimmte Vorgänge, sogenannte Custom Doors. Mehrere Projekte verfügen über benutzerdefinierte Versionen von Plonk, darunter unter anderem Aztec, ZK-Sync, Polygon ZKEVM, Mina’s Kimchi, Plonky2, Halo 2 und Scroll. Sehen Sie sich den Blog an. Alles, was Sie über Plonk wissen wollten.

3.5 Lookups (2018/2020)

Gabizon und Williamson führten 2020 Plookups ein, bei denen eine große Produktprüfung eingesetzt wurde, um zu beweisen, dass ein Wert in einer vorberechneten Wertetabelle enthalten ist. Obwohl in Arya bereits Suchargumente vorgeschlagen wurden, erforderte ihre Konstruktion die Bestimmung der Multiplizitäten der Suchvorgänge, was weniger effizient war. Das PlonkUp-Papier zeigt, wie man das Plookup-Argument in Plonk einführt. Das Problem mit diesen Suchargumenten besteht darin, dass sie den Prüfer dazu zwingen, für die gesamte Tabelle zu zahlen, unabhängig von der Anzahl der Suchvorgänge. Dies bedeutet, dass die Kosten für große Tabellen beträchtlich sind und große Anstrengungen unternommen wurden, um die Kosten des Prüfers auf die Anzahl der von ihm verwendeten Suchvorgänge zu reduzieren.

Haböck führt LogUp ein, das logarithmische Ableitungen verwendet, um Produktschecks in Summen von Kehrwerten umzuwandeln. LogUp ist entscheidend für die Leistung von Polygon plonky2 ZKEVM (Beyond Limits: Pushing the Boundaries of ZK-EVM), was die Aufteilung der gesamten Tabelle in mehrere STARK-Module erfordert. Die Module müssen ordnungsgemäß verknüpft sein und es sind tabellenübergreifende Suchvorgänge erforderlich, um diesen Vorgang durchzusetzen. Die Einführung von LogUp-GKR nutzt das GKR-Protokoll, um die Leistung von LogUp zu verbessern. Caulk ist das erste Suchargument, dessen Prüferzeit eine sublineare Beziehung zur Tabellengröße hat, mit einer Vorverarbeitungszeit von O ( N log ⁡ N ) und einem Speicher von O ( N ), wobei N die Tabellengröße ist. Es folgten mehrere weitere Schemata, wie Baloo, Flookup, CQ und Caulk+. Lasso schlug mehrere Verbesserungen vor, um zu vermeiden, dass eine Tabelle festgeschrieben wird, wenn sie eine bestimmte Struktur hat. Darüber hinaus zahlt der Prüfer von Lasso nur für Tabelleneinträge, auf die durch Suchvorgänge zugegriffen wird. Jolt nutzt Lasso, um die Ausführung virtueller Maschinen durch Suchvorgänge nachzuweisen.

3.6 Spartan (2019)

Spartan stellt IOPs für mit R1CS beschriebene Schaltkreise bereit und nutzt dabei die Eigenschaften multivariabler Polynome und das Sumcheck-Protokoll. Unter Verwendung eines geeigneten Polynom-Commitment-Schemas wird ein transparentes SNARK mit einem linearen Dauerprüfer erstellt.

3.7 HyperPlonk (2022)

HyperPlonk basiert auf der Idee von Plonk, Polynome mit mehreren Variablen zu verwenden. Es basiert nicht auf Quotienten, um die Durchsetzung von Einschränkungen zu überprüfen, sondern auf dem Sumcheck-Protokoll. Es unterstützt auch hochgradige Einschränkungen, ohne die Laufzeit des Prüfers zu beeinträchtigen. Da es auf multivariablen Polynomen basiert, muss keine FFT durchgeführt werden, und die Laufzeit des Prüfers skaliert linear mit der Schaltkreisgröße. HyperPlonk führt neue Permutations-IOPs ein, die für kleinere Domänen geeignet sind, und ein auf Summenprüfungen basierendes Batch-Öffnungsprotokoll, das den Prüferaufwand, die Prüfgröße und die Prüferzeit reduziert.

3.8 Faltschemata (2008/2021)

Nova führt die Idee von Faltschemata ein, eine neue Möglichkeit zur Implementierung inkrementeller überprüfbarer Berechnungen (IVC). Das Konzept von IVC geht auf Valiant zurück, der zeigte, wie man zwei Beweise der Länge k kk in einem einzigen Beweis der Länge k kk kombiniert. Die Idee ist, dass ein rekursiver Beweis verwendet werden kann, um zu beweisen, dass die Ausführung von Schritt i ii zu Schritt i + 1 i+1i+1 korrekt ist, und um den Übergang von Schritt i − 1 i-1i−1 zu Schritt i ii zu verifizieren ist korrekt und beweist damit, dass dies für jede lang andauernde Berechnung der Fall ist.

Nova kann einheitliche Berechnungen sehr gut bewältigen; später wurde es mit der Einführung von Supernova erweitert, um verschiedene Arten von Schaltkreisen zu verarbeiten. Nova verwendet eine entspannte Version von R1CS und arbeitet mit freundlichen elliptischen Kurven. Die Verwendung benutzerfreundlicher Kurvenzyklen (z. B. Pasta-Kurven) zur Implementierung von IVC wird auch in Pickles, dem Hauptbasismodul von Mina, verwendet, um prägnante Zustände zu erreichen. Die Idee des Faltens unterscheidet sich jedoch von der rekursiven SNARK-Verifizierung. Die Idee der Akkumulatoren ist tiefer mit dem Konzept der Batch-Proofs verbunden. Halo führt das Konzept der Akkumulation als Alternative zu rekursiven Beweiskombinationen ein. Protostar bietet eine uneinheitliche IVC-Lösung für Plonk, die hochgradige Gates und Vektorsuchen unterstützt.

4. SNARKs, die kollisionsresistente Hash-Funktionen verwenden

Ungefähr zur gleichen Zeit wie Pinocchios Entwicklung gab es einige Ideen zur Generierung von Schaltkreisen/Rechenschemata, die die Korrektheit der Ausführung einer virtuellen Maschine beweisen könnten. Obwohl die Arithmetik der Entwicklung einer virtuellen Maschine komplexer oder weniger effizient sein kann als das Schreiben dedizierter Schaltkreise für einige Programme, bietet sie den Vorteil, dass jedes Programm, egal wie komplex es auch sein mag, durch den Nachweis, dass es in einer virtuellen Maschine korrekt ausgeführt wird, nachgewiesen werden kann. Die Ideen in TinyRAM wurden später mit dem Design von Cairo vm und nachfolgenden virtuellen Maschinen wie zk-evms oder generischen zkvms verfeinert. Durch die Verwendung einer kollisionsresistenten Hash-Funktion entfällt die Notwendigkeit eines vertrauenswürdigen Setups oder der Verwendung einer elliptischen Kurvenarithmetik, allerdings auf Kosten längerer Beweise.

1) TinyRAM (2013)

In SNARKs für C wird ein PCP-basierter SNARK entwickelt, um die Korrektheit der Ausführung eines in TinyRAM (Reduced Instruction Set Computer) kompilierten C-Programms zu beweisen. Der Computer verwendet die Harvard-Architektur mit adressierbarem Direktzugriffsspeicher auf Byte-Ebene. Durch die Nutzung des Nichtdeterminismus skaliert die Schaltkreisgröße quasilinear mit der Rechengröße und ermöglicht so eine effiziente Handhabung beliebiger datenbezogener Schleifen, Kontrollflüsse und Speicherzugriffe.

2) STARKs (2018)

STARKs wurde 2018 von Ben Sasson et al. vorgeschlagen. Seine Implementierung hat eine Beweisgröße von O(log2n), verfügt über schnelle Prüfer und Verifizierer, erfordert kein vertrauenswürdiges Setup und gilt als Post-Quantum-sicher. Es wurde erstmals von Starkware/Starknet mit der virtuellen Maschine Cairo verwendet. Zu seinen Schlüsselkomponenten gehören:

Algebraic Intermediate Representation (AIR)

und das FRI-Protokoll (Fast Reed-Solomon Interactive Oracle Proof of Proximity).

STARKs werden auch von anderen Projekten (Polygon Miden, Risc0, Winterfell, Neptune) oder einigen Adaptionen davon (ZK-Sync's Boojum, Plonky2, Starky) verwendet.

3) Ligero (2017)

Ligero führt ein Beweissystem ein, dessen Beweisgröße O(Wurzel n) ist, wobei n die Schaltkreisgröße ist. Es ordnet Polynomkoeffizienten in Matrixform an und verwendet lineare Codes.

Brakedown baut auf Ligero auf und führt die Idee domänenunabhängiger Polynom-Commitment-Schemata ein.

5. Einige neue Entwicklungen im ZKP

Der Einsatz verschiedener Proofsysteme in der Produktion zeigt die Vorteile jeder Methode und bringt neue Entwicklungen mit sich. Plonkish-Arithmetik bietet beispielsweise eine einfache Möglichkeit, benutzerdefinierte Gates und Suchargumente einzubeziehen; FRI zeigt als PCS eine hervorragende Leistung vor Plonky. Ebenso verbessert die Verwendung der großen Produktprüfung in AIR (was zu randomisiertem AIR mit Vorverarbeitung führt) die Leistung und vereinfacht den Speicherzugriff auf Argumente. Versprechen, die auf Hash-Funktionen basieren, haben sich durchgesetzt – entweder aufgrund der Geschwindigkeit von Hash-Funktionen in der Hardware oder der Einführung neuer SNARK-freundlicher Hash-Funktionen.

1) Neues Polynom-Commitment-Schema (2023)

Mit dem Aufkommen effizienter SNARKs, die auf multivariaten Polynomen (wie Spartan oder HyperPlonk) basieren, wächst das Interesse an neuen Commitment-Schemata, die für solche Polynome geeignet sind. Binius, Zeromorph und Basefold schlagen alle neue Formen für multilineare Polynome vor. Binius hat den Vorteil, dass es keinen Overhead für die Darstellung von Datentypen gibt (während viele Beweissysteme mindestens 32-Bit-Feldelemente zur Darstellung eines einzelnen Bits verwenden) und arbeitet im Binärbereich. Das Binius-Versprechen basiert auf Brakedown und ist domänenunabhängig konzipiert. Basefold verallgemeinert FRI auf Codes jenseits von Reed-Solomon, was zu domänenunabhängigen PCS führt.

2) Anpassbare Constraint-Systeme (CCS) (2023)

CCS verallgemeinert R1CS und erfasst gleichzeitig R1CS-, Plonkish- und AIR-Arithmetik ohne Overhead. Durch die Kombination von CCS mit Spartan IOP entsteht SuperSpartan, das hochgradige Einschränkungen unterstützt, ohne dass für den Prüfer kryptografische Kosten anfallen, die mit dem Grad der Einschränkung skalieren. Insbesondere generiert SuperSpartan SNARKs für AIR mit einem linearen Zeitprüfer.

6. Fazit

Dieser Artikel beschreibt den Fortschritt von SNARK seit seiner Einführung Mitte der 1980er Jahre. Fortschritte in der Informatik, Mathematik und Hardware sowie die Einführung der Blockchain haben zu neuen, effizienteren SNARKs geführt und die Tür zu vielen Anwendungen geöffnet, die unsere Gesellschaft verändern könnten. Forscher und Ingenieure schlugen je nach Bedarf Verbesserungen und Anpassungen an SNARKs vor, wobei der Schwerpunkt auf Beweisgröße, Speichernutzung, Transparenzeinstellungen, Post-Quanten-Sicherheit, Prüferzeit und Verifiziererzeit lag.

Obwohl es ursprünglich zwei Hauptlinien gab (SNARK und STARK), beginnen die Grenzen zwischen den beiden zu verschwinden und man versucht, die Vorteile verschiedener Beweissysteme zu kombinieren. Beispielsweise die Kombination verschiedener arithmetischer Schemata mit neuen Polynom-Commitment-Schemata. Es ist zu erwarten, dass weiterhin neue Proofsysteme entstehen und sich die Leistung verbessern wird. Für einige Systeme, die einige Zeit zur Anpassung benötigen, wird es jedoch schwierig sein, mit diesen Entwicklungen Schritt zu halten, es sei denn, die Tools können problemlos verwendet werden, ohne dass einige Kerninfrastrukturen geändert werden müssen .

Das obige ist der detaillierte Inhalt vonEntdecken Sie die wahren Gründe für die Entstehung zeitloser Innovationen bei wissensfreien Beweisen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!