Explorando Circle STARKs

En los últimos años, la tendencia en el diseño de protocolos STARKs ha sido hacia el uso de campos más pequeños. Las primeras implementaciones de producción de STARKs utilizaban campos de 256 bits, es decir, realizaban operaciones modulares sobre grandes números, lo que hacía que estos protocolos fueran compatibles con firmas basadas en curvas elípticas. Sin embargo, la eficiencia de este diseño es relativamente baja; en general, procesar cálculos 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 usar 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 Poseidon2 por segundo en una computadora portátil M3. Esto significa que, siempre que estemos dispuestos a confiar en Poseidon2 como función hash, se puede resolver el problema de desarrollar un ZK-EVM eficiente. ¿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, con un enfoque especial 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, una técnica muy importante es demostrar a través de los resultados de la evaluación del polinomio en puntos aleatorios, lo que puede validar indirectamente las propiedades del polinomio. Este método puede simplificar considerablemente el proceso de prueba, ya que la evaluación en puntos aleatorios suele ser mucho más fácil que manejar el polinomio completo.

Para prevenir ataques, necesitamos elegir r después de que el atacante haya proporcionado A. Fiat-Shamir es una técnica utilizada para mejorar la seguridad del protocolo, evitando ataques al establecer ciertos parámetros como un valor hash. Los parámetros elegidos deben provenir de un conjunto lo suficientemente grande para asegurar que el atacante no pueda predecir o adivinar estos parámetros, aumentando así la seguridad del sistema.

En protocolos basados en curvas elípticas y en STARKs de la época de 2019, el 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 STARKs sobre campos más pequeños, nos encontramos con un problema: solo hay alrededor de 2 mil millones de posibles valores para r que se pueden elegir, por lo que un atacante que desee falsificar una prueba solo necesita intentar 2 mil millones de veces; aunque la carga de trabajo es grande, para un atacante decidido, ¡es completamente 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 hay problemas de eficiencia. Si estás tratando con un polinomio de grado menor que un cierto valor y operando en un dominio de cierto tamaño, un atacante puede construir un polinomio malicioso que en realidad parece normal en estas posiciones. Por lo tanto, si pueden o no comprometer con éxito el protocolo es un problema probabilístico, por lo que es necesario aumentar el número de verificaciones para mejorar la seguridad general y asegurarse de que se pueden defender eficazmente contra los ataques del atacante.

Esto da lugar a otra solución: el campo extendido, que es similar a los números complejos, pero se basa en campos finitos. Introducimos un nuevo valor, denotado como α, y declaramos que satisface cierta relación, como α2=un valor determinado. De esta manera, creamos una nueva estructura matemática capaz de realizar operaciones más complejas sobre campos finitos. En este campo extendido, el cálculo de la multiplicación se convierte en una multiplicación utilizando el nuevo valor α. Ahora podemos operar con pares de valores en el campo extendido, en lugar de solo números individuales. Por ejemplo, si estamos trabajando en campos como Mersenne o BabyBear, tal expansión nos permite tener más opciones de valores, aumentando 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 expresa como seleccionar α de manera que α2=un valor determinado.

A través de dominios extendidos, 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 añadir algo de trabajo computacional adicional en el protocolo para mejorar la seguridad.

El dominio extendido se utiliza en la práctica solo en el protocolo FRI y en otros escenarios que requieren combinaciones lineales aleatorias. La mayor parte de las operaciones matemáticas aún se realizan sobre el campo base, que generalmente son campos módulo p o q. Al mismo tiempo, casi todos los datos hash se realizan sobre el campo base, por lo tanto, cada valor solo necesita ser hash de cuatro bytes. Esto permite aprovechar la eficiencia de los campos pequeños, mientras que cuando se requiere un aumento de seguridad, se pueden utilizar campos más grandes.

FRI Regular

