Die Macht von Zero-Knowledge-Beweisen: Tauchen Sie tief in zk-SNARKs ein

In diesem Artikel wird diese Technologie mithilfe der Mathematik entschlüsselt und veranschaulicht, wie sie die Wahrheit von Wissen beweisen kann, ohne Informationen preiszugeben.

Zusammengestellt von: DODO Research

Autor: 0xAlpha Mitbegründer @DeriProtocol

Einführung

Zk-SNARK, ein prägnantes, nicht interaktives Wissensargument ohne Wissen, ermöglicht es einem Prüfer, zu bestätigen, dass ein Prüfer über bestimmtes Wissen (sogenannte Zeugen) verfügt, das bestimmte Beziehungen erfüllt, ohne Informationen über das Wissen selbst preiszugeben.

Das Generieren eines zk-SNARK für ein bestimmtes Problem umfasst die folgenden vier Schritte:

• Wandeln Sie ein Problem (oder eine Funktion) in eine Rechenschaltung um.
• Diese Schaltung wird dann in eine Matrixgleichung übersetzt.
• Diese Matrixgleichung wird weiter in ein Polynom umgewandelt, das durch ein bestimmtes minimales Polynom teilbar sein sollte.
• Schließlich wird diese Teilbarkeit in elliptischen Kurvenpunkten über einem endlichen Körper ausgedrückt, in denen der Beweis stattfindet.

Die ersten drei Schritte verändern lediglich die Darstellung der ursprünglichen Aussage. Der letzte Schritt projiziert die Aussage aus dem dritten Schritt mithilfe homomorpher Verschlüsselung in einen verschlüsselten Raum, sodass der Prüfer die darin enthaltenen gespiegelten Aussagen überprüfen kann. Da diese Projektion eine asymmetrische Verschlüsselung verwendet, ist es nicht möglich, von der Aussage in Schritt 3 zur ursprünglichen Aussage zurückzukehren, um eine wissensfreie Offenlegung sicherzustellen.

Der zum Lesen dieses Artikels erforderliche mathematische Hintergrund ist mit dem Algebra-Niveau vergleichbar, das von MINT-Studenten im ersten Studienjahr erwartet wird. Das einzige Konzept, das eine Herausforderung darstellen könnte, könnte die Kryptographie mit elliptischen Kurven sein. Für diejenigen, die damit nicht vertraut sind: Sie können es sich als eine Exponentialfunktion mit einer speziellen Basis vorstellen, wobei zu bedenken ist, dass ihre Umkehrung ungelöst bleibt.

Dieser Artikel folgt den folgenden Notationsregeln:

Matrizen: Fette Großbuchstaben, z. B A; in expliziter Form geschrieben \
Vektoren: Kleinbuchstabe mit Pfeilen, geschrieben in expliziter Form [ ]; Alle Vektoren sind standardmäßig Spaltenvektoren \
Skalare: Dargestellt durch normale Buchstaben

Nehmen wir als Beispiel die folgende Frage:

f(x)=x^3+x^2+5 (1)

Angenommen, Alice möchte beweisen, dass sie eine Wahrheit kennt. Wir werden die gesamte Prozedur durchgehen, die Alice durchführen muss, um einen zk-SNARK für ihren Beweis zu generieren.
Diese Frage mag zu einfach erscheinen, da sie keinen Kontrollfluss beinhaltet (z. B. wenn-dann-sonst). Es ist jedoch nicht schwierig, Funktionen mit Kontrollfluss in arithmetische Ausdrücke umzuwandeln. Betrachten Sie beispielsweise das folgende Problem (oder „Funktion“ in Programmiersprachen):

f(x, z):
if(z==1):
Rückgabe xxx+xx+5
anders:
gib xx+5 zurück

Das Umschreiben dieses Problems in den folgenden arithmetischen Ausdruck (vorausgesetzt, z gehört zu (0,1)) ist nicht komplexer als Gleichung (1).

f(x,z)=(z-1)(x^2+5)+z(x^3+x^2+5)

In diesem Artikel werden wir weiterhin Gleichung (1) als Grundlage für unsere Diskussion verwenden.

Schritt 1: Arithmetische Schaltung

Gleichung (1) lässt sich in folgende Grundrechenoperationen zerlegen:

Dies entspricht der folgenden Rechenschaltung:

Wir bezeichnen Gleichung (2) auch als einen Satz von 4 „primären Einschränkungen“, wobei jede Einschränkung die Beziehung eines arithmetischen Gatters in der Schaltung beschreibt. Im Allgemeinen kann eine Menge von n primären Nebenbedingungen als quadratisches Arithmetikprogramm (QAP) zusammengefasst werden, was im Folgenden erläutert wird.

Schritt 2: Matrix

