Unsere höchst subjektive Sicht auf die Geschichte der Zero-Knowledge-Proofs

Zero-Knowledge, Succinct, Non-interactive ARguments of Knowledge (zk-SNARKs) sind mächtige kryptographische Primitive, die es einer Partei, dem Beweiser, ermöglichen, eine andere Partei, den Verifizierer, davon zu überzeugen, dass eine bestimmte Aussage wahr ist, ohne etwas anderes als die Gültigkeit der Aussage preiszugeben. Sie haben aufgrund ihrer Anwendungen in überprüfbaren privaten Berechnungen, die den Nachweis der Korrektheit der Ausführung von Computerprogrammen erbringen und bei der Skalierung von Blockchains helfen, große Aufmerksamkeit erlangt. Wir glauben, dass SNARKs einen erheblichen Einfluss auf die Gestaltung unserer Welt haben werden, wie wir in unserem Beitrag beschreiben. SNARKs fungiert als Dach für verschiedene Arten von Beweissystemen, die verschiedene polynomiale Commitment-Schemata (PCS), Arithmetisierungsschemata, interaktive Orakelbeweise (IOP) oder probabilistisch überprüfbare Beweise (PCP) verwenden. Die grundlegenden Ideen und Konzepte stammen jedoch aus der Mitte der 1980er Jahre. Die Entwicklung hat sich nach der Einführung von Bitcoin und Ethereum erheblich beschleunigt, was sich als spannender und leistungsstarker Anwendungsfall erwiesen hat, da man sie durch die Verwendung von Zero-Knowledge-Beweisen (für diesen speziellen Anwendungsfall allgemein als Validitätsbeweise bezeichnet) skalieren kann. SNARKs sind ein wesentliches Werkzeug für die Skalierbarkeit der Blockchain. Wie Ben-Sasson beschreibt, gab es in den letzten Jahren eine kambrische Explosion kryptographischer Beweise. Jedes Proof-System bietet Vor- und Nachteile und wurde unter Berücksichtigung bestimmter Kompromisse entwickelt. Fortschritte in der Hardware, bessere Algorithmen, neue Argumente und Gadgets führen zu einer verbesserten Leistung und der Geburt neuer Systeme. Viele von ihnen werden in der Produktion eingesetzt, und wir verschieben immer wieder die Grenzen. Werden wir ein allgemeines Nachweissystem für alle Anwendungen haben oder mehrere Systeme, die für unterschiedliche Anforderungen geeignet sind? Wir halten es für unwahrscheinlich, dass ein Beweissystem sie alle beherrscht, weil:

1. Die Vielfalt der Anwendungen.
2. Die Arten von Einschränkungen, die wir haben (in Bezug auf Speicher, Überprüfungszeiten, Prüfzeiten).
3. Das Bedürfnis nach Robustheit (wenn ein Beweissystem kaputt geht, haben wir immer noch andere).

Auch wenn sich Nachweissysteme stark ändern, bieten sie alle eine wesentliche Eigenschaft: Nachweise können schnell verifiziert werden. Eine Schicht zu haben, die Beweise verifiziert und leicht an neue Beweissysteme angepasst werden kann, löst die Schwierigkeiten, die mit der Änderung der Basisschicht verbunden sind, wie z. B. Ethereum. Um einen Überblick über die verschiedenen Eigenschaften von SNARKs zu geben:

• Kryptographische Annahmen: kollisionsresistente Hash-Funktionen, diskretes Log-Problem über elliptischen Kurven, Kenntnis des Exponenten.
• Transparentes vs. vertrauenswürdiges Setup.
• Prover-Zeit: linear vs. superlinear.
• Prüfzeit: konstante Zeit, logarithmisch, sublinear, linear.
• Proof-Größe.
• Einfache Rekursion.
• Arithmetisierungs-Schema.
• Univariate vs. multivariate Polynome.

Dieser Beitrag befasst sich mit den Ursprüngen von SNARKs, einigen grundlegenden Bausteinen und dem Aufstieg (und Fall) verschiedener Beweissysteme. Der Beitrag erhebt nicht den Anspruch, eine erschöpfende Analyse von Beweissystemen zu sein. Wir konzentrieren uns stattdessen auf diejenigen, die uns beeinflusst haben. Natürlich waren diese Entwicklungen nur mit der großartigen Arbeit und den Ideen der Pioniere auf diesem Gebiet möglich.

