Nullteadmiste Canon

Toimetaja märkus: a16z krüptol on olnud pikk seeriarelvad”, meie DAO Canon eelmisel aastal meie NFT Canon varem (ja enne seda meie originaal Krüpto Canon) — registreeruge kindlasti meie web3 iganädalane uudiskiri rohkemate värskenduste ja muude kureeritud ressursside jaoks.

Seega below, oleme kogunud ressursse neile, kes soovivad mõista, süveneda ja kõikehõlmavalt ehitada null teadmist: võimsad põhitehnoloogiad, mis hoiavad plokiahela skaleeritavuse võtmeid ning esindavad privaatsust säilitavate rakenduste tulevikku ja lugematuid muid eesolevaid uuendusi. Kui teil on ettepanekuid kvaliteetsete tükkide lisamiseks, andke meile teada @a16zcrypto.

Teadmistevabad süsteemid on olnud kasutusel aastakümneid: Shafi Goldwasseri, Silvio Micali ja Charles Rackoffi kasutuselevõtul 1985. aastal oli krüptograafia valdkonda muutev mõju ning seda tunnustati ACM Turingi auhinnaga, mis omistati Goldwasserile ja Micalile aastal. 2012. Kuna see töö – sealhulgas selle üleminek teoorialt praktikale ja tänapäeval krüpto/web3 rakendustele – on kestnud aastakümneid, jagame esimest korda oma kaanonite sarjas ka teist osa (praegu on see allpool): poolt kommenteeritud lugemisloend Justin Thaler, järgides esimest osa allpool.

Tänuavaldused: Aitäh ka Michael Blaule, Sam Ragsdale'ile ja Tim Roughgardenile.

Vundamendid, taust, evolutsioonid

Mõned neist dokumentidest käsitlevad ka rohkem krüptograafiat üldiselt (mitte kõik nullteadmised iseenesest), sealhulgas kirjeldatakse probleeme või olulisi edusamme, mida tänapäeval käsitletakse nullteadmiste tõenditega: kuidas tagada privaatsus ja autentimine avatud võrkudes.

Uued suunad krüptograafias (1976)
autorid Whitfield Diffie ja Martin Hellman
https://ee.stanford.edu/~hellman/publications/24.pdf

Meetod digitaalallkirjade ja avaliku võtmega krüptosüsteemide saamiseks
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

Avaliku võtmega krüptosüsteemide protokollid (1980)
autor Ralph Merkle
http://www.merkle.com/papers/Protocols.pdf

Turvaline side ebaturvaliste kanalite kaudu (1978)
autor Ralph Merkle
https://www.merkle.com/1974/PuzzlesAsPublished.pdf

Elliptiliste kõverate kasutamine krüptograafias (1988)
autor Victor Miller
https://link.springer.com/content/pdf/10.1007%2F3-540-39799-X_31.pdf

Interaktiivsete tõestussüsteemide teadmiste keerukus (1985)
Shafi Goldwasser, Silvio Micali, Charles Rackof
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.419.8132&rep=rep1&type=pdf

Arvutuslikud helitõendid (2000)
autor Silvio Micali
https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/Computationally_Sound_Proofs.pdf

Alates ekstraheeritavast kokkupõrkekindlusest kuni lühikeste mitteinteraktiivsete teadmiste argumentideni [SNARK-id] ja tagasi (2011)
autor: Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer
https://eprint.iacr.org/2011/443.pdf

Tõhus nullteadmiste argument segamise õigsuse kohta (2012)
Stephanie Bayeri ja Jens Grothi poolt
http://www0.cs.ucl.ac.uk/staff/J.Groth/MinimalShuffle.pdf

Lühike, mitteinteraktiivne nullteadmine von Neumanni arhitektuuri jaoks (2013)
Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer ja Madars Virza
https://eprint.iacr.org/2013/879.pdf

Skaleeritav, läbipaistev ja kvantijärgne turvaline arvutuslik terviklikkus (2018)
Eli Ben-Sasson, Iddo Bentov, Yinon Horesh ja Michael Riabzev
https://eprint.iacr.org/2018/046.pdf

Avaliku mündi nullteadmiste argumendid (peaaegu) minimaalse aja- ja ruumikuluga (2020)
autor: Alexander Block, Justin Holmgren, Alon Rosen, Ron Rothblum ja Pratik Soni
https://www.iacr.org/cryptodb/data/paper.php?pubkey=30645

Ülevaated ja sissejuhatused

Tõestused, argumendid ja nullteadmised — ülevaade kontrollitavatest arvutustest ja interaktiivsetest tõestustest ja argumentidest, krüptoprotokollidest, mis võimaldavad tõestajal anda tõendajale garantii, et tõestaja sooritas nõutud arvutuse õigesti, sealhulgas nullteadmised (kui tõendid ei näita muud teavet peale nende enda kehtivuse) . Zk argumentidel on krüptograafias lugematu arv rakendusi ja need on viimase kümnendi jooksul teinud hüppe teooriast praktikasse.
autor Justin Thaler
https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf

Nullteadmiste tõestuste mudelite areng — nullteadmiste tõendite ülevaade, kus Meiklejohn (Londoni ülikooli kolledž, Google) vaatleb rakendusi, mis nende arengut juhivad, erinevaid mudeleid, mis on tekkinud nende uute interaktsioonide jäädvustamiseks, konstruktsioone, mida me suudame saavutada, ja tööd. jäänud teha.
autor Sarah Meiklejohn
https://www.youtube.com/watch?v=HO97kVMI3SE

ZK tahvli seansid — sissejuhatavad moodulid
koos Dan Boneh jt
https://zkhack.dev/whiteboard/

Turvalisus ja privaatsus zkps-iga krüpto jaoks — teadmiste nullimise tõenduse teerajaja praktikas; mis on zkps ja kuidas need töötavad... sealhulgas live-ees "demo"
autor Zooko Wilcox
https://a16z.com/2019/08/29/security-and-privacy-for-crypto-with-zero-knowledge-proofs/

Tipptehnoloogia teemad, selgitatud — sealhulgas nullteadmiste määratlused ja tagajärjed üldiselt
autor: 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

Kuidas tulevane privaatsuskiht katkise veebi parandab
autor Howard Wu
https://future.com/a-privacy-layer-for-the-web-can-change-everything/

Sissejuhatus zkSNARK-idesse
koos Howard Wu ja Anna Rose'iga
https://zeroknowledge.fm/38-2/

Miks ja kuidas zk-SNARK töötab: lõplik selgitus
autor Maksym Petkus
https://arxiv.org/pdf/1906.07221.pdf

Sissejuhatus nullteadmiste tõestustesse
autor Fredrik Harrysson ja Anna Rose
https://www.zeroknowledge.fm/21 [+ kokkuvõte mujal siin]

Zk-SNARKs: kapoti all
autor Vitalik Buterin
https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
osa 1, osa 2, osa 3

Detsentraliseeritud kiirus — teadmiste puudumise tõendite ja detsentraliseeritud riistvara edusammude kohta
autor Elena Burger
https://a16z.com/2022/04/15/zero-knowledge-proofs-hardware-decentralization-innovation/

Tipptasemel zk-uuringud - koos Ethereumi sihtasutuse zk-teadlasega
koos Mary Malleri, Anna Rose'i, Kobi Gurkaniga
https://zeroknowledge.fm/232-2/

zk-uuringute uurimine — DFINITY teadusdirektoriga; ka Groth16-suguste edusammude taga
koos Jens Grothi, Anna Rose'i, Kobi Gurkaniga
https://zeroknowledge.fm/237-2/

SNARKi teadus- ja pedagoogika - koos ZCashi ja Starkware ühe kaasasutajaga
koos Alessandro Chiesaga, Anna Rose'iga
https://zeroknowledge.fm/episode-200-snark-research-pedagogy-with-alessandro-chiesa/

Sügavsukeldumised, ehitaja juhendid

Tõenäosuslike tõestuste alused — kursus 5 ühikuga interaktiivsetest tõestustest ja muust
autor Alessandro Chiesa
https://www.youtube.com/playlist?list=PLGkwtcB-DfpzST-medFVvrKhinZisfluC

STARKid — I, II, III osa
autor 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

TÄHE anatoomia — kuueosaline õpetus, mis selgitab STARK-i tõestussüsteemi mehaanikat
autor Alan Szepieniec
https://aszepieniec.github.io/stark-anatomy/

SNARKi kujundus, 1. osa — uuring, kasutamine koondfailides jne
autor Justin Thaler
https://www.youtube.com/watch?v=tg6lKPdR_e4

SNARKi kujundus, 2. osa — kokkuvõtted, jõudlus, turvalisus
autor Justin Thaler
https://www.youtube.com/watch?v=cMAI7g3UcoI

SNARKi jõudluse mõõtmine - esiküljed, taustaprogrammid ja palju muud
autor Justin Thaler
https://a16zcrypto.com/measuring-snark-performance-frontends-backends-and-the-future/

PLONKist arusaamine
https://vitalik.ca/general/2019/09/22/plonk.html

PLONK null-teadmiste kindel süsteem — 12 lühikesest videost koosnev sari PLONKi toimimise kohta
autor David Wong
https://www.youtube.com/playlist?list=PLBJMt6zV1c7Gh9Utg-Vng2V6EYVidTFCC

Alates AIR-idest kuni RAP-ideni — kuidas PLONK-stiilis aritmetiseerimine toimib
autor Ariel Gabizon
https://hackmd.io/@aztec-network/plonk-arithmetiization-air

Multiset kontrollib PLONKis ja Plookupis
autor Ariel Gabizon
https://hackmd.io/@arielg/ByFgSDA7D

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

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

Rakendused ja õpetused: kontseptsioonide tõendid, demod, tööriistad ja palju muud

Rakendatud zk — õppevahendid
0xPARC poolt
https://learn.0xparc.org/materials/intro

zkSNARKide veebipõhine arenduskeskkond — zkREPL, uus tööriistade komplekt Sircomi tööriistavirnaga suhtlemiseks brauseris
autor Kevin Kwok
https://zkrepl.dev (+ selgituslõng siin)

Ruutarvulised aritmeetilised programmid nullist kangelaseni
autor Vitalik Buterin
https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

