- Tema
82k Popularidad
37k Popularidad
12k Popularidad
4k Popularidad
4k Popularidad
30k Popularidad
16k Popularidad
23k Popularidad
13k Popularidad
3k Popularidad
- Anclado
82k Popularidad
37k Popularidad
12k Popularidad
4k Popularidad
4k Popularidad
30k Popularidad
16k Popularidad
23k Popularidad
13k Popularidad
3k Popularidad
Circle STARKs: pruebas zk-SNARKs eficientes sobre campos pequeños
Explorando Circle STARKs
En los últimos años, el diseño del protocolo STARKs tiende a utilizar campos más pequeños. Las primeras implementaciones de STARKs usaban campos de 256 bits, realizando operaciones de módulo con números grandes, siendo compatibles con firmas basadas en curvas elípticas. Sin embargo, este diseño es menos eficiente y desperdicia poder de cálculo al procesar grandes números. Para resolver este problema, STARKs comenzó a usar campos más pequeños: Goldilocks, 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 laptop M3. Siempre que se confíe en Poseidon2 como función hash, se puede resolver el problema del desarrollo eficiente de ZK-EVM. ¿Cómo funcionan estas tecnologías? ¿Cómo se establece la prueba en campos pequeños? Este artículo explorará estos detalles, con un enfoque especial en el esquema Circle STARKs.
Preguntas frecuentes sobre el uso de campos pequeños
Al crear una prueba basada en hash, un truco importante es validar indirectamente las propiedades del polinomio a través de la evaluación del polinomio en puntos aleatorios. Esto simplifica enormemente el proceso de prueba.
Por ejemplo, supongamos que se quiere demostrar que el polinomio A satisface A^3(x) + x - A(ωx) = x^N. El protocolo puede requerir seleccionar coordenadas aleatorias r y demostrar A(r) + r - A(ωr) = r^N. Luego, se deduce A(r) = c, y se prueba que Q = (A - c)/(X - r) es un polinomio.
Para prevenir ataques, es necesario seleccionar r después de que el atacante proporcione A. En un campo de 256 bits, es muy sencillo: simplemente selecciona un número aleatorio de 256 bits. Pero en campos pequeños, el valor de r disponible es solo de aproximadamente 2 mil millones, lo que significa que, aunque el trabajo del atacante sea considerable, todavía podría intentar todas las posibilidades.
Hay dos soluciones:
Las verificaciones múltiples son simples y efectivas, pero existen problemas de eficiencia. Los campos extendidos son similares a los plurales, pero se basan en un campo finito. Se introduce un nuevo valor α que satisface cierta relación, como α^2 = cierto valor. Esto crea una nueva estructura matemática que permite realizar operaciones más complejas sobre campos finitos. El campo extendido se utiliza solo cuando se necesitan combinaciones lineales aleatorias; la mayoría de las operaciones aún se realizan en el campo base.
FRI Regular
El primer paso para construir un SNARK o STARK es transformar el problema de cálculo en la ecuación polinómica P(X,Y,Z)=0. La solución debe demostrar que el valor propuesto es un polinomio razonable y de grado limitado. Esto se logra aplicando combinaciones lineales aleatorias de manera gradual:
B aisla los coeficientes pares de A, C aisla los coeficientes impares. Dado B y C, se puede recuperar A: A(x) = B(x^2) + xC(x^2). Si el grado de A es < 2^20, los grados de B y C son respectivamente el grado de A y el grado de A - 1. D, como combinación aleatoria, debe tener el grado del grado de A.
FRI simplifica la verificación al reducir la prueba del grado de polinomio d a una prueba del grado d/2. Este proceso se puede repetir varias veces, cada vez reduciendo el problema a la mitad. Si la salida en alguna etapa no cumple con el grado esperado, esa ronda de verificación fallará.
FRI reduce a la mitad el grado del polinomio y el tamaño del conjunto de puntos en cada paso. El primero es clave para el funcionamiento de FRI, y el segundo hace que el algoritmo se ejecute muy rápido: 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 utiliza un mapeo de dos a uno. Este mapeo permite reducir a la mitad el tamaño del conjunto de datos y es repetible. Comenzando con el subgrupo multiplicativo, el múltiplo 2x de cada elemento x también está en el conjunto. Al elevar al cuadrado el conjunto S, el nuevo conjunto S^2 conserva la misma propiedad. Esto permite seguir reduciendo el tamaño del conjunto de datos hasta que quede solo un valor.
El módulo de BabyBear hace que su máximo subgrupo multiplicativo contenga todos los valores no cero, con un tamaño de 2^k-1. Esto es muy adecuado para la técnica mencionada, ya que se puede reducir efectivamente el grado del polinomio mediante la aplicación repetida de mapeo. El tamaño del subgrupo multiplicativo de Mersenne31 es de 2^31-1, y solo se puede dividir por 2 una vez, después de lo cual esta técnica no se puede utilizar.
El campo Mersenne31 es muy adecuado para cálculos en CPU/GPU de 32 bits. Su característica de módulo ( como 2^31-1) permite que muchas operaciones se realicen utilizando operaciones de bits eficientes: los resultados que superan el módulo pueden reducirse mediante desplazamiento. La multiplicación se puede manejar de manera eficiente con instrucciones específicas de CPU. Las operaciones aritméticas de Mersenne31 son aproximadamente 1.3 veces más rápidas que BabyBear. Si se puede implementar FRI en Mersenne31, se mejorará significativamente la eficiencia.
Circle FRI
La genialidad de Circle STARKs radica en que, dado un número primo p, se puede encontrar un grupo del tamaño de p que tiene una propiedad similar a la de una relación de dos a uno. Este grupo está compuesto por puntos que satisfacen condiciones específicas, como el conjunto de puntos donde x^2 mod p es igual a un cierto valor.
Estos puntos siguen la regla de la adición: (x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1) Forma doble: 2*(x,y) = (2x^2 - 1, 2xy)
Nos enfocamos en los puntos en posiciones impares en el círculo. Primero, convergemos todos los puntos en una línea recta: f0(x) = (F(x,y) + F(x,-y))/2
Luego se realiza una combinación lineal aleatoria, obteniendo un polinomio unidimensional P(x).
A partir de la segunda ronda, el mapeo se convierte en: f0(2x^2-1) = (F(x) + F(-x))/2
Este mapeo reduce el tamaño del conjunto a la mitad cada vez. Cada x representa dos puntos: (x,y) y (x,-y). (x → 2x^2 - 1) es la regla de duplicación de puntos. Convertimos las coordenadas x de dos puntos opuestos en el círculo a las coordenadas x del punto duplicado.
FFTs circulares
El grupo Circle también soporta FFT, y su método de construcción es similar al de FRI. La diferencia clave es que el FFT de Circle no procesa polinomios estrictos, sino espacios de Riemann-Roch: polinomios módulo (x^2 + y^2 - 1 = 0).
Los coeficientes de salida de Circle FFT son bases específicas: {1, y, x, xy, 2x^2 - 1, 2x^2y - y, 2x^3 - x, 2x^3y - xy, 8x^4 - 8x^2 + 1...}
Los desarrolladores casi pueden ignorar este punto. Los STARKs solo necesitan almacenar un conjunto de evaluaciones de polinomios. FFT se utiliza solo para la expansión de bajo grado: dado N valores, genera k*N valores en el mismo polinomio.
Operación comercial
Una operación común de STARK es realizar operaciones de comercio sobre puntos específicos. Por ejemplo, probar que P(x)=y se puede hacer a través de los siguientes pasos:
En el grupo STARK de Circle, debido a la falta de una función lineal puntual, se requieren diferentes técnicas. Se puede construir una función tangente, pero tiene un multiplicidad de 2 en el punto. Por lo tanto, debe evaluarse en dos puntos para demostrarlo.
Si P es igual a y1 en x1 y igual a y2 en x2, elegimos la función de interpolación L que es igual en estos dos puntos. Luego demostramos que P-L es cero en estos dos puntos, y al dividir L por L demostramos que el cociente Q es un polinomio.
Polinomio desaparecido
Las ecuaciones polinómicas que STARK intenta probar suelen tener la forma C(P(x), P(next(x))) = Z(x) · H(x), Z(x) es idéntico a cero en el dominio de evaluación original.
En STARK circular, la función correspondiente es: Z1(x,y) = y Z2(x,y) = x Zn+1(x,y) = (2 * Zn(x,y)^2) - 1
Orden inverso
La evaluación de polinomios en STARKs generalmente se organiza en orden inverso de bits. En los STARKs de círculo, la estructura de plegado es ligeramente diferente:
Para ajustar el orden inverso, se debe invertir cada uno de los dígitos excepto el último, utilizando el último dígito para decidir si se deben voltear los otros.
Eficiencia
Circle STARKs es muy eficiente. Los cálculos suelen involucrar:
La clave de la eficiencia radica en aprovechar al máximo el espacio de seguimiento computacional. Aquí el tamaño del campo es de 2^31, el desperdicio de espacio no es grande. Los hashes como Poseidon aprovechan al máximo cada bit de cada número en cualquier campo.
Binius logra un empaquetado de bits más eficiente al mezclar campos de diferentes tamaños, pero el costo es un concepto más complejo. Circle STARKs es conceptualmente relativamente simple.
Conclusión
Circle STARKs no son más complejos para los desarrolladores que los STARKs. La principal diferencia en la implementación con respecto al FRI convencional radica en las tres cuestiones mencionadas anteriormente. A pesar de que la matemática detrás es compleja, esta complejidad está bien oculta.
Entender Circle FRI y FFTs puede ser un camino para entender otros FFTs especiales, como los FFTs de campo binario y los FFTs de curvas elípticas.
Combinando tecnologías como Mersenne31, BabyBear y Binius, nos estamos acercando al límite de eficiencia de la capa base de STARKs. Las futuras optimizaciones pueden centrarse en: