Los ARgumentos de conocimiento cero, concisos y no interactivos (zk-SNARKs) son poderosas primitivas criptográficas que permiten a una parte, el probador, convencer a otra parte, el verificador, de que una declaración dada es verdadera sin revelar nada más que la validez de la declaración. Han ganado una amplia atención debido a sus aplicaciones en la computación privada verificable, proporcionando pruebas de la corrección de la ejecución de programas informáticos y ayudando a escalar blockchains. Creemos que los SNARK tendrán un impacto significativo en la configuración de nuestro mundo, como describimos en nuestra publicación. SNARKs actúa como un paraguas para diferentes tipos de sistemas de prueba, utilizando diferentes esquemas de compromiso polinómico (PCS), esquemas de aritmética, pruebas de oráculo interactivo (IOP) o pruebas probabilísticamente verificables (PCP). Sin embargo, las ideas y conceptos básicos se remontan a mediados de la década de 1980. El desarrollo se aceleró significativamente después de la introducción de Bitcoin y Ethereum, que demostraron ser un caso de uso emocionante y poderoso, ya que puede escalarlos mediante el uso de pruebas de conocimiento cero (generalmente llamadas pruebas de validez para este caso de uso en particular). Los SNARK son una herramienta esencial para la escalabilidad de la cadena de bloques. Como describe Ben-Sasson, en los últimos años se ha producido una explosión cámbrica de pruebas criptográficas. Cada sistema de prueba ofrece ventajas y desventajas y fue diseñado teniendo en cuenta ciertas compensaciones. Los avances en hardware, mejores algoritmos, nuevos argumentos y gadgets dan como resultado un mejor rendimiento y el nacimiento de nuevos sistemas. Muchos de ellos se utilizan en la producción, y seguimos superando los límites. ¿Tendremos un sistema de prueba general para todas las aplicaciones o varios sistemas adecuados para diferentes necesidades? Creemos que es poco probable que un sistema de prueba los gobierne a todos porque:

1. La diversidad de aplicaciones.
2. Los tipos de restricciones que tenemos (con respecto a la memoria, los tiempos de verificación, los tiempos de prueba).
3. La necesidad de robustez (si un sistema de prueba se rompe, todavía tenemos otros).

Incluso si los sistemas de prueba cambian mucho, todos ofrecen una propiedad significativa: las pruebas se pueden verificar rápidamente. Tener una capa que verifique las pruebas y que se pueda adaptar fácilmente para manejar nuevos sistemas de prueba resuelve las dificultades asociadas con el cambio de la capa base, como Ethereum. Para dar una visión general de las diferentes características de los SNARK:

• Supuestos criptográficos: funciones hash resistentes a colisiones, problema de registro discreto sobre curvas elípticas, conocimiento del exponente.
• Configuración transparente frente a configuración de confianza.
• Tiempo de prueba: lineal vs superlineal.
• Tiempo verificador: tiempo constante, logarítmico, sublineal, lineal.
• Tamaño de la prueba.
• Facilidad de recursividad.
• Esquema de aritmética.
• Polinomios univariados vs multivariados.

Esta publicación analizará los orígenes de los SNARK, algunos bloques de construcción fundamentales y el auge (y caída) de los diferentes sistemas de prueba. El post no pretende ser un análisis exhaustivo de los sistemas de prueba. En cambio, nos enfocamos en aquellos que tuvieron un impacto en nosotros. Por supuesto, estos desarrollos solo fueron posibles con el gran trabajo e ideas de los pioneros de este campo.

Fundamentos

Como mencionamos, las pruebas de conocimiento cero no son nuevas. Las definiciones, los fundamentos, los teoremas importantes e incluso los protocolos importantes se establecieron a partir de mediados de la década de 1980. Algunas de las ideas y protocolos clave que utilizamos para construir SNARK modernos se propusieron en la década de 1990 (el protocolo sumcheck) o incluso antes de la llegada de Bitcoin (GKR en 2007). Los principales problemas con su adopción estaban relacionados con la falta de un caso de uso potente (Internet no estaba tan desarrollado en la década de 1990) y la cantidad de potencia computacional necesaria.

Pruebas de conocimiento cero: los orígenes (1985/1989)

El campo de las pruebas de conocimiento cero hizo su aparición en la literatura académica con el artículo de Goldwasser, Micali y Rackoff. Para una discusión sobre los orígenes, puede ver el siguiente video. El artículo introdujo las nociones de completitud, solidez y conocimiento cero, proporcionando construcciones para la residualidad cuadrática y la no residualidad cuadrática.

Protocolo Sumcheck (1992)

El protocolo de verificación de sumas fue propuesto por Lund, Fortnow, Karloff y Nisan en 1992. Es uno de los bloques de construcción más importantes para pruebas interactivas sucintas. Nos ayuda a reducir una afirmación sobre la suma de las evaluaciones de un polinomio multivariante a una sola evaluación en un punto elegido al azar.

Goldwasser-Kalai-Rothblum (GKR) (2007)

El protocolo GKR es un protocolo interactivo que tiene un probador que se ejecuta linealmente en el número de puertas de un circuito, mientras que el verificador se ejecuta sublinealmente en el tamaño del circuito. En el protocolo, el probador y el verificador acuerdan un circuito aritmético de abanico en dos sobre un campo finito de profundidad d, donde la capa d corresponde a la capa de entrada y la capa 0 es la capa de salida. El protocolo comienza con una reivindicación relativa a la salida del circuito, que se reduce a una reivindicación sobre los valores de la capa anterior. Usando la recursividad, podemos convertir esto en una afirmación sobre las entradas del circuito, que se puede verificar fácilmente. Estas reducciones se logran a través del protocolo de verificación de sumas.

Esquema de compromiso polinómico KZG (2010)

Kate, Zaverucha y Goldberg introdujeron en 2010 un esquema de compromiso para polinomios utilizando un grupo de emparejamiento bilineal. El compromiso consiste en un solo elemento de grupo, y el committer puede abrir eficientemente el compromiso a cualquier evaluación correcta del polinomio. Además, debido a las técnicas de dosificación, la apertura se puede hacer a varias evaluaciones. Los compromisos de KZG proporcionaron uno de los componentes básicos para varios SNARK eficientes, como Pinocho, Groth16 y Plonk. También está en el corazón del EIP-4844. Para tener una intuición sobre las técnicas de procesamiento por lotes, puede ver nuestra publicación sobre el puente Mina-Ethereum.

SNARKs prácticos que utilizan curvas elípticas

Las primeras construcciones prácticas para SNARK aparecieron en 2013. Estos requerían un paso de preprocesamiento para generar las claves de prueba y verificación, y eran específicos del programa/circuito. Estas claves podían ser bastante grandes, y dependían de parámetros secretos que debían permanecer desconocidos para las partes; de lo contrario, podrían falsificar pruebas. Transformar el código en algo que pudiera ser probado requería compilar el código en un sistema de restricciones polinómicas. Al principio, esto tenía que hacerse de forma manual, lo que lleva mucho tiempo y es propenso a errores. Los avances en esta área trataron de eliminar algunos de los principales problemas:

1. Tener probadores más eficientes.
2. Reduzca la cantidad de preprocesamiento.
3. Tener configuraciones universales en lugar de específicas del circuito.
4. Evite tener configuraciones confiables.
5. Desarrollar formas de describir circuitos utilizando un lenguaje de alto nivel, en lugar de escribir las restricciones polinómicas manualmente.

Pinocho (2013)

Pinocho es el primer zk-SNARK práctico y utilizable. El SNARK se basa en programas aritméticos cuadráticos (QAP). El tamaño de la prueba era originalmente de 288 bytes. La cadena de herramientas de Pinocho proporcionó un compilador de código C a circuitos aritméticos, que se transformó aún más en un QAP. El protocolo requería que el verificador generara las claves, que son específicas del circuito. Utilizó pares de curvas elípticas para comprobar las ecuaciones. La asintótica para la generación de pruebas y la configuración de claves fue lineal en el tamaño del cálculo, y el tiempo de verificación fue lineal en el tamaño de las entradas y salidas públicas.

