1. Introducere
ZK-SNARK este un sistem de dovezi criptografice care permite unei entități să demonstreze că ceva este adevărat fără a dezvălui alte informații.
ZK-SNARK-urile sunt utile în mai multe aplicații și domenii, cum ar fi blockchain și calculul verificabil. O aplicație blockchain notabilă este utilizată în ZK-Rollups.
ZK-Rollup-urile sunt blockchain-uri de strat al doilea construite peste alte blockchain-uri (cum ar fi Ethereum) care utilizează ZK-SNARK-uri (sau alte sisteme de dovezi criptografice) pentru a dovedi validitatea tranzițiilor de stare. Adică, de fiecare dată când se realizează o nouă actualizare a rețelei (se adaugă un nou lot de tranzacții), se calculează o nouă stare de rețea și se generează o dovadă a validității acestei stări. Ideea este că este necesară o singură entitate pentru a genera această dovadă și oricine poate avea încredere în validitatea ei.
Proprietățile dorite furnizate de ZK-Rollups sunt de obicei (i) scalabilitate și/sau (ii) protecția vieții private. ZK-Rollup-urile sunt uneori numite Rollup-uri de eficiență atunci când este necesară doar scalabilitate.
Pentru a calcula dovezi în ZK-Rollups concepute pentru a extinde EVM-ul Ethereum, poate fi utilizat ZK-EVM. Strict definit, ZK-EVM este un set de programe criptografice (circuite) responsabile pentru generarea de dovezi cu cunoștințe zero (ZKP), deși uneori, în mod colocvial, se referă și la totalitatea ZK-Rollup-urilor universale capabile de EVM.
2. Definiția ZK-SNARK
Un SNARK este o dovadă concisă că o anumită afirmație este adevărată. În mod formal, demonstrează cunoașterea urmei de execuție a unui algoritm care produce o soluție corectă la o problemă. Mai degrabă, demonstrează cunoașterea valorilor non-publice și non-constante care efectuează urmărirea. Aceste valori în ansamblu sunt adesea numite martori. Elementele martorului, adică părțile de intrare la algoritm, constituie martori independenți deoarece există înainte de execuția algoritmului și nu sunt determinate de alte elemente ale urmei de execuție. Valoarea publică neconstantă a urmei de execuție, care specifică instanța problemei pe care o rezolvă algoritmul, se numește declarație publică.
ZK-SNARK înseamnă Zero-Knowledge Succinct Non-Interactive Knowledge Argument.
S - Simplitate
Simplitate - dovada este „scurtă” iar timpul de verificare este „rapid”:
O dovadă „scurtă” înseamnă că dimensiunea probei este subliniară, raportată la dimensiunea martorului.
Timpul de verificare „rapid” înseamnă că timpul de funcționare al verificatorului ar trebui (i) să fie subliniar în dimensiunea martorului și (ii) să fie liniar în cererea publică.
Dar, de fapt, vrem să fie nu numai „concis”, ci și „nivel polinom log”.
Aceasta înseamnă că dimensiunea probei și timpul de verificare sunt aproape independente de mărimea martorului.
Demonstrați că dimensiunea lui π nu ar trebui să crească mai repede decât un multiplu constant al pătratului logaritmului mărimii martorului w (pentru w suficient de mare):
Mărimea dovezii depinde de protocolul specific ZK-SNARK. Pentru Plonky2 este O(log^2(|w|)), dar acesta este „cel mai rău” caz. De exemplu, pentru PLONK clasic și Groth16, dimensiunea demonstrației este O(1), care este o constantă.
Timpul de verificare t_v nu trebuie să fie mai mare de câteva ori constantă pătratul logaritmului martorului w și liniar în dimensiunea declarației publice x (x și w sunt suficient de mari atunci când doar unul dintre ele își schimbă dimensiunea).
N - Neinteractiv - Generarea dovezilor are loc fără a primi date de la verificator.
ARK - Knowledge Proof - Similar cu dovezile obișnuite, dar sunetul se ține numai împotriva doveditorilor mărginiți polinomial, în timp ce în dovezi sunetul se ține împotriva demonstratorilor nemărginiți din punct de vedere computațional. Vom discuta conceptul de sunet în secțiunea următoare.
ZK - Zero Knowledge - Nicio dezvăluire a martorilor.
3. Proprietățile ZK-SNARK-urilor
ZK-SNARK-urile au trei proprietăți principale, după cum este descris mai jos:
Completitudine: Dacă probatorul cunoaște traiectoria corectă de execuție a algoritmului, atunci verificatorul trebuie să creadă că probatorul are aceste cunoștințe.
Soliditatea cunoștințelor: cu excepția cazului în care probatorul cunoaște cu adevărat traiectoria de execuție corectă, probatorul nu poate convinge verificatorul că o știe, dar există o probabilitate foarte mică.
Zero-cunoștințe: verificatorul nu știe nimic despre traiectoria de execuție, cu excepția faptului că este corectă.
4.PLONKish ZK-SNARK proof sistem
4.1 Introducere în PLONKish ZK-SNARK și funcțiile acestora
Pentru a fi aplicat unui anumit algoritm, sistemul de demonstrare ZK-SNARK trebuie să cunoască sistemul de ecuații pe câmpul finit. Aceste ecuații descriu relația dintre valorile din tabelul de traiectorie de execuție a algoritmului. structura de date care stochează traiectoria de execuție) pentru a se asigura că calculul este Integritate. Limbajul folosit pentru a exprima acest sistem de ecuații (numit și sistem de constrângeri) se numește aritmetică.
Sistemul de verificare PLONKish ZK-SNARK folosește aritmetică cu o putere de expresie mai mare decât sistemele de dovezi mai vechi. Primul ne permite să folosim ecuații de sistem de constrângeri de formă polinomială arbitrară peste variabilele de constrângere, în timp ce pentru sistemele de demonstrare mai vechi (adică sisteme bazate pe R1CS) aceste ecuații au fost de forma polinoame liniare și pătratice. Această caracteristică face ca sistemul de verificare PLONKish ZK-SNARK să aibă un impact pozitiv asupra eficienței computaționale a probatorului și îl face mai ușor de aplicat la diverși algoritmi. Prin urmare, în ultimii ani au apărut multe sisteme de dovezi PLONKish ZK-SNARK, cum ar fi clasicul PLONK, Halo2, Kimchi, Plonky2, HyperPlonk etc.
În Taiko, folosim o variantă a sistemului de verificare Halo2 bazată pe schema de angajare polinomială KZG.
Sistemul de protecție PLONKish ZK-SNARK constă din trei componente:
4.2 Planul de angajament
Schema de promisiune permite unui committer să publice o valoare, numită promisiune, care leagă pe committer de un mesaj fără a dezvălui mesajul în sine. Autorul poate apoi deschide angajamentul și poate expune mesajul angajat, sau o parte din acesta, verificatorului, care poate verifica dacă informațiile expuse sunt în concordanță cu angajamentul.
Diferiți autori descriu un număr diferit de algoritmi care alcătuiesc o schemă de angajament. Cu toate acestea, ar trebui să menționăm cel puțin patru dintre acești algoritmi:
Configurare: ia ca intrare niște parametri inițiali și generează parametrii de configurare. Setările specifică (i) la ce ne angajăm (de exemplu, pentru schema de angajare polinomială unară, specificăm domeniul coeficientului și gradul maxim al polinomului la care ne angajăm) și (ii) nivelul de securitate în biți. Putem defini pur și simplu nivelul de securitate după cum urmează: Dacă este nevoie de O(2^n) timp pentru a sparge un sistem de criptare, atunci sistemul de criptare are un nivel de securitate de n biți.
Promisiune: O promisiune care generează mesaje pe baza unor parametri stabiliți.
Deschidere parțială: generează o dovadă de deschidere parțială specifică unei părți selectate a mesajului (de exemplu, valoarea unui polinom unar angajat pentru un parametru), precum și setarea parametrilor.
Validare: Folosiți o atestare parțial deschisă și setați parametrii pentru a verifica dacă informațiile expuse de către probator sunt partea specificată a mesajului corespunzătoare angajamentului specificat.
*Pentru unele scheme de angajare, algoritmii „de configurare” și „deschis” pot să nu existe (de exemplu, când se utilizează o funcție hash pentru a comite valori mari).
Planul de angajament trebuie să aibă următoarele caracteristici:
Legarea: Odată ce probatorul se angajează la un anumit mesaj, acesta va fi legat de mesajul la care sa angajat;
Ascundere: o promisiune de a nu dezvălui nicio informație despre mesaj. Ascunderea poate fi perfectă, adică o dovadă parțial deschisă nu dezvăluie nicio informație despre partea neinterogata a mesajului (de exemplu, angajamentul KZG) sau neperfectă, adică o dovadă parțial deschisă dezvăluie o parte din informațiile menționate mai sus (de exemplu, bazată pe FRI angajament polinom).
Schemele de angajament pot fi împărțite în mai multe tipuri în funcție de obiectul țintă: angajamentul de un singur element;
Schemele de angajament polinomial sunt singurul tip utilizat direct în sistemul de verificare PLONKish ZK-SNARK. Pentru sistemele de demonstrare de mai sus (cum ar fi clasicul PLONK, Halo2, Kimchi, Plonky2 etc.), schema de angajare polinomială univariată este foarte importantă. Cu toate acestea, există acum câteva metode noi PLONKish ZK-SNARK bazate pe scheme de angajare polinomiale multiliniare (de exemplu, HyperPlonk).
4.3 Oracle Proof interactiv
O dovadă interactivă a oracolului este o dovadă interactivă în care verificatorul are „acces la oracol” pentru a obține mesajele doveditorului, le poate interoga într-o manieră probabilistică și nu are nevoie să citească mesajele întregului doveditor.
4.4 Euristică Fiat-Shamir
Euristica Fiat-Shamir oferă o modalitate de a transforma argumentele interactive (monede publice) în argumente non-interactive. Intuitiv, ideea este de a înlocui provocarea aleatorie a validatorului cu hash-ul mesajului anterior, dar specificul este în general nespecificat.
*Public Coin Protocol este un protocol în care validatorii trimit doar elemente aleatorii.
4.5 Principiul de funcționare al sistemului de protecție ZK-SNARK în stil PLONK
În sistemul de verificare ZK-SNARK, este utilizată o metodă de demonstrare interactivă Oracle modificată pentru a dovedi cunoștințele martorului, care utilizează angajamente polinomiale pentru a oferi Oracle acces la mesajul probator și îl face fără interacțiune prin euristica Fiat-Shamir. În această secțiune, vom explica în detaliu constructorul dat.
Amintiți-vă că aplicarea sistemului de demonstrare ZK-SNARK la un algoritm necesită construirea unui sistem de constrângeri corespunzător. Pentru a-l putea construi, definim structura tabelului de urmărire a execuției algoritmului și valorile constante din acesta. Folosim termenul „circuit” pentru a ne referi la structura complexă a unui tabel de urmărire a execuției populat doar cu constante și sistemul de constrângeri corespunzător. Pentru a genera o dovadă ZK-SNARK pentru o instanță de execuție a unui algoritm, trebuie să sintetizăm o instanță de circuit pentru acesta, care este o instanță corespunzătoare a circuitului algoritmului și a tabelului de urmărire a execuției (adică, un tabel care specifică constante, martori, şi valorile declaraţiei publice) combinaţie.
Să luăm în considerare structura tabelului de urmărire utilizat de un sistem de verificare ZK-SNARK în stil PLONK. Toate coloanele dintr-un astfel de tabel aparțin unuia dintre cele trei tipuri, pe care le denumim conform terminologiei utilizate în Halo2 și le descriem după cum urmează:
Coloane fixe - celulele lor conțin constante din tabelul de urmărire a execuției;
Coloana Instanță - folosită pentru a stoca valorile declarațiilor publice;
Coloana de sugestii - unde sunt stocate toate datele martorilor (inclusiv valorile martorilor independente și rezultatele secrete calculate).
Pentru a rezuma, notăm următoarele:
Tabel de urmărire de execuție (tip PLONKish) = coloane fixe + coloane de instanță + coloane de sugestie = tabel de urmărire de execuție care conține doar constante + sistem de constrângere = circuit + martori în tabelul său + declarații publice: (Circuit; declarație publică, valoare martor independent) → Instanță de circuit Aplicați sistemul de verificare ZK-SNARK la un anumit algoritm = descrieți circuitul + definiți procesul de sinteză.
De ce este folosit pe scară largă termenul „circuit” în acest context? Inițial, când erau disponibile numai sistemele de dovezi ZK-SNARK bazate pe R1CS, era convenabil să se reprezinte sistemul de constrângeri sub forma unui circuit aritmetic, a cărui ieșire trebuie să fie zero. Credem că, în contextul SNARK-urilor PLONKish, termenul „circuit” este folosit din motive istorice. Oricum, să luăm în considerare pe scurt circuitul aritmetic folosit pentru versiunile mai vechi ale ZK-SNARK.
Circuitul aritmetic pentru SNARK-uri bazate pe R1CS definește un polinom n-variabil peste un câmp finit și are o schemă de evaluare. Inițial, este reprezentat ca un graf aciclic direcționat (DAG):
include:
Intrarea publică x, utilizată pentru a specifica valoarea declarației publice;
Intrarea secretă w, utilizată pentru a specifica valoarea martor independent;
Porți aritmetice utilizate pentru a specifica adunarea și înmulțirea pe câmpuri finite.
Să ne uităm la un exemplu de circuit aritmetic peste câmpul numerelor raționale.
Începem de jos și lucrăm cu cele mai joase porți din diagramă, adică (2 x 4 = 8) și (4 + 11 = 15), salvând aceste valori ca valori intermediare;
Apoi trecem cu un rând în sus (la al doilea rând) și calculăm suma celor două valori intermediare (pe care le-am obținut în etapa anterioară), care este (8 + 15 = 23);
Deoarece avem doar trei porți și le-am trecut pe toate, 23 este rezultatul final.
După ce sistemul de verificare PLONKish ZK-SNARK sintetizează instanța circuitului, coloanele fiecărei tabele de urmărire a execuției instanței sunt codificate ca polinoame peste câmpuri finite în felul următor. Să presupunem că C_j(x) este un polinom care descrie coloana j și ω este o rădăcină primitivă 2^k-th, unde k este ales astfel încât 2^k să fie puțin mai mare decât înălțimea inițială a instanței tabelului. Instanța tabelului este populată cu rânduri aleatorii (numai cu celule diferite de zero în coloanele sugerate) pentru a conține 2^k rânduri, iar C_j(ω^i) este setat la valoarea i-lea rând al j-lea. coloana instanței tabelului dat. Rolul umpluturii pentru atributele zero-cunoștințe va fi explicat mai târziu.
Afirmația „ω este o rădăcină primitivă 2^k-a” înseamnă că ω^(2^k) = 1 și avem ω^t ≠ 1 pentru orice număr întreg pozitiv t mai mic decât 2^k.
Sistemul de constrângeri este transformat în formă de ecuație polinomială prin înlocuirea variabilelor din acesta cu polinoamele corespunzătoare obținute din polinoamele coloanei, prin înlocuirea „x ori ω ridicat la o anumită putere” în locul lui x.
De exemplu, să considerăm ecuația sistemului de constrângeri s(i) * (a(i) * b(i) - c(i+1)) = 0. Înseamnă că dacă s(i) este diferit de zero, atunci a(i) * b(i) trebuie să fie egal cu c(i+1). Aici, a, b și c sunt coloanele sugerate, s este coloana fixă și i este numărul de rând curent.
Această constrângere poate fi aplicată tuturor celor 2^k rânduri după cum urmează. Fie S(x), A(x), B(x) și C(x) polinoame în coloanele a, b, c și respectiv s. Prin urmare, sperăm:
Aceasta înseamnă că toate elementele din această mulțime trebuie să fie rădăcini ale lui S(x) * (A(x) * B(x) - C(x * ω)). Prin urmare, acest polinom trebuie să fie divizibil cu:
Deoarece ω este o rădăcină primitivă de ordinul 2^k.
Z(x) = x^(2^k) - 1 se numește „polinom de dispariție” deoarece este 0 pentru toți x care sunt elemente ale grupului multiplicativ ciclic generat de ω. Prin urmare, S(x) * (A(x) * B(x) - C(x * ω)) mod Z(x) = 0 înseamnă că constrângerile de mai sus sunt valabile pentru toate cele 2^k rânduri.
Să presupunem că P_0(x), P_1(x), ... , P_m(x) sunt constrângeri aplicate tuturor celor 2^k rânduri și sunt consecvente cu polinomul S(x) * (A(x) * B(x) considerat de mai sus ) - C(x * ω)) are o formă similară. Dacă α este aleasă aleatoriu de către verificator din câmpul finit, atunci
Aceasta înseamnă că, cu o probabilitate extrem de mare, toate aceste constrângeri sunt îndeplinite pentru toate cele 2^k rânduri. Această ecuație înseamnă că putem găsi un polinom coeficient T(x) astfel încât
Prin urmare, pentru ca verificatorul să creadă că demonstratorul cunoaște conținutul tabelului de urmărire a execuției care satisface toate m constrângerile cu o probabilitate foarte mare, trebuie doar să se demonstreze că pentru un α selectat aleatoriu, demonstratorul are aparițiile P_0 (x), P_1(x ),..., polinoamele de coloană sugerate și polinoamele de coeficient T(x) în P_m(x) satisfac această ecuație polinomială. Verificatorul poate face acest lucru solicitând demonstratorului să găsească valoarea unui polinom dat într-un punct aleatoriu ales de verificator dintre punctele non-rădăcină ζ ale lui Z(x) și să evalueze ambele părți ale acelei ecuații în acel punct. ζ cred că probatorul cunoaște probabil aceste polinoame. Această metodă poate fi demonstrată prin lema Schwartz-Zippel.
Pentru ca generarea de dovezi să nu fie interactivă, toate valorile aleatorii generate de verificator în versiunea interactivă ar trebui să fie obținute folosind euristica Fiat-Shamir.
Pentru a lega demonstratorul de polinomul său propus și de polinomul coeficient T(x), se folosește o schemă de angajare polinomială. Dovatorul face angajamente pe aceste polinoame, deschide aceste angajamente la ζ (sau pe ζ * ω^q dacă o constrângere afectează rândurile i și i + q) și creează o dovadă care include (I) aceste angajamente, (II) Valoarea a polinomului la ζ (sau peste ζ * ω^q dacă este necesar) și (III) demonstrația deschisă corespunzătoare. De fapt, pentru a face demonstrația mai scurtă, utilizați deschiderea multiplă, adică generați o mică demonstrație pentru valorile tuturor punctelor polinomiale. Prin urmare, dovada este concisă.
Pentru a satisface proprietatea zero-cunoștințe, rândurile selectate aleatoriu de către probator sunt atașate instanței tabelului de urmărire a execuției, făcându-i înălțimea de 2^k rânduri. Aceste rânduri au numai celule diferite de zero în coloana de sugestii, deoarece numai coloana de sugestii conține datele pe care dorim să le ascundem. Faceți acest lucru înainte de a construi polinoamele coloanei de propunere, astfel încât numărul de perechi „valoarea parametrilor” dezvăluite în perioada de deschidere a angajamentului să fie mai mic decât numărul de perechi adăugate aleatoriu pentru fiecare polinom. Prin urmare, pentru fiecare polinom al coloanei de propunere, cantitatea de informații necesare pentru a o recupera după deschiderea angajamentului este mai mare decât cantitatea de informații despre martori. Această situație are ca rezultat zero cunoștințe.
În timpul fazei de preprocesare, toate instanțele circuitului de execuție efectuează unele dintre aceleași calcule, inclusiv stabilirea și calcularea polinoamelor de coloană fixă și angajamentele acestora pentru schema de angajare polinomială. Porțiunea de date produsă de aceste calcule este utilizată de verificator și este adesea numită cheie de verificare. În mod similar, conceptul de cheie de probă poate fi definit. Schema de angajament polinomială de bază determină dacă setările de încredere sunt făcute în timpul fazei de preprocesare.