Zk-SNARKs: aktualizovateľné nastavenia na blockchaine
Zk-SNARK sa osvedčili ako “švajčiarsky armádny nôž” pre blockchain a distribuované účtovné knihy s aplikáciami v oblasti ochrany súkromia, interoperability a škálovateľnosti
Od svojho zavedenia sa dôkazy nulovej znalosti (ZKP) používajú na podporu potenciálnych aplikácií od overiteľných externých výpočtov až po anonymné poverenia v rámci množstva nastavení, ktoré vyžadujú rovnováhu medzi súkromím a integritou. ZKP umožňujú jednej strane dokázať druhej strane, že určitý výrok alebo tvrdenie je pravdivé, bez toho, aby sa odhalil obsah tohto výroku. Aplikácia ZKP v rôznych prípadoch použitia v reťazci prispieva k riešeniu otázok ochrany súkromia, interoperability a škálovateľnosti.
V tomto príspevku sa pozrieme na rôzne typy ZKP a ich špecifické prípady použitia. Diskutujeme tiež o zk-SNARK, niektorých známych problémoch pri jeho použití a navrhujeme mechanizmus blockchainu s bezpečnými vlastnosťami za podmienok porovnateľných s protokolom blockchainu. Článok vychádza z výskumnej práce “Mining for Privacy: How to Bootstrap a Snarky Blockchain”, ktorú napísali Thomas Kerber, Aggelos Kiayias a Markulf Kohlweiss.
Rôzne typy ZKP
V prostredí blockchainu je bežné, že klienti sťahujú a overujú každú transakciu zverejnenú v sieti. To znamená, že pre praktické nasadenie zero-knowledge protokolov sú dôležité malé veľkosti dôkazov a rýchly čas overovania. Existuje niekoľko praktických schém, z ktorých si možno vybrať, s rozsiahlym priestorom kompromisov v oblasti výkonu a kryptografických predpokladov:
- Neinteraktívne argumenty nulovej znalosti (NIZK): ide o najvšeobecnejší koncept. NIZK môže byť neúplný, ale ako výhoda sa môže opierať o štandardné kryptografické predpoklady a často spĺňa silné bezpečnostné záruky.
- Súrodé neinteraktívne argumenty nulovej znalosti (SNARG): dosahujú súrodosť za cenu silnejších kryptografických predpokladov a často slabších bezpečnostných záruk.
- Súhrnné neinteraktívne argumenty nulovej znalosti (SNARK alebo niekedy zk-SNARK): ide o SNARG, ktoré sú zároveň dôkazmi znalosti a nulovej znalosti. Tento názov je populárny aj vďaka nonsensovej básni Lewisa Carrola “The Hunting of the Snark”.
- Súvislé transparentné argumenty znalostí (STARK): transparentné tu znamená, že nastavenie vyžaduje len dôveryhodnú hashovaciu funkciu. Je to výhodné, ale môže to byť spojené s výkonnostnou réžiou.
V súčasnosti je z pohľadu overovateľa najatraktívnejším systémom dokazovania (predspracovaný) stručný neinteraktívny argument znalostí, skrátene zk-SNARK, ktorý má malú konštantnú veľkosť dôkazu a náklady na overenie v konštantnom čase aj pre ľubovoľne veľké vzťahy. Zk-SNARK sa osvedčili ako “švajčiarsky armádny nôž” pre blockchain a distribuované účtovné knihy s aplikáciami v oblasti súkromia, interoperability a škálovateľnosti.
Prípady použitia
Prípady použitia zk-SNARK sú veľmi rozmanité. Niekedy sa SNARKy využívajú na zlepšenie výkonnosti a stručnosti vlastností systému. V iných prípadoch použitia sa zk-SNARK využívajú na zlepšenie súkromia. Niektoré prípady sú zmiešané, kde hrajú úlohu oba aspekty.
V prostredí blockchainu, pri zohľadnení výkonnosti a stručnosti, môžu zk-SNARKS výrazne prispieť k prípadom použitia, ako napr:
- ľahkí klienti: na zvýšenie efektívnosti parametrov a celkovej štruktúry aplikácií. Efektívne systémy dôkazov (bez požiadavky na nulovú znalosť) zohrávajú dôležitú úlohu pri zavádzaní ľahkých klientov. Rekurzívne dôkazové systémy sa tiež dobre hodia pre tento prípad použitia, aby sa zabezpečila bezpečnosť pre neobmedzenú rekurziu, ako aj použitie vonkajších funkcií (napríklad hashovacích funkcií) v rekurzívnych dôkazoch.
- Chytré kontrakty: na odľahčenie možného preťaženia účtovnej knihy z dôvodu verejného vykonávania inteligentných kontraktov. Kompilácia kódu na reťazci do SNARK s konštantným alebo logaritmickým časom overovania môže umožniť zložitejšie validátory.
- Dôkaz užitočnej práce (PoUW): SNARKy môžu byť kľúčom k overovaniu “užitočných výpočtov” vykonávaných baníkmi, ktorých validácia na reťazci by inak bola nákladná.
Z hľadiska ochrany súkromia mnohé aplikácie využívajú dôkazy nulovej znalosti na nasadenie bezpečných platobných riešení, výmenu opcií, správu identít, hlasovanie, aukcie, overiteľné štatistiky (forma blockchainového orákula) alebo motivovanú anonymnú komunikáciu. Medzi prípady použitia môžu patriť napr:
- Súkromné inteligentné zmluvy: SNARK sú neoddeliteľnou súčasťou súčasného návrhu súkromných inteligentných zmlúv. Prvoradé sú dve veci: univerzálnosť, aby sa podporili inteligentné zmluvy nasadené používateľmi, a jednoduchosť kompilácie. Expresivitu inteligentných kontraktov možno eliminovať, aby sa zmenšil problémový priestor, napríklad zakázaním neobmedzených cyklov a rekurzie, takže rekurzívna kompozícia SNARK nie je potrebná. V zásade možno do obvodu SNARK skompilovať určitú podmnožinu vysokoúrovňového zmluvného jazyka.
- Súkromné platby: aktíva možno považovať za osobitnú formu nároku na identitu, ktorá zahŕňa modelovanie nedostatku. Návrh súkromných platieb môže podporovať aj multi-assets a nefungujúce tokeny a spájať tieto tokeny s inteligentnými zmluvami.
- Správa identity: V kontexte overiteľných poverení môžu emitenti tvrdiť tvrdenia o subjektoch generovaním kryptografických objektov (poverení). Subjekty neskôr predkladajú svoje poverenia iným používateľom, ktorí vystupujú ako overovatelia. Overovatelia sú potom schopní overiť, že vydavateľ tvrdil tvrdenia o subjekte, ktorý predložil poverenie.
- Hlasovanie a pokladnica: Dôkazy ZK sa môžu použiť pri hlasovaní o pokladnici. Napríklad protokol treasury system for cryptocurrencies poskytuje schému hlasovania zachovávajúcu súkromie, kde sú hlasovacie lístky voličov zašifrované a neskôr sčítané pomocou homomorfných výpočtov. ZK dôkazy v pokladnici sú neinteraktívne Sigma protokoly založené na DLP, ktoré sa používajú na dokazovanie správnosti zašifrovaných správ v rôznych fázach protokolu (napr. že zašifrovaný hlasovací lístok voliča obsahuje správne zostavený hlasovací lístok).
Medzi zmiešané prípady použitia patria napr:
- Blockchain oracles: SNARK môžu znížiť náklady na overenie pri agregácii údajov z viacerých zdrojov a môžu znížiť veľkosť zverejnených údajov v reťazci tým, že namiesto všetkých dátových bodov obsahujú len agregovanú hodnotu a dôkaz. Na dosiahnutie týchto dvoch vlastností by strany mali byť schopné stručne dokázať znalosť podpisov na určitom počte dátových bodov, ako aj príslušný priemer/medián/variantu.
- Bočné reťazce: jeden reťazec v konfigurácii pripájania reťazcov môže pôsobiť ako ľahký klient voči druhému reťazcu, pričom overuje transakcie medzi reťazcami v druhom reťazci bez toho, aby musel overovať celý tento reťazec. Rozdiel je v tom, že toto pegging sa často udržiava dlhodobo, a tak sa dôkazy môžu poskytovať pravidelne a “aktualizovateľným” spôsobom. Viac informácií nájdete v časti Proof of stake Sidechains.
Známe problémy
Neinteraktívna nulová znalosť vyžaduje určitú zdieľanú náhodnosť alebo spoločný referenčný reťazec. Pre mnohé stručné systémy je potrebná silnejšia vlastnosť:
Nielenže je potrebná zdieľaná náhodná hodnota, ale musí dodržiavať špecifickú štruktúru. Štruktúrovaný referenčný reťazec (SRS) sa zvyčajne skladá zo súvisiacich skupinových prvkov, t. j.: gxi pre všetky i∈𝕫n.
Zrejmý spôsob výberu vzorky takéhoto referenčného reťazca z verejnej náhodnosti odhaľuje použité exponenty - a znalosť týchto hodnôt narúša spoľahlivosť samotného dôkazového systému. Aby to bolo ešte horšie, bezpečnosť týchto systémov sa zvyčajne spolieha (okrem iného) na znalosť exponentových predpokladov, ktoré hovoria, že na vytvorenie takto súvisiacich skupinových prvkov je potrebná znalosť základných exponentov, a preto každý vzorkovač SRS bude musieť “poznať” použité exponenty a byť dôveryhodný pri ich vymazávaní, čím sa v podstate stáva jediným bodom zlyhania základného systému.
Bezpečný výpočet s viacerými stranami (MPC) sa môže použiť a aj sa použil na zníženie dôveryhodnosti takéhoto procesu nastavenia. Výber účastníkov bezpečného výpočtu a overovanie generovania SRS protokolom MPC si však zachováva prvok centralizácie. Použitie MPC zostáva kontroverzným prvkom pri nastavovaní decentralizovaného systému, ktorý vyžaduje SNARK.
Riešenie otázok ochrany súkromia pri bezpečnom generovaní SRS
Aktualizovateľný štruktúrovaný referenčný reťazec (uSRS) možno bezpečne inicializovať pomocou distribuovanej účtovnej knihy tým, že sa od tvorcov blokov vyžaduje, aby počas počiatočného obdobia nastavenia vykonávali aktualizácie vyvíjajúceho sa uSRS. Po vyčkaní na dohodu o konečnom uSRS ho možno bezpečne používať.
Dôkaz tohto sa opiera o základný spôsob fungovania účtovných kníh typu Nakamoto: rôzni používatelia môžu rozšíriť reťazec blokov, ak dokážu splniť určitú podmienku, pričom táto podmienka je spojená s typom tvrdosti, ktorý zabezpečuje, že útočníci sú obmedzení v počte rozšírení, ktoré môžu vykonať. Vzhľadom na takúto štruktúru priradíme ku každému bloku aktualizáciu uSRS pred časom 𝛿1. Tento čas je zvolený tak, aby bezpečnostné vlastnosti účtovnej knihy zabezpečili, že v každom konkurenčnom reťazci je v tomto čase aspoň jeden z blokov poctivý.
To možno skonštruovať z funkcie účtovnej knihy s dodatočným stavom vedenia, ktorý je odvodený z informácií, ktoré baníci vkladajú do svojich blokov na zakódovanie aktualizácie uSRS. Toto je ponechané dostatočne všeobecné, aby umožnilo aj iné použitie. Základnou myšlienkou je ukázať, že účtovná kniha, ktorá vykonáva aktualizácie uSRS v stave vedenia, je ekvivalentná tej, ktorá ich nevykonáva, ale je sprevádzaná bezpečným uSRS. Po uplynutí času 𝛿1 používatelia čakajú ďalší časový úsek 𝛿2, kým spoločný prefix nezabezpečí, že sa všetky strany dohodnú na referenčnom reťazci.
Navrhovaná abstrakcia účtovnej knihy
Naša konštrukcia funkcionality aktualizovateľného štruktúrovaného referenčného reťazca sa opiera o vlastnosti spoločný prefix, kvalita reťazca a rast reťazca definované v analýze chrbtice Bitcoinu od Garaya a kol. pre konsenzuálne algoritmy v Nakamotovom štýle:
- spoločný prefix. Pri súčasných reťazcoch 𝛱1 a 𝛱2 dvoch strán a odstránení k blokov z prvého je prefixom druhého: 𝛱1⌊k ≺𝛱2.
- Existenciálna kvalita reťazca. Pre aktuálny reťazec ľubovoľnej strany 𝛱 budú všetky po sebe nasledujúce l bloky v tomto reťazci obsahovať aspoň jeden blok vytvorený poctivou stranou.
- Rast reťazca. Ak má reťazec strany dĺžku c, potom o s časových intervalov neskôr bude mať dĺžku aspoň c+𝛾.
Decentralizovaná konštrukcia uSRS
Nami navrhovaná konštrukcia, podrobne opísaná v článku Mining for Privacy, je jednoduchá: každý reťazec je spojený s konkrétnym uSRS a keď baník reťazec predĺži, dodatočne vykoná aktualizáciu uSRS. Pri vzniku reťazca sa môže použiť známa náhodnosť (alebo dokonca žiadna náhodnosť). Princíp tohto návrhu je jednoduchý: aktualizovateľnosť uSRS zaručuje, že ak sa jedna aktualizácia vykoná poctivo (s použitím skutočnej náhodnosti aj vymazaním tejto náhodnosti po vykonaní aktualizácie), výsledný uSRS sa môže bezpečne používať. Na zaručenie tohto sa spoliehame na vlastnosť existenčnej kvality reťazca - po vygenerovaní l blokov musí aspoň jeden z nich vytvoriť poctivý baník, a preto po l blokoch je uSRS reťazca bezpečný.
Nestačí však úplne vedieť, že referenčný reťazec konkrétneho reťazca je bezpečný - pre väčšinu praktických aplikácií chceme, aby sa všetci používatelia zhodli na referenčnom reťazci. To zabezpečuje vlastnosť spoločný prefix, ktorá zaručuje, že pre ľubovoľný reťazec dlhý l+k blokov budú mať všetci ostatní používatelia rovnaký referenčný reťazec ako ten, ktorý je generovaný týmto reťazcom - za predpokladu, že používatelia prestanú aktualizovať po l blokoch!
A nakoniec, rast reťazca zaručuje, že udalosť, ktorá nás zaujíma - keď sa všetci zhodnú na referenčnom reťazci - nakoniec nastane. Zaručuje, že používatelia budú mať nakoniec reťazec dĺžky l+k. Konkrétne, keďže každých s časových jednotiek sa generujú bloky, udalosť nastane najneskôr v čase ⌈(l+k)/s⌉.
To všetko je abstraktne dobre, ale ponecháva to otázky praktického využitia: takéto abstraktné analýzy predpokladajú, že aktualizácie sa dajú vytvoriť s malými alebo žiadnymi nákladmi a že neovplyvňujú štandardný postup ťažby. V prípade ťažby proof-of-work to však nie je celkom pravda:
- Aktualizácie sú relatívne nákladné, ich výpočet trvá 5 až 10 minút v závislosti od veľkosti cieľového uSRS.
- Aktualizácie je možné podvádzať, vykonávať ich rýchlejšie, ale bez pridania bezpečnosti referenčného reťazca.
V kombinácii tieto faktory predstavujú výzvu, najmä v nastavení proof-of-work, kde sa aktualizácia musí vykonať predtým, ako môže baník začať ťažiť blok. To zdržuje nepodvádzajúcich baníkov, zatiaľ čo ich podvádzajúci kolegovia už ťažia! V dôsledku toho by ťažobná obtiažnosť (zodpovedajúca zamýšľanému času medzi blokmi) nemala byť príliš nízka, pretože čím je nižšia, tým väčšie výhody má podvádzajúci baník. Na druhej strane, vysoká obtiažnosť prirodzene vedie k dlhšiemu času na dosiahnutie konsenzu. Tento kompromis je znázornený na obrázku 1.
Za predpokladu, že je obtiažnosť vhodne kalibrovaná, simulačná analýza ukazuje, že tento efekt nepoškodzuje celkovú bezpečnosť. V závislosti od pravdepodobnosti zlyhania (є), ktorú sme ochotní tolerovať, a od podielu ťažobnej sily útočníka (а), pred ktorým chceme chrániť, sa dá uSRS bezpečne vygenerovať pomocou postupu buď v priebehu niekoľkých hodín, alebo v priebehu niekoľkých mesiacov v pesimistickejšom scenári, ako je znázornené na obrázku 1.
Obrázok 1. Čas potrebný, kým je zaručená aspoň jedna poctivá aktualizácia, ako funkcia času cieľového bloku
Zdroj: “Mining for Privacy: How to Bootstrap a Snarky Blockchain” výskumný dokument.
Podobný problém nastáva aj pri uvažovaní o racionálnom správaní - ťažiarov, ktorí sa snažia len o zisk, sa budú snažiť podvádzať aj pri aktualizáciách, nie však zo zlého úmyslu, ale jednoducho preto, že ak to urobia, môžu vytvárať bloky rýchlejšie. Tento problém sa dá obísť dodatočným odmeňovaním dobrého správania - výberovú vzorku baníkov možno dodatočne požiadať, aby poskytli náhodnosť svojich aktualizácií a preukázali, že bola vybraná vhodným spôsobom (napríklad pomocou hašovacej funkcie). Ak sa im to podarí, môžu získať dodatočnú odmenu, ktorá vyváži prípadnú stratu z nepodvádzania.
Celkovo možno povedať, že použiteľnosť zk-SNARK výrazne prospieva rôznym prípadom použitia v reťazci, ktoré riešia otázky súkromia, interoperability a škálovateľnosti. Hoci sa zdá, že dôveryhodné nastavenie, ktoré sa vyžaduje pre mnohé zk-SNARKy, je v rozpore s decentralizovanou povahou distribuovaných účtovných kníh, v prípade SNARKov s aktualizovateľnými referenčnými reťazcami ho možno vykonať plne decentralizovaným spôsobom. Hoci v princípe je možné používať aj transparentné SNARKy, ako napríklad Halo, vyššie opísané techniky umožňujú, aby sa SNARKy, ako napríklad Plonk (ktoré môžu byť efektívnejšie v závislosti od okolností), spoliehajúce sa na aktualizovateľné referenčné reťazce, bezpečne používali aj pre aplikácie v reťazci - už neplatí, že nastavenia SNARKov sú príliš nepriehľadné na to, aby sa im dalo dôverovať, ak vôbec niekedy boli.
(Napísal Thomas Kerber) - preklad @Martin.M
Pôvodný článok: Zk-SNARKs: updatable setups on the blockchain - IOHK Blog