1. Úvod
ZK-SNARK je kryptografický důkazní systém, který umožňuje subjektu prokázat, že je něco pravdivé, aniž by prozradil další informace.
ZK-SNARK jsou užitečné v mnoha aplikacích a oblastech, jako je blockchain a ověřitelné výpočty. V ZK-Rollups se používá jedna pozoruhodná blockchainová aplikace.
ZK-Rollups jsou blockchainy druhé vrstvy postavené na jiných blockchainech (jako je Ethereum), které využívají ZK-SNARK (nebo jiné kryptografické důkazní systémy) k prokázání platnosti stavových přechodů. To znamená, že při každé nové aktualizaci sítě (přidání nové dávky transakcí) se vypočítá nový stav sítě a vygeneruje se doklad o platnosti tohoto stavu. Jde o to, že k vygenerování tohoto důkazu je zapotřebí pouze jedna entita a kdokoli pak může věřit jeho platnosti.
Požadované vlastnosti poskytované ZK-Rollups jsou obvykle (i) škálovatelnost a/nebo (ii) ochrana soukromí. ZK-Rollups se někdy nazývají efektivita Rollups, když je vyžadována pouze škálovatelnost.
Pro výpočet důkazů v ZK-Rollups navržených pro rozšíření EVM Etherea lze použít ZK-EVM. Přísně definované ZK-EVM je sada kryptografických programů (obvodů) odpovědných za generování důkazů s nulovými znalostmi (ZKP), i když někdy hovorově také odkazuje na celek univerzálních ZK-Rollups schopných EVM.
2. Definice ZK-SNARK
SNARK je stručným důkazem, že určité tvrzení je pravdivé. Formálně prokazuje znalost průběhu provádění algoritmu, který vytváří správné řešení určitého problému. Spíše prokazuje znalost neveřejných a nekonstantních hodnot, které provádějí sledování. Tyto hodnoty jako celek jsou často nazývány svědky. Prvky svědka, tj. části vstupu do algoritmu, představují nezávislé svědky, protože existují před provedením algoritmu a nejsou určeny jinými prvky sledování provádění. Veřejná nekonstantní hodnota trasování provedení, která specifikuje instanci problému, kterou algoritmus řeší, se nazývá veřejný příkaz.
ZK-SNARK je zkratka pro Zero-Knowledge Succinct Non-Interactive Knowledge Argument.
S - Jednoduchost
Jednoduchost – důkaz je „krátký“ a doba ověření „rychlá“:
„Krátký“ důkaz znamená, že velikost důkazu je sublineární vzhledem k velikosti svědka.
"Rychlý" čas ověření znamená, že čas ověřovatele by měl (i) být sublineární ve velikosti svědka a (ii) být lineární ve veřejném tvrzení.
Ale ve skutečnosti chceme, aby to nebylo jen „výstižné“, ale také „log polynomiální úroveň“.
To znamená, že velikost důkazu a doba ověření jsou téměř nezávislé na velikosti svědka.
Dokažte, že velikost π by neměla růst rychleji než nějaké konstanty krát druhá mocnina logaritmu velikosti svědka w (pro dostatečně velké w):
Velikost nátisku závisí na konkrétním protokolu ZK-SNARK. Pro Plonky2 je to O(log^2(|w|)), ale to je ten "nejhorší" případ. Například pro klasické PLONK a Groth16 je velikost důkazu O(1), což je konstanta.
Ověřovací čas t_v by neměl být delší než několik konstant krát čtverec logaritmu svědka w a lineární ve velikosti veřejné deklarace x (x a w jsou dostatečně velké, když svou velikost změní pouze jeden z nich).
N – Neinteraktivní – Generování důkazu probíhá bez obdržení jakýchkoli dat od ověřovatele.
ARK - Knowledge Proof - Podobné jako běžné důkazy, ale zvuk platí pouze proti polynomiálně ohraničeným dokazovatelům, zatímco u důkazů zvuk platí proti výpočetně neomezeným dokazovatelům. Pojem zvuk probereme v další části.
ZK - Zero Knowledge - Žádné zveřejnění svědka.
3. Vlastnosti ZK-SNARKů
ZK-SNARK mají tři hlavní vlastnosti, jak je popsáno níže:
Úplnost: Pokud ověřovatel zná správnou trajektorii provádění algoritmu, musí ověřovatel věřit, že tuto znalost má.
Spolehlivost znalostí: Pokud ověřovatel skutečně nezná správnou trajektorii provádění, nemůže ověřovatele přesvědčit, že ji zná, ale existuje velmi malá pravděpodobnost.
Zero-knowledge: Ověřovatel neví nic o trajektorii provádění kromě toho, že je správná.
4. PLONKish ZK-SNARK proof systém
4.1 Úvod do PLONKish ZK-SNARK a jejich funkcí
Aby mohl být aplikován na určitý algoritmus, musí důkazní systém ZK-SNARK znát systém rovnic na konečném poli. Tyto rovnice popisují vztah mezi hodnotami v tabulce trajektorie provádění algoritmu (tzv. datová struktura, která ukládá trajektorii provádění), aby bylo zajištěno, že výpočet je integrita. Jazyk používaný k vyjádření tohoto systému rovnic (také nazývaného systém omezení) se nazývá aritmetika.
Nátiskový systém PLONKish ZK-SNARK využívá aritmetiku s vyšší vypovídací schopností než starší nátiskové systémy. První nám umožňuje použít rovnice omezovacího systému libovolného polynomického tvaru nad omezujícími proměnnými, zatímco pro starší důkazové systémy (tj. systémy založené na R1CS) byly tyto rovnice ve tvaru lineárních a kvadratických polynomů. Díky této vlastnosti má PLONKish ZK-SNARK proof systém pozitivní dopad na výpočetní efektivitu zkoušečky a usnadňuje aplikaci na různé algoritmy. Proto se v posledních letech objevilo mnoho PLONKish ZK-SNARK proof systémů, jako jsou klasické PLONK, Halo2, Kimchi, Plonky2, HyperPlonk atd.
V Taiko používáme variantu systému Halo2 proof založenou na schématu KZG polynomiálního závazku.
Ochranný systém PLONKish ZK-SNARK se skládá ze tří komponent:
4.2 Plán závazků
Schéma slibu umožňuje zadavateli zveřejnit hodnotu zvanou slib, která váže zadavatele ke zprávě, aniž by odhalil samotnou zprávu. Pověřenec pak může otevřít závazek a vystavit potvrzenou zprávu nebo její část ověřovateli, který může zkontrolovat, zda jsou vystavené informace v souladu se závazkem.
Různí autoři popisují různý počet algoritmů, které tvoří schéma závazků. Měli bychom však zmínit alespoň čtyři z těchto algoritmů:
Nastavení: vezme některé počáteční parametry jako vstup a vygeneruje parametry nastavení. Nastavení specifikují (i) k čemu se zavazujeme (např. pro schéma jednočlenného polynomu zadáváme doménu koeficientů a maximální stupeň polynomu, ke kterému se zavazujeme), a (ii) úroveň zabezpečení v bitech. Úroveň zabezpečení můžeme jednoduše definovat následovně: Pokud prolomení šifrovacího systému trvá O(2^n) čas, pak má šifrovací systém úroveň zabezpečení n bitů.
Promise: Slib, který generuje zprávy na základě nastavených parametrů.
Částečné otevření: Vygeneruje důkaz částečného otevření specifický pro vybranou část zprávy (např. hodnota potvrzeného unárního polynomu pro některý parametr), stejně jako nastavení parametrů.
Validace: Použijte částečně otevřenou atestaci a nastavte parametry ke kontrole, zda informace vystavené prokazatelem jsou specifikovanou částí zprávy odpovídající zadanému závazku.
*U některých schémat potvrzení nemusí existovat algoritmy „nastavení“ a „otevření“ (například při použití hašovací funkce k potvrzení velkých hodnot).
Plán závazků by měl mít tyto vlastnosti:
Vazba: Jakmile se prover zaváže ke konkrétní zprávě, bude vázán na zprávu, ke které se zavázal;
Skrytí: Slib, že neprozradí žádné informace o zprávě. Skrytí může být dokonalé, to znamená, že částečně otevřený důkaz neodhalí žádné informace o nevyžádané části zprávy (např. závazek KZG), nebo nedokonalý, tj. částečně otevřený důkaz odhalí část výše uvedených informací (např. polynomiální závazek).
Schémata závazků lze rozdělit do několika typů podle cílového objektu: závazek s jedním prvkem;
Polynomiální závazková schémata jsou jediným typem přímo používaným v systému PLONKish ZK-SNARK. Pro výše uvedené důkazové systémy (jako klasický PLONK, Halo2, Kimchi, Plonky2 atd.) je schéma jednorozměrného polynomu velmi důležité. Nyní však existují některé nové metody PLONKish ZK-SNARK založené na schématech multilineárních polynomů (např. HyperPlonk).
4.3 Interaktivní Oracle Proof
Interaktivní důkaz věštce je interaktivní důkaz, ve kterém má ověřovatel „přístup k věštci“, aby získal zprávy zkoušejícího, může se na ně dotazovat pravděpodobnostním způsobem a nemusí číst zprávy celého zkoušeče.
4.4 Heuristika Fiat-Shamir
Heuristika Fiat-Shamir poskytuje způsob, jak transformovat (veřejné mince) interaktivní argumenty na argumenty neinteraktivní. Intuitivně je myšlenkou nahradit náhodnou výzvu validátoru hashem předchozí zprávy, ale specifika obecně nejsou specifikována.
*Public Coin Protocol je protokol, kde validátoři odesílají pouze náhodné prvky.
4.5 Princip fungování systému ZK-SNARK ve stylu PLONK
V systému důkazu ZK-SNARK se k prokázání znalostí svědka používá upravená interaktivní metoda důkazu Oracle, která využívá polynomiální závazky k poskytnutí přístupu Oracle ke zprávě dokazovatele a díky heuristice Fiat-Shamir je bez interakce. V této části si daný konstruktor podrobně vysvětlíme.
Připomeňme, že použití důkazního systému ZK-SNARK na algoritmus vyžaduje vytvoření odpovídajícího omezovacího systému. Abychom jej mohli sestavit, definujeme strukturu tabulky sledování provádění algoritmu a konstantní hodnoty v ní. Termín "obvod" používáme k označení složité struktury tabulky trasování provádění naplněné pouze konstantami a odpovídajícím systémem omezení. Abychom vygenerovali důkaz ZK-SNARK pro instanci provedení algoritmu, musíme pro něj syntetizovat instanci obvodu, která je odpovídající instancí obvodu algoritmu a tabulky trasování provedení (tj. tabulka, která specifikuje konstanty, svědky, a veřejné deklarační hodnoty).
Podívejme se na strukturu sledovacího stolu používaného systémem ZK-SNARK ve stylu PLONK. Všechny sloupce v takové tabulce patří do jednoho ze tří typů, které pojmenujeme podle terminologie používané v Halo2 a popíšeme je takto:
Pevné sloupce - jejich buňky obsahují konstanty z tabulky sledování provádění;
Sloupec instance – slouží k ukládání hodnot veřejné deklarace;
Sloupec Návrh – kde jsou uložena všechna data svědků (včetně hodnot nezávislých svědků a vypočítaných tajných výsledků).
Abychom to shrnuli, poznamenáváme následující:
Tabulka sledování provedení (typ PLONKish) = pevné sloupce + sloupce instance + sloupce návrhu okruh = tabulka sledování provedení obsahující pouze konstanty + omezující systém instance = okruh + svědci ve své tabulce Složení: (Circuit, veřejné prohlášení, hodnota nezávislého svědka) → Instance obvodu Aplikujte důkazní systém ZK-SNARK na určitý algoritmus = popište obvod + definujte proces syntézy.
Proč je v této souvislosti široce používán termín „obvod“? Zpočátku, když byly k dispozici pouze důkazové systémy ZK-SNARK založené na R1CS, bylo vhodné reprezentovat omezovací systém ve formě aritmetického obvodu, jehož výstup musí být nulový. Domníváme se, že v kontextu PLONKish SNARKs je termín „okruh“ používán z historických důvodů. Každopádně se krátce zamysleme nad aritmetickým obvodem používaným u starších verzí ZK-SNARK.
Aritmetický obvod pro SNARK na bázi R1CS definuje n-proměnný polynom nad konečným polem a má vyhodnocovací schéma. Zpočátku je reprezentován jako směrovaný acyklický graf (DAG):
to zahrnuje:
Veřejný vstup x, který se používá k určení hodnoty veřejné deklarace;
Tajný vstup w, používaný k určení hodnoty nezávislého svědka;
Aritmetické brány používané k určení sčítání a násobení přes konečná pole.
Podívejme se na příklad aritmetického obvodu nad oborem racionálních čísel.
Začneme zdola a pracujeme s nejnižšími hradly v diagramu, tj. (2 x 4 = 8) a (4 + 11 = 15), přičemž tyto hodnoty uložíme jako mezihodnoty;
Poté se posuneme o řádek nahoru (do druhého řádku) a vypočítáme součet dvou mezihodnot (které jsme získali v předchozí fázi), což je (8 + 15 = 23);
Protože máme jen tři brány a prošli jsme je všemi, je 23 náš konečný výstup.
Poté, co zkušební systém PLONKish ZK-SNARK syntetizuje instanci obvodu, jsou sloupce každé tabulky trasování provedení instance zakódovány jako polynomy nad konečnými poli následujícím způsobem. Předpokládejme, že C_j(x) je polynom popisující sloupec j a ω je primitivní kořen 2^k-tý, kde k je zvoleno tak, že 2^k je o něco větší než počáteční výška instance tabulky. Instance tabulky je vyplněna náhodnými řádky (pouze nenulovými buňkami v navrhovaných sloupcích), aby obsahovala 2^k řádků, a C_j(ω^i) je nastaveno na hodnotu i-tého řádku j-tého sloupec dané instance tabulky . Role výplně pro atributy s nulovými znalostmi bude vysvětlena později.
Výrok "ω je primitivní kořen 2^k-tý" znamená, že ω^(2^k) = 1 a máme ω^t ≠ 1 pro jakékoli kladné celé číslo t menší než 2^k.
Systém omezení je převeden do tvaru polynomiální rovnice nahrazením proměnných v něm odpovídajícími polynomy získanými ze sloupcových polynomů, dosazením "x krát ω umocněno na nějakou mocninu" místo x.
Uvažujme například rovnici omezovacího systému s(i) * (a(i) * b(i) - c(i+1)) = 0. Znamená to, že pokud s(i) je nenulové, pak a(i) * b(i) se musí rovnat c(i+1). Zde jsou a, b a c navrhované sloupce, s je pevný sloupec a i je číslo aktuálního řádku.
Toto omezení lze aplikovat na všechny 2^k řádky následovně. Nechť S(x), A(x), B(x) a C(x) jsou polynomy ve sloupcích a, b, c a s. Proto doufáme:
To znamená, že všechny prvky v této množině musí být kořeny S(x) * (A(x) * B(x) - C(x * ω)). Proto musí být tento polynom dělitelný:
Protože ω je primitivní kořen řádu 2^k.
Z(x) = x^(2^k) - 1 se nazývá "mizející polynom", protože je 0 pro všechna x, která jsou prvky cyklické multiplikativní grupy generované ω. Proto S(x) * (A(x) * B(x) - C(x * ω)) mod Z(x) = 0 znamená, že výše uvedená omezení platí pro všech 2^k řádků.
Předpokládejme, že P_0(x), P_1(x), ..., P_m(x) jsou omezení aplikovaná na všech 2^k řádků a jsou konzistentní s polynomem S(x) * (A(x) * B(x) uvažovaným výše ) - C(x * ω)) má podobný tvar. Pokud α náhodně vybere ověřovatel z konečného pole, pak
To znamená, že s extrémně vysokou pravděpodobností jsou všechna tato omezení splněna pro všechny 2^k řádky. Tato rovnice znamená, že můžeme najít kvocientový polynom T(x) takový, že
Proto, aby se ověřovatel domníval, že dokazovatel zná obsah tabulky trasování provedení, která s velkou pravděpodobností splňuje všech m omezení, stačí dokázat, že pro náhodně vybrané α má dokazovatel výskytů P_0 (x), P_1(x),..., navrhované sloupcové polynomy a kvocientové polynomy T(x) v P_m(x) splňují tuto polynomickou rovnici. Ověřovatel to může udělat tak, že požádá dokazovatele, aby našel hodnotu daného polynomu v náhodném bodě zvoleném ověřovatelem z nekořenových bodů ζ Z(x), a aby v tomto bodě vyhodnotil obě strany této rovnice. ζ. Domnívám se, že dokazovatel tyto polynomy pravděpodobně zná. Tuto metodu lze dokázat Schwartz-Zippelovým lemmatem.
Aby bylo generování důkazů neinteraktivní, měly by být všechny náhodné hodnoty generované ověřovatelem v interaktivní verzi získány pomocí heuristiky Fiat-Shamir.
K navázání dokazu na jeho návrhový polynom a kvocientový polynom T(x) se používá schéma polynomického závazku. Ověřovatel učiní závazky na tyto polynomy, otevře tyto závazky na ζ (nebo na ζ * ω^q, pokud nějaké omezení ovlivňuje řádky i a i + q), a vytvoří důkaz, který zahrnuje (I) tyto závazky, (II) Hodnota polynomu na ζ (nebo nad ζ * ω^q v případě potřeby) a (III) odpovídající otevřený důkaz. Ve skutečnosti, aby byl důkaz kratší, použijte vícenásobné otevření, tj. vygenerujte malý důkaz pro hodnoty všech bodů polynomu. Proto je důkaz stručný.
Aby byla splněna vlastnost zero-knowledge, náhodně vybrané řádky proverem jsou připojeny k instanci tabulky trasování provádění, takže její výška činí 2^k řádků. Tyto řádky obsahují pouze nenulové buňky ve sloupci návrhu, protože pouze sloupec návrhu obsahuje data, která chceme skrýt. Udělejte to před vytvořením polynomů sloupce nabídky tak, aby počet párů "hodnoty parametru" odhalených během období otevírání závazku byl menší než počet náhodně přidaných párů pro každý polynom. Proto je pro každý polynom sloupce návrhu množství informací požadovaných k jeho obnovení po otevření závazku větší než množství svědeckých informací. Tato situace má za následek nulové znalosti.
Během fáze předběžného zpracování provádějí všechny instance prováděcího obvodu některé ze stejných výpočtů, včetně nastavení a výpočtu polynomů s pevným sloupcem a jejich závazků pro schéma vázaných polynomů. Část dat vytvořená těmito výpočty je používána ověřovatelem a často se nazývá ověřovací klíč. Podobně lze definovat koncept kontrolního klíče. Základní schéma polynomiálního závazku určuje, zda jsou nastavení důvěryhodnosti provedena během fáze předběžného zpracování.