Null kunnskap Canon

Redaktørens notat: a16z crypto har hatt en lang serie med "våpen", fra vår DAO Canon i fjor til vår NFT Canon tidligere (og før det vår original Krypto Canon) — sørg for å registrere deg for vår web3 ukentlige nyhetsbrev for flere oppdateringer samt andre kuraterte ressurser.

Så bNedenfor har vi samlet et sett med ressurser for de som ønsker å forstå, gå dypere og bygge med alle ting null kunnskap: kraftige, grunnleggende teknologier som holder nøklene til blokkjedeskalerbarhet, og representerer fremtiden for personvernbevarende applikasjoner og utallige andre innovasjoner som kommer. Hvis du har forslag til stykker av høy kvalitet å legge til, gi oss beskjed @a16zcrypto.

Nullkunnskapssikre systemer har eksistert i flere tiår: Introduksjonen deres av Shafi Goldwasser, Silvio Micali og Charles Rackoff i 1985 hadde en transformativ effekt på kryptografifeltet, og ble anerkjent av ACM Turing Award tildelt Goldwasser og Micali i 2012. Siden dette arbeidet – inkludert overgangen fra teori til praksis og applikasjoner i krypto/web3 i dag – har vært flere tiår under utvikling, deler vi også for første gang i vår kanonserie en del to (foreløpig inkludert her nedenfor): en leseliste kommentert av Justin Thaler, etter del én nedenfor.

Takk også til Michael Blau, Sam Ragsdale og Tim Roughgarden.

Grunnlag, bakgrunn, evolusjoner

Noen av disse papirene handler også mer om kryptografi generelt (ikke all null kunnskap per se), inkludert skisserer problemer eller viktige fremskritt som er adressert av null kunnskapsbevis i dag: hvordan sikre personvern og autentisering i åpne nettverk.

Nye retninger innen kryptografi (1976)
av Whitfield Diffie og Martin Hellman
https://ee.stanford.edu/~hellman/publications/24.pdf

En metode for å skaffe digitale signaturer og offentlige nøkkelkryptosystemer
av 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

Protokoller for offentlige nøkkelkryptosystemer (1980)
av Ralph Merkle
http://www.merkle.com/papers/Protocols.pdf

Sikker kommunikasjon over usikre kanaler (1978)
av Ralph Merkle
https://www.merkle.com/1974/PuzzlesAsPublished.pdf

Bruk av elliptiske kurver i kryptografi (1988)
av Victor Miller
https://link.springer.com/content/pdf/10.1007%2F3-540-39799-X_31.pdf

Kunnskapskompleksiteten til interaktive bevissystemer (1985)
av Shafi Goldwasser, Silvio Micali, Charles Rackof
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.419.8132&rep=rep1&type=pdf

Beregningsmessige lydprøver (2000)
av Silvio Micali
https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/Computationally_Sound_Proofs.pdf

Fra uttrekkbar kollisjonsmotstand til konsise ikke-interaktive kunnskapsargumenter [SNARKs], og tilbake igjen (2011)
av Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer
https://eprint.iacr.org/2011/443.pdf

Effektivt nullkunnskapsargument for riktigheten av en shuffle (2012)
av Stephanie Bayer og Jens Groth
http://www0.cs.ucl.ac.uk/staff/J.Groth/MinimalShuffle.pdf

Kortfattet ikke-interaktiv nullkunnskap for en von Neumann Architecture (2013)
av Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer og Madars Virza
https://eprint.iacr.org/2013/879.pdf

Skalerbar, transparent og post-kvantesikker beregningsintegritet (2018)
av Eli Ben-Sasson, Iddo Bentov, Yinon Horesh og Michael Riabzev
https://eprint.iacr.org/2018/046.pdf

Offentlig mynt null-kunnskapsargumenter med (nesten) minimale tid- og romkostnader (2020)
av Alexander Block, Justin Holmgren, Alon Rosen, Ron Rothblum og Pratik Soni
https://www.iacr.org/cryptodb/data/paper.php?pubkey=30645

Oversikter og introer

Bevis, argumenter og nullkunnskap — En oversikt over verifiserbar databehandling og interaktive bevis og argumenter, kryptografiske protokoller som gjør det mulig for en kontrollør å gi en garanti til en verifikator om at beviseren utførte en forespurt beregning riktig, inkludert nullkunnskap (der bevis ikke avslører annen informasjon enn deres egen gyldighet) . Zk-argumenter har et mylder av applikasjoner innen kryptografi og har gjort hoppet fra teori til praksis det siste tiåret.
av Justin Thaler
https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf

En utvikling av modeller for null-kunnskapsbevis — En gjennomgang av nullkunnskapsbevis, der Meiklejohn (University College London, Google) ser på applikasjonene som driver utviklingen deres, de forskjellige modellene som har dukket opp for å fange opp disse nye interaksjonene, konstruksjonene vi kan oppnå, og arbeidet igjen å gjøre.
av Sarah Meiklejohn
https://www.youtube.com/watch?v=HO97kVMI3SE

ZK tavleøkter — introduksjonsmoduler
med Dan Boneh et al
https://zkhack.dev/whiteboard/

Sikkerhet og personvern for krypto med zkps — banebrytende beviset om null kunnskap i praksis; hva zkps er og hvordan de fungerer ... inkludert live scene "demo"
av Zooko Wilcox
https://a16z.com/2019/08/29/security-and-privacy-for-crypto-with-zero-knowledge-proofs/

Toppteknologiske emner, forklart – inkludert definisjoner og implikasjoner av nullkunnskap generelt
av 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

Hvordan det kommende personvernlaget vil fikse et ødelagt nett
av Howard Wu
https://future.com/a-privacy-layer-for-the-web-can-change-everything/

Introduksjon til zkSNARKs
med Howard Wu, Anna Rose
https://zeroknowledge.fm/38-2/

Hvorfor og hvordan zk-SNARK fungerer: en definitiv forklaring
av Maksym Petkus
https://arxiv.org/pdf/1906.07221.pdf

En introduksjon til nullkunnskapsbevis
av Fredrik Harrysson og Anna Rose
https://www.zeroknowledge.fm/21 [+ oppsummering andre steder her.]

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

Desentralisert hastighet — på fremskritt innen null kunnskapsbevis, desentralisert maskinvare
av Elena Burger
https://a16z.com/2022/04/15/zero-knowledge-proofs-hardware-decentralization-innovation/

Nyskapende zk-forskning — med zk-forsker ved Ethereum Foundation
med Mary Maller, Anna Rose, Kobi Gurkan
https://zeroknowledge.fm/232-2/

Utforsker zk-forskning — med forskningsdirektør ved DFINITY; også bak fremskritt som Groth16
med Jens Groth, Anna Rose, Kobi Gurkan
https://zeroknowledge.fm/237-2/

SNARK forskning & pedagogikk — med en av medgründerne av ZCash og Starkware
med Alessandro Chiesa, Anna Rose
https://zeroknowledge.fm/episode-200-snark-research-pedagogy-with-alessandro-chiesa/

Dypdykk, byggmesterguider

Grunnlaget for sannsynlige bevis — et kurs med 5 enheter fra interaktive prøvetrykk og mer
av Alessandro Chiesa
https://www.youtube.com/playlist?list=PLGkwtcB-DfpzST-medFVvrKhinZisfluC

STARKs - del I, II, III
av 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

Anatomien til en STARK — en seksdelt opplæring som forklarer mekanikken til et STARK-sikkert system
av Alan Szepieniec
https://aszepieniec.github.io/stark-anatomy/

SNARK design, del 1 — undersøkelse, bruk i sammendrag, mer
av Justin Thaler
https://www.youtube.com/watch?v=tg6lKPdR_e4

SNARK design, del 2 — rollups, ytelse, sikkerhet
av Justin Thaler
https://www.youtube.com/watch?v=cMAI7g3UcoI

Måling av SNARK-ytelse — frontends, backends, mer
av Justin Thaler
https://a16zcrypto.com/measuring-snark-performance-frontends-backends-and-the-future/

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

PLONK null-kunnskapssikkert system — serie med 12 korte videoer om hvordan PLONK fungerer
av David Wong
https://www.youtube.com/playlist?list=PLBJMt6zV1c7Gh9Utg-Vng2V6EYVidTFCC

Fra AIR-er til RAP-er — hvordan aritmetisering i PLONK-stil fungerer
av Ariel Gabizon
https://hackmd.io/@aztec-network/plonk-arithmetiization-air

Multisett sjekker i PLONK og Plookup
av Ariel Gabizon
https://hackmd.io/@arielg/ByFgSDA7D

Halo2 design - fra ECC
https://zcash.github.io/halo2/design.html

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

Applikasjoner og veiledninger: bevis på konsepter, demoer, verktøy, mer

Påført zk — læringsressurser
av 0xPARC
https://learn.0xparc.org/materials/intro

Et online utviklingsmiljø for zkSNARKs — zkREPL, et nytt sett med verktøy for samhandling med Circom-verktøystakken i nettleseren
av Kevin Kwok
https://zkrepl.dev (+ forklaringstråd her.)

Kvadratiske aritmetiske programmer fra null til helt
av Vitalik Buterin
https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

På zkEVM-er
med Alex Gluchowski og Anna Rose
https://zeroknowledge.fm/175-2/

Ulike typer zkEVM-er
av Vitalik Buterin
https://vitalik.ca/general/2022/08/04/zkevm.html

ZK maskinlæring — opplæring og demo for å sette et nevralt nett inn i en SNARK
av Horace Pan, Francis Ho og Henri Palacci
https://0xparc.org/blog/zk-mnist

På ZK-språk
med Alex Ozdemir og Anna Rose
https://zeroknowledge.fm/172-2/

Dark Forest – bruker zk-kryptografi på spill — et fullstendig desentralisert og vedvarende RTS-spill (sanntidsstrategi).
https://blog.zkga.me/announcing-darkforest

ZKP-er for ingeniører - en titt på Dark Forest ZKPs
https://blog.zkga.me/df-init-circuit

Et dykk inn i null kunnskap
med Elena Nadolinkski, Anna Rose, James Prestwich
https://zeroknowledge.fm/182-2/

zkDocs: Null-kunnskapsinformasjonsdeling
av Sam Ragsdale og Dan Boneh
https://a16zcrypto.com/zkdocs-zero-knowledge-information-sharing/

Personvernbeskyttende krypto-airdrops med null kunnskapsbevis
av Sam Ragsdale
https://a16z.com/2022/03/27/crypto-airdrop-privacy-tool-zero-knowledge-proofs/

On-chain pålitelige oppsettseremonier -
av Valeria Nikolaenko og Sam Ragsdale
https://a16zcrypto.com/on-chain-trusted-setup-ceremony/

Kryptoforskrifter, ulovlig finans, personvern og mer – inkluderer en del om nullkunnskap i regulatoriske/compliance-sammenhenger; forskjellen mellom "personvernbevarende" vs tilslørende teknologier
med Michele Korver, Jai Ramaswamy, Sonal Chokshi
https://web3-with-a16z.simplecast.com/episodes/crypto-regulations-sanctions-compliance-aml-ofac-news-explained

Andre ressurser

zkMesh nyhetsbrev – et månedlig nyhetsbrev som deler det siste innen desentralisert personvernbevarende teknologi, utvikling av personvernprotokoller og null kunnskapssystemer
https://zkmesh.substack.com/

Zero Knowledge-podcast — på den nyeste zk-forskningen og zk-applikasjonene og eksperter som bygger kryptografi-aktivert personvernteknologi
med Anna Rose
https://zeroknowledge.fm/

…en kommentert leseliste, etter emne og kronologi, av Justin Thaler:

SNARK-er fra lineære PCP-er (aka SNARK-er med kretsspesifikt oppsett)

Effektive argumenter uten korte PCP-er (2007)
av Yuval Ishai, Eyal Kushilevitz og Rafail Ostrovsky

Før ca 2007 ble SNARK-er først og fremst designet via Kilian-micali paradigme, med å ta et "kort" sannsynlighetskontrollerbart bevis (PCP) og "kryptografisk kompilere" det til et kortfattet argument via Merkle-hashing og Fiat-Shamir-transformasjonen. Dessverre er korte PCP-er kompliserte og upraktiske, selv i dag. Denne artikkelen (IKO) viste hvordan man kan bruke homomorf kryptering for å få kortfattede (ikke-transparente) interaktive argumenter fra "lange, men strukturerte" PCP-er. Disse kan være mye enklere enn korte PCP-er, og de resulterende SNARK-ene har mye kortere bevis og raskere verifisering. Disse argumentene ble først anerkjent som å ha potensialet for praktisk effektivitet, og raffinert og implementert i Pepper. Dessverre har IKOs argumenter en kvadratisk tidsbevis og en strukturert referansestreng i kvadratisk størrelse, slik at de ikke skaleres til store beregninger.

Quadratic Span-programmer og kortfattede NIZK-er uten PCP-er (2012)
av Rosario Gennaro, Craig Gentry, Bryan Parno og Mariana Raykova

Dette banebrytende papiret (GGPR) reduserte prøvekostnadene ved IKOs tilnærming fra kvadratisk i størrelsen på kretsen til kvasilineær. Bygger på tidligere arbeid av Groth og Lipmaa, ga det også SNARKs via paringsbasert kryptografi, i stedet for interaktive argumenter som i IKO. Den beskrev sine SNARK-er i sammenheng med det som nå omtales som rang-1 constraint satisfaction (R1CS) problemer, en generalisering av aritmetisk krets-tilfredshet.

