Preámbulo
En el contexto de blockchain, zk-SNARK es una tecnología de seguridad avanzada que mejora la privacidad y garantiza la transparencia en las transacciones criptográficas.
Zk-SNARK permite acreditar un conocimiento sin revelar ese conocimiento, manteniendo la información del usuario absolutamente protegida.
Zcash, una criptomoneda líder, utiliza la tecnología zk-SNARK para anonimizar completamente las transacciones, garantizando una alta seguridad y no exponiendo la información personal de los usuarios. Esto aumenta la seguridad y confiabilidad de los usuarios al realizar transacciones en línea.
Para la parte 1 de la serie de investigación "Exploración de ZK-SNARK", profundizaré en los detalles importantes sobre zk-SNARK, así como en los algoritmos subyacentes y el cifrado detrás de esta tecnología, con gran detalle y de forma fácil de entender.
Concepto y mecanismo de acción de zk-SNARK
Conceptos básicos de zk-SNARK
Zk-SNARK significa Zero-Knowledge Succinct Non-Interactive Argument of Knowledge, que se traduce aproximadamente como "Prueba concisa y no interactiva de divulgación de no conocimiento" (lo traduje así para una fácil comprensión). Se trata de una construcción de prueba que permite a una parte (el probador) demostrar que posee cierta información, por ejemplo, una clave secreta, sin tener que revelar esa información y sin requerir correspondencia con otra parte (verificador).
Actualmente, zk-SNARK es el sistema de prueba más popular en uso.
Dividiremos el acrónimo “zk-SNARK” en componentes más pequeños para examinar su significado de la manera más clara.
“Conocimiento cero”: esto significa que la información ingresada se ocultará y no se revelará al verificador. En otras palabras, el verificador no puede saber nada sobre ese conocimiento sino sólo su validez.
“Sucinta” (breve): esto significa que las pruebas generadas son de tamaño pequeño, de unos pocos cientos de bytes, y se verifican rápidamente. Este es el primer beneficio que aporta SNARK.
“No interactivo”: Este es el segundo beneficio de SNARK, ambas partes (probador y verificador), la prueba consiste en un único mensaje del probador al verificador sin necesidad de comunicación de ida y vuelta.
“Argumento de conocimiento”: es un término técnico que significa que si el verificador acepta una prueba, entonces debe conocer un secreto relacionado con la afirmación que se está probando (en lugar de simplemente convencer al verificador de que la afirmación es verdadera).
Mecanismo de acción
Matemáticamente, zk-SNARK consta de 3 algoritmos:
Generación de claves (KG): este es un algoritmo de generación de claves, que generará un par de claves, una para prueba (pk) y otra para verificación (vk). El algoritmo de generación de claves toma como entrada el parámetro de seguridad λ y un programa en C, luego genera las claves. Este paso también se denomina paso de configuración confiable. Entraremos en detalles en la sección siguiente.(pk, vk) = KG(λ, C)
Prueba (P): Este algoritmo de prueba probará tomando como entrada una clave de prueba pk, una declaración x y un testigo w. El resultado es una prueba prf.prf = P(pk, x, w)
Verificación (V): El algoritmo de verificación toma como entrada la clave de verificación vk, la declaración x y la prueba prf. La salida es aceptar o rechazar.
Resultado de verificación = V(vk, x, prf)
Beneficios de ZK-SNARK
Los ZK-SNARK aportan muchos beneficios importantes, especialmente al mejorar el anonimato, la seguridad, la escalabilidad y la eficiencia de las transacciones en una variedad de aplicaciones. Aquí hay dos beneficios clave para las aplicaciones de software:
Privacidad: el atributo de “conocimiento cero” permite ocultar datos sensibles relacionados con los cálculos y al mismo tiempo demostrar la exactitud de la declaración. En otras palabras, zk-snark realiza transacciones sin revelar información personal, manteniendo la información de las transacciones anónima y segura. Esto es útil en criptomonedas como Zcash, donde los usuarios pueden enviar fondos sin revelar el monto, origen o destino de las transacciones.
Escalabilidad: gracias al tamaño pequeño de la prueba y al corto tiempo de verificación, el verificador puede saber rápidamente que el cálculo se realizó fielmente sin tener que volver a ejecutarlo, lo que reduce el tiempo y los recursos necesarios para verificar cálculos complejos, lo que aumenta el rendimiento y la confiabilidad del sistema. al mismo tiempo que ayuda a reducir costos y mejorar su escalabilidad.
Ceremonia de instalación de confianza
El proceso de establecimiento de confianza es un paso importante que se realiza solo una vez para generar un conjunto de datos necesario, que se utilizará más adelante cada vez que se implementen protocolos criptográficos.
En ZK-SNARK, este paso de configuración de confianza es necesario para generar claves de prueba y verificación. Luego, estas claves se ponen a disposición del público, lo que permite a los participantes utilizarlas para crear y verificar evidencia.
Para cada nuevo programa C, se debe realizar una nueva configuración confiable porque depende de los detalles de ese programa C. Durante la configuración, el proceso de generación de claves KG utiliza una lambda secreta y un programa C como entrada para generar una clave pública (pk) y una clave de verificación (vk).
(pk, vk) = KG(λ, C)
Por lo tanto, el proceso de configuración confiable no es estándar y debe realizarse por separado para cada programa nuevo.
Residuos Tóxicos (Residuos Tóxicos)
Se necesita un parámetro secreto llamado lamda para una configuración confiable. Este parámetro, a menudo llamado "Residuo Tóxico", a veces dificulta la aplicación de zk-SNARK a aplicaciones prácticas.
Esto se debe a que quien tenga este parámetro tiene la capacidad de crear pruebas falsas. Específicamente, el titular de lambda puede generar una prueba falsa, llamada fakeProof, para cualquier programa C con entradas públicas x, de modo que
V(vk,x,pruebafalsa)=verdadero
juzgado como verdadero sin conocer al testigo secreto w. ¡Esto es desastroso!
La forma más eficiente de generar parámetros públicos para zk-SNARK es que alguien genere un par de claves públicas y privadas, similar al par de claves ECDSA, y luego destruya la clave privada. Sin embargo, el punto de preocupación es ¿cómo podemos estar seguros de que este lado realmente ha eliminado esos “desechos tóxicos”?
Por lo tanto, para solucionar este problema se aplica la Computación Multipartita (Multi-Party Computation, MPC).
MPC es un protocolo criptográfico que permite que varias partes participen en el cálculo distribuido sin que ninguna de las partes tenga acceso a los datos confidenciales de la otra parte.
En cada proceso de establecimiento de confianza, varias partes participan juntas en el proceso para generar los componentes criptográficos necesarios, como la clave pública (pk) y la clave de verificación (vk). Cada parte aporta parte de sus datos confidenciales a este proceso.
El objetivo final de cada parte tras este proceso es eliminar por completo los residuos tóxicos. El supuesto de confiabilidad en este caso es que mientras uno de los n participantes sea honesto, se garantiza que el resultado final será seguro.
Durante la configuración de una confianza, cada una de las n partes aporta su lambda secreta para cogenerar las claves de prueba y verificación.
Para que esta configuración falle, sería necesario que las n partes tuvieran malas intenciones y compartieran sus secretos entre sí. Sin embargo, mientras una de las partes decida no revelar su secreto, el proceso de establecimiento del fideicomiso seguirá siendo exitoso, haciendo imposible la producción de pruebas falsas.
Las matemáticas y la codificación detrás de zk-snark
Fundamentos matemáticos
teoría de grupos
ZK-SNARK aprovecha la teoría de grupos para realizar cálculos en curvas elípticas y otros grupos, especialmente cuando se utilizan pares bilineales y algoritmos relacionados.
En pocas palabras, un grupo es un conjunto de elementos {a, b, c,...} combinados con una operación binaria, que denotamos aquí como “•”.
Un conjunto y una operación se denominan grupo si satisfacen las siguientes propiedades:
Cierre: Para todos los a y b en el grupo G, la operación a • b también debe estar en G.
Asociatividad: para todo a, b y c en G, la operación (a • b) • c debe ser igual a a • (b • c).
Elemento de identidad: Debe haber un elemento e en G tal que para cada elemento a en G, las operaciones e • a y a • e sean iguales a a. Este elemento es único.
Elemento inverso: para cada elemento a en G, debe haber un elemento b en G, a menudo llamado a^-1, tal que las operaciones a • b y b • a sean iguales a partir de la unidad e.
Subgrupos
Cuando un subconjunto de elementos de un grupo obedece a todas las propiedades del grupo, ese conjunto se denomina subgrupo del grupo original.
Campos
Un campo es una estructura algebraica especial donde un conjunto de elementos realiza dos operaciones básicas: suma y multiplicación. Cada campo debe ceñirse a una serie de axiomas básicos, que definen y garantizan sus propiedades generales.
A continuación se muestran los axiomas que debe satisfacer un campo, siendo a, byc cualquier elemento del campo F:
Asociatividad de la suma y la multiplicación : a + (b + c)= (a + b) + c anda · (b · c) = (a · b) · c
Propiedades conmutativas de la suma y la multiplicación: a + b = b + a y a · b = b · a
Ecuación de suma y multiplicación : Existen dos elementos diferentes 0 y 1 en F tales que a + 0 = a y a · 1 = a
Inverso aditivo: para cada a en F, existe un elemento en F, denotado −a, llamado inverso aditivo de a tal que a + (−a) = 0
Inverso de la multiplicación : Para cada a≠ 0 en F, existe un elemento en F, denotado a^ -1, llamado inverso multiplicativo de a tal que a · a^ -1 = 1
Distribución de la multiplicación con respecto a la suma: a· (b + c) = (a · b) + (a · c)
Ejemplos de campos incluyen el conjunto de números reales con suma y multiplicación, así como números enteros módulo primo, donde se definen tanto la suma como la multiplicación.
campos finitos
En ZK-SNARK, todas las operaciones se realizan en campos finitos, donde los valores y las operaciones se definen en módulo de un número primo o en función de un polinomio primo.
Un campo finito es un campo con un número finito de elementos, por ejemplo el conjunto de números enteros módulo p, donde p es primo.
El número de elementos en un campo, llamado orden del campo, para un campo finito puede ser:
Algunos números primos (campo primo)
O una potencia de un número primo (campo extendido)
En un campo primo simple, un elemento se puede representar mediante un número entero de 0 a p-1, donde Zp = {0, 1,…, p-1}.
La extensión de Zp, llamada grupo multiplicativo Zp*, consta de elementos que son coprimos con p, es decir, Zp* = {1,…, p-1}.
Generadores de campos finitos.
En todo campo finito existe un elemento llamado generador, que es capaz de generar todos los elementos del grupo usando su exponenciación.
Por ejemplo, considere el grupo Z5* en el campo principal Z5 = {0, 1, 2, 3, 4}, luego Z5* = {1, 2, 3, 4}. En el grupo Z5*, la multiplicación es una operación binaria y las multiplicaciones se realizan en módulo 5; Por ejemplo, al multiplicar 3 × 4 no se obtiene 12 sino 2, ya que 12 mod 5 = 2.
El grupo Z5* es cíclico y tiene los generadores 2 y 3, porque:
Con el generador 2, tenemos:
2^0 = 1,
2^1 = 2,
2^2 = 4,
2^3 = 3,
2^4 = 1 (repetir ciclo)
Y con el generador 3 tenemos:
3^0 = 1,
3^1 = 3,
3^2 = 4,
3^3 = 2,
3^4 = 1 (repetir ciclo)
Estas propiedades hacen de Z5* un grupo poderoso para operaciones criptográficas y se usa comúnmente en algoritmos criptográficos como ZK-SNARK.
Homomorfismos de grupo
Los homomorfismos son asignaciones entre dos estructuras algebraicas similares, como grupos o campos, y preservan las operaciones dentro de esa estructura.
Específicamente, un homomorfismo es un mapeo f del grupo A al grupo B, cuando los dos grupos tienen la misma operación binaria, como la multiplicación o la suma. Este mapeo preserva la operación, lo que significa:
Si ⋅ es una operación binaria en la estructura de los grupos A y B, entonces, para cada elemento a y b en el grupo A, la asignación f satisface la condición:
f ( x ⋅ y ) = f ( x )⋅ f ( y )
Esto garantiza que el resultado de la operación aplicada a los elementos del grupo A, después de asignarse al grupo B mediante f, siga siendo equivalente a la operación realizada directamente en el grupo B.
Los homomorfismos son fundamentales para manejar las propiedades de los pares bilineales, lo que hace que el proceso de generación y verificación de pruebas en zk-SNARK sea más eficiente.
Polinomios
Los polinomios son un componente central en la creación de programas de aritmética cuadrática (QAP), donde los problemas se representan mediante polinomios y se resuelven mediante evaluación y compromiso de polinomios.
Un polinomio es una expresión matemática formada por variables y constantes, que utiliza suma, multiplicación y exponenciación con exponentes enteros no negativos.
Por ejemplo, el polinomio 5x² + 2x + 8 es un buen ejemplo.
Al considerar una ecuación polinómica, esta puede representar un número infinito de ecuaciones diferentes entre números. Por ejemplo, si tenemos la ecuación A(x) + B(x) = C(x) que es verdadera, entonces también será cierta en todos los valores de x, como:
A(0) + B(0) = C(0)
A(1) + B(1) = C(1)
A(2) + B(2) = C(2)
A(3) + B(3) = C(3)
etcétera.
En cuanto al grado del polinomio, está determinado por la mayor potencia de la variable en el polinomio. Por ejemplo, el polinomio 6x⁴ + 2x³ + 3 tiene grado 4, porque la potencia más alta de la variable x es 4.
Criptografía
Funciones hash
Las funciones hash se utilizan ampliamente para crear "compromisos" en protocolos criptográficos, lo que ayuda a garantizar que los datos no puedan modificarse sin ser detectados.
Una función hash es un algoritmo o función matemática que convierte una cadena de datos de entrada de longitud variable en una cadena de salida de longitud fija, denominada valor hash.
La fórmula de representación de la función hash se puede describir de la siguiente manera:
f(metro)=H
donde f es la función hash, m es el mensaje y H es el valor hash resultante.
Las funciones hash tienen muchas propiedades importantes, lo que las hace muy útiles en muchas aplicaciones criptográficas. Esos atributos incluyen:
Resistencia previa a la imagen: Matemáticamente, recuperar el mensaje original a partir del valor hash es muy difícil.
Segunda resistencia previa a la imagen: dado un mensaje de entrada particular y su valor hash, es difícil encontrar otro mensaje que produzca el mismo valor hash.
Resistencia a la colisión: es difícil encontrar dos mensajes diferentes que produzcan el mismo valor hash.
Una propiedad muy deseable de las buenas funciones hash es el efecto avalancha. Esta es la propiedad por la cual un pequeño cambio en la entrada provocará un gran cambio en la salida, haciendo que la salida parezca aleatoria e indistinguible.
Cifrado
En pocas palabras, el cifrado es el proceso de convertir un mensaje de entrada (texto sin formato) en una salida aparentemente aleatoria (texto cifrado), de modo que solo las personas autorizadas puedan decodificar y comprender esa información. El cifrado se basa en el uso de una clave criptográfica, que es un conjunto de valores matemáticos que tanto el emisor como el receptor utilizan para cifrar y descifrar la información.
Hay dos tipos de algoritmos de cifrado: cifrado simétrico y cifrado asimétrico.
Cifrado simétrico
En el cifrado simétrico, todas las partes involucradas en el proceso de comunicación utilizan la misma clave para cifrar y descifrar el mensaje. Esta clave se mantiene en secreto entre las partes para garantizar la seguridad de la información intercambiada.
Cifrado asimétrico
En el cifrado asimétrico, también conocido como cifrado de clave pública, hay dos tipos de claves: una clave pública que se utiliza para el cifrado y una clave privada que se utiliza para el descifrado. El destinatario mantiene la clave privada en privado (de ahí la “clave privada”), mientras que la clave pública puede compartirse ampliamente con cualquiera que desee enviar información confidencial (de ahí la “clave privada”).
El cifrado asimétrico se utiliza ampliamente en las siguientes situaciones:
Envío de un mensaje seguro: el remitente utiliza la clave pública del destinatario para cifrar el mensaje y luego lo envía al destinatario. Sólo el destinatario en posesión de la clave privada puede descifrar y leer el mensaje.
Demostrar la propiedad de (conocimiento de) una clave privada: en el proceso de demostrar la propiedad de una clave privada, el remitente cifra (o firma) el mensaje con su clave privada y luego lo envía al destinatario. El destinatario utiliza la clave pública del remitente para descifrar el mensaje. Este proceso suele denominarse firma digital y el mensaje así cifrado se denomina "firma digital". De este modo, una firma digital demuestra que el mensaje fue enviado por alguien que posee la clave privada correspondiente y también ayuda a verificar la integridad de la información del mensaje.
Cifrado homomórfico (Cifrado homomórfico)
El cifrado homomórfico tiene una gran influencia en el diseño de pruebas de conocimiento cero de alto nivel, porque permite realizar cálculos sobre datos cifrados sin tener que descifrarlos.
El cifrado homomórfico es un tipo especial de cifrado que permite realizar cálculos directamente sobre datos cifrados. Esto significa que se pueden realizar cálculos adicionales sobre datos cifrados sin necesidad de una clave secreta. Los resultados de estos cálculos permanecen cifrados, lo que garantiza la seguridad sin revelar el contenido de los datos originales.
En la práctica, el cifrado totalmente homomórfico, que permite realizar todo tipo de cálculos arbitrarios sobre datos cifrados, todavía tiene muchas limitaciones y aún no es ampliamente aplicable. Sin embargo, realizar ciertas operaciones en estructuras homomórficas es factible y se ha utilizado en aplicaciones prácticas.
Estas operaciones incluyen la suma y multiplicación de datos cifrados, lo que ha abierto nuevas posibilidades para el procesamiento seguro de datos sin descifrado.
Criptografía de curva elíptica (ECC)
En ZK-SNARK, las curvas elípticas juegan un papel importante gracias a las operaciones de agrupación sobre las que se realiza el emparejamiento bilineal. ECC (criptografía de curva elíptica) proporciona una plataforma eficiente para crear y verificar pruebas de conocimiento cero.
Una curva elíptica es un conjunto de puntos que satisfacen una ecuación matemática específica. La ecuación de una curva elíptica tiene la siguiente forma:
Donde, a y b son constantes conocidas. La gráfica de esta ecuación se ve así:
Hay muchas representaciones diferentes de curvas elípticas, pero la técnica consiste principalmente en encontrar puntos que satisfagan una determinada ecuación matemática.
Las propiedades de las curvas elípticas las hacen muy importantes en muchos campos de las matemáticas y especialmente en el campo de la criptografía.
Una propiedad interesante de las curvas elípticas es su simetría horizontal. Cualquier punto de la curva se puede reflejar a través del eje x manteniendo la curva intacta. Esto significa que si tomas dos puntos cualesquiera de la curva y trazas una línea a través de ellos, esa línea cruzará la curva en un tercer punto.
Imagina que esto es un juego de billar, la bola se dispara desde un punto y cuando golpea la curva elíptica, rebota hacia arriba o hacia abajo, dependiendo de su posición relativa al eje x.
Una propiedad interesante de las curvas elípticas es que puedes "puntear" dos puntos en la curva para crear un nuevo punto. También puedes "poner puntos" sucesivamente en un punto consigo mismo para crear diferentes puntos en la curva.
Pero lo interesante es que, si conoces el punto final y el punto inicial, calcular el número de "puntos" necesarios para llegar desde el punto inicial al punto final es muy difícil.
Imagínese a una persona jugando sola en una habitación, golpeando la pelota según las reglas del juego. Luego entra alguien más y ve la posición final de la pelota. Incluso si conocieran la posición inicial y las reglas del juego, no podrían saber cuántas veces se golpeó la pelota para llegar allí sin revisar todo el juego desde el principio. Esto crea una propiedad especial en criptografía, llamada irreversibilidad, y es la base de muchas aplicaciones potentes, como la función Trapdoor.
Los logaritmos discretos en curvas elípticas son un problema difícil que sustenta la criptografía basada en curvas elípticas. A diferencia de la factorización, no existe ningún atajo que pueda resolver este problema, lo que hace que sea mucho más difícil descifrar la criptografía de curva elíptica que con RSA y Diffie-Hellman.
Si bien ECC proporciona un alto nivel de seguridad con claves más cortas, aún conserva un buen rendimiento en dispositivos de bajo consumo. Esto convierte a ECC en la opción ideal para aplicaciones criptográficas en dispositivos y sistemas móviles con recursos limitados.
Al final de esta sección, expuse algunos conceptos matemáticos y de codificación básicos detrás de zk-SNARK; en la siguiente parte, desarrollaré conceptos más avanzados como programas aritméticos cuadráticos y emparejamientos de curvas elípticas.
Gracias por leer hasta aquí. Si te ha gustado este artículo no olvides seguirlo y dejar un aplauso.
Fuente del artículo: Team Tech/Research – AlphaTrue
Fuente de referencia:
1.Nguồn: Reitwiessner, C. (2016). zkSNARK en pocas palabras. Blog de Ethereum, 6, 1-15. https://chriseth.github.io/notes/articles/zksnarks/zksnarks.pdf
2. https://medium.com/coinmonks/from-zero-to-hero-in-zero-knowledge-proofs-part-7-61d639c2ef02
3. https://celo.academy/t/zk-snarks-proofs-as-a-privacy-solution-on-the-blockchain/1961
4.Nguồn: 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
5. https://medium.com/coinmonks/from-zero-to-hero-in-zero-knowledge-proofs-part-8-262f923f1537
6. https://medium.com/@hira.siddiqui/from-zero-to-hero-in-zero-knowledge-proofs-part-2-ef17ce470f2d
7. Easttom, W. (2022). Criptografía moderna: matemáticas aplicadas al cifrado y seguridad de la información. Naturaleza Springer.
8. https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/
