Vitaliks neues Werk: Entdecken Sie Circle STARKs

Originaltitel: „Exploring Circle STARKs“

Geschrieben von: Vitalik Buterin, Mitbegründer von Ethereum

Zusammengestellt von: Chris, Techub News

Voraussetzung für das Verständnis dieses Artikels ist, dass Sie die Grundprinzipien von SNARKs und STARKs bereits verstehen. Wenn Sie damit nicht vertraut sind, empfehle ich Ihnen, die ersten Teile dieses Artikels zu lesen, um die Grundlagen zu verstehen.

In den letzten Jahren ging der Trend beim STARK-Protokolldesign hin zur Verwendung kleinerer Felder. Die frühesten Produktionsimplementierungen von STARKs verwendeten 256-Bit-Felder, d. h. Modulo-Arithmetik für große Zahlen (z. B. 21888...95617), wodurch diese Protokolle mit Signaturen auf Basis elliptischer Kurven kompatibel wurden. Die Effizienz dieses Entwurfs ist jedoch relativ gering. Unter normalen Umständen hat die Verarbeitung und Berechnung dieser großen Zahlen keinen praktischen Nutzen und verschwendet viel Rechenleistung, z. B. die Verarbeitung von X (die eine bestimmte Zahl darstellt) und die Verarbeitung von viermal X , Verarbeitung Es wird nur ein Neuntel der Rechenzeit benötigt. Um dieses Problem zu lösen, begannen STARKs, auf kleinere Felder auszuweichen: zuerst Goldlöckchen, dann Mersenne31 und BabyBear.

Diese Verschiebung hat die Beweisgeschwindigkeit verbessert, so dass Starkware beispielsweise 620.000 Poseidon2-Hashes pro Sekunde auf einem M3-Laptop nachweisen kann. Das heißt, solange wir bereit sind, Poseidon2 als Hash-Funktion zu vertrauen, können wir das schwierige Problem der Entwicklung eines effizienten ZK-EVM lösen. Wie funktionieren diese Technologien? Wie bauen diese Beweise auf kleineren Feldern auf? Wie schneiden diese Protokolle im Vergleich zu Lösungen wie Binius ab? Dieser Artikel untersucht diese Details und konzentriert sich dabei insbesondere auf ein Schema namens Circle STARKs (implementiert in Starkwares stwo, Polygons plonky3 und meiner eigenen Version in Python), das die einzigartige Eigenschaft hat, mit Mersenne31-Feldern kompatibel zu sein.

Häufige Probleme bei der Arbeit mit kleineren Mathematikfeldern

Ein sehr wichtiger Trick beim Erstellen von Hash-basierten Beweisen (oder Beweisen jeglicher Art) besteht darin, die Eigenschaften eines Polynoms indirekt überprüfen zu können, indem das Polynom an zufälligen Punkten ausgewertet wird. Dieser Ansatz kann den Beweisprozess erheblich vereinfachen, da die Auswertung an zufälligen Punkten normalerweise viel einfacher ist als die Betrachtung des gesamten Polynoms.

Angenommen, ein Beweissystem erfordert, dass Sie eine Verpflichtung zu einem Polynom A generieren, das A^3 (x) + x - A (\omega*x) = x^N erfüllen muss (eine im ZK sehr häufig vorkommende Gleichung). -SNARK-Protokoll-Proof-Typ). Das Protokoll könnte Sie auffordern, eine zufällige Koordinate auszuwählen und zu beweisen, dass A (r) + r - A (\omega*r) = r^N. Arbeiten Sie dann rückwärts zu A (r) = c und beweisen Sie, dass Q = \frac {A - c}{X - r} ein Polynom ist.

Wenn Sie die Details oder Interna der Protokolle im Voraus kennen, können Sie möglicherweise Möglichkeiten finden, sie zu umgehen oder zu hacken. Als nächstes können spezifische Maßnahmen oder Methoden erwähnt werden, um dies zu erreichen. Um beispielsweise die Gleichung A (\omega * r) zu erfüllen, könnten Sie A (r) auf 0 setzen und A eine gerade Linie durch diese beiden Punkte sein lassen.

