Nul Kennis Canon

Noot van de redactie: a16z crypto heeft een lange reeks van de "geweren", van onze DAO-canon vorig jaar naar onze NFT-Canon eerder (en daarvoor onze originele Crypto-Canon) — zorg ervoor dat u zich aanmeldt voor onze web3 wekelijkse nieuwsbrief voor meer updates en andere beheerde bronnen.

Dus bHieronder hebben we een reeks bronnen verzameld voor diegenen die alles willen begrijpen, dieper willen gaan en willen bouwen nul kennis: krachtige, fundamentele technologieën die de sleutels vormen tot blockchain-schaalbaarheid en die de toekomst vertegenwoordigen van privacybeschermende applicaties en talloze andere innovaties die eraan komen. Als je suggesties hebt voor stukken van hoge kwaliteit om toe te voegen, laat het ons dan weten @a16zcrypto.

Zero-knowledge proof-systemen bestaan ​​al tientallen jaren: hun introductie door Shafi Goldwasser, Silvio Micali en Charles Rackoff in 1985 had een transformerend effect op het gebied van cryptografie en werd erkend door de ACM Turing Award, toegekend aan Goldwasser en Micali in 2012. Aangezien dit werk - inclusief de overgang van theorie naar praktijk en toepassingen in crypto/web3 vandaag - decennia in de maak is, delen we ook voor het eerst in onze canons-serie een deel twee (voor nu, hieronder opgenomen): een leeslijst geannoteerd door Justin Taler, naar aanleiding van het eerste deel hieronder.

Dankbetuiging: ook dank aan Michael Blau, Sam Ragsdale en Tim Roughgarden.

Fundamenten, achtergronden, evoluties

Sommige van deze artikelen gaan ook meer over cryptografie in het algemeen (niet allemaal zero-knowledge per se), inclusief het schetsen van problemen of belangrijke vorderingen die tegenwoordig worden aangepakt door zero-knowledge proofs: hoe privacy en authenticatie in open netwerken te waarborgen.

Nieuwe richtingen in cryptografie (1976)
door Whitfield Diffie en Martin Hellman
https://ee.stanford.edu/~hellman/publications/24.pdf

Een methode voor het verkrijgen van digitale handtekeningen en cryptosystemen met openbare sleutels
door 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

Protocollen voor cryptosystemen met openbare sleutels (1980)
door Ralph Merkle
http://www.merkle.com/papers/Protocols.pdf

Beveiligde communicatie via onveilige kanalen (1978)
door Ralph Merkle
https://www.merkle.com/1974/PuzzlesAsPublished.pdf

Gebruik van elliptische krommen in cryptografie (1988)
door Victor Miller
https://link.springer.com/content/pdf/10.1007%2F3-540-39799-X_31.pdf

De kenniscomplexiteit van interactieve bewijssystemen (1985)
door Shafi Goldwasser, Silvio Micali, Charles Rackof
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.419.8132&rep=rep1&type=pdf

Computationele geluidsisolatie (2000)
door Silvio Micali
https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/Computationally_Sound_Proofs.pdf

Van extraheerbare botsingsweerstand tot beknopte niet-interactieve kennisargumenten [SNARKs], en weer terug (2011)
door Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer
https://eprint.iacr.org/2011/443.pdf

Efficiënt nul-kennisargument voor correctheid van een shuffle (2012)
door Stephanie Bayer en Jens Groth
http://www0.cs.ucl.ac.uk/staff/J.Groth/MinimalShuffle.pdf

Beknopte niet-interactieve nulkennis voor een von Neumann Architecture (2013)
door Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer en Madars Virza
https://eprint.iacr.org/2013/879.pdf

Schaalbare, transparante en post-kwantum veilige computationele integriteit (2018)
door Eli Ben-Sasson, Iddo Bentov, Yinon Horesh en Michael Riabzev
https://eprint.iacr.org/2018/046.pdf

Public-coin zero-knowledge argumenten met (bijna) minimale overheadkosten in tijd en ruimte (2020)
door Alexander Block, Justin Holmgren, Alon Rosen, Ron Rothblum en Pratik Soni
https://www.iacr.org/cryptodb/data/paper.php?pubkey=30645

Overzichten & intro's

Bewijzen, argumenten en nulkennis — Een overzicht van verifieerbare computer- en interactieve bewijzen en argumenten, cryptografische protocollen waarmee een bewijzer een verificateur kan garanderen dat de bewijzer een gevraagde berekening correct heeft uitgevoerd, inclusief nulkennis (waarbij bewijzen geen andere informatie onthullen dan hun eigen geldigheid) . Zk-argumenten hebben talloze toepassingen in cryptografie en hebben het afgelopen decennium de sprong gemaakt van theorie naar praktijk.
door Justin Thaler
https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf

Een evolutie van modellen voor zero-knowledge proofs — Een overzicht van zero-knowledge proofs, waarbij Meiklejohn (University College London, Google) kijkt naar de toepassingen die hun ontwikkeling stimuleren, de verschillende modellen die zijn ontstaan ​​om deze nieuwe interacties vast te leggen, de constructies die we kunnen bereiken en het werk over om te doen.
door Sarah Meiklejohn
https://www.youtube.com/watch?v=HO97kVMI3SE

ZK whiteboard-sessies — inleidende modules
met Dan Boneh et al
https://zkhack.dev/whiteboard/

Beveiliging en privacy voor crypto met zkps — pionieren met het zero-knowledge proof in de praktijk; wat zkps zijn en hoe ze werken ... inclusief live stage "demo"
door Zooko Wilcox
https://a16z.com/2019/08/29/security-and-privacy-for-crypto-with-zero-knowledge-proofs/

Top technische onderwerpen, uitgelegd — inclusief definities en implicaties van nulkennis in het algemeen
door 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

Hoe de komende privacylaag een gebroken web zal repareren
door Howard Wu
https://future.com/a-privacy-layer-for-the-web-can-change-everything/

Inleiding tot zkSNARKs
met Howard Wu, Anna Rose
https://zeroknowledge.fm/38-2/

Waarom en hoe zk-SNARK werkt: een definitieve uitleg
door Maksym Petkus
https://arxiv.org/pdf/1906.07221.pdf

Een inleiding tot zero-knowledge proofs
door Fredrik Harrysson en Anna Rose
https://www.zeroknowledge.fm/21 [+ samenvatting elders hier]

Zk-SNARKs: onder de motorkap
door Vitalik Buterin
https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
deel 1, deel 2, deel 3

Gedecentraliseerde snelheid — over vooruitgang in zero-knowledge proofs, gedecentraliseerde hardware
door Elena Burger
https://a16z.com/2022/04/15/zero-knowledge-proofs-hardware-decentralization-innovation/

Baanbrekend zk-onderzoek — met zk onderzoeker bij Ethereum Foundation
met Mary Maller, Anna Rose, Kobi Gurkan
https://zeroknowledge.fm/232-2/

Zk-onderzoek verkennen — met onderzoeksdirecteur bij DFINITY; ook achter vorderingen zoals Groth16
met Jens Groth, Anna Rose, Kobi Gurkan
https://zeroknowledge.fm/237-2/

SNARK onderzoek & pedagogiek — met een van de medeoprichters van ZCash en Starkware
met Alessandro Chiesa, Anna Rose
https://zeroknowledge.fm/episode-200-snark-research-pedagogy-with-alessandro-chiesa/

Diepe duiken, bouwgidsen

Grondslagen van probabilistische bewijzen — een cursus met 5 eenheden van interactieve bewijzen en meer
door Alessandro Chiesa
https://www.youtube.com/playlist?list=PLGkwtcB-DfpzST-medFVvrKhinZisfluC

STARK's - deel I, II, III
door 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

Anatomie van een STARK - een zesdelige tutorial waarin de mechanica van een STARK-bewijssysteem wordt uitgelegd
door Alan Szepieniec
https://aszepieniec.github.io/stark-anatomy/

SNARK-ontwerp, deel 1 — enquête, gebruik in rollups, meer
door Justin Thaler
https://www.youtube.com/watch?v=tg6lKPdR_e4

SNARK-ontwerp, deel 2 — rollups, prestaties, beveiliging
door Justin Thaler
https://www.youtube.com/watch?v=cMAI7g3UcoI

SNARK-prestaties meten — frontends, backends, meer
door Justin Thaler
https://a16zcrypto.com/measuring-snark-performance-frontends-backends-and-the-future/

PLENK . begrijpen
https://vitalik.ca/general/2019/09/22/plonk.html

Het PLON zero-knowledge proof systeem — serie van 12 korte video's over hoe PLON werkt
door David Wong
https://www.youtube.com/playlist?list=PLBJMt6zV1c7Gh9Utg-Vng2V6EYVidTFCC

Van AIR's naar RAP's — hoe rekenkunde in PLON-stijl werkt
door Ariel Gabizon
https://hackmd.io/@aztec-network/plonk-arithmetiization-air

Multiset-controles in PLONK en Plookup
door Ariel Gabizon
https://hackmd.io/@arielg/ByFgSDA7D

Halo2-ontwerp — van ECC
https://zcash.github.io/halo2/design.html

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

Toepassingen & tutorials: proof of concepten, demo's, tools, meer

toegepast zk — leermiddelen
door 0xPARC
https://learn.0xparc.org/materials/intro

Een online ontwikkelomgeving voor zkSNARKs — zkREPL, een nieuwe set tools voor interactie met de Circom-toolstack in de browser
door Kevin Kwoko
https://zkrepl.dev (+ uitlegthread hier)

Kwadratische rekenprogramma's van nul tot held
door Vitalik Buterin
https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

