Zero Knowledge Canon

A szerkesztő megjegyzése: Az a16z crypto hosszú sorozattal rendelkezik a „pisztolyok", tőlünk DAO Canon tavaly nálunk NFT Canon korábban (és előtte az eredeti Crypto Canon) — feltétlenül iratkozzon fel a mi oldalunkra web3 heti hírlevél további frissítésekért, valamint egyéb kurált forrásokért.

Zokogáselow, összegyűjtöttünk egy sor forrást azok számára, akik mindent megértenek, mélyebbre akarnak menni és építenek nulla tudás: erőteljes, alapvető technológiák, amelyek a blokklánc méretezhetőségének kulcsait rejtik, és a magánélet-megőrző alkalmazások jövőjét és számtalan további újítást képviselnek. Ha javaslata van a kiváló minőségű darabokkal kapcsolatban, tudassa velünk @a16zcrypto.

A zéró tudásalapú rendszerek évtizedek óta léteznek: Shafi Goldwasser, Silvio Micali és Charles Rackoff 1985-ös bevezetése átalakító hatással volt a kriptográfia területére, és az ACM Turing-díjjal ismerték el, amelyet Goldwassernek és Micalinak ítéltek oda. 2012. Mivel ez a munka – beleértve az elméletből a gyakorlatba való áttérést és a crypto/web3-ban való mai alkalmazásokba való áttérését – évtizedek óta készül, a kánonsorozatunkban először megosztunk egy második részt is (jelenleg alább található): által jegyzett olvasmánylista Justin Thaler, az alábbi első részt követően.

Köszönetnyilvánítás: Köszönet Michael Blaunak, Sam Ragsdale-nek és Tim Roughgardennek is.

Alapok, háttér, evolúciók

Ezeknek a tanulmányoknak némelyike ​​általában a kriptográfiáról is szól (nem minden zéró tudás önmagában), beleértve azokat a problémákat vagy kulcsfontosságú előrelépéseket, amelyekkel manapság nulla tudásalapú bizonyítékok foglalkoznak: hogyan biztosítható a magánélet és a hitelesítés nyílt hálózatokban.

Új irányok a kriptográfiában (1976)
írta Whitfield Diffie és Martin Hellman
https://ee.stanford.edu/~hellman/publications/24.pdf

Módszer digitális aláírások és nyilvános kulcsú kriptorendszerek megszerzésére
írta: 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

Protokollok nyilvános kulcsú kriptorendszerekhez (1980)
írta: Ralph Merkle
http://www.merkle.com/papers/Protocols.pdf

Biztonságos kommunikáció nem biztonságos csatornákon (1978)
írta: Ralph Merkle
https://www.merkle.com/1974/PuzzlesAsPublished.pdf

Elliptikus görbék használata a kriptográfiában (1988)
írta: Victor Miller
https://link.springer.com/content/pdf/10.1007%2F3-540-39799-X_31.pdf

Az interaktív bizonyítási rendszerek tudáskomplexitása (1985)
írta Shafi Goldwasser, Silvio Micali, Charles Rackof
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.419.8132&rep=rep1&type=pdf

Számítási hangszigetelések (2000)
írta: Silvio Micali
https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/Computationally_Sound_Proofs.pdf

A kivonható ütközésállóságtól a tudás tömör, nem interaktív érveiig [SNARK], és vissza (2011)
írta: Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer
https://eprint.iacr.org/2011/443.pdf

Hatékony nulla tudású argumentum a keverés helyességére (2012)
Írta: Stephanie Bayer és Jens Groth
http://www0.cs.ucl.ac.uk/staff/J.Groth/MinimalShuffle.pdf

Tömör, nem interaktív nulla tudás a Neumann-építészethez (2013)
Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer és Madars Virza
https://eprint.iacr.org/2013/879.pdf

Skálázható, átlátható és kvantum után biztonságos számítási integritás (2018)
szerző: Eli Ben-Sasson, Iddo Bentov, Yinon Horesh és Michael Riabzev
https://eprint.iacr.org/2018/046.pdf

Nyilvános érmék nulla tudásszintű érvek (majdnem) minimális idő- és térráfordítással (2020)
írta: Alexander Block, Justin Holmgren, Alon Rosen, Ron Rothblum és Pratik Soni
https://www.iacr.org/cryptodb/data/paper.php?pubkey=30645

Áttekintések és bevezetők

Bizonyítások, érvek és nulla tudás — Az ellenőrizhető számítástechnikai és interaktív bizonyítások és érvek, kriptográfiai protokollok áttekintése, amelyek lehetővé teszik a bizonyító számára, hogy garanciát nyújtson a hitelesítőnek arra vonatkozóan, hogy a bizonyító helyesen hajtotta végre a kért számítást, beleértve a nulla tudást is (ahol a bizonyítások a saját érvényességükön kívül más információt nem tárnak fel) . A Zk-érveknek számtalan alkalmazása van a kriptográfiában, és az elmúlt évtizedben az elméletből a gyakorlatba ugrottak.
írta Justin Thaler
https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf

A zéró tudás bizonyítására szolgáló modellek evolúciója — A nulla tudásalapú bizonyítékok áttekintése, ahol Meiklejohn (University College London, Google) megvizsgálja a fejlesztésüket mozgató alkalmazásokat, az új interakciók rögzítésére kidolgozott különböző modelleket, az elérhető konstrukciókat és a munkát. maradt tennivaló.
Írta: Sarah Meiklejohn
https://www.youtube.com/watch?v=HO97kVMI3SE

ZK tábla-ülések — bevezető modulok
Dan Boneh és munkatársaival
https://zkhack.dev/whiteboard/

Biztonság és adatvédelem a zkps-s titkosításhoz — a zéró tudás bizonyításának úttörője a gyakorlatban; mi az a zkps és hogyan működnek… beleértve az élő színpadi „demót”
írta: Zooko Wilcox
https://a16z.com/2019/08/29/security-and-privacy-for-crypto-with-zero-knowledge-proofs/

Legjobb technológiai témák, elmagyarázva — beleértve általában a nulla tudás definícióit és következményeit
Szerző: 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

Hogyan fogja az elkövetkező adatvédelmi réteg megjavítani az elromlott webet
írta: Howard Wu
https://future.com/a-privacy-layer-for-the-web-can-change-everything/

Bevezetés a zkSNARK-okba
Howard Wu-val, Anna Rose-zal
https://zeroknowledge.fm/38-2/

Miért és hogyan működik a zk-SNARK: határozott magyarázat
írta: Maksym Petkus
https://arxiv.org/pdf/1906.07221.pdf

Bevezetés a nulla tudásszintű bizonyításokba
Fredrik Harrysson és Anna Rose
https://www.zeroknowledge.fm/21 [+ összefoglaló írás máshol itt]

Zk-SNARK: a motorháztető alatt
írta Vitalik Buterin
https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
rész 1, rész 2, rész 3

Decentralizált sebesség — a tudás nulla bizonyítása, a decentralizált hardver fejlesztése
írta: Elena Burger
https://a16z.com/2022/04/15/zero-knowledge-proofs-hardware-decentralization-innovation/

Élvonalbeli zk kutatás — az Ethereum Alapítvány zk kutatójával
Mary Mallerrel, Anna Rose-zal, Kobi Gurkannal
https://zeroknowledge.fm/232-2/

A zk kutatás feltárása — a DFINITY kutatási igazgatójával; olyan fejlesztések mögött is, mint a Groth16
Jens Groth, Anna Rose, Kobi Gurkan közreműködésével
https://zeroknowledge.fm/237-2/

SNARK kutatás és pedagógia - a ZCash és a Starkware egyik társalapítójával
Alessandro Chiesával, Anna Rose-zal
https://zeroknowledge.fm/episode-200-snark-research-pedagogy-with-alessandro-chiesa/

Mély merülések, építő útmutatók

A valószínűségi bizonyítások alapjai — egy kurzus 5 egységből interaktív bizonyításokból és egyebekből
írta: Alessandro Chiesa
https://www.youtube.com/playlist?list=PLGkwtcB-DfpzST-medFVvrKhinZisfluC

STARK-ok – I., II., III. rész
írta 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

Egy STARK anatómiája — egy hatrészes oktatóanyag, amely elmagyarázza a STARK bizonyítási rendszer mechanikáját
írta Alan Szepieniec
https://aszepieniec.github.io/stark-anatomy/

SNARK tervezés, 1. rész — felmérés, összesítésben való felhasználás stb
írta Justin Thaler
https://www.youtube.com/watch?v=tg6lKPdR_e4

SNARK tervezés, 2. rész — összevonások, teljesítmény, biztonság
írta Justin Thaler
https://www.youtube.com/watch?v=cMAI7g3UcoI

A SNARK teljesítményének mérése - frontendek, háttérrendszerek, egyebek
írta Justin Thaler
https://a16zcrypto.com/measuring-snark-performance-frontends-backends-and-the-future/

A PLONK megértése
https://vitalik.ca/general/2019/09/22/plonk.html

A PLONK nulla tudásbiztos rendszer — 12 rövid videóból álló sorozat a PLONK működéséről
írta: David Wong
https://www.youtube.com/playlist?list=PLBJMt6zV1c7Gh9Utg-Vng2V6EYVidTFCC

Az AIR-től a RAP-ig — hogyan működik a PLONK-stílusú aritmetizálás
írta: Ariel Gabizon
https://hackmd.io/@aztec-network/plonk-arithmetiization-air

Multiset ellenőrzések a PLONK-ban és a Plookup-ban
írta: Ariel Gabizon
https://hackmd.io/@arielg/ByFgSDA7D

Halo2 design - az ECC-től
https://zcash.github.io/halo2/design.html

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

Alkalmazások és oktatóanyagok: koncepciók, demók, eszközök stb

Alkalmazott zk — tanulási források
0xPARC által
https://learn.0xparc.org/materials/intro

Online fejlesztői környezet a zkSNARK-okhoz — zkREPL, egy új eszközkészlet a Circom toolstack böngészőn belüli interakciójához
írta: Kevin Kwok
https://zkrepl.dev (+ magyarázó szál itt)

Másodfokú aritmetikai programok nullától hősig
írta Vitalik Buterin
https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

A zkEVM-eken
Alex Gluchowskival és Anna Rose-zal
https://zeroknowledge.fm/175-2/

Különböző típusú zkEVM-ek
írta Vitalik Buterin
https://vitalik.ca/general/2022/08/04/zkevm.html

ZK gépi tanulás — oktatóanyag és bemutató neurális háló SNARK-ba helyezéséhez
írta: Horace Pan, Francis Ho és Henri Palacci
https://0xparc.org/blog/zk-mnist

A ZK nyelveken
Alex Ozdemirrel és Anna Rose-zal
https://zeroknowledge.fm/172-2/

Dark Forest — zk kriptográfia alkalmazása játékokra — egy teljesen decentralizált és tartós RTS (valós idejű stratégiai) játék
https://blog.zkga.me/announcing-darkforest

ZKP-k mérnökök számára — egy pillantás a Sötéterdő ZKP-kra
https://blog.zkga.me/df-init-circuit

Merülés a nulla tudásba
Elena Nadolinkski, Anna Rose, James Prestwich szereplésével
https://zeroknowledge.fm/182-2/

zkDocs: Zéró tudás megosztása
írta: Sam Ragsdale és Dan Boneh
https://a16zcrypto.com/zkdocs-zero-knowledge-information-sharing/

Magánéletet védő crypto airdrops, nulla tudásigazolással
írta: Sam Ragsdale
https://a16z.com/2022/03/27/crypto-airdrop-privacy-tool-zero-knowledge-proofs/

A láncon belüli megbízható beállítási ceremóniák -
írta: Valeria Nikolaenko és Sam Ragsdale
https://a16zcrypto.com/on-chain-trusted-setup-ceremony/

Kriptoszabályozás, tiltott finanszírozás, adatvédelem és még sok más – tartalmaz egy szakaszt a szabályozási/megfelelőségi összefüggésekben a nulla tudásról; különbség a „magánélet-megőrző” és a zavaró technológiák között
Michele Korverrel, Jai Ramaswamyval, Sonal Chokshival
https://web3-with-a16z.simplecast.com/episodes/crypto-regulations-sanctions-compliance-aml-ofac-news-explained

Egyéb források

zkMesh hírlevél - havi hírlevél, amely megosztja a decentralizált adatvédelmi technológiák, az adatvédelmi protokollok fejlesztése és a nulla tudású rendszerek legújabb eredményeit
https://zkmesh.substack.com/

Zero Knowledge podcast - a legújabb zk kutatásról és zk-alkalmazásokról, valamint a kriptográfia-kompatibilis adatvédelmi technológiát építő szakértőkről
Anna Rose-zal
https://zeroknowledge.fm/

…a jegyzetekkel ellátott olvasmánylista, téma és időrend szerint, Justin Thalertől:

SNARK-ok lineáris PCP-kből (más néven SNARK-ok áramkör-specifikus beállítással)

Hatékony érvek rövid PCP-k nélkül (2007)
Yuval Ishai, Eyal Kushilevitz és Rafail Ostrovsky

2007 előtt a SNARK-okat elsősorban a Kilian-micali paradigmája, hogy egy „rövid” valószínűségileg ellenőrizhető bizonyítékot (PCP) veszünk, és „kriptográfiailag összeállítjuk” egy tömör érvvé Merkle-hashing és a Fiat-Shamir transzformáció révén. Sajnos a rövid PCP-k még ma is bonyolultak és nem praktikusak. Ez a cikk (IKO) bemutatta, hogyan lehet homomorf titkosítást használni, hogy tömör (nem átlátszó) interaktív érveket nyerjünk „hosszú, de strukturált” PCP-kből. Ezek sokkal egyszerűbbek lehetnek, mint a rövid PCP-k, és az eredményül kapott SNARK-ok sokkal rövidebb bizonyítással és gyorsabb ellenőrzéssel rendelkeznek. Ezeket az érveket először felismerték, mint a gyakorlati hatékonyság lehetőségét, majd finomították és alkalmazták Pepper. Sajnos az IKO argumentumai másodfokú idejű próbával és másodfokú méretű strukturált hivatkozási karakterlánccal rendelkeznek, így nem skálázódnak nagy számításokhoz.

Quadratic Span programok és tömör NIZK-k PCP-k nélkül (2012)
írta: Rosario Gennaro, Craig Gentry, Bryan Parno és Mariana Raykova

Ez az áttörést jelentő papír (GGPR) csökkentette az IKO megközelítésének bizonyítási költségeit az áramkör négyzetes méretéről a kvázilineárisra. korábbi munkáira építve Groth és a Lipmaa, a SNARK-okat is párosításon alapuló kriptográfián keresztül adta meg, nem pedig interaktív argumentumokkal, mint az IKO-ban. SNARK-jait a manapság az 1. rangú kényszerkielégítés (R1CS) problémáinak kontextusában írta le, ami az aritmetikai áramkörök kielégíthetőségének általánosítása.

Ez a tanulmány egyben elméleti alapjául is szolgált az első SNARK-oknak, amelyek kereskedelmi forgalomba kerültek (pl. ZCash-ben), és közvetlenül vezetett a ma is népszerű SNARK-okhoz (pl. Groth16). A GGPR argumentumainak kezdeti megvalósítása bejött zaatarral és a Pinokkió, és a későbbi változatok közé tartozik SNARK-ok C-nek és a BCTV. BCIOP egy általános keretet adott, amely megvilágítja ezeket a lineáris PCP-től SNARK-ig transzformációkat (lásd még az A függeléket zaatarral), és leírja annak különböző példányait.

A párosításon alapuló nem interaktív argumentumok méretéről (2016)
írta: Jens Groth

Ez a köznyelvben Groth16 néven emlegetett cikk a GGPR SNARK-jainak egy olyan finomítását mutatta be, amely ma is a legkorszerűbb konkrét hitelesítési költségeket biztosítja (a bizonyítások 3 csoportelemből állnak, és a hitelesítést három párosítási művelet uralja, legalábbis a nyilvánosságot feltételezve a bevitel rövid). A biztonságot az általános csoportmodell bizonyítja.

SNARK-ok univerzális megbízható beállítással

PlonK: Permutációk a Lagrange-alapokon a tudás ökumenikus, nem interaktív érveihez (2019)
írta: Ariel Gabizon, Zachary Williamson és Oana Ciobotaru

Marlin: zkSNARK-ok előfeldolgozása univerzális és frissíthető SRS-sel (2019)
Írta: Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely és Nicholas Ward

Mind a PlonK, mind a Marlin lecseréli a Groth16 áramkör-specifikus megbízható beállítását egy univerzális beállításra. Ez 4x-6x nagyobb bizonyítás rovására megy. Elképzelhető, hogy a PlonK és a Marlin elvégzi az áramkör-specifikus munkát a Groth16 és az elődök megbízható beállítása során, és áthelyezi azt egy előfeldolgozási fázisba, amely megtörténik. után a megbízható beállítás, valamint a SNARK proof-generálás során.

Az önkényes áramkörök és R1CS-rendszerek ilyen módon történő feldolgozásának képességét néha holográfiás vagy számítási kötelezettségvállalásnak nevezik, és le is írják spártai (az összeállítás későbbi részében lesz szó róla). Mivel több munka történik a próbagenerálás során, a PlonK és a Marlin proversei lassabbak, mint a Groth16 egy adott áramkör vagy R1CS példány esetében. A Groth16-tól eltérően azonban a PlonK és a Marlin általánosabb köztes reprezentációkkal is működhet, mint az R1CS.

Polinom elkötelezettségi sémák, kulcsfontosságú kriptográfiai primitív a SNARK-okban

Állandó méretű kötelezettségvállalások polinomokhoz és alkalmazásaikhoz (2010)
Írta: Aniket Kate, Gregory Zaverucha és Ian Goldberg

Ez a cikk bemutatta a polinomiális kötelezettségvállalási sémák fogalmát. Sémát adott az egyváltozós polinomokhoz (általános nevén KZG kötelezettségvállalásokhoz), állandó méretű kötelezettségvállalásokkal és kiértékelési bizonyítással. A séma megbízható beállítást (azaz strukturált hivatkozási karakterláncot) és párosításon alapuló titkosítást használ. A gyakorlatban ma is rendkívül népszerű, és a SNARK-okban használják, beleértve a fentebb tárgyalt PlonK-t és Marlint (a Groth16 pedig rendkívül hasonló kriptográfiai technikákat használ).

Gyors Reed-Solomon interaktív Oracle Proofs of Proximity (2017)
szerző: Eli Ben-Sasson, Iddo Bentov, Ynon Horesh, Michael Riabzev

Interaktív oracle proof-ot (IOP) ad a Reed-Solomon teszteléshez – vagyis annak bizonyítására, hogy egy lekötött karakterlánc közel áll egy egyváltozós polinom kiértékelő táblázatához. Merkle-hashinggel és a Fiat-Shamir transzformációval kombinálva ez egy transzparens polinomiális kötelezettségvállalási sémát eredményez polilogaritmikus méretű kiértékelési bizonyítványokkal (lásd VP19 a részletekért). Ma ez a legrövidebb a valószínűen posztkvantumpolinomiális kötelezettségvállalási sémák között.

Ligero: Könnyű szublineáris érvek megbízható beállítás nélkül (2017)
írta: Scott Ames, Carmit Hazay, Yuval Ishai és Muthuramakrishnan Venkitasubramaniam

Hasonlóan a FRI-hez, ez a munka IOP-t ad a Reed-Solomon teszthez, de négyzetgyök-ellenőrző hosszúsággal, nem pedig polilogaritmikussal. Elméleti művek megmutatta, hogy a Reed-Solomon kódot egy másik, gyorsabb kódolású hibajavító kódra cserélve egy lineáris idejű bizonyítást kaphatunk, amely ráadásul natív módon működik bármely mezőn. Ezt a megközelítést finomították és alkalmazták ben Lefékezés és a Orion, ami a legmodernebb bizonyítási teljesítményt nyújtja.

Golyóálló: rövid bizonyítékok bizalmas tranzakciókhoz és egyebek (2017)
írta: Benedikt Bunz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille és Greg Maxwell

Korábbi munkák finomítása által BCCGPA Bulletproofs átlátszó polinom elkötelezettségi sémát ad (valójában egy általánosítást, amelyet belső szorzatargumentumnak neveznek), amely a diszkrét logaritmusok kiszámításának keménységén alapul, logaritmikus bizonyítási mérettel, de lineáris ellenőrző idővel. A séma ma is népszerű az átláthatósága és a rövid proofok miatt (pl. a ZCash Orchardban és a Moneroban használatos).

Dory: Hatékony, átlátható érvek az általánosított belső termékek és polinomiális kötelezettségvállalások mellett (2020)
írta: Jonathan Lee

A Dory a Bulletproofs ellenőrző idejét lineárisról logaritmikusra csökkenti, miközben megőrzi az átlátszóságot és a logaritmikus méretű (bár konkrétan nagyobb, mint a golyóállók) és az átlátszóságot. Párosítást használ, és az SXDH feltételezésen alapul.

Interaktív bizonyítások, több próbát használó interaktív bizonyítványok és a kapcsolódó SNARK-ok

Számítás delegálása: Interaktív bizonyítékok mugliknak (2008)
Shafi Goldwasser, Yael Tauman Kalai és Guy Rothblum

Ezt a dolgozatot megelőzően általános célú interaktív bizonyításra volt szükség a szuperpolinom-idő bizonyító. Ez a cikk interaktív bizonyítási protokollt ad, amelyet általában GKR-protokollnak neveznek, polinomiális időellenőrzővel és kvázilineáris időellenőrzővel minden olyan problémára, amely hatékony párhuzamos algoritmussal rendelkezik (az interaktív bizonyítás minden kis mélységű aritmetikai áramkörre vonatkozik).

Gyakorlati ellenőrzött számítás streaming interaktív bizonyítással (2011)
írta: Graham Cormode, Michael Mitzenmacher, Justin Thaler

Ez a papír (néha CMT-nek is nevezik) a GKR-protokollban a bebizonyítási időt az áramkör kvartikus méretéről kvázilineárisra csökkentette. Elkészítette egy általános célú interaktív bizonyíték első megvalósítását. A következő munkák sora (Vegyesfűszer, Thaler13, Zsiráfés Libra) tovább csökkentette a prover futási idejét, kvázilineárisról lineárisra az áramkör méretét tekintve.

vSQL: Tetszőleges SQL-lekérdezések ellenőrzése dinamikus kiszervezett adatbázisokon keresztül (2017)
írta: Yupeng Zhang, Daniel Genkin, Jonathan Katz, Dimitrios Papadopoulos és Charalampos Papamanthou

Bár a cím egy konkrét alkalmazási területre (adatbázisokra) utal, a jelen cikk hozzájárulásai általánosabbak. Pontosabban azt figyelte meg, hogy az interaktív bizonyítások és a polinomiális kötelezettségvállalási sémák (multilineáris polinomok esetén) kombinálásával tömör érveket kaphatunk az áramkör kielégíthetőségére.

Később művek kiolvasztott az argumentumok nulla tudást, és különböző kötelezettségvállalási sémákat vezettek be többlineáris polinomokhoz.

Spartan: Hatékony és általános célú zkSNARK-ok megbízható beállítás nélkül (2019)
írta Srinath Setty

SNARK-okat kap az áramkör-kielégítéshez és az R1CS-hez a többpróbás interaktív bizonyítások (MIP) és polinomiális kötelezettségvállalási sémák kombinálásával, a konkrétan hatékony MIP-eken, az ún. Lóhere. A hatás az, hogy a SNARK-okat rövidebb bizonyítással kapjuk meg, mint azok, amelyek az interaktív bizonyításokból származnak, mint például a fent tárgyalt GKR protokoll. A PlonK-hoz és a Marlinhoz hasonlóan a Spartan azt is bemutatja, hogyan lehet tetszőleges áramköröket és R1CS rendszereket feldolgozni előfeldolgozáson és SNARK-ellenőrzésen keresztül.

Spartan polinomiális kötelezettségvállalási sémát használt hyrax. A későbbi munkák ún Lefékezés és a Orion kombinálja a Spartan MIP-jét más polinomiális kötelezettségvállalási sémákkal, hogy megkapja az első megvalósított SNARK-okat lineáris idejű bizonyítóval.

Rövid PCP-k és IOP-k

Rövid PCP-k Polylog Query Complexitással (2005)
Eli Ben-Sasson és Madhu Sudan

 Ez az elméleti munka megadta az első valószínűségileg ellenőrizhető bizonyítást (PCP), amelynek bizonyítási hossza kvázilineáris az igazolandó számítás méretében és polilogaritmikus lekérdezési költségében (bár lineáris verifikációs idő). A PCP-k SNARK-okká való Kilian-Micali átalakítását követően ez egy lépés volt a kvázi lineáris időellenőrzővel és polilogaritmikus időellenőrzővel rendelkező SNARK-ok felé.

Később elméleti munka az ellenőrző időt polilogaritmikusra csökkentette. Későbbi a gyakorlatiasságra összpontosító munka finomította ezt a megközelítést, de a rövid PCP-k ma is kivitelezhetetlenek. A gyakorlati SNARK-ok megszerzéséhez, a későbbiekben művek fordult nak nek nevű interaktív általánosítása a PCP-knek Interaktív Oracle Proofs (IOP). Ezek az erőfeszítések oda vezettek, és tovább építettek INGYENES, egy népszerű polinomiális kötelezettségvállalási séma, amelyet a jelen összeállítás polinomiális kötelezettségvállalások részében tárgyalunk.

