Zero Knowledge Canon

Opomba urednika: a16z crypto je imel dolg niz "pištole”, od našega DAO Canon lani našim NFT Canon prej (in pred tem naš original Kripto Canon) — obvezno se prijavite na naše tedensko glasilo web3 za več posodobitev in druge izbrane vire.

Torej bspodaj, izbrali smo nabor virov za tiste, ki želijo razumeti, se poglobiti in graditi z vsemi stvarmi nič znanja: zmogljive, temeljne tehnologije, ki imajo ključ do razširljivosti verige blokov in predstavljajo prihodnost aplikacij za ohranjanje zasebnosti ter nešteto drugih inovacij, ki prihajajo. Če imate predloge za visokokakovostne kose, ki bi jih lahko dodali, nam to sporočite @a16zcrypto.

Dokazni sistemi z ničelnim znanjem obstajajo že desetletja: njihova uvedba s strani Shafija Goldwasserja, Silvia Micalija in Charlesa Rackoffa leta 1985 je imela preobrazbeni učinek na področju kriptografije in je bila priznana z nagrado ACM Turing, ki jo je prejela Goldwasser in Micali leta 2012. Ker je to delo – vključno z njegovim prehodom od teorije k praksi in današnjim aplikacijam v crypto/web3 – nastajalo desetletja, v naši seriji kanonov prvič delimo tudi drugi del (zaenkrat vključen tukaj spodaj): bralni seznam z opombami Justin Thaler, ki sledi prvemu delu spodaj.

Zahvala: Hvala tudi Michaelu Blau, Samu Ragsdaleu in Timu Roughgardnu.

Temelji, ozadje, razvoj

Nekateri od teh prispevkov so tudi bolj o kriptografiji na splošno (ne samo o ničelnem znanju), vključno z orisom težav ali ključnih napredkov, ki jih danes obravnavajo dokazila o ničelnem znanju: kako zagotoviti zasebnost in avtentikacijo v odprtih omrežjih.

Nove smeri v kriptografiji (1976)
avtorja Whitfield Diffie in Martin Hellman
https://ee.stanford.edu/~hellman/publications/24.pdf

Metoda za pridobivanje digitalnih podpisov in kriptosistemov z javnimi ključi
od Ronald Rivest, Adi Shamir, Leonard Adelman
https://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=856E21BC2F75800D37FD611032C30B9C?doi=10.1.1.40.5588&rep=rep1&type=pdf

Protokoli za kriptosisteme z javnimi ključi (1980)
avtor Ralph Merkle
http://www.merkle.com/papers/Protocols.pdf

Varna komunikacija po nevarnih kanalih (1978)
avtor Ralph Merkle
https://www.merkle.com/1974/PuzzlesAsPublished.pdf

Uporaba eliptičnih krivulj v kriptografiji (1988)
avtorja Victor Miller
https://link.springer.com/content/pdf/10.1007%2F3-540-39799-X_31.pdf

Kompleksnost znanja interaktivnih dokaznih sistemov (1985)
od Shafi Goldwasser, Silvio Micali, Charles Rackof
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.419.8132&rep=rep1&type=pdf

Računalniško zanesljivi dokazi (2000)
avtorja Silvio Micali
https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/Computationally_Sound_Proofs.pdf

Od izločljive odpornosti proti trkom do jedrnatih neinteraktivnih argumentov znanja [SNARK] in spet nazaj (2011)
od Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer
https://eprint.iacr.org/2011/443.pdf

Učinkovit argument brez znanja za pravilnost mešanja (2012)
avtorja Stephanie Bayer in Jens Groth
http://www0.cs.ucl.ac.uk/staff/J.Groth/MinimalShuffle.pdf

Jedrnato neinteraktivno nič znanja za von Neumannovo arhitekturo (2013)
avtorji Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer in Madars Virza
https://eprint.iacr.org/2013/879.pdf

Razširljiva, pregledna in postkvantno varna računalniška celovitost (2018)
od Eli Ben-Sasson, Iddo Bentov, Yinon Horesh in Michael Riabzev
https://eprint.iacr.org/2018/046.pdf

Argumenti z ničelnim znanjem javnega kovanca s (skoraj) minimalnimi stroški časa in prostora (2020)
od Alexander Block, Justin Holmgren, Alon Rosen, Ron Rothblum in Pratik Soni
https://www.iacr.org/cryptodb/data/paper.php?pubkey=30645

Pregledi in predstavitve

Dokazi, argumenti in ničelno znanje — Pregled preverljivega računalništva ter interaktivnih dokazov in argumentov, kriptografskih protokolov, ki dokazovalcu omogočajo, da preveritelju zagotovi jamstvo, da je preverjalnik izvedel zahtevano računanje pravilno, vključno z ničelnim znanjem (kjer dokazila ne razkrijejo nobenih informacij razen lastne veljavnosti) . Zk argumenti imajo nešteto aplikacij v kriptografiji in so v zadnjem desetletju naredili skok iz teorije v prakso.
avtorja Justin Thaler
https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf

Razvoj modelov za dokaze brez znanja — Pregled dokazov brez znanja, kjer Meiklejohn (University College London, Google) obravnava aplikacije, ki poganjajo njihov razvoj, različne modele, ki so se pojavili za zajemanje teh novih interakcij, konstrukcije, ki jih lahko dosežemo, in delo ostalo storiti.
avtorja Sarah Meiklejohn
https://www.youtube.com/watch?v=HO97kVMI3SE

ZK table seje — uvodni moduli
z Danom Bonehom idr
https://zkhack.dev/whiteboard/

Varnost in zasebnost za kripto z zkps — pionirsko uvajanje dokazov brez znanja v praksi; kaj so zkps in kako delujejo ... vključno z "predstavitvijo" v živo
avtorja Zooko Wilcox
https://a16z.com/2019/08/29/security-and-privacy-for-crypto-with-zero-knowledge-proofs/

Najboljše tehnološke teme, razložene — vključno z opredelitvami in posledicami ničelnega znanja na splošno
od Joe Bonneau, Tim Roughgarden, Scott Kominers, Ali Yahya, Chris Dixon
https://web3-with-a16z.simplecast.com/episodes/hot-research-summer-blockchain-crypto-tech-topics-explainers-overviews-seminar-videos

Kako bo prihajajoči sloj zasebnosti popravil pokvarjen splet
avtorja Howard Wu
https://future.com/a-privacy-layer-for-the-web-can-change-everything/

Uvod v zkSNARKs
s Howardom Wujem, Anno Rose
https://zeroknowledge.fm/38-2/

Zakaj in kako zk-SNARK deluje: dokončna razlaga
avtorja Maksym Petkus
https://arxiv.org/pdf/1906.07221.pdf

Uvod v dokaze brez znanja
avtorja Fredrik Harrysson in Anna Rose
https://www.zeroknowledge.fm/21 [+ zapis povzetka drugje tukaj]

Zk-SNARKs: pod pokrovom
avtorja Vitalik Buterin
https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
del 1, del 2, del 3

Decentralizirana hitrost — o napredku v dokazih brez znanja, decentralizirani strojni opremi
avtorja Elena Burger
https://a16z.com/2022/04/15/zero-knowledge-proofs-hardware-decentralization-innovation/

Vrhunska zk raziskava — z raziskovalcem zk pri Ethereum Foundation
z Mary Maller, Anno Rose, Kobijem Gurkanom
https://zeroknowledge.fm/232-2/

Raziskovanje raziskav zk — z direktorjem raziskav pri DFINITY; tudi za napredki, kot je Groth16
z Jensom Grothom, Anno Rose, Kobijem Gurkanom
https://zeroknowledge.fm/237-2/

SNARK raziskovanje in pedagogika — z enim od soustanoviteljev ZCash in Starkware
z Alessandro Chiesa, Anna Rose
https://zeroknowledge.fm/episode-200-snark-research-pedagogy-with-alessandro-chiesa/

Globoki potopi, gradbeni vodniki

Temelji verjetnostnih dokazov — tečaj s 5 enotami iz interaktivnih dokazov in več
avtorja Alessandro Chiesa
https://www.youtube.com/playlist?list=PLGkwtcB-DfpzST-medFVvrKhinZisfluC

STARKi — del I, II, III
avtorja Vitalik Buterin
https://vitalik.ca/general/2017/11/09/starks_part_1.html
https://vitalik.ca/general/2017/11/22/starks_part_2.html
https://vitalik.ca/general/2018/07/21/starks_part_3.html

Anatomija STARKA — šestdelna vadnica, ki razlaga mehaniko dokaznega sistema STARK
avtorja Alan Szepieniec
https://aszepieniec.github.io/stark-anatomy/

SNARK design, 1. del — anketa, uporaba v zbiranjih, več
avtorja Justin Thaler
https://www.youtube.com/watch?v=tg6lKPdR_e4

SNARK design, 2. del — zbiranje, zmogljivost, varnost
avtorja Justin Thaler
https://www.youtube.com/watch?v=cMAI7g3UcoI

Merjenje zmogljivosti SNARK — čelni deli, zaledja, več
avtorja Justin Thaler
https://a16zcrypto.com/measuring-snark-performance-frontends-backends-and-the-future/

Razumevanje PLONK
https://vitalik.ca/general/2019/09/22/plonk.html

Sistem brez znanja PLONK — serija 12 kratkih videov o delovanju PLONK
avtorja David Wong
https://www.youtube.com/playlist?list=PLBJMt6zV1c7Gh9Utg-Vng2V6EYVidTFCC

Od AIR do RAP — kako deluje aritmetizacija v slogu PLONK
avtorja Ariel Gabizon
https://hackmd.io/@aztec-network/plonk-arithmetiization-air

Multiset preverja v PLONK in Plookup
avtorja Ariel Gabizon
https://hackmd.io/@arielg/ByFgSDA7D

Dizajn Halo2 — iz ECC
https://zcash.github.io/halo2/design.html

