Einführung

In unserem vorherigen Beitrag haben wir das Konzept von SNARK und die erforderlichen Grundeigenschaften vorgestellt. Mit dem Hauptziel dieser Beitragsreihe vor Augen, nämlich: wie man zk-SNARKs für beliebige Berechnungen erstellt, stellen wir in diesem Beitrag die Erstellung eines SNARK vor, um die Kenntnis eines Polynoms zu beweisen. Wir werden es Schritt für Schritt tun, ausgehend von einer Konstruktion, die nicht alle Anforderungen erfüllt, und zu einem Protokoll, das ein „vollständiges“ Zero-Knowledge-SNARK sein wird.

ZK-SNARKs für Polynome

Wir werden Schritt für Schritt ein zk-SNARK bauen, beginnend mit einer einfacheren Konstruktion, die kein SNARK ist, und sie dann mit neuen Techniken verbessern, bis wir unsere Ziele erreichen.

Erster Schritt: das Schwartz-Zippel-Lemma

Wir möchten ein Protokoll erstellen, das es einem Beweiser P ermöglicht, einen Prüfer V von der Kenntnis eines bestimmten Polynoms vom Grad n mit Koeffizienten in einem endlichen Körper F zu überzeugen. Mit anderen Worten, P möchte V davon überzeugen, dass er ein Polynom der Form kennt

Nehmen wir an, dass a_1, a_2, …, a_n ∈ F die n Wurzeln dieses Polynoms sind, daher kann p(x) geschrieben werden als

Nehmen wir an, dass V d < n Wurzeln des Polynoms p(x) kennt.

Dann können wir unser Problem umformulieren: Nun möchte P V beweisen, dass er ein Polynom h(x) kennt, so dass

Das Polynom t(x) wird als Zielpolynom bezeichnet. Beachten Sie, dass es die Form hat

Die erste Version unseres zk-SNARK basiert auf dem Schwartz-Zippel-Lemma: Sei F ein Körper und f: F^m → F ein multivariables Polynom vom Grad n. Dann gilt für jede endliche Menge S ⊆ F:

Das Lemma zeigt, dass, wenn wir u ∈ Sm gleichmäßig zufällig nehmen, die Wahrscheinlichkeit, dass u eine Menge von Wurzeln für f ist, höchstens n / |S| beträgt. Beachten Sie, dass diese Wahrscheinlichkeit winzig ist, wenn wir S als das endliche Feld F betrachten. Die Feldgröße wäre im Vergleich zu n sehr groß.

Es mag widersprüchlich erscheinen, aber dieses Lemma ermöglicht es uns, die Kenntnis eines Polynoms f zu beweisen. Wir müssen nicht beweisen, dass wir alle Koeffizienten von p kennen, sondern nur, dass wir wissen, wie man das Paar (s, f(s)) für jedes s ∈ Fm berechnet. Das Schwartz-Zippel-Lemma sorgt für die in unserem zk-SNARK erforderliche Effizienz.

Erstes Protokoll

Wir erinnern uns, dass P das Polynom p(x) kennt und V d < n Wurzeln von p(x) kennt oder, äquivalent, V das Zielpolynom t(x) kennt. P kennt auch t(x).

Unser erster Ansatz ist wie folgt:

1. V nimmt einen Zufallswert s und berechnet t = t(s). V sendet s an P.
2. P berechnet das Polynom

4. V prüft, ob die Gleichheit p = t · h gilt.

Dieses Protokoll ist korrekt, denn wenn P das Polynom p(x) kennt, kann er h(x) berechnen und daher kann P auch die Werte h und p berechnen, so dass p = h · t. Andererseits ist dieses Protokoll aufgrund des Schwartz-Zippel-Lemmas auch effizient.

Dennoch ist dieses Protokoll nicht robust, da der Beweiser t = t(s) mithilfe des Zielpolynoms berechnen kann, selbst wenn P p(x) nicht kennt. Er kann ein zufälliges h nehmen und p = h · t berechnen und das Paar (h, p) an V senden, der das Paar als gültig akzeptieren würde.

