SNARK-prestaties meten: frontends, backends en de toekomst

Een SNARK (Succinct Non-interactive Arguments of Knowledge) is een belangrijke cryptografische primitieve toepassing voor blockchain-schaalbaarheid (bijv. L2-rollups) en privacy. SNARK's laten iemand bewijzen aan een niet-vertrouwde verificateur V (bijvoorbeeld de Ethereum-blockchain) dat ze bepaalde gegevens kennen (bijvoorbeeld een reeks geldige transacties). Een naïeve manier om dit te bewijzen zou zijn om de gegevens te sturen naar: V, die dan direct de geldigheid ervan kan controleren. Een SNARK bereikt hetzelfde, maar met betere kosten om V. In het bijzonder moet een SNARK-bewijs korter zijn dan het naïeve bewijs dat de gegevens zelf bevat. (Voor meer details, zie het concept van mijn leerboek, Bewijzen, argumenten en nulkennis. Voor een inleiding tot SNARKs, zie Sarah Meicklejohn's presentatie bij de a16z crypto Zomeronderzoeksreeks.)

De verificatiekosten voor SNARK's kunnen variëren, maar zijn goed begrepen en vaak redelijk goed. Bijvoorbeeld, PlonK bewijzen kosten ongeveer 290,000 gas om te verifiëren op Ethereum, terwijl de bewijzen van StarkWare ongeveer 5 miljoen gas kosten. SNARK's zijn mogelijk toepasbaar in diverse omgevingen, zelfs buiten blockchains, waardoor bijvoorbeeld het gebruik van snelle maar niet-vertrouwde servers en hardware. 

Maar omdat SNARK-verificatie doorgaans goedkoop is, zijn de belangrijkste determinanten van toepasbaarheid de kosten van de SNARK-bewijzer P. In dit bericht leg ik uit hoe je deze kosten kunt inschatten om te bepalen wanneer het redelijk is om SNARK's te gebruiken en hoe SNARK's in de toekomst kunnen verbeteren. Het is vermeldenswaard dat dit een snel bewegende ruimte is en dat verschillende van de in dit bericht besproken projecten hun prestaties actief verbeteren.

Maar eerst: hoe SNARK's worden ingezet

In SNARK-implementatie schrijft een ontwikkelaar meestal een computerprogramma ψ dat neemt als invoer de gegevens w dat de bewijzer beweert te weten (w staat voor Getuige), en controleert dat w is geldig. In rollups controleert het programma bijvoorbeeld of alle transacties in w digitaal ondertekend zijn, er niet voor zorgen dat het saldo op de rekening onder nul daalt, enzovoort. Het programma ψ wordt dan gevoed door een SNARK-frontend die het compileert in een formaat dat beter geschikt is voor toepassing van SNARK-technologie. Dit SNARK-vriendelijke formaat heet an intermediaire representatie (GAAN). 

Meestal is de IR een soort circuit-tevredenheidsinstantie die gelijk is aan: . Dit betekent dat de schakeling C neemt als invoer de gegevens w, evenals enkele extra invoer die gewoonlijk 'niet-deterministisch advies' wordt genoemd, en loopt ψ on w. De adviesinvoer wordt gebruikt om te helpen C lopen ψ, met behoud van C klein. Bijvoorbeeld elke keer ψ verdeelt twee getallen x en y, het quotiënt q en rest r kan worden gegeven als advies aan C en C kan dat gewoon controleren x = qy + r. Deze controle is minder duur dan het maken C voer een delingsalgoritme uit om te berekenen q en r vanuit het niets.

Ten slotte wordt een SNARK voor circuittevredenheid toegepast op: C. Dit heet de SNARK-backend. Voor een handvol zeer gestructureerde problemen zoals: Matrix vermenigvuldiging, windingen en verschillende grafische problemen, bestaan ​​er bekende SNARK's die dit frontend/backend-paradigma vermijden en daardoor een veel snellere prover bereiken. Maar de focus van dit bericht ligt op SNARK's voor algemene doeleinden.

