Autor: LambdaClass die Richtigkeit einer Aussage, ohne dass über die Aussage hinausgehende Informationen preisgegeben werden. 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) erheblich beschleunigt. zk-SNARKs spielen eine entscheidende Rolle bei der Skalierbarkeit der Blockchain. Wie Ben-Sasson feststellt, kam es in den letzten Jahren zu einer kambrischen Explosion kryptografischer Beweise. 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 alle ein wichtiges Merkmal gemeinsam: schnelle Überprüfbarkeit. Die mit der Änderung von Basisschichten wie Ethereum verbundenen Schwierigkeiten können durch eine Schicht gelöst werden, die Beweise überprüft und sich flexibel an neue Beweissysteme anpassen kann. In diesem Artikel werden die verschiedenen Eigenschaften von SNARKs kurz beschrieben: 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. GrundkenntnisseZero-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) Zero-Knowledge-Beweis: Ursprünge (1985/1989). Das Gebiet des wissensfreien Beweises 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 über die Ursprünge können Sie sich das Video ZKP MOOC Lecture 1: Introduction and History of ZKP vom Januar 2023 ansehen. In diesem Artikel werden die Konzepte Vollständigkeit, 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 Notwendigkeit der Summierung multivariater Polynomauswertungen 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 Prüfer linear mit der Anzahl der Gatter in der Schaltung und der Prüfer sublinear mit der Größe der Schaltung 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 durch das Sumcheck-Protokoll implementiert. 4) KZG-Polynom-Commitment-Schema (2010).Kate, Zaverucha und Goldberg führten 2010 in Constant-Size Commitments to Polynomials and Their Applications ein Polynom-Commitment-Schema unter Verwendung bilinearer Paarungsgruppen ein. 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 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.
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) Nutzen Sie Setups, die universell 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 und Plonk ( 2019)
5) Lookups (2018/2020)
6) Spartan (2019)
7) HyperPlonk (2022)
8) Faltschemata (2008/2021)
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, bei dem die Prüfzeit eine sublineare Beziehung zur Tabellengröße hat. Seine Vorverarbeitungszeit beträgt O (N log N) und der Speicher beträgt O (N), wobei N die Tabellengröße ist. Es folgten mehrere andere Lösungen, 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 Lookups nachzuweisen.
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.
HyperPlonk basiert auf der Idee von Plonk, Polynome mit mehreren Variablen zu verwenden. Es basiert nicht auf Quotienten, um die Ausführung 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 die Arbeitsbelastung des Prüfers, die Prüfgröße und die Prüfzeit reduziert.
Nova stellt die Idee von Faltschemata vor, eine neue Methode 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.
Ungefähr zur gleichen Zeit, als Pinocchio entwickelt wurde, gab es einige Ideen zur Generierung von Schaltkreisen/Rechenschemata, die die Korrektheit der Ausführung virtueller Maschinen 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, nachgewiesen werden kann, indem nachgewiesen wird, dass es in einer virtuellen Maschine korrekt ausgeführt wird. 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-basiertes SNARK entwickelt, um die Korrektheit der C-Programmausführung zu beweisen, das in TinyRAM (Reduced Instruction Set Computer) kompiliert wird. Der Computer verwendet die Harvard-Architektur mit adressierbarem Direktzugriffsspeicher auf Byte-Ebene. Unter Ausnutzung des Nichtdeterminismus steht die Größe der Schaltung in einem quasilinearen Verhältnis zur Größe der Berechnung, wodurch beliebige datenbezogene Schleifen, Kontrollflüsse und Speicherzugriffe effizient verarbeitet werden können.
2) STARKs (2018)
STARKs wurde 2018 von Ben Sasson et al. vorgeschlagen. Die implementierte Beweisgröße beträgt O(log2n), es verfügt über schnelle Prüfer und Verifizierer, erfordert keine vertrauenswürdige Einrichtung 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.
Der Einsatz verschiedener Proofsysteme in der Produktion zeigt die Vorteile der einzelnen Methoden und bringt neue Entwicklungen mit sich. Beispielsweise bietet die plonkische Arithmetik eine einfache Möglichkeit, benutzerdefinierte Gates und Suchargumente einzubeziehen, da PCS eine hervorragende Leistung vor Plonky aufweist. Ebenso verbessert die Verwendung einer großen Produktprüfung in AIR (was zu randomisiertem AIR mit Vorverarbeitung führt) die Leistung und vereinfacht die Argumente für den Speicherzugriff. 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) Neue Polynom-Commitment-Schemata (2023)
Mit dem Aufkommen effizienter SNARKs basierend auf multivariaten Polynomen (wie Spartan oder HyperPlonk) steigt 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, Datentypen ohne Overhead darzustellen (während viele Beweissysteme mindestens 32-Bit-Feldelemente verwenden, um ein einzelnes Bit darzustellen) und arbeitet mit dem Binärfeld. Binius verspricht, auf Brakedown zu basieren und domänenunabhängig zu sein. 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 R1CS-, Plonkish- und AIR-Arithmetik gleichzeitig ohne Overhead. Die Kombination von CCS mit Spartan IOP führt zu SuperSpartan, das hochgradige Einschränkungen unterstützt, ohne dass der Prüfer kryptografische Kosten tragen muss, die mit dem Grad der Einschränkung skalieren. Insbesondere generiert SuperSpartan SNARKs für AIR mit einem linearen Zeitnachweis.
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. Zum Beispiel 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 vonIOSG: Was ist die treibende Kraft für kontinuierliche Innovation bei wissensfreien Beweisen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!