Nolla tietämystä Canon

Toimittajan huomautus: a16z kryptolla on ollut pitkä sarja "aseet", meiltä DAO Canon viime vuonna meidän NFT Canon aikaisemmin (ja ennen sitä meidän alkuperäinen Crypto Canon) — muista rekisteröityä palveluumme web3 viikoittainen uutiskirje saadaksesi lisää päivityksiä sekä muita kuratoituja resursseja.

Joten below, olemme keränneet joukon resursseja niille, jotka haluavat ymmärtää, mennä syvemmälle ja rakentaa kaiken kanssa nolla tietoa: tehokkaat, perustavanlaatuiset tekniikat, joissa on avaimet lohkoketjun skaalautumiseen ja jotka edustavat yksityisyyttä suojelevien sovellusten tulevaisuutta ja lukemattomia muita tulevia innovaatioita. Jos sinulla on ehdotuksia laadukkaiksi lisättäviksi kappaleiksi, ota meihin yhteyttä @a16zcrypto.

Nollatietojärjestelmät ovat olleet olemassa jo vuosikymmeniä: Shafi Goldwasserin, Silvio Micalin ja Charles Rackoffin vuonna 1985 käyttöönotolla niiden käyttöönotolla oli muuttava vaikutus kryptografian alalla, ja se tunnustettiin Goldwasserille ja Micalille vuonna XNUMX myönnetystä ACM Turing -palkinnosta. 2012. Koska tämä työ – mukaan lukien sen siirtyminen teoriasta käytäntöön ja sovellukset krypto/web3:ssa tänään – on ollut vuosikymmeniä tekeillä, jaamme myös ensimmäistä kertaa canons-sarjassamme toisen osan (toistaiseksi, tässä alla): lukulista, johon on merkitty Justin Thaler, seuraavan osan jälkeen.

Kiitokset: Kiitos myös Michael Blaulle, Sam Ragsdalelle ja Tim Roughgardenille.

Perusteet, tausta, evoluutio

Jotkut näistä kirjoituksista koskevat myös enemmän kryptografiaa yleisesti (ei kaikki nollatietoa sinänsä), mukaan lukien hahmotellaan ongelmia tai keskeisiä edistysaskeleita, joita käsitellään nykyään nollatiedontodistuksilla: kuinka varmistetaan yksityisyys ja todennus avoimissa verkoissa.

Uudet suunnat kryptografiassa (1976)
Whitfield Diffie ja Martin Hellman
https://ee.stanford.edu/~hellman/publications/24.pdf

Menetelmä digitaalisten allekirjoitusten ja julkisen avaimen salausjärjestelmien hankkimiseksi
kirjoittaneet 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

Protokollat ​​julkisen avaimen salausjärjestelmille (1980)
Kirjailija: Ralph Merkle
http://www.merkle.com/papers/Protocols.pdf

Suojattu viestintä turvattomilla kanavilla (1978)
Kirjailija: Ralph Merkle
https://www.merkle.com/1974/PuzzlesAsPublished.pdf

Elliptisten käyrien käyttö kryptografiassa (1988)
kirjoittanut Victor Miller
https://link.springer.com/content/pdf/10.1007%2F3-540-39799-X_31.pdf

Interaktiivisten todistusjärjestelmien tiedon monimutkaisuus (1985)
Shafi Goldwasser, Silvio Micali, Charles Rackof
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.419.8132&rep=rep1&type=pdf

Laskennalliset äänieristykset (2000)
Kirjailija: Silvio Micali
https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/Computationally_Sound_Proofs.pdf

Poimittavasta törmäyskestävyydestä ytimekkäisiin ei-interaktiivisiin tiedon argumentteihin [SNARK] ja takaisin (2011)
Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer
https://eprint.iacr.org/2011/443.pdf

Tehokas nolla-tietoargumentti sekoituksen oikeellisuudesta (2012)
Stephanie Bayer ja Jens Groth
http://www0.cs.ucl.ac.uk/staff/J.Groth/MinimalShuffle.pdf

Lyhyt, ei-interaktiivinen nollatieto von Neumann-arkkitehtuurille (2013)
Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer ja Madars Virza
https://eprint.iacr.org/2013/879.pdf

Skaalautuva, läpinäkyvä ja kvanttiturvallinen laskennallinen eheys (2018)
Eli Ben-Sasson, Iddo Bentov, Yinon Horesh ja Michael Riabzev
https://eprint.iacr.org/2018/046.pdf

Julkiset kolikon nollatietoargumentit (melkein) minimaalisilla aika- ja tilakuluilla (2020)
kirjoittaneet Alexander Block, Justin Holmgren, Alon Rosen, Ron Rothblum ja Pratik Soni
https://www.iacr.org/cryptodb/data/paper.php?pubkey=30645

Yleiskatsaukset ja esittelyt

Todistuksia, argumentteja ja nollatietoa — Yleiskatsaus todennettavissa olevista laskennoista ja vuorovaikutteisista todisteista ja argumenteista, kryptografisista protokollista, joiden avulla todistaja voi taata todentajalle, että todistaja suoritti pyydetyn laskennan oikein, mukaan lukien nollatieto (jos todisteet eivät paljasta muuta tietoa kuin niiden oma pätevyys) . Zk-argumenteilla on lukemattomia sovelluksia kryptografiassa, ja ne ovat hypänneet teoriasta käytäntöön viimeisen vuosikymmenen aikana.
Kirjailija: Justin Thaler
https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf

Nollatietotodisteiden mallien kehitys — Nollatietotodisteiden katsaus, jossa Meiklejohn (University College London, Google) tarkastelee sovelluksia, jotka ohjaavat niiden kehitystä, erilaisia ​​malleja, joita on syntynyt näiden uusien vuorovaikutusten vangitsemiseksi, rakennuksia, joita voimme saavuttaa, ja työtä jäänyt tekemään.
Kirjailija: Sarah Meiklejohn
https://www.youtube.com/watch?v=HO97kVMI3SE

ZK valkotaulun istunnot — johdantomoduulit
Dan Boneh et ai
https://zkhack.dev/whiteboard/

Suojaus ja yksityisyys salaukselle zkps:n kanssa — nolla tietämyksen pioneeri käytännössä; mitä zkps ovat ja miten ne toimivat… mukaan lukien live-vaiheen "demo"
Kirjailija: Zooko Wilcox
https://a16z.com/2019/08/29/security-and-privacy-for-crypto-with-zero-knowledge-proofs/

Huipputekniikan aiheet, selitetty — mukaan lukien nollatiedon määritelmät ja vaikutukset yleisesti
Kirjailija: 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

Kuinka tuleva tietosuojakerros korjaa rikkinäisen verkon
Kirjailija: Howard Wu
https://future.com/a-privacy-layer-for-the-web-can-change-everything/

Johdatus zkSNARKeihin
Howard Wun ja Anna Rosen kanssa
https://zeroknowledge.fm/38-2/

Miksi ja miten zk-SNARK toimii: lopullinen selitys
Kirjailija: Maksym Petkus
https://arxiv.org/pdf/1906.07221.pdf

Johdatus nollatietotodistuksiin
Fredrik Harrysson ja Anna Rose
https://www.zeroknowledge.fm/21 [+ yhteenveto muualla tätä]

Zk-SNARKit: konepellin alla
Kirjailija: Vitalik Buterin
https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
osa 1, osa 2, osa 3

Hajautettu nopeus — nollatietämyksen ja hajautetun laitteiston edistyminen
Kirjailija: Elena Burger
https://a16z.com/2022/04/15/zero-knowledge-proofs-hardware-decentralization-innovation/

Huippuluokan zk-tutkimus — Ethereum Foundationin zk-tutkijan kanssa
Mary Mallerin, Anna Rosen ja Kobi Gurkanin kanssa
https://zeroknowledge.fm/232-2/

zk-tutkimukseen tutustuminen — DFINITYn tutkimusjohtajan kanssa; myös Groth16:n kaltaisten edistysten takana
Jens Grothin, Anna Rosen ja Kobi Gurkanin kanssa
https://zeroknowledge.fm/237-2/

SNARK tutkimus ja pedagogiikka - yhden ZCashin ja Starkwaren perustajista
Alessandro Chiesan ja Anna Rosen kanssa
https://zeroknowledge.fm/episode-200-snark-research-pedagogy-with-alessandro-chiesa/

Syväsukellukset, rakentajan oppaat

Todennäköisyyspohjaisten todisteiden perusteet - kurssi, jossa on 5 yksikköä interaktiivisista todisteista ja paljon muuta
Kirjailija: Alessandro Chiesa
https://www.youtube.com/playlist?list=PLGkwtcB-DfpzST-medFVvrKhinZisfluC

STARKit — osa I, II, III
Kirjailija: 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

STARKIN anatomia — kuusiosainen opetusohjelma, jossa selitetään STARK-todistusjärjestelmän mekaniikka
Kirjailija Alan Szepieniec
https://aszepieniec.github.io/stark-anatomy/

SNARK-suunnittelu, osa 1 — kysely, käyttö kokoelmassa jne
Kirjailija: Justin Thaler
https://www.youtube.com/watch?v=tg6lKPdR_e4

SNARK-suunnittelu, osa 2 — Rollupit, suorituskyky, turvallisuus
Kirjailija: Justin Thaler
https://www.youtube.com/watch?v=cMAI7g3UcoI

SNARKin suorituskyvyn mittaaminen - käyttöliittymät, taustaohjelmat, enemmän
Kirjailija: Justin Thaler
https://a16zcrypto.com/measuring-snark-performance-frontends-backends-and-the-future/

PLONKin ymmärtäminen
https://vitalik.ca/general/2019/09/22/plonk.html

PLONK nollatietojärjestelmä — 12 lyhyen videon sarja PLONKin toiminnasta
Kirjailija: David Wong
https://www.youtube.com/playlist?list=PLBJMt6zV1c7Gh9Utg-Vng2V6EYVidTFCC

AIRista RAP:iin — miten PLONK-tyylinen aritmetisointi toimii
Kirjailija: Ariel Gabizon
https://hackmd.io/@aztec-network/plonk-arithmetiization-air

Multiset tarkistukset PLONKissa ja Plookupissa
Kirjailija: Ariel Gabizon
https://hackmd.io/@arielg/ByFgSDA7D

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

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

Sovellukset ja opetusohjelmat: todisteita konsepteista, demoista, työkaluista ja paljon muuta

Sovellettu zk — oppimisresurssit
tekijä 0xPARC
https://learn.0xparc.org/materials/intro

Online-kehitysympäristö zkSNARKsille — zkREPL, uusi työkalusarja Circom-työkalupinon vuorovaikutukseen selaimen kanssa
Kirjailija: Kevin Kwok
https://zkrepl.dev (+ selityslanka tätä)

Toisen asteen aritmeettiset ohjelmat nollasta sankariin
Kirjailija: Vitalik Buterin
https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

zkEVM:issä
Alex Gluchowskin ja Anna Rosen kanssa
https://zeroknowledge.fm/175-2/