Zoals we zullen zien, groeien de bewijskosten van de SNARK-backend mee C's maat. houden C klein kan een uitdaging zijn, omdat circuits een extreem beperkt formaat zijn om een ​​berekening uit te drukken. Ze bestaan ​​uit: poorten, verbonden door draden. elke poort g krijgt enkele waarden en past a . toe zeer eenvoudige functie voor die waarden. Het resultaat wordt vervolgens ingevoerd in "stroomafwaartse" poorten via de draden die afkomstig zijn van g.

SNARK-schaalbaarheid: hoeveel tijd kost het echt?

De hamvraag is: hoeveel meer tijd kost de SNARK-bewijzer in vergelijking met gewoon opnieuw uitvoeren? ψ op de gegevens? Het antwoord is de bewijs overhead van de SNARK, ten opzichte van directe getuigenverificatie. De laatste uitdrukking verwijst naar het feit dat, in het naïeve bewijs waarin P verzendt w naar V, V cheques w's geldigheid door het uitvoeren van ψ op. 

Het is handig om de prover overhead op te splitsen in 'frontend overhead' en 'backend overhead'. Als u het circuit evalueert: C poort voor poort is F keer duurder dan hardlopen ψ, dan zeggen we dat de frontend overhead is F. Als u de backend-prover toepast op: C is B keer duurder dan evalueren C gate-by-gate, dan zeggen we dat de backend overhead is B. De totale proever overhead is de artikel, F·B. Deze multiplicatieve overhead kan aanzienlijk zijn, zelfs als: F en B zijn individueel bescheiden. 

In praktijk, F en B kunnen beide ongeveer 1000 of groter zijn. Dit betekent dat de totale overheadkosten ten opzichte van directe getuigencontrole 1 miljoen tot 10 miljoen of meer kunnen zijn. Een programma dat slechts één seconde op een laptop draait, kan er gemakkelijk toe leiden dat een SNARK-prover tientallen of honderden dagen rekentijd nodig heeft (single-threaded). Gelukkig is dit werk typisch parallelleerbaar in verschillende mate (afhankelijk van de SNARK). 

Samenvattend, als u vandaag een SNARK in een toepassing wilt gebruiken, moet een van de drie dingen waar zijn:

1. Directe getuigenverificatie duurt veel minder dan een seconde op een laptop.
2. Directe getuigencontrole is bijzonder geschikt voor weergave in een circuit, dus de frontend-overhead is klein.
3. U bent bereid dagen te wachten tot de SNARK-prover klaar is en/of te betalen voor enorme parallelle rekenbronnen.

TDe rest van dit bericht legt uit waar frontend- en backend-overheads vandaan komen en hoe ik ze schat voor verschillende SNARK's. Dan gaan we in op de vooruitzichten voor verbetering. 

Scheiding van frontends en backends

Het volledig scheiden van frontends van backends kan een uitdaging zijn omdat verschillende backends verschillende soorten circuits ondersteunen. Daarom kunnen frontends verschillen, afhankelijk van de backend waarmee ze verwachten te communiceren.

SNARK-backends ondersteunen over het algemeen zogenaamde rekenkundige circuits, wat betekent dat de ingangen naar de circuits elementen zijn van een eindig veld en dat de poorten van het circuit de optelling en vermenigvuldiging van twee veldelementen uitvoeren. Deze circuits komen ruwweg overeen met lineaire computerprogramma's (geen takken, voorwaardelijke uitspraken, enzovoort) die algebraïsch van aard zijn - dat wil zeggen dat hun primitieve gegevenstype veldelementen zijn. 

De meeste backends ondersteunen eigenlijk een generalisatie van rekenkundige circuits, vaak Rank-1 Constraint Satisfaction (R1CS) -instanties genoemd. Met de opmerkelijke uitzondering van Groth16 en zijn voorgangers, deze SNARK's kunnen ook worden gemaakt om andere IR's te ondersteunen. StarkWare gebruikt bijvoorbeeld iets dat Algebraic Intermediate Representation (AIR) wordt genoemd, wat ook lijkt op een begrip genaamd PlonKish rekenkunde die kunnen worden ondersteund door PlonK en andere backends. Het vermogen van sommige backends om algemenere IR's te ondersteunen, kan de overhead van frontends die deze IR's produceren, verminderen. 

Backends variëren ook in termen van de eindige velden die ze native ondersteunen. Ik zal dit verder bespreken in de volgende sectie.

Verschillende benaderingen van frontends

Sommige (heel bijzondere) computerprogramma's komen natuurlijk overeen met rekenkundige circuits. Een voorbeeld is het computerprogramma dat een naïeve vermenigvuldiging van matrices over een bepaald veld uitvoert. Maar de meeste computerprogramma's zijn niet lineair of algebraïsch. Het gaat vaak om voorwaardelijke uitspraken, bewerkingen zoals deling van gehele getallen of rekenkunde met drijvende komma die van nature niet overeenkomen met rekenkunde met eindige velden, en meer. In deze gevallen zal de frontend overhead aanzienlijk zijn. 

Een populaire frontend-aanpak is om circuits te produceren die in wezen stap voor stap een eenvoudige CPU uitvoeren, ook wel een virtuele machine (VM) genoemd. Frontend-ontwerpers specificeren een reeks "primitieve bewerkingen" analoog aan montage-instructies voor echte computerprocessors. Ontwikkelaars die de frontend willen gebruiken, zullen ofwel "witness-checking-programma's" rechtstreeks in de assembleertaal schrijven of anders in een taal op een hoger niveau, zoals Solidity, en hun programma's automatisch laten compileren tot assemblagecode. 

Bijvoorbeeld StarkWare's Cairo is een zeer beperkte assembleertaal waarin montage-instructies ruwweg optellen en vermenigvuldigen over een eindig veld, functieaanroepen en lezen en schrijven naar een onveranderlijk (dwz eenmalig schrijven) geheugen toestaan. De Cairo VM is een von Neumann-architectuur, wat betekent dat de circuits die door de frontend worden geproduceerd in wezen een Cairo-programma als publieke input nemen en het programma op de getuige "uitvoeren". De Cairo-taal is Turing Complete - ondanks de beperkte instructieset kan het meer standaardarchitecturen simuleren, hoewel dit duur kan zijn. De frontend van Caïro zet Caïro-programma's in uitvoering T primitieve instructies in wat een “graad-2 LUCHT met T rijen en over 50 kolommen.” Wat precies dit betekent is niet belangrijk voor deze post, maar voor zover het SNARK-provers betreft, komt dit overeen met circuits met tussen de 50 en 100 poorten voor elk van de T stappen van de Caïro-CPU. 

RISC nul heeft een vergelijkbare benadering als Cairo, maar met de virtuele machine als de zogenaamde RISC-V-architectuur, een open-sourcearchitectuur met een rijk software-ecosysteem dat steeds populairder wordt. Omdat het een zeer eenvoudige instructieset is, kan het ontwerpen van een efficiënte SNARK-frontend die dit ondersteunt relatief handelbaar zijn (tenminste in vergelijking met gecompliceerde architecturen zoals x86 of ARM). Vanaf mei is RISC Zero draait programma's uitvoeren T primitieve RISC-V instructies in graad-5 AIRs met 3T rijen en 160 kolommen. Dit komt overeen met circuits met ten minste 500 poorten per stap van de RISC-V CPU. In de nabije toekomst worden verdere verbeteringen verwacht.

De verschillende zkEVM-projecten (bijv. zkSync 2.0, Scroll, Polygon's zkEVM) nemen de virtuele machine als (duh) de Ethereum Virtual Machine. Het proces om elke EVM-instructie om te zetten in een equivalent "gadget" (dwz een geoptimaliseerd circuit dat de instructie implementeert) is aanzienlijk ingewikkelder dan voor de eenvoudigere Cairo- en RISC-V-architecturen. Om deze en andere redenen, enkele van de zkEVM-projecten implementeren de EVM-instructieset niet rechtstreeks, maar compileren eerder Solidity-programma's op hoog niveau in andere assembleertalen voordat ze deze in circuits veranderen. Prestatieresultaten van deze projecten zijn in afwachting.

"CPU-emulator"-projecten zoals RISC-V en Cairo produceren één circuit dat alle programma's in de bijbehorende assembleertaal aankan. Alternatieve benaderingen zijn "ASIC-achtig" en produceren verschillende circuits voor verschillende programma's. Deze ASIC-achtige benadering kan voor sommige programma's kleinere circuits opleveren, vooral wanneer de montage-instructie die het programma bij elke tijdstap uitvoert niet afhankelijk is van de invoer van het programma. Het kan bijvoorbeeld frontend-overhead mogelijk volledig vermijden voor lineaire programma's zoals naïeve matrixvermenigvuldiging. Maar de ASIC-aanpak lijkt ook zeer beperkt; voor zover ik weet, is het niet bekend hoe het te gebruiken om lussen te ondersteunen zonder vooraf bepaalde iteratiegrenzen. 

Het laatste onderdeel van frontend overhead komt van het feit dat alle SNARK's circuits gebruiken die over eindige velden werken. De CPU op uw laptop kan twee gehele getallen vermenigvuldigen of optellen met een enkele machine-instructie. Als een frontend een circuit uitvoert over een veld met voldoende karakteristieke eigenschappen, kan het in wezen die vermenigvuldiging of optelling simuleren via de overeenkomstige veldbewerking. Het implementeren van de veldbewerking op een echte CPU vereist echter meestal veel machine-instructies (hoewel sommige moderne processors native ondersteuning voor bepaalde velden hebben). 

Sommige SNARK-backends maken flexibelere veldkeuzes mogelijk dan andere. Als de backend bijvoorbeeld gebruik maakt van een cryptografische groep G, het veld van het circuit moet overeenkomen met het aantal elementen in G, wat beperkend kan zijn. Bovendien ondersteunen niet alle velden praktische FFT-algoritmen. 

Er is slechts één geïmplementeerde SNARK, Remmen, die native berekeningen ondersteunt over willekeurige (groot genoeg) velden. Samen met zijn afstammelingen, het heeft de snelst bekende concrete bewijsprestaties, zelfs over velden die andere SNARK's ondersteunen, maar de bewijzen zijn momenteel te groot voor veel blockchain-toepassingen. Recent werk probeert de bewijsgrootte te verbeteren, maar de bewijzer is asymptotisch langzamer en daar schijnt te zijn barrières naar de praktijk.

Sommige projecten hebben ervoor gekozen om over velden te werken met bijzonder snelle rekenkunde. Bijvoorbeeld, Plonky2 en anderen gebruiken een veld van kenmerk 2⁶⁴ - 2³² + 1 omdat rekenen in dit veld meerdere malen sneller kan worden geïmplementeerd dan in minder gestructureerde velden. Het gebruik van zo'n klein kenmerk kan echter leiden tot uitdagingen bij het efficiënt weergeven van gehele rekenkunde via veldbewerkingen (bijv. het vermenigvuldigen van twee 32-bits gehele getallen zonder teken kan een resultaat opleveren dat groter is dan het veldkenmerk). 

 Maar wat er ook gebeurt, om alle populaire SNARK's vandaag 128 bits beveiliging te laten bereiken (zonder een significante verhoging van de verificatiekosten), moeten ze werken over een veld groter dan 2¹²⁸. Voor zover ik weet, betekent dit dat voor elke veldbewerking ten minste ongeveer tien 64-bits machinevermenigvuldigingen nodig zijn, en aanzienlijk meer optellingen en bitsgewijze bewerkingen. Daarom moet men rekening houden met ten minste een orde van grootte frontend overhead vanwege de behoefte aan circuits die over eindige velden werken. 

Om samen te vatten, bestaande frontends die gebruik maken van een virtuele machine-abstractie, produceren circuits met 100x tot 1000x poorten per stap van de virtuele machine, en mogelijk meer voor meer gecompliceerde virtuele machines. Bovendien is rekenkunde met eindige velden minstens 10x langzamer dan analoge instructies op moderne processors (met mogelijke uitzonderingen als de processor ingebouwde ondersteuning heeft voor bepaalde velden). Een "ASIC frontend-benadering" kan sommige van deze overheadkosten verminderen, maar is momenteel beperkt in het soort programma's dat het kan ondersteunen.

Wat zijn de knelpunten in de backend?

SNARK's voor circuittevredenheid worden meestal ontworpen door een informatietheoretisch veilig protocol te combineren dat een "polynoom IOP” met een cryptografisch protocol genaamd een “polynomiale verbintenisregeling.” In de meeste gevallen is het concrete knelpunt voor de bewijzer het polynomiale commitment-schema. In het bijzonder hebben deze SNARK's de bewijzer cryptografisch vastgelegd in een of meer polynomen waarvan de graad (minstens) |C|, het aantal poorten in het circuit C. 

Het concrete knelpunt binnen het polynomiale commitment-schema zal op zijn beurt afhangen van het gebruikte schema en de circuitgrootte. Maar het zal altijd een van de volgende drie bewerkingen zijn: het berekenen van FFT's, machtsverheffingen in een cryptografische groep, of Merkle-hashing. Merkle-hashing is meestal alleen een knelpunt als het circuit klein is, dus we zullen het niet verder bespreken. 

Polynomiale verplichtingen op basis van discrete log

In polynomiale verplichtingen op basis van de hardheid van het discrete logaritmeprobleem in een cryptografische groep G (KZG, Kogelvrij, Dory en Hyrax-commit), moet de bewijzer a . berekenen Pedersen vector verbintenis met de coëfficiënten van de polynoom. Dit omvat een multi-exponentiatie, van grootte gelijk aan de graad van de polynoom. In SNARK's is deze graad meestal de grootte |C| van de schakeling C.

Naïef gedaan, een multi-exponentiation van grootte |C| vereist ongeveer 1.5·|C|·inloggen |G| ≈ 400·|C| groepsactiviteiten, waar |G| geeft het aantal elementen in de groep aan G. Er is echter een benadering, het algoritme van Pippenger, die dit kan verminderen met een factor van ruwweg log |C|. Voor grote circuits (zeg, |C| 225), dit logboek |C| factor kan concreet 25 of meer zijn, dat wil zeggen, voor grote circuits verwachten we dat de Pedersen-vectorverplichting berekenbaar kan zijn met iets meer dan 10·|C| groepsactiviteiten. Elke groepsoperatie is op zijn beurt (als een zeer ruwe marge) ongeveer 10x langzamer dan een eindige veldoperatie. SNARK's die deze polynomiale verplichtingen gebruiken, zijn net zo duur voor P ongeveer 100·|C| veldoperaties. 

Helaas hebben bestaande SNARK's extra overheadkosten bovenop de 100x-factor hierboven. Bijvoorbeeld:

• spartaans's bewijzer, die de Hyrax polynomiale verbintenis gebruikt, heeft te maken met: |C|^½ veel multi-exponentiations elk van grootte |C|^½, waardoor de versnelling van het algoritme van Pippenger met een factor van ongeveer twee wordt verzwakt. 
• In Groth16, P moet werken met een groep die vriendelijk is voor paren, waarvan de handelingen doorgaans minstens 2x langzamer zijn dan groepen die niet vriendelijk zijn voor paren. P moet ook 3 multi-exponentiaties uitvoeren in plaats van 1. Gecombineerd resulteert dit in ten minste een extra vertraging van factor 6 ten opzichte van de 100·|C| schatting hierboven. 
• Marlin en PlonK vereisen ook paren, en hun bewijzers om zich te committeren aan aanzienlijk meer dan 3 polynomen. 
• Voor elke SNARK die gebruik maakt van Kogelvrij (Bv Halo2, wat ruwweg PlonK is, maar met Bulletproofs in plaats van KZG-polynomiale verplichtingen), moet de bewijzer logaritmisch veel multi-exponentiaties berekenen tijdens de "openingsfase" van het commitment-schema, en dit wist grotendeels elke Pippenger-versnelling uit. 

Samengevat lijken bekende SNARK's die gebruik maken van Pedersen-vectortoezeggingen een backend-overhead te hebben van ten minste 200x en tot 1000x of meer. 

Andere polynomiale verplichtingen

Voor SNARK's die andere polynomiale verplichtingen gebruiken (zoals VR en Ligero-commit), is het knelpunt dat de bewijzer grote FFT's moet uitvoeren. Bijvoorbeeld in de graad-2 AIRs geproduceerd door Cairo (met 51 kolommen en T rijen, één per stap van de Caïro-CPU), doet de ingezette bewijzer van StarkWare ten minste 2 FFT's per kolom, met een lengte tussen 16 ·T en 32 ·T. de constanten 16 en 32 zijn afhankelijk van interne parameters van FRI zoals ingesteld door StarkWare en kunnen worden verminderd — maar ten koste van hogere verificatiekosten. 

Optimistisch, een FFT van lengte 32·T duurt ongeveer 64·T·logboek(32T) veldvermenigvuldigingen. Dit betekent dat zelfs voor relatief kleine waarden van T (Bv T ≥ 2²⁰), het aantal veldbewerkingen per kolom is minimaal 64·25·T= 1600·T. Dus de backend-overhead lijkt op zijn minst in de duizenden te lopen. Bovendien is het mogelijk dat grote FFT's nog meer worden gehinderd door geheugenbandbreedte dan door veldoperaties. 

In sommige contexten kan de backend-overhead van SNARK's die grote FFT's uitvoeren, worden beperkt met een techniek die bewijsaggregatie wordt genoemd. Voor rollups zou dit betekenen dat: P (de rollup-service) breekt een grote batch transacties op in bijvoorbeeld 10 kleinere batches. Voor elke kleine batch i, P produceert een SNARK proof πi van de geldigheid van de partij. Maar P plaatst deze bewijzen niet op Ethereum, omdat dit zou leiden tot een bijna 10-voudige stijging van de gaskosten. In plaats daarvan wordt de SNARK opnieuw toegepast, dit keer om een ​​bewijs te produceren π vaststellen dat P weet π₁ , ...,π₁₀. Dat wil zeggen, de getuige die P beweert te weten zijn de tien bewijzen₁,…,π₁₀, en directe getuigencontrole past de SNARK-verificatieprocedure toe op elk van de bewijzen. Dit enige bewijs π wordt gepost op Ethereum. 

In polynomiale commitments zoals FRI en Ligero-commit is er een sterke spanning tussen P tijd en V kosten, waarbij interne parameters fungeren als een knop die de een voor de ander kan inruilen. Sinds π₁ ,…,π₁₀ worden niet op Ethereum gepost, de knop kan worden afgesteld, dus deze bewijzen zijn groot, en de productie ervan is sneller. Alleen in de definitieve toepassing van de SNARK, om te aggregeren π₁ ,…,π₁₀ in een enkel bewijs π, moet het commitment-schema worden geconfigureerd om een ​​klein bewijs te garanderen. 

StarkWare is van plan om bewijsaggregatie in te zetten imminently. Dit is ook de focus van projecten zoals: Plonky2.

Wat zijn de andere knelpunten voor de schaalbaarheid van SNARK?

Dit bericht is gericht op prover niet de tijd of, maar andere bewijskosten kunnen ook knelpunten in de schaalbaarheid zijn. Voor veel SNARK-backends moet de prover bijvoorbeeld verschillende veldelementen voor elke poort opslaan in C, en deze ruimtekosten kunnen enorm zijn. Bijvoorbeeld een programma ψ draaien in één seconde op een laptop kan misschien een miljard primitieve bewerkingen uitvoeren op een moderne processor. Zoals we hebben gezien, mag men in het algemeen verwachten: C om meer dan 100 poorten per dergelijke operatie te vereisen. Dit betekent 100 miljard poorten, wat, afhankelijk van de SNARK, tientallen of honderden terabytes aan ruimte voor P. 

Een ander voorbeeld: veel populaire SNARK's (bijv. PlonK, Marlin, Groth16) vereisen een gecompliceerde "vertrouwde installatieceremonie" om een ​​gestructureerde "bewijssleutel" te genereren, die door de bewijzer moet worden opgeslagen. Voor zover ik weet is de grootste dergelijke ceremonie genereerde een testsleutel die circuits kan ondersteunen met ongeveer 2²⁸≈250 miljoen poorten. De bewijssleutel is enkele tientallen gigabytes groot. 

In contexten waar bewijsaggregatie mogelijk is, kunnen deze knelpunten aanzienlijk worden verminderd. 

Vooruitblik: vooruitzichten voor meer schaalbare SNARK's

Zowel frontend- als backend-overheadkosten kunnen drie orden van grootte of meer bedragen. Kunnen we verwachten dat deze in de nabije toekomst substantieel zullen dalen? 

Ik denk dat we zullen - tot op zekere hoogte. Ten eerste, de snelste backends van vandaag (bijv. spartaans en Remmen, en andere SNARK's die de . combineren som-check protocol met polynomiale verplichtingen) hebben grote bewijzen - meestal vierkantswortel in de grootte van het circuit - dus mensen gebruiken ze niet echt. Ik verwacht dat de proefgrootte en verificatietijd in de nabije toekomst aanzienlijk zullen worden verminderd via een compositie met diepte-één met kleine-proof SNARK's. Net als bij bewijsaggregatie betekent dit dat een bewijzer eerst een SNARK-bewijs genereert π met de “fast-prover, large-proof” SNARK, maar niet sturen π naar V. Liever, P zou een small-proof SNARK gebruiken om een ​​proof te produceren π' dat het weet π, en verzend π' naar V. Dit zou een orde van grootte van de backend-overheadkosten van SNARK's die tegenwoordig populair zijn, kunnen scheren. 

Ten tweede kan hardwareversnelling helpen. Een zeer ruwe algemene regel is dat GPU's een 10x snellere snelheid dan CPU's kunnen kopen, en ASIC's een 10x snellere snelheid dan GPU's. Op dit vlak heb ik echter drie bedenkingen. Ten eerste kunnen grote FFT's worden gehinderd door geheugenbandbreedte in plaats van veldbewerkingen, dus SNARK's die dergelijke FFT's uitvoeren, kunnen beperkte versnellingen zien van gespecialiseerde hardware. Ten tweede, hoewel deze post zich concentreerde op het knelpunt van de polynomiale verbintenis, vereisen veel SNARK's dat de bewijzer andere bewerkingen uitvoert die slechts iets minder duur zijn. Dus het doorbreken van de bottleneck van de polynomiale commitment (bijv. het versnellen van multi-exponentiations in discrete-log-gebaseerde SNARK's) kan een nieuwe bottleneck-operatie achterlaten die niet veel beter is dan de oude. (SNARK's, waaronder Groth16, Marlin en PlonK, hebben bijvoorbeeld ook de prover om FFT's te doen, naast multi-exponentiations.) Ten slotte kunnen de velden en elliptische curven die leiden tot de meest efficiënte SNARK's nog enige tijd blijven evolueren, en dat kan uitdagingen opleveren voor ASIC-gebaseerde bewijzerversnelling.

Aan de frontend zullen we in toenemende mate merken dat de "CPU-emulator"-benadering van projecten zoals Cairo, RISC Zero, zkEVM's en andere behoorlijk goed schaalt (in termen van prestaties) met de complexiteit van CPU-instructiesets. Dit is inderdaad precies de hoop van verschillende zkEVM-projecten. Dit kan betekenen dat, hoewel de frontend-overhead drie orden van grootte of meer blijft, de frontends erin slagen VM's te ondersteunen die steeds meer overeenkomen met echte CPU-architecturen. Een tegenwicht is dat de frontends ingewikkeld en moeilijk te controleren kunnen worden, omdat met de hand gecodeerde gadgets die steeds ingewikkelder instructies implementeren, toenemen. Formele verificatiemethoden zullen waarschijnlijk een belangrijke rol spelen bij het aanpakken van deze zorg. 

Ten slotte kunnen we, althans in blockchain-applicaties, ontdekken dat de meeste slimme contracten die in het wild verschijnen, voornamelijk eenvoudige, SNARK-vriendelijke instructies gebruiken. Dit kan in de praktijk lage frontend-overheads mogelijk maken, terwijl de algemeenheid en verbeterde ontwikkelaarservaring behouden blijft die wordt geleverd met het ondersteunen van programmeertalen op hoog niveau zoals Solidity en uitgebreide instructiesets, inclusief die van de EVM. 

***

Justin Taler is een universitair hoofddocent aan de Universiteit van Georgetown. Voordat hij bij Georgetown kwam, was hij twee jaar Research Scientist bij Yahoo Labs in New York, waarvoor hij Research Fellow was bij de Simons Instituut voor de theorie van de informatica bij UC Berkeley. 

***

Dankbetuiging: Ik ben dankbaar voor Elena Burger voor het voorstellen van het onderwerp van dit bericht, en om Arasu Arun, Jozef Boneau en Sam Ragsdale voor verhelderende opmerkingen. Speciale dank ook aan mijn redacteur, Tim Sullivan.

***

De standpunten die hier naar voren worden gebracht, zijn die van het individuele personeel van AH Capital Management, LLC (“a16z”) dat wordt geciteerd en zijn niet de standpunten van a16z of haar gelieerde ondernemingen. Bepaalde informatie in dit document is verkregen uit externe bronnen, waaronder van portefeuillebedrijven van fondsen die worden beheerd door a16z. Hoewel ontleend aan bronnen die betrouwbaar worden geacht, heeft a16z dergelijke informatie niet onafhankelijk geverifieerd en doet het geen uitspraken over de blijvende nauwkeurigheid van de informatie of de geschiktheid ervan voor een bepaalde situatie. Bovendien kan deze inhoud advertenties van derden bevatten; a16z heeft dergelijke advertenties niet beoordeeld en keurt de daarin opgenomen advertentie-inhoud niet goed.

Deze inhoud is uitsluitend bedoeld voor informatieve doeleinden en mag niet worden beschouwd als juridisch, zakelijk, investerings- of belastingadvies. U dient hierover uw eigen adviseurs te raadplegen. Verwijzingen naar effecten of digitale activa zijn alleen voor illustratieve doeleinden en vormen geen beleggingsaanbeveling of aanbod om beleggingsadviesdiensten te verlenen. Bovendien is deze inhoud niet gericht op of bedoeld voor gebruik door beleggers of potentiële beleggers, en mag er in geen geval op worden vertrouwd bij het nemen van een beslissing om te beleggen in een fonds dat wordt beheerd door a16z. (Een aanbod om te beleggen in een a16z-fonds wordt alleen gedaan door middel van het onderhandse plaatsingsmemorandum, de inschrijvingsovereenkomst en andere relevante documentatie van een dergelijk fonds en moet in hun geheel worden gelezen.) Alle genoemde beleggingen of portefeuillebedrijven waarnaar wordt verwezen, of beschreven zijn niet representatief voor alle investeringen in voertuigen die door a16z worden beheerd, en er kan geen garantie worden gegeven dat de investeringen winstgevend zullen zijn of dat andere investeringen die in de toekomst worden gedaan vergelijkbare kenmerken of resultaten zullen hebben. Een lijst van investeringen die zijn gedaan door fondsen die worden beheerd door Andreessen Horowitz (met uitzondering van investeringen waarvoor de uitgevende instelling geen toestemming heeft gegeven aan a16z om openbaar te maken, evenals onaangekondigde investeringen in openbaar verhandelde digitale activa) is beschikbaar op https://a16z.com/investments /.

De grafieken en grafieken die hierin worden verstrekt, zijn uitsluitend bedoeld voor informatieve doeleinden en er mag niet op worden vertrouwd bij het nemen van een investeringsbeslissing. In het verleden behaalde resultaten zijn geen indicatie voor toekomstige resultaten. De inhoud spreekt alleen vanaf de aangegeven datum. Alle projecties, schattingen, voorspellingen, doelstellingen, vooruitzichten en/of meningen die in deze materialen worden uitgedrukt, kunnen zonder voorafgaande kennisgeving worden gewijzigd en kunnen verschillen of in strijd zijn met meningen van anderen. Zie https://a16z.com/disclosures voor aanvullende belangrijke informatie.