Definieren wir zunächst einen „Zeugen“-Vektor wie folgt:

wobei y, s1, s2 und s3 wie in Gleichung (2) definiert sind.
Typischerweise gilt für ein Problem mit m Eingängen und n arithmetischen Gattern (d. h n-1 Zwischenschritte und die endgültige Ausgabe) wird dieser Zeugenvektor (m+n+1)-dimensional sein. In realen Fällen kann die Zahl n extrem groß sein. Beispielsweise liegt n bei Hash-Funktionen normalerweise im Tausenderbereich.

Als nächstes konstruieren wir drei n(m+n+1) Matrizen A,B,C, sodass wir Gleichung (2) wie folgt umschreiben können:

Gleichung (3) ist nur eine weitere Darstellung von Gleichung (2): Jeder Satz (ai, bi, ci) entspricht einem Gatter in der Schaltung. Wir können dies sehen, indem wir die Matrixgleichung explizit erweitern:

LHS=RHS ist also genau dasselbe wie Gleichung (2) und jede Zeile der Matrixgleichung entspricht einer primären Einschränkung (dh einem arithmetischen Gatter in der Schaltung).

Wir haben die Bauschritte (A, B, C) übersprungen, die eigentlich relativ einfach sind. Wir müssen sie nur gemäß den entsprechenden primären Einschränkungen in eine Matrix umwandeln, um den Inhalt jeder Zeile von (A, B, C) zu bestimmen, dh (ai, bi, ci). Nehmen wir die erste Zeile als Beispiel: Wir können leicht erkennen, dass wir [0,1,0,0,0], [0, 1,0, 0,0] und [0,0,0,1,0,0] durch den Vektor s.

Somit haben wir die Rechenschaltung erfolgreich in eine Matrixgleichung umgewandelt, nämlich Gleichung (3). Gleichzeitig haben wir auch das Objekt, dessen Beherrschung nachgewiesen werden muss, in die Zeugenvektoren geändert.

Schritt 3: Polynome

Lassen Sie uns nun eine n(n+m+*1)-Matrix PA konstruieren, die eine Menge von Polynomen bezüglich z definiert:

Sicherstellen, dass die Funktionnimmt bei {1, 2, 3, 4} die folgenden Werte an erfüllt die Bedingungen:

Dann können wir A umschreiben als:

Hierbei handelt es sich um vier Sätze linearer Gleichungen mit sechs Variablen, die mit herkömmlichen Methoden gelöst werden können. Ein effizienterer Weg zur Lösung von PA ist in diesem Fall jedoch die Lagrange-Interpolation, die die Besonderheiten des Problems ausnutzt. Hier überspringen wir den Prozess der Lösung von PA, der etwas mühsam, aber unkompliziert ist.

In ähnlicher Weise konstruieren wir PB und PC getrennt für B und C. Dann können wir die Matrixgleichung umschreibenwie folgt:

Wenn man jede Zeile einzeln betrachtet, ist es offensichtlich, dass diese vier Zeilen demselben Ausdruck entsprechen, der an vier verschiedenen Punkten ausgewertet wurde. Daher ist die obige Matrixgleichung äquivalent zu:

Schritt 3: Elliptischer Kurvenpunkt

Schreiben Sie Gleichung (4) um als:

wobei i(z)=1 nur ein triviales Polynom nullten Grades in z ist, das zur Vereinheitlichung der Gleichungen verwendet wird – alle Terme sind quadratisch. Die Notwendigkeit hierfür wird in Kürze klar werden. Beachten Sie, dass diese Gleichung nur die Addition und Multiplikation von Polynomen in z enthält.

Bitte beachten Sie, dass arithmetische Operationen, Addition (+) und Multiplikation (X), auch auf entsprechende Operationen im endlichen Körper elliptischer Kurvenpunkte abgebildet werden. Die Symbole Und werden verwendet, um Verwirrung zu vermeiden und darauf hinzuweisen, dass es sich um neu definierte Feldoperationen handelt.

Als nächstes erklären wir Ihnen die praktischen Schritte genauer.

Elliptische Kurvenkryptographie

Die allgemeine Theorie elliptischer Kurven geht weit über den Rahmen dieses Artikels hinaus. Für die Zwecke hierin wird eine elliptische Kurve als Abbildungen von einem Primfeld Fp auf die Funktion E definiert, wobei E Punkte enthält, so dass y^2=x^3+ax+b (elliptische Kurvenpunkte oder kurz ECPs genannt) .

Bitte beachten Sie, dass beim Übergang zu einem Primkörper, obwohl wir bisher die reguläre Arithmetik besprochen haben, arithmetische Operationen an Zahlen mithilfe der modularen Arithmetik ausgeführt werden. Zum Beispiel a+b=a+b(mod p), wobei p die Ordnung von Fp ist.

