Canon de conocimiento cero

Nota del editor: a16z crypto ha tenido una larga serie de "pistolas", De nuestros Canon DAO el año pasado a nuestro Canon NFT antes (y antes de eso nuestro original Canon criptográfico) — asegúrese de registrarse en nuestro boletín semanal web3 para obtener más actualizaciones y otros recursos seleccionados.

Entonces ba continuación, hemos seleccionado un conjunto de recursos para aquellos que buscan comprender, profundizar y construir con todas las cosas conocimiento cero: tecnologías poderosas y fundamentales que contienen las claves para la escalabilidad de blockchain y representan el futuro de las aplicaciones que preservan la privacidad y otras innumerables innovaciones por venir. Si tiene sugerencias para agregar piezas de alta calidad, háganoslo saber @a16zcripto.

Los sistemas de prueba de conocimiento cero han existido durante décadas: su introducción por parte de Shafi Goldwasser, Silvio Micali y Charles Rackoff en 1985 tuvo un efecto transformador en el campo de la criptografía y fue reconocida por el Premio ACM Turing otorgado a Goldwasser y Micali en 2012. Dado que este trabajo, incluido su paso de la teoría a la práctica y las aplicaciones en crypto/web3 hoy en día, lleva décadas en desarrollo, también compartimos por primera vez en nuestra serie de cánones una segunda parte (por ahora, incluida aquí a continuación): una lista de lectura anotada por justin thaler, siguiendo la primera parte a continuación.

Agradecimientos: Gracias también a Michael Blau, Sam Ragsdale y Tim Roughgarden.

Fundamentos, antecedentes, evoluciones.

Algunos de estos documentos también tratan más sobre la criptografía en general (no todos los conocimientos cero per se), incluidos los problemas que se describen o los avances clave que abordan las pruebas de conocimiento cero en la actualidad: cómo garantizar la privacidad y la autenticación en redes abiertas.

Nuevas direcciones en criptografía (1976)
por Whitfield Diffie y Martin Hellman
https://ee.stanford.edu/~hellman/publications/24.pdf

Un método para obtener firmas digitales y criptosistemas de clave pública
por 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

Protocolos para criptosistemas de clave pública (1980)
por Ralph Merkle
http://www.merkle.com/papers/Protocols.pdf

Comunicaciones seguras a través de canales inseguros (1978)
por Ralph Merkle
https://www.merkle.com/1974/PuzzlesAsPublished.pdf

Uso de curvas elípticas en criptografía (1988)
por Víctor Miller
https://link.springer.com/content/pdf/10.1007%2F3-540-39799-X_31.pdf

La complejidad del conocimiento de los sistemas de prueba interactivos (1985)
por Shafi Goldwasser, Silvio Micali, Charles Rackof
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.419.8132&rep=rep1&type=pdf

Pruebas de sonido computacional (2000)
por Silvio Micali
https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/Computationally_Sound_Proofs.pdf

De la resistencia de colisión extraíble a argumentos de conocimiento sucintos no interactivos [SNARK], y viceversa (2011)
de Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer
https://eprint.iacr.org/2011/443.pdf

Argumento eficiente de conocimiento cero para la corrección de una reproducción aleatoria (2012)
por Stephanie Bayer y Jens Groth
http://www0.cs.ucl.ac.uk/staff/J.Groth/MinimalShuffle.pdf

Conocimiento cero sucinto no interactivo para una arquitectura von Neumann (2013)
por Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer y Madars Virza
https://eprint.iacr.org/2013/879.pdf

Integridad computacional segura escalable, transparente y poscuántica (2018)
por Eli Ben-Sasson, Iddo Bentov, Yinon Horesh y Michael Riabzev
https://eprint.iacr.org/2018/046.pdf

Argumentos de conocimiento cero de moneda pública con (casi) gastos generales mínimos de tiempo y espacio (2020)
por Alexander Block, Justin Holmgren, Alon Rosen, Ron Rothblum y Pratik Soni
https://www.iacr.org/cryptodb/data/paper.php?pubkey=30645

Resúmenes e introducciones

Pruebas, argumentos y conocimiento cero — Una descripción general de la computación verificable y las pruebas y argumentos interactivos, los protocolos criptográficos que permiten a un probador proporcionar una garantía a un verificador de que el probador realizó un cálculo solicitado correctamente, incluido el conocimiento cero (cuando las pruebas no revelan información distinta de su propia validez) . Los argumentos Zk tienen una miríada de aplicaciones en criptografía y han dado el salto de la teoría a la práctica durante la última década.
por Justin Thaler
https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf

Una evolución de modelos para pruebas de conocimiento cero — Una revisión de las pruebas de conocimiento cero, donde Meiklejohn (University College London, Google) analiza las aplicaciones que están impulsando su desarrollo, los diferentes modelos que han surgido para capturar estas nuevas interacciones, las construcciones que podemos lograr y el trabajo queda por hacer.
por Sarah Meiklejohn
https://www.youtube.com/watch?v=HO97kVMI3SE

Sesiones de pizarra ZK — módulos introductorios
con Dan Boneh y otros
https://zkhack.dev/whiteboard/

Seguridad y privacidad para cripto con zkps — ser pionero en la prueba de conocimiento cero en la práctica; qué son los zkps y cómo funcionan... incluida la "demostración" en vivo
por Zooko Wilcox
https://a16z.com/2019/08/29/security-and-privacy-for-crypto-with-zero-knowledge-proofs/

Temas de tecnología de punta, explicados — incluyendo definiciones e implicaciones del conocimiento cero en general
por 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

Cómo la próxima capa de privacidad arreglará una red rota
por Howard Wu
https://future.com/a-privacy-layer-for-the-web-can-change-everything/

Introducción a zkSNARK
con Howard Wu, Anna Rose
https://zeroknowledge.fm/38-2/

Por qué y cómo funciona zk-SNARK: una explicación definitiva
por Maksym Petkus
https://arxiv.org/pdf/1906.07221.pdf

Una introducción a las pruebas de conocimiento cero
por Fredrik Harrysson y Anna Rose
https://www.zeroknowledge.fm/21 [+ artículo resumido en otro lugar esta página]

Zk-SNARK: bajo el capó
por Vitalik Buterin
https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
parte 1, parte 2, parte 3

Velocidad descentralizada — sobre avances en pruebas de conocimiento cero, hardware descentralizado
por Elena Hamburguesa
https://a16z.com/2022/04/15/zero-knowledge-proofs-hardware-decentralization-innovation/

Investigación zk de vanguardia — con un investigador de zk en la Fundación Ethereum
con Mary Maller, Anna Rose, Kobi Gurkan
https://zeroknowledge.fm/232-2/

Explorando la investigación de zk — con el director de investigación de DFINITY; también detrás de avances como Groth16
con Jens Groth, Anna Rose, Kobi Gurkan
https://zeroknowledge.fm/237-2/

SNARK investigación y pedagogía — con uno de los cofundadores de ZCash y Starkware
con Alessandro Chiesa, Anna Rose
https://zeroknowledge.fm/episode-200-snark-research-pedagogy-with-alessandro-chiesa/

Inmersiones profundas, guías de construcción

Fundamentos de las pruebas probabilísticas — un curso con 5 unidades de pruebas interactivas y más
por Alessandro Chiesa
https://www.youtube.com/playlist?list=PLGkwtcB-DfpzST-medFVvrKhinZisfluC

STARK — parte I, II, III
por 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

Anatomía de un STARK — un tutorial de seis partes que explica la mecánica de un sistema de prueba STARK
por Alan Szepieniec
https://aszepieniec.github.io/stark-anatomy/

Diseño SNARK, parte 1 — encuesta, uso en resúmenes, más
por Justin Thaler
https://www.youtube.com/watch?v=tg6lKPdR_e4

Diseño SNARK, parte 2 — resúmenes, rendimiento, seguridad
por Justin Thaler
https://www.youtube.com/watch?v=cMAI7g3UcoI

Medición del rendimiento de SNARK - frontends, backends, más
por Justin Thaler
https://a16zcrypto.com/measuring-snark-performance-frontends-backends-and-the-future/

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

El sistema de prueba de conocimiento cero PLONK — serie de 12 videos cortos sobre cómo funciona PLONK
por David Wong
https://www.youtube.com/playlist?list=PLBJMt6zV1c7Gh9Utg-Vng2V6EYVidTFCC

De AIR a RAP — cómo funciona la aritmetización al estilo PLONK
por Ariel Gabizon
https://hackmd.io/@aztec-network/plonk-arithmetiization-air

Comprobaciones de conjuntos múltiples en PLONK y Plookup
por Ariel Gabizon
https://hackmd.io/@arielg/ByFgSDA7D

diseño halo2 — de ECC
https://zcash.github.io/halo2/design.html

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

Aplicaciones y tutoriales: prueba de conceptos, demostraciones, herramientas, más

Zk aplicado — recursos de aprendizaje
por 0xPARC
https://learn.0xparc.org/materials/intro

Un entorno de desarrollo en línea para zkSNARKs — zkREPL, un nuevo conjunto de herramientas para interactuar con la pila de herramientas de Circom en el navegador
por Kevin Kwok
https://zkrepl.dev (+ hilo explicativo esta página)

Programas de aritmética cuadrática de cero a héroe
por Vitalik Buterin
https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

En zkEVM
con Alex Gluchowski y Anna Rose
https://zeroknowledge.fm/175-2/

Diferentes tipos de zkEVM
por Vitalik Buterin
https://vitalik.ca/general/2022/08/04/zkevm.html

Aprendizaje automático ZK — tutorial y demostración para poner una red neuronal en un SNARK
de Horace Pan, Francis Ho y Henri Palacci
https://0xparc.org/blog/zk-mnist

En idiomas ZK
con Alex Ozdemir y Anna Rose
https://zeroknowledge.fm/172-2/

Dark Forest: aplicación de la criptografía zk a los juegos — un juego RTS (estrategia en tiempo real) completamente descentralizado y persistente
https://blog.zkga.me/announcing-darkforest

ZKP para ingenieros — un vistazo a los ZKP del Bosque Oscuro
https://blog.zkga.me/df-init-circuit

Una inmersión en el conocimiento cero
con Elena Nadolinkski, Anna Rose, James Prestwich
https://zeroknowledge.fm/182-2/

zkDocs: intercambio de información sin conocimiento
por Sam Ragsdale y Dan Boneh
https://a16zcrypto.com/zkdocs-zero-knowledge-information-sharing/

Lanzamientos aéreos criptográficos que protegen la privacidad con pruebas de conocimiento cero
por Sam Ragsdale
https://a16z.com/2022/03/27/crypto-airdrop-privacy-tool-zero-knowledge-proofs/

Ceremonias de configuración de confianza en cadena -
por Valeria Nikolaenko y Sam Ragsdale
https://a16zcrypto.com/on-chain-trusted-setup-ceremony/

Criptoregulaciones, finanzas ilícitas, privacidad y más – incluye una sección sobre conocimiento cero en contextos regulatorios/de cumplimiento; diferencia entre tecnologías de "preservación de la privacidad" y de ofuscación
con Michele Korver, Jai Ramaswamy, Sonal Chokshi
https://web3-with-a16z.simplecast.com/episodes/crypto-regulations-sanctions-compliance-aml-ofac-news-explained

Otros recursos

boletín zkMesh — un boletín mensual que comparte lo último en tecnologías descentralizadas de preservación de la privacidad, desarrollo de protocolos de privacidad y sistemas de conocimiento cero
https://zkmesh.substack.com/

Podcast de conocimiento cero — sobre las últimas investigaciones de zk y aplicaciones de zk y expertos que crean tecnología de privacidad habilitada para criptografía
con ana rosa
https://zeroknowledge.fm/

…una lista de lectura comentada, por tema y cronología, por Justin Thaler:

SNARK de PCP lineales (también conocidos como SNARK con configuración específica del circuito)

Argumentos eficientes sin PCP cortos (2007)
por Yuval Ishai, Eyal Kushilevitz y Rafail Ostrovsky

Antes de aproximadamente 2007, los SNARK se diseñaron principalmente a través de la Kilian–micali paradigma, de tomar una prueba verificable probabilísticamente (PCP) "corta" y "compilarla criptográficamente" en un argumento sucinto a través de Merkle hash y la transformación Fiat-Shamir. Desafortunadamente, las PCP cortas son complicadas y poco prácticas, incluso hoy en día. Este documento (IKO) mostró cómo usar el cifrado homomórfico para obtener argumentos interactivos sucintos (no transparentes) de PCP "largos pero estructurados". Estos pueden ser mucho más simples que los PCP cortos, y los SNARK resultantes tienen pruebas mucho más cortas y una verificación más rápida. Primero se reconoció que estos argumentos tenían el potencial para la eficiencia práctica, y se refinaron e implementaron, en Pimienta. Desafortunadamente, los argumentos de IKO tienen un probador de tiempo cuadrático y una cadena de referencia estructurada de tamaño cuadrático, por lo que no se adaptan a cálculos grandes.

Programas de intervalo cuadrático y NIZK sucintos sin PCP (2012)
por Rosario Gennaro, Craig Gentry, Bryan Parno y Mariana Raykova

Este documento innovador (GGPR) redujo los costos del probador del enfoque de IKO de cuadrático en el tamaño del circuito a cuasilineal. Basándose en trabajos anteriores de crecimiento y lipmaa, también proporcionó SNARK a través de criptografía basada en emparejamiento, en lugar de argumentos interactivos como en IKO. Describió sus SNARK en el contexto de lo que ahora se conoce como problemas de satisfacción de restricciones de rango 1 (R1CS), una generalización de la satisfacibilidad de circuitos aritméticos.

Este documento también sirvió como base teórica de los primeros SNARK que se implementaron comercialmente (p. ej., en ZCash) y condujo directamente a los SNARK que siguen siendo populares en la actualidad (p. ej., Groth16). Las implementaciones iniciales de los argumentos de GGPR llegaron Zaatar y Pinocho, y las variantes posteriores incluyen SNARK para C y BCTV. BCIOP proporcionó un marco general que aclara estas transformaciones lineales de PCP a SNARK (consulte también el Apéndice A de Zaatar) y describe varias instancias de los mismos.

Sobre el tamaño de los argumentos no interactivos basados ​​en emparejamiento (2016)
por Jens Groth

Este documento, conocido coloquialmente como Groth16, presentó un refinamiento de SNARK de GGPR que logra costos de verificación concretos de última generación incluso hoy en día (las pruebas son 3 elementos grupales y la verificación está dominada por tres operaciones de emparejamiento, al menos suponiendo que el público la entrada es corta). La seguridad se prueba en el modelo de grupo genérico.

SNARK con configuración universal de confianza

PlonK: permutaciones sobre bases de Lagrange para argumentos ecuménicos no interactivos de conocimiento (2019)
por Ariel Gabizon, Zachary Williamson y Oana Ciobotaru

Marlin: preprocesamiento de zkSNARK con SRS universal y actualizable (2019)
por Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely y Nicholas Ward

Tanto PlonK como Marlin reemplazan la configuración confiable específica del circuito en Groth16 con una configuración universal. Esto se produce a expensas de pruebas 4x-6x más grandes. Uno puede pensar en PlonK y Marlin como tomando el trabajo específico del circuito durante la configuración confiable en Groth16 y predecesores y moviéndolo a una fase de preprocesamiento que sucede después de la configuración de confianza, así como durante la generación de prueba de SNARK.

La capacidad de procesar circuitos arbitrarios y sistemas R1CS de esta manera a veces se denomina holografía o compromisos de cálculo, y también se describió en espartano (discutido más adelante en esta compilación). Debido a que ocurre más trabajo durante la generación de pruebas, los probadores de PlonK y Marlin son más lentos que Groth16 para un circuito dado o una instancia de R1CS. Sin embargo, a diferencia de Groth16, se puede hacer que PlonK y Marlin funcionen con representaciones intermedias más generales que R1CS.

Esquemas de compromiso polinomial, una primitiva criptográfica clave en SNARK

Compromisos de tamaño constante para polinomios y sus aplicaciones (2010)
por Aniket Kate, Gregory Zaverucha e Ian Goldberg

Este documento introdujo la noción de esquemas de compromiso polinomial. Dio un esquema para polinomios univariados (comúnmente llamados compromisos KZG) con compromisos de tamaño constante y pruebas de evaluación. El esquema utiliza una configuración confiable (es decir, una cadena de referencia estructurada) y criptografía basada en emparejamiento. Sigue siendo extremadamente popular en la práctica actual y se usa en SNARK, incluidos PlonK y Marlin discutidos anteriormente (y Groth16 usa técnicas criptográficas extremadamente similares).

Pruebas de proximidad rápidas de Reed-Solomon Interactive Oracle (2017)
por Eli Ben-Sasson, Iddo Bentov, Ynon Horesh, Michael Riabzev

Proporciona una prueba oracular interactiva (IOP) para la prueba Reed-Solomon, es decir, prueba que una cadena confirmada está cerca de la tabla de evaluación de un polinomio univariado. Combinado con Merkle-hashing y la transformación Fiat-Shamir, esto produce un esquema de compromiso polinomial transparente con pruebas de evaluación de tamaño polilogarítmico (ver VP19 para detalles). Hoy en día, este sigue siendo el más corto entre los plausibles esquemas de compromiso polinómico poscuántico.

Ligero: argumentos sublineales ligeros sin una configuración de confianza (2017)
por Scott Ames, Carmit Hazay, Yuval Ishai y Muthuramakrishnan Venkitasubramaniam

Similar a FRI, este trabajo proporciona una IOP para la prueba Reed-Solomon, pero con longitud de prueba de raíz cuadrada en lugar de polilogarítmica. teorético funciona mostró que, al cambiar el código Reed-Solomon por un código de corrección de errores diferente con una codificación más rápida, se puede obtener un probador de tiempo lineal que además funciona de forma nativa en cualquier campo. Este enfoque ha sido refinado e implementado en Destruir y Orión, proporcionando un rendimiento de probador de última generación.

Bulletproofs: pruebas cortas para transacciones confidenciales y más (2017)
por Benedikt Bunz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille y Greg Maxwell

Refinando el trabajo previo por BCCGP, Bulletproofs proporciona un esquema de compromiso polinomial transparente (de hecho, una generalización llamada argumento del producto interno) basado en la dificultad de calcular logaritmos discretos con tamaño de prueba logarítmico pero tiempo de verificación lineal. El esquema sigue siendo popular hoy en día debido a su transparencia y pruebas cortas (por ejemplo, se usa en ZCash Orchard y Monero).

Dory: Argumentos eficientes y transparentes para productos internos generalizados y compromisos polinómicos (2020)
por Jonathan Lee

Dory reduce el tiempo del verificador en Bulletproofs de lineal a logarítmico, al tiempo que conserva la transparencia y las pruebas de tamaño logarítmico (aunque concretamente más grandes que Bulletproofs) y la transparencia. Utiliza emparejamientos y se basa en el supuesto SXDH.

Pruebas interactivas, pruebas interactivas de probadores múltiples y SNARK asociados

Cómputo delegado: Pruebas interactivas para muggles (2008)
por Shafi Goldwasser, Yael Tauman Kalai y Guy Rothblum

Antes de este documento, las pruebas interactivas de propósito general requerían un superpolinomio-tiempo tirador de pruebas. Este documento proporciona un protocolo de prueba interactivo, comúnmente llamado protocolo GKR, con un probador de tiempo polinomial y un verificador de tiempo cuasilineal, para cualquier problema que posea un algoritmo paralelo eficiente (equivalentemente, la prueba interactiva se aplica a cualquier circuito aritmético con poca profundidad).

Cálculo práctico verificado con transmisión de pruebas interactivas (2011)
por Graham Cormode, Michael Mitzenmacher, Justin Thaler

Este artículo (a veces llamado CMT) redujo el tiempo de prueba en el protocolo GKR de cuartico en el tamaño del circuito a cuasilineal. Produjo la primera implementación de una prueba interactiva de propósito general. Una línea de obras posteriores (Pimienta de Jamaica, tálero13, Jirafay Libra) redujo aún más el tiempo de ejecución del probador, de cuasilineal a lineal en el tamaño del circuito.

vSQL: verificación de consultas SQL arbitrarias en bases de datos subcontratadas dinámicas (2017)
por Yupeng Zhang, Daniel Genkin, Jonathan Katz, Dimitrios Papadopoulos y Charalampos Papamanthou

Aunque el título se refiere a un área de aplicación específica (bases de datos), las contribuciones de este artículo son más generales. Específicamente, observó que uno puede obtener argumentos sucintos para la satisfacibilidad del circuito al combinar pruebas interactivas con esquemas de compromiso polinomial (para polinomios multilineales).

Later funciona prestados los argumentos de conocimiento cero e introdujo diferentes esquemas de compromiso para polinomios multilineales.

Spartan: zkSNARK eficientes y de propósito general sin una configuración confiable (2019)
por Srinath Setty

Obtiene SNARK para la satisfacción del circuito y R1CS mediante la combinación de pruebas interactivas de múltiples probadores (MIP) con esquemas de compromiso polinomial, basándose en trabajos anteriores sobre MIP concretamente eficientes llamados Trébol. El efecto es obtener SNARK con pruebas más cortas que las derivadas de pruebas interactivas como el protocolo GKR discutido anteriormente. De manera análoga a PlonK y Marlin, Spartan también muestra cómo procesar circuitos arbitrarios y sistemas R1CS mediante preprocesamiento y generación de prueba SNARK.

Spartan usó un esquema de compromiso polinomial de hyrax. Trabajos posteriores llamados Destruir y Orión combine el MIP de Spartan con otros esquemas de compromiso polinomial para generar los primeros SNARK implementados con un probador de tiempo lineal.

PCP e IOP cortos

PCP cortos con complejidad de consulta de Polylog (2005)
por Eli Ben-Sasson y Madhu Sudán

 Este trabajo teórico dio la primera prueba verificable probabilísticamente (PCP) con una longitud de prueba cuasilineal en el tamaño del cálculo a verificar y un costo de consulta polilogarítmico (aunque el tiempo del verificador es lineal). Tras la transformación de Kilian-Micali de PCP en SNARK, este fue un paso hacia SNARK con probador de tiempo casi lineal y verificador de tiempo polilogarítmico.