Grundlagen

Wie bereits erwähnt, sind Zero-Knowledge-Beweise nicht neu. Die Definitionen, Grundlagen, wichtigen Theoreme und sogar wichtigen Protokolle wurden ab Mitte der 1980er Jahre festgelegt. Einige der wichtigsten Ideen und Protokolle, die wir verwenden, um moderne SNARKs zu bauen, wurden in den 1990er Jahren (das Sumcheck-Protokoll) oder sogar vor dem Aufkommen von Bitcoin (GKR im Jahr 2007) vorgeschlagen. Die Hauptprobleme bei der Einführung hingen mit dem Fehlen eines leistungsstarken Anwendungsfalls zusammen (das Internet war in den 1990er Jahren noch nicht so weit entwickelt) und der Menge an benötigter Rechenleistung.

Zero-Knowledge-Beweise: die Ursprünge (1985/1989)

Das Feld der Zero-Knowledge-Proofs tauchte mit der Arbeit von Goldwasser, Micali und Rackoff in der akademischen Literatur auf. Für eine Diskussion über die Ursprünge können Sie sich das folgende Video ansehen. Der Artikel führte die Begriffe Vollständigkeit, Solidität und Nullwissen ein und lieferte Konstruktionen für quadratische Residuosität und quadratische Nicht-Residuosität.

Sumcheck-Protokoll (1992)

Das Sumcheck-Protokoll wurde 1992 von Lund, Fortnow, Karloff und Nisan vorgeschlagen. Es ist einer der wichtigsten Bausteine für prägnante interaktive Proofs. Es hilft uns, eine Behauptung über die Summe der Auswertungen eines multivariaten Polynoms auf eine einzige Auswertung an einem zufällig ausgewählten Punkt zu reduzieren.

Goldwasser-Kalai-Rothblum (GKR) (2007)

Das GKR-Protokoll ist ein interaktives Protokoll, das über einen Prüfer verfügt, der linear in der Anzahl der Gatter eines Schaltkreises läuft, während der Verifizierer in der Größe des Schaltkreises sublinear läuft. In dem Protokoll einigen sich der Prüfer und der Verifizierer auf eine arithmetische Schaltung von Fan-in-Two über ein endliches Feld der Tiefe d, wobei die Schicht d der Eingabeschicht und die Schicht 0 der Ausgabeschicht entspricht. Das Protokoll beginnt mit einem Anspruch auf den Ausgang der Schaltung, der auf einen Anspruch auf die Werte der vorherigen Schicht reduziert wird. Mit Hilfe der Rekursion können wir daraus einen Anspruch auf die Eingänge der Schaltung machen, der leicht überprüft werden kann. Diese Reduktionen werden über das Sumcheck-Protokoll erreicht.

KZG-Polynom-Commitment-Schema (2010)

Kate, Zaverucha und Goldberg führten 2010 ein Commitment-Schema für Polynome ein, das eine bilineare Paarungsgruppe verwendet. Der Commit besteht aus einem einzelnen Gruppenelement, und der Committer kann den Commit effizient für jede korrekte Auswertung des Polynoms öffnen. Darüber hinaus kann die Öffnung aufgrund von Batching-Techniken für mehrere Auswertungen erfolgen. Die KZG-Verpflichtungen waren einer der Grundbausteine für mehrere effiziente SNARKs wie Pinocchio, Groth16 und Plonk. Es ist auch das Herzstück des EIP-4844. Um eine Intuition für Batching-Techniken zu bekommen, können Sie unseren Beitrag über die Mina-Ethereum-Brücke lesen.

Praktische SNARKs mit elliptischen Kurven

Im Jahr 2013 erschienen die ersten praktischen Konstruktionen für SNARKs. Diese erforderten einen Vorverarbeitungsschritt zur Generierung der Prüf- und Verifizierungsschlüssel und waren programm-/schaltungsspezifisch. Diese Schlüssel konnten recht umfangreich sein und hingen von geheimen Parametern ab, die den Parteien unbekannt bleiben sollten. Andernfalls könnten sie Beweise fälschen. Um Code in etwas umzuwandeln, das bewiesen werden konnte, musste der Code in ein System von polynomialen Einschränkungen kompiliert werden. Zunächst musste dies manuell erfolgen, was zeitaufwendig und fehleranfällig ist. Mit den Fortschritten in diesem Bereich wurde versucht, einige der Hauptprobleme zu beseitigen:

1. Haben Sie effizientere Beweise.
2. Reduzieren Sie den Umfang der Vorverarbeitung.
3. Universelle statt schaltungsspezifische Setups.
4. Vermeiden Sie vertrauenswürdige Setups.
5. Entwicklung von Möglichkeiten zur Beschreibung von Schaltkreisen mit einer Hochsprache, anstatt die polynomialen Nebenbedingungen manuell zu schreiben.

Pinocchio (2013)

Pinocchio ist der erste praktische, nutzbare zk-SNARK. Das SNARK basiert auf quadratischen arithmetischen Programmen (QAP). Die Proofgröße betrug ursprünglich 288 Bytes. Die Toolchain von Pinocchio lieferte einen Compiler von C-Code bis hin zu arithmetischen Schaltkreisen, der wiederum in eine QAP umgewandelt wurde. Das Protokoll erforderte, dass der Verifizierer die Schlüssel generierte, die leitungsspezifisch sind. Es verwendete elliptische Kurvenpaare, um die Gleichungen zu überprüfen. Die Asymptotik für die Beweisgenerierung und die Schlüsseleinrichtung war linear in der Rechengröße, und die Verifikationszeit war linear in der Größe der öffentlichen Ein- und Ausgänge.

Groth 16 (2016)

Groth führte ein neues Argument des Wissens mit erhöhter Leistung für Probleme ein, die von einem R1CS beschrieben wurden. Es hat die kleinste Proofgröße (nur drei Gruppenelemente) und eine schnelle Verifikation mit drei Paarungen. Es umfasst auch einen Vorverarbeitungsschritt, um die strukturierte Referenzzeichenfolge zu erhalten. Der Hauptnachteil ist, dass es für jedes Programm, das wir beweisen wollen, ein anderes vertrauenswürdiges Setup erfordert, was unpraktisch ist. Groth16 wurde in ZCash verwendet.

Bulletproofs & IPA (2016)

Einer der Schwachpunkte des KZG-PCS ist, dass es ein vertrauenswürdiges Setup erfordert. Bootle et al. führte ein effizientes Zero-Knowledge-Argumentationssystem für Öffnungen von Pedersen-Verpflichtungen ein, die eine innere Produktbeziehung befriedigen. Das Argument des inneren Produkts hat einen linearen Beweis mit logarithmischer Kommunikation und Interaktion, aber mit linearer Zeitverifikation. Sie entwickelten auch ein polynomiales Commitment-Schema, das kein vertrauenswürdiges Setup erfordert. PCS, die diese Ideen verwenden, werden von Halo 2 und Kimchi verwendet.

Sonic, Marlin und Plonk (2019)

Sonic, Plonk und Marlin lösen das Problem des vertrauenswürdigen Setups pro Programm, das wir in Groth16 hatten, indem sie universelle und aktualisierbare strukturierte Referenzzeichenfolgen einführten. Marlin bietet ein Proof-System auf Basis von R1CS und ist das Herzstück von Aleo.

Plonk führte ein neues Arithmetisierungsschema (später Plonkish genannt) und die Verwendung der Grand-Product-Prüfung für die Kopierbeschränkungen ein. Plonkish erlaubte auch die Einführung von spezialisierten Toren für bestimmte Operationen, den sogenannten Custom Gates. Mehrere Projekte haben angepasste Versionen von Plonk, darunter Aztec, zkSync, Polygon ZKEVM, Mina's Kimchi, Plonky2, Halo 2 und Scroll, um nur einige zu nennen.

Nachschlagewerke (2018/2020)

Gabizon und Williamson führten Plookup im Jahr 2020 ein, bei dem mit dem Grand Product Check nachgewiesen wird, dass ein Wert in einer vorberechneten Wertetabelle enthalten ist. Obwohl die Argumente für die Suche zuvor in Arya vorgestellt wurden, erforderte die Konstruktion die Bestimmung der Multiplizitäten für die Lookups, was die Konstruktion weniger effizient macht. Das PlonkUp-Papier zeigte, wie das Nachschlageargument in Plonk eingeführt werden kann. Das Problem mit diesen Lookup-Argumenten war, dass sie den Beweisenden zwangen, den Preis für die gesamte Tabelle zu zahlen, unabhängig von der Anzahl seiner Lookups. Dies bedeutet erhebliche Kosten für große Tabellen, und es wurde viel Aufwand betrieben, um die Kosten für den Prüfer auf die Anzahl der von ihm verwendeten Suchvorgänge zu reduzieren.
Haböck führte LogUp ein, das die logarithmische Ableitung verwendet, um die Prüfung des Gesamtprodukts in eine Summe von Kehrwerten umzuwandeln. LogUp ist entscheidend für die Leistung im Polygon ZKEVM, wo die gesamte Tabelle in mehrere STARK-Module aufgeteilt werden muss. Diese Module müssen korrekt verknüpft sein, und tabellenübergreifende Lookups erzwingen dies. Die Einführung von LogUp-GKR nutzt das GKR-Protokoll , um die Leistung von LogUp zu erhöhen. Caulk war das erste Schema mit sublinearer Beweiszeit in der Tabellengröße, indem die Vorverarbeitungszeit O(NlogN) und die Speicherzeit O(N) verwendet wurden, wobei N die Tabellengröße ist. Es folgten mehrere andere Schemata, wie z. B. Baloo, flookup, cq und caulk+. Lasso bietet mehrere Verbesserungen , indem es vermeidet, sich auf die Tabelle festzulegen, wenn sie eine bestimmte Struktur hat. Außerdem zahlt der Beweisbeweis von Lasso nur für Tabelleneinträge, auf die durch die Suchvorgänge zugegriffen wird. Jolt nutzt Lasso, um die Ausführung einer virtuellen Maschine über Lookups nachzuweisen.

Spartanisch (2019)

Spartan bietet einen IOD für Schaltkreise, die mit R1CS beschrieben werden, und nutzt dabei die Eigenschaften multivariater Polynome und das Sumcheck-Protokoll. Unter Verwendung eines geeigneten polynomialen Commitment-Schemas ergibt sich ein transparentes SNARK mit einem linearen Zeitnachweis.

HyperPlonk (2022)

HyperPlonk baut auf den Ideen von Plonk auf und verwendet multivariate Polynome. Anstelle von Quotienten, um die Durchsetzung der Einschränkungen zu überprüfen, wird das Sumcheck-Protokoll verwendet. Es unterstützt auch Einschränkungen in hohem Maße, ohne die Laufzeit des Prüfers zu beeinträchtigen. Da er auf multivariaten Polynomen beruht, müssen keine FFTs durchgeführt werden, und die Laufzeit des Prüfers ist linear in der Schaltungsgröße. HyperPlonk führt einen neuen Permutations-IOD ein, der für kleinere Felder geeignet ist, und ein auf Summenprüfung basierendes Batch-Öffnungsprotokoll, das die Arbeit des Prüfers, die Proofgröße und die Zeit des Prüfers reduziert.

Faltschemata (2008/2021)

Nova führt die Idee eines Faltungsschemas ein, bei dem es sich um einen neuen Ansatz handelt, um inkrementell verifizierbare Berechnungen (IVC) zu erreichen. Das Konzept der IVC geht auf Valiant zurück, der zeigte, wie man zwei Beweise der Länge k zu einem einzigen Beweis der Länge k zusammenführt. Die Idee ist, dass wir jede lang andauernde Berechnung beweisen können, indem wir rekursiv beweisen, dass die Ausführung von Schritt i zu Schritt I+1+1 korrekt ist, und einen Beweis verifizieren, der zeigt, dass der Übergang von Schritt i