Denne artikkelen fungerte også som det teoretiske grunnlaget for de første SNARK-ene som så kommersiell distribusjon (f.eks. i ZCash) og førte direkte til SNARK-er som fortsatt er populære i dag (f.eks. Groth16). De første implementeringene av GGPRs argumenter kom inn zaatar og Pinocchio, og senere varianter inkluderer SNARKs for C og BCTV. BCIOP ga et generelt rammeverk som belyser disse lineære-PCP-er-til-SNARK-transformasjonene (se også vedlegg A til zaatar) og beskriver ulike instansiasjoner derav.

På størrelse med paringsbaserte ikke-interaktive argumenter (2016)
av Jens Groth

Denne artikkelen, i daglig tale referert til som Groth16, presenterte en foredling av GGPRs SNARK-er som oppnår toppmoderne betongverifiseringskostnader selv i dag (bevis er 3 gruppeelementer, og verifisering domineres av tre sammenkoblingsoperasjoner, i det minste forutsatt at offentligheten input er kort). Sikkerhet er bevist i den generiske gruppemodellen.

SNARK-er med universelt pålitelig oppsett

PlonK: Permutasjoner over Lagrange-baser for økumeniske ikke-interaktive kunnskapsargumenter (2019)
av Ariel Gabizon, Zachary Williamson og Oana Ciobotaru

Marlin: Forbehandling av zkSNARK-er med universell og oppdaterbar SRS (2019)
av Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely og Nicholas Ward

Både PlonK og Marlin erstatter det kretsspesifikke klarerte oppsettet i Groth16 med et universelt oppsett. Dette går på bekostning av 4x-6x større prøvetrykk. Man kan tenke på PlonK og Marlin som å ta det kretsspesifikke arbeidet under det pålitelige oppsettet i Groth16 og forgjengere og flytte det inn i en forhåndsbehandlingsfase som skjer etter det pålitelige oppsettet, så vel som under SNARK proof-generering.

Evnen til å behandle vilkårlige kretser og R1CS-systemer på denne måten kalles noen ganger holografi eller beregningsforpliktelser, og ble også beskrevet i Spartan (diskutert senere i denne samlingen). Fordi mer arbeid skjer under bevisgenerering, er PlonK og Marlins bevisere tregere enn Groth16 for en gitt krets eller R1CS-forekomst. Imidlertid, i motsetning til Groth16, kan PlonK og Marlin fås til å fungere med mer generelle mellomrepresentasjoner enn R1CS.

Polynomiske forpliktelsesordninger, en nøkkel kryptografisk primitiv i SNARK-er

Forpliktelser i konstant størrelse til polynomer og deres applikasjoner (2010)
av Aniket Kate, Gregory Zaverucha og Ian Goldberg

Denne artikkelen introduserte begrepet polynomiske forpliktelsesordninger. Det ga et opplegg for univariate polynomer (ofte kalt KZG-forpliktelser) med forpliktelser i konstant størrelse og evalueringsbevis. Opplegget bruker et klarert oppsett (dvs. strukturert referansestreng) og sammenkoblingsbasert kryptografi. Det er fortsatt ekstremt populært i praksis i dag, og brukes i SNARK-er inkludert PlonK og Marlin diskutert ovenfor (og Groth16 bruker ekstremt lignende kryptografiske teknikker).

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

Gir et interaktivt orakelbevis (IOP) for Reed-Solomon-testing - det vil si beviser at en forpliktet streng er nær evalueringstabellen til et univariat polynom. Kombinert med Merkle-hashing og Fiat-Shamir-transformasjonen, gir dette et transparent polynomisk forpliktelsessystem med evalueringsbevis i polylogaritmisk størrelse (se VP19 for detaljer). I dag er dette fortsatt den korteste blant plausibelt post-kvantepolynomiske forpliktelsesordninger.

Ligero: Lette sublineære argumenter uten et pålitelig oppsett (2017)
av Scott Ames, Carmit Hazay, Yuval Ishai og Muthuramakrishnan Venkitasubramaniam

I likhet med FRI gir dette arbeidet en IOP for Reed-Solomon-testing, men med kvadratrotsikker lengde i stedet for polylogaritmisk. teoretisk virker viste at ved å bytte ut Reed-Solomon-koden for en annen feilkorrigerende kode med raskere koding, kan man få en lineær-tidsbeviser som dessuten fungerer naturlig over ethvert felt. Denne tilnærmingen har blitt foredlet og implementert i Bryte sammen og Orion, som gir toppmoderne prøveytelse.

Bulletproofs: Korte bevis for konfidensielle transaksjoner og mer (2017)
av Benedikt Bunz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille og Greg Maxwell

Foredling av tidligere arbeid ved BCCGP, Bulletproofs gir et gjennomsiktig polynomisk forpliktelsessystem (faktisk en generalisering kalt et indre produktargument) basert på hardheten til å beregne diskrete logaritmer med logaritmisk bevisstørrelse men lineær verifikatørtid. Ordningen er fortsatt populær i dag på grunn av dens åpenhet og korte prøvetrykk (f.eks. brukes den i ZCash Orchard og Monero).

Dory: Effektive, transparente argumenter for generaliserte indre produkter og polynomiske forpliktelser (2020)
av Jonathan Lee

Dory reduserer verifikatorens tid i Bulletproofs fra lineær til logaritmisk, samtidig som transparens og bevis i logaritmisk størrelse (om enn konkret større enn Bulletproofs) og transparens bevares. Bruker sammenkoblinger og er basert på SXDH-antakelsen.

Interactive Proofs, multi-prover interaktive Proofs, og tilhørende SNARKs

Delegering av beregninger: interaktive bevis for mugglere (2008)
av Shafi Goldwasser, Yael Tauman Kalai og Guy Rothblum

Før denne artikkelen krevde interaktive prøvetrykk for generelle formål en superpolynomisk tid bevis. Denne artikkelen gir en interaktiv bevisprotokoll, ofte kalt GKR-protokollen, med en polynomisk tidsbeviser og kvasilineær tidsverifikator, for ethvert problem som har en effektiv parallellalgoritme (tilsvarende gjelder det interaktive beviset for enhver aritmetisk krets med liten dybde).

Praktisk verifisert beregning med streaming interaktive bevis (2011)
av Graham Cormode, Michael Mitzenmacher, Justin Thaler

Denne artikkelen (noen ganger kalt CMT) reduserte prøvetiden i GKR-protokollen fra kvartisk i størrelsen på kretsen til kvasilineær. Produserte den første implementeringen av et interaktivt bevis for generell bruk. En rekke påfølgende verk (allehånde, Thaler13, Sjiraffog Libra) reduserte kjøretiden til proveren ytterligere, fra kvasilineær til lineær i størrelsen på kretsen.

vSQL: Verifisering av vilkårlige SQL-spørringer over dynamiske outsourcede databaser (2017)
av Yupeng Zhang, Daniel Genkin, Jonathan Katz, Dimitrios Papadopoulos og Charalampos Papamanthou

Selv om tittelen refererer til et spesifikt bruksområde (databaser), er bidragene i denne artikkelen mer generelle. Spesifikt observerte den at man kan få kortfattede argumenter for kretstilfredshet ved å kombinere interaktive bevis med polynomiske forpliktelsesskjemaer (for multilineære polynomer).

Senere virker gjengitt argumentene null-kunnskap og introduserte ulike forpliktelsesordninger for multilineære polynomer.

Spartansk: Effektive og generelle zkSNARK-er uten pålitelig oppsett (2019)
av Srinath Setty

Skaffer SNARK-er for krets-tilfredshet og R1CS ved å kombinere multi-prover interaktive bevis (MIP-er) med polynomiske forpliktelsesordninger, og bygger på tidligere arbeid med konkret effektive MIP-er kalt Kløver. Effekten er å få SNARK-er med kortere bevis enn de som er avledet fra interaktive bevis som GKR-protokollen diskutert ovenfor. Analogt med PlonK og Marlin, viser Spartan også hvordan man behandler vilkårlige kretser og R1CS-systemer via forhåndsbehandling og SNARK-bevisgenerering.

Spartan brukte en polynomisk forpliktelsesordning fra hyrax. Etterfølgende arbeider kalt Bryte sammen og Orion kombiner Spartans MIP med andre polynomiske forpliktelsesordninger for å gi de første implementerte SNARKene med en lineær-tidsbevis.

Korte PCP-er og IOP-er

Korte PCP-er med Polylog Query-kompleksitet (2005)
av Eli Ben-Sasson og Madhu Sudan

 Dette teoretiske arbeidet ga det første probabilistisk kontrollerbare beviset (PCP) med bevislengde kvasilineær i størrelsen på beregningen som skal verifiseres og polylogaritmiske spørringskostnader (selv om lineær verifikatortid). Etter Kilian-Micali-transformasjonen av PCP-er til SNARK-er, var dette et skritt mot SNARK-er med kvasi-lineær tidsbeviser og polylogaritmisk tidsbekreftelse.

Senere teoretisk arbeid reduserte verifikatorens tid til polylogaritmisk. Påfølgende praktisk fokusert arbeid foredlet denne tilnærmingen, men korte PCP-er er fortsatt upraktiske i dag. For å få praktiske SNARK-er, seinere virker slått til en interaktiv generalisering av PCP kalt Interaktive Oracle Proofs (IOPs). Denne innsatsen førte til og bygger videre på Fredag, et populært polynomforpliktelsesskjema som er omtalt i polynomforpliktelsesdelen av denne samlingen.

Andre verk i denne kategorien inkluderer ZKBoo og dens etterkommere. Disse oppnår ikke kortfattede bevis, men de har gode konstante faktorer og er derfor attraktive for å bevise små utsagn. De har ført til familier av postkvantesignaturer som f.eks Piknik som har vært optimalisert in flere virker. ZKBoo presenteres som følger et distinkt designparadigme kalt MPC-i-hodet, men det gir en IOP.

Rekursive SNARKs

Inkrementelt verifiserbar beregning eller bevis på kunnskap innebærer tids-/romeffektivitet (2008)
av Paul Valiant

Dette arbeidet introduserte den grunnleggende forestillingen om inkrementelt verifiserbar beregning (IVC), der er prover kjører en beregning og til enhver tid opprettholder et bevis på at beregningen så langt har vært korrekt. Den konstruerte IVC via rekursiv sammensetning av SNARK-er. Her, den kunnskapsmessig forsvarlighet egenskapen til SNARKs er avgjørende for å etablere soliditeten til rekursivt komponerte ikke-interaktive argumenter. Denne artikkelen ga også en ekstremt effektiv kunnskapsekstraktor for PCP-avledede SNARK-er (i henhold til Kilian-Micali-paradigmet).

Skalerbar null kunnskap via sykluser av elliptiske kurver (2014)
av Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer og Madars Virza

Følgende teoretisk arbeid, brukte denne artikkelen rekursiv applikasjon av en variant av GGPRs SNARK, for å gi den første implementeringen av IVC for en enkel virtuell maskin (TinyRAM, fra SNARKs for C papir).

Introduserte også forestillingen om sykluser av elliptiske kurver, som er nyttige for rekursivt komponere SNARK-er som bruker elliptisk kurvekryptografi.

Rekursiv beviskomposisjon uten et klarert oppsett (2019)
av Sean Bowe, Jack Grigg og Daira Hopwood

Dette verket (kalt Halo) studerer hvordan man rekursivt komponerer transparente SNARK-er. Dette er mer utfordrende enn å komponere ikke-transparente fordi verifiseringsprosedyren i transparente SNARK-er kan være mye dyrere.

Dette utløste deretter en linje of arbeid som har kulminert i systemer som f.eks Nova oppnå state-of-the-art IVC-ytelse, overlegen til og med den som oppnås ved sammensetning av ikke-transparente SNARK-er som Groth16.

applikasjoner

Zerocash: Desentraliserte anonyme betalinger fra Bitcoin (2014)
av Eli Ben Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, Madars Virza

Bygger på tidligere arbeid, inkludert null mynt (og med Pinnochio mynt som samtidig arbeid), bruker denne artikkelen GGPR-avledede SNARK-er for å designe en privat kryptovaluta. Ledet til ZCash.

Geppetto: Allsidig verifiserbar beregning (2014)
av Craig Costello, Cédric Fournet, Jon Howell, Markulf Kohlweiss, Benjamin Kreuter, Michael Naehrig, Bryan Parno og Samee Zahur

Geppetto er uten tvil før eksplosjonen av interesse for privat utførelse av smartkontrakter, etter å ha blitt skrevet omtrent ett år etter etableringen av Ethereum. Derfor presenteres den ikke i sammenheng med privat utførelse av smartkontrakter. Imidlertid bruker den begrenset dybderekursjon av SNARK-er for å la en upålitelig beviser kjøre ethvert privat (forpliktet/signert) dataprogram på private data, uten å avsløre informasjon om programmet som kjøres eller dataene det kjøres på. Følgelig er det en forgjenger for arbeid på private smartkontraktplattformer, som f.eks Zexe [beskrevet nedenfor].

Verifiserbare ASIC-er (2015)
av Riad Wahby, Max Howald, Siddharth Garg, abhi shelat, Michael Walfish

Denne artikkelen tar for seg problemet med hvordan man trygt og fruktbart kan bruke en ASIC produsert i et upålitelig støperi (i 2015 var det bare fem nasjoner med toppstøperier). Tilnærmingen er å få den raske, men upålitelige ASIC-en til å bevise riktigheten av utdataene til en verifikator som kjører på en langsommere, men pålitelig ASIC. Løsningen er interessant så lenge den totale utførelsestiden for systemet (dvs. summen av kjøretidene for beviseren og verifikatoren pluss eventuelle dataoverføringskostnader) er mindre enn den naive grunnlinjen: tiden som kreves for å kjøre beregningen i sin helhet på den tregere -men pålitelig ASIC. Ved å bruke en variant av GKR/CMT/Allspice interaktive prøvetrykk, slår papiret faktisk den naive grunnlinjen for en rekke grunnleggende problemer, inkludert tallteoretiske transformasjoner, mønstertilpasning og elliptiske kurveoperasjoner. Dette arbeidet antyder at noen bevissystemer er mer egnet for maskinvareimplementering enn andre. Optimalisering av bevissystemer for maskinvareimplementering mottas nå betydelig oppmerksomhet, men mye gjenstår å utforske.

