Canone a Conoscenza Zero

Nota del redattore: a16z crypto ha avuto una lunga serie di “pistole", dal nostro Canonico DAO l'anno scorso al ns Canone NFT prima (e prima ancora il nostro originale Cripto Canone) — assicurati di iscriverti al nostro newsletter settimanale web3 per ulteriori aggiornamenti e altre risorse curate.

Quindi bIn basso, abbiamo selezionato una serie di risorse per coloro che cercano di capire, approfondire e costruire con tutte le cose conoscenza zero: tecnologie potenti e fondamentali che detengono le chiavi della scalabilità blockchain e rappresentano il futuro delle applicazioni per la tutela della privacy e innumerevoli altre innovazioni a venire. Se hai suggerimenti per pezzi di alta qualità da aggiungere, faccelo sapere @a16zcrypto.

I sistemi a prova di conoscenza zero esistono da decenni: la loro introduzione da parte di Shafi Goldwasser, Silvio Micali e Charles Rackoff nel 1985 ha avuto un effetto trasformativo nel campo della crittografia ed è stata riconosciuta dall'ACM Turing Award assegnato a Goldwasser e Micali in 2012. Dal momento che questo lavoro - incluso il suo passaggio dalla teoria alla pratica e alle applicazioni in cripto/web3 oggi - ha richiesto decenni di lavoro, condividiamo per la prima volta nella nostra serie di canoni una seconda parte (per ora, inclusa qui sotto): una lista di lettura annotata da Giustino Thaler, seguendo la prima parte.

Ringraziamenti: Grazie anche a Michael Blau, Sam Ragsdale e Tim Roughgarden.

Fondamenti, background, evoluzioni

Alcuni di questi documenti riguardano anche la crittografia in generale (non tutti a conoscenza zero di per sé), inclusi i problemi che delineano o i progressi chiave che vengono affrontati oggi da prove di conoscenza zero: come garantire la privacy e l'autenticazione nelle reti aperte.

Nuove direzioni nella crittografia (1976)
di Whitfield Diffie e Martin Hellman
https://ee.stanford.edu/~hellman/publications/24.pdf

Un metodo per ottenere firme digitali e sistemi crittografici a chiave pubblica
di 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

Protocolli per crittosistemi a chiave pubblica (1980)
di Ralph Merkle
http://www.merkle.com/papers/Protocols.pdf

Comunicazioni sicure su canali non sicuri (1978)
di Ralph Merkle
https://www.merkle.com/1974/PuzzlesAsPublished.pdf

Uso di curve ellittiche in crittografia (1988)
di Victor Miller
https://link.springer.com/content/pdf/10.1007%2F3-540-39799-X_31.pdf

La complessità della conoscenza dei sistemi di prova interattivi (1985)
di Shafi Goldwasser, Silvio Micali, Charles Rackof
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.419.8132&rep=rep1&type=pdf

Prove computazionalmente valide (2000)
di Silvio Micali
https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/Computationally_Sound_Proofs.pdf

Dalla resistenza alle collisioni estraibili a succinti argomenti di conoscenza non interattivi [SNARKs], e viceversa (2011)
di Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer
https://eprint.iacr.org/2011/443.pdf

Argomento efficiente a conoscenza zero per la correttezza di un shuffle (2012)
di Stephanie Bayer e Jens Groth
http://www0.cs.ucl.ac.uk/staff/J.Groth/MinimalShuffle.pdf

Conoscenza zero succinta non interattiva per un'architettura von Neumann (2013)
di Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer e Madars Virza
https://eprint.iacr.org/2013/879.pdf

Integrità computazionale sicura, scalabile, trasparente e post-quantistica (2018)
di Eli Ben-Sasson, Iddo Bentov, Yinon Horesh e Michael Riabzev
https://eprint.iacr.org/2018/046.pdf

Argomenti a conoscenza zero di monete pubbliche con spese generali di tempo e spazio (quasi) minime (2020)
di Alexander Block, Justin Holmgren, Alon Rosen, Ron Rothblum e Pratik Soni
https://www.iacr.org/cryptodb/data/paper.php?pubkey=30645

Panoramica e introduzioni

Dimostrazioni, argomentazioni e conoscenza zero — Una panoramica del calcolo verificabile e di prove e argomentazioni interattive, protocolli crittografici che consentono a un prover di fornire una garanzia a un verificatore che il prover abbia eseguito correttamente un calcolo richiesto, inclusa la conoscenza zero (laddove le prove non rivelano informazioni diverse dalla propria validità) . Gli argomenti Zk hanno una miriade di applicazioni in crittografia e sono passati dalla teoria alla pratica negli ultimi dieci anni.
di Justin Thaler
https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf

Un'evoluzione di modelli per dimostrazioni a conoscenza zero — Una rassegna di prove a conoscenza zero, in cui Meiklejohn (University College London, Google) esamina le applicazioni che ne stanno guidando lo sviluppo, i diversi modelli emersi per catturare queste nuove interazioni, le costruzioni che possiamo realizzare e il lavoro rimasto da fare.
di Sarah Meiklejohn
https://www.youtube.com/watch?v=HO97kVMI3SE

Sessioni di lavagna ZK — moduli introduttivi
con Dan Boneh et al
https://zkhack.dev/whiteboard/

Sicurezza e privacy per le criptovalute con zkps — sperimentando nella pratica la prova a conoscenza zero; cosa sono gli zkps e come funzionano... inclusa la "demo" dal vivo
di Zooko Wilcox
https://a16z.com/2019/08/29/security-and-privacy-for-crypto-with-zero-knowledge-proofs/

Argomenti tecnologici principali, spiegati — comprese le definizioni e le implicazioni della conoscenza zero in generale
di 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

Come il prossimo livello di privacy risolverà un web rotto
di Howard Wu
https://future.com/a-privacy-layer-for-the-web-can-change-everything/

Introduzione a zkSNARKs
con Howard Wu, Anna Rose
https://zeroknowledge.fm/38-2/

Perché e come funziona zk-SNARK: una spiegazione definitiva
di Maksym Petkus
https://arxiv.org/pdf/1906.07221.pdf

Introduzione alle dimostrazioni a conoscenza zero
di Fredrik Harrysson e Anna Rose
https://www.zeroknowledge.fm/21 [+ commento riassuntivo altrove qui]

Zk-SNARKs: sotto il cofano
di Vitalik Buterin
https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
parte 1, parte 2, parte 3

Velocità decentralizzata — sui progressi nelle prove di conoscenza zero, hardware decentralizzato
di Elena Burger
https://a16z.com/2022/04/15/zero-knowledge-proofs-hardware-decentralization-innovation/

Ricerca zk all'avanguardia — con zk ricercatore presso Ethereum Foundation
con Mary Maller, Anna Rose, Kobi Gurkan
https://zeroknowledge.fm/232-2/

Esplorando la ricerca zk — con direttore della ricerca presso DFINITY; anche dietro anticipazioni come Groth16
con Jens Groth, Anna Rose, Kobi Gurkan
https://zeroknowledge.fm/237-2/

SNARK ricerca e pedagogia — con uno dei co-fondatori di ZCash e Starkware
con Alessandro Chiesa, Anna Rose
https://zeroknowledge.fm/episode-200-snark-research-pedagogy-with-alessandro-chiesa/

Immersioni profonde, guide ai costruttori

Fondamenti di prove probabilistiche — un corso con 5 unità da prove interattive e altro
di Alessandro Chiesa
https://www.youtube.com/playlist?list=PLGkwtcB-DfpzST-medFVvrKhinZisfluC

STARKs — parte I, II, III
di 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 di uno STARK — un tutorial in sei parti che spiega i meccanismi di un sistema di prova STARK
di Alan Szepieniec
https://aszepieniec.github.io/stark-anatomy/

Design SNARK, parte 1 — sondaggio, uso nei rollup, altro
di Justin Thaler
https://www.youtube.com/watch?v=tg6lKPdR_e4

Design SNARK, parte 2 — rollup, prestazioni, sicurezza
di Justin Thaler
https://www.youtube.com/watch?v=cMAI7g3UcoI

Misurare le prestazioni di SNARK — frontend, backend, altro
di Justin Thaler
https://a16zcrypto.com/measuring-snark-performance-frontends-backends-and-the-future/

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

Il sistema PLONK a prova di conoscenza zero — serie di 12 brevi video su come funziona PLONK
di David Wong
https://www.youtube.com/playlist?list=PLBJMt6zV1c7Gh9Utg-Vng2V6EYVidTFCC

Dagli AIR ai RAP — come funziona l'aritmetizzazione in stile PLONK
di Ariel Gabizon
https://hackmd.io/@aztec-network/plonk-arithmetiization-air

Controlli multiset in PLONK e Plookup
di Ariel Gabizon
https://hackmd.io/@arielg/ByFgSDA7D

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

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

Applicazioni e tutorial: proof of concept, demo, strumenti, altro ancora

Zk applicato - risorse di apprendimento
per 0xPARC
https://learn.0xparc.org/materials/intro

Un ambiente di sviluppo online per zkSNARKs — zkREPL, un nuovo set di strumenti per interagire con il tooltack di Circom nel browser
di Kevin Kwok
https://zkrepl.dev (+ thread esplicativo qui)

Programmi aritmetici quadratici da zero a eroe
di Vitalik Buterin
https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

Su zkEVM
con Alex Gluchowski e Anna Rose
https://zeroknowledge.fm/175-2/

Diversi tipi di zkEVM
di Vitalik Buterin
https://vitalik.ca/general/2022/08/04/zkevm.html

Apprendimento automatico ZK — tutorial e demo per inserire una rete neurale in uno SNARK
di Horace Pan, Francis Ho e Henri Palacci
https://0xparc.org/blog/zk-mnist

Sulle lingue ZK
con Alex Ozdemir e Anna Rose
https://zeroknowledge.fm/172-2/

Dark Forest: applica la crittografia zk ai giochi — un gioco RTS (strategia in tempo reale) completamente decentralizzato e persistente
https://blog.zkga.me/announcing-darkforest

ZKP per ingegneri — uno sguardo agli ZKP della Foresta Oscura
https://blog.zkga.me/df-init-circuit

Un tuffo nella conoscenza zero
con Elena Nadolinkski, Anna Rose, James Prestwich
https://zeroknowledge.fm/182-2/

zkDocs: condivisione di informazioni a conoscenza zero
di Sam Ragsdale e Dan Boneh
https://a16zcrypto.com/zkdocs-zero-knowledge-information-sharing/

Airdrop crittografici a protezione della privacy con zero prove di conoscenza
di Sam Ragsdale
https://a16z.com/2022/03/27/crypto-airdrop-privacy-tool-zero-knowledge-proofs/

Cerimonie di installazione affidabili su catena -
di Valeria Nikolaenko e Sam Ragsdale
https://a16zcrypto.com/on-chain-trusted-setup-ceremony/

Normative sulle criptovalute, finanza illecita, privacy e altro – include la sezione sulla conoscenza zero in contesti normativi/di conformità; differenza tra tecnologie di "conservazione della privacy" e tecnologie di offuscamento
con Michele Korver, Jai Ramaswamy, Sonal Chokshi
https://web3-with-a16z.simplecast.com/episodes/crypto-regulations-sanctions-compliance-aml-ofac-news-explained

Altre risorse

Newsletter di zkMesh — una newsletter mensile che condivide le ultime novità in fatto di tecnologie decentralizzate di tutela della privacy, sviluppo di protocolli di privacy e sistemi a conoscenza zero
https://zkmesh.substack.com/

Podcast Conoscenza Zero — sulle ultime ricerche zk e sulle applicazioni zk e sugli esperti che creano tecnologia per la privacy abilitata alla crittografia
con Anna Rosa
https://zeroknowledge.fm/

…un elenco di letture commentate, per argomento e cronologia, di Justin Thaler:

SNARK da Linear PCP (aka SNARK con configurazione specifica del circuito)

Argomenti efficienti senza PCP brevi (2007)
di Yuval Ishai, Eyal Kushilevitz e Rafail Ostrovsky

Prima del 2007 circa, gli SNARK erano progettati principalmente tramite il Kilian-micali paradigma, di prendere una prova "breve" probabilisticamente verificabile (PCP) e "compilarla crittograficamente" in un argomento succinto tramite l'hashing di Merkle e la trasformazione Fiat-Shamir. Sfortunatamente, i PCP brevi sono complicati e poco pratici, anche oggi. Questo documento (IKO) ha mostrato come utilizzare la crittografia omomorfa per ottenere argomenti interattivi succinti (non trasparenti) da PCP "lunghi ma strutturati". Questi possono essere molto più semplici dei PCP brevi e gli SNARK risultanti hanno prove molto più brevi e verifiche più rapide. Questi argomenti sono stati inizialmente riconosciuti come aventi il ​​potenziale per l'efficienza pratica, e perfezionati e implementati, in Pepper. Sfortunatamente, gli argomenti di IKO hanno un dimostratore di tempo quadratico e una stringa di riferimento strutturata di dimensioni quadratiche, quindi non si adattano a calcoli di grandi dimensioni.

Programmi quadratici e NIZK succinti senza PCP (2012)
di Rosario Gennaro, Craig Gentry, Bryan Parno e Mariana Raykova

Questo documento rivoluzionario (GGPR) ha ridotto i costi di prova dell'approccio di IKO da quadratici nella dimensione del circuito a quasilineari. Basandosi sul lavoro precedente di Grotto ed Lipma, ha anche fornito SNARK tramite crittografia basata sull'accoppiamento, piuttosto che argomenti interattivi come in IKO. Ha descritto i suoi SNARK nel contesto di quelli che ora vengono definiti problemi di soddisfazione dei vincoli di rango 1 (R1CS), una generalizzazione della soddisfacibilità del circuito aritmetico.