−1−1Schritt I war richtig. Nova kommt gut mit einheitlichen Berechnungen zurecht; Später wurde es mit der Einführung von Supernova erweitert, um verschiedene Arten von Schaltkreisen zu handhaben. Nova verwendet eine entspannte Version von R1CS und arbeitet über sanfte elliptische Kurven. Die Arbeit mit einvernehmlichen Kurvenzyklen (z. B. den Pasta-Kurven), um IVC zu erreichen, wird auch in Pickles verwendet, Minas Hauptbaustein, um einen prägnanten Zustand zu erreichen. Die Idee der Faltung unterscheidet sich jedoch von der rekursiven SNARK-Verifikation. Die Akkumulator-Idee ist tiefer mit dem Konzept der Batching-Proofs verbunden. Halo führte den Begriff der Akkumulation als Alternative zur rekursiven Beweiskomposition ein. Protostar bietet ein uneinheitliches IVC-Schema für Plönk, das High-Degree-Gates und Vektor-Lookups unterstützt.

Kollisionsresistente Hash-Funktionen verwenden

Etwa zur gleichen Zeit, als Pinocchio entwickelt wurde, gab es einige Ideen, Schaltkreise/Arithmetisierungsschemata zu generieren, die die Korrektheit der Ausführung einer virtuellen Maschine beweisen konnten. Auch wenn die Entwicklung der Arithmetisierung einer virtuellen Maschine komplexer oder weniger effizient sein konnte als das Schreiben dedizierter Schaltkreise für einige Programme, bot sie den Vorteil, dass jedes noch so komplizierte Programm bewiesen werden konnte, indem gezeigt wurde, dass es in der virtuellen Maschine korrekt ausgeführt wurde. Die Ideen in TinyRAM wurden später mit dem Design der Cairo VM und nachfolgender virtueller Maschinen (wie zk-evms oder allgemeine zkvms) verbessert. Durch die Verwendung von kollisionsresistenten Hash-Funktionen entfiel die Notwendigkeit vertrauenswürdiger Setups oder die Verwendung von elliptischen Kurvenoperationen, auf Kosten längerer Beweise.

TinyRAM (2013)

In SNARKs for C entwickelten sie ein SNARK auf Basis eines PCP, um die Korrektheit der Ausführung eines C-Programms zu beweisen, das auf TinyRAM, einen Computer mit reduziertem Befehlssatz, kompiliert wird. Der Computer verwendete eine Harvard-Architektur mit adressierbarem Direktzugriffsspeicher auf Byte-Ebene. Durch die Nutzung des Nichtdeterminismus ist die Größe der Schaltung quasilinear in Bezug auf die Größe der Berechnung, wodurch beliebige und datenabhängige Schleifen, Kontrollflüsse und Speicherzugriffe effizient verarbeitet werden.

STARKs (2018)

STARKs wurden 2018 von Ben Sasson et al. eingeführt. Sie erreichen O(log2n)(log2)