Op zkEVM's
met Alex Gluchowski en Anna Rose
https://zeroknowledge.fm/175-2/

Verschillende soorten zkEVM's
door Vitalik Buterin
https://vitalik.ca/general/2022/08/04/zkevm.html

ZK-machine learning - tutorial & demo voor het plaatsen van een neuraal net in een SNARK
door Horace Pan, Francis Ho en Henri Palacci
https://0xparc.org/blog/zk-mnist

Op ZK-talen
met Alex Ozdemir en Anna Rose
https://zeroknowledge.fm/172-2/

Dark Forest — zk-cryptografie toepassen op games — een volledig gedecentraliseerd en persistent RTS-spel (realtime strategy)
https://blog.zkga.me/announcing-darkforest

ZKP's voor ingenieurs — een blik op de Dark Forest ZKP's
https://blog.zkga.me/df-init-circuit

Een duik in nulkennis
met Elena Nadolinkski, Anna Rose, James Prestwich
https://zeroknowledge.fm/182-2/

zkDocs: informatie delen zonder kennis
door Sam Ragsdale en Dan Boneh
https://a16zcrypto.com/zkdocs-zero-knowledge-information-sharing/

Privacybeschermende crypto-airdrops zonder kennisbewijzen
door Sam Ragsdale
https://a16z.com/2022/03/27/crypto-airdrop-privacy-tool-zero-knowledge-proofs/

Betrouwbare installatieceremonies in de keten -
door Valeria Nikolaenko en Sam Ragsdale
https://a16zcrypto.com/on-chain-trusted-setup-ceremony/

Crypto-regelgeving, illegale financiering, privacy en meer – bevat een sectie over nulkennis in regelgevings-/nalevingscontexten; verschil tussen "privacybehoud" versus verduisterende technologieën
met Michele Korver, Jai Ramaswamy, Sonal Chokshi
https://web3-with-a16z.simplecast.com/episodes/crypto-regulations-sanctions-compliance-aml-ofac-news-explained

Andere bronnen

zkMesh nieuwsbrief — een maandelijkse nieuwsbrief met de nieuwste gedecentraliseerde technologieën voor privacybehoud, ontwikkeling van privacyprotocollen en systemen zonder kennis
https://zkmesh.substack.com/

Zero Knowledge-podcast — over de nieuwste zk research & zk-applicaties en experts die privacytechnologie met cryptografie bouwen
met Anna Rose
https://zeroknowledge.fm/

... een geannoteerde leeslijst, per onderwerp en chronologie, door Justin Thaler:

SNARK's van lineaire PCP's (ook bekend als SNARK's met circuitspecifieke instellingen)

Efficiënte argumenten zonder korte PCP's (2007)
door Yuval Ishai, Eyal Kushilevitz en Rafail Ostrovsky

Vóór ongeveer 2007 werden SNARK's voornamelijk ontworpen via de Kilian-micali paradigma, van het nemen van een "kort" probabilistisch controleerbaar bewijs (PCP) en het "cryptografisch compileren" tot een beknopt argument via Merkle-hashing en de Fiat-Shamir-transformatie. Helaas zijn korte PCP's zelfs vandaag de dag nog ingewikkeld en onpraktisch. Dit artikel (IKO) liet zien hoe homomorfe versleuteling kan worden gebruikt om beknopte (niet-transparante) interactieve argumenten te verkrijgen uit "lange maar gestructureerde" PCP's. Deze kunnen veel eenvoudiger zijn dan korte PCP's, en de resulterende SNARK's hebben veel kortere bewijzen en snellere verificatie. Deze argumenten werden voor het eerst erkend als potentieel voor praktische efficiëntie, en verfijnd en geïmplementeerd, in Pepper. Helaas hebben de argumenten van IKO een kwadratische tijdbewijzer en een gestructureerde referentiereeks van kwadratische grootte, zodat ze niet kunnen worden geschaald naar grote berekeningen.

Kwadratische spanprogramma's en beknopte NIZK's zonder PCP's (2012)
door Rosario Gennaro, Craig Gentry, Bryan Parno en Mariana Raykova

Dit baanbrekende document (GGPR) verminderde de bewijskosten van IKO's aanpak van kwadratisch in de grootte van het circuit naar quasilineair. Voortbouwend op eerder werk van Grot en Lipmaa, het gaf ook SNARK's via op paren gebaseerde cryptografie, in plaats van interactieve argumenten zoals in IKO. Het beschreef zijn SNARK's in de context van wat nu wordt aangeduid als rang-1 constraint satisfaction (R1CS) problemen, een generalisatie van rekenkundige circuit-vervulbaarheid.

Dit artikel diende ook als de theoretische basis voor de eerste SNARK's die commercieel werden ingezet (bijv. in ZCash) en leidde direct tot SNARK's die vandaag de dag nog steeds populair zijn (bijv. Groth16). De eerste implementaties van de argumenten van GGPR kwamen binnen Zaatar en Pinocchio, en latere varianten omvatten SNARK's voor C en BCTV. BCIOP gaf een algemeen raamwerk dat deze lineaire-PCP's-naar-SNARK-transformaties verduidelijkt (zie ook bijlage A van Zaatar) en beschrijft verschillende uitvoeringen daarvan.

Over de grootte van op paren gebaseerde niet-interactieve argumenten (2016)
door Jens Groth

Dit artikel, in de volksmond Groth16 genoemd, presenteerde een verfijning van GGPR's SNARK's die zelfs vandaag de dag state-of-the-art concrete verificatiekosten opleveren (bewijzen zijn 3 groepselementen en verificatie wordt gedomineerd door drie koppelingsbewerkingen, tenminste in de veronderstelling dat het publiek ingang is kort). Veiligheid wordt bewezen in het generieke groepsmodel.

SNARK's met universele vertrouwde setup

PlonK: Permutaties over Lagrange-bases voor oecumenische niet-interactieve argumenten van kennis (2019)
door Ariel Gabizon, Zachary Williamson en Oana Ciobotaru

Marlin: zkSNARK's voorbewerken met universele en bijwerkbare SRS (2019)
door Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely en Nicholas Ward

Zowel PlonK als Marlin vervangen de circuitspecifieke vertrouwde opstelling in Groth16 door een universele opstelling. Dit gaat ten koste van 4x-6x grotere bewijzen. Je kunt aan PlonK en Marlin denken dat ze het circuitspecifieke werk tijdens de vertrouwde setup in Groth16 en voorgangers nemen en het in een pre-processingfase brengen die plaatsvindt na de vertrouwde setup, evenals tijdens het genereren van SNARK-proof.

De mogelijkheid om willekeurige circuits en R1CS-systemen op deze manier te verwerken, wordt soms holografie of rekenverplichtingen genoemd, en werd ook beschreven in spartaans (wordt later in deze compilatie besproken). Omdat er meer werk gebeurt tijdens het genereren van bewijzen, zijn de provers van PlonK en Marlin langzamer dan Groth16 voor een bepaald circuit of R1CS-instantie. Echter, in tegenstelling tot Groth16, kunnen PlonK en Marlin worden gemaakt om te werken met meer algemene intermediaire representaties dan R1CS.

Polynomiale commitment-schema's, een sleutelcryptografische primitief in SNARK's

Toezeggingen van constante grootte aan veeltermen en hun toepassingen (2010)
door Aniket Kate, Gregory Zaverucha en Ian Goldberg

In dit artikel werd het begrip polynomiale verbintenisschema's geïntroduceerd. Het gaf een schema voor univariate polynomen (gewoonlijk KZG-verplichtingen genoemd) met verplichtingen van constante grootte en evaluatiebewijzen. Het schema maakt gebruik van een vertrouwde opstelling (dwz een gestructureerde referentiereeks) en op paren gebaseerde cryptografie. Het blijft vandaag extreem populair in de praktijk en wordt gebruikt in SNARK's, waaronder PlonK en Marlin die hierboven zijn besproken (en Groth16 gebruikt extreem vergelijkbare cryptografische technieken).

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

Geeft een interactief orakelbewijs (IOP) voor Reed-Solomon-testen - dat wil zeggen, bewijzen dat een vastgelegde string dicht bij de evaluatietabel van een univariate polynoom ligt. Gecombineerd met Merkle-hashing en de Fiat-Shamir-transformatie, levert dit een transparant polynomiaal commitment-schema op met evaluatiebewijzen van polylogaritmische grootte (zie VP19 voor details). Vandaag de dag is dit nog steeds de kortste van alle aannemelijke post-kwantumpolynomiale verbintenisregelingen.

Ligero: lichtgewicht sublineaire argumenten zonder een vertrouwde setup (2017)
door Scott Ames, Carmit Hazay, Yuval Ishai en Muthuramakrishnan Venkitasubramaniam

Net als bij FRI geeft dit werk een IOP voor Reed-Solomon-testen, maar met een vierkantswortelproeflengte in plaats van polylogaritmisch. theoretisch Bedrijven toonde aan dat, door de Reed-Solomon-code uit te wisselen voor een andere foutcorrigerende code met snellere codering, men een lineaire-tijdbewijzer kan verkrijgen die bovendien native over elk veld werkt. Deze aanpak is verfijnd en geïmplementeerd in Remmen en Orion, wat state-of-the-art bewijsprestaties oplevert.

Bulletproofs: korte bewijzen voor vertrouwelijke transacties en meer (2017)
door Benedikt Bunz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille en Greg Maxwell

Eerder werk verfijnen door: BCCGP, Bulletproofs geeft een transparant polynomiaal commitment-schema (in feite een generalisatie die een inwendig productargument wordt genoemd) op basis van de hardheid van het berekenen van discrete logaritmen met logaritmische bewijsgrootte maar lineaire verificatietijd. Het schema blijft vandaag populair vanwege zijn transparantie en korte bewijzen (het wordt bijvoorbeeld gebruikt in ZCash Orchard en Monero).

Dory: efficiënte, transparante argumenten voor gegeneraliseerde innerlijke producten en polynomiale verplichtingen (2020)
door Jonathan Lee

Dory reduceert de verificatietijd in Bulletproofs van lineair naar logaritmisch, met behoud van transparantie en bewijzen van logaritmische grootte (zij het concreet groter dan Bulletproofs) en transparantie. Maakt gebruik van koppelingen en is gebaseerd op de SXDH-aanname.

Interactieve bewijzen, interactieve bewijzen voor meerdere bewijzen en bijbehorende SNARK's

Berekening delegeren: interactieve bewijzen voor dreuzels (2008)
door Shafi Goldwasser, Yael Tauman Kalai en Guy Rothblum

Voorafgaand aan dit artikel waren interactieve proefdrukken voor algemene doeleinden vereist: superpolynomiale tijd bewijs. Dit artikel geeft een interactief bewijsprotocol, gewoonlijk het GKR-protocol genoemd, met een polynomiale tijdbewijzer en quasilineaire tijdverificator, voor elk probleem met een efficiënt parallel algoritme (equivalent is het interactieve bewijs van toepassing op elk rekenkundig circuit met een kleine diepte).

Praktisch geverifieerde berekening met streaming interactieve bewijzen (2011)
door Graham Cormode, Michael Mitzenmacher, Justin Thaler

Dit artikel (ook wel CMT genoemd) bracht de testtijd in het GKR-protocol terug van quartic in de grootte van het circuit naar quasilineair. Produceerde de eerste implementatie van een interactief bewijs voor algemene doeleinden. Een reeks volgende werken (Piment, Thaler13, Giraffe en libra) verminderde de looptijd van de rijswijzer verder, van quasilineair naar lineair in de grootte van het circuit.

vSQL: Willekeurige SQL-query's verifiëren via dynamische uitbestede databases (2017)
door Yupeng Zhang, Daniel Genkin, Jonathan Katz, Dimitrios Papadopoulos en Charalampos Papamanthou

Hoewel de titel verwijst naar een specifiek toepassingsgebied (databases), zijn de bijdragen van dit artikel meer algemeen. In het bijzonder merkte het op dat men beknopte argumenten voor circuit-vervulbaarheid kan verkrijgen door interactieve bewijzen te combineren met polynomiale commitment-schema's (voor multilineaire polynomen).

Later Bedrijven gerenderd de argumenten nul-kennis en introduceerde verschillende commitment-schema's voor multilineaire polynomen.

Spartaans: efficiënte en algemene zkSNARK's zonder vertrouwde setup (2019)
door Srinath Setty

Verkrijgt SNARK's voor circuit-satisfiability en R1CS door multi-prover interactieve bewijzen (MIP's) te combineren met polynomiale commitment-schema's, voortbouwend op eerder werk aan concreet efficiënte MIP's genaamd Klaver. Het effect is dat SNARK's worden verkregen met kortere bewijzen dan die welke zijn afgeleid van interactieve bewijzen zoals het hierboven besproken GKR-protocol. Analoog aan PlonK en Marlin, laat Spartan ook zien hoe willekeurige circuits en R1CS-systemen kunnen worden verwerkt via pre-processing en SNARK-proof-generatie.

Spartan gebruikte een polynomiaal commitment-schema van hyrax. Latere werken genaamd Remmen en Orion combineer Spartan's MIP met andere polynomiale commitment-schema's om de eerste geïmplementeerde SNARK's op te leveren met een lineaire-tijdbewijzer.

Korte PCP's en IOP's

Korte PCP's met Polylog Query Complexity (2005)
door Eli Ben-Sasson en Madhu Sudan

 Dit theoretische werk leverde het eerste probabilistisch controleerbare bewijs (PCP) op met een quasilineaire bewijslengte in de grootte van de te verifiëren berekening en polylogaritmische vraagkosten (hoewel lineaire verificatietijd). Na de Kilian-Micali-transformatie van PCP's in SNARK's, was dit een stap in de richting van SNARK's met quasi-lineaire tijdbewijzer en polylogaritmische tijdverificator.

Later theoretisch werk de verificatietijd teruggebracht tot polylogaritmisch. Volgend praktisch gericht werk verfijnde deze benadering, maar korte PCP's blijven vandaag onpraktisch. Om praktische SNARK's te verkrijgen, later Bedrijven gedraaid naar een interactieve generalisatie van PCP's genaamd Interactieve Oracle-bewijzen (IOP's). Deze inspanningen hebben geleid tot en bouwen voort op VR, een populair schema voor polynoomverbintenissen dat wordt besproken in het gedeelte over polynoomverbintenissen van deze compilatie.

Andere werken in deze categorie zijn onder meer: ZKBo en zijn nakomelingen. Deze leveren geen beknopte bewijzen op, maar ze hebben goede constante factoren en zijn daarom aantrekkelijk voor het bewijzen van kleine uitspraken. Ze hebben geleid tot families van post-kwantum handtekeningen zoals: Picknick die moeten geweest geoptimaliseerde in verscheidene Bedrijven. ZKBoo wordt gepresenteerd volgens een duidelijk ontwerpparadigma genaamd MPC-in-het-hoofd, maar het levert een IOP op.

Recursieve SNARK's

Incrementeel verifieerbare berekeningen of bewijzen van kennis impliceren tijd-/ruimte-efficiëntie (2008)
door Paul Valiant

Dit werk introduceerde de fundamentele notie van incrementeel verifieerbare berekening (IVC), waarbij een bewijzer een berekening uitvoert en te allen tijde een bewijs behoudt dat de berekening tot nu toe correct is geweest. Het construeerde IVC via recursieve samenstelling van SNARK's. Hier de kennis-degelijkheid eigenschap van SNARK's is essentieel voor het vaststellen van de deugdelijkheid van recursief samengestelde niet-interactieve argumenten. Dit artikel gaf ook een uiterst efficiënte kennisextractor voor PCP-afgeleide SNARK's (volgens het Kilian-Micali-paradigma).

Schaalbare nulkennis via cycli van elliptische krommen (2014)
door Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer en Madars Virza

volgend theoretisch werk, dit artikel gebruikte recursieve toepassing van een variant van GGPR's SNARK, om de eerste implementatie van IVC voor een eenvoudige virtuele machine (TinyRAM, van de SNARK's voor C papier).

Ook het begrip cycli van elliptische krommen geïntroduceerd, die nuttig zijn voor het recursief samenstellen van SNARK's die gebruik maken van cryptografie met elliptische krommen.

Recursieve bewijssamenstelling zonder een vertrouwde setup (2019)
door Sean Bowe, Jack Grigg en Daira Hopwood

Dit werk (Halo genaamd) bestudeert hoe transparante SNARK's recursief kunnen worden samengesteld. Dit is uitdagender dan het samenstellen van niet-transparante, omdat de verificatieprocedure in transparante SNARK's veel duurder kan zijn.

Dit leidde vervolgens tot een lijn of werk dat heeft geresulteerd in systemen zoals: Nova het bereiken van state-of-the-art IVC-prestaties, zelfs superieur aan die verkregen door de samenstelling van niet-transparante SNARK's zoals Groth16.

Toepassingen

Zerocash: gedecentraliseerde anonieme betalingen van Bitcoin (2014)
door Eli Ben Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, Madars Virza

Voortbouwend op eerder werk, waaronder: Zerocoin (en met Pinnochio-munt als gelijktijdig werk), gebruikt dit artikel GGPR-afgeleide SNARK's om een ​​privé-cryptocurrency te ontwerpen. Geleid tot ZCash.

Geppetto: veelzijdige verifieerbare berekening (2014)
door Craig Costello, Cédric Fournet, Jon Howell, Markulf Kohlweiss, Benjamin Kreuter, Michael Naehrig, Bryan Parno en Samee Zahur

Geppetto dateert waarschijnlijk van vóór de explosie van interesse in de uitvoering van particuliere smart-contracten, die ongeveer een jaar na de oprichting van Ethereum is geschreven. Daarom wordt het niet gepresenteerd in de context van private smart-contractuitvoering. Het gebruikt echter begrensde diepte-recursie van SNARK's om een ​​niet-vertrouwde prover in staat te stellen een privé (toegezegd/ondertekend) computerprogramma op privégegevens uit te voeren, zonder informatie te onthullen over het programma dat wordt uitgevoerd of de gegevens waarop het wordt uitgevoerd. Dienovereenkomstig is het een voorloper van werk aan particuliere smart-contractplatforms, zoals: Zex [hieronder beschreven].

Verifieerbare ASIC's (2015)
door Riad Wahby, Max Howald, Siddharth Garg, abhi Shelat, Michael Walfish

Dit artikel gaat in op het probleem van het veilig en vruchtbaar gebruik van een ASIC die is vervaardigd in een niet-vertrouwde gieterij (in 2015 waren er slechts vijf landen met hoogwaardige gieterijen). De aanpak is om de snelle maar niet-vertrouwde ASIC de juistheid van de uitvoer te laten bewijzen aan een verificateur die op een langzamere maar vertrouwde ASIC draait. De oplossing is interessant zolang de totale uitvoeringstijd van het systeem (dwz de som van de test- en verifier-runtimes plus eventuele datatransmissiekosten) minder is dan de naïeve basislijn: de tijd die nodig is om de berekening volledig uit te voeren op de langzamere -maar vertrouwde ASIC. Door gebruik te maken van een variant van de GKR/CMT/Allspice interactieve bewijzen, verslaat het artikel inderdaad de naïeve basislijn voor een aantal fundamentele problemen, waaronder getaltheoretische transformaties, patroonovereenkomst en elliptische krommebewerkingen. Dit werk suggereert dat sommige bewijssystemen meer geschikt zijn voor hardware-implementatie dan andere. Het optimaliseren van bewijssystemen voor hardware-implementatie wordt nu ontvangen aanzienlijk aandacht, maar er moet nog veel worden onderzocht.