Questo documento è servito anche come base teorica per i primi SNARK a vedere la distribuzione commerciale (ad esempio, in ZCash) e ha portato direttamente agli SNARK che rimangono popolari oggi (ad esempio, Groth16). Sono arrivate le prime implementazioni delle argomentazioni di GGPR Zaatar ed Pinocchioe le varianti successive includono SNARK per C ed BCTV. BCIOP ha fornito un quadro generale che chiarisce queste trasformazioni da PCP lineari a SNARK (vedi anche Appendice A di Zaatar) e ne descrive varie esemplificazioni.

Sulla dimensione degli argomenti non interattivi basati sull'abbinamento (2016)
di Jens Groth

Questo documento, chiamato colloquialmente Groth16, ha presentato un perfezionamento degli SNARK di GGPR che raggiunge costi di verifica concreti all'avanguardia anche oggi (le prove sono 3 elementi di gruppo e la verifica è dominata da tre operazioni di abbinamento, almeno assumendo che il pubblico l'input è breve). La sicurezza è dimostrata nel modello di gruppo generico.

SNARK con configurazione affidabile universale

PlonK: Permutazioni su basi di Lagrange per argomenti ecumenici non interattivi della conoscenza (2019)
di Ariel Gabizon, Zachary Williamson e Oana Ciobotaru

Marlin: preelaborazione di zkSNARK con SRS universale e aggiornabile (2019)
di Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely e Nicholas Ward

Sia PlonK che Marlin sostituiscono la configurazione affidabile specifica del circuito in Groth16 con una configurazione universale. Questo va a scapito di prove di stampa 4x-6x più grandi. Si può pensare che PlonK e Marlin svolgano il lavoro specifico del circuito durante l'installazione affidabile in Groth16 e predecessori e lo spostino in una fase di pre-elaborazione che avviene dopo la configurazione affidabile, nonché durante la generazione di prove SNARK.

La capacità di elaborare circuiti arbitrari e sistemi R1CS in questo modo è talvolta chiamata olografia o impegni di calcolo ed è stata anche descritta in spartano (discusso più avanti in questa compilation). Poiché durante la generazione delle prove viene svolto più lavoro, i prover di PlonK e Marlin sono più lenti di Groth16 per un determinato circuito o istanza R1CS. Tuttavia, a differenza di Groth16, PlonK e Marlin possono essere fatti funzionare con rappresentazioni intermedie più generali rispetto a R1CS.

Schemi di impegno polinomiale, una primitiva crittografica chiave negli SNARK

Impegni a dimensione costante per i polinomi e le loro applicazioni (2010)
di Aniket Kate, Gregory Zaverucha e Ian Goldberg

Questo articolo ha introdotto la nozione di schemi di impegno polinomiale. Ha fornito uno schema per polinomi univariati (comunemente chiamati impegni KZG) con impegni di dimensione costante e prove di valutazione. Lo schema utilizza una configurazione affidabile (cioè una stringa di riferimento strutturata) e una crittografia basata sull'accoppiamento. Rimane estremamente popolare nella pratica oggi ed è utilizzato negli SNARK tra cui PlonK e Marlin discussi sopra (e Groth16 utilizza tecniche crittografiche estremamente simili).

Fast Reed-Solomon Interactive Oracle Prove di prossimità (2017)
di Eli Ben-Sasson, Iddo Bentov, Ynon Horesh, Michael Riabzev

Fornisce una prova di oracolo interattiva (IOP) per il test di Reed-Solomon, ovvero dimostrando che una stringa impegnata è vicina alla tabella di valutazione di un polinomio univariato. Combinato con Merkle-hashing e la trasformazione Fiat-Shamir, questo produce uno schema di impegno polinomiale trasparente con prove di valutazione di dimensioni polilogaritmiche (vedi VP19 per dettagli). Oggi, questo rimane il più breve tra gli schemi di impegno polinomiale plausibilmente post-quantistico.

Ligero: argomenti sublineari leggeri senza una configurazione affidabile (2017)
di Scott Ames, Carmit Hazay, Yuval Ishai e Muthuramakrishnan Venkitasubramaniam

Simile a FRI, questo lavoro fornisce una IOP per il test Reed-Solomon, ma con una lunghezza di prova della radice quadrata anziché polilogaritmica. teorico lavori ha mostrato che, sostituendo il codice Reed-Solomon con un diverso codice di correzione degli errori con una codifica più veloce, si può ottenere un dimostratore a tempo lineare che inoltre funziona in modo nativo su qualsiasi campo. Questo approccio è stato perfezionato e implementato Frenata ed Orion, offrendo prestazioni di prova all'avanguardia.

A prova di proiettile: brevi prove per transazioni riservate e altro (2017)
di Benedikt Bunz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille e Greg Maxwell

Perfezionamento del lavoro precedente da parte di BCCGP, Bulletproofs fornisce uno schema di impegno polinomiale trasparente (in effetti, una generalizzazione chiamata argomento di prodotto interno) basato sulla durezza del calcolo dei logaritmi discreti con dimensione della prova logaritmica ma tempo di verifica lineare. Lo schema rimane popolare oggi grazie alla sua trasparenza e alle prove brevi (ad esempio, è utilizzato in ZCash Orchard e Monero).

Dory: argomenti efficienti e trasparenti per prodotti interni generalizzati e impegni polinomiali (2020)
di Jonathan Lee

Dory riduce il tempo di verifica in Bulletproof da lineare a logaritmico, preservando la trasparenza e le prove di dimensioni logaritmiche (sebbene concretamente più grandi di Bulletproofs) e trasparenza. Utilizza accoppiamenti e si basa sul presupposto SXDH.

Prove interattive, prove interattive multi-prover e SNARK associati

Delegare il calcolo: prove interattive per i Babbani (2008)
di Shafi Goldwasser, Yael Tauman Kalai e Guy Rothblum

Prima di questo documento, le prove interattive di uso generale richiedevano a tempo superpolinomiale prover. Questo documento fornisce un protocollo di prova interattivo, comunemente chiamato protocollo GKR, con un verificatore di tempo polinomiale e un verificatore di tempo quasilineare, per qualsiasi problema che possieda un algoritmo parallelo efficiente (equivalentemente, la dimostrazione interattiva si applica a qualsiasi circuito aritmetico con profondità ridotta).

Calcolo pratico verificato con prove interattive in streaming (2011)
di Graham Cormode, Michael Mitzenmacher, Justin Thaler

Questo documento (a volte chiamato CMT) ha ridotto il tempo di prova nel protocollo GKR da quartico nella dimensione del circuito a quasilineare. Ha prodotto la prima implementazione di una dimostrazione interattiva generica. Una linea di opere successive (Pepe di Giamaica, Tallero13, Giraffae Libra) ha ridotto ulteriormente il tempo di esecuzione del prover, da quasi lineare a lineare nella dimensione del circuito.

vSQL: verifica di query SQL arbitrarie su database dinamici in outsourcing (2017)
di Yupeng Zhang, Daniel Genkin, Jonathan Katz, Dimitrios Papadopoulos e Charalampos Papamanthou

Benché il titolo si riferisca ad una specifica area applicativa (banche dati), i contributi di questo contributo sono più generali. In particolare, ha osservato che si possono ottenere argomenti succinti per la soddisfacibilità del circuito combinando dimostrazioni interattive con schemi di impegno polinomiale (per polinomi multilineari).

Più tardi lavori reso gli argomenti a conoscenza zero e ha introdotto diversi schemi di impegno per polinomi multilineari.

Spartan: zkSNARK efficienti e generici senza una configurazione affidabile (2019)
di Srinath Setty

Ottiene SNARK per la soddisfacibilità del circuito e R1CS combinando prove interattive multi-prover (MIP) con schemi di impegno polinomiale, basandosi sul lavoro precedente su MIP concretamente efficienti chiamati Trifoglio. L'effetto è quello di ottenere SNARK con prove più brevi rispetto a quelle derivate da prove interattive come il protocollo GKR discusso sopra. Analogamente a PlonK e Marlin, Spartan mostra anche come elaborare circuiti arbitrari e sistemi R1CS tramite pre-elaborazione e generazione di prove SNARK.

Spartan ha utilizzato uno schema di impegno polinomiale da Irace. Lavori successivi chiamati Frenata ed Orion combinare il MIP di Spartan con altri schemi di impegno polinomiale per produrre i primi SNARK implementati con un prover a tempo lineare.

PCP e IOP brevi

PCP brevi con complessità di query Polylog (2005)
di Eli Ben-Sasson e Madhu Sudan

 Questo lavoro teorico ha fornito la prima prova probabilisticamente verificabile (PCP) con lunghezza della prova quasilineare nella dimensione del calcolo da verificare e costo della query polilogaritmica (sebbene il tempo di verifica lineare). Dopo la trasformazione Kilian-Micali dei PCP in SNARK, questo è stato un passo verso gli SNARK con un dimostratore di tempo quasi lineare e un verificatore di tempo polilogaritmico.

Lavoro teorico successivo ridotto il tempo del verificatore a polilogaritmico. Successivo il lavoro incentrato sulla pratica ha perfezionato questo approccio, ma i PCP brevi rimangono poco pratici oggi. Per ottenere pratici SNARK, dopo lavori girato a una generalizzazione interattiva di PCP chiamata Prove Oracle interattive (IOP). Questi sforzi hanno portato a e continuare VEN, un popolare schema di impegno polinomiale discusso nella sezione impegni polinomiali di questa compilation.

Altre opere in questa categoria includono ZKBoo e i suoi discendenti. Questi non ottengono dimostrazioni succinte, ma hanno buoni fattori costanti e quindi sono attraenti per dimostrare piccole affermazioni. Hanno portato a famiglie di firme post-quantistiche come Picnic che hanno stato ottimizzati in alcuni lavori. ZKBoo si presenta come seguendo un paradigma di design distinto chiamato MPC in testa, ma restituisce un IOP.

SNARK ricorsivi

Il calcolo incrementale o le prove di conoscenza implicano efficienza nel tempo/spazio (2008)
di Paolo Valoroso

Questo lavoro ha introdotto la nozione fondamentale di calcolo incrementale verificabile (IVC), in cui il prover esegue un calcolo e mantiene in ogni momento una prova che il calcolo finora è stato corretto. Ha costruito IVC tramite la composizione ricorsiva di SNARK. Ecco, il solidità della conoscenza la proprietà degli SNARK è essenziale per stabilire la solidità degli argomenti non interattivi composti in modo ricorsivo. Questo documento ha anche fornito un estrattore di conoscenza estremamente efficiente per SNARK derivati ​​​​da PCP (secondo il paradigma Kilian-Micali).

Conoscenza zero scalabile tramite cicli di curve ellittiche (2014)
di Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer e Madars Virza

A seguire lavoro teorico, questo documento ha utilizzato l'applicazione ricorsiva di una variante di SNARK di GGPR, per fornire la prima implementazione di IVC per una macchina virtuale semplice (TinyRAM, dal SNARK per C carta).

Introdotta anche la nozione di cicli di curve ellittiche, utili per comporre ricorsivamente SNARK che fanno uso della crittografia delle curve ellittiche.

Composizione di prova ricorsiva senza una configurazione affidabile (2019)
di Sean Bowe, Jack Grigg e Daira Hopwood

Questo lavoro (chiamato Halo) studia come comporre ricorsivamente SNARK trasparenti. Questo è più impegnativo che comporre quelli non trasparenti perché la procedura di verifica negli SNARK trasparenti può essere molto più costosa.

Questo ha poi acceso a linea of lavoro che è culminato in sistemi come Nova ottenere prestazioni IVC all'avanguardia, superiori anche a quelle ottenute dalla composizione di SNARK non trasparenti come Groth16.

Applicazioni

Zerocash: pagamenti anonimi decentralizzati da Bitcoin (2014)
di Eli Ben Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, Madars Virza

Basandosi sul lavoro precedente compreso Zerocoin (e con Moneta Pinnochio come lavoro simultaneo), questo documento utilizza SNARK derivati ​​da GGPR per progettare una criptovaluta privata. Ha portato a ZCash.

Geppetto: calcolo verificabile versatile (2014)
di Craig Costello, Cédric Fournet, Jon Howell, Markulf Kohlweiss, Benjamin Kreuter, Michael Naehrig, Bryan Parno e Samee Zahur

Geppetto probabilmente precede l'esplosione di interesse per l'esecuzione di contratti intelligenti privati, essendo stato scritto circa un anno dopo la creazione di Ethereum. Pertanto, non è presentato nel contesto dell'esecuzione di contratti intelligenti privati. Tuttavia, utilizza la ricorsione a profondità limitata degli SNARK per consentire a un prover non attendibile di eseguire qualsiasi programma per computer privato (impegnato/firmato) su dati privati, senza rivelare informazioni sul programma in esecuzione o sui dati su cui viene eseguito. Di conseguenza, è un predecessore del lavoro su piattaforme private di contratti intelligenti, come Zexe [descritto sotto].

ASIC verificabili (2015)
di Riad Wahby, Max Howald, Siddharth Garg, abhi shelat, Michael Walfish

Questo documento esamina il problema di come utilizzare in modo sicuro e fruttuoso un ASIC prodotto in una fonderia non affidabile (nel 2015 c'erano solo cinque nazioni con fonderie di fascia alta). L'approccio consiste nel fare in modo che l'ASIC veloce ma non affidabile provi la correttezza del suo output a un verificatore che funziona su un ASIC più lento ma affidabile. La soluzione è interessante fintanto che il tempo totale di esecuzione del sistema (cioè la somma dei tempi di esecuzione del prover e del verificatore più eventuali costi di trasmissione dei dati) è inferiore alla linea di base ingenua: il tempo necessario per eseguire il calcolo per intero sul più lento -ma-fidato ASIC. Utilizzando una variante delle dimostrazioni interattive GKR/CMT/Allspice, l'articolo supera effettivamente la linea di base ingenua per una serie di problemi fondamentali, comprese le trasformazioni teoriche dei numeri, il pattern matching e le operazioni su curve ellittiche. Questo lavoro suggerisce che alcuni sistemi di prova sono più adatti per l'implementazione hardware rispetto ad altri. L'ottimizzazione dei sistemi di prova per l'implementazione dell'hardware è ora in arrivo notevole attenzione, ma resta ancora molto da esplorare.

Verificabile Funzioni di ritardo (2018)
di Dan Boneh, Joseph Bonneau, Benedikt Bünz e Ben Fisch

Introdotta la notazione delle funzioni di ritardo verificabili (VDF), una primitiva crittografica ampiamente utile nelle applicazioni blockchain, ad esempio per mitigare la possibile manipolazione dei protocolli di consenso proof-of-stake. Gli SNARK (soprattutto per il calcolo incrementale verificabile) offrono un percorso verso VDF all'avanguardia.

Zexe: abilitazione del calcolo privato decentralizzato (2018)
di Sean Bowe, Alessandro Chiesa, Matthew Green, Ian Miers, Pratyush Mishra e Howard Wu

Zexe è un progetto per una piattaforma di smart contract privata. Si può vedere Zexe come un'estensione di Zerocash (descritto sopra). Zerocash consente di eseguire una singola applicazione in catena (consentendo agli utenti di trasferire i token) proteggendo al contempo la privacy dei dati degli utenti, ad esempio a chi stanno inviando i token, da cui ricevono i token, la quantità di token trasferiti, ecc. Zexe consente molti diverse applicazioni (smart contract) da girare sulla stessa blockchain e interagire tra loro. Le transazioni vengono eseguite fuori catena e le prove della corretta esecuzione vengono pubblicate sulla catena. Non solo la privacy dei dati è protetta, ma anche la privacy delle funzioni. Ciò significa che la prova associata a ciascuna transazione non rivela nemmeno a quale applicazione si riferisce la transazione. Un contributo ingegneristico più generale di Zexe è che ha introdotto BLS12-377, un gruppo di curve ellittiche utile per una composizione efficiente della profondità 1 di SNARK basati sull'accoppiamento.

Macchine a stati replicate senza esecuzione replicata (2020)
di Jonathan Lee, Kirill Nikitin e Srinath Setty

Questo è uno dei pochi articoli accademici sui rollup per la scalabilità blockchain. Non utilizza il termine rollup, perché è antecedente o contemporaneo al concetto introdotto al di fuori della letteratura accademica.

Front-end (trasformazioni efficienti da programmi per computer a rappresentazioni intermedie come soddisfacibilità del circuito, R1CS e altro)

Riduzioni rapide dalle RAM ai problemi di soddisfazione dei vincoli succinti delegabili (2012)
di Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin e Eran Tromer

Da una prospettiva moderna, questo è uno dei primi lavori sulle trasformazioni pratiche da programma di computer a SAT per un'astrazione di una macchina virtuale (VM). Basandosi su opere dalla fine degli anni '1970 agli anni '1990 (ad es Robson) questo documento illustra una riduzione deterministica dall'esecuzione di una VM per passaggi T alla soddisfacibilità di un circuito di dimensione O(T*polylog(T)).

Documenti successivi, ad es. SNARK per C ed BCTV, ha continuato a sviluppare front-end tramite un'astrazione VM e le istanze moderne includono progetti come Cairo, RISCZeroe Poligono Miden.

Facendo un calcolo verificato basato su prove un po' più vicino alla praticità (2012)
di Srinath Setty, Victor Vu, Nikhil Panpalia, Benjamin Braun, Muqeet Ali, Andrew J. Blumberg e Michael Walfish

Questo documento, denominato Ginger, è un altro dei primi contributi alle tecniche pratiche di front-end. Ginger ha introdotto gadget per primitive di programmazione generali come condizionali ed espressioni logiche, confronti e aritmetica bit per bit tramite divisione dei bit, aritmetica primitiva in virgola mobile, ecc. Ha utilizzato questi gadget per fornire il primo front-end implementato da un linguaggio di alto livello a un basso grado vincoli aritmetici (simili a ciò che ora è noto come R1CS), una rappresentazione intermedia (IR) a cui può essere applicato un back-end SNARK.

Considerando che il documento "Fast Reductions" e i suoi discendenti utilizzano un approccio "CPU-emulatore" nella produzione di IR (cioè, l'IR impone che il prover abbia eseguito correttamente un particolare programma applicando la funzione di transizione della CPU per un numero specificato di passaggi) , Ginger e i suoi discendenti adottano un approccio più simile all'ASIC, producendo IR adattati al programma per computer che il prover afferma di eseguire correttamente.

Per esempio, buffet mostra che è possibile gestire un flusso di controllo complesso nel modello ASIC, trasformando tale flusso di controllo in una macchina a stati finiti adattata al programma in esecuzione, e che questo approccio può essere significativamente più efficiente rispetto alla creazione di un emulatore di CPU generico. xJsnark fornisce una costruzione efficiente per aritmetica multi-precisione, ottimizzazioni per RAM e ROM ed espone un linguaggio di alto livello simile a Java a un programmatore, che rimane popolare oggi. Circ osserva che la compilazione di programmi per computer in R1CS è strettamente correlata a tecniche ben note dall'analisi del programma e crea un toolkit di costruzione del compilatore che incorpora idee da entrambe le comunità ("LLVM per rappresentazioni simili a circuiti"). I lavori precedenti che hanno contribuito ai front-end in stile ASIC includono Pinocchio ed Geppetto.

Il documento "Fast-Reductions" utilizzava una costruzione complicata e costosa chiamata "reti di instradamento" per le cosiddette controllo della memoria (ossia, assicurarsi che il prover non attendibile mantenga correttamente la memoria ad accesso casuale della VM durante l'esecuzione della VM la cui correttezza è stata dimostrata). Questa scelta è stata fatta perché i primi lavori come questo cercavano di ottenere un PCP, che richiedeva che lo fosse il front-end entrambi non interattivo e informazioni teoricamente sicuro. Il lavoro successivo ha chiamato Dispensa (un predecessore del buffet lavoro menzionato sopra) ha utilizzato Merkle-tree al posto delle reti di routing, ottenendo efficienza compilando una funzione hash algebrica (cioè "SNARK-friendly"), grazie a Ajtai, in vincoli. Ciò ha portato a front-end "sicuri dal punto di vista computazionale". Oggi esiste un'ampia letteratura di ricerca sulle funzioni hash compatibili con SNARK, con esempi tra cui Poseidon, MiMC, Cemento armato, SalvataggioE altro ancora.

Le tecniche all'avanguardia per garantire che il prover mantenga correttamente la RAM si basano sui cosiddetti metodi di "impronta digitale invariante permutazione" risalenti almeno al Lipton (1989) e utilizzato per il controllo della memoria da Blum et al. (1991). Queste tecniche implicano intrinsecamente l'interazione tra un verificatore e un verificatore, ma possono essere rese non interattive con la trasformazione Fiat-Shamir. Per quanto ne sappiamo, sono stati introdotti nella letteratura sui front-end SNARK pratici da un sistema chiamato VRAM.

Le tecniche di fingerprinting invarianti per mutazione sono ora utilizzate in molti front-end e SNARK per le astrazioni di macchine virtuali, incluso ad esempio Cairo. Idee strettamente correlate sono riapparse in contesti correlati nelle due opere seguenti, che sono ampiamente utilizzate nella pratica oggi.

Prove a conoscenza zero a tempo quasi lineare per la corretta esecuzione del programma (2018)
di Jonathan Bootle, Andrea Cerulli, Jens Groth, Sune Jakobsen e Mary Maller

Plookup: un protocollo polinomiale semplificato per tabelle di ricerca (2020)
di Ariel Gabizon e Zachary Williamson

I primi lavori sui front-end rappresentavano operazioni "non aritmetiche" (come controlli di intervallo, operazioni bit per bit e confronti di interi) all'interno di circuiti e relativi IR suddividendo gli elementi del campo in bit, eseguendo le operazioni su questi bit e quindi "comprimendo" il risultato di nuovo in un singolo elemento di campo. In termini di dimensioni del circuito risultante, ciò si traduce in un sovraccarico logaritmico per operazione.

I due lavori precedenti (BCGJM e Plookup) forniscono tecniche influenti (basate sulle cosiddette "tabelle di ricerca") per rappresentare in modo più efficiente queste operazioni all'interno dei circuiti, in senso ammortizzato. In parole povere, per alcuni parametri B scelti dal progettista front-end, questi riducono il numero di porte necessarie per rappresentare ogni operazione non aritmetica nel circuito di un fattore logaritmico in B, a costo del prover che si impegna crittograficamente a un extra vettore "consiglio" di lunghezza approssimativamente B.