En los últimos años, la tendencia en el diseño de protocolos STARKs es cambiar hacia el uso de campos más pequeños. Las primeras implementaciones de producción de STARKs utilizaban un campo de 256 bits, es decir, realizaban operaciones módulo sobre números grandes. Sin embargo, este diseño es menos eficiente y el procesamiento de números grandes desperdicia mucha potencia de cálculo. Para solucionar este problema, los STARKs comenzaron a usar campos más pequeños: primero Goldilocks, luego Mersenne31 y BabyBear.
Esta transformación ha mejorado significativamente la velocidad de prueba. Por ejemplo, Starkware ahora puede probar 620,000 hashes Poseidon2 por segundo en una computadora portátil M3. Esto significa que siempre que confiemos en Poseidon2 como función hash, podemos resolver el desafío del desarrollo eficiente de ZK-EVM. ¿Cómo funcionan estas tecnologías? ¿Cómo se construyen las pruebas en campos pequeños? Este artículo explorará estos detalles, con un enfoque especial en los STARKs de Circle, que son compatibles con el campo Mersenne31.
Problemas comunes al usar campos pequeños
Al crear pruebas basadas en hash, un truco importante es validar indirectamente las propiedades del polinomio mediante la evaluación del polinomio en puntos aleatorios. Esto puede simplificar enormemente el proceso de prueba.
Por ejemplo, supongamos que el protocolo requiere que generes un compromiso del polinomio A, que satisfaga A^3(x) + x - A(ωx) = x^N. El protocolo puede requerir que elijas coordenadas aleatorias r y demuestres que A(r)^3 + r - A(ωr) = r^N. Luego, deduces que A(r) = c, y demuestras que Q = (A - c)/(X - r) es un polinomio.
Para prevenir ataques, necesitamos elegir r después de que el atacante proporcione A. En los protocolos basados en curvas elípticas, esto es simple: podemos 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 r disponibles, y el atacante podría romperlo mediante fuerza bruta.
Este problema tiene dos soluciones:
Realizar múltiples inspecciones aleatorias
Campos extendidos
Las verificaciones aleatorias múltiples son simples y efectivas, pero pueden existir problemas de eficiencia. El dominio extendido es similar a los números complejos, pero se basa en un campo finito. Introducimos un nuevo valor α, declarando que α^2= un cierto valor. Esto crea una nueva estructura matemática que puede realizar operaciones más complejas sobre un campo finito.
A través de la expansión de dominios, tenemos suficientes valores para elegir, cumpliendo con las necesidades de seguridad. La mayoría de las operaciones matemáticas aún se realizan en el campo base, utilizando campos más grandes solo cuando se requiere una mayor seguridad.
FRI Regular
FRI (Fast Reed-Solomon Interactive) es un paso importante en la construcción de SNARK o STARK. Simplifica el proceso de verificación al reducir el problema de un polinomio de prueba de grado d a un problema de polinomio de prueba de grado d/2. Este proceso se puede repetir varias veces, reduciendo el problema a la mitad en cada ocasión.
El principio de funcionamiento de FRI es repetir el proceso de simplificación. Comenzando desde la prueba de que el grado del polinomio es d, a través de una serie de pasos, finalmente se prueba que el grado es d/2. Después de cada simplificación, el grado del polinomio generado disminuye gradualmente. Si en alguna etapa la salida no cumple con lo esperado, esa ronda de verificación fallará.
Para lograr una reducción gradual del dominio, se utilizó un mapeo de dos a uno. Este mapeo permite reducir a la mitad el tamaño del conjunto de datos, manteniendo al mismo tiempo las mismas propiedades. Esta operación se puede imaginar como el proceso de extender un segmento a lo largo de la circunferencia durante dos vueltas.
Para que la técnica de mapeo sea efectiva, el tamaño del subgrupo multiplicativo original necesita tener un gran factor de potencia de 2. El módulo de BabyBear permite que su máximo subgrupo multiplicativo contenga todos los valores no cero, lo que lo hace muy adecuado para esta técnica. El tamaño del subgrupo multiplicativo de Mersenne31 solo tiene un factor de potencia de 2, lo que limita su rango de aplicación.
El campo Mersenne31 es muy adecuado para realizar operaciones aritméticas en CPU/GPU de 32 bits, siendo aproximadamente 1.3 veces más rápido que el campo BabyBear. Si se puede implementar FRI en el campo Mersenne31, se mejorará significativamente la eficiencia computacional.
Circle FRI
La ingeniosidad de Circle STARKs radica en que, dado un primo p, se puede encontrar un grupo de tamaño p que tiene una propiedad similar de dos a uno. Este grupo está formado por puntos que satisfacen ciertas condiciones, como el conjunto de puntos donde x^2 mod p es igual a 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)
Circle FRI primero hace que todos los puntos se concentren en una sola línea recta, luego realiza una combinación lineal aleatoria para obtener 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, convirtiendo las coordenadas x de dos puntos opuestos en el círculo en las coordenadas x del punto multiplicado. Esto se podría hacer en un espacio bidimensional, pero la operación unidimensional es más eficiente.
FFTs Circulares
El grupo Circle también admite FFT, y su construcción es similar a FRI. El objeto que maneja Circle FFT es el espacio de Riemann-Roch, en lugar de ser estrictamente un polinomio. Los coeficientes de salida de Circle FFT son específicos de la base de Circle FFT.
Como desarrollador, puedes ignorar casi por completo este aspecto. Los STARKs solo necesitan almacenar polinomios como un conjunto de valores de evaluación. El único lugar donde se necesita FFT es para realizar una extensión de bajo grado: dado N valores, generar k*N valores sobre el mismo polinomio.
Quotienting
En Circle STARKs, debido a la falta de funciones lineales que se puedan evaluar en un solo punto, se requieren diferentes técnicas para reemplazar las operaciones comerciales tradicionales. Nos vemos obligados a demostrar evaluando en dos puntos, añadiendo un punto virtual.
Si el polinomio P es igual a y1 en x1 y a y2 en x2, elegimos la función de interpolación L, que es igual en esos dos puntos. Luego demostramos que P-L es cero en esos dos puntos, demostrando que el cociente Q al dividir L por L es un polinomio.
Polinomios que desaparecen
En Circle STARKs, el polinomio de desaparición es:
Z1(x,y) = y
Z2(x,y) = x
Zn+1(x,y) = (2 * Zn(x,y)^2) - 1
Esto se puede deducir de la función de pliegue: en Circle STARKs, se reutiliza x → 2x^2 - 1. La primera ronda requiere un tratamiento especial.
Invertir el orden de los bits
Circle STARKs utiliza un orden de bits inverso modificado, invirtiendo cada bit excepto el último, y utilizando el último bit para determinar si se invierten otros bits. Esto refleja la estructura de plegado única de Circle STARKs.
Eficiencia
Circle STARKs son muy eficientes. Los cálculos generalmente involucran:
Aritmética nativa: utilizada para la lógica de negocios
Aritmética nativa: utilizada en criptografía ( como el hash Poseidon )
Buscar parámetros: realizar varios cálculos a través de la tabla de búsqueda de valores
Circle STARKs aprovechan al máximo el espacio de cálculo, desperdiciando menos. Son un poco inferiores a Binius, pero el concepto es más simple.
Conclusión
Circle STARKs no son más complicados para los desarrolladores que los STARKs convencionales. Comprender Circle FRI y FFTs puede ayudar a entender otros FFTs especiales. Actualmente, la eficiencia de la capa base de STARKs se acerca a su límite, y las direcciones de optimización futuras pueden incluir:
Maximizar la eficiencia aritmética de las funciones hash y las firmas
Construcción recursiva para mejorar 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.
19 me gusta
Recompensa
19
4
Republicar
Compartir
Comentar
0/400
NftBankruptcyClub
· 08-09 22:10
La letra es más pequeña, pero la eficiencia ha aumentado...666
Ver originalesResponder0
GasWhisperer
· 08-09 22:08
hmm... campos más pequeños = pruebas más rápidas, pero ¿podemos confiar en poseidon2? me siento conflicted sobre este tradeoff eficiencia/seguridad, tbh
Ver originalesResponder0
alpha_leaker
· 08-09 21:58
Stark es un poco aterrador.
Ver originalesResponder0
ChainDetective
· 08-09 21:54
Solo entendí que básicamente es una forma simplificada para calcular rápidamente.
Circle STARKs: Exploración y avances en pruebas ZK eficientes de pequeño campo
Explorar Circle STARKs
En los últimos años, la tendencia en el diseño de protocolos STARKs es cambiar hacia el uso de campos más pequeños. Las primeras implementaciones de producción de STARKs utilizaban un campo de 256 bits, es decir, realizaban operaciones módulo sobre números grandes. Sin embargo, este diseño es menos eficiente y el procesamiento de números grandes desperdicia mucha potencia de cálculo. Para solucionar este problema, los STARKs comenzaron a usar campos más pequeños: primero Goldilocks, luego Mersenne31 y BabyBear.
Esta transformación ha mejorado significativamente la velocidad de prueba. Por ejemplo, Starkware ahora puede probar 620,000 hashes Poseidon2 por segundo en una computadora portátil M3. Esto significa que siempre que confiemos en Poseidon2 como función hash, podemos resolver el desafío del desarrollo eficiente de ZK-EVM. ¿Cómo funcionan estas tecnologías? ¿Cómo se construyen las pruebas en campos pequeños? Este artículo explorará estos detalles, con un enfoque especial en los STARKs de Circle, que son compatibles con el campo Mersenne31.
Problemas comunes al usar campos pequeños
Al crear pruebas basadas en hash, un truco importante es validar indirectamente las propiedades del polinomio mediante la evaluación del polinomio en puntos aleatorios. Esto puede simplificar enormemente el proceso de prueba.
Por ejemplo, supongamos que el protocolo requiere que generes un compromiso del polinomio A, que satisfaga A^3(x) + x - A(ωx) = x^N. El protocolo puede requerir que elijas coordenadas aleatorias r y demuestres que A(r)^3 + r - A(ωr) = r^N. Luego, deduces que A(r) = c, y demuestras que Q = (A - c)/(X - r) es un polinomio.
Para prevenir ataques, necesitamos elegir r después de que el atacante proporcione A. En los protocolos basados en curvas elípticas, esto es simple: podemos 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 r disponibles, y el atacante podría romperlo mediante fuerza bruta.
Este problema tiene dos soluciones:
Las verificaciones aleatorias múltiples son simples y efectivas, pero pueden existir problemas de eficiencia. El dominio extendido es similar a los números complejos, pero se basa en un campo finito. Introducimos un nuevo valor α, declarando que α^2= un cierto valor. Esto crea una nueva estructura matemática que puede realizar operaciones más complejas sobre un campo finito.
A través de la expansión de dominios, tenemos suficientes valores para elegir, cumpliendo con las necesidades de seguridad. La mayoría de las operaciones matemáticas aún se realizan en el campo base, utilizando campos más grandes solo cuando se requiere una mayor seguridad.
FRI Regular
FRI (Fast Reed-Solomon Interactive) es un paso importante en la construcción de SNARK o STARK. Simplifica el proceso de verificación al reducir el problema de un polinomio de prueba de grado d a un problema de polinomio de prueba de grado d/2. Este proceso se puede repetir varias veces, reduciendo el problema a la mitad en cada ocasión.
El principio de funcionamiento de FRI es repetir el proceso de simplificación. Comenzando desde la prueba de que el grado del polinomio es d, a través de una serie de pasos, finalmente se prueba que el grado es d/2. Después de cada simplificación, el grado del polinomio generado disminuye gradualmente. Si en alguna etapa la salida no cumple con lo esperado, esa ronda de verificación fallará.
Para lograr una reducción gradual del dominio, se utilizó un mapeo de dos a uno. Este mapeo permite reducir a la mitad el tamaño del conjunto de datos, manteniendo al mismo tiempo las mismas propiedades. Esta operación se puede imaginar como el proceso de extender un segmento a lo largo de la circunferencia durante dos vueltas.
Para que la técnica de mapeo sea efectiva, el tamaño del subgrupo multiplicativo original necesita tener un gran factor de potencia de 2. El módulo de BabyBear permite que su máximo subgrupo multiplicativo contenga todos los valores no cero, lo que lo hace muy adecuado para esta técnica. El tamaño del subgrupo multiplicativo de Mersenne31 solo tiene un factor de potencia de 2, lo que limita su rango de aplicación.
El campo Mersenne31 es muy adecuado para realizar operaciones aritméticas en CPU/GPU de 32 bits, siendo aproximadamente 1.3 veces más rápido que el campo BabyBear. Si se puede implementar FRI en el campo Mersenne31, se mejorará significativamente la eficiencia computacional.
Circle FRI
La ingeniosidad de Circle STARKs radica en que, dado un primo p, se puede encontrar un grupo de tamaño p que tiene una propiedad similar de dos a uno. Este grupo está formado por puntos que satisfacen ciertas condiciones, como el conjunto de puntos donde x^2 mod p es igual a 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)
Circle FRI primero hace que todos los puntos se concentren en una sola línea recta, luego realiza una combinación lineal aleatoria para obtener 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, convirtiendo las coordenadas x de dos puntos opuestos en el círculo en las coordenadas x del punto multiplicado. Esto se podría hacer en un espacio bidimensional, pero la operación unidimensional es más eficiente.
FFTs Circulares
El grupo Circle también admite FFT, y su construcción es similar a FRI. El objeto que maneja Circle FFT es el espacio de Riemann-Roch, en lugar de ser estrictamente un polinomio. Los coeficientes de salida de Circle FFT son específicos de la base de Circle FFT.
Como desarrollador, puedes ignorar casi por completo este aspecto. Los STARKs solo necesitan almacenar polinomios como un conjunto de valores de evaluación. El único lugar donde se necesita FFT es para realizar una extensión de bajo grado: dado N valores, generar k*N valores sobre el mismo polinomio.
Quotienting
En Circle STARKs, debido a la falta de funciones lineales que se puedan evaluar en un solo punto, se requieren diferentes técnicas para reemplazar las operaciones comerciales tradicionales. Nos vemos obligados a demostrar evaluando en dos puntos, añadiendo un punto virtual.
Si el polinomio P es igual a y1 en x1 y a y2 en x2, elegimos la función de interpolación L, que es igual en esos dos puntos. Luego demostramos que P-L es cero en esos dos puntos, demostrando que el cociente Q al dividir L por L es un polinomio.
Polinomios que desaparecen
En Circle STARKs, el polinomio de desaparición es: Z1(x,y) = y Z2(x,y) = x Zn+1(x,y) = (2 * Zn(x,y)^2) - 1
Esto se puede deducir de la función de pliegue: en Circle STARKs, se reutiliza x → 2x^2 - 1. La primera ronda requiere un tratamiento especial.
Invertir el orden de los bits
Circle STARKs utiliza un orden de bits inverso modificado, invirtiendo cada bit excepto el último, y utilizando el último bit para determinar si se invierten otros bits. Esto refleja la estructura de plegado única de Circle STARKs.
Eficiencia
Circle STARKs son muy eficientes. Los cálculos generalmente involucran:
Circle STARKs aprovechan al máximo el espacio de cálculo, desperdiciando menos. Son un poco inferiores a Binius, pero el concepto es más simple.
Conclusión
Circle STARKs no son más complicados para los desarrolladores que los STARKs convencionales. Comprender Circle FRI y FFTs puede ayudar a entender otros FFTs especiales. Actualmente, la eficiencia de la capa base de STARKs se acerca a su límite, y las direcciones de optimización futuras pueden incluir: