Kanon zerowej wiedzy

Komentarz edytora: a16z crypto ma długą serię „pistolety", z naszego Kanon DAO w zeszłym roku do naszego Kanon NFT wcześniej (a wcześniej nasz oryginał Kanon kryptograficzny) — koniecznie zapisz się do naszego cotygodniowy biuletyn web3 aby uzyskać więcej aktualizacji, a także inne wyselekcjonowane zasoby.

Szlochponiżej, wybraliśmy zestaw zasobów dla tych, którzy chcą zrozumieć, zagłębić się i budować ze wszystkich rzeczy zero wiedzy: potężne, fundamentalne technologie, które są kluczem do skalowalności łańcucha bloków i reprezentują przyszłość aplikacji chroniących prywatność oraz niezliczonych innych przyszłych innowacji. Jeśli masz sugestie dotyczące elementów wysokiej jakości do dodania, daj nam znać @a16zcrypto.

Systemy odporne na wiedzę zerową istnieją od dziesięcioleci: ich wprowadzenie przez Shafiego Goldwassera, Silvio Micali i Charlesa Rackoffa w 1985 r. 2012. Ponieważ ta praca — w tym jej przejście od teorii do praktyki i dzisiejszych zastosowań w crypto/web3 — była tworzona przez dziesięciolecia, po raz pierwszy udostępniamy również w naszej serii kanonów część drugą (na razie uwzględnioną tutaj poniżej): lista lektur z adnotacją Justin Talar, zgodnie z częścią pierwszą poniżej.

Podziękowania: Dziękuję również Michaelowi Blau, Samowi Ragsdale i Timowi Roughgarden.

Fundamenty, tło, ewolucje

Niektóre z tych artykułów dotyczą również ogólnie kryptografii (nie wszystkie informacje o zerowej wiedzy per se), w tym opisują problemy lub kluczowe postępy, którymi obecnie zajmują się dowody zerowej wiedzy: jak zapewnić prywatność i uwierzytelnianie w otwartych sieciach.

Nowe kierunki w kryptografii (1976)
autorstwa Whitfielda Diffie i Martina Hellmana
https://ee.stanford.edu/~hellman/publications/24.pdf

Metoda uzyskiwania podpisów cyfrowych i kryptosystemów klucza publicznego
autorstwa Ronalda Rivesta, Adi Shamira, Leonarda Adelmana
https://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=856E21BC2F75800D37FD611032C30B9C?doi=10.1.1.40.5588&rep=rep1&type=pdf

Protokoły dla kryptosystemów klucza publicznego (1980)
przez Ralpha Merkle
http://www.merkle.com/papers/Protocols.pdf

Bezpieczna komunikacja przez niezabezpieczone kanały (1978)
przez Ralpha Merkle
https://www.merkle.com/1974/PuzzlesAsPublished.pdf

Wykorzystanie krzywych eliptycznych w kryptografii (1988)
autorstwa Victora Millera
https://link.springer.com/content/pdf/10.1007%2F3-540-39799-X_31.pdf

Złożoność wiedzy interaktywnych systemów dowodowych (1985)
Shafi Goldwasser, Silvio Micali, Charles Rackof
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.419.8132&rep=rep1&type=pdf

Dowody dźwiękowe obliczeniowo (2000)
przez Silvio Micali
https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/Computationally_Sound_Proofs.pdf

Od ekstrahowalnej odporności na kolizje do zwięzłych, nieinteraktywnych argumentów wiedzy [SNARKs] i z powrotem (2011)
autorzy: Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer
https://eprint.iacr.org/2011/443.pdf

Skuteczny argument z wiedzą zerową za poprawność przetasowania (2012)
autorstwa Stephanie Bayer i Jensa Grotha
http://www0.cs.ucl.ac.uk/staff/J.Groth/MinimalShuffle.pdf

Zwięzła nieinteraktywna wiedza zerowa dla architektury von Neumanna (2013)
Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer i Madars Virza
https://eprint.iacr.org/2013/879.pdf

Skalowalna, przejrzysta i postkwantowa bezpieczna integralność obliczeniowa (2018)
Eli Ben-Sasson, Iddo Bentov, Yinon Horesh i Michael Riabzev
https://eprint.iacr.org/2018/046.pdf

Argumenty o zerowej wiedzy publicznej monety z (prawie) minimalnymi kosztami ogólnymi czasu i przestrzeni (2020)
autorstwa Alexandra Blocka, Justina Holmgrena, Alona Rosena, Rona Rothbluma i Pratika Soni
https://www.iacr.org/cryptodb/data/paper.php?pubkey=30645

Przeglądy i wprowadzenie

Dowody, argumenty i wiedza zerowa — przegląd weryfikowalnych obliczeń i interaktywnych dowodów i argumentów, protokołów kryptograficznych, które umożliwiają dowodzącemu zapewnienie weryfikatorowi, że prawidłowo wykonał żądane obliczenia, w tym wiedzę zerową (w przypadku gdy dowody nie ujawniają żadnych innych informacji poza swoją własną ważnością). . Argumenty Zk mają mnóstwo zastosowań w kryptografii i w ciągu ostatniej dekady przeskoczyły z teorii do praktyki.
przez Justina Thalera
https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf

Ewolucja modeli dowodów z wiedzą zerową — Przegląd dowodów z wiedzą zerową, w którym Meiklejohn (University College London, Google) przygląda się aplikacjom, które napędzają ich rozwój, różnym modelom, które pojawiły się w celu uchwycenia tych nowych interakcji, konstrukcjom, które możemy osiągnąć, oraz pracy do zrobienia.
autorstwa Sarah Meiklejohn
https://www.youtube.com/watch?v=HO97kVMI3SE

Sesje tablicy ZK — moduły wprowadzające
z Danem Boneh i in
https://zkhack.dev/whiteboard/

Bezpieczeństwo i prywatność dla krypto z zkps — pionierskie zastosowanie dowodu wiedzy zerowej w praktyce; czym są zkps i jak działają… w tym „demo” na żywo
przez Zooko Wilcox
https://a16z.com/2019/08/29/security-and-privacy-for-crypto-with-zero-knowledge-proofs/

Wyjaśnienie najważniejszych tematów technicznych — łącznie z definicjami i implikacjami wiedzy zerowej w ogóle
autorzy: 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

Jak nadchodząca warstwa prywatności naprawi zepsutą sieć?
autor: Howard Wu
https://future.com/a-privacy-layer-for-the-web-can-change-everything/

Wprowadzenie do zkSNARKs
z Howardem Wu, Anną Rose
https://zeroknowledge.fm/38-2/

Dlaczego i jak działa zk-SNARK: ostateczne wyjaśnienie
Maksym Petkus
https://arxiv.org/pdf/1906.07221.pdf

Wprowadzenie do dowodów z wiedzą zerową
autorstwa Fredrika Harryssona i Anny Rose
https://www.zeroknowledge.fm/21 [+ podsumowanie w innym miejscu tutaj]

Zk-SNARKs: pod maską
autorstwa Vitalika Buterina
https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
część 1, część 2, część 3

Zdecentralizowana prędkość — o postępach w zerowych dowodach wiedzy, zdecentralizowanym sprzęcie
przez Elenę Burger
https://a16z.com/2022/04/15/zero-knowledge-proofs-hardware-decentralization-innovation/

Najnowocześniejsze badania zk — z badaczem zk w Fundacji Ethereum
z Mary Maller, Anną Rose, Kobi Gurkan
https://zeroknowledge.fm/232-2/

Odkrywanie badań zk — z dyrektorem ds. badań w DFINITY; także za postępami takimi jak Groth16
z Jensem Grothem, Anną Rose, Kobi Gurkan
https://zeroknowledge.fm/237-2/

Badania i pedagogika SNARK — z jednym ze współzałożycieli ZCash i Starkware
z Alessandro Chiesą, Anną Rose
https://zeroknowledge.fm/episode-200-snark-research-pedagogy-with-alessandro-chiesa/

Nurkowania głębokie, przewodniki dla budowniczych

Podstawy dowodów probabilistycznych — kurs z 5 jednostkami z interaktywnych dowodów i nie tylko
autorstwa Alessandro Chiesy
https://www.youtube.com/playlist?list=PLGkwtcB-DfpzST-medFVvrKhinZisfluC

STARKs — część I, II, III
autorstwa Vitalika Buterina
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

Anatomia STARKA — sześcioczęściowy samouczek wyjaśniający mechanikę systemu dowodowego STARK
przez Alana Szepieniec
https://aszepieniec.github.io/stark-anatomy/

Projekt SNARK, część 1 — ankieta, wykorzystanie w rollupach, więcej
przez Justina Thalera
https://www.youtube.com/watch?v=tg6lKPdR_e4

Projekt SNARK, część 2 — rollupy, wydajność, bezpieczeństwo
przez Justina Thalera
https://www.youtube.com/watch?v=cMAI7g3UcoI

Pomiar wydajności SNARK — frontendy, backendy, więcej
przez Justina Thalera
https://a16zcrypto.com/measuring-snark-performance-frontends-backends-and-the-future/

Zrozumieć PLONK
https://vitalik.ca/general/2019/09/22/plonk.html

System dowodu wiedzy o zerowej wiedzy PLONK — seria 12 krótkich filmów o tym, jak działa PLONK
autorstwa Davida Wong
https://www.youtube.com/playlist?list=PLBJMt6zV1c7Gh9Utg-Vng2V6EYVidTFCC

Od AIR do RAP — jak działa arytmetyka w stylu PLONK
autor: Ariel Gabizon
https://hackmd.io/@aztec-network/plonk-arithmetiization-air

Kontrole wielozestawowe w PLONK i Plookup
autor: Ariel Gabizon
https://hackmd.io/@arielg/ByFgSDA7D

Projekt Halo2 — z ECC
https://zcash.github.io/halo2/design.html

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

Aplikacje i samouczki: weryfikacja koncepcji, prezentacje, narzędzia, więcej

Zastosowano zk - Zasoby edukacyjne
przez 0xPARC
https://learn.0xparc.org/materials/intro

Środowisko programistyczne online dla zkSNARKs — zkREPL, nowy zestaw narzędzi do interakcji z zestawem narzędzi Circom w przeglądarce
autor: Kevin Kwok
https://zkrepl.dev (+ wątek wyjaśniający tutaj)

Programy arytmetyczne kwadratowe od zera do bohatera
autorstwa Vitalika Buterina
https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

Na zkEVMs
z Alexem Gluchowskim i Anną Rose
https://zeroknowledge.fm/175-2/

Różne typy zkEVM
autorstwa Vitalika Buterina
https://vitalik.ca/general/2022/08/04/zkevm.html

Uczenie maszynowe ZK — samouczek i demo dotyczące umieszczania sieci neuronowej w SNARK
Horace Pan, Francis Ho i Henri Palacci
https://0xparc.org/blog/zk-mnist

W językach ZK
z Alexem Ozdemirem i Anną Rose
https://zeroknowledge.fm/172-2/

Dark Forest — zastosowanie kryptografii zk do gier — w pełni zdecentralizowana i trwała gra RTS (strategia czasu rzeczywistego)
https://blog.zkga.me/announcing-darkforest

ZKP dla inżynierów — spojrzenie na ZKP Mroczny Las
https://blog.zkga.me/df-init-circuit

Nurkowanie w zerowej wiedzy
z Eleną Nadolinską, Anną Rose, Jamesem Prestwich
https://zeroknowledge.fm/182-2/

zkDocs: Udostępnianie informacji o zerowej wiedzy
autorzy Sam Ragsdale i Dan Boneh
https://a16zcrypto.com/zkdocs-zero-knowledge-information-sharing/

Chroniące prywatność krypto airdropy z zerowymi dowodami wiedzy
autor: Sam Ragsdale
https://a16z.com/2022/03/27/crypto-airdrop-privacy-tool-zero-knowledge-proofs/

Ceremonie zaufanej konfiguracji na łańcuchu -
Valeria Nikolaenko i Sam Ragsdale
https://a16zcrypto.com/on-chain-trusted-setup-ceremony/

Przepisy dotyczące kryptowalut, nielegalne finansowanie, prywatność i nie tylko – zawiera sekcję dotyczącą wiedzy zerowej w kontekście przepisów/zgodności; różnica między technologiami „zachowującymi prywatność” a technologiami zaciemniającymi
z Michele Korver, Jai Ramaswamy, Sonal Chokshi
https://web3-with-a16z.simplecast.com/episodes/crypto-regulations-sanctions-compliance-aml-ofac-news-explained

Inne zasoby

biuletyn zkMesh — comiesięczny biuletyn udostępniający najnowsze zdecentralizowane technologie ochrony prywatności, rozwój protokołów prywatności i systemy zerowej wiedzy
https://zkmesh.substack.com/

Podcast o zerowej wiedzy — na temat najnowszych badań zk i aplikacji zk oraz ekspertów budujących technologię prywatności z obsługą kryptografii
z Anną Rose
https://zeroknowledge.fm/

…lista lektur z adnotacjami, według tematu i chronologii, autorstwa Justina Thalera:

SNARKs z Linear PCP (inaczej SNARKs z konfiguracją specyficzną dla obwodu)

Skuteczne argumenty bez krótkich PCP (2007)
Yuval Ishai, Eyal Kushilevitz i Rafail Ostrovsky

Przed około 2007 r. SNARKi były projektowane głównie przez Kilian-mikali paradygmatu polegającego na wzięciu „krótkiego” dowodu, który można sprawdzić probabilistycznie (PCP) i „kryptograficznej kompilacji” go w zwięzły argument za pomocą mieszania Merkle i transformacji Fiata-Shamira. Niestety krótkie PCP są skomplikowane i niepraktyczne nawet dzisiaj. Ten artykuł (IKO) pokazał, jak używać homomorficznego szyfrowania do uzyskania zwięzłych (nieprzejrzystych) interaktywnych argumentów z „długich, ale ustrukturyzowanych” PCP. Mogą być znacznie prostsze niż krótkie PCP, a wynikowe SNARK mają znacznie krótsze dowody i szybszą weryfikację. Argumenty te zostały po raz pierwszy uznane za mające potencjał praktycznej wydajności, a następnie dopracowane i wdrożone w Pepper. Niestety, argumenty IKO mają dowodzenie w czasie kwadratowym i strukturalny ciąg odniesienia o rozmiarze kwadratowym, więc nie skalują się do dużych obliczeń.

Programy rozpiętości kwadratowej i zwięzłe NIZK bez PCP (2012)
Rosario Gennaro, Craig Gentry, Bryan Parno i Mariana Raykova

Ten przełomowy dokument (GGPR) obniżył koszty sprawdzonego podejścia IKO z kwadratowego rozmiaru obwodu do quasilinearnego. Opierając się na wcześniejszych pracach Grotha i Lipma, dał również SNARKs za pomocą kryptografii opartej na parowaniu, a nie interaktywnych argumentów, jak w IKO. Opisał swoje SNARKs w kontekście tego, co obecnie nazywamy problemami spełniania ograniczeń rang 1 (R1CS), uogólnieniem spełnialności obwodów arytmetycznych.