Eri tyyppiset zkEVM:t
Kirjailija: Vitalik Buterin
https://vitalik.ca/general/2022/08/04/zkevm.html

ZK koneoppiminen — opetusohjelma ja demo hermoverkon asettamiseen SNARKiin
kirjoittaneet Horace Pan, Francis Ho ja Henri Palacci
https://0xparc.org/blog/zk-mnist

ZK-kielillä
Alex Ozdemirin ja Anna Rosen kanssa
https://zeroknowledge.fm/172-2/

Dark Forest — zk-salauksen käyttäminen peleissä — täysin hajautettu ja jatkuva RTS (reaaliaikainen strategia) peli
https://blog.zkga.me/announcing-darkforest

ZKP:t insinööreille - katsaus Dark Forestin ZKP:ihin
https://blog.zkga.me/df-init-circuit

Sukellus nollatietoon
Elena Nadolinkskin, Anna Rosen ja James Prestwichin kanssa
https://zeroknowledge.fm/182-2/

zkDocs: Tiedon jakaminen ilman tietoa
Sam Ragsdale ja Dan Boneh
https://a16zcrypto.com/zkdocs-zero-knowledge-information-sharing/

Yksityisyyttä suojelevat krypto-airdropit, joissa ei ole todisteita tiedosta
Kirjailija: Sam Ragsdale
https://a16z.com/2022/03/27/crypto-airdrop-privacy-tool-zero-knowledge-proofs/

Ketjussa luotettavat asennusseremoniat -
Valeria Nikolaenko ja Sam Ragsdale
https://a16zcrypto.com/on-chain-trusted-setup-ceremony/

Salaussäännökset, laiton rahoitus, yksityisyys ja muut – sisältää osan nollatiedoista sääntely-/säännöstenmukaisuusympäristöissä; Ero "yksityisyyttä säilyttävän" ja hämärtävän tekniikan välillä
Michele Korverin, Jai Ramaswamyn ja Sonal Chokshin kanssa
https://web3-with-a16z.simplecast.com/episodes/crypto-regulations-sanctions-compliance-aml-ofac-news-explained

Muut resurssit

zkMesh-uutiskirje - kuukausittainen uutiskirje, jossa jaetaan viimeisimmät hajautetut yksityisyyden säilyttämistekniikat, tietosuojaprotokollan kehittäminen ja nollatietojärjestelmät
https://zkmesh.substack.com/

Zero Knowledge podcast - viimeisimmistä zk-tutkimuksesta ja zk-sovelluksista sekä asiantuntijoista, jotka rakentavat kryptografiaa tukevaa tietosuojatekniikkaa
Anna Rosen kanssa
https://zeroknowledge.fm/

… selostettu lukulista aiheittain ja kronologisesti, kirjoittanut Justin Thaler:

SNARKit lineaarisista PCP:istä (eli SNARKit piirikohtaisilla asetuksilla)

Tehokkaat argumentit ilman lyhyitä PCP:itä (2007)
Yuval Ishai, Eyal Kushilevitz ja Rafail Ostrovski

Ennen noin vuotta 2007 SNARKit suunniteltiin ensisijaisesti Kilian-micali paradigma, jossa otetaan "lyhyt" todennäköisyydellä tarkistettava todistus (PCP) ja "salakirjoitetaan" se ytimekkääksi argumentiksi Merklen hajautuksen ja Fiat-Shamir-muunnoksen avulla. Valitettavasti lyhyet PCP:t ovat monimutkaisia ​​ja epäkäytännöllisiä vielä nykyäänkin. Tämä artikkeli (IKO) osoitti, kuinka homomorfista salausta käytetään ytimekkäiden (ei läpinäkyvien) interaktiivisten argumenttien saamiseksi "pitkistä mutta strukturoiduista" PCP:istä. Nämä voivat olla paljon yksinkertaisempia kuin lyhyet PCP:t, ja tuloksena olevilla SNARKilla on paljon lyhyemmät todisteet ja nopeampi todentaminen. Näillä argumenteilla havaittiin ensin olevan potentiaalia käytännön tehokkuuteen, ja niitä jalostettiin ja otettiin käyttöön Pippuri. Valitettavasti IKO:n argumenteilla on neliöllinen aikatodistaja ja neliökokoinen rakenteellinen viitemerkkijono, joten ne eivät skaalaudu suuriin laskelmiin.

Quadratic Span -ohjelmat ja suppeat NIZK:t ilman PCP:tä (2012)
kirjoittaneet Rosario Gennaro, Craig Gentry, Bryan Parno ja Mariana Raykova

Tämä läpimurtopaperi (GGPR) alensi IKO:n lähestymistavan todentamiskustannuksia piirin neliökokoisesta kvasilineaariseen. Aiemman työn pohjalta Groth ja Lipmaa, se antoi myös SNARKit pariliitospohjaisen kryptografian kautta interaktiivisten argumenttien sijaan, kuten IKO:ssa. Se kuvasi SNARK-arvojaan kontekstissa, jota nykyään kutsutaan rank-1 rajoitustyytyväisyysongelmaksi (R1CS), joka on yleistys aritmeettisen piirin tyydyttävyydestä.

Tämä artikkeli toimi myös teoreettisena perustana ensimmäisille SNARKeille, jotka näkivät kaupallisen käyttöönoton (esim. ZCashissa) ja johti suoraan SNARKeihin, jotka ovat edelleen suosittuja (esim. Groth16). GGPR:n argumenttien ensimmäiset toteutukset tulivat zaatar ja Pinocchio, ja myöhemmät versiot sisältävät SNARKit C:lle ja BCTV. BCIOP antoi yleisen viitekehyksen, joka selittää nämä lineaariset PCP:t SNARK-muunnokset (katso myös liite A zaatar) ja kuvaa sen erilaisia ​​ilmentymiä.

