1. Introducción
ZK-SNARK es un sistema de prueba criptográfica que permite a una entidad demostrar que algo es cierto sin revelar otra información.
Los ZK-SNARK son útiles en múltiples aplicaciones y campos, como blockchain y computación verificable. Una aplicación blockchain notable se utiliza en ZK-Rollups.
Los ZK-Rollups son cadenas de bloques de segunda capa construidas sobre otras cadenas de bloques (como Ethereum) que utilizan ZK-SNARK (u otros sistemas de prueba criptográfica) para demostrar la validez de las transiciones de estado. Es decir, cada vez que se realiza una nueva actualización de la red (se agrega un nuevo lote de transacciones), se calcula un nuevo estado de la red y se genera una prueba de la validez de este estado. La cuestión es que sólo se necesita una entidad para generar esta prueba y cualquiera puede confiar en su validez.
Las propiedades deseadas proporcionadas por ZK-Rollups suelen ser (i) escalabilidad y/o (ii) protección de la privacidad. Los ZK-Rollups a veces se denominan Rollups de efectividad cuando solo se requiere escalabilidad.
Para calcular pruebas en ZK-Rollups diseñados para ampliar EVM de Ethereum, se puede utilizar ZK-EVM. Estrictamente definido, ZK-EVM es un conjunto de programas (circuitos) criptográficos responsables de generar pruebas de conocimiento cero (ZKP), aunque a veces coloquialmente también se refiere al ZK-Rollup universal compatible con EVM en su conjunto.
2. Definición de ZK-SNARK
Un SNARK es una prueba concisa de que una determinada afirmación es cierta. Formalmente, demuestra conocimiento del seguimiento de ejecución de un algoritmo que produce una solución correcta a un determinado problema. Más bien, demuestra conocimiento de valores no públicos y no constantes que realizan el seguimiento. Estos valores en su conjunto suelen denominarse testigos. Los elementos del testigo, es decir, las partes de la entrada al algoritmo, constituyen testigos independientes porque existen antes de la ejecución del algoritmo y no están determinados por otros elementos del seguimiento de ejecución. El valor público no constante del seguimiento de ejecución, que especifica la instancia del problema que resuelve el algoritmo, se denomina declaración pública.
ZK-SNARK significa Argumento de conocimiento no interactivo, sucinto y de conocimiento cero.
S - Simplicidad
Simplicidad: la prueba es "breve" y el tiempo de verificación es "rápido":
Una prueba "breve" significa que el tamaño de la prueba es sublineal, en relación con el tamaño del testigo.
El tiempo de verificación "rápido" significa que el tiempo de ejecución del verificador debe (i) ser sublineal en el tamaño del testigo y (ii) ser lineal en el reclamo público.
Pero, de hecho, queremos que no sólo sea "conciso" sino también "nivel logarítmico polinómico".
Esto significa que el tamaño de la prueba y el tiempo de verificación son casi independientes del tamaño del testigo.
Demuestre que el tamaño de π no debe crecer más rápido que algunas veces constante el cuadrado del logaritmo del tamaño del testigo w (para w suficientemente grande):
El tamaño de la prueba depende del protocolo ZK-SNARK específico. Para Plonky2 es O(log^2(|w|)), pero ese es el "peor" caso. Por ejemplo, para PLONK y Groth16 clásicos, el tamaño de la prueba es O(1), que es una constante.
El tiempo de verificación t_v no debe ser mayor que algunas constantes multiplicadas por el cuadrado del logaritmo del testigo w, y lineal en el tamaño de la declaración pública x (x y w son lo suficientemente grandes cuando solo uno de ellos cambia su tamaño).
N: No interactivo: la generación de pruebas se produce sin recibir ningún dato del verificador.
ARK - Prueba de conocimiento: similar a las pruebas regulares, pero el sonido solo es válido contra probadores polinómicamente acotados, mientras que en las pruebas el sonido es válido contra probadores computacionalmente ilimitados. Discutiremos el concepto de sonido en la siguiente sección.
ZK - Conocimiento cero - Sin divulgación de testigos.
3. Propiedades de ZK-SNARK
Los ZK-SNARK tienen tres propiedades principales, como se describe a continuación:
Integridad: si el probador conoce la trayectoria de ejecución correcta del algoritmo, entonces el verificador debe creer que el probador tiene este conocimiento.
Solidez del conocimiento: a menos que el probador realmente conozca la trayectoria de ejecución correcta, no puede convencer al verificador de que la sabe, pero existe una probabilidad muy pequeña.
Conocimiento cero: el verificador no sabe nada sobre la trayectoria de ejecución excepto que es correcta.
4.Sistema de prueba PLONKish ZK-SNARK
4.1 Introducción a PLONKish ZK-SNARK y sus funciones
Para poder aplicarse a un determinado algoritmo, el sistema de prueba ZK-SNARK necesita conocer el sistema de ecuaciones en el campo finito. Estas ecuaciones describen la relación entre los valores en la tabla de trayectoria de ejecución del algoritmo (la. estructura de datos que almacena la trayectoria de ejecución) para garantizar que el cálculo sea Integridad. El lenguaje utilizado para expresar este sistema de ecuaciones (también llamado sistema de restricciones) se llama aritmética.
El sistema de prueba PLONKish ZK-SNARK utiliza aritmética con mayor poder expresivo que los sistemas de prueba más antiguos. El primero nos permite usar ecuaciones de sistemas de restricciones de forma polinómica arbitraria sobre las variables de restricciones, mientras que para los sistemas de prueba más antiguos (es decir, sistemas basados en R1CS) estas ecuaciones tenían la forma de polinomios lineales y cuadráticos. Esta característica hace que el sistema de prueba PLONKish ZK-SNARK tenga un impacto positivo en la eficiencia computacional del probador y facilita su aplicación a varios algoritmos. Por lo tanto, en los últimos años han aparecido muchos sistemas de prueba PLONKish ZK-SNARK, como el clásico PLONK, Halo2, Kimchi, Plonky2, HyperPlonk, etc.
En Taiko utilizamos una variante del sistema de prueba Halo2 basado en el esquema de compromiso polinomial KZG.
El sistema de prueba PLONKish ZK-SNARK consta de tres componentes:
4.2 Plan de compromiso
El esquema de promesa permite a un confirmador publicar un valor, llamado promesa, que vincula al confirmador a un mensaje sin revelar el mensaje en sí. Luego, el remitente puede abrir el compromiso y exponer el mensaje comprometido, o alguna parte del mismo, al verificador, quien puede verificar si la información expuesta es consistente con el compromiso.
Diferentes autores describen una cantidad diferente de algoritmos que componen un esquema de compromiso. Sin embargo, debemos mencionar al menos cuatro de estos algoritmos:
Configuración: toma algunos parámetros iniciales como entrada y genera parámetros de configuración. La configuración especifica (i) a qué nos comprometemos (por ejemplo, para el esquema de compromiso polinómico unario, especificamos el dominio del coeficiente y el grado máximo del polinomio al que nos comprometemos), y (ii) el nivel de seguridad en bits. Simplemente podemos definir el nivel de seguridad de la siguiente manera: si se necesita O (2 ^ n) tiempo para romper un sistema de cifrado, entonces el sistema de cifrado tiene un nivel de seguridad de n bits.
Promesa: una promesa que genera mensajes basados en parámetros establecidos.
Apertura parcial: genera una prueba de apertura parcial específica de una parte seleccionada del mensaje (por ejemplo, el valor de un polinomio unario comprometido para algún parámetro), además de configurar los parámetros.
Validación: utilice una atestación parcialmente abierta y establezca parámetros para verificar si la información expuesta por el probador es la parte especificada del mensaje correspondiente al compromiso especificado.
*Para algunos esquemas de compromiso, es posible que los algoritmos de "configuración" y "apertura" no existan (por ejemplo, cuando se utiliza una función hash para confirmar valores grandes).
El plan de compromiso debe tener las siguientes características:
Vinculación: una vez que el probador se compromete con un mensaje específico, quedará vinculado al mensaje al que se comprometió;
Ocultar: Promesa de no revelar ninguna información sobre el mensaje. La ocultación puede ser perfecta, es decir, una prueba parcialmente abierta no revela ninguna información sobre la parte no consultada del mensaje (por ejemplo, compromiso KZG), o no perfecta, es decir, una prueba parcialmente abierta revela alguna parte de la información antes mencionada (por ejemplo, basada en FRI). compromiso polinomial).
Los esquemas de compromiso se pueden dividir en varios tipos según el objeto objetivo: compromiso de un solo elemento; compromiso de conjunto;
Los esquemas de compromiso polinomial son el único tipo utilizado directamente en el sistema de prueba PLONKish ZK-SNARK. Para los sistemas de prueba anteriores (como el PLONK clásico, Halo2, Kimchi, Plonky2, etc.), el esquema de compromiso polinómico univariante es muy importante. Sin embargo, ahora existen algunos métodos PLONKish ZK-SNARK nuevos basados en esquemas de compromiso polinomial multilineal (por ejemplo, HyperPlonk).
4.3 Prueba interactiva de Oracle
Una prueba interactiva de Oracle es una prueba interactiva en la que el verificador tiene "acceso al oráculo" para obtener los mensajes del probador, puede consultarlos de manera probabilística y no necesita leer los mensajes completos del probador.
4.4 Heurística Fiat-Shamir
La heurística Fiat-Shamir proporciona una manera de transformar argumentos interactivos (monedas públicas) en argumentos no interactivos. Intuitivamente, la idea es reemplazar el desafío aleatorio del validador con el hash del mensaje anterior, pero los detalles generalmente no se especifican.
*Public Coin Protocol es un protocolo donde los validadores solo envían elementos aleatorios.
4.5 Principio de funcionamiento del sistema de prueba ZK-SNARK estilo PLONK
En el sistema de prueba ZK-SNARK, se utiliza un método de prueba interactivo de Oracle modificado para probar el conocimiento del testigo, que utiliza compromisos polinomiales para proporcionar acceso de Oracle al mensaje del probador y lo hace interactivo a través de la heurística Fiat-Shamir. En esta sección, explicaremos en detalle el constructor dado.
Recuerde que aplicar el sistema de prueba ZK-SNARK a un algoritmo requiere construir un sistema de restricciones correspondiente. Para poder construirlo, definimos la estructura de la tabla de seguimiento de ejecución del algoritmo y los valores constantes que contiene. Usamos el término "circuito" para referirnos a la estructura compleja de una tabla de seguimiento de ejecución poblada únicamente con constantes y el sistema de restricciones correspondiente. Para generar una prueba ZK-SNARK para una instancia de ejecución de un algoritmo, necesitamos sintetizar una instancia de circuito que sea una instancia correspondiente del circuito del algoritmo y la tabla de seguimiento de ejecución (es decir, una tabla que especifica constantes, testigos, y valores de declaración pública).
Consideremos la estructura de la mesa de seguimiento utilizada por un sistema de prueba ZK-SNARK estilo PLONK. Todas las columnas de dicha tabla pertenecen a uno de tres tipos, que denominamos según la terminología utilizada en Halo2 y que describimos de la siguiente manera:
Columnas fijas: sus celdas contienen constantes de la tabla de seguimiento de ejecución;
Columna de instancia: utilizada para almacenar valores de declaración pública;
Columna de sugerencias: donde se almacenan todos los datos de los testigos (incluidos los valores de los testigos independientes y los resultados secretos calculados).
A modo de resumen, destacamos lo siguiente:
Tabla de seguimiento de ejecución (tipo PLONKish) = columnas fijas + columnas de instancia + columnas de sugerencia; tabla de seguimiento de ejecución que contiene solo constantes + sistema de restricciones; circuito + testigos en su tabla + declaraciones públicas en su tabla: (Circuito, declaración pública, valor de testigo independiente) → Instancia de circuito; aplicar el sistema de prueba ZK-SNARK a un determinado algoritmo = describir el circuito + definir el proceso de síntesis.
¿Por qué se utiliza ampliamente el término "circuito" en este contexto? Inicialmente, cuando sólo estaban disponibles los sistemas de prueba ZK-SNARK basados en R1CS, era conveniente representar el sistema de restricciones en forma de un circuito aritmético, cuya salida debía ser cero. Creemos que en el contexto de PLONKish SNARK el término "circuito" se utiliza por razones históricas. De todos modos, consideremos brevemente el circuito aritmético utilizado para versiones anteriores de ZK-SNARK.
El circuito aritmético para SNARK basados en R1CS define un polinomio de n variables sobre un campo finito y tiene un esquema de evaluación. Inicialmente, se representa como un gráfico acíclico dirigido (DAG):
incluye:
Entrada pública x, utilizada para especificar el valor de la declaración pública;
Entrada secreta w, utilizada para especificar el valor del testigo independiente;
Puertas aritméticas para especificar la suma y la multiplicación en campos finitos.
Veamos un ejemplo de un circuito aritmético sobre el campo de números racionales.
Comenzamos desde abajo y trabajamos con las puertas más bajas del diagrama, es decir (2 x 4 = 8) y (4 + 11 = 15), guardando estos valores como valores intermedios;
Luego subimos una fila (a la segunda fila) y calculamos la suma de los dos valores intermedios (que obtuvimos en la etapa anterior), que es (8 + 15 = 23);
Como solo tenemos tres puertas y las atravesamos todas, 23 es nuestro resultado final.
Después de que el sistema de prueba PLONKish ZK-SNARK sintetiza la instancia del circuito, las columnas de la tabla de seguimiento de ejecución de cada instancia se codifican como polinomios sobre campos finitos de la siguiente manera. Supongamos que C_j(x) es un polinomio que describe la columna j y ω es una raíz primitiva 2^k-ésima, donde k se elige de modo que 2^k sea ligeramente mayor que la altura inicial de la instancia de la tabla. La instancia de la tabla se completa con filas aleatorias (solo con celdas distintas de cero en las columnas sugeridas) para contener 2^k filas, y C_j(ω^i) se establece en el valor de la i-ésima fila de la j-ésima columna de la instancia de tabla dada. El papel del relleno para los atributos de conocimiento cero se explicará más adelante.
La afirmación "ω es una raíz primitiva 2^k-ésima" significa que ω^(2^k) = 1, y tenemos ω^t ≠ 1 para cualquier entero positivo t menor que 2^k.
El sistema de restricciones se convierte en forma de ecuación polinómica reemplazando las variables que contiene con los polinomios correspondientes obtenidos de los polinomios de la columna, sustituyendo "x por ω elevado a alguna potencia" en lugar de x.
Por ejemplo, consideremos la ecuación del sistema de restricciones s(i) * (a(i) * b(i) - c(i+1)) = 0. Significa que si s(i) es distinto de cero, entonces a(i) * b(i) debe ser igual a c(i+1). Aquí, a, byc son las columnas sugeridas, s es la columna fija e i es el número de fila actual.
Esta restricción se puede aplicar a las 2^k filas de la siguiente manera. Sean S(x), A(x), B(x) y C(x) polinomios en las columnas a, b, cys respectivamente. Por lo tanto esperamos:
Esto significa que todos los elementos de este conjunto deben ser raíces de S(x) * (A(x) * B(x) - C(x * ω)). Por tanto, este polinomio debe ser divisible por:
Porque ω es una raíz primitiva de orden 2^k.
Z(x) = x^(2^k) - 1 se llama "polinomio evanescente" porque es 0 para todos los x que son elementos del grupo multiplicativo cíclico generado por ω. Por lo tanto, S(x) * (A(x) * B(x) - C(x * ω)) mod Z(x) = 0 significa que las restricciones anteriores se cumplen para las 2^k filas.
Supongamos que P_0(x), P_1(x), ..., P_m(x) son restricciones aplicadas a las 2^k filas y son consistentes con el polinomio S(x) * (A(x) * B(x) considerado arriba ) - C(x * ω)) tiene una forma similar. Si el verificador elige aleatoriamente α del campo finito, entonces
Esto significa que con una probabilidad extremadamente alta todas estas restricciones se cumplen para las 2^k filas. Esta ecuación significa que podemos encontrar un polinomio cociente T(x) tal que
Por lo tanto, para que el verificador crea que el probador conoce el contenido de la tabla de seguimiento de ejecución que satisface todas las m restricciones con una probabilidad muy alta, sólo necesita demostrar que para un α seleccionado aleatoriamente, el probador tiene las ocurrencias P_0 (x), P_1(x ),..., los polinomios de columna sugeridos y los polinomios cocientes T(x) en P_m(x) satisfacen esta ecuación polinómica. El verificador puede hacer esto pidiéndole que encuentre el valor de un polinomio dado en un punto aleatorio elegido por el verificador entre los puntos no raíz ζ de Z(x), y que evalúe ambos lados de esa ecuación en ese punto. ζ. Creo que el probador probablemente conoce estos polinomios. Este método puede demostrarse mediante el lema de Schwartz-Zippel.
Para que la generación de pruebas no sea interactiva, todos los valores aleatorios generados por el verificador en la versión interactiva deben obtenerse utilizando la heurística Fiat-Shamir.
Para vincular el probador a su polinomio propuesto y al polinomio cociente T(x), se utiliza un esquema de compromiso polinomial. El demostrador hace compromisos sobre estos polinomios, abre estos compromisos en ζ (o en ζ * ω^q si alguna restricción afecta las filas i e i + q) y crea una prueba que incluye (I) estos compromisos, (II) el valor del polinomio en ζ (o sobre ζ * ω^q si es necesario) y (III) la prueba abierta correspondiente. En realidad, para acortar la prueba, utilice la apertura múltiple, es decir, genere una pequeña prueba para los valores de todos los puntos polinomiales. Por tanto, la prueba es concisa.
Para satisfacer la propiedad de conocimiento cero, las filas seleccionadas aleatoriamente por el probador se agregan a la instancia de la tabla de seguimiento de ejecución, lo que hace que su altura sea de 2^k filas. Estas filas solo tienen celdas distintas de cero en la columna de sugerencias porque solo la columna de sugerencias contiene los datos que queremos ocultar. Haga esto antes de construir los polinomios de la columna propuesta de modo que el número de pares de "valores de parámetros" revelados durante el período de apertura del compromiso sea menor que el número de pares agregados aleatoriamente para cada polinomio. Por lo tanto, para cada polinomio de columna de propuesta, la cantidad de información requerida para recuperarlo después de que se abre el compromiso es mayor que la cantidad de información testigo. Esta situación resulta en conocimiento nulo.
Durante la fase de preprocesamiento, todas las instancias del circuito de ejecución realizan algunos de los mismos cálculos, incluida la configuración y el cálculo de polinomios de columnas fijas y sus compromisos para el esquema de compromiso de polinomios. El verificador utiliza la parte de los datos producidos por estos cálculos y, a menudo, se denomina clave de verificación. De manera similar, se puede definir el concepto de clave de prueba. El esquema de compromiso polinómico subyacente determina si se realizan configuraciones de confianza durante la fase de preprocesamiento.
