Binius, ein äußerst effizientes Nachweissystem

Weitergeleiteter Originaltitel 'Vitalik erklärt Binius im Detail: ein effizientes Beweissystem basierend auf binären Feldern'

Dieser Beitrag richtet sich in erster Linie an Leser, die mit der Kryptographie aus dem Jahr 2019 vertraut sind, insbesondere mit SNARKs und STARKs. Wenn Sie das nicht sind, empfehle ich Ihnen, diese Artikel zuerst zu lesen. Besonderer Dank an Justin Drake, Jim Posen, Benjamin Diamond und Radi Cojbasic für das Feedback und die Überprüfung.

In den letzten zwei Jahren sind STARKs zu einer entscheidenden und unersetzlichen Technologie geworden, um effizient einfach zu verifizierende kryptographische Beweise für sehr komplexe Aussagen (z.B. den Nachweis, dass ein Ethereum-Block gültig ist) zu erstellen. Ein wesentlicher Grund dafür sind die kleinen Feldgrößen: Während elliptische Kurven-basierte SNARKs erfordern, dass Sie über 256-Bit-Integer arbeiten, um sicher genug zu sein, lassen Sie STARKs viel kleinere Feldgrößen verwenden, die effizienter sind: zuerst das Goldilocks-Feld (64-Bit-Integer) und dann Mersenne31 und BabyBear (beide 31-Bit). Dank dieser Effizienzgewinne ist Plonky2, das Goldilocks verwendet, hunderte Male schneller bei der Beweisführung vieler Arten von Berechnungen als seine Vorgänger.

Eine naheliegende Frage ist: Können wir diesen Trend konsequent weiterverfolgen, indem wir Beweissysteme aufbauen, die noch schneller laufen, indem sie direkt über Nullen und Einsen arbeiten? Genau das versucht Binius zu tun, indem er eine Reihe mathematischer Tricks verwendet, die es sehr von den SNARKs und STARKs vor drei Jahren unterscheiden. In diesem Beitrag werden die Gründe erläutert, warum kleine Felder die Beweisgenerierung effizienter machen, warum binäre Felder einzigartig leistungsfähig sind und welche Tricks Binius verwendet, um Beweise über binäre Felder so effektiv zu machen.

Binius. Am Ende dieses Beitrags sollten Sie in der Lage sein, jeden Teil dieses Diagramms zu verstehen.

Zusammenfassung: endliche Felder

Eine der Hauptaufgaben eines kryptografischen Beweissystems besteht darin, über riesige Datenmengen zu operieren, während die Zahlen klein bleiben. Wenn Sie eine Aussage über ein großes Programm in eine mathematische Gleichung mit ein paar Zahlen komprimieren können, aber diese Zahlen so groß sind wie das ursprüngliche Programm, haben Sie nichts gewonnen.

Um komplizierte Arithmetik durchzuführen und dabei die Zahlen klein zu halten, verwenden Kryptographen in der Regel modulare Arithmetik. Wir wählen ein primens „Modulus“ p. Der % Operator bedeutet „den Rest nehmen von“: 15 % 7=1, 53 % 10=3 usw. (Beachten Sie, dass die Antwort immer nicht-negativ ist, also zum Beispiel −1 % 10=9).

Du hast wahrscheinlich bereits modulare Arithmetik gesehen, im Kontext des Hinzufügens und Subtrahierens von Zeit (z.B. welche Zeit ist vier Stunden nach 9:00?). Aber hier fügen wir nicht nur modulo eine Zahl hinzu und subtrahieren, sondern wir multiplizieren auch, dividieren und nehmen Exponenten.

Wir definieren neu:

Die obigen Regeln sind alle selbstkonsistent. Zum Beispiel, wenn p=7, dann:

5+3=1 (because 8%7=1)

1-3=5 (because -2%7=5)

2*5=3

3/5=2

Ein allgemeinerer Begriff für diese Art von Struktur ist ein endlicher Körper. Ein endlicher Körper ist eine mathematische Struktur, die den üblichen Gesetzen der Arithmetik gehorcht, aber es gibt nur eine begrenzte Anzahl möglicher Werte, und daher kann jeder Wert in einer festen Größe dargestellt werden.

Modulare Arithmetik (oder Primkörper) ist die häufigste Art von endlichen Körpern, aber es gibt auch einen anderen Typ: Erweiterungskörper. Sie haben wahrscheinlich bereits einen Erweiterungskörper gesehen: die komplexen Zahlen. Wir "erfinden" ein neues Element, das wir mit 𝑖 bezeichnen, und erklären, dass es 𝑖2=−1 erfüllt. Sie können dann jede Kombination aus regulären Zahlen und 𝑖 nehmen und damit rechnen: (3𝑖+2)∗(2𝑖+4)= 6𝑖2+12𝑖+4𝑖+8=16𝑖+2. Wir können ähnlich Erweiterungen von Primkörpern vornehmen. Wenn wir mit kleineren Feldern arbeiten, werden Erweiterungen von Primkörpern zunehmend wichtig für die Sicherheit, und binäre Felder (die Binius verwendet) sind vollständig auf Erweiterungen angewiesen, um praktisch nützlich zu sein.

Zusammenfassung: Arithmetisierung

Der Weg, wie SNARKs und STARKs Dinge über Computerprogramme beweisen, erfolgt durch Arithmetisierung: Sie wandeln eine Aussage über ein Programm, das Sie beweisen möchten, in eine mathematische Gleichung mit Polynomen um. Eine gültige Lösung für die Gleichung entspricht einer gültigen Ausführung des Programms.

Um ein einfaches Beispiel zu geben, nehmen wir an, dass ich die 100. Fibonacci-Zahl berechnet habe und dir beweisen möchte, was es ist. Ich erstelle ein Polynom 𝐹, das Fibonacci-Zahlen codiert: also 𝐹(0)=𝐹(1)=1, 𝐹(2)=2, 𝐹(3)=3, 𝐹(4)=5 usw. für 100 Schritte. Die Bedingung, die ich beweisen muss, ist, dass 𝐹(𝑥+2)=𝐹(𝑥)+𝐹(𝑥+1) über den Bereich 𝑥={0,1…98} gilt. Ich kann dich davon überzeugen, indem ich dir den Quotienten gebe:

wo Z(x) = (x-0) (x-1) …(x-98). . Wenn ich nachweisen kann, dass es ein F und H gibt, die diese Gleichung erfüllen, dann muss F die Gleichung F(x+2)-F(x+1)-F(x) im Bereich erfüllen. Wenn ich zusätzlich überprüfe, dass F erfüllt ist, F(0)=F(1)=1, dann muss F(100) tatsächlich die 100. Fibonacci-Zahl sein.

Wenn Sie etwas Komplizierteres beweisen möchten, ersetzen Sie die „einfache“ Beziehung 𝐹(𝑥+2)=𝐹(𝑥)+𝐹(𝑥+1) durch eine kompliziertere Gleichung, die im Grunde besagt, dass „𝐹(𝑥+1) der Ausgabe beim Initialisieren einer virtuellen Maschine mit dem Zustand 𝐹(𝑥) und dem Ausführen eines Berechnungsschritts“ ist. Sie können auch die Zahl 100 durch eine größere Zahl, z.B. 100000000, ersetzen, um mehr Schritte zu ermöglichen.

Alle SNARKs und STARKs basieren auf dieser Idee, eine einfache Gleichung über Polynome (manchmal auch Vektoren und Matrizen) zu verwenden, um eine große Anzahl von Beziehungen zwischen einzelnen Werten darzustellen. Nicht alle beinhalten die Überprüfung der Äquivalenz zwischen benachbarten Rechenschritten auf die gleiche Weise wie oben: PLONK zum Beispiel nicht, genauso wenig R1CS. Aber viele der effizientesten tun es, denn das Durchsetzen der gleichen Überprüfung (oder der gleichen wenigen Überprüfungen) viele Male macht es einfacher, den Overhead zu minimieren.

Plonky2: von 256-Bit SNARKs und STARKs zu 64-Bit... nur STARKs

Vor fünf Jahren war eine vernünftige Zusammenfassung der verschiedenen Arten von Zero-Knowledge-Beweisen wie folgt. Es gibt zwei Arten von Beweisen: (elliptische-Kurven-basierte) SNARKs und (hash-basierte) STARKs. Technisch gesehen sind STARKs eine Art von SNARK, aber in der Praxis ist es üblich, „SNARK“ nur für die elliptische-Kurven-basierte Variante und „STARK“ für hash-basierte Konstruktionen zu verwenden. SNARKs sind klein, sodass Sie sie sehr schnell überprüfen und problemlos onchain passen können. STARKs sind groß, erfordern jedoch keine vertrauenswürdigen Setups und sind quantenresistent.

STARKs funktionieren, indem sie die Daten als Polynom behandeln, Auswertungen dieses Polynoms an einer großen Anzahl von Punkten berechnen und die Merkle-Wurzel dieser erweiterten Daten als "Polynom-Commitment" verwenden

Ein Schlüsselaspekt der Geschichte ist, dass SNARKs auf elliptischen Kurven zuerst weit verbreitet verwendet wurden: Es dauerte bis etwa 2018, bis STARKs effizient genug wurden, um sie zu verwenden, dank FRI, und zu diesem Zeitpunkt lief Zcash bereits seit über einem Jahr. SNARKs auf elliptischen Kurven haben eine wichtige Einschränkung: Wenn Sie SNARKs auf elliptischen Kurven verwenden möchten, muss die Arithmetik in diesen Gleichungen mit ganzen Zahlen modulo der Anzahl der Punkte auf der elliptischen Kurve durchgeführt werden. Dies ist eine große Zahl, normalerweise in der Nähe von 2256: zum Beispiel für die bn128-Kurve sind es 21888242871839275222246405745257275088548364400416034343698204186575808495617. Aber die tatsächliche Berechnung verwendet kleine Zahlen: Wenn Sie über ein "echtes" Programm in Ihrer bevorzugten Sprache nachdenken, handelt es sich bei den meisten Elementen um Zähler, Indizes in Schleifen, Positionen im Programm, einzelne Bits, die Wahr oder Falsch repräsentieren, und andere Dinge, die fast immer nur wenige Ziffern lang sind.

Auch wenn Ihre „ursprünglichen“ Daten aus „kleinen“ Zahlen bestehen, erfordert der Nachweisprozess das Berechnen von Quotienten, Erweiterungen, zufälligen linearen Kombinationen und anderen Transformationen der Daten, die zu einer gleich großen oder größeren Anzahl von Objekten führen, die im Durchschnitt so groß sind wie die volle Größe Ihres Feldes. Dies führt zu einer Schlüsseleffizienz: Um eine Berechnung über n kleine Werte nachzuweisen, müssen Sie sogar noch mehr Berechnungen über n viel größere Werte durchführen. Zuerst übernahmen STARKs die Gewohnheit, 256-Bit-Felder von SNARKs zu verwenden, und litten daher unter derselben Ineffizienz.

Eine Reed-Solomon-Erweiterung einiger Polynom-Auswertungen. Obwohl die ursprünglichen Werte klein sind, explodieren alle zusätzlichen Werte auf die volle Größe des Feldes (in diesem Fall 2 hoch 31 -1).

Im Jahr 2022 wurde Plonky2 veröffentlicht. Die Hauptinnovation von Plonky2 bestand darin, Arithmetik modulo einer kleineren Primzahl durchzuführen: 2⁶⁴−2³²+1=18446744069414584321. Jetzt kann jede Addition oder Multiplikation immer in nur wenigen Anweisungen auf einer CPU durchgeführt werden, und das Hashen aller Daten zusammen ist 4x schneller als zuvor. Aber das hat einen Haken: Dieser Ansatz ist nur STARK. Wenn Sie versuchen, einen SNARK zu verwenden, mit einer elliptischen Kurve von so geringer Größe, wird die elliptische Kurve unsicher.

Um weiterhin sicher zu sein, musste auch Plonky2 Erweiterungsfelder einführen. Eine Schlüsseltechnik beim Überprüfen von arithmetischen Gleichungen ist das "Abtasten an einem zufälligen Punkt": Wenn Sie überprüfen möchten, ob 𝐻(𝑥)∗𝑍(𝑥) tatsächlich gleich 𝐹(𝑥+2)−𝐹(𝑥+1)−𝐹(𝑥) ist, können Sie einen zufälligen Koordinatenpunkt 𝑟 auswählen, Beweise für die Öffnung von polynomiale Verpflichtungen vorlegen, die beweisen, dass 𝐻(𝑟), 𝑍(𝑟), 𝐹(𝑟), 𝐹(𝑟+1) und 𝐹(𝑟+2), und dann tatsächlich überprüfen, ob 𝐻(𝑟)∗𝑍(𝑟) gleich 𝐹(𝑟+2)−𝐹(𝑟+1)−𝐹(𝑟) ist. Wenn der Angreifer den Koordinatenpunkt im Voraus erraten kann, kann der Angreifer das Beweissystem täuschen - daher muss es zufällig sein. Das bedeutet aber auch, dass der Koordinatenpunkt aus einer hinreichend großen Menge ausgewählt werden muss, damit der Angreifer ihn nicht durch Zufall erraten kann. Wenn das Modulus nahe bei 2 liegt²⁵⁶, das ist offensichtlich der Fall. Aber mit einem Modul von 2⁶⁴−2³²+1, wir sind noch nicht ganz da, und wenn wir auf 2 fallen³¹−1, es ist definitiv nicht der Fall. Versuchen, einen Nachweis zweimal Milliarden Mal zu fälschen, bis man Glück hat, liegt absolut im Bereich der Fähigkeiten eines Angreifers.

Um dies zu stoppen, entnehmen wir 𝑟 aus einem Erweiterungsfeld. Zum Beispiel können Sie 𝑦 definieren, wo 𝑦³=5, und nehmen Kombinationen von 1, 𝑦 und 𝑦². Dies erhöht die Gesamtzahl der Koordinaten wieder auf ungefähr 2⁹³Der Großteil der Polynome, die vom Beweiser berechnet werden, gehen nicht in dieses Erweiterungsfeld; sie verwenden einfach Ganzzahlen modulo 2.³¹−1, und so erhalten Sie immer noch alle Effizienzen aus der Verwendung des kleinen Feldes. Aber die zufällige Punktkontrolle und die FRI-Berechnung tauchen in dieses größere Feld ein, um die erforderliche Sicherheit zu gewährleisten.

Von kleinen Primzahlen bis Binär

Computer führen Arithmetik aus, indem sie größere Zahlen als Sequenzen von Nullen und Einsen darstellen und "Schaltkreise" auf der Grundlage dieser Bits aufbauen, um Dinge wie Addition und Multiplikation zu berechnen. Computer sind besonders optimiert für die Berechnung mit 16-Bit-, 32-Bit- und 64-Bit-Integern. Module wie 2⁶⁴−2³²+1 und 2³¹−1 werden nicht nur ausgewählt, weil sie innerhalb dieser Grenzen passen, sondern auch, weil sie gut mit diesen Grenzen übereinstimmen: Sie können Multiplikation modulo 2 durchführen⁶⁴−2³²+1 durch regelmäßige 32-Bit-Multiplikation, Verschieben und Bitweise Kopieren der Ausgaben an einigen Stellen; in diesem Artikel werden einige der Tricks gut erklärt.

Was jedoch noch besser wäre, ist die direkte Berechnung im Binärsystem. Was, wenn die Addition einfach XOR sein könnte, ohne sich um das „Tragen“ des Überlaufs von der Addition von 1 + 1 in einer Bit-Position zur nächsten kümmern zu müssen? Was, wenn die Multiplikation auf ähnliche Weise parallelisierbarer sein könnte? Und all diese Vorteile würden noch oben drauf kommen, wenn man in der Lage wäre, Wahr/Falsch-Werte mit nur einem Bit darzustellen.

Die Erfassung dieser Vorteile der direkten Durchführung binärer Berechnungen ist genau das, was Binius zu tun versucht. Eine Tabelle aus der zkSummit-Präsentation des Binius-Teams zeigt die Effizienzgewinne:

Trotz ungefähr gleicher "Größe" benötigt eine 32-Bit-Binärfeldoperation 5-mal weniger Rechenressourcen als eine Operation über das 31-Bit-Mersenne-Feld.

Von univariaten Polynomen zu Hyperwürfeln

Angenommen, wir sind von diesem Argument überzeugt und möchten alles über Bits (Nullen und Einsen) machen. Wie verpflichten wir uns tatsächlich zu einem Polynom, das eine Milliarde Bits darstellt?

Hier stehen wir vor zwei praktischen Problemen:

1. Damit ein Polynom eine Vielzahl von Werten darstellen kann, müssen diese Werte bei der Auswertung des Polynoms zugänglich sein: In unserem obigen Fibonacci-Beispiel, 𝐹(0), 𝐹(1) … 𝐹(100), und bei einer größeren Berechnung würden die Indizes in die Millionen gehen. Und das verwendete Feld muss Zahlen bis zu dieser Größe enthalten.

2. Etwas über einen Wert zu beweisen, zu dem wir uns in einem Merkle-Baum verpflichten (wie es alle STARKs tun), erfordert das Reed-Solomon-Codieren: das Erweitern von 𝑛 Werten auf z. B. 8𝑛 Werte und die Verwendung der Redundanz, um zu verhindern, dass ein bösartiger Beweiser betrügt, indem er einen Wert in der Mitte der Berechnung fälscht. Dies erfordert auch ein groß genugens Feld: Um eine Million Werte auf 8 Millionen zu erweitern, benötigen Sie 8 Millionen verschiedene Punkte, an denen das Polynom bewertet werden soll.

Eine Schlüsselidee in Binius ist es, diese beiden Probleme getrennt voneinander zu lösen, und zwar durch die Darstellung derselben Daten auf zwei verschiedene Arten. Erstens, das Polynom selbst. Auf elliptischen Kurven basierende SNARKs, STARKs aus dem Jahr 2019, Plonky2 und andere Systeme befassen sich im Allgemeinen mit Polynomen über einer Variablen: F(x). Binius hingegen lässt sich vom Spartan-Protokoll inspirieren und arbeitet mit multivariaten Polynomen: F(x1,x2... xk). Tatsächlich stellen wir die gesamte Rechenspur auf dem "Hyperwürfel" von Auswertungen dar, wobei jedes xi entweder 0 oder 1 ist. Wenn wir zum Beispiel eine Folge von Fibonacci-Zahlen darstellen wollten und immer noch ein Feld verwenden, das groß genug ist, um sie darzustellen, könnten wir uns die ersten sechzehn von ihnen in etwa so vorstellen:

Das heißt, 𝐹(0,0,0,0) wäre 1, 𝐹(1,0,0,0) wäre auch 1, 𝐹(0,1,0,0) wäre 2 usw., bis wir zu 𝐹(1,1,1,1)=987 gelangen. Angesichts eines solchen Hyperwürfels von Auswertungen gibt es genau ein multilineares (Grad-1 in jeder Variablen) Polynom, das diese Auswertungen produziert. Daher können wir diesen Satz von Auswertungen als das Polynom betrachten; wir müssen die Koeffizienten nie tatsächlich berechnen.

Dieses Beispiel dient natürlich nur zur Veranschaulichung: In der Praxis besteht der eigentliche Sinn darin, zu einem Hypercube zu gehen, um mit einzelnen Bits arbeiten zu können. Der „Binius-native“ Weg, Fibonacci-Zahlen zu zählen, wäre die Verwendung eines höherdimensionalen Würfels, wobei jede Gruppe von z. B. 16 Bits zur Speicherung einer Zahl verwendet wird. Dies erfordert etwas Geschick, um die Ganzzahlarithmetik über den Bits zu implementieren, aber mit Binius ist es nicht allzu schwierig.

Nun kommen wir zur Streichungscodierung. Die Art und Weise, wie STARKs funktionieren, ist: Sie nehmen 𝑛 Werte, erweitern sie nach Reed-Solomon auf eine größere Anzahl von Werten (oft 8𝑛, normalerweise zwischen 2𝑛 und 32𝑛) und wählen dann zufällig einige Merkle-Äste aus der Erweiterung aus und führen eine Art Überprüfung an ihnen durch. Ein Hypercube hat eine Länge von 2 in jeder Dimension. Daher ist es nicht praktisch, ihn direkt zu erweitern: Es gibt nicht genügend „Platz“, um Merkle-Äste aus 16 Werten auszuwählen. Was machen wir also stattdessen? Wir geben vor, der Hypercube sei ein Quadrat!

Einfacher Binius - ein Beispiel

Siehe hierfür eine Python-Implementierung dieses Protokolls.

Lassen Sie uns ein Beispiel durchgehen, wobei wir zur Vereinfachung reguläre Ganzzahlen als unser Feld verwenden (in einer realen Implementierung handelt es sich hierbei um binäre Feldelemente). Zuerst nehmen wir den Hyperwürfel, zu dem wir uns verpflichten möchten, und kodieren ihn als Quadrat:

Jetzt erweitern wir Reed-Solomon das Quadrat. Das heißt, wir behandeln jede Zeile als einen Polynom vom Grad 3, ausgewertet bei x = {0, 1, 2, 3}, und werten dasselbe Polynom bei x = {4, 5, 6, 7} aus:

Beachten Sie, dass die Zahlen schnell ansteigen! Deshalb verwenden wir in einer echten Implementierung immer einen endlichen Körper dafür, anstelle von regulären ganzen Zahlen: Wenn wir zum Beispiel Ganzzahlen modulo 11 verwenden würden, wäre die Erweiterung der ersten Zeile einfach [3, 10, 0, 6].

Wenn Sie mit der Erweiterung und Überprüfung der Zahlen hier herumspielen möchten, können Sie mein einfacher Reed-Solomon-Erweiterungscode hier.

Als nächstes behandeln wir diese Erweiterung als Spalten und erstellen einen Merkle-Baum der Spalten. Die Wurzel des Merkle-Baums ist unser Engagement.

Nun, nehmen wir an, dass der Beweiser eine Auswertung dieses Polynoms an einem Punkt 𝑟={𝑟0,𝑟1,𝑟2,𝑟3} beweisen möchte. In Binius gibt es einen feinen Unterschied, der es etwas schwächer macht als andere polynomiale Engagement-Schemata: Der Beweiser sollte 𝑠 nicht kennen oder erraten können, bis sie sich zur Merkle-Wurzel bekannt haben (mit anderen Worten sollte 𝑟 ein pseudozufälliger Wert sein, der von der Merkle-Wurzel abhängt). Dies macht das Schema für die „Datenbankabfrage“ nutzlos (z. B. „ok, du hast mir die Merkle-Wurzel gegeben, jetzt beweise mir 𝑃(0,0,1,0)!“). Aber die tatsächlichen Zero-Knowledge-Beweisprotokolle, die wir im Allgemeinen verwenden, benötigen keine „Datenbankabfrage“; sie müssen einfach das Polynom an einem zufälligen Auswertungspunkt überprüfen. Daher ist diese Einschränkung für unsere Zwecke in Ordnung.

Angenommen, wir wählen 𝑟={1,2,3,4} (das Polynom wertet zu diesem Zeitpunkt auf −137 aus; Sie können es bestätigenmit diesem CodeJetzt kommen wir zum eigentlichen Beweisprozess. Wir teilen 𝑟 in zwei Teile auf: Der erste Teil {1,2} stellt eine lineare Kombination von Spalten innerhalb einer Zeile dar, und der zweite Teil {3,4} stellt eine lineare Kombination von Zeilen dar. Wir berechnen ein „Tensorprodukt“, sowohl für den Spaltenteil:

Und für den Teil der Reihe:

Was das bedeutet ist: eine Liste aller möglichen Produkte eines Werts aus jedem Satz. Im Zeilenfall erhalten wir:

[(1-r2)(1-r3), (1-r3), (1-r2)r3, r2*r3]

Verwenden Sie r={1,2,3,4} (also r2=3 und r3=4):

[(1-3)(1-4), 3(1-4),(1-3)4,34] = [6, -9 -8 -12]

Nun berechnen wir eine neue „Zeile“ 𝑡′, indem wir diese lineare Kombination der vorhandenen Zeilen bilden. Das heißt, wir nehmen:

Sie können sehen, was hier passiert, als eine partielle Auswertung. Wenn wir das vollständige Tensorprodukt ⨂𝑖=03(1−𝑟𝑖,𝑟𝑖) mit dem vollen Vektor aller Werte multiplizieren würden, würden Sie die Auswertung 𝑃(1,2,3,4)=−137 erhalten. Hier multiplizieren wir ein teilweises Tensorprodukt, das nur die Hälfte der Auswertungskoordinaten verwendet, und reduzieren ein Gitter von 𝑁 Werten auf eine Reihe von 𝑁 Werten. Wenn Sie diese Zeile jemand anderem geben, können sie das Tensorprodukt der anderen Hälfte der Auswertungskoordinaten verwenden, um den Rest der Berechnung abzuschließen.

Der Beweiser stellt dem Verifizierer diese neue Zeile, 𝑡′, sowie die Merkle-Beweise einiger zufällig ausgewählter Spalten zur Verfügung. Dies sind 𝑂(𝑁) Daten. In unserem illustrierenden Beispiel wird der Beweiser nur die letzte Spalte bereitstellen; im wirklichen Leben müsste der Beweiser jedoch einige Dutzend Spalten bereitstellen, um ausreichende Sicherheit zu gewährleisten.

Jetzt nutzen wir die Linearität der Reed-Solomon-Codes. Die Schlüsseleigenschaft, die wir nutzen, ist: Wenn wir eine lineare Kombination einer Reed-Solomon-Erweiterung durchführen, erhalten wir dasselbe Ergebnis wie bei einer Reed-Solomon-Erweiterung einer linearen Kombination. Diese Art von "Ordnungsunabhängigkeit" tritt oft auf, wenn Sie zwei Operationen haben, die beide linear sind.

Der Verifizierer tut genau dies. Sie berechnen die Erweiterung von 𝑡′, und sie berechnen die gleiche lineare Kombination von Spalten, die der Beweiser zuvor berechnet hat (aber nur für die vom Beweiser bereitgestellten Spalten), und überprüfen, ob diese beiden Verfahren die gleiche Antwort liefern.

In diesem Fall erweitern 𝑡′, und die Berechnung der gleichen linearen Kombination ([6,−9,−8,12]) der Spalte ergibt beide die gleiche Antwort: −10746. Dies beweist, dass der Merkle-Wurzel „im guten Glauben“ konstruiert wurde (oder zumindest „nah genug“), und es passt zu 𝑡′: mindestens die große Mehrheit der Spalten sind miteinander kompatibel und mit 𝑡′.

Aber der Überprüfer muss noch eine weitere Sache überprüfen: tatsächlich die Auswertung des Polynoms bei {𝑟0..𝑟3} überprüfen. Bisher hing keiner der Schritte des Überprüfers tatsächlich vom Wert ab, den der Beweiser behauptet hat. Hier ist also, wie wir diese Überprüfung durchführen. Wir nehmen das Tensorprodukt von dem, was wir als den "Spaltenanteil" des Auswertungspunktes bezeichnet haben:

In unserem Beispiel, wo r={1,2,3,4} ist, so dass die Hälfte der ausgewählten Spalte {1,2}) ist, entspricht dies:

Also nehmen wir nun diese lineare Kombination von 𝑡′:

Was genau dem Ergebnis entspricht, das Sie erhalten, wenn Sie das Polynom direkt auswerten.

Das obige ist ziemlich nahe an einer vollständigen Beschreibung des „einfachen“ Binius-Protokolls. Dies hat bereits einige interessante Vorteile: Zum Beispiel benötigen Sie aufgrund der Aufteilung der Daten in Zeilen und Spalten nur ein Feld von halber Größe. Aber dies kommt nicht annähernd an die vollen Vorteile der Durchführung von Berechnungen im Binärcode heran. Dafür benötigen wir das vollständige Binius-Protokoll. Aber zuerst wollen wir ein tieferes Verständnis von Binärfeldern bekommen.

Binärfeld

Das kleinste mögliche Feld ist die arithmetische Modulo-2, das so klein ist, dass wir seine Addition und Multiplikationstabellen aufschreiben können:

Wir können größere binäre Felder erstellen, indem wir Erweiterungen vornehmen: Wenn wir mit 𝐹2 (Restklassen modulo 2) beginnen und dann 𝑥 definieren, wo 𝑥2=𝑥+1, erhalten wir die folgende Addition und Multiplikationstabelle:

Es stellt sich heraus, dass wir das binäre Feld durch wiederholten Aufbau beliebig vergrößern können. Anders als bei komplexen Zahlen über den Reellen, wo Sie ein neues Element 𝑖 hinzufügen können, aber nicht mehr hinzufügen können (Quaternionen existieren, aber sie sind mathematisch seltsam, z. B. 𝑎𝑏≠𝑏𝑎), können Sie bei endlichen Feldern immer neue Erweiterungen hinzufügen. Speziell definieren wir die Elemente wie folgt:

Und so weiter. Dies wird oft als Turmkonstruktion bezeichnet, da jede aufeinanderfolgende Erweiterung als Hinzufügen einer neuen Schicht zu einem Turm angesehen werden kann. Dies ist nicht die einzige Möglichkeit, Binärfelder beliebiger Größe zu konstruieren, aber es hat einige einzigartige Vorteile, die Binius ausnutzt.

Wir können diese Zahlen als Liste von Bits darstellen, z.B. 1100101010001111. Das erste Bit repräsentiert Vielfache von 1, das zweite Bit repräsentiert Vielfache von 𝑥0, dann repräsentieren die folgenden Bits Vielfache von: 𝑥1, 𝑥1∗𝑥0, 𝑥2, 𝑥2∗𝑥0 usw. Diese Codierung ist schön, weil man sie zerlegen kann:

Dies ist eine relativ ungewöhnliche Notation, aber ich mag es, binäre Feldelemente als Ganzzahlen darzustellen, wobei die Bitdarstellung so erfolgt, dass die signifikanteren Bits rechts stehen. Das heißt, 1=1, 𝑥₀=01=2, 1+𝑥₀=11=3, 1+𝑥₀+𝑥₂=11001000=19 und so weiter. 1100101010001111 ist in dieser Darstellung 61779.

Die Addition in einem binären Feld ist einfach nur XOR (genauso wie die Subtraktion, übrigens); beachten Sie, dass dies bedeutet, dass x+x=0 für jedes x ist. Um zwei Elemente x*y zu multiplizieren, gibt es einen sehr einfachen rekursiven Algorithmus: Teilen Sie jede Zahl in der Mitte auf:

Dann teilen Sie die Multiplikation auf:

Das letzte Stück ist das einzige, das ein wenig knifflig ist, weil Sie die Reduktionsregel anwenden und 𝑅𝑥∗𝑅𝑦∗𝑥𝑘2 durch 𝑅𝑥∗𝑅𝑦∗(𝑥𝑘−1∗𝑥𝑘+1) ersetzen müssen. Es gibt effizientere Möglichkeiten zur Multiplikation, Analogien des Karatsuba-Algorithmus und der schnellen Fourier-Transformationen, aber ich überlasse es dem interessierten Leser, diese herauszufinden.

Die Division in binären Feldern erfolgt durch Kombination von Multiplikation und Inversion. Der „einfache, aber langsame“ Weg zur Inversion ist eine Anwendung des verallgemeinerten kleinen Satzes von Fermat. Es gibt auch einen komplizierteren, aber effizienteren Inversionsalgorithmus, den Sie finden können hierSie können verwenden der Code hierum selbst mit binärer Feldaddition, -multiplikation und -division herumzuspielen.

Links: Additionstabelle für vier-Bit-Binärfeldelemente (d. h. Elemente, die nur aus Kombinationen von 1, 𝑥 bestehen₀，𝑥₁und 𝑥₀𝑥₁).

Richtig: Multiplikationstabelle für vier Bit binäre Feld Elemente.

Das Schöne an dieser Art von binärem Feld ist, dass es einige der besten Teile von "normalen" ganzen Zahlen und modularer Arithmetik kombiniert. Wie normale ganze Zahlen sind binäre Feldelemente unbegrenzt: Sie können so weit expandieren, wie Sie möchten. Aber wie bei der modularen Arithmetik bleiben auch bei Operationen über Werte innerhalb einer bestimmten Größenbeschränkung alle Ihre Antworten innerhalb derselben Grenze. Wenn du z.B. aufeinanderfolgende Potenzen von 42 nimmst, erhältst du:

Nach 255 Schritten bist du wieder bei 42²⁵⁵ = 1. Genau wie positive ganze Zahlen und modulare Arithmetik folgen sie den üblichen mathematischen Gesetzen: ab=ba, a(b+c)=a b+a*c, es gibt sogar einige seltsame neue Gesetze.

Schließlich machen binäre Felder es einfach, Bits zu handhaben: wenn Sie Mathematik mit Zahlen machen, die 2 passen^kBits, dann passt auch Ihre gesamte Ausgabe in 2 k Bits. Dies vermeidet Peinlichkeiten. In Ethereum's EIP-4844 muss jeder „Block“ eines Blobs ein digitaler Modul 52435875175126190479447740508185965837690552500527637822603658699938581184513 sein, sodass das Codieren der Binärdaten das Wegwerfen von etwas Platz und zusätzliches Überprüfen erfordert, um sicherzustellen, dass jedes Element einen Wert speichert, der kleiner als 2 ist.²⁴⁸. Dies bedeutet auch, dass binäre Feldoperationen auf Computern - sowohl CPUs als auch theoretisch optimale FPGA- und ASIC-Designs - super schnell sind.

Was das alles bedeutet, ist, dass wir etwas Ähnliches wie die Reed-Solomon-Codierung, die wir oben gemacht haben, auf eine Weise machen können, die den „Explosion“ der ganzen Zahlen vollständig vermeidet, wie wir es in unserem Beispiel gesehen haben, und das auf eine sehr „explosive“ Weise. „Native“ Art und Weise, die Art von Berechnung, die Computer gut beherrschen. Das „Split“-Merkmal von binären Feldern - wie wir es tun 1100101010001111=11001010+10001111*x₃und dann nach unseren Bedürfnissen aufteilen ist auch entscheidend, um eine hohe Flexibilität zu erreichen.

Voller Binius

Siehe hierfür eine Python-Implementierung dieses Protokolls.

Nun können wir zu „Gate Binius“ übergehen, das „einfachen Binius“ anpasst, um (i) über binäre Felder zu arbeiten und (ii) es uns ermöglicht, uns zu einzelnen Bits zu verpflichten. Dieses Protokoll ist schwierig zu verstehen, weil es ständig zwischen verschiedenen Möglichkeiten hin und her wechselt, eine Matrix von Bits zu betrachten; es hat sicher länger gedauert, bis ich es verstanden habe, als es normalerweise dauert, bis ich ein kryptografisches Protokoll verstehe. Aber sobald man binäre Felder versteht, gibt es die gute Nachricht, dass Binius nicht auf „schwererer Mathematik“ beruht. Dies ist nicht wie elliptische Kurvenpaarungen, bei denen es tiefere und tiefere Kaninchenlöcher der algebraischen Geometrie gibt; hier reichen binäre Felder völlig aus.

Lassen Sie uns das vollständige Diagramm noch einmal betrachten:

Bis jetzt sollten Sie mit den meisten Komponenten vertraut sein. Die Idee, einen Hyperwürfel in ein Raster zu 'flachen', die Idee, eine Zeilenkombination und eine Spaltenkombination als Tensorprodukte des Auswertungspunktes zu berechnen, und die Idee, die Äquivalenz zwischen 'Reed-Solomon erweitern und dann die Zeilenkombination berechnen' und 'die Zeilenkombination berechnen und dann Reed-Solomon erweitern' zu überprüfen, waren alle in einfachem Binius.

Was gibt es Neues in „vollem Binius“? Im Grunde drei Dinge:

• Die einzelnen Werte im Hypercube und im Quadrat müssen Bits (0 oder 1) sein
• Der Erweiterungsvorgang erweitert Bits in mehr Bits, indem Bits in Spalten gruppiert und vorübergehend so getan werden, als ob sie größere Felderlemente wären
• Nach dem Zeilenzusammenführungsschritt gibt es einen elementweisen „In Bits zerlegen“-Schritt, der die Erweiterung wieder in Bits umwandelt

Wir werden beide nacheinander durchgehen. Zuerst das neue Erweiterungsverfahren. Ein Reed-Solomon-Code hat die grundlegende Einschränkung, dass wenn Sie 𝑛 Werte auf 𝑘∗𝑛 Werte erweitern, Sie in einem Feld arbeiten müssen, das 𝑘∗𝑛 verschiedene Werte hat, die Sie als Koordinaten verwenden können. Mit 𝐹₂ (auch bekannt als Bits) können Sie das nicht tun. Und deshalb machen wir das, was wir tun, ist, benachbarte 𝐹 "zu "packen"₂Elemente zusammen zu größeren Werten packen. Im Beispiel hier packen wir zwei Bits gleichzeitig in Elemente in {0,1,2,3}, da unsere Erweiterung nur vier Auswertungspunkte hat und das für uns ausreicht. In einem "echten" Beweis würden wir wahrscheinlich 16 Bits gleichzeitig zusammenpacken. Dann führen wir den Reed-Solomon-Code über diese gepackten Werte aus und packen sie wieder in Bits aus.

Nun, die Zeilenkombination. Um 'an einem zufälligen Punkt auswerten' kryptografisch sicher zu machen, müssen wir sicherstellen, dass dieser Punkt aus einem ziemlich großen Raum ausgewählt wird, der viel größer ist als der Hyperwürfel selbst. Daher sind die Punkte innerhalb des Hyperwürfels Bits, während die Auswertungen außerhalb des Hyperwürfels viel größer sein werden. In unserem obigen Beispiel ergibt die 'Zeilenkombination' letztendlich [11,4,6,1].

Dies stellt ein Problem dar: wir wissen, wie man Paare von Bits zu einem größeren Wert kombiniert und dann eine Reed-Solomon-Erweiterung darauf durchführt, aber wie macht man dasselbe mit Paaren von viel größeren Werten?

Der Trick bei Binius besteht darin, es bitweise zu tun: Wir betrachten die einzelnen Bits jedes Werts (z.B. für das, was wir als "11" bezeichnet haben, das ist [1,1,0,1]), und dann erweitern wir zeilenweise. Das heißt, wir führen das Erweiterungsverfahren auf der 1. Zeile jedes Elements durch, dann auf der 𝑥0-Zeile, dann auf der "𝑥"-Zeile.₁"Reihe, dann auf dem 𝑥₀∗𝑥₁Zeile und so weiter (nun ja, in unserem Spielzeugbeispiel hören wir dort auf, aber in einer realen Implementierung würden wir bis zu 128 Zeilen gehen (die letzte wäre x₆∗ …∗ 𝑥₀)).

Zusammenfassend:

• Wir nehmen die Bits im Hypercube und wandeln sie in ein Raster um
• Dann behandeln wir benachbarte Bitgruppen in jeder Zeile als größere Feldelemente und führen arithmetische Operationen auf ihnen aus, um die Zeilen mit Reed-Solomon zu erweitern.
• Dann nehmen wir eine Zeilenkombination jeder Bit-Spalte und erhalten eine (für Quadrate größer als 4x4 viel kleinere) Bit-Spalte für jede Zeile als Ausgabe
• Dann betrachten wir die Ausgabe als Matrix und behandeln die Bits wieder als Zeilen

Warum funktioniert das? In der "normalen" Mathematik hört die Fähigkeit, (oft) lineare Operationen in beliebiger Reihenfolge durchzuführen und das gleiche Ergebnis zu erzielen, auf zu funktionieren, wenn Sie anfangen, eine Zahl nach Ziffern aufzuteilen. Wenn ich zum Beispiel mit der Zahl 345 beginne und sie mit 8 multipliziere und dann mit 3 multipliziere, erhalte ich 8280, und wenn ich diese beiden Operationen umkehre, erhalte ich ebenfalls 8280. Wenn ich jedoch eine "Aufteilung nach Ziffern"-Operation zwischen den beiden Schritten einfüge, bricht es zusammen: Wenn Sie zuerst 8x und dann 3x durchführen, erhalten Sie:

Aber wenn Sie 3x machen und dann 8x machen, erhalten Sie:

Aber in einem mit einem Turmstruktur gebauten binären Feld funktioniert dieser Ansatz. Der Grund liegt in ihrer Trennbarkeit: Wenn Sie einen großen Wert mit einem kleinen Wert multiplizieren, bleibt das, was in jedem Segment passiert, in jedem Segment. Wenn wir 1100101010001111 mit 11 multiplizieren, ist dies dasselbe wie die erste Faktorisierung von 1100101010001111, was

Und dann jedes Komponente separat mit 11 multiplizieren.

Alles zusammenbringen

Im Allgemeinen arbeiten Nullwissensbeweissysteme, indem sie Aussagen über Polynome machen, die gleichzeitig Aussagen über die zugrunde liegenden Bewertungen darstellen: genauso wie wir es im Fibonacci-Beispiel gesehen haben, prüft 𝐹(𝑋+2)−𝐹(𝑋+1)−𝐹(𝑋)=𝑍(𝑋)∗𝐻(𝑋) gleichzeitig alle Schritte der Fibonacci-Berechnung. Wir überprüfen Aussagen über Polynome, indem wir Auswertungen an einem zufälligen Punkt nachweisen. Diese Überprüfung an einem zufälligen Punkt ersetzt die Überprüfung des gesamten Polynoms: Wenn die Polynomgleichung nicht übereinstimmt, ist die Wahrscheinlichkeit, dass sie an einer bestimmten zufälligen Koordinate übereinstimmt, winzig.

In der Praxis stammt eine wesentliche Quelle der Ineffizienz daher, dass in realen Programmen die meisten Zahlen, mit denen wir arbeiten, winzig sind: Indizes in Schleifen, Wahr/Falsch-Werte, Zähler und ähnliche Dinge. Aber wenn wir die Daten mittels Reed-Solomon-Codierung "erweitern", um ihnen die Redundanz zu geben, die für die Sicherheit von Merkle-Proof-Checks erforderlich ist, nehmen die meisten der "zusätzlichen" Werte letztendlich die volle Größe eines Feldes ein, auch wenn die originalen Werte klein sind.

Um dieses Problem zu umgehen, möchten wir das Feld so klein wie möglich machen. Plonky2 hat uns von 256-Bit-Zahlen auf 64-Bit-Zahlen heruntergebracht, und dann ging Plonky3 weiter auf 31 Bits. Aber auch das ist noch nicht optimal. Mit binären Feldern können wir über einzelne Bits arbeiten. Dies macht die Kodierung "dicht": Wenn Ihre tatsächlichen zugrunde liegenden Daten n Bits haben, dann wird Ihre Kodierung n Bits haben, und die Erweiterung wird 8 * n Bits haben, ohne zusätzlichen Overhead.

Lassen Sie uns das Diagramm ein drittes Mal betrachten:

In Binius, verpflichten wir uns zu einem multilinenaren Polynom: einem Hyperwürfel 𝑃(x₀,x₁,…x_k) , wobei die einzelnen Auswertungen 𝑃(0,0…0) , 𝑃(0,0…1) bis 𝑃(1,1,…1) die Daten enthalten, die uns interessieren. Um eine Auswertung an einem Punkt zu beweisen, „re-interpretieren“ wir die gleichen Daten als Quadrat. Dann erweitern wir jede Zeile, indem wir Reed-Solomon-Codierung über Gruppen von Bits verwenden, um den Daten die Redundanz zu geben, die für sichere zufällige Merkle-Zweigabfragen erforderlich ist. Wir berechnen dann eine zufällige lineare Kombination von Zeilen, wobei die Koeffizienten so konzipiert sind, dass die neue kombinierte Zeile tatsächlich die Auswertung enthält, die uns interessiert. Sowohl diese neu erstellte Zeile (die als 128 Zeilen von Bits neu interpretiert wird) als auch einige zufällig ausgewählte Spalten mit Merkle-Zweigen werden an den Prüfer übergeben.

Der Überprüfer führt dann eine „Reihenkombination der Erweiterung“ (oder genauer gesagt, einige Spalten der Erweiterung) und eine „Erweiterung der Reihenkombination“ durch und überprüft, ob die beiden übereinstimmen. Anschließend berechnen sie eine Spaltenkombination und überprüfen, ob der Wert zurückgegeben wird, den der Beweiser angibt. Und da ist unser Beweissystem (oder genauer gesagt, das polynomiale Commitment-Schema, das der Schlüsselbaustein eines Beweissystems ist).

Was haben wir nicht behandelt?

• Effiziente Algorithmen zur Erweiterung der Zeilen, die erforderlich sind, um tatsächlich die Rechenleistung des Überprüfers zu verbessern. Wir verwenden schnelle Fourier-Transformationen über binären Feldern, beschriebenhier (obwohl die genaue Implementierung anders sein wird, da dieser Beitrag eine weniger effiziente Konstruktion verwendet, die nicht auf rekursiver Erweiterung basiert).
• Arithmetisierung. Eindimensionale Polynome sind praktisch, weil man Dinge wie F(X+2)-F(X+1)-F(X) = Z(X)*H(X) machen kann, um benachbarte Schritte in der Berechnung zu verknüpfen. In einem Hyperwürfel ist "der nächste Schritt" weit weniger interpretierbar als "X+1". Man könnte X+k, Potenzen von k, aber dieses Sprungverhalten würde viele der wesentlichen Vorteile von Binius opfern. Die Lösung wird präsentiert im Binius Papier(Siehe Abschnitt 4.3), aber dies ist an sich ein tiefes Kaninchenloch.
• Wie man tatsächlich sicher spezifische Wertprüfungen durchführt. Das Fibonacci-Beispiel erfordert die Überprüfung der Schlüsselgrenzbedingungen: F(0)=F(1)=1 und des Werts von F(100). Aber mit "rohem" Binius ist es unsicher, an vorbekannten Auswertungspunkten zu überprüfen. Es gibt ziemlich einfache Möglichkeiten, eine bekannte Auswertungsprüfung in eine unbekannte Auswertungsprüfung umzuwandeln, unter Verwendung dessen, was als Summenprüfungsprotokolle bezeichnet werden; aber wir sind hier nicht darauf eingegangen.
• Nachschlageprotokolle, eine weitere Technologie, die in letzter Zeit vermehrt verwendet wird, um ultraeffiziente Beweissysteme zu erstellen. Binius kann für viele Anwendungen mit Nachschlageprotokollen kombiniert werden.
• Überschreitung der Quadratwurzel-Verifikationszeit. Die Quadratwurzel ist teuer: Ein Beweis von Bits ist etwa 11 MB lang. Sie können dies beheben, indem Sie ein anderes Beweissystem verwenden, um einen "Beweis eines Binius-Beweises" zu erstellen und so sowohl die Effizienz von Binius beim Beweisen der Hauptaussage als auch eine geringe Beweisgröße zu erzielen. Eine weitere Option ist das viel kompliziertere FRI-Binius-Protokoll, das einen polylogarithmischen Beweis erzeugt (wie das reguläre FRI).
• Wie Binius beeinflusst, was als „SNARK-freundlich“ gilt. Die grundlegende Zusammenfassung lautet, dass Sie bei Verwendung von Binius nicht mehr viel Aufmerksamkeit darauf richten müssen, die Berechnung „arithmetikfreundlich“ zu gestalten: „reguläre“ Hashes sind nicht mehr effizienter als traditionelle arithmetische Hashes, Multiplikation modulo oder modulo ist im Vergleich zur Multiplikation modulo nicht mehr ein großes Problem usw. Aber dies ist ein komplexes Thema; es ändert sich vieles, wenn alles in binärer Form erfolgt.

Ich erwarte in den kommenden Monaten viele weitere Verbesserungen in den auf dem Binärfeld basierenden Beweistechniken.

Haftungsausschluss：

1. Dieser Artikel ist abgedruckt von [Panews]. Weiterleiten des Originaltitels 'Vitalik erklärt Binius: Ein effizientes Beweissystem basierend auf binären Feldern'. Alle Urheberrechte liegen beim Originalautor [GateVitalik Buterin*]. Wenn es Einwände gegen diesen Nachdruck gibt, wenden Sie sich bitte an die Gate LearnTeam, und sie werden es schnell erledigen.
2. Haftungsausschluss: Die Ansichten und Meinungen, die in diesem Artikel zum Ausdruck gebracht werden, 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, Verteilen oder Plagiieren der übersetzten Artikel untersagt.