zkEVM-ides
koos Alex Gluchowski ja Anna Rose'iga
https://zeroknowledge.fm/175-2/

Erinevat tüüpi zkEVM-id
autor Vitalik Buterin
https://vitalik.ca/general/2022/08/04/zkevm.html

ZK masinõpe — õpetus ja demo närvivõrgu sisestamiseks SNARKi
Horace Pan, Francis Ho ja Henri Palacci
https://0xparc.org/blog/zk-mnist

ZK keeltes
koos Alex Ozdemiri ja Anna Rose'iga
https://zeroknowledge.fm/172-2/

Dark Forest — zk-krüptograafia rakendamine mängudele — täielikult detsentraliseeritud ja püsiv RTS (reaalajas strateegia) mäng
https://blog.zkga.me/announcing-darkforest

ZKP-d inseneridele - pilk Dark Foresti ZKP-dele
https://blog.zkga.me/df-init-circuit

Sukeldumine nullteadmistesse
koos Elena Nadolinkski, Anna Rose, James Prestwichiga
https://zeroknowledge.fm/182-2/

zkDocs: nullteadmisteta teabe jagamine
autor Sam Ragsdale ja Dan Boneh
https://a16zcrypto.com/zkdocs-zero-knowledge-information-sharing/

Privaatsust kaitsvad krüpto-airdrops nullteadmiste tõestusega
autor Sam Ragsdale
https://a16z.com/2022/03/27/crypto-airdrop-privacy-tool-zero-knowledge-proofs/

Ketisisesed usaldusväärsed seadistamistseremooniad -
Valeria Nikolaenko ja Sam Ragsdale
https://a16zcrypto.com/on-chain-trusted-setup-ceremony/

Krüptoeeskirjad, ebaseaduslik rahastamine, privaatsus ja muu – sisaldab jaotist nullteadmiste kohta regulatiivses/ vastavuse kontekstis; erinevus "privaatsust säilitavate" ja segavate tehnoloogiate vahel
koos Michele Korveri, Jai Ramaswamy, Sonal Chokshiga
https://web3-with-a16z.simplecast.com/episodes/crypto-regulations-sanctions-compliance-aml-ofac-news-explained

Muud ressursid

zkMeshi uudiskiri — igakuine uudiskiri, mis jagab uusimaid detsentraliseeritud privaatsust säilitavaid tehnoloogiaid, privaatsusprotokolli arendamist ja nullteadmissüsteeme
https://zkmesh.substack.com/

Zero Knowledge podcast - uusimate zk-uuringute ja zk-rakenduste ning krüptograafia toega privaatsustehnoloogia loomise ekspertide kohta
koos Anna Rose'iga
https://zeroknowledge.fm/

… kommenteeritud lugemisloend teemade ja kronoloogia järgi, autor Justin Thaler:

SNARK-id lineaarsetest PCP-dest (teise nimega SNARK-id vooluringipõhise seadistusega)

Tõhusad argumendid ilma lühikeste PCP-deta (2007)
Yuval Ishai, Eyal Kushilevitzi ja Rafail Ostrovski poolt

Enne umbes 2007. aastat kavandati SNARK-id peamiselt Kilian-micali paradigma, võtta "lühike" tõenäosuslikult kontrollitav tõend (PCP) ja "krüptograafiliselt kompileerida" see lakooniliseks argumendiks Merkle'i räsimise ja Fiat-Shamiri teisenduse kaudu. Kahjuks on lühikesed PCP-d keerulised ja ebapraktilised isegi tänapäeval. See artikkel (IKO) näitas, kuidas kasutada homomorfset krüptimist, et saada lühikesi (mitteläbipaistvaid) interaktiivseid argumente "pikkadest, kuid struktureeritud" PCP-dest. Need võivad olla palju lihtsamad kui lühikesed PCP-d ja saadud SNARK-idel on palju lühemad tõendid ja kiirem kontrollimine. Neid argumente tunnistati esmalt kui praktilise tõhususe potentsiaali ning neid viimistleti ja rakendati aastal Pipar. Kahjuks on IKO argumentidel ruutajaline tõend ja ruutsuuruses struktureeritud viitestring, mistõttu need ei skaleeri suurteks arvutusteks.

Ruutvahemiku programmid ja sisutihedad NIZK-id ilma PCP-deta (2012)
Rosario Gennaro, Craig Gentry, Bryan Parno ja Mariana Raykova

See läbimurdepaber (GGPR) vähendas IKO lähenemisviisi tõendamiskulusid vooluringi ruutkeskmiselt kvaasilineaarsele. Toetudes varasemale tööle Groth ja Lipmaa, andis see ka SNARK-id sidumispõhise krüptograafia kaudu, mitte interaktiivsete argumentide kaudu, nagu IKO puhul. See kirjeldas oma SNARK-e kontekstis, mida praegu nimetatakse 1. järgu piiranguga rahulolu (R1CS) probleemideks, mis on aritmeetilise vooluahela rahuldavuse üldistus.

See artikkel oli ka teoreetiline alus esimestele SNARKidele, mis nägid kaubanduslikku kasutuselevõttu (nt ZCashis) ja tõid kaasa SNARK-id, mis on endiselt populaarsed (nt Groth16). GGPR-i argumentide esialgsed juurutused tulid sisse Zaatar ja Pinocchioja hilisemad variandid hõlmavad SNARKid C jaoks ja BCTV. BCIOP andis üldise raamistiku, mis selgitab neid lineaarseid PCP-dest SNARK-i teisendusi (vt ka lisa A Zaatar) ja kirjeldab selle erinevaid eksemplare.

Sidumisel põhinevate mitteinteraktiivsete argumentide suurusest (2016)
autor Jens Groth

See artikkel, mida kõnekeeles nimetatakse Groth16, tutvustas GGPR-i SNARK-ide täpsustust, mis saavutab ka tänapäeval tipptasemel betooni kontrollimise kulud (tõestused on 3 rühmaelementi ja kontrollimisel domineerivad kolm sidumistoimingut, vähemalt eeldades, et avalikkus sisend on lühike). Turvalisus on tõestatud üldise rühmamudeliga.

Universaalse usaldusväärse seadistusega SNARK-id

PlonK: Lagrange'i aluste permutatsioonid oikumeeniliste mitteinteraktiivsete teadmiste argumentide jaoks (2019)
Ariel Gabizon, Zachary Williamson ja Oana Ciobotaru

Marlin: zkSNARKide eeltöötlemine universaalse ja värskendatava SRS-iga (2019)
autorid Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely ja Nicholas Ward

Nii PlonK kui ka Marlin asendavad Groth16 vooluringipõhise usaldusväärse seadistuse universaalse seadistusega. See tuleb 4x-6x suuremate tõendite arvelt. Võib mõelda, et PlonK ja Marlin võtavad Groth16 ja eelkäijate usaldusväärse seadistamise ajal vooluringipõhise töö ning viivad selle eeltöötlusfaasi, mis juhtub. pärast usaldusväärse seadistuse, aga ka SNARKi tõendi genereerimise ajal.

Suvaliste vooluahelate ja R1CS-süsteemide sellisel viisil töötlemise võimalust nimetatakse mõnikord holograafiaks või arvutuskohustusteks ning seda kirjeldati ka artiklis Spartan (seda käsitletakse käesolevas kogumikus hiljem). Kuna tõendi genereerimisel tehakse rohkem tööd, on PlonK ja Marlini proovid antud vooluringi või R16CS eksemplari puhul aeglasemad kui Groth1. Kuid erinevalt Groth16-st saab PlonK-i ja Marlini panna töötama üldisemate vaheesitlustega kui R1CS.

Polünoomsete kohustuste skeemid, SNARKide peamine krüptograafiline primitiiv

Konstantse suurusega kohustused polünoomidele ja nende rakendustele (2010)
Aniket Kate, Gregory Zaverucha ja Ian Goldberg

Selles artiklis tutvustati polünoomsete kohustuste skeemide mõistet. See andis skeemi ühemõõtmeliste polünoomide jaoks (tavaliselt nimetatakse KZG kohustusteks) konstantse suurusega kohustuste ja hindamistõestustega. Skeem kasutab usaldusväärset seadistust (st struktureeritud viitestringi) ja sidumispõhist krüptograafiat. See on tänapäeval praktikas äärmiselt populaarne ja seda kasutatakse SNARK-ides, sealhulgas ülalpool käsitletud PlonK ja Marlin (ja Groth16 kasutab väga sarnaseid krüptotehnikaid).

Kiired Reed-Solomoni interaktiivsed Oracle'i läheduse tõendid (2017)
Eli Ben-Sasson, Iddo Bentov, Ynon Horesh, Michael Riabzev

Annab interaktiivse oraakli tõendi (IOP) Reed-Solomoni testimiseks, st tõestab, et määratud string on ühemõõtmelise polünoomi hindamistabeli lähedal. Kombineerituna Merkle'i räsimise ja Fiat-Shamiri teisendusega annab see läbipaistva polünoomilise kohustuste skeemi polülogaritmilise suurusega hindamistõestustega (vt VP19 üksikasjade saamiseks). Täna on see usutavalt post-kvantpolünoomilise kohustuse skeemide seas lühim.

Ligero: kerged sublineaarsed argumendid ilma usaldusväärse seadistuseta (2017)
Scott Ames, Carmit Hazay, Yuval Ishai ja Muthuramakrishnan Venkitasubramaniam

Sarnaselt FRI-ga annab see töö Reed-Solomoni testimiseks silmasisese rõhu, kuid pigem ruutjuure pikkusega kui polülogaritmiliselt. Teoreetiline töötab näitas, et kui vahetada Reed-Solomoni kood välja teistsuguse veaparanduskoodi vastu, millel on kiirem kodeering, on võimalik saada lineaarajaline tõestus, mis pealegi töötab natiivselt mis tahes väljal. Seda lähenemisviisi on täiustatud ja rakendatud aastal Pidurdamine ja Orion, mis annab tipptasemel tõestamisjõudluse.

Kuulikindlad: lühikesed tõendid konfidentsiaalsete tehingute ja muu kohta (2017)
autor Benedikt Bunz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille ja Greg Maxwell