verifiserbar Forsinkelsesfunksjoner (2018)
av Dan Boneh, Joseph Bonneau, Benedikt Bünz og Ben Fisch

Introduserte notasjonen for verifiserbare forsinkelsesfunksjoner (VDFs), en kryptografisk primitiv som er allment nyttig i blokkjedeapplikasjoner, for eksempel for å redusere mulig manipulasjon av proof-of-stake konsensusprotokoller. SNARK-er (spesielt for inkrementelt verifiserbar beregning) tilbyr en rute til toppmoderne VDF-er.

Zexe: Aktiverer desentralisert privat beregning (2018)
av Sean Bowe, Alessandro Chiesa, Matthew Green, Ian Miers, Pratyush Mishra og Howard Wu

Zexe er et design for en privat smartkontraktsplattform. Man kan se Zexe som en utvidelse av Zerocash (beskrevet ovenfor). Zerocash gjør det mulig å kjøre en enkelt applikasjon på kjeden (som gjør det mulig for brukere å overføre tokens) samtidig som personvernet til brukerdata beskyttes, f.eks. hvem de sender tokens til, mottar tokens fra, mengden tokens som overføres, osv. Zexe lar mange forskjellige applikasjoner (smarte kontrakter) for å kjøre på samme blokkjede og samhandle med hverandre. Transaksjoner utføres utenfor kjeden, og bevis på korrekt utførelse legges ut i kjeden. Ikke bare er personvernet beskyttet, det samme er funksjonsvernet. Dette betyr at beviset knyttet til hver transaksjon ikke en gang avslører hvilke(n) applikasjon(er) transaksjonen gjelder. Et mer generelt ingeniørbidrag fra Zexe er at det introduserte BLS12-377, en elliptisk kurvegruppe som er nyttig for effektiv dybde-1-sammensetning av paringsbaserte SNARK-er.

Replikerte tilstandsmaskiner uten replikert utførelse (2020)
av Jonathan Lee, Kirill Nikitin og Srinath Setty

Dette er en av få akademiske artikler om sammendrag for skalerbarhet av blokkjeder. Den bruker ikke begrepet rollups, fordi det dateres før eller er samtidig med at konseptet introduseres utenfor den akademiske litteraturen.

Frontends (effektive transformasjoner fra dataprogrammer til mellomrepresentasjoner som krets-tilfredshet, R1CS og mer)

Raske reduksjoner fra RAM-er til delegerbare kortfattede begrensningsproblemer (2012)
av Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin og Eran Tromer

Fra et moderne perspektiv er dette et tidlig arbeid med praktiske data-program-til-krets-SAT-transformasjoner for en virtuell maskin (VM) abstraksjon. Bygger på arbeider fra slutten av 1970-tallet til 1990-tallet (f.eks. arbeid av Robson) dette papiret beskriver en deterministisk reduksjon fra å utføre en VM for T-trinn til tilfredsstillelsen til en krets med størrelse O(T*polylog(T)).

Etterfølgende papirer, f.eks. SNARKs for C og BCTV, fortsatte å utvikle front-ends via en VM-abstraksjon, og moderne instansiasjoner inkluderer prosjekter som f.eks. Kairo, RISC nullog Polygon Miden.

Ved å ta bevisbasert verifisert beregning noen få skritt nærmere praktisk (2012)
av Srinath Setty, Victor Vu, Nikhil Panpalia, Benjamin Braun, Muqeet Ali, Andrew J. Blumberg og Michael Walfish

Denne artikkelen, referert til som ingefær, er et annet tidlig bidrag til praktiske front-end-teknikker. Ginger introduserte gadgets for generelle programmeringsprimitiver som betingede og logiske uttrykk, sammenligninger og bitvis aritmetikk via bitdeling, primitiv flytekommaaritmetikk, osv. Den brukte disse gadgetene til å gi den første implementerte grensesnittet fra et høyt nivå språk til lav grad aritmetiske begrensninger (ligner på det som nå er kjent som R1CS), en mellomrepresentasjon (IR) som en SNARK-backend kan brukes på.