Um diese Angriffe zu verhindern, müssen wir r auswählen, nachdem der Angreifer A bereitgestellt hat (Fiat-Shamir ist eine Technik zur Verbesserung der Protokollsicherheit, indem bestimmte Parameter auf einen Hash-Wert gesetzt werden, um Angriffe zu vermeiden. Wählen Sie Die Parameter müssen aus einem ausreichend großen Bereich stammen So wird sichergestellt, dass ein Angreifer diese Parameter nicht vorhersagen oder erraten kann, wodurch die Sicherheit des Systems erhöht wird.

Bei elliptischen Kurven-basierten Protokollen und STARKs im Zeitraum 2019 ist das Problem einfach: Alle unsere mathematischen Operationen basieren auf 256-Bit-Zahlen, sodass wir r als zufällige 256-Bit-Zahl wählen können, sodass . Bei STARKs auf kleineren Feldern stoßen wir jedoch auf ein Problem: Es stehen nur etwa 2 Milliarden mögliche Werte von r zur Auswahl, sodass ein Angreifer, der einen Beweis fälschen möchte, nur 2 Milliarden Mal versuchen muss, was a ist Viel Arbeit, aber für einen entschlossenen Angreifer ist es durchaus möglich!

Für dieses Problem gibt es zwei Lösungen:

• Führen Sie mehrere Stichprobenkontrollen durch

• Erweiterungsfelder

Der einfachste und effizienteste Weg, mehrere Stichprobenprüfungen durchzuführen, besteht darin, die Prüfung nicht an einer Koordinate, sondern an vier zufälligen Koordinaten zu wiederholen. Dies ist theoretisch möglich, es gibt jedoch Effizienzprobleme. Wenn Sie es mit einem Polynom mit einem Grad kleiner als einem bestimmten Wert zu tun haben und auf einer Domäne einer bestimmten Größe arbeiten, kann ein Angreifer tatsächlich ein bösartiges Polynom erstellen, das an diesen Stellen normal aussieht. Ob sie das Protokoll erfolgreich durchbrechen können, ist daher eine Wahrscheinlichkeitsfrage. Daher muss die Anzahl der Überprüfungsrunden erhöht werden, um die allgemeine Sicherheit zu verbessern und sicherzustellen, dass Angreifer wirksam gegen Angriffe verteidigt werden können.

Dies führt zu einer anderen Lösung: Erweiterte Felder sind wie komplexe Zahlen, basieren jedoch auf endlichen Feldern. Wir führen einen neuen Wert ein, der als α\alphaα bezeichnet wird, und erklären, dass er eine bestimmte Beziehung erfüllt, wie zum Beispiel α2=irgendein Wert\alpha^2 = \text {irgendein Wert}α2=irgendein Wert. Auf diese Weise schaffen wir eine neue mathematische Struktur, die in der Lage ist, komplexere Operationen auf endlichen Feldern durchzuführen. In diesem erweiterten Bereich wird die Berechnung der Multiplikation zu einer Multiplikation mit dem neuen Wert α\alphaα. Wir können jetzt Wertepaare in einem erweiterten Bereich bearbeiten, nicht nur einzelne Zahlen. Wenn wir beispielsweise an einem Bereich wie Mersenne oder BabyBear arbeiten, ermöglicht uns eine solche Erweiterung mehr Wertauswahlmöglichkeiten und verbessert so die Sicherheit. Um die Feldgröße weiter zu vergrößern, können wir dieselbe Technik wiederholt anwenden. Da wir α\alphaα bereits verwendet haben, müssen wir einen neuen Wert definieren, der in Mersenne31 durch die Wahl von α\alphaα dargestellt wird, sodass α2=ein Wert\alpha^2 = \text {ein Wert}α2=ein Wert ist.

Code (Sie können ihn mit Karatsuba verbessern)

Durch die Erweiterung der Domain haben wir nun genügend Werte zur Auswahl, die unseren Sicherheitsanforderungen entsprechen. Wenn es sich um Polynome mit einem Grad kleiner als ddd handelt, bietet dies 104 Bit Sicherheit pro Runde. Das bedeutet, dass wir über ausreichende Sicherheit verfügen. Wenn eine höhere Sicherheitsstufe erforderlich ist, beispielsweise 128-Bit, können wir dem Protokoll zusätzliche Rechenarbeit hinzufügen, um die Sicherheit zu erhöhen.

Erweiterte Domänen werden tatsächlich nur in FRI-Protokollen (Fast Reed-Solomon Interactive) und anderen Szenarien verwendet, die zufällige lineare Kombinationen erfordern. Der größte Teil der Berechnung wird immer noch für die zugrunde liegenden Felder durchgeführt, bei denen es sich normalerweise um Felder modulo ppp oder qqq handelt. Außerdem werden fast alle gehashten Daten in den zugrunde liegenden Feldern verarbeitet, sodass nur vier Bytes pro Wert gehasht werden. Dadurch wird die Effizienz kleiner Felder genutzt und gleichzeitig die Verwendung größerer Felder ermöglicht, wenn Sicherheitsverbesserungen erforderlich sind.

Regulär FR

Beim Erstellen eines SNARK oder STARK ist der erste Schritt normalerweise die Arithmetisierung. Dies ist die Umwandlung eines beliebigen Rechenproblems in eine Gleichung, in der einige der Variablen und Koeffizienten Polynome sind. Konkret sieht diese Gleichung typischerweise so aus: P (X,Y,Z)=0P (X,Y,Z) = 0P (X,Y,Z)=0, wobei P ein Polynom und Z ein gegebener Parameter ist und die Der Löser muss X- und Y-Werte bereitstellen. Sobald Sie eine solche Gleichung haben, entspricht die Lösung dieser Gleichung der Lösung des zugrunde liegenden Rechenproblems.

Um zu beweisen, dass Sie eine Lösung haben, müssen Sie zeigen, dass die von Ihnen ermittelten Werte tatsächlich legitime Polynome sind (im Gegensatz zu Brüchen oder dass sie an manchen Stellen wie ein Polynom und an anderen wie ein anderes Polynom aussehen usw.). Und diese Polynome haben einen bestimmten Maximalgrad. Dazu verwenden wir eine stochastische Linearkombinationstechnik, die schrittweise angewendet wird:

• Angenommen, Sie haben eine Auswertung eines Polynoms A und möchten beweisen, dass sein Grad kleiner als 2^{20} ist.

• Betrachten Sie das Polynom B (x^2) = A (x) + A (-x), C (x^2) = \frac {A (x) - A (-x)}{x}

• D ist eine zufällige lineare Kombination von B und C, d. h. D=B+rCD = B + rCD=B+rC, wobei r ein Zufallskoeffizient ist.

Im Wesentlichen isoliert B die geraden Koeffizienten von A und ? isoliert die ungeraden Koeffizienten. Wenn B und C gegeben sind, können Sie das ursprüngliche Polynom A wiederherstellen: A (x) = B (x^2) + xC (x^2). Wenn der Grad von A tatsächlich kleiner als 2^{20} ist, dann sind die Grade von B und C der Grad von A bzw. der Grad von A minus 1. Denn die Kombination von geraden und ungeraden Termen erhöht den Grad nicht. Da D eine zufällige lineare Kombination von B und C ist, sollte der Grad von D auch der Grad von A sein, sodass Sie anhand des Grades von D überprüfen können, ob der Grad von A die Anforderungen erfüllt.

Erstens vereinfacht FRI den Verifizierungsprozess, indem es das Problem des Beweises eines Polynoms vom Grad d auf das Problem des Beweises eines Polynoms vom Grad d/2 reduziert. Dieser Vorgang kann viele Male wiederholt werden, wodurch sich das Problem jedes Mal halbiert.

FRI funktioniert durch die Wiederholung dieses Vereinfachungsprozesses. Wenn Sie beispielsweise zunächst beweisen, dass der Grad eines Polynoms d ist, werden Sie in einer Reihe von Schritten schließlich beweisen, dass der Grad des Polynoms d/2 ist. Nach jeder Vereinfachung nimmt der Grad des resultierenden Polynoms allmählich ab. Wenn die Ausgabe einer Stufe nicht dem erwarteten Polynomgrad entspricht, schlägt diese Prüfrunde fehl. Wenn jemand versucht, ein Polynom, das nicht vom Grad d ist, durch diese Technik voranzutreiben, wird sein Grad in der zweiten Ausgaberunde mit einer gewissen Wahrscheinlichkeit nicht den Erwartungen entsprechen, und in der dritten Runde wird es eher inkonsistent sein. und schließlich wird die Prüfung fehlschlagen. Dieses Design kann Eingaben, die nicht den Anforderungen entsprechen, effektiv erkennen und zurückweisen. Ein Datensatz besteht die FRI-Validierung wahrscheinlich, wenn er an den meisten Stellen einem Polynom vom Grad d entspricht. Um einen solchen Datensatz zu erstellen, muss der Angreifer jedoch die tatsächlichen Polynome kennen, sodass selbst ein leicht fehlerhafter Beweis zeigt, dass der Beweiser in der Lage ist, einen „echten“ Beweis zu generieren.

Werfen wir einen genaueren Blick darauf, was hier vor sich geht und welche Eigenschaften erforderlich sind, damit das alles funktioniert. Bei jedem Schritt reduzieren wir den Grad des Polynoms um die Hälfte und reduzieren auch die Menge der Punkte (die Menge der Punkte, die uns interessiert) um die Hälfte. Ersteres ist der Schlüssel dazu, dass das FRI-Protokoll (Fast Reed-Solomon Interactive) ordnungsgemäß funktioniert. Letzteres führt dazu, dass der Algorithmus extrem schnell läuft: Da die Größe jeder Runde im Vergleich zur vorherigen Runde um die Hälfte reduziert wird, beträgt der Gesamtrechenaufwand O (N) statt O (N*log (N)).

Um eine progressive Reduzierung der Domäne zu erreichen, wird eine Zwei-zu-Eins-Abbildung verwendet, d. h. jeder Punkt wird einem von zwei Punkten zugeordnet. Durch diese Zuordnung können wir die Größe des Datensatzes um die Hälfte reduzieren. Ein wichtiger Vorteil dieser Zwei-zu-Eins-Zuordnung besteht darin, dass sie wiederholbar ist. Das heißt, wenn wir diese Zuordnung anwenden, behält die resultierende Ergebnismenge immer noch dieselben Eigenschaften. Angenommen, wir beginnen mit einer multiplikativen Untergruppe. Diese Untergruppe ist eine Menge S, in der jedes Element x auch in der Menge ein Vielfaches von 2x hat. Wenn Sie die Menge S quadrieren (d. h. jedes Element x in der Menge auf x^2 abbilden), behält die neue Menge S^2 dieselben Eigenschaften. Dieser Vorgang ermöglicht es uns, die Größe des Datensatzes weiter zu reduzieren, bis schließlich nur noch ein Wert übrig bleibt. Während wir theoretisch den Datensatz auf nur einen Wert verkleinern könnten, hören wir in der Praxis normalerweise auf, bevor wir einen kleineren Satz erreichen.

Sie können sich diesen Vorgang als den Vorgang vorstellen, bei dem eine Linie (z. B. ein Liniensegment oder ein Bogen) auf dem Umfang eines Kreises gestreckt wird, sodass sie zwei Umdrehungen um den Kreis macht. Wenn sich ein Punkt beispielsweise bei x Grad auf dem Umfang befindet, wird er nach diesem Vorgang um 2x Grad verschoben. Jeder Punkt auf dem Kreis von 0 bis 179 Grad hat einen entsprechenden Punkt von 180 bis 359 Grad, und diese beiden Punkte fallen zusammen. Das heißt, wenn Sie einen Punkt von x Grad auf 2x Grad abbilden, fällt er mit einer Position bei x+180 Grad zusammen. Dieser Vorgang kann wiederholt werden. Das heißt, Sie können diesen Zuordnungsvorgang mehrmals anwenden und dabei jedes Mal die Punkte auf dem Kreis an ihre neuen Positionen verschieben.

Damit die Abbildungstechnik effektiv ist, muss die Größe der ursprünglichen multiplikativen Untergruppe große Potenzen von 2 als Faktoren aufweisen. BabyBear ist ein System mit einem bestimmten Modul, sodass seine maximale multiplikative Untergruppe alle Werte ungleich Null enthält, sodass die Größe der Untergruppe 2k−1 beträgt (wobei k die Anzahl der Stellen im Modul ist). Untergruppen dieser Größe eignen sich gut für die obige Technik, da sie eine effiziente Reduzierung des Polynomgrades durch wiederholte Anwendung der Abbildungsoperation ermöglicht. In BabyBear können Sie eine Untergruppe der Größe 2^k auswählen (oder einfach den gesamten Satz verwenden), dann die FRI-Methode anwenden, um den Grad des Polynoms schrittweise auf 15 zu reduzieren, und am Ende den Grad des Polynoms überprüfen. Diese Methode nutzt die Eigenschaften des Moduls und der Größe der multiplikativen Untergruppe und macht den Berechnungsprozess sehr effizient. Mersenne31 ist ein weiteres System, dessen Modul ein Wert ist, sodass die Größe der multiplikativen Untergruppe 2^31 - 1 beträgt. In diesem Fall hat die Größe der multiplikativen Untergruppe als Faktor nur eine Potenz von 2, sodass sie nur einmal durch 2 geteilt werden kann. Die anschließende Verarbeitung ist für die oben genannten Techniken nicht mehr geeignet, d. h. es ist nicht möglich, FFT für eine effiziente Polynomgradreduktion wie BabyBear zu verwenden.

Mersenne31-Felder eignen sich gut für arithmetische Operationen auf vorhandenen 32-Bit-CPU/GPU-Operationen. Aufgrund seiner Modulus-Eigenschaften (z. B. 2^{31} - 1) können viele Operationen mit effizienten Bitoperationen abgeschlossen werden: Wenn das Ergebnis der Addition zweier Zahlen den Modulus überschreitet, kann das Ergebnis durch die Modulus-Operation verschoben werden, um es zu reduzieren auf einen angemessenen Bereich. Der Verdrängungsvorgang ist ein sehr effizienter Vorgang. Bei Multiplikationsoperationen werden bestimmte CPU-Anweisungen (oft als Schiebeanweisungen höherer Ordnung bezeichnet) zur Verarbeitung des Ergebnisses verwendet. Diese Anweisungen können den höherwertigen Teil der Multiplikation effizient berechnen und so die Effizienz der Operation verbessern. In der Mersenne31-Domäne sind arithmetische Operationen aufgrund der oben beschriebenen Eigenschaften etwa 1,3-mal schneller als in der BabyBear-Domäne. Mersenne31 bietet eine höhere Recheneffizienz. Wenn FRI in der Mersenne31-Domäne implementiert werden kann, wird dies die Recheneffizienz erheblich verbessern und FRI-Anwendungen effizienter machen.

Kreis FR

Das ist das Schöne an Circle STARKs: Wenn eine Primzahl p gegeben ist, können Sie eine Population der Größe p finden, die ähnliche Zwei-zu-Eins-Eigenschaften aufweist. Diese Population besteht aus allen Punkten, die bestimmte Bedingungen erfüllen, beispielsweise der Menge der Punkte, bei denen x^2 mod p einem bestimmten Wert entspricht.

Diese Punkte folgen einem additiven Muster, das Ihnen vielleicht bekannt vorkommt, wenn Sie sich in letzter Zeit mit Trigonometrie oder komplexer Multiplikation beschäftigt haben.

(x_1, y_1) + (x_2, y_2) = (x_1x_2 - y_1y_2, x_1y_2 + x_2y_1)

Die doppelte Form ist:

2 * (x, y) = (2x^2 - 1, 2xy)

Konzentrieren wir uns nun auf die ungeraden Punkte in diesem Kreis:

Zuerst konvergieren wir alle Punkte zu einer Geraden. Die äquivalente Form der Formeln B (x²) und C (x²), die wir im regulären FRI verwenden, ist:

f_0 (x) = \frac {F (x,y) + F (x,-y)}{2}

Wir können dann zufällige lineare Kombinationen durchführen, um ein eindimensionales Polynom P(x) zu erhalten, das über eine Teilmenge der x-Linien definiert ist:

Ab der zweiten Runde ändert sich die Zuordnung:

f_0 (2x^2-1) = \frac {F (x) + F (-x)}{2}

Diese Zuordnung reduziert tatsächlich jedes Mal die Größe des obigen Satzes um die Hälfte. Was hier passiert, ist, dass jedes x in gewisser Weise zwei Punkte darstellt: (x, y) und (x, -y). Und (x → 2x^2 - 1) ist die obige Punktverdopplungsregel. Daher wandeln wir die x-Koordinaten zweier gegenüberliegender Punkte auf dem Kreis in die x-Koordinaten des multiplizierten Punkts um.

Nehmen wir zum Beispiel den zweiten Wert auf dem Kreis von rechts, 2, und wenden die Abbildung 2 → 2 (2^2) - 1 = 7 an, erhalten wir als Ergebnis 7. Wenn wir zum ursprünglichen Kreis zurückkehren, ist (2, 11) der dritte Punkt von rechts, also verdoppeln wir uns, dass wir den sechsten Punkt von rechts erhalten, nämlich (7, 13).

Dies hätte in zwei Dimensionen erfolgen können, aber die Arbeit in einer Dimension macht den Prozess effizienter.

Kreis-FFTs

Ein eng mit FRI verwandter Algorithmus ist FFT, der n Bewertungen eines Polynoms mit einem Grad kleiner als n in n Koeffizienten dieses Polynoms umwandelt. Der Prozess der FFT ähnelt dem von FRI, mit der Ausnahme, dass FFT nicht bei jedem Schritt zufällige lineare Kombinationen f_0 und f_1 generiert, sondern rekursiv eine FFT halber Größe für diese ausführt und die Ausgabe der FFT (f_0) als gerade Koeffizienten verwendet. Behandeln Sie die Ausgabe der FFT (f_1) als ungerade Koeffizienten.

Kreisgruppen unterstützen auch FFTs, die ähnlich wie FRIs aufgebaut sind. Ein wesentlicher Unterschied besteht jedoch darin, dass Circle FFT (und Circle FRI) Objekte behandeln, die keine reinen Polynome sind. Stattdessen handelt es sich um sogenannte Riemann-Roch-Räume: In diesem Fall sind die Polynome modulo-zirkular ( x^2 + y^2 - 1 = 0 ). Das heißt, wir behandeln jedes Vielfache von x^2 + y^2 - 1 als Null. Anders ausgedrückt: Wir lassen nur zu, dass y potenziert wird: Sobald ein y^2-Term erscheint, ersetzen wir ihn durch 1 - x^2 .

Dies bedeutet auch, dass die von Circle FFT ausgegebenen Koeffizienten keine Monome wie reguläres FRI sind (wenn beispielsweise reguläres FRI [6, 2, 8, 3] ausgibt, dann wissen wir, dass dies P (x) = 3x^3 + 8x bedeutet ^2 + 2x + 6). Im Gegensatz dazu sind die Koeffizienten der Kreis-FFT spezifisch für die Kreis-FFT-Basis: {1, y, x, xy, 2x^2 - 1, 2x^2y - y, 2x^3 - x, 2x^3y - xy, 8x^4 - 8x^2 + 1...}

Die gute Nachricht ist, dass Sie als Entwickler dies fast vollständig ignorieren können. Bei STARKs müssen Sie niemals die Koeffizienten kennen. Stattdessen speichern Sie das Polynom einfach als Satz von Bewertungswerten über einen bestimmten Bereich. Der einzige Ort, an dem Sie FFT verwenden müssen, ist eine Erweiterung niedrigen Grades (ähnlich dem Riemann-Roch-Raum): Bei gegebenen N Werten werden k*N Werte generiert, alle auf demselben Polynom. In diesem Fall können Sie eine FFT verwenden, um die Koeffizienten zu generieren, (k-1) n Nullen an diese Koeffizienten anhängen und dann die inverse FFT verwenden, um einen größeren Satz ausgewerteter Werte zu erhalten.

Kreis-FFTs sind nicht der einzige spezielle FFT-Typ. Elliptische Kurven-FFTs sind leistungsfähiger, da sie auf jedem endlichen Körper (Primärkörper, Binärkörper usw.) arbeiten können. ECFFT ist jedoch komplexer und weniger effizient. Da wir Circle FFT für p = 2^{31}-1 verwenden können, entscheiden wir uns für die Verwendung.

Von hier aus werden wir uns mit einigen der obskureren Details befassen, die die Implementierung von Circle STARKs von regulären STARKs unterscheiden.

Quotientenbildung

Im STARK-Protokoll besteht eine übliche Operation darin, Quotientenoperationen an bestimmten Punkten durchzuführen. Diese Punkte können absichtlich oder zufällig ausgewählt werden. Wenn Sie beispielsweise beweisen möchten, dass P (x) = y ist, können Sie dies tun, indem Sie die folgenden Schritte ausführen:

Berechnen Sie den Quotienten: Berechnen Sie bei einem gegebenen Polynom P (x) und einer Konstanten y den Quotienten Q ={P - y}/{X - x}, wobei X der gewählte Punkt ist.

Polynome beweisen: Beweisen Sie, dass Q ein Polynom und kein Bruch ist. Auf diese Weise wird bewiesen, dass P (x)=y wahr ist.

Darüber hinaus werden im DEEP-FRI-Protokoll die Bewertungspunkte zufällig ausgewählt, um die Anzahl der Merkle-Zweige zu reduzieren und dadurch die Sicherheit und Effizienz des FRI-Protokolls zu verbessern.

Da es beim Umgang mit dem STARK-Protokoll der Kreisgruppe keine lineare Funktion gibt, die durch einen einzelnen Punkt verlaufen kann, müssen unterschiedliche Techniken verwendet werden, um die herkömmliche Quotientenoperationsmethode zu ersetzen. Dies erfordert häufig die Entwicklung neuer Algorithmen, die die einzigartigen geometrischen Eigenschaften von Kreisgruppen nutzen.

In einer Kreisgruppe können Sie eine Tangentenfunktion konstruieren, die einen bestimmten Punkt (P_x, P_y) tangiert, aber diese Funktion hat durch den Punkt eine Multiplizität von 2, das heißt, ein Polynom wird zum A-Vielfachen einer linearen Funktion, die muss strengere Bedingungen erfüllen, als zu diesem Zeitpunkt einfach Null zu sein. Daher können Sie die Bewertungsergebnisse nicht einfach an einem Punkt beweisen. Wie gehen wir also damit um?

Wir mussten diese Herausforderung annehmen und sie durch die Bewertung an zwei Punkten beweisen und dabei einen Dummy-Punkt hinzufügen, auf den wir uns nicht konzentrieren mussten.

Linienfunktion: ax + by + c. Wenn Sie es in eine Gleichung umwandeln und den Wert 0 erzwingen, erkennen Sie es möglicherweise als eine Linie in der sogenannten Standardform in der Mathematik der Oberstufe.

Wenn wir ein Polynom P haben, das bei x_1 gleich y_1 und bei x_2 gleich y_2 ist, können wir eine Interpolationsfunktion L wählen, die bei x_1 gleich y_1 und bei x_2 gleich y_2 ist. Dies kann einfach ausgedrückt werden als L = \frac {y_2 - y_1}{x_2 - x_1} \cdot (x - x_1) + y_1.

Wir beweisen dann, dass P gleich y_1 bei x_1 und y_2 bei x_2 ist, indem wir L subtrahieren (wodurch P - L an beiden Punkten Null wird) und durch L (d. h. eine lineare Funktion zwischen x_2 - x_1) dividieren. Durch L dividieren, um zu beweisen, dass der Quotient Q a ist Polynom.

Verschwindende Polynome

In STARK sieht die Polynomgleichung, die Sie zu beweisen versuchen, normalerweise wie folgt aus: C (P (x), P ({next}(x))) = Z (x) ⋅ H (x) , wobei Z (x) ein A ist Polynom gleich Null über den gesamten ursprünglichen Bewertungsbereich. Im regulären STARK ist diese Funktion x^n - 1. Im zirkulären STARK lautet die entsprechende Funktion:

Z_1 (x,y) = y

Z_2 (x,y) = x

Z_{n+1}(x,y) = (2 * Z_n (x,y)^2) - 1

Beachten Sie, dass Sie das verschwindende Polynom aus der Faltfunktion ableiten können: Im regulären STARK verwenden Sie x → x^2 wieder, während Sie im zirkulären STARK x → 2x^2 - 1 wiederverwenden. In der ersten Runde macht man es allerdings anders, denn die erste Runde ist etwas Besonderes.

Umgekehrte Bitreihenfolge

In STARKs werden Polynome normalerweise nicht in der „natürlichen“ Reihenfolge ausgewertet (z. B. P (1), P (ω), P (ω2),…, P (ωn−1)), sondern in dem, was ich die inverse Anordnung nenne umgekehrte Bitreihenfolge:

P (\omega^{\frac {3n}{8}})

Wenn wir n=16 setzen und uns nur darauf konzentrieren, nach welchen Potenzen von ω wir evaluieren, sieht die Liste wie folgt aus:

{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}

Diese Sortierung hat die Schlüsseleigenschaft, dass zu Beginn des FRI-Bewertungsprozesses gruppierte Werte in der Sortierung benachbart werden. Zum Beispiel der erste Schritt der FRI-Gruppen x und -x. Im Fall von n = 16 ist ω^8 = -1, was P (ω^i) ) und ( P (-ω^i) = P (ω^{i+8}) \) bedeutet. Wie wir sehen können, handelt es sich hierbei genau um die direkt nebeneinander liegenden Paare. Der zweite Schritt der FRI-Gruppen P (ω^i), P (ω^{i+4}), P (ω^{i+8}) und P (ω^{i+12}). Genau das sehen wir in Vierergruppen und so weiter. Dadurch wird FRI platzsparender, da Sie einen Merkle-Beweis für die zusammengefalteten Werte liefern können (oder, wenn Sie k Runden auf einmal falten, für alle 2^k-Werte).

