Zero-Knowledge-Kanon

Anmerkung der Redaktion: a16z crypto hat eine lange Reihe von „Gewehre", von unserer DAO-Kanon letztes Jahr zu unserem NFT-Kanon früher (und davor unser Original Krypto-Kanon) – melden Sie sich unbedingt bei unserem an web3 wöchentlicher Newsletter für weitere Updates sowie andere kuratierte Ressourcen.

SchluchzenUnten haben wir eine Reihe von Ressourcen für diejenigen zusammengestellt, die verstehen, tiefer gehen und mit allen Dingen bauen möchten kein Wissen: Leistungsstarke, grundlegende Technologien, die den Schlüssel zur Blockchain-Skalierbarkeit enthalten und die Zukunft datenschutzrechtlicher Anwendungen und unzähliger weiterer Innovationen darstellen. Wenn Sie Vorschläge für hochwertige Stücke zum Hinzufügen haben, lassen Sie es uns wissen @a16zcrypto.

Zero-Knowledge-Proof-Systeme gibt es seit Jahrzehnten: Ihre Einführung durch Shafi Goldwasser, Silvio Micali und Charles Rackoff im Jahr 1985 hatte eine transformative Wirkung auf das Gebiet der Kryptografie und wurde durch den ACM Turing Award gewürdigt, der an Goldwasser und Micali verliehen wurde 2012. Da diese Arbeit – einschließlich ihres Übergangs von der Theorie zur Praxis und den heutigen Anwendungen in Crypto/Web3 – Jahrzehnte in der Entstehung war, teilen wir auch zum ersten Mal in unserer Canons-Serie einen zweiten Teil (vorerst hier unten enthalten): eine Leseliste, kommentiert von Justin Thaler, nach dem ersten Teil unten.

Danksagung: Dank auch an Michael Blau, Sam Ragsdale und Tim Roughgarden.

Grundlagen, Hintergründe, Entwicklungen

Einige dieser Artikel befassen sich auch mehr mit Kryptografie im Allgemeinen (nicht alle Zero Knowledge per se), einschließlich der Skizzierung von Problemen oder wichtigen Fortschritten, die heute von Zero Knowledge Proofs angesprochen werden: wie Datenschutz und Authentifizierung in offenen Netzwerken gewährleistet werden können.

Neue Richtungen in der Kryptographie (1976)
von Whitfield Diffie und Martin Hellman
https://ee.stanford.edu/~hellman/publications/24.pdf

Eine Methode zum Abrufen digitaler Signaturen und Kryptosysteme mit öffentlichem Schlüssel
von 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

Protokolle für Kryptosysteme mit öffentlichem Schlüssel (1980)
von Ralf Merkle
http://www.merkle.com/papers/Protocols.pdf

Sichere Kommunikation über unsichere Kanäle (1978)
von Ralf Merkle
https://www.merkle.com/1974/PuzzlesAsPublished.pdf

Verwendung elliptischer Kurven in der Kryptographie (1988)
von Victor Miller
https://link.springer.com/content/pdf/10.1007%2F3-540-39799-X_31.pdf

Die Wissenskomplexität interaktiver Beweissysteme (1985)
von Shafi Goldwasser, Silvio Micali, Charles Rackof
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.419.8132&rep=rep1&type=pdf

Rechnerisch einwandfreie Beweise (2000)
von Silvio Micali
https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/Computationally_Sound_Proofs.pdf

Von extrahierbarer Kollisionsresistenz zu prägnanten nicht-interaktiven Wissensargumenten [SNARKs] und wieder zurück (2011)
von Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer
https://eprint.iacr.org/2011/443.pdf

Effizientes Zero-Knowledge-Argument für die Korrektheit eines Shuffle (2012)
von Stephanie Bayer und Jens Groth
http://www0.cs.ucl.ac.uk/staff/J.Groth/MinimalShuffle.pdf

Prägnantes nicht-interaktives Nullwissen für eine von Neumann-Architektur (2013)
von Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer und Madars Virza
https://eprint.iacr.org/2013/879.pdf

Skalierbare, transparente und postquantensichere Rechenintegrität (2018)
von Eli Ben-Sasson, Iddo Bentov, Yinon Horesh und Michael Riabzev
https://eprint.iacr.org/2018/046.pdf

Public-Coin-Zero-Knowledge-Argumente mit (fast) minimalem Zeit- und Platzaufwand (2020)
von Alexander Block, Justin Holmgren, Alon Rosen, Ron Rothblum und Pratik Soni
https://www.iacr.org/cryptodb/data/paper.php?pubkey=30645

Übersichten & Einführungen

Beweise, Argumente und Zero-Knowledge — Eine Übersicht über verifizierbares Rechnen und interaktive Beweise und Argumente, kryptografische Protokolle, die es einem Beweiser ermöglichen, einem Verifizierer zu garantieren, dass der Beweiser eine angeforderte Berechnung korrekt durchgeführt hat, einschließlich Zero-Knowledge (wenn Beweise keine anderen Informationen als ihre eigene Gültigkeit offenbaren) . Zk-Argumente haben eine Vielzahl von Anwendungen in der Kryptografie und haben in den letzten zehn Jahren den Sprung von der Theorie in die Praxis geschafft.
von JustinThaler
https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf

Eine Weiterentwicklung von Modellen für Zero-Knowledge-Beweise – Ein Überblick über Zero-Knowledge-Beweise, in dem Meiklejohn (University College London, Google) die Anwendungen betrachtet, die ihre Entwicklung vorantreiben, die verschiedenen Modelle, die zur Erfassung dieser neuen Interaktionen entstanden sind, die Konstruktionen, die wir erreichen können, und die Arbeit muss noch gemacht werden.
von Sarah Meiklejohn
https://www.youtube.com/watch?v=HO97kVMI3SE

ZK-Whiteboard-Sitzungen — Einführungsmodule
mit Dan Boneh et al
https://zkhack.dev/whiteboard/

Sicherheit und Datenschutz für Krypto mit zkps — Pionierarbeit für den Zero-Knowledge-Beweis in der Praxis; was zkps sind und wie sie funktionieren… inklusive Live-Stage „Demo“
von Zooko Wilcox
https://a16z.com/2019/08/29/security-and-privacy-for-crypto-with-zero-knowledge-proofs/

Top-Tech-Themen erklärt — einschließlich Definitionen und Implikationen von Zero Knowledge im Allgemeinen
von 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

Wie die kommende Datenschutzschicht ein kaputtes Web reparieren wird
von Howard Wu
https://future.com/a-privacy-layer-for-the-web-can-change-everything/

Einführung in zkSNARKS
mit Howard Wu, Anna Rose
https://zeroknowledge.fm/38-2/

Warum und wie zk-SNARK funktioniert: eine endgültige Erklärung
von Maksym Petkus
https://arxiv.org/pdf/1906.07221.pdf

Eine Einführung in Zero-Knowledge-Beweise
von Fredrik Harrysson und Anna Rose
https://www.zeroknowledge.fm/21 [+ Zusammenfassung an anderer Stelle hier]

Zk-SNARKS: unter der Haube
von Vitalik Buterin
https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
Teil 1, Teil 2, Teil 3

Dezentrale Geschwindigkeit — zu Fortschritten bei Zero-Knowledge-Proofs, dezentralisierter Hardware
von Elena Burger
https://a16z.com/2022/04/15/zero-knowledge-proofs-hardware-decentralization-innovation/

Modernste zk-Forschung — mit zk-Forscher bei der Ethereum Foundation
mit Mary Maller, Anna Rose, Kobi Gurkan
https://zeroknowledge.fm/232-2/

Erkundung von zk research — mit Forschungsdirektor bei DFINITY; auch hinter Fortschritten wie Groth16
mit Jens Groth, Anna Rose, Kobi Gurkan
https://zeroknowledge.fm/237-2/

SNARK-Forschung und -Pädagogik – mit einem der Mitbegründer von ZCash und Starkware
mit Alessandro Chiesa, Anna Rose
https://zeroknowledge.fm/episode-200-snark-research-pedagogy-with-alessandro-chiesa/

Tiefe Tauchgänge, Bauanleitungen

Grundlagen probabilistischer Beweise — ein Kurs mit 5 Einheiten aus interaktiven Beweisen und mehr
von Alessandro Chiesa
https://www.youtube.com/playlist?list=PLGkwtcB-DfpzST-medFVvrKhinZisfluC

STARKs — Teil I, II, III
von 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

Anatomie eines STARK — ein sechsteiliges Tutorial, das die Mechanik eines STARK Proof-Systems erklärt
von Alan Szepieniec
https://aszepieniec.github.io/stark-anatomy/

SNARK-Design, Teil 1 — Umfrage, Verwendung in Rollups, mehr
von JustinThaler
https://www.youtube.com/watch?v=tg6lKPdR_e4

SNARK-Design, Teil 2 — Rollups, Leistung, Sicherheit
von JustinThaler
https://www.youtube.com/watch?v=cMAI7g3UcoI

Messen der SNARK-Leistung — Frontends, Backends, mehr
von JustinThaler
https://a16zcrypto.com/measuring-snark-performance-frontends-backends-and-the-future/

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

Das Zero-Knowledge-Proof-System von PLONK — Serie von 12 Kurzvideos zur Funktionsweise von PLONK
von DavidWong
https://www.youtube.com/playlist?list=PLBJMt6zV1c7Gh9Utg-Vng2V6EYVidTFCC

Von AIRs zu RAPs — wie die Arithmetik im PLONK-Stil funktioniert
von Ariel Gabizon
https://hackmd.io/@aztec-network/plonk-arithmetiization-air

Multiset-Prüfungen in PLONK und Plookup
von Ariel Gabizon
https://hackmd.io/@arielg/ByFgSDA7D

Halo2-Design — von ECC
https://zcash.github.io/halo2/design.html

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

Anwendungen & Tutorials: Proof of Concepts, Demos, Tools, mehr

Angewandt zk - Lernmittel
von 0xPARC
https://learn.0xparc.org/materials/intro

Eine Online-Entwicklungsumgebung für zkSNARKs — zkREPL, eine neue Reihe von Tools für die Interaktion mit dem Circom-Toolstack im Browser
von Kevin Kwok
https://zkrepl.dev (+ Erklärthread hier)

Quadratische Rechenprogramme von Null bis Held
von Vitalik Buterin
https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

Auf zkEVMs
mit Alex Gluchowski und Anna Rose
https://zeroknowledge.fm/175-2/

Verschiedene Arten von zkEVMs
von Vitalik Buterin
https://vitalik.ca/general/2022/08/04/zkevm.html

ZK maschinelles Lernen — Tutorial & Demo zum Einfügen eines neuronalen Netzes in einen SNARK
von Horace Pan, Francis Ho und Henri Palacci
https://0xparc.org/blog/zk-mnist

Auf ZK-Sprachen
mit Alex Özdemir und Anna Rose
https://zeroknowledge.fm/172-2/

Dark Forest – Anwenden von zk-Kryptografie auf Spiele — ein vollständig dezentralisiertes und persistentes RTS-Spiel (Echtzeitstrategie).
https://blog.zkga.me/announcing-darkforest

ZKPs für Ingenieure — ein Blick auf die Dark Forest ZKPs
https://blog.zkga.me/df-init-circuit

Ein Sprung ins Nullwissen
mit Elena Nadolinkski, Anna Rose, James Prestwich
https://zeroknowledge.fm/182-2/

zkDocs: Zero-Knowledge-Informationsaustausch
von Sam Ragsdale und Dan Boneh
https://a16zcrypto.com/zkdocs-zero-knowledge-information-sharing/

Krypto-Airdrops zum Schutz der Privatsphäre mit Zero-Knowledge-Proofs
von Sam Ragsdale
https://a16z.com/2022/03/27/crypto-airdrop-privacy-tool-zero-knowledge-proofs/

Vertrauenswürdige On-Chain-Setup-Zeremonien -
von Valeria Nikolaenko und Sam Ragsdale
https://a16zcrypto.com/on-chain-trusted-setup-ceremony/

Kryptoregulierungen, illegale Finanzen, Datenschutz und mehr – enthält einen Abschnitt über Zero-Knowledge in regulatorischen/Compliance-Kontexten; Unterschied zwischen „Datenschutz“- und Verschleierungstechnologien
mit Michele Korver, Jai Ramaswamy, Sonal Chokshi
https://web3-with-a16z.simplecast.com/episodes/crypto-regulations-sanctions-compliance-aml-ofac-news-explained

Andere Ressourcen

zkMesh-Newsletter — ein monatlicher Newsletter mit den neuesten Informationen zu dezentralisierten Technologien zur Wahrung der Privatsphäre, Entwicklung von Datenschutzprotokollen und Zero-Knowledge-Systemen
https://zkmesh.substack.com/

Zero-Knowledge-Podcast – über die neuesten zk-Forschungs- und zk-Anwendungen und Experten, die kryptografiefähige Datenschutztechnologien entwickeln
mit AnnaRose
https://zeroknowledge.fm/

…eine kommentierte Leseliste, thematisch und chronologisch geordnet, von Justin Thaler:

SNARKs von linearen PCPs (auch bekannt als SNARKs mit schaltungsspezifischem Setup)

Effiziente Argumente ohne kurze PCPs (2007)
von Yuval Ishai, Eyal Kushilevitz und Rafail Ostrovsky

Vor etwa 2007 wurden SNARKs hauptsächlich über die entwickelt Kilian-mikali Paradigma, einen „kurzen“ probabilistisch prüfbaren Beweis (PCP) zu nehmen und ihn mittels Merkle-Hashing und der Fiat-Shamir-Transformation „kryptographisch zu einem prägnanten Argument zusammenzufügen“. Leider sind kurze PCPs auch heute noch kompliziert und unpraktisch. Dieses Papier (IKO) zeigte, wie man homomorphe Verschlüsselung verwendet, um prägnante (nicht transparente) interaktive Argumente von „langen, aber strukturierten“ PCPs zu erhalten. Diese können viel einfacher sein als kurze PCPs, und die resultierenden SNARKs haben viel kürzere Beweise und eine schnellere Verifizierung. Diese Argumente wurden erstmals als praxistauglich erkannt, verfeinert und umgesetzt PEPPER. Unglücklicherweise haben die Argumente von IKO einen Nachweiser mit quadratischer Zeit und eine strukturierte Referenzzeichenkette mit quadratischer Größe, sodass sie nicht für große Berechnungen skaliert werden können.

Quadratische Span-Programme und prägnante NIZKs ohne PCPs (2012)
von Rosario Gennaro, Craig Gentry, Bryan Parno und Mariana Raykova

Dieses bahnbrechende Papier (GGPR) reduzierte die Nachweiskosten des IKO-Ansatzes von quadratisch in der Größe der Schaltung auf quasilinear. Aufbauend auf früheren Arbeiten von Grotte und Lipmaa, gab es auch SNARKs über Pairing-basierte Kryptografie statt interaktive Argumente wie in IKO. Es beschrieb seine SNARKs im Zusammenhang mit dem, was heute als Rang-1-Einschränkungserfüllungsprobleme (R1CS) bezeichnet wird, eine Verallgemeinerung der Erfüllbarkeit arithmetischer Schaltungen.

Dieses Papier diente auch als theoretische Grundlage für die ersten SNARKs, die kommerziell eingesetzt wurden (z. B. in ZCash), und führte direkt zu SNARKs, die bis heute beliebt sind (z. B. Groth16). Erste Implementierungen der Argumente von GGPR kamen herein Zaatar und Pinocchio, und spätere Varianten umfassen SNARKS für C und BCTV. BCIOP gab einen allgemeinen Rahmen, der diese linearen PCPs-zu-SNARK-Transformationen erläutert (siehe auch Anhang A von Zaatar) und beschreibt verschiedene Instanziierungen davon.

Über die Größe paarungsbasierter nicht interaktiver Argumente (2016)
von Jens Groth

Dieses Papier, umgangssprachlich als Groth16 bezeichnet, stellte eine Verfeinerung der SNARKs von GGPR vor, die auch heute noch konkrete Verifikationskosten auf dem Stand der Technik erreicht (Beweise sind 3 Gruppenelemente, und die Verifikation wird von drei Paarungsoperationen dominiert, so zumindest die Öffentlichkeit Eingabe ist kurz). Die Sicherheit wird im generischen Gruppenmodell nachgewiesen.

SNARKs mit universell vertrauenswürdigem Setup

PlonK: Permutationen über Lagrange-Basen für ökumenische nicht-interaktive Wissensargumente (2019)
von Ariel Gabizon, Zachary Williamson und Oana Ciobotaru

Marlin: Vorverarbeitung von zkSNARKs mit universellem und aktualisierbarem SRS (2019)
von Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely und Nicholas Ward

Sowohl PlonK als auch Marlin ersetzen das schaltungsspezifische vertrauenswürdige Setup in Groth16 durch ein universelles Setup. Dies geht zu Lasten von 4x-6x größeren Proofs. Man kann sich vorstellen, dass PlonK und Marlin die schaltungsspezifische Arbeit während des bewährten Setups in Groth16 und Vorgängern übernehmen und sie in eine Vorverarbeitungsphase verschieben, die stattfindet nachdem das vertrauenswürdige Setup sowie während der SNARK-Proof-Generierung.

Die Fähigkeit, beliebige Schaltungen und R1CS-Systeme auf diese Weise zu verarbeiten, wird manchmal als Holographie oder Berechnungsverpflichtungen bezeichnet und wurde auch in beschrieben spartanisch (wird später in dieser Zusammenstellung besprochen). Da während der Beweisgenerierung mehr Arbeit anfällt, sind die Beweiser von PlonK und Marlin für eine bestimmte Schaltung oder R16CS-Instanz langsamer als Groth1. Im Gegensatz zu Groth16 können PlonK und Marlin jedoch dazu gebracht werden, mit allgemeineren Zwischendarstellungen als R1CS zu arbeiten.

Polynomial Commitment Schemes, ein wichtiges kryptografisches Primitiv in SNARKs

Zusagen konstanter Größe für Polynome und ihre Anwendungen (2010)
von Aniket Kate, Gregory Zaverucha und Ian Goldberg

In diesem Artikel wurde der Begriff der polynomialen Commitment-Schemata eingeführt. Es gab ein Schema für univariate Polynome (allgemein als KZG-Zusagen bezeichnet) mit Zusagen konstanter Größe und Bewertungsbeweisen. Das Schema verwendet eine vertrauenswürdige Einrichtung (dh eine strukturierte Referenzzeichenfolge) und eine auf Paarung basierende Kryptografie. Es ist auch heute noch in der Praxis äußerst beliebt und wird in SNARKs verwendet, darunter PlonK und Marlin, die oben diskutiert wurden (und Groth16 verwendet äußerst ähnliche kryptografische Techniken).

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

Liefert einen interaktiven Orakelbeweis (IOP) für Reed-Solomon-Tests – das heißt, er beweist, dass eine festgeschriebene Zeichenfolge nahe an der Bewertungstabelle eines univariaten Polynoms liegt. Kombiniert mit Merkle-Hashing und der Fiat-Shamir-Transformation ergibt dies ein transparentes Polynom-Commitment-Schema mit polylogarithmischen Bewertungsbeweisen (vgl VP19 für Details). Heutzutage bleibt dies das kürzeste unter plausiblen Post-Quanten-Polynombindungsschemata.

Ligero: Leichte sublineare Argumente ohne vertrauenswürdige Einrichtung (2017)
von Scott Ames, Carmit Hazay, Yuval Ishai und Muthuramakrishnan Venkitasubramaniam

Ähnlich wie bei FRI gibt diese Arbeit einen IOP für Reed-Solomon-Tests an, aber mit Quadratwurzel-Beweislänge statt polylogarithmisch. theoretisch Werk zeigte, dass man durch Austausch des Reed-Solomon-Codes gegen einen anderen fehlerkorrigierenden Code mit schnellerer Codierung einen Linearzeitbeweis erhalten kann, der außerdem nativ über jedem Feld funktioniert. Dieser Ansatz wurde verfeinert und implementiert in Bremsung und Orion, was eine State-of-the-Art-Prover-Leistung ergibt.

Bulletproofs: Kurze Beweise für vertrauliche Transaktionen und mehr (2017)
von Benedikt Bunz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille und Greg Maxwell

Vorarbeiten verfeinern durch BCCGP, gibt Bulletproofs ein transparentes Polynom-Commitment-Schema (in der Tat eine Verallgemeinerung, die als inneres Produktargument bezeichnet wird) basierend auf der Schwierigkeit, diskrete Logarithmen mit logarithmischer Beweisgröße, aber linearer Verifiziererzeit zu berechnen. Das Schema ist aufgrund seiner Transparenz und kurzen Beweise auch heute noch beliebt (z. B. wird es in ZCash Orchard und Monero verwendet).

