Explorando Circle STARKs

En los últimos años, la tendencia en el diseño del protocolo STARKs ha sido hacia el uso de campos más pequeños. Las primeras implementaciones de producción de STARKs utilizaban un campo de 256 bits, lo que implicaba la operación modular de grandes números, haciendo que estos protocolos fueran compatibles con las firmas basadas en curvas elípticas. Sin embargo, la eficiencia de este diseño es relativamente baja, ya que, en general, el procesamiento de estos grandes números no tiene un uso práctico y desperdicia mucha potencia de cálculo. Para resolver este problema, STARKs comenzó a utilizar campos más pequeños: primero Goldilocks, luego Mersenne31 y BabyBear.

Esta transformación ha mejorado la velocidad de prueba, por ejemplo, Starkware puede probar 620,000 valores hash de Poseidon2 por segundo en una computadora portátil M3. Esto significa que, siempre que estemos dispuestos a confiar en Poseidon2 como función hash, podemos resolver el desafío de desarrollar un ZK-EVM eficiente. Entonces, ¿cómo funcionan estas tecnologías? ¿Cómo se establecen estas pruebas en campos más pequeños? ¿Cómo se comparan estos protocolos con soluciones como Binius? Este artículo explorará estos detalles, centrándose especialmente en una solución llamada Circle STARKs, que tiene propiedades únicas compatibles con el campo Mersenne31.

Problemas comunes al usar campos matemáticos más pequeños

Al crear pruebas basadas en hash ( o cualquier tipo de prueba ), una técnica muy importante es probar mediante los resultados de la evaluación de un polinomio en puntos aleatorios, lo que permite validar indirectamente las propiedades del polinomio. Este método puede simplificar enormemente el proceso de prueba, ya que la evaluación en puntos aleatorios suele ser mucho más fácil que manejar todo el polinomio.

Por ejemplo, supongamos que un sistema de prueba requiere que generes un compromiso para un polinomio, A, que debe satisfacer A^3(x) + x - A(ωx) = x^N(. Este es un tipo de prueba muy común en el protocolo ZK-SNARK ). El protocolo puede requerir que elijas una coordenada aleatoria r y demuestres que A(r) + r - A(ωr) = r^N. Luego, deduces que A(r) = c, has demostrado que Q = (A - c)/(X - r) es un polinomio.

Para prevenir ataques, necesitamos elegir r después de que el atacante haya proporcionado A. Los parámetros seleccionados deben provenir de un conjunto lo suficientemente grande para asegurar que el atacante no pueda predecir o adivinar estos parámetros, lo que aumenta la seguridad del sistema.

En los protocolos basados en curvas elípticas y en los STARKs de 2019, este problema es bastante simple: todas nuestras operaciones matemáticas se realizan sobre números de 256 bits, por lo que podemos elegir r como un número aleatorio de 256 bits, y eso es todo. Sin embargo, en los STARKs sobre campos más pequeños, nos encontramos con un problema: solo hay aproximadamente 2 mil millones de posibles valores de r para elegir, por lo que un atacante que quiera falsificar una prueba solo necesita intentarlo 2 mil millones de veces; aunque la carga de trabajo es considerable, ¡para un atacante decidido, sigue siendo totalmente factible!

Este problema tiene dos soluciones:

• Realizar múltiples inspecciones aleatorias
• Campo de extensión

El método de realizar múltiples verificaciones aleatorias es el más simple y efectivo: en lugar de verificar en una coordenada, es mejor repetir la verificación en cuatro coordenadas aleatorias. Esto es teóricamente factible, pero existen problemas de eficiencia. Si estás tratando con un polinomio de grado menor que cierto valor y operando en un dominio de cierto tamaño, el atacante puede construir un polinomio malicioso que parece normal en esas posiciones. Por lo tanto, si pueden o no comprometer el protocolo es un problema probabilístico, y se necesita aumentar el número de verificaciones para mejorar la seguridad general y garantizar que se pueda defender eficazmente contra los ataques de los atacantes.

Esto da lugar a otra solución: el cuerpo extendido, que es similar a los números complejos, pero se basa en cuerpos finitos. Introducimos un nuevo valor, denotado como α, y declaramos que satisface cierta relación, por ejemplo, α^2=some value. De esta manera, creamos una nueva estructura matemática que permite realizar cálculos más complejos sobre cuerpos finitos. En este cuerpo extendido, el cálculo de la multiplicación se convierte en la multiplicación utilizando el nuevo valor α. Ahora podemos operar con pares de valores en el cuerpo extendido, y no solo con números individuales. Por ejemplo, si estamos trabajando en campos como Mersenne o BabyBear, tal extensión nos permite tener más opciones de valores, mejorando así la seguridad. Para aumentar aún más el tamaño del campo, podemos aplicar la misma técnica repetidamente. Dado que ya hemos utilizado α, necesitamos definir un nuevo valor, lo que en Mersenne31 se traduce en elegir α de modo que α^2=some value.

A través de la expansión del dominio, ahora tenemos suficientes valores para elegir, que satisfacen nuestras necesidades de seguridad. Si se trata de un polinomio de grado menor que d, cada ronda puede proporcionar 104 bits de seguridad. Esto significa que tenemos suficiente protección de seguridad. Si se necesita alcanzar un nivel de seguridad más alto, como 128 bits, podemos agregar un trabajo computacional adicional en el protocolo para mejorar la seguridad.

El dominio extendido se utiliza en la práctica solo en el protocolo FRI(Fast Reed-Solomon Interactive) y en otros escenarios que requieren combinaciones lineales aleatorias. La mayoría de las operaciones matemáticas aún se realizan sobre campos básicos, que suelen ser campos módulo p o q. Al mismo tiempo, casi todos los datos de hash se realizan sobre campos básicos, por lo que cada valor solo necesita un hash de cuatro bytes. Esto permite aprovechar la eficiencia de los campos pequeños, mientras que en situaciones que requieren un aumento de seguridad, se pueden usar campos más grandes.

FRI Regular

Al construir un SNARK o STARK, el primer paso suele ser la aritmética. Esto implica convertir un problema de cálculo arbitrario en una ecuación, donde algunas variables y coeficientes son polinomios. En concreto, esta ecuación suele verse como P(X,Y,Z)=0, donde P es un polinomio, X, Y y Z son parámetros dados, y el solucionador necesita proporcionar los valores de X e Y. Una vez que se tiene tal ecuación, la solución de la ecuación corresponde a la solución del problema de cálculo subyacente.

Para demostrar que tienes una solución, necesitas probar que el valor que propones es efectivamente un polinomio razonable ( y no una fracción, o que en algunos lugares parece un polinomio, mientras que en otros lugares es un polinomio diferente, etc. ), y que estos polinomios tienen un grado máximo determinado. Para ello, utilizamos una técnica de combinación lineal aleatoria aplicada de manera gradual:

• Supongamos que tienes un valor de evaluación de un polinomio A, quieres demostrar que su grado es menor que 2^20
• Considera el polinomio B(x^2) = A(x) + A(-x), C(x^2) = (A(x) - A(-x))/x
• D es una combinación lineal aleatoria de B y C, es decir, D=B+rC, donde r es un coeficiente aleatorio.

Esencialmente, lo que sucede es que B aísla los coeficientes de grado par A, y C aísla los coeficientes de grado impar. Dado B y C, puedes recuperar el polinomio original A: A(x) = B(x^2) + xC(x^2). Si el grado de A es de hecho menor que 2^20, entonces los grados de B y C serán respectivamente el grado de A y el grado de A menos 1. Porque la combinación de términos de grado par e impar no aumentará el grado. Dado que D es una combinación lineal aleatoria de B y C, el grado de D también debería ser el grado de A, lo que te permite verificar si el grado de A cumple con los requisitos a través del grado de D.

Primero, FRI simplifica el proceso de verificación al reducir el problema de demostrar que el grado del polinomio es d al problema de demostrar que el grado del polinomio es d/2. Este proceso se puede repetir varias veces, reduciendo el problema a la mitad en cada ocasión.

El funcionamiento de FRI es repetir este proceso de simplificación. Por ejemplo, si comienzas con un polinomio de grado d, a través de una serie de pasos, eventualmente demostrarás que el grado del polinomio es d/2. Después de cada simplificación, el grado del polinomio generado disminuye gradualmente. Si la salida en alguna etapa no es el grado de polinomio esperado, entonces esta ronda de verificación fallará. Si alguien intenta empujar un polinomio que no tiene grado d utilizando esta técnica, entonces en la segunda salida, es probable que su grado no cumpla con lo esperado, y en la tercera ronda, será aún más probable que aparezca un resultado no conforme, lo que llevará a que la verificación final falle. Este diseño puede detectar y rechazar efectivamente entradas que no cumplen con los requisitos. Si el conjunto de datos es igual a un polinomio de grado d en la mayoría de las posiciones, es posible que este conjunto de datos pase la verificación de FRI. Sin embargo, para construir tal conjunto de datos, el atacante necesita conocer el polinomio real, por lo que incluso una prueba con ligeras fallas indica que el probador puede generar una prueba 'real'.