Eelneva töö viimistlemine BCCGP, Bulletproofs annab läbipaistva polünoomilise kohustuse skeemi (tegelikult üldistuse, mida nimetatakse sisemise korrutise argumendiks), mis põhineb diskreetsete logaritmide arvutamise keerukusel logaritmilise tõendi suuruse, kuid lineaarse kontrollimisajaga. Skeem on tänapäeval populaarne tänu oma läbipaistvusele ja lühikestele tõestustele (nt seda kasutatakse ZCash Orchardis ja Moneros).

Dory: tõhusad, läbipaistvad argumendid üldiste sisemiste toodete ja polünoomiliste kohustuste kohta (2020)
autor Jonathan Lee

Dory vähendab kuulikindlates kontrollimisaega lineaarselt logaritmiliseks, säilitades samal ajal läbipaistvuse ja logaritmilise suurusega tõestused (kuigi konkreetselt suuremad kui kuulikindlad) ja läbipaistvuse. Kasutab sidumisi ja põhineb SXDH eeldusel.

Interaktiivsed tõendid, mitme prooviga interaktiivsed tõendid ja nendega seotud SNARK-id

Arvutamise delegeerimine: interaktiivsed tõendid muggide jaoks (2008)
Shafi Goldwasser, Yael Tauman Kalai ja Guy Rothblum

Enne seda artiklit oli üldotstarbeliste interaktiivsete tõestuste jaoks vaja a superpolünoom-aeg tõend. See artikkel annab interaktiivse tõestusprotokolli, mida tavaliselt nimetatakse GKR-protokolliks, polünoomilise aja tõestaja ja kvaasilineaarse ajatõendiga iga probleemi jaoks, millel on tõhus paralleelalgoritm (samaväärselt kehtib interaktiivne tõestus iga väikese sügavusega aritmeetilise ahela kohta).

Praktiline kontrollitud arvutus koos voogesituse interaktiivsete tõestustega (2011)
Graham Cormode, Michael Mitzenmacher, Justin Thaler

See paber (mõnikord nimetatakse seda ka CMT-ks) vähendas GKR-protokolli proovimisaega vooluringi suuruselt kvartilisest kvaasilineaarseks. Tekitas esimese üldotstarbelise interaktiivse tõestuse teostuse. Rida järgnevaid töid (Lõhnamaitse, Taaler13, kaelkirjakja Kaalud) vähendas tõestaja tööaega veelgi, kvaasilineaarselt lineaarsele vooluringi suuruses.

vSQL: suvaliste SQL-päringute kontrollimine dünaamiliste sisseostetud andmebaaside kaudu (2017)
Yupeng Zhang, Daniel Genkin, Jonathan Katz, Dimitrios Papadopoulos ja Charalampos Papamanthou

Kuigi pealkiri viitab konkreetsele rakendusvaldkonnale (andmebaasidele), on selle töö panused üldisemad. Täpsemalt täheldas see, et vooluringi rahuldavuse kohta on võimalik saada lühikesi argumente, kombineerides interaktiivseid tõestusi polünoomiliste kohustuste skeemidega (mitmelineaarsete polünoomide jaoks).

pärast töötab sulatatud argumendid null-teadmised ja tutvustasid mitmelineaarsete polünoomide jaoks erinevaid kohustusskeeme.

Spartan: tõhusad ja üldotstarbelised zkSNARK-id ilma usaldusväärse seadistuseta (2019)
autor Srinath Setty

Hangib SNARK-id vooluringide rahuldavuse ja R1CS-i jaoks, kombineerides multi-prover interaktiivseid tõestusi (MIP) polünoomsete kohustuste skeemidega, tuginedes varasemale tööle konkreetselt tõhusate MIP-ide kallal, mida nimetatakse Ristikhein. Tulemuseks on lühemate tõestustega SNARK-ide saamine kui need, mis on saadud interaktiivsetest tõestustest, nagu ülalpool käsitletud GKR-protokoll. Sarnaselt PlonK-i ja Marliniga näitab Spartan ka, kuidas töödelda suvalisi vooluahelaid ja R1CS-süsteeme eeltöötluse ja SNARK-i tõestuse genereerimise kaudu.

Spartan kasutas polünoomilist kohustuste skeemi alates hyrax. Järgnevad tööd nn Pidurdamine ja Orion kombineerige Spartani MIP teiste polünoomiliste kohustuste skeemidega, et saada esimesed rakendatud SNARK-id koos lineaarse aja tõestajaga.

Lühikesed PCP-d ja IOP-d

Lühikesed PCP-d polülogipäringu keerukusega (2005)
Eli Ben-Sasson ja Madhu Sudan

 See teoreetiline töö andis esimese tõenäosuslikult kontrollitava tõestuse (PCP), mille tõestuse pikkus oli kvaasilineaarne kontrollitava arvutuse suuruse ja polülogaritmilise päringu maksumuse (kuigi lineaarse kontrollimise aja) poolest. Pärast PCP-de Kilian-Micali muutmist SNARK-ideks oli see samm kvaasilineaarse ajaproovi ja polülogaritmilise aja verifitseerijaga SNARK-ide poole.

Hilisem teoreetiline töö vähendas kontrollija aega polülogaritmiliseks. Järgnevad praktiliselt keskendunud töö täiustas seda lähenemisviisi, kuid lühikesed PCP-d on tänapäeval ebapraktilised. Praktiliste SNARKide saamiseks pärast töötab pööratud et nimega PCP-de interaktiivne üldistus Interaktiivsed Oracle'i tõendid (IOP-id). Need jõupingutused viisid ja jätkasid TASUTA, populaarne polünoomikohustuste skeem, mida käsitletakse selle kogumiku polünoomikohustuste osas.

Sellesse kategooriasse kuuluvad muud tööd ZKBoo ja selle järglased. Need ei anna täpseid tõestusi, kuid neil on head konstantsed tegurid ja seetõttu on need atraktiivsed väikeste väidete tõestamiseks. Need on viinud kvantijärgsete signatuuride perekondadeni, näiteks Piknik mis on olnud optimeeritud in mitu töötab. ZKBoo esitletakse erineva disainiparadigma järgi MPC-in-the-head, kuid see annab silmasisese rõhu.

Rekursiivsed SNARK-id

Järk-järgult kontrollitav arvutus või teadmiste tõendid viitavad aja-/ruumitõhususele (2008)
autor Paul Valiant

See töö tutvustas astmeliselt kontrollitava arvutuse (IVC) põhimõistet, mille puhul tõestaja teostab arvutuse ja säilitab kogu aeg tõendi, et senine arvutus on olnud õige. See konstrueeris IVC SNARKide rekursiivse koostise kaudu. Siin, teadmised-põhjalikkus SNARKide omadus on oluline rekursiivselt koostatud mitteinteraktiivsete argumentide usaldusväärsuse kindlakstegemiseks. See artikkel andis ka äärmiselt tõhusa teadmiste ammutaja PCP-st tuletatud SNARKide jaoks (vastavalt Kilian-Micali paradigmale).

Skaleeritavad nullteadmised elliptiliste kõverate tsüklite kaudu (2014)
Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer ja Madars Virza

Järel teoreetiline töö, kasutati selles artiklis GGPR-i SNARK-i variandi rekursiivset rakendust, et pakkuda IVC esimest rakendust lihtsa virtuaalse masina jaoks (TinyRAM, alates SNARKid C jaoks paber).

Samuti tutvustati elliptiliste kõverate tsüklite mõistet, mis on kasulikud SNARKide rekursiivseks koostamiseks, mis kasutavad elliptilise kõvera krüptograafiat.

Rekursiivne tõestuskompositsioon ilma usaldusväärse seadistuseta (2019)
Sean Bowe, Jack Grigg ja Daira Hopwood

See töö (nn Halo) uurib, kuidas rekursiivselt koostada läbipaistvaid SNARK-e. See on keerulisem kui läbipaistmatute koostamine, kuna läbipaistvate SNARK-ide kontrolliprotseduur võib olla palju kulukam.

See tekitas siis a rida of töö mis on kulmineerunud selliste süsteemidega nagu Uus saavutades tipptasemel IVC jõudluse, mis on isegi parem kui läbipaistmatute SNARK-ide, nagu Groth16, koostamisel.

Rakendused

Zerocash: detsentraliseeritud anonüümsed maksed Bitcoinilt (2014)
autorid Eli Ben Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, Madars Virza

Tuginedes eelnevale tööle sh Nullmünt (ja koos Pinnochio münt samaaegse tööna), kasutatakse selles artiklis GGPR-st tuletatud SNARK-e privaatse krüptovaluuta kujundamiseks. Viinud ZCashini.

Geppetto: mitmekülgne kontrollitav arvutus (2014)
autorid Craig Costello, Cédric Fournet, Jon Howell, Markulf Kohlweiss, Benjamin Kreuter, Michael Naehrig, Bryan Parno ja Samee Zahur

Geppetto pärineb väidetavalt enne kui plahvatuslikult kasvas huvi eraviisiliste nutikate lepingute täitmise vastu, kuna see on kirjutatud umbes aasta pärast Ethereumi loomist. Seetõttu ei esitata seda nutikate eralepingute täitmise kontekstis. Siiski kasutab see SNARK-ide piiratud sügavuse rekursiooni, et lubada ebausaldusväärsel tõestajal käivitada privaatsete (kohustuslike/allkirjastatud) arvutiprogrammide privaatandmetel, ilma et see avaldaks teavet käitatava programmi või andmete kohta, millel see töötab. Sellest tulenevalt on see privaatsete nutikate lepingute platvormidel tehtud töö eelkäija, näiteks Zexe [kirjeldatud allpool].

Kontrollitavad ASIC-id (2015)
autor: Riad Wahby, Max Howald, Siddharth Garg, abhi shelat, Michael Walfish

Käesolevas artiklis käsitletakse probleemi, kuidas ohutult ja viljakalt kasutada ebausaldusväärses valukojas toodetud ASIC-i (2015. aastal oli tipptasemel valukojaga vaid viis riiki). Lähenemisviis on lasta kiirel, kuid ebausaldusväärsel ASIC-il tõestada oma väljundi õigsust kontrollijale, mis töötab aeglasema, kuid usaldusväärse ASIC-iga. Lahendus on huvitav seni, kuni süsteemi kogu täitmisaeg (st tõestaja ja kontrollija käitusaegade summa pluss võimalikud andmeedastuskulud) on väiksem kui naiivne baasjoon: aeg, mis kulub arvutuse täielikuks käivitamiseks aeglasemas süsteemis. -aga-usaldusväärne ASIC. Kasutades GKR/CMT/Allspice interaktiivsete tõestuste varianti, ületab paber tõepoolest naiivse lähtejoone mitmete põhiprobleemide puhul, sealhulgas arvuteoreetilised teisendused, mustrite sobitamine ja elliptilise kõvera operatsioonid. See töö viitab sellele, et mõned tõestussüsteemid sobivad riistvara juurutamiseks paremini kui teised. Tõestussüsteemide optimeerimine riistvara juurutamiseks on nüüd vastu võetud märkimisväärne tähelepanu, kuid palju on veel uurida.

Kontrollitav Viivitusfunktsioonid (2018)
autor: Dan Boneh, Joseph Bonneau, Benedikt Bünz ja Ben Fisch

Võttis kasutusele kontrollitavate viivitusfunktsioonide (VDF) tähistused, krüptograafiline primitiiv, mis on laialdaselt kasulik plokiahela rakendustes, nt panuse tõestamise konsensusprotokollide võimaliku manipuleerimise leevendamiseks. SNARK-id (eriti astmeliselt kontrollitava arvutuse jaoks) pakuvad teed tipptasemel VDF-idele.

Zexe: detsentraliseeritud privaatarvutuse lubamine (2018)
Sean Bowe, Alessandro Chiesa, Matthew Green, Ian Miers, Pratyush Mishra ja Howard Wu

Zexe on privaatse nutika lepingu platvormi disain. Zexet saab vaadata Zerocashi laiendusena (kirjeldatud ülal). Zerocash võimaldab ühe rakenduse ahelas käitamist (võimaldab kasutajatel žetoone üle kanda), kaitstes samal ajal kasutajaandmete privaatsust, nt kellele nad žetoone saadavad, kellelt žetoone saavad, ülekantud žetoonide kogust jne. Zexe võimaldab paljusid erinevad rakendused (nutilepingud), mis töötavad samas plokiahelas ja suhtlevad üksteisega. Tehingud sooritatakse väljaspool ahelat ja tõendid korrektse täitmise kohta postitatakse ahelasse. Kaitstud pole mitte ainult andmete privaatsus, vaid ka funktsioonide privaatsus. See tähendab, et iga tehinguga seotud tõend ei näita isegi seda, millist rakendust (rakendusi) tehing puudutab. Zexe üldisem tehniline panus on see, et see tutvustas BLS12-377, elliptilise kõvera rühma, mis on kasulik sidumispõhiste SNARK-ide tõhusaks sügavus-1 koostiseks.

Paljundatud olekumasinad ilma kopeeritud täitmiseta (2020)
Jonathan Lee, Kirill Nikitin ja Srinath Setty

See on üks väheseid akadeemilisi töid plokiahela skaleeritavuse koondamise kohta. Selles ei kasutata terminit rollups, kuna see pärineb väljaspool akadeemilist kirjandust kasutusele võetud mõistet või on sellega samaaegne.

Esiotsad (tõhusad teisendused arvutiprogrammidest vaheesitusteks, nagu vooluringi rahuldavus, R1CS ja palju muud)

Kiire vähendamine RAM-idelt delegeeritavate lühikeste piirangutega rahuloluprobleemideni (2012)
Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin ja Eran Tromer

Kaasaegsest vaatenurgast on see virtuaalmasina (VM) abstraktsiooni jaoks mõeldud praktiliste arvutiprogrammide ja SAT-i teisenduste varajane töö. Toetudes 1970. aastate lõpust kuni 1990. aastateni tehtud töödele (nt Robson) selles artiklis kirjeldatakse deterministlikku taandamist VM-i täitmisest T-sammude jaoks kuni O(T*polylog(T)-suurusega vooluringi rahuldamiseni).

Järgnevad paberid, nt. SNARKid C jaoks ja BCTV, jätkas kasutajaliideste arendamist VM-i abstraktsiooni kaudu ja kaasaegsed instantseeringud hõlmavad selliseid projekte nagu Kairo, RISC nullja Hulknurk Miden.

Tõestuspõhise kontrollitud arvutuse viimine praktilisusele paar sammu lähemale (2012)
Srinath Setty, Victor Vu, Nikhil Panpalia, Benjamin Braun, Muqeet Ali, Andrew J. Blumberg ja Michael Walfish

See paber, millele viidatakse kui Ginger, on veel üks varajane panus praktilistesse esiotsa tehnikatesse. Ginger tutvustas vidinaid üldiste programmeerimisprimitiivide jaoks, nagu tingimuslikud ja loogilised avaldised, võrdlused ja bitipõhise aritmeetika bittide jagamise, primitiivse ujukomaaritmeetika jne abil. Ta kasutas neid vidinaid, et pakkuda esimest rakendust kõrgetasemelisest keelest madala astmeni. aritmeetilised piirangud (sarnaselt R1CS-ile), vaheesitus (IR), millele saab rakendada SNARK-i tausta.

Arvestades, et paber "Kiired vähendamised" ja selle järeltulijad kasutavad IR-de loomisel "CPU-emulaatori" lähenemisviisi (st IR tagab, et tõestaja käivitas konkreetse programmi õigesti, rakendades CPU üleminekufunktsiooni teatud arvu etappide jaoks) , Ginger ja tema järeltulijad kasutavad rohkem ASIC-laadset lähenemist, luues IR-sid, mis on kohandatud arvutiprogrammile, mida tõestaja väidetavalt õigesti käivitab.

Näiteks Einelaud näitab, et ASIC-mudelis on võimalik käsitleda keerulist juhtimisvoogu, muutes sellise juhtimisvoo lõpliku olekuga masinaks, mis on kohandatud käivitatava programmi jaoks, ja et see lähenemisviis võib olla oluliselt tõhusam kui üldotstarbelise protsessori emulaatori ehitamine. xJsnark annab tõhusa konstruktsiooni mitme täpsusega aritmeetika jaoks, optimeerib RAM-i ja ROM-i ning paljastab Java-laadse kõrgtasemelise keele programmeerijale, mis on tänapäeval endiselt populaarne. CirC märgib, et arvutiprogrammide kompileerimine R1CS-i on tihedalt seotud programmianalüüsist hästi tuntud tehnikatega ja loob kompilaatori ehitustööriistakomplekti, mis sisaldab mõlema kogukonna ideid (“LLVM vooluringilaadsete esituste jaoks”). Varasemad tööd, mis on panustanud ASIC-stiilis esiotsadesse, hõlmavad ka Pinocchio ja geppetto.

“Fast-Reductions” paberil kasutati keerulist ja kallist konstruktsiooni, mida nimetatakse “marsruutimisvõrkudeks” nn. mälu kontrollimine (st tagades, et ebausaldusväärne tõestaja säilitab VM-i muutmälu õigesti kogu selle VM-i käitamise ajal, mille õigsust kontrollitakse). See valik tehti seetõttu, et varased tööd, nagu see, soovisid saada PCP-d, mis nõudis esiotsa mõlemad mitteinteraktiivne ja infoteoreetiliselt turvaline. Hiljem töö kutsus Pahtlane ( eelkäija Einelaud eespool mainitud töö) kasutas marsruutimisvõrkude asemel Merkle-puid, saavutades tõhususe algebralise (st "SNARK-sõbraliku") räsifunktsiooni kompileerimisega, kuna Ajtai, piirangutesse. Selle tulemuseks olid "arvutuslikult turvalised" esiotsad. Tänapäeval on SNARK-sõbralike räsifunktsioonide kohta palju uurimiskirjandust, sealhulgas näiteid Poseidon, MiMC, Raudbetoonist, PäästmaJa palju muud.

Kaasaegsed tehnikad, mis tagavad, et tõestaja säilitab RAM-i õigesti, tuginevad nn permutatsiooniinvariantsete sõrmejälgede võtmise meetoditele, mis pärinevad vähemalt aastast Liptoni (1989) ja kasutas mälu kontrollimiseks Blum et al. (1991). Need tehnikad hõlmavad oma olemuselt tõestaja ja kontrollija vahelist koostoimet, kuid neid saab Fiat-Shamiri teisendusega muuta mitteinteraktiivseks. Meile teadaolevalt tutvustas neile praktilisi SNARK-liideseid käsitlevat kirjandust süsteem nn. vRAM.

Permutatsiooniga muutumatuid sõrmejälgede võtmise tehnikaid kasutatakse nüüd paljudes esiotsades ja SNARK-ides virtuaalse masina abstraktsioonide jaoks, sealhulgas näiteks Kairo. Tihedalt seotud ideed ilmusid seotud kontekstides uuesti kahes alltoodud teoses, mida tänapäeval praktikas laialdaselt kasutatakse.

Peaaegu lineaarse aja nullteadmiste tõendid programmi õigeks täitmiseks (2018)
Jonathan Bootle, Andrea Cerulli, Jens Groth, Sune Jakobsen ja Mary Maller

Plookup: lihtsustatud polünoomiprotokoll otsingutabelite jaoks (2020)
Ariel Gabizon ja Zachary Williamson

Varasemad tööd esiotsadega kujutasid endast "mittearitmeetilisi" toiminguid (nagu vahemiku kontrollimine, bitipõhised toimingud ja täisarvude võrdlused) ahelates ja nendega seotud IR-des, jagades väljaelemendid bittideks, sooritades nende bittidega toiminguid ja seejärel "pakkides". tulemus tagasi üheks väljaelemendiks. Saadud vooluringi suurust silmas pidades annab see logaritmilise üldkulu operatsiooni kohta.

Kaks ülaltoodud tööd (BCGJM ja Plookup) annavad mõjukaid tehnikaid (nn. otsingutabelitel põhinevad) nende toimingute efektiivsemaks esitamiseks vooluringides, amortiseerunud tähenduses. Jämedalt öeldes vähendavad need mõne esiotsa disaineri valitud parameetri B puhul lülituste arvu, mis on vajalik iga mittearitmeetilise operatsiooni esitamiseks ahelas B-s oleva logaritmilise teguri võrra, kusjuures tõestaja võtab krüptograafiliselt kohustuse teha lisatasu. “nõu” vektor pikkusega ligikaudu B.