Dory: Effiziente, transparente Argumente für verallgemeinerte innere Produkte und Polynomverpflichtungen (2020)
von Jonathan Lee

Dory reduziert die Überprüfungszeit in Bulletproofs von linear auf logarithmisch, während Transparenz und Proofs in logarithmischer Größe (wenn auch konkret größer als Bulletproofs) und Transparenz erhalten bleiben. Verwendet Paarungen und basiert auf der SXDH-Annahme.

Interaktive Proofs, interaktive Multi-Prover-Proofs und zugehörige SNARKs

Berechnung delegieren: Interaktive Beweise für Muggel (2008)
von Shafi Goldwasser, Yael Tauman Kalai und Guy Rothblum

Vor diesem Dokument erforderten interaktive Allzweck-Proofs a superpolynomielle Zeit Prüfer. Dieses Papier gibt ein interaktives Beweisprotokoll, allgemein als GKR-Protokoll bezeichnet, mit einem polynomiellen Zeitbeweiser und einem quasilinearen Zeitverifizierer für jedes Problem, das einen effizienten parallelen Algorithmus besitzt (äquivalent gilt der interaktive Beweis für jede arithmetische Schaltung mit geringer Tiefe).

Praktisch verifizierte Berechnung mit Streaming interaktiver Beweise (2011)
von Graham Cormode, Michael Mitzenmacher, Justin Thaler

Dieses Papier (manchmal auch als CMT bezeichnet) reduzierte die Nachweiszeit im GKR-Protokoll von quartisch in der Größe der Schaltung auf quasilinear. Erzeugte die erste Implementierung eines universellen interaktiven Beweises. Eine Reihe nachfolgender Werke (Piment, Taler13, Giraffe und Libra) reduzierte die Laufzeit des Beweisers weiter, von quasilinear zu linear in der Größe der Schaltung.

vSQL: Verifizieren beliebiger SQL-Abfragen über dynamische ausgelagerte Datenbanken (2017)
von Yupeng Zhang, Daniel Genkin, Jonathan Katz, Dimitrios Papadopoulos und Charalampos Papamanthou

Obwohl sich der Titel auf ein bestimmtes Anwendungsgebiet (Datenbanken) bezieht, sind die Beiträge dieses Papiers allgemeiner. Insbesondere wurde beobachtet, dass man prägnante Argumente für die Schaltungserfüllbarkeit erhalten kann, indem man interaktive Beweise mit polynomialen Commitment-Schemata (für multilineare Polynome) kombiniert.

später Werk gemacht die Argumente Zero-Knowledge und führten verschiedene Commitment-Schemata für multilineare Polynome ein.

Spartan: Effiziente und universelle zkSNARKs ohne vertrauenswürdige Einrichtung (2019)
von Srinath Setty

Erhält SNARKs für Schaltungserfüllbarkeit und R1CS durch Kombinieren von interaktiven Multi-Prover-Beweisen (MIPs) mit Polynom-Commitment-Schemata, aufbauend auf früheren Arbeiten zu konkret effizienten MIPs, die als MIPs bezeichnet werden Clover. Der Effekt besteht darin, SNARKs mit kürzeren Beweisen zu erhalten als diejenigen, die von interaktiven Beweisen wie dem oben diskutierten GKR-Protokoll abgeleitet werden. Analog zu PlonK und Marlin zeigt Spartan auch, wie man beliebige Schaltungen und R1CS-Systeme über Pre-Processing und SNARK-Proof-Generierung verarbeiten kann.

Spartan verwendet ein Polynom-Commitment-Schema aus Klippschliefer. Nachfolgende Werke genannt Bremsung und Orion Kombinieren Sie Spartans MIP mit anderen Polynom-Commitment-Schemata, um die ersten implementierten SNARKs mit einem Linearzeitbeweis zu erhalten.

Kurze PCPs und IOPs

Kurze PCPs mit Polylog-Abfragekomplexität (2005)
von Eli Ben-Sasson und Madhu Sudan

 Diese theoretische Arbeit lieferte den ersten probabilistisch prüfbaren Beweis (PCP) mit Beweislänge quasilinear in der Größe der zu verifizierenden Berechnung und polylogarithmischen Abfragekosten (obwohl lineare Verifiziererzeit). Nach der Kilian-Micali-Transformation von PCPs in SNARKs war dies ein Schritt in Richtung SNARKs mit quasilinearem Zeitbeweis und polylogarithmischem Zeitverifizierer.

Spätere theoretische Arbeit reduzierte die Prüfzeit auf polylogarithmisch. Nachfolgende praxisorientierte Arbeit verfeinerte diesen Ansatz, aber kurze PCPs sind bis heute unpraktisch. Um praktische SNARKs zu erhalten, später Werk drehte sich um zu eine interaktive Verallgemeinerung von PCPs genannt Interaktive Oracle-Beweise (IOPs). Diese Bemühungen führten zu und bauen darauf auf Freitag, ein beliebtes Polynom-Commitment-Schema, das im Abschnitt „Polynom-Commitments“ dieser Zusammenstellung besprochen wird.

Andere Arbeiten in dieser Kategorie umfassen ZKBoo und seine Nachkommen. Diese führen keine prägnanten Beweise, haben aber gute konstante Faktoren und sind daher attraktiv für den Beweis kleiner Aussagen. Sie haben zu Familien von Post-Quanten-Signaturen geführt, wie z Picknick Das haben war optimiert in mehrere Werk. ZKBoo wird nach einem bestimmten Design-Paradigma mit dem Namen präsentiert MPC-im-Kopf, aber es ergibt einen IOP.

Rekursive SNARKs

Inkrementell verifizierbare Berechnungen oder Wissensnachweise implizieren Zeit-/Raumeffizienz (2008)
von Paul Valiant

Diese Arbeit führte den grundlegenden Begriff der inkrementell verifizierbaren Berechnung (IVC) ein, bei der ein Beweiser eine Berechnung durchführt und zu jeder Zeit einen Beweis dafür unterhält, dass die Berechnung bisher korrekt war. Es konstruierte IVC durch rekursive Zusammensetzung von SNARKs. Hier die Wissen-Gesundheit Die Eigenschaft von SNARKs ist wesentlich, um die Solidität rekursiv zusammengesetzter, nicht interaktiver Argumente festzustellen. Dieses Papier lieferte auch einen äußerst effizienten Wissensextraktor für PCP-abgeleitete SNARKs (gemäß dem Kilian-Micali-Paradigma).

Skalierbares Zero Knowledge über Zyklen elliptischer Kurven (2014)
von Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer und Madars Virza

folgende theoretische Arbeit, verwendete dieses Papier die rekursive Anwendung einer Variante von GGPRs SNARK, um die erste Implementierung von IVC für eine einfache virtuelle Maschine (TinyRAM, aus der SNARKS für C Papier).

Außerdem wurde der Begriff der Zyklen elliptischer Kurven eingeführt, die für die rekursive Erstellung von SNARKs nützlich sind, die die Kryptografie mit elliptischen Kurven verwenden.

Rekursive Beweiserstellung ohne Trusted Setup (2019)
von Sean Bowe, Jack Grigg und Daira Hopwood

Diese Arbeit (namens Halo) untersucht, wie man transparente SNARKs rekursiv komponiert. Dies ist schwieriger als das Erstellen nicht transparenter, da das Überprüfungsverfahren in transparenten SNARKs viel teurer sein kann.

Dies löste dann einen aus Linie of Arbeit das hat in Systemen wie kulminiert Nova Erzielung einer hochmodernen IVC-Leistung, die sogar derjenigen überlegen ist, die durch die Zusammensetzung von nicht transparenten SNARKs wie Groth16 erreicht wird.

Anwendungen

Zerocash: Dezentrale anonyme Zahlungen von Bitcoin (2014)
von Eli Ben Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, Madars Virza

Aufbauend auf Vorarbeiten inkl Zerocoin (und mit Pinnochio-Münze als gleichzeitige Arbeit) verwendet dieses Papier GGPR-abgeleitete SNARKs, um eine private Kryptowährung zu entwerfen. Zu ZCash geführt.

Geppetto: Vielseitige verifizierbare Berechnung (2014)
von Craig Costello, Cédric Fournet, Jon Howell, Markulf Kohlweiss, Benjamin Kreuter, Michael Naehrig, Bryan Parno und Samee Zahur

Geppetto datiert wohl vor die Explosion des Interesses an der Ausführung privater Smart Contracts, da es etwa ein Jahr nach der Gründung von Ethereum geschrieben wurde. Daher wird es nicht im Zusammenhang mit der Ausführung privater Smart-Contracts dargestellt. Es verwendet jedoch eine Rekursion mit begrenzter Tiefe von SNARKs, um einem nicht vertrauenswürdigen Beweiser zu ermöglichen, ein privates (festgeschriebenes/signiertes) Computerprogramm auf privaten Daten auszuführen, ohne Informationen über das ausgeführte Programm oder die Daten, auf denen es ausgeführt wird, preiszugeben. Dementsprechend ist es ein Vorläufer der Arbeit an privaten Smart-Contract-Plattformen, wie z Zexe [nachstehend beschrieben].

Überprüfbare ASICs (2015)
von Riad Wahby, Max Howald, Siddharth Garg, Abhi Shelat, Michael Walfish

Dieses Papier befasst sich mit dem Problem, wie ein ASIC, das in einer nicht vertrauenswürdigen Gießerei hergestellt wurde, sicher und erfolgreich verwendet werden kann (2015 gab es nur fünf Nationen mit erstklassigen Gießereien). Der Ansatz besteht darin, den schnellen, aber nicht vertrauenswürdigen ASIC die Korrektheit seiner Ausgabe einem Verifizierer beweisen zu lassen, der auf einem langsameren, aber vertrauenswürdigen ASIC läuft. Die Lösung ist so lange interessant, wie die Gesamtausführungszeit des Systems (dh die Summe der Laufzeiten von Beweiser und Verifizierer zuzüglich etwaiger Datenübertragungskosten) kleiner ist als die naive Basislinie: die Zeit, die benötigt wird, um die Berechnung vollständig auszuführen, desto langsamer -aber-vertrauenswürdiger ASIC. Unter Verwendung einer Variante der interaktiven Beweise von GKR/CMT/Allspice schlägt das Papier tatsächlich die naive Basislinie für eine Reihe grundlegender Probleme, einschließlich zahlentheoretischer Transformationen, Mustervergleich und Operationen mit elliptischen Kurven. Diese Arbeit legt nahe, dass einige Beweissysteme besser für die Hardwareimplementierung geeignet sind als andere. Die Optimierung von Beweissystemen für die Hardwareimplementierung wird jetzt erhalten erheblich Aufmerksamkeit, aber es bleibt noch viel zu erforschen.