te verifiëren Vertragingsfuncties (2018)
door Dan Boneh, Joseph Bonneau, Benedikt Bünz en Ben Fisch

Introductie van de notatie van verifieerbare vertragingsfuncties (VDF's), een cryptografische primitief die veel wordt gebruikt in blockchain-toepassingen, bijvoorbeeld bij het verminderen van mogelijke manipulatie van proof-of-stake consensusprotocollen. SNARK's (vooral voor Incrementeel Verifieerbare Computation) bieden een route naar ultramoderne VDF's.

Zexe: gedecentraliseerde privécomputing inschakelen (2018)
door Sean Bowe, Alessandro Chiesa, Matthew Green, Ian Miers, Pratyush Mishra en Howard Wu

Zexe is een ontwerp voor een particulier smart-contractplatform. Men kan Zexe zien als een uitbreiding van Zerocash (hierboven beschreven). Met Zerocash kan een enkele applicatie on-chain worden uitgevoerd (waardoor gebruikers tokens kunnen overdragen) terwijl de privacy van gebruikersgegevens wordt beschermd, bijvoorbeeld naar wie ze tokens verzenden, tokens ontvangen van, het aantal overgedragen tokens, enz. Zexe maakt veel verschillende applicaties (slimme contracten) om op dezelfde blockchain te draaien en met elkaar te communiceren. Transacties worden off-chain uitgevoerd en bewijzen van correcte uitvoering worden on-chain geplaatst. Niet alleen de gegevensprivacy wordt beschermd, maar ook de functieprivacy. Dit betekent dat het bewijs dat bij elke transactie hoort, niet eens onthult op welke applicatie(s) de transactie betrekking heeft. Een meer algemene technische bijdrage van Zexe is dat het BLS12-377 introduceerde, een elliptische curvegroep die nuttig is voor een efficiënte diepte-1-samenstelling van op paren gebaseerde SNARK's.

Gerepliceerde statusmachines zonder gerepliceerde uitvoering (2020)
door Jonathan Lee, Kirill Nikitin en Srinath Setty

Dit is een van de weinige academische papers over rollups voor blockchain-schaalbaarheid. Het gebruikt de term rollups niet, omdat het dateert van vóór of gelijktijdig is met het concept dat buiten de academische literatuur wordt geïntroduceerd.

Front-ends (efficiënte transformaties van computerprogramma's naar intermediaire representaties zoals circuit-satisfiablity, R1CS en meer)

Snelle reducties van RAM's naar delegeerbare beknopte tevredenheidsproblemen (2012)
door Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin en Eran Tromer

Vanuit een modern perspectief is dit een vroeg werk over praktische computer-programma-naar-circuit-SAT-transformaties voor een virtuele machine (VM) abstractie. Voortbouwend op werken uit de late jaren 1970 tot 1990 (bijv. werk van Robson) dit artikel beschrijft een deterministische reductie van het uitvoeren van een VM voor T-stappen naar de verzadigbaarheid van een circuit met de grootte O (T * polylog (T)).

Latere artikelen, bijv. SNARK's voor C en BCTV, bleef front-ends ontwikkelen via een VM-abstractie, en moderne instantiaties omvatten projecten zoals: Cairo, RISC nul en Polygoon Miden.

Een op bewijs gebaseerde geverifieerde berekening een paar stappen dichter bij de praktijk brengen (2012)
door Srinath Setty, Victor Vu, Nikhil Panpalia, Benjamin Braun, Muqeet Ali, Andrew J. Blumberg en Michael Walfish

Dit artikel, dat Ginger wordt genoemd, is een andere vroege bijdrage aan praktische front-end-technieken. Ginger introduceerde gadgets voor algemene programmeerprimitieven zoals conditionals en logische uitdrukkingen, vergelijkingen en bitsgewijze rekenkunde via bitsplitsing, primitieve drijvende-kommaberekeningen, enz. Het gebruikte deze gadgets om de eerste geïmplementeerde front-end te bieden van een taal op hoog niveau naar lage graad rekenkundige beperkingen (vergelijkbaar met wat nu bekend staat als R1CS), een intermediaire representatie (IR) waarop een SNARK-back-end kan worden toegepast.

Terwijl het "Fast Reductions" -papier en zijn nakomelingen een "CPU-emulator" -benadering gebruiken bij het produceren van IR's (dwz de IR dwingt af dat de prover een bepaald programma correct heeft uitgevoerd door de overgangsfunctie van de CPU toe te passen voor een bepaald aantal stappen) , Ginger en zijn nakomelingen nemen een meer ASIC-achtige benadering aan en produceren IR's die zijn afgestemd op het computerprogramma dat de bewijzer beweert correct uit te voeren.

Bijvoorbeeld Buffet laat zien dat het mogelijk is om complexe besturingsstroom in het ASIC-model aan te pakken, door een dergelijke besturingsstroom in een eindige-toestandsmachine te veranderen die is afgestemd op het programma dat wordt uitgevoerd, en dat deze aanpak aanzienlijk efficiënter kan zijn dan het bouwen van een CPU-emulator voor algemeen gebruik. xJsnark geeft een efficiënte constructie voor multi-precisie rekenen, optimalisaties voor RAM's en ROM's, en stelt een Java-achtige taal op hoog niveau bloot aan een programmeur, die vandaag de dag nog steeds populair is. CircC merkt op dat het compileren van computerprogramma's naar R1CS nauw verwant is aan bekende technieken uit programma-analyse en bouwt een compiler-constructietoolkit met ideeën van beide gemeenschappen ("LLVM voor circuitachtige representaties"). Eerdere werken die bijdragen aan ASIC-achtige front-ends omvatten: Pinocchio en Geppetto.

Het artikel "Fast-Reductions" gebruikte een gecompliceerde en dure constructie genaamd "routeringsnetwerken" voor zogenaamde geheugencontrole (dwz ervoor zorgen dat de niet-vertrouwde prover het willekeurig toegankelijke geheugen van de VM correct handhaaft tijdens de uitvoering van de VM waarvan de juistheid wordt bewezen). Deze keuze is gemaakt omdat vroege werken zoals deze op zoek waren naar een PCP, waarvoor de front-end nodig was zowel niet-interactief en informatietheoretisch veilig. Later werk genaamd Provisiekamer (een voorloper van de Buffet werk hierboven genoemd) gebruikte Merkle-trees in plaats van routeringsnetwerken, waardoor efficiëntie werd bereikt door een algebraïsche (dwz "SNARK-vriendelijke") hashfunctie te compileren, vanwege Ajtai, in beperkingen. Dit resulteerde in "computationeel veilige" front-ends. Tegenwoordig is er een grote onderzoeksliteratuur over SNARK-vriendelijke hashfuncties, met voorbeelden zoals: Poseidon, MiMC, Gewapend beton, ReddenEn nog veel meer.

State-of-the-art technieken om ervoor te zorgen dat de bewijzer RAM correct onderhoudt, vertrouwen op zogenaamde "permutatie-invariante vingerafdrukken"-methoden die minstens teruggaan tot Lipton (1989) en gebruikt voor geheugencontrole door Blum et al. (1991). Deze technieken impliceren inherent interactie tussen een bewijzer en een verificateur, maar kunnen niet-interactief worden gemaakt met de Fiat-Shamir-transformatie. Voor zover we weten, werden ze geïntroduceerd in de literatuur over praktische SNARK front-ends door een systeem genaamd vRAM.

Permutatie-invariante vingerafdruktechnieken worden nu gebruikt in veel front-ends en SNARK's voor abstracties van virtuele machines, waaronder bijvoorbeeld Cairo. Nauw verwante ideeën kwamen opnieuw naar voren in verwante contexten in de twee onderstaande werken, die tegenwoordig veel worden gebruikt in de praktijk.

Bijna lineaire nulkennisbewijzen voor correcte uitvoering van het programma (2018)
door Jonathan Bootle, Andrea Cerulli, Jens Groth, Sune Jakobsen en Mary Maller

Plookup: een vereenvoudigd polynoomprotocol voor opzoektabellen (2020)
door Ariel Gabizon en Zachary Williamson

Vroege werken aan front-ends vertegenwoordigden "niet-rekenkundige" bewerkingen (zoals bereikcontroles, bitsgewijze bewerkingen en vergelijkingen van gehele getallen) binnen circuits en gerelateerde IR's door veldelementen in bits te breken, de bewerkingen op deze bits uit te voeren en vervolgens "verpakken" het resultaat terug in een enkel veldelement. In termen van de grootte van de resulterende schakeling resulteert dit in een logaritmische overhead per bewerking.

De bovenstaande twee werken (BCGJM en Plookup) geven invloedrijke technieken (gebaseerd op zogenaamde "lookup-tabellen") om deze bewerkingen in circuits efficiënter weer te geven, in geamortiseerde zin. Grofweg, voor een parameter B die door de front-end ontwerper is gekozen, verminderen deze het aantal poorten dat nodig is om elke niet-rekenkundige bewerking in de schakeling weer te geven met een factor logaritmisch in B, ten koste van de bewijzer die zich cryptografisch verplicht tot een extra "advies" vector van lengte ongeveer B.