1. Einleitung
ZK-SNARK ist ein kryptografisches Beweissystem, das es einer Entität ermöglicht, zu beweisen, dass etwas wahr ist, ohne andere Informationen preiszugeben.
ZK-SNARKs sind in verschiedenen Anwendungen und Bereichen nützlich, beispielsweise in der Blockchain und im verifizierbaren Computing. Eine bemerkenswerte Blockchain-Anwendung wird in ZK-Rollups verwendet.
ZK-Rollups sind Blockchains der zweiten Schicht, die auf anderen Blockchains (wie Ethereum) aufbauen und ZK-SNARKs (oder andere kryptografische Beweissysteme) verwenden, um die Gültigkeit von Zustandsübergängen zu beweisen. Das heißt, jedes Mal, wenn eine neue Netzwerkaktualisierung durchgeführt wird (ein neuer Transaktionsstapel hinzugefügt wird), wird ein neuer Netzwerkstatus berechnet und ein Beweis für die Gültigkeit dieses Status generiert. Der Punkt ist, dass nur eine Entität erforderlich ist, um diesen Beweis zu erstellen, und jeder dann auf seine Gültigkeit vertrauen kann.
Gewünschte Eigenschaften von ZK-Rollups sind in der Regel (i) Skalierbarkeit und/oder (ii) Datenschutz. ZK-Rollups werden manchmal als Effektivitäts-Rollups bezeichnet, wenn nur Skalierbarkeit erforderlich ist.
Um Beweise in ZK-Rollups zu berechnen, die die EVM von Ethereum erweitern sollen, kann ZK-EVM verwendet werden. Streng definiert handelt es sich bei ZK-EVM um eine Reihe von kryptografischen Programmen (Schaltkreisen), die für die Generierung von Zero-Knowledge-Proofs (ZKP) verantwortlich sind, obwohl manchmal umgangssprachlich damit auch das EVM-fähige universelle ZK-Rollup als Ganzes gemeint ist.
2.ZK-SNARK-Definition
Ein SNARK ist ein prägnanter Beweis dafür, dass eine bestimmte Aussage wahr ist. Formal demonstriert es die Kenntnis der Ausführungsspur eines Algorithmus, die eine korrekte Lösung für ein bestimmtes Problem liefert. Vielmehr demonstriert es das Wissen über nicht öffentliche und nicht konstante Werte, die das Tracking durchführen. Diese Werte in ihrer Gesamtheit werden oft als Zeugen bezeichnet. Die Elemente des Zeugen, also die Teile der Eingabe in den Algorithmus, stellen unabhängige Zeugen dar, da sie vor der Ausführung des Algorithmus vorhanden sind und nicht durch andere Elemente des Ausführungs-Trace bestimmt werden. Der öffentliche, nicht konstante Wert des Ausführungs-Trace, der die Probleminstanz angibt, die der Algorithmus löst, wird als öffentliche Anweisung bezeichnet.
ZK-SNARK steht für Zero-Knowledge Succinct Non-Interactive Knowledge Argument.
S – Einfachheit
Einfachheit – der Beweis ist „kurz“ und die Verifizierungszeit ist „schnell“:
Ein „kurzer“ Beweis bedeutet, dass die Größe des Beweises im Verhältnis zur Größe des Zeugen sublinear ist.
„Schnelle“ Verifizierungszeit bedeutet, dass die Laufzeit des Verifizierers (i) in Bezug auf die Größe des Zeugen sublinear und (ii) in Bezug auf den öffentlichen Anspruch linear sein sollte.
Tatsächlich möchten wir jedoch, dass es nicht nur „prägnant“, sondern auch „log-polynomial“ ist.
Dies bedeutet, dass Beweisgröße und Überprüfungszeit nahezu unabhängig von der Größe des Zeugen sind.
Beweisen Sie, dass die Größe von π nicht schneller wachsen sollte als ein konstantes Vielfaches des Quadrats des Logarithmus der Größe des Zeugen w (für ausreichend großes w):
Der Umfang des Nachweises hängt vom spezifischen ZK-SNARK-Protokoll ab. Für Plonky2 ist es O(log^2(|w|)), aber das ist der „schlimmste“ Fall. Für klassisches PLONK und Groth16 beträgt die Größe des Beweises beispielsweise O(1), was eine Konstante ist.
Die Überprüfungszeit t_v sollte nicht mehr als ein konstantes Vielfaches des Quadrats des Logarithmus des Zeugen w betragen und linear in der Größe der öffentlichen Erklärung x sein (x und w sind groß genug, wenn nur einer von ihnen seine Größe ändert).
N – Nicht interaktiv – Die Beweiserstellung erfolgt, ohne dass Daten vom Prüfer empfangen werden.
ARK – Wissensbeweis – Ähnlich wie reguläre Beweise, aber der Klang gilt nur für polynomial begrenzte Beweiser, während der Klang bei Beweisen für rechnerisch unbegrenzte Beweiser gilt. Wir werden das Konzept des Klangs im nächsten Abschnitt besprechen.
ZK – Zero Knowledge – Keine Zeugenauskunft.
3. Eigenschaften von ZK-SNARKs
ZK-SNARKs haben drei Haupteigenschaften, wie unten beschrieben:
Vollständigkeit: Wenn der Prüfer den korrekten Ausführungsverlauf des Algorithmus kennt, muss der Prüfer davon ausgehen, dass der Prüfer über dieses Wissen verfügt.
Wissenssicherheit: Sofern der Prüfer nicht tatsächlich die korrekte Ausführungsbahn kennt, kann der Prüfer den Prüfer nicht davon überzeugen, dass er sie kennt, aber es besteht eine sehr geringe Wahrscheinlichkeit.
Wissensfrei: Der Verifizierer weiß nichts über den Ausführungsverlauf, außer dass er korrekt ist.
4.PLONKisches ZK-SNARK-Proof-System
4.1 Einführung in PLONKish ZK-SNARKs und ihre Funktionen
Um auf einen bestimmten Algorithmus angewendet zu werden, muss das ZK-SNARK-Beweissystem das Gleichungssystem auf dem endlichen Körper kennen. Diese Gleichungen beschreiben die Beziehung zwischen den Werten in der Ausführungs-Trajektorientabelle des Algorithmus (die Datenstruktur, die die Ausführungstrajektorie speichert), um sicherzustellen, dass die Berechnung Integrität ist. Die Sprache, mit der dieses Gleichungssystem (auch Zwangsbedingungssystem genannt) ausgedrückt wird, heißt Arithmetik.
Das PLONKish ZK-SNARK-Beweissystem verwendet Arithmetik mit höherer Ausdruckskraft als ältere Beweissysteme. Das erste erlaubt uns die Verwendung von Zwangssystemgleichungen beliebiger Polynomform über den Zwangsvariablen, während diese Gleichungen bei älteren Beweissystemen (d. h. auf R1CS basierenden Systemen) die Form linearer und quadratischer Polynome hatten. Durch diese Funktion wirkt sich das PLONKish ZK-SNARK-Beweissystem positiv auf die Recheneffizienz des Beweisers aus und erleichtert die Anwendung auf verschiedene Algorithmen. Daher sind in den letzten Jahren viele PLONK-artige ZK-SNARK-Proof-Systeme erschienen, wie zum Beispiel klassisches PLONK, Halo2, Kimchi, Plonky2, HyperPlonk usw.
In Taiko verwenden wir eine Variante des Halo2-Beweissystems, die auf dem KZG-Polynom-Commitment-Schema basiert.
Das PLONKish ZK-SNARK-Proof-System besteht aus drei Komponenten:
4.2 Verpflichtungsplan
Das Promise-Schema ermöglicht es einem Committer, einen Wert, ein sogenanntes Promise, zu veröffentlichen, der den Committer an eine Nachricht bindet, ohne die Nachricht selbst preiszugeben. Der Committer kann dann die Commitment öffnen und die Committed-Nachricht oder einen Teil davon dem Prüfer zur Verfügung stellen, der prüfen kann, ob die offengelegten Informationen mit der Commitment konsistent sind.
Verschiedene Autoren beschreiben eine unterschiedliche Anzahl von Algorithmen, aus denen ein Commitment-Schema besteht. Wir sollten jedoch mindestens vier dieser Algorithmen erwähnen:
Setup: Nimmt einige Anfangsparameter als Eingabe und generiert Setup-Parameter. Die Einstellungen geben an, (i) worauf wir uns festlegen (z. B. geben wir für das unäre Polynom-Verpflichtungsschema den Koeffizientenbereich und den maximalen Grad des Polynoms an, auf das wir uns festlegen) und (ii) die Sicherheitsstufe in Bits. Wir können die Sicherheitsstufe einfach wie folgt definieren: Wenn es O(2^n) Zeit braucht, um ein Verschlüsselungssystem zu knacken, dann hat das Verschlüsselungssystem eine Sicherheitsstufe von n Bits.
Versprechen: Ein Versprechen, das Nachrichten basierend auf festgelegten Parametern generiert.
Teilweise Öffnung: Erzeugt einen teilweisen Öffnungsbeweis speziell für einen ausgewählten Teil der Nachricht (z. B. den Wert eines festgelegten unären Polynoms für einen Parameter) und legt die Parameter fest.
Validierung: Verwenden Sie eine teilweise offene Attestierung und legen Sie Parameter fest, um zu überprüfen, ob die vom Prüfer offengelegten Informationen der angegebene Teil der Nachricht sind, der der angegebenen Verpflichtung entspricht.
*Bei einigen Commit-Schemata sind die Algorithmen „setup“ und „open“ möglicherweise nicht vorhanden (z. B. wenn eine Hash-Funktion zum Commit großer Werte verwendet wird).
Der Verpflichtungsplan sollte die folgenden Merkmale aufweisen:
Bindung: Sobald sich der Prüfer auf eine bestimmte Nachricht festlegt, wird er an die Nachricht gebunden, auf die er sich festgelegt hat.
Verstecken: Ein Versprechen, keine Informationen über die Nachricht preiszugeben. Das Verstecken kann perfekt sein, d. h. ein teilweise offener Beweis gibt keine Informationen über den nicht abgefragten Teil der Nachricht preis (z. B. KZG-Verpflichtung), oder nicht perfekt, d. h. ein teilweise offener Beweis enthüllt einen Teil der oben genannten Informationen (z. B. FRI-basiert). Polynombindung).
Commitment-Schemata können je nach Zielobjekt in verschiedene Typen unterteilt werden: Commitment für einzelne Elemente; Commitment für festgelegte Vektoren;
Polynom-Commitment-Schemata sind der einzige Typ, der direkt im PLONKish ZK-SNARK-Beweissystem verwendet wird. Für die oben genannten Beweissysteme (wie klassisches PLONK, Halo2, Kimchi, Plonky2 usw.) ist das univariate Polynom-Commitment-Schema sehr wichtig. Allerdings gibt es mittlerweile einige neue PLONK-artige ZK-SNARK-Methoden, die auf multilinearen Polynom-Commitment-Schemata basieren (z. B. HyperPlonk).
4.3 Interaktiver Oracle-Beweis
Ein interaktiver Oracle-Beweis ist ein interaktiver Beweis, bei dem der Prüfer „Zugriff auf das Orakel“ hat, um die Nachrichten des Prüfers zu erhalten, diese auf probabilistische Weise abfragen kann und nicht die gesamten Nachrichten des Prüfers lesen muss.
4.4 Fiat-Shamir-Heuristik
Die Fiat-Shamir-Heuristik bietet eine Möglichkeit, (öffentliche) interaktive Argumente in nicht interaktive Argumente umzuwandeln. Intuitiv besteht die Idee darin, die zufällige Abfrage des Validators durch den Hash der vorherigen Nachricht zu ersetzen, die Einzelheiten sind jedoch im Allgemeinen nicht spezifiziert.
*Public Coin Protocol ist ein Protokoll, bei dem Validatoren nur zufällige Elemente senden.
4.5 Funktionsprinzip des ZK-SNARK-Proof-Systems im PLONK-Stil
Im ZK-SNARK-Beweissystem wird eine modifizierte interaktive Oracle-Beweismethode verwendet, um das Wissen des Zeugen zu beweisen, die Polynomverpflichtungen verwendet, um Oracle Zugriff auf die Nachricht des Beweisers zu gewähren und sie durch die Fiat-Shamir-Heuristik interaktionsfrei zu machen. In diesem Abschnitt erklären wir den angegebenen Konstruktor im Detail.
Denken Sie daran, dass die Anwendung des ZK-SNARK-Beweissystems auf einen Algorithmus den Aufbau eines entsprechenden Einschränkungssystems erfordert. Um es erstellen zu können, definieren wir die Struktur der Ausführungs-Trace-Tabelle des Algorithmus und die darin enthaltenen konstanten Werte. Wir verwenden den Begriff „Schaltkreis“, um uns auf die komplexe Struktur einer Ausführungs-Trace-Tabelle zu beziehen, die nur mit Konstanten und dem entsprechenden Einschränkungssystem gefüllt ist. Um einen ZK-SNARK-Beweis für eine Ausführungsinstanz eines Algorithmus zu generieren, müssen wir eine Schaltungsinstanz dafür synthetisieren, die eine entsprechende Instanz der Schaltungs- und Ausführungs-Trace-Tabelle des Algorithmus ist (d. h. eine Tabelle, die Konstanten, Zeugen usw. angibt). und öffentliche Deklarationswerte) Kombination.
Betrachten wir die Struktur der Tracking-Tabelle, die von einem ZK-SNARK-Proof-System im PLONK-Stil verwendet wird. Alle Spalten in einer solchen Tabelle gehören zu einem von drei Typen, die wir entsprechend der in Halo2 verwendeten Terminologie benennen und wie folgt beschreiben:
Feste Spalten – ihre Zellen enthalten Konstanten aus der Ausführungs-Trace-Tabelle;
Instanzspalte – wird zum Speichern öffentlicher Deklarationswerte verwendet;
Vorschlagsspalte – in der alle Zeugendaten gespeichert werden (einschließlich unabhängiger Zeugenwerte und berechneter geheimer Ergebnisse).
Zusammenfassend stellen wir Folgendes fest:
Ausführungs-Trace-Tabelle (Typ PLONK) = feste Spalten + Instanzspalten + Vorschlagsspalten; Schaltung = Ausführungs-Trace-Tabelle, die nur Konstanten enthält + Einschränkungssystem-Schaltungsinstanz = Schaltung + Zeugen in ihrer Tabelle + öffentliche Deklarationen in ihrer Tabelle; öffentliche Aussage, unabhängiger Zeugenwert) → Schaltungsinstanz; Wenden Sie das ZK-SNARK-Beweissystem auf einen bestimmten Algorithmus an = beschreiben Sie die Schaltung + definieren Sie den Syntheseprozess.
Warum wird in diesem Zusammenhang häufig der Begriff „Schaltung“ verwendet? Als zunächst nur R1CS-basierte ZK-SNARK-Beweissysteme verfügbar waren, war es praktisch, das Einschränkungssystem in Form einer arithmetischen Schaltung darzustellen, deren Ausgabe Null sein musste. Wir glauben, dass im Zusammenhang mit PLONK-SNARKs der Begriff „Circuit“ aus historischen Gründen verwendet wird. Wie dem auch sei, betrachten wir kurz die Rechenschaltung, die für ältere Versionen von ZK-SNARK verwendet wird.
Die Rechenschaltung für R1CS-basierte SNARKs definiert ein Polynom mit n Variablen über einem endlichen Feld und verfügt über ein Bewertungsschema. Zunächst wird es als gerichteter azyklischer Graph (DAG) dargestellt:
es enthält:
Öffentliche Eingabe x, wird zur Angabe des öffentlichen Deklarationswerts verwendet;
Geheime Eingabe w, die zur Angabe des unabhängigen Zeugenwerts verwendet wird;
Arithmetische Gatter zur Spezifizierung von Addition und Multiplikation über endliche Körper.
Schauen wir uns ein Beispiel einer arithmetischen Schaltung über dem Körper der rationalen Zahlen an.
Wir beginnen von unten und arbeiten mit den niedrigsten Toren im Diagramm, also (2 x 4 = 8) und (4 + 11 = 15), und speichern diese Werte als Zwischenwerte;
Dann gehen wir eine Zeile nach oben (in die zweite Zeile) und berechnen die Summe der beiden Zwischenwerte (die wir im vorherigen Schritt erhalten haben), nämlich (8 + 15 = 23);
Da wir nur drei Tore haben und alle durchlaufen haben, ist 23 unser Endergebnis.
Nachdem das PLONKish ZK-SNARK-Proof-System die Schaltungsinstanz synthetisiert hat, werden die Spalten jeder Instanzausführungs-Trace-Tabelle auf folgende Weise als Polynome über endlichen Feldern codiert. Angenommen, C_j(x) ist ein Polynom, das die Spalte j beschreibt, und ω ist eine primitive Wurzel 2^k-th, wobei k so gewählt ist, dass 2^k etwas größer als die anfängliche Höhe der Tabelleninstanz ist. Die Tabelleninstanz wird mit zufälligen Zeilen gefüllt (nur mit Zellen ungleich Null in den vorgeschlagenen Spalten), um 2^k Zeilen zu enthalten, und C_j(ω^i) wird auf den Wert der i-ten Zeile des j-ten gesetzt Spalte der angegebenen Tabelleninstanz. Die Rolle des Auffüllens für Zero-Knowledge-Attribute wird später erläutert.
Die Aussage „ω ist eine primitive Wurzel 2^k-th“ bedeutet, dass ω^(2^k) = 1 und wir haben ω^t ≠ 1 für jede positive ganze Zahl t kleiner als 2^k.
Das Zwangsbedingungssystem wird in die Form einer Polynomgleichung umgewandelt, indem die darin enthaltenen Variablen durch die entsprechenden Polynome ersetzt werden, die aus den Spaltenpolynomen erhalten werden, indem anstelle von x „x mal ω potenziert“ eingesetzt wird.
Betrachten wir zum Beispiel die Gleichung des Zwangssystems s(i) * (a(i) * b(i) - c(i+1)) = 0. Das bedeutet, dass, wenn s(i) ungleich Null ist, a(i) * b(i) gleich c(i+1) sein muss. Hier sind a, b und c die vorgeschlagenen Spalten, s ist die feste Spalte und i ist die aktuelle Zeilennummer.
Diese Einschränkung kann wie folgt auf alle 2^k Zeilen angewendet werden. Seien S(x), A(x), B(x) und C(x) Polynome in den Spalten a, b, c bzw. s. Deshalb hoffen wir:
Das bedeutet, dass alle Elemente in dieser Menge Wurzeln von S(x) * (A(x) * B(x) - C(x * ω)) sein müssen. Daher muss dieses Polynom teilbar sein durch:
Weil ω eine primitive Wurzel der Ordnung 2^k ist.
Z(x) = x^(2^k) - 1 wird als „verschwindendes Polynom“ bezeichnet, da es für alle x, die Elemente der durch ω erzeugten zyklischen multiplikativen Gruppe sind, 0 ist. Daher bedeutet S(x) * (A(x) * B(x) - C(x * ω)) mod Z(x) = 0, dass die oben genannten Einschränkungen für alle 2^k Zeilen gelten.
Angenommen, P_0(x), P_1(x), ..., P_m(x) sind Einschränkungen, die auf alle 2^k Zeilen angewendet werden und mit dem betrachteten Polynom S(x) * (A(x) * B(x) konsistent sind oben) - C(x * ω)) hat eine ähnliche Form. Wenn α vom Prüfer zufällig aus dem endlichen Körper ausgewählt wird, dann
Dies bedeutet, dass mit extrem hoher Wahrscheinlichkeit alle diese Einschränkungen für alle 2^k Zeilen erfüllt sind. Diese Gleichung bedeutet, dass wir ein Quotientenpolynom T(x) finden können, so dass
Damit der Prüfer also davon ausgehen kann, dass der Prüfer den Inhalt der Ausführungsverfolgungstabelle kennt, die alle m Einschränkungen mit sehr hoher Wahrscheinlichkeit erfüllt, muss nur nachgewiesen werden, dass der Prüfer für ein zufällig ausgewähltes α die Vorkommen P_0 hat (x), P_1(x ),..., die vorgeschlagenen Spaltenpolynome und Quotientenpolynome T(x) in P_m(x) erfüllen diese Polynomgleichung. Der Prüfer kann dies tun, indem er den Beweiser auffordert, den Wert eines gegebenen Polynoms an einem zufälligen Punkt zu finden, den der Prüfer aus den Nicht-Wurzelpunkten ζ von Z(x) ausgewählt hat, und beide Seiten dieser Gleichung an diesem Punkt auszuwerten ζ. Ich glaube, dass der Prüfer diese Polynome wahrscheinlich kennt. Diese Methode kann durch das Schwartz-Zippel-Lemma bewiesen werden.
Um die Beweiserstellung nicht interaktiv zu gestalten, sollten alle vom Verifizierer in der interaktiven Version generierten Zufallswerte mithilfe der Fiat-Shamir-Heuristik ermittelt werden.
Um den Beweiser an sein Vorschlagspolynom und das Quotientenpolynom T(x) zu binden, wird ein Polynombindungsschema verwendet. Der Prüfer macht Verpflichtungen zu diesen Polynomen, öffnet diese Verpflichtungen bei ζ (oder bei ζ * ω^q, wenn sich eine Einschränkung auf die Zeilen i und i + q auswirkt) und erstellt einen Beweis, der (I) diese Verpflichtungen und (II) den Wert enthält des Polynoms bei ζ (oder über ζ * ω^q, falls erforderlich) und (III) der entsprechende offene Beweis. Um den Beweis kürzer zu machen, verwenden Sie tatsächlich eine Mehrfachöffnung, d. h. generieren Sie einen kleinen Beweis für die Werte aller Polynompunkte. Daher ist der Beweis prägnant.
Um die Zero-Knowledge-Eigenschaft zu erfüllen, werden vom Prüfer zufällig ausgewählte Zeilen an die Instanz der Ausführungs-Trace-Tabelle angehängt, sodass ihre Höhe 2^k Zeilen beträgt. Diese Zeilen enthalten in der Vorschlagsspalte nur Zellen ungleich Null, da nur die Vorschlagsspalte die Daten enthält, die wir ausblenden möchten. Tun Sie dies, bevor Sie die Polynome der Vorschlagsspalte konstruieren, sodass die Anzahl der „Parameterwert“-Paare, die während des Verpflichtungseröffnungszeitraums offenbart werden, kleiner ist als die Anzahl der zufällig hinzugefügten Paare für jedes Polynom. Daher ist für jedes Vorschlagsspaltenpolynom die Menge an Informationen, die erforderlich ist, um es nach dem Öffnen der Verpflichtung wiederherzustellen, größer als die Menge an Zeugeninformationen. Diese Situation führt zu Nullwissen.
Während der Vorverarbeitungsphase führen alle Instanzen der Ausführungsschaltung einige der gleichen Berechnungen durch, einschließlich der Einrichtung und Berechnung fester Spaltenpolynome und ihrer Verpflichtungen für das Polynom-Verpflichtungsschema. Der durch diese Berechnungen erzeugte Datenanteil wird vom Prüfer verwendet und oft als Prüfschlüssel bezeichnet. Ebenso kann das Konzept eines Beweisschlüssels definiert werden. Das zugrunde liegende Polynom-Commitment-Schema bestimmt, ob Vertrauenseinstellungen während der Vorverarbeitungsphase vorgenommen werden.