Zéro Connaissance Canon

Note de la rédaction: a16z crypto a eu une longue série de «chanoines", de notre Canon DAO l'année dernière à notre Canon NFT plus tôt (et avant cela notre original Canon cryptographique) — assurez-vous de vous inscrire à notre newsletter hebdomadaire web3 pour plus de mises à jour ainsi que d'autres ressources organisées.

Donc bCi-dessous, nous avons sélectionné un ensemble de ressources pour ceux qui cherchent à comprendre, approfondir et construire avec toutes choses connaissance zéro: des technologies puissantes et fondamentales qui détiennent les clés de l'évolutivité de la blockchain et représentent l'avenir des applications préservant la confidentialité et d'innombrables autres innovations à venir. Si vous avez des suggestions de pièces de haute qualité à ajouter, faites-le nous savoir @a16zcrypto.

Les systèmes de preuve à connaissance nulle existent depuis des décennies : leur introduction par Shafi Goldwasser, Silvio Micali et Charles Rackoff en 1985 a eu un effet transformateur sur le domaine de la cryptographie et a été reconnue par le prix ACM Turing décerné à Goldwasser et Micali en 2012. Étant donné que ce travail - y compris son passage de la théorie à la pratique et aux applications dans crypto/web3 aujourd'hui - dure depuis des décennies, nous partageons également pour la première fois dans notre série de canons une deuxième partie (pour l'instant, incluse ci-dessous) : une liste de lecture annotée par Justin Thalier, en suivant la première partie ci-dessous.

Remerciements : Merci également à Michael Blau, Sam Ragsdale et Tim Roughgarden.

Fondements, historique, évolutions

Certains de ces articles portent également davantage sur la cryptographie en général (pas tous sur la connaissance zéro en soi), y compris les problèmes ou les avancées clés qui sont résolus par les preuves de connaissance zéro aujourd'hui : comment garantir la confidentialité et l'authentification dans les réseaux ouverts.

Nouvelles orientations en cryptographie (1976)
de Whitfield Diffie et Martin Hellman
https://ee.stanford.edu/~hellman/publications/24.pdf

Procédé d'obtention de signatures numériques et cryptosystèmes à clé publique
de 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

Protocoles pour les cryptosystèmes à clé publique (1980)
par Ralph Merkel
http://www.merkle.com/papers/Protocols.pdf

Communications sécurisées sur des canaux non sécurisés (1978)
par Ralph Merkel
https://www.merkle.com/1974/PuzzlesAsPublished.pdf

Utilisation des courbes elliptiques en cryptographie (1988)
par Victor Miller
https://link.springer.com/content/pdf/10.1007%2F3-540-39799-X_31.pdf

La complexité des connaissances des systèmes de preuve interactifs (1985)
de Shafi Goldwasser, Silvio Micali, Charles Rackof
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.419.8132&rep=rep1&type=pdf

Preuves informatiques sonores (2000)
par Silvio Micali
https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/Computationally_Sound_Proofs.pdf

De la résistance aux collisions extractibles aux arguments succincts non interactifs de la connaissance [SNARKs], et inversement (2011)
de Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer
https://eprint.iacr.org/2011/443.pdf

Argument efficace de connaissance nulle pour l'exactitude d'un mélange (2012)
de Stéphanie Bayer et Jens Groth
http://www0.cs.ucl.ac.uk/staff/J.Groth/MinimalShuffle.pdf

Connaissance zéro succincte non interactive pour une architecture von Neumann (2013)
par Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer et Madars Virza
https://eprint.iacr.org/2013/879.pdf

Intégrité informatique sécurisée évolutive, transparente et post-quantique (2018)
par Eli Ben-Sasson, Iddo Bentov, Yinon Horesh et Michael Riabzev
https://eprint.iacr.org/2018/046.pdf

Arguments de monnaie publique sans connaissance avec (presque) un minimum de temps et d'espace (2020)
par Alexander Block, Justin Holmgren, Alon Rosen, Ron Rothblum et Pratik Soni
https://www.iacr.org/cryptodb/data/paper.php?pubkey=30645

Aperçus et introductions

Preuves, arguments et connaissance zéro — Un aperçu de l'informatique vérifiable et des preuves et arguments interactifs, des protocoles cryptographiques qui permettent à un prouveur de fournir une garantie à un vérificateur que le prouveur a effectué correctement un calcul demandé, y compris la connaissance zéro (où les preuves ne révèlent aucune information autre que leur propre validité) . Les arguments Zk ont ​​une myriade d'applications en cryptographie et sont passés de la théorie à la pratique au cours de la dernière décennie.
par Justin Thaler
https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf

Une évolution des modèles pour les preuves à connaissance nulle — Une revue des preuves à connaissance zéro, où Meiklejohn (University College London, Google) se penche sur les applications qui pilotent leur développement, les différents modèles qui ont émergé pour capturer ces nouvelles interactions, les constructions que nous pouvons réaliser et le travail reste à faire.
par Sarah Meiklejohn
https://www.youtube.com/watch?v=HO97kVMI3SE

Séances de tableau blanc ZK — modules d'introduction
avec Dan Boneh et al
https://zkhack.dev/whiteboard/

Sécurité et confidentialité pour la cryptographie avec zkps — pionnier de la preuve de connaissance zéro dans la pratique ; ce que sont les zkps et comment ils fonctionnent… y compris la «démo» en direct
par Zooko Wilcox
https://a16z.com/2019/08/29/security-and-privacy-for-crypto-with-zero-knowledge-proofs/

Top sujets techniques, expliqués — y compris les définitions et les implications de la connaissance zéro en général
par 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

Comment la couche de confidentialité à venir réparera un Web cassé
par Howard Wu
https://future.com/a-privacy-layer-for-the-web-can-change-everything/

Introduction aux zkSNARK
avec Howard Wu, Anna Rose
https://zeroknowledge.fm/38-2/

Pourquoi et comment zk-SNARK fonctionne : une explication définitive
par Maksym Petkus
https://arxiv.org/pdf/1906.07221.pdf

Une introduction aux preuves à connaissance nulle
de Fredrik Harrysson et Anna Rose
https://www.zeroknowledge.fm/21 [+ résumé écrit ailleurs ici]

Zk-SNARK : sous le capot
par Vitalik Buterin
https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
partie 1, partie 2, partie 3

Vitesse décentralisée - sur les progrès des preuves de connaissance zéro, du matériel décentralisé
par Elena Burger
https://a16z.com/2022/04/15/zero-knowledge-proofs-hardware-decentralization-innovation/

Recherche zk de pointe — avec un chercheur zk à la Fondation Ethereum
avec Mary Maller, Anna Rose, Kobi Gurkan
https://zeroknowledge.fm/232-2/

Explorer la recherche zk — avec directeur de recherche à DFINITY ; également derrière des avancées comme Groth16
avec Jens Groth, Anna Rose, Kobi Gurkan
https://zeroknowledge.fm/237-2/

Recherche & pédagogie SNARK — avec l'un des co-fondateurs de ZCash et Starkware
avec Alessandro Chiesa, Anna Rose
https://zeroknowledge.fm/episode-200-snark-research-pedagogy-with-alessandro-chiesa/

Plongées profondes, guides du constructeur

Fondements des preuves probabilistes — un cours avec 5 unités de preuves interactives et plus
par Alessandro Chiesa
https://www.youtube.com/playlist?list=PLGkwtcB-DfpzST-medFVvrKhinZisfluC

STARK — parties I, II, III
par 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 d'un STARK - un didacticiel en six parties expliquant les mécanismes d'un système de preuve STARK
par Alan Szepieniec
https://aszepieniec.github.io/stark-anatomy/

Conception SNARK, partie 1 — enquête, utilisation dans les cumuls, plus
par Justin Thaler
https://www.youtube.com/watch?v=tg6lKPdR_e4

Conception SNARK, partie 2 — cumuls, performances, sécurité
par Justin Thaler
https://www.youtube.com/watch?v=cMAI7g3UcoI

Mesurer les performances de SNARK — frontends, backends, plus
par Justin Thaler
https://a16zcrypto.com/measuring-snark-performance-frontends-backends-and-the-future/

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

Le système de preuve à connaissance zéro PLONK — série de 12 courtes vidéos sur le fonctionnement de PLONK
par David Wang
https://www.youtube.com/playlist?list=PLBJMt6zV1c7Gh9Utg-Vng2V6EYVidTFCC

Des AIR aux RAP - comment fonctionne l'arithmétisation de style PLONK
par Ariel Gabizon
https://hackmd.io/@aztec-network/plonk-arithmetiization-air

Vérifications multiset dans PLONK et Plookup
par Ariel Gabizon
https://hackmd.io/@arielg/ByFgSDA7D

Conception Halo2 — de l'ECC
https://zcash.github.io/halo2/design.html

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

Applications et tutoriels : preuve de concepts, démos, outils, plus

Appliqué zk - ressources d'apprentissage
par 0xPARC
https://learn.0xparc.org/materials/intro

Un environnement de développement en ligne pour zkSNARKs - zkREPL, un nouvel ensemble d'outils pour interagir avec la pile d'outils Circom dans le navigateur
par Kevin Kwok
https://zkrepl.dev (+ fil explicatif ici)