Pariliitospohjaisten ei-vuorovaikutteisten argumenttien koosta (2016)
Kirjailija: Jens Groth

Tämä artikkeli, jota puhekielessä kutsutaan Grothiksi16, esitteli GGPR:n SNARKien jalostuksen, joka saavuttaa nykyaikaiset konkreettiset todentamiskustannukset (todisteet ovat 3 ryhmäelementtiä, ja todentamista hallitsee kolme paritusoperaatiota, ainakin olettaen, että yleisö syöttö on lyhyt). Turvallisuus on todistettu geneerisessä ryhmämallissa.

SNARKit yleisillä luotetuilla asetuksilla

PlonK: Permutaatiot Lagrange-perusteisiin okumeenisille ei-interaktiivisille tiedon argumenteille (2019)
Ariel Gabizon, Zachary Williamson ja Oana Ciobotaru

Marlin: zkSNARKien esikäsittely yleisellä ja päivitettävällä SRS:llä (2019)
Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely ja Nicholas Ward

Sekä PlonK että Marlin korvaavat Groth16:n piirikohtaisen luotetun asennuksen yleisellä asetuksella. Tämä tapahtuu 4x-6x suurempien todisteiden kustannuksella. Voidaan ajatella, että PlonK ja Marlin ottavat piirikohtaisen työn Groth16:n ja edeltäjien luotetun asennuksen aikana ja siirtävät sen esikäsittelyvaiheeseen, jota tapahtuu. jälkeen luotetussa asennuksessa sekä SNARK-todistuksen luomisen aikana.

Mahdollisuutta käsitellä mielivaltaisia ​​piirejä ja R1CS-järjestelmiä tällä tavalla kutsutaan joskus holografia- tai laskentasitoumuksiksi, ja se kuvattiin myös spartalainen (käsitelty myöhemmin tässä kokoelmassa). Koska todisteiden luomisen aikana tapahtuu enemmän työtä, PlonK:n ja Marlinin todistajat ovat hitaampia kuin Groth16 tietyssä piirissä tai R1CS-instanssissa. Toisin kuin Groth16, PlonK ja Marlin voidaan kuitenkin saada toimimaan yleisempien väliesitysten kanssa kuin R1CS.

Polynomiset sitoutumisjärjestelmät, keskeinen kryptografinen primitiivi SNARKissa

Vakiokokoiset sitoumukset polynomeihin ja niiden sovelluksiin (2010)
Aniket Kate, Gregory Zaverucha ja Ian Goldberg

Tässä artikkelissa esiteltiin polynomisten sitoumusjärjestelmien käsite. Se antoi järjestelmän yksimuuttujapolynomeille (jota kutsutaan yleisesti KZG-sitoumuksiksi) vakiokokoisilla sitoumuksilla ja arviointitodistuksilla. Kaava käyttää luotettua asennusta (eli strukturoitua viitemerkkijonoa) ja pariliitospohjaista kryptografiaa. Se on edelleen erittäin suosittu käytännössä nykyään, ja sitä käytetään SNARK:issa, mukaan lukien edellä käsitellyt PlonK ja Marlin (ja Groth16 käyttää erittäin samanlaisia ​​salaustekniikoita).

Nopeat Reed-Solomonin interaktiiviset Oracle-todistukset läheisyydestä (2017)
Eli Ben-Sasson, Iddo Bentov, Ynon Horesh, Michael Riabzev

Antaa interaktiivisen oraakkelitodistuksen (IOP) Reed-Solomon-testausta varten – eli osoittaa, että sitoutunut merkkijono on lähellä yksimuuttujapolynomin arviointitaulukkoa. Yhdessä Merkle-hashingin ja Fiat-Shamir-muunnoksen kanssa tämä tuottaa läpinäkyvän polynomisen sitoutumisjärjestelmän polylogaritmisen kokoisilla arviointitodistuksilla (katso VP19 yksityiskohtia varten). Nykyään tämä on lyhin uskottavasti post-kvanttipolynomisten sitoumusjärjestelmien joukossa.

Ligero: Kevyet sublineaariset argumentit ilman luotettavaa asennusta (2017)
Scott Ames, Carmit Hazay, Yuval Ishai ja Muthuramakrishnan Venkitasubramaniam

Kuten FRI, tämä työ antaa IOP:n Reed-Solomon-testaukseen, mutta neliöjuuren todistepituudella polylogaritmisen sijaan. Teoreettinen toimii osoitti, että vaihtamalla Reed-Solomon-koodi eri virheenkorjaavaan koodiin, jossa on nopeampi koodaus, voidaan saada lineaarinen aikatodistus, joka lisäksi toimii natiivisti millä tahansa kentällä. Tämä lähestymistapa on jalostettu ja otettu käyttöön vuonna Jarrutus ja Orion, joka tuottaa huippuluokan suorituskyvyn.

Luodinkestävät: Lyhyet todisteet luottamuksellisista tapahtumista ja paljon muuta (2017)
Kirjailija: Benedikt Bunz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille ja Greg Maxwell

Jalostaa aikaisempia töitä BCCGP, Bulletproofs antaa läpinäkyvän polynomisen sitoutumismallin (itse asiassa yleistyksen, jota kutsutaan sisätuloargumentiksi), joka perustuu diskreettien logaritmien laskemisen kovuuteen logaritmisella todistuskoolla mutta lineaarisella todentamisajalla. Järjestelmä on edelleen suosittu tänään läpinäkyvyytensä ja lyhyiden todisteidensa vuoksi (esim. sitä käytetään ZCash Orchardissa ja Monerossa).

Dory: Tehokkaat, läpinäkyvät argumentit yleistetyille sisäisille tuotteille ja polynomisille sitoumuksille (2020)
Kirjailija: Jonathan Lee

Dory vähentää Bulletproofsissa todentamisaikaa lineaarisesta logaritmiseen säilyttäen samalla läpinäkyvyyden ja logaritmisen kokoiset vedokset (tosinkin konkreettisesti suurempia kuin Bulletproofs) ja läpinäkyvyyden. Käyttää pareja ja perustuu SXDH-oletukseen.

Vuorovaikutteiset todisteet, usean todistajan interaktiiviset todisteet ja niihin liittyvät SNARKit

Laskennan delegointi: Interaktiiviset todisteet jäseille (2008)
Shafi Goldwasser, Yael Tauman Kalai ja Guy Rothblum

Ennen tätä paperia yleiskäyttöiset interaktiiviset vedokset vaadittiin a superpolynomi-aika todistaja. Tässä artikkelissa annetaan interaktiivinen todistusprotokolla, jota kutsutaan yleisesti GKR-protokollaksi, jossa on polynominen aikatodistaja ja kvasilineaarinen aikatodentaja, jokaiselle ongelmalle, jolla on tehokas rinnakkaisalgoritmi (vastaavasti interaktiivinen todistus koskee mitä tahansa aritmeettista piiriä, jolla on pieni syvyys).

Käytännön varmennettu laskenta vuorovaikutteisten todisteiden suoratoistolla (2011)
kirjoittaneet Graham Cormode, Michael Mitzenmacher, Justin Thaler

Tämä paperi (jota joskus kutsutaan CMT:ksi) lyhensi prover-aikaa GKR-protokollassa kvartisesta piirin koosta kvasilineaariseen. Tuotti ensimmäisen yleiskäyttöisen interaktiivisen todisteen täytäntöönpanon. Rivi myöhempiä töitä (Maustepippuri, Thaler 13, Kirahvija Vaaka) lyhensi todistajan käyttöaikaa edelleen kvasilineaarisesta lineaariseen piirin koossa.

vSQL: mielivaltaisten SQL-kyselyiden tarkistaminen dynaamisten ulkoistettujen tietokantojen kautta (2017)
Yupeng Zhang, Daniel Genkin, Jonathan Katz, Dimitrios Papadopoulos ja Charalampos Papamanthou

Vaikka otsikko viittaa tiettyyn sovellusalueeseen (tietokantoihin), tämän artikkelin panokset ovat yleisempiä. Tarkemmin sanottuna se havaitsi, että voidaan saada ytimekkäitä argumentteja piirien tyydyttävyydestä yhdistämällä interaktiivisia todisteita polynomisten sitoumusmenetelmien kanssa (monilineaarisille polynomeille).

Myöhemmin toimii sulatettu argumentit nolla-tietoa ja esittelivät erilaisia ​​sitoumuksia monilineaarisille polynomeille.

Spartan: Tehokkaat ja yleiskäyttöiset zkSNARKit ilman luotettavaa asennusta (2019)
Kirjailija: Srinath Setty

Hanki SNARKit piirien tyydyttävyyttä ja R1CS:ää varten yhdistämällä multi-prover interaktiivisia todisteita (MIP) polynomisiin sitoutumismenetelmiin, jotka perustuvat aikaisempaan työhön konkreettisesti tehokkaiden MIP-tiedostojen parissa. Apila. Vaikutus on saada SNARKit lyhyemmillä todisteilla kuin ne, jotka on johdettu interaktiivisista todisteista, kuten edellä käsitellystä GKR-protokollasta. Analogisesti PlonK:n ja Marlinin kanssa, Spartan näyttää myös kuinka käsitellä mielivaltaisia ​​piirejä ja R1CS-järjestelmiä esikäsittelyn ja SNARK-todistuksen generoinnin avulla.

Spartan käytti polynomista sitoutumisjärjestelmää hyrax. Myöhemmät teokset ns Jarrutus ja Orion Yhdistä Spartanin MIP muihin polynomisiin sitoumuksiin saadaksesi ensimmäiset toteutetut SNARKit lineaarisella aikatodistimella.

Lyhyet PCP:t ja IOP:t

Lyhyet PCP:t polylogikyselyn monimutkaisuudella (2005)
Eli Ben-Sasson ja Madhu Sudan

 Tämä teoreettinen työ antoi ensimmäisen todennäköisyydellä tarkistettavan todisteen (PCP), jonka todistuksen pituus oli kvasilineaarinen varmennettavan laskelman koossa ja polylogaritmisella kyselyllä (tosin lineaarisella todentamisajalla). Kilian-Micali-muunnoksen jälkeen PCP:t SNARK:iksi, tämä oli askel kohti SNARKeja, joissa oli kvasilineaarinen aikatodistaja ja polylogaritminen aikatodentaja.

Myöhemmin teoreettinen työ lyhensi todentajan ajan polylogaritmiseen. Myöhempi Käytännöllinen työ jalosti tätä lähestymistapaa, mutta lyhyet PCP:t ovat edelleen epäkäytännöllisiä nykyään. Saadaksesi käytännöllisiä SNARKeja, myöhemmin toimii kääntyi että nimeltään PCP:n interaktiivinen yleistys Interaktiiviset Oracle Proofs (IOP:t). Nämä pyrkimykset johtivat ja jatkoivat Perjantai, suosittu polynomisten sitoumusten järjestelmä, jota käsitellään tämän kokoelman polynomisia sitoumuksia käsittelevässä osassa.

Muita tämän kategorian teoksia ovat mm ZKBoo ja sen jälkeläiset. Näillä ei saada ytimekkäitä todisteita, mutta niillä on hyvät vakiotekijät ja siksi ne ovat houkuttelevia pienten väitteiden todistamiseen. Ne ovat johtaneet kvanttijälkeisten allekirjoitusten perheisiin, kuten Piknikki jotka ovat ollut optimoitu in useat toimii. ZKBoo esitetään noudattaen erillistä suunnitteluparadigmaa nimeltä MPC-päässä, mutta se tuottaa silmänpaineen.

Rekursiiviset SNARKit

Asteittain todennettavissa oleva laskenta tai todisteet tiedosta viittaavat aika-/tilatehokkuuteen (2008)
Kirjailija: Paul Valiant

Tämä työ esitteli perustavanlaatuisen käsitteen inkrementaalisesti todennettavasta laskennasta (IVC), jossa todistaja suorittaa laskennan ja ylläpitää aina todistetta siitä, että laskenta on tähän mennessä ollut oikein. Se rakensi IVC:n SNARKien rekursiivisen koostumuksen avulla. Tässä, tieto-uskollisuus SNARKien ominaisuus on välttämätön rekursiivisesti muodostettujen ei-interaktiivisten argumenttien luotettavuuden määrittämiseksi. Tämä artikkeli tarjosi myös erittäin tehokkaan tiedonpoimijan PCP-peräisille SNARKeille (Kilian-Micali-paradigman mukaisesti).

Skaalautuva nollatieto elliptisten käyrien sykleillä (2014)
Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer ja Madars Virza

Jälkeen teoreettinen työTässä artikkelissa käytettiin GGPR:n SNARKin muunnelman rekursiivista sovellusta IVC:n ensimmäisen toteutuksen aikaansaamiseksi yksinkertaiselle virtuaalikoneelle (TinyRAM, SNARKit C:lle paperi).

Esitteli myös käsitteen elliptisten käyrien jaksoista, jotka ovat hyödyllisiä elliptisen käyrän salausta hyödyntävien SNARKien rekursiivisessa muodostamisessa.

Rekursiivinen todistekoostumus ilman luotettua asennusta (2019)
Sean Bowe, Jack Grigg ja Daira Hopwood

Tämä työ (nimeltään Halo) tutkii, kuinka rekursiivisesti luodaan läpinäkyviä SNARKeja. Tämä on haastavampaa kuin ei-läpinäkyvien muodostaminen, koska läpinäkyvien SNARKien varmennusmenettely voi olla paljon kalliimpaa.

Tämä herätti sitten a viiva of työ joka on huipentunut järjestelmiin, kuten Nova saavuttaa huippuluokan IVC-suorituskyvyn, joka on jopa parempi kuin läpinäkymättömien SNARKien, kuten Groth16, koostumuksella.

Sovellukset

Zerocash: Hajautetut nimettömät maksut Bitcoinista (2014)
Eli Ben Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, Madars Virza

Aiemman työn pohjalta mm nollakolikoita (ja kanssa Pinnochio kolikko samanaikaisena työnä), tässä artikkelissa käytetään GGPR-pohjaisia ​​SNARKeja yksityisen kryptovaluutan suunnitteluun. Johti ZCashiin.

Geppetto: Monipuolinen verifioitava laskenta (2014)
kirjoittaneet Craig Costello, Cédric Fournet, Jon Howell, Markulf Kohlweiss, Benjamin Kreuter, Michael Naehrig, Bryan Parno ja Samee Zahur

Geppetto on luultavasti ennen kuin kiinnostus räjähdysmäisesti kasvoi yksityiseen älykkäiden sopimusten toteuttamiseen, koska se on kirjoitettu noin vuosi Ethereumin luomisen jälkeen. Siksi sitä ei esitetä yksityisen älykkäiden sopimusten täytäntöönpanon yhteydessä. Se kuitenkin käyttää SNARKien rajattua syvyysrekursiota, jotta epäluotettava todistaja voi suorittaa minkä tahansa yksityisen (sitoutuneen/allekirjoitetun) tietokoneohjelman yksityisillä tiedoilla paljastamatta tietoja käynnissä olevasta ohjelmasta tai datasta, jolla sitä ajetaan. Näin ollen se on edeltäjä työlle yksityisillä älykkäillä sopimusalustoilla, kuten Zexe [kuvailtu alla].

Varmennettavissa olevat ASIC:t (2015)
Riad Wahby, Max Howald, Siddharth Garg, abhi shelat, Michael Walfish

Tässä artikkelissa pohditaan ongelmaa, kuinka turvallisesti ja hedelmällisesti käyttää epäluotettavassa valimossa valmistettua ASIC-järjestelmää (vuonna 2015 huippuluokan valimoita oli vain viidessä maassa). Lähestymistapa on saada nopea, mutta epäluotettava ASIC todistamaan tulostensa oikeellisuus todentajalle, joka käyttää hitaampaa mutta luotettavaa ASIC:ia. Ratkaisu on mielenkiintoinen niin kauan kuin järjestelmän kokonaissuoritusaika (todistajan ja todentajan ajoaikojen summa plus mahdolliset tiedonsiirtokustannukset) on pienempi kuin naiivi perusviiva: aika, joka tarvitaan laskennan suorittamiseen kokonaan hitaammin. - mutta luotettu ASIC. Käyttämällä GKR/CMT/Allspice interaktiivisten vedosten varianttia paperi todellakin ylittää naiivin perusviivan useissa perusongelmissa, mukaan lukien lukuteoreettiset muunnokset, kuvioiden sovitus ja elliptisen käyrän operaatiot. Tämä työ viittaa siihen, että jotkut todistusjärjestelmät sopivat paremmin laitteistototeutukseen kuin toiset. Vedosjärjestelmien optimointi laitteiston toteutusta varten on nyt saamassa huomattava huomio, mutta paljon on vielä tutkimatta.

todennettavissa Viivetoiminnot (2018)
kirjoittaneet Dan Boneh, Joseph Bonneau, Benedikt Bünz ja Ben Fisch

Otettiin käyttöön todennettavissa olevien viivetoimintojen (VDF) merkintä, kryptografinen primitiivi, joka on laajalti hyödyllinen lohkoketjusovelluksissa, esim. proof-of-stake-konsensusprotokollien mahdollisen manipuloinnin vähentämisessä. SNARKit (erityisesti asteittain todettavissa olevaan laskemiseen) tarjoavat reitin huippuluokan VDF-tiedostoihin.

Zexe: Ottaa käyttöön hajautetun yksityisen laskennan (2018)
kirjoittaneet Sean Bowe, Alessandro Chiesa, Matthew Green, Ian Miers, Pratyush Mishra ja Howard Wu

Zexe on suunnittelu yksityiselle älysopimusalustalle. Zexeä voidaan pitää Zerocashin (kuvattu yllä) laajenteena. Zerocash mahdollistaa yhden sovelluksen ajamisen ketjussa (jolloin käyttäjät voivat siirtää tokeneita) samalla kun käyttäjätietojen yksityisyys suojelee, esim. kenelle he lähettävät merkkejä, vastaanottavat tokeneja, siirrettyjen tokenien määrän jne. Zexe mahdollistaa monia eri sovellukset (älykkäät sopimukset) toimivat samassa lohkoketjussa ja ovat vuorovaikutuksessa toistensa kanssa. Tapahtumat toteutetaan ketjun ulkopuolella, ja todisteet oikeasta toteutuksesta postitetaan ketjuun. Tietosuojan lisäksi toimintojen yksityisyys on suojattu. Tämä tarkoittaa, että kuhunkin tapahtumaan liittyvä todiste ei edes paljasta, mihin sovelluksiin tapahtuma liittyy. Zexen yleisempi suunnittelupanos on se, että se esitteli BLS12-377:n, elliptisen käyräryhmän, joka on hyödyllinen pariliitospohjaisten SNARKien tehokkaassa syvyys 1 -koostumuksessa.

Replikoidut tilakoneet ilman replikoitua suoritusta (2020)
Jonathan Lee, Kirill Nikitin ja Srinath Setty

Tämä on yksi harvoista akateemisista kirjoituksista, jotka käsittelevät lohkoketjun skaalautuvuutta. Siinä ei käytetä termiä rollups, koska se on aikaisempi tai on samanaikainen käsitteen kanssa, joka esitellään akateemisen kirjallisuuden ulkopuolella.

Käyttöliittymät (tehokkaat muunnokset tietokoneohjelmista välimuotoisiksi esityksiksi, kuten piirien tyytyväisyyteen, R1CS:ään ja muihin)

Nopeat vähennykset RAM-muistista delegoitaviin ytimekkäisiin rajoitustyytyväisyysongelmiin (2012)
Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin ja Eran Tromer

Nykyaikaisesta näkökulmasta tämä on varhainen työ käytännön tietokone-ohjelmasta piiriin-SAT -muunnoksille virtuaalikoneen (VM) abstraktiota varten. Perustuu teoksiin 1970-luvun lopulta 1990-luvulle (esim Robson) tässä artikkelissa esitetään deterministinen pelkistys VM:n suorittamisesta T-vaiheessa O(T*polylog(T))-koon piirin tyydyttävyyteen.

Myöhemmät paperit, esim. SNARKit C:lle ja BCTV, jatkoi käyttöliittymän kehittämistä virtuaalikoneen abstraktion avulla, ja nykyaikaisiin ilmentymiin kuuluu mm. Kairo, RISC Zeroja Polygon Miden.

Todistukseen perustuvan laskennan siirtäminen muutaman askeleen lähemmäksi käytännöllisyyttä (2012)
Srinath Setty, Victor Vu, Nikhil Panpalia, Benjamin Braun, Muqeet Ali, Andrew J. Blumberg ja Michael Walfish

Tämä artikkeli, jota kutsutaan nimellä Ginger, on toinen varhainen panos käytännön etupään tekniikoihin. Ginger esitteli gadgeteja yleisiin ohjelmointiprimitiiveihin, kuten ehdollisiin ja loogisiin lausekkeisiin, vertailuihin ja bittikohtaiseen aritmetiikkaan bittien jakamisen, primitiivisen liukulukuaritmetiikan jne. avulla. Se käytti näitä vempaimia tarjotakseen ensimmäisen toteutetun käyttöliittymän korkean tason kielestä matalan asteen kieleen. aritmeettiset rajoitukset (samankaltainen kuin nyt R1CS), väliesitys (IR), johon voidaan soveltaa SNARK-taustaa.

Kun taas "Fast Reductions" -paperi ja sen jälkeläiset käyttävät "CPU-emulaattori" -lähestymistapaa IR:ien tuottamisessa (eli IR varmistaa, että todistaja suoritti tietyn ohjelman oikein käyttämällä CPU:n siirtymätoimintoa tietylle määrälle vaiheita) , Ginger ja sen jälkeläiset omaksuvat ASIC-kaltaisen lähestymistavan ja tuottavat IR:itä, jotka on räätälöity tietokoneohjelmalle, jonka todistaja väittää suorittavansa oikein.

