1. Ievads
ZK-SNARK ir kriptogrāfiska pierādīšanas sistēma, kas ļauj uzņēmumam pierādīt, ka kaut kas ir patiess, neatklājot citu informāciju.
ZK-SNARK ir noderīgi vairākās lietojumprogrammās un jomās, piemēram, blokķēdē un pārbaudāmā skaitļošanā. ZK-Rollups tiek izmantota viena ievērojama blokķēdes lietojumprogramma.
ZK-Rollups ir otrā slāņa blokķēdes, kas veidotas virs citām blokķēdēm (piemēram, Ethereum), kas izmanto ZK-SNARK (vai citas kriptogrāfiskās pārbaudes sistēmas), lai pierādītu stāvokļa pāreju derīgumu. Tas nozīmē, ka katru reizi, kad tiek veikts jauns tīkla atjauninājums (tiek pievienota jauna darījumu partija), tiek aprēķināts jauns tīkla stāvoklis un tiek ģenerēts šī stāvokļa derīguma apliecinājums. Lieta tāda, ka šī pierādījuma ģenerēšanai ir nepieciešama tikai viena entītija, un ikviens var uzticēties tā derīgumam.
Vēlamie rekvizīti, ko nodrošina ZK-Rollups, parasti ir (i) mērogojamība un/vai (ii) privātuma aizsardzība. ZK apkopojumus dažreiz sauc par efektivitātes apkopojumiem, ja ir nepieciešama tikai mērogojamība.
Lai aprēķinātu pierādījumus ZK-Rollups, kas paredzēti Ethereum EVM paplašināšanai, var izmantot ZK-EVM. Stingri definēts, ZK-EVM ir kriptogrāfijas programmu (ķēžu) kopums, kas ir atbildīgs par nulles zināšanu pierādījumu (ZKP) ģenerēšanu, lai gan dažreiz sarunvalodā tas attiecas arī uz EVM spējīgu universālo ZK-Rollup kopumā.
2.ZK-SNARK definīcija
SNARK ir īss pierādījums tam, ka noteikts apgalvojums ir patiess. Formāli tas parāda zināšanas par algoritma izpildes izsekošanu, kas rada pareizu risinājumu noteiktai problēmai. Drīzāk tas parāda zināšanas par nepubliskām un nepastāvīgām vērtībām, kas veic izsekošanu. Šīs vērtības kopumā bieži sauc par lieciniekiem. Liecinieka elementi, tas ir, algoritma ievades daļas, veido neatkarīgus lieciniekus, jo tie pastāv pirms algoritma izpildes un nav noteikti ar citiem izpildes izsekošanas elementiem. Izpildes trases publisko nekonstanto vērtību, kas norāda algoritma atrisināmo problēmas gadījumu, sauc par publisku paziņojumu.
ZK-SNARK apzīmē nulles zināšanu kodolīgu neinteraktīvu zināšanu argumentu.
S – vienkāršība
Vienkāršība - pierādījums ir "īss" un pārbaudes laiks ir "ātrs":
"Īss" pierādījums nozīmē, ka pierādījuma lielums ir sublineārs attiecībā pret liecinieka lielumu.
“Ātrais” verifikācijas laiks nozīmē, ka verificētāja darbības laikam (i) jābūt sublineāram liecinieka lielumā un (ii) publiskajā pretenzijā jābūt lineāram.
Bet patiesībā mēs vēlamies, lai tas būtu ne tikai "īss", bet arī "loga polinoma līmenis".
Tas nozīmē, ka pierādījuma lielums un pārbaudes laiks ir gandrīz neatkarīgi no liecinieka lieluma.
Pierādiet, ka π izmēram nevajadzētu augt ātrāk par kādu konstanti, kas reizināta ar liecinieka w lieluma logaritma kvadrātu (pietiekami lielam w):
Pierādījuma lielums ir atkarīgs no konkrētā ZK-SNARK protokola. Plonky2 tas ir O(log^2(|w|)), bet tas ir "sliktākais" gadījums. Piemēram, klasiskajiem PLONK un Groth16 pierādījuma lielums ir O(1), kas ir konstante.
Pārbaudes laikam t_v nevajadzētu būt lielākam par dažām konstantēm, reizinātām ar liecinieka w logaritma kvadrātu, un lineāram publiskās deklarācijas x lielumā (x un w ir pietiekami lieli, ja tikai viens no tiem maina izmēru).
N — neinteraktīvs — pierādījumu ģenerēšana notiek, nesaņemot datus no verificētāja.
ARK — zināšanu pierādījums — līdzīgi kā parastie pierādījumi, taču skaņa darbojas tikai pret polinomiski ierobežotiem pierādījumiem, turpretim pierādījumos skaņa atbilst skaitļošanas ziņā neierobežotiem pierādījumiem. Par skaņas jēdzienu mēs runāsim nākamajā sadaļā.
ZK — nulles zināšanu — liecinieks netiek atklāts.
3. ZK-SNARK īpašības
ZK-SNARK ir trīs galvenās īpašības, kā aprakstīts tālāk:
Pilnīgums: ja pārbaudītājs zina pareizo algoritma izpildes trajektoriju, tad pārbaudītājam ir jātic, ka pārbaudītājam ir šīs zināšanas.
Zināšanu pamatotība: ja vien pārbaudītājs faktiski nezina pareizo izpildes trajektoriju, pārbaudītājs nevar pārliecināt pārbaudītāju, ka tas to zina, taču pastāv ļoti maza varbūtība.
Nulles zināšanas: verificētājs neko nezina par izpildes trajektoriju, izņemot to, ka tā ir pareiza.
4.PLONKish ZK-SNARK proof sistēma
4.1. Ievads par PLONKish ZK-SNARK un to funkcijām
Lai ZK-SNARK pierādīšanas sistēmai to piemērotu noteiktam algoritmam, ir jāzina vienādojumu sistēma galīgajā laukā. Šie vienādojumi apraksta attiecības starp vērtībām algoritma izpildes trajektorijas tabulā. datu struktūra, kas saglabā izpildes trajektoriju), lai nodrošinātu, ka aprēķins ir Integrity. Valodu, ko izmanto, lai izteiktu šo vienādojumu sistēmu (ko sauc arī par ierobežojumu sistēmu), sauc par aritmētisko.
PLONKish ZK-SNARK pārbaudes sistēma izmanto aritmētiku ar lielāku izteiksmes spēku nekā vecākas pārbaudes sistēmas. Pirmais ļauj mums izmantot ierobežojumu sistēmu vienādojumus ar patvaļīgu polinoma formu virs ierobežojuma mainīgajiem, savukārt vecākām pierādīšanas sistēmām (t.i., sistēmām, kuru pamatā ir R1CS) šie vienādojumi bija lineāru un kvadrātisku polinomu formā. Šī funkcija ļauj PLONKish ZK-SNARK pārbaudes sistēmai pozitīvi ietekmēt pārbaudītāja skaitļošanas efektivitāti un atvieglo tās piemērošanu dažādiem algoritmiem. Tāpēc pēdējos gados ir parādījušās daudzas PLONKish ZK-SNARK pārbaudes sistēmas, piemēram, klasiskās PLONK, Halo2, Kimchi, Plonky2, HyperPlonk u.c.
Taiko mēs izmantojam Halo2 pārbaudes sistēmas variantu, kura pamatā ir KZG polinomu saistību shēma.
PLONKish ZK-SNARK proof sistēma sastāv no trim sastāvdaļām:
4.2. Saistību plāns
Solījumu shēma ļauj apsolītājam publicēt vērtību, ko sauc par solījumu, kas saista solītāju ar ziņojumu, neatklājot pašu ziņojumu. Pēc tam apņemšanās var atvērt saistību un nodot apņemto ziņojumu vai kādu tā daļu verificētājam, kurš var pārbaudīt, vai atklātā informācija atbilst saistībām.
Dažādi autori apraksta atšķirīgu skaitu algoritmu, kas veido saistību shēmu. Tomēr mums vajadzētu pieminēt vismaz četrus no šiem algoritmiem:
Iestatīšana: izmanto dažus sākotnējos parametrus kā ievadi un ģenerē iestatīšanas parametrus. Iestatījumos ir norādīts (i) tas, ko mēs apņemamies (piemēram, vienkāršā polinoma saistību shēmai mēs norādām koeficienta domēnu un polinoma maksimālo pakāpi, ko mēs apņemamies), un (ii) drošības līmeni bitos. Mēs varam vienkārši definēt drošības līmeni šādi: Ja ir nepieciešams O(2^n) laiks, lai izjauktu šifrēšanas sistēmu, tad šifrēšanas sistēmas drošības līmenis ir n biti.
Solījums: solījums, kas ģenerē ziņojumus, pamatojoties uz iestatītajiem parametriem.
Daļēja atvēršana: ģenerē daļēju atvēršanas pierādījumu, kas ir raksturīgs atlasītajai ziņojuma daļai (piemēram, noteikta unāra polinoma vērtība kādam parametram), kā arī iestata parametrus.
Validācija: izmantojiet daļēji atvērtu apliecinājumu un iestatiet parametrus, lai pārbaudītu, vai pārbaudītāja atklātā informācija ir norādītā ziņojuma daļa, kas atbilst norādītajām saistībām.
* Dažām saistību shēmām “iestatīšanas” un “atvēršanas” algoritmi var nepastāvēt (piemēram, ja izmanto jaucējfunkciju lielu vērtību noteikšanai).
Saistību plānam ir jābūt šādām īpašībām:
Saistošs: kad pārbaudītājs ir apņēmies ievērot noteiktu ziņojumu, tas tiks saistīts ar ziņojumu, ko tas apņēmās;
Slēpšanās: solījums neizpaust nekādu informāciju par ziņojumu. Slēpšana var būt nevainojama, t.i., daļēji atvērts pierādījums neatklāj nekādu informāciju par ziņojuma neapjautāto daļu (piemēram, KZG saistības), vai neperfekts, t.i., daļēji atklāts pierādījums atklāj kādu daļu no iepriekš minētās informācijas (piemēram, uz FRI bāzes). polinoma saistības).
Saistību shēmas var iedalīt vairākos veidos, pamatojoties uz mērķa objektu: viena elementa saistības;
Polinomu saistību shēmas ir vienīgais veids, ko tieši izmanto PLONKish ZK-SNARK pārbaudes sistēmā. Vienfaktoru polinomu saistību shēmas ir ļoti svarīgas iepriekš minētajām pierādīšanas sistēmām (piemēram, klasiskajām PLONK, Halo2, Kimchi, Plonky2 utt.). Tomēr tagad ir dažas jaunas PLONKish ZK-SNARK metodes, kuru pamatā ir daudzlīniju polinomu saistību shēmas (piemēram, HyperPlonk).
4.3. Interaktīvā Oracle pārbaude
Interaktīvs orākula pierādījums ir interaktīvs pierādījums, kurā verificētājam ir "piekļuve orākulam", lai iegūtu pārbaudītāja ziņojumus, viņš var tos vaicāt varbūtības veidā, un viņam nav jālasa visi pārbaudītāja ziņojumi.
4.4 Fiat-Shamir heiristika
Fiat-Shamir heiristika nodrošina veidu, kā pārveidot (publisku monētu) interaktīvos argumentus neinteraktīvos argumentos. Intuitīvi ideja ir aizstāt validatora nejaušo izaicinājumu ar iepriekšējā ziņojuma jaucējkodu, taču specifika parasti nav precizēta.
*Publiskais monētu protokols ir protokols, kurā pārbaudītāji sūta tikai nejaušus elementus.
4.5. PLONK stila ZK-SNARK proof sistēmas darbības princips
ZK-SNARK pārbaudes sistēmā liecinieka zināšanu apliecināšanai tiek izmantota modificēta interaktīva Oracle pierādīšanas metode, kas izmanto polinomu saistības, lai nodrošinātu Oracle piekļuvi pierādītāja ziņojumam un padara to bez interaktīva, izmantojot Fiat-Shamir heiristiku. Šajā sadaļā mēs detalizēti izskaidrosim doto konstruktoru.
Atgādiniet, ka ZK-SNARK pārbaudes sistēmas piemērošanai algoritmam ir jāizveido atbilstoša ierobežojumu sistēma. Lai to varētu izveidot, mēs definējam algoritma izpildes izsekošanas tabulas struktūru un tajā esošās konstantās vērtības. Mēs izmantojam terminu "shēma", lai apzīmētu izpildes izsekošanas tabulas sarežģīto struktūru, kas aizpildīta tikai ar konstantēm un atbilstošo ierobežojumu sistēmu. Lai ģenerētu ZK-SNARK pierādījumu algoritma izpildes gadījumam, mums ir jāsintezē tam ķēdes gadījums, kas ir atbilstošs algoritma shēmas un izpildes izsekošanas tabulas gadījums (t.i., tabula, kas norāda konstantes, lieciniekus, un publiskās deklarācijas vērtības) kombinācija.
Apskatīsim izsekošanas tabulas struktūru, ko izmanto PLONK stila ZK-SNARK pārbaudes sistēma. Visas kolonnas šādā tabulā pieder vienam no trim veidiem, kurus mēs nosaucam saskaņā ar Halo2 lietoto terminoloģiju un aprakstām šādi:
Fiksētās kolonnas - to šūnas satur konstantes no izpildes izsekošanas tabulas;
Instances kolonna - izmanto publisko deklarāciju vērtību glabāšanai;
Ieteikumu kolonna - kur tiek glabāti visi liecinieku dati (ieskaitot neatkarīgo liecinieku vērtības un aprēķinātos slepenos rezultātus).
Apkopojot, mēs atzīmējam sekojošo:
Izpildes izsekošanas tabula (PLONKish tips) = fiksētas kolonnas + gadījumu kolonnas + ieteikumu kolonnas = izpildes izsekošanas tabula, kas satur tikai konstantes + ierobežojumu sistēma = ķēde + liecinieki savā tabulā + publiskās deklarācijas savā tabulā; publisks paziņojums, neatkarīga liecinieka vērtība) → Shēmas gadījums. Pielietojiet ZK-SNARK pārbaudes sistēmu noteiktam algoritmam = aprakstiet ķēdi + definējiet sintēzes procesu.
Kāpēc termins "shēma" tiek plaši izmantots šajā kontekstā? Sākotnēji, kad bija pieejamas tikai uz R1CS balstītas ZK-SNARK pārbaudes sistēmas, ierobežojumu sistēmu bija ērti attēlot aritmētiskās shēmas veidā, kuras izvadei jābūt nullei. Mēs uzskatām, ka PLONKish SNARK kontekstā termins "shēma" tiek lietots vēsturisku iemeslu dēļ. Jebkurā gadījumā īsumā apskatīsim aritmētisko shēmu, ko izmanto vecākām ZK-SNARK versijām.
Aritmētiskā shēma uz R1CS balstītiem SNARK definē n-mainīgo polinomu ierobežotā laukā, un tai ir novērtēšanas shēma. Sākotnēji tas tiek attēlots kā virzīts aciklisks grafiks (DAG):
tas iekļauj:
Publiskā ievade x, ko izmanto, lai norādītu publiskās deklarācijas vērtību;
Slepenā ievade w, ko izmanto, lai norādītu neatkarīgā liecinieka vērtību;
Aritmētiskie vārti, ko izmanto, lai norādītu saskaitīšanu un reizināšanu ierobežotos laukos.
Apskatīsim aritmētiskās shēmas piemēru racionālo skaitļu laukā.
Mēs sākam no apakšas un strādājam ar zemākajiem vārtiem diagrammā, t.i. (2 x 4 = 8) un (4 + 11 = 15), saglabājot šīs vērtības kā starpvērtības;
Tad mēs virzāmies vienu rindu uz augšu (uz otro rindu) un aprēķinām divu starpvērtību summu (ko ieguvām iepriekšējā posmā), kas ir (8 + 15 = 23);
Tā kā mums ir tikai trīs vārti un mēs izgājām cauri tiem visiem, 23 ir mūsu gala rezultāts.
Pēc tam, kad PLONKish ZK-SNARK pārbaudes sistēma sintezē ķēdes gadījumu, katras instances izpildes izsekošanas tabulas kolonnas tiek kodētas kā polinomi ierobežotos laukos šādā veidā. Pieņemsim, ka C_j(x) ir polinoms, kas apraksta kolonnu j, un ω ir primitīva sakne 2^k-tā, kur k ir izvēlēts tā, lai 2^k būtu nedaudz lielāks par tabulas instances sākotnējo augstumu. Tabulas gadījums ir aizpildīts ar nejaušām rindām (tikai ar šūnām, kas nav nulle ieteiktajās kolonnās), lai tajā būtu 2^k rindas, un C_j(ω^i) ir iestatīta uz j-tās rindas i-tās rindas vērtību. dotās tabulas instances kolonna . Polsterējuma loma nulles zināšanu īpašībām tiks izskaidrota vēlāk.
Apgalvojums "ω ir primitīva sakne 2^k-tā" nozīmē, ka ω^(2^k) = 1, un mums ir ω^t ≠ 1 jebkuram pozitīvam veselam skaitlim t, kas ir mazāks par 2^k.
Ierobežojumu sistēma tiek pārvērsta polinoma vienādojuma formā, aizstājot tajā esošos mainīgos ar atbilstošajiem polinomiem, kas iegūti no kolonnas polinomiem, x vietā aizstājot "x reiz ω, kas paaugstināts līdz kādai pakāpei".
Piemēram, aplūkosim ierobežojumu sistēmas vienādojumu s(i) * (a(i) * b(i) - c(i+1)) = 0. Tas nozīmē, ka, ja s(i) nav nulle, tad a(i) * b(i) ir jābūt vienādam ar c(i+1). Šeit a, b un c ir ieteiktās kolonnas, s ir fiksētā kolonna un i ir pašreizējās rindas numurs.
Šo ierobežojumu var piemērot visām 2^k rindām šādi. Lai S(x), A(x), B(x) un C(x) ir polinomi attiecīgi kolonnās a, b, c un s. Tāpēc mēs ceram:
Tas nozīmē, ka visiem šīs kopas elementiem ir jābūt S(x) * (A(x) * B(x) - C(x * ω) saknēm). Tāpēc šim polinomam ir jādalās ar:
Jo ω ir 2^k kārtas primitīva sakne.
Z(x) = x^(2^k) — 1 sauc par "izzūdošu polinomu", jo tas ir 0 visiem x, kas ir ω ģenerētās cikliskās reizināšanas grupas elementi. Tāpēc S(x) * (A(x) * B(x) - C(x * ω)) mod Z(x) = 0 nozīmē, ka iepriekš minētie ierobežojumi attiecas uz visām 2^k rindām.
Pieņemsim, ka P_0(x), P_1(x), ... , P_m(x) ir ierobežojumi, kas tiek piemēroti visām 2^k rindām un atbilst polinomam S(x) * (A(x) * B(x). iepriekš ) - C(x * ω)) ir līdzīga forma. Ja verificētājs nejauši izvēlas α no galīgā lauka, tad
Tas nozīmē, ka ar ļoti lielu varbūtību visi šie ierobežojumi ir izpildīti visām 2^k rindām. Šis vienādojums nozīmē, ka mēs varam atrast koeficientu polinomu T(x) tādu, ka
Tāpēc, lai pārbaudītājs uzskatītu, ka pārbaudītājs zina izpildes izsekošanas tabulas saturu, kas ar ļoti lielu varbūtību apmierina visus m ierobežojumus, ir tikai jāpierāda, ka nejauši izvēlētam α pārbaudītājam ir gadījumi P_0 (x), P_1(x ),..., ieteiktie kolonnu polinomi un koeficientu polinomi T(x) P_m(x) atbilst šim polinoma vienādojumam. Verificētājs to var izdarīt, lūdzot pārbaudītājam atrast dotā polinoma vērtību nejaušā punktā, ko verificētājs izvēlējies no Z(x) nesaknes punktiem ζ, un šajā punktā novērtēt abas šī vienādojuma puses. ζ Es uzskatu, ka pieteicējs droši vien zina šos polinomus. Šo metodi var pierādīt ar Schwartz-Zippel lemmu.
Lai pierādījumu ģenerēšana nebūtu interaktīva, visas nejaušās vērtības, ko verificētājs ģenerē interaktīvajā versijā, ir jāiegūst, izmantojot Fiat-Shamir heiristiku.
Lai saistītu pierādītāju ar tā ierosinājuma polinomu un koeficienta polinomu T(x), tiek izmantota polinoma saistību shēma. Pierādītājs uzņemas saistības attiecībā uz šiem polinomiem, atver šīs saistības pie ζ (vai uz ζ * ω^q, ja kāds ierobežojums ietekmē rindas i un i + q), un izveido pierādījumu, kas ietver (I) šīs saistības, (II) vērtību. polinoma pie ζ (vai virs ζ * ω^q, ja nepieciešams) un (III) atbilstošā atklātā pierādījuma. Faktiski, lai saīsinātu pārbaudi, izmantojiet vairākas atvēršanas iespējas, t.i., ģenerējiet nelielu pierādījumu visu polinoma punktu vērtībām. Tāpēc pierādījums ir kodolīgs.
Lai apmierinātu nulles zināšanu īpašību, izpildes izsekošanas tabulas gadījumam tiek pievienotas pārbaudītāja nejauši atlasītas rindas, padarot tās augstumu 2^k rindu. Šajās rindās ieteikumu kolonnā ir tikai šūnas, kas nav nulles, jo tikai ieteikumu kolonna satur datus, kurus vēlamies paslēpt. Dariet to pirms piedāvājuma kolonnas polinomu izveides, lai saistību atvēršanas periodā atklāto "parametra vērtību" pāru skaits būtu mazāks nekā nejauši pievienoto pāru skaits katram polinomam. Tāpēc katram piedāvājuma kolonnas polinomam informācijas apjoms, kas nepieciešams, lai to atgūtu pēc saistību atvēršanas, ir lielāks nekā liecinieku informācijas apjoms. Šī situācija rada nulles zināšanas.
Priekšapstrādes fāzē visi izpildshēmas gadījumi veic dažus no tiem pašiem aprēķiniem, tostarp nosaka un aprēķina fiksēto kolonnu polinomus un to saistības polinoma saistību shēmai. Šo aprēķinu iegūto datu daļu izmanto verificētājs, un to bieži sauc par verifikācijas atslēgu. Līdzīgi var definēt pierādījuma atslēgas jēdzienu. Pamatā esošā polinomu saistību shēma nosaka, vai priekšapstrādes posmā tiek veikti uzticamības iestatījumi.