Vitalik Buterin prek Blog Vitalika Buterina
To je ogledalo objave na https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
To je tretji del serije člankov, ki pojasnjujejo, kako deluje tehnologija za zk-SNARKs; prejšnje članke o programi za kvadratno aritmetiko in eliptične pare krivulj sta obvezno branje in ta članek bo predpostavljal poznavanje obeh konceptov. Predpostavlja se tudi osnovno znanje o tem, kaj zk-SNARK so in kaj počnejo. Poglej tudi Članek Christiana Reitwiessnerja tukaj za še en tehnični uvod.
V prejšnjih člankih smo predstavili program kvadratne aritmetike, način predstavitve katerega koli računskega problema s polinomsko enačbo, ki je veliko bolj dovzeten za različne oblike matematičnih zvijač. Predstavili smo tudi pare eliptičnih krivulj, ki omogočajo zelo omejeno obliko enosmernega homomorfnega šifriranja, ki vam omogoča preverjanje enakosti. Zdaj bomo začeli od tam, kjer smo končali, in uporabili pare eliptičnih krivulj, skupaj z nekaj drugimi matematičnimi triki, da bi dokazovalcu omogočili, da dokaže, da pozna rešitev za določen QAP, ne da bi razkril kar koli drugega o dejansko rešitev.
Ta članek se bo osredotočil na Ostržkov protokol Parno, Gentry, Howell in Raykova iz leta 2013 (pogosto imenovan PGHR13); obstaja nekaj različic osnovnega mehanizma, zato lahko shema zk-SNARK, ki se izvaja v praksi, deluje nekoliko drugače, vendar bodo osnovna načela na splošno ostala enaka.
Za začetek pojdimo na ključno kriptografsko predpostavko, na kateri temelji varnost mehanizma, ki ga bomo uporabili: *poznavanje eksponenta* predpostavka.
V bistvu, če dobite par točk � in �, kjer je �⋅�=�, in dobite točko �, potem ni mogoče priti do �⋅�, razen če je � na nek način "izpeljan" iz � da veš. To se morda zdi intuitivno očitno, vendar te predpostavke pravzaprav ni mogoče izpeljati iz nobene druge predpostavke (npr. trdote diskretnega logaritma), ki jo običajno uporabljamo pri dokazovanju varnosti protokolov, ki temeljijo na eliptičnih krivuljah, zato zk-SNARK dejansko temeljijo na nekoliko bolj trhla podlaga kot kriptografija z eliptično krivuljo na splošno — čeprav je še vedno dovolj trdna, da se večina kriptografov strinja z njo.
Zdaj pa poglejmo, kako je to mogoče uporabiti. Predpostavimo, da par točk (�,�) pade z neba, kjer je �⋅�=�, vendar nihče ne ve, kakšna je vrednost �. Zdaj pa predpostavimo, da pridem do par točk (�,�), kjer je �⋅�=�. Potem predpostavka KoE pomeni, da je bil edini način, da sem lahko dosegel ta par točk, tako da sem vzel � in � ter oboje pomnožil z nekim faktorjem r ki jih osebno poznam. Upoštevajte tudi, da zahvaljujoč čarobnosti združevanja eliptičnih krivulj preverjanje, da je �=�⋅� pravzaprav ni potrebno vedeti � – namesto tega lahko preprosto preverite, ali je �(�,�)=�(�,�) ali ne.
Naredimo nekaj bolj zanimivega. Recimo, da nam z neba pade deset parov točk: (�1,�1),(�2,�2)…(�10,�10). V vseh primerih je ��⋅�=��. Recimo, da vam nato ponudim par točk (�,�), kjer je �⋅�=�. Kaj zdaj veš? Veste, da je � neka linearna kombinacija �1⋅�1+�2⋅�2+…+�10⋅�10, kjer poznam koeficiente �1,�2...�10. To pomeni, da je edini način, da pridemo do takega para točk (�,�), da vzamemo nekaj večkratnikov �1,�2...�10 in jih seštejemo ter izvedemo enak izračun z �1,�2... �10.
Upoštevajte, da glede na določen niz �1...�10 točk, za katere bi morda želeli preveriti linearne kombinacije, dejansko ne morete ustvariti spremljajočih �1...�10 točk, ne da bi vedeli, kaj je �, in če veste, kaj � potem lahko ustvarite par (�,�), kjer je �⋅�=� za karkoli � želite, ne da bi se trudili ustvariti linearno kombinacijo. Da bi to delovalo, je absolutno nujno, da je tisti, ki ustvari te točke, vreden zaupanja in dejansko izbriše �, ko ustvari deset točk. Od tod izvira koncept "zaupanja vredne nastavitve"..
Ne pozabite, da je rešitev QAP množica polinomov (�,�,�), tako da je �(�)⋅�(�)−�(�)=�(�)⋅�(�), kjer je:
- � je linearna kombinacija niza polinomov {�1…��}
- � je linearna kombinacija {�1…��} z enakimi koeficienti
- � je linearna kombinacija {�1…��} z enakimi koeficienti
Množice {�1…��}, {�1…��} in {�1…��} ter polinom � so del navedbe problema.
Vendar pa so v večini primerov v resničnem svetu �,� in � izjemno veliki; za nekaj z več tisoč vrati vezja, kot je zgoščevalna funkcija, imajo lahko polinomi (in faktorji za linearne kombinacije) več tisoč členov. Zato bomo namesto, da bi dokazovalnik neposredno zagotovil linearne kombinacije, uporabili trik, ki smo ga predstavili zgoraj, da bi dokazal, da zagotavlja nekaj, kar je linearna kombinacija, vendar ne da bi razkril karkoli drugega.
Morda ste opazili, da zgornji trik deluje na točkah eliptične krivulje, ne na polinomih. Zato se dejansko zgodi, da zaupanja vredni nastavitvi dodamo naslednje vrednosti:
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
Lahko si predstavljate t kot "skrivno točko", na kateri se ovrednoti polinom. � je "generator" (neka naključna točka eliptične krivulje, ki je določena kot del protokola) in �,��,�� in �� so "strupeni odpadki", številke, ki jih je nujno treba izbrisati za vsako ceno, sicer kdor jih ima, bo lahko delal lažne dokaze. Zdaj, če vam nekdo da par točk �, � tako, da je �⋅��=� (opomnik: za preverjanje tega ne potrebujemo ��, saj lahko opravimo preverjanje seznanjanja), potem veste, da vam dajejo linearno kombinacijo �� polinomov, ovrednotenih pri �.
Zato mora dokazovalec zaenkrat dati:
- ��=�⋅�(�),��′=�⋅�(�)⋅��
- ��=�⋅�(�),��′=�⋅�(�)⋅��
- ��=�⋅�(�),��′=�⋅�(�)⋅��
Upoštevajte, da dokazovalcu dejansko ni treba poznati (in ne bi smel vedeti!) �,��,�� ali �� za izračun teh vrednosti; Preverjevalnik bi moral imeti možnost izračunati te vrednosti samo iz točk, ki jih dodajamo zaupanja vredni nastavitvi.
Naslednji korak je zagotoviti, da imajo vse tri linearne kombinacije enake koeficiente. To lahko naredimo tako, da zaupanja vredni nastavitvi dodamo še en niz vrednosti: �⋅(��(�)+��(�)+��(�))⋅�, kjer je � drugo število, ki bi ga morali šteti za “strupeno”. odpadki« in zavržejo takoj, ko je zaupanja vredna nastavitev končana. Nato lahko preverjevalnik ustvari linearno kombinacijo s temi vrednostmi z enakimi koeficienti in uporabi isti trik za združevanje kot zgoraj, da preveri, ali se ta vrednost ujema s podanim �+�+�.
Na koncu moramo dokazati, da je �⋅�−�=�⋅�. To naredimo še enkrat s preverjanjem seznanjanja:
�(��,��)/�(��,�)?=�(�ℎ,�⋅�(�))
Kjer je �ℎ=�⋅�(�). Če se vam povezava med to enačbo in �⋅�−�=�⋅� ne zdi smiselna, se vrnite in preberite članek o parjenju.
Zgoraj smo videli, kako pretvoriti �,� in � v točke eliptične krivulje; � je le generator (tj. točka eliptične krivulje, ki je enaka številki ena). V zaupanja vredno nastavitev lahko dodamo �⋅�(�). � je težje; � je samo polinom in zelo malo vnaprej napovemo, kakšni bodo njegovi koeficienti za vsako posamezno rešitev QAP. Zato moramo zaupanja vredni nastavitvi dodati še več podatkov; natančneje zaporedje:
�,�⋅�,�⋅�2,�⋅�3,�⋅�4….
V zaupanja vredni nastavitvi Zcash gre zaporedje tukaj do približno 2 milijona; to je, koliko potenc � morate zagotoviti, da boste lahko vedno izračunali �(�), vsaj za določen primerek QAP, za katerega skrbijo. In s tem lahko dokazovalnik zagotovi vse informacije, da preveritelj opravi končno preverjanje.
Obstaja še ena podrobnost, o kateri se moramo pogovoriti. Večino časa ne želimo samo abstraktno dokazati, da obstaja rešitev za določen problem; namesto tega želimo dokazati ali pravilnost določene rešitve (npr. dokazati, da če vzamete besedo "krava" in jo SHA3 zgostite milijonkrat, se končni rezultat začne z 0x73064fe5) ali da rešitev obstaja, če omejite nekaj parametrov. Na primer, v primeru kriptovalute, kjer so zneski transakcij in stanja na računu šifrirani, želite dokazati, da poznate nek ključ za dešifriranje k, tako da:
decrypt(old_balance, k) >= decrypt(tx_value, k)
decrypt(old_balance, k) - decrypt(tx_value, k) = decrypt(new_balance, k)
Šifrirano old_balance
, tx_value
in new_balance
je treba navesti javno, saj gre za posebne vrednosti, ki jih želimo preveriti v določenem času; le ključ za dešifriranje mora biti skrit. Za ustvarjanje »ključa za preverjanje po meri«, ki ustreza določeni omejitvi vnosov, je potrebnih nekaj manjših sprememb protokola.
Zdaj pa stopimo malo nazaj. Najprej je tukaj algoritem preverjanja v celoti, z dovoljenjem bena Sasson, Tromer, Virza in Chiesa:
Prva vrstica obravnava parametrizacijo; v bistvu si lahko predstavljate njegovo funkcijo kot ustvarjanje "ključa za preverjanje po meri" za konkreten primer težave kjer so navedeni nekateri argumenti. Druga vrstica je preverjanje linearne kombinacije za �,� in �; tretja vrstica je preverjanje, ali imajo linearne kombinacije enake koeficiente, četrta vrstica pa preverjanje produkta �⋅�−�=�⋅�.
Skupaj je postopek preverjanja sestavljen iz nekaj množenj eliptične krivulje (eno za vsako »javno« vhodno spremenljivko) in petih preverjanj seznanjanja, od katerih eno vključuje dodatno množenje seznanjanja. Dokaz vsebuje osem točk eliptične krivulje: po par točk za �(�),�(�) in �(�), točko �� za �⋅(�(�)+�(�)+�(� )) in točko �ℎ za �(�). Sedem od teh točk je na krivulji �� (vsaka 32 bajtov, saj lahko koordinato � stisnete na en sam bit), v izvedbi Zcash pa je ena točka (��) na zasukani krivulji v ��2 (64 bajtov), tako da je skupna velikost dokazila ~288 bajtov.
Dva računalniško najtežja dela ustvarjanja dokaza sta:
- Deljenje (�⋅�−�)/�, da dobimo � (algoritmi, ki temeljijo na Hitra Fourierjeva transformacija lahko to naredi v subkvadratnem času, vendar je še vedno precej računsko zahtevno)
- Množenje in seštevanje eliptične krivulje za ustvarjanje vrednosti �(�),�(�),�(�) in �(�) ter njihovih ustreznih parov
Osnovni razlog, zakaj je ustvarjanje dokaza tako težko, je dejstvo, da se tisto, kar je bila ena sama binarna logična vrata v prvotnem izračunu, spremeni v operacijo, ki jo je treba kriptografsko obdelati z operacijami eliptične krivulje, če iz tega naredimo dokaz brez znanja. . To dejstvo, skupaj s superlinearnostjo hitrih Fourierjevih transformacij, pomeni, da ustvarjanje dokazov traja približno 20–40 sekund za transakcijo Zcash.
Drugo zelo pomembno vprašanje je: ali lahko poskušamo narediti zaupanja vredno nastavitev nekoliko … manj zahtevno glede zaupanja? Na žalost ne moremo narediti popolnoma nezaupljivega; sama predpostavka KoE preprečuje izdelavo neodvisnih parov (��,��⋅�), ne da bi vedeli, kaj je �. Vendar pa lahko močno povečamo varnost z uporabo večstranskega računanja �-of-� – to je, da zgradimo zaupanja vredno nastavitev med � stranmi na tak način, da ste v redu, če je vsaj eden od udeležencev izbrisal svoje strupene odpadke. .
Da bi dobili občutek, kako bi to naredili, je tukaj preprost algoritem za prevzem obstoječega nabora (�,�⋅�,�⋅�2,�⋅�3 ...) in "dodajanje" lastne skrivnosti tako da za goljufanje potrebujete svojo skrivnost in prejšnjo skrivnost (ali prejšnji niz skrivnosti).
Izhodni niz je preprosto:
�,(�⋅�)⋅�,(�⋅�2)⋅�2,(�⋅�3)⋅�3…
Upoštevajte, da lahko ustvarite ta niz, če poznate samo prvotni niz in s, novi niz pa deluje na enak način kot stari niz, le da zdaj uporabljate �⋅� kot "strupeni odpadek" namesto �. Dokler vam in osebi (ali osebam), ki je ustvarila prejšnji niz, oba ne uspeta izbrisati strupenih odpadkov in se pozneje dogovorita, je niz "varen".
Narediti to za popolno zaupanja vredno nastavitev je precej težje, saj je vključenih več vrednosti, algoritem pa je treba izvajati med strankami v več krogih. To je področje aktivnega raziskovanja, da bi ugotovili, ali je algoritem za večstransko računanje mogoče še poenostaviti in narediti tako, da bo zahteval manj krogov, ali ga narediti bolj vzporednega, saj bolj ko lahko to storite, več strank postane izvedljivo vključiti v postopek zaupanja vredne nastavitve. . Razumno je razumeti, zakaj bi lahko zaupanja vredna postavitev med šestimi udeleženci, ki se vsi poznajo in sodelujejo med seboj, nekaterim ljudem povzročala nelagodje, vendar bi bila zaupanja vredna postavitev s tisoči udeležencev skoraj neločljiva od nikakršnega zaupanja – in če ste res paranoični , lahko vstopite in sodelujete v postopku namestitve sami ter se prepričate, da ste osebno izbrisali svojo vrednost.
Drugo področje aktivnega raziskovanja je uporaba drugih pristopov, ki ne uporabljajo parov in iste paradigme zaupanja vredne nastavitve za doseganje istega cilja; glej Nedavna predstavitev Eli ben Sasson za eno alternativo (čeprav pozor, je vsaj tako matematično zapletena kot so SNARK-ji!)
Posebna zahvala Arielu Gabizonu in Christianu Reitwiessnerju za pregled.
- Distribucija vsebine in PR s pomočjo SEO. Okrepite se še danes.
- PlatoData.Network Vertical Generative Ai. Opolnomočite se. Dostopite tukaj.
- PlatoAiStream. Web3 Intelligence. Razširjeno znanje. Dostopite tukaj.
- PlatoESG. Ogljik, CleanTech, Energija, Okolje, sončna energija, Ravnanje z odpadki. Dostopite tukaj.
- PlatoHealth. Obveščanje o biotehnologiji in kliničnih preskušanjih. Dostopite tukaj.
- BlockOffsets. Posodobitev okoljskega offset lastništva. Dostopite tukaj.
- vir: Platonova podatkovna inteligenca.