Zero Knowledge Canon

Redaktörens anteckning: a16z crypto har haft en lång serie av "pistoler", från vår DAO Canon förra året till vår NFT Canon tidigare (och innan dess vårt original Krypto Canon) — se till att registrera dig för vår web3 veckobrev för fler uppdateringar samt andra kurerade resurser.

Så bNedan har vi samlat ihop en uppsättning resurser för dem som vill förstå, gå djupare och bygga med allt ingen kunskap: kraftfull, grundläggande teknik som håller nycklarna till blockkedjeskalbarhet och representerar framtiden för integritetsbevarande applikationer och otaliga andra innovationer som kommer. Om du har förslag på högkvalitativa bitar att lägga till, låt oss veta @a16zcrypto.

Noll-kunskapssäkra system har funnits i decennier: Deras introduktion av Shafi Goldwasser, Silvio Micali och Charles Rackoff 1985 hade en transformativ effekt på kryptografiområdet och erkändes av ACM Turing Award som tilldelades Goldwasser och Micali i 2012. Eftersom detta arbete – inklusive dess övergång från teori till praktik och tillämpningar inom krypto/web3 idag – har varit årtionden under utveckling, delar vi också för första gången i vår kanonserie en del två (för nu, inkluderad här nedan): en läslista kommenterad av Justin Thaler, efter del ett nedan.

Tack också till Michael Blau, Sam Ragsdale och Tim Roughgarden.

Grunder, bakgrund, evolutioner

Vissa av dessa dokument handlar också mer om kryptografi i allmänhet (inte all noll kunskap i sig), inklusive att skissera problem eller nyckelframsteg som tas upp av noll kunskapsbevis idag: hur man säkerställer integritet och autentisering i öppna nätverk.

Nya riktningar inom kryptografi (1976)
av Whitfield Diffie och Martin Hellman
https://ee.stanford.edu/~hellman/publications/24.pdf

En metod för att erhålla digitala signaturer och kryptosystem med publik nyckel
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

Protokoll för kryptosystem med offentliga nyckel (1980)
av Ralph Merkle
http://www.merkle.com/papers/Protocols.pdf

Säker kommunikation över osäkra kanaler (1978)
av Ralph Merkle
https://www.merkle.com/1974/PuzzlesAsPublished.pdf

Användning av elliptiska kurvor i kryptografi (1988)
av Victor Miller
https://link.springer.com/content/pdf/10.1007%2F3-540-39799-X_31.pdf

Kunskapskomplexiteten hos interaktiva bevissystem (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

Beräkningsljud korrektur (2000)
av Silvio Micali
https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/Computationally_Sound_Proofs.pdf

Från extraherbart kollisionsmotstånd till kortfattade icke-interaktiva kunskapsargument [SNARKs] och tillbaka igen (2011)
av Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer
https://eprint.iacr.org/2011/443.pdf

Effektivt nollkunskapsargument för korrektheten av en blandning (2012)
av Stephanie Bayer och Jens Groth
http://www0.cs.ucl.ac.uk/staff/J.Groth/MinimalShuffle.pdf

Kortfattad icke-interaktiv noll kunskap för en von Neumann Architecture (2013)
av Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer och Madars Virza
https://eprint.iacr.org/2013/879.pdf

Skalbar, transparent och post-kvantsäker beräkningsintegritet (2018)
av Eli Ben-Sasson, Iddo Bentov, Yinon Horesh och Michael Riabzev
https://eprint.iacr.org/2018/046.pdf

Offentligt mynt noll-kunskapsargument med (nästan) minimala tids- och utrymmeskostnader (2020)
av Alexander Block, Justin Holmgren, Alon Rosen, Ron Rothblum och Pratik Soni
https://www.iacr.org/cryptodb/data/paper.php?pubkey=30645

Översikter & intros

Bevis, argument och noll-kunskap — En översikt över verifierbar datoranvändning och interaktiva bevis och argument, kryptografiska protokoll som gör det möjligt för en verifierare att ge en garanti till en verifierare att verifieraren utförde en begärd beräkning korrekt, inklusive noll-kunskap (där bevis inte avslöjar någon annan information än deras egen giltighet) . Zk-argument har en myriad av tillämpningar inom kryptografi och har tagit steget från teori till praktik under det senaste decenniet.
av Justin Thaler
https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf

En utveckling av modeller för nollkunskapsbevis — En genomgång av nollkunskapsbevis, där Meiklejohn (University College London, Google) tittar på applikationerna som driver deras utveckling, de olika modellerna som har dykt upp för att fånga dessa nya interaktioner, de konstruktioner vi kan åstadkomma och arbetet kvar att göra.
av Sarah Meiklejohn
https://www.youtube.com/watch?v=HO97kVMI3SE

ZK whiteboard sessioner — Introduktionsmoduler
med Dan Boneh et al
https://zkhack.dev/whiteboard/

Säkerhet och integritet för krypto med zkps — Banbrytande bevis på nollkunskap i praktiken; vad zkps är och hur de fungerar ... inklusive livescen "demo"
av Zooko Wilcox
https://a16z.com/2019/08/29/security-and-privacy-for-crypto-with-zero-knowledge-proofs/

Topp tekniska ämnen, förklarat — inklusive definitioner och konsekvenser av nollkunskap i allmänhet
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

Hur det kommande integritetslagret kommer att fixa en trasig webb
av Howard Wu
https://future.com/a-privacy-layer-for-the-web-can-change-everything/

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

Varför och hur zk-SNARK fungerar: en definitiv förklaring
av Maksym Petkus
https://arxiv.org/pdf/1906.07221.pdf

En introduktion till nollkunskapsbevis
av Fredrik Harrysson och Anna Rose
https://www.zeroknowledge.fm/21 [+ sammanfattningsskrivning någon annanstans här.]

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

Decentraliserad hastighet — på framsteg inom noll kunskapsbevis, decentraliserad hårdvara
av Elena Burger
https://a16z.com/2022/04/15/zero-knowledge-proofs-hardware-decentralization-innovation/

Banbrytande zk-forskning — med zk-forskare på Ethereum Foundation
med Mary Maller, Anna Rose, Kobi Gurkan
https://zeroknowledge.fm/232-2/

Utforska zk-forskning — med forskningschef vid DFINITY; också bakom framsteg som Groth16
med Jens Groth, Anna Rose, Kobi Gurkan
https://zeroknowledge.fm/237-2/

SNARK forskning & pedagogik — med en av medgrundarna till ZCash och Starkware
med Alessandro Chiesa, Anna Rose
https://zeroknowledge.fm/episode-200-snark-research-pedagogy-with-alessandro-chiesa/

Djupdyk, byggguider

Grunderna för probabilistiska bevis — en kurs med 5 enheter från interaktiva korrektur och 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

Anatomi av en STARK — en självstudie i sex delar som förklarar mekaniken i ett STARK-bevissystem
av Alan Szepieniec
https://aszepieniec.github.io/stark-anatomy/

SNARK design, del 1 — undersökning, användning i sammanslagningar, mer
av Justin Thaler
https://www.youtube.com/watch?v=tg6lKPdR_e4

SNARK design, del 2 — rollups, prestanda, säkerhet
av Justin Thaler
https://www.youtube.com/watch?v=cMAI7g3UcoI

Mätning av SNARK-prestanda — frontends, backends, mer
av Justin Thaler
https://a16zcrypto.com/measuring-snark-performance-frontends-backends-and-the-future/

Förstå PLONK
https://vitalik.ca/general/2019/09/22/plonk.html

PLONK noll-kunskapssäkert system — serie med 12 korta videor om hur PLONK fungerar
av David Wong
https://www.youtube.com/playlist?list=PLBJMt6zV1c7Gh9Utg-Vng2V6EYVidTFCC

Från AIR till RAP — hur aritmetisering i PLONK-stil fungerar
av Ariel Gabizon
https://hackmd.io/@aztec-network/plonk-arithmetiization-air

Multiset checkar i PLONK och Plookup
av Ariel Gabizon
https://hackmd.io/@arielg/ByFgSDA7D

Halo2 design — från ECC
https://zcash.github.io/halo2/design.html

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

Applikationer och handledning: bevis på koncept, demos, verktyg, mer

Tillämpad zk — Lärmedel
av 0xPARC
https://learn.0xparc.org/materials/intro

En onlineutvecklingsmiljö för zkSNARKs — zkREPL, en ny uppsättning verktyg för att interagera med Circom Toolstack i webbläsaren
av Kevin Kwok
https://zkrepl.dev (+ förklarar tråd här.)

Kvadratiska aritmetiska program från noll till hjälte
av Vitalik Buterin
https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

På zkEVMs
med Alex Gluchowski och Anna Rose
https://zeroknowledge.fm/175-2/

Olika typer av zkEVMs
av Vitalik Buterin
https://vitalik.ca/general/2022/08/04/zkevm.html

ZK maskininlärning — handledning och demo för att placera ett neuralt nät i en SNARK
av Horace Pan, Francis Ho och Henri Palacci
https://0xparc.org/blog/zk-mnist

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

Dark Forest — tillämpa zk-kryptering på spel — ett helt decentraliserat och beständigt RTS-spel (realtidsstrategi).
https://blog.zkga.me/announcing-darkforest

ZKP för ingenjörer — en titt på Dark Forest ZKPs
https://blog.zkga.me/df-init-circuit

En dykning in i noll kunskap
med Elena Nadolinkski, Anna Rose, James Prestwich
https://zeroknowledge.fm/182-2/

zkDocs: Noll-kunskapsinformationsdelning
av Sam Ragsdale och Dan Boneh
https://a16zcrypto.com/zkdocs-zero-knowledge-information-sharing/

Sekretessskyddande krypto-airdrops med noll kunskapsbevis
av Sam Ragsdale
https://a16z.com/2022/03/27/crypto-airdrop-privacy-tool-zero-knowledge-proofs/

Pålitliga installationsceremonier på kedjan -
av Valeria Nikolaenko och Sam Ragsdale
https://a16zcrypto.com/on-chain-trusted-setup-ceremony/

Kryptoregleringar, olaglig finansiering, integritet och mer – Innehåller avsnitt om noll kunskap i regel-/efterlevnadssammanhang; skillnaden mellan "integritetsbevarande" och förvirrande teknologier
med Michele Korver, Jai Ramaswamy, Sonal Chokshi
https://web3-with-a16z.simplecast.com/episodes/crypto-regulations-sanctions-compliance-aml-ofac-news-explained

Andra resurser

zkMesh nyhetsbrev — ett månatligt nyhetsbrev som delar det senaste inom decentraliserad integritetsbevarande teknik, utveckling av sekretessprotokoll och noll kunskapssystem
https://zkmesh.substack.com/

Zero Knowledge podcast — om den senaste zk-forskningen och zk-applikationerna och experter som bygger kryptografi-aktiverad integritetsteknik
med Anna Rose
https://zeroknowledge.fm/

…en kommenterad läslista, efter ämne och kronologi, av Justin Thaler:

SNARK från linjära PCP (alias SNARKs med kretsspecifik inställning)

Effektiva argument utan korta PCP (2007)
av Yuval Ishai, Eyal Kushilevitz och Rafail Ostrovsky

Före omkring 2007 designades SNARK främst via Kilian-Micali paradigm, att ta ett "kort" probabilistiskt kontrollerbart bevis (PCP) och "kryptografiskt sammanställa" det till ett kortfattat argument via Merkle-hashing och Fiat-Shamir-transformationen. Tyvärr är korta PCP komplicerade och opraktiska, även idag. Detta dokument (IKO) visade hur man använder homomorf kryptering för att få kortfattade (otransparenta) interaktiva argument från "långa men strukturerade" PCP. Dessa kan vara mycket enklare än korta PCP, och de resulterande SNARK:erna har mycket kortare bevis och snabbare verifiering. Dessa argument erkändes först som att de hade potential för praktisk effektivitet och förfinades och implementerades i Peppar. Tyvärr har IKO:s argument en kvadratisk tidsbevisare och en strukturerad referenssträng i kvadratisk storlek, så de skalas inte till stora beräkningar.

Quadratic Span-program och kortfattade NIZK utan PCP (2012)
av Rosario Gennaro, Craig Gentry, Bryan Parno och Mariana Raykova

Detta genombrottspapper (GGPR) minskade provningskostnaderna för IKO:s tillvägagångssätt från kvadratisk i storleken på kretsen till kvasilinjär. Bygger på tidigare arbete av Groth och Lipmaa, gav det också SNARKs via parningsbaserad kryptografi, snarare än interaktiva argument som i IKO. Den beskrev sina SNARKs i sammanhanget av vad som nu kallas rank-1 constraint satisfaction (R1CS) problem, en generalisering av aritmetisk krets-satisfiability.

Denna artikel fungerade också som den teoretiska grunden för de första SNARKs som såg kommersiell utplacering (t.ex. i ZCash) och ledde direkt till SNARKs som fortfarande är populära idag (t.ex. Groth16). Inledande implementeringar av GGPR:s argument kom in Zaatar och Pinocchio, och senare varianter inkluderar SNARKs för C och BCTV. BCIOP gav ett allmänt ramverk som belyser dessa linjära-PCP-till-SNARK-transformationer (se även Appendix A i Zaatar) och beskriver olika instansieringar därav.

Om storleken på parningsbaserade icke-interaktiva argument (2016)
av Jens Groth

Det här dokumentet, i vardagsspråk kallat Groth16, presenterade en förfining av GGPR:s SNARKs som uppnår toppmoderna betongverifieringskostnader även idag (bevis är 3 gruppelement, och verifiering domineras av tre parningsoperationer, åtminstone förutsatt att allmänheten ingången är kort). Säkerhet bevisas i den generiska gruppmodellen.

SNARKs med universell pålitlig installation

PlonK: Permutationer över Lagrange-baser för ekumeniska icke-interaktiva kunskapsargument (2019)
av Ariel Gabizon, Zachary Williamson och Oana Ciobotaru

Marlin: Förbearbetning av zkSNARKs med universell och uppdateringsbar SRS (2019)
av Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely och Nicholas Ward

Både PlonK och Marlin ersätter den kretsspecifika betrodda uppställningen i Groth16 med en universell uppställning. Detta kommer på bekostnad av 4x-6x större provtryck. Man kan tänka på PlonK och Marlin som att ta det kretsspecifika arbetet under den betrodda installationen i Groth16 och föregångare och flytta det till en förbearbetningsfas som händer efter den pålitliga installationen, såväl som under SNARK-provgenerering.

Förmågan att bearbeta godtyckliga kretsar och R1CS-system på detta sätt kallas ibland holografi eller beräkningsåtaganden, och beskrevs också i Spartan (diskuteras senare i denna sammanställning). Eftersom mer arbete sker under provgenerering är PlonK och Marlins provare långsammare än Groth16 för en given krets eller R1CS-instans. Men till skillnad från Groth16 kan PlonK och Marlin fås att fungera med mer generella mellanrepresentationer än R1CS.

Polynomiska åtagandescheman, en nyckel kryptografisk primitiv i SNARKs

Åtaganden i konstant storlek för polynom och deras tillämpningar (2010)
av Aniket Kate, Gregory Zaverucha och Ian Goldberg

Detta dokument introducerade begreppet polynomiska åtagandesystem. Den gav ett schema för univariata polynom (vanligen kallade KZG-åtaganden) med åtaganden i konstant storlek och utvärderingsbevis. Schemat använder en betrodd uppsättning (dvs. strukturerad referenssträng) och parningsbaserad kryptografi. Det är fortfarande extremt populärt i praktiken idag och används i SNARKs inklusive PlonK och Marlin som diskuterats ovan (och Groth16 använder extremt liknande kryptografiska tekniker).

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

Ger ett interaktivt orakelbevis (IOP) för Reed-Solomon-testning - det vill säga bevisar att en tecknad sträng ligger nära utvärderingstabellen för ett univariat polynom. I kombination med Merkle-hashing och Fiat-Shamir-transformationen ger detta ett transparent polynomåtagandesystem med utvärderingsbevis i polylogaritmisk storlek (se VP19 för detaljer). Idag är detta det kortaste bland troligtvis post-kvantpolynomiska åtagandesystem.

Ligero: Lättvikts sublinjära argument utan en pålitlig uppsättning (2017)
av Scott Ames, Carmit Hazay, Yuval Ishai och Muthuramakrishnan Venkitasubramaniam

I likhet med FRI ger detta arbete en IOP för Reed-Solomon-testning, men med kvadratrotssäker längd snarare än polylogaritmisk. Teoretisk fungerar visade att genom att byta ut Reed-Solomon-koden mot en annan felkorrigerande kod med snabbare kodning kan man få ett linjärt tidsbevis som dessutom fungerar inbyggt över vilket fält som helst. Detta tillvägagångssätt har förfinats och implementerats i Bromsning och Orion, vilket ger toppmodern provprestanda.

Bulletproofs: Korta bevis för konfidentiella transaktioner och mer (2017)
av Benedikt Bunz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille och Greg Maxwell

Förfina tidigare arbete av BCCGP, Bulletproofs ger ett transparent polynomförpliktelseschema (i själva verket en generalisering som kallas ett inre produktargument) baserat på hårdheten i att beräkna diskreta logaritmer med logaritmisk bevisstorlek men linjär verifieringstid. Systemet är fortfarande populärt idag på grund av dess transparens och korta provtryck (t.ex. används det i ZCash Orchard och Monero).

Dory: Effektiva, transparenta argument för generaliserade inre produkter och polynomiska åtaganden (2020)
av Jonathan Lee

Dory minskar verifieringstiden i Bulletproofs från linjär till logaritmisk, samtidigt som transparens och bevis i logaritmisk storlek (om än konkret större än Bulletproofs) och transparens bevaras. Använder parningar och är baserad på SXDH-antagandet.

Interactive Proofs, multi-prover interaktiva Proofs och tillhörande SNARKs

Delegerande beräkning: Interaktiva bevis för mugglare (2008)
av Shafi Goldwasser, Yael Tauman Kalai och Guy Rothblum

Före detta dokument krävde interaktiva korrektur för allmänna ändamål en superpolynom-tid bevis. Detta dokument ger ett interaktivt bevisprotokoll, vanligtvis kallat GKR-protokollet, med en polynomisk tidsbevisare och kvasilinjär tidsverifierare, för alla problem som har en effektiv parallellalgoritm (motsvarande gäller det interaktiva beviset för alla aritmetiska kretsar med litet djup).

Praktisk verifierad beräkning med strömmande interaktiva bevis (2011)
av Graham Cormode, Michael Mitzenmacher, Justin Thaler

Detta papper (ibland kallat CMT) reducerade provningstiden i GKR-protokollet från kvarts i storleken på kretsen till kvasilinjär. Producerade den första implementeringen av ett interaktivt prov för allmänt bruk. En rad efterföljande verk (Kryddpeppar, Thaler13, Giraffoch Vågen) minskade provarens körtid ytterligare, från kvasilinjär till linjär i storleken på kretsen.

vSQL: Verifiera godtyckliga SQL-frågor över dynamiska outsourcade databaser (2017)
av Yupeng Zhang, Daniel Genkin, Jonathan Katz, Dimitrios Papadopoulos och Charalampos Papamanthou

Även om titeln hänvisar till ett specifikt tillämpningsområde (databaser), är bidragen i denna artikel mer generella. Specifikt observerade den att man kan få kortfattade argument för kretsens tillfredsställelse genom att kombinera interaktiva bevis med polynomiska åtagandescheman (för multilinjära polynom).

Senare fungerar renderade argumenten noll-kunskap och introducerade olika åtagandesystem för multilinjära polynom.

Spartan: Effektiva och allmänna zkSNARKs utan pålitlig installation (2019)
av Srinath Setty

Erhåller SNARK för krets-tillfredsställelse och R1CS genom att kombinera multi-prover interaktiva bevis (MIPs) med polynomiella åtagandescheman, som bygger på tidigare arbete med konkret effektiva MIPs som kallas Clover. Effekten är att erhålla SNARKs med kortare bevis än de som härrör från interaktiva bevis såsom GKR-protokollet diskuterat ovan. Analogt med PlonK och Marlin visar Spartan också hur man bearbetar godtyckliga kretsar och R1CS-system via förbearbetning och SNARK proof-generering.

Spartan använde ett polynomåtagandeschema från hyrax. Efterföljande verk kallas Bromsning och Orion kombinera Spartans MIP med andra polynomiska åtagandesystem för att ge de första implementerade SNARKs med en linjär-tidsbevisare.

Korta PCP och IOP

Korta PCP:er med Polylog Query Complexity (2005)
av Eli Ben-Sasson och Madhu Sudan

 Detta teoretiska arbete gav det första probabilistiskt kontrollerbara beviset (PCP) med bevislängden kvasilinjär i storleken på beräkningen som ska verifieras och polylogaritmisk frågekostnad (men linjär verifieringstid). Efter Kilian-Micali-omvandlingen av PCP:er till SNARK:er var detta ett steg mot SNARK:er med kvasilinjär tidsbevisare och polylogaritmisk tidsverifierare.

Senare teoretiskt arbete reducerade verifieringstiden till polylogaritmisk. Efterföljande praktiskt fokuserat arbete förfinade detta tillvägagångssätt, men korta PCP är fortfarande opraktiska idag. För att få praktiska SNARKs, senare fungerar vände till en interaktiv generalisering av PCP kallas Interaktiva Oracle Proofs (IOP). Dessa ansträngningar ledde till och bygger vidare Fredag, ett populärt polynomåtagandeschema som diskuteras i polynomåtagandeavsnittet i denna sammanställning.

Andra verk i denna kategori inkluderar ZKBoo och dess ättlingar. Dessa ger inga kortfattade bevis, men de har goda konstanta faktorer och är därför attraktiva för att bevisa små påståenden. De har lett till familjer av post-kvantsignaturer som t.ex Picknick som har varit optimerad in flera fungerar. ZKBoo presenteras enligt ett distinkt designparadigm som kallas MPC-i-huvudet, men det ger en IOP.

Rekursiva SNARKs

Inkrementellt verifierbar beräkning eller kunskapsbevis innebär tids-/rymdeffektivitet (2008)
av Paul Valiant

Detta arbete introducerade den grundläggande uppfattningen om inkrementellt verifierbar beräkning (IVC), där prover kör en beräkning och alltid upprätthåller ett bevis på att beräkningen hittills har varit korrekt. Det konstruerade IVC via rekursiv sammansättning av SNARKs. Här, den kunskap-sundhet SNARKs egendom är väsentlig för att fastställa sundheten hos rekursivt sammansatta icke-interaktiva argument. Detta dokument gav också en extremt effektiv kunskapsextraktor för PCP-härledda SNARKs (enligt Kilian-Micali-paradigmet).

Skalbar nollkunskap via cykler av elliptiska kurvor (2014)
av Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer och Madars Virza

Efter teoretiskt arbete, använde detta dokument rekursiv tillämpning av en variant av GGPR:s SNARK, för att tillhandahålla den första implementeringen av IVC för en enkel virtuell maskin (TinyRAM, från SNARKs för C papper).

Introducerade också begreppet cykler av elliptiska kurvor, som är användbara för att rekursivt komponera SNARKs som använder sig av elliptisk kurvkryptografi.

Rekursiv beviskomposition utan en pålitlig installation (2019)
av Sean Bowe, Jack Grigg och Daira Hopwood

Detta arbete (kallat Halo) studerar hur man rekursivt komponerar transparenta SNARKs. Detta är mer utmanande än att komponera icke-transparenta eftersom verifieringsproceduren i transparenta SNARKs kan vara mycket dyrare.

Detta utlöste sedan en linje of arbete som har kulminerat i system som t.ex Nytt uppnå toppmoderna IVC-prestanda, överlägsen till och med den som erhålls genom sammansättning av icke-transparenta SNARKs som Groth16.

Applikationer

Zerocash: Decentraliserade anonyma betalningar från Bitcoin (2014)
av Eli Ben Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, Madars Virza

Bygger på tidigare arbete inklusive Nollmynt (och med Pinnochio mynt som samtidigt arbete) använder detta dokument GGPR-härledda SNARKs för att designa en privat kryptovaluta. Ledde till ZCash.

Geppetto: mångsidig verifierbar beräkning (2014)
av Craig Costello, Cédric Fournet, Jon Howell, Markulf Kohlweiss, Benjamin Kreuter, Michael Naehrig, Bryan Parno och Samee Zahur

Geppetto är utan tvekan före explosionen av intresse för privat utförande av smarta kontrakt, efter att ha skrivits ungefär ett år efter skapandet av Ethereum. Därför presenteras det inte i samband med privat utförande av smarta kontrakt. Den använder dock bounded-depth-rekursion av SNARK:er för att tillåta en opålitlig provare att exekvera alla privata (engagerade/signerade) datorprogram på privata data, utan att avslöja information om programmet som körs eller data det körs på. Följaktligen är det en föregångare för arbete på privata smarta kontraktsplattformar, som t.ex Zexe [beskrivet nedan].

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

Detta dokument tar upp problemet med hur man säkert och fruktbart använder en ASIC tillverkad i ett opålitligt gjuteri (2015 fanns det bara fem nationer med toppgjuterier). Tillvägagångssättet är att låta den snabba men opålitliga ASIC:en bevisa riktigheten av dess utdata för en verifierare som körs på en långsammare men pålitlig ASIC. Lösningen är intressant så länge som den totala exekveringstiden för systemet (dvs summan av provarens och verifierarens körtider plus eventuella dataöverföringskostnader) är mindre än den naiva baslinjen: tiden som krävs för att köra beräkningen i sin helhet på den långsammare -men litade på ASIC. Genom att använda en variant av GKR/CMT/Allspice interaktiva korrektur, slår papperet verkligen den naiva baslinjen för ett antal grundläggande problem, inklusive talteoretiska transformationer, mönstermatchning och elliptiska kurvoperationer. Detta arbete antyder att vissa provsystem är mer lämpade för hårdvaruimplementering än andra. Optimering av bevissystem för hårdvaruimplementering tar nu emot betydande uppmärksamhet, men mycket återstår att utforska.

kontrollerbara Fördröjningsfunktioner (2018)
av Dan Boneh, Joseph Bonneau, Benedikt Bünz och Ben Fisch

Introducerade notationen för verifierbara fördröjningsfunktioner (VDFs), en kryptografisk primitiv som är allmänt användbar i blockkedjeapplikationer, t.ex. för att mildra eventuell manipulation av proof-of-stake konsensusprotokoll. SNARKs (särskilt för inkrementellt verifierbara beräkningar) erbjuder en väg till toppmoderna VDF:er.

Zexe: Aktiverar decentraliserad privat beräkning (2018)
av Sean Bowe, Alessandro Chiesa, Matthew Green, Ian Miers, Pratyush Mishra och Howard Wu

Zexe är en design för en privat smart kontraktsplattform. Man kan se Zexe som en förlängning av Zerocash (beskrivs ovan). Zerocash gör det möjligt att köra en enda applikation i kedjan (så att användare kan överföra tokens) samtidigt som användardata skyddas, t.ex. vem de skickar tokens till, tar emot tokens från, mängden tokens som överförs, etc. Zexe tillåter många olika applikationer (smarta kontrakt) att köra på samma blockchain och interagera med varandra. Transaktioner utförs utanför kedjan, och bevis på korrekt utförande läggs upp i kedjan. Inte bara är dataintegritet skyddad, så är funktionssekretess. Detta innebär att beviset för varje transaktion inte ens avslöjar vilken eller vilka applikationer transaktionen avser. Ett mer allmänt tekniskt bidrag från Zexe är att det introducerade BLS12-377, en elliptisk kurvgrupp som är användbar för effektiv djup-1-sammansättning av parningsbaserade SNARKs.

Replikerade tillståndsmaskiner utan replikerad exekvering (2020)
av Jonathan Lee, Kirill Nikitin och Srinath Setty

Det här är en av få akademiska artiklar om sammanslagningar för skalbarhet av blockkedjor. Den använder inte termen rollups, eftersom den går före eller är samtidigt med att konceptet introduceras utanför den akademiska litteraturen.

Front-ends (effektiva transformationer från datorprogram till mellanliggande representationer som krets-tillfredsställelse, R1CS och mer)

Snabba minskningar från RAM-minnen till delegerbara kortfattade problem med tillfredsställelse (2012)
av Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin och Eran Tromer

Ur ett modernt perspektiv är detta ett tidigt arbete med praktiska dator-program-till-krets-SAT-transformationer för abstraktion av en virtuell maskin (VM). Bygger på verk från slutet av 1970-talet till 1990-talet (t.ex. arbete av Robson) denna uppsats anger en deterministisk minskning från exekvering av en VM för T-steg till tillfredsställelsen av en krets med storleken O(T*polylog(T)).

Efterföljande uppsatser, t.ex. SNARKs för C och BCTV, fortsatte att utveckla front-ends via en VM-abstraktion, och moderna instansieringar inkluderar projekt som t.ex. Kairo, RISC nolloch Polygon Miden.

Att ta bevisbaserade verifierade beräkningar några steg närmare praktiskt (2012)
av Srinath Setty, Victor Vu, Nikhil Panpalia, Benjamin Braun, Muqeet Ali, Andrew J. Blumberg och Michael Walfish

Detta papper, kallat Ginger, är ett annat tidigt bidrag till praktiska front-end-tekniker. Ginger introducerade prylar för allmänna programmeringsprimitiver som villkor och logiska uttryck, jämförelser och bitvis aritmetik via bitdelning, primitiv flyttalsaritmetik, etc. Den använde dessa prylar för att tillhandahålla den första implementerade front-end från ett högnivåspråk till låggradig aritmetiska begränsningar (liknande vad som nu är känt som R1CS), en mellanrepresentation (IR) på vilken en SNARK-backend kan appliceras.

Medan "Fast Reductions"-papperet och dess ättlingar använder en "CPU-emulator"-metod för att producera IR:er (dvs. IR:n tvingar fram att provaren körde ett visst program korrekt genom att tillämpa processorns övergångsfunktion för ett specificerat antal steg) , Ginger och dess ättlingar tar ett mer ASIC-liknande tillvägagångssätt, och producerar IR:er som är skräddarsydda för det datorprogram som provaren påstår sig köra korrekt.

Till exempel, Buffet visar att det är möjligt att hantera komplexa kontrollflöden i ASIC-modellen, genom att förvandla ett sådant kontrollflöde till en finita-state-maskin anpassad till programmet som körs, och att detta tillvägagångssätt kan vara betydligt effektivare än att bygga en CPU-emulator för allmänt bruk. xJsnark ger en effektiv konstruktion för aritmetik med flera precisioner, optimeringar för RAM och ROM, och exponerar ett Java-liknande högnivåspråk för en programmerare, vilket fortfarande är populärt idag. CirC observerar att kompilering av datorprogram till R1CS är nära relaterat till välkända tekniker från programanalys och bygger en kompilatorkonstruktionsverktygssats som innehåller idéer från båda gemenskaperna ("LLVM för kretsliknande representationer"). Tidigare arbeten som ger bidrag till ASIC-liknande frontends inkluderar Pinocchio och Geppetto.

Tidningen ”Fast-Reductions” använde en komplicerad och dyr konstruktion som kallas ”routing-nätverk” för s.k. minneskontroll (dvs. att säkerställa att den opålitliga provaren korrekt upprätthåller den virtuella datorns slumpmässiga åtkomstminne under exekveringen av den virtuella datorn vars korrekthet bevisas). Detta val gjordes eftersom tidiga verk som detta försökte få en PCP, vilket krävde att front-end båda icke-interaktiva och informationsteoretiskt säkra. Senare ringde arbetet Skafferi (en föregångare till Buffet arbete som nämnts ovan) använde Merkle-träd i stället för routingnätverk, vilket uppnådde effektivitet genom att kompilera en algebraisk (dvs. "SNARK-vänlig") hashfunktion, p.g.a. Ajtai, in i begränsningar. Detta resulterade i "beräkningssäkra" gränssnitt. Idag finns en stor forskningslitteratur om SNARK-vänliga hashfunktioner, med exempel bl.a Poseidon, MiMC, Förstärkt betong, RäddaOch mycket mer.

Toppmoderna tekniker för att säkerställa att provaren upprätthåller RAM korrekt förlitar sig på så kallade "permutation-invariant fingerprinting"-metoder som går tillbaka åtminstone till Lipton (1989) och används för minneskontroll av Blum et al. (1991). Dessa tekniker involverar i sig interaktion mellan en provare och verifierare, men kan göras icke-interaktiva med Fiat-Shamir-transformationen. Såvitt vi känner till introducerades de till litteraturen om praktiska SNARK-gränssnitt genom ett system som heter Vram.

Permutationsinvariant fingeravtryckstekniker används nu i många front-ends och SNARKs för abstraktioner av virtuella maskiner, inklusive t.ex. Kairo. Närbesläktade idéer återkom i besläktade sammanhang i de två verken nedan, som används flitigt i praktiken idag.

Nästan linjär-tid noll-kunskapsbevis för korrekt programexekvering (2018)
av Jonathan Bootle, Andrea Cerulli, Jens Groth, Sune Jakobsen och Mary Maller

Plookup: Ett förenklat polynomprotokoll för uppslagstabeller (2020)
av Ariel Gabizon och Zachary Williamson

Tidiga arbeten på front-ends representerade "icke-aritmetiska" operationer (såsom avståndskontroller, bitvisa operationer och heltalsjämförelser) inuti kretsar och relaterade IR:er genom att bryta fältelement i bitar, utföra operationerna på dessa bitar och sedan "packa" resultatet tillbaka till ett enda fältelement. När det gäller storleken på den resulterande kretsen resulterar detta i en logaritmisk overhead per operation.

Ovanstående två verk (BCGJM och Plookup) ger inflytelserika tekniker (baserade på så kallade "uppslagstabeller") för att mer effektivt representera dessa operationer inuti kretsar, i en amortiserad mening. Grovt sett, för vissa parameter B som valts av front-end-designern, minskar dessa antalet grindar som krävs för att representera varje icke-aritmetisk operation i kretsen med en logaritmisk faktor i B, på bekostnad av att provaren kryptografiskt förbinder sig till en extra "råd" vektor med längd ungefär B.