Plonky2
https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf

Aplikacije in vadnice: dokaz konceptov, predstavitve, orodja, več

Uporabljeno zk — učni viri
avtor 0xPARC
https://learn.0xparc.org/materials/intro

Spletno razvojno okolje za zkSNARKs — zkREPL, nov nabor orodij za interakcijo z naborom orodij Circom v brskalniku
avtorja Kevin Kwok
https://zkrepl.dev (+ razlagalna nit tukaj)

Kvadratni aritmetični programi od nič do junaka
avtorja Vitalik Buterin
https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

Na zkEVM
z Alexom Gluchowskim in Anno Rose
https://zeroknowledge.fm/175-2/

Različne vrste zkEVM
avtorja Vitalik Buterin
https://vitalik.ca/general/2022/08/04/zkevm.html

ZK strojno učenje — vadnica in predstavitev za vstavljanje nevronske mreže v SNARK
avtorji Horace Pan, Francis Ho in Henri Palacci
https://0xparc.org/blog/zk-mnist

Na jezikih ZK
z Alexom Ozdemirjem in Anno Rose
https://zeroknowledge.fm/172-2/

Dark Forest — uporaba zk kriptografije v igrah — popolnoma decentralizirana in obstojna igra RTS (strategija v realnem času).
https://blog.zkga.me/announcing-darkforest

ZKP za inženirje — pogled na ZKP-je Dark Forest
https://blog.zkga.me/df-init-circuit

Potop v nič znanja
z Elena Nadolinkski, Anna Rose, James Prestwich
https://zeroknowledge.fm/182-2/

zkDocs: izmenjava informacij brez znanja
avtorja Sam Ragsdale in Dan Boneh
https://a16zcrypto.com/zkdocs-zero-knowledge-information-sharing/

Kripto airdrops, ki ščitijo zasebnost, z dokazi brez znanja
avtorja Sam Ragsdale
https://a16z.com/2022/03/27/crypto-airdrop-privacy-tool-zero-knowledge-proofs/

Ceremonije zaupanja vredne nastavitve v verigi -
avtorja Valeria Nikolaenko in Sam Ragsdale
https://a16zcrypto.com/on-chain-trusted-setup-ceremony/

Kripto predpisi, nedovoljene finance, zasebnost in drugo – vključuje razdelek o ničelnem znanju v kontekstu predpisov/skladnosti; razlika med tehnologijami, ki ohranjajo zasebnost, in tehnologijami, ki zakrivajo
z Michele Korver, Jai Ramaswamy, Sonal Chokshi
https://web3-with-a16z.simplecast.com/episodes/crypto-regulations-sanctions-compliance-aml-ofac-news-explained

Drugi viri

zkMesh glasilo — mesečno glasilo, ki deli najnovejše informacije o decentraliziranih tehnologijah za ohranjanje zasebnosti, razvoju protokolov za zasebnost in sistemih brez znanja
https://zkmesh.substack.com/

Podcast Zero Knowledge — o najnovejših raziskavah zk in aplikacijah zk ter strokovnjakih, ki gradijo tehnologijo zasebnosti, ki podpira kriptografijo
z Anno Rose
https://zeroknowledge.fm/

… seznam branja s pripombami, po temah in kronologiji, avtor Justin Thaler:

SNARK-ji iz linearnih PCP-jev (tudi SNARK-i z nastavitvijo za specifično vezje)

Učinkoviti argumenti brez kratkih PCP (2007)
avtorji Yuval Ishai, Eyal Kushilevitz in Rafail Ostrovsky

Pred približno letom 2007 so bili SNARK-i zasnovani predvsem prek Kilian-micali paradigmo, vzeti "kratek" verjetnostno preverljiv dokaz (PCP) in ga "kriptografsko sestaviti" v jedrnat argument prek zgoščevanja Merkle in Fiat-Shamirjeve transformacije. Na žalost so kratki PCP še danes zapleteni in nepraktični. Ta dokument (IKO) je pokazal, kako uporabiti homomorfno šifriranje za pridobitev jedrnatih (nepreglednih) interaktivnih argumentov iz "dolgih, a strukturiranih" PCP-jev. Ti so lahko veliko enostavnejši od kratkih PCP-jev, nastali SNARK pa imajo veliko krajša dokazila in hitrejše preverjanje. Ti argumenti so bili najprej prepoznani kot potencial za praktično učinkovitost ter so bili izboljšani in implementirani v Pepper. Na žalost imajo IKO-jevi argumenti preverjalnik kvadratnega časa in strukturiran referenčni niz kvadratne velikosti, zato niso primerni za velike izračune.

Programi kvadratnega razpona in jedrnati NIZK brez PCP (2012)
Rosario Gennaro, Craig Gentry, Bryan Parno in Mariana Raykova