Groth 16 (2016)

Groth introdujo un nuevo argumento de conocimiento con un mayor rendimiento para problemas descritos por un R1CS. Tiene el tamaño de prueba más pequeño (solo tres elementos de grupo) y una verificación rápida que involucra tres emparejamientos. También implica un paso de preprocesamiento para obtener la cadena de referencia estructurada. El principal inconveniente es que requiere una configuración de confianza diferente por programa que queremos probar, lo cual es un inconveniente. Groth16 se utilizó en ZCash.

A prueba de balas e IPA (2016)

Uno de los puntos débiles del KZG PCS es que requiere una configuración confiable. Bootle y cols. introdujo un sistema eficiente de argumentos de conocimiento cero de aperturas de compromisos de Pedersen que satisfacen una relación interna de producto. El argumento del producto interno tiene un probador lineal, con comunicación e interacción logarítmica, pero con verificación de tiempo lineal. También desarrollaron un esquema de compromiso polinómico que no requiere una configuración confiable. Los PCS que usan estas ideas son utilizados por Halo 2 y Kimchi.

Sonic, Marlin y Plonk (2019)

Sonic, Plonk y Marlin resuelven el problema de la configuración confiable por programa que teníamos en Groth16, mediante la introducción de cadenas de referencia estructuradas universales y actualizables. Marlin proporciona un sistema de prueba basado en R1CS y es el núcleo de Aleo.

Plonk introdujo un nuevo esquema de aritmética (más tarde llamado Plonkish) y el uso de la comprobación de gran producto para las restricciones de copia. Plonkish también permitió la introducción de puertas especializadas para ciertas operaciones, las llamadas puertas personalizadas. Varios proyectos tienen versiones personalizadas de Plonk, incluidos Aztec, zkSync, Polygon ZKEVM, Mina's Kimchi, Plonky2, Halo 2 y Scroll, entre otros.

Búsquedas (2018/2020)

Gabizon y Williamson introdujeron plookup en 2020, utilizando la comprobación del gran producto para demostrar que un valor está incluido en una tabla de valores precalculada. Aunque los argumentos de búsqueda se presentaron anteriormente en Arya, la construcción requirió la determinación de las multiplicidades para las búsquedas, lo que hace que la construcción sea menos eficiente. El artículo de PlonkUp mostró cómo introducir el argumento plookup en Plonk. El problema con estos argumentos de búsqueda era que obligaban al probador a pagar el precio de toda la tabla, independientemente de su número de búsquedas. Esto implica un costo considerable para tablas grandes, y se ha dedicado mucho esfuerzo a reducir el costo del probador a solo el número de búsquedas que utiliza.
Haböck introdujo LogUp, que utiliza la derivada logarítmica para convertir el cheque del gran producto en una suma de recíprocos. LogUp es crucial para el rendimiento en el Polygon ZKEVM, donde necesitan dividir toda la tabla en varios módulos STARK. Estos módulos deben estar vinculados correctamente, y las búsquedas entre tablas lo refuerzan. La introducción de LogUp-GKR utiliza el protocolo GKR para aumentar el rendimiento de LogUp. Caulk fue el primer esquema con tiempo de prueba sublineal en el tamaño de la tabla mediante el uso del tiempo de preprocesamiento O(NlogN) y el almacenamiento O(N), donde N es el tamaño de la tabla. Le siguieron otros esquemas, como Baloo, flookup, cq y caulk+. Lasso presenta varias mejoras, evitando comprometerse con la mesa si tiene una estructura dada. Además, el probador de Lasso solo paga por las entradas de tabla a las que acceden las operaciones de búsqueda. Jolt aprovecha Lasso para probar la ejecución de una máquina virtual a través de búsquedas.

Espartano (2019)

Spartan proporciona una IOP para circuitos descritos mediante R1CS, aprovechando las propiedades de los polinomios multivariantes y el protocolo de comprobación de sumas. Utilizando un esquema de compromiso polinómico adecuado, da como resultado un SNARK transparente con un probador de tiempo lineal.

HyperPlonk (2022)

HyperPlonk se basa en las ideas de Plonk utilizando polinomios multivariantes. En lugar de cocientes para comprobar la aplicación de las restricciones, se basa en el protocolo de comprobación de suma. También soporta restricciones de alto grado sin perjudicar el tiempo de funcionamiento del probador. Dado que se basa en polinomios multivariantes, no es necesario realizar FFT y el tiempo de ejecución del probador es lineal en el tamaño del circuito. HyperPlonk presenta una nueva IOP de permutación adecuada para campos más pequeños y un protocolo de apertura de lotes basado en la verificación de suma, que reduce el trabajo del probador, el tamaño de la prueba y el tiempo del verificador.

Esquemas de plegado (2008/2021)

Nova introduce la idea de un esquema de plegado, que es un nuevo enfoque para lograr la computación verificable incremental (IVC). El concepto de IVC se remonta a Valiant , quien mostró cómo fusionar dos pruebas de longitud k en una sola prueba de longitud k. La idea es que podemos probar cualquier cálculo de larga duración demostrando recursivamente que la ejecución del paso i al paso I+1+1 es correcta y verificando una prueba que muestre que la transición del paso i

−1−1Al paso I estaba en lo correcto. Nova maneja bien los cálculos uniformes; más tarde se amplió para manejar diferentes tipos de circuitos con la introducción de Supernova. Nova utiliza una versión relajada de R1CS y trabaja sobre curvas elípticas amistosas. Trabajar con ciclos amistosos de curvas (por ejemplo, las curvas de pasta) para lograr la VCI también se usa en Pickles, el principal componente de Mina para lograr un estado sucinto. Sin embargo, la idea de plegado difiere de la verificación recursiva de SNARK. La idea del acumulador está más profundamente conectada con el concepto de pruebas por lotes. Halo introdujo la noción de acumulación como una alternativa a la composición de prueba recursiva. Protostar proporciona un esquema IVC no uniforme para Plonk que admite puertas de alto grado y búsquedas vectoriales.

Uso de funciones hash resistentes a colisiones

Casi al mismo tiempo que se desarrolló Pinocho, hubo algunas ideas para generar circuitos/esquemas de aritmética que pudieran probar la corrección de la ejecución de una máquina virtual. A pesar de que el desarrollo de la aritmética de una máquina virtual podía ser más complejo o menos eficiente que escribir circuitos dedicados para algunos programas, ofrecía la ventaja de que cualquier programa, por complicado que fuera, podía probarse demostrando que se ejecutaba correctamente en la máquina virtual. Las ideas de TinyRAM se mejoraron más tarde con el diseño de la máquina virtual Cairo y las máquinas virtuales posteriores (como zk-evms o zkvms de propósito general). El uso de funciones hash resistentes a colisiones eliminó la necesidad de configuraciones confiables o el uso de operaciones de curva elíptica, a expensas de pruebas más largas.

TinyRAM (2013)

En SNARKs for C, desarrollaron un SNARK basado en un PCP para demostrar la corrección de la ejecución de un programa en C, que se compila en TinyRAM, un ordenador con un conjunto de instrucciones reducido. La computadora usaba una arquitectura de Harvard con memoria de acceso aleatorio direccionable a nivel de bytes. Aprovechando el no determinismo, el tamaño del circuito es cuasilineal en el tamaño de la computación, manejando de manera eficiente bucles arbitrarios y dependientes de datos, flujo de control y accesos a memoria.

LOS ESTABLOS (2018)

Los STARK fueron introducidos por Ben Sasson et al. en 2018. Logran O(log2n)(log2)

Los tamaños de prueba, con probador y verificador rápidos, no requieren una configuración confiable y se conjetura que son seguros poscuánticos. Fueron utilizados por primera vez por Starkware/Starknet, junto con el Cairo vm. Entre sus principales introducciones se encuentran la representación intermedia algebraica (AIR) y el protocolo FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity). También es utilizado por otros proyectos (Polygon Miden, Risc0, Winterfell, Neptune) o ha visto adaptaciones de algunos componentes (zkSync's Boojum, Plonky2, Starky).

Ligero (2017)

Ligero presenta un sistema de pruebas que consigue pruebas cuyo tamaño es

O(√n), donde n es el tamaño del circuito. Organiza los coeficientes polinómicos en forma de matriz y utiliza códigos lineales.
Brakedown se basa en Ligero e introduce la idea de esquemas de compromiso polinómico independientes del campo.

Algunas novedades

El uso de diferentes sistemas de prueba en la producción mostró los méritos de cada uno de los enfoques y condujo a nuevos desarrollos. Por ejemplo, la aritmética plonkish ofrece una forma sencilla de incluir puertas personalizadas y argumentos de búsqueda; FRI ha demostrado un gran rendimiento como PCS, lo que ha llevado a Plonky. Del mismo modo, el uso de la comprobación de producto general en AIR (que conduce a AIR aleatorio con preprocesamiento) mejoró su rendimiento y simplificó los argumentos de acceso a la memoria. Los compromisos basados en funciones hash han ganado popularidad, basándose en la velocidad de las funciones hash en el hardware o en la introducción de nuevas funciones hash compatibles con SNARK.

Nuevos esquemas de compromiso polinómico (2023)

Con el advenimiento de SNARKs eficientes basados en polinomios multivariantes, como Spartan o HyperPlonk, ha habido un creciente interés en nuevos esquemas de compromiso adecuados para este tipo de polinomios. Binius, Zeromorph y Basefold proponen nuevas formas para comprometerse con polinomios multilineales. Binius ofrece la ventaja de no tener sobrecarga para representar tipos de datos (mientras que muchos sistemas de prueba utilizan al menos elementos de campo de 32 bits para representar bits individuales) y funciona sobre campos binarios. El compromiso adapta el sistema brakedown, que fue diseñado para ser independiente del campo. Basefold generaliza FRI a códigos distintos de Reed-Solomon, lo que lleva a un PCS independiente del campo.

Sistemas de restricción personalizables (2023)

CCS generaliza R1CS mientras captura la aritmética R1CS, Plonkish y AIR sin sobrecargas. El uso de CCS con Spartan IOP produce SuperSpartan, que admite restricciones de alto grado sin tener el probador para incurrir en costos criptográficos que escalan con el grado de la restricción. En particular, SuperSpartan produce un SNARK para AIR con un probador de tiempo lineal.

Conclusión

Esta publicación describe los avances de los SNARK desde su introducción a mediados de la década de 1980. Los avances en informática, matemáticas y hardware, junto con la introducción de blockchain, han dado lugar a SNARK nuevos y más eficientes, abriendo la puerta a muchas aplicaciones que podrían transformar nuestra sociedad. Los investigadores e ingenieros han propuesto mejoras y adaptaciones a los SNARK de acuerdo con sus necesidades, centrándose en el tamaño de la prueba, el uso de la memoria, la configuración transparente, la seguridad poscuántica, el tiempo de prueba y el tiempo de verificación. Si bien originalmente había dos líneas principales (SNARKs vs STARKs), la frontera entre ambas ha comenzado a desvanecerse, tratando de combinar las ventajas de los diferentes sistemas de prueba. Por ejemplo, combinando diferentes esquemas de aritmética con nuevos esquemas de compromiso polinómico. Podemos esperar que los nuevos sistemas de prueba continúen aumentando, con un mayor rendimiento, y será difícil para algunos sistemas que requieren algún tiempo de adaptación mantenerse al día con estos desarrollos, a menos que podamos usar fácilmente estas herramientas sin tener que cambiar parte de la infraestructura central.

Renuncia:

1. Este artículo es una reimpresión de [lambdaclass], Todos los derechos de autor pertenecen al autor original [LambdaClass]. Si hay objeciones a esta reimpresión, comuníquese con el equipo de Gate Learn y ellos lo manejarán de inmediato.
2. Descargo de responsabilidad: Los puntos de vista y opiniones expresados en este artículo son únicamente los del autor y no constituyen ningún consejo de inversión.
3. Las traducciones del artículo a otros idiomas son realizadas por el equipo de Gate Learn. A menos que se mencione, está prohibido copiar, distribuir o plagiar los artículos traducidos.