Pruebas de conocimiento cero: introducción a los fundamentos

Introducción

Las pruebas de conocimiento cero se encuentran entre las herramientas más poderosas creadas por los criptógrafos. Por desgracia, la mayoría de las personas no las entienden. Este artículo busca remediarlo con una descripción completa de las pruebas de conocimiento cero desde sus principios fundamentales. Abordamos la teoría, las matemáticas y la criptografía que las sustentan para que cualquiera pueda entender los avances más recientes en Solana, en particular ZK Compression y el futuro de la interoperabilidad.

Este artículo presupone que conoces el modelo de programación de Solana y las primitivas criptográficas propias de los sistemas blockchain (es decir, funciones hash, punteros hash, árboles de Merkle y árboles de Merkle concurrentes). Si estos conceptos son nuevos para ti, te recomiendo leer primero estas publicaciones anteriores del blog:

• Herramientas criptográficas 101: explicación de las funciones hash y los árboles de Merkle
• El modelo de programación de Solana: introducción al desarrollo en Solana

Ten en cuenta que este artículo se diseñó de forma modular. Si estos temas son nuevos para ti, te recomendamos leer cada sección y subsección en orden. Pero si ya conoces ciertos temas o quieres aprender sobre uno en particular, puedes ir directamente a la sección correspondiente.

Este también es el primer artículo de una serie de dos partes sobre pruebas de conocimiento cero. Te recomendamos encarecidamente leerlo antes de continuar con Pruebas de conocimiento cero: sus aplicaciones en Solana.

La teoría detrás de las pruebas de conocimiento cero

En 1989, los investigadores del MIT Shafi Goldwasser, Silvio Micali (fundador de Algorand) y Charles Rackoff publicaron La complejidad del conocimiento de los sistemas de pruebas interactivas. Trabajaban en sistemas donde una parte (es decir, el probador) intercambia mensajes con una segunda parte (es decir, el verificador) para convencerla de que cierta afirmación matemática es verdadera. Fueron los primeros en preguntar: «¿Qué ocurre si ni el probador ni el verificador confían el uno en el otro?». La preocupación es cuánta información aprenderá el verificador durante estos intercambios, aparte del hecho de que la afirmación es verdadera. Por ejemplo, el probador podría querer convencer al verificador de que conoce la solución de un acertijo complejo sin revelar la solución.

¿Qué tipo de problemas intentamos resolver en primer lugar?

Coloración de grafos con tres colores

La coloración de grafos con tres colores es un problema clásico de las ciencias de la computación y la teoría de grafos. Consiste en colorear los vértices de un grafo con tres colores de modo que ningún par de vértices adyacentes comparta el mismo color. En un grafo con tres vértices, esto es sencillo. Sin embargo, se vuelve cada vez más difícil conforme aumenta el número de vértices.

Una aplicación real sería la creación de horarios universitarios. En una universidad grande, los horarios deben evitar que un estudiante tenga clases superpuestas. Cada clase puede representarse como un vértice de un grafo y las aristas representan a los estudiantes compartidos entre clases. Esto garantiza que dos clases con un estudiante en común no se programen al mismo tiempo. Otras restricciones incluyen la capacidad de las aulas, los horarios preferidos de los profesores y una distribución uniforme de las clases durante la semana. Por tanto, deben asignarse horarios y aulas de modo que dos clases adyacentes no compartan el mismo horario. Esto puede resolverse con la coloración de grafos con tres colores.

Ahora imagina que una firma auditora externa debe verificar el horario final. Debido a ciertas normas de privacidad, la universidad no puede compartir con los auditores información detallada sobre la matrícula de los estudiantes. En su lugar, debe demostrar que el horario final cumple las restricciones necesarias sin revelar qué estudiantes están inscritos en cada clase. 

Para hacerlo, la universidad debe crear un grafo donde cada vértice represente una clase. Se dibujaría una arista entre dos vértices si las clases correspondientes tienen al menos un estudiante en común. La universidad asignaría horarios a cada clase para garantizar que dos clases adyacentes no se programen al mismo tiempo. Luego, la universidad se comprometería con el horario terminado mediante un esquema de compromiso criptográfico. Esto implica crear un hash criptográfico del horario asignado a cada clase y compartir los hashes con el verificador sin revelar los horarios. Después, la firma auditora externa seleccionaría al azar pares de clases adyacentes para cuestionar el horario asignado. La universidad revelaría los horarios comprometidos del par seleccionado y proporcionaría los compromisos originales (es decir, los hashes) para que la firma auditora pudiera verificar los valores revelados. Estos últimos pasos de cuestionar, revelar y verificar se repiten hasta que la firma auditora queda convencida de que no hay clases superpuestas. Recomiendo mucho la demostración interactiva de colorabilidad con tres colores y conocimiento cero del MIT para ver estos pasos en tiempo real.

La universidad quiere demostrarle a la firma auditora externa que conoce un horario correcto. Es decir, quiere demostrarle a otra parte que sabe algo. Lo interesante de este problema es que es NP-completo.

NP-completo

En la teoría de la complejidad computacional, un problema es NP-completo cuando:

• Para cualquier entrada del problema, la salida es «sí» o «no»
• Cuando la respuesta es «sí», puede demostrarse con una solución breve
• Debe ser posible verificar rápidamente si cada solución es correcta, y un algoritmo de fuerza bruta puede encontrar una solución probando todas las posibilidades

Los problemas NP-completos son importantes porque representan los problemas más difíciles dentro de la clase NP (es decir, un grupo de acertijos muy difíciles donde verificar una posible solución es sencillo en tiempo polinómico, pero encontrarla es difícil). Estos problemas destacan por su capacidad de simulación universal. Es decir, si podemos resolver rápidamente un problema NP-completo, podemos reducir o transformar cualquier problema NP en uno NP-completo y encontrar su solución en tiempo polinómico. Verificar las soluciones de problemas NP-completos también es sencillo. 

Por tanto, tenemos toda una clase de problemas que podemos demostrar de forma eficiente con pruebas de conocimiento cero. Por ejemplo:

• Problema del viajante — Dada una lista de ciudades y las distancias entre cada par, encuentra la ruta más corta posible que visite cada ciudad una vez y regrese a la ciudad de origen. Este problema tiene muchas aplicaciones en logística, planificación de rutas, fabricación y gestión de cadenas de suministro
• Problema de la mochila — Dado un conjunto de objetos, determina cuántas unidades de cada objeto deben incluirse en una colección para que el peso total sea menor o igual que un límite dado y el valor total sea lo más alto posible. Es un problema habitual en las finanzas y la asignación de recursos
• Programación de trabajos — Dado un conjunto de trabajos con duraciones y plazos específicos, prográmalos en una sola máquina para minimizar la penalización total por retrasos. Tiene numerosas aplicaciones en computación, fabricación y gestión de proyectos

Además, el teorema de Cook-Levin establece que el problema de satisfacibilidad booleana es NP-completo. Es decir, cualquier problema cuyas variables puedan sustituirse por valores verdaderos o falsos de modo que al final se evalúe como verdadero puede transformarse en un problema NP-completo. Esto implica que cualquier problema que podamos reducir a una serie de preguntas de verdadero o falso puede demostrarse eficientemente con pruebas de conocimiento cero.

Propiedades de una prueba de conocimiento cero

Dada la complejidad y la importancia de los problemas NP-completos, es esencial demostrar las soluciones de esta clase de problemas de forma eficiente y segura. Las pruebas de conocimiento cero permiten hacerlo sin comprometer la privacidad de la información involucrada. Goldwasser, Micali y Rackoff propusieron que todas las pruebas de conocimiento cero deben satisfacer las siguientes propiedades:

• Completitud — el probador acabará convenciendo al verificador si actúa con honestidad
• Solidez — un probador deshonesto nunca convencerá a un verificador de una afirmación falsa
• Conocimiento cero — la interacción entre el probador y el verificador solo revela si una afirmación es verdadera, y nada más

