TL;DR
- **¿Cuál es el proceso de construcción de SNARK? **
Problemas a demostrar-Circuitos aritméticos-R1CS-Polinomios
- ** ¿Por qué convertir a polinomio al final? **
Debido a las características de los polinomios, el tiempo de verificación se acorta de manera efectiva y se logra la simplicidad.
- **¿Cómo lograr el conocimiento cero? **
En pocas palabras, en el proceso de derivación del polinomio, se seleccionan dos números aleatorios más, de modo que el polinomio derivado pueda evitar que el verificador obtenga los coeficientes del polinomio original, es decir, la entrada secreta del probador, de modo que para realizar ZK.
- **¿Cómo lograr la no interacción? **
Antes de que comience la prueba, se introduce un tercero, es decir, una configuración confiable, que asigna al verificador original la tarea de elegir números aleatorios para la configuración confiable, logrando así la no interacción entre el verificador y el probador.
La tecnología ZK ha atraído mucha atención en el campo Web3 en los últimos dos años. A partir de Rollup, cada vez más proyectos en diferentes pistas intentan utilizar la tecnología ZK. Entre ellos, SNARK y STARK son los dos términos más comúnmente escuchados. Para comprender mejor la aplicación de la tecnología ZK en la etapa posterior, **este artículo simplificará la lógica de prueba de SNARK desde una perspectiva no técnica y luego usará * * Scroll’s zk Rollup ** se utiliza como ejemplo para ilustrar el funcionamiento del sistema de prueba zk. **
El propósito del artículo es explicar la lógica básica, que sea fácil de leer. Intentará evitar el uso de terminología y no entrará en detalles como transformaciones matemáticas. Perdónenme por cualquier omisión.
En enero de 2012, Alessandro Chiesa, profesor de la Universidad de California, Berkeley, fue coautor de un artículo sobre SNARK y propuso el término zk-SNARK.
zk-SNARK, nombre completo Zero-Knowledge-Succinct Non-Interactive Argument of Knowledge, es un sistema de prueba que utiliza tecnología ZK. **Cabe señalar que SNARK es el nombre de una clase de esquemas, y existen muchos métodos de combinación diferentes que pueden implementar SNARK. **
- Zero-Knowledge (Conocimiento Cero): El contenido que solo conoce el probador estará oculto, y nadie más podrá verlo excepto el probador.
- Corto (Sucinto): La prueba generada es pequeña y el tiempo de verificación es rápido.
- No interactivo (Non-Interactive): Hay poca o ninguna interacción entre el probador y el verificador.
- Argumento: La verificación del verificador solo es válida para el probador con poder de cómputo limitado, porque el probador con súper poder de cómputo puede falsificar la prueba, es decir, el sistema tiene confiabilidad computacional.
- Conocimiento: El probador solo puede calcular la prueba si conoce alguna información que el verificador no conoce.
Lo que zk-SNARK necesita resolver es el “problema de verificación de cálculo”, es decir, si el verificador puede verificar eficientemente los resultados del cálculo sin conocer la privacidad del probador.
A continuación, se utilizará el proceso de construcción simplificado de zk-SNARK para ilustrar cómo el sistema combina el conocimiento cero para lograr una verificación eficiente. **
Construcción Zk-SNARK
Transformar el problema a demostrar en un polinomio
En pocas palabras, la idea de SNARK es convertir la prueba de si la afirmación es verdadera o no en la prueba de si la igualdad polinomial es verdadera o no.
Todo el proceso de conversión: problemas a verificar ➡ circuito aritmético ➡ R1CS ➡ polinomio ➡ conversión entre polinomios
Pregunta a verificar➡Circuito aritmético
Para probar si una pregunta es verdadera a través del cálculo, la pregunta a probar primero debe transformarse en un problema de cálculo, y cualquier cálculo puede describirse como un circuito aritmético.
Los circuitos aritméticos generalmente se componen de constantes, “compuertas de suma” y “compuertas de multiplicación”. A través de la superposición de compuertas, podemos construir polinomios complejos.
El polinomio construido por el circuito aritmético de la figura anterior es: (Inp1+Inp2)*(-1) = Salida
El problema en realidad es extremadamente complicado de convertir en un circuito aritmético, podemos entenderlo simplemente como: ingresa algún contenido, el contenido es transformado por el circuito, y finalmente genera un resultado. Ahora mismo:
Con base en el concepto de circuitos aritméticos, construimos un circuito aritmético para generar pruebas, a saber:
El circuito contiene dos conjuntos de entradas, la entrada pública x y la entrada secreta w. La entrada pública x significa que el contenido es un valor fijo del problema a probar, que es conocido tanto por el verificador como por el probador, y la entrada secreta w significa que el contenido es conocido solo por el probador.
El circuito aritmético que construimos es C( x, w ) = 0, es decir, ingresamos x y w a través del circuito, y el resultado de salida final es 0. Cuando el probador y el verificador saben que la salida del circuito es 0 y la entrada pública es x, el probador necesita demostrar que conoce la entrada secreta w.
Circuito aritmético ➡R1CS
Finalmente, necesitamos un polinomio, pero el circuito aritmético no se puede convertir directamente en un polinomio, y se necesita R1CS como intermediario entre los dos, por lo que primero se convierte el circuito aritmético en R1CS.
R1CS, nombre completo Rank-1 Constraints (sistema de restricciones de primer orden), es un lenguaje para describir circuitos, que es esencialmente una ecuación matricial-vectorial. Específicamente, R1CS es una secuencia de tres vectores (a,b,c), y la solución de R1CS es un vector s, donde s debe satisfacer la ecuación:
Entre ellos, representa la operación del producto interior.
La conversión matemática específica aquí se puede encontrar en Vatalik: Programas aritméticos cuadráticos: de cero a héroe
Solo necesitamos saber que el papel de **R1CS es limitar la descripción de cada puerta en el circuito aritmético, para que los vectores entre cada puerta satisfagan la relación anterior. **
R1CS➡Polinomio
Después de obtener el medio de R1CS, podemos convertirlo en un polinomio equivalente.
Las conversiones equivalentes entre matrices y polinomios se pueden realizar como se muestra en la siguiente figura:
polinomio
convertir a matriz
De acuerdo con la naturaleza de la transformación equivalente anterior, para una matriz que satisfaga R1CS, podemos usar el método de interpolación de Lagrange para restaurar cada coeficiente del polinomio. Con base en esta relación, podemos derivar la matriz R1CS como una relación polinomial, a saber:
Nota: A, B, C representan un polinomio respectivamente
Un polinomio corresponde a una restricción de la matriz R1CS correspondiente al problema que queremos probar, mediante la conversión anterior podemos saber que si los polinomios satisfacen la relación anterior, significa que nuestra matriz R1CS es correcta, indicando así que el probador está en el circuito aritmético. La entrada secreta para también es correcta.
Hasta este punto, nuestro problema se simplifica a: el verificador selecciona aleatoriamente un número x y le pide al certificador que demuestre que A(x) * B(x)=C(x) es verdadero. significa que la entrada secreta del certificador es correcta.
Conversión entre polinomios
En circuitos aritméticos complejos, hay decenas de miles de puertas y necesitamos verificar si cada puerta satisface la restricción R1CS. En otras palabras, necesitamos verificar la igualdad de A(x) * B(x)=C(x) varias veces, pero la eficiencia de la verificación separada una por una es demasiado baja. ¿Cómo podemos verificar la corrección de todas restricciones de puerta a la vez?sexo?
Para facilitar la comprensión, introducimos un P(x), sea P(x) = A(x) * B(x) – C(x)
Sabemos que cualquier polinomio se puede descomponer en polinomios lineales siempre que tenga solución. Entonces dividimos P(x) en F(x) y H(x), a saber:
Entonces F(x) es público, lo que significa que hay un H(x) = P(x)/F(x), por lo que el polinomio que queremos verificar finalmente se convierte en:
A(x) * B(x) – C(x): Contiene los coeficientes del polinomio, conocidos solo por el probador, es decir, la entrada secreta.
F(x) : Un polinomio público conocido tanto por el verificador como por el probador, es decir, entrada pública.
H(x): El probador lo sabe a través del cálculo, pero el verificador es incognoscible.
**El problema final a probar es: la ecuación polinomial A(x) * B(x) – C(x) = F(x) * H(x), se cumple en todo x. **
Ahora solo es necesario verificar el polinomio una vez para verificar que todas las restricciones satisfacen las relaciones de la matriz.
**Aquí hemos completado la transformación del problema a demostrar en un polinomio que solo necesita ser verificado una vez, dándonos cuenta de la simplicidad del sistema. **
Pero la simplicidad de esta implementación es acortar el tiempo de verificación del verificador, entonces, ¿qué pasa con el tamaño de la prueba?
**Simplemente hablando, en el protocolo de prueba, se utiliza la estructura de árbol de Merkle, que reduce efectivamente el tamaño de la prueba. **
Después de completar todo el proceso de conversión, surgirán naturalmente dos problemas:
- ¿Por qué convertir a polinomio?
Porque los polinomios permiten la simplicidad de la prueba. El problema de la prueba de conocimiento cero es verificar que los cálculos satisfagan múltiples restricciones, y los polinomios pueden verificar múltiples restricciones en un punto. En otras palabras, el verificador tiene que verificar n veces para confirmar el problema, pero ahora solo necesita verificar una vez para confirmar la corrección de la prueba con una alta probabilidad.
- ¿Por qué se pueden establecer dos polinomios A(x) * B(x) – C(x )= F(x) * H(x) verificando un punto en el polinomio?
Esto está determinado por las características de los polinomios, es decir, el resultado del cálculo de un polinomio en cualquier punto puede considerarse como la representación de su identidad única. Para dos polinomios, solo se intersecarán en un número finito de puntos.
Para los dos polinomios anteriores de grado d: A(x) * B(x) – C(x) y F(x) * H(x), si no son iguales, serán como máximo d puntos Se intersecan, es decir, las soluciones en d puntos son iguales.
Después de completar la conversión de polinomios, ingresaremos a la etapa de demostración de polinomios.
Prueba que el polinomio se cumple
Por el bien de la ilustración, usamos el polinomio P(x) = F(x) * H(x).
Ahora, el problema que el probador quiere probar es: en todo x, P(x) = F(x) * H(x).
El proceso de verificación del polinomio anterior por parte del demostrador y el verificador es el siguiente:
- El verificador elige un punto de desafío aleatorio x, asumiendo x = s;
- Después de que el probador reciba s, calcule P(s) y H(s), y entregue estos dos valores al verificador;
- El verificador primero calcula F(s), luego calcula F(s) * H(s), y juzga si F(s) * H(s) = P(s) es verdadero, y si es verdadero, se pasa la verificación.
Pero si pensamos detenidamente, encontraremos que hay algunos problemas en el proceso anterior:
- El probador puede conocer la información de toda la ecuación. Si recibe un punto aleatorio s, puede calcular F(s) y luego construir un par de falsos P(x) y H(x), de modo que P(s ) = F(s) * H(s) para engañar al verificador.
- El probador no utiliza la s dada por el verificador para calcular F(s) y H(s), sino que calcula con otros valores para engañar al verificador.
- El valor recibido por el verificador se calcula mediante la entrada pública y la entrada privada del probador. Si el verificador tiene una gran potencia informática, puede descifrar la entrada privada del probador.
Para resolver los problemas anteriores, hacemos las siguientes optimizaciones:
- Después de que el verificador selecciona un punto aleatorio s, realiza un cifrado homomórfico en s. El cifrado homomórfico significa la solución calculada después del cifrado = la solución cifrada después del cálculo; en esta forma de cifrado, el probador puede calcular la solución, pero no puede construir falso P(x) y H(x).
- Cuando el verificador elige el punto de desafío s, se selecciona otro parámetro aleatorio λ para generar una relación lineal adicional entre s y λ. El verificador envía tanto s como λ después del cifrado homomórfico al probador. El probador devuelve la prueba y el verificador necesita verificar la relación entre el parámetro aleatorio λ y s además de verificar si la prueba es verdadera.
- **Apuntando al problema de que el verificador puede descifrar la entrada secreta, podemos introducir ZK. ** Mirando la prueba completa, podemos encontrar que durante el proceso de verificación, el probador solo envía el valor del polinomio calculado al verificador, y el verificador puede deducir el coeficiente del polinomio a través del valor, que es la entrada secreta del tirador de pruebas. Para evitar que el verificador retroceda, podemos seleccionar dos números aleatorios más y agregar un conjunto de valores al derivar los polinomios A, B y C de R1CS, de modo que el polinomio restaurado sea un orden más que el polinomio original. , de modo que la verificación El lector no puede obtener la información del polinomio original del polinomio encriptado para realizar ZK.
Después de la optimización, encontramos que el sistema de prueba aún requiere interacción entre el verificador y el probador.¿Cómo podemos lograr la no interacción?
Implementar no interactivo
**Para lograr la no interacción, SNARK introduce configuraciones confiables (Configuración). **
En otras palabras, antes del inicio de la prueba, el derecho del verificador a elegir puntos de desafío aleatorios se entrega a un tercero de confianza. Después de que el tercero elige el parámetro aleatorio λ, coloca el λ encriptado en el circuito R1CS. En este manera, se genera CRS (Common Reference String, cadena de referencia pública). El verificador puede obtener su propio Sv del CRS, y el probador puede obtener su propio Sp del CRS.
Cabe señalar que λ debe destruirse después de generar Sv y Sp. Si se filtra λ, puede usarse para falsificar transacciones a través de una verificación falsa.
Flujo de trabajo zk-SNARK
Después de comprender el proceso de construcción de SNARK, basado en el circuito aritmético que construimos que puede generar pruebas, el proceso de prueba de zk-SNARK es el siguiente:
- Configuración: (C circuito, λ) = (Sv, Sp)
A través del circuito C y el parámetro aleatorio λ, se generan los parámetros aleatorios Sv y Sp utilizados por el probador y verificador posterior.
El probador calcula la prueba Π a través del parámetro aleatorio Sp, la entrada pública x y la entrada secreta w.
- Verificar(Sv,x,Π) == (∃ w st C(x,w))
El verificador verifica si C(x,w)=0 existe a través del parámetro aleatorio Sv, la entrada pública x y la prueba Π. Al mismo tiempo, verifique si la prueba es calculada por el circuito C o no.
En este punto, hemos completado la explicación de todo el zk-SNARK. Echemos un vistazo al caso de aplicación real.
Caso: Tome el zk Rollup de Scroll como ejemplo
El papel del sistema de prueba es permitir que el probador convenza al verificador de creer una cosa;
Para el sistema de prueba zk, es hacer creer al verificador que la prueba de conocimiento cero (Zero-knowledge Proof) calculada por el algoritmo zk es verdadera.
Tomamos el zk Rollup de Scroll como ejemplo para ilustrar el funcionamiento del sistema de prueba zk.
Rollup se refiere al cálculo fuera de la cadena y la verificación en la cadena. Para zk Rollup, después de que la transacción se ejecuta fuera de la cadena, el probador debe generar un certificado zk para la nueva raíz de estado generada después de ejecutar la transacción y luego pasar el certificado al contrato L1 Rollup para la verificación en cadena.
Cabe señalar que existen dos tipos de bloques en zk Rollup:
- L1 Rollup block: el bloque enviado a Ethereum
- Bloque L2: un bloque compuesto por transacciones enviadas por usuarios en L2
El siguiente es el flujo de trabajo del zk Rollup de Scroll:
- El usuario inicia una transacción en L2, el secuenciador recupera la transacción, ejecuta la transacción fuera de la cadena y genera un bloque L2 y una nueva raíz de estado; al mismo tiempo, envía los datos de la transacción y la nueva raíz de estado al contrato de resumen en Ethereum (el envío de datos de transacciones es para disponibilidad de datos);
- Cuando se genera el bloque L2, el Coordinador recibirá la pista de ejecución del bloque del Secuenciador y luego asignará aleatoriamente la pista a cualquier Roller;
- Roller convierte la pista de ejecución recibida en circuitos, y genera un certificado de validez para cada circuito, y luego envía el certificado de vuelta al Coordinador;
- Cada vez que se generan k bloques L2, el Coordinador enviará una tarea de agregación a otro Rodillo para agregar las pruebas de k bloques en una sola prueba agregada;
- El coordinador envía una sola prueba de agregación al contrato de resumen, y el contrato de resumen verifica la prueba de agregación combinada con la raíz del estado y los datos de transacción enviados anteriormente. Si se aprueba la verificación, se considera que el bloque correspondiente está finalizado en Scroll.
Como se puede ver en el proceso anterior, Roller es el probador en el sistema y el contrato de Rollup es el verificador. Roller genera una prueba zk para las transacciones ejecutadas fuera de la cadena; el contrato de resumen verifica la prueba y, si pasa la verificación, el contrato de resumen adoptará directamente la raíz del estado enviada como su nueva raíz del estado.
