SNARKin suorituskyvyn mittaaminen: käyttöliittymät, taustajärjestelmät ja tulevaisuus

SNARK (Succinct Non-Interactive Arguments of Knowledge) on tärkeä kryptografinen primitiivinen hakusovellus lohkoketjun skaalautumiseen (esim. L2-kokoelmat) ja yksityisyyteen. SNARKit antavat jonkun todistaa epäluotettavalle todentajalle V (esim. Ethereum-lohkoketju), että he tietävät joitain tietoja (esim. erän kelvollisia tapahtumia). Naiivi tapa todistaa tämä olisi lähettää tiedot osoitteeseen V, joka voi sitten suoraan tarkistaa sen oikeellisuuden. SNARK saavuttaa saman, mutta paremmilla kustannuksilla V. Erityisesti SNARK-todisteen tulee olla lyhyempi kuin naiivi, joka sisältää itse tiedot. (Katso lisätietoja oppikirjani luonnoksesta, Todistuksia, argumentteja ja nollatietoa. Johdatus SNARKeihin on Sarah Meicklejohnin artikkelissa esitys a16z kryptolla Kesätutkimussarja.)

SNARKien varmennuskustannukset voivat vaihdella, mutta ne ovat hyvin ymmärrettäviä ja usein melko hyviä. Esimerkiksi, Punkku todisteet maksavat noin 290,000-kaasu tarkistaa Ethereumissa, kun taas StarkWaren todisteet maksoivat noin 5 miljoonaa kaasua. SNARKit ovat mahdollisesti käyttökelpoisia erilaisissa ympäristöissä myös lohkoketjujen ulkopuolella – mahdollistaen esimerkiksi nopean mutta epäluotettavan käytön. palvelimet ja laitteisto. 

Mutta koska SNARK-todentaminen on tyypillisesti halpaa, pääasialliset sovellettavuuden määräävät tekijät ovat SNARK-todistajan kustannukset. P. Tässä viestissä selitän, kuinka arvioida nämä kustannukset määrittääksesi, milloin on järkevää käyttää SNARKeja ja miten SNARKit voivat parantaa tulevaisuudessa. On syytä huomata, että tämä on nopeasti muuttuva tila, ja useat tässä viestissä käsitellyt projektit parantavat aktiivisesti suorituskykyään.

Mutta ensin: kuinka SNARKit otetaan käyttöön

SNARK-käytössä kehittäjä kirjoittaa tyypillisesti tietokoneohjelman ψ joka ottaa syötteenä tiedot w jonka todistaja väittää tietävänsä (w tarkoittaa Todistaja), ja tarkistaa sen w on voimassa. Esimerkiksi kokoelmassa ohjelma tarkistaa, että kaikki tapahtumat tulevat sisään w ovat digitaalisesti allekirjoitettuja, eivätkä tilin saldot putoa alle nollan ja niin edelleen. Ohjelma ψ syötetään sitten a SNARK käyttöliittymä joka kokoaa sen muotoon, joka soveltuu paremmin SNARK-tekniikan soveltamiseen. Tätä SNARK-ystävällistä muotoa kutsutaan an välimuotoinen edustus (IR). 

Tyypillisesti IR on jonkinlainen piirin tyydyttävyysinstanssi, joka vastaa ψ. Tämä tarkoittaa, että piiri C ottaa syötteeksi tiedot w, sekä joitain ylimääräisiä syötteitä, joita yleensä kutsutaan "ei-deterministisiksi neuvoiksi", ja suoritetaan ψ on w. Ohjeita käytetään apuna C ajaa ψ, säilyttäen C pieni. Esimerkiksi joka kerta ψ jakaa kaksi lukua x ja y, osamäärä q ja loput r voidaan antaa neuvona Cja C sen voi yksinkertaisesti tarkistaa x = qy + r. Tämä tarkistus on halvempi kuin tekeminen C suorita jakoalgoritmi laskeaksesi q ja r tyhjästä.

Lopuksi piirien tyydyttävyyden SNARK-arvoa sovelletaan C. Tätä kutsutaan SNARK-taustaohjelma. Joillekin erittäin jäsennellyille ongelmille, kuten matriisin kertolasku, käänteitäja useita kaavioongelmia, on olemassa tunnettuja SNARKeja, jotka välttävät tämän frontend/backend-paradigman ja saavuttavat siten huomattavasti nopeamman testauksen. Mutta tämän viestin painopiste on yleiskäyttöisissä SNARKeissa.

Kuten näemme, SNARK-taustajärjestelmän prover-kustannukset kasvavat Cn koko. Säilytys C pieni voi olla haastavaa, koska piirit ovat erittäin rajoitettu muoto laskennan ilmaisemiseksi. Ne koostuvat portit, yhdistää johdot. Jokainen portti g syötetään joitain arvoja ja sovelletaan a hyvin yksinkertainen funktio näihin arvoihin. Tulos syötetään sitten "alavirran" portteihin lähtevien johtojen kautta g.

SNARK-skaalautuvuus: Kuinka paljon aikaa se todella vie?

Avainkysymys on, kuinka paljon enemmän aikaa SNARK-todistaja vie, verrattuna pelkkään uudelleensuoritukseen ψ tiedoissa? Vastaus on todistaa yläpuolella SNARKista suhteessa suora todistajantarkastus. Jälkimmäinen ilmaus viittaa siihen tosiasiaan, että naiivissa todistuksessa, jossa P lähettää w että V, V tarkastukset wn voimassaoloa suorittamalla ψ sitä. 

On hyödyllistä jakaa prover overhead "frontend overhead" ja "backend overhead". Jos arvioit piiriä C portti portilta on F kertaa kalliimpi kuin juokseminen ψ, silloin sanomme, että käyttöliittymän yleiskustannukset ovat F. Jos sovelletaan taustatodistajaa C is B kertaa kalliimpaa kuin arvioida C portilta portilta, sanomme, että backend overhead on B. Todistajan kokonaiskustannukset ovat tuote, F·B. Tämä moninkertainen yleiskustannukset voivat olla huomattavat, vaikka F ja B ovat yksilöllisesti vaatimattomia. 

Käytännössä, F ja B molemmat voivat olla noin 1000 tai suurempia. Tämä tarkoittaa, että todisteiden kokonaiskustannukset suoraan todistajantarkastukseen verrattuna voivat olla 1–10 miljoonaa tai enemmän. Ohjelma, joka toimii vain yhden sekunnin kannettavassa tietokoneessa, voi helposti johtaa SNARK-todistajaan, joka vaatii kymmeniä tai satoja päiviä laskenta-aikaa (yksisäikeinen). Onneksi tämä työ on tyypillisesti rinnastettavissa vaihtelevissa määrin (riippuen SNARKista). 

Yhteenvetona, jos haluat käyttää SNARKia sovelluksessa tänään, yhden kolmesta asiasta on oltava totta:

1. Suora todistajantarkastus kestää paljon vähemmän kuin yhden sekunnin kannettavalla tietokoneella.
2. Suora todistajantarkastus soveltuu erityisen hyvin piirissä edustamiseen, joten etupään yleiskustannukset ovat pienet.
3. Olet valmis odottamaan päiviä SNARK-kokeilun valmistumista ja/tai maksamaan valtavista rinnakkaislaskentaresursseista.

Ttämän postauksen loppuosa selittää, mistä käyttöliittymän ja taustajärjestelmän yleiskustannukset tulevat ja kuinka arvioin ne eri SNARKeille. Siirrymme sitten parannusnäkymiin. 

Erottelee käyttöliittymät ja taustaohjelmat

Frontendien täydellinen erottaminen taustaohjelmista voi olla haastavaa, koska erilaiset taustaohjelmat tukevat erilaisia ​​piirejä. Tästä syystä käyttöliittymät voivat vaihdella sen mukaan, minkä taustaohjelman kanssa ne odottavat liittyvän.

SNARK-taustajärjestelmät tukevat yleensä ns. aritmeettisia piirejä, mikä tarkoittaa, että piirien tulot ovat jonkin äärellisen kentän elementtejä ja että piirin portit suorittavat kahden kenttäelementin yhteen- ja kertolaskua. Nämä piirit vastaavat karkeasti suoraviivaisia ​​tietokoneohjelmia (ei haaroja, ehdollisia lausekkeita ja niin edelleen), jotka ovat luonteeltaan algebrallisia – eli niiden primitiivinen tietotyyppi on kenttäelementtejä. 

Useimmat taustaohjelmat tukevat aritmeettisten piirien yleistämistä, jota usein kutsutaan Rank-1 Constraint Satisfaction (R1CS) -instanssiksi. Huomattavaa poikkeusta lukuun ottamatta Groth16 ja sen edeltäjät, nämä SNARKit voidaan saada tukemaan myös muita IR:itä. Esimerkiksi StarkWare käyttää jotain nimeltä Algebraic Intermediate Representation (AIR), joka on myös samanlainen kuin käsite ns. PlonKish-aritmetisointi joita PlonK ja muut taustaohjelmat voivat tukea. Joidenkin taustaohjelmien kyky tukea yleisempiä IR:itä voi vähentää näitä IR:itä tuottavien käyttöliittymien kustannuksia. 

Taustaohjelmat vaihtelevat myös niiden natiivisti tukemien äärellisten kenttien suhteen. Keskustelen tästä lisää seuraavassa osiossa.

Erilaisia ​​lähestymistapoja frontendeihin

Jotkut (erittäin erikoiset) tietokoneohjelmat vastaavat luonnollisesti aritmeettisia piirejä. Yksi esimerkki on tietokoneohjelma, joka suorittaa matriisien naiivia kertolaskua jossain kentässä. Mutta useimmat tietokoneohjelmat eivät ole suoraviivaisia ​​eivätkä algebrallisia. Ne sisältävät usein ehdollisia lausekkeita, operaatioita, kuten kokonaislukujakoa tai liukulukuaritmetiikkaa, jotka eivät luonnollisesti vastaa äärellisen kentän aritmetiikkaa, ja paljon muuta. Näissä tapauksissa käyttöliittymän yleiskustannukset ovat huomattavat. 

Eräs suosittu käyttöliittymätapa on tuottaa piirejä, jotka käytännössä suorittavat askel askeleelta yksinkertaisen suorittimen, jota kutsutaan myös virtuaalikoneeksi (VM). Käyttöliittymäsuunnittelijat määrittelevät joukon "primitiivisiä operaatioita", jotka ovat analogisia oikeiden tietokoneprosessorien kokoonpanoohjeiden kanssa. Kehittäjät, jotka haluavat käyttää käyttöliittymää, joko kirjoittavat "todistajien tarkistusohjelmat" suoraan assembly-kielellä tai jollakin korkeamman tason kielellä, kuten Solidityllä, ja käännetään ohjelmansa automaattisesti kokoonpanokoodiksi. 

Esimerkiksi StarkWare Kairo on erittäin rajoitettu kokoonpanokieli, jossa kokoonpanokäskyt sallivat karkeasti yhteen- ja kertolaskujen äärellisen kentän yli, funktiokutsuja sekä lukemisen ja kirjoittamisen muuttumattomaan (eli kerran kirjoitettavaan) muistiin. Cairo VM on von Neumann -arkkitehtuuri, mikä tarkoittaa, että käyttöliittymän tuottamat piirit ottavat kairo-ohjelman julkisena syötteenä ja "ajoivat" ohjelman todistajan päällä. Kairon kieli on Turing Complete – rajallisesta käskyjoukostaan ​​huolimatta se voi simuloida standardiarkkitehtuuria, vaikka se voi olla kallista. Kairon käyttöliittymä käynnistää Kairon ohjelmat T primitiiviset ohjeet niin kutsuttuun "tutkintoon"2 AIR kanssa T rivejä ja noin 50 sarakkeita." Mitä juuri tämä tarkoittaa ei ole tärkeä tälle viestille, mutta mitä tulee SNARKin todistajiin, tämä vastaa piirejä, joissa on 50-100 porttia jokaiselle T Kairon CPU:n vaiheet. 

RISC Zero ottaa samanlaisen lähestymistavan Kairoon, mutta virtuaalikoneen ollessa ns RISC-V -arkkitehtuuri, avoimen lähdekoodin arkkitehtuuri, jossa on rikas ohjelmistoekosysteemi ja jonka suosio kasvaa. Hyvin yksinkertaisena käskysarjana sitä tukevan tehokkaan SNARK-käyttöliittymän suunnittelu voi olla suhteellisen helposti seurattavaa (ainakin verrattuna monimutkaisiin arkkitehtuureihin, kuten x86 tai ARM). Toukokuusta lähtien RISC Zero kääntää ohjelmia täytäntöönpanosta T primitiiviset RISC-V-ohjeet asteen-5 AIR:iin 3T rivit ja 160 sarakkeita. Tämä vastaa piirejä, joissa on vähintään 500 portit RISC-V CPU:n askelta kohti. Lisää parannuksia odotetaan lähitulevaisuudessa.

Erilaiset zkEVM-projektit (esim. zkSync 2.0, Scroll, Polygonin zkEVM) pitävät virtuaalikoneen (duh) Ethereum-virtuaalikoneena. Prosessi, jossa jokainen EVM-käsky muutetaan vastaavaksi "vempaimeksi" (eli optimoiduksi piiriksi, joka toteuttaa käskyn), on huomattavasti enemmän mukana kuin yksinkertaisemmissa Kairo- ja RISC-V-arkkitehtuureissa. Tästä ja muista syistä, joitakin zkEVM-projekteja eivät toteuta suoraan EVM-käskysarjaa, vaan pikemminkin kääntävät korkean tason Solidity-ohjelmia muille kokoonpanokielille ennen niiden muuttamista piireiksi. Näiden hankkeiden tulostuloksia odotetaan.

"CPU-emulaattori" -projektit, kuten RISC-V ja Cairo, tuottavat yhden piirin, joka pystyy käsittelemään kaikkia ohjelmia siihen liittyvällä asennuskielellä. Vaihtoehtoiset lähestymistavat ovat "ASIC-tyyppisiä", jotka tuottavat erilaisia ​​piirejä eri ohjelmille. Tämä ASIC-tyyppinen lähestymistapa voi tuottaa pienempiä piirejä joillekin ohjelmille, varsinkin kun ohjelman jokaisessa aikavaiheessa suorittama kokoonpanokäsky ei riipu ohjelman syötteestä. Se voi esimerkiksi mahdollisesti välttää käyttöliittymän yleiskustannukset kokonaan suoraviivaisissa ohjelmissa, kuten naiivi matriisikerto. Mutta ASIC-lähestymistapa näyttää myös erittäin rajoitetulta; Sikäli kuin tiedän, sitä ei tiedetä käyttää silmukoiden tukemiseen ilman ennalta määrättyjä iteraatiorajoja. 

Viimeinen käyttöliittymän ylimääräinen komponentti tulee siitä tosiasiasta, että kaikki SNARKit käyttävät piirejä, jotka toimivat äärellisten kenttien yli. Kannettavan tietokoneen CPU voi kertoa tai lisätä kaksi kokonaislukua yhdellä konekäskyllä. Jos etuosa lähettää piirin riittävän suuren ominaiskäyrän kentän yli, se voi olennaisesti simuloida tätä kertolaskua tai yhteenlaskua vastaavan kenttäoperaation kautta. Kenttäoperaation toteuttaminen todellisella prosessorilla vaatii kuitenkin tyypillisesti monia konekäskyjä (vaikka joillakin nykyaikaisilla prosessoreilla on natiivi tuki tietyille kentille). 

Jotkut SNARK-taustaohjelmat mahdollistavat joustavammat kenttävalinnat kuin toiset. Jos taustaohjelma esimerkiksi käyttää salausryhmää G, piirin kentän on vastattava elementtien lukumäärää G, joka voi olla rajoittava. Lisäksi kaikki kentät eivät tue käytännöllisiä FFT-algoritmeja. 

On vain yksi toteutettu SNARK, Jarrutus, joka tukee natiivisti laskentaa mielivaltaisilla (riittävän suurilla) kentillä. Yhdessä sen kanssa jälkeläisiä, sillä on nopein tunnettu betonikoestuskyky jopa muiden SNARKien tukemilla kentillä, mutta sen todisteet ovat tällä hetkellä liian suuria moniin lohkoketjusovelluksiin. Viimeaikaisia ​​töitä pyrkii parantamaan todisteen kokoa, mutta todistaja on asymptoottisesti hitaampi ja siellä näyttää olevan esteet käytännöllisyyteen.

Jotkut projektit ovat päättäneet työskennellä kenttien yli erityisen nopealla aritmetiikalla. Esimerkiksi, Plonky2 ja toiset käyttävät ominaisuuden 2 kenttää⁶⁴ - 2³² + 1, koska aritmetiikka tässä kentässä voidaan toteuttaa useita kertoja nopeammin kuin vähemmän jäsennellyissä kentissä. Tällaisen pienen ominaisuuden käyttäminen voi kuitenkin johtaa haasteisiin kokonaislukuaritmeettisen kokonaisluvun tehokkaassa esittämisessä kenttäoperaatioiden avulla (esim. kahden 32-bittisen etumerkittömän kokonaisluvun kertominen voi saada tuloksen, joka on suurempi kuin kenttäominaisuus). 

 Mutta mitä tahansa, jotta kaikki nykyään suositut SNARKit saavuttavat 128 bitin suojauksen (ilman vahvistuskustannusten merkittävää kasvua), niiden on toimittava yli 2:n kokoisella kentällä.¹²⁸. Ymmärtääkseni tämä tarkoittaa sitä, että jokainen kenttäoperaatio vaatii vähintään kymmenen 64-bittistä konekertoa sekä huomattavasti enemmän yhteen- ja bittioperaatioita. Tästä syystä tulisi ottaa huomioon vähintään suuruusluokkaa etupään yläraja, koska tarvitaan piirejä, jotka toimivat äärellisten kenttien yli. 

