Canon cu cunoștințe zero

Nota editorului: a16z crypto a avut o serie lungă de „arme”, de la noi DAO Canon anul trecut la noi NFT Canon mai devreme (și înainte de asta originalul nostru Crypto Canon) — asigurați-vă că vă înscrieți la programul nostru buletin informativ săptămânal web3 pentru mai multe actualizări, precum și pentru alte resurse organizate.

Deci bmai jos, am adunat un set de resurse pentru cei care doresc să înțeleagă, să aprofundeze și să construiască cu toate lucrurile zero cunostinte: tehnologii puternice, fundamentale, care dețin cheile scalabilității blockchain și reprezintă viitorul aplicațiilor care păstrează confidențialitatea și al nenumăratelor alte inovații care urmează. Dacă aveți sugestii pentru piese de înaltă calitate de adăugat, anunțați-ne @a16zcrypto.

Sistemele de demonstrare a cunoștințelor zero există de zeci de ani: introducerea lor de către Shafi Goldwasser, Silvio Micali și Charles Rackoff în 1985 a avut un efect de transformare în domeniul criptografiei și a fost recunoscut de Premiul ACM Turing acordat lui Goldwasser și Micali în 2012. Deoarece această lucrare – inclusiv trecerea ei de la teorie la practică și aplicațiile în cripto/web3 astăzi – a fost în pregătire de zeci de ani, împărtășim pentru prima dată în seria noastră de canoane și partea a doua (deocamdată, inclusă aici mai jos): o listă de lectură adnotată de Justin Thaler, urmând partea întâi de mai jos.

Mulțumiri: Mulțumesc și lui Michael Blau, Sam Ragsdale și Tim Roughgarden.

Fundamente, fundal, evoluții

Unele dintre aceste lucrări sunt, de asemenea, mai mult despre criptografie în general (nu toate cunoștințele zero per se), inclusiv subliniind problemele sau progresele cheie care sunt abordate de dovezile zero cunoștințe astăzi: cum să asigurați confidențialitatea și autentificarea în rețelele deschise.

Noi direcții în criptografie (1976)
de Whitfield Diffie și Martin Hellman
https://ee.stanford.edu/~hellman/publications/24.pdf

O metodă pentru obținerea semnăturilor digitale și a criptosistemelor cu cheie publică
de 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

Protocoale pentru criptosisteme cu cheie publică (1980)
de Ralph Merkle
http://www.merkle.com/papers/Protocols.pdf

Comunicații securizate prin canale nesigure (1978)
de Ralph Merkle
https://www.merkle.com/1974/PuzzlesAsPublished.pdf

Utilizarea curbelor eliptice în criptografie (1988)
de Victor Miller
https://link.springer.com/content/pdf/10.1007%2F3-540-39799-X_31.pdf

Complexitatea cunoștințelor sistemelor de dovezi interactive (1985)
de Shafi Goldwasser, Silvio Micali, Charles Rackof
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.419.8132&rep=rep1&type=pdf

Dovada de sunet computerizat (2000)
de Silvio Micali
https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/Computationally_Sound_Proofs.pdf

De la rezistența la coliziune extractibilă la argumente succinte non-interactive ale cunoașterii [SNARKs] și înapoi (2011)
de Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer
https://eprint.iacr.org/2011/443.pdf

Argument eficient de zero cunoștințe pentru corectitudinea unei amestecări (2012)
de Stephanie Bayer și Jens Groth
http://www0.cs.ucl.ac.uk/staff/J.Groth/MinimalShuffle.pdf

Cunoștințe succinte non-interactive zero pentru o arhitectură von Neumann (2013)
de Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer și Madars Virza
https://eprint.iacr.org/2013/879.pdf

Integritate computațională sigură scalabilă, transparentă și post-cuantică (2018)
de Eli Ben-Sasson, Iddo Bentov, Yinon Horesh și Michael Riabzev
https://eprint.iacr.org/2018/046.pdf

Argumente cu monede publice zero cunoștințe cu cheltuieli generale (aproape) minime de timp și spațiu (2020)
de Alexander Block, Justin Holmgren, Alon Rosen, Ron Rothblum și Pratik Soni
https://www.iacr.org/cryptodb/data/paper.php?pubkey=30645

Prezentare generală și introduceri

Dovezi, argumente și cunoștințe zero — O privire de ansamblu asupra dovezilor și argumentelor interactive și de calcul verificabile, protocoale criptografice care permit unui probator să ofere o garanție unui verificator că acesta a efectuat corect un calcul solicitat, inclusiv cunoștințe zero (în cazul în care dovezile nu dezvăluie altă informație decât propria lor validitate) . Argumentele Zk au o multitudine de aplicații în criptografie și au făcut saltul de la teorie la practică în ultimul deceniu.
de Justin Thaler
https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf

O evoluție a modelelor pentru dovezi cu cunoștințe zero — O revizuire a dovezilor cu cunoștințe zero, în care Meiklejohn (University College London, Google) analizează aplicațiile care conduc dezvoltarea lor, diferitele modele care au apărut pentru a surprinde aceste noi interacțiuni, construcțiile pe care le putem realiza și munca lăsat de făcut.
de Sarah Meiklejohn
https://www.youtube.com/watch?v=HO97kVMI3SE

Sesiuni de tablă ZK — module introductive
cu Dan Boneh et al
https://zkhack.dev/whiteboard/

Securitate și confidențialitate pentru cripto cu zkps — introducerea în practică a dovezii zero-cunoștințe; ce sunt zkps și cum funcționează... inclusiv „demo” live pe scenă
de Zooko Wilcox
https://a16z.com/2019/08/29/security-and-privacy-for-crypto-with-zero-knowledge-proofs/

Subiecte tehnologice de top, explicate — inclusiv definiții și implicații ale cunoștințelor zero în general
de 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

Cum va repara stratul de confidențialitate viitor un web rupt
de Howard Wu
https://future.com/a-privacy-layer-for-the-web-can-change-everything/

Introducere în zkSNARKs
cu Howard Wu, Anna Rose
https://zeroknowledge.fm/38-2/

De ce și cum funcționează zk-SNARK: o explicație definitivă
de Maksym Petkus
https://arxiv.org/pdf/1906.07221.pdf

O introducere în dovezile zero-cunoștințe
de Fredrik Harrysson și Anna Rose
https://www.zeroknowledge.fm/21 [+ rezumat în altă parte aici]

Zk-SNARK-uri: sub capotă
de Vitalik Buterin
https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
parte 1, parte 2, parte 3

Viteză descentralizată — privind progresele în dovezile zero cunoștințe, hardware descentralizat
de Elena Burger
https://a16z.com/2022/04/15/zero-knowledge-proofs-hardware-decentralization-innovation/

Cercetare zk de vârf — cu cercetător zk la Ethereum Foundation
cu Mary Maller, Anna Rose, Kobi Gurkan
https://zeroknowledge.fm/232-2/

Explorarea cercetării zk — cu director de cercetare la DFINITY; tot în spatele unor avansuri precum Groth16
cu Jens Groth, Anna Rose, Kobi Gurkan
https://zeroknowledge.fm/237-2/

cercetare și pedagogie SNARK — cu unul dintre co-fondatorii ZCash și Starkware
cu Alessandro Chiesa, Anna Rose
https://zeroknowledge.fm/episode-200-snark-research-pedagogy-with-alessandro-chiesa/

Scufundări adânci, ghizi de constructori

Fundamentele demonstrațiilor probabilistice — un curs cu 5 unități din dovezi interactive și multe altele
de Alessandro Chiesa
https://www.youtube.com/playlist?list=PLGkwtcB-DfpzST-medFVvrKhinZisfluC

STARKs - partea I, II, III
de 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

Anatomia unui STARK — un tutorial în șase părți care explică mecanica unui sistem de verificare STARK
de Alan Szepieniec
https://aszepieniec.github.io/stark-anatomy/

Design SNARK, partea 1 — sondaj, utilizare în pachete, mai mult
de Justin Thaler
https://www.youtube.com/watch?v=tg6lKPdR_e4

Design SNARK, partea 2 — rollup-uri, performanță, securitate
de Justin Thaler
https://www.youtube.com/watch?v=cMAI7g3UcoI

Măsurarea performanței SNARK — front-end-uri, back-end-uri, mai mult
de Justin Thaler
https://a16zcrypto.com/measuring-snark-performance-frontends-backends-and-the-future/

Înțelegerea lui PLONK
https://vitalik.ca/general/2019/09/22/plonk.html

Sistemul de demonstrare a cunoștințelor zero PLONK — serie de 12 videoclipuri scurte despre cum funcționează PLONK
de David Wong
https://www.youtube.com/playlist?list=PLBJMt6zV1c7Gh9Utg-Vng2V6EYVidTFCC

De la AIR la RAP — cum funcționează aritmetizarea în stil PLONK
de Ariel Gabizon
https://hackmd.io/@aztec-network/plonk-arithmetiization-air

Verificări multiseturi în PLONK și Plookup
de Ariel Gabizon
https://hackmd.io/@arielg/ByFgSDA7D

Design Halo2 — de la ECC
https://zcash.github.io/halo2/design.html

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

Aplicații și tutoriale: dovezi de concepte, demonstrații, instrumente, mai mult

Aplicat zk - resurse de învățare
de 0xPARC
https://learn.0xparc.org/materials/intro

Un mediu de dezvoltare online pentru zkSNARKs — zkREPL, un nou set de instrumente pentru interacțiunea cu stiva de instrumente Circom în browser
de Kevin Kwok
https://zkrepl.dev (+ fir explicativ aici)

Programe de aritmetică cuadratică de la zero la erou
de Vitalik Buterin
https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

Pe zkEVM-uri
cu Alex Gluchowski și Anna Rose
https://zeroknowledge.fm/175-2/

Diferite tipuri de zkEVM
de Vitalik Buterin
https://vitalik.ca/general/2022/08/04/zkevm.html

ZK machine learning — tutorial și demonstrație pentru introducerea unei rețele neuronale într-un SNARK
de Horace Pan, Francis Ho și Henri Palacci
https://0xparc.org/blog/zk-mnist

Pe limbile ZK
cu Alex Ozdemir și Anna Rose
https://zeroknowledge.fm/172-2/

Dark Forest — aplicarea criptografiei zk la jocuri — un joc RTS (strategie în timp real) complet descentralizat și persistent
https://blog.zkga.me/announcing-darkforest

ZKP-uri pentru ingineri — o privire la ZKP-urile Pădurii Întunecate
https://blog.zkga.me/df-init-circuit

O scufundare în cunoștințe zero
cu Elena Nadolinkski, Anna Rose, James Prestwich
https://zeroknowledge.fm/182-2/

zkDocs: schimb de informații fără cunoștințe
de Sam Ragsdale și Dan Boneh
https://a16zcrypto.com/zkdocs-zero-knowledge-information-sharing/

Airdrops cripto care protejează confidențialitatea fără dovezi de cunoștințe
de Sam Ragsdale
https://a16z.com/2022/03/27/crypto-airdrop-privacy-tool-zero-knowledge-proofs/

Ceremonii de configurare de încredere în lanț -
de Valeria Nikolaenko și Sam Ragsdale
https://a16zcrypto.com/on-chain-trusted-setup-ceremony/

Reglementări cripto, finanțare ilegală, confidențialitate și nu numai – include secțiune privind zero cunoștințe în contexte de reglementare/conformitate; diferența dintre tehnologiile de „păstrare a confidențialității” și cele de ofuscare
cu Michele Korver, Jai Ramaswamy, Sonal Chokshi
https://web3-with-a16z.simplecast.com/episodes/crypto-regulations-sanctions-compliance-aml-ofac-news-explained

Alte resurse

Buletinul informativ zkMesh — un buletin informativ lunar care împărtășește cele mai recente tehnologii descentralizate de păstrare a confidențialității, dezvoltarea protocolului de confidențialitate și sisteme de cunoștințe zero
https://zkmesh.substack.com/

Podcastul Zero Knowledge — pe cele mai recente aplicații zk research și zk și experți care construiesc tehnologie de confidențialitate criptată
cu Anna Rose
https://zeroknowledge.fm/

… o listă de lectură adnotată, după subiect și cronologie, de Justin Thaler:

SNARK-uri de la PCP-uri liniare (alias SNARK-uri cu configurație specifică circuitului)

Argumente eficiente fără PCP scurte (2007)
de Yuval Ishai, Eyal Kushilevitz și Rafail Ostrovsky

Înainte de aproximativ 2007, SNARK-urile au fost proiectate în principal prin intermediul Kilian-micali paradigmă, de a lua o „scurtă” dovadă verificabilă probabil (PCP) și de a o „compila criptografic” într-un argument succint prin hashingul Merkle și transformarea Fiat-Shamir. Din păcate, PCP-urile scurte sunt complicate și nepractice, chiar și astăzi. Această lucrare (IKO) a arătat cum să utilizați criptarea homomorfă pentru a obține argumente interactive succinte (netransparente) de la PCP-uri „lungi, dar structurate”. Acestea pot fi mult mai simple decât PCP-urile scurte, iar SNARK-urile rezultate au dovezi mult mai scurte și o verificare mai rapidă. Aceste argumente au fost mai întâi recunoscute ca având potențialul de eficiență practică și rafinate și implementate în Piper. Din păcate, argumentele lui IKO au un doveditor de timp pătratic și șir de referință structurat de dimensiune pătratică, așa că nu se scalează la calcule mari.

Programe cu întindere patratică și NIZK succinte fără PCP (2012)
de Rosario Gennaro, Craig Gentry, Bryan Parno și Mariana Raykova

Această lucrare revoluționară (GGPR) a redus costurile de verificare ale abordării IKO de la pătratică în dimensiunea circuitului la cvasiliniară. Bazându-se pe lucrările anterioare ale Groth și Lipmaa, a dat, de asemenea, SNARK-uri prin criptografie bazată pe perechi, mai degrabă decât argumente interactive ca în IKO. Și-a descris SNARK-urile în contextul a ceea ce se numește acum probleme de satisfacție a constrângerii de rang 1 (R1CS), o generalizare a satisfacției circuitului aritmetic.

Această lucrare a servit, de asemenea, ca fundament teoretic al primelor SNARK-uri care au văzut implementarea comercială (de exemplu, în ZCash) și a condus direct la SNARK-uri care rămân populare astăzi (de exemplu, Groth16). Au venit implementările inițiale ale argumentelor GGPR Zaatar și Pinocchio, iar variantele ulterioare includ SNARK-uri pentru C și BCTV. BCIOP a oferit un cadru general care elucidează aceste transformări liniare-PCP-uri la SNARK (vezi, de asemenea, Anexa A la Zaatar) și descrie diverse instanțieri ale acestora.

Despre dimensiunea argumentelor neinteractive bazate pe împerechere (2016)
de Jens Groth

Această lucrare, denumită în mod colocvial Groth16, a prezentat o rafinare a SNARK-urilor GGPR care realizează costuri de verificare concrete de ultimă generație chiar și astăzi (dovezile sunt 3 elemente de grup, iar verificarea este dominată de trei operațiuni de împerechere, cel puțin presupunând publicul). intrarea este scurtă). Securitatea este dovedită în modelul de grup generic.

SNARK-uri cu configurație universală de încredere

PlonK: Permutări asupra bazelor Lagrange pentru argumente oecumenice neinteractive ale cunoașterii (2019)
de Ariel Gabizon, Zachary Williamson și Oana Ciobotaru

Marlin: preprocesarea zkSNARK-urilor cu SRS universal și actualizabil (2019)
de Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely și Nicholas Ward

Atât PlonK, cât și Marlin înlocuiesc configurația de încredere specifică circuitului din Groth16 cu o configurație universală. Acest lucru vine în detrimentul dovezilor de 4x-6x mai mari. Se poate crede că PlonK și Marlin au preluat munca specifică circuitului în timpul configurării de încredere în Groth16 și predecesorii și o mută într-o fază de preprocesare care are loc. după configurația de încredere, precum și în timpul generării probei SNARK.

Capacitatea de a procesa circuite arbitrare și sisteme R1CS în acest mod este uneori numită holografie sau angajamente de calcul și a fost, de asemenea, descrisă în Spartan (discutat mai târziu în această compilație). Deoarece se lucrează mai mult în timpul generării dovezilor, probatorii lui PlonK și Marlin sunt mai lenți decât Groth16 pentru un anumit circuit sau instanță R1CS. Cu toate acestea, spre deosebire de Groth16, PlonK și Marlin pot fi făcute să lucreze cu reprezentări intermediare mai generale decât R1CS.

Scheme de angajament polinomial, o primitivă criptografică cheie în SNARK

Angajamente de dimensiune constantă față de polinoame și aplicațiile acestora (2010)
de Aniket Kate, Gregory Zaverucha și Ian Goldberg

Această lucrare a introdus noțiunea de scheme de angajament polinomial. A oferit o schemă pentru polinoame univariate (denumite în mod obișnuit angajamente KZG) cu angajamente de dimensiune constantă și dovezi de evaluare. Schema folosește o configurație de încredere (adică șir de referință structurat) și criptografie bazată pe împerechere. Rămâne extrem de popular în practică astăzi și este folosit în SNARK-uri, inclusiv PlonK și Marlin discutate mai sus (iar Groth16 folosește tehnici criptografice extrem de similare).

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

Oferă o dovadă interactivă a oracolului (IOP) pentru testarea Reed-Solomon - adică, demonstrând că un șir angajat este aproape de tabelul de evaluare a unui polinom univariat. Combinat cu Merkle-hashing și transformarea Fiat-Shamir, aceasta produce o schemă transparentă de angajare polinomială cu dovezi de evaluare de dimensiuni polilogaritmice (vezi VP19 pentru detalii). Astăzi, aceasta rămâne cea mai scurtă dintre schemele de angajament polinomial post-cuantic plauzibil.

Ligero: Argumente subliniare ușoare fără o configurare de încredere (2017)
de Scott Ames, Carmit Hasay, Yuval Ishai și Muthuramakrishnan Venkitasubramaniam

Similar cu FRI, această lucrare oferă un IOP pentru testarea Reed-Solomon, dar cu lungimea de verificare a rădăcinii pătrate mai degrabă decât polilogaritmică. Teoretic fabrică a arătat că, schimbând codul Reed-Solomon cu un alt cod de corectare a erorilor cu o codificare mai rapidă, se poate obține un doveditor în timp liniar care, în plus, funcționează nativ în orice domeniu. Această abordare a fost rafinată și implementată în Frânare și Orion, oferind performanțe de ultimă generație.