Proof-Größen mit schnellem Prüfer und Verifizierer erfordern kein vertrauenswürdiges Setup und gelten als Post-Quantum-sicher. Sie wurden zuerst von Starkware/Starknet zusammen mit der Cairo vm verwendet. Zu den wichtigsten Einführungen gehören die algebraische Zwischendarstellung (AIR) und das FRI-Protokoll (Fast Reed-Solomon Interactive Oracle Proof of Proximity). Es wird auch von anderen Projekten verwendet (Polygon Miden, Risc0, Winterfell, Neptune) oder hat Anpassungen einiger Komponenten gesehen (zkSync's Boojum, Plonky2, Starky).

Ligero (2017)

Ligero stellt ein Beweissystem vor, mit dem Nachweise erzielt werden, deren Größe

O(√n), wobei n die Größe des Schaltkreises ist. Es ordnet die Polynomkoeffizienten in Matrixform an und verwendet lineare Codes.
Brakedown baut auf Ligero auf und führt die Idee von feldagnostischen polynomialen Commitment-Schemata ein.

Einige neue Entwicklungen

Der Einsatz unterschiedlicher Nachweissysteme in der Produktion zeigte die Vorzüge der einzelnen Ansätze und führte zu neuen Entwicklungen. Beispielsweise bietet die plonkische Arithmetisierung eine einfache Möglichkeit, benutzerdefinierte Gatter und Nachschlageargumente einzuschließen. FRI hat als PCS eine großartige Leistung gezeigt, was zu Plonic führte. In ähnlicher Weise verbesserte die Verwendung der großen Produktprüfung in AIR (die zu einer randomisierten AIR mit Vorverarbeitung führte) die Leistung und vereinfachte die Argumente für den Speicherzugriff. Verpflichtungen, die auf Hash-Funktionen basieren, haben an Popularität gewonnen, basierend auf der Geschwindigkeit von Hash-Funktionen in Hardware oder der Einführung neuer SNARK-freundlicher Hash-Funktionen.

Neue polynomiale Verpflichtungsschemata (2023)

Mit dem Aufkommen effizienter SNARKs, die auf multivariaten Polynomen basieren, wie z. B. Spartan oder HyperPlonk, ist das Interesse an neuen Commitment-Schemata gestiegen, die für diese Art von Polynomen geeignet sind. Binius, Zeromorph und Basefold schlagen alle neue Formen vor, um multilineare Polynome zu definieren. Binius bietet den Vorteil, dass es keinen Overhead für die Darstellung von Datentypen hat (während viele Beweissysteme mindestens 32-Bit-Feldelemente verwenden, um einzelne Bits darzustellen) und funktioniert mit binären Feldern. Das Engagement passt den Brakedown an, der so konzipiert wurde, dass er feldunabhängig ist. Basefold verallgemeinert FRI auf andere Codes als Reed-Solomon, was zu einem feldunabhängigen PCS führt.

Anpassbare Beschränkungssysteme (2023)

CCS verallgemeinert R1CS und erfasst gleichzeitig R1CS-, Plonkish- und AIR-Arithmetisierung ohne Overhead. Die Verwendung von CCS mit Spartan IOP ergibt SuperSpartan, das Einschränkungen mit hohem Grad unterstützt, ohne dass der Beweis dafür besteht, dass kryptografische Kosten anfallen, die mit dem Grad der Einschränkung skaliert werden. Insbesondere liefert SuperSpartan ein SNARK für AIR mit einem linearen Zeitnachweis.

Schlussfolgerung

Dieser Beitrag beschreibt die Fortschritte von SNARKs seit ihrer Einführung Mitte der 1980er Jahre. Fortschritte in der Informatik, Mathematik und Hardware haben zusammen mit der Einführung der Blockchain zu neuen und effizienteren SNARKs geführt, die die Tür für viele Anwendungen öffnen, die unsere Gesellschaft verändern könnten. Forscher und Ingenieure haben Verbesserungen und Anpassungen an SNARKs entsprechend ihren Bedürfnissen vorgeschlagen, wobei der Schwerpunkt auf der Proofgröße, der Speichernutzung, dem transparenten Aufbau, der Post-Quanten-Sicherheit, der Testzeit und der Verifier-Zeit lag. Während es ursprünglich zwei Hauptlinien gab (SNARKs vs. STARKs), hat sich die Grenze zwischen beiden zu verflüchtigen begonnen, um die Vorteile der verschiedenen Beweissysteme zu kombinieren. Zum Beispiel die Kombination verschiedener Arithmetisierungsschemata mit neuen polynomialen Commitment-Schemata. Wir können davon ausgehen, dass neue Nachweissysteme mit zunehmender Leistung weiter zunehmen werden, und es wird für einige Systeme, die einige Zeit benötigen, um sich anzupassen, schwierig sein, mit diesen Entwicklungen Schritt zu halten, es sei denn, wir können diese Tools problemlos verwenden, ohne eine Kerninfrastruktur ändern zu müssen.

Verzichtserklärung:

1. Dieser Artikel ist ein Nachdruck von [lambdaclass], Alle Urheberrechte liegen beim ursprünglichen Autor [LambdaClass]. Wenn es Einwände gegen diesen Nachdruck gibt, wenden Sie sich bitte an das Gate Learn-Team , das sich umgehend darum kümmern wird.
2. Haftungsausschluss: Die in diesem Artikel geäußerten Ansichten und Meinungen sind ausschließlich die des Autors und stellen keine Anlageberatung dar.
3. Übersetzungen des Artikels in andere Sprachen werden vom Gate Learn-Team durchgeführt. Sofern nicht anders angegeben, ist das Kopieren, Verbreiten oder Plagiieren der übersetzten Artikel verboten.