Az ebbe a kategóriába tartozó további művek közé tartozik ZKBoo és leszármazottai. Ezek nem érnek el tömör bizonyítást, de jó konstans tényezőik vannak, ezért vonzóak kis állítások bizonyítására. Olyan posztkvantum aláírások családjaihoz vezettek, mint pl Piknik amelyek óta optimalizált in számos művek. A ZKBoo egy különálló tervezési paradigmát követ, az úgynevezett MPC-in-the-head, de IOP-t ad.

Rekurzív SNARK-ok

A fokozatosan ellenőrizhető számítások vagy a tudás bizonyítása idő/térhatékonyságot jelent (2008)
írta Paul Valiant

Ez a munka bevezette az inkrementálisan verifikálható számítás (IVC) alapfogalmát, amelyben a bizonyító lefuttat egy számítást, és mindenkor bizonyítja, hogy az eddigi számítások helyesek voltak. Az IVC-t SNARK-ok rekurzív összetételével építette meg. Itt, a tudás-helyesség A SNARK-ok tulajdonsága elengedhetetlen a rekurzív módon összeállított, nem interaktív argumentumok megalapozottságának megállapításához. Ez a cikk egy rendkívül hatékony tudáskinyerőt is adott a PCP-eredetű SNARK-okhoz (a Kilian-Micali paradigma szerint).

Skálázható nulla tudás az elliptikus görbék ciklusain keresztül (2014)
Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer és Madars Virza

Következő elméleti munka, ez a cikk a GGPR SNARK egy változatának rekurzív alkalmazását használta, hogy biztosítsa az IVC első megvalósítását egy egyszerű virtuális géphez (TinyRAM, a SNARK-ok C-nek papír).

Bevezette az elliptikus görbék ciklusainak fogalmát is, amelyek hasznosak az elliptikus görbe kriptográfiáját használó SNARK-ok rekurzív összeállításához.

Rekurzív bizonyítási kompozíció megbízható beállítás nélkül (2019)
szerző: Sean Bowe, Jack Grigg és Daira Hopwood

Ez a munka (az úgynevezett Halo) azt tanulmányozza, hogyan lehet rekurzívan összeállítani transzparens SNARK-okat. Ez nagyobb kihívást jelent, mint a nem átlátszóak összeállítása, mivel az átlátszó SNARK-okban az ellenőrzési eljárás sokkal drágább lehet.

Ez aztán kiváltotta a vonal of munka amely olyan rendszerekben csúcsosodott ki, mint pl Nova a legkorszerűbb IVC-teljesítmény elérése, amely még a nem átlátszó SNARK-ok, például a Groth16 összeállításával elért teljesítménynél is jobb.

Alkalmazási területek

Zerocash: Decentralizált névtelen fizetések Bitcoinról (2014)
szerző: Eli Ben Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, Madars Virza

Korábbi munkára építve, beleértve zerocoin (és Pinnochio érme párhuzamos munkaként), ez a cikk GGPR-eredetű SNARK-okat használ egy privát kriptovaluta tervezésére. ZCashhez vezetett.

Geppetto: Sokoldalú, ellenőrizhető számítás (2014)
szerző: Craig Costello, Cédric Fournet, Jon Howell, Markulf Kohlweiss, Benjamin Kreuter, Michael Naehrig, Bryan Parno és Samee Zahur

A Geppetto vitathatatlanul megelőzte a privát intelligens szerződések végrehajtása iránti érdeklődés robbanásszerű növekedését, mivel nagyjából egy évvel az Ethereum létrehozása után íródott. Ezért nem kerül bemutatásra az intelligens magánszerződések végrehajtásával összefüggésben. Mindazonáltal a SNARK-ok korlátos mélységű rekurzióját használja, hogy lehetővé tegye egy megbízhatatlan bizonyító számára, hogy bármilyen privát (elkötelezett/aláírt) számítógépes programot végrehajtson privát adatokon anélkül, hogy felfedne információkat a futó programról vagy azokról az adatokról, amelyeken fut. Ennek megfelelően a privát smart-contract platformokon végzett munka elődje, mint pl Zexe [az alábbiakban leírt].

Ellenőrizhető ASIC-ek (2015)
szerző: Riad Wahby, Max Howald, Siddharth Garg, abhi shelat, Michael Walfish

Ez a cikk azt a problémát vizsgálja, hogyan lehet biztonságosan és eredményesen használni egy nem megbízható öntödében gyártott ASIC-et (2015-ben mindössze öt nemzet volt csúcskategóriás öntödével). A megközelítés az, hogy a gyors, de nem megbízható ASIC bizonyítja kimenetének helyességét egy lassabb, de megbízható ASIC-en futó ellenőrzőnek. A megoldás mindaddig érdekes, amíg a rendszer teljes végrehajtási ideje (azaz a bevizsgáló és ellenőrző futási idők összege plusz az esetleges adatátviteli költségek) kisebb, mint a naiv alapvonal: a számítás teljes futtatásához szükséges idő a lassabb rendszeren. - de megbízható ASIC. A GKR/CMT/szegfűbors interaktív bizonyítások egy változatát használva a papír valóban felülmúlja a naiv alapvonalat számos alapvető probléma tekintetében, beleértve a számelméleti transzformációkat, a mintaillesztést és az elliptikus görbe műveleteit. Ez a munka azt sugallja, hogy egyes próbarendszerek alkalmasabbak hardveres megvalósításra, mint mások. A próbarendszerek optimalizálása a hardveres implementációhoz most már folyamatban van tekintélyes figyelem, de még sok a felfedeznivaló.

Igazolható Késleltetési funkciók (2018)
írta: Dan Boneh, Joseph Bonneau, Benedikt Bünz és Ben Fisch

Bevezette az igazolható késleltetési függvények (VDF) jelölését, egy kriptográfiai primitívet, amely széles körben hasznos a blokklánc alkalmazásokban, például a tét-bizonyítási konszenzus protokollok lehetséges manipulációinak enyhítésében. A SNARK-ok (különösen a növekményesen ellenőrizhető számításokhoz) utat kínálnak a legmodernebb VDF-ekhez.

Zexe: A decentralizált magánszámítás engedélyezése (2018)
szerző: Sean Bowe, Alessandro Chiesa, Matthew Green, Ian Miers, Pratyush Mishra és Howard Wu

A Zexe egy privát intelligens szerződéses platformhoz készült design. A Zexe a Zerocash (fentebb leírt) kiterjesztéseként tekinthető. A Zerocash lehetővé teszi egyetlen alkalmazás futtatását a láncon belül (lehetővé teszi a felhasználók számára tokenek átvitelét), miközben védi a felhasználói adatok titkosságát, pl. hogy kinek küldenek tokeneket, kitől kapnak tokeneket, mennyi tokent küldenek, stb. A Zexe sok lehetőséget tesz lehetővé. különböző alkalmazások (intelligens szerződések), amelyek ugyanazon a blokkláncon futnak, és kölcsönhatásba lépnek egymással. A tranzakciókat a láncon kívül hajtják végre, és a helyes végrehajtás igazolásait a láncon közzéteszik. Nem csak az adatok védelme, hanem a funkciók védelme is. Ez azt jelenti, hogy az egyes tranzakciókhoz tartozó bizonyítékok még azt sem árulják el, hogy a tranzakció mely alkalmazás(ok)ra vonatkozik. A Zexe általánosabb mérnöki hozzájárulása az, hogy bevezette a BLS12-377-et, egy elliptikus görbecsoportot, amely hasznos a párosításon alapuló SNARK-ok hatékony mélység-1 összeállításához.

Replikált állapotú gépek replikált végrehajtás nélkül (2020)
Jonathan Lee, Kirill Nikitin és Srinath Setty

Ez azon kevés akadémiai dolgozatok egyike, amelyek a blokklánc skálázhatóságának összesítésével foglalkoznak. Nem használja a rollups kifejezést, mert megelőzi vagy egyidős azzal a fogalommal, amelyet a szakirodalomon kívül vezettek be.

Kezelőfelületek (hatékony átalakítások számítógépes programokból köztes megjelenítésekké, például áramkör-kielégítés, R1CS stb.)

Gyors csökkentés a RAM-okról a delegálható tömör korlátozások elégedettségi problémáira (2012)
Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin és Eran Tromer

Modern szemszögből nézve ez egy korai munka a virtuális gép (VM) absztrakciójához szükséges gyakorlati számítógép-program-áramkör-SAT transzformációkról. Az 1970-es évek végétől az 1990-es évekig terjedő alkotásokra építve (pl Robson) ez a cikk egy determinisztikus csökkentést ír le egy T lépéses virtuális gép végrehajtásától az O(T*polylog(T)) méretű áramkör kielégíthetőségéig.

Későbbi papírok, pl. SNARK-ok C-nek és a BCTV, folytatta a frontendek fejlesztését egy virtuális gép absztrakción keresztül, és a modern példányosítások között olyan projektek is szerepelnek, mint pl. Kairó, RISC Zeroés Sokszög Miden.

A bizonyítási alapú ellenőrzött számítás néhány lépéssel közelebb kerül a gyakorlatiassághoz (2012)
Srinath Setty, Victor Vu, Nikhil Panpalia, Benjamin Braun, Muqeet Ali, Andrew J. Blumberg és Michael Walfish

Ez a Ginger néven emlegetett dokumentum egy újabb korai hozzájárulás a gyakorlati front-end technikákhoz. A Ginger modulokat mutatott be az általános programozási primitívekhez, például a feltételes feltételekhez és a logikai kifejezésekhez, az összehasonlításhoz és a bitenkénti aritmetikához bitfelosztással, primitív lebegőpontos aritmetikával stb. Ezeket a modulokat használta arra, hogy a magas szintű nyelvtől az alacsony fokú nyelvig az első implementált felületet biztosítsa. aritmetikai megszorítások (hasonlóan a ma R1CS néven ismerthez), egy köztes reprezentáció (IR), amelyre SNARK-háttér alkalmazható.

Míg a „Fast Reductions” papír és leszármazottai „CPU-emulátor” megközelítést használnak az IR-ek létrehozása során (azaz az IR kikényszeríti, hogy a bizonyító helyesen fusson le egy adott programot azáltal, hogy a CPU átmeneti függvényét alkalmazza meghatározott számú lépésre) , Ginger és leszármazottai inkább ASIC-szerű megközelítést alkalmaznak, és olyan IR-ket állítanak elő, amelyek a számítógépes programhoz vannak szabva, amelyet a bizonyító állítása szerint helyesen hajt végre.

Például, Büfé azt mutatja, hogy az ASIC modellben lehetséges az összetett vezérlési folyamatok kezelése azáltal, hogy az ilyen vezérlési folyamatokat a végrehajtott programra szabott véges állapotú géppé alakítják, és ez a megközelítés lényegesen hatékonyabb lehet, mint egy általános célú CPU-emulátor felépítése. xJsnark hatékony konstrukciót ad több pontosságú aritmetikához, RAM-ok és ROM-ok optimalizálásához, és egy Java-szerű, magas szintű nyelvet tesz a programozó elé, amely ma is népszerű. CirC megjegyzi, hogy a számítógépes programok R1CS-be fordítása szorosan kapcsolódik a programelemzésből jól ismert technikákhoz, és létrehoz egy fordítóépítő eszközkészletet, amely mindkét közösség ötleteit tartalmazza („LLVM áramkörszerű ábrázolásokhoz”). A korábbi munkák, amelyek hozzájárultak az ASIC-stílusú kezelőfelületekhez Pinokkió és a Geppetto.

A „Fast-Reductions” lap egy bonyolult és költséges konstrukciót, az úgynevezett „routing networks” ún. memória-ellenőrzés (azaz annak biztosítása, hogy a nem megbízható hitelesítő megfelelően karbantartja a virtuális gép véletlen elérésű memóriáját annak a virtuális gépnek a végrehajtása során, amelynek helyességét igazolják). Azért esett erre a választásra, mert az olyan korai munkák, mint amilyen ez is, PCP megszerzésére törekedtek, ami megkövetelte, hogy a front-end mindkét nem interaktív és információelméletileg biztonságos. Későbbi munka hívott Éléskamra (elődje a Büfé fent említett munkája) Merkle-fákat használt az útválasztási hálózatok helyett, a hatékonyságot algebrai (azaz „SNARK-barát”) hash függvény összeállításával érve el, mivel Ajtai, korlátokba. Ez „számításilag biztonságos” front-endeket eredményezett. Napjainkban széles körű kutatási irodalom áll rendelkezésre a SNARK-barát hash-függvényekről, példákkal Poseidon, MiMC, Vasbeton, Mentés, És így tovább.

A legkorszerűbb technikák annak biztosítására, hogy a vizsgáló megfelelően karbantartsa a RAM-ot, az úgynevezett „permutáció-invariáns ujjlenyomat-vételi” módszerekre támaszkodnak, amelyek legalább XNUMX óta Lipton (1989) és memória-ellenőrzésre használta Blum és mtsai. (1991). Ezek a technikák eredendően magukban foglalják a bizonyító és a hitelesítő közötti interakciót, de a Fiat-Shamir transzformációval interaktívvá tehetők. Tudomásunk szerint egy ún. VRAM.

A permutáció-invariáns ujjlenyomat-vételi technikákat ma már számos előtérben és SNARK-ban használják virtuálisgép-absztrakciókhoz, beleértve pl. Kairó. A szorosan összefüggő gondolatok egymáshoz kapcsolódó kontextusban újra megjelentek az alábbi két műben, melyeket ma már széles körben alkalmaznak a gyakorlatban.

Közel lineáris idejű nulla tudású bizonyítékok a program helyes végrehajtásához (2018)
Írta: Jonathan Bootle, Andrea Cerulli, Jens Groth, Sune Jakobsen és Mary Maller

Plookup: Egy egyszerűsített polinomiális protokoll keresőtáblákhoz (2020)
Írta: Ariel Gabizon és Zachary Williamson

A front-end-eken végzett korai munkák „nem aritmetikus” műveleteket (például tartomány-ellenőrzéseket, bitenkénti műveleteket és egész számok összehasonlítását) képviselték az áramkörökön és a kapcsolódó IR-eken belül azáltal, hogy a mezőelemeket bitekre bontották, ezeken a biteken hajtották végre a műveleteket, majd „csomagolták”. az eredményt vissza egyetlen mezőelembe. Az eredményül kapott áramkör méretét tekintve ez műveletenként logaritmikus többletköltséget eredményez.

A fenti két munka (BCGJM és Plookup) hatásos technikákat ad (ún. „lookup table” alapján) ezeknek a műveleteknek az áramkörökön belüli, amortizált értelemben történő hatékonyabb ábrázolására. Durván szólva, a front-end tervező által választott bizonyos B paraméterek esetében ezek egy B-beli logaritmikus tényezővel csökkentik azoknak a kapuknak a számát, amelyek az áramkörben az egyes nem aritmetikai műveletek megjelenítéséhez szükségesek, annak az árán, hogy a hitelesítő kriptográfiailag elkötelezi magát egy pluszra. nagyjából B hosszúságú „tanács” vektor.