Mens "Fast Reductions"-papiret og dets etterkommere bruker en "CPU-emulator"-tilnærming for å produsere IR-er (dvs. IR-en håndhever at beviseren kjørte et bestemt program riktig ved å bruke overgangsfunksjonen til CPU-en for et spesifisert antall trinn) , Ginger og dens etterkommere tar en mer ASIC-lignende tilnærming, og produserer IR-er som er skreddersydd for dataprogrammet som beviseren hevder å utføre korrekt.

For eksempel, Buffet viser at det er mulig å håndtere kompleks kontrollflyt i ASIC-modellen, ved å gjøre slik kontrollflyt til en finite-state maskin skreddersydd for programmet som kjøres, og at denne tilnærmingen kan være betydelig mer effektiv enn å bygge en generell CPU-emulator. xJsnark gir en effektiv konstruksjon for aritmetikk med flere presisjoner, optimaliseringer for RAM-er og ROM-er, og eksponerer et Java-lignende høynivåspråk for en programmerer, som fortsatt er populært i dag. CirC observerer at kompilering av dataprogrammer til R1CS er nært beslektet med velkjente teknikker fra programanalyse og bygger et kompilatorkonstruksjonsverktøysett som inneholder ideer fra begge fellesskap ("LLVM for kretslignende representasjoner"). Tidligere arbeider som gir bidrag til frontends i ASIC-stil inkluderer Pinocchio og Geppetto.

Papiret «Fast-Reductions» brukte en komplisert og kostbar konstruksjon kalt «rutingsnettverk» for s.k. minnesjekking (dvs. å sikre at den ikke-klarerte beviseren opprettholder den virtuelle maskinens tilfeldige tilgangsminne på riktig måte gjennom utførelsen av den virtuelle maskinen hvis korrekthet blir bevist). Dette valget ble tatt fordi tidlige arbeider som dette søkte å skaffe en PCP, som krevde at front-end var både ikke-interaktiv og informasjonsteoretisk sikker. Senere ringte arbeidet Pantry (en forgjenger til Buffet arbeid nevnt ovenfor) brukte Merkle-trær i stedet for rutenettverk, og oppnådde effektivitet ved å kompilere en algebraisk (dvs. "SNARK-vennlig") hash-funksjon, pga. Ajtai, inn i begrensninger. Dette resulterte i "beregningssikre" grensesnitt. I dag finnes det en stor forskningslitteratur om SNARK-vennlige hasjfunksjoner, med eksempler bl.a Poseidon, MiMC, Armert betong, Rescue, Og mer.

State-of-the-art teknikker for å sikre at beviseren vedlikeholder RAM riktig, er avhengig av såkalte "permutasjons-invariant fingeravtrykk"-metoder som dateres tilbake til minst til Lipton (1989) og brukt til minnesjekk av Blum et al. (1991). Disse teknikkene involverer iboende interaksjon mellom en beviser og verifikator, men kan gjøres ikke-interaktive med Fiat-Shamir-transformasjonen. Så vidt vi er kjent med, ble de introdusert til litteraturen om praktiske SNARK-frontends av et system kalt VRAM.

Permutasjons-invariante fingeravtrykksteknikker brukes nå i mange front-ends og SNARK-er for virtuell maskinabstraksjoner, inkludert f.eks. Kairo. Nært beslektede ideer dukket opp igjen i beslektede sammenhenger i de to verkene nedenfor, som brukes mye i praksis i dag.

Nesten lineær-tid null-kunnskap bevis for korrekt programutførelse (2018)
av Jonathan Bootle, Andrea Cerulli, Jens Groth, Sune Jakobsen og Mary Maller

Plookup: En forenklet polynomprotokoll for oppslagstabeller (2020)
av Ariel Gabizon og Zachary Williamson

Tidlige arbeider på front-ends representerte "ikke-aritmetiske" operasjoner (som rekkeviddekontroller, bitvise operasjoner og heltallssammenligninger) inne i kretser og relaterte IR-er ved å bryte feltelementer i biter, utføre operasjonene på disse bitene og deretter "pakke" resultatet tilbake til et enkelt feltelement. Når det gjelder størrelsen på den resulterende kretsen, resulterer dette i en logaritmisk overhead per operasjon.

De to ovennevnte verkene (BCGJM og Plookup) gir innflytelsesrike teknikker (basert på såkalte "oppslagstabeller") for mer effektivt å representere disse operasjonene inne i kretser, i amortisert forstand. Grovt sett, for noen parameter B valgt av frontend-designeren, reduserer disse antallet porter som kreves for å representere hver ikke-aritmetiske operasjon i kretsen med en faktor logaritmisk i B, på bekostning av at beviseren kryptografisk forplikter seg til en ekstra "råd" vektor med lengde omtrent B.