Bulletproofs: dovezi scurte pentru tranzacții confidențiale și multe altele (2017)
de Benedikt Bunz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille și Greg Maxwell

Rafinarea lucrărilor anterioare de către BCCGP, Bulletproofs oferă o schemă de angajare polinomială transparentă (de fapt, o generalizare numită argument de produs interior) bazată pe duritatea calculării logaritmilor discreti cu dimensiunea dovezii logaritmice, dar timpul verificatorului liniar. Schema rămâne populară astăzi datorită transparenței și dovezilor scurte (de exemplu, este folosită în ZCash Orchard și Monero).

Dory: Argumente eficiente, transparente pentru produse interne generalizate și angajamente polinomiale (2020)
de Jonathan Lee

Dory reduce timpul de verificare în Bulletproofs de la liniar la logaritmic, păstrând în același timp transparența și dovezile de dimensiune logaritmică (deși în mod concret mai mari decât Bulletproofs) și transparența. Utilizează perechi și se bazează pe ipoteza SXDH.

Dovezi interactive, dovezi interactive cu mai multe probe și SNARK-uri asociate

Delegarea calculului: dovezi interactive pentru muggles (2008)
de Shafi Goldwasser, Yael Tauman Kalai și Guy Rothblum

Înainte de această lucrare, dovezile interactive de uz general necesitau: a superpolinom-timp doveditor. Această lucrare oferă un protocol de demonstrare interactiv, denumit în mod obișnuit protocolul GKR, cu un probator de timp polinomial și un verificator de timp cvasiliniar, pentru orice problemă care posedă un algoritm paralel eficient (în mod echivalent, demonstrația interactivă se aplică oricărui circuit aritmetic cu adâncime mică).

Calcul practic verificat cu probe interactive în flux (2011)
de Graham Cormode, Michael Mitzenmacher, Justin Thaler

Această lucrare (uneori numită CMT) a redus timpul de probă în protocolul GKR de la quartic în dimensiunea circuitului la cvasiliniar. A produs prima implementare a unei dovezi interactive de uz general. O serie de lucrări ulterioare (cuișoare englezești, Thaler13, Girafă, și Balanta) a redus și mai mult timpul de rulare al probatorului, de la cvasiliniar la liniar în dimensiunea circuitului.

vSQL: Verificarea interogărilor SQL arbitrare pe baze de date externalizate dinamice (2017)
de Yupeng Zhang, Daniel Genkin, Jonathan Katz, Dimitrios Papadopoulos și Charalampos Papamanthou

Deși titlul se referă la o anumită zonă de aplicare (baze de date), contribuțiile acestei lucrări sunt mai generale. În mod specific, a observat că se pot obține argumente succinte pentru satisfacția circuitului prin combinarea dovezilor interactive cu scheme de angajare polinomiale (pentru polinoame multiliniare).

Mai târziu fabrică prestate argumentele zero-cunoaștere și au introdus diferite scheme de angajare pentru polinoame multiliniare.

Spartan: zkSNARK eficiente și de uz general, fără o configurare de încredere (2019)
de Srinath Setty

Obține SNARK-uri pentru satisfacția circuitului și R1CS prin combinarea dovezilor interactive cu mai multe dovezi (MIP) cu scheme de angajament polinomial, bazându-se pe lucrările anterioare pe MIP-uri eficiente concret numite Trifoi. Efectul este de a obține SNARK-uri cu dovezi mai scurte decât cele derivate din dovezi interactive, cum ar fi protocolul GKR discutat mai sus. Analog cu PlonK și Marlin, Spartan arată, de asemenea, cum să proceseze circuite arbitrare și sisteme R1CS prin preprocesare și generare de probe SNARK.

Spartan a folosit o schemă de angajament polinomial din hyrax. Lucrările ulterioare numite Frânare și Orion combinați MIP-ul lui Spartan cu alte scheme de angajare polinomiale pentru a produce primele SNARK-uri implementate cu un doveditor în timp liniar.

PCP și IOP scurte

PCP-uri scurte cu complexitate de interogare Polylog (2005)
de Eli Ben-Sasson și Madhu Sudan

 Această lucrare teoretică a oferit prima dovadă verificabilă probabil (PCP) cu lungimea dovezii cvasiliniară în dimensiunea calculului de verificat și costul interogării polilogaritmice (deși timpul verificatorului liniar). În urma transformării Kilian-Micali a PCP-urilor în SNARK, acesta a fost un pas către SNARK-uri cu probator de timp cvasi-liniar și verificator de timp polilogaritmic.

