Nul viden Canon

Redaktionel note: a16z crypto har haft en lang række af "kanoner”, fra vores DAO Canon sidste år til vores NFT Canon tidligere (og før det vores originale Krypto Canon) — sørg for at tilmelde dig vores web3 ugentlige nyhedsbrev for flere opdateringer samt andre kuraterede ressourcer.

Så bNedenfor har vi samlet et sæt ressourcer til dem, der søger at forstå, gå dybere og bygge med alle ting nul viden: kraftfulde, grundlæggende teknologier, der har nøglerne til blockchain-skalerbarhed og repræsenterer fremtiden for privatlivsbevarende applikationer og utallige andre innovationer, der kommer. Hvis du har forslag til stykker af høj kvalitet at tilføje, så lad os det vide @a16zcrypto.

Nulvidenssikre systemer har eksisteret i årtier: Deres introduktion af Shafi Goldwasser, Silvio Micali og Charles Rackoff i 1985 havde en transformativ effekt på kryptografiområdet og blev anerkendt af ACM Turing Award tildelt Goldwasser og Micali i 2012. Da dette arbejde - inklusive dets bevægelse fra teori til praksis og applikationer i krypto/web3 i dag - har været årtier undervejs, deler vi også for første gang i vores kanonserie en del to (for nu, inkluderet her nedenfor): en læseliste kommenteret af Justin Thaler, efter del et nedenfor.

Tak: Også tak til Michael Blau, Sam Ragsdale og Tim Roughgarden.

Fundamenter, baggrund, evolutioner

Nogle af disse papirer handler også mere om kryptografi generelt (ikke al viden om nul i sig selv), herunder skitsering af problemer eller nøglefremskridt, der behandles af beviser med nul viden i dag: hvordan man sikrer privatliv og autentificering i åbne netværk.

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

En metode til at opnå digitale signaturer og offentlige nøglekryptosystemer
af 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 til offentlige nøglekryptosystemer (1980)
af Ralph Merkle
http://www.merkle.com/papers/Protocols.pdf

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

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

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

Beregningsmæssigt forsvarlige korrektur (2000)
af Silvio Micali
https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/Computationally_Sound_Proofs.pdf

Fra ekstraherbar kollisionsmodstand til kortfattede ikke-interaktive vidensargumenter [SNARKs] og tilbage igen (2011)
af Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer
https://eprint.iacr.org/2011/443.pdf

Effektivt nul-viden-argument for korrektheden af ​​en blanding (2012)
af Stephanie Bayer og Jens Groth
http://www0.cs.ucl.ac.uk/staff/J.Groth/MinimalShuffle.pdf

Kortfattet ikke-interaktiv nulviden til en von Neumann-arkitektur (2013)
af Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer og Madars Virza
https://eprint.iacr.org/2013/879.pdf

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

Offentlig mønt-nulvidensargumenter med (næsten) minimale tid- og rumomkostninger (2020)
af Alexander Block, Justin Holmgren, Alon Rosen, Ron Rothblum og Pratik Soni
https://www.iacr.org/cryptodb/data/paper.php?pubkey=30645

Oversigter og introer

Beviser, argumenter og nul-viden — En oversigt over verificerbar databehandling og interaktive beviser og argumenter, kryptografiske protokoller, der gør det muligt for en beviser at give en garanti til en verifikator for, at beviseren udførte en anmodet beregning korrekt, herunder nul-viden (hvor beviser ikke afslører andre oplysninger end deres egen gyldighed) . Zk-argumenter har et utal af applikationer inden for kryptografi og har taget springet fra teori til praksis i løbet af det sidste årti.
af Justin Thaler
https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf

En udvikling af modeller for nul-viden beviser — En gennemgang af nulvidensbeviser, hvor Meiklejohn (University College London, Google) ser på de applikationer, der driver deres udvikling, de forskellige modeller, der er dukket op for at fange disse nye interaktioner, de konstruktioner, vi kan opnå, og arbejdet tilbage at gøre.
af Sarah Meiklejohn
https://www.youtube.com/watch?v=HO97kVMI3SE

ZK tavlesessioner — introduktionsmoduler
med Dan Boneh et al
https://zkhack.dev/whiteboard/

Sikkerhed og privatliv til krypto med zkps — banebrydende bevis på nulviden i praksis; hvad zkps er, og hvordan de fungerer... inklusive live scene "demo"
af Zooko Wilcox
https://a16z.com/2019/08/29/security-and-privacy-for-crypto-with-zero-knowledge-proofs/

Topteknologiske emner, forklaret — herunder definitioner og implikationer af nulviden generelt
af 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 privatlivslag vil rette et ødelagt web
af Howard Wu
https://future.com/a-privacy-layer-for-the-web-can-change-everything/

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

Hvorfor og hvordan zk-SNARK virker: en endelig forklaring
af Maksym Petkus
https://arxiv.org/pdf/1906.07221.pdf

En introduktion til nul-viden beviser
af Fredrik Harrysson og Anna Rose
https://www.zeroknowledge.fm/21 [+ opsummering andetsteds link.]

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

Decentral hastighed — om fremskridt inden for beviser på nul viden, decentraliseret hardware
af Elena Burger
https://a16z.com/2022/04/15/zero-knowledge-proofs-hardware-decentralization-innovation/

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

Udforsker zk-forskning — med forskningsdirektør hos DFINITY; også bag fremskridt som Groth16
med Jens Groth, Anna Rose, Kobi Gurkan
https://zeroknowledge.fm/237-2/

SNARK forskning & pædagogik — med en af ​​medstifterne af ZCash og Starkware
med Alessandro Chiesa, Anna Rose
https://zeroknowledge.fm/episode-200-snark-research-pedagogy-with-alessandro-chiesa/

Dybde dyk, bygherreguider

Grundlaget for sandsynlighedsbeviser — et kursus med 5 enheder fra interaktive korrektur og mere
af Alessandro Chiesa
https://www.youtube.com/playlist?list=PLGkwtcB-DfpzST-medFVvrKhinZisfluC

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

Anatomi af en STARK — en seksdelt tutorial, der forklarer mekanikken i et STARK-bevissystem
af Alan Szepieniec
https://aszepieniec.github.io/stark-anatomy/

SNARK design, del 1 — undersøgelse, brug i rollups, mere
af Justin Thaler
https://www.youtube.com/watch?v=tg6lKPdR_e4

SNARK design, del 2 — rollups, ydeevne, sikkerhed
af Justin Thaler
https://www.youtube.com/watch?v=cMAI7g3UcoI

Måling af SNARK ydeevne — frontends, backends, mere
af 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 nul-viden bevis system — serie på 12 korte videoer om, hvordan PLONK fungerer
af David Wong
https://www.youtube.com/playlist?list=PLBJMt6zV1c7Gh9Utg-Vng2V6EYVidTFCC

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

Multiset checks i PLONK og Plookup
af 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

Applikationer og selvstudier: bevis på koncepter, demoer, værktøjer, mere

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

Et online udviklingsmiljø for zkSNARKs — zkREPL, et nyt sæt værktøjer til at interagere med Circom toolstack i browseren
af Kevin Kwok
https://zkrepl.dev (+ forklarende tråd link.)

Kvadratiske aritmetiske programmer fra nul til helt
af 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/

Forskellige typer zkEVM'er
af Vitalik Buterin
https://vitalik.ca/general/2022/08/04/zkevm.html

ZK maskinlæring — tutorial og demo til at sætte et neuralt net ind i en SNARK
af Horace Pan, Francis Ho og Henri Palacci
https://0xparc.org/blog/zk-mnist

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

Dark Forest — anvendelse af zk-kryptering til spil — et fuldt decentraliseret og vedvarende RTS (real-time strategy) spil
https://blog.zkga.me/announcing-darkforest

ZKP'er for ingeniører - et kig på Dark Forest ZKP'erne
https://blog.zkga.me/df-init-circuit

Et dyk ned i nul viden
med Elena Nadolinkski, Anna Rose, James Prestwich
https://zeroknowledge.fm/182-2/

zkDocs: Nul-viden informationsdeling
af Sam Ragsdale og Dan Boneh
https://a16zcrypto.com/zkdocs-zero-knowledge-information-sharing/

Privatlivsbeskyttende krypto-airdrops uden vidensbeviser
af Sam Ragsdale
https://a16z.com/2022/03/27/crypto-airdrop-privacy-tool-zero-knowledge-proofs/

On-chain betroede opsætningsceremonier —
af Valeria Nikolaenko og Sam Ragsdale
https://a16zcrypto.com/on-chain-trusted-setup-ceremony/

Kryptoregler, ulovlig finansiering, privatliv og mere – inkluderer afsnit om nul viden i lovgivnings-/overholdelsessammenhænge; forskellen mellem "privatlivsbevarende" og slø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 ressourcer

zkMesh nyhedsbrev — et månedligt nyhedsbrev, der deler det seneste inden for decentraliserede teknologier til beskyttelse af privatlivets fred, udvikling af privatlivsprotokol og nul videnssystemer
https://zkmesh.substack.com/

Zero Knowledge podcast — om den seneste zk research & zk-applikationer og eksperter, der bygger kryptografi-aktiveret privatlivsteknologi
med Anna Rose
https://zeroknowledge.fm/

…en kommenteret læseliste, efter emne og kronologi, af Justin Thaler:

SNARK'er fra lineære PCP'er (alias SNARK'er med kredsløbsspecifik opsætning)

Effektive argumenter uden korte PCP'er (2007)
af Yuval Ishai, Eyal Kushilevitz og Rafail Ostrovsky

Før omkring 2007 blev SNARK'er primært designet via Kilian-micali paradigme, at tage et "kort" probabilistisk kontrollerbart bevis (PCP) og "kryptografisk kompilere" det til et kortfattet argument via Merkle-hashing og Fiat-Shamir-transformationen. Desværre er korte PCP'er komplicerede og upraktiske, selv i dag. Dette papir (IKO) viste, hvordan man bruger homomorfisk kryptering til at opnå kortfattede (ikke-gennemsigtige) interaktive argumenter fra "lange, men strukturerede" PCP'er. Disse kan være meget enklere end korte PCP'er, og de resulterende SNARK'er har meget kortere beviser og hurtigere verifikation. Disse argumenter blev først anerkendt som havende potentialet for praktisk effektivitet og forfinet og implementeret i Pepper. Desværre har IKO's argumenter en kvadratisk tidsbevis og en struktureret referencestreng i kvadratisk størrelse, så de skaleres ikke til store beregninger.

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

Dette banebrydende papir (GGPR) reducerede bevisomkostningerne ved IKOs tilgang fra kvadratisk i størrelsen af ​​kredsløbet til kvasilineær. Bygger på tidligere arbejde af Groth , Lipmaa, det gav også SNARK'er via parringsbaseret kryptografi, snarere end interaktive argumenter som i IKO. Den beskrev sine SNARK'er i sammenhæng med, hvad der nu omtales som rang-1 constraint satisfaction (R1CS) problemer, en generalisering af aritmetisk kredsløbs-tilfredshed.

Dette papir tjente også som det teoretiske grundlag for de første SNARK'er, der så kommerciel udrulning (f.eks. i ZCash) og førte direkte til SNARK'er, der forbliver populære i dag (f.eks. Groth16). Indledende implementeringer af GGPRs argumenter kom ind Zaatar , Pinocchio, og senere varianter omfatter SNARKs til C , BCTV. BCIOP gav en generel ramme, der belyser disse lineære-PCP'er-til-SNARK-transformationer (se også Appendiks A til Zaatar) og beskriver forskellige instanseringer deraf.

På størrelse med parringsbaserede ikke-interaktive argumenter (2016)
af Jens Groth

Dette papir, der i daglig tale omtales som Groth16, præsenterede en forfining af GGPR's SNARK'er, der opnår state-of-the-art konkrete verifikationsomkostninger selv i dag (beviser er 3 gruppeelementer, og verifikation domineres af tre parringsoperationer, i det mindste forudsat at offentligheden input er kort). Sikkerhed er bevist i den generiske gruppemodel.

SNARK'er med universel pålidelig opsætning

PlonK: Permutationer over Lagrange-baser for økumeniske ikke-interaktive argumenter for viden (2019)
af Ariel Gabizon, Zachary Williamson og Oana Ciobotaru

Marlin: Forbehandling af zkSNARK'er med Universal og Opdaterbar SRS (2019)
af Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely og Nicholas Ward

Både PlonK og Marlin erstatter det kredsløbsspecifikke betroede setup i Groth16 med et universelt setup. Dette kommer på bekostning af 4x-6x større korrektur. Man kan tænke på PlonK og Marlin som at tage det kredsløbsspecifikke arbejde under det betroede setup i Groth16 og forgængere og flytte det ind i en forbehandlingsfase, der sker efter det betroede opsætning, såvel som under SNARK proof-generering.

Evnen til at behandle vilkårlige kredsløb og R1CS-systemer på denne måde kaldes nogle gange holografi eller beregningsforpligtelser og blev også beskrevet i Spartan (omtales senere i denne samling). Fordi der sker mere arbejde under bevisgenerering, er PlonK og Marlins beviser langsommere end Groth16 for et givet kredsløb eller R1CS-forekomst. Men i modsætning til Groth16 kan PlonK og Marlin fås til at arbejde med mere generelle mellemrepræsentationer end R1CS.

Polynomielle forpligtelsesordninger, en nøgle kryptografisk primitiv i SNARK'er

Forpligtelser i konstant størrelse til polynomier og deres applikationer (2010)
af Aniket Kate, Gregory Zaverucha og Ian Goldberg

Dette papir introducerede begrebet polynomielle forpligtelsesordninger. Det gav et skema for univariate polynomier (almindeligvis kaldet KZG-forpligtelser) med forpligtelser i konstant størrelse og evalueringsbeviser. Skemaet bruger en betroet opsætning (dvs. struktureret referencestreng) og parringsbaseret kryptografi. Det forbliver ekstremt populært i praksis i dag og bruges i SNARK'er, herunder PlonK og Marlin diskuteret ovenfor (og Groth16 bruger ekstremt lignende kryptografiske teknikker).

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

Giver et interaktivt orakelbevis (IOP) til Reed-Solomon-testning - det vil sige beviser, at en forpligtet streng er tæt på evalueringstabellen for et univariat polynomium. Kombineret med Merkle-hashing og Fiat-Shamir-transformationen giver dette et gennemsigtigt polynomielt engagementsskema med evalueringsbeviser i polylogaritmisk størrelse (se VP19 for detaljer). I dag er dette fortsat den korteste blandt plausibelt post-kvante polynomielle forpligtelsesordninger.

Ligero: Letvægts sublineære argumenter uden et betroet opsætning (2017)
af Scott Ames, Carmit Hazay, Yuval Ishai og Muthuramakrishnan Venkitasubramaniam

I lighed med FRI giver dette arbejde en IOP for Reed-Solomon-testning, men med kvadratrodssikker længde snarere end polylogaritmisk. Teoretisk virker viste, at ved at bytte Reed-Solomon-koden ud med en anden fejlkorrigerende kode med hurtigere kodning, kan man opnå en lineær-tidsbeviser, der desuden fungerer indbygget over ethvert felt. Denne tilgang er blevet forfinet og implementeret i Nedbremsning , Orion, hvilket giver state-of-the-art prøvepræstation.

Bulletproofs: Korte beviser for fortrolige transaktioner og mere (2017)
af Benedikt Bunz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille og Greg Maxwell

Forfining af tidligere arbejde ved BCCGP, Bulletproofs giver et gennemsigtigt polynomisk forpligtelsesskema (faktisk en generalisering kaldet et indre produktargument) baseret på hårdheden af ​​at beregne diskrete logaritmer med logaritmisk bevisstørrelse men lineær verifikatortid. Ordningen er stadig populær i dag på grund af dens gennemsigtighed og korte beviser (f.eks. bruges den i ZCash Orchard og Monero).

Dory: Effektive, gennemsigtige argumenter for generaliserede indre produkter og polynomielle forpligtelser (2020)
af Jonathan Lee

Dory reducerer verifikatortiden i Bulletproofs fra lineær til logaritmisk, mens den bevarer gennemsigtighed og logaritmiske beviser (omend konkret større end Bulletproofs) og gennemsigtighed. Bruger parringer og er baseret på SXDH-antagelsen.

Interaktive beviser, interaktive beviser med flere beviser og tilhørende SNARK'er

Delegerende beregning: Interaktive beviser for mugglere (2008)
af Shafi Goldwasser, Yael Tauman Kalai og Guy Rothblum

Forud for dette papir krævede interaktive korrektur til generelle formål en superpolynomisk tid bevis. Dette papir giver en interaktiv bevisprotokol, almindeligvis kaldet GKR-protokollen, med en polynomisk tidsbeviser og kvasilineær tidsbekræftelse, for ethvert problem, der har en effektiv parallelalgoritme (tilsvarende gælder det interaktive bevis for ethvert aritmetisk kredsløb med lille dybde).

Praktisk verificeret beregning med streaming af interaktive beviser (2011)
af Graham Cormode, Michael Mitzenmacher, Justin Thaler

Dette papir (nogle gange kaldet CMT) reducerede bevistiden i GKR-protokollen fra kvartisk i størrelsen af ​​kredsløbet til kvasilineær. Producerede den første implementering af et interaktivt bevis til generelle formål. En række af efterfølgende værker (allehånde, Thaler13, Girafog Libra) reducerede testerens køretid yderligere, fra kvasilineær til lineær i størrelsen af ​​kredsløbet.

vSQL: Verifikation af vilkårlige SQL-forespørgsler over dynamiske outsourcede databaser (2017)
af Yupeng Zhang, Daniel Genkin, Jonathan Katz, Dimitrios Papadopoulos og Charalampos Papamanthou

Selvom titlen refererer til et specifikt anvendelsesområde (databaser), er bidragene i denne artikel mere generelle. Specifikt observerede den, at man kan opnå kortfattede argumenter for kredsløbstilfredsstillelse ved at kombinere interaktive beviser med polynomielle forpligtelsesskemaer (for multilineære polynomier).

Senere virker afsmeltet argumenterne nul-viden og introducerede forskellige forpligtelsesordninger for multilineære polynomier.

Spartansk: Effektive og generelle zkSNARK'er uden pålidelig opsætning (2019)
af Srinath Setty

Får SNARK'er for kredsløbstilfredshed og R1CS ved at kombinere multi-prover interaktive beviser (MIP'er) med polynomielle forpligtelsesskemaer, der bygger på tidligere arbejde med konkret effektive MIP'er kaldet Clover. Effekten er at opnå SNARK'er med kortere beviser end dem, der er afledt af interaktive beviser, såsom GKR-protokollen diskuteret ovenfor. Analogt med PlonK og Marlin viser Spartan også, hvordan man behandler vilkårlige kredsløb og R1CS-systemer via forbehandling og SNARK-bevisgenerering.

Spartan brugte en polynomisk forpligtelsesordning fra hyrax. Efterfølgende værker kaldt Nedbremsning , Orion kombinere Spartans MIP med andre polynomielle forpligtelsesordninger for at give de første implementerede SNARK'er med en lineær-tidsbeviser.

Korte PCP'er og IOP'er

Korte PCP'er med Polylog Query Complexity (2005)
af Eli Ben-Sasson og Madhu Sudan

 Dette teoretiske arbejde gav det første probabilistisk kontrollerbare bevis (PCP) med bevislængde kvasilineær i størrelsen af ​​den beregning, der skal verificeres, og polylogaritmiske forespørgselsomkostninger (dog lineær verifikatortid). Efter Kilian-Micali-transformationen af ​​PCP'er til SNARK'er var dette et skridt mod SNARK'er med kvasi-lineær tidsbeviser og polylogaritmisk tidsbekræftelse.

Senere teoretisk arbejde reducerede verifikatortiden til polylogaritmisk. Efterfølgende praktisk fokuseret arbejde forfinede denne tilgang, men korte PCP'er er stadig upraktiske i dag. For at få praktiske SNARK'er, senere virker vendte til en interaktiv generalisering af PCP'er kaldet Interaktive Oracle Proofs (IOP'er). Disse bestræbelser førte til og byggede videre på FRE, et populært polynomielt forpligtelsesskema diskuteret i afsnittet om polynomielle forpligtelser i denne kompilering.

Andre værker i denne kategori omfatter ZKBoo og dets efterkommere. Disse opnår ikke kortfattede beviser, men de har gode konstante faktorer og er derfor attraktive til at bevise små udsagn. De har ført til familier af post-kvante signaturer som f.eks Picnic der har været optimeret in flere virker. ZKBoo præsenteres som efter et særskilt designparadigme kaldet MPC-i-hovedet, men det giver en IOP.

Rekursive SNARK'er

Trinvis verificerbare beregninger eller beviser for viden indebærer tids-/rumeffektivitet (2008)
af Paul Valiant

Dette arbejde introducerede den grundlæggende forestilling om inkrementelt verificerbar beregning (IVC), hvor prover kører en beregning og til enhver tid opretholder et bevis på, at beregningen hidtil har været korrekt. Det konstruerede IVC via rekursiv sammensætning af SNARK'er. Her, den viden-sundhed SNARK'ers egenskab er afgørende for at etablere soliditeten af ​​rekursivt komponerede ikke-interaktive argumenter. Dette papir gav også en ekstremt effektiv videnudtrækker til PCP-afledte SNARK'er (i henhold til Kilian-Micali-paradigmet).

Skalerbar nulviden via cyklusser af elliptiske kurver (2014)
af Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer og Madars Virza

Følgende teoretisk arbejde, brugte dette papir rekursiv anvendelse af en variant af GGPR's SNARK for at levere den første implementering af IVC til en simpel virtuel maskine (TinyRAM, fra SNARKs til C papir).

Introducerede også begrebet cyklusser af elliptiske kurver, som er nyttige til rekursivt at komponere SNARK'er, der gør brug af elliptisk kurvekryptografi.

Rekursiv bevissammensætning uden et betroet opsætning (2019)
af Sean Bowe, Jack Grigg og Daira Hopwood

Dette arbejde (kaldet Halo) studerer, hvordan man rekursivt komponerer transparente SNARK'er. Dette er mere udfordrende end at sammensætte ikke-gennemsigtige, fordi verifikationsproceduren i gennemsigtige SNARK'er kan være meget dyrere.

Dette udløste så en linje of arbejde der er kulmineret i systemer som f.eks Nova opnåelse af state-of-the-art IVC-ydelse, overlegen endda den, der opnås ved sammensætning af ikke-gennemsigtige SNARK'er såsom Groth16.

Applikationer

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

Bygger på tidligere arbejde inkl nulmønt (og med Pinnochio mønt som sideløbende arbejde), bruger dette papir GGPR-afledte SNARK'er til at designe en privat kryptovaluta. Førte til ZCash.

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

Geppetto er uden tvivl før eksplosionen af ​​interesse for privat udførelse af smarte kontrakter, der er blevet skrevet omkring et år efter oprettelsen af ​​Ethereum. Derfor præsenteres det ikke i forbindelse med privat udførelse af smarte kontrakter. Den bruger dog bounded-depth rekursion af SNARK'er for at tillade en upålidelig beviser at udføre ethvert privat (forpligtet/signeret) computerprogram på private data, uden at afsløre information om det program, der køres, eller de data, det køres på. Derfor er det en forløber for arbejde på private smart-contract platforme, som f.eks Zexe [beskrevet nedenfor].

Verificerbare ASIC'er (2015)
af Riad Wahby, Max Howald, Siddharth Garg, abhi shelat, Michael Walfish

Dette papir overvejer problemet med, hvordan man sikkert og frugtbart kan bruge en ASIC fremstillet i et støberi, der ikke er tillid til (i 2015 var der kun fem nationer med top-end støberier). Fremgangsmåden er at få den hurtige, men upålidelige ASIC til at bevise rigtigheden af ​​dens output til en verifikator, der kører på en langsommere, men pålidelig ASIC. Løsningen er interessant, så længe systemets samlede eksekveringstid (dvs. summen af ​​prover- og verifikatorkørselstider plus eventuelle datatransmissionsomkostninger) er mindre end den naive baseline: den tid, der kræves for at køre beregningen fuldt ud på den langsommere -men betroede ASIC. Ved at bruge en variant af GKR/CMT/Allspice interaktive beviser slår papiret faktisk den naive baseline for en række fundamentale problemer, herunder talteoretiske transformationer, mønstertilpasning og elliptiske kurveoperationer. Dette arbejde tyder på, at nogle bevissystemer er mere velegnede til hardwareimplementering end andre. Optimering af bevissystemer til hardwareimplementering modtager nu betydelig opmærksomhed, men meget mangler at blive udforsket.

verificerbar Forsinkelsesfunktioner (2018)
af Dan Boneh, Joseph Bonneau, Benedikt Bünz og Ben Fisch

Introducerede notationen af ​​verificerbare forsinkelsesfunktioner (VDF'er), en kryptografisk primitiv, der er bredt anvendelig i blockchain-applikationer, f.eks. til at afbøde mulig manipulation af proof-of-stake konsensusprotokoller. SNARK'er (især til inkrementelt verificerbare beregninger) tilbyder en rute til avancerede VDF'er.

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

Zexe er et design til en privat smart-kontrakt platform. Man kan se Zexe som en forlængelse af Zerocash (beskrevet ovenfor). Zerocash gør det muligt at køre en enkelt applikation på kæden (der gør det muligt for brugere at overføre tokens), mens privatlivets fred for brugerdata beskyttes, f.eks. hvem de sender tokens til, modtager tokens fra, mængden af ​​tokens, der overføres osv. Zexe tillader mange forskellige applikationer (smarte kontrakter) til at køre på den samme blockchain og interagere med hinanden. Transaktioner udføres uden for kæden, og beviser for korrekt udførelse bogføres på kæden. Databeskyttelse er ikke kun beskyttet, det samme er funktionsbeskyttelse. Dette betyder, at beviset forbundet med hver transaktion ikke engang afslører, hvilke applikationer transaktionen vedrører. Et mere generelt teknisk bidrag fra Zexe er, at det introducerede BLS12-377, en elliptisk kurvegruppe, der er nyttig til effektiv dybde-1-sammensætning af parringsbaserede SNARK'er.

Replikerede tilstandsmaskiner uden replikeret udførelse (2020)
af Jonathan Lee, Kirill Nikitin og Srinath Setty

Dette er en af ​​de få akademiske artikler om rollups til skalerbarhed af blockchain. Den bruger ikke begrebet rollups, fordi det går forud for eller er samtidig med, at konceptet introduceres uden for den akademiske litteratur.

Front-ends (effektive transformationer fra computerprogrammer til mellemliggende repræsentationer såsom kredsløbstilfredshed, R1CS og mere)

Hurtige reduktioner fra RAM'er til delegerbare kortfattede problemer med tilfredshed (2012)
af Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin og Eran Tromer

Fra et moderne perspektiv er dette et tidligt arbejde med praktiske computer-program-til-kredsløb-SAT-transformationer til en virtuel maskine (VM) abstraktion. Bygger på værker fra slutningen af ​​1970'erne til 1990'erne (f.eks. arbejde af Robson) dette papir beskriver en deterministisk reduktion fra at udføre en VM for T-trin til tilfredsstillelsen af ​​et kredsløb af størrelse O(T*polylog(T)).

Efterfølgende papirer, f.eks. SNARKs til C , BCTV, fortsatte med at udvikle front-ends via en VM-abstraktion, og moderne instantiationer omfatter projekter som f.eks. Cairo, RISC nulog Polygon Miden.

Ved at tage bevisbaseret verificeret beregning et par skridt tættere på praktisk (2012)
af Srinath Setty, Victor Vu, Nikhil Panpalia, Benjamin Braun, Muqeet Ali, Andrew J. Blumberg og Michael Walfish

Dette papir, kaldet Ginger, er endnu et tidligt bidrag til praktiske front-end-teknikker. Ginger introducerede gadgets til generelle programmeringsprimitiver som betingede og logiske udtryk, sammenligninger og bitvis aritmetik via bitopdeling, primitiv flydende aritmetik osv. Den brugte disse gadgets til at levere den første implementerede front-end fra et højt niveau sprog til lav grad aritmetiske begrænsninger (svarende til det, der nu er kendt som R1CS), en mellemrepræsentation (IR), som en SNARK-backend kan anvendes til.

Hvorimod papiret "Hurtige reduktioner" og dets efterkommere bruger en "CPU-emulator"-tilgang til at producere IR'er (dvs. IR'en håndhæver, at beviseren kørte et bestemt program korrekt ved at anvende CPU'ens overgangsfunktion til et specificeret antal trin) , Ginger og dens efterkommere tager en mere ASIC-lignende tilgang og producerer IR'er, der er skræddersyet til det computerprogram, som beviseren hævder at udføre korrekt.

For eksempel: Buffet viser, at det er muligt at håndtere komplekst kontrolflow i ASIC-modellen ved at omdanne et sådant kontrolflow til en finite-state maskine, der er skræddersyet til det program, der udføres, og at denne tilgang kan være væsentligt mere effektiv end at bygge en generel CPU-emulator. xJsnark giver en effektiv konstruktion til multi-præcision aritmetik, optimeringer til RAM'er og ROM'er og afslører et Java-lignende sprog på højt niveau for en programmør, som stadig er populær i dag. CirC bemærker, at kompilering af computerprogrammer til R1CS er tæt forbundet med velkendte teknikker fra programanalyse og bygger et kompileringsværktøjssæt, der inkorporerer ideer fra begge fællesskaber ("LLVM for kredsløbslignende repræsentationer"). Tidligere værker, der giver bidrag til ASIC-stil front-ends omfatter Pinocchio , Geppetto.

Papiret "Fast-Reductions" brugte en kompliceret og dyr konstruktion kaldet "routing-netværk" til såkaldte hukommelseskontrol (dvs. at sikre, at den ikke-betroede beviser korrekt vedligeholder VM'ens random access memory under udførelsen af ​​den VM, hvis korrekthed bliver bevist). Dette valg blev truffet, fordi tidlige værker som dette søgte at opnå en PCP, hvilket krævede, at front-end var både ikke-interaktiv og informationsteoretisk sikker. Senere arbejde kaldte Pantry (en forgænger til Buffet arbejde nævnt ovenfor) brugte Merkle-træer i stedet for routing-netværk, hvilket opnåede effektivitet ved at kompilere en algebraisk (dvs. "SNARK-venlig") hashfunktion, pga. Ajtai, ind i begrænsninger. Dette resulterede i "beregningssikre" front-ends. I dag findes der en stor forskningslitteratur om SNARK-venlige hashfunktioner, med eksempler bl.a Poseidon, MiMC, Forstærket beton, RescueOg meget mere.

Avancerede teknikker til at sikre, at beviseren vedligeholder RAM korrekt, er afhængige af såkaldte "permutation-invariant fingerprinting"-metoder, der går tilbage i det mindste Lipton (1989) og bruges til hukommelseskontrol af Blum et al. (1991). Disse teknikker involverer i sagens natur interaktion mellem en beviser og verifikator, men kan gøres ikke-interaktive med Fiat-Shamir-transformationen. Så vidt vi ved, blev de introduceret til litteraturen om praktiske SNARK front-ends af et system kaldet VRAM.

Permutations-invariante fingeraftryksteknikker bruges nu i mange front-ends og SNARK'er til virtuelle maskineabstraktioner, herunder f.eks. Cairo. Nært beslægtede ideer dukkede op igen i beslægtede sammenhænge i de to værker nedenfor, som bruges meget i praksis i dag.

Næsten lineær-tid nul-viden beviser for korrekt programudførelse (2018)
af Jonathan Bootle, Andrea Cerulli, Jens Groth, Sune Jakobsen og Mary Maller

Plookup: En forenklet polynomiel protokol til opslagstabeller (2020)
af Ariel Gabizon og Zachary Williamson

Tidlige værker på front-ends repræsenterede "ikke-aritmetiske" operationer (såsom rækkeviddetjek, bitvise operationer og heltalssammenligninger) inde i kredsløb og relaterede IR'er ved at opdele feltelementer i bits, udføre operationerne på disse bit og derefter "pakke" resultatet tilbage i et enkelt feltelement. Med hensyn til størrelsen af ​​det resulterende kredsløb resulterer dette i en logaritmisk overhead pr. operation.

Ovenstående to værker (BCGJM og Plookup) giver indflydelsesrige teknikker (baseret på såkaldte "opslagstabeller") til mere effektivt at repræsentere disse operationer inde i kredsløb, i en amortiseret forstand. Groft sagt, for nogle parameter B valgt af front-end designeren, reducerer disse antallet af porte, der kræves for at repræsentere hver ikke-aritmetisk operation i kredsløbet med en faktor logaritmisk i B, på bekostning af, at beviseren kryptografisk forpligter sig til en ekstra "råd"-vektor af længden omtrent B.