Bei Kreis-STARKs ist die Faltstruktur etwas anders: Im ersten Schritt paaren wir (x, y) mit (x, -y); im zweiten Schritt paaren wir x mit -x; mit q, und wähle p und q so, dass Q^i (p) = -Q^i (q), wobei Q^i eine Abbildung ist, die x → 2x^2-1 i-mal wiederholt. Wenn wir uns die Punkte anhand ihrer Position auf dem Kreis vorstellen, dann sieht es bei jedem Schritt so aus, als ob der erste Punkt mit dem letzten Punkt gepaart wird, der zweite Punkt mit dem vorletzten Punkt und so weiter.

Um die umgekehrte Bitreihenfolge anzupassen, um diese Faltstruktur widerzuspiegeln, müssen wir jedes Bit außer dem letzten Bit umkehren. Wir behalten das letzte Bit und verwenden es, um zu entscheiden, ob die anderen Bits umgedreht werden sollen.

Eine Faltung der Größe 16 in umgekehrter Bitreihenfolge sieht wie folgt aus:

{0, 15, 8, 7, 4, 11, 12, 3, 2, 13, 10, 5, 6, 9, 14, 1}

Wenn Sie sich den Kreis aus dem vorherigen Abschnitt ansehen, werden Sie sehen, dass die Punkte 0, 15, 8 und 7 (von rechts gegen den Uhrzeigersinn) (x, y), (x, -y), (-x , - y) und (-x, y), was genau das ist, was wir brauchen.

Effizienz

In Circle STARKs (und 31-Bit-Prime-STARKs im Allgemeinen) sind diese Protokolle sehr effizient. Eine in Circle STARK bewiesene Berechnung umfasst typischerweise mehrere Arten von Berechnungen:

1. Native Arithmetik: Wird für Geschäftslogik verwendet, beispielsweise zum Zählen.

2. Native Arithmetik: Wird in der Kryptographie verwendet, beispielsweise für Hash-Funktionen wie Poseidon.

3. Nachschlageparameter: Eine allgemeine und effiziente Berechnungsmethode, die verschiedene Berechnungen durch Auslesen von Werten aus der Tabelle durchführt.

Der entscheidende Maßstab für die Effizienz ist, ob Sie den gesamten Speicherplatz vollständig nutzen, um nützliche Arbeit in einem Compute-Trace zu leisten, oder ob Sie viel freien Speicherplatz übrig lassen. In SNARKs für große Felder gibt es oft viel freien Speicherplatz: Geschäftslogik und Nachschlagetabellen beinhalten oft Berechnungen mit kleinen Zahlen (diese Zahlen sind in der Regel kleiner als N, wobei N die Gesamtzahl der Schritte in einer Berechnung ist, also in Üben Sie weniger als 2^{25}), aber Sie müssen trotzdem die Kosten für die Verwendung eines Feldes mit einer Größe von 2^{256} Bits bezahlen. Hier beträgt die Größe des Feldes 2^{31}, sodass der verschwendete Platz nicht sehr groß ist. Hashes mit geringer arithmetischer Komplexität, die für SNARKs (wie Poseidon) entwickelt wurden, nutzen jedes Bit jeder Zahl im Trace in jedem Feld vollständig aus.

Binius ist eine bessere Lösung als Circle STARKs, da es Ihnen ermöglicht, Felder unterschiedlicher Größe zu mischen, was zu einer effizienteren Bitpackung führt. Binius bietet auch die Möglichkeit, 32-Bit-Additionen ohne den Aufwand von Nachschlagetabellen durchzuführen. Diese Vorteile gehen jedoch (meiner Meinung nach) zu Lasten einer komplexeren Konzeption, während Circle STARKs (und reguläre BabyBear-basierte STARKs) konzeptionell viel einfacher sind.

Fazit: Meine Gedanken zu Circle STARKs

Circle STARKs sind für Entwickler nicht komplizierter als STARKs. Während des Implementierungsprozesses sind die drei oben genannten Probleme im Wesentlichen die Unterschiede zum herkömmlichen FRI. Obwohl die Mathematik hinter den Polynomen, mit denen Circle FRI arbeitet, sehr komplex ist und einige Zeit braucht, um sie zu verstehen und zu schätzen, ist diese Komplexität tatsächlich so verborgen, dass sie von Entwicklern nicht direkt gespürt wird.

Das Verständnis von Circle FRI und Circle FFTs kann auch ein Einstieg in das Verständnis anderer spezieller FFTs sein: vor allem binäre Domänen-FFTs, wie sie von Binius und früher LibSTARK verwendet wurden, aber auch einige komplexere Konstrukte, wie elliptische Kurven-FFTs, die mit wenigen To-Many-Mapping lässt sich gut mit elliptischen Kurvenpunktoperationen kombinieren.

In Kombination mit Mersenne31, BabyBear und binären Domänentechnologien wie Binius haben wir wirklich das Gefühl, dass wir uns den Effizienzgrenzen der STARKs-Basisschicht nähern. An dieser Stelle gehe ich davon aus, dass sich die Optimierungsrichtung von STARK auf die folgenden Punkte konzentrieren wird:

Arithmetisierung von Hash-Funktionen, Signaturen usw. zur Maximierung der Effizienz: Optimieren Sie grundlegende kryptografische Grundelemente wie Hash-Funktionen und digitale Signaturen in ihre effizientesten Formen, damit sie bei der Verwendung in STARK-Beweisen eine optimale Leistung erzielen können. Dies bedeutet spezielle Optimierungen für diese Grundelemente, um den Rechenaufwand zu reduzieren und die Effizienz zu steigern.

Rekursive Konstruktion, um mehr Parallelisierung zu ermöglichen: Unter rekursiver Konstruktion versteht man die rekursive Anwendung des STARK-Proof-Prozesses auf verschiedenen Ebenen, wodurch die Parallelverarbeitungsfähigkeiten erhöht werden. Dadurch können Rechenressourcen effizienter genutzt und der Beweisprozess beschleunigt werden.

Virtuelle Maschinen arithmetisieren, um die Entwicklererfahrung zu verbessern: Durch die Arithmetisierung virtueller Maschinen können Entwickler Rechenaufgaben effizienter und einfacher erstellen und ausführen. Dazu gehört die Optimierung der virtuellen Maschine für die Verwendung in STARK-Proofs und die Verbesserung der Entwicklererfahrung beim Erstellen und Testen von Smart Contracts oder anderen Computeraufgaben.