Lucrări teoretice ulterioare a redus timpul de verificare la polilogaritmic. Ulterior munca concentrată practic a rafinat această abordare, dar PCP-urile scurte rămân nepractice astăzi. Pentru a obține SNARK-uri practice, mai tarziu fabrică avansat la o generalizare interactivă a PCP numită Dovezi interactive Oracle (IOP-uri). Aceste eforturi au condus la și au construit pe GRATUIT, o schemă populară de angajamente polinomiale discutată în secțiunea de angajamente polinomiale a acestei compilații.

Alte lucrări din această categorie includ ZKBoo și descendenții săi. Acestea nu realizează dovezi succinte, dar au factori constanți buni și, prin urmare, sunt atractive pentru demonstrarea afirmațiilor mici. Au condus la familii de semnături post-cuantice, cum ar fi Picnic care au fost optimizate in câteva fabrică. ZKBoo este prezentat ca urmând o paradigmă distinctă de design numită MPC-in-cap, dar dă un IOP.

SNARK-uri recursive

Calculul verificabil incremental sau dovezile de cunoștințe implică eficiență în timp/spațiu (2008)
de Paul Valiant

Această lucrare a introdus noțiunea fundamentală de calcul incremental verificabil (IVC), în care probele rulează un calcul și mențin în orice moment o dovadă că calculul până acum a fost corect. A construit IVC prin compoziția recursivă a SNARK-urilor. Aici cunoaștere-soliditate proprietatea SNARK-urilor este esențială pentru stabilirea solidității argumentelor non-interactive compuse recursiv. Această lucrare a oferit, de asemenea, un extractor de cunoștințe extrem de eficient pentru SNARK-uri derivate din PCP (conform paradigmei Kilian-Micali).

Cunoștințe zero scalabile prin cicluri de curbe eliptice (2014)
de Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer și Madars Virza

Urmărești: lucrare teoretică, această lucrare a folosit aplicarea recursivă a unei variante a SNARK al GGPR, pentru a oferi prima implementare a IVC pentru o mașină virtuală simplă (TinyRAM, din SNARK-uri pentru C hârtie).

De asemenea, a introdus noțiunea de cicluri de curbe eliptice, care sunt utile pentru alcătuirea recursiv a SNARK-urilor care utilizează criptografia cu curbe eliptice.

Compoziție de dovezi recursive fără o configurare de încredere (2019)
de Sean Bowe, Jack Grigg și Daira Hopwood

Această lucrare (numită Halo) studiază cum să compună recursiv SNARK-uri transparente. Acest lucru este mai dificil decât alcătuirea celor netransparente, deoarece procedura de verificare în SNARK-uri transparente poate fi mult mai costisitoare.

Aceasta a declanșat apoi o linie of muncă care a culminat cu sisteme precum Nova obținând performanțe IVC de ultimă generație, superioare chiar și celei obținute prin compoziția unor SNARK-uri netransparente precum Groth16.

aplicatii

Zerocash: plăți anonime descentralizate de la Bitcoin (2014)
de Eli Ben Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, Madars Virza

Bazându-se pe lucrările anterioare, inclusiv Zerocoin (si cu Moneda Pinnochio ca lucru concomitent), această lucrare folosește SNARK-uri derivate din GGPR pentru a proiecta o criptomonedă privată. A condus la ZCash.

Geppetto: calcul versatil verificabil (2014)
de Craig Costello, Cédric Fournet, Jon Howell, Markulf Kohlweiss, Benjamin Kreuter, Michael Naehrig, Bryan Parno și Samee Zahur

Geppetto este probabil anterioară exploziei de interes pentru execuția unui contract inteligent privat, fiind scris la aproximativ un an de la crearea Ethereum. Prin urmare, nu este prezentat în contextul execuției private smart-contract. Cu toate acestea, folosește recursiunea SNARK la adâncime limitată pentru a permite unui probator neîncrezat să execute orice program de calculator privat (commit/semnat) pe date private, fără a dezvălui informații despre programul care rulează sau despre datele pe care se rulează. În consecință, este un predecesor al lucrării pe platforme private de contracte inteligente, cum ar fi Zexe [descris mai jos].

ASIC-uri verificabile (2015)
de Riad Wahby, Max Howald, Siddharth Garg, abhi shelat, Michael Walfish

Această lucrare ia în considerare problema modului de utilizare sigur și fructuoasă a unui ASIC fabricat într-o turnătorie nede încredere (în 2015, existau doar cinci țări cu turnătorii de top). Abordarea este ca ASIC-ul rapid, dar de încredere, să demonstreze corectitudinea ieșirii sale unui verificator care rulează pe un ASIC mai lent, dar de încredere. Soluția este interesantă atâta timp cât timpul total de execuție a sistemului (adică, suma timpilor de execuție al dovezitorului și al verificatorului plus orice costuri de transmitere a datelor) este mai mic decât linia de bază naivă: timpul necesar pentru a rula calculul în întregime pe cea mai lentă. -dar-de încredere ASIC. Folosind o variantă a dovezilor interactive GKR/CMT/Allspice, lucrarea depășește într-adevăr linia de bază naivă pentru o serie de probleme fundamentale, inclusiv transformări teoretice numerice, potrivire a modelelor și operații cu curba eliptică. Această lucrare sugerează că unele sisteme de probă sunt mai potrivite pentru implementarea hardware decât altele. Optimizarea sistemelor de probă pentru implementarea hardware este acum primită considerabil atenţie, dar mai rămân multe de explorat.

verificabil Funcții de întârziere (2018)
de Dan Boneh, Joseph Bonneau, Benedikt Bünz și Ben Fisch

A introdus notarea funcțiilor de întârziere verificabile (VDF), o primitivă criptografică care este utilă pe scară largă în aplicațiile blockchain, de exemplu, în atenuarea posibilei manipulări a protocoalelor de consens de dovadă a mizei. SNARK-urile (în special pentru calculul verificabil incremental) oferă o cale către VDF-uri de ultimă generație.

Zexe: Activarea calculului privat descentralizat (2018)
de Sean Bowe, Alessandro Chiesa, Matthew Green, Ian Miers, Pratyush Mishra și Howard Wu

Zexe este un design pentru o platformă privată de contracte inteligente. Se poate vedea Zexe ca o extensie a Zerocash (descris mai sus). Zerocash permite rularea în lanț a unei singure aplicații (permițând utilizatorilor să transfere jetoane), protejând în același timp confidențialitatea datelor utilizatorului, de exemplu, cui trimit jetoane, de la care primesc jetoane, cantitatea de jetoane transferate etc. Zexe permite multe aplicații diferite (contracte inteligente) să ruleze pe același blockchain și să interacționeze între ele. Tranzacțiile sunt executate în afara lanțului, iar dovezile executării corecte sunt postate în lanț. Nu numai confidențialitatea datelor este protejată, la fel și confidențialitatea funcției. Aceasta înseamnă că dovada asociată fiecărei tranzacții nu dezvăluie nici măcar la ce aplicație (e) se referă tranzacția. O contribuție inginerească mai generală a Zexe este că a introdus BLS12-377, un grup de curbe eliptice care este util pentru compoziția eficientă de adâncime-1 a SNARK-urilor bazate pe asociere.

Mașini de stat replicate fără execuție replicată (2020)
de Jonathan Lee, Kirill Nikitin și Srinath Setty

Aceasta este una dintre puținele lucrări academice despre rollup-uri pentru scalabilitatea blockchain. Nu folosește termenul rollups, deoarece este anterior sau este contemporan cu conceptul introdus în afara literaturii academice.

Front-end-uri (transformări eficiente de la programe de calculator la reprezentări intermediare, cum ar fi satisfacția circuitului, R1CS și multe altele)

Reduceri rapide de la RAM-uri la probleme de satisfacție a constrângerilor succinte delegabile (2012)
de Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin și Eran Tromer

Dintr-o perspectivă modernă, aceasta este o lucrare timpurie privind transformările practice de calculator-program-în-circuit-SAT pentru o abstractizare a unei mașini virtuale (VM). Pe baza lucrărilor de la sfârșitul anilor 1970 până în anii 1990 (de exemplu, lucrarea lui Robson) această lucrare explică o reducere deterministă de la executarea unui VM pentru T pași la satisfacabilitatea unui circuit de dimensiunea O(T*polylog(T)).

Lucrările ulterioare, de exemplu, SNARK-uri pentru C și BCTV, a continuat să dezvolte front-end-uri printr-o abstractizare VM, iar instanțiile moderne includ proiecte precum Cairo, RISC Zero, și Poligonul Miden.

Luând calculul verificat bazat pe dovezi cu câțiva pași mai aproape de practic (2012)
de Srinath Setty, Victor Vu, Nikhil Panpalia, Benjamin Braun, Muqeet Ali, Andrew J. Blumberg și Michael Walfish

Această lucrare, denumită Ginger, este o altă contribuție timpurie la tehnicile practice front-end. Ginger a introdus gadget-uri pentru primitive de programare generală, cum ar fi condiționale și expresii logice, comparații și aritmetică pe biți prin împărțirea biților, aritmetica primitivă în virgulă mobilă etc. constrângeri aritmetice (similar cu ceea ce este acum cunoscut sub numele de R1CS), o reprezentare intermediară (IR) căreia i se poate aplica un back-end SNARK.