Al aprovechar las sólidas propiedades de las pruebas de conocimiento cero, podemos demostrar hechos o el conocimiento de cierta información en distintos contextos, preservando la privacidad y garantizando la exactitud. En secciones posteriores, analizaremos por qué esto resulta tan valioso para aplicaciones que requieren altos niveles de seguridad y eficiencia, como las blockchain.

Interactivas frente a no interactivas

Las pruebas de conocimiento cero suelen seguir la misma estructura de tres pasos:

• El probador genera una solución al cálculo (es decir, el testigo) y luego envía un compromiso con la respuesta del testigo
• El verificador responde con un valor de desafío generado al azar
• El probador calcula la prueba final a partir del compromiso y el desafío

Esta estructura es inherentemente interactiva: el probador afirma que sabe algo y el verificador lo cuestiona continuamente hasta que la probabilidad de que el probador lo engañe sea insignificante. Esto no es ideal para la mayoría de las aplicaciones, ya que el probador necesita una o varias respuestas antes de generar la prueba completa. Esta configuración presenta de forma inherente los siguientes desafíos:

• El verificador podría conspirar con el probador y permitirle falsificar pruebas
• El verificador podría crear pruebas falsas
• El verificador debe almacenar sus valores secretos en algún lugar, lo que podría exponerlos a filtraciones o ataques

La heurística de Fiat-Shamir es una técnica que toma una prueba interactiva de conocimiento y crea una firma digital basada en ella. De esta manera, puede demostrarse públicamente un hecho sin revelar la información subyacente. La idea es que, en vez de que el verificador envíe al probador un valor de desafío aleatorio, el probador puede calcular esta firma digital por sí mismo mediante una función aleatoria, como una buena función hash criptográfica. Así, en vez de que el verificador inspeccione el cálculo en 500 puntos distintos para comprobar que todos sean correctos, el probador calcula una raíz de Merkle del cálculo, usa esa raíz para elegir 500 índices de forma seudoaleatoria y proporciona las 500 ramas de Merkle correspondientes. La idea clave es que el probador no sabe qué ramas deberá revelar hasta después de comprometer los datos.

El lector atento puede detectar un defecto fatal al aplicar el muestreo aleatorio para revisar cálculos: el cálculo es inherentemente frágil. Un probador malicioso podría cambiar un solo bit en medio del cálculo sin que el verificador llegara a descubrirlo. ¿Cómo puede un verificador revisar cada parte del cálculo sin examinarlas una por una? Polinomios.

Sin embargo, debemos entender bastantes conceptos matemáticos antes de hablar de polinomios.

Las matemáticas detrás de las pruebas de conocimiento cero

Esta no pretende ser una introducción exhaustiva a los siguientes campos matemáticos; cada sección podría constituir un artículo completo. Es una introducción breve para que comiences a entender los fundamentos matemáticos de las pruebas de conocimiento cero y su funcionamiento general.

Este artículo también te presentará la notación matemática adecuada. Por ejemplo, en la siguiente subsección sobre teoría de conjuntos presentamos los símbolos ∈, ∉ y ⊆. En última instancia, todos estos símbolos son marcadores de otra cosa. Las pruebas de conocimiento cero no son un tema para principiantes; por eso, la gran mayoría de los artículos sobre el tema no son accesibles para ellos. No explicarán qué significan estos símbolos y darán por hecho que el lector entiende esta notación. Presentarla ahora es fundamental para que resulte menos intimidante si quieres profundizar en las pruebas de conocimiento cero. Intenta no perderte en la notación. Sigue adelante: llegará el momento en que mirarás estos símbolos y verás los conceptos subyacentes en vez de una letra griega.

Teoría de conjuntos

La teoría de conjuntos es una rama de las matemáticas que estudia colecciones de objetos. Un conjunto es una colección de objetos distintos. Estos objetos se denominan elementos o miembros del conjunto. Por ejemplo, considera una colección de frutas:

En la notación de conjuntos, se usan llaves para encerrar una colección de elementos y representar un conjunto. Así sabemos que manzana, naranja, pera y plátano forman parte del conjunto, mientras que algo como «papa» no. El símbolo ∈ indica pertenencia a un conjunto y se lee como «es un elemento de». Del mismo modo, ∉ indica que un elemento no pertenece a un conjunto determinado. Por tanto, podemos decir:

Esto se leería como «manzana es un elemento del conjunto Fruit y papa no es un elemento del conjunto Fruit».

Subconjuntos

También podemos tener conjuntos formados por otros conjuntos. Un subconjunto es un conjunto que solo contiene elementos presentes en otro conjunto. Por ejemplo, si tuviéramos:

Podemos decir que el conjunto Citrus es un subconjunto del conjunto mayor AllFruits. También podríamos usar nuestro conjunto Fruit anterior para decir que Fruit es un subconjunto del conjunto mayor AllFruit. En notación de conjuntos, lo escribiríamos así:

¿Por qué debería importarme?

La teoría de conjuntos es esencial para entender los conceptos de rangos y restricciones. En las siguientes secciones sobre teoría de números y aritmética modular, exploraremos la idea de que los números se encuentren dentro de cierto rango. Por ejemplo, podríamos tener un conjunto de valores posibles para una clave criptográfica:

Aquí, K define el rango de todas las claves posibles. Podemos crear pruebas de conocimiento cero que apliquen ciertas restricciones a este conjunto para que solo determinados valores sean válidos. Por ejemplo, podríamos indicar que la clave debe ser un número entre 1 y 5. 

Por tanto, la teoría de conjuntos aporta el lenguaje, las herramientas y la notación fundamentales para definir y analizar conjuntos de posibles entradas, salidas y estados en protocolos criptográficos. En las pruebas de conocimiento cero, a menudo debemos demostrar que un elemento pertenece a un conjunto o rango específico sin revelar el elemento.

Te recomiendo visitar Khan Academy para resolver algunas excelentes preguntas prácticas sobre notación básica de conjuntos.

Teoría de números

La teoría de números es una rama de las matemáticas que estudia los números enteros y las funciones aritméticas. Podemos definir los enteros como un conjunto de números sin parte fraccionaria, incluidos los números positivos, los negativos y el cero. De manera más formal, podemos definir el conjunto de los enteros así:

Aquí se usa ℤ para representar el conjunto de los enteros, y los puntos suspensivos muestran que van desde el infinito negativo hasta el infinito positivo. Por ejemplo, 12 es un entero y -1978649832794275 también lo es.

Números racionales

Los números racionales son números que podemos expresar como una fracción cuyo denominador (es decir, el número situado debajo de la línea en una fracción común, un divisor) no es cero. Por ejemplo, $(\frac{1}{2}), 74, (\frac{2}{3})$ son números racionales. Podemos definirlos de manera más formal como un conjunto de números que pueden expresarse como la fracción pq, donde p es el numerador, q es el denominador y q no es 0. El símbolo ℚ representa los números racionales. En notación de conjuntos, escribiríamos:‍

‍Aunque a primera vista parezca intimidante, esto describe exactamente lo que dice la oración anterior. Leeríamos esta extraña jerga matemática así: «Q es el conjunto de todas las fracciones p sobre q, donde p y q son enteros, y q no es igual a cero». 

Números reales

Los números reales abarcan tanto los racionales como los irracionales. Los números irracionales no pueden expresarse como una fracción simple y tienen decimales infinitos no periódicos. Por ejemplo, pi (es decir, π) y $\sqrt{2}$ (es decir, 1.4.1421…) son números irracionales. Omitiremos por ahora la notación de conjuntos, pero ten en cuenta que los números reales se representan con el símbolo ℝ.

¿Por qué debería importarme?

La teoría de números está estrechamente relacionada con la teoría de conjuntos, pues estudia conjuntos específicos de números (por ejemplo, los números racionales). Estos conjuntos suelen ser la base para definir rangos y restricciones en problemas matemáticos y criptográficos. 

También podemos ver la conexión entre ambas teorías. Por ejemplo, podemos decir que el conjunto de todos los enteros ℤ es un subconjunto de los números racionales ℚ. Esto resulta evidente en nuestra definición anterior de los números reales mediante notación de conjuntos, cuando afirmamos que el numerador y el denominador son enteros.

Aritmética modular

La aritmética modular, también conocida como aritmética del reloj, es un sistema de operaciones numéricas con enteros donde los números «vuelven al principio» después de alcanzar un valor específico, llamado módulo. La idea es que, en vez de trabajar con un conjunto infinito de números, trabajamos con los primeros n números positivos.

Relojes

Considera un reloj analógico (detesto que hoy en día deba especificar que tiene manecillas y no es digital) con los números del 1 al 12. Si fueran las 11 y quisiéramos saber la hora dentro de dos horas, no serían las 13. En cambio, volveríamos a la 1. Esto puede expresarse como $11 + 2 \equiv 1 \pmod{12}$ . La expresión matemática correcta sería $13 \bmod 12 = 1$. Quienes programan estarán familiarizados con el uso de la operación módulo en el formato $13 \% 12 = 1$.

Operación módulo

Cuando escribimos n mod k, queremos obtener el residuo de dividir n entre k. Esto se conoce como operación módulo. Por ejemplo:

• 25 mod 3 significa dividir 25 entre 3, lo que deja un residuo de 1 porque $25 = 8 \times 3 + 1$
• 15 mod 4 significa dividir 15 entre 4, lo que deja un residuo de 3 porque $15 = 3 \times 4 + 3$

En la aritmética modular, el residuo nunca es negativo.

¿Por qué debería importarme?

Entender la aritmética modular es fundamental porque permite comprender el comportamiento de los números bajo restricciones, algo valioso para la criptografía. La aritmética modular sustenta muchos algoritmos criptográficos y se usa en las ciencias de la computación, la ingeniería y cualquier campo que requiera manipular y cifrar datos de forma segura.

Considera el cálculo x + y = z. Si trabajamos con un campo finito definido por un número primo p = 17 (lo veremos enseguida; por ahora, piensa en él como el conjunto de todos los enteros del 0 al 16 que vuelve al principio al llegar a 17), el cálculo sería (x + y) mod p = z en este campo. Si x = 12 e y = 15, el cálculo sería:‍

El uso de la aritmética modular nos permite realizar cálculos dentro de un rango manejable de valores, definido por el número primo p. Esto es especialmente importante porque las computadoras y los procesadores tienen espacio limitado, por lo que normalmente trabajamos con enteros de tamaño fijo, como u32 o u64. La aritmética modular garantiza que nuestros valores permanezcan dentro de estos límites. Además, el uso de números primos añade una capa de complejidad. Esto es vital desde el punto de vista criptográfico porque mejora la seguridad y hace que ciertas propiedades matemáticas sean más predecibles y fiables.

Por ejemplo, la aritmética modular se usa en los zk-SNARKs para garantizar que los valores calculados permanezcan dentro de límites específicos y manejables. También se usa para crear circuitos aritméticos sobre un conjunto determinado de números. Así podemos expresar cálculos y garantizar que puedan verificarse de forma eficiente. En este caso, el probador tendría que demostrar que realizó el cálculo sin revelar los valores de x, y y z.

Te recomiendo consultar el conjunto de problemas de Art of Problem Solving y los ejercicios de aritmética modular de Joseph Zoller para adquirir más experiencia práctica en la resolución de problemas de aritmética modular. 

Teoría de grupos

La teoría de grupos es una rama de las matemáticas que estudia las estructuras algebraicas conocidas como grupos. Un grupo es un conjunto de elementos con una operación que satisface las siguientes condiciones, conocidas como axiomas de grupo:

• Clausura — El resultado de cualquier cálculo aritmético será otro elemento del conjunto
• Asociatividad — Al realizar la misma operación sobre tres o más elementos, la forma de agruparlos no importa; el resultado será el mismo
• Elemento identidad — Existe un elemento con el que puedes realizar una operación sobre cualquier otro elemento sin cambiar su valor
• Elemento inverso — Existe un elemento con el que puedes realizar una operación sobre cualquier otro elemento y obtener el elemento identidad

Formalmente, se definen así:

• Clausura — Si a y b pertenecen al grupo, el resultado de la operación (que suele representarse como $a \times b$, $ab$, $a \circ b$, o $ab$) también pertenece al grupo. Formalmente, podemos escribir $\forall a, b \in G \mid a \circ b \in G$. Podemos leerlo así: «para todos los valores de los elementos a y b del conjunto G, el resultado de la operación entre a y b está en G»
• Asociatividad — Si a, b y c pertenecen al grupo, entonces (ab)c = a(cb). Formalmente, podemos escribir $\forall a, b, c \in G \mid (a \circ b) \circ c = a \circ (b \circ c)$. Podemos leerlo así: «para todos los valores de los elementos a, b y c del conjunto G, la operación de a y b seguida de c es igual a la operación de a seguida de la operación de b y c»
• Elemento identidad — Existe un elemento e en el grupo tal que, para cada elemento a del grupo, se cumple la operación $e \circ a = a \circ e = a$. Formalmente, lo escribiríamos como $\exists e \in G \mid \forall a \in G \mid e \circ a = a \circ e = a$. Podemos leerlo así: «existe un elemento e en el conjunto G donde, para cada elemento a del conjunto G, la operación de e seguida de a es igual a la operación de a seguida de e, que es igual a a»
• Elemento inverso — Para cada elemento a del grupo, existe un elemento b en el grupo tal que $a \circ b = b \circ a = e$, donde e es el elemento identidad. Formalmente, lo escribiríamos como $\forall a \in G \mid \exists b \in G \mid a \circ b = b \circ a = e$. Podemos leerlo así: «para todos los valores de los elementos a del conjunto G, existe un elemento b en el conjunto G donde la operación de a seguida de b es igual a la operación de b seguida de a, que es igual al elemento identidad»

Podemos hacer más comprensible toda esta jerga matemática con un ejemplo. Considera el conjunto de los enteros bajo la suma. Podemos decir que este conjunto forma un grupo porque satisface los cuatro axiomas de grupo:

• Clausura — Si sumas dos enteros, obtienes otro entero
• Asociatividad — $(5 + 4) + 3 = 5 + (4 + 3)$
• Elemento identidad — El número cero se considera el elemento identidad porque sumar cero a cualquier entero no cambia su valor. Por ejemplo, $7 + 0 = 0 + 7 = 7$
• Elemento inverso — El inverso de cualquier entero es su negación porque al sumarlos se obtiene el elemento identidad. Por ejemplo, $5 + (-5) = 0$. Podemos generalizarlo como $n + (-n) = 0$

También podemos ampliar esto a un ejemplo más difícil, como el conjunto de números racionales distintos de cero $\mathbb{Q} = \left\{ \frac{a}{b} \mid a, b \in \mathbb{Z}, b \ne 0 \right\}$ bajo la multiplicación. Este también forma un grupo:

• Clausura — Multiplicar dos números racionales distintos de cero da como resultado otro número racional distinto de cero
• Asociatividad — $ab \times cd \times ef = ab \times (cd \times ef)$
• Elemento identidad — El número 1 se considera el elemento identidad porque multiplicar cualquier número racional distinto de cero por uno no cambia su valor. Por ejemplo, $\frac{1}{2} \times 1 = 1 \times \frac{1}{2} = \frac{1}{2}$
• Elemento inverso — El inverso de cualquier número racional distinto de cero es su recíproco (es decir, se intercambian el numerador y el denominador), porque el resultado será 1, el elemento identidad. Por ejemplo, $\frac{3}{5} \times \frac{5}{3} = 1$

Subgrupos

Un subgrupo es un grupo dentro de otro grupo. Para afirmar que el subgrupo H del grupo G es un subconjunto de G, tendrían que cumplirse los siguientes axiomas de grupo:

• Clausura — Si a y b están en H, el resultado de la operación entre ambos también debe estar en H
• Asociatividad — Este axioma se hereda del grupo mayor G 
• Elemento identidad — El elemento identidad de G también debe estar en H 
• Elemento inverso — Para cada elemento a de H, debe existir un elemento b también en H tal que ab y ba sean iguales al elemento identidad

El ejemplo clásico es el conjunto de los enteros pares bajo la suma como subgrupo del conjunto de los enteros bajo la suma:

• Clausura — Sumar dos enteros pares da como resultado otro entero par
• Asociatividad — Este axioma se hereda de los enteros. Por ejemplo, $2 + (4 + 6) = (2 + 4) + 6$
• Elemento identidad — El número cero se considera el elemento identidad porque sumar cero a cualquier entero par no cambia su valor. El cero también pertenece al conjunto de los enteros
• Elemento inverso — El inverso de cualquier número par también es par. Por ejemplo, el inverso de 4 es -4 porque $4 + (-4) = 0$, que es el elemento identidad

Podemos aplicar esto a un ejemplo más difícil. Considera el conjunto de todos los números racionales distintos de cero (es decir, ℚ*) bajo la multiplicación. Podemos demostrar que ℚ* es un subgrupo del conjunto de números reales distintos de cero (es decir, ℝ*) bajo la multiplicación:

• Clausura — Si a y b son números racionales distintos de cero, su producto ab también es un número distinto de cero. Por ejemplo, $\frac{1}{2} \times \frac{3}{4} = \frac{3}{8}$, que es un número racional distinto de cero
• Asociatividad — La multiplicación de números racionales es asociativa. Por ejemplo, $(\frac{1}{2} \times \frac{3}{4}) \times \frac{5}{6} = \frac{1}{2} \times (\frac{3}{4} \times \frac{5}{6})$
• Elemento identidad — El número 1 se considera el elemento identidad porque multiplicar cualquier número racional distinto de cero por 1 no lo modifica. Por ejemplo, $\frac{1}{2} \times 1 = 1 \times \frac{1}{2} = \frac{1}{2}$
• Elemento inverso — Cada número racional distinto de cero $a = \frac{p}{q}$ tiene un inverso multiplicativo $a^{-1} = \frac{q}{p}$, que también es un número racional distinto de cero y cuyo producto es igual al elemento identidad. Por ejemplo, sea a = $\frac{2}{3}$. Su inverso es $\frac{3}{2}$ porque $\frac{2}{3} \times \frac{3}{2} = 1$

Como ℚ* satisface todos los axiomas de grupo, forma un grupo. Además, puesto que ℚ* es un subconjunto de ℝ* y hereda sus propiedades, podemos afirmar que ℚ* es un subgrupo de ℝ*.

¿Por qué debería importarme?

Los grupos sustentan distintos conceptos y estructuras matemáticas y criptográficas. Por ejemplo, criptosistemas como RSA y la criptografía de curva elíptica dependen en gran medida de las propiedades de los grupos y sus operaciones. Entender los subgrupos permite comprender la estructura de grupos mayores mediante el análisis de sus subconjuntos más pequeños y manejables. Los grupos ofrecen un marco básico para entender la simetría, las operaciones y las transformaciones, algo esencial para la siguiente sección sobre campos.

Campos

Un campo es un conjunto de elementos que satisface los axiomas de campo para la suma y la multiplicación, y constituye un álgebra de división conmutativa (es decir, la división siempre es posible, excepto entre cero). Los axiomas de campo suelen escribirse en pares aditivos y multiplicativos:

• Suma
  • Asociatividad: $(a + b) + c = a + (b + c)$
  • Conmutatividad: $a + b = b + a$
  • Distributividad: $a(b + c) = ab + ac$
  • Elemento identidad: $a + 0 = 0 + a = a$
  • Elemento inverso: $a + (-a) = 0$
• Multiplicación
  • Asociatividad: $(ab)c = a(bc)$
  • Conmutatividad: $ab = ba$
  • Distributividad: $(a + b)c = ac + bc$
  • Elemento identidad: $(a + b)c = ac + bc$
  • Elemento inverso: $a \times a^{-1} = a^{-1} \times a = 1, \text{ if } a \ne 0$

Campos finitos y generadores

Un campo finito es un campo con un conjunto limitado de elementos. Los campos finitos también se conocen como campos de Galois. El número de elementos se denomina orden o cardinalidad del campo. Siempre será una potencia de un número primo. Lo interesante de los campos finitos es que cualquier operación aritmética realizada con elementos del campo permanecerá en él. Esto se debe a que todas las operaciones se realizan módulo el orden del campo, lo que hace que los valores vuelvan al principio.

Todo campo finito tiene un generador. Un generador puede producir todos los elementos del campo mediante exponenciación. Esto significa que podemos tomar el generador e incrementar su exponente en uno hasta obtener todos los elementos del campo. Por tanto, un generador es un elemento del campo que, mediante sus potencias, puede producir todos los elementos distintos de cero.

