- Tema
84k Popularidad
38k Popularidad
11k Popularidad
5k Popularidad
30k Popularidad
16k Popularidad
23k Popularidad
13k Popularidad
3k Popularidad
13k Popularidad
- Anclado
84k Popularidad
38k Popularidad
11k Popularidad
5k Popularidad
30k Popularidad
16k Popularidad
23k Popularidad
13k Popularidad
3k Popularidad
13k Popularidad
Circle STARKs: explorando nuevas formas de pruebas ZK eficientes
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 utilizaban campos de 256 bits, compatibles con firmas basadas en curvas elípticas. Sin embargo, este diseño tiene una eficiencia baja y el procesamiento de números grandes desperdicia potencia de cálculo. Para resolver este problema, STARKs ha comenzado a adoptar 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 laptop M3. Siempre que confiemos 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? Este artículo explorará estos detalles, con un enfoque especial en el esquema de Circle STARKs.
Problemas comunes al usar campos matemáticos más pequeños
Al crear pruebas basadas en hash, un truco importante es demostrar los resultados de la evaluación de un polinomio en puntos aleatorios, verificando indirectamente las propiedades del polinomio. Esto puede simplificar enormemente el proceso de prueba.
Por ejemplo, supongamos que se requiere generar el compromiso del polinomio A, debe cumplir 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 puede deducir A(r) = c, demostrando que Q = (A - c)/(X - r) es un polinomio.
Para prevenir ataques, es necesario elegir r después de que el atacante proporcione A. En los protocolos basados en curvas elípticas, se puede elegir un número aleatorio de 256 bits. Pero en los STARKs de campos más pequeños, solo hay alrededor de 2 mil millones de valores de r disponibles, y el atacante podría romperlo mediante fuerza bruta.
Hay dos soluciones:
Las verificaciones aleatorias múltiples son simples y efectivas, pero presentan problemas de eficiencia. El campo ampliado es similar a los números complejos, pero se basa en un campo finito. Se introduce un nuevo valor α, declarando que α^2 = cierto valor. De esta manera, se pueden realizar operaciones más complejas en un campo finito. El campo ampliado solo se utiliza en escenarios como el protocolo FRI, la mayoría de las operaciones matemáticas aún se realizan en el campo base.
FRI regular
Al construir un SNARK o STARK, el primer paso es la aritmética, que convierte el problema computacional en una ecuación polinómica. Para probar que tiene solución, es necesario demostrar que los valores propuestos son polinomios razonables y tienen un grado máximo. Para ello se utiliza la técnica de combinación lineal aleatoria aplicada de manera gradual:
Esencialmente, B aísla coeficientes pares, y C aísla coeficientes impares. Dados B y C, se puede recuperar A. 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 lineal aleatoria, debe tener un grado igual al grado de A.
FRI simplifica el proceso de verificación al reducir el problema de demostrar un polinomio de grado d a demostrar un polinomio de grado d/2. Este proceso se puede repetir varias veces, reduciendo el problema a la mitad en cada ocasión.
Para lograr la reducción progresiva del dominio, se utiliza un mapeo uno a uno. Este mapeo permite reducir a la mitad el tamaño del conjunto de datos y es repetible. Comenzando con un subgrupo multiplicativo, se aplica la operación de cuadrado al conjunto S, el nuevo conjunto S^2 conserva la misma propiedad. Esto permite reducir continuamente el tamaño del conjunto de datos hasta que finalmente quede solo un valor.
El módulo BabyBear hace que su subgrupo multiplicativo máximo contenga todos los valores no cero, y el tamaño del subgrupo es 2k-1. Se puede elegir un subgrupo de tamaño 2^k, y luego aplicar el método FRI para reducir gradualmente el grado del polinomio a 15. El módulo Mersenne31 hace que el tamaño del subgrupo multiplicativo sea 2^31-1, que solo puede ser dividido por 2 una vez, y después no se pueden usar las técnicas mencionadas anteriormente.
El campo Mersenne31 es adecuado para cálculos en CPU/GPU de 32 bits. Su característica de módulo permite que muchas operaciones se realicen utilizando operaciones de bits eficientes. En el campo Mersenne31, las operaciones aritméticas son aproximadamente 1.3 veces más rápidas que en el campo BabyBear. Si se puede implementar FRI en el campo Mersenne31, se mejorará significativamente la eficiencia de cálculo.
Circle FRI
La astucia de Circle STARKs radica en que, dado un primo p, se puede encontrar un grupo de tamaño p que tiene una propiedad similar a la de uno a dos. Este grupo está compuesto por puntos que satisfacen ciertas condiciones, 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)
La forma doble es: 2 * (x,y) = (2x^2 - 1, 2xy)
Nos enfocamos en los puntos en posiciones impares en el círculo. Primero, hacemos que todos los puntos converjan 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
Esta asignación 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.
FFTs Circulares
El grupo Circle también soporta FFT, la forma de construcción es similar a FRI. El objeto que procesa Circle FFT es el espacio de Riemann-Roch: polinomios módulo círculo (x^2 + y^2 - 1 = 0).
Los coeficientes de salida de Circle FFT son una base específica: {1, y, x, xy, 2x^2 - 1, 2x^2y - y, 2x^3 - x, 2x^3y - xy, 8x^4 - 8x^2 + 1...}
Los desarrolladores pueden ignorar este punto. STARKs solo necesitan almacenar los polinomios como un conjunto de valores de evaluación. FFT se utiliza para la expansión de bajo grado: dado N valores, se generan k*N valores en el mismo polinomio.
Operaciones comerciales
En el protocolo STARK, una operación común es realizar una multiplicación sobre puntos específicos. Por ejemplo, probar P(x)=y:
En el grupo STARK de circle, dado que no hay una función lineal de un solo punto, se deben emplear diferentes técnicas para sustituir los métodos de cálculo convencionales. Se demuestra mediante la evaluación en dos puntos, añadiendo un punto virtual que no necesita atención.
Si el polinomio P es igual a y1 en x1 y a y2 en x2, elige la función de interpolación L que es igual a y1 en x1 y a y2 en x2: L = ((y2 - y1)/(x2 - x1)) * (x - x1) + y1
Luego demuestra que P - L es cero en estos dos puntos, y prueba que el cociente Q es un polinomio al dividir L entre L.
Polinomio desaparecido
En STARK, las ecuaciones polinómicas suelen tener la forma C(P(x), P(next(x))) = Z(x) · H(x), Z(x) es cero en todo el dominio de evaluación.
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
Los polinomios que desaparecen se pueden derivar de funciones de plegado: el STARK convencional reutiliza x → x^2, el STARK circular reutiliza x → 2x^2 - 1.
Orden inverso
En STARKs, la evaluación de polinomios generalmente se organiza en orden inverso de bits. Por ejemplo, cuando n=16: {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}
Este ordenamiento hace que los valores de los grupos tempranos en el proceso de evaluación FRI estén adyacentes en el orden, ahorrando espacio.
En los STARKs de circle, la estructura de plegado es ligeramente diferente. Para ajustar el orden inverso y reflejar esta estructura, se debe invertir cada bit excepto el último, utilizando el último bit para decidir si se invierten otros bits.
Tamaño 16 de la secuencia invertida plegable: {0, 15, 8, 7, 4, 11, 12, 3, 2, 13, 10, 5, 6, 9, 14, 1}
Eficiencia
Circle STARKs son muy eficientes. Los cálculos normalmente implican:
La clave de la eficiencia radica en aprovechar al máximo el espacio de seguimiento computacional. El tamaño del campo Circle STARKs es de 2^31, lo que desperdicia poco espacio.
Binius es mejor que Circle STARKs, permite combinar campos de diferentes tamaños, logrando un empaquetado de bits más eficiente. Pero el costo es que el concepto es más complejo, mientras que el concepto de Circle STARKs es relativamente simple.
Conclusión
Circle STARKs no son más complejos que STARKs para los desarrolladores. Entender Circle FRI y Circle FFTs puede ser una vía para comprender otros FFTs especiales.
Combinando tecnologías como Mersenne31, BabyBear y Binius, nos acercamos al límite de eficiencia de la capa base de STARKs. Las posibles direcciones de optimización de STARK en el futuro podrían incluir: