Autor: 0xAlpha Cofundadora @DeriProtocol; Compilador: DODO Research
Introducción
zk-SNARKs, o “argumentos de conocimiento no interactivos concisos de conocimiento cero”, permiten a un verificador confirmar que un probador tiene ciertos conocimientos específicos, conocidos como testigos, que satisfacen relaciones específicas sin revelar nada sobre el testigo en sí.
La generación de zk-SNARKs para un problema específico consta de las siguientes cuatro fases:
- Convertir un problema (o función) en un circuito de puerta aritmética.
- Este circuito se traduce en una fórmula matricial.
- Esta fórmula matricial se convierte además en un polinomio, que debe ser divisible por un polinomio mínimo específico.
- Finalmente, esta divisibilidad se representa en puntos de curva elíptica en cuerpos finitos, donde tiene lugar la demostración.
Los tres primeros pasos simplemente convierten la representación de la instrucción original. El paso final utiliza el cifrado homomórfico para proyectar la instrucción del paso 3 en el espacio criptográfico, lo que permite al probador verificar la instrucción espejo en él. Dado que esta proyección hace uso de criptografía asimétrica, no es factible remontarse a la declaración original del paso tres, lo que garantiza la exposición de conocimiento cero.
La formación en matemáticas requerida para leer este artículo es equivalente al nivel de álgebra de primer año para las carreras STEM. El único concepto que puede ser desafiante es probablemente el cifrado de curva elíptica. Para aquellos que no están familiarizados con esto, se puede considerar como una función exponencial con una cardinalidad especial, teniendo en cuenta que su inversa sigue sin resolverse.
Este artículo seguirá las siguientes reglas de notación:
- Matriz: letras mayúsculas en negrita, por ejemplo, A; Escribir explícitamente en el formulario
- Vector: letras minúsculas con flechas, escritas en forma explícita [ ] ; De forma predeterminada, todos los vectores son vectores columnares
- Escalar: Representación regular de letras
Usemos esta pregunta como ejemplo:
f(x)=x^3+x^2+5 (1)
Digamos que Alicia quiere demostrar que conoce uno. Vamos a repasar todo el procedimiento que Alice debe seguir para generar zk-SNARKs para sus pruebas.
Esta pregunta puede parecer demasiado simple porque no implica un flujo de control (por ejemplo, si-entonces-no). Sin embargo, no es difícil convertir una función con un flujo de control en una expresión aritmética. Por ejemplo, consideremos la siguiente pregunta (o “función” en un lenguaje de programación):
f(x, z):
if(z==1):
return x*x*x+x*x+5
más:
return x*x+5
Es fácil reescribir este problema en la siguiente expresión aritmética (asumiendo que z pertenece a (0,1)), que no es mucho más complicada que la ecuación (1).
f(x,z)=(z-1)(x^2+5)+z(x^3+x^2+5)
En este artículo, continuaremos usando la ecuación (1) como base para la discusión.
Paso 1: Circuito de puerta aritmética
La ecuación (1) se puede descomponer en las siguientes operaciones aritméticas básicas:
! [El Poder de las Pruebas de Conocimiento Cero: Decodificando matemáticamente zk-SNARKs] (https://img.jinse.cn/7128057_watermarknone.png)
Esto corresponde al siguiente circuito de puerta aritmética:
! [El Poder de las Pruebas de Conocimiento Cero: Decodificando matemáticamente zk-SNARKs] (https://img.jinse.cn/7127628_watermarknone.png)
También nos referimos a la ecuación (2) como un conjunto de 4 “restricciones de primer orden”, cada una de las cuales describe la relación de una puerta aritmética en un circuito. En general, un conjunto de n restricciones de primer orden se puede generalizar como un procedimiento aritmético cuadrático (QAP), que se explicará a continuación.
Paso 2: Matriz
Primero, definamos un vector “testigo” de la siguiente manera:
! [El Poder de las Pruebas de Conocimiento Cero: Decodificando matemáticamente zk-SNARKs] (https://img.jinse.cn/7128058_watermarknone.png)
donde y, s1, s2, s3 son los mismos que se definen en la ecuación (2).
En general, para un problema con m entradas y n puertas aritméticas (es decir, n-1 pasos intermedios y salida final), este vector testigo será (m + n + 1) dimensional. En un problema práctico, el número n puede ser muy grande. Por ejemplo, para una función hash, n suele ser unos pocos miles.
A continuación, construyamos tres matrices n*(m+n+*1) A,B,C para que podamos reescribir la ecuación (2) de la siguiente manera:
! [El Poder de las Pruebas de Conocimiento Cero: Decodificando matemáticamente zk-SNARKs] (https://img.jinse.cn/7128059_watermarknone.png)
La ecuación (3) no es más que otra representación de la ecuación (2): cada grupo (ai, bi, ci) corresponde a una puerta en el circuito. Solo necesitamos expandir sin ambigüedades la fórmula matricial para ver esto:
! [El Poder de las Pruebas de Conocimiento Cero: Decodificando matemáticamente zk-SNARKs] (https://img.jinse.cn/7128060_watermarknone.png)
Por lo tanto, LHS = RHS es exactamente lo mismo que la ecuación (2), y cada fila de la ecuación de la matriz corresponde a una restricción de primer orden (es decir, una puerta aritmética en el circuito).
Nos saltamos los pasos de compilación (A, B, C), que son relativamente sencillos. Solo necesitamos convertirlos en forma de matriz de acuerdo con las restricciones de primer nivel correspondientes, para determinar el contenido de cada fila de (A, B, C), es decir, (ai, bi, ci). Tomemos la primera línea como ejemplo: es fácil ver que para que la restricción de primer orden x se multiplique por x igual a s1 para que se cumpla, necesitamos multiplicar [0,1,0,0,0,0,0], [0,1,0,0,0] y [0,0,0,1,0,0] con el vector s.
Por lo tanto, hemos logrado convertir el circuito de la puerta aritmética en una fórmula matricial, es decir, la ecuación (3). Al mismo tiempo, también hemos cambiado el objeto que se debe probar para ser dominado a un vector testigo s.
Paso 3: Polinomios
Ahora, construyamos una matriz n*(*n+m+*1) PA que defina un conjunto de polinomios alrededor de z:
! [El Poder de las Pruebas de Conocimiento Cero: Decodificando matemáticamente zk-SNARKs] (https://img.jinse.cn/7128061_watermarknone.png)
! [El Poder de las Pruebas de Conocimiento Cero: Decodificando matemáticamente zk-SNARKs] (https://img.jinse.cn/7128062_watermarknone.png)
Se trata de cuatro conjuntos de ecuaciones lineales para seis variables que pueden resolverse con métodos tradicionales. Sin embargo, una forma más eficiente de resolver la PA en este caso es la interpolación lagrangiana, que aprovecha la especificidad del problema. Aquí nos saltamos el proceso de resolución de PA, que es un poco tedioso pero sencillo.
! [El Poder de las Pruebas de Conocimiento Cero: Decodificando matemáticamente zk-SNARKs] (https://img.jinse.cn/7128063_watermarknone.png)
A continuación:
! [El Poder de las Pruebas de Conocimiento Cero: Decodificando matemáticamente zk-SNARKs] (https://img.jinse.cn/7128064_watermarknone.png)
Paso 4: Puntos de la curva de elipse
Reescribe la ecuación (4) de la siguiente manera:
! [El Poder de las Pruebas de Conocimiento Cero: Decodificando matemáticamente zk-SNARKs] (https://img.jinse.cn/7128065_watermarknone.png)
donde i(z)=1 es solo un polinomio trivial de orden cero para z, que se usa para unificar la ecuación: todos los términos son cuadráticos. Pronto se hará evidente la necesidad de hacerlo. Ten en cuenta que esta ecuación contiene solo la suma y multiplicación del polinomio de z.
! [El Poder de las Pruebas de Conocimiento Cero: Decodificando matemáticamente zk-SNARKs] (https://img.jinse.cn/7128066_watermarknone.png)
A continuación, explicaremos los pasos reales con más detalle.
Cifrado de curva elíptica
La teoría general de las curvas elípticas está mucho más allá del alcance de este artículo. A los efectos de este artículo, las curvas elípticas se definen como la asignación desde el dominio primo Fp a la función E, donde E incluye puntos que satisfacen y^2=x^3+ax+b (llamados puntos de curva elíptica, o ECP para abreviar).
Ten en cuenta que, si bien hemos estado hablando de aritmética regular hasta ahora, ahora, cuando convertimos a campos primos, las operaciones aritméticas en números se realizan de forma modular. Por ejemplo, a+b=a+b(mod p), donde p es el orden de Fp.
Por otro lado, la definición de suma de dos puntos de curva elíptica se muestra en la siguiente figura:
! [El Poder de las Pruebas de Conocimiento Cero: Decodificando matemáticamente zk-SNARKs] (https://img.jinse.cn/7128067_watermarknone.png)
En concreto, la suma de dos PAE, P y Q:
Halla la intersección de la recta PQ y la curva R, definida como -(P+Q)
Voltea al punto de ‘espejo’ R’ en la curva para R.
Así que definimos la suma de puntos de curva elíptica P+Q=R’:
Tenga en cuenta que esta regla también se aplica a casos especiales, es decir, cuando se utiliza un autoaditivo ECP, donde se utilizará la tangente del punto.
Ahora supongamos que elegimos un punto G aleatorio y le asignamos el número 1. (Este “mapeo inicial” suena un poco arbitrario). Más adelante hablaremos de ello). Entonces, para que cualquier n pertenezca a Fp, definimos:
E(N)=G+G+G+…+G=G
Tiene una expresión de acción. Las acciones que definen +G son “generadores” y se denotan como g. Entonces la definición anterior es equivalente a:
! [El Poder de las Pruebas de Conocimiento Cero: Decodificando matemáticamente zk-SNARKs] (https://img.jinse.cn/7128068_watermarknone.png)
Para aquellos que no están familiarizados con las curvas elípticas, se puede comparar esta asignación con una función exponencial regular en la que la g cardinal reemplaza a los números reales. Las operaciones aritméticas se comportan de manera similar. Sin embargo, una diferencia clave es que la función inversa de g^n no es computacionalmente factible. Es decir, ¡no hay forma de calcular la versión de curva elíptica! [El Poder de las Pruebas de Conocimiento Cero: Decodificando matemáticamente zk-SNARKs] (https://img.jinse.cn/7128069_watermarknone.png)。 Esta es, por supuesto, la base de la criptografía de curva elíptica. Este tipo de asignación se conoce como cifrado unidireccional.
Tenga en cuenta que dada una curva elíptica, dado que la selección de G (y, por lo tanto, el generador g) es arbitraria (excepto para los puntos en el eje x), hay un número infinito de formas de asignarla. Elegir (G o g) puede ser análogo a elegir la cardinalidad de una función exponencial (2^x, 10^x, e^x, etc.) como parte del sentido común.
! [El Poder de las Pruebas de Conocimiento Cero: Decodificando matemáticamente zk-SNARKs] (https://img.jinse.cn/7128070_watermarknone.png)
Sin embargo, la ecuación (5) que Alicia quiere demostrar es cuadrática y, por lo tanto, no es lo suficientemente lineal. Para tratar con términos cuadráticos, necesitamos definir la multiplicación en el espacio criptográfico. Esto se conoce como función de emparejamiento, o mapa bilineal, y se explicará a continuación.
Mapeo bilineal
! [El Poder de las Pruebas de Conocimiento Cero: Decodificando matemáticamente zk-SNARKs] (https://img.jinse.cn/7128071_watermarknone.png)
Cadena de referencia común
! [El Poder de las Pruebas de Conocimiento Cero: Decodificando matemáticamente zk-SNARKs] (https://img.jinse.cn/7128072_watermarknone.png)
Todo el proceso se denomina “clave de verificación”, o VK para abreviar. Aquí solo hay 7 puntos de curva elíptica (ECP), que deben proporcionarse al verificador. Es importante tener en cuenta que no importa cuántas entradas y restricciones de primer nivel estén involucradas en el problema, VK siempre se compone de 7 ECP.
Además, vale la pena mencionar que la “configuración confiable” y el proceso de generación de PK y VK se pueden realizar una vez para un problema en particular.
Prueba y verificación
Ahora, con la clave pública (PK), Alice calculará los siguientes puntos de curva elíptica (ECP):
! [El Poder de las Pruebas de Conocimiento Cero: Decodificando matemáticamente zk-SNARKs] (https://img.jinse.cn/7128073_watermarknone.png)
¡Estos 9 puntos de curva elíptica son la clave para las pruebas no interactivas concisas de conocimiento cero (zk-SNARK)!
Tenga en cuenta que Alice en realidad solo está haciendo algunas operaciones combinatorias lineales en los puntos de la curva elíptica en la clave pública. Esto es particularmente crítico y se comprobará durante la validación.
Ahora que Alice ha entregado la prueba de zk-SNARK, entremos finalmente en el proceso de verificación, que es un proceso de tres pasos.
En primer lugar, es importante asegurarse de que los primeros 8 puntos de la curva elíptica sean realmente una combinación lineal de esos puntos en la cadena de referencia genérica.
! [El Poder de las Pruebas de Conocimiento Cero: Decodificando matemáticamente zk-SNARKs] (https://img.jinse.cn/7128074_watermarknone.png)
Si las tres comprobaciones son verdaderas, entonces se verifica la ecuación (5), por lo que creemos que Alicia conoce al testigo.
Expliquemos la lógica detrás de la ecuación. Tomemos como ejemplo la primera ecuación de la primera parte, que se cumple debido a la naturaleza bilineal:
! [El Poder de las Pruebas de Conocimiento Cero: Decodificando matemáticamente zk-SNARKs] (https://img.jinse.cn/7128075_watermarknone.png)
Sin embargo, dado que Alicia no conoce el valor del símbolo alfa, no puede calcular esta suma explícitamente. La única forma en que pudo encontrar un par que satisficiera la ecuación (EA, EA’) fue usar el mismo conjunto de vectores s cada uno, ¡calcular! [El Poder de las Pruebas de Conocimiento Cero: Decodificando matemáticamente zk-SNARKs] (https://img.jinse.cn/7128076_watermarknone.png).
Referencias
“Zk-SNARKs: Bajo el capó” (Vitalik Buterin)
“Una revisión de las pruebas de conocimiento cero” (Thomas Chen, Abby Lu, Jern Kunpittaya y Alan Luo)
“Por qué y cómo funciona zk-SNARK: explicación definitiva” (Maksym Petkus)
Sitio web: Zero-Knowledge Proofs
Wikipedia:Curva elíptica
Wikipedia:Campo finito
Wikipedia:Criptografía basada en emparejamiento
