Preámbulo
Esta es la cuarta parte de una serie de artículos que exploran zk-SNARK, una tecnología que permite demostrar la exactitud de un conocimiento sin tener que revelar información secreta. En las partes anteriores, aprendimos algunos conceptos complejos como el programa de aritmética cuadrática y los pares de curvas elípticas (copie el enlace de la parte 3 en este texto en negrita).
El programa de aritmética cuadrática permite representar problemas computacionales mediante polinomios y los pares de curvas elípticas proporcionan una herramienta de codificación útil para comprobar la exactitud de los datos. Al combinarlos con algún otro algoritmo, podemos permitir que el probador demuestre que conoce la solución a un QAP en particular sin revelar nada más. Esto proporciona confianza sin revelar datos confidenciales.
Este artículo se centrará en el Protocolo Pinocho para QAP , que permite demostrar que una variable satisface ciertas condiciones sin tener que revelar detalles sobre el valor de la variable.
Esta prueba es fácil de crear y se puede autenticar sin verificar cada paso computacional, lo que garantiza la privacidad y seguridad de los datos en aplicaciones blockchain y otras áreas que requieren una autenticación segura y de alto rendimiento sin revelar información privada.
Construcción del protocolo Pinocho con conocimiento distinto de cero
Comenzamos ilustrando cómo funciona el protocolo Pinocho de la siguiente manera:
Sea G un grupo de orden primo p. Sea E: Fp → G una codificación homomórfica. Como sigue:
para un generador g
Poner
La expresión anterior es un "mapa bilineal" de una curva elíptica. Supongamos que el probador P conoce a un testigo como se muestra a continuación
para el circuito aritmético original. Simplificando, conocerá algún polinomio tal que
A estas alturas todavía nos resultará un poco confuso, ¿verdad? No te preocupes, lee atentamente cada línea y estudia las fórmulas, ¡te explicaré la idea principal de este protocolo justo debajo!
V(verificador) quiere probar P(Prover) en un punto aleatorio (punto aleatorio) z ∈ Fp contra los valores del polinomio anterior. Se pregunta a P por el valor de
y h(z) en algún valor aleatorio z ∈ Fp. P codificará homomórficamente) estos valores y los enviará a V . Gracias a las propiedades del mapa homomórfico y bilineal, V puede verificar que el valor codificado homomórficamente satisface la misma ecuación (20) anterior.
Si lo hace, el Verificador puede estar seguro de que el Probador realmente conoce a un testigo sin tener que enterarse de ese testigo. A continuación se muestra información más detallada sobre la idea principal que se acaba de describir.
El primer paso del protocolo es crear una cadena de referencia común (CRS), que contiene codificaciones homomórficas de múltiplos de z.
CRS tendrá dos propósitos:
En primer lugar, el Prover puede generar codificaciones homomórficas para su prueba utilizando combinaciones lineales (combinaciones lineales) de los elementos del grupo del CRS sin conocer z.
En segundo lugar, configurar un CRS elimina la necesidad de que V genere manualmente z y envíe un mensaje cifrado de z a P. Esto permite que esta prueba sea completamente no interactiva, porque una vez que se crea el CRS, P está en condiciones de producir evidencia convincente.
Podemos pensar en CRS como dos conjuntos de elementos de grupos públicos:
La clave de evaluación, que contiene los elementos de grupo necesarios para construir la prueba, y la clave de verificación, que contiene los elementos necesarios para la verificación.
Cadena de referencia común:
Elija aleatoriamente α, βu, βv, βw, γ, z ∈ F ∗ p .
Implemente el CRS a continuación, luego elimine todos los elementos del grupo utilizados en su creación (residuos tóxicos).
Mensaje del demostrador:
Supongamos que Prover tiene el siguiente polinomio:
Primero, el probador calcula h(x). Entonces, la evidencia del probador incluye lo siguiente:
Verificación:
Al recibir la prueba del probador, el verificador primero verifica si los términos u(z), v(z), w(z), h(z) se construyen como combinaciones lineales de cálculo de términos en CRS o no, realice las siguientes 4 comprobaciones :
A continuación, compruebe que cada término u(z), v(z), w(z) se genere utilizando los mismos coeficientes lineales:
Esto se puede comprobar verificando la siguiente ecuación:
Finalmente, comprobamos la condición clave que caracteriza el criterio de divisibilidad polinómica:
Hemos construido con éxito el Protocolo de Pinocho de conocimiento distinto de cero si y solo si todas las comprobaciones de (21) a (26) se cumplen.
¡A continuación pasaremos al paso de analizar el Protocolo de Pinocho de conocimiento distinto de cero!
Análisis del protocolo Pinocho de conocimiento distinto de cero
Primero, necesitamos aprender el conocimiento de la suposición de exponentes.
Supongamos que a Alice se le da un par de elementos del grupo (x, αx)
A este par lo llamamos α-separado. Entonces, para Alice, generar otro par α-separado (y, αy) no es factible, excepto generarlo de la siguiente manera:
Dados n pares separados por α, si Alice devuelve otro par separado por α, debe ser una combinación lineal de los pares separados por α originales con alta probabilidad.
Volviendo a nuestro protocolo, la condición principal que V debe verificar es la condición de divisibilidad polinomial:
Sin embargo, además de esta ecuación, debe haber otras ecuaciones que el verificador también debe verificar.
Esto se debe a que es posible que el probador genere valores que satisfagan esta ecuación, pero que no se generen a partir de testigos reales para el circuito aritmético. Para garantizar esto, Verifier necesita una forma de verificar que los polinomios utilizados por Prover son en realidad una combinación lineal de los polinomios subyacentes en el CRS.
El supuesto de "conocimiento del exponente" es útil porque si un par de elementos de grupo que envía Prover y un par dado están separados α-, el par de Prover debe generarse como una combinación lineal de los pares α- separados dados.
Por lo tanto, el Verificador puede usar una función de concatenación para probar efectivamente que estos dos pares están separados α-, para garantizar que el Prover genere usando una representación verdaderamente satisfactoria del circuito aritmético. Más específicamente, para dos pares (x, αx),(y, αy), se cumple lo siguiente:
Verifier puede usar esto para realizar las siguientes comprobaciones:
Usando esta idea, el verificador necesita verificar tres cosas:
A partir de ahí, podemos demostrar que el protocolo de Pinocho satisface dos propiedades: integridad y solidez (esta prueba es bastante complicada, puedes leer más sobre los documentos fuente que pongo a continuación para comprender mejor).
Modificación del protocolo Pinocho de conocimiento cero
Esencialmente, si el verificador V genera su propia prueba s' = (s'₁, s'₂,…, s'ₙ), puede calcular E(u'(z)), E (v'(z)), E (w'(z)), E(h'(z)) según el protocolo del probador.
Si estos valores difieren de E(u(z)), E(v(z)), E(w(z)), E(h(z)), que el probador calcula en s, entonces el verificador concluye que la prueba del probador no es s' (Explicando SNARKs Parte VI: El Protocolo de Pinocho)
Para eliminar esta violación de "conocimiento cero", el probador P agrega un desplazamiento aleatorio a los polinomios u, v y w (Pinocho: computación verificable casi práctica)
El desplazamiento aleatorio será un múltiplo de t(x), de modo que todo siga siendo el mismo mod t(x). Para δ₁, δ₂, δ₃ aleatorios pertenecientes a Fp, seleccionados al azar:
Luego, P los evaluará en z usando CRS y presentará términos desplazados (términos desplazados) en su prueba en lugar de los términos no desplazados correspondientes.
Entonces, el paso de Modificación del Protocolo de Pinocho de conocimiento cero se ha completado. En este punto, todos se sienten confundidos =)))))).
Pero eso es todo, gracias nuevamente por leer hasta aquí. Si te ha gustado este artículo no olvides seguirlo y dejar un aplauso.
Así termina mi serie de artículos sobre “Descubriendo zk-SNARK” . ¡Espero que dejen sus contribuciones para poder mejorar y motivarme para escribir los próximos artículos!
Fuente del artículo: Team Tech/Research AlphaTrue
Fuente de referencia:
Chen, T., Lu, H., Kunpittaya, T. y Luo, A. (2022). Una revisión de zk-snarks. Preimpresión de arXiv arXiv:2202.06877. https://arxiv.org/pdf/2202.06877.pdf