Conozcamos con más detalle lo que está sucediendo aquí y las propiedades necesarias para que todo esto funcione correctamente. En cada paso, reducimos a la mitad el grado del polinomio, al mismo tiempo que también reducimos a la mitad el conjunto de puntos (, el conjunto de puntos que nos interesa ). El primero es clave para que el protocolo FRI( Fast Reed-Solomon Interactive) funcione adecuadamente. El segundo permite que el algoritmo funcione a gran velocidad: dado que el tamaño de cada ronda se reduce a la mitad en comparación con la ronda anterior, el costo total de cálculo es O(N), en lugar de O(N*log(N)).

Para lograr la reducción gradual del dominio, se utilizó un mapeo de dos a uno, es decir, cada punto se mapea a uno de dos puntos. Este mapeo permite reducir el tamaño del conjunto de datos a la mitad. Una ventaja importante de este mapeo de dos a uno es que es reproducible. Es decir, cuando aplicamos este mapeo, el conjunto de resultados obtenido aún conserva las mismas propiedades. Supongamos que comenzamos con un subgrupo multiplicativo (. Este subgrupo es un conjunto S, donde cada elemento x tiene su múltiplo 2x también en el conjunto. Si realizamos la operación de cuadrado sobre el conjunto S ), es decir, mapeando cada elemento x del conjunto a x^2(, el nuevo conjunto S^2 también conservará las mismas propiedades. Esta operación nos permite seguir reduciendo el tamaño del conjunto de datos hasta que finalmente quede solo un valor. Aunque teóricamente podemos reducir el conjunto de datos hasta que quede un solo valor, en la práctica, generalmente se detiene antes de alcanzar un conjunto más pequeño.

Puedes imaginar esta operación como un proceso en el que una línea en la circunferencia, ), por ejemplo, un segmento o arco, ( se extiende a lo largo de la circunferencia, haciendo que gire dos veces alrededor de la circunferencia. Por ejemplo, si un punto está en la posición de x grados en la circunferencia, después de esta operación, se moverá a la posición de 2x grados. Cada punto en la circunferencia desde 0 hasta 179 grados tiene un punto correspondiente en la posición de 180 a 359 grados, y estos dos puntos coinciden. Esto significa que cuando mapeas un punto de x grados a 2x grados, coincidirá con uno que está en la posición de x + 180 grados. Este proceso se puede repetir. Es decir, puedes aplicar esta operación de mapeo múltiples veces, moviendo cada vez los puntos de la circunferencia a sus nuevas posiciones.

![Vitalik nueva obra: Explorando Circle STARKs])https://img-cdn.gateio.im/webp-social/moments-4e2ceec842bcdcc68f5efb0e9ec2d6ab.webp(

Para que la técnica de mapeo sea efectiva, el tamaño del subgrupo multiplicativo original necesita tener una gran potencia de 2 como factor. BabyBear es un sistema con un módulo específico, cuyo módulo es un cierto valor, de modo que su subgrupo multiplicativo máximo contiene todos los valores no nulos, por lo que el tamaño del subgrupo es 2k−1) donde k es el número de bits del módulo (. Este tamaño de subgrupo es muy adecuado para la técnica mencionada, ya que permite reducir de manera efectiva el grado del polinomio mediante la aplicación repetida de la operación de mapeo. En BabyBear, puedes elegir un subgrupo de tamaño 2^k ) o usar directamente todo el conjunto (, y luego aplicar el método FRI para reducir gradualmente el grado del polinomio a 15, y finalmente verificar el grado del polinomio. Este método aprovecha las propiedades del módulo y el tamaño del subgrupo multiplicativo, lo que hace que el proceso de cálculo sea muy eficiente. Mersenne31 es otro sistema, cuyo módulo es un cierto valor, de modo que el tamaño del subgrupo multiplicativo es 2^31 - 1. En este caso, el tamaño del subgrupo multiplicativo solo tiene una potencia de 2 como factor, lo que significa que solo puede ser dividido por 2 una vez. El procesamiento posterior ya no es aplicable a la técnica mencionada, es decir, no se puede usar FFT para una reducción efectiva del grado del polinomio como en BabyBear.

El campo Mersenne31 es muy adecuado para realizar operaciones aritméticas en las operaciones existentes de CPU/GPU de 32 bits. Debido a las características de su módulo ), por ejemplo, 2^31 - 1(, muchas operaciones se pueden completar utilizando operaciones de bits eficientes: si la suma de dos números excede el módulo, se puede realizar un bit