Vitalik Buterin a través de Blog de Vitalik Buterin
Este es un espejo de la publicación en https://medium.com/@VitalikButerin/programas-de-aritmética-cuadrática-de-cero-al-héroe-f6d558cea649
Últimamente ha habido mucho interés en la tecnología detrás de los zk-SNARK, y la gente está cada vez más tratando de desmitificar algo que muchos han llegado a llamar “matemáticas lunares” debido a su percibida complejidad pura e indescifrable. De hecho, los zk-SNARK son bastante difíciles de entender, especialmente debido a la gran cantidad de partes móviles que deben unirse para que todo funcione, pero si desglosamos la tecnología pieza por pieza, comprenderla se vuelve más simple.
El propósito de esta publicación no es servir como una introducción completa a zk-SNARK; asume como conocimiento previo que (i) sabes qué son los zk-SNARK y qué hacen, y (ii) sabes suficientes matemáticas para poder razonar sobre cosas como polinomios (si la afirmación �(�)+�(�) =(�+�)(�) , donde � y � son polinomios, te parece natural y obvio, entonces estás en el nivel correcto). Más bien, la publicación profundiza en la maquinaria detrás de la tecnología e intenta explicar lo mejor posible la primera mitad del proceso, como lo dibuja aquí el investigador de zk-SNARK, Eran Tromer:
Los pasos aquí se pueden dividir en dos mitades. En primer lugar, los zk-SNARK no se pueden aplicar directamente a ningún problema computacional; más bien, hay que convertir el problema en la “forma” correcta para que funcione. La forma se llama “programa aritmético cuadrático” (QAP), y transformar el código de una función en uno de estos no es en sí mismo nada trivial. Junto con el proceso para convertir el código de una función en un QAP, hay otro proceso que se puede ejecutar para que, si tiene una entrada al código, pueda crear una solución correspondiente (a veces llamada "testigo" del QAP). Después de esto, hay otro proceso bastante complejo para crear la “prueba de conocimiento cero” real para este testigo, y un proceso separado para verificar una prueba que otra persona le pasa a usted, pero estos son detalles que están fuera del alcance de esta publicación. .
El ejemplo que elegiremos es sencillo: demostrar que conoces la solución de una ecuación cúbica: �3+�+5=35 (pista: la respuesta es 3). Este problema es lo suficientemente simple como para que el QAP resultante no sea tan grande como para resultar intimidante, pero no lo suficientemente trivial como para que se pueda ver toda la maquinaria entrar en juego.
Escribamos nuestra función de la siguiente manera:
def qeval(x):
y = x**3
return x + y + 5El sencillo lenguaje de programación de propósito especial que estamos usando aquí admite aritmética básica (+, −, ⋅, /), exponenciación de potencia constante (�7 pero no ��) y asignación de variables, que es lo suficientemente poderosa como para que teóricamente puedas hacerlo. cualquier cálculo dentro de él (siempre que el número de pasos computacionales esté limitado; no se permiten bucles). Tenga en cuenta que el módulo (%) y los operadores de comparación (<, >, ≤, ≥) NO son compatibles, ya que no existe una manera eficiente de hacer módulo o comparación directamente en aritmética de grupos cíclicos finitos (agradezca esto; si hubiera una manera hacer cualquiera de las dos cosas, entonces la criptografía de curva elíptica se rompería más rápido de lo que se puede decir "búsqueda binaria" y "teorema del resto chino").
Puede extender el lenguaje a módulos y comparaciones proporcionando descomposiciones de bits (por ejemplo, 13=23+22+1) como entradas auxiliares, demostrando la exactitud de esas descomposiciones y haciendo los cálculos en circuitos binarios; en aritmética de campos finitos, hacer comprobaciones de igualdad (==) también es factible y, de hecho, un poco más fácil, pero ambos son detalles en los que no entraremos en detalles ahora. Podemos extender el lenguaje para admitir condicionales (por ejemplo, si �<5:�=7; de lo contrario: �=9) convirtiéndolos a una forma aritmética: �=7⋅(�<5)+9⋅(�≥5 ) aunque tenga en cuenta que sería necesario ejecutar ambas “rutas” del condicional, y si tiene muchos condicionales anidados, esto puede generar una gran cantidad de gastos generales.
Repasemos ahora este proceso paso a paso. Si desea hacer esto usted mismo para cualquier fragmento de código, le implementó un compilador aquí (Solo con fines educativos; ¡todavía no estoy listo para crear QAP para zk-SNARK del mundo real!).
Aplastamiento
El primer paso es un procedimiento de "aplanamiento", en el que convertimos el código original, que puede contener declaraciones y expresiones arbitrariamente complejas, en una secuencia de declaraciones que tienen dos formas: �=� (donde � puede ser una variable o un número ) y �=� (��) � (donde �� puede ser +, −, ⋅, / y � y � pueden ser variables, números o subexpresiones en sí mismas). Puedes pensar en cada una de estas afirmaciones como si fueran puertas lógicas en un circuito. El resultado del proceso de aplanamiento del código anterior es el siguiente:
sym_1 = x * x
y = sym_1 * x
sym_2 = y + x
~out = sym_2 + 5Si lees el código original y el código aquí, podrás ver con bastante facilidad que los dos son equivalentes.
Puertas a R1CS
Ahora, convertimos esto en algo llamado sistema de restricciones de rango 1 (R1CS). Un R1CS es una secuencia de grupos de tres vectores (�, �, �), y la solución de un R1CS es un vector �, donde � debe satisfacer la ecuación �.�⋅�.�−�.�=0, donde . representa el producto escalar; en términos más simples, si “juntamos” � y �, multiplicamos los dos valores en las mismas posiciones, y luego tomamos la suma de estos productos, luego hacemos lo mismo con � y � y luego con � y � , entonces el tercer resultado es igual al producto de los dos primeros resultados. Por ejemplo, este es un R1CS satisfecho:
Primero, proporcionaremos el mapeo de variables que usaremos:
'~one', 'x', '~out', 'sym_1', 'y', 'sym_2'El vector de solución constará de asignaciones para todas estas variables, en ese orden.
Ahora, daremos el triple (�,�,�) para la primera puerta:
a = [0, 1, 0, 0, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 1, 0, 0]Puede ver que si el vector solución contiene 3 en la segunda posición y 9 en la cuarta posición, entonces, independientemente del resto del contenido del vector solución, la verificación del producto escalar se reducirá a 3⋅3=9, y así pasará. Si el vector solución tiene −3 en la segunda posición y 9 en la cuarta posición, la verificación también pasará; de hecho, si el vector de solución tiene 7 en la segunda posición y 49 en la cuarta posición, entonces esa verificación aún pasará; el propósito de esta primera verificación es verificar la coherencia de las entradas y salidas de la primera puerta únicamente.
Ahora pasemos a la segunda puerta:
a = [0, 0, 0, 1, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 0, 1, 0]De manera similar a la primera verificación del producto escalar, aquí estamos verificando que ���1⋅�=�.
Ahora, la tercera puerta:
a = [0, 1, 0, 0, 1, 0]
b = [1, 0, 0, 0, 0, 0]
c = [0, 0, 0, 0, 0, 1]Aquí, el patrón es algo diferente: se multiplica el primer elemento en el vector solución por el segundo elemento, luego por el quinto elemento, se suman los dos resultados y se verifica si la suma es igual al sexto elemento. Debido a que el primer elemento en el vector solución es siempre uno, esto es solo una verificación de suma, verificando que la salida sea igual a la suma de las dos entradas.
Finalmente, la cuarta puerta:
a = [5, 0, 0, 0, 0, 1]
b = [1, 0, 0, 0, 0, 0]
c = [0, 0, 1, 0, 0, 0]Aquí, estamos evaluando la última verificación, ~out =���2+5. La verificación del producto escalar funciona tomando el sexto elemento en el vector de solución, sumando cinco veces el primer elemento (recordatorio: el primer elemento es 1, por lo que esto efectivamente significa sumar 5) y comparándolo con el tercer elemento, que es donde almacenar la variable de salida.
Y ahí tenemos nuestro R1CS con cuatro restricciones. El testigo es simplemente la asignación de todas las variables, incluidas las de entrada, de salida y las internas:
[1, 3, 35, 9, 27, 30]Puede calcular esto usted mismo simplemente "ejecutando" el código aplanado anterior, comenzando con la asignación de la variable de entrada �=3 e ingresando los valores de todas las variables intermedias y la salida a medida que las calcula.
El R1CS completo en conjunto es:
A
[0, 1, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 1, 0]
[5, 0, 0, 0, 0, 1]
B
[0, 1, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
C
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0]R1CS a QAP
El siguiente paso es tomar este R1CS y convertirlo al formato QAP, que implementa exactamente la misma lógica excepto que usa polinomios en lugar de productos escalares. Hacemos esto de la siguiente manera. Pasamos de cuatro grupos de tres vectores de longitud seis a seis grupos de tres polinomios de grado 3, donde evaluamos los polinomios en cada coordenada x representa una de las restricciones. Es decir, si evaluamos los polinomios en �=1, obtenemos nuestro primer conjunto de vectores, si evaluamos los polinomios en �=2, entonces obtenemos nuestro segundo conjunto de vectores, y así sucesivamente.
Podemos hacer esta transformación usando algo llamado Interpolación de Lagrange. El problema que resuelve una interpolación de Lagrange es el siguiente: si tienes un conjunto de puntos (es decir, (�,�) pares de coordenadas), entonces hacer una interpolación de Lagrange en esos puntos te da un polinomio que pasa por todos esos puntos. Hacemos esto descomponiendo el problema: para cada coordenada, creamos un polinomio que tiene la coordenada deseada en esa coordenada y una coordenada de 0 en todas las demás coordenadas que nos interesan, y luego obtenemos la coordenada final. Como resultado sumamos todos los polinomios.
Hagamos un ejemplo. Supongamos que queremos un polinomio que pase por (1,3), (2,2) y (3,4). Comenzamos haciendo un polinomio que pase por (1,3), (2,0) y (3,0). Resulta que hacer un polinomio que “sobresalga” en �=1 y sea cero en los otros puntos de interés es fácil; simplemente hacemos:
(x - 2) * (x - 3)Que se ve así:
(x - 2) * (x - 3) * 3 / ((1 - 2) * (1 - 3))Esto nos da:
1.5 * x**2 - 7.5 * x + 9
1.5 * x**2 - 5.5 * x + 7
Ahora, usemos la interpolación de Lagrange para transformar nuestro R1CS. Lo que vamos a hacer es tomar el primer valor de cada vector �, usar la interpolación de Lagrange para hacer un polinomio a partir de eso (donde evaluar el polinomio en � obtiene el primer valor del �ésimo vector �), repetir el proceso para el primer valor de cada vector � y �, y luego repita ese proceso para el segundo valor, el tercero, valores, etc. Para mayor comodidad, proporcionaré las respuestas ahora mismo:
A polynomials
[-5.0, 9.166, -5.0, 0.833]
[8.0, -11.333, 5.0, -0.666]
[0.0, 0.0, 0.0, 0.0]
[-6.0, 9.5, -4.0, 0.5]
[4.0, -7.0, 3.5, -0.5]
[-1.0, 1.833, -1.0, 0.166]
B polynomials
[3.0, -5.166, 2.5, -0.333]
[-2.0, 5.166, -2.5, 0.333]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
C polynomials
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[-1.0, 1.833, -1.0, 0.166]
[4.0, -4.333, 1.5, -0.166]
[-6.0, 9.5, -4.0, 0.5]
[4.0, -7.0, 3.5, -0.5]Los coeficientes están en orden ascendente, por lo que el primer polinomio anterior es en realidad 0.833⋅�3—5⋅�2+9.166⋅�−5. Este conjunto de polinomios (más un polinomio Z que explicaré más adelante) constituye los parámetros para esta instancia QAP en particular. Tenga en cuenta que todo el trabajo hasta este punto debe realizarse solo una vez para cada función que intenta utilizar zk-SNARKs para verificar; Una vez generados los parámetros QAP, se pueden reutilizar.
Intentemos evaluar todos estos polinomios en �=1. Evaluar un polinomio en �=1 simplemente significa sumar todos los coeficientes (como 1�=1 para todo �), por lo que no es difícil. Obtenemos:
A results at x=1
0
1
0
0
0
0
B results at x=1
0
1
0
0
0
0
C results at x=1
0
0
0
1
0
0Y he aquí, lo que tenemos aquí es exactamente lo mismo que el conjunto de tres vectores para la primera puerta lógica que creamos arriba.
Comprobando el QAP
Ahora bien, ¿cuál es el punto de esta loca transformación? La respuesta es que en lugar de verificar las restricciones en el R1CS individualmente, ahora podemos verificar todas las restricciones al mismo tiempo haciendo la verificación del producto escalar sobre los polinomios.
Tenga en cuenta que el polinomio resultante no tiene por qué ser cero y, de hecho, en la mayoría de los casos no lo será; podría tener cualquier comportamiento en los puntos que no corresponden a ninguna puerta lógica, siempre que el resultado sea cero en todos los puntos que do corresponden a alguna puerta. Para verificar la corrección, en realidad no evaluamos el polinomio �=�.�⋅�.�−�.� en cada punto correspondiente a una puerta; en su lugar, dividimos � por otro polinomio, �, y comprobamos que � divide uniformemente a �, es decir, que la división �/� no deja resto.
� se define como (�−1)⋅(�−2)⋅(�−3)… – el polinomio más simple que es igual a cero en todos los puntos que corresponden a puertas lógicas. Es un hecho elemental del álgebra que cualquier un polinomio que es igual a cero en todos estos puntos tiene que ser múltiplo de este polinomio mínimo, y si un polinomio es múltiplo de � entonces su evaluación en cualquiera de esos puntos será cero; esta equivalencia facilita mucho nuestro trabajo.
Ahora, hagamos la verificación del producto escalar con los polinomios anteriores. Primero, los polinomios intermedios:
A . s = [43.0, -73.333, 38.5, -5.166]
B . s = [-3.0, 10.333, -5.0, 0.666]
C . s = [-41.0, 71.666, -24.5, 2.833]Ahora, �.�⋅�.�—�.�:
t = [-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444]Ahora, el polinomio mínimo �=(�−1)⋅(�−2)⋅(�−3)⋅(�−4):
Z = [24, -50, 35, -10, 1]Y si dividimos el resultado anterior por �, obtenemos:
h = t / Z = [-3.666, 17.055, -3.444]Sin resto.
Y así tenemos la solución para el QAP. Si intentamos falsificar cualquiera de las variables en la solución R1CS de la que derivamos esta solución QAP (digamos, establecer la última en 31 en lugar de 30), obtenemos un polinomio � que no pasa una de las comprobaciones (en ese caso en particular). caso, el resultado en �=3 sería igual a −1 en lugar de 0), y además � no sería múltiplo de �; más bien, dividir �/� daría un resto de [−5.0,8.833,−4.5,0.666].
Tenga en cuenta que lo anterior es una simplificación; “En el mundo real”, la suma, multiplicación, resta y división no ocurrirán con números regulares, sino con elementos de campo finitos: un tipo espeluznante de aritmética que es autoconsistente, por lo que todas las leyes algebraicas que conocemos y amamos aún es cierto, pero donde todas las respuestas son elementos de algún conjunto de tamaño finito, generalmente números enteros dentro del rango de 0 a �−1 para algún �. Por ejemplo, si �=13, entonces 1/2=7 (y 7⋅2=1),3⋅5=2, y así sucesivamente. El uso de aritmética de campos finitos elimina la necesidad de preocuparse por los errores de redondeo y permite que el sistema funcione bien con curvas elípticas, que terminan siendo necesarias para el resto de la maquinaria zk-SNARK que hace que el protocolo zk-SNARK sea realmente seguro.
Un agradecimiento especial a Eran Tromer por ayudarme a explicarme muchos detalles sobre el funcionamiento interno de zk-SNARK.
- Distribución de relaciones públicas y contenido potenciado por SEO. Consiga amplificado hoy.
- PlatoData.Network Vertical Generativo Ai. Empodérate. Accede Aquí.
- PlatoAiStream. Inteligencia Web3. Conocimiento amplificado. Accede Aquí.
- PlatoESG. Carbón, tecnología limpia, Energía, Ambiente, Solar, Gestión de residuos. Accede Aquí.
- PlatoSalud. Inteligencia en Biotecnología y Ensayos Clínicos. Accede Aquí.
- Desplazamientos de bloque. Modernización de la propiedad de compensaciones ambientales. Accede Aquí.
- Fuente: Inteligencia de datos de Platón.