Yhteenvetona voidaan todeta, että nykyiset käyttöliittymät, jotka käyttävät virtuaalikoneen abstraktiota, tuottavat piirejä, joissa on 100-1000-kertaiset portit virtuaalikoneen vaihetta kohti ja mahdollisesti enemmän monimutkaisempia virtuaalikoneita varten. Tämän lisäksi äärellisen kentän aritmetiikka on vähintään 10 kertaa hitaampi kuin nykyaikaisten prosessorien analogiset ohjeet (lukuun ottamatta mahdollisia poikkeuksia, jos prosessorissa on sisäänrakennettu tuki tiettyjä kenttiä varten). "ASIC-käyttöliittymän lähestymistapa" saattaa vähentää joitain näistä yleiskustannuksista, mutta tällä hetkellä se tukee rajoitetusti ohjelmia.

Mitkä ovat taustajärjestelmän pullonkaulat?

SNARKit piirien tyydyttävyyttä varten suunnitellaan tyypillisesti yhdistämällä informaatioteoreettisesti turvallinen protokolla nimeltä "polynomi IOP" kryptografisella protokollalla nimeltä "polynominen sitoumusjärjestelmä.” Useimmissa tapauksissa todistajan konkreettinen pullonkaula on polynominen sitoumusmalli. Erityisesti näillä SNARK:illa on salaussitoutuminen yhteen tai useampaan polynomiin, jonka aste on (vähintään) |C|, piirin porttien lukumäärä C. 

Konkreettinen pullonkaula polynomin sitoutumismallissa puolestaan ​​riippuu käytetystä kaavasta ja piirin koosta. Mutta se on aina yksi seuraavista kolmesta operaatiosta: FFT:n laskenta, eksponentioiminen salausryhmässä tai Merklen hajautus. Merkle-hashing on tyypillisesti pullonkaula vain, jos piiri on pieni, joten emme käsittele sitä enempää. 

Diskreettiin lokiin perustuvat polynomiset sitoumukset

Polynomisissa sitoumuksissa, jotka perustuvat diskreetin logaritmitehtävän kovuuteen kryptografisessa ryhmässä G (KZG, Bulletproofs, Pietarinkalaja Hyrax-sitoumus), todistajan on laskettava a Pedersen-vektorisitoumus polynomin kertoimiin. Tähän liittyy monieksponentti, jonka koko on yhtä suuri kuin polynomin aste. SNARKissa tämä aste on tyypillisesti koko |C| piirin C.

Naiivisti tehty, koon moninkertaistaminen |C| vaatii noin 1.5·|C|·log |G| ≈ 400·|C| ryhmätoimintaa, missä |G| ilmaisee ryhmän elementtien lukumäärän G. On kuitenkin olemassa lähestymistapa, nimeltään Pippengerin algoritmi, joka voi pienentää tätä karkeasti log-kertoimella. |C|. Suurille piireille (esim. |C| ≥ 225), tämä loki |C| kerroin voi konkreettisesti olla 25 tai enemmän, eli suurilla piireillä odotamme, että Pedersen-vektorisitoumus voi olla laskettavissa hieman yli 10:llä·|C| ryhmätoimintaa. Jokainen ryhmäoperaatio vuorostaan ​​on (erittäin karkeana pallokenttänä) noin 10x hitaampi kuin äärellisen kentän operaatio. Näitä polynomisia sitoumuksia käyttävät SNARKit ovat yhtä kalliita P noin 100·|C| kenttäoperaatiot. 

Valitettavasti nykyisillä SNARKilla on ylimääräisiä yleiskustannuksia yllä olevan 100-kertaisen kertoimen lisäksi. Esimerkiksi:

• spartalainenTodistaja, joka käyttää Hyrax-polynomin sitoutumista, on tehtävä |C|^½ monia monien eksponentioiden kunkin kokoisia |C|^½, mikä heikentää Pippengerin algoritmin nopeutta noin kaksinkertaiseksi. 
• In Groth16, P täytyy työskennellä pariliitosystävällisessä ryhmässä, jonka toiminta on tyypillisesti vähintään 2x hitaampaa kuin ryhmät, jotka eivät ole paritusystävällisiä. P on myös suoritettava 3 monieksponenttia yhden sijasta. Yhdessä tämä johtaa ainakin lisähidastumiseen 1 verrattuna 6:aan·|C| arvio yllä. 
• Marlin ja Punkku vaativat myös pariliitoksia, ja niiden todistajat sitoutuvat huomattavasti useampaan kuin kolmeen polynomiin. 
• Kaikille SNARKille, jotka käyttävät Bulletproofs (esim, Halo2, joka on suunnilleen PlonK, mutta jossa on Bulletproofs pikemminkin kuin KZG-polynomiset sitoumukset), todistajan on laskettava logaritmisesti monta monieksponenttia sitoumusjärjestelmän "avautumisvaiheen" aikana, ja tämä suurelta osin poistaa kaiken Pippengerin nopeutumisen. 