Al construir un SNARK o STARK, el primer paso suele ser la aritmetización. Esto implica transformar un problema de cálculo arbitrario en una ecuación en la que algunas variables y coeficientes son polinomios. En concreto, esta ecuación suele parecerse a 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 demostrar que el valor que propones es efectivamente un polinomio razonable (y no una fracción, o que en algunos lugares parece ser un polinomio y en otros es un polinomio diferente, etc.), y que estos polinomios tienen un cierto grado máximo. 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 pares de A, y C aísla los coeficientes impares. Dado B y C, puedes recuperar el polinomio original A: A(x) = B(x^2) + xC(x^2). Si el grado de A es realmente 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 probar que el grado del polinomio es d al problema de probar que el grado del polinomio es d/2. Este proceso se puede repetir varias veces, reduciendo el problema a la mitad cada vez.

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, finalmente demostrarás que el polinomio tiene un grado de 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 un grado de d mediante esta técnica, entonces en la segunda salida, su grado tendrá una cierta probabilidad de no cumplir con lo esperado, en la tercera ronda será aún más probable que no cumpla, y la verificación final fallará. Este diseño puede detectar y rechazar de manera efectiva las 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 un conjunto de datos así, 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".

Entendamos más detalladamente lo que está sucediendo aquí y las propiedades necesarias para que todo funcione correctamente. En cada paso, reducimos el grado del polinomio a la mitad, al mismo tiempo que también reducimos a la mitad el conjunto de puntos (el conjunto de puntos que nos interesa). Lo primero es clave para que el protocolo FRI funcione correctamente. Lo segundo permite que el algoritmo funcione a gran velocidad: como 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 una reducción gradual del dominio, se utilizó una asignación de dos a uno, es decir, cada punto se asigna a uno de dos puntos. Esta asignación nos permite reducir el tamaño del conjunto de datos a la mitad. Una ventaja importante de esta asignación de dos a uno es que es repetible. Esto significa que, cuando aplicamos esta asignación, 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 aplicamos la operación de elevar al cuadrado al conjunto S (es decir, asignar a cada elemento x del conjunto 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, a menudo se detiene antes de llegar a un conjunto más pequeño.

Puedes imaginar esta operación como un proceso que extiende una línea (por ejemplo, un segmento o un arco) a lo largo de la circunferencia, haciendo que gire dos veces alrededor de la circunferencia. Por ejemplo, si un punto en la circunferencia está en la posición x grados, entonces después de esta operación, se moverá a la posición 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 se superponen. Esto significa que cuando mapeas un punto de x grados a 2x grados, se superpondrá con uno que está en la posición 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 en la circunferencia a sus nuevas posiciones.

Para que la técnica de mapeo sea efectiva, el tamaño del subgrupo de multiplicación original necesita tener un gran poder 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 de multiplicación máximo contiene todos los valores no cero, por lo tanto, 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 al final verificar el grado del polinomio. Este método aprovecha las propiedades del módulo y el tamaño del subgrupo de multiplicación, 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 de multiplicación es 2^31 - 1. En este caso, el tamaño del subgrupo de multiplicación solo tiene un poder de 2 como factor, lo que significa que solo puede ser dividido por 2 una vez. El tratamiento posterior ya no se aplica a la técnica mencionada, es decir, no se puede usar FFT para reducir de manera efectiva el 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 llevar a cabo utilizando operaciones de bits eficientes: si la suma de dos números excede el módulo, se puede reducir a un rango apropiado desplazando el resultado con el módulo. La operación de desplazamiento es un cálculo muy eficiente. En la multiplicación, se pueden utilizar instrucciones específicas de la CPU (generalmente conocidas como instrucciones de desplazamiento de bits altos) para manejar el resultado. Estas instrucciones pueden calcular de manera eficiente la parte alta de la multiplicación, mejorando así la eficiencia del cálculo. En el campo Mersenne31, debido a las características mencionadas, las operaciones aritméticas son aproximadamente 1.3 veces más rápidas que en el campo BabyBear. Mersenne31 proporciona una mayor eficiencia computacional. Si se puede implementar FRI en el campo Mersenne31, esto mejorará significativamente la eficiencia computacional, haciendo que la respuesta de FRI sea.