Ta prelomni dokument (GGPR) je zmanjšal stroške dokazovalnika IKO-jevega pristopa s kvadratne velikosti vezja na kvazilinearno. Na podlagi prejšnjega dela Groth in Lipmaa, je dal tudi SNARK prek kriptografije, ki temelji na združevanju, namesto interaktivnih argumentov, kot je IKO. Svoje SNARK-je je opisal v kontekstu tega, kar se zdaj imenuje problemi zadovoljevanja omejitev ranga 1 (R1CS), posplošitev zadovoljivosti aritmetičnega vezja.

Ta članek je služil tudi kot teoretična podlaga za prve SNARK-e, ki so bili komercialno uporabljeni (npr. v ZCash) in je neposredno vodil do SNARK-ov, ki so še danes priljubljeni (npr. Groth16). Prišle so začetne izvedbe argumentov GGPR Zaatar in Ostržekin poznejše različice vključujejo SNARK za C in BCTV. BCIOP podal splošen okvir, ki pojasnjuje te transformacije linearnih PCP-jev v SNARK (glejte tudi Dodatek A k Zaatar) in opisuje različne primere tega.

O velikosti neinteraktivnih argumentov, ki temeljijo na seznanjanju (2016)
avtorja Jens Groth

Ta članek, pogovorno imenovan Groth16, je predstavil izboljšavo SNARK-jev GGPR, ki dosega najsodobnejše konkretne stroške preverjanja še danes (dokazi so 3 skupinski elementi, pri preverjanju pa prevladujejo tri operacije združevanja, vsaj ob predpostavki, da javnost vnos je kratek). Varnost je dokazana v generičnem skupinskem modelu.

SNARK-i z univerzalno zaupanja vredno nastavitvijo

PlonK: Permutacije nad Lagrangeovimi bazami za ekumenske neinteraktivne argumente znanja (2019)
avtorji Ariel Gabizon, Zachary Williamson in Oana Ciobotaru

Marlin: Predobdelava zkSNARK-jev z univerzalnim in nadgradljivim SRS (2019)
od Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely in Nicholas Ward

Tako PlonK kot Marlin nadomestita zaupanja vredno nastavitev, specifično za vezje, v Groth16 z univerzalno nastavitvijo. To gre na račun 4x-6x večjih dokazov. O PlonK in Marlinu si lahko predstavljamo, kot da prevzameta delo, specifično za vezje, med zaupanja vredno nastavitvijo v Groth16 in predhodnikih ter ga premakneta v fazo predprocesiranja, ki se zgodi po zaupanja vredna nastavitev, kot tudi med generiranjem dokazov SNARK.

Zmožnost obdelave poljubnih vezij in sistemov R1CS na ta način se včasih imenuje holografija ali računske obveznosti in je bila tudi opisana v Spartan (razpravljamo kasneje v tej kompilaciji). Ker se med generiranjem dokazov zgodi več dela, sta PlonK in Marlinova preverjalnika počasnejša od Groth16 za dano vezje ali instanco R1CS. Vendar je za razliko od Groth16 PlonK in Marlin mogoče pripraviti za delo z bolj splošnimi vmesnimi predstavitvami kot R1CS.

Sheme polinomske zaveze, ključni kriptografski primitiv v SNARK-ih

Zaveze konstantne velikosti za polinome in njihove aplikacije (2010)
avtorji Aniket Kate, Gregory Zaverucha in Ian Goldberg

Ta članek je uvedel pojem shem polinomskih obveznosti. Podal je shemo za univariatne polinome (običajno imenovane zaveze KZG) z zavezami konstantne velikosti in dokazi vrednotenja. Shema uporablja zaupanja vredno nastavitev (tj. strukturiran referenčni niz) in kriptografijo na podlagi združevanja. Danes je v praksi izjemno priljubljen in se uporablja v SNARK-ih, vključno z PlonK in Marlin, o katerih smo govorili zgoraj (in Groth16 uporablja zelo podobne kriptografske tehnike).

Fast Reed-Solomon Interactive Oracle Proofs of Proximity (2017)
od Eli Ben-Sasson, Iddo Bentov, Ynon Horesh, Michael Riabzev

Zagotavlja interaktivni Oracle proof (IOP) za Reed-Solomonovo testiranje — to je dokazovanje, da je odobreni niz blizu tabele vrednotenja univariatnega polinoma. V kombinaciji z Merkleovim zgoščevanjem in Fiat-Shamirjevo transformacijo to daje pregledno polinomsko zavezujočo shemo s polilogaritemskimi dokazi vrednotenja (glej VP19 za podrobnosti). Danes je to še vedno najkrajša med verjetno postkvantnimi polinomskimi shemami obveznosti.

Ligero: Lahki sublinearni argumenti brez zaupanja vredne nastavitve (2017)
avtorji Scott Ames, Carmit Hazay, Yuval Ishai in Muthuramakrishnan Venkitasubramaniam

Podobno kot FRI, to delo podaja IOP za Reed-Solomonovo testiranje, vendar z dolžino dokaza kvadratnega korena in ne s polilogaritemsko. Teoretično deluje je pokazalo, da lahko z zamenjavo Reed-Solomonove kode za drugo kodo za popravljanje napak s hitrejšim kodiranjem pridobimo linearni časovni dokaznik, ki poleg tega izvorno deluje na katerem koli polju. Ta pristop je bil izpopolnjen in implementiran v Zaviranje in Orion, ki zagotavlja najsodobnejšo zmogljivost preverjevalnika.

Bulletproofs: kratka dokazila za zaupne transakcije in več (2017)
od Benedikt Bunz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille in Greg Maxwell

Izboljšanje predhodnega dela s BCCGP, Bulletproofs daje pregledno shemo polinomske zaveze (pravzaprav posplošitev, imenovano argument notranjega produkta), ki temelji na trdoti računanja diskretnih logaritmov z logaritemsko dokazno velikostjo, vendar linearnim časom preverjanja. Shema je še danes priljubljena zaradi svoje preglednosti in kratkih dokazov (npr. uporablja se v ZCash Orchard in Monero).

Dory: Učinkoviti, pregledni argumenti za generalizirane notranje produkte in polinomske zaveze (2020)
avtorja Jonathan Lee

Dory skrajša čas preverjanja v Bulletproofs z linearnega na logaritemski, hkrati pa ohranja prosojnost in dokaze logaritemske velikosti (čeprav konkretno večje od Bulletproofs) in preglednost. Uporablja pare in temelji na predpostavki SXDH.

Interaktivni dokazi, interaktivni dokazi z več preverjanji in povezani SNARK-ji

Delegiranje računanja: Interaktivni dokazi za Muggles (2008)
avtorji Shafi Goldwasser, Yael Tauman Kalai in Guy Rothblum

Pred tem dokumentom so interaktivni dokazi za splošni namen zahtevali a superpolinomski čas dokazovalnik. Ta članek podaja interaktivni dokazni protokol, običajno imenovan protokol GKR, s polinomskim preverjanjem časa in kvazilinearnim preverjanjem časa za vsak problem, ki ima učinkovit vzporedni algoritem (enakovredno se interaktivni dokaz uporablja za katero koli aritmetično vezje z majhno globino).

Praktično preverjeno računanje s pretočnimi interaktivnimi dokazi (2011)
od Graham Cormode, Michael Mitzenmacher, Justin Thaler

Ta članek (včasih imenovan CMT) je zmanjšal čas preverjanja v protokolu GKR s kvartičnega v velikosti vezja na kvazilinearnega. Izdelal prvo implementacijo splošnega interaktivnega dokaza. Vrsta nadaljnjih del (Piment, Thaler13, Žirafain Tehtnica) je dodatno zmanjšal čas delovanja preverjalnika, od kvazilinearnega do linearnega glede na velikost vezja.

vSQL: Preverjanje poljubnih poizvedb SQL nad dinamičnimi zunanjimi bazami podatkov (2017)
od Yupeng Zhang, Daniel Genkin, Jonathan Katz, Dimitrios Papadopoulos in Charalampos Papamanthou

Čeprav se naslov nanaša na specifično področje uporabe (baze podatkov), so prispevki tega prispevka bolj splošni. Natančneje, opazil je, da je mogoče pridobiti jedrnate argumente za zadovoljivost vezja s kombiniranjem interaktivnih dokazov s shemami polinomske zaveze (za multilinearne polinome).

Kasneje deluje opravljene argumenti z ničelnim znanjem in predstavili različne sheme obveznosti za multilinearne polinome.

Spartan: Učinkoviti in splošni zkSNARK-ji brez zaupanja vredne nastavitve (2019)
avtorja Srinath Setty

Pridobi SNARK za zadovoljivost vezja in R1CS s kombiniranjem interaktivnih dokazov z več dokazilci (MIP) s shemami polinomske zaveze, ki temelji na prejšnjem delu na konkretno učinkovitih MIP, imenovanih Clover. Učinek je pridobitev SNARK s krajšimi dokazi od tistih, ki izhajajo iz interaktivnih dokazov, kot je protokol GKR, o katerem smo razpravljali zgoraj. Podobno kot PlonK in Marlin, Spartan tudi pokaže, kako obdelati poljubna vezja in sisteme R1CS prek predprocesiranja in generiranja dokazov SNARK.

Spartan je uporabil shemo polinomske zaveze iz hyrax. Kasnejša dela imenovana Zaviranje in Orion združiti Spartanov MIP z drugimi shemami polinomske zaveze, da bi dobili prve implementirane SNARK z linearnim časovnim preverjalnikom.

Kratki PCP in IOP

Kratki PCP-ji s kompleksnostjo poizvedbe poliloga (2005)
avtorja Eli Ben-Sasson in Madhu Sudan

 To teoretično delo je dalo prvi verjetnostno preverljiv dokaz (PCP) z dolžino dokaza, ki je kvazilinearna glede na velikost izračuna, ki ga je treba preveriti, in stroške polilogaritmične poizvedbe (čeprav linearni čas preverjanja). Po Kilian-Micalijevi transformaciji PCP v SNARK je bil to korak k SNARK s kvazilinearnim preverjanjem časa in polilogaritemskim preverjanjem časa.

Kasneje teoretično delo zmanjšal čas preverjanja na polilogaritemski. Po praktično osredotočeno delo je izboljšalo ta pristop, vendar so kratki PCP še danes nepraktični. Za pridobitev praktičnih SNARK, pozneje deluje obrnjen do interaktivna posplošitev PCP-jev, imenovana Interaktivni dokazi Oracle (IOP). Ta prizadevanja so pripeljala do tega in nadgradila FREE, priljubljena shema polinomske zaveze, o kateri razpravljamo v razdelku o polinomskih zavezah te zbirke.

Druga dela v tej kategoriji vključujejo ZKBoo in njegovi potomci. Ti ne dosegajo jedrnatih dokazov, vendar imajo dobre konstantne faktorje in so zato privlačni za dokazovanje majhnih trditev. Privedli so do družin postkvantnih podpisov, kot je npr Piknik da imajo bilo optimizirana in več deluje. ZKBoo je predstavljen tako, da sledi posebni oblikovalski paradigmi, imenovani MPC-v-glavi, vendar daje IOP.

Rekurzivni SNARK-ji

Postopoma preverljivi izračuni ali dokazila o znanju nakazujejo časovno/prostorsko učinkovitost (2008)
avtorja Paul Valiant

To delo je uvedlo temeljni pojem inkrementalno preverljivega računanja (IVC), pri katerem preverjalec izvaja izračun in ves čas ohranja dokaz, da je bil dosedanji izračun pravilen. Konstruiral je IVC prek rekurzivne sestave SNARK-jev. Tukaj, utemeljenost znanja Lastnost SNARK je bistvena za ugotavljanje trdnosti rekurzivno sestavljenih neinteraktivnih argumentov. Ta članek je prav tako ponudil izjemno učinkovit ekstraktor znanja za SNARK, ki izhajajo iz PCP (v skladu s paradigmo Kilian-Micali).

Prilagodljivo ničelno znanje prek ciklov eliptičnih krivulj (2014)
avtorji Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer in Madars Virza

Po teoretično delo, ta dokument je uporabil rekurzivno uporabo različice GGPR SNARK, da bi zagotovil prvo implementacijo IVC za preprost virtualni stroj (TinyRAM, iz SNARK za C papir).

Predstavil je tudi pojem ciklov eliptičnih krivulj, ki so uporabni za rekurzivno sestavljanje SNARK-jev, ki uporabljajo kriptografijo eliptičnih krivulj.

Rekurzivna dokazna sestava brez zaupanja vredne nastavitve (2019)
avtorji Sean Bowe, Jack Grigg in Daira Hopwood

To delo (imenovano Halo) preučuje, kako rekurzivno sestaviti pregledne SNARK-e. To je zahtevnejše od sestavljanja netransparentnih, saj je lahko postopek preverjanja v preglednih SNARK-ih veliko dražji.

To je nato sprožilo a vrstica of delo ki je kulminiral v sistemih, kot je npr Nova doseganje najsodobnejše zmogljivosti IVC, ki je boljša celo od tiste, pridobljene s sestavljanjem neprozornih SNARK, kot je Groth16.

Aplikacije

Zerocash: decentralizirana anonimna plačila iz bitcoinov (2014)
od Eli Ben Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, Madars Virza

Na podlagi predhodnega dela, vključno z zerocoin (in z Kovanec Pinnochio kot sočasno delo), ta dokument uporablja SNARK-e, ki izhajajo iz GGPR, za oblikovanje zasebne kriptovalute. Pripeljal do ZCash.

Geppetto: vsestransko preverljivo računanje (2014)
od Craig Costello, Cédric Fournet, Jon Howell, Markulf Kohlweiss, Benjamin Kreuter, Michael Naehrig, Bryan Parno in Samee Zahur

Geppetto je verjetno pred eksplozijo zanimanja za izvajanje zasebnih pametnih pogodb, saj je bil napisan približno eno leto po ustanovitvi Ethereuma. Zato ni predstavljen v kontekstu izvajanja zasebne pametne pogodbe. Vendar pa uporablja rekurzijo SNARK z omejeno globino, da nezaupljivemu dokazovalniku omogoči izvajanje katerega koli zasebnega (dodeljenega/podpisanega) računalniškega programa na zasebnih podatkih, ne da bi razkril informacije o programu, ki se izvaja, ali podatkih, na katerih se izvaja. Skladno s tem je predhodnik dela na zasebnih platformah pametnih pogodb, kot je npr Zexe [opisano spodaj].

Preverljivi ASIC-ji (2015)
od Riad Wahby, Max Howald, Siddharth Garg, abhi shelat, Michael Walfish