Yhteenvetona voidaan todeta, että tunnetuilla SNARKilla, jotka käyttävät Pedersenin vektorisitoumuksia, taustatieto näyttää olevan vähintään 200x ja jopa 1000x tai enemmän. 

Muut polynomiset sitoumukset

SNARK:ille, jotka käyttävät muita polynomisia sitoumuksia (esim Perjantai ja Ligero-sitoumus), pullonkaula on se, että todistajan on suoritettava suuria FFT:itä. Esimerkiksi Kairon valmistamissa asteen 2 AIR:issä (51 sarakkeella ja T rivejä, yksi Kairon CPU:n askelta kohti), StarkWaren käyttöön otettu testaaja tekee vähintään 2 FFT:tä saraketta kohden, pituus välillä 16 ·T ja 32 ·T. Vakiot 16 ja 32 riippuvat StarkWaren asettamista FRI:n sisäisistä parametreista, ja niitä voidaan vähentää – mutta lisääntyneiden varmennuskustannusten kustannuksella. 

Optimistisesti katsottuna FFT, jonka pituus on 32·T kestää noin 64·T·loki(32T) kentän kertolaskuja. Tämä tarkoittaa, että jopa suhteellisen pienillä arvoilla T (esim, T ≥ 2²⁰), kenttätoimintojen määrä saraketta kohden on vähintään 64·25·T= 1600·T. Joten taustajärjestelmän yleiskustannukset näyttävät olevan ainakin tuhansia. Lisäksi on mahdollista, että suuret FFT:t ovat jopa enemmän pullonkauloja muistin kaistanleveyden takia kuin kenttätoiminnot. 

Joissakin yhteyksissä suuria FFT:itä suorittavien SNARKien taustakuormitusta voidaan lieventää tekniikalla, jota kutsutaan todisteiden yhdistämiseksi. Rollupeille tämä tarkoittaisi sitä P (Rollup-palvelu) jakaa suuren erän tapahtumia esimerkiksi 10 pienempään erään. Jokaiselle pienelle erälle i, P tuottaa SNARK-todistuksen πi erän voimassaolosta. Mutta P ei lähetä näitä todisteita Ethereumiin, koska tämä johtaisi lähes 10-kertaiseen kaasukustannusten nousuun. Sen sijaan SNARKia käytetään jälleen, tällä kertaa todisteen tuottamiseksi π sen vahvistaminen P tietää π₁ ...,π₁₀. Eli sen todistaja P väittää tietävänsä on kymmenen todistetta π₁,…,π₁₀, ja suora todistajantarkastus soveltaa SNARK-varmennusmenettelyä jokaiseen todisteeseen. Tämä yksittäinen todiste π lähetetään Ethereumiin. 

Polynomisissa sitoumuksissa, kuten FRI ja Ligero-commit, välillä on voimakas jännite P aika ja V kustannuksia, ja sisäiset parametrit toimivat nuppina, joka voi vaihtaa keskenään. Siitä asti kun π₁ ,…,π₁₀ ei lähetetty Ethereumiin, nuppia voidaan säätää niin, että nämä todisteet ovat suuria ja niiden tuottaminen on nopeampaa. Vain lopullisessa sovelluksessa SNARK, aggregaatti π₁ ,…,π₁₀ yhdeksi todisteeksi π, tarvitseeko sitoumusjärjestelmä konfiguroida pienen todisteen varmistamiseksi. 

StarkWare aikoo ottaa käyttöön todisteiden yhdistämisen lähiaikoina. Tämä on myös projektien, kuten esim Plonky2.

Mitä muita SNARKin skaalautuvuuden pullonkauloja on?

Tämä viesti on keskittynyt todistamiseen aika, mutta myös muut kustannukset voivat olla skaalautuvuuden pullonkauloja. Esimerkiksi monille SNARK-taustajärjestelmille proverin on tallennettava useita kenttäelementtejä jokaiselle portille C, ja tämä tilakustannukset voivat olla valtavat. Esimerkiksi ohjelma ψ Sekunnissa kannettavalla tietokoneella voi suorittaa ehkä miljardi primitiivistä toimintoa nykyaikaisella prosessorilla. Kuten olemme nähneet, yleensä pitäisi odottaa C vaatia reilusti yli 100 porttia tällaista toimenpidettä kohden. Tämä tarkoittaa 100 miljardia porttia, mikä SNARKista riippuen voi tarkoittaa kymmeniä tai satoja teratavuja tilaa P. 

Toinen esimerkki: monet suositut SNARKit (esim. Punkku, Marlin, Groth16) vaativat monimutkaisen "luotetun määritysseremonian" jäsennellyn "todistusavaimen" luomiseksi, jotka todistajan on tallennettava. Sikäli kuin tiedän, suurin tällainen seremonia loi koeavaimen, joka pystyy tukemaan piirejä noin 2:lla²⁸≈250 miljoonaa porttia. Todistusavain on kooltaan useita kymmeniä gigatavuja. 

Konteksteissa, joissa todisteiden yhdistäminen on mahdollista, näitä pullonkauloja voidaan lieventää merkittävästi. 

Katse eteenpäin: mahdollisuus saada lisää skaalautuvia SNARKeja

Sekä käyttöliittymän että taustapuolen yleiskustannukset voivat olla vähintään kolme suuruusluokkaa. Voimmeko odottaa näiden laskevan merkittävästi lähitulevaisuudessa? 

Luulen, että teemme - tiettyyn pisteeseen asti. Ensinnäkin tämän päivän nopeimmat taustaohjelmat (esim. spartalainen ja Jarrutus, ja muut SNARKit, jotka yhdistävät summan tarkistusprotokolla polynomisilla sitoumuksilla) on suuria todisteita - tyypillisesti neliöjuuria piirin koosta - joten ihmiset eivät todellakaan käytä niitä. Odotan, että vedoskokoa ja todentamisaikaa lyhennetään merkittävästi lähitulevaisuudessa Defence-one-koostumuksen avulla, jossa on pieniä todisteita SNARKeja. Kuten todisteiden yhdistäminen, tämä tarkoittaa, että todistaja luo ensin SNARK-todistuksen π "nopeasti todistetun, suuren todisteen" SNARKin kanssa, mutta älä lähetä π että V. pikemminkin P käyttäisi pieni todiste SNARK tuottaa todiste π" että se tietää π, ja lähetä π" että V. Tämä voi pienentää nykyisin suosittujen SNARKien taustakustannuksia suuruusluokkaa. 

Toiseksi laitteistokiihdytys voi auttaa. Hyvin karkea yleinen sääntö on, että GPU:t voivat ostaa 10-kertaisen nopeutuksen prosessoreihin verrattuna ja ASIC:t 10-kertaisen nopeutuksen GPU:ihin verrattuna. Minulla on kuitenkin kolme huolenaihetta tällä alalla. Ensinnäkin suuret FFT:t voivat olla pullonkauloja muistin kaistanleveyden vuoksi kenttätoimintojen sijaan, joten tällaisia ​​FFT:itä suorittavat SNARKit voivat nähdä rajoitetusti erikoislaitteiston nopeutta. Toiseksi, vaikka tämä viesti keskittyi polynomisten sitoumusten pullonkaulaan, monet SNARKit vaativat todistajan suorittamaan muita toimintoja, jotka ovat vain hieman halvempia. Joten rikkomalla polynomin sitoutumisen pullonkaula (esim. monien eksponentioiden nopeuttaminen erillisissä lokipohjaisissa SNARKissa) voi jättää uuden pullonkaulatoiminnon, joka ei ole huomattavasti parempi kuin vanha. (Esimerkiksi SNARK:illa, mukaan lukien Groth16, Marlin ja PlonK, on ​​myös FFT:t, monien eksponentioiden lisäksi.) Lopuksi kentät ja elliptiset käyrät, jotka johtavat tehokkaimpiin SNARK:eihin, voivat jatkaa kehittymistä jonkin aikaa, mikä voi luoda haasteita ASIC-pohjaiselle prover-kiihtyvyydelle.

Käyttöliittymän puolella saatamme yhä useammin huomata, että "CPU-emulaattori" -lähestymistapa sellaisissa projekteissa kuin Cairo, RISC Zero, zkEVMs ja muut skaalautuvat melko hyvin (suorituskyvyn suhteen) suorittimen käskysarjojen monimutkaisuuden vuoksi. Tämä on todellakin erilaisten zkEVM-projektien toivo. Tämä voi tarkoittaa, että vaikka käyttöliittymän yleiskustannukset säilyvät vähintään kolme suuruusluokkaa, käyttöliittymät onnistuvat tukemaan virtuaalikoneita, jotka vastaavat yhä enemmän todellisia suoritinarkkitehtuureja. Vastapuolena huolenaihe on, että käyttöliittymät voivat monimutkaistaa ja niitä on vaikea tarkastaa, kun yhä monimutkaisempia ohjeita toteuttavat käsin koodatut gadgetit lisääntyvät. Muodollisilla varmistusmenetelmillä on todennäköisesti tärkeä rooli tämän huolen ratkaisemisessa. 

Lopuksi, ainakin lohkoketjusovelluksissa, voimme huomata, että useimmat luonnossa esiintyvät älykkäät sopimukset käyttävät ensisijaisesti yksinkertaisia, SNARK-ystävällisiä ohjeita. Tämä voi mahdollistaa alhaiset käyttöliittymän yleiskustannukset käytännössä säilyttäen samalla yleisyyden ja paremman kehittäjäkokemuksen, joka tulee tukemaan korkean tason ohjelmointikieliä, kuten Solidity, ja runsaita käskysarjoja, mukaan lukien EVM:n kielet. 

***

Justin Thaler is apulaisprofessori Georgetownin yliopistossa. Ennen Georgetowniin tuloaan hän työskenteli kaksi vuotta tutkijana Yahoo Labsissa New Yorkissa, mitä ennen hän oli tutkijana Simons Institute for the Theory of Computing UC Berkeleyssä. 

***

Kiitokset: Olen kiitollinen Elena Burger tämän julkaisun aiheen ehdottamisesta ja Arasu Arun, Joseph Bonneauja Sam Ragsdale oivaltavista kommenteista. Erityiset kiitokset myös toimittajalleni, Tim Sullivan.

***

Tässä esitetyt näkemykset ovat yksittäisen AH Capital Management, LLC:n ("a16z") lainaaman henkilöstön näkemyksiä, eivätkä ne ole a16z:n tai sen tytäryhtiöiden näkemyksiä. Tietyt tähän sisältyvät tiedot on saatu kolmansien osapuolien lähteistä, mukaan lukien a16z:n hallinnoimien rahastojen kohdeyrityksiltä. Vaikka a16z on otettu luotettaviksi uskotuista lähteistä, se ei ole itsenäisesti tarkistanut tällaisia ​​tietoja eikä esitä tietojen pysyvää tarkkuutta tai sen soveltuvuutta tiettyyn tilanteeseen. Lisäksi tämä sisältö voi sisältää kolmannen osapuolen mainoksia; a16z ei ole tarkistanut tällaisia ​​mainoksia eikä tue mitään niiden sisältämää mainossisältöä.

Tämä sisältö on tarkoitettu vain tiedoksi, eikä siihen tule luottaa lainopillisena, liike-, sijoitus- tai veroneuvona. Näissä asioissa kannattaa kysyä neuvojanne. Viittaukset arvopapereihin tai digitaaliseen omaisuuteen ovat vain havainnollistavia, eivätkä ne ole sijoitussuositus tai tarjous tarjota sijoitusneuvontapalveluita. Lisäksi tämä sisältö ei ole suunnattu eikä tarkoitettu sijoittajien tai mahdollisten sijoittajien käytettäväksi, eikä siihen voida missään olosuhteissa luottaa tehdessään sijoituspäätöstä mihinkään a16z:n hallinnoimaan rahastoon. (A16z-rahastoon sijoitustarjous tehdään vain minkä tahansa tällaisen rahaston suunnatun osakeannin muistion, merkintäsopimuksen ja muiden asiaankuuluvien asiakirjojen perusteella, ja ne tulee lukea kokonaisuudessaan.) Kaikki mainitut sijoitukset tai kohdeyritykset, joihin viitataan, tai kuvatut eivät edusta kaikkia investointeja a16z:n hallinnoimiin ajoneuvoihin, eikä voi olla varmuutta siitä, että investoinnit ovat kannattavia tai että muilla tulevaisuudessa tehtävillä investoinneilla on samanlaisia ​​ominaisuuksia tai tuloksia. Luettelo Andreessen Horowitzin hallinnoimien rahastojen tekemistä sijoituksista (lukuun ottamatta sijoituksia, joiden osalta liikkeeseenlaskija ei ole antanut a16z:lle lupaa julkistaa, sekä ennalta ilmoittamattomat sijoitukset julkisesti noteerattuihin digitaalisiin omaisuuseriin) on saatavilla osoitteessa https://a16z.com/investments /.

Kaaviot ja kaaviot ovat vain tiedoksi, eikä niihin tule luottaa sijoituspäätöstä tehtäessä. Aiempi kehitys ei kerro tulevista tuloksista. Sisältö puhuu vain ilmoitetun päivämäärän mukaan. Kaikki näissä materiaaleissa esitetyt ennusteet, arviot, ennusteet, tavoitteet, näkymät ja/tai mielipiteet voivat muuttua ilman erillistä ilmoitusta ja voivat poiketa tai olla ristiriidassa muiden ilmaisemien mielipiteiden kanssa. Tärkeitä lisätietoja on osoitteessa https://a16z.com/disclosures.