Programmes d'arithmétique quadratique de zéro à héros
par Vitalik Buterin
https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

Sur les zkEVM
avec Alex Gluchowski et Anna Rose
https://zeroknowledge.fm/175-2/

Différents types de zkEVM
par Vitalik Buterin
https://vitalik.ca/general/2022/08/04/zkevm.html

Apprentissage automatique ZK - tutoriel et démo pour mettre un réseau de neurones dans un SNARK
par Horace Pan, Francis Ho et Henri Palacci
https://0xparc.org/blog/zk-mnist

Sur les langues ZK
avec Alex Ozdemir et Anna Rose
https://zeroknowledge.fm/172-2/

Dark Forest - application de la cryptographie zk aux jeux — un jeu RTS (stratégie en temps réel) entièrement décentralisé et persistant
https://blog.zkga.me/announcing-darkforest

ZKP pour ingénieurs — un regard sur les ZKP de la Forêt Sombre
https://blog.zkga.me/df-init-circuit

Une plongée dans la connaissance zéro
avec Elena Nadolinkski, Anna Rose, James Prestwich
https://zeroknowledge.fm/182-2/

zkDocs : partage d'informations sans connaissance
de Sam Ragsdale et Dan Boneh
https://a16zcrypto.com/zkdocs-zero-knowledge-information-sharing/

Parachutages cryptographiques protégeant la vie privée sans aucune preuve de connaissance
par Sam Ragsdale
https://a16z.com/2022/03/27/crypto-airdrop-privacy-tool-zero-knowledge-proofs/

Cérémonies de configuration de confiance en chaîne -
de Valeria Nikolaenko et Sam Ragsdale
https://a16zcrypto.com/on-chain-trusted-setup-ceremony/

Réglementations cryptographiques, financement illicite, confidentialité et au-delà – comprend une section sur la connaissance zéro dans les contextes de réglementation/conformité ; différence entre les technologies "préservant la vie privée" et les technologies d'obscurcissement
avec Michele Korver, Jai Ramaswamy, Sonal Chokshi
https://web3-with-a16z.simplecast.com/episodes/crypto-regulations-sanctions-compliance-aml-ofac-news-explained

Autres ressources

newsletter zkMesh - une newsletter mensuelle partageant les dernières technologies décentralisées de préservation de la vie privée, le développement de protocoles de confidentialité et les systèmes de connaissance zéro
https://zkmesh.substack.com/

Podcast Zéro Connaissance - sur les dernières applications zk research et zk et les experts qui créent une technologie de confidentialité compatible avec la cryptographie
avec Anna Rose
https://zeroknowledge.fm/

…une liste de lecture annotée, par sujet et chronologie, par Justin Thaler :

SNARK des PCP linéaires (alias SNARK avec configuration spécifique au circuit)

Arguments efficaces sans PCP courts (2007)
de Yuval Ishai, Eyal Kushilevitz et Rafail Ostrovsky

Avant 2007 environ, les SNARK étaient principalement conçus via le Kilian-Micali paradigme, consistant à prendre une preuve probabiliste vérifiable (PCP) "courte" et à la "compiler cryptographiquement" en un argument succinct via le hachage de Merkle et la transformation de Fiat-Shamir. Malheureusement, les PCP courts sont compliqués et peu pratiques, même aujourd'hui. Cet article (IKO) a montré comment utiliser le cryptage homomorphe pour obtenir des arguments interactifs succincts (non transparents) à partir de PCP « longs mais structurés ». Ceux-ci peuvent être beaucoup plus simples que les PCP courts, et les SNARK résultants ont des preuves beaucoup plus courtes et une vérification plus rapide. Ces arguments ont d'abord été reconnus comme ayant un potentiel d'efficacité pratique, puis affinés et mis en œuvre, en PEPPER. Malheureusement, les arguments d'IKO ont un prouveur de temps quadratique et une chaîne de référence structurée de taille quadratique, de sorte qu'ils ne s'adaptent pas à de grands calculs.

Programmes d'envergure quadratique et NIZK succincts sans PCP (2012)
de Rosario Gennaro, Craig Gentry, Bryan Parno et Mariana Raykova

Cet article révolutionnaire (GGPR) a réduit les coûts du prouveur de l'approche d'IKO de quadratique dans la taille du circuit à quasi linéaire. S'appuyant sur les travaux antérieurs de Croissance ainsi que Lipma, il a également donné des SNARK via une cryptographie basée sur l'appariement, plutôt que des arguments interactifs comme dans IKO. Il a décrit ses SNARK dans le contexte de ce que l'on appelle maintenant les problèmes de satisfaction de contrainte de rang 1 (R1CS), une généralisation de la satisfaction de circuit arithmétique.

Cet article a également servi de base théorique aux premiers SNARK à voir le déploiement commercial (par exemple, dans ZCash) et a directement conduit aux SNARK qui restent populaires aujourd'hui (par exemple, Groth16). Les premières mises en œuvre des arguments de GGPR sont arrivées Zaatar ainsi que Pinocchio, et les variantes ultérieures incluent SNARK pour C ainsi que BCTV. BCIOP a donné un cadre général qui élucide ces transformations linéaires PCP-SNARK (voir également l'annexe A de Zaatar) et en décrit diverses instanciations.

Sur la taille des arguments non interactifs basés sur l'appariement (2016)
par Jens Groth

Cet article, familièrement appelé Groth16, a présenté un raffinement des SNARK de GGPR qui atteint des coûts de vérification concrets de pointe, même aujourd'hui (les preuves sont des éléments de 3 groupes, et la vérification est dominée par trois opérations d'appariement, au moins en supposant que le public l'entrée est courte). La sécurité est prouvée dans le modèle de groupe générique.

SNARK avec configuration de confiance universelle

PlonK : Permutations sur les bases de Lagrange pour les arguments œcuméniques non interactifs de la connaissance (2019)
par Ariel Gabizon, Zachary Williamson et Oana Ciobotaru

Marlin : prétraitement des zkSNARK avec SRS universel et actualisable (2019)
par Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely et Nicholas Ward

PlonK et Marlin remplacent la configuration de confiance spécifique au circuit dans Groth16 par une configuration universelle. Cela se fait au détriment de preuves 4x-6x plus grandes. On peut penser que PlonK et Marlin prennent le travail spécifique au circuit lors de la configuration de confiance dans Groth16 et ses prédécesseurs et le déplacent dans une phase de pré-traitement qui se produit après la configuration de confiance, ainsi que pendant la génération de preuves SNARK.

La capacité de traiter des circuits arbitraires et des systèmes R1CS de cette manière est parfois appelée engagements d'holographie ou de calcul, et a également été décrite dans spartiate (discuté plus loin dans cette compilation). Parce que plus de travail se produit pendant la génération de preuve, les prouveurs de PlonK et Marlin sont plus lents que Groth16 pour un circuit donné ou une instance R1CS. Cependant, contrairement à Groth16, PlonK et Marlin peuvent fonctionner avec des représentations intermédiaires plus générales que R1CS.

Schémas d'engagement polynomial, une primitive cryptographique clé dans les SNARK

Engagements de taille constante envers les polynômes et leurs applications (2010)
par Aniket Kate, Gregory Zaverucha et Ian Goldberg

Cet article a introduit la notion de schémas d'engagement polynomiaux. Il a donné un schéma pour les polynômes univariés (communément appelés engagements KZG) avec des engagements de taille constante et des preuves d'évaluation. Le schéma utilise une configuration de confiance (c'est-à-dire une chaîne de référence structurée) et une cryptographie basée sur l'appariement. Il reste extrêmement populaire dans la pratique aujourd'hui et est utilisé dans les SNARK, y compris PlonK et Marlin discutés ci-dessus (et Groth16 utilise des techniques cryptographiques extrêmement similaires).

Preuves de proximité Oracle interactives rapides Reed-Solomon (2017)
par Eli Ben-Sasson, Iddo Bentov, Ynon Horesh, Michael Riabzev

Donne une preuve oracle interactive (IOP) pour les tests de Reed-Solomon, c'est-à-dire prouvant qu'une chaîne validée est proche de la table d'évaluation d'un polynôme univarié. Combiné avec le hachage de Merkle et la transformation de Fiat-Shamir, cela donne un schéma d'engagement polynomial transparent avec des preuves d'évaluation de taille polylogarithmique (voir VP19 pour plus de détails). Aujourd'hui, cela reste le plus court parmi les schémas d'engagement polynomiaux plausiblement post-quantiques.

Ligero : Arguments sublinéaires légers sans configuration de confiance (2017)
par Scott Ames, Carmit Hazay, Yuval Ishai et Muhuramakrishnan Venkitasubramaniam

Semblable à FRI, ce travail donne une PIO pour les tests de Reed-Solomon, mais avec une longueur d'épreuve racine carrée plutôt que polylogarithmique. théorique vos contrats ont montré qu'en remplaçant le code Reed-Solomon par un autre code correcteur d'erreurs avec un encodage plus rapide, on peut obtenir un prouveur en temps linéaire qui fonctionne de plus nativement sur n'importe quel champ. Cette approche a été affinée et mise en œuvre dans Freinage ainsi que Orion, produisant des performances de pointe.

Bulletproofs : épreuves courtes pour les transactions confidentielles et plus encore (2017)
par Benedikt Bunz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille et Greg Maxwell

Affiner les travaux antérieurs en BCCGP, Bulletproofs donne un schéma d'engagement polynomial transparent (en fait, une généralisation appelée argument de produit interne) basé sur la difficulté de calculer des logarithmes discrets avec une taille de preuve logarithmique mais un temps de vérification linéaire. Le système reste populaire aujourd'hui en raison de sa transparence et de ses preuves courtes (par exemple, il est utilisé dans ZCash Orchard et Monero).

Dory : des arguments efficaces et transparents pour des produits intérieurs généralisés et des engagements polynomiaux (2020)
par Jonathan Lee

Dory réduit le temps de vérification dans Bulletproofs de linéaire à logarithmique, tout en préservant la transparence et les épreuves de taille logarithmique (bien que concrètement plus grandes que Bulletproofs) et la transparence. Utilise des appariements et est basé sur l'hypothèse SXDH.

Preuves interactives, Preuves interactives multi-prouveurs et SNARK associés

Déléguer le calcul : preuves interactives pour les moldus (2008)
de Shafi Goldwasser, Yael Tauman Kalai et Guy Rothblum

Avant cet article, les preuves interactives à usage général nécessitaient une temps superpolynomial prouveur. Cet article propose un protocole de preuve interactif, communément appelé protocole GKR, avec un prouveur en temps polynomial et un vérificateur en temps quasilinéaire, pour tout problème possédant un algorithme parallèle efficace (de manière équivalente, la preuve interactive s'applique à tout circuit arithmétique de faible profondeur).

Calcul vérifié pratique avec des preuves interactives en continu (2011)
de Graham Cormode, Michael Mitzenmacher, Justin Thaler

Cet article (parfois appelé CMT) a réduit le temps de preuve dans le protocole GKR de quartique dans la taille du circuit à quasi linéaire. Production de la première implémentation d'une preuve interactive à usage général. Une série d'œuvres ultérieures (Piment, Thaler13, Girafeet Libra) a encore réduit le temps d'exécution du prouveur, de quasi-linéaire à linéaire dans la taille du circuit.

vSQL : vérification des requêtes SQL arbitraires sur des bases de données externalisées dynamiques (2017)
par Yupeng Zhang, Daniel Genkin, Jonathan Katz, Dimitrios Papadopoulos et Charalampos Papamanthou

Bien que le titre fasse référence à un domaine d'application spécifique (les bases de données), les contributions de cet article sont plus générales. Plus précisément, il a observé que l'on peut obtenir des arguments succincts pour la satisfaction du circuit en combinant des preuves interactives avec des schémas d'engagement polynomiaux (pour les polynômes multilinéaires).

Later vos contrats rendu les arguments à connaissance nulle et introduit différents schémas d'engagement pour les polynômes multilinéaires.

Spartan : zkSNARK efficaces et polyvalents sans configuration de confiance (2019)
par Srinath Setty

Obtient des SNARK pour la satisfiabilité des circuits et R1CS en combinant des preuves interactives multi-prouveurs (MIP) avec des schémas d'engagement polynomiaux, en s'appuyant sur des travaux antérieurs sur des MIP concrètement efficaces appelés Clover. L'effet est d'obtenir des SNARK avec des preuves plus courtes que celles dérivées de preuves interactives telles que le protocole GKR discuté ci-dessus. Analogue à PlonK et Marlin, Spartan montre également comment traiter des circuits arbitraires et des systèmes R1CS via le prétraitement et la génération de preuves SNARK.

Spartan a utilisé un schéma d'engagement polynomial de hyrax. Des travaux ultérieurs appelés Freinage ainsi que Orion combiner le MIP de Spartan avec d'autres schémas d'engagement polynomial pour produire les premiers SNARK implémentés avec un prouveur en temps linéaire.

PCP et IOP courts

PCP courts avec complexité des requêtes polylog (2005)
par Eli Ben-Sasson et Madhu Soudan

 Ce travail théorique a donné la première preuve probabiliste vérifiable (PCP) avec une longueur de preuve quasi linéaire dans la taille du calcul à vérifier et un coût de requête polylogarithmique (bien que temps de vérification linéaire). Suite à la transformation Kilian-Micali des PCP en SNARK, ce fut une étape vers les SNARK avec un prouveur de temps quasi-linéaire et un vérificateur de temps polylogarithmique.

Travaux théoriques ultérieurs réduit le temps du vérificateur à polylogarithmique. Subséquent des travaux axés sur la pratique ont affiné cette approche, mais les PCP courts restent peu pratiques aujourd'hui. Pour obtenir des SNARK pratiques, plus tard vos contrats tourné à une généralisation interactive des PCP appelée Preuves Oracle interactives (IOP). Ces efforts ont conduit à et se sont appuyés sur VEN, un schéma d'engagement polynomial populaire discuté dans la section des engagements polynomiaux de cette compilation.

Parmi les autres œuvres de cette catégorie figurent ZKBoo et ses descendants. Ceux-ci ne permettent pas d'obtenir des preuves succinctes, mais ils ont de bons facteurs constants et sont donc attrayants pour prouver de petites déclarations. Ils ont conduit à des familles de signatures post-quantiques telles que pique-nique qui ont était optimisé in plusieurs vos contrats. ZKBoo est présenté comme suivant un paradigme de conception distinct appelé MPC dans la tête, mais cela donne une IOP.

SNARK récursifs

Le calcul incrémentiellement vérifiable ou les preuves de connaissance impliquent une efficacité temporelle/spatiale (2008)
par Paul Vaillant

Ce travail a introduit la notion fondamentale de calcul incrémentiellement vérifiable (IVC), dans lequel le prouveur exécute un calcul et maintient à tout moment une preuve que le calcul jusqu'à présent a été correct. Il a construit IVC via une composition récursive de SNARK. Ici le connaissance-solidité La propriété des SNARK est essentielle pour établir la validité des arguments non interactifs composés de manière récursive. Cet article a également fourni un extracteur de connaissances extrêmement efficace pour les SNARK dérivés de PCP (selon le paradigme Kilian-Micali).

Connaissance zéro évolutive via des cycles de courbes elliptiques (2014)
par Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer et Madars Virza

Following travaux théoriques, cet article a utilisé l'application récursive d'une variante de SNARK de GGPR, pour fournir la première implémentation d'IVC pour une machine virtuelle simple (TinyRAM, du SNARK pour C papier).

A également introduit la notion de cycles de courbes elliptiques, qui sont utiles pour composer de manière récursive des SNARK qui utilisent la cryptographie des courbes elliptiques.

Composition de preuve récursive sans configuration de confiance (2019)
de Sean Bowe, Jack Grigg et Daira Hopwood

Ce travail (appelé Halo) étudie comment composer récursivement des SNARK transparents. C'est plus difficile que d'en composer des non transparents, car la procédure de vérification dans les SNARK transparents peut être beaucoup plus coûteuse.

Cela a alors déclenché une en ligne of travail qui a abouti à des systèmes tels que La Nova atteindre des performances IVC de pointe, supérieures même à celles obtenues par la composition de SNARK non transparents tels que Groth16.

Applications

Zerocash : paiements anonymes décentralisés à partir de Bitcoin (2014)
par Eli Ben Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, Madars Virza

S'appuyant sur des travaux antérieurs, y compris le ZEROCO (et avec Pièce Pinnochio en tant que travail simultané), cet article utilise des SNARK dérivés de GGPR pour concevoir une crypto-monnaie privée. Mené à ZCash.

Geppetto : calcul vérifiable polyvalent (2014)
par Craig Costello, Cédric Fournet, Jon Howell, Markulf Kohlweiss, Benjamin Kreuter, Michael Naehrig, Bryan Parno et Samee Zahur

Geppetto est sans doute antérieur à l'explosion d'intérêt pour l'exécution de contrats intelligents privés, ayant été écrit environ un an après la création d'Ethereum. Par conséquent, il n'est pas présenté dans le contexte de l'exécution de contrats intelligents privés. Cependant, il utilise la récursivité à profondeur limitée des SNARK pour permettre à un prouveur non fiable d'exécuter n'importe quel programme informatique privé (engagé/signé) sur des données privées, sans révéler d'informations sur le programme en cours d'exécution ou les données sur lesquelles il est exécuté. En conséquence, il s'agit d'un prédécesseur des travaux sur les plates-formes privées de contrats intelligents, telles que Zexé [décrit ci-dessous].

ASIC vérifiables (2015)
par Riad Wahby, Max Howald, Siddharth Garg, abhi shelat, Michael Walfish

Cet article examine le problème de l'utilisation sûre et fructueuse d'un ASIC fabriqué dans une fonderie non fiable (en 2015, seuls cinq pays disposaient de fonderies haut de gamme). L'approche consiste à faire en sorte que l'ASIC rapide mais non fiable prouve l'exactitude de sa sortie à un vérificateur qui s'exécute sur un ASIC plus lent mais fiable. La solution est intéressante tant que le temps d'exécution total du système (c'est-à-dire la somme des durées d'exécution du prouveur et du vérificateur plus les coûts de transmission de données) est inférieur à la ligne de base naïve : le temps nécessaire pour exécuter le calcul en entier sur le plus lent -mais-ASIC de confiance. En utilisant une variante des preuves interactives GKR/CMT/Allspice, l'article bat en effet la ligne de base naïve pour un certain nombre de problèmes fondamentaux, y compris les transformations de la théorie des nombres, la correspondance de motifs et les opérations sur les courbes elliptiques. Ce travail suggère que certains systèmes de preuve sont plus adaptés à l'implémentation matérielle que d'autres. L'optimisation des systèmes de preuve pour la mise en œuvre matérielle reçoit désormais considérable précaution, mais beaucoup reste à explorer.

Vérifiable : Fonctions de retard (2018)
de Dan Boneh, Joseph Bonneau, Benedikt Bünz et Ben Fisch

Introduction de la notation des fonctions de retard vérifiables (VDF), une primitive cryptographique largement utile dans les applications de blockchain, par exemple, pour atténuer la manipulation possible des protocoles de consensus de preuve de participation. Les SNARK (en particulier pour le calcul incrémental vérifiable) offrent une voie vers les VDF à la pointe de la technologie.

Zexe : activer le calcul privé décentralisé (2018)
par Sean Bowe, Alessandro Chiesa, Matthew Green, Ian Miers, Pratyush Mishra et Howard Wu

Zexe est une conception pour une plate-forme privée de contrats intelligents. On peut voir Zexe comme une extension de Zerocash (décrit ci-dessus). Zerocash permet à une seule application d'être exécutée en chaîne (permettant aux utilisateurs de transférer des jetons) tout en protégeant la confidentialité des données des utilisateurs, par exemple, à qui ils envoient des jetons, de qui ils reçoivent des jetons, la quantité de jetons transférés, etc. Zexe permet à de nombreux différentes applications (contrats intelligents) pour s'exécuter sur la même blockchain et interagir les unes avec les autres. Les transactions sont exécutées hors chaîne et les preuves d'exécution correcte sont publiées en chaîne. Non seulement la confidentialité des données est protégée, mais la confidentialité des fonctions l'est également. Cela signifie que la preuve associée à chaque transaction ne révèle même pas à quelle(s) application(s) la transaction se rapporte. Une contribution technique plus générale de Zexe est qu'il a introduit BLS12-377, un groupe de courbes elliptiques qui est utile pour une composition efficace en profondeur 1 de SNARK basés sur l'appariement.

Machines d'état répliquées sans exécution répliquée (2020)
par Jonathan Lee, Kirill Nikitin et Srinath Setty

Il s'agit de l'un des rares articles académiques sur les cumuls pour l'évolutivité de la blockchain. Il n'utilise pas le terme cumuls, car il est antérieur ou contemporain au concept introduit en dehors de la littérature académique.

Frontaux (transformations efficaces des programmes informatiques vers des représentations intermédiaires telles que la satisfaction des circuits, R1CS, etc.)

Réductions rapides des RAM aux problèmes de satisfaction des contraintes succinctes délégables (2012)
par Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin et Eran Tromer

D'un point de vue moderne, il s'agit d'un premier travail sur les transformations pratiques de programme informatique en circuit SAT pour une abstraction de machine virtuelle (VM). S'appuyant sur des travaux de la fin des années 1970 aux années 1990 (par exemple, le travail de Robson) cet article décrit une réduction déterministe de l'exécution d'une VM pour T étapes à la satisfaisabilité d'un circuit de taille O(T*polylog(T)).

Documents ultérieurs, par exemple, SNARK pour C ainsi que BCTV, ont continué à développer des interfaces via une abstraction de VM, et les instanciations modernes incluent des projets tels que Caire, RISC Zéroet Polygone Miden.

Rapprocher le calcul vérifié basé sur la preuve de quelques pas vers la praticité (2012)
par Srinath Setty, Victor Vu, Nikhil Panpalia, Benjamin Braun, Muqeet Ali, Andrew J. Blumberg et Michael Walfish

Cet article, appelé Ginger, est une autre des premières contributions aux techniques frontales pratiques. Ginger a introduit des gadgets pour les primitives de programmation générales telles que les expressions conditionnelles et logiques, les comparaisons et l'arithmétique au niveau du bit via le fractionnement de bits, l'arithmétique primitive à virgule flottante, etc. Il a utilisé ces gadgets pour fournir le premier frontal implémenté d'un langage de haut niveau à un faible degré contraintes arithmétiques (semblables à ce qui est maintenant connu sous le nom de R1CS), une représentation intermédiaire (IR) à laquelle un back-end SNARK peut être appliqué.

Alors que l'article "Fast Reductions" et ses descendants utilisent une approche "CPU-émulateur" pour produire des IR (c'est-à-dire que l'IR impose que le prouveur ait correctement exécuté un programme particulier en appliquant la fonction de transition du CPU pour un nombre spécifié d'étapes) , Ginger et ses descendants adoptent une approche plus proche de l'ASIC, produisant des IR adaptés au programme informatique que le prouveur prétend exécuter correctement.

Par exemple, Buffet montre qu'il est possible de gérer un flux de contrôle complexe dans le modèle ASIC, en transformant ce flux de contrôle en une machine à états finis adaptée au programme en cours d'exécution, et que cette approche peut être nettement plus efficace que la construction d'un émulateur de CPU à usage général. xJsnark donne une construction efficace pour l'arithmétique multi-précision, des optimisations pour les RAM et les ROM, et expose un langage de haut niveau de type Java à un programmeur, qui reste populaire aujourd'hui. CirC observe que la compilation de programmes informatiques vers R1CS est étroitement liée à des techniques bien connues d'analyse de programme et construit une boîte à outils de construction de compilateur incorporant des idées des deux communautés ("LLVM pour des représentations de type circuit"). Les travaux antérieurs apportant des contributions aux frontaux de style ASIC incluent Pinocchio ainsi que Geppetto.

Le document « Fast-Reductions » utilisait une construction compliquée et coûteuse appelée « réseaux de routage » pour les soi-disant vérification de la mémoire (c'est-à-dire, s'assurer que le prouveur non fiable maintient correctement la mémoire vive de la VM tout au long de l'exécution de la VM dont l'exactitude est prouvée). Ce choix a été fait car les premiers travaux comme celui-ci cherchaient à obtenir un PCP, ce qui nécessitait que le front-end soit tous les deux non interactif et information théoriquement sécurisé. Des travaux ultérieurs appelés Garde-manger (un prédécesseur du Buffet travaux mentionnés ci-dessus) ont utilisé des arbres de Merkle à la place des réseaux de routage, atteignant l'efficacité en compilant une fonction de hachage algébrique (c'est-à-dire «conviviale pour SNARK»), en raison de Ajtaï, en contraintes. Cela a abouti à des frontaux « sécurisés sur le plan informatique ». Aujourd'hui, il existe une importante littérature de recherche sur les fonctions de hachage compatibles avec SNARK, avec des exemples tels que Poséidon, MiMC, Béton armé, Sauveret plus encore.

Les techniques de pointe pour s'assurer que le démonstrateur maintient correctement la RAM s'appuient sur des méthodes dites « d'empreintes invariantes par permutation » datant au moins de Lipton (1989) et utilisé pour la vérification de la mémoire par Blum et coll. (1991). Ces techniques impliquent intrinsèquement une interaction entre un prouveur et un vérificateur, mais peuvent être rendues non interactives avec la transformation de Fiat-Shamir. À notre connaissance, ils ont été introduits dans la littérature sur les interfaces pratiques SNARK par un système appelé vRAM.

Les techniques d'empreintes digitales invariantes à la permutation sont désormais utilisées dans de nombreux frontaux et SNARK pour les abstractions de machines virtuelles, y compris par exemple Caire. Des idées étroitement liées sont réapparues dans des contextes connexes dans les deux ouvrages ci-dessous, qui sont largement utilisés dans la pratique aujourd'hui.

Preuves de connaissance zéro en temps quasi linéaire pour une exécution correcte du programme (2018)
par Jonathan Bootle, Andrea Cerulli, Jens Groth, Sune Jakobsen et Mary Maller

Plookup : un protocole polynomial simplifié pour les tables de recherche (2020)
par Ariel Gabizon et Zachary Williamson

Les premiers travaux sur les frontaux représentaient des opérations « non arithmétiques » (telles que des vérifications de plage, des opérations au niveau du bit et des comparaisons d'entiers) à l'intérieur des circuits et des IR associés en divisant les éléments de champ en bits, en effectuant les opérations sur ces bits, puis en « compactant » le résultat dans un seul élément de champ. En termes de taille du circuit résultant, cela se traduit par une surcharge logarithmique par opération.

Les deux travaux ci-dessus (BCGJM et Plookup) donnent des techniques influentes (basées sur ce qu'on appelle des "tables de correspondance") pour représenter plus efficacement ces opérations à l'intérieur des circuits, dans un sens amorti. En gros, pour un paramètre B choisi par le concepteur du front-end, ceux-ci réduisent le nombre de portes nécessaires pour représenter chaque opération non arithmétique dans le circuit par un facteur logarithmique en B, au prix du prouveur s'engage cryptographiquement à un extra vecteur « conseil » de longueur environ B.