Andererseits ist die Addition zweier elliptischer Kurvenpunkte wie folgt definiert:

Insbesondere die Addition von P und Q zweier ECPs:

Finden Sie den Schnittpunkt der Linie PQ und der Kurve R und definieren Sie ihn als -(P+Q)
Wechseln Sie zum „Spiegel“-Punkt R' von R auf der Kurve.
Daher definieren wir die Addition elliptischer Kurvenpunkte P+Q=R‘:

Beachten Sie, dass diese Regel auch für den Sonderfall gilt, bei dem die Addition eines ECP verwendet wird. In diesem Fall wird die Tangente an diesen Punkt verwendet.

Nehmen wir nun an, wir wählen zufällig einen Punkt G aus und ordnen ihm die Zahl 1 zu. (Diese „erste Zuordnung“ klingt etwas willkürlich. Wir werden später darüber sprechen). Und für jedes n, das zu Fp gehört, definieren wir:

E(N)=G+G+G+…..+G=G multipliziert mit n

Es gibt einen Operationsausdruck. Definieren Sie die Operation +G als „Generator“, bezeichnet als g. Dann ist die obige Definition äquivalent zu:

Nach der Definition der Addition wird folgender linearer Zusammenhang deutlich:

Daher bleibt jede lineare Beziehung (oder Einschränkung) in Fp durch diese Zuordnung im verschlüsselten Raum B erhalten. Beispielsweise führt die Gleichung l + m = n in Fp zu

Da Gleichung (5), die Alice beweisen möchte, jedoch eine quadratische Form hat, ist sie nicht linear genug. Um quadratische Terme verarbeiten zu können, müssen wir die Multiplikation im verschlüsselten Raum definieren. Dies wird als Paarung oder bilineare Karte bezeichnet, die ich im folgenden Abschnitt erläutern werde.

Bilineare Karte

Angenommen, G1, G2 und GT sind Gruppen der Primzahlordnung g. Eine Paarungsfunktion oder bilineare Karte ist wie folgt definiert:

Gemeinsame Referenzzeichenfolge

Dieses Ganze wird als „Prüfschlüssel“ (PK) bezeichnet. Beachten Sie, dass die Darstellung von Vektoren in E() als Vektoren elliptischer Kurvenpunkte verstanden werden sollte, wobei jeder Punkt vom entsprechenden Vektorelement abgebildet wird. Somit umfassen diese 11 Vektoren tatsächlich 62 (=42+63+63+63) elliptische Kurvenpunkte. Diese 62 ECPs werden Alice, der Prüferin, zur Verfügung gestellt. In einem allgemeinen Szenario enthält die PK für ein Problem mit m Eingaben und n primären Einschränkungen 2n + 3(m+n+1)*3 = 11n + 9m + 9 ECPs.

Gleichzeitig werden folgende Berechnungen durchgeführt:

Der gesamte Vorgang wird als „Verifizierungsschlüssel“ (VK) bezeichnet. Hierbei handelt es sich lediglich um 7 Elliptic Curve Points (ECPs), die dem Verifizierer zur Verfügung gestellt werden müssen. Es ist zu beachten, dass VK immer aus 7 ECPs besteht, unabhängig davon, wie viele Eingaben und primäre Einschränkungen an dem Problem beteiligt sind.

Darüber hinaus ist zu erwähnen, dass das „Trusted Setup“ und der Prozess der Generierung von PK und VK nur einmal für ein bestimmtes Problem durchgeführt werden müssen.

Beweisen und Verifizieren

Alice verfügt nun über den öffentlichen Schlüssel (PK) und berechnet die folgenden elliptischen Kurvenpunkte (ECPs):

Diese 9 elliptischen Kurvenpunkte sind entscheidend für ein wissensfreies, prägnantes, nicht interaktives Wissensargument (zk-SNARK)!

Beachten Sie, dass Alice im Wesentlichen nur lineare Kombinationen an den Punkten der elliptischen Kurve im öffentlichen Schlüssel durchführt. Dies ist besonders kritisch und wird bei der Verifizierung streng überprüft.

Nun präsentiert Alice den zk-SNARK-Beweis und führt uns schließlich zum Verifizierungsprozess, der in drei Schritten erfolgt.

Zunächst muss bestätigt werden, dass die ersten 8 Punkte der elliptischen Kurve tatsächlich die linearen Kombinationen dieser Punkte in der gemeinsamen Referenzzeichenfolge sind.

Haftungsausschluss:

1. Dieser Artikel wurde von [chaincatcher] nachgedruckt. Alle Urheberrechte liegen beim ursprünglichen Autor [0xAlpha Mitbegründer @ DeriProtocol]. Wenn Sie Einwände gegen diesen Nachdruck haben, 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.