Vitalik Buterin a través de Blog de Vitalik Buterin

Este es un espejo de la publicación en https://medium.com/@VitalikButerin/zk-snarks-bajo-el-capó-b33151a013f6

Esta es la tercera parte de una serie de artículos que explican cómo funciona la tecnología detrás de los zk-SNARK; los artículos anteriores sobre programas de aritmética cuadrática y parejas de curvas elípticas son lecturas obligatorias, y este artículo asumirá el conocimiento de ambos conceptos. También se asumen conocimientos básicos de qué son los zk-SNARK y qué hacen. Ver también Artículo de Christian Reitwiessner aquí para otra introducción técnica.

En los artículos anteriores, presentamos el programa de aritmética cuadrática, una forma de representar cualquier problema computacional con una ecuación polinómica que es mucho más susceptible a diversas formas de engaño matemático. También introdujimos pares de curvas elípticas, que permiten una forma muy limitada de cifrado homomórfico unidireccional que permite realizar comprobaciones de igualdad. Ahora, comenzaremos desde donde lo dejamos y usaremos pares de curvas elípticas, junto con algunos otros trucos matemáticos, para permitir que un probador demuestre que conoce una solución para un QAP en particular sin revelar nada más sobre el problema. solución real.

Este artículo se centrará en la Protocolo de Pinocho por Parno, Gentry, Howell y Raykova de 2013 (a menudo llamado PGHR13); Existen algunas variaciones en el mecanismo básico, por lo que un esquema zk-SNARK implementado en la práctica puede funcionar de manera ligeramente diferente, pero los principios básicos en general seguirán siendo los mismos.

Para empezar, analicemos el supuesto criptográfico clave que subyace a la seguridad del mecanismo que vamos a utilizar: el *conocimiento del exponente* suposición.

Básicamente, si obtienes un par de puntos � y �, donde �⋅�=�, y obtienes un punto �, entonces no es posible obtener �⋅� a menos que � se “deriva” de � de alguna manera. que tu sabes. Esto puede parecer intuitivamente obvio, pero esta suposición en realidad no puede derivarse de ninguna otra suposición (por ejemplo, dureza de registros discretos) que usualmente usamos cuando probamos la seguridad de protocolos basados ​​en curvas elípticas, por lo que los zk-SNARK de hecho descansan en un una base más inestable que la criptografía de curva elíptica en general, aunque todavía es lo suficientemente sólida como para que la mayoría de los criptógrafos estén de acuerdo con ella.

Ahora, veamos cómo se puede utilizar esto. Supongamos que un par de puntos (�,�) caen del cielo, donde �⋅�=�, pero nadie sabe cuál es el valor de �. Ahora, supongamos que se me ocurre un par de puntos (�,�) donde �⋅�=�. Entonces, la suposición de KoE implica que la única forma en que podría haber obtenido ese par de puntos fue tomando � y �, y multiplicando ambos por algún factor r. que lo sé personalmente. Tenga en cuenta también que gracias a la magia de los pares de curvas elípticas, comprobar que �=�⋅� en realidad no requiere saberlo – en su lugar, simplemente puede verificar si �(�,�)=�(�,�) o no.

Hagamos algo más interesante. Supongamos que tenemos diez pares de puntos que caen del cielo: (�1,�1),(�2,�2)…(�10,�10). En todos los casos, ��⋅�=��. Supongamos que luego le proporciono un par de puntos (�,�) donde �⋅�=�. ¿Qué sabes ahora? Sabes que � es una combinación lineal �1⋅�1+�2⋅�2+…+�10⋅�10, donde conozco los coeficientes �1,�2…�10. Es decir, la única forma de llegar a ese par de puntos (�,�) es tomar algunos múltiplos de �1,�2…�10 y sumarlos, y hacer el mismo cálculo con �1,�2… �10.

Tenga en cuenta que, dado cualquier conjunto específico de �1…�10 puntos para el que desee verificar combinaciones lineales, en realidad no puede crear los �1…�10 puntos que lo acompañan sin saber qué es �, y si sabe qué � es entonces que puedes crear un par (�,�) donde �⋅�=� para lo que � quieras, sin molestarte en crear una combinación lineal. Por lo tanto, para que esto funcione es absolutamente imperativo que quien crea esos puntos sea confiable y realmente los elimine una vez que hayan creado los diez puntos. De aquí proviene el concepto de “configuración confiable”.

Recuerde que la solución a un QAP es un conjunto de polinomios (�,�,�) tales que �(�)⋅�(�)−�(�)=�(�)⋅�(�), donde:

• � es una combinación lineal de un conjunto de polinomios {�1…��}
• � es la combinación lineal de {�1…��} con los mismos coeficientes
• � es una combinación lineal de {�1…��} con los mismos coeficientes

Los conjuntos {�1…��},{�1…��} y {�1…��} y el polinomio � son parte del planteamiento del problema.

Sin embargo, en la mayoría de los casos del mundo real, �,� y � son extremadamente grandes; para algo con muchos miles de puertas de circuito como una función hash, los polinomios (y los factores para las combinaciones lineales) pueden tener muchos miles de términos. Por lo tanto, en lugar de que el probador proporcione las combinaciones lineales directamente, usaremos el truco que presentamos anteriormente para que el probador demuestre que está proporcionando algo que es una combinación lineal, pero sin revelar nada más.

Es posible que hayas notado que el truco anterior funciona en puntos de curvas elípticas, no en polinomios. Por lo tanto, lo que realmente sucede es que agregamos los siguientes valores a la configuración confiable:

• �⋅�1(�),�⋅�1(�)⋅��
• �⋅�2(�),�⋅�2(�)⋅��
• ...
• �⋅�1(�),�⋅�1(�)⋅��
• �⋅�2(�),�⋅�2(�)⋅��
• ...
• �⋅�1(�),�⋅�1(�)⋅��
• �⋅�2(�),�⋅�2(�)⋅��
• ...

Puedes pensar en t como un “punto secreto” en el cual se evalúa el polinomio. � es un “generador” (algún punto de curva elíptica aleatoria que se especifica como parte del protocolo) y �,��,�� y �� son “residuos tóxicos”, números que absolutamente deben eliminarse a toda costa, o de lo contrario quien las tenga podrá hacer pruebas falsas. Ahora, si alguien te da un par de puntos �, � tales que �⋅��=� (recordatorio: no necesitamos �� para verificar esto, ya que podemos hacer una verificación de emparejamiento), entonces sabes que lo que lo que estás dando es una combinación lineal de �� polinomios evaluados en �.

Por lo tanto, hasta ahora el probador debe dar:

• ��=�⋅�(�),��′=�⋅�(�)⋅��
• ��=�⋅�(�),��′=�⋅�(�)⋅��
• ��=�⋅�(�),��′=�⋅�(�)⋅��

Tenga en cuenta que el demostrador en realidad no necesita saber (¡y no debería saber!) �,��,�� o �� para calcular estos valores; más bien, el probador debería poder calcular estos valores solo a partir de los puntos que estamos agregando a la configuración confiable.

El siguiente paso es asegurarse de que las tres combinaciones lineales tengan los mismos coeficientes. Esto lo podemos hacer agregando otro conjunto de valores a la configuración confiable: �⋅(��(�)+��(�)+��(�))⋅�, donde � es otro número que debería considerarse “tóxico”. residuos” y se descartan tan pronto como se completa la configuración confiable. Luego podemos hacer que el probador cree una combinación lineal con estos valores con los mismos coeficientes y use el mismo truco de emparejamiento que el anterior para verificar que este valor coincida con el �+�+� proporcionado.

Finalmente, necesitamos demostrar que �⋅�−�=�⋅�. Hacemos esto una vez más con una verificación de emparejamiento:

�(��,��)/�(��,�)?=�(�ℎ,�⋅�(�))

Donde �ℎ=�⋅�(�). Si la conexión entre esta ecuación y �⋅�−�=�⋅� no tiene sentido para usted, regrese y lea el artículo sobre emparejamientos.

Vimos arriba cómo convertir �,� y � en puntos de curva elíptica; � es solo el generador (es decir, el punto de curva elíptica equivalente al número uno). Podemos agregar �⋅�(�) a la configuración confiable. � es más difícil; � es simplemente un polinomio y predecimos muy poco de antemano cuáles serán sus coeficientes para cada solución QAP individual. Por lo tanto, necesitamos agregar aún más datos a la configuración confiable; específicamente la secuencia:

�,�⋅�,�⋅�2,�⋅�3,�⋅�4….

En la configuración confiable de Zcash, la secuencia aquí sube a aproximadamente 2 millones; Esta es la cantidad de potencias de � que necesita para asegurarse de poder calcular siempre �(�), al menos para la instancia QAP específica que les interesa. Y con eso, el probador puede proporcionar toda la información para que el verificador realice la verificación final.

Hay un detalle más que debemos discutir. La mayoría de las veces no queremos simplemente demostrar en abstracto que existe alguna solución para algún problema específico; más bien, queremos demostrar la exactitud de alguna solución específica (por ejemplo, demostrar que si tomas la palabra "vaca" y le aplicas hash SHA3 un millón de veces, el resultado final comienza con 0x73064fe5), o que existe una solución si restringes algunos de los parámetros. Por ejemplo, en una creación de instancias de criptomonedas donde los montos de las transacciones y los saldos de las cuentas están cifrados, desea demostrar que conoce alguna clave de descifrado k tal que:

1. decrypt(old_balance, k) >= decrypt(tx_value, k)
2. decrypt(old_balance, k) - decrypt(tx_value, k) = decrypt(new_balance, k)

El cifrado old_balance, tx_value y new_balance deben especificarse públicamente, ya que esos son los valores específicos que buscamos verificar en ese momento en particular; sólo se debe ocultar la clave de descifrado. Se necesitan algunas modificaciones leves al protocolo para crear una “clave de verificación personalizada” que corresponda a alguna restricción específica en las entradas.

Ahora retrocedamos un poco. En primer lugar, aquí está el algoritmo de verificación en su totalidad, cortesía de ben. Sasson, Tromer, Virza y ​​Chiesa:

La primera línea trata de la parametrización; Básicamente, puedes pensar en su función como la de crear una "clave de verificación personalizada". para el caso específico del problema donde se especifican algunos de los argumentos. La segunda línea es la verificación de combinación lineal para �,� y �; la tercera línea es la verificación de que las combinaciones lineales tengan los mismos coeficientes, y la cuarta línea es la verificación del producto �⋅�−�=�⋅�.

En total, el proceso de verificación consiste en unas pocas multiplicaciones de curvas elípticas (una para cada variable de entrada "pública") y cinco comprobaciones de emparejamiento, una de las cuales incluye una multiplicación de emparejamiento adicional. La prueba contiene ocho puntos de la curva elíptica: un par de puntos cada uno para �(�),�(�) y �(�), un punto �� para �⋅(�(�)+�(�)+�(� )), y un punto �ℎ para �(�). Siete de estos puntos están en la curva �� (32 bytes cada uno, ya que puedes comprimir la coordenada � en un solo bit), y en la implementación de Zcash un punto (��) está en la curva torcida en ��2 (64 bytes), por lo que el tamaño total de la prueba es ~288 bytes.

Las dos partes computacionalmente más difíciles de crear una prueba son:

• Dividiendo (�⋅�−�)/� para obtener � (algoritmos basados ​​en la Transformada rápida de Fourier puede hacer esto en tiempo subcuadrático, pero sigue siendo bastante intensivo desde el punto de vista computacional)
• Realizar multiplicaciones y sumas de la curva elíptica para crear los valores �(�),�(�),�(�) y �(�) y sus pares correspondientes.

La razón básica por la que crear una prueba es tan difícil es el hecho de que lo que era una única puerta lógica binaria en el cálculo original se convierte en una operación que debe procesarse criptográficamente a través de operaciones de curva elíptica si estamos haciendo una prueba con conocimiento cero a partir de ella. . Este hecho, junto con la superlinealidad de las transformadas rápidas de Fourier, significa que la creación de pruebas tarda entre 20 y 40 segundos para una transacción de Zcash.

Otra pregunta muy importante es: ¿podemos intentar hacer que la configuración confiable sea un poco… menos exigente? Desafortunadamente no podemos hacerlo completamente sin confianza; el supuesto KoE en sí mismo impide hacer pares independientes (��,��⋅�) sin saber qué es �. Sin embargo, podemos aumentar enormemente la seguridad mediante el uso de computación multipartita "de-", es decir, construyendo la configuración confiable entre las partes de tal manera que, siempre que al menos uno de los participantes elimine sus desechos tóxicos, entonces todo estará bien. .

Para tener una idea de cómo harías esto, aquí tienes un algoritmo simple para tomar un conjunto existente (�,�⋅�,�⋅�2,�⋅�3…) y “agregar” tu propio secreto. de modo que necesitas tanto tu secreto como el secreto anterior (o el conjunto de secretos anterior) para hacer trampa.

El conjunto de salida es simplemente:

�,(�⋅�)⋅�,(�⋅�2)⋅�2,(�⋅�3)⋅�3…

Tenga en cuenta que puede producir este conjunto conociendo solo el conjunto original y s, y el nuevo conjunto funciona de la misma manera que el conjunto anterior, excepto que ahora usa �⋅� como “desecho tóxico” en lugar de �. Siempre y cuando usted y la persona (o personas) que crearon el conjunto anterior no dejen de eliminar sus desechos tóxicos y luego se confabulen, el conjunto es “seguro”.

Hacer esto para una configuración confiable completa es un poco más difícil, ya que hay varios valores involucrados y el algoritmo debe realizarse entre las partes en varias rondas. Es un área de investigación activa para ver si el algoritmo de cálculo multipartito se puede simplificar aún más y hacer que requiera menos rondas o hacerse más paralelizable, ya que cuanto más se pueda hacer, más partes será factible incluir en el procedimiento de configuración confiable. . Es razonable ver por qué una configuración confiable entre seis participantes que se conocen y trabajan entre sí puede incomodar a algunas personas, pero una configuración confiable con miles de participantes sería casi indistinguible de ninguna confianza en absoluto, y si estás realmente paranoico , puede ingresar y participar en el procedimiento de configuración usted mismo y asegurarse de haber eliminado personalmente su valor.

Otra área de investigación activa es el uso de otros enfoques que no utilizan emparejamientos ni el mismo paradigma de configuración confiable para lograr el mismo objetivo; ver La reciente presentación de Eli ben Sasson para una alternativa (aunque tenga cuidado, ¡es al menos tan complicado matemáticamente como lo son los SNARK!)

Un agradecimiento especial a Ariel Gabizon y Christian Reitwiessner por su revisión.

• 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.