Preámbulo
¿Estás listo para explorar un lado más complejo de zk-SNARK? En la sección anterior, aprendimos sobre algunos conceptos más avanzados como el circuito aritmético y el programa aritmético cuadrático. En esta sección, ampliaremos nuestro conocimiento profundizando en otro concepto poderoso: Emparejamientos de curvas elípticas.
Nota: Comprender en profundidad un tema como Emparejamientos de curvas elípticas a veces puede resultar un desafío para muchos. Sin embargo, es por eso que tenemos este artículo: para ayudarle a obtener al menos una perspectiva básica sobre esto.
Mi objetivo no es sólo explicar detalladamente los emparejamientos de curvas elípticas, sino también hacer que el tema sea más interesante y fácil de entender. Con suerte, a través de este artículo verás el poder de los pares de curvas elípticas en matemáticas y criptografía en general, así como en sus aplicaciones específicas en zk-SNARK en particular.
Curvas elípticas
Las curvas elípticas forman parte del campo de la criptografía de curvas elípticas. Este es un tema complejo que no es fácil de entender para todos. Para entenderlos mejor, echa un vistazo a mi artículo sobre ECC de la sección anterior.
La criptografía de curva elíptica implica "puntos" en un espacio bidimensional, cada "punto" caracterizado por un par de coordenadas (x, y).
Existen reglas específicas para realizar operaciones matemáticas como suma y resta entre puntos, lo que permite calcular las coordenadas de un nuevo punto cuando se conocen otros puntos.
Ejemplo: Calcular las coordenadas R = P + Q
También puedes multiplicar un punto por un número entero sumando repetidamente el punto a sí mismo tantas veces como ese número entero.
Por ejemplo: P * n = P + P +… + P
Esto proporciona una manera eficiente de realizar operaciones matemáticas en criptografía de curva elíptica
En una curva elíptica, hay un punto especial llamado “punto en el infinito” (O), equivalente a cero en el cálculo de puntos, siempre es cierto que P + O = P.
Una curva también tiene un "orden"; existe un número n tal que P * n = O para todo P ( P * (n+1) = P, P * (7*n + 5) = P * 5, y así sucesivamente).
También hay un "punto generador" (G), que se entiende que representa el número 1 de alguna manera. En teoría, cualquier punto de la curva (excepto O) podría ser G.
Maridajes
Los emparejamientos permiten realizar pruebas de ecuaciones más complejas en puntos de curvas elípticas.
Por ejemplo:
puedes comprobar si p * q es igual a r solo a partir de P, Q y R.
Aunque la información sobre p puede filtrarse desde P, esta fuga se controla cuidadosamente.
Los emparejamientos permiten probar restricciones cuadráticas.
Por ejemplo: Probar e(P, Q) * e(G, G * 5) = 1 es en realidad probar p * q + 5 = 0.
Es una operación matemática llamada emparejamiento. Los matemáticos también lo llaman mapeo bilineal. “Bilineal” aquí cumplirá con las siguientes reglas:
Tenga en cuenta que puede utilizar los operadores + y * de cualquier forma, siempre que cumplan con las siguientes reglas:
y
Si P, Q, R y S son números simples, crear una operación de emparejamiento simple es fácil con la expresión:
Los siguientes resultados:
¡Eso es paralelismo!
Sin embargo, operaciones de emparejamiento tan simples no son adecuadas para la criptografía porque operan con números enteros simples y son demasiado fáciles de analizar.
Una vez que conozca un número y su resultado al realizar la operación de emparejamiento, podrá calcular y encontrar fácilmente el número restante.
Usamos operaciones matemáticas como “cajas negras”, donde solo se pueden realizar operaciones básicas sin mayor análisis o comprensión. Esta es la razón por la que las curvas elípticas y la operación de emparejamiento en curvas elípticas se vuelven importantes en criptografía.
Campos principales y campos de extensión
Es posible crear un mapa bilineal (Bilinear Maps) en puntos de curvas elípticas, es decir, crear una función.
donde P y Q son puntos de curva elíptica y el resultado es un tipo de elemento llamado F_p¹²
Primero, comprendamos los campos primos y los campos de extensión.
La curva elíptica en la imagen de arriba es tan hermosa porque la ecuación de la curva se define usando números reales ordinarios.
Sin embargo, en criptografía, el uso de números reales ordinarios puede llevar al uso de logaritmos para "retroceder" y arruinar las cosas, ya que la cantidad de espacio necesario para almacenar y representar números puede aumentar arbitrariamente. Por lo tanto, utilizamos números en campos primos.
Un campo primo está formado por el conjunto de números 0, 1, 2… p-1, donde p es primo y las distintas operaciones se definen de la siguiente manera:
Todas las operaciones se realizan módulo p
La división es un caso especial; Normalmente, 3/2 no es un número entero y ahora solo quiero tratar con números enteros, así que intento encontrar el número x tal que
x * 2 = 3.
Esto se puede hacer utilizando el algoritmo euclidiano extendido. Por ejemplo, si p = 7, entonces:
A continuación, hablaremos de los campos de extensión.
Un ejemplo común que se encuentra a menudo en los libros de matemáticas es el campo de números complejos, donde el campo de números reales se "extiende" con el elemento adicional sqrt(-1) = i.
Los campos de extensión funcionan tomando un campo existente, luego "agregando" un nuevo elemento y definiendo una relación entre ese nuevo elemento y los elementos que ya están en el campo original (por ejemplo, i² + 1 = 0).
Lo importante es que esta ecuación no es cierta para ningún número en el campo original, y luego considere todas las combinaciones lineales de los elementos en el campo original y el nuevo elemento recién creado.
También podemos ampliar los campos principales.
Por ejemplo, ampliando el campo principal mod 7 que describimos anteriormente con i, podemos hacer lo siguiente:
Si desea ver todos los cálculos realizados en el código, los campos principales y las extensiones de campo se realizan aquí
Emparejamientos de curvas elípticas
El emparejamiento de curvas elípticas es un mecanismo que toma dos puntos de dos curvas elípticas y asigna esos puntos a un solo número.
Puedes pensar en este mapeo como equivalente a multiplicar puntos en una curva elíptica.
Matemáticamente, el emparejamiento de curvas elípticas se define como asignar dos puntos de una curva elíptica a un elemento de otro grupo como un campo finito:
Aquí e es emparejamiento, E1 y E2 son curvas elípticas y 𝐹 es un campo finito.
Tenga en cuenta que las curvas elípticas E1 y E2 no necesitan ser diferentes.
Una vez que se produce la concatenación, el resultado es que un elemento de otro grupo no se puede reutilizar para la siguiente concatenación.
Los pares de curvas elípticas tienen ciertas propiedades llamadas asignaciones bilineales:
Aquí P, Q y R son puntos de la curva elíptica y 𝑎∈𝑍, 𝑏∈𝑍
Usando estos "asignaciones bilineales" podemos "mover" los coeficientes 𝑎 y 𝑏 en esas dos curvas mientras mantenemos la asignación:
Fuente: https://muens.io/elliptic-curve-pairing
Podemos imaginar el emparejamiento de curvas elípticas como un mapeo de G2 x G1 -> Gt, donde:
G1 es una curva elíptica, donde los puntos satisfacen una ecuación de forma
y ambas coordenadas son elementos de F_p (son números simples, pero las operaciones se realizan módulo de un número primo particular)
G2 también es una curva elíptica, donde los puntos satisfacen la misma ecuación que G1, pero sus coordenadas pertenecen al campo F_p¹² (definimos un nuevo “número mágico” w, definido por un polinomio de grado 12 como:
Gt es el tipo de objeto al que va el resultado de la curva elíptica. En las curvas que consideramos, Gt es F_p¹² (el mismo número complejo fuerte que se usa en G2)
Aquí debe satisfacer la bilinealidad:
Junto con otros dos criterios importantes:
Computabilidad eficiente: La computabilidad eficiente significa poder calcular operaciones compuestas rápidamente y sin demasiada complejidad. Por ejemplo, si simplemente tomamos el logaritmo discreto de los puntos y los multiplicamos para crear una concatenación, esto sería computacionalmente demasiado difícil. al igual que romper el cifrado de curva elíptica original. Por lo tanto, una operación compuesta se considera computacionalmente eficiente si se puede calcular de manera eficiente sin imponer demasiada carga computacional.
No degeneración: La no degeneración garantiza que la concatenación no sea una concatenación inútil, es decir, que no devuelva simplemente un valor fijo independiente de los puntos de entrada. Por ejemplo: si pretendemos que el significado compuesto sea e(P, Q) = 1. para todos P y Q, lo que no proporciona ninguna información útil sobre la relación entre puntos en la curva elíptica. Por lo tanto, una concatenación se considera no degenerativa si proporciona información útil sobre la relación entre los puntos de entrada.
Entonces, ¿cómo hacer eso?
Primero, debemos entender el concepto de divisor, otra forma de representar una función sobre puntos en una curva elíptica.
Un divisor de una función esencialmente cuenta los ceros y los números infinitos de la función. Para entender lo que esto significa, veamos algunos ejemplos. Arreglemos algunos puntos P = (P_x, P_y) y consideremos la siguiente función:
El divisor là [P] + [-P] – 2 * [O]
[P] + [Q] no es lo mismo que [P + Q]. Las razones son las siguientes:
La función es cero en P porque cuando x es P_x, entonces x – P_x = 0.
La función es 0 en -P porque -P y P tienen la misma coordenada x.
La función llega al infinito cuando x tiende al infinito, por lo que decimos que la función es infinita en O.
La razón está en la ecuación de la curva elíptica:
y crece hasta el infinito aproximadamente "1,5 veces" más rápido que x para poder seguir el ritmo de x^3. Por lo tanto, si una función lineal tiene solo x, se representará como infinito con multiplicidad de 2, pero si tiene y, se representará como infinito con multiplicidad de 3.
Ahora, considere una “función de línea”:
Donde a, b y c se eligen cuidadosamente para que la línea pase por los puntos P y Q en la curva elíptica.
Debido a la forma en que funciona la suma en una curva elíptica, esto también significa que pasa por el punto -P-Q. Esta función también llega al infinito dependiendo tanto de x como de y, dividiendo así las posibilidades
Cada “función racional” (una función definida usando solo un número finito de operaciones +, -, *, / en las coordenadas de un punto) corresponde únicamente a un divisor, sujeto a la condición de multiplicar por una constante (es decir, si dos funciones F y G tienen el mismo divisor, entonces F = G * k donde k es una constante).
La división del producto de dos funciones es igual a la suma de las divisiones de cada función, entonces
entonces
Fuente del artículo: Team Tech/Research Alphatrue
Fuente de referencia:
https://medium.com/@VitalikButerin/explorando-eliptic-curve-pairings-c73c1864e627