Überprüfbar Verzögerungsfunktionen (2018)
von Dan Boneh, Joseph Bonneau, Benedikt Bünz und Ben Fisch

Einführung der Notation von verifizierbaren Verzögerungsfunktionen (VDFs), einem kryptografischen Primitiv, das in Blockchain-Anwendungen weithin nützlich ist, z. B. um mögliche Manipulationen von Proof-of-Stake-Konsensprotokollen abzuschwächen. SNARKs (insbesondere für Incrementally Verifiable Computation) bieten einen Weg zu modernsten VDFs.

Zexe: Dezentralisiertes privates Rechnen ermöglichen (2018)
von Sean Bowe, Alessandro Chiesa, Matthew Green, Ian Miers, Pratyush Mishra und Howard Wu

Zexe ist ein Design für eine private Smart-Contract-Plattform. Man kann Zexe als Erweiterung von Zerocash (oben beschrieben) ansehen. Zerocash ermöglicht die Ausführung einer einzelnen Anwendung in der Kette (so dass Benutzer Token übertragen können) und schützt gleichzeitig die Privatsphäre der Benutzerdaten, z. B. an wen sie Token senden, von wem sie Token empfangen, die Menge der übertragenen Token usw. Zexe ermöglicht viele verschiedene Anwendungen (Smart Contracts), die auf derselben Blockchain laufen und miteinander interagieren. Transaktionen werden Off-Chain ausgeführt und Nachweise der korrekten Ausführung werden On-Chain veröffentlicht. Nicht nur der Datenschutz ist geschützt, sondern auch der Funktionsschutz. Das bedeutet, dass der mit jeder Transaktion verbundene Nachweis nicht einmal offenbart, zu welcher(n) Anwendung(en) die Transaktion gehört. Ein allgemeinerer technischer Beitrag von Zexe besteht darin, dass es BLS12-377 eingeführt hat, eine elliptische Kurvengruppe, die für eine effiziente Zusammensetzung der Tiefe 1 von paarungsbasierten SNARKs nützlich ist.

Replizierte Zustandsautomaten ohne replizierte Ausführung (2020)
von Jonathan Lee, Kirill Nikitin und Srinath Setty

Dies ist eine der wenigen wissenschaftlichen Arbeiten zu Rollups für die Blockchain-Skalierbarkeit. Der Begriff Rollups wird nicht verwendet, da er älter ist oder zeitgleich mit dem Konzept ist, das außerhalb der akademischen Literatur eingeführt wurde.

Front-Ends (effiziente Transformationen von Computerprogrammen zu Zwischendarstellungen wie Circuit-Satisfiablity, R1CS und mehr)

Schnelle Reduktionen von RAMs zu delegierbaren Problemen zur Befriedigung von knappen Einschränkungen (2012)
von Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin und Eran Tromer

Aus heutiger Sicht ist dies eine frühe Arbeit an praktischen Computerprogramm-zu-Schaltkreis-SAT-Transformationen für eine Abstraktion einer virtuellen Maschine (VM). Aufbauend auf Arbeiten aus den späten 1970er bis 1990er Jahren (z. B. Arbeiten von Robson) beschreibt dieses Papier eine deterministische Reduktion von der Ausführung einer VM für T Schritte auf die Erfüllbarkeit einer Schaltung der Größe O(T*polylog(T)).

Folgearbeiten, z. SNARKS für C und BCTV, entwickelte weiterhin Frontends über eine VM-Abstraktion, und moderne Instanziierungen umfassen Projekte wie z Kairo, RISC Null und Polygonmitte.

Die beweisbasierte verifizierte Berechnung ein paar Schritte näher an die Praxistauglichkeit bringen (2012)
von Srinath Setty, Victor Vu, Nikhil Panpalia, Benjamin Braun, Muqeet Ali, Andrew J. Blumberg und Michael Walfish

Dieses als Ginger bezeichnete Papier ist ein weiterer früher Beitrag zu praktischen Front-End-Techniken. Ginger führte Gadgets für allgemeine Programmierprimitive wie Bedingungen und logische Ausdrücke, Vergleiche und bitweise Arithmetik über Bitaufteilung, primitive Gleitkommaarithmetik usw. ein. Es verwendete diese Gadgets, um das erste implementierte Front-End von einer Hochsprache zu einem niedrigen Grad bereitzustellen arithmetische Einschränkungen (ähnlich dem, was jetzt als R1CS bekannt ist), eine Zwischendarstellung (IR), auf die ein SNARK-Back-End angewendet werden kann.

Während das Papier „Fast Reductions“ und seine Nachkommen einen „CPU-Emulator“-Ansatz bei der Erstellung von IRs verwenden (dh das IR erzwingt, dass der Beweiser ein bestimmtes Programm korrekt ausgeführt hat, indem es die Übergangsfunktion der CPU für eine bestimmte Anzahl von Schritten anwendet) , Ginger und seine Nachkommen verfolgen einen eher ASIC-ähnlichen Ansatz und produzieren IRs, die auf das Computerprogramm zugeschnitten sind, von dem der Prüfer behauptet, dass es korrekt ausgeführt wird.

Zum Beispiel, Büfett zeigt, dass es möglich ist, einen komplexen Kontrollfluss im ASIC-Modell zu handhaben, indem ein solcher Kontrollfluss in eine Finite-State-Maschine umgewandelt wird, die auf das ausgeführte Programm zugeschnitten ist, und dass dieser Ansatz erheblich effizienter sein kann als der Aufbau eines Allzweck-CPU-Emulators. xJsnark bietet eine effiziente Konstruktion für Multipräzisionsarithmetik, Optimierungen für RAMs und ROMs und stellt einem Programmierer eine Java-ähnliche Hochsprache zur Verfügung, die bis heute beliebt ist. Zirk stellt fest, dass das Kompilieren von Computerprogrammen für R1CS eng mit bekannten Techniken aus der Programmanalyse verwandt ist, und erstellt ein Toolkit zum Erstellen von Compilern, das Ideen aus beiden Gemeinschaften enthält („LLVM für schaltungsähnliche Darstellungen“). Frühere Arbeiten, die Beiträge zu Front-Ends im ASIC-Stil leisten, umfassen Pinocchio und Geppetto.

Das „Fast-Reductions“-Papier verwendete eine komplizierte und teure Konstruktion namens „Routing-Netzwerke“ für sog Gedächtnisprüfung (dh Sicherstellen, dass der nicht vertrauenswürdige Prüfer den Direktzugriffsspeicher der VM während der gesamten Ausführung der VM, deren Korrektheit bewiesen wird, korrekt verwaltet). Diese Wahl wurde getroffen, weil frühe Arbeiten wie diese versuchten, ein PCP zu erhalten, was das Front-End erforderte beide nicht interaktiv und informationstheoretisch sicher. Spätere Arbeit angerufen Speisekammer (ein Vorgänger der Büfett Arbeit, die oben erwähnt wurde) Merkle-Bäume anstelle von Routing-Netzwerken verwendet, um Effizienz durch Kompilieren einer algebraischen (dh „SNARK-freundlichen“) Hash-Funktion zu erreichen Ajtai, in Einschränkungen. Das Ergebnis waren „rechnerisch sichere“ Frontends. Heute gibt es eine große Forschungsliteratur zu SNARK-freundlichen Hash-Funktionen, einschließlich Beispielen Poseidon, MiMC, Verstärkter Beton, RettungUnd vieles mehr.

Modernste Techniken, um sicherzustellen, dass der Prüfer RAM korrekt verwaltet, beruhen auf sogenannten „permutationsinvarianten Fingerprinting“-Methoden, die mindestens bis zurückgehen Lipton (1989) und zur Gedächtnisprüfung von verwendet Blümet al. (1991). Diese Techniken beinhalten von Natur aus eine Interaktion zwischen einem Beweiser und einem Verifizierer, können aber mit der Fiat-Shamir-Transformation nicht-interaktiv gemacht werden. Soweit uns bekannt ist, wurden sie durch ein System namens vRAM.

Permutationsinvariante Fingerprinting-Techniken werden jetzt in vielen Front-Ends und SNARKs für Abstraktionen virtueller Maschinen verwendet, einschließlich zum Beispiel Kairo. Eng verwandte Ideen tauchten in verwandten Kontexten in den beiden folgenden Arbeiten wieder auf, die heute in der Praxis weit verbreitet sind.

Nahezu lineare Zero-Knowledge-Beweise für die korrekte Programmausführung (2018)
von Jonathan Bootle, Andrea Cerulli, Jens Groth, Sune Jakobsen und Mary Maller

Plookup: Ein vereinfachtes Polynomprotokoll für Nachschlagetabellen (2020)
von Ariel Gabizon und Zachary Williamson

Frühe Arbeiten an Front-Ends stellten „nicht-arithmetische“ Operationen (wie Bereichsprüfungen, bitweise Operationen und ganzzahlige Vergleiche) innerhalb von Schaltungen und verwandten IRs dar, indem Feldelemente in Bits zerlegt, die Operationen an diesen Bits durchgeführt und dann „gepackt“ wurden. das Ergebnis zurück in ein einzelnes Feldelement. Bezogen auf die Größe der resultierenden Schaltung ergibt sich ein logarithmischer Overhead pro Operation.

Die beiden oben genannten Arbeiten (BCGJM und Plookup) geben einflussreiche Techniken (basierend auf sogenannten „Nachschlagetabellen“) für eine effizientere Darstellung dieser Operationen innerhalb von Schaltkreisen im amortisierten Sinne. Grob gesagt reduzieren diese für einige vom Front-End-Designer ausgewählte Parameter B die Anzahl der Gatter, die erforderlich sind, um jede nicht arithmetische Operation in der Schaltung darzustellen, um einen in B logarithmischen Faktor, auf Kosten des Prüfers, der sich kryptografisch zu einem Extra verpflichtet "Ratschlag"-Vektor der Länge ungefähr B.