En los últimos años, la tendencia en el diseño del protocolo STARKs es cambiar hacia el uso de campos más pequeños. Las primeras implementaciones de STARKs utilizaban campos de 256 bits, lo que hacía que estos protocolos fueran compatibles con las firmas basadas en curvas elípticas. Sin embargo, este diseño es menos eficiente y procesar números grandes desperdicia mucha potencia de cálculo. Para abordar este problema, STARKs comenzó a utilizar campos más pequeños: primero Goldilocks, luego Mersenne31 y BabyBear.
Esta transformación ha mejorado significativamente la velocidad de prueba. Por ejemplo, Starkware puede probar 620,000 valores hash Poseidon2 por segundo en una laptop M3. Esto significa que, siempre que se confíe en Poseidon2 como función hash, se puede resolver el problema del ZK-EVM eficiente. ¿Cómo funcionan estas tecnologías? ¿Cómo se construyen pruebas en campos pequeños? Este artículo explorará estos detalles, con un enfoque particular en la solución Circle STARKs.
Preguntas frecuentes sobre el uso de campos pequeños
Al crear pruebas basadas en hash, un truco importante es validar indirectamente las propiedades del polinomio a través de los resultados de la evaluación del polinomio en puntos aleatorios. Esto simplifica enormemente el proceso de prueba.
Por ejemplo, supongamos que se requiere generar un compromiso de un polinomio A que satisfaga 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, 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 el protocolo de gran campo, se puede elegir un número aleatorio de 256 bits como r. Pero en STARKs de campo pequeño, solo hay alrededor de 2 mil millones de valores de r disponibles, y el atacante puede intentar todas las posibilidades.
Este problema tiene dos soluciones:
Realizar múltiples inspecciones aleatorias
Campo de extensión
Las múltiples inspecciones aleatorias son simples y efectivas, pero presentan problemas de eficiencia. Los campos de extensión son similares a los números complejos, pero se basan en un campo finito. Se introduce un nuevo valor α que satisface α^2 = cierto valor, creando una nueva estructura matemática. Esto nos permite tener más opciones de valores, mejorando la seguridad.
FRI Regular
El primer paso del protocolo FRI suele ser la aritmética, transformando el problema computacional en la ecuación P(X,Y,Z)=0, donde P es un polinomio, X, Y, Z son parámetros. Resolver la ecuación corresponde a resolver el problema original.
Para demostrar la corrección de la solución, se debe probar que el valor propuesto es un polinomio razonable y de grado máximo. Utilizando la técnica de combinaciones lineales aleatorias:
Supongamos que hay un valor de evaluación del polinomio A, hay que demostrar que su grado es < 2^20
D es una combinación lineal aleatoria de B y C: D = B + rC
En esencia, B aísla los coeficientes pares, y C aísla los coeficientes impares. B y C pueden 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 aleatoria, debe tener un grado igual al de A.
FRI repite este proceso de simplificación, reduciendo el problema a la mitad cada vez. Este diseño detecta de manera efectiva las entradas que no cumplen con los requisitos.
Circle FRI
Esta es la astucia de Circle STARKs. 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 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, convergiendo 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.
FFTs Circulares
El grupo Circle también admite FFT, y su método de construcción es similar al de FRI. Sin embargo, el objeto que maneja Circle FFT es el espacio de Riemann-Roch, y no un polinomio estricto.
Como desarrollador, puedes ignorar este punto. STARKs solo necesitan almacenar los polinomios como un conjunto de valores de evaluación. FFT se utiliza principalmente para la baja expansión: dados N valores, genera k*N valores sobre el mismo polinomio.
Cotejo
En Circle STARKs, debido a la falta de funciones lineales de punto único, se deben emplear técnicas diferentes para sustituir las operaciones comerciales tradicionales. A través de la evaluación en dos puntos, se demuestra la adición de un punto virtual.
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 en estos dos puntos. Luego, demuestra que P-L es cero en los dos puntos, y al dividir L se obtiene un cociente Q que es un polinomio.
Polinomios que desaparecen
El polinomio desaparecido en Circle STARKs es:
Z1(x,y) = y
Z2(x,y) = x
Zn+1(x,y) = (2 * Zn(x,y)^2) - 1
Esto se puede derivar de la función de plegado: reutilizar x → 2x^2 - 1.
Invertir el orden de los bits
En STARKs de Circle, el orden inverso necesita ser ajustado: invierte cada bit excepto el último, utilizando el último bit para decidir si invertir otros bits.
Circle STARKs son muy eficientes. Los cálculos generalmente implican:
Aritmética nativa de la lógica de negocios
Aritmética nativa de la criptografía
Buscar parámetros
La clave de la eficiencia radica en aprovechar al máximo el espacio de seguimiento computacional. El campo de 31 bits reduce el desperdicio. Binius mezcla campos de diferentes tamaños con mayor eficiencia, pero el concepto es más complejo.
Conclusión
Circle STARKs no son complicados para los desarrolladores. Entender la matemática detrás toma tiempo, pero la complejidad está bien oculta. También es una vía para entender otros FFTs especiales.
Actualmente, la eficiencia de la capa base de STARKs está cerca de su límite. Las posibles direcciones de optimización en el futuro podrían incluir:
Maximizar la eficiencia de funciones hash y otros primitivos criptográficos básicos
Construcción recursiva para aumentar la paralelización
Máquina virtual aritmética para mejorar la experiencia de desarrollo
Esta página puede contener contenido de terceros, que se proporciona únicamente con fines informativos (sin garantías ni declaraciones) y no debe considerarse como un respaldo por parte de Gate a las opiniones expresadas ni como asesoramiento financiero o profesional. Consulte el Descargo de responsabilidad para obtener más detalles.
Explorando Circle STARKs: La revolución de pruebas eficientes traídas por campos pequeños
Explorando en profundidad Circle STARKs
En los últimos años, la tendencia en el diseño del protocolo STARKs es cambiar hacia el uso de campos más pequeños. Las primeras implementaciones de STARKs utilizaban campos de 256 bits, lo que hacía que estos protocolos fueran compatibles con las firmas basadas en curvas elípticas. Sin embargo, este diseño es menos eficiente y procesar números grandes desperdicia mucha potencia de cálculo. Para abordar este problema, STARKs comenzó a utilizar campos más pequeños: primero Goldilocks, luego Mersenne31 y BabyBear.
Esta transformación ha mejorado significativamente la velocidad de prueba. Por ejemplo, Starkware puede probar 620,000 valores hash Poseidon2 por segundo en una laptop M3. Esto significa que, siempre que se confíe en Poseidon2 como función hash, se puede resolver el problema del ZK-EVM eficiente. ¿Cómo funcionan estas tecnologías? ¿Cómo se construyen pruebas en campos pequeños? Este artículo explorará estos detalles, con un enfoque particular en la solución Circle STARKs.
Preguntas frecuentes sobre el uso de campos pequeños
Al crear pruebas basadas en hash, un truco importante es validar indirectamente las propiedades del polinomio a través de los resultados de la evaluación del polinomio en puntos aleatorios. Esto simplifica enormemente el proceso de prueba.
Por ejemplo, supongamos que se requiere generar un compromiso de un polinomio A que satisfaga 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, 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 el protocolo de gran campo, se puede elegir un número aleatorio de 256 bits como r. Pero en STARKs de campo pequeño, solo hay alrededor de 2 mil millones de valores de r disponibles, y el atacante puede intentar todas las posibilidades.
Este problema tiene dos soluciones:
Las múltiples inspecciones aleatorias son simples y efectivas, pero presentan problemas de eficiencia. Los campos de extensión son similares a los números complejos, pero se basan en un campo finito. Se introduce un nuevo valor α que satisface α^2 = cierto valor, creando una nueva estructura matemática. Esto nos permite tener más opciones de valores, mejorando la seguridad.
FRI Regular
El primer paso del protocolo FRI suele ser la aritmética, transformando el problema computacional en la ecuación P(X,Y,Z)=0, donde P es un polinomio, X, Y, Z son parámetros. Resolver la ecuación corresponde a resolver el problema original.
Para demostrar la corrección de la solución, se debe probar que el valor propuesto es un polinomio razonable y de grado máximo. Utilizando la técnica de combinaciones lineales aleatorias:
En esencia, B aísla los coeficientes pares, y C aísla los coeficientes impares. B y C pueden 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 aleatoria, debe tener un grado igual al de A.
FRI repite este proceso de simplificación, reduciendo el problema a la mitad cada vez. Este diseño detecta de manera efectiva las entradas que no cumplen con los requisitos.
Circle FRI
Esta es la astucia de Circle STARKs. 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 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, convergiendo 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.
FFTs Circulares
El grupo Circle también admite FFT, y su método de construcción es similar al de FRI. Sin embargo, el objeto que maneja Circle FFT es el espacio de Riemann-Roch, y no un polinomio estricto.
Como desarrollador, puedes ignorar este punto. STARKs solo necesitan almacenar los polinomios como un conjunto de valores de evaluación. FFT se utiliza principalmente para la baja expansión: dados N valores, genera k*N valores sobre el mismo polinomio.
Cotejo
En Circle STARKs, debido a la falta de funciones lineales de punto único, se deben emplear técnicas diferentes para sustituir las operaciones comerciales tradicionales. A través de la evaluación en dos puntos, se demuestra la adición de un punto virtual.
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 en estos dos puntos. Luego, demuestra que P-L es cero en los dos puntos, y al dividir L se obtiene un cociente Q que es un polinomio.
Polinomios que desaparecen
El polinomio desaparecido en Circle STARKs es: Z1(x,y) = y Z2(x,y) = x Zn+1(x,y) = (2 * Zn(x,y)^2) - 1
Esto se puede derivar de la función de plegado: reutilizar x → 2x^2 - 1.
Invertir el orden de los bits
En STARKs de Circle, el orden inverso necesita ser ajustado: invierte cada bit excepto el último, utilizando el último bit para decidir si invertir otros bits.
16 tamaño de la secuencia inversa plegable es: {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 generalmente implican:
La clave de la eficiencia radica en aprovechar al máximo el espacio de seguimiento computacional. El campo de 31 bits reduce el desperdicio. Binius mezcla campos de diferentes tamaños con mayor eficiencia, pero el concepto es más complejo.
Conclusión
Circle STARKs no son complicados para los desarrolladores. Entender la matemática detrás toma tiempo, pero la complejidad está bien oculta. También es una vía para entender otros FFTs especiales.
Actualmente, la eficiencia de la capa base de STARKs está cerca de su límite. Las posibles direcciones de optimización en el futuro podrían incluir: