Messen der SNARK-Leistung: Frontends, Backends und die Zukunft

Ein SNARK (Succinct Non-interactive Arguments of Knowledge) ist ein wichtiges kryptografisches Primitiv, das Anwendungen für Blockchain-Skalierbarkeit (z. B. L2-Rollups) und Datenschutz findet. SNARKs lassen jemanden einem nicht vertrauensvollen Verifizierer beweisen V (z. B. die Ethereum-Blockchain), dass sie einige Daten kennen (z. B. einen Stapel gültiger Transaktionen). Ein naiver Weg, dies zu beweisen, wäre, die Daten an zu senden V, der die Gültigkeit dann direkt überprüfen kann. Ein SNARK erreicht das gleiche, aber zu besseren Kosten V. Insbesondere sollte ein SNARK-Beweis kürzer sein als der naive Beweis, der die Daten selbst enthält. (Weitere Einzelheiten finden Sie im Entwurf meines Lehrbuchs, Beweise, Argumente und Zero Knowledge. Eine Einführung in SNARKs finden Sie bei Sarah Meicklejohn presentation bei der a16z crypto Sommerforschungsreihe.)

Die Verifizierungskosten für SNARKs können variieren, sind aber allgemein bekannt und oft recht gut. Zum Beispiel, PlönK Proofs kosten ca 290,000 Gas auf Ethereum zu überprüfen, während die Beweise von StarkWare etwa 5 Millionen Gas kosten. SNARKs sind möglicherweise in verschiedenen Umgebungen auch außerhalb von Blockchains anwendbar – zum Beispiel, um die Verwendung von schnell, aber nicht vertrauenswürdig zu ermöglichen Server und Hardware. 

Da die SNARK-Verifizierung jedoch in der Regel billig ist, sind die Hauptdeterminanten für die Anwendbarkeit die Kosten des SNARK-Beweisers P. In diesem Beitrag erkläre ich, wie man diese Kosten schätzt, um festzustellen, wann es sinnvoll ist, SNARKs zu verwenden, und wie sich SNARKs in Zukunft verbessern könnten. Es ist erwähnenswert, dass dies ein sich schnell bewegender Bereich ist und mehrere der in diesem Beitrag besprochenen Projekte ihre Leistung aktiv verbessern.

Aber zuerst: Wie SNARKs eingesetzt werden

Bei der SNARK-Bereitstellung schreibt ein Entwickler normalerweise ein Computerprogramm ψ die die Daten als Eingabe nimmt w dass der Prüfer zu wissen behauptet (w steht für Zeuge) und prüft das w ist gültig. Bei Rollups prüft das Programm beispielsweise, ob alle Transaktionen eingegangen sind w sind digital signiert, lassen keinen Kontostand unter Null sinken und so weiter. Das Programm ψ wird dann durch a geführt SNARK-Frontend das es in ein Format kompiliert, das für die Anwendung der SNARK-Technologie zugänglicher ist. Dieses SNARK-freundliche Format heißt an Zwischendarstellung (GEHEN). 

Typischerweise ist das IR eine Art Schaltungserfüllbarkeitsinstanz, die äquivalent zu ist ψ. Das bedeutet, dass die Schaltung C nimmt als Eingabe die Daten w, sowie einige zusätzliche Eingaben, die normalerweise als „nicht deterministische Ratschläge“ bezeichnet werden, und Läufe ψ on w. Die Beratungseingaben dienen als Hilfestellung C Lauf ψ, unter Beibehaltung C klein. Zum Beispiel jedes Mal ψ dividiert zwei Zahlen x und y, der Quotient q und Rest r kann als Beratung zur Verfügung gestellt werden C und C kann das einfach nachprüfen x = qy + r. Diese Überprüfung ist weniger teuer als die Herstellung C Führen Sie einen Divisionsalgorithmus zur Berechnung aus q und r von Grund auf neu.

Schließlich wird ein SNARK für die Schaltungserfüllbarkeit angewendet C. Dies nennt man das SNARK-Backend. Für eine Handvoll stark strukturierter Probleme wie z Matrix-Multiplikation, Windungen und mehrere Grafikprobleme, gibt es bekannte SNARKs, die dieses Frontend/Backend-Paradigma vermeiden und dadurch einen wesentlich schnelleren Beweis erreichen. Der Schwerpunkt dieses Beitrags liegt jedoch auf Allzweck-SNARKs.

Wie wir sehen werden, wachsen die Prover-Kosten des SNARK-Backends mit C's Größe. Halten C klein kann eine Herausforderung sein, da Schaltungen ein extrem begrenztes Format zum Ausdrücken einer Berechnung sind. Sie bestehen aus Tore, verbunden über Drähte. Jedes Tor g wird mit einigen Werten gefüttert und wendet a an sehr einfache Funktion zu diesen Werten. Das Ergebnis wird dann über die ausgehenden Drähte in „nachgelagerte“ Tore eingespeist g.

SNARK-Skalierbarkeit: Wie lange dauert es wirklich?

Die Schlüsselfrage lautet: Wie viel mehr Zeit benötigt der SNARK-Prüfer im Vergleich zur einfachen erneuten Ausführung ψ auf die Daten? Die Antwort ist die Prüfaufwand des SNARK, relativ zu direkte Zeugenüberprüfung. Der letztere Ausdruck bezieht sich darauf, dass in dem naiven Beweis, in dem P sendet w zu V, V Schecks w's Gültigkeit durch Ausführung ψ darauf. 

Es ist hilfreich, den Prover-Overhead in „Frontend-Overhead“ und „Backend-Overhead“ aufzuteilen. Wenn die Schaltung ausgewertet wird C Tor für Tor ist F mal teurer als Laufen ψ, dann sagen wir, der Frontend-Overhead ist F. Wenn Sie den Back-End-Prover auf anwenden C is B mal teurer als bewerten C Gate-by-Gate, dann sagen wir, dass der Backend-Overhead ist B. Der gesamte Prover-Overhead ist der Produkt, F·B. Dieser multiplikative Overhead kann beträchtlich sein, selbst wenn F und B sind individuell bescheiden. 

In der Praxis, F und B können beide ungefähr 1000 oder größer sein. Dies bedeutet, dass der Gesamtaufwand für den Beweiser im Vergleich zur direkten Zeugenüberprüfung 1 Million bis 10 Millionen oder mehr betragen kann. Ein Programm, das nur eine Sekunde auf einem Laptop läuft, kann leicht zu einem SNARK-Prover führen, der mehrere zehn oder hundert Tage Rechenzeit benötigt (Single-Threaded). Glücklicherweise ist diese Arbeit typischerweise in unterschiedlichem Umfang parallelisierbar (je nach SNARK). 

Zusammenfassend lässt sich sagen, dass, wenn Sie heute einen SNARK in einer Anwendung verwenden möchten, eines von drei Dingen zutreffen muss:

1. Die direkte Zeugenüberprüfung dauert auf einem Laptop viel weniger als eine Sekunde.
2. Die direkte Zeugenüberprüfung eignet sich besonders für die Darstellung in einem Schaltkreis, sodass der Frontend-Overhead gering ist.
3. Sie sind bereit, tagelang auf die Fertigstellung des SNARK-Provers zu warten und/oder für riesige parallele Rechenressourcen zu bezahlen.

TDer Rest dieses Beitrags erklärt, woher Frontend- und Backend-Gemeinkosten kommen und wie ich sie für verschiedene SNARKs schätze. Wir wenden uns dann den Aussichten für Verbesserungen zu. 

Trennung von Frontends und Backends

Die vollständige Trennung von Frontends und Backends kann eine Herausforderung darstellen, da unterschiedliche Backends unterschiedliche Arten von Schaltkreisen unterstützen. Daher können sich Frontends je nach Backend unterscheiden, mit dem sie eine Schnittstelle erwarten.

SNARK-Backends unterstützen im Allgemeinen sogenannte arithmetische Schaltungen, was bedeutet, dass die Eingaben in die Schaltungen Elemente eines endlichen Felds sind und dass die Gatter der Schaltung die Addition und Multiplikation von zwei Feldelementen durchführen. Diese Schaltungen entsprechen grob geradlinigen Computerprogrammen (keine Verzweigungen, bedingten Anweisungen usw.), die algebraischer Natur sind – das heißt, ihr primitiver Datentyp sind Feldelemente. 

Die meisten Backends unterstützen tatsächlich eine Verallgemeinerung arithmetischer Schaltungen, die oft als Instanzen der Rang-1-Einschränkungserfüllung (R1CS) bezeichnet werden. Mit der bemerkenswerten Ausnahme von Wachstum16 und seinen Vorgängern können diese SNARKs auch so gestaltet werden, dass sie andere IRs unterstützen. Zum Beispiel verwendet StarkWare etwas namens Algebraic Intermediate Representation (AIR), das auch einem Begriff namens ähnlich ist PlonKische Arithmetik das von PlonK und anderen Backends unterstützt werden kann. Die Fähigkeit einiger Backends, allgemeinere IRs zu unterstützen, kann den Overhead von Frontends reduzieren, die diese IRs erzeugen. 

Backends unterscheiden sich auch in Bezug auf die endlichen Felder, die sie nativ unterstützen. Ich werde dies im nächsten Abschnitt weiter besprechen.

Verschiedene Ansätze für Frontends

Einige (sehr spezielle) Computerprogramme entsprechen natürlich arithmetischen Schaltungen. Ein Beispiel ist das Computerprogramm, das eine naive Multiplikation von Matrizen über einem Feld durchführt. Aber die meisten Computerprogramme sind weder geradlinig noch algebraisch. Sie umfassen oft bedingte Anweisungen, Operationen wie ganzzahlige Division oder Gleitkomma-Arithmetik, die natürlicherweise nicht der Finite-Feld-Arithmetik entsprechen, und mehr. In diesen Fällen ist der Frontend-Overhead erheblich. 

Ein beliebter Frontend-Ansatz besteht darin, Schaltkreise zu erstellen, die im Wesentlichen Schritt für Schritt eine einfache CPU ausführen, die auch als virtuelle Maschine (VM) bezeichnet wird. Frontend-Designer spezifizieren eine Reihe von „primitiven Operationen“ analog zu Montageanweisungen für echte Computerprozessoren. Entwickler, die das Frontend nutzen wollen, schreiben „Witness-Checking-Programme“ entweder direkt in der Assembler-Sprache oder in einer höheren Sprache wie Solidity und lassen ihre Programme automatisch in Assembler-Code kompilieren. 

Zum Beispiel die von StarkWare Kairo ist eine sehr begrenzte Assemblersprache, in der Assembleranweisungen ungefähr Addition und Multiplikation über ein endliches Feld, Funktionsaufrufe und Lese- und Schreibvorgänge in einen unveränderlichen (dh einmal beschreibbaren) Speicher zulassen. Die Cairo-VM ist eine von Neumann-Architektur, was bedeutet, dass die vom Frontend erzeugten Schaltkreise im Wesentlichen ein Cairo-Programm als öffentliche Eingabe verwenden und das Programm auf dem Zeugen „ausführen“. Die Cairo-Sprache ist Turing Complete – trotz ihres begrenzten Befehlssatzes kann sie mehr Standardarchitekturen simulieren, obwohl dies teuer sein kann. Das Cairo-Frontend sorgt dafür, dass Cairo-Programme ausgeführt werden T primitive Anweisungen in das, was ein „Grad-2 LUFT mit T Reihen und ungefähr 50 Säulen." Was genau das bedeutet ist für diesen Beitrag nicht wichtig, aber was die SNARK-Prüfer betrifft, entspricht dies Schaltungen mit zwischen 50 und 100 Gattern für jedes der T Schritte der Cairo-CPU. 

RISC Null verfolgt einen ähnlichen Ansatz wie Cairo, aber mit der virtuellen Maschine als sogenannter RISC-V-Architektur, eine Open-Source-Architektur mit einem reichhaltigen Software-Ökosystem, das immer beliebter wird. Als sehr einfacher Befehlssatz kann das Entwerfen eines effizienten SNARK-Frontends, das es unterstützt, relativ leicht zu handhaben sein (zumindest im Vergleich zu komplizierten Architekturen wie x86 oder ARM). Ab Mai RISC Zero dreht Programme Ausführung T primitive RISC-V-Anweisungen in Grad-5-AIRs mit 3T Zeilen und 160 Säulen. Dies entspricht Schaltungen mit mind 500 Gates pro Schritt der RISC-V-CPU. Weitere Verbesserungen sind in naher Zukunft zu erwarten.

Die verschiedenen zkEVM-Projekte (z. B. zkSync 2.0, Scroll, zkEVM von Polygon) nehmen die virtuelle Maschine als (duh) die virtuelle Ethereum-Maschine an. Der Prozess, jeden EVM-Befehl in ein äquivalentes „Gadget“ (dh eine optimierte Schaltung, die den Befehl implementiert) umzuwandeln, ist wesentlich aufwändiger als bei den einfacheren Cairo- und RISC-V-Architekturen. Aus diesem und anderen Gründen, einige der zkEVM-Projekte implementieren den EVM-Befehlssatz nicht direkt, sondern kompilieren Solidity-Programme auf hoher Ebene in andere Assemblersprachen, bevor sie diese in Schaltkreise umwandeln. Leistungsergebnisse aus diesen Projekten stehen noch aus.

„CPU-Emulator“-Projekte wie RISC-V und Cairo erzeugen einen einzigen Schaltkreis, der alle Programme in der zugehörigen Assemblersprache verarbeiten kann. Alternative Ansätze sind „ASIC-ähnlich“ und produzieren unterschiedliche Schaltungen für unterschiedliche Programme. Dieser ASIC-ähnliche Ansatz kann für einige Programme zu kleineren Schaltungen führen, insbesondere wenn die Assembler-Anweisung, die das Programm in jedem Zeitschritt ausführt, nicht von der Eingabe des Programms abhängt. Zum Beispiel kann es möglicherweise Frontend-Overhead vollständig für geradlinige Programme wie naive Matrizenmultiplikation vermeiden. Aber der ASIC-Ansatz scheint auch sehr begrenzt zu sein; Soweit ich weiß, ist nicht bekannt, wie man damit Schleifen ohne vorgegebene Iterationsgrenzen unterstützt. 

Die letzte Komponente des Frontend-Overheads ergibt sich aus der Tatsache, dass alle SNARKs Schaltungen verwenden, die über endliche Felder arbeiten. Die CPU auf Ihrem Laptop kann zwei ganze Zahlen mit einem einzigen Maschinenbefehl multiplizieren oder addieren. Wenn ein Frontend eine Schaltung über ein Feld mit ausreichend großer Charakteristik ausgibt, kann es diese Multiplikation oder Addition über die entsprechende Feldoperation im Wesentlichen simulieren. Die Implementierung der Feldoperation auf einer echten CPU erfordert jedoch normalerweise viele Maschinenanweisungen (obwohl einige moderne Prozessoren bestimmte Felder nativ unterstützen). 

Einige SNARK-Backends ermöglichen eine flexiblere Feldauswahl als andere. Zum Beispiel, wenn das Backend eine kryptografische Gruppe verwendet G, muss das Feld der Schaltung mit der Anzahl der Elemente übereinstimmen G, was einschränkend sein kann. Außerdem unterstützen nicht alle Felder praktische FFT-Algorithmen. 

Es gibt nur einen implementierten SNARK, Bremsung, das nativ Berechnungen über beliebige (ausreichend große) Felder unterstützt. Zusammen mit seiner Nachkommen, hat es die schnellste bekannte konkrete Beweisleistung, selbst über Feldern, die andere SNARKs unterstützen, aber seine Beweise sind derzeit zu groß für viele Blockchain-Anwendungen. Kürzliche Arbeit versucht, die Beweisgröße zu verbessern, aber der Beweiser ist asymptotisch langsamer und da zu sein scheinen Barrieren zur Praktikabilität.

Einige Projekte haben sich dafür entschieden, Felder mit besonders schneller Arithmetik zu bearbeiten. Zum Beispiel, Plonky2 und andere verwenden ein Feld der Eigenschaft 2⁶⁴ - 2³² + 1, weil Arithmetik in diesem Feld um ein Vielfaches schneller implementiert werden kann als in weniger strukturierten Feldern. Die Verwendung einer so kleinen Charakteristik kann jedoch zu Herausforderungen bei der effizienten Darstellung ganzzahliger Arithmetik über Feldoperationen führen (z. B. könnte das Multiplizieren zweier 32-Bit-Ganzzahlen ohne Vorzeichen zu einem Ergebnis führen, das größer als die Feldcharakteristik ist). 

 Aber egal was, damit alle gängigen SNARKs heute 128 Bit Sicherheit erreichen (ohne eine signifikante Erhöhung der Verifizierungskosten), müssen sie über ein Feld mit einer Größe von mehr als 2 arbeiten¹²⁸. Soweit ich das beurteilen kann, bedeutet dies, dass jede Feldoperation mindestens etwa zehn 64-Bit-Maschinenmultiplikationen und erheblich mehr Additionen und bitweise Operationen erfordern wird. Daher sollte man aufgrund der Notwendigkeit von Schaltungen, die über endliche Felder arbeiten, mindestens eine Größenordnung an Frontend-Overhead berücksichtigen. 

Zusammenfassend produzieren bestehende Frontends, die eine Abstraktion einer virtuellen Maschine verwenden, Schaltkreise mit 100x bis 1000x Gattern pro Schritt der virtuellen Maschine und möglicherweise mehr für kompliziertere virtuelle Maschinen. Darüber hinaus ist die Finite-Field-Arithmetik mindestens 10-mal langsamer als analoge Anweisungen auf modernen Prozessoren (mit möglichen Ausnahmen, wenn der Prozessor über eine integrierte Unterstützung für bestimmte Felder verfügt). Ein „ASIC-Frontend-Ansatz“ könnte einige dieser Overheads reduzieren, ist jedoch derzeit in der Art der Programme, die er unterstützen kann, begrenzt.

Was sind die Backend-Engpässe?

SNARKs für die Schaltungserfüllbarkeit werden typischerweise durch die Kombination eines informationstheoretisch sicheren Protokolls entwickelt, das als „Polynomischer IOP“ mit einem kryptografischen Protokoll namens „Polynomielles Commitment-Schema.“ Der konkrete Engpass für den Beweiser ist in den meisten Fällen das Polynom-Commitment-Schema. Insbesondere haben diese SNARKs den Beweiser kryptografisch auf ein oder mehrere Polynome festgelegt, deren Grad (mindestens) |C|, die Anzahl der Gatter in der Schaltung C. 

Der konkrete Engpass innerhalb des polynomialen Commitment-Schemas hängt wiederum von dem verwendeten Schema und der Schaltungsgröße ab. Aber es wird immer eine der folgenden drei Operationen sein: Berechnung von FFTs, Potenzierungen in einer kryptographischen Gruppe, oder Merkle-Hashing. Merkle-Hashing ist normalerweise nur dann ein Engpass, wenn die Schaltung klein ist, daher werden wir es nicht weiter diskutieren. 

Polynomische Verpflichtungen basierend auf diskretem Log

Bei polynomialen Bindungen basierend auf der Härte des Problems des diskreten Logarithmus in einer kryptographischen Gruppe G (KZG, Kugelsicherungen, Dory und Hyrax-Commit), muss der Beweiser a berechnen Pedersen-Vektorbindung zu den Koeffizienten des Polynoms. Dies beinhaltet eine Mehrfachexponentiation, deren Größe dem Grad des Polynoms entspricht. In SNARKs ist dieser Grad typischerweise die Größe |C| der Schaltungs C.

Naiv gemacht, eine mehrfache Potenzierung der Größe |C| erfordert etwa 1.5·|C|·Log |G| ≈ 400·|C| Gruppenoperationen, wo |G| bezeichnet die Anzahl der Elemente in der Gruppe G. Es gibt jedoch einen Ansatz namens Pippenger-Algorithmus, der dies um einen Faktor von ungefähr log reduzieren kann |C|. Für große Schaltungen (z. |C| ≥ 225), dieses Protokoll |C| Der Faktor kann konkret 25 oder mehr betragen, das heißt, für große Schaltungen erwarten wir, dass die Pedersen-Vektorbindung mit etwas über 10 berechenbar ist·|C| Gruppenoperationen. Jede Gruppenoperation wiederum ist tendenziell (als sehr grober Anhaltspunkt) etwa 10x langsamer als eine endliche Feldoperation. SNARKs, die diese Polynomverpflichtungen verwenden, sind genauso teuer P so um die 100·|C| Feldoperationen. 

Leider haben bestehende SNARKs zusätzlich zum obigen 100-fachen Faktor zusätzliche Gemeinkosten. Zum Beispiel:

• spartanisch's Beweiser, der die Hyrax-Polynomzusage verwendet, zu tun |C|^½ viele Multipotenzierungen jeder Größe |C|^½, wodurch die Beschleunigung von Pippengers Algorithmus um einen Faktor von ungefähr zwei abgeschwächt wird. 
• In Wachstum16, P muss über eine Pairing-freundliche Gruppe funktionieren, deren Operationen normalerweise mindestens 2x langsamer sind als Gruppen, die nicht Pairing-freundlich sind. P muss auch 3 Multipotenzierungen anstelle von 1 durchführen. Kombiniert führt dies zu einer zusätzlichen Verlangsamung um den Faktor 6 relativ zu 100·|C| Schätzung oben. 
• Marlin und PlönK erfordern auch Paarungen, und ihre Beweiser müssen sich auf erheblich mehr als 3 Polynome festlegen. 
• Für jeden SNARK, der verwendet Kugelsicherungen (z.B, Halo2, was ungefähr PlonK ist, aber mit Bulletproofs statt KZG-Polynomverpflichtungen), muss der Beweiser logarithmisch viele Mehrfachexponentiationen während der „Öffnungs“-Phase des Verpflichtungsschemas berechnen, und dies löscht weitgehend jede Pippenger-Beschleunigung. 

Zusammenfassend scheinen bekannte SNARKs, die Pedersen-Vektor-Commitments verwenden, einen Backend-Overhead von mindestens 200x und bis zu 1000x oder mehr zu haben. 

Andere Polynomverpflichtungen

Für SNARKs, die andere Polynomverpflichtungen verwenden (wie z Freitag und Ligero-Commit), besteht der Engpass darin, dass der Beweiser große FFTs durchführen muss. Zum Beispiel in den von Cairo produzierten Grad-2-AIRs (mit 51 Spalten und T Zeilen, eine pro Schritt der Cairo-CPU), führt der eingesetzte Beweiser von StarkWare mindestens 2 FFTs pro Spalte mit einer Länge dazwischen aus 16 ·T und 32 ·T. Die Konstanten 16 und 32 hängen von den von StarkWare festgelegten internen Parametern von FRI ab und können reduziert werden – jedoch auf Kosten erhöhter Verifizierungskosten. 

Optimistisch eine FFT der Länge 32·T dauert etwa 64·T·anmelden (32T) Feldmultiplikationen. Dies bedeutet, dass selbst für relativ kleine Werte von T (z.B, T ≥ 2²⁰) beträgt die Anzahl der Feldoperationen pro Spalte mindestens 64·25·T= 1600·T. Der Backend-Overhead scheint also mindestens in die Tausende zu gehen. Darüber hinaus ist es möglich, dass große FFTs noch mehr durch die Speicherbandbreite als durch Feldoperationen beeinträchtigt werden. 

In einigen Zusammenhängen kann der Backend-Overhead von SNARKs, die große FFTs durchführen, mit einer Technik namens Proof-Aggregation gemildert werden. Für Rollups würde dies das bedeuten P (der Rollup-Service) teilt einen großen Stapel von Transaktionen in beispielsweise 10 kleinere Stapel auf. Für jede Kleinserie i, P erzeugt einen SNARK-Proof πi der Gültigkeit der Charge. Aber P sendet diese Nachweise nicht an Ethereum, da dies zu einer fast 10-fachen Erhöhung der Gaskosten führen würde. Stattdessen wird der SNARK noch einmal angewendet, diesmal um einen Beweis zu erbringen π das feststellen P kennt π₁ ...,π₁₀. Das heißt, der Zeuge, dass P zu wissen beansprucht, sind die zehn Beweise π₁,…,π₁₀, und die direkte Zeugenprüfung wendet das SNARK-Verifizierungsverfahren auf jeden der Beweise an. Dieser einzige Beweis π wird auf Ethereum gebucht. 

Bei polynomialen Commitments wie FRI und Ligero-commit besteht eine starke Spannung zwischen P Zeit und V Kosten, wobei interne Parameter wie ein Knopf fungieren, der gegeneinander abwägen kann. Seit π₁ ,…,π₁₀ werden nicht an Ethereum gepostet, der Knopf kann also an diesen Beweisen dran sein sind groß und ihre Herstellung geht schneller. Nur in der endgültigen Anwendung des SNARK, um zu aggregieren π₁ ,…,π₁₀ in einen einzigen Beweis π, Muss das Commitment-Schema konfiguriert werden, um einen kleinen Nachweis zu gewährleisten. 

StarkWare plant die Bereitstellung von Proof-Aggregation unmittelbar bevorstehend. Dies steht auch im Fokus von Projekten wie z Plonky2.

Was sind die anderen Engpässe für die SNARK-Skalierbarkeit?

Dieser Beitrag hat sich auf Beweiser konzentriert Zeit, aber auch andere Nachweiskosten können Skalierbarkeitsengpässe sein. Beispielsweise muss der Beweiser für viele SNARK-Backends mehrere Feldelemente für jedes Gate in speichern C, und diese Platzkosten können enorm sein. Zum Beispiel ein Programm ψ Die Ausführung in einer Sekunde auf einem Laptop kann auf einem modernen Prozessor vielleicht eine Milliarde primitiver Operationen ausführen. Wie wir gesehen haben, sollte man im Allgemeinen damit rechnen C weit über 100 Gatter pro derartiger Operation zu erfordern. Das bedeutet 100 Milliarden Gates, was je nach SNARK mehrere zehn oder hundert Terabyte Speicherplatz bedeuten kann P. 

Ein weiteres Beispiel: Viele beliebte SNARKs (zB PlönK, Marlin, Wachstum16) erfordern eine komplizierte „Trusted Setup Ceremony“, um einen strukturierten „Proving Key“ zu generieren. die vom Prüfer gespeichert werden müssen. Soweit ich weiß, die größte derartige Zeremonie einen Prüfschlüssel generiert, der Schaltungen mit etwa 2 unterstützen kann²⁸≈250 Millionen Tore. Der Prüfschlüssel ist mehrere Dutzend Gigabyte groß. 

In Kontexten, in denen eine Proof-Aggregation möglich ist, können diese Engpässe wesentlich gemildert werden. 

Ausblick: Perspektiven für skalierbarere SNARKs

Sowohl Front-End- als auch Back-End-Gemeinkosten können drei Größenordnungen oder mehr betragen. Können wir davon ausgehen, dass diese in naher Zukunft erheblich zurückgehen werden? 

Ich denke, das werden wir – bis zu einem gewissen Punkt. Erstens, die schnellsten Back-Ends von heute (z. B. spartanisch und Bremsung, und andere SNARKs, die die kombinieren Summenprüfprotokoll mit Polynomverpflichtungen) haben große Beweise – typischerweise Quadratwurzel in der Größe des Schaltkreises –, sodass die Leute sie nicht wirklich verwenden. Ich gehe davon aus, dass die Proof-Größe und die Verifier-Zeit in naher Zukunft durch die Depth-One-Komposition mit Small-Proof-SNARKs deutlich reduziert werden. Ähnlich wie bei der Proof-Aggregation bedeutet dies, dass ein Prover zunächst einen SNARK-Proof generieren würde π mit dem „fast-prover, large-proof“ SNARK, aber nicht senden π zu V. Lieber, P würde einen Small-Proof SNARK verwenden, um einen Beweis zu erzeugen π' dass es weiß π, und senden π' zu V. Dies könnte die Backend-Overheads von SNARKs, die heute beliebt sind, um eine Größenordnung reduzieren. 

Zweitens kann Hardwarebeschleunigung helfen. Eine sehr grobe allgemeine Regel lautet, dass GPUs eine 10-fache Beschleunigung gegenüber CPUs und ASICs eine 10-fache Beschleunigung gegenüber GPUs kaufen können. Allerdings habe ich an dieser Front drei Bedenken. Erstens können große FFTs eher durch die Speicherbandbreite als durch Feldoperationen beeinträchtigt werden, sodass SNARKs, die solche FFTs durchführen, möglicherweise begrenzte Beschleunigungen durch spezialisierte Hardware erfahren. Zweitens, während sich dieser Beitrag auf den Polynom-Commitment-Engpass konzentrierte, erfordern viele SNARKs, dass der Beweiser andere Operationen durchführt, die nur geringfügig weniger kostspielig sind. Um also den Polynom-Commitment-Engpass zu durchbrechen (z. B. Beschleunigung von Mehrfachexponentiationen in auf diskreten Protokollen basierenden SNARKs) kann eine neue Engpassoperation hinterlassen, die nicht wesentlich besser ist als die alte. (Zum Beispiel haben SNARKs, einschließlich Groth16, Marlin und PlonK, zusätzlich zu Mehrfachexponentiationen auch den Beweiser, der FFTs durchführt.) Schließlich können sich die Felder und elliptischen Kurven, die zu den effizientesten SNARKs führen, noch einige Zeit weiterentwickeln, was zu Herausforderungen für die ASIC-basierte Nachweisbeschleunigung führen kann.

Auf der Frontend-Seite stellen wir möglicherweise zunehmend fest, dass der „CPU-Emulator“-Ansatz von Projekten wie Cairo, RISC Zero, zkEVMs und anderen tatsächlich recht gut (in Bezug auf die Leistung) mit der Komplexität der CPU-Befehlssätze skaliert. Genau das ist die Hoffnung verschiedener zkEVM-Projekte. Dies kann bedeuten, dass der Frontend-Overhead zwar drei Größenordnungen oder mehr beträgt, die Frontends es jedoch schaffen, VMs zu unterstützen, die zunehmend realen CPU-Architekturen entsprechen. Eine entgegenstehende Sorge ist, dass die Frontends kompliziert und schwer zu prüfen sein könnten, da sich handcodierte Gadgets vermehren, die immer kompliziertere Anweisungen implementieren. Formale Überprüfungsmethoden werden wahrscheinlich eine wichtige Rolle bei der Lösung dieses Problems spielen. 

Schließlich können wir zumindest in Blockchain-Anwendungen feststellen, dass die meisten intelligenten Verträge, die in freier Wildbahn erscheinen, hauptsächlich einfache, SNARK-freundliche Anweisungen verwenden. Dies kann in der Praxis niedrige Frontend-Overheads ermöglichen und gleichzeitig die Allgemeingültigkeit und verbesserte Entwicklererfahrung beibehalten, die mit der Unterstützung von Programmiersprachen auf hoher Ebene wie Solidity und umfangreichen Befehlssätzen, einschließlich denen des EVM, einhergeht. 

***

Justin Thaler is außerordentlicher Professor an der Georgetown University. Bevor er zu Georgetown kam, verbrachte er zwei Jahre als Research Scientist bei Yahoo Labs in New York, davor war er Research Fellow am Simons Institute for The Theory of Computing an der UC Berkeley. 

***

Danksagung: Ich bedanke mich bei Elena Burger für das Vorschlagen des Themas dieses Beitrags und an Arasu Arun, Josef Boneau und Sam Ragdale für aufschlussreiche Kommentare. Besonderer Dank gilt auch meinem Lektor, Tim Sullivan.

***

Die hier geäußerten Ansichten sind die der einzelnen zitierten Mitarbeiter von AH Capital Management, LLC („a16z“) und nicht die Ansichten von a16z oder seinen verbundenen Unternehmen. Bestimmte hierin enthaltene Informationen stammen aus Drittquellen, einschließlich von Portfoliounternehmen von Fonds, die von a16z verwaltet werden. Obwohl sie aus als zuverlässig erachteten Quellen stammen, hat a16z solche Informationen nicht unabhängig überprüft und gibt keine Zusicherungen über die dauerhafte Genauigkeit der Informationen oder ihre Angemessenheit für eine bestimmte Situation. Darüber hinaus kann dieser Inhalt Werbung von Drittanbietern enthalten; a16z hat solche Anzeigen nicht überprüft und unterstützt keine darin enthaltenen Werbeinhalte.

Dieser Inhalt wird nur zu Informationszwecken bereitgestellt und sollte nicht als Rechts-, Geschäfts-, Anlage- oder Steuerberatung angesehen werden. Sie sollten diesbezüglich Ihre eigenen Berater konsultieren. Verweise auf Wertpapiere oder digitale Vermögenswerte dienen nur der Veranschaulichung und stellen keine Anlageempfehlung oder ein Angebot zur Erbringung von Anlageberatungsdiensten dar. Darüber hinaus richtet sich dieser Inhalt nicht an Anleger oder potenzielle Anleger und ist nicht für die Verwendung durch diese bestimmt, und es darf unter keinen Umständen darauf vertraut werden, wenn eine Entscheidung getroffen wird, in einen von a16z verwalteten Fonds zu investieren. (Ein Angebot zur Investition in einen a16z-Fonds wird nur durch das Privatplatzierungsmemorandum, den Zeichnungsvertrag und andere relevante Unterlagen eines solchen Fonds abgegeben und sollte vollständig gelesen werden.) Alle erwähnten, erwähnten oder erwähnten Investitionen oder Portfoliounternehmen oder Portfoliounternehmen Die beschriebenen Investitionen sind nicht repräsentativ für alle Investitionen in von a16z verwaltete Vehikel, und es kann nicht garantiert werden, dass die Investitionen rentabel sind oder dass andere Investitionen in der Zukunft ähnliche Merkmale oder Ergebnisse aufweisen werden. Eine Liste der Investitionen von Fonds, die von Andreessen Horowitz verwaltet werden (mit Ausnahme von Investitionen, für die der Emittent a16z keine Genehmigung zur öffentlichen Offenlegung erteilt hat, sowie unangekündigte Investitionen in öffentlich gehandelte digitale Vermögenswerte) ist unter https://a16z.com/investments verfügbar /.

Die darin bereitgestellten Diagramme und Grafiken dienen ausschließlich zu Informationszwecken und sollten bei Anlageentscheidungen nicht als verlässlich angesehen werden. Die Wertentwicklung in der Vergangenheit ist kein Hinweis auf zukünftige Ergebnisse. Der Inhalt spricht nur zum angegebenen Datum. Alle Prognosen, Schätzungen, Prognosen, Ziele, Aussichten und/oder Meinungen, die in diesen Materialien geäußert werden, können ohne Vorankündigung geändert werden und können von den Meinungen anderer abweichen oder ihnen widersprechen. Weitere wichtige Informationen finden Sie unter https://a16z.com/disclosures.