Trabajo teórico posterior redujo el tiempo del verificador a polilogarítmico. Posterior El trabajo centrado en la práctica perfeccionó este enfoque, pero los PCP cortos siguen siendo poco prácticos en la actualidad. Para obtener SNARK prácticos, luego funciona convertido a una generalización interactiva de PCP llamada Pruebas interactivas de Oracle (PIO). Estos esfuerzos condujeron y se basaron en Viernes, un esquema de compromiso polinomial popular discutido en la sección de compromisos polinómicos de esta compilación.

Otros trabajos en esta categoría incluyen ZKBoo y sus descendientes. Estos no logran pruebas sucintas, pero tienen buenos factores constantes y, por lo tanto, son atractivos para probar declaraciones pequeñas. Han dado lugar a familias de firmas poscuánticas como Picnic que tienen esto optimizado in Varios funciona. ZKBoo se presenta siguiendo un paradigma de diseño distinto llamado MPC-en-la-cabeza, pero produce una PIO.

SNARK recursivos

Cálculo incrementalmente verificable o pruebas de conocimiento implican eficiencia de tiempo/espacio (2008)
por Paul Valiente

Este trabajo introdujo la noción fundamental de computación incrementalmente verificable (IVC), en la que un probador ejecuta una computación y mantiene en todo momento una prueba de que la computación hasta el momento ha sido correcta. Construyó IVC a través de la composición recursiva de SNARK. Aquí el solidez del conocimiento La propiedad de SNARK es esencial para establecer la solidez de los argumentos no interactivos compuestos de forma recursiva. Este documento también proporcionó un extractor de conocimiento extremadamente eficiente para SNARK derivados de PCP (según el paradigma de Kilian-Micali).

Conocimiento cero escalable a través de ciclos de curvas elípticas (2014)
por Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer y Madars Virza

Siguiendo trabajo teórico, este documento usó la aplicación recursiva de una variante de SNARK de GGPR, para proporcionar la primera implementación de IVC para una máquina virtual simple (TinyRAM, del SNARK para C papel).

También introdujo la noción de ciclos de curvas elípticas, que son útiles para componer recursivamente SNARK que utilizan criptografía de curva elíptica.

Composición de prueba recursiva sin una configuración de confianza (2019)
por Sean Bowe, Jack Grigg y Daira Hopwood

Este trabajo (llamado Halo) estudia cómo componer recursivamente SNARKs transparentes. Esto es más desafiante que redactar no transparentes porque el procedimiento de verificación en SNARK transparentes puede ser mucho más costoso.

Esto entonces provocó una línea of trabajo que ha culminado en sistemas como Nova logrando un rendimiento IVC de última generación, superior incluso al obtenido por composición de SNARKs no transparentes como Groth16.

Aplicaciones

Zerocash: pagos anónimos descentralizados de Bitcoin (2014)
por Eli Ben Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, Madars Virza

Sobre la base de trabajos anteriores, incluidos Zerocoin (y con Moneda Pinocho como trabajo concurrente), este documento utiliza SNARK derivados de GGPR para diseñar una criptomoneda privada. Llevó a ZCash.

Geppetto: computación verificable versátil (2014)
por Craig Costello, Cédric Fournet, Jon Howell, Markulf Kohlweiss, Benjamin Kreuter, Michael Naehrig, Bryan Parno y Samee Zahur

Podría decirse que Geppetto es anterior a la explosión de interés en la ejecución privada de contratos inteligentes, ya que se escribió aproximadamente un año después de la creación de Ethereum. Por lo tanto, no se presenta en el contexto de la ejecución privada de contratos inteligentes. Sin embargo, utiliza recursión de profundidad limitada de SNARK para permitir que un probador no confiable ejecute cualquier programa de computadora privado (comprometido/firmado) en datos privados, sin revelar información sobre el programa que se ejecuta o los datos en los que se ejecuta. En consecuencia, es un predecesor del trabajo en plataformas privadas de contratos inteligentes, como Zexe [descrito abajo].

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

Este documento considera el problema de cómo usar de manera segura y fructífera un ASIC fabricado en una fundición que no es de confianza (en 2015, solo había cinco países con fundiciones de primer nivel). El enfoque es hacer que el ASIC rápido pero no confiable demuestre la corrección de su salida a un verificador que se ejecuta en un ASIC más lento pero confiable. La solución es interesante siempre que el tiempo total de ejecución del sistema (es decir, la suma de los tiempos de ejecución del comprobador y el verificador más cualquier costo de transmisión de datos) sea menor que la línea de base ingenua: el tiempo requerido para ejecutar el cálculo en su totalidad en el sistema más lento. -pero-ASIC de confianza. Utilizando una variante de las demostraciones interactivas GKR/CMT/Allspice, el documento realmente supera la línea de base ingenua para una serie de problemas fundamentales, incluidas las transformaciones de teoría numérica, la coincidencia de patrones y las operaciones con curvas elípticas. Este trabajo sugiere que algunos sistemas de prueba son más adecuados para la implementación de hardware que otros. La optimización de los sistemas de prueba para la implementación de hardware ahora está recibiendo considerable Whatsapp, pero queda mucho por explorar.

Verificable Funciones de retardo (2018)
por Dan Boneh, Joseph Bonneau, Benedikt Bünz y Ben Fisch

Introdujo la notación de funciones de retraso verificables (VDF), una primitiva criptográfica que es muy útil en aplicaciones de cadenas de bloques, por ejemplo, para mitigar la posible manipulación de los protocolos de consenso de prueba de participación. Los SNARK (especialmente para la computación incrementalmente verificable) ofrecen una ruta hacia los VDF de última generación.

Zexe: habilitar la computación privada descentralizada (2018)
por Sean Bowe, Alessandro Chiesa, Matthew Green, Ian Miers, Pratyush Mishra y Howard Wu

Zexe es un diseño para una plataforma privada de contratos inteligentes. Uno puede ver a Zexe como una extensión de Zerocash (descrito anteriormente). Zerocash permite ejecutar una sola aplicación en la cadena (lo que permite a los usuarios transferir tokens) mientras protege la privacidad de los datos del usuario, por ejemplo, a quién envía tokens, de quién recibe tokens, la cantidad de tokens transferidos, etc. Zexe permite muchos diferentes aplicaciones (contratos inteligentes) para ejecutarse en la misma cadena de bloques e interactuar entre sí. Las transacciones se ejecutan fuera de la cadena y las pruebas de ejecución correcta se publican en la cadena. No solo se protege la privacidad de los datos, sino también la privacidad de las funciones. Esto significa que la prueba asociada con cada transacción ni siquiera revela a qué aplicación(es) pertenece la transacción. Una contribución de ingeniería más general de Zexe es que introdujo BLS12-377, un grupo de curvas elípticas que es útil para la composición eficiente de profundidad 1 de SNARK basados ​​en emparejamiento.

Máquinas de estado replicadas sin ejecución replicada (2020)
por Jonathan Lee, Kirill Nikitin y Srinath Setty

Este es uno de los pocos artículos académicos sobre acumulaciones para la escalabilidad de blockchain. No utiliza el término acumulaciones porque es anterior o contemporáneo al concepto que se introduce fuera de la literatura académica.

Front-ends (transformaciones eficientes de programas de computadora a representaciones intermedias como la satisfacción del circuito, R1CS y más)

Reducciones rápidas de RAM a problemas de satisfacción de restricciones sucintas delegables (2012)
por Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin y Eran Tromer

Desde una perspectiva moderna, este es un trabajo temprano sobre transformaciones prácticas de programa de computadora a circuito-SAT para una abstracción de máquina virtual (VM). Sobre la base de obras de finales de la década de 1970 hasta la década de 1990 (p. ej., obra de Robson) este documento explica en detalle una reducción determinista de la ejecución de una VM para T pasos a la satisfacibilidad de un circuito de tamaño O (T * polylog (T)).

Documentos posteriores, por ejemplo, SNARK para C y BCTV, continuó desarrollando interfaces a través de una abstracción de VM, y las instancias modernas incluyen proyectos como El Cairo, RISC ceroy Polígono Miden.

Llevando el cálculo verificado basado en pruebas unos pasos más cerca de la practicidad (2012)
por Srinath Setty, Victor Vu, Nikhil Panpalia, Benjamin Braun, Muqeet Ali, Andrew J. Blumberg y Michael Walfish

Este documento, denominado Ginger, es otra contribución temprana a las técnicas prácticas de front-end. Ginger introdujo dispositivos para primitivas de programación general como condicionales y expresiones lógicas, comparaciones y aritmética bit a bit a través de división de bits, aritmética de coma flotante primitiva, etc. Usó estos dispositivos para proporcionar la primera interfaz implementada desde un lenguaje de alto nivel hasta bajo grado. restricciones aritméticas (similares a lo que ahora se conoce como R1CS), una representación intermedia (IR) a la que se puede aplicar un back-end SNARK.

Mientras que el documento de "Reducciones rápidas" y sus descendientes utilizan un enfoque de "emulador de CPU" para producir IR (es decir, el IR hace cumplir que el probador ejecutó correctamente un programa en particular aplicando la función de transición de la CPU para un número específico de pasos) , Ginger y sus descendientes adoptan un enfoque más parecido a ASIC, produciendo IR que se adaptan al programa de computadora que el probador afirma ejecutar correctamente.

Por ejemplo, Bufé muestra que es posible manejar un flujo de control complejo en el modelo ASIC, al convertir dicho flujo de control en una máquina de estado finito adaptada al programa que se está ejecutando, y que este enfoque puede ser significativamente más eficiente que construir un emulador de CPU de uso general. xJsnark brinda una construcción eficiente para aritmética de precisión múltiple, optimizaciones para RAM y ROM, y expone un lenguaje de alto nivel similar a Java para un programador, que sigue siendo popular en la actualidad. CirC observa que la compilación de programas informáticos para R1CS está estrechamente relacionada con técnicas bien conocidas del análisis de programas y crea un conjunto de herramientas de construcción de compiladores que incorpora ideas de ambas comunidades ("LLVM para representaciones similares a circuitos"). Los trabajos anteriores que hicieron contribuciones a los front-end de estilo ASIC incluyen Pinocho y Geppetto.

El documento de "Reducciones rápidas" usó una construcción complicada y costosa llamada "redes de enrutamiento" para los llamados comprobación de memoria (es decir, garantizar que el probador que no es de confianza mantenga correctamente la memoria de acceso aleatorio de la VM durante la ejecución de la VM cuya corrección se está probando). Esta elección se hizo porque los primeros trabajos como este buscaban obtener un PCP, lo que requería que el front-end fuera ambas no interactivo y de información teóricamente segura. Trabajo posterior llamado Despensa (un antecesor del Bufé trabajo mencionado anteriormente) usó Merkle-trees en lugar de redes de enrutamiento, logrando eficiencia al compilar una función hash algebraica (es decir, "amigable con SNARK"), debido a ajtai, en restricciones. Esto resultó en front-ends "computacionalmente seguros". Hoy en día, existe una gran literatura de investigación sobre funciones hash compatibles con SNARK, con ejemplos que incluyen Poseidón, MiMC, Concreto reforzado, Rescate, y más.

Las técnicas de última generación para garantizar que el probador mantenga correctamente la memoria RAM se basan en los métodos denominados de "huellas dactilares invariantes de permutación" que se remontan al menos a Lipton (1989) y utilizado para comprobar la memoria por Blum et al. (1991). Estas técnicas involucran inherentemente la interacción entre un probador y un verificador, pero pueden volverse no interactivas con la transformación Fiat-Shamir. Por lo que sabemos, fueron introducidos a la literatura sobre front-ends prácticos de SNARK por un sistema llamado vRAM.

Las técnicas de huellas dactilares invariantes de permutación ahora se utilizan en muchos front-end y SNARK para abstracciones de máquinas virtuales, que incluyen, por ejemplo, El Cairo. Ideas estrechamente relacionadas reaparecieron en contextos relacionados en los dos trabajos a continuación, que se utilizan ampliamente en la práctica hoy en día.

Pruebas de conocimiento cero en tiempo casi lineal para la ejecución correcta del programa (2018)
por Jonathan Bootle, Andrea Cerulli, Jens Groth, Sune Jakobsen y Mary Maller

Plookup: un protocolo polinomial simplificado para tablas de búsqueda (2020)
por Ariel Gabizon y Zachary Williamson

Los primeros trabajos en front-end representaban operaciones "no aritméticas" (como comprobaciones de rango, operaciones bit a bit y comparaciones de enteros) dentro de circuitos e IR relacionados al dividir elementos de campo en bits, realizar las operaciones en estos bits y luego "empaquetar". el resultado de nuevo en un solo elemento de campo. En términos del tamaño del circuito resultante, esto da como resultado una sobrecarga logarítmica por operación.

Los dos trabajos anteriores (BCGJM y Plookup) brindan técnicas influyentes (basadas en las llamadas "tablas de búsqueda") para representar de manera más eficiente estas operaciones dentro de los circuitos, en un sentido amortizado. En términos generales, para algún parámetro B elegido por el diseñador front-end, estos reducen la cantidad de puertas requeridas para representar cada operación no aritmética en el circuito por un factor logarítmico en B, a costa de que el probador se comprometa criptográficamente a un extra. vector de "consejo" de longitud aproximadamente B.