Ten artykuł posłużył również jako teoretyczna podstawa pierwszych SNARK-ów, które zostały wprowadzone do użytku komercyjnego (np. w ZCash) i bezpośrednio doprowadził do SNARK-ów, które pozostają popularne do dziś (np. Groth16). Pojawiły się pierwsze implementacje argumentów GGPR Zatar i Pinokio, a późniejsze warianty obejmują SNARKI dla C i BCTV. BCIOP dał ogólne ramy, które wyjaśniają te transformacje liniowe PCP w SNARK (patrz także Dodatek A Zatar) i opisuje różne ich przykłady.

O wielkości nieinteraktywnych argumentów opartych na parowaniu (2016)
autorstwa Jensa Grotha

W tym artykule, potocznie określanym jako Groth16, zaprezentowano udoskonalenie SNARK GGPR, które do dziś osiąga najnowocześniejsze koszty weryfikacji betonu (dowody to 3 elementy grupowe, a weryfikacja jest zdominowana przez trzy operacje parowania, przynajmniej przy założeniu wejście jest krótkie). Bezpieczeństwo jest udowodnione w ogólnym modelu grupowym.

SNARK z uniwersalną zaufaną konfiguracją

PlonK: Permutacje na podstawach Lagrange'a dla ekumenicznych nieinteraktywnych argumentów wiedzy (2019)
autorzy: Ariel Gabizon, Zachary Williamson i Oana Ciobotaru

Marlin: Wstępne przetwarzanie zkSNARKs z uniwersalnym i aktualizowalnym SRS (2019)
Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely i Nicholas Ward

Zarówno PlonK, jak i Marlin zastępują zaufaną konfigurację specyficzną dla obwodów w Groth16 konfiguracją uniwersalną. Odbywa się to kosztem 4x-6x większych odbitek próbnych. Można myśleć o PlonK i Marlinie jako o podjęciu pracy specyficznej dla obwodu podczas zaufanej konfiguracji w Groth16 i poprzednikach i przeniesieniu jej do fazy przetwarzania wstępnego, która ma miejsce po zaufanej konfiguracji, a także podczas generowania proofów SNARK.

Zdolność do przetwarzania dowolnych obwodów i systemów R1CS w ten sposób jest czasami nazywana holografią lub zobowiązaniami obliczeniowymi i została również opisana w Spartanin (omówione w dalszej części tej kompilacji). Ponieważ podczas generowania dowodu zachodzi więcej pracy, testy PlonK i Marlin są wolniejsze niż Groth16 dla danego obwodu lub instancji R1CS. Jednak w przeciwieństwie do Groth16, PlonK i Marlin mogą pracować z bardziej ogólnymi pośrednimi reprezentacjami niż R1CS.

Wielomianowe schematy zobowiązań, kluczowy prymityw kryptograficzny w SNARKs

Zobowiązania o stałym rozmiarze do wielomianów i ich zastosowania (2010)
Aniket Kate, Gregory Zaverucha i Ian Goldberg

W niniejszym artykule wprowadzono pojęcie wielomianowych schematów zobowiązań. Dało to schemat wielomianów jednowymiarowych (potocznie nazywanych zobowiązaniami KZG) ze zobowiązaniami o stałej wielkości i dowodami oceny. Schemat wykorzystuje zaufaną konfigurację (tj. uporządkowany ciąg odniesienia) i kryptografię opartą na parowaniu. Pozostaje niezwykle popularny w praktyce do dziś i jest używany w SNARK-ach, w tym PlonK i Marlin omówionych powyżej (a Groth16 używa bardzo podobnych technik kryptograficznych).

Szybkie interaktywne dowody zbliżeniowe firmy Reed-Solomon firmy Oracle (2017)
Eli Ben-Sasson, Iddo Bentov, Ynon Horesh, Michael Riabzev

Daje interaktywny dowód wyroczni (IOP) do testowania Reeda-Solomona — czyli dowodzący, że zatwierdzony ciąg jest zbliżony do tabeli ewaluacyjnej wielomianu jednowymiarowego. W połączeniu z haszowaniem Merkle'a i transformacją Fiata-Shamira, daje to przejrzysty wielomianowy schemat zaangażowania z dowodami oceny o wielkości polilogarytmicznej (patrz VP19 dla szczegółów). Obecnie jest to najkrótszy spośród możliwych do przyjęcia schematów zaangażowania wielomianowego post-kwantowego.

Ligero: Lekkie podliniowe argumenty bez zaufanej konfiguracji (2017)
Scott Ames, Carmit Hazay, Yuval Ishai i Muthuramakrishnan Venkitasubramaniam

Podobnie jak w przypadku FRI, ta praca daje IOP dla testów Reeda-Solomona, ale z długością sprawdzającą pierwiastek kwadratowy, a nie polilogarytmiczną. teoretyczny działa wykazali, że zamieniając kod Reeda-Solomona na inny kod korygujący błędy z szybszym kodowaniem, można uzyskać dowód liniowy, który ponadto działa natywnie w dowolnym polu. To podejście zostało dopracowane i wdrożone w Awaria i Orion, zapewniając najnowocześniejsze osiągi testera.

Bulletproofs: krótkie dowody dotyczące transakcji poufnych i nie tylko (2017)
Benedikt Bunz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille i Greg Maxwell

Udoskonalenie wcześniejszej pracy przez BCCGP, Bulletproofs daje przejrzysty wielomianowy schemat zaangażowania (w rzeczywistości uogólnienie zwane argumentem produktu wewnętrznego) oparty na twardości obliczania dyskretnych logarytmów z logarytmicznym rozmiarem dowodu, ale liniowym czasem weryfikacji. Schemat jest dziś popularny ze względu na swoją przejrzystość i krótkie dowody (np. jest używany w ZCash Orchard i Monero).

Dory: skuteczne, przejrzyste argumenty za uogólnionymi produktami wewnętrznymi i zobowiązaniami wielomianowymi (2020)
przez Jonathana Lee

Dory skraca czas weryfikatora w Bulletproofs z liniowego na logarytmiczny, zachowując jednocześnie przezroczystość i dowody o wielkości logarytmicznej (choć konkretnie większe niż Bulletproofs) i przezroczystość. Używa parowania i opiera się na założeniu SXDH.

Interaktywne Proofy, interaktywne Proofy z wieloma dowodami i powiązane SNARKs

Delegowanie obliczeń: interaktywne dowody dla mugoli (2008)
Shafi Goldwasser, Yael Tauman Kalai i Guy Rothblum

Przed tym artykułem, interaktywne dowody ogólnego przeznaczenia wymagały: superwielomian-czas udowodnić. Niniejszy artykuł przedstawia interaktywny protokół dowodowy, powszechnie nazywany protokołem GKR, z wielomianowym dowodzeniem czasu i quasiliniowym weryfikatorem czasu, dla każdego problemu posiadającego wydajny algorytm równoległy (odpowiednik interaktywny dowód dotyczy dowolnego układu arytmetycznego o małej głębokości).

Praktyczne zweryfikowane obliczenia z interaktywnymi dowodami przesyłanymi strumieniowo (2011)
Graham Cormode, Michael Mitzenmacher, Justin Thaler

Ten artykuł (czasami nazywany CMT) skrócił czas sprawdzania w protokole GKR z kwarcowego rozmiaru obwodu do quasilinearnego. Wyprodukowałem pierwszą implementację interaktywnego dowodu ogólnego przeznaczenia. Linia kolejnych prac (Piment, Talar13, Żyrafa, Libra) jeszcze bardziej skrócił czas pracy testera, z quasilinearnego do liniowego w rozmiarze obwodu.

vSQL: weryfikacja dowolnych zapytań SQL w dynamicznych zewnętrznych bazach danych (2017)
Yupeng Zhang, Daniel Genkin, Jonathan Katz, Dimitrios Papadopoulos i Charalampos Papamanthou

Chociaż tytuł odnosi się do konkretnego obszaru zastosowań (baz danych), wkład tego artykułu jest bardziej ogólny. W szczególności zaobserwował, że można uzyskać zwięzłe argumenty za spełnialnością obwodów, łącząc interaktywne dowody z wielomianowymi schematami zobowiązań (dla wielomianów wieloliniowych).

Później działa renderowane argumenty wiedzy zerowej i wprowadziły różne schematy zobowiązań dla wielomianów wieloliniowych.

Spartan: Wydajne i uniwersalne zkSNARK bez zaufanej konfiguracji (2019)
przez Srinatha Setty

Uzyskuje SNARK dla spełnialności obwodów i R1CS, łącząc interaktywne dowody wielomianowe (MIP) z wielomianowymi schematami zaangażowania, opierając się na wcześniejszych pracach nad konkretnie wydajnymi MIP Koniczyna. Efektem jest uzyskanie SNARK z krótszymi dowodami niż te pochodzące z dowodów interaktywnych, takich jak omówiony powyżej protokół GKR. Analogicznie do PlonK i Marlin, Spartan pokazuje również, jak przetwarzać dowolne obwody i systemy R1CS poprzez przetwarzanie wstępne i generowanie dowodów SNARK.

Spartan użył wielomianowego schematu zobowiązań z Góralek. Kolejne prace nazwane Awaria i Orion połączyć MIP Spartan z innymi wielomianowymi schematami zobowiązań, aby uzyskać pierwsze zaimplementowane SNARKs z dowodem liniowym.

Krótkie PCP i IOP

Krótkie PCP ze złożonością zapytań Polylog (2005)
Eli Ben-Sasson i Madhu Sudan

 Ta praca teoretyczna dała pierwszy dowód sprawdzalny probabilistycznie (PCP) o długości dowodu quasilinearnej w rozmiarze obliczeń do zweryfikowania i kosztach zapytania polilogarytmicznego (chociaż liniowy czas weryfikacji). Po transformacji PCP Kiliana-Micaliego w SNARK, był to krok w kierunku SNARK z quasi-liniowym weryfikatorem czasu i polilogarytmicznym weryfikatorem czasu.

Późniejsza praca teoretyczna skrócił czas weryfikatora do polilogarytmicznego. Kolejny prace skoncentrowane na praktyce udoskonaliły to podejście, ale krótkie PCP pozostają dziś niepraktyczne. Aby uzyskać praktyczne SNARKI, później działa obrócony do interaktywne uogólnienie PCP zwane Interaktywne dowody Oracle (IOP). Te wysiłki doprowadziły do ​​i opierają się na Piątek, popularny schemat zobowiązań wielomianowych omówiony w sekcji zobowiązań wielomianowych tej kompilacji.

Inne prace w tej kategorii to ZKBoo i jego potomkowie. Nie dają one zwięzłych dowodów, ale mają dobre współczynniki stałe, a zatem są atrakcyjne do udowodnienia małych stwierdzeń. Doprowadziły one do powstania rodzin sygnatur post-kwantowych, takich jak piknik które mają być zoptymalizowane in kilka działa. ZKBoo jest przedstawiany zgodnie z odrębnym paradygmatem projektowym zwanym RPP w głowie, ale daje IOP.

Rekurencyjne SNARK

Obliczenia weryfikowalne przyrostowo lub dowody wiedzy implikują efektywność czasową/przestrzenną (2008)
autor: Paul Valiant

W pracy tej wprowadzono podstawowe pojęcie obliczeń weryfikowalnych przyrostowo (IVC), w których program Prover przeprowadza obliczenia i przez cały czas utrzymuje dowód, że dotychczasowe obliczenia były prawidłowe. Skonstruował IVC poprzez rekurencyjną kompozycję SNARK. Tutaj wiedza-solidność właściwość SNARKs jest niezbędna do ustalenia prawidłowości rekursywnie skomponowanych nieinteraktywnych argumentów. Artykuł ten dał również niezwykle wydajny ekstraktor wiedzy dla SNARK-ów pochodzących z PCP (zgodnie z paradygmatem Kiliana-Micali).

Skalowalna wiedza zerowa za pomocą cykli krzywych eliptycznych (2014)
Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer i Madars Virza

Obserwujący praca teoretyczna, w tym artykule wykorzystano rekurencyjne zastosowanie wariantu SNARK GGPR, aby zapewnić pierwszą implementację IVC dla prostej maszyny wirtualnej (TinyRAM, z SNARKI dla C papier).

Wprowadzono również pojęcie cykli krzywych eliptycznych, które są przydatne do rekurencyjnego komponowania SNARK wykorzystujących kryptografię krzywych eliptycznych.

Rekurencyjna kompozycja dowodowa bez zaufanej konfiguracji (2019)
autorstwa Seana Bowe'a, Jacka Grigga i Dairy Hopwood

Ta praca (zwana Halo) bada, jak rekurencyjnie komponować przezroczyste SNARK. Jest to trudniejsze niż komponowanie nieprzezroczystych, ponieważ procedura weryfikacji w przezroczystych SNARK-ach może być znacznie droższa.

To następnie wywołało a linia of praca które zaowocowało systemami takimi jak Nova osiągnięcie najnowocześniejszych osiągów IVC, przewyższających nawet te uzyskane przez kompozycję nieprzezroczystych SNARK-ów, takich jak Groth16.

Konsultacje

Zerocash: zdecentralizowane anonimowe płatności z Bitcoin (2014)
Eli Ben Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, Madars Virza

Opierając się na wcześniejszej pracy, w tym Zerocoin (i z Moneta Pinokio jako praca równoległa), ten artykuł wykorzystuje SNARKs pochodzące z GGPR do zaprojektowania prywatnej kryptowaluty. Doprowadzony do ZCash.

Geppetto: Wszechstronne weryfikowalne obliczenia (2014)
Craig Costello, Cédric Fournet, Jon Howell, Markulf Kohlweiss, Benjamin Kreuter, Michael Naehrig, Bryan Parno i Samee Zahur

Geppetto prawdopodobnie poprzedza eksplozję zainteresowania prywatnymi inteligentnymi kontraktami, napisany mniej więcej rok po stworzeniu Ethereum. W związku z tym nie jest przedstawiany w kontekście realizacji prywatnych inteligentnych kontraktów. Jednak wykorzystuje rekursję SNARK o ograniczonej głębokości, aby umożliwić niezaufanemu programowi udowadniającemu wykonanie dowolnego prywatnego (zatwierdzonego/podpisanego) programu komputerowego na prywatnych danych, bez ujawniania informacji o uruchomionym programie lub danych, na których jest uruchomiony. W związku z tym jest poprzednikiem prac nad prywatnymi platformami smart-kontraktów, takimi jak: Zexe [Opisane poniżej].

Weryfikowalne ASIC (2015)
Riad Wahby, Max Howald, Siddharth Garg, abhi shelat, Michael Walfish

W niniejszym artykule omówiono problem bezpiecznego i owocnego korzystania z ASIC wyprodukowanego w niezaufanej odlewni (w 2015 r. tylko pięć krajów posiadało najwyższej klasy odlewnie). Podejście polega na tym, aby szybki, ale niezaufany ASIC udowodnił poprawność swoich danych wyjściowych weryfikatorowi, który działa na wolniejszym, ale zaufanym ASIC. Rozwiązanie jest interesujące, o ile łączny czas wykonania systemu (tj. suma czasów działania programu sprawdzającego i weryfikującego plus wszelkie koszty transmisji danych) jest mniejszy niż naiwna linia bazowa: czas wymagany do pełnego uruchomienia obliczeń na wolniejszym -ale zaufany ASIC. Używając wariantu interaktywnych dowodów GKR/CMT/Allspice, artykuł rzeczywiście bije naiwną linię bazową dla wielu podstawowych problemów, w tym przekształceń teorii liczb, dopasowywania wzorców i operacji na krzywych eliptycznych. Ta praca sugeruje, że niektóre systemy sprawdzające są bardziej odpowiednie do implementacji sprzętowej niż inne. Optymalizacja systemów dowodowych pod kątem implementacji sprzętowej jest teraz odbierana znaczny Uwaga, ale wiele pozostaje do zbadania.

Sprawdzalny Funkcje opóźniające (2018)
Dan Boneh, Joseph Bonneau, Benedikt Bünz i Ben Fisch

Wprowadzono notację weryfikowalnych funkcji opóźniających (VDF), prymityw kryptograficzny, który jest szeroko przydatny w zastosowaniach blockchain, np. w łagodzeniu możliwych manipulacji protokołami konsensusu proof-of-stake. SNARK (zwłaszcza w przypadku obliczeń weryfikowalnych przyrostowo) oferują drogę do najnowocześniejszych VDF.

Zexe: Włączanie zdecentralizowanych prywatnych obliczeń (2018)
Sean Bowe, Alessandro Chiesa, Matthew Green, Ian Miers, Pratyush Mishra i Howard Wu

Zexe to projekt prywatnej platformy smart-kontraktów. Można postrzegać Zexe jako rozszerzenie Zerocash (opisane powyżej). Zerocash umożliwia uruchomienie pojedynczej aplikacji w łańcuchu (umożliwiając użytkownikom przesyłanie tokenów) przy jednoczesnej ochronie prywatności danych użytkowników, np. do kogo wysyłają tokeny, od których otrzymują tokeny, ilość przekazywanych tokenów itp. Zexe pozwala na wiele różne aplikacje (inteligentne kontrakty) działające na tym samym łańcuchu bloków i współdziałające ze sobą. Transakcje są realizowane poza łańcuchem, a dowody prawidłowego wykonania są umieszczane w łańcuchu. Prywatność danych jest chroniona nie tylko, ale także prywatność funkcji. Oznacza to, że dowód powiązany z każdą transakcją nie ujawnia nawet, której aplikacji dotyczy dana transakcja. Bardziej ogólny wkład inżynierski Zexe polega na tym, że wprowadził BLS12-377, grupę krzywych eliptycznych, która jest przydatna do wydajnego składu głębokości-1 SNARK opartych na parach.

Zreplikowane maszyny stanowe bez zreplikowanego wykonania (2020)
autorstwa Jonathana Lee, Kirilla Nikitina i Srinatha Setty

Jest to jeden z nielicznych artykułów naukowych na temat rollupów dotyczących skalowalności blockchain. Nie posługuje się terminem rollupy, ponieważ poprzedza lub jest współczesna z pojęciem wprowadzanym poza literaturą akademicką.

Front-endy (efektywne transformacje z programów komputerowych do reprezentacji pośrednich, takich jak zgodność obwodów, R1CS i inne)

Szybkie redukcje z pamięci RAM do delegowanych problemów z satysfakcją zwięzłego ograniczenia (2012)
Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin i Eran Tromer

Z nowoczesnej perspektywy jest to wczesna praca nad praktycznymi przekształceniami komputer-program-obwód-SAT dla abstrakcji maszyny wirtualnej (VM). Opierając się na pracach od końca lat 1970. do lat 1990. (np. prace Robson) ten artykuł określa deterministyczną redukcję z wykonania VM dla kroków T do spełnialności obwodu o rozmiarze O(T*polylog(T)).

Kolejne artykuły, m.in. SNARKI dla C i BCTV, nadal rozwijał interfejsy za pomocą abstrakcji maszyn wirtualnych, a nowoczesne instancje obejmują projekty takie jak Kair, RYZYKO Zero, Wielobok Miden.

Przyjmowanie zweryfikowanych obliczeń opartych na dowodach o kilka kroków bliżej praktyczności (2012)
Śrinath Setty, Victor Vu, Nikhil Panpalia, Benjamin Braun, Muqeet Ali, Andrew J. Blumberg i Michael Walfish

Ten artykuł, określany jako Ginger, to kolejny wczesny wkład w praktyczne techniki front-endowe. Firma Ginger wprowadziła gadżety do ogólnych prymitywów programowania, takie jak warunkowe i wyrażenia logiczne, porównania i arytmetyka bitowa poprzez dzielenie bitów, prymitywna arytmetyka zmiennoprzecinkowa itp. Wykorzystała te gadżety, aby zapewnić pierwszy zaimplementowany interfejs z języka wysokiego poziomu do niskiego stopnia ograniczenia arytmetyczne (podobne do tego, co jest obecnie znane jako R1CS), pośrednia reprezentacja (IR), do której można zastosować back-end SNARK.

Podczas gdy artykuł „Fast Reductions” i jego potomkowie używają podejścia „emulator procesora” do tworzenia IR (tj. IR wymusza, aby tester poprawnie uruchomił określony program, stosując funkcję przejścia procesora dla określonej liczby kroków) , Ginger i jego potomkowie stosują podejście bardziej zbliżone do ASIC, tworząc IRy dostosowane do programu komputerowego, który tester twierdzi, że poprawnie wykonuje.

Na przykład, Bufet pokazuje, że możliwe jest obsłużenie złożonego przepływu sterowania w modelu ASIC, poprzez przekształcenie takiego przepływu sterowania w maszynę skończoną dostosowaną do wykonywanego programu oraz że takie podejście może być znacznie wydajniejsze niż budowanie ogólnego emulatora procesora. xJsnark zapewnia wydajną konstrukcję dla arytmetyki o dużej precyzji, optymalizacje dla pamięci RAM i ROM oraz udostępnia programiście język wysokiego poziomu podobny do Java, który pozostaje popularny do dziś. CircC Zauważa, że ​​kompilacja programów komputerowych do R1CS jest ściśle związana z dobrze znanymi technikami z analizy programów i buduje zestaw narzędzi do budowy kompilatora zawierający pomysły z obu społeczności („LLVM dla reprezentacji podobnych do obwodów”). Wcześniejsze prace wnoszące wkład do front-endów w stylu ASIC obejmują: Pinokio i Geppetto.

W artykule „Fast-Reductions” wykorzystano skomplikowaną i kosztowną konstrukcję zwaną „sieciami routingu” dla tzw sprawdzanie pamięci (tj. zapewnienie, że niezaufany program do sprawdzania prawidłowo utrzymuje pamięć o dostępie swobodnym maszyny wirtualnej przez cały czas wykonywania maszyny wirtualnej, której poprawność została udowodniona). Wybór ten został dokonany, ponieważ wczesne prace, takie jak ten, dążyły do ​​uzyskania PCP, co wymagało, aby front-end był obie nieinteraktywny i teoretycznie bezpieczny dla informacji. Późniejsza praca o nazwie Spiżarnia (poprzednik Bufet wspomniane wyżej prace) wykorzystywały drzewa Merkle'a zamiast sieci routingu, osiągając wydajność dzięki kompilacji algebraicznej (tj. „przyjaznej dla SNARK”) funkcji mieszającej, ze względu na Adżtaj, na ograniczenia. Zaowocowało to „bezpiecznymi obliczeniowo” front-endami. Obecnie istnieje obszerna literatura badawcza na temat funkcji skrótu przyjaznych dla SNARK, z przykładami, w tym Poseidon, MiMC, Żelbetowe, RatowanieI więcej.

Najnowocześniejsze techniki zapewniające prawidłowe utrzymanie pamięci RAM przez tester opierają się na tak zwanych metodach „permutacji-niezmiennych odcisków palców” pochodzących przynajmniej od Lipton (1989) i używany do sprawdzania pamięci przez Blum i in. (1991). Techniki te nieodłącznie wiążą się z interakcją między weryfikatorem a weryfikatorem, ale mogą stać się nieinteraktywne w przypadku transformacji Fiata-Shamira. O ile nam wiadomo, zostały one wprowadzone do literatury na temat praktycznych nakładek SNARK przez system o nazwie pamięć RAM.

Niezmienne permutacyjne techniki odcisków palców są obecnie używane w wielu front-endach i SNARK do abstrakcji maszyn wirtualnych, w tym na przykład Kair. Ściśle powiązane idee pojawiły się ponownie w pokrewnych kontekstach w dwóch poniższych pracach, które są dziś szeroko stosowane w praktyce.

Niemal liniowe dowody wiedzy o zerowej wiedzy dla prawidłowego wykonania programu (2018)
Jonathan Bootle, Andrea Cerulli, Jens Groth, Sune Jakobsen i Mary Maller

Plookup: uproszczony protokół wielomianowy dla tabel przeglądowych (2020)
autorzy: Ariel Gabizon i Zachary Williamson

Wczesne prace nad front-endami przedstawiały operacje „niearytmetyczne” (takie jak sprawdzanie zakresu, operacje bitowe i porównywanie liczb całkowitych) wewnątrz obwodów i powiązanych IR poprzez dzielenie elementów pola na bity, wykonywanie operacji na tych bitach, a następnie „pakowanie” wynik z powrotem do pojedynczego elementu pola. Pod względem rozmiaru powstałego obwodu skutkuje to logarytmicznym obciążeniem na operację.

Powyższe dwie prace (BCGJM i Plookup) podają wpływowe techniki (oparte na tak zwanych „tabelach przeglądowych”) dla efektywniejszego odwzorowania tych operacji wewnątrz obwodów, w sensie zamortyzowanym. Z grubsza rzecz biorąc, dla niektórych parametrów B wybranych przez projektanta front-endu, zmniejszają one liczbę bramek wymaganych do reprezentowania każdej niearytmetycznej operacji w obwodzie o współczynnik logarytmiczny w B, kosztem dowodzącego, który kryptograficznie zobowiązuje się do dodatkowego wektor „porady” o długości z grubsza B.