În timp ce lucrarea „Reduceri rapide” și descendenții săi folosesc o abordare „emulator CPU” în producerea IR-urilor (adică, IR-ul impune ca probatorul să ruleze corect un anumit program prin aplicarea funcției de tranziție a CPU pentru un număr specificat de pași) , Ginger și descendenții săi adoptă o abordare mai asemănătoare cu ASIC, producând IR-uri care sunt adaptate programului de calculator pe care probatorul pretinde că îl execută corect.

De exemplu, bufet arată că este posibil să se gestioneze fluxul de control complex în modelul ASIC, transformând un astfel de flux de control într-o mașină cu stări finite adaptată programului care este executat și că această abordare poate fi semnificativ mai eficientă decât construirea unui emulator CPU de uz general. xJsnark oferă o construcție eficientă pentru aritmetică multi-precizie, optimizări pentru RAM și ROM-uri și expune unui programator un limbaj de nivel înalt asemănător Java, care rămâne popular și astăzi. CirC observă că compilarea programelor de calculator la R1CS este strâns legată de tehnici bine cunoscute din analiza programului și construiește un set de instrumente de construcție a compilatorului care încorporează idei din ambele comunități („LLVM pentru reprezentări asemănătoare circuitelor”). Lucrările anterioare care au contribuit la front-end-urile în stil ASIC includ Pinocchio și Geppetto.

Lucrarea „Reduceri rapide” a folosit o construcție complicată și costisitoare numită „rețele de rutare” pentru așa-numitele verificarea memoriei (adică, asigurarea faptului că probatorul neîncrezător menține corect memoria cu acces aleatoriu a VM-ului pe toată durata execuției VM-ului a cărui corectitudine este dovedită). Această alegere a fost făcută deoarece lucrările timpurii, cum ar fi aceasta, căutau să obțină un PCP, care necesita ca front-end-ul să fie atât non-interactiv și informațional-teoretic sigur. Mai târziu a sunat munca cămară (un predecesor al lui bufet lucrarea menționată mai sus) a folosit arbori Merkle în locul rețelelor de rutare, obținând eficiență prin compilarea unei funcții hash algebrice (adică, „prietenoasă cu SNARK”), datorită Ajtai, în constrângeri. Acest lucru a dus la front-end-uri „securizate din punct de vedere computațional”. Astăzi, există o literatură largă de cercetare despre funcțiile hash prietenoase cu SNARK, cu exemple inclusiv Poseidon, MiMC, Beton armat, Salvare, Și mai mult.

Tehnicile de ultimă generație pentru a se asigura că probatorul menține RAM corect se bazează pe așa-numitele metode de „amprentare invariabilă la permutare” care datează cel puțin la Lipton (1989) și folosit pentru verificarea memoriei de către Blum şi colab. (1991). Aceste tehnici implică în mod inerent interacțiunea între un demonstrat și un verificator, dar pot fi făcute neinteractive cu transformarea Fiat-Shamir. Din câte știm, aceștia au fost introduși în literatura privind front-end-urile practice SNARK printr-un sistem numit Vram.

Tehnicile de amprentare invariante la permutare sunt acum utilizate în multe front-end-uri și SNARK-uri pentru abstracții de mașini virtuale, inclusiv, de exemplu Cairo. Ideile strâns legate au reapărut în contexte conexe în cele două lucrări de mai jos, care sunt utilizate pe scară largă în practică astăzi.

Probe de cunoștințe aproape liniare în timp zero pentru execuția corectă a programului (2018)
de Jonathan Bootle, Andrea Cerulli, Jens Groth, Sune Jakobsen și Mary Maller

Căutare: un protocol polinom simplificat pentru tabelele de căutare (2020)
de Ariel Gabizon și Zachary Williamson

Lucrările timpurii pe front-end-uri reprezentau operații „non-aritmetice” (cum ar fi verificări ale intervalului, operații pe biți și comparații întregi) în interiorul circuitelor și IR-uri aferente, prin ruperea elementelor de câmp în biți, efectuarea operațiilor pe acești biți și apoi „împachetarea” rezultatul înapoi într-un singur element de câmp. În ceea ce privește dimensiunea circuitului rezultat, aceasta are ca rezultat o supraîncărcare logaritmică per operație.

Cele două lucrări de mai sus (BCGJM și Plookup) oferă tehnici influente (bazate pe așa-numitele „tabele de căutare”) pentru reprezentarea mai eficientă a acestor operații în interiorul circuitelor, în sens amortizat. Aproximativ vorbind, pentru un parametru B ales de proiectantul front-end, aceștia reduc numărul de porți necesare pentru a reprezenta fiecare operație non-aritmetică din circuit cu un factor logaritmic în B, cu prețul doveditorului se angajează criptografic la un plus. vector „sfat” de lungime aproximativ B.