Wir beobachten, dass der kritische Punkt, der es P ermöglicht, V zu täuschen, darin besteht, dass P den Bewertungspunkt s kennt. Dieser Trick wäre unmöglich, wenn P p bewerten könnte, ohne den Bewertungspunkt s zu kennen. Dies führt uns zum zweiten Schritt: homomorphe Verschleierung oder homomorphes Verstecken.

Zweiter Schritt: homomorphe Verschleierung

Um unser Protokoll robust zu machen, müssen wir in der Lage sein, ein Polynom an einem Punkt auszuwerten, ohne diesen Punkt zu kennen.

Dabei stützen wir uns auf die Härte des Problems des diskreten Logarithmus. Für einen klassischen Computer ist das Problem des diskreten Logarithmus rechnerisch nicht durchführbar: In einer zyklischen Gruppe G der Ordnung p, die von einem Element g erzeugt wird, wird ein Element a bestimmt, so dass = ga (mod p) für ein bekanntes .

Unter der Annahme der Härte des diskreten Logarithmuspolynoms können wir einen Wert a verschleiern, indem wir = ga (mod p) berechnen. Ein Empfänger von allein kann den Wert a nicht lernen. Der interessante Punkt dieser Technik besteht darin, dass die Potenzierung einige homomorphe Eigenschaften hat:

Das Produkt zweier verschleierter Werte ist dasselbe wie die Verschleierung der Addition der zugehörigen Werte im Klartext.

Wenn wir ein Polynom auswerten wollen

auf einem Punkt x = s, ohne dem Bewerter den genauen Punkt mitzuteilen, müssen wir das gesamte Polynom verschleiern:

Wir müssen auch die Potenzen aller verschleierten Werte für x = r berechnen, von 1 bis zum Grad des Polynoms, das heißt:

Beachten Sie, dass wir mit all diesen Elementen nun die verschleierte Auswertung des Polynoms p für einen Punkt x = r berechnen können. In der Tat:

Ein Beispiel für homomorphes Verstecken

Betrachten wir das endliche Feld F = ℤ127 und g = 3 als Generator. Nehmen wir an, dass P das Polynom p(x) = 4x2 + 3x + 1 kennt und dass V möchte, dass P das Polynom am Punkt x = 2 auswertet, ohne P den Punkt mitzuteilen. Wir können dies durch die folgenden Schritte tun:

1. V berechnet alle Potenzen von x = 2 von 0 bis zum Grad des Polynoms, n = 2:

1.b. 32 (mod 127) = 9

1.c. 34 (mod 127) = 81

und sendet das Paar (9, 81) an P.

2. P kann die Auswertung von p(x) für x = 2 berechnen, ohne den Wert von x zu kennen. Tatsächlich kann er unter Verwendung der von V erhaltenen Informationen Folgendes berechnen:

Zweites Protokoll

Nachdem wir nun wissen, wie man Punkte verschleiert, damit der Beweiser das Polynom an diesem verschleierten Punkt auswerten kann, werden wir das erste Protokoll verbessern. Wir erinnern uns, dass P das Polynom p(x) kennt und V d < n Wurzeln von p(x) kennt oder, äquivalent, V das Zielpolynom t(x) kennt. P kennt auch t(x).

Unser zweites Protokoll lautet wie folgt:

1. V nimmt einen Zufallswert s und berechnet t = t(s).
2. V berechnet die folgenden Potenzen und sendet sie an P:

4. Unter Verwendung der Werte berechnet P g^p = g^{p(s)} und g^h = g*{h(s)} unter Verwendung der Anweisungen des vorherigen Beispiels.

5. P sendet g^p und g^h an V.

6. V prüft, ob die folgende Identität gilt: g^p = (g^h)^t

Beachten Sie, dass der im ersten Protokoll festgestellte Fehler geändert wurde, dieses zweite Protokoll jedoch noch nicht robust ist. Tatsächlich kann P immer noch die Werte zp und zh verwenden, so dass z_p = (z_h)^t ist, und sie an V senden, als wären sie g^p und g^h. P könnte dies tun, indem es ein zufälliges r nimmt, z_h = g^r berechnet und z_p = (g^t)^r setzt. Der Wert z_p kann mithilfe der von V gesendeten verschleierten Potenzen berechnet werden.

Um diese Situation zu vermeiden, müssen wir sicherstellen, dass g^p und g^h nur unter Verwendung der von V gesendeten verschleierten Potenzen berechnet werden.

Dritter Schritt: die Annahme der Exponentenkenntnis

Bei der Definition eines SNARK gibt es eine allgemeine Annahme: Betrachten wir eine Primzahl q, so dass 2q + 1 ebenfalls eine Primzahl ist. Betrachten wir einen Generator von ℤ_{2q + 1}. Gegeben q, g und g' = g^, wollen wir ein Paar (x, y) finden, so dass x ≠ g, y ≠ g' und y = x^. Die Exponentenwissensannahme (KEA) besagt, dass der einzige Weg, das Paar (x, y) zu finden, darin besteht, einen Wert c ∈ ℤ_q zu nehmen, zuerst x = g^c zu berechnen und dann y = (g')^ zu nehmen C.

Der KEA bedeutet, dass man, wenn man das Paar (x, y) erhalten möchte, dies nur erreichen kann, indem man einen Exponenten c kennt, so dass x = g^c. Mit anderen Worten: Wir können das Paar (x, y) mit der KEA-Eigenschaft nur mithilfe von Potenzen von g erhalten.

Mithilfe des KEA stellt das folgende Protokoll sicher, dass P eine bestimmte Potenz von g, einem Generator einer multiplikativen Untergruppe, zurückgibt, die von V geliefert wird:

1. V nimmt einen Zufallswert und berechnet g' = g^ (mod 2q + 1).
2. V sendet das Paar (g, g') an P und fragt nach einem Paar (b, b'), so dass (b, b') = (g, g').
3. P nimmt einen Wert c und berechnet b = g^c (mod 2q + 1), b' = (g')^c (mod 2q + 1) und sendet das Paar (b, b') an V.
4. V prüft, ob b' = b^ (mod 2q + 1).

P verwendete für g und g' die gleiche Potenz c und konnte nur die von V gelieferten Werte verwenden.

Drittes Protokoll

Wir sind bereit, ein geeignetes Protokoll zu erstellen, das sicherstellt, dass Beweiser P Potenzen des Werts s auf der verschleierten Domäne ausgibt.

1. V nimmt einen Zufallswert s und berechnet t = t(s).
2. V nimmt einen Zufallswert und berechnet t( · s).
3. V berechnet die folgende Reihe verschleierter Werte und sendet sie an P.
4. V berechnet die folgende Reihe verschleierter Werte

5. P berechnet das Polynom h(x).

6. Mit berechnet P p(s) und h(s) zusammen mit g^p = g^{p(s)} und g^h = g^{h(s)}.

7. Mit berechnet P p(s) und h(s) zusammen mit g^{p'} = g^{p( · s)}.

8. P sendet g^p, g^h und g^{p'} an V.

9. V prüft, ob P die Berechnungen der verschleierten Werte nur anhand der Informationen durchgeführt hat, die er ihm gesendet hat. Dazu prüft V, ob g^p = g^{p'}.

10. V prüft, ob die folgende Identität gilt: g^p = (g^h)^{t(s)}.

Dieses Protokoll erfüllt nun die von einem SNARK geforderten Eigenschaften: Es ist korrekt, es ist robust und es ist effizient. In den nächsten Abschnitten geht es um Nicht-Interaktivität und Null-Wissen.

Anmerkung: Die Schritte 6 und 7 im obigen Protokoll werden gemäß dem Beispiel zum homomorphen Verstecken durchgeführt.

Nullwissen

In dem bisher vorgestellten Protokoll sind die Koeffizienten ci des P bekannten Polynoms sehr spezifisch, und V könnte versuchen, mithilfe von gp, gh und gp', die von P stammen, einige Informationen über sie zu erfahren. Daher, um sicherzustellen, dass P sicher ist Damit V nichts lernt, muss P diese Werte verbergen.

Die Strategie zum Ausblenden der von P gesendeten Werte folgt den zuvor verwendeten Schritten: P nimmt ein zufälliges und verwendet es, um die in der Kommunikation mit V gesendeten Werte zu verbergen. Um genau zu sein, sendet es nicht g^p, g^h und g ^{p'}, P berechnet und sendet (g^p)^, (g^h)^ und (g^{p'})^. Dann führt V die Überprüfung der unter verborgenen Werte durch.

Die Verifizierungsprozedur, die V ausführen muss, ist mit diesem Verbergen tatsächlich immer noch gültig:

Um das dritte Protokoll wissensfrei zu machen, ersetzt man Schritt 8, damit P die verschleierten Werte senden kann.

Keine Interaktivität

Die verschiedenen Protokolle, die wir vorgestellt haben, erfordern die Interaktion zwischen dem Prüfer und dem Verifizierer, und das liegt daran, dass die Korrektheit der Protokolle von den geheimen Werten s und abhängt, die vom Verifizierer ausgewählt werden.

Wenn wir eines der oben genannten Protokolle mit einem anderen Verifizierer V' wiederholen möchten, müsste V' neue Werte s' und ' wählen. Die Verwendung der von V generierten Werte kann es P ermöglichen, zu betrügen, wenn er mit V zusammenarbeitet und V P die Werte s und preisgibt.

Um die obige Situation zu vermeiden, muss unser Protokoll nicht interaktiv sein. Dies können wir durch die Verwendung öffentlicher, vertrauenswürdiger und wiederverwendbarer Parameter erreichen. Dies kann erreicht werden, indem diese Parameter mithilfe eines Generators g verschleiert werden. Selbst wenn die verwendeten Verschleierungstechniken homomorph sind, ermöglichen sie jedoch nur das Hinzufügen klarer Nachrichten unter Verwendung des Produkts versteckter Werte, nicht jedoch die Durchführung des Produkts klarer Werte im verschleierten Bereich, und dieser Schritt ist bei der Überprüfung von entscheidender Bedeutung die Korrektheit des Polynoms und seiner Wurzeln.

Um dieses Problem zu lösen, werden wir Paarungen einführen. Erinnern wir uns daran, dass eine Paarung die folgende Eigenschaft hat:

Diese Eigenschaft ermöglicht die Überprüfung der Gleichheit der Produkte in der verschleierten Domäne.

Um unsere Protokolle nicht interaktiv zu machen, besteht der erste Schritt darin, die geheimen Zufallswerte s und zu verschleiern: g^, und .

Sobald wir diese Potenzen berechnet haben, können wir die geheimen Werte s und entfernen und ihre verschleierten Werte, bekannt als Common Reference String (CRS), verbreiten. Die CRS-Werte werden normalerweise wie folgt gespeichert:

1. Bewertungsschlüssel: (, ).
2. Verifizierungsschlüssel: (g^, g^{t(s)}).

Abschlussprotokoll: zk-SNARK zur Kenntnis eines Polynoms

Wir definieren nun ein zk-SNARK, um das Wissen über ein Polynom p(x) vom Grad n bei gegebenem Zielpolynom t(x) zu beweisen.

Parametereinstellung

1. Jede Partei nimmt zufällig zwei geheime Werte s und .
2. Jede Partei berechnet g, und .
3. Die Werte s und werden zerstört.
4. Man sendet den Bewertungsschlüssel ( und ).
5. Man sendet den Verifizierungsschlüssel g^, g^{t(s)}.

1. Unter der Annahme, dass P p(x) kennt, berechnet P das Polynom h(x).
2. P wertet p(x) und h(x) aus und berechnet gp(s) und gh(s) anhand der im Bewertungsschlüssel enthaltenen Werte.
3. P berechnet den Wert g^{p( · s)} mithilfe des Bewertungsschlüssels.
4. P nimmt einen zufälligen Wert an .
5. P sendet den Beweis π = (g^{ · p(s)}, g^{ · h(s)}, g^{ · p( · s)}) = (g^{ · p }, g^{ · h}, g^{ · p'}).

Unter der Annahme, dass V Zugriff auf π = (g^{ · p}, g^{ · h}, g^{ · p'} hat), prüft es, ob

Es ist uns gelungen, ein Protokoll zu erstellen, das alle für die Definition eines zk-SNARK erforderlichen Eigenschaften erfüllt: Prägnanz (da der Beweis nur die Prüfung eines Polynoms an einem Punkt ist), wissensfrei und nicht interaktiv (da ein CRS verwendet wird). ).

Generierung des CRS

Zk-SNARKs können durch die Verwendung einer Reihe versteckter Werte, bekannt als Common Reference String (CRS), nicht interaktiv gemacht werden. Diese verborgenen Werte, die in unserem Fall die Form und haben, stammen aus geheimen Werten, s und , die zerstört werden müssen, sobald die verborgenen Werte abgeleitet wurden. Beachten Sie, dass die Generierung des CRS von entscheidender Bedeutung ist, denn wenn man die Generierung an einen dritten Teilnehmer delegiert, muss jeder darauf vertrauen, dass der Teilnehmer die Werte s und zerstören wird. Der Dritte stellt einen Single Point of Failure dar.

Wenn wir den Single Point of Failure vermeiden wollen, brauchen wir eine verteilte Methode zur Generierung des CRS, bei der ein einziger ehrlicher Teilnehmer ausreicht, um zu garantieren, dass die Werte s und nicht wiederhergestellt werden können.

Lassen Sie uns das CRS für den SNARK verwenden, den wir in unserem vorherigen Beispiel erstellt haben. Wir erinnern uns, dass wir unter Verwendung von s und als Geheimnisse die verborgenen Werte und Potenzen g^, und berechnen müssen.

In unserem neuen Protokoll werden wir die von einem einzelnen Dritten generierten Werte s und durch die von drei Benutzern A, B und C generierten Werte s_{ABC} und _{ABC} ersetzen. Die Ausweitung des Mechanismus auf n Benutzer ist unkompliziert .

Das Protokoll folgt:

1. Benutzer A generiert das Paar (sA, A), berechnet und sendet Folgendes:

3. B-Sendungen:

4. C nimmt ein zufälliges Paar (sC, C), berechnet und sendet:

Dieses Protokoll generiert die versteckten Werte für s_{ABC} = s_A · s_B · s_C und _{ABC} = _A · _B · _C, ohne dass ein einzelner Teilnehmer dieses Wertepaar kennt.

Dennoch benötigen wir ein Protokoll, das es den Teilnehmern ermöglicht, zu überprüfen, ob diese versteckten Werte korrekt berechnet wurden. Wir müssen sicherstellen, dass die von jedem Benutzer generierten Werte die Anforderungen erfüllen, das heißt, dass die Menge der Werte Potenzen von gs für den s-Wert jedes Benutzers sind, und dass die Menge korrekt berechnet wurde. Dazu prüfen wir, ob jedes (g^s)^i effektiv die i-te Potenz von gs ist. Dies kann erreicht werden, indem überprüft wird, ob die folgenden Gleichungen gelten. Diese Prüfung wird von jedem Teilnehmer für alle Werte sU und U durchgeführt, die jedem Teilnehmer U zugeordnet sind:

Dies ist nicht die einzige erforderliche Überprüfung. Wir müssen auch überprüfen, ob jeder Teilnehmer die richtigen Werte des vorherigen Teilnehmers verwendet. Dazu verwendet jeder Teilnehmer versteckte öffentliche Parameter eines Benutzers in Kombination mit den Ausgaben eines anderen Teilnehmers. Beispielsweise kann C die Zwischenwerte des von B generierten CRS mithilfe der CRS-Informationen von A überprüfen, indem er Folgendes überprüft:

Abschluss

Bisher haben wir gelernt, wie man ein SNARK von Grund auf und mit allen Details erstellt, um die Kenntnis eines Polynoms nachzuweisen. In unserem nächsten Beitrag, dem letzten, werden wir die obige Konstruktion auf jede beliebige Berechnung erweitern. Dazu werden wir zwei Schlüsselkonzepte einführen: quadratische Arithmetikprogramme, QAPs, und Rang-1-Beschränkungssysteme, R1CS, wobei letzteres nicht speziell eingeführt wird (es wird als unterschwellige Botschaft erscheinen).

Verweise

Jordi Herrera Joancomartí, Cristina Pérez Solà, Criptografia avançada. Vorlesungsnotizen. Offene Universität Katalonien, 2022.