Ta članek obravnava problem, kako varno in uspešno uporabljati ASIC, izdelan v nezaupljivi livarni (leta 2015 je bilo samo pet držav z vrhunskimi livarnami). Pristop je, da hitri, a nezaupanja vreden ASIC dokaže pravilnost svojega izhoda verifikatorju, ki deluje na počasnejšem, a zaupanja vrednem ASIC. Rešitev je zanimiva, dokler je skupni čas izvajanja sistema (tj. vsota izvajalnih časov dokazovalnika in preverjalnika plus morebitni stroški prenosa podatkov) manjši od naivnega izhodišča: čas, potreben za izvedbo celotnega izračuna na počasnejšem -vendar zaupanja vreden ASIC. Z uporabo različice interaktivnih dokazov GKR/CMT/Allspice prispevek dejansko premaga naivno osnovo za številne temeljne težave, vključno s pretvorbami številske teorije, ujemanjem vzorcev in operacijami eliptičnih krivulj. To delo nakazuje, da so nekateri dokazni sistemi bolj primerni za izvedbo strojne opreme kot drugi. Optimiziranje dokaznih sistemov za izvedbo strojne opreme je zdaj na voljo velika pozornosti, vendar je treba še veliko raziskati.

Preverljivo Funkcije zakasnitve (2018)
avtorji Dan Boneh, Joseph Bonneau, Benedikt Bünz in Ben Fisch

Predstavil je notacijo preverljivih funkcij zakasnitve (VDF), kriptografskega primitiva, ki je široko uporaben v aplikacijah verige blokov, npr. pri blaženju morebitne manipulacije protokolov soglasja o dokazu deleža. SNARK-ji (zlasti za postopno preverljive izračune) ponujajo pot do najsodobnejših VDF-jev.

Zexe: Omogočanje decentraliziranega zasebnega računanja (2018)
od Sean Bowe, Alessandro Chiesa, Matthew Green, Ian Miers, Pratyush Mishra in Howard Wu

Zexe je zasnova za zasebno platformo pametnih pogodb. Na Zexe lahko gledate kot na razširitev Zerocasha (opisano zgoraj). Zerocash omogoča izvajanje ene same aplikacije v verigi (omogoča uporabnikom prenos žetonov), hkrati pa ščiti zasebnost uporabniških podatkov, npr. komu pošiljajo žetone, od koga prejemajo žetone, količino prenesenih žetonov itd. Zexe omogoča številne različne aplikacije (pametne pogodbe), ki delujejo na isti verigi blokov in medsebojno delujejo. Transakcije se izvajajo izven verige, dokazila o pravilni izvedbi pa so objavljena v verigi. Zaščitena ni le zasebnost podatkov, temveč tudi zasebnost funkcij. To pomeni, da dokazilo, povezano z vsako transakcijo, sploh ne razkrije, na katero(-e) aplikacijo(-e) se transakcija nanaša. Splošnejši inženirski prispevek Zexe je, da je uvedel BLS12-377, skupino eliptičnih krivulj, ki je uporabna za učinkovito sestavo globine 1 SNARK-jev, ki temeljijo na združevanju.

Podvojeni državni stroji brez podvojene izvedbe (2020)
avtorji Jonathan Lee, Kirill Nikitin in Srinath Setty

To je eden redkih akademskih člankov o zbiranjih za razširljivost verige blokov. Ne uporablja izraza zbiranje, ker je pred ali je sočasen konceptu, ki je bil uveden zunaj akademske literature.

Front-ends (učinkovite transformacije iz računalniških programov v vmesne predstavitve, kot je zadovoljivost vezja, R1CS in drugo)

Hitro zmanjšanje z RAM-ov na delegirane jedrnate težave z zadovoljevanjem omejitev (2012)
avtorji Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin in Eran Tromer

S sodobnega vidika je to zgodnje delo o praktičnih transformacijah računalniškega programa v vezje SAT za abstrakcijo virtualnega stroja (VM). Na podlagi del iz poznih sedemdesetih do devetdesetih (npr. delo Robson) ta članek opisuje deterministično redukcijo od izvajanja VM za T korakov do zadovoljivosti vezja velikosti O(T*polylog(T)).

Kasnejši dokumenti, npr. SNARK za C in BCTV, nadaljeval z razvojem sprednjih koncev prek abstrakcije VM, sodobne instancije pa vključujejo projekte, kot je npr. Cairo, RISC ničin Poligon Miden.

Na dokazih temelječe preverjeno računanje nekaj korakov bližje praktičnosti (2012)
od Srinath Setty, Victor Vu, Nikhil Panpalia, Benjamin Braun, Muqeet Ali, Andrew J. Blumberg in Michael Walfish

Ta članek, imenovan Ginger, je še en zgodnji prispevek k praktičnim front-end tehnikam. Ginger je uvedel pripomočke za splošne programske primitive, kot so pogojniki in logični izrazi, primerjave in bitna aritmetika prek delitve bitov, primitivna aritmetika s plavajočo vejico itd. Te pripomočke je uporabil za zagotavljanje prvega implementiranega sprednjega dela iz jezika visoke ravni v jezik nizke stopnje aritmetične omejitve (podobno temu, kar je zdaj znano kot R1CS), vmesna predstavitev (IR), za katero je mogoče uporabiti zaledje SNARK.

