Shēmu ietvaru etalonuzdevumi, izmantojot SHA-256
Mēs vēlamies pateikties komandām no Polygon Zero, gnark projekta Consensys, Pado Labs un Delphinus Lab par vērtīgo pārskatu un atsauksmēm par šo emuāru.
Nulles zināšanu panteons
Pēdējo dažu mēnešu laikā mēs esam veltījuši ievērojamu laiku un pūles, lai izstrādātu visprogresīvāko infrastruktūru, kas izmanto zk-SNARK kodolīgus pierādījumus. Kā daļu no mūsu attīstības centieniem mēs esam pārbaudījuši un izmantojuši plašu Zero-Knowledge-Proof (ZKP) izstrādes ietvaru klāstu. Lai gan šis ceļojums ir bijis izdevīgs, mēs apzināmies, ka pieejamo ZKP ietvaru pārpilnība bieži rada izaicinājumu jaunajiem izstrādātājiem, kuri cenšas atrast saviem konkrētajiem lietošanas gadījumiem un veiktspējas prasībām vislabāko. Paturot prātā šo sāpīgo punktu, mēs uzskatām, ka ir nepieciešama kopienas novērtēšanas platforma, kas spēj nodrošināt visaptverošus etalonu rezultātus un kas ļoti palīdzēs šo jauno lietojumprogrammu izstrādē.
Lai apmierinātu šo vajadzību, mēs uzsākam Nulles Zināšanu Pierādījumu Pantheon kā sabiedrības labumu kopienas iniciatīvu. Pirmais solis būs aicināt kopienu dalīties ar reproducējamiem novērtēšanas rezultātiem no dažādiem ZKP ietvariem. Mūsu galīgais mērķis ir kopīgi un sadarbībā izveidot un uzturēt vispārēji atzītu novērtēšanas testu, kas aptver zemu līmeņu shēmu izstrādes ietvarus, augsta līmeņa zkVM un kompilatorus, un pat aparatūras paātrinātāju nodrošinātājus. Mēs ceram, ka šī iniciatīva paātrinās ZKP pieņemšanu, veicinot informētu lēmumu pieņemšanu, vienlaikus mudinot ZKP ietvaru evolūciju un iterāciju, nodrošinot kopumu kopīgi atsaucamu novērtēšanas rezultātu. Mēs esam apņēmušies ieguldīt šajā iniciatīvā un aicinām visus līdzīgi domājošos kopienas locekļus pievienoties mums un kopīgi ieguldīt šajā darbā!
Pirmais solis: Novērtēšanas shēmu ietvaru izmantošana ar SHA-256
Šajā emuāra ierakstā mēs veicam pirmo soli uz Nulles Zināšanu Pierādījumu Pantheon, sniedzot reproducējamu novērtēšanas rezultātu kopumu, izmantojot SHA-256 dažādos zemu līmeņu shēmu izstrādes ietvaros. Lai gan mēs atzīstam, ka ir iespējami citi novērtēšanas smalkumi un primitīvi, mēs izvēlējāmies SHA-256, jo tā piemērojamība plaša spektra ZKP lietojumos, tostarp blokķēdes sistēmām, digitālajām parakstiem, zkDID un citiem. Ir vērts pieminēt, ka mēs arī izmantojam SHA-256 savā sistēmā, tādēļ tas ir diezgan ērti arī mums! 😂
Mūsu novērtējums izvērtē SHA-256 sniegumu dažādos zk-SNARK un zk-STARK shēmu izstrādes ietvaros. Caurskatot šo salīdzinājumu, mēs cenšamies sniegt izstrādātājiem ieskatus par katra ietvara efektivitāti un praktiskumu. Mūsu mērķis ir, ka šie atklājumi ļaus izstrādātājiem pieņemt informētus lēmumus, izvēloties vispiemērotāko ietvaru saviem projektiem.
Pierādīšanas sistēmas
Pēdējos gados mēs esam novērojuši nulles zināšanu pierādīšanas sistēmu izplatīšanos. Lai gan ir grūti sekot visām aizraujošajām attīstībām šajā jomā, mēs esam rūpīgi izvēlējušies šādas pierādīšanas sistēmas, pamatojoties uz to nobriedumu un izstrādātāju pieņemšanu. Mūsu mērķis ir prezentēt pārstāvošu paraugu no dažādiem priekšējā/ aizmugurējā kombinācijām.
Circom + snarkjs / rapidsnark: Circom ir populāra DSL shēmu rakstīšanai un R1CS ierobežojumu ģenerēšanai, kamēr snarkjs spēj ģenerēt Groth16 vai Plonk pierādījumu Circom. Rapidsnark ir arī Circom pierādītājs, kas ģenerē Groth16 pierādījumu un parasti ir daudz ātrāks nekā snarkjs, pateicoties ADX paplašinājumam, kas paralelizē pierādījumu ģenerēšanu pēc iespējas vairāk.
gnark: gnark ir visaptverošs Golang ietvars no Consensys, kas atbalsta Groth16, Plonk un daudzus citus progresīvus elementus.
Arkworks: Arkworks ir visaptverošs Rust ietvars zk-SNARKs.
Halo2 (KZG): Halo2 ir Zcash zk-SNARK realizācija ar Plonk. Tas ir aprīkots ar ļoti elastīgu Plonkish aritmētizāciju, kas atbalsta daudzus noderīgus primitīvus, piemēram, pielāgotas vārti un meklēšanas tabulas. Mēs izmantojam Halo2 atzaru ar KZG atbalstu no Ethereum Foundation un Scroll.
Plonky2: Plonky2 ir SNARK realizācija, kas balstīta uz PLONK un FRI tehnikām no Polygon Zero. Plonky2 izmanto mazu Goldilocks lauku un atbalsta efektīvu rekursiju. Mūsu novērtēšanā mēs mērķējām uz 100-bit apgalvotu drošību un izmantoja parametrus, kas nodrošināja labāko pierādījumu laiku novērtējuma darbam. Konkrēti, mēs izmantojām 28 Merkle pieprasījumus, paplašināšanas faktoru 8 un 16-bit pierādījumu par darbu grūdienu. Turklāt mēs uzstādījām num_of_wires = 60 un num_routed_wires = 60.
Starky: Starky ir augsti efektīvs STARK ietvars no Polygon Zero. Mūsu novērtēšanā mēs mērķējām uz 100-bit apgalvotu drošību un izmantoja parametrus, kas nodrošināja labāko pierādījumu laiku. Konkrēti, mēs izmantojām 90 Merkle pieprasījumus, paplašināšanas faktoru 2, un 10-bit pierādījumu par darbu grūdienu.
Zemāk esošā tabula apkopo iepriekš minētos ietvarus ar attiecīgajām konfigurācijām, kas izmantotas mūsu novērtēšanā. Šis saraksts noteikti nav izsmeļošs un daudzi mūsdienīgi ietvari/tehnoloģijas (piemēram, Nova, GKR, Hyperplonk) ir atstāti nākotnes darbam.
Lūdzu, ņemiet vērā, ka šie novērtēšanas rezultāti attiecas tikai uz shēmu izstrādes ietvariem. Mēs plānojam nākotnē publicēt atsevišķu emuāru, novērtējot dažādus zkVM (piemēram, Scroll, Polygon zkEVM, Consensys zkEVM, zkSync, Risc Zero, zkWasm) un IR kompilatoru ietvarus (piemēram, Noir, zkLLVM).
Novērtēšanas metodoloģija
Lai novērtētu šos dažādos pierādīšanas sistēmas, mēs aprēķinājām SHA-256 hash N bajtu datiem, kur mēs eksperimentējām ar N = 64, 128, ..., 64K (izņēmums ir Starky, kur shēma atkārto SHA-256 aprēķinu fiksētam 64-bajtu ievadam, bet saglabā kopējo ziņojumu gabalu skaitu). Novērtēšanas kods un SHA-256 shēmas realizācijas ir pieejamas šajā krātuvē.
Turklāt mēs veicām katras sistēmas novērtēšanu, izmantojot šādus snieguma rādītājus:
Pierādījumu ģenerēšanas laiks (iekļaujot liecinieka ģenerēšanas laiku)
Maksimālā atmiņas izmantošana pierādījumu ģenerēšanas laikā
Vidējā CPU izmantošana % pierādījumu ģenerēšanas laikā. (Šis rādītājs atspoguļo paralelizācijas pakāpi pierādījumu ģenerēšanas laikā)
Lūdzu, ņemiet vērā, ka mēs veicam dažas "rokas mājienu" pieņēmumus attiecībā uz pierādījuma izmēru un pierādījumu verifikācijas izmaksām, jo šos aspektus var mazināt, sastādot ar Groth16/KZG pirms doties uz ķēdi.
Mašīnas
Mēs veicām mūsu novērtēšanu uz divām dažādām mašīnām:
Linux serveris: 20 kodoli @2.3 GHz, 384GB atmiņa
Macbook M1 Pro: 10 kodoli @3.2Ghz, 16GB atmiņa
Linux serveris tika izmantots, lai simulētu scenāriju ar daudziem CPU kodoliem un bagātīgu atmiņu. Savukārt Macbook M1 Pro, kas parasti tiek izmantots R&D, ir jaudīgāks CPU ar mazāku kodolu skaitu.
Mēs iespējām daudzuzdevumu izpildi, kur tas bija iespējams, taču mēs neizmantojām GPU paātrinājumu šajā novērtējumā. Mēs plānojam iekļaut GPU novērtēšanu kā daļu no mūsu nākotnes darba.
Novērtēšanas rezultāti
Ierobežojumu skaits
Pirms mēs pārejam pie detalizētajiem novērtēšanas rezultātiem, ir noderīgi vispirms saprast SHA-256 sarežģītību, aplūkojot ierobežojumu skaitu katrā pierādīšanas sistēmā. Ir svarīgi būt informētam, ka ierobežojumu skaitļi dažādās aritmētizācijas shēmās nav tieši salīdzināmi.
Zemākie rezultāti atbilst iepriekšējā attēla izmēram 64KB. Lai gan rezultāti var atšķirties ar citiem iepriekšējiem attēla izmēriem, tie var tikt aptuveni lineāri skaloti.
Circom, gnark un Arkworks visi izmanto to pašu R1CS aritmētizāciju, un R1CS ierobežojumu skaits 64KB SHA-256 aprēķināšanai ir aptuveni 30M līdz 45M. Atšķirība starp Circom, gnark un Arkworks, visticamāk, ir saistīta ar realizācijas atšķirībām.
Halo2 un Plonky2 abi izmanto Plonkish aritmētizāciju, kur rindu skaits svārstās no 2^22 līdz 2^23. Halo2 realizācija SHA-256 ir daudz efektīvāka nekā Plonky2 dēļ meklēšanas tabulu izmantošanas.
Starky izmanto AIR aritmētizāciju, kur izpildes izsekošanas tabulām nepieciešami 2^16 pārejas soļi.
Pierādījumu ģenerēšanas laiks
[Attēls 1] ilustrē katra ietvara pierādījumu ģenerēšanas laiku SHA-256 dažādiem iepriekšējā attēla izmēriem, izmantojot Linux serveri. Mēs spējam veikt sekojošas novērošanas:
SHA-256 gadījumā Groth16 ietvari (rapidsnark, gnark un Arkworks) ģenerē pierādījumus ātrāk nekā Plonk ietvari (Halo2 un Plonky2). Tas ir tāpēc, ka SHA-256 galvenokārt sastāv no bitu operācijām, kur vadu vērtības ir vai nu 0, vai 1. Groth16 gadījumā tas samazina lielāko daļu aprēķinu no eliptiskās līknes skalarreizes līdz eliptiskās līknes punkta saskaitīšanai. Tomēr vadu vērtības netiek tieši izmantotas Plonk aprēķinos, tāpēc īpašā vadu struktūra SHA-256 nesamazina nepieciešamā aprēķinu daudzuma Plonk ietvaros.
Visu Groth16 ietvaru vidū gnark un rapidsnark ir 5x-10x ātrāki nekā Arkworks un snarkjs. Tas ir pateicoties viņu izcilajai spējai izmantot vairākus kodolus, lai paralelizētu pierādījumu ģenerēšanu. Gnark ir 25% ātrāks nekā rapidsnark.
Plonk ietvaros Plonky2 ir 50% lēnāks nekā Halo2 SHA-256 gadījumā, izmantojot lielāku iepriekšējā attēla izmēru, kas ir >= 4KB. Tas ir tāpēc, ka Halo2 realizācija intensīvi izmanto meklēšanas tabulu, lai paātrinātu bitu operācijas, rezultātā iegūstot 2x mazāku rindu skaitu nekā Plonky2. Tomēr, ja mēs salīdzinām Plonky2 un Halo2 ar to pašu rindu skaitu (piemēram, SHA-256 pār 2KB Halo2 pret SHA-256 pār 4KB Plonky2), Plonky2 ir 50% ātrāks nekā Halo2. Ja mēs īstenojam SHA-256 ar meklēšanas tabulu Plonky2, mēs varam sagaidīt, ka Plonky2 būs ātrāks nekā Halo2, lai gan Plonky2 pierādījumu izmērs ir lielāks.
No otras puses, kad ievades iepriekšējā attēla izmērs ir mazs (<=512 bajti), Halo2 ir lēnāks nekā Plonky2 (un citi ietvari) dēļ fiksētā uzstādīšanas izmaksām meklēšanas tabulā, kas veido lielāko daļu ierobežojumu. Tomēr, palielinoties iepriekšējā attēla izmēram, Halo2 sniegums kļūst konkurētspējīgāks, ar pierādījumu ģenerēšanas laiku, kas paliek nemainīgs iepriekšējā attēla izmēriem līdz 2KB un pēc tam gandrīz lineāri palielinās, kā var novērot grafikā.
Kā gaidīts, Starky pierādījumu ģenerēšanas laiks ir ievērojami īsāks (5x-50x) nekā jebkuram SNARK ietvaram, taču tas nāk ar daudz lielāku pierādījumu izmēru.
Papildu piezīme ir tāda, ka pat ja shēmas izmērs ir lineārs attiecībā uz iepriekšējā attēla izmēru, pierādījumu ģenerēšana aug super-lineāri SNARK gadījumā dēļ O(nlogn) FFT (lai gan tas nav acīmredzams grafikā dēļ logaritmiskā mēroga).
Mēs arī veicām pierādījumu ģenerēšanas laika novērtējumu uz Macbook M1 Pro, kā ilustrēts [Attēls 2]. Tomēr ir svarīgi atzīmēt, ka rapidsnark netika iekļauts šajā novērtējumā, jo tam trūka atbalsta arm64 arhitektūrai. Lai izmantotu snarkjs uz arm64, mums bija jāģenerē liecinieks, izmantojot webassembly, kas ir lēnāks nekā C++ liecinieka ģenerēšana, ko izmantoja Linux serveris.
Veicot novērtējumu uz Macbook M1 Pro, tika veiktas vairākas papildu novērošanas:
Izņemot Starky, visi SNARK ietvari saskārās ar atmiņas trūkuma (OOM) kļūdām vai izmantoja maiņas atmiņu (kas noveda pie lēnāka pierādīšanas laika), kad iepriekšējā attēla izmērs kļuva liels. Īpaši Groth16 ietvari (snarkjs, gnark, Arkworks) sāka izmantot maiņas atmiņu, kad iepriekšējā attēla izmērs bija lielāks vai vienāds ar 8KB, un gnark saskārās ar OOM 64KB. Halo2 saskārās ar atmiņas ierobežojumu, kad iepriekšējā attēla izmērs bija lielāks vai vienāds ar 32KB. Plonky2 sāk izmantot maiņas atmiņu, kad iepriekšējā attēla izmērs bija lielāks vai vienāds ar 8KB.
FRI balstīti ietvari (Starky un Plonky2) bija par apmēram 60% ātrāki uz Macbook M1 Pro nekā uz Linux servera, kamēr citi ietvari redzēja līdzīgas pierādīšanas reizes salīdzinājumā ar Linux serveri. Tādējādi Plonky2 sasniedza gandrīz to pašu pierādīšanas laiku kā Halo2 uz Macbook M1 Pro, lai gan meklēšanas tabula netika izmantota Plonky2. Galvenais iemesls tam ir tas, ka Macbook M1 Pro ir jaudīgāks CPU, bet ar mazāku kodolu skaitu. FRI galvenokārt veic hash operācijas, kas ir jutīgākas pret CPU pulksteņa cikliem, bet ne tik labi paralelizējamas kā KZG/Groth16.
Maksimālā atmiņas izmantošana
Maksimālā atmiņas izmantošana pierādījumu ģenerēšanas laikā uz Linux servera un Macbook M1 Pro ir parādīta [Attēls 3] un [Attēls 4], attiecīgi. Pamatojoties uz šiem novērtēšanas rezultātiem, var veikt sekojošas novērošanas:
Visu SNARK ietvaru vidū rapidsnark ir visefektīvākais atmiņas ziņā. Mēs arī redzam, ka Halo2 izmanto vairāk atmiņas, kad iepriekšējā attēla izmērs ir mazāks, dēļ fiksētajām uzstādīšanas izmaksām meklēšanas tabulā, bet kopumā patērē mazāk atmiņas, kad iepriekšējā attēla izmērs ir lielāks.
Starky ir vairāk nekā 10x efektīvāks atmiņas ziņā nekā SNARK ietvari. Tam ir daļēji saistība ar mazāku rindu skaitu.
Jāatzīmē, ka maksimālā atmiņas izmantošana uz Macbook M1 Pro paliek relatīvi stabila, kad iepriekšējā attēla izmērs kļūst liels, dēļ maiņas atmiņas izmantošanas.
CPU izmantošana
Mēs novērtējām paralelizācijas pakāpi katrai pierādīšanas sistēmai, mērot vidējo CPU izmantošanu pierādījumu ģenerēšanas laikā SHA-256 virs 4KB iepriekšējā attēla ievada. Zemāk esošā tabula parāda vidējo CPU izmantošanu (un vidējo izmantošanu uz kodolu iekavās) gan Linux serverī (ar 20 kodoliem), gan Macbook M1 Pro (ar 10 kodoliem).
Galvenās novērošanas ir sekojošas:
Gnark un rapidsnark rāda visaugstāko CPU izmantošanu Linux serverī, norādot uz viņu spēju efektīvi izmantot vairākus kodolus un paralelizēt pierādījumu ģenerēšanu. Halo2 arī demonstrē labu paralelizācijas sniegumu.
Vairums ietvaru demonstrē 2x CPU izmantošanu Linux serverī salīdzinājumā ar Macbook Pro M1, izņēmums ir snarkjs.
Neskatoties uz sākotnējām cerībām, ka FRI balstīti ietvari (Plonky2 un Starky) varētu cīnīties ar vairāku kodolu efektīvu izmantošanu, tie veic ne sliktāk nekā daži Groth16/KZG ietvari mūsu novērtējumos. Joprojām ir jāredz, vai būs kādas atšķirības CPU izmantošanā uz mašīnas ar vēl vairāk kodoliem (piemēram, 100 kodoliem).
Secinājums un nākotnes darbs
Šis emuāra ieraksts sniedz visaptverošu salīdzinājumu par SHA-256 sniegumu dažādos zk-SNARK un zk-STARK izstrādes ietvaros. Izmantojot novērtēšanas rezultātus, mēs esam guvuši ieskatus par katra ietvara efektivitāti un praktiskumu izstrādātājiem, kuriem nepieciešami kodolīgi pierādījumi SHA-256 operācijām. Groth16 ietvari (piemēram, rapidsnark, gnark) izrādās ātrāki pierādījumu ģenerēšanā nekā Plonk ietvari (piemēram, Halo2, Plonky2). Meklēšanas tabula Plonkish aritmētizācijā būtiski samazina ierobežojumus un pierādīšanas laiku SHA-256 gadījumā, izmantojot lielāku iepriekšējā attēla izmēru. Turklāt gnark un rapidsnark demonstrē izcilu spēju izmantot vairākus kodolus paralelizācijai. Starky, savukārt, parāda daudz īsāku pierādījumu ģenerēšanas laiku, bet par daudz lielāku pierādījumu izmēru. Attiecībā uz atmiņas efektivitāti rapidsnark un Starky pārspēj citus ietvarus.
Kā pirmie soļi uz Nulles Zināšanu Pierādījumu Pantheon, mēs atzīstam, ka šis novērtēšanas rezultāts ir tālu no tā, lai būtu galīgais visaptverošais testu lauks, ko mēs vēlamies, lai tas kādreiz būtu. Mēs laipni gaidām un esam atvērti atsauksmēm un kritikai, un aicinām visus piedalīties šajā iniciatīvā, kas padara ZKP vieglāk pieejamus un pieejamus izstrādātājiem. Mēs arī esam gatavi piešķirt stipendijas individuāliem dalībniekiem, lai segtu lielapjoma novērtēšanai nepieciešamos aprēķinu resursus. Kopā mēs varam uzlabot ZKP efektivitāti un praktiskumu plašākai sabiedrībai.