El poder de las pruebas de conocimiento cero: inmersión profunda en zk-SNARK

Este artículo decodificará esta tecnología utilizando matemáticas, ilustrando cómo puede probar la verdad del conocimiento sin revelar ninguna información.

Compilado por: Investigación DODO

Autor: Cofundador de 0xAlpha @DeriProtocol

Introducción

Zk-SNARK, o argumento de conocimiento sucinto no interactivo de conocimiento cero, permite a un verificador confirmar que un demostrador posee cierto conocimiento (llamado testigos) que satisface relaciones específicas sin revelar ninguna información sobre el conocimiento en sí.

Generar un zk-SNARK para un problema específico implica las siguientes cuatro etapas:

• Convertir un problema (o función) en un circuito aritmético.
• Este circuito luego se traduce a una ecuación matricial.
• Esta ecuación matricial se convierte además en un polinomio que debería ser divisible por un polinomio mínimo específico.
• Finalmente, esta divisibilidad se expresa en puntos de curva elíptica sobre un campo finito, donde se realiza la demostración.

Los primeros tres pasos simplemente transforman la representación de la declaración original. El último paso proyecta la declaración del tercer paso en un espacio cifrado utilizando cifrado homomórfico, lo que permite al probador verificar las declaraciones reflejadas en el mismo. Dado que esta proyección utiliza cifrado asimétrico, no es factible retroceder desde la declaración del paso 3 a la declaración original, asegurando una exposición de conocimiento cero.

La formación matemática necesaria para leer este artículo es comparable al nivel de álgebra que se espera de los estudiantes universitarios STEM de primer año. El único concepto que podría resultar desafiante podría ser el de la criptografía de curva elíptica. Para aquellos que no estén familiarizados con esto, pueden pensar en ella como una función exponencial con una base especial, teniendo en cuenta que su inversa sigue sin resolverse.

Este artículo seguirá las siguientes reglas de notación:

Matrices: letras mayúsculas en negrita, por ejemplo A; escrito en formas explícitas \
Vectores: Letra minúscula con flechas, escrita en formas explícitas [ ]; todos los vectores son vectores de columna por defecto \
Escalares: Representados por letras regulares

Tomemos como ejemplo la siguiente pregunta:

f(x)=x^3+x^2+5 (1)

Supongamos que Alice quiere demostrar que sabe una verdad. Repasaremos todo el procedimiento que Alice debe seguir para generar un zk-SNARK como prueba.
Esta pregunta puede parecer demasiado simple porque no implica un flujo de control (por ejemplo, si-entonces-si no). Sin embargo, no es difícil convertir funciones con flujo de control en expresiones aritméticas. Por ejemplo, considere el siguiente problema (o “función” en lenguajes de programación):

f(x,z):
si(z==1):
devolver xxx+xx+5
demás:
volverxx+5

Reescribir este problema en la siguiente expresión aritmética (asumiendo que z pertenece a (0,1)) no es más complejo 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 nuestra discusión.

Paso 1: circuito aritmético

La ecuación (1) se puede dividir en las siguientes operaciones aritméticas básicas:

Esto corresponde al siguiente circuito aritmético:

También nos referimos a la ecuación (2) como un conjunto de 4 "restricciones primarias", cada restricción describe la relación de una puerta aritmética en el circuito. En general, un conjunto de n restricciones primarias se puede resumir como un programa aritmético cuadrático (QAP), que se explicará a continuación.

Paso 2: Matriz

Primero, definamos un vector "testigo" de la siguiente manera:

donde y, s1, s2 y s3 se definen como en la ecuación (2).
Normalmente, para un problema con m entradas yn puertas aritméticas (es decir, n-1 pasos intermedios y la salida final), este vector testigo será (m+n+1) dimensional. En casos del mundo real, el número n puede ser extremadamente grande. Por ejemplo, para las funciones hash, n suele ser de miles.

A continuación, construyamos tres n(m+n+1) matrices A,B,C para que podamos reescribir la ecuación (2) de la siguiente manera:

La ecuación (3) es simplemente otra representación de la ecuación (2): cada conjunto (ai, bi, ci) corresponde a una puerta en el circuito. Podemos ver esto expandiendo explícitamente la ecuación matricial:

Entonces LHS=RHS es exactamente lo mismo que la ecuación (2), y cada fila de la ecuación matricial corresponde a una restricción primaria (es decir, una puerta aritmética en el circuito).

Nos saltamos los pasos de construcción (A, B, C), que en realidad son relativamente sencillos. Solo necesitamos convertirlos en matrices de acuerdo con las restricciones primarias correspondientes para determinar el contenido de cada fila de (A, B, C), es decir, (ai, bi, ci). Tomando la primera fila como ejemplo: podemos ver fácilmente que para hacer que la primera restricción primaria x multiplicada por x sea igual a s1, necesitamos multiplicar [0,1,0,0,0], [0, 1,0, 0,0] y [0,0,0,1,0,0] por el vector s.

Por lo tanto, hemos convertido con éxito el circuito aritmético en una ecuación matricial, es decir, la ecuación (3). Al mismo tiempo, también cambiamos el objeto que necesita ser probado para ser dominado por los vectores testigo s.

Paso 3: polinomios

Ahora, construyamos una matriz PA n(n+m+*1), que define un conjunto de polinomios con respecto a z:

Garantizar que la funcióntoma los siguientes valores en {1, 2, 3, 4} satisface las condiciones:

Entonces podemos reescribir A como:

Se trata de cuatro conjuntos de ecuaciones lineales que implican seis variables y que se pueden resolver utilizando métodos tradicionales. Sin embargo, una forma más eficaz de resolver PA en este caso es la interpolación lagrangiana, que explota las peculiaridades del problema. Aquí nos saltamos el proceso de resolución de PA, que es un poco tedioso pero sencillo.

De manera similar, construimos PB y PC por separado para B y C. Luego podemos reescribir la ecuación matricialcomo sigue:

Observando cada fila por separado, es evidente que estas cuatro filas corresponden a la misma expresión evaluada en cuatro puntos diferentes. Por lo tanto, la ecuación matricial anterior es equivalente a:

Paso 3: Punto de curva elíptica

Reescribe la ecuación (4) como:

donde i(z)=1 es simplemente un polinomio trivial de grado cero en z usado para unificar las ecuaciones; todos los términos son cuadráticos. La necesidad de esto quedará clara en breve. Tenga en cuenta que esta ecuación solo contiene la suma y multiplicación de polinomios en z.

Tenga en cuenta que las operaciones aritméticas, suma (+) y multiplicación (X), también se asignan a operaciones correspondientes en el campo finito de puntos de curva elíptica. los simbolos y se utilizan para evitar confusiones e indicar que se trata de operaciones de campo redefinidas.

A continuación, explicaremos los pasos prácticos con más detalle.

Criptografía de curva elíptica

La teoría general de las curvas elípticas va mucho más allá del alcance de este artículo. Para los propósitos del presente documento, una curva elíptica se define como asignaciones de un campo primo Fp a la función E, donde E incluye puntos tales que y^2=x^3+ax+b (llamados puntos de curva elíptica, o ECP para abreviar) .

Tenga en cuenta que, si bien hemos estado analizando la aritmética regular hasta ahora, cuando se realiza la transición a un campo primo, las operaciones aritméticas con números se realizan utilizando aritmética modular. Por ejemplo, a+b=a+b(mod p), donde p es el orden de Fp.

Por otro lado, la suma de dos puntos de la curva elíptica se define como se muestra a continuación:

Específicamente, la suma de P y Q de dos ECP:

Encuentre la intersección de la línea PQ y la curva R y defínala como -(P+Q)
Gire al punto “espejo” R' de R en la curva.
Por lo tanto definimos la suma de puntos de curva elíptica P+Q=R':

Tenga en cuenta que esta regla también se aplica al caso especial en el que se utiliza la suma de un ECP, en cuyo caso se utilizará la tangente a ese punto.

Ahora supongamos que seleccionamos aleatoriamente un punto G y le asignamos el número 1. (Este “mapeo inicial” suena un poco arbitrario. Lo discutiremos más adelante). Y para cualquier n perteneciente a Fp, definimos:

E(N)=G+G+G+…..+G=G multiplicado por n

Hay una expresión de operación. Defina la operación +G como “generador”, denotada como g. Entonces la definición anterior es equivalente a:

Después de definir la suma, se hace evidente la siguiente relación lineal:

Por lo tanto, cualquier relación lineal (o restricción) en Fp se preservará en el espacio cifrado B a través de este mapeo. Por ejemplo, la ecuación l + m = n en Fp conducirá a

Sin embargo, como la ecuación (5) que Alice quiere demostrar está en forma cuadrática, no es lo suficientemente lineal. Para manejar términos cuadráticos, necesitamos definir la multiplicación en el espacio cifrado. Esto se llama mapa de emparejamiento o bilineal, que explicaré en la siguiente sección.

Mapa bilineal

Supongamos que G1, G2 y GT son grupos de orden primo g. Una función de emparejamiento, o mapa bilineal, se define de la siguiente manera:

Cadena de referencia común

Este conjunto se denomina “clave de prueba” (PK). Tenga en cuenta que la representación de vectores dentro de E() debe entenderse como vectores de puntos de curva elíptica, donde cada punto se asigna desde el elemento vectorial correspondiente. Por lo tanto, estos 11 vectores en realidad comprenden 62 (=42+63+63+63) puntos de curva elíptica. Estas 62 PAE se entregarán a Alice, la demostradora. En un escenario general, para un problema con m entradas yn restricciones primarias, la PK contendrá 2n + 3(m+n+1)*3 = 11n + 9m + 9 ECP.

Simultáneamente se realizarán los siguientes cálculos:

Todo el proceso se denomina “clave de verificación” (VK). Aquí solo intervienen 7 puntos de curva elíptica (ECP), que deben proporcionarse al verificador. Cabe señalar que no importa cuántas entradas y restricciones primarias estén involucradas en el problema, VK siempre está compuesto por 7 ECP.

Además, cabe mencionar que la “configuración confiable” y el proceso de generación de PK y VK solo deben realizarse una vez para un problema específico.

Prueba y verificación

Ahora que posee la clave pública (PK), Alice calculará los siguientes puntos de curva elíptica (ECP):

¡Estos 9 puntos de la curva elíptica son cruciales para un argumento de conocimiento sucinto y no interactivo de conocimiento cero (zk-SNARK)!

Tenga en cuenta que Alice esencialmente solo realiza combinaciones lineales en los puntos de la curva elíptica en la clave pública. Esto es particularmente crítico y será verificado rigurosamente durante la verificación.

Ahora, Alice presenta la prueba de zk-SNARK, lo que finalmente nos lleva al proceso de verificación, que se realiza en tres pasos.

Primero, es necesario confirmar que los primeros 8 puntos de la curva elíptica son de hecho combinaciones lineales de esos puntos en la cadena de referencia común.

Descargo de responsabilidad:

1. Este artículo se reimprime de [Chaincatcher]. Todos los derechos de autor pertenecen al autor original [0xAlpha Cofundador @ DeriProtocol]. 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 están a cargo del equipo de Gate Learn. A menos que se mencione, está prohibido copiar, distribuir o plagiar los artículos traducidos.