Esimerkiksi Bufetti osoittaa, että on mahdollista käsitellä monimutkaista ohjausvirtaa ASIC-mallissa muuttamalla tällainen ohjausvirta suoritettavan ohjelman mukaan räätälöityksi äärellistilaiseksi koneeksi ja että tämä lähestymistapa voi olla huomattavasti tehokkaampi kuin yleiskäyttöisen CPU-emulaattorin rakentaminen. xJsnark tarjoaa tehokkaan rakenteen monitarkkuusaritmetiikkaan, RAM- ja ROM-muistien optimointiin ja paljastaa ohjelmoijalle Java-tyyppisen korkean tason kielen, joka on edelleen suosittu tänään. CirC panee merkille, että tietokoneohjelmien kääntäminen R1CS:ään liittyy läheisesti ohjelma-analyysistä tunnettuihin tekniikoihin, ja rakentaa kääntäjän rakentamisen työkalupakin, joka sisältää ideoita molemmilta yhteisöiltä ("LLVM piirin kaltaisille esityksille"). Aikaisempia töitä, jotka ovat vaikuttaneet ASIC-tyylisiin käyttöliittymiin, ovat mm Pinocchio ja Geppetto.

"Fast-Reductions" -paperissa käytettiin monimutkaista ja kallista rakennetta, jota kutsutaan "reititysverkoiksi" ns. muistin tarkistus (eli varmistamalla, että epäluotettava todistaja ylläpitää oikein VM:n hajasaantimuistia koko sen virtuaalikoneen suorituksen ajan, jonka oikeellisuutta todistetaan). Tämä valinta tehtiin, koska tämän kaltaiset varhaiset työt pyrkivät saamaan PCP:tä, mikä edellytti käyttöliittymän sekä ei-interaktiivinen ja tietoteoreettisesti turvallinen. Myöhemmin työ soitti Ruokakomero (edellinen Bufetti edellä mainittu työ) käytti Merkle-puita reititysverkkojen sijaan saavuttaen tehokkuutta kääntämällä algebrallisen (eli "SNARK-ystävällisen") hash-funktion, koska Ajtai, rajoituksiin. Tämä johti "laskennallisesti turvalliseen" käyttöliittymään. Nykyään SNARK-ystävällisistä hash-funktioista on olemassa laaja tutkimuskirjallisuus, jossa on esimerkkejä mm Poseidon, MiMC, Teräsbetoni, Pelastus, Ja enemmän.

Huippuluokan tekniikat, joilla varmistetaan, että todistaja ylläpitää RAM-muistia oikein, perustuvat niin kutsuttuihin "permutaatioinvariantteihin sormenjälkien" menetelmiin, jotka ovat peräisin ainakin vuodesta Lipton (1989) ja käyttänyt muistin tarkistamiseen Blum et ai. (1991). Nämä tekniikat sisältävät luonnostaan ​​vuorovaikutuksen todistajan ja todentajan välillä, mutta ne voidaan tehdä ei-vuorovaikutteisiksi Fiat-Shamir-muunnoksen kanssa. Sikäli kuin tiedämme, he tutustuivat käytännön SNARK-käyttöliittymän kirjallisuuteen ns. VRAM.

Permutaatioinvariantteja sormenjälkitekniikoita käytetään nykyään monissa käyttöliittymissä ja SNARKissa virtuaalikoneen abstraktioissa, mukaan lukien esim. Kairo. Läheisesti toisiinsa liittyvät ideat ilmaantuivat uudelleen toisiinsa liittyvissä yhteyksissä alla olevissa kahdessa teoksessa, joita käytetään laajasti nykyään käytännössä.

Lähes lineaarisen ajan nollatietotodisteet ohjelman oikeaan suorittamiseen (2018)
Kirjailija: Jonathan Bootle, Andrea Cerulli, Jens Groth, Sune Jakobsen ja Mary Maller

Plookup: Yksinkertaistettu polynomiprotokolla hakutaulukoille (2020)
kirjoittaneet Ariel Gabizon ja Zachary Williamson

Varhaiset käyttöliittymätyöt edustivat "ei-aritmeettisia" operaatioita (kuten etäisyyden tarkistuksia, bittikohtaisia ​​operaatioita ja kokonaislukuvertailuja) piireissä ja niihin liittyvissä IR:issä hajottamalla kenttäelementit biteiksi, suorittamalla operaatioita näille biteille ja sitten "pakkaamalla". tuloksen takaisin yhdeksi kenttäelementiksi. Tuloksena olevan piirin koon suhteen tämä johtaa logaritmiseen lisäkustannuksiin operaatiota kohden.

Yllä olevat kaksi teosta (BCGJM ja Plookup) antavat vaikuttavia tekniikoita (jotka perustuvat ns. "hakutaulukoihin") näiden toimintojen kuvaamiseksi tehokkaammin piirien sisällä, amortisoidussa mielessä. Karkeasti sanottuna joidenkin käyttöliittymäsuunnittelijan valitsemien parametrien B kohdalla nämä vähentävät jokaisen ei-aritmeettisen toiminnon esittämiseen tarvittavien porttien määrää B:ssä logaritmisella kertoimella, sen kustannuksella, että todistaja sitoutuu kryptografisesti ylimääräiseen "neuvonta"-vektori, jonka pituus on suunnilleen B.