Por ejemplo, imagina que tomamos el conjunto de enteros módulo p = 7 y tenemos el campo $\mathbb{Z}_7 = \{0, 1, 2, 3, 4, 5, 6\}$. Si queremos encontrar el generador g de $\mathbb{Z}_7^*$ (es decir, el grupo multiplicativo de elementos distintos de cero de $\mathbb{Z}_7$, debemos asegurarnos de que g1, g2, g3, etc. puedan generar todos los elementos distintos de cero del campo.

Comprobemos si 3 es un generador:

Las potencias de 3 generan todos los elementos distintos de cero de $\mathbb{Z}_7$. Por tanto, 3 es un generador del grupo multiplicativo $\mathbb{Z}_7^*$.

¿Por qué debería importarme?

La criptografía es una ciencia que trabaja con conjuntos finitos. Esto aporta conocimientos fundamentales para abordar temas como el problema del logaritmo discreto, el cifrado, el intercambio Diffie-Hellman y las curvas elípticas. Los generadores permiten realizar operaciones aritméticas con polinomios cifrados sin descifrarlos (es decir, cifrado homomórfico). Es decir, podemos procesar datos cifrados y preservar la privacidad de los valores subyacentes. Entender esta sección es fundamental para la parte de conocimiento cero de las pruebas de conocimiento cero.

Te recomiendo visitar Bill’s Security Site, que ofrece un ejemplo interactivo para generar campos finitos con parámetros específicos y explica la teoría subyacente en Python. 

Funciones

Una función es una expresión, regla o ley que define una relación entre dos variables: la variable independiente y la variable dependiente. Estas dos variables suelen describirse como la causa y el efecto, respectivamente. Esta relación suele representarse como y = f(x), que se lee «f de x». Para cada valor de x hay un valor único de y, lo que significa que f(x) no puede tener más de un valor para la misma x.

Las funciones pueden ser uno a uno o muchos a uno, lo que suele denominarse cardinalidad. Esto significa que un valor x puede corresponder a un valor y único, o que varios valores x pueden corresponder al mismo valor y

Imagina una recta definida por $y = 3x + 4$. Esta es una función lineal donde introducir un valor de x devuelve el valor correspondiente de y. Juntos, estos dos valores forman un punto de la recta. Por ejemplo, podemos reescribir la ecuación como $f(x) = 3x + 4$ y evaluarla cuando x = 1, lo que da $f(1) = 7$. Las funciones también pueden tener varias variables. Por ejemplo, considera la fórmula del área de un triángulo: $A = \frac{bh}{2}$. Aquí, A (es decir, el área) se define como una función tanto de b (es decir, la base) como de h (es decir, la altura).

Dominio y rango

El dominio de una función es el conjunto de todos los valores de entrada posibles (es decir, las variables independientes) que la función puede aceptar. El rango de la función es el conjunto de todos los valores de salida posibles (es decir, las variables dependientes) que puede producir.

Para la función $y = 2x + 2$:

• El dominio abarca todos los números reales porque funciona cualquier número desde el infinito negativo hasta el infinito positivo. Por ejemplo:
  • Si x = 2.5, entonces $y = 2(2.5) + 2 = 7$ 
  • Si x = -9234525, entonces $y = 2(-9234525) + 2 = -18469048$
• El rango también abarca todos los números reales porque puede producirse cualquier número desde el infinito negativo hasta el infinito positivo. Por ejemplo:
  • Para encontrar y = -50, resolvemos -50 = 2x + 2, lo que da x = -26. 
  • Para encontrar y = 0, resolvemos 0 = 2x + 2, lo que da x = 0

¿Por qué debería importarme?

Las funciones son fundamentales para entender los polinomios. Estos son funciones especiales que incluyen variables elevadas a distintas potencias y sus coeficientes. Los polinomios son estructuras algebraicas fundamentales que sirven como base para construir protocolos criptográficos. En la siguiente sección, los analizaremos en detalle y veremos sus propiedades y su importancia en las pruebas de conocimiento cero.

Te recomiendo consultar Paul’s Online Notes y resolver sus ejercicios prácticos para entender mejor las funciones.

Polinomios

Un polinomio es una función compuesta por varias variables y coeficientes que solo utiliza las operaciones de suma, resta, multiplicación y exponenciación de variables a enteros no negativos. Los polinomios suelen escribirse de la siguiente forma:‍

Donde $a_n x^n + a_{n-1} x^{n-1} + \ldots + a_1 x + a_0$ son coeficientes y x es la variable. La potencia más alta de la variable x con un coeficiente distinto de cero se denomina grado del polinomio.

Los polinomios pueden clasificarse como univariados, si incluyen una sola variable (como la forma anterior), o multivariados, si incluyen varias variables (por ejemplo, $P(x, y) = a_nx^ny^n + a_{n-1}x^{n-1}y^{n-1} + \cdots + a_1xy + a_0$. Sum-Check es un ejemplo de protocolo que usa polinomios multivariados. Sin embargo, la mayoría de las veces, las pruebas de conocimiento cero solo requieren una variable.

Los nombres comunes asignados a los polinomios según su grado son:

• Grado 0 — Constante distinta de cero (por ejemplo, $P(x) = 6$)
• Grado 1 — Lineal (por ejemplo, $P(x) = 2x - 7$)
• Grado 2 — Cuadrático (por ejemplo, $P(x) = 8x^2 - 3x + 1$)
• Grado 3 — Cúbico (por ejemplo, $P(x) = 3x^3 - 4x$)

Si tenemos dos polinomios distintos de grado máximo $d$, pueden intersecarse en no más de $d$ puntos (por ejemplo, si igualamos una función lineal con una función cúbica, pueden intersecarse hasta tres veces). Esta propiedad se deriva de cómo encontramos puntos compartidos. Si queremos encontrar dónde se intersecan dos polinomios, los igualamos. En la siguiente subsección, practicaremos cómo encontrar las raíces de un polinomio, es decir, dónde un polinomio dado interseca el eje x. El teorema fundamental del álgebra establece que un polinomio de grado $d$ puede tener como máximo $d$ soluciones y, por lo tanto, como máximo $d$ puntos compartidos.

Raíces de polinomios 

Las raíces, o ceros, de un polinomio son los valores de x para los que el polinomio es igual a cero. En otras palabras, si $P(x)$ es un polinomio, una raíz $r$ es una solución de la ecuación $P(r) = 0$. Para encontrar las raíces, debemos saber factorizar polinomios. Factorizar consiste en determinar qué debemos multiplicar para obtener una cantidad dada. Por ejemplo, hay varias formas de factorizar 12:

Un método común de factorización consiste en descomponer por completo el número en factores primos positivos. Al factorizar, siempre es mejor comenzar por el máximo común divisor (MCD) que comparten todos los términos. Por ejemplo:

En el ejemplo anterior, ambos términos (es decir, 6x y 3) son divisibles entre 3, por lo que comparten un MCD de 3. Por lo tanto, los factores son 3 y $2x + 1$. Invertimos la propiedad distributiva: $3 \times 2x$ y $3 \times 1$. Encontrar las raíces consiste en despejar x cuando $P(x) = 0$.

La factorización es sencilla para polinomios con dos términos. Es aún más sencilla cuando se proporciona una gráfica, ya que las raíces se encuentran donde el polinomio interseca el eje x. Sin embargo, agregar tres o más grados puede aumentar la complejidad. Te recomiendo leer el artículo Cómo factorizar polinomios: explicación para obtener una explicación más detallada. 

No es esencial conocer todos los matices de la factorización de distintos polinomios para leer el resto de este artículo. Para nuestros fines, nos interesa cuándo se iguala un polinomio a otro valor. En este caso, nos interesa cuándo un polinomio es igual a cero. Más adelante, nos interesará cuándo un polinomio es igual a otro o cuándo la diferencia entre dos polinomios es idénticamente cero (es decir, todos los coeficientes son cero), lo que implica comprobar si un polinomio dado tiene determinadas raíces.

El lema de Schwartz-Zippel 

El lema de Schwartz-Zippel es una herramienta probabilística para comprobar si una ecuación polinómica siempre es verdadera. Evalúa el polinomio en puntos aleatorios y comprueba si el resultado es cero.

Imagina una ecuación compleja que involucra las variables $x_1, x_2, \ldots, x_n$. Si esta ecuación es un polinomio y no solo una colección aleatoria de términos, el lema de Schwartz_Zippel nos ayuda a verificar si se cumple para todos los valores posibles de estas variables.

Así es como funciona:

• Sea $P(x_1, x_2, \ldots, x_n)$ un polinomio de grado total d (es decir, la mayor suma de exponentes de cualquier término)
• Elige un conjunto finito S del cuerpo (como elegir un conjunto de números)
• Selecciona aleatoriamente valores para cada variable $x_1, x_2, \ldots, x_n$ del conjunto S

El lema establece que la probabilidad de que P sea cero en estos puntos elegidos al azar es, como máximo, $\frac{d}{S}$. Esto significa que, si el polinomio no es cero, es muy poco probable que parezca serlo por pura casualidad. Esto resulta especialmente útil para las pruebas de conocimiento cero, donde necesitamos verificar identidades polinómicas de forma eficiente.

Interpolación de Lagrange

La interpolación de Lagrange es un método para construir un polinomio que pasa por un conjunto dado de puntos. El polinomio de Lagrange es el polinomio de menor grado que pasa por cada punto dado. Para n puntos, se puede crear un polinomio de grado n-1 que pase por todos ellos. Por ejemplo, si tienes dos puntos en un plano, podemos definir una línea recta que pase por ambos. Si tenemos tres puntos en un plano, podemos definir un polinomio cuadrático (es decir, $y = ax^2 + bx + c$) que pase por todos los puntos. Y así sucesivamente.

¿Por qué debería importarme?

Los polinomios son un único objeto matemático que puede contener una cantidad ilimitada de información: piensa en un polinomio como una lista de números enteros y esto resulta evidente. Por lo tanto, una sola ecuación entre polinomios puede representar una cantidad ilimitada de ecuaciones entre números. Si alguien puede verificar una ecuación dada entre polinomios, implícitamente está verificando todas las ecuaciones posibles al mismo tiempo. Así protegemos las pruebas no interactivas de los riesgos de un probador malicioso y evitamos depender de comprobaciones aleatorias de un cálculo determinado. 

Los polinomios también tienen varias propiedades que los hacen útiles para crear pruebas:

• Si se proporcionan suficientes puntos de un polinomio dado, se puede reconstruir el polinomio completo
• Un pequeño cambio en la entrada de un polinomio puede provocar un cambio significativo en su salida, lo que facilita la detección de errores
• Los polinomios pueden detectar y corregir errores en los cálculos, de forma similar a como los códigos de borrado hacen que los datos sean tolerantes a fallos (lo cual es fundamental para el funcionamiento de Turbine)

Las pruebas de conocimiento cero se dedican a demostrar determinados cálculos. Los polinomios son invaluables para esta tarea, ya que podemos diseñarlos con características específicas. Supongamos que tienes un cálculo o un conjunto de puntos de datos que quieres demostrar. La forma más sencilla de hacerlo es codificarlo en un polinomio y usar sus propiedades para crear una prueba:

• Codifica los datos en un polinomio $P(x)$ de modo que evaluar $P(x)$ en determinados puntos produzca los datos originales o el resultado de un cálculo dado
• Para garantizar que el polinomio cumpla los criterios dados (por ejemplo, que todos los valores estén dentro de un rango), crea un polinomio de restricción $C(x)$. Por ejemplo, $C(x) = (P(x) - 0)(P(x) - 1)$ garantiza que $P(x)$ sea 0 o 1
• Transforma el problema en demostrar que $P(x)$ cumple ciertas condiciones para tu conjunto de datos o cálculo
• Crea un polinomio conocido $H(x)$ que sea múltiplo de $P(x)$ y codifique estas condiciones
• El probador confirma los valores de $P(x)$ y de cualquier polinomio relacionado mediante la creación de un árbol de Merkle con las evaluaciones, y envía el hash raíz al verificador
• El verificador selecciona al azar algunos puntos y pide al probador que proporcione los valores de $P(x)$ y $C(x)$ en esos puntos
• El verificador compara los valores proporcionados con el hash raíz confirmado y las relaciones polinómicas esperadas

No importa qué tan grande sea el polinomio. Como usamos el compromiso polinómico, podemos verificar ecuaciones entre polinomios en poco tiempo. Esta es una forma muy compacta y eficiente de crear pruebas. Cualquier error se amplifica y, mediante técnicas como la heurística de Fiat-Shamir, estas pruebas pueden volverse no interactivas para que cualquiera pueda verificarlas sin más interacción. 

Para ampliar tus conocimientos, te recomiendo revisar los siguientes problemas prácticos:

• Problemas prácticos de polinomios
• Problemas prácticos para encontrar ceros de polinomios
• Factorización de polinomios: problemas muy difíciles con soluciones

Khan Academy también tiene una unidad extensa sobre expresiones, ecuaciones y funciones polinómicas.

Ahora, para comprender mejor los compromisos polinómicos, es necesario explorar la criptografía detrás de las pruebas de conocimiento cero.

La criptografía detrás de las pruebas de conocimiento cero

Exploremos el cifrado simétrico y asimétrico.

Cifrado simétrico

El cifrado simétrico es una técnica en la que se usa la misma clave para cifrar el texto plano y descifrar el texto cifrado. Esta clave suele denominarse clave secreta o clave privada, porque usar una sola clave exige mantenerla en secreto. Sin embargo, esto también significa que la clave secreta debe compartirse con las dos partes antes de que puedan comunicarse de forma segura. Por eso, administrar y distribuir la clave secreta de manera segura puede resultar difícil y ser susceptible a filtraciones si no se maneja correctamente. Pese a esta desventaja, el cifrado simétrico es rápido, eficiente y requiere menos potencia de cómputo y memoria que otros esquemas de cifrado.

Entre los algoritmos comunes de cifrado simétrico se incluyen:

Estándar de Cifrado Avanzado (AES)

El Estándar de Cifrado Avanzado (AES) es una variante del cifrado por bloques Rijndael que se usa ampliamente en todo el mundo para proteger datos. Admite tamaños de clave de 128, 192 y 256 bits.

ChaCha20

ChaCha20 es un cifrado de flujo moderno y eficiente desarrollado por Daniel J. Bernstein. Es una variante del cifrado de flujo Salsa20 que aprovecha las operaciones de suma, rotación y XOR (ARX). Asigna una clave de 256 bits, un nonce de 64 bits y un contador de 64 bits a un bloque de 512 bits del flujo de claves, lo que permite buscar de forma eficiente cualquier posición del flujo de claves en tiempo constante.

Aunque el cifrado simétrico es robusto y eficiente, requiere un método seguro para intercambiar claves. Uno de estos métodos es el intercambio de claves Diffie-Hellman, que permite a dos partes compartir de forma segura una clave secreta a través de un canal inseguro. Sin embargo, este método se basa en principios de cifrado asimétrico, que veremos en la siguiente sección.

Cifrado asimétrico

El cifrado asimétrico, también conocido como cifrado de clave pública, es un método que usa un par de claves relacionadas (es decir, una clave pública y una clave privada) para cifrar y descifrar información. La clave pública se comparte abiertamente, mientras que la privada se mantiene en secreto. Cuando un remitente quiere cifrar un mensaje, usa la clave pública del destinatario. Al recibirlo, el destinatario descifra el mensaje con su clave privada correspondiente. Los datos cifrados con la clave pública solo pueden descifrarse con la clave privada. Por lo tanto, el cifrado asimétrico permite una comunicación segura a través de canales inseguros, ya que la clave de descifrado nunca se comparte.

El cifrado asimétrico es ventajoso porque ofrece un alto nivel de seguridad, ya que la clave privada nunca se comparte. También simplifica la distribución de claves porque la clave pública puede compartirse abiertamente y permite las firmas digitales. Sin embargo, el cifrado asimétrico exige más recursos de cómputo y es más lento que el simétrico. Administrar pares de claves también puede volverse complejo, especialmente en sistemas con muchos usuarios y donde los pares de claves no son intuitivos. 

Entre los algoritmos comunes de cifrado asimétrico se incluyen:

• Rivest-Shamir-Adleman (RSA) — uno de los criptosistemas de clave pública más antiguos y utilizados para transmitir datos de forma segura. Se desarrolló en la década de 1970 y se basa en la dificultad práctica de factorizar el producto de dos números primos grandes
• Criptografía de Curva Elíptica (ECC) — un enfoque de criptografía de clave pública basado en la estructura algebraica de las curvas elípticas sobre cuerpos finitos. Ofrece una seguridad similar a RSA, pero con claves más pequeñas, lo que permite cálculos más rápidos y reduce los requisitos de almacenamiento. Solana usa la curva elíptica Ed25519 para generar sus pares de claves

Firmas digitales

Las firmas digitales son un aspecto clave de la criptografía de clave pública y permiten verificar la autenticidad e integridad de un mensaje, software o documento digital. Una firma digital se crea con la clave privada del remitente y puede verificarla cualquier persona que tenga acceso a la clave pública correspondiente. Esto garantiza que el mensaje provenga de un remitente legítimo y no haya sido alterado.

Entre los algoritmos comunes usados para firmas digitales se incluyen:

• Algoritmo de Firma Digital (DSA) — un enfoque basado en la exponenciación modular (es decir, exponenciación realizada sobre un módulo) y el problema del logaritmo discreto
• Algoritmo de Firma Digital de Curva Elíptica (ECDSA) — una variante de DSA que usa criptografía de curva elíptica para ofrecer un mayor nivel de seguridad con claves más pequeñas

Problema del logaritmo discreto

El problema del logaritmo discreto consiste en encontrar el exponente k en la ecuación $g^k \equiv h \pmod{p}$, donde:

• g es una base conocida (es decir, un generador)
• h es un resultado conocido (es decir, un elemento del grupo)
• p es un número primo (es decir, el orden del grupo)
• k es el exponente desconocido (es decir, el logaritmo discreto de h en base g)

Para desglosarlo, si conoces los valores de g, h y p, el problema del logaritmo discreto consiste en encontrar k. Por ejemplo, dada la ecuación $2^k \equiv 9 \pmod{23}$, el objetivo es encontrar k.

Se considera que el problema del logaritmo discreto es difícil de resolver de forma eficiente, especialmente con números grandes. Debido a esta dificultad, constituye la base de la seguridad de diversos sistemas criptográficos, incluidos Solana, el cifrado ElGamal, los algoritmos de firma digital (es decir, DSA y ECDSA) y el intercambio de claves Diffie-Hellman

Intercambio de claves Diffie-Hellman

El intercambio de claves Diffie-Hellman es un método para intercambiar claves criptográficas de forma segura a través de un canal público.  La implementación original y más sencilla (es decir, Diffie-Hellman sobre cuerpos finitos) funciona así:

• Alice y Bob acuerdan públicamente dos números: un número primo grande p (es decir, el módulo) y una base g (es decir, el generador), que es una raíz primitiva módulo p 
• Alice selecciona un entero secreto a y luego envía a Bob $A \equiv g^a \pmod{p}$
• Bob selecciona un entero secreto b y luego envía a Alice $B \equiv g^b \pmod{p}$
• Alice calcula $s \equiv B^a \pmod{p}$ 
• Bob calcula $s = A^b \pmod{p}$ 

Ahora Alice y Bob tienen el mismo valor secreto. Esto se debe a que ambos cálculos producen el mismo secreto s, porque:

Este secreto compartido s puede usarse como clave para el cifrado simétrico, lo que permite que Alice y Bob se comuniquen de forma segura. La seguridad del intercambio de claves Diffie-Hellman se basa en la dificultad del problema del logaritmo discreto. Sin conocer los valores secretos a y b, es computacionalmente inviable que alguien que esté espiando obtenga el secreto compartido. Esto se conoce como función unidireccional: es relativamente fácil de calcular, pero extremadamente difícil de invertir.

Aunque el intercambio de claves Diffie-Helman sobre cuerpos finitos es seguro y se usa ampliamente, requiere claves grandes para garantizar la seguridad. Por ejemplo, si Alice y Bob eligieran públicamente un módulo de 23, sería mucho más fácil vulnerarlo, ya que solo existen 23 resultados posibles de n mod 23. Por lo tanto, puede exigir muchos recursos de cómputo y ser menos eficiente. Para abordar estos desafíos, la criptografía de curva elíptica (ECC) ofrece una alternativa más eficiente, ya que proporciona el mismo nivel de seguridad con claves mucho más pequeñas y cálculos más rápidos.

Curvas elípticas

Una curva elíptica se define mediante la ecuación $y^2 = x^3 + ax + b$, donde a y b son constantes. La criptografía de curva elíptica consiste simplemente en trabajar con puntos de una curva elíptica dada. Estas curvas tienen varias propiedades únicas que las hacen útiles para la criptografía. Por ejemplo:

• Suma de puntos — Dados dos puntos, P y Q, en una curva elíptica, su suma R = P + Q también será un punto de la curva. El artículo de Preethi Kasireddy, Una guía sencilla de criptografía para pruebas de conocimiento cero, ofrece una buena explicación sobre cómo sumar puntos en una curva elíptica
• Multiplicación escalar — Dados un punto P en una curva elíptica y un entero k, la multiplicación escalar consiste en sumar el punto P consigo mismo k veces. Esto produce otro punto (es decir, kP) en la curva. Se usa para generar claves públicas a partir de claves privadas
• Problema del logaritmo discreto — El problema del logaritmo discreto en curvas elípticas es mucho más difícil de resolver que su equivalente con enteros. Dados los puntos P y q = kP, es computacionalmente inviable determinar k si los parámetros de la curva se eligen correctamente. Esto significa que las curvas elípticas proporcionan la misma seguridad que los sistemas tradicionales con claves mucho más pequeñas, lo que las hace más eficientes

Con nuestros nuevos conocimientos de teoría de grupos, podemos afirmar que ciertas ecuaciones de curvas elípticas satisfacen el conjunto de axiomas:

• Se pueden sumar dos puntos cualesquiera para obtener un tercer punto
• No importa en qué orden se sumen los dos puntos
• Si tienes más de dos puntos que sumar, no importa en qué orden se sumen
• Existe un elemento identidad (es decir, sumar cero a cualquier punto de la curva da como resultado el mismo punto)

Te recomiendo ampliamente leer Criptografía de curva elíptica de Georgie Bumpus para explorar con mayor detalle esta estructura de grupo. 

Las curvas elípticas ofrecen el mismo nivel de seguridad que otros criptosistemas tradicionales, como RSA, pero con claves mucho más pequeñas. Por ejemplo, una clave de 256 bits en ECC proporciona una seguridad comparable a la de una clave de 3072 bits en RSA. Esto resulta beneficioso porque:

• Las claves más pequeñas permiten cifrar y descifrar con mayor rapidez
• Las claves y los certificados requieren menos espacio
• Las claves más pequeñas reducen la cantidad de datos transmitidos, lo que resulta beneficioso en entornos con ancho de banda limitado, como una blockchain

Curvas de Montgomery

Las curvas de Montgomery son un tipo de curva elíptica definido por la ecuación $By^2 = x^3 + Ax^2 + x$ sobre un cuerpo finito, donde A y B son constantes, B no es igual a cero y A no es -2 ni 2. Estas curvas son especiales porque la multiplicación de curva elíptica puede implementarse de forma más eficiente mediante una escalera de Montgomery. 

Una escalera de Montgomery toma básicamente un punto P de una curva de Montgomery y un escalar k, inicializa dos puntos desde el infinito hasta P y actualiza cada bit del escalar k, desde el bit más significativo hasta el menos significativo. La idea principal es mantener dos puntos y actualizarlos mediante una secuencia constante de operaciones, independientemente de los bits del escalar k.

Esto es importante por varias razones:

• Es resistente a los ataques de canal lateral, que son ataques basados en la información adicional que puede recopilarse debido a la implementación o el diseño de un protocolo o algoritmo. Es un tema muy, muy técnico en el que te recomiendo profundizar. Estos ataques abarcan desde las variaciones en el consumo de energía del hardware durante el cálculo hasta la radiación electromagnética filtrada
• No necesita la coordenada y, ya que la multiplicación escalar puede realizarse solo con las coordenadas x
• Opera en tiempo constante, lo que significa que el tiempo necesario para un cálculo no depende del valor de entrada

Las curvas de Montgomery se usan ampliamente en protocolos criptográficos, como el algoritmo X25519 para el intercambio de claves, que usa la forma de Montgomery de la curva Curve25519. Este algoritmo constituye la base de las comunicaciones seguras modernas, incluidas sus implementaciones en protocolos populares como TLS. 

Curvas de Edwards

Las curvas de Edwards son un tipo de curva elíptica definido por la ecuación $x^2 + y^2 = 1 + d x^2 y^2$, donde d es una constante distinta de cero y de 1.  

Estas curvas son importantes porque:

• Eficiencia en las operaciones con puntos — La suma de dos puntos en una curva de Edwards es más eficiente que en otras formas de curvas elípticas. Las fórmulas para sumar y duplicar puntos son más sencillas e implican menos operaciones de cuerpo, por lo que son más rápidas de calcular
• Fórmula de suma unificada — Las curvas de Edwards usan una fórmula de suma unificada, lo que significa que la misma fórmula puede usarse para sumar y duplicar puntos. Esto reduce la posibilidad de errores de implementación y mejora la seguridad
• Completitud — Para determinados valores de d, las curvas de Edwards son completas. Esto significa que la ley de suma cubre todas las entradas posibles sin excepciones.
• Resistencia a ataques de canal lateral — Al igual que las curvas de Montgomery, las curvas de Edwards son resistentes a los ataques de canal lateral gracias a sus patrones de operación uniformes y predecibles.

Una curva de Edwards ampliamente utilizada es Edwards25519, definida por la ecuación $x^2 + y^2 = 1 - \frac{121665}{121666} x^2 y^2$. Esta curva es conocida por su aritmética eficiente y su clave de 256 bits. Su esquema de firmas se implementa en diversos protocolos y sistemas de seguridad, incluidos Solana, OpenSSH y Tor. Monero usa Edwards25519 como base para generar sus pares de claves.

¿Por qué debería importarme?

Las curvas elípticas son fundamentales para las pruebas de conocimiento cero por su eficiencia y sus propiedades que mejoran la seguridad. Ten en cuenta que el uso de curvas elípticas permite crear pruebas más pequeñas y rápidas, algo esencial para cualquier implementación práctica. Analizaremos esto en mayor profundidad cuando hablemos de desarrollos relacionados con el conocimiento cero, pero contar con pruebas pequeñas y rápidas es fundamental en un entorno de alto cómputo con diversas restricciones de cuentas y transacciones. Esto hace que las pruebas de conocimiento cero resulten atractivas para crear rollups, ya que se podría generar una prueba compacta de que todas las operaciones en una L2 son válidas y validarla en la L1.

En última instancia, piensa en las curvas elípticas como un sustituto de la aritmética modular. Con las curvas elípticas, es mucho más difícil obtener un punto específico. Si usáramos la aritmética modular tradicional con $g^a \bmod n$, donde g es un generador, n es un número primo grande y a es la clave secreta, necesitaríamos un número primo muy grande para proteger la clave secreta, como vimos anteriormente con el problema del logaritmo discreto. Las curvas elípticas ofrecen una alternativa más eficiente con claves más pequeñas y proporcionan el mismo nivel de seguridad con un rendimiento mucho mayor.

Aleatoriedad

Nada más de este artículo importaría sin la aleatoriedad, un aspecto fundamental de la criptografía. ¿Cómo puedes esperar que un sistema sea seguro si sus valores son predecibles y están sesgados? Lograr una aleatoriedad verdadera puede resultar difícil, pero es esencial por varias razones:

• Generación de claves — Las claves criptográficas deben generarse aleatoriamente para garantizar que sean impredecibles y seguras
• Nonces y sales — Los nonces (es decir, números que se usan una sola vez) y las sales (es decir, valores aleatorios añadidos a los datos antes del hashing) evitan los ataques de repetición y protegen contra los ataques precalculados, respectivamente
• Protocolos seguros — La aleatoriedad se usa para garantizar la equidad y la seguridad, e impedir la previsibilidad y los patrones que los atacantes podrían explotar

La mayoría de los generadores de números aleatorios no producen un número aleatorio que pueda verificarse criptográficamente. Esto los vuelve vulnerables a la manipulación y limita sus casos de uso. Sin embargo, las funciones aleatorias verificables resuelven este problema.

Funciones aleatorias verificables

Una función aleatoria verificable (VRF) es una primitiva criptográfica que produce una salida aleatoria y una prueba de que esa salida se generó correctamente a partir de una entrada dada. Una VRF debe ser impredecible, lo que significa que su salida es indistinguible de un valor aleatorio para cualquiera que no conozca la entrada secreta. Su seguridad se basa en la suposición de RSA de que resulta difícil calcular $y = h^d \bmod n$ sin conocer el exponente secreto d, así como en la seguridad de la función hash H. 

Los pasos principales de una VRF determinada son los siguientes:

• Generación de claves — El usuario genera un par de claves RSA: (e, n) como clave pública y (d, n) como clave privada. En la clave pública, e es el exponente y n es el módulo. En la clave privada, d es el exponente secreto
• Cálculo — Dada una entrada x, el usuario calcula la salida de la VRF y y la prueba π. Primero, se calcula el hash h = H(x), donde H es una función hash criptográfica. Después se calcula $y = h^d \bmod n$, que es la firma RSA del hash. Por último, se calcula la prueba π = (h, y)
• Verificación — Con la clave pública (e, n), la entrada x, la salida y y la prueba π = (h, y), cualquiera puede verificar que la salida de la VRF sea correcta comprobando que el hash h sea igual a $H(x)$ y que $y^e \equiv h \pmod{n}$ verifique la ecuación RSA‍

Las VRF suelen usarse en protocolos de consenso donde la aleatoriedad debe ser impredecible, pero verificable. Varias L1, incluidas Algorand, Cardano, Internet Computer y Polkadot, usan VRF en sus mecanismos de consenso para seleccionar productores de bloques al azar. Chainlink ofrece Chainlink VRF como una capa de abstracción entre el usuario y la blockchain para generar valores demostrablemente imparciales y verificables. Pyth Entropy también ofrece una fuente de aleatoriedad confiable y segura.

Ceremonias y configuraciones de confianza

Las ceremonias criptográficas son protocolos o eventos en los que se realizan cálculos criptográficos críticos dentro de un entorno seguro y controlado. Existen varios tipos de ceremonias criptográficas, entre ellas:

• Ceremonias de generación de claves — Consisten en generar claves criptográficas para garantizar que ninguna entidad individual controle el proceso de generación
• Ceremonias de generación de parámetros — Consisten en crear parámetros criptográficos que usarán varias partes
• Ceremonias de cómputo multipartito (MPC) — Consisten en que varias partes realicen conjuntamente un cálculo criptográfico para garantizar que ninguna de ellas pueda comprometer el proceso

Una ceremonia de configuración de confianza es un evento o proceso especial diseñado para generar un conjunto de parámetros criptográficos necesarios para ejecutar un protocolo criptográfico. En nuestra sección sobre pruebas de conocimiento cero interactivas y no interactivas, identificamos que el primer paso de una prueba consiste en que el probador y el verificador acuerden algún valor que usarán. En una ceremonia de configuración de confianza, varios participantes aportan aleatoriedad a la configuración para garantizar que ninguno controle el proceso por sí solo. Cada participante genera un valor aleatorio que se combina con los valores proporcionados por los demás. El resultado combinado se convierte en un conjunto de parámetros en el que todos pueden confiar. 

Este proceso es fundamental porque, si todos los participantes se confabularan, podrían vulnerar el sistema al generar una prueba para una afirmación no válida. Sin embargo, basta con que un solo participante sea honesto para garantizar la seguridad de los parámetros. 

Zcash utilizó una conocida ceremonia de confianza para inicializar las funciones de privacidad de la cadena. Ethereum también llevó a cabo la ceremonia KZG, un ritual público coordinado para proporcionar una base criptográfica a sus esfuerzos de escalabilidad (por ejemplo, EIP-4844 / proto-danksharding). 

Ten en cuenta que algunos sistemas de pruebas de conocimiento cero, como los zk-STARK, no requieren una configuración de confianza. Exploraremos esto con mayor detalle en el segundo artículo.

Conclusión

En este artículo, exploramos la teoría, las matemáticas y la criptografía que sustentan las pruebas de conocimiento cero. Esto es todo lo que necesitas saber para empezar a responder qué son las pruebas de conocimiento cero. Ahora podemos aplicar lo aprendido a redes como Solana para contribuir al debate y al desarrollo general de estas pruebas.

Continuamos este análisis en el segundo y último artículo de nuestra serie de dos partes sobre las pruebas de conocimiento cero, acertadamente titulado Pruebas de conocimiento cero: sus aplicaciones en Solana. 

Si llegaste hasta aquí, ¡gracias, anon! Ingresa tu dirección de correo electrónico abajo para no perderte ninguna novedad sobre Solana. ¿Quieres profundizar? Explora los artículos más recientes en el blog de Helius y continúa hoy tu recorrido por Solana.

Recursos adicionales

• ¿Existe la verdadera aleatoriedad?
• Curvas elípticas — Computerphile
• Introducción a la clase de complejidad NP-completa
• Problemas del intercambio de claves — Computerphile
• Unidad de Khan Academy sobre criptografía
• Criptografía de clave pública — Computerphile
• La complejidad del conocimiento en los sistemas de pruebas interactivas