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 STARKs utilizaban campos de 256 bits, pero este diseño tenía una eficiencia relativamente baja. Para mejorar la eficiencia, los STARKs comenzaron a utilizar campos más pequeños, como Goldilocks, Mersenne31 y BabyBear.

El uso de campos pequeños puede mejorar significativamente la velocidad de prueba. Por ejemplo, Starkware puede demostrar 620,000 hashes Poseidon2 por segundo en una laptop M3. Sin embargo, los campos pequeños también presentan nuevos desafíos, como garantizar la seguridad en un espacio de elección limitado.

Este artículo explorará Circle STARKs, que es un nuevo esquema compatible con el campo Mersenne31. Circle STARKs resuelve los problemas de seguridad que presentan los campos pequeños al operar sobre grupos de puntos en un círculo.

Circle FRI

La idea central de Circle FRI es definir un grupo de puntos de tamaño p en el círculo, el cual tiene la propiedad de un mapeo de dos a uno. Los puntos en el grupo satisfacen x^2 + y^2 = 1 (mod p).

El proceso de mapeo de Circle FRI es el siguiente:

1. Primero, converger todos los puntos en el eje x.
2. Realizar una combinación lineal aleatoria para obtener un polinomio unidimensional P(x)
3. A partir de la segunda ronda, usar el mapeo f_0(2x^2-1) = (F(x) + F(-x))/2

Este proceso reduce a la mitad el tamaño del conjunto de puntos cada vez, similar al FRI convencional.

FFTs circulares

El grupo Circle también admite FFT, cuya construcción es similar a Circle FRI. La diferencia es que el Circle FFT no maneja polinomios en el sentido estricto, sino el espacio de Riemann-Roch.

Los coeficientes de salida de Circle FFT son específicos de la base de Circle FFT: {1, y, x, xy, 2x^2 - 1, 2x^2y - y, ...}

Como desarrollador, puedes ignorar estos detalles matemáticos y simplemente almacenar el polinomio como un conjunto de valores de evaluación.

Otros detalles técnicos

• La operación comercial en STARKs de Circle necesita ser evaluada en dos puntos.
• La forma de construir polinomios desaparecidos es diferente
• Utilizar la secuencia de bits invertida modificada para adaptarse a la estructura de colapso de Circle STARKs

Eficiencia

Circle STARKs es muy eficiente en un campo primo de 31 bits:

• Aprovechó al máximo el espacio de cálculo
• Aplicable a la lógica de negocios y el cálculo criptográfico
• Soporte para operaciones eficientes de tablas de búsqueda

En comparación, la solución Binius tiene una ligera ventaja en eficiencia, pero el concepto es más complejo.

Resumen

Circle STARKs no son más complicados para los desarrolladores que los STARKs convencionales. Proporciona una solución elegante para los STARKs de campo pequeños, con la esperanza de impulsar la tecnología STARKs hacia una mayor eficiencia.

Las posibles direcciones de optimización para STARKs en el futuro incluyen:

• Optimización de funciones hash y otros primitivos criptográficos básicos
• Utilizar la construcción recursiva para mejorar la paralelización
• Mejorar la aritmética de la máquina virtual para mejorar la experiencia de desarrollo