Vitalik Buterin über die Vitalik Buterin Blog

Dies ist ein Spiegelbild des Beitrags unter https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

In letzter Zeit gab es großes Interesse an der Technologie hinter zk-SNARKs, und das Interesse der Menschen nimmt zu versuchen zu entmystifizieren etwas, das viele wegen seiner scheinbar unentzifferbaren Komplexität „Mondmathematik“ nennen. ZK-SNARKs sind in der Tat ziemlich schwer zu verstehen, vor allem aufgrund der schieren Anzahl beweglicher Teile, die zusammenkommen müssen, damit das Ganze funktioniert. Aber wenn wir die Technologie Stück für Stück aufschlüsseln, wird es einfacher, sie zu verstehen.

Der Zweck dieses Beitrags besteht nicht darin, als vollständige Einführung in zk-SNARKs zu dienen. Als Hintergrundwissen wird davon ausgegangen, dass (i) Sie wissen, was zk-SNARKs sind und was sie tun, und (ii) Sie über ausreichende Mathematikkenntnisse verfügen, um über Dinge wie Polynome nachdenken zu können (wenn die Aussage �(�)+�(�) =(�+�)(�) , wobei � und � Polynome sind, erscheint Ihnen natürlich und offensichtlich, dann sind Sie auf der richtigen Ebene. Vielmehr befasst sich der Beitrag tiefer mit der Maschinerie hinter der Technologie und versucht, die erste Hälfte der Pipeline so gut wie möglich zu erklären, wie sie hier vom zk-SNARK-Forscher Eran Tromer gezeichnet wurde:

Die Schritte hier können in zwei Hälften unterteilt werden. Erstens können zk-SNARKs nicht direkt auf Rechenprobleme angewendet werden; Vielmehr müssen Sie das Problem in die richtige „Form“ umwandeln, damit das Problem bearbeitet werden kann. Die Form wird als „quadratisches Arithmetikprogramm“ (QAP) bezeichnet, und die Umwandlung des Codes einer Funktion in eines dieser Programme ist selbst höchst nicht trivial. Neben dem Prozess zum Konvertieren des Codes einer Funktion in einen QAP gibt es einen weiteren Prozess, der parallel ausgeführt werden kann, sodass Sie, wenn Sie eine Eingabe in den Code haben, eine entsprechende Lösung erstellen können (manchmal auch „Zeuge“ des QAP genannt). Danach gibt es einen weiteren ziemlich komplizierten Prozess zur Erstellung des eigentlichen „Null-Knowledge-Beweises“ für diesen Zeugen und einen separaten Prozess zur Überprüfung eines Beweises, den jemand anderes an Sie weitergibt. Dies sind jedoch Details, die nicht Gegenstand dieses Beitrags sind .

Das Beispiel, das wir wählen werden, ist einfach: Der Beweis, dass Sie die Lösung einer kubischen Gleichung kennen: �3+�+5=35 (Hinweis: Die Antwort ist 3). Dieses Problem ist so einfach, dass der resultierende QAP nicht so groß ist, dass es einschüchternd wirkt, aber nicht trivial genug, dass man sehen kann, wie alle Mechanismen ins Spiel kommen.

Schreiben wir unsere Funktion wie folgt auf:

def qeval(x):
    y = x**3
    return x + y + 5

Die einfache Spezialprogrammiersprache, die wir hier verwenden, unterstützt grundlegende Arithmetik (+, −, ⋅, /), Potenzierung mit konstanter Potenz (�7, aber nicht ��) und Variablenzuweisung, was leistungsstark genug ist, dass Sie dies theoretisch tun können jede darin enthaltene Berechnung (solange die Anzahl der Rechenschritte begrenzt ist; keine Schleifen erlaubt). Beachten Sie, dass Modulo (%) und Vergleichsoperatoren (<, >, ≤, ≥) NICHT unterstützt werden, da es keine effiziente Möglichkeit gibt, Modulo oder Vergleich direkt in der endlichen zyklischen Gruppenarithmetik durchzuführen (seien Sie dafür dankbar; wenn es eine Möglichkeit gäbe). Wenn man beides tun würde, würde die Elliptische-Kurven-Kryptographie schneller kaputt gehen, als man „binäre Suche“ und „Chinesischer Restsatz“ sagen kann.

Sie können die Sprache auf Modulo und Vergleiche erweitern, indem Sie Bitzerlegungen (z. B. 13=23+22+1) als Hilfseingaben bereitstellen, die Richtigkeit dieser Zerlegungen beweisen und die Mathematik in binären Schaltkreisen durchführen; In der Arithmetik endlicher Körper ist die Durchführung von Gleichheitsprüfungen (==) ebenfalls machbar und tatsächlich etwas einfacher, aber auf diese beiden Details gehen wir jetzt nicht näher ein. Wir können die Sprache erweitern, um Bedingungen zu unterstützen (z. B. wenn �<5:�=7; sonst: �=9), indem wir sie in eine arithmetische Form umwandeln: �=7⋅(�<5)+9⋅(�≥5 ) Beachten Sie jedoch, dass beide „Pfade“ der Bedingung ausgeführt werden müssten, und wenn Sie viele verschachtelte Bedingungen haben, kann dies zu einem großen Overhead führen.

Lassen Sie uns diesen Prozess nun Schritt für Schritt durchgehen. Wenn Sie dies für einen beliebigen Codeabschnitt selbst tun möchten, kann ich Folgendes tun: habe hier einen Compiler implementiert (Nur zu Bildungszwecken; noch nicht bereit, QAPs für reale zk-SNARKs zu erstellen!).

Abflachen

Der erste Schritt ist ein „Flattening“-Verfahren, bei dem wir den ursprünglichen Code, der beliebig komplexe Anweisungen und Ausdrücke enthalten kann, in eine Folge von Anweisungen konvertieren, die zwei Formen haben: �=� (wobei � eine Variable oder eine Zahl sein kann ) und �=� (��) � (wobei �� +, −, ⋅, / sein kann und � und � Variablen, Zahlen oder selbst Unterausdrücke sein können). Sie können sich jede dieser Anweisungen als eine Art logisches Gatter in einer Schaltung vorstellen. Das Ergebnis des Abflachungsprozesses für den obigen Code ist wie folgt:

sym_1 = x * x
y = sym_1 * x
sym_2 = y + x
~out = sym_2 + 5

Wenn Sie den Originalcode und den Code hier lesen, können Sie ziemlich leicht erkennen, dass die beiden gleichwertig sind.

Tore zu R1CS

Nun wandeln wir dies in etwas um, das als Rang-1-Beschränkungssystem (R1CS) bezeichnet wird. Ein R1CS ist eine Folge von Gruppen von drei Vektoren (�, �, �), und die Lösung eines R1CS ist ein Vektor �, wobei � die Gleichung �.�⋅�.�−�.�=0 erfüllen muss, wobei . stellt das Skalarprodukt dar – einfacher ausgedrückt: Wenn wir � und � „zusammenzählen“, die beiden Werte an den gleichen Positionen multiplizieren und dann die Summe dieser Produkte bilden, dann machen wir dasselbe mit � und � und dann mit � und � , dann entspricht das dritte Ergebnis dem Produkt der ersten beiden Ergebnisse. Dies ist beispielsweise ein erfülltes R1CS:

Aber anstatt nur eine Einschränkung zu haben, werden wir viele Einschränkungen haben: eine für jedes Logikgatter. Es gibt eine Standardmethode zum Konvertieren eines Logikgatters in ein (�,�,�)-Tripel, abhängig davon, um welche Operation es sich handelt (+, −, ⋅ oder /) und ob es sich bei den Argumenten um Variablen oder Zahlen handelt. Die Länge jedes Vektors entspricht der Gesamtzahl der Variablen im System, einschließlich einer Dummy-Variable ~one am ersten Index, die die Zahl 1 darstellt, der Eingabevariablen, einer Dummy-Variable ~out, die die Ausgabe darstellt, und dann allen Zwischenvariablen (���1 und ���2 oben); Die Vektoren werden im Allgemeinen sehr spärlich sein und nur die Slots ausfüllen, die den Variablen entsprechen, die von einem bestimmten Logikgatter beeinflusst werden.

Zuerst stellen wir die Variablenzuordnung bereit, die wir verwenden werden:

'~one', 'x', '~out', 'sym_1', 'y', 'sym_2'

Der Lösungsvektor besteht aus Zuweisungen für alle diese Variablen in dieser Reihenfolge.

Nun geben wir das (�,�,�)-Triple für das erste Tor an:

a = [0, 1, 0, 0, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 1, 0, 0]

Sie können sehen, dass, wenn der Lösungsvektor an der zweiten Position 3 und an der vierten Position 9 enthält, die Skalarproduktprüfung unabhängig vom restlichen Inhalt des Lösungsvektors auf 3⋅3=9 und reduziert wird also wird es vergehen. Wenn der Lösungsvektor an der zweiten Position −3 und an der vierten Position 9 hat, ist die Prüfung ebenfalls erfolgreich; Wenn der Lösungsvektor tatsächlich 7 an der zweiten Position und 49 an der vierten Position hat, dann wird diese Prüfung trotzdem bestanden – der Zweck dieser ersten Prüfung besteht nur darin, die Konsistenz der Ein- und Ausgänge des ersten Gatters zu überprüfen.

Kommen wir nun zum zweiten Tor:

a = [0, 0, 0, 1, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 0, 1, 0]

In einem ähnlichen Stil wie bei der ersten Skalarproduktprüfung überprüfen wir hier, dass ����1⋅�=� ist.

Nun das dritte Tor:

a = [0, 1, 0, 0, 1, 0]
b = [1, 0, 0, 0, 0, 0]
c = [0, 0, 0, 0, 0, 1]

Hier ist das Muster etwas anders: Man multipliziert das erste Element im Lösungsvektor mit dem zweiten Element, dann mit dem fünften Element, addiert die beiden Ergebnisse und prüft, ob die Summe dem sechsten Element entspricht. Da das erste Element im Lösungsvektor immer eins ist, handelt es sich lediglich um eine Additionsprüfung, bei der überprüft wird, ob die Ausgabe der Summe der beiden Eingaben entspricht.

Zum Schluss das vierte Tor:

a = [5, 0, 0, 0, 0, 1]
b = [1, 0, 0, 0, 0, 0]
c = [0, 0, 1, 0, 0, 0]

Hier werten wir die letzte Prüfung aus, ~out =���2+5. Die Skalarproduktprüfung funktioniert, indem das sechste Element im Lösungsvektor genommen, das Fünffache des ersten Elements addiert wird (zur Erinnerung: Das erste Element ist 1, das bedeutet also effektiv, dass 5 addiert werden) und es mit dem dritten Element verglichen wird, bei dem wir Speichern Sie die Ausgabevariable.

Und da haben wir unser R1CS mit vier Einschränkungen. Der Zeuge ist einfach die Zuweisung zu allen Variablen, einschließlich Eingabe-, Ausgabe- und internen Variablen:

[1, 3, 35, 9, 27, 30]

Sie können dies selbst berechnen, indem Sie einfach den obigen abgeflachten Code „ausführen“, mit der Zuweisung der Eingabevariablen �=3 beginnen und die Werte aller Zwischenvariablen und die Ausgabe eingeben, während Sie sie berechnen.

Das vollständige R1CS besteht aus:

A
[0, 1, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 1, 0]
[5, 0, 0, 0, 0, 1]

B
[0, 1, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]

C
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0]

R1CS zu QAP

Der nächste Schritt besteht darin, dieses R1CS zu nehmen und in die QAP-Form umzuwandeln, die genau die gleiche Logik implementiert, außer dass Polynome anstelle von Skalarprodukten verwendet werden. Wir machen das wie folgt. Wir gehen von vier Gruppen mit drei Vektoren der Länge sechs zu sechs Gruppen mit drei Polynomen vom Grad 3 über, wobei wir die Polynome jeweils auswerten x-Koordinate stellt eine der Einschränkungen dar. Das heißt, wenn wir die Polynome bei �=1 auswerten, erhalten wir unseren ersten Vektorsatz, wenn wir die Polynome bei �=2 auswerten, erhalten wir unseren zweiten Vektorsatz und so weiter.

Wir können diese Transformation mit etwas namens a durchführen Lagrange-Interpolation. Das Problem, das eine Lagrange-Interpolation löst, ist folgendes: Wenn Sie eine Reihe von Punkten haben (d. h. (�,�) Koordinatenpaare), dann erhalten Sie durch eine Lagrange-Interpolation an diesen Punkten ein Polynom, das durch alle diese Punkte verläuft. Wir tun dies, indem wir das Problem zerlegen: Für jede �-Koordinate erstellen wir ein Polynom, das an dieser �-Koordinate die gewünschte �-Koordinate und an allen anderen �-Koordinaten, an denen wir interessiert sind, eine �-Koordinate von 0 hat, und erhalten dann das Endergebnis Als Ergebnis addieren wir alle Polynome.

Machen wir ein Beispiel. Angenommen, wir wollen ein Polynom, das durch (1,3), (2,2) und (3,4) verläuft. Wir beginnen mit der Erstellung eines Polynoms, das durch (1,3), (2,0) und (3,0) verläuft. Wie sich herausstellt, ist es einfach, ein Polynom zu erstellen, das bei �=1 „herausragt“ und an den anderen interessierenden Punkten Null ist; Wir machen einfach:

(x - 2) * (x - 3)

Welches sieht so aus:

Jetzt müssen wir es nur noch „neu skalieren“, damit die Höhe bei x=1 stimmt:

(x - 2) * (x - 3) * 3 / ((1 - 2) * (1 - 3))

Dies gibt uns:

1.5 * x**2 - 7.5 * x + 9

Das Gleiche machen wir dann mit den anderen beiden Punkten und erhalten zwei weitere ähnlich aussehende Polynome, nur dass sie bei �=2 und �=3 statt bei �=1 „herausragen“. Wir addieren alle drei und erhalten:

1.5 * x**2 - 5.5 * x + 7

Mit genau den Koordinaten, die wir wollen. Der oben beschriebene Algorithmus benötigt �(�3) Zeit, da es � Punkte gibt und jeder Punkt �(�2) Zeit benötigt, um die Polynome miteinander zu multiplizieren; Mit ein wenig Nachdenken kann dies auf �(�2) Zeit reduziert werden, und mit viel mehr Nachdenken, unter Verwendung schneller Fourier-Transformationsalgorithmen und dergleichen, kann es sogar noch weiter reduziert werden – eine entscheidende Optimierung, wenn Funktionen verwendet werden, die in zk verwendet werden -SNARKs haben in der Praxis oft viele tausend Tore.

Lassen Sie uns nun die Lagrange-Interpolation verwenden, um unser R1CS zu transformieren. Was wir tun werden, ist, den ersten Wert aus jedem �-Vektor zu entnehmen, mithilfe der Lagrange-Interpolation ein Polynom daraus zu erstellen (wobei die Auswertung des Polynoms bei � den ersten Wert des �-ten �-Vektors ergibt) und den Vorgang zu wiederholen für den ersten Wert jedes �- und �-Vektors und wiederholen Sie diesen Vorgang dann für die zweiten Werte, die dritten Werte usw. Der Einfachheit halber gebe ich gleich die Antworten:

A polynomials
[-5.0, 9.166, -5.0, 0.833]
[8.0, -11.333, 5.0, -0.666]
[0.0, 0.0, 0.0, 0.0]
[-6.0, 9.5, -4.0, 0.5]
[4.0, -7.0, 3.5, -0.5]
[-1.0, 1.833, -1.0, 0.166]

B polynomials
[3.0, -5.166, 2.5, -0.333]
[-2.0, 5.166, -2.5, 0.333]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]

C polynomials
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[-1.0, 1.833, -1.0, 0.166]
[4.0, -4.333, 1.5, -0.166]
[-6.0, 9.5, -4.0, 0.5]
[4.0, -7.0, 3.5, -0.5]

Die Koeffizienten sind in aufsteigender Reihenfolge, daher ist das erste Polynom oben tatsächlich 0.833⋅�3—5⋅�2+9.166⋅�−5. Dieser Satz Polynome (plus ein Z-Polynom, das ich später erläutern werde) bildet die Parameter für diese spezielle QAP-Instanz. Beachten Sie, dass die gesamte Arbeit bis zu diesem Punkt nur einmal für jede Funktion durchgeführt werden muss, die Sie mit zk-SNARKs überprüfen möchten. Sobald die QAP-Parameter generiert sind, können sie wiederverwendet werden.

Versuchen wir, alle diese Polynome bei �=1 auszuwerten. Die Auswertung eines Polynoms bei �=1 bedeutet einfach, alle Koeffizienten zu addieren (da 1�=1 für alle �), es ist also nicht schwierig. Wir bekommen:

A results at x=1
0
1
0
0
0
0

B results at x=1
0
1
0
0
0
0

C results at x=1
0
0
0
1
0
0

Und siehe da, was wir hier haben, ist genau das Gleiche wie der Satz von drei Vektoren für das erste Logikgatter, das wir oben erstellt haben.

Überprüfung des QAP

Was ist nun der Sinn dieser verrückten Transformation? Die Antwort lautet: Anstatt die Einschränkungen im R1CS einzeln zu überprüfen, können wir jetzt eine Überprüfung durchführen alle Einschränkungen gleichzeitig indem Sie die Punktproduktprüfung durchführen auf den Polynomen.

Da es sich bei der Skalarproduktprüfung in diesem Fall um eine Reihe von Additionen und Multiplikationen von Polynomen handelt, ist das Ergebnis selbst ein Polynom. Wenn das resultierende Polynom, das an jeder �-Koordinate ausgewertet wird, die wir oben zur Darstellung eines Logikgatters verwendet haben, gleich Null ist, bedeutet das, dass alle Prüfungen bestanden sind; Wenn das resultierende Polynom, das an mindestens einer der ein Logikgatter darstellenden �-Koordinate ausgewertet wird, einen Wert ungleich Null ergibt, bedeutet dies, dass die Werte, die in dieses Logikgatter ein- und ausgehen, inkonsistent sind (d. h. das Gatter ist �=�⋅��). �1, aber die bereitgestellten Werte könnten �=2,���1=2 und �=5 sein).

Beachten Sie, dass das resultierende Polynom selbst nicht Null sein muss und in den meisten Fällen auch nicht Null sein wird. Es könnte sich an den Punkten, die keinem Logikgatter entsprechen, beliebig verhalten, solange das Ergebnis an allen Punkten Null ist do entsprechen einem Tor. Um die Richtigkeit zu überprüfen, werten wir das Polynom �=�.�⋅�.�−�.� nicht an jedem Punkt aus, der einem Tor entspricht; Stattdessen dividieren wir � durch ein anderes Polynom, �, und überprüfen, ob � gleichmäßig teilt – das heißt, die Division �/� hinterlässt keinen Rest.

� ist definiert als (�−1)⋅(�−2)⋅(�−3)… – das einfachste Polynom, das an allen Punkten, die Logikgattern entsprechen, gleich Null ist. Das ist eine elementare Tatsache der Algebra jedem Ein Polynom, das an allen diesen Punkten gleich Null ist, muss ein Vielfaches dieses minimalen Polynoms sein, und wenn ein Polynom ein Vielfaches von ist, dann ist seine Auswertung an jedem dieser Punkte Null; Diese Gleichwertigkeit erleichtert unsere Arbeit erheblich.

Lassen Sie uns nun tatsächlich die Skalarproduktprüfung mit den obigen Polynomen durchführen. Zuerst die Zwischenpolynome:

A . s = [43.0, -73.333, 38.5, -5.166]
B . s = [-3.0, 10.333, -5.0, 0.666]
C . s = [-41.0, 71.666, -24.5, 2.833]

Nun, �.�⋅�.�—�.�:

t = [-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444]

Nun ist das Minimalpolynom �=(�−1)⋅(�−2)⋅(�−3)⋅(�−4):

Z = [24, -50, 35, -10, 1]

Und wenn wir das obige Ergebnis durch � dividieren, erhalten wir:

h = t / Z = [-3.666, 17.055, -3.444]

Ohne Rest.

Und so haben wir die Lösung für den QAP. Wenn wir versuchen, eine der Variablen in der R1CS-Lösung, aus der wir diese QAP-Lösung ableiten, zu verfälschen – beispielsweise die letzte Variable auf 31 statt auf 30 zu setzen, erhalten wir ein �-Polynom, das eine der Prüfungen nicht besteht (in diesem Fall). In diesem Fall wäre das Ergebnis bei �=3 −1 statt 0) und außerdem wäre � kein Vielfaches von �; Vielmehr würde die Division von �/� einen Rest von [−5.0,8.833,−4.5,0.666] ergeben.

Beachten Sie, dass es sich bei dem oben Gesagten um eine Vereinfachung handelt. „In der realen Welt“ geschieht die Addition, Multiplikation, Subtraktion und Division nicht mit regulären Zahlen, sondern mit endlichen Körperelementen – eine gruselige Art der Arithmetik, die in sich selbst konsistent ist, also alle algebraischen Gesetze, die wir noch kennen und lieben gilt, aber alle Antworten sind Elemente einer Menge endlicher Größe, normalerweise ganze Zahlen im Bereich von 0 bis �−1 für einige �. Wenn beispielsweise �=13, dann 1/2=7 (und 7⋅2=1), 3⋅5=2 und so weiter. Durch die Verwendung der Finite-Feld-Arithmetik müssen Sie sich keine Gedanken über Rundungsfehler machen, und das System kann problemlos mit elliptischen Kurven arbeiten, die letztendlich für den Rest der zk-SNARK-Maschinerie notwendig sind, die das zk-SNARK-Protokoll tatsächlich sicher macht.

Besonderer Dank geht an Eran Tromer, der mir dabei geholfen hat, mir viele Details über das Innenleben von zk-SNARKs zu erklären.

• SEO-gestützte Content- und PR-Distribution. Holen Sie sich noch heute Verstärkung.
• PlatoData.Network Vertikale generative KI. Motiviere dich selbst. Hier zugreifen.
• PlatoAiStream. Web3-Intelligenz. Wissen verstärkt. Hier zugreifen.
• PlatoESG. Kohlenstoff, CleanTech, Energie, Umwelt, Solar, Abfallwirtschaft. Hier zugreifen.
• PlatoHealth. Informationen zu Biotechnologie und klinischen Studien. Hier zugreifen.
• BlockOffsets. Modernisierung des Eigentums an Umweltkompensationen. Hier zugreifen.
• Quelle: Datenintelligenz von Platon.