Medtem ko dokument »Fast Reductions« in njegovi potomci uporabljajo pristop »CPE-emulator« pri izdelavi IR-jev (tj. IR uveljavlja, da je preverjalnik pravilno zagnal določen program z uporabo prehodne funkcije CPE-ja za določeno število korakov) , Ginger in njegovi potomci uporabljajo pristop, ki je bolj podoben ASIC-u, in proizvajajo IR-je, ki so prilagojeni računalniškemu programu, za katerega dokazovalnik trdi, da ga pravilno izvaja.

Na primer, Buffet kaže, da je mogoče upravljati s kompleksnim nadzornim tokom v modelu ASIC, tako da tak nadzorni tok spremenimo v končni stroj, prilagojen izvajanemu programu, in da je ta pristop lahko bistveno učinkovitejši od gradnje splošnega emulatorja CPE. xJsnark nudi učinkovito konstrukcijo za aritmetiko z več natančnostmi, optimizacije za pomnilnike RAM in ROM ter programerju izpostavi jezik visoke ravni, podoben Javi, ki je še danes priljubljen. CirC opaža, da je prevajanje računalniških programov v R1CS tesno povezano z dobro znanimi tehnikami iz analize programov in gradi komplet orodij za gradnjo prevajalnika, ki vključuje ideje iz obeh skupnosti (»LLVM za vezju podobne predstavitve«). Prejšnja dela, ki prispevajo k vmesnikom v slogu ASIC, vključujejo Ostržek in Geppetto.

Prispevek »Fast-Reductions« je uporabil zapleteno in drago konstrukcijo, imenovano »usmerjevalna omrežja« za t.i. preverjanje spomina (tj. zagotavljanje, da nezaupanja vreden preverjalnik pravilno vzdržuje pomnilnik z naključnim dostopom VM skozi celotno izvajanje VM, katerega pravilnost se dokazuje). Ta izbira je bila sprejeta, ker so zgodnja dela, kot je to, želela pridobiti PCP, ki je zahteval, da je sprednji del tako neinteraktiven in informacijsko teoretično varen. Kasneje poklicano delo Shramba (predhodnik Buffet delo, omenjeno zgoraj) je namesto usmerjevalnih omrežij uporabil Merklova drevesa in dosegel učinkovitost s prevajanjem algebraične (tj. »SNARK-prijazne«) zgoščevalne funkcije zaradi Ajtai, v omejitve. To je povzročilo "računalniško varne" sprednje strani. Danes obstaja obsežna raziskovalna literatura o SNARK prijaznih zgoščevalnih funkcijah, vključno s primeri Poseidon, MiMC, Ojačani beton, Rescue, In še več.

Najsodobnejše tehnike za zagotavljanje, da preverjalnik pravilno vzdržuje RAM, se opirajo na tako imenovane metode »permutacijsko invariantnega prstnega odtisa«, ki segajo vsaj do Lipton (1989) in ga uporablja za preverjanje spomina Blum et al. (1991). Te tehnike same po sebi vključujejo interakcijo med dokazovalnikom in verifikatorjem, vendar jih je mogoče narediti neinteraktivne s Fiat-Shamirjevo transformacijo. Kolikor vemo, so bili predstavljeni v literaturi o praktičnih vmesnikih SNARK s sistemom, imenovanim vRAM.

Tehnike prstnih odtisov, ki so nespremenljive s permutacijo, se zdaj uporabljajo v številnih sprednjih delih in SNARK-ih za abstrakcije virtualnih strojev, vključno z npr. Cairo. Tesno povezane ideje so se ponovno pojavile v povezanih kontekstih v spodnjih dveh delih, ki se danes pogosto uporabljajo v praksi.

Skoraj linearni časovni dokazi brez znanja za pravilno izvajanje programa (2018)
od Jonathan Bootle, Andrea Cerulli, Jens Groth, Sune Jakobsen in Mary Maller

Plookup: poenostavljen polinomski protokol za iskalne tabele (2020)
avtorja Ariel Gabizon in Zachary Williamson

Zgodnja dela na sprednjih delih so predstavljala »nearitmetične« operacije (kot so preverjanja obsega, bitne operacije in primerjave celih števil) znotraj vezij in sorodnih IR-jev z razbijanjem elementov polja na bite, izvajanjem operacij na teh bitih in nato »pakiranjem« rezultat nazaj v en sam element polja. Kar zadeva velikost nastalega vezja, ima to za posledico logaritemske režijske stroške na operacijo.

Zgornji dve deli (BCGJM in Plookup) podajata vplivne tehnike (na podlagi tako imenovanih »iskalnih tabel«) za učinkovitejšo predstavitev teh operacij znotraj vezij, v amortiziranem smislu. Grobo povedano, za nek parameter B, ki ga je izbral začetni oblikovalec, ti zmanjšajo število vrat, potrebnih za predstavitev vsake nearitmetične operacije v vezju, za logaritemski faktor v B, na ceno dokazovalnika, ki se kriptografsko zaveže dodatnemu vektor »nasveta« dolžine približno B.