Circle FFT — Parte 1: Construyendo el dominio del círculo

Last updated on Aug 20, 2025

Circle STARKs es un nuevo esquema zk-STARK que ha sido implementado en Stwo y Plonky3, y ha sido adoptado por varios proyectos de zkVM. Su innovación clave radica en permitir el uso de pequeños campos de 32 bits (primo de Mersenne $2^{31}-1$ ) mientras mantiene las propiedades matemáticas necesarias para realizar operaciones eficientes de FFT. En esta serie de artículos explicativos, discutiremos el algoritmo principal detrás de Circle STARK, denominado Circle FFT.

En el artículo de la Parte 1, primero revisamos cómo han evolucionado los primos aptos para STARK, y luego exploramos los conceptos fundamentales de Circle FFT—es decir, la curva del círculo, su estructura de grupo y los roles de los twin-cosets y los cosets en posición estándar, utilizando ejemplos y derivaciones detalladas. Luego, en el artículo de la Parte 2, describiremos en detalle el algoritmo Circle FFT en sí.

También proporcionamos un recorrido por estas ideas centrales—como el grupo del círculo y la Circle FFT—junto con cálculos de ejemplo explícitos para $p=31$ (primo de Mersenne con exponente $5$ : $2^5 -1$ ) con un script de Python.

Nuestro enfoque es cómo cada uno de estos bloques de construcción conduce a una rutina completa tipo FFT incluso cuando $p-1$ no tiene un factor 2-ádico grande.

Si estás interesado en ejecutar los ejemplos por ti mismo, el código completo de Python está disponible aquí, y lo referenciamos en secciones posteriores como la Sección 4 y 6, donde recorremos la construcción del grupo y del dominio en el código.

Este artículo fue escrito por Yugo en colaboración con RareSkills. Este artículo fue financiado por un Soulforge Grant. Agradecemos su apoyo.

0. De Primos Aptos para STARK a Mersenne 31

Antes de sumergirnos en los primos aptos para STARK, primero recordemos los conceptos básicos de los campos finitos.

Un campo es un conjunto en el que se definen la suma, resta, multiplicación y división (excepto por cero). Cuando el conjunto de elementos es finito, se le llama campo finito. $\mathbb{F}_p$ se refiere al conjunto de enteros desde $0$ hasta $p-1$ (donde $p$ es un número primo), con la suma, resta y multiplicación tomadas módulo $p$ , y la división definida como la inversa de la multiplicación módulo $p$ .

Denotamos mediante $\mathbb{F}_p^*$ al conjunto $\mathbb{F}_p \setminus \{0\}$ . Cada elemento en $\mathbb{F}_p^*$ tiene un inverso multiplicativo, por lo que $\mathbb{F}_p^*$ puede verse como un grupo multiplicativo. El tamaño de este grupo, $|\mathbb{F}_p^*|$ , es $p-1$ . Cuando factorizamos $p-1$ en sus factores primos, se sabe que si un primo $q$ aparece $r$ veces, entonces hay un subgrupo cíclico de tamaño $q^r$ .

Puedes ilustrar esto brevemente con un primo pequeño, por ejemplo $p=7$ . Dado que $p-1=6$ se factoriza como $2\times 3$ , deben existir subgrupos de tamaños $2$ y $3$ . De hecho, en $\mathbb{F}_7^* = \{1,2,3,4,5,6\}$ , el elemento $6$ genera un subgrupo de tamaño $2$ $\{1,6\}$ , y el elemento $2$ genera un subgrupo de tamaño $3$ $\{1,2,4\}$ .

En muchos protocolos STARK, la Transformada Teórica de Números (NTT) o Transformada Rápida de Fourier (FFT) depende de dicho subgrupo donde el factor es una potencia de 2, de modo que el subgrupo tiene tamaño $2^r$ . El mayor número entero $r$ tal que $2^r$ divide a $(p-1)$ se llama la 2-adicidad. Una alta 2-adicidad permite un mayor tamaño de potencia de 2 para los dominios de FFT/NTT, lo cual es clave para lograr evaluaciones, interpolaciones y multiplicaciones de polinomios rápidas. Además, implementar estas operaciones basadas en NTT de manera eficiente depende en gran medida de multiplicaciones modulares rápidas—ya que la FFT/NTT implica multiplicar repetidamente elementos y reducirlos módulo $p$ .

Originalmente, los STARKs utilizaban un primo $p = 2^{251} + 17 \cdot 2^{192} + 1$ , que tiene una 2-adicidad de $192$ . En las implementaciones modernas de STARK, una de las mejoras que se hizo fue reducir la sobrecarga disminuyendo el tamaño del campo finito. Por ejemplo, el campo Goldilocks es $p = 2^{64} - 2^{32} + 1$ y tiene una 2-adicidad de $32$ . De manera crucial, debido a que $2^{64} \equiv 2^{32} - 1 \pmod{p},$ el producto de dos números de 64 bits puede dividirse en base $2^{32}$ y reducirse con solo unas pocas sumas y restas.

¿Qué hay de los Circle STARKs? Como se propone en el documento de Circle STARKs, utiliza un primo de Mersenne,

p = 2^{31} - 1.

Un primo de Mersenne es un número primo de la forma $2^n -1$ para algún entero $n$ . Aquí, $n=31$ da $2^{31}−1$ , que resulta ser primo y por lo tanto está categorizado como un primo de Mersenne.

Una de las razones principales para elegir $2^{31}-1$ es que cabe dentro de una palabra de máquina de 32 bits, lo que hace que la multiplicación modular sea extremadamente rápida. Específicamente, cuando se multiplican dos números de 32 bits, el resultado es un valor de 64 bits, y la reducción modular por $2^{31}-1$ se puede realizar con solo dos sumas.

Esta operación puede ser mucho más rápida con instrucciones vectorizadas. Las CPUs modernas sobresalen procesando enteros de 32 bits nativamente, y el Mersenne 31 ( $2^{31}-1$ ) se ajusta a esta arquitectura, permitiendo una utilización óptima de las capacidades del hardware. Comparado con el primo de 256 bits utilizado en el STARK original, el Mersenne 31 ofrece una multiplicación modular aproximadamente 125 veces más rápida, y un aumento de velocidad de 1.3 veces sobre Baby Bear ( $2^{31} - 2^{27} + 1$ ), como se discute en Why I’m Excited By Circle Stark And Stwo por Eli Ben-Sasson.

Sin embargo, el enfoque tradicional de FFT o NTT requiere un gran factor 2-ádico en $p-1$ para formar un subgrupo suficiente de potencia de 2 en $\mathbb{F}_p^*$ . Aquí, $|\mathbb{F}_p^*| = p - 1 \;=\; 2^{31} - 2,$ el cual tiene una 2-adicidad de solo 1. Por lo tanto, no podemos usar directamente un subgrupo grande de potencia de 2 bajo la multiplicación.

Circle STARK todavía emplea el campo primo de Mersenne $p = 2^{31} - 1$ . Sin embargo, en lugar de trabajar directamente con $\mathbb{F}_p$ en sí, observamos que la curva

x^2 + y^2 = 1

sobre

\mathbb{F}_p

(donde

p \equiv 3 \pmod{4}

) tiene exactamente

p + 1

puntos. Por ejemplo, cuando

p = 3\; (= 2^2 - 1)

, hay exactamente cuatro de tales puntos:

(0,1), (0,2), (1,0), (2,0)

Esto es crucial porque $p+1$ puede incluir una gran potencia de 2, creando subgrupos de tamaño $2^n$ . Por lo tanto, en lugar de trabajar con elementos individuales en $\mathbb{F}_p$ , Circle STARK considera pares $(x,y)\in \mathbb{F}_p^2$ que satisfacen $x^2 + y^2 = 1$ (es decir, puntos en la curva del círculo).
Al hacerlo, Circle STARK puede implementar su propia interpolación y evaluación rápida de polinomios—a menudo referida como la Circle FFT—directamente sobre estos elementos del círculo.

1. Curva del Círculo

Pasemos a las matemáticas centrales de Circle STARKs. Una curva del círculo sobre un campo finito $\mathbb{F}_p$ es el subconjunto de $\mathbb{F}_p^2$ definido por todos los puntos $(x,y)$ que satisfacen

x^2 + y^2 = 1.

A veces denotamos este conjunto por

C(\mathbb{F}_p)

o simplemente “el círculo”.

En los Circle STARKs, nos centramos en primos $p$ con $p \equiv 3 \pmod{4}$ (por ejemplo, $p=3,7,11,\dots$ ). Bajo esta condición, $-1$ no es un cuadrado en $\mathbb{F}_p$ . Concretamente, esto asegura que la ecuación $x^2 + y^2 = 1$ tenga exactamente $p+1$ soluciones en $\mathbb{F}_p^2$ y ninguna solución atípica adicional (es decir, puntos en el infinito). Para este artículo, todo lo que necesitamos saber es que $x^2 + y^2 = 1$ en $\mathbb{F}_p^2$ produce exactamente $p+1$ puntos bajo esa condición.

(Sin embargo, para los lectores interesados en una perspectiva geométrica sobre por qué $p \equiv 3 \pmod{4}$ lleva a exactamente $p + 1$ soluciones, ver el Apéndice).

1.1 Ejemplo de Juguete $p=7\equiv 3 \pmod{4}$

Por ejemplo, si $p =7$ (que es $3 \pmod{4}$ ), entonces $C(\mathbb{F}_{7})$ es el conjunto de todos los $(x,y) \in \mathbb{F}_{7}^2$ tales que $x^2 + y^2 = 1.$

Aquí hay algunos pares $(x,y)$ en $\mathbb{F}_{7}^2$ que satisfacen $x^2 + y^2 \equiv 1 \pmod{7}$ . Por ejemplo:

$(1, 0)$ y $(0, 1)$ son obvios porque $1^2 + 0^2=1$ y $0^2 + 1^2=1$ .
$(5,2)$ también funciona porque $5^2 + 2^2 = 25 + 4 = 29$ , y $29 \bmod 7 = 1$ .

Vemos que hay exactamente $8$ $(p+1)$ pares de este tipo para $p=7$ .

2. Grupo del Círculo

Este tipo de conjunto se denota por $C(\mathbb{F}_p)$ y a menudo se llama Curva del Círculo sobre $\mathbb{F}_p$ . Un hecho sorprendente es que $|C(\mathbb{F}_p)| = p + 1$ . Por ejemplo, si $p = 7$ , entonces hay exactamente $7 + 1 = 8$ puntos en el círculo — notablemente $8 = 2^3$ .

Esto es importante porque en el entorno usual de STARK, a menudo queremos un dominio de tamaño $2^n$ para operaciones similares a FFT. En el caso de $p = 7$ , tener exactamente 8 puntos en el círculo significa que podemos formar subgrupos de tamaño $2^n$ . Más adelante, veremos cómo esta propiedad (la alta 2-adicidad en $p+1$ ) se explota en la Circle FFT.

Una propiedad clave es que se le puede dar a $C(\mathbb{F}_p)$ una operación de grupo (la cual es, en esencia, un operador binario) en sus puntos. Específicamente, usamos “ $\cdot$ ” para denotar esta operación: para dos puntos $(x_0,y_0)$ y $(x_1,y_1)$ en $C(\mathbb{F}_p)$ ,

(x_0, y_0)\,\cdot\,(x_1, y_1) \;=\; \bigl(x_0 x_1 - y_0 y_1,\;\; x_0 y_1 + y_0 x_1\bigr).

Podemos verificar que esta operación de grupo se mantiene dentro de $C(\mathbb{F}_p)$ (el resultado aún satisface $x^2 + y^2=1$ ) y convierte el conjunto en un grupo cíclico de tamaño $p+1$ .

2.1 Verificación de los Axiomas de Grupo

Como los axiomas de un grupo, típicamente enumeramos las siguientes cuatro propiedades: clausura, el elemento identidad, el elemento inverso y la asociatividad. Echemos un vistazo más de cerca a cada una para confirmar que todas se cumplen.

2.1.1 Clausura

Toma dos puntos $(x_0, y_0)$ y $(x_1, y_1)$ en el círculo;

x_0^2 + y_0^2 = 1 \quad\text{y}\quad x_1^2 + y_1^2 = 1.

Define un nuevo punto

(\hat{x}, \hat{y}) \;=\; \bigl( x_0\,x_1 \;-\; y_0\,y_1, \;\; x_0\,y_1 \;+\; y_0\,x_1 \bigr).

Mostraremos que $(\hat{x}, \hat{y})$ también se encuentra en el círculo calculando $(\hat{x}^2 + \hat{y}^2)$ paso a paso:

\begin{aligned} \hat{x}^2 + \hat{y}^2 &=\; (x_0 x_1 - y_0 y_1)^2 \;+\; (x_0 y_1 + y_0 x_1)^2 \quad \text{// expandir cuadrados} \\[6pt] &=\; {x_0^2 x_1^2} -\; 2\,x_0 x_1\,y_0 y_1 +\; {y_0^2 y_1^2} \;+\; {x_0^2 y_1^2} +\; 2\,x_0 y_1\,y_0 x_1 +\; {y_0^2 x_1^2} \\[4pt] &=\; x_0^2 x_1^2 \;+\; y_0^2 y_1^2 \;+\; x_0^2 y_1^2 \;+\; y_0^2 x_1^2 \quad \text{// cancelado $\pm2\,x_0 y_1\,y_0 x_1$} \\[3pt] &=\; x_0^2 \bigl(x_1^2 + y_1^2\bigr) \;+\; y_0^2 \bigl(x_1^2 + y_1^2\bigr) \quad \text{// factorizar }(x_1^2 + y_1^2) \\[3pt] &=\; \bigl(x_0^2 + y_0^2\bigr)\, \bigl(x_1^2 + y_1^2\bigr) \quad \text{// factorizar nuevamente usando }x_0^2 + y_0^2 \end{aligned}

Dado que sabemos que $x_0^2 + y_0^2 = 1$ y $x_1^2 + y_1^2 = 1$ , sustituimos estos valores en el producto:

\hat{x}^2 + \hat{y}^2 \;=\; (x_0^2 + y_0^2)\,(x_1^2 + y_1^2) \;=\; 1 \times 1 \;=\; 1.

Por lo tanto $(\hat{x}, \hat{y})$ también satisface $(\hat{x}^2 + \hat{y}^2 = 1)$ y, en consecuencia, se encuentra en el círculo. Esto confirma que el conjunto es cerrado bajo la operación

(x_0, y_0) \;\cdot\; (x_1, y_1) \;=\; (\hat{x}, \hat{y}).

2.1.2 Elemento Identidad

El punto $(1,0)$ sirve como el elemento identidad bajo la operación de grupo. Concretamente, para cualquier $(x,y)$ en el círculo,

(1,0)\cdot(x,y) \;=\; \bigl(1\cdot x - 0\cdot y,\;1\cdot y + 0\cdot x\bigr) \;=\; (x,y),

Uno podría preguntarse sobre el punto $(0,1)$ . Si intentamos usar $(0,1)$ como una identidad, vemos que falla:

(0,1)\cdot(x,y) \;=\; \bigl(0\cdot x - 1\cdot y,\;0\cdot y + 1\cdot x\bigr) \;=\; (-y,\;x),

lo cual no es igual a

(x,y)

para un

x,y

general. Debido a que el elemento identidad es único,

(0,1)

no puede ser la identidad.

2.1.3 Inverso

En un grupo, el inverso de un elemento $(x,y)$ es el punto único $(x',y')$ que satisface

(x,y)\,\cdot\,(x',y') \;=\; (1,0).

En el círculo, vemos que

(x,-y)

sirve como el inverso de

(x,y)

con respecto a la operación de grupo. De hecho,

(x,y)\,\cdot\,(x,\,-y) \;=\; \bigl(x\,x - y\,(-y),\; x\,(-y) + y\,x\bigr) \;=\; \bigl(x^2 + y^2,\;0\bigr) \;=\; (1,0),

ya que

x^2 + y^2 = 1

.
Por lo tanto, el inverso de

(x,y)

bajo la operación de grupo es

(x,\,-y)

2.1.4 Asociatividad

El último axioma de grupo es la asociatividad: para cualesquiera tres puntos

$(x_0,y_0), (x_1,y_1), (x_2,y_2)$ en el círculo,

\bigl((x_0,y_0)\,\cdot\,(x_1,y_1)\bigr)\,\cdot\,(x_2,y_2) \;=\; (x_0,y_0)\,\cdot\,\bigl((x_1,y_1)\,\cdot\,(x_2,y_2)\bigr).

Esto puede verificarse expandiendo el polinomio, pero no entraremos en detalles aquí ya que sería demasiado extenso.

2.2 Una Operación Especial: El Mapeo de Cuadratura $\pi$

Más allá de estos axiomas de grupo, hay otra operación en el círculo que es particularmente útil en secciones posteriores, especialmente para la Circle FFT, a saber, el mapeo de cuadratura. Este mapeo aplica la operación de grupo a un punto consigo mismo:

\pi(x,y) \;=\; (x,y)\,\cdot\,(x,y) \;=\; \bigl(x^2 - y^2,\;2\,x\,y\bigr).

Dado que el círculo satisface $x^2 + y^2 = 1$ , obtenemos $x^2 - y^2 = 2x^2 - 1$ , por lo que

\pi(x,y) \;=\; \bigl(2\,x^2 - 1,\;2\,x\,y\bigr).

En la Circle FFT, usaremos $\pi$ para reducir a la mitad ciertos dominios de evaluación de manera recursiva—cada aplicación de $\pi$ reduce el tamaño del dominio por un factor de 2. Esto se debe a que $\pi$ es compatible con la operación de grupo. Concretamente, para dos puntos $P$ y $Q$ en el círculo,

\pi\bigl(P \cdot Q\bigr) \;=\; \pi(P) \;\cdot\; \pi(Q).

Esta compatibilidad implica que $\pi$ mapea un twin-coset de tamaño $2^n$ en otro twin-coset de tamaño $2^{n-1}$ . Volveremos a esta propiedad de reducción a la mitad del dominio en detalle más adelante.

2.3 Una Operación Especial: La Involución $J$

Además del mapeo de cuadratura, existe otra operación importante. Esta operación, llamada la involución, se define por

J(x,y) \;=\; (x,\;-y).

Geométricamente, invierte el signo de la coordenada

y

dejando inalterada la coordenada

x

. Nota que

J

es su propia inversa—aplicar

J

dos veces te devuelve al punto original:

J\bigl(J(x,y)\bigr) \;=\; J(x,\;-y) \;=\; (x,\;y).

En el círculo $x^2 + y^2 = 1$ , la involución $J(x,y)$ mantiene todos los puntos en la curva (ya que negar $y$ no afecta a $x^2 + y^2$ ). Sin embargo, un punto con $y=0$ permanece fijo bajo $J$ , lo que significa que $J(x,\,0) = (x,\,0)$ .

2.4 Operación Concreta del Grupo del Círculo en $p=31$

En el ejemplo concreto anterior, exploramos $C(\mathbb{F}_p)$ con $p = 7$ , que sirvió como un útil ejemplo de juguete para construir intuición. Sin embargo, $p = 7$ es demasiado pequeño para revelar las propiedades estructurales más profundas del Grupo del Círculo—como cadenas de subgrupos más largas o la construcción de twin-cosets o cosets en posición estándar.

Por lo tanto, ahora pasamos a un primo ligeramente más grande, $p = 31$ (que satisface $p = 2^5 - 1$ ), para ilustrar estos comportamientos más ricos de una manera más significativa.

Dado $p = 31$ , que es congruente con $3 \pmod{4}$ , el conjunto de puntos $(x, y) \in \mathbb{F}_{31}^2$ que satisfacen la ecuación $x^2 + y^2 = 1$ , denotado como $C(\mathbb{F}_{31})$ , se ilustra en el siguiente diagrama:

Aquí hay algunos ejemplos de pares $(x,y)$ en $\mathbb{F}_{31}^2$ que satisfacen $x^2 + y^2 \equiv 1 \pmod{31}$ :

$(5,10)$ también funciona porque $5^2 + 10^2 = 25 + 100 = 125$ , y $125 \bmod 31 = 125 - 4\cdot31 = 1$ .
$(7,13)$ también es una solución: $7^2 = 49 \equiv 18$ (mod 31) y $13^2 = 169 \equiv 14$ (mod 31), por lo que $18 + 14 = 32 \equiv 1$ (mod 31).
$(30,0)$ demuestra que $30 \equiv -1 \pmod{31}$ , por lo tanto $(-1)^2 + 0^2 \equiv 1$ (mod 31).

Para ver el Grupo del Círculo, trabajemos sobre $\mathbb{F}_{31}$ , donde el círculo $C(\mathbb{F}_{31})$ tiene 32 puntos. Supongamos que elegimos el punto

Q \;=\; (13,\,7).

Podemos combinar

Q

con el punto

(30,0)

a través de la operación de grupo:

(13,\,7) \,\cdot\,(30,\,0) \;=\; \bigl( 13 \cdot 30 - 7 \cdot 0,\;\; 13 \cdot 0 + 7 \cdot 30 \bigr) \;=\; (390,\,210) \;\equiv\; (18,\,24) \pmod{31}.

En efecto, uno verifica

18^2 + 24^2 \;\equiv\; 324 + 576 \;\equiv\; 900 \;\equiv\; 1 \pmod{31},

por lo que $(18,\,24)$ también yace en el círculo $x^2 + y^2 = 1$ .
Mientras tanto, el inverso de $Q$ es

Q^{-1} \;=\; (13,\,-7)\;\equiv\;(13,\,24)\pmod{31},

porque

(13,\,7)\,\cdot\,(13,\,24) \;=\; (1,\,0).

Adicionalmente, el mapeo de cuadratura puede funcionar en el punto $Q=(13,7)$ . Recuerda que

\pi(x,y) \;=\; (x,y)\,\cdot\,(x,y).

Por lo tanto,

\pi(Q) \;=\; (13,7)\,\cdot\,(13,7) \;=\; \bigl(13\cdot 13 - 7\cdot 7,\;13\cdot 7 + 7\cdot 13\bigr) \; \;\equiv\; (27,\,27) \pmod{31}.

3. Subgrupos del Grupo del Círculo

Hemos establecido que $C(\mathbb{F}_p)$ es un grupo cíclico de tamaño $p+1$ . Si $p + 1$ es una potencia de dos, digamos $p+1 = 2^m$ , entonces existe una cadena anidada de subgrupos

G_0 \;\subset\; G_1 \;\subset\; G_2 \;\subset\; \dots \;\subset\; G_m \;=\; C(\mathbb{F}_p)

donde cada

G_k

tiene un orden

|G_k| = 2^k

.
En otras palabras,

G_1

es un subgrupo de tamaño 2,

G_2

es de tamaño 4, y así sucesivamente, hasta

G_m = C(\mathbb{F}_p)

en sí mismo, que tiene un tamaño de

2^m = p+1

Por ejemplo, si $p = 31$ (así que $p+1 = 32 = 2^5$ ), obtenemos una cadena

G_0,\,G_1,\,G_2,\,G_3,\,G_4,\,G_5

donde

G_5 = C(\mathbb{F}_{31})

y cada

G_k

tiene tamaño

2^k

. Un resumen podría verse así:

$k$	$\lvert G_k\rvert = 2^k$
$G_0$	1
$G_1$	2
$G_2$	4
$G_3$	8
$G_4$	16
$G_5$	32

A continuación, listamos explícitamente cada subgrupo en $C(\mathbb{F}_{31})$ .

Size 1:  [Point(1, 0)]
Size 2:  [Point(1, 0), Point(30, 0)]
Size 4:  [Point(1, 0), Point(0, 30), Point(30, 0), Point(0, 1)]
Size 8:  [Point(1, 0), Point(4, 27), Point(0, 30), Point(27, 27), Point(30, 0), Point(27, 4), Point(0, 1), Point(4, 4)]
Size 16:  [Point(1, 0), Point(7, 13), Point(4, 27), Point(18, 24), Point(0, 30), Point(13, 24), Point(27, 27), Point(24, 13), Point(30, 0), Point(24, 18), Point(27, 4), Point(13, 7), Point(0, 1), Point(18, 7), Point(4, 4), Point(7, 18)]
Size 32:  [Point(1, 0), Point(2, 11), Point(7, 13), Point(26, 10), Point(4, 27), Point(21, 5), Point(18, 24), Point(20, 29), Point(0, 30), Point(11, 29), Point(13, 24), Point(10, 5), Point(27, 27), Point(5, 10), Point(24, 13), Point(29, 11), Point(30, 0), Point(29, 20), Point(24, 18), Point(5, 21), Point(27, 4), Point(10, 26), Point(13, 7), Point(11, 2), Point(0, 1), Point(20, 2), Point(18, 7), Point(21, 26), Point(4, 4), Point(26, 21), Point(7, 18), Point(2, 20)]

4. Código Python 1: Grupo del Círculo

Ahora revisaremos el código del Grupo del Círculo a través de una implementación sencilla en Python. Solo se describen las funciones o partes más importantes aquí, y todo el código está disponible aquí.

Aquí, definimos dos clases clave — FieldElement y CirclePoint — para manejar la aritmética en el campo finito subyacente y las operaciones de grupo en la curva, respectivamente.

4.1 FieldElement

Primero, la clase FieldElement define las operaciones aritméticas en el campo finito $\mathbb{F}_{31}$ , tales como la suma, multiplicación e inversión módulo 31. Esta es la base para todos los cálculos en la curva del círculo.

# Mersenne 5
MOD = 31

class FieldElement:
    def __init__(self, value):
        """Initialize a field element"""
        self.value = value % MOD

    def __add__(self, other):
        """Add two field elements"""
        return FieldElement((self.value + other.value) % MOD)

    def __mul__(self, other):
        """Multiply two field elements"""
        return FieldElement((self.value * other.value) % MOD)

    def inv(self):
        """Compute the multiplicative inverse"""
        return FieldElement(pow(self.value, MOD - 2, MOD))

    def square(self):
        """Compute the square"""
        return self * self

4.2 CirclePoint

La clase CirclePoint representa puntos en la curva del círculo $x^2+y^2=1$ . El método add implementa la operación de grupo, mientras que double aplica el mapeo de cuadratura.

class CirclePoint:
    def __init__(self, x, y):
        """Initialize a point on the circle x^2 + y^2 = 1"""
        if (x.square() + y.square()).value != 1:
            raise ValueError("Point does not lie on the circle")
        self.x = x
        self.y = y

    def add(self, other):
       """Perform group operation: (x1,y1)・(x2,y2) = (x1*x2 - y1*y2, x1*y2 + x2*y1)."""
        nx = self.x * other.x - self.y * other.y
        ny = self.x * other.y + other.x * self.y
        return CirclePoint(nx, ny)

    def double(self):
        """Apply squaring map: π(x,y) = (2*x^2 - 1, 2*x*y), since x^2 + y^2 = 1."""
        xx = self.x.square().double() - FieldElement.one()
        yy = self.x.double() * self.y
        return CirclePoint(xx, yy)

    @classmethod
    def identity(cls):
        """Return the identity element (1, 0) of the circle group."""
        return cls(FieldElement.one(), FieldElement.zero())

Luego puedes simular un ejemplo de la operación del Grupo del Círculo tal como se describe en la sección 2.4.

Por ejemplo, sumar el CirclePoint $(13, 7)$ y el CirclePoint $(30, 0)$ resulta en el Point $(18, 24)$ .

p1 = CirclePoint(FieldElement(13), FieldElement(7))
p2 = CirclePoint(FieldElement(30), FieldElement(0))

# group operation
p3 = p1.add(p2)
print(f"p1・p2 = {p3}")

p1・p2 = Point(18, 24)

Duplicar $p1=(13,7)$ da como resultado $(27, 27)$

# squaring map
p1_double = p1.double()
print(f"π(p1) = {p1_double}")

π(p1) = Point(27, 27)

El inverso de $(13, 7)$ es $(13, 24)$ , y sumarlos da la identidad $(1, 0)$

# Inverse
p1_inv = p1.inverse()
print(f"p1's inverse = {p1_inv}")
p1_plus_inv = p1.add(p1_inv)
print(f"p1・p1_inv = {p1_plus_inv}")

p1's inverse = Point(13, 24)
p1・p1_inv = Point(1, 0)

4.3 Grupo del Círculo

La función generate_subgroup genera un subgrupo $G_k$ de orden $2^k$ . Obtiene el generador apropiado de la función get_nth_generator y repite la operación de grupo add para construir el subgrupo.

def generate_subgroup(k: int) -> list[CirclePoint]:
    """Generate a subgroup of size 2^k using the generator."""
    g_k = get_nth_generator(k)
    p = CirclePoint.identity()
    return [ (p := p.add(g_k)) if i else p
             for i in range(1 << k) ]

Por ejemplo, puedes obtener el subgrupo de tamaño 8.

G3 = generate_subgroup(3)

Size 8:  [Point(1, 0), Point(4, 27), Point(0, 30), Point(27, 27), Point(30, 0), Point(27, 4), Point(0, 1), Point(4, 4)]

5. Cosets, Twin-Cosets y Cosets en Posición Estándar

Los Twin-Cosets y los Cosets en Posición Estándar son los dominios en Circle STARKs. Revisemos brevemente cómo se utilizan los dominios en los STARKS tradicionales antes de entender las propiedades matemáticas de los twin-cosets y los cosets en posición estándar. Como se discutió en la Sección 0, los STARKS tradicionales típicamente utilizaban (sub)grupos multiplicativos representados como $\mathbb{F}_p^*$ como sus dominios. Estos dominios servían principalmente para dos propósitos.

En primer lugar, actuaban como el dominio de evaluación al construir polinomios a partir de la traza computacional vía IFFT, y tenemos que realizar la Extensión de Bajo Grado (LDE) con el dominio extendido vía FFT, y además construimos polinomios de restricciones y los evaluamos sobre la LDE.

En segundo lugar, en la Prueba de Bajo Grado, particularmente con los compromisos de FRI, los polinomios deben ser evaluados vía FFT sobre dominios que se reducen iterativamente a la mitad durante los pasos recursivos de plegado de FRI.

Además, durante los pasos de plegado de FRI, a medida que el grado del polinomio se reducía a la mitad, el tamaño del dominio también necesitaba reducirse a la mitad. Reducir a la mitad el tamaño del dominio es fundamental tanto para FRI como para FFT. Ten esto en cuenta a medida que avanzamos.

Porque si bien el grupo del círculo en sí ya ofrece una alta 2-adicidad, la construcción de Twin-Cosets o Cosets en Posición Estándar asegura que, durante los pasos de cuadratura recursiva en la FFT, los dominios de evaluación (es decir, los Twin-Cosets o Cosets en Posición Estándar) también puedan ser reducidos a la mitad en tamaño mientras preservan su estructura de coset. Esto es esencial para permitir operaciones tipo FFT sobre estos dominios en cada nivel de la recursión.

5.1 Coset

Recordemos la definición de un coset en la teoría de grupos. Supongamos que $H$ es un subgrupo de un grupo $\mathcal{G}$ , y sea $Q \in \mathcal{G}$ . Entonces el coset izquierdo de $H$ por $Q$ es el conjunto

Q \,\cdot\, H \;=\; \{\,Q \cdot h \;\mid\; h \in H\}.

Si $Q \in H$ , entonces $Q \cdot H = H$ . De lo contrario, en el caso de $Q \notin H$ , $Q \cdot H$ es un conjunto disjunto de $H$ , pero aún tiene el mismo tamaño que $H$ . Esto se cumple porque si $Q \in H$ , la clausura de $H$ bajo la operación de grupo asegura que $Q \cdot H = H$ , mientras que si $Q \notin H$ , ningún elemento de $Q \cdot H$ puede estar en $H$ sin implicar $Q \in H$ , y la biyección $h \mapsto Q \cdot h$ preserva el tamaño.

En nuestro entorno particular, $\mathcal{G} = C(\mathbb{F}_p)$ , que es cíclico de tamaño $p+1$ . De la sección anterior, sabemos que hay una cadena de subgrupos $G_0 \subset G_1 \subset \dots \subset G_m$ con $|G_k| = 2^k$ .

Por lo tanto, por ejemplo, si fijamos $G_{n-1}$ de orden $2^{n-1}$ , entonces para cualquier punto $Q$ en el círculo, el coset

Q \,\cdot\, G_{n-1} \;=\; \bigl\{Q\cdot g \;\mid\; g\in G_{n-1}\bigr\}

se llama un coset de $G_{n-1}$ .
Ese conjunto tendrá la misma cardinalidad $2^{n-1}$ , y es disjunto de $G_{n-1}$ en sí mismo a menos que $Q$ ya pertenezca a $G_{n-1}$ .

5.1.1 Ejemplo de Coset

Vamos a ilustrar este ejemplo rápidamente. En el caso $p=31$ , recuerda que $p+1=32=2^5$ , por lo que existe una cadena de subgrupos $G_1, G_2, \dots, G_5$ donde $|G_1|=2$ . Concretamente,

G_1 \;=\; \{\,(1,0),\,(30,0)\}.

Ahora tomemos un punto $Q$ que no está en $G_1$ . Por ejemplo,

Q \;=\; (2,\,11).

Dado que $Q$ no está en $G_1$ , el conjunto

Q \,\cdot\, G_1 \;=\; \{\,(2,11)\cdot(1,0),\,(2,11)\cdot(30,0)\}

será un coset distinto de $G_1$ , disjunto de $G_1$ mismo.

$(2,11)\cdot(1,0) \;=\; (\,2\cdot1 - 11\cdot0,\;\;2\cdot0 + 11\cdot1) \;=\; (2,\,11),$
$(2,11)\cdot(30,0) \;=\; (\,2\cdot30 - 11\cdot0,\;\;2\cdot0 + 30\cdot11) \;\equiv\; (29,\,20) \;\pmod{31}.$

Por lo tanto,

Q \cdot G_1 \;=\; \{(2,\,11),\,(29,\,20)\},

lo cual efectivamente tiene un tamaño de 2. Este es el coset de $G_1$ correspondiente a $Q=(2,11)$ , claramente diferente del subgrupo $G_1$ mismo.

5.2 Twin-Cosets

Ahora definimos un twin-coset tomando la unión de dos cosets: $Q \cdot G_{n-1}$ y su coset inverso $Q^{-1} \cdot G_{n-1}$ . Concretamente, sea

D \;=\; \bigl(Q \,\cdot\, G_{n-1}\bigr) \;\cup\; \bigl(Q^{-1} \,\cdot\, G_{n-1}\bigr).

Decimos que

D

es un twin-coset de tamaño

2^n

si se cumplen las siguientes condiciones:

Disyunción
Los dos cosets $Q \cdot G_{n-1}$ y $Q^{-1} \cdot G_{n-1}$ son disjuntos.
En la práctica, esta disyunción equivale a asegurar que $Q^2 \notin G_{n-1}$ . Esta equivalencia surge de las propiedades de los cosets. Si $Q^2 \in G_{n-1}$ , entonces $Q = Q^{-1} \cdot Q^2$ estaría tanto en $Q \cdot G_{n-1}$ como en $Q^{-1} \cdot G_{n-1}$ (solapamiento). A la inversa, si los cosets no se solapan, entonces $Q$ no se puede escribir como $Q^{-1} \cdot g$ (para ningún $g \in G_{n-1}$ ), lo que implica $Q^2 \notin G_{n-1}$ .
Sin puntos fijos bajo la involución $J$
Un punto $P$ se llama punto fijo de un mapeo $f$ si $f(P) = P$ . En nuestro caso, consideramos la involución $J(x,y) \;=\; \bigl(x,\;-y\bigr).$
Si $D$ contuviera algún punto donde $y=0$ , entonces $J(x,0) = (x,0)$ permanecería inalterado. Es un punto fijo. Queremos evitar tener tales puntos en $D$ , porque por definición un twin-coset excluye cualquier punto fijo de $J$ .

Bajo estas condiciones, cada coset $Q \cdot G_{n-1}$ y $Q^{-1} \cdot G_{n-1}$ tiene $2^{n-1}$ puntos distintos, dando un total de $2^n$ puntos en $D$ . Intuitivamente, fusionamos un coset con su coset inverso, formando un dominio de $2^n$ elementos.

5.2.1 Ejemplo de Twin-Coset

Continuando con el ejemplo del coset de la Sección 5.1.1 (donde escogimos $Q=(2,11)$ que no está en $G_1$ ), formemos ahora un twin-coset de tamaño $2^n = 2^2 = 4$ . Ya vimos que:

Q \cdot G_1 \;=\; \{(2,\,11),\,(29,\,20)\}.

A continuación, calculemos

Q^{-1}=(2,\,20)

y formemos el coset

Q^{-1}\cdot G_1

Q^{-1} \,\cdot\, G_1 \;=\; \{\,(2,20)\cdot(1,0),\,(2,20)\cdot(30,0)\}

$(2,20)\cdot(1,0)\;=\;\bigl(2\cdot1 \;-\;20\cdot0,\;\;2\cdot0 \;+\;1\cdot20\bigr)\;=\;(2,\,20).$
$(2,20)\cdot(30,0)\;=\;\bigl(2\cdot30 \;-\;20\cdot0,\;\;2\cdot0 \;+\;30\cdot20\bigr)\;=\;(60,\,600)\;\equiv\;(29,\,11)\;\pmod{31}.$

Por lo tanto,

Q^{-1}\cdot G_1 \;=\; \{(2,\,20),\,(29,\,11)\}.

Tomando la unión, el twin-coset es:

D \;=\; \bigl(Q \cdot G_1\bigr) \;\cup\; \bigl(Q^{-1}\cdot G_1\bigr) \;=\; \{(2,\,11),\,(29,\,20)\} \;\cup\; \{(2,\,20),\,(29,\,11)\}.

Este dominio

D

tiene un tamaño de 4 y satisface las condiciones del twin-coset: los dos cosets son disjuntos (ya que

Q^2\notin G_1

), y

D

no contiene ningún punto con

y=0

, por lo que no hay puntos fijos bajo la involución

J(x,y)=(x,-y)

. Así,

D

es en efecto un twin-coset de tamaño

2^2=4

5.3 Cosets en Posición Estándar

Un coset en posición estándar es un tipo especial de twin-coset $D$ de tamaño $2^n$ que también coincide con un único coset del subgrupo $G_n$ :

D \;=\; Q \cdot G_{n-1} \;\cup\; Q^{-1}\cdot G_{n-1} \;=\; Q \cdot G_n.

Aquí, recuerda que $G_n$ es el único subgrupo de $C(\mathbb{F}_p)$ de orden $2^n$ , como se introdujo anteriormente en la Sección 3. Tenemos una cadena de subgrupos:

G_0 \subset G_1 \subset \dots \subset G_n \subset \dots \subset C(\mathbb{F}_p),

y cada $G_k$ es de tamaño $2^k$ . Entonces, $G_n$ contiene a $G_{n-1}$ , y relacionaremos los cosets de estos subgrupos usando un punto $Q$ de orden $2^{n+1}$ .

Desglosemos esto paso a paso:

Primero, dado que $G_{n-1} \subset G_n$ , podemos ver a $G_n$ como compuesto por dos cosets disjuntos de $G_{n-1}$ , a saber:

G_n = G_{n-1} \cup R \cdot G_{n-1},\quad \text{para algún } R \notin G_{n-1}.

Si ahora multiplicamos esto por un punto fijo

Q

de orden

2^{n+1}

, obtenemos:

Q \cdot G_n = Q \cdot G_{n-1} \cup Q \cdot R \cdot G_{n-1}.

Resulta que $Q \cdot R = Q^{-1}$ , por lo tanto:

Q \cdot G_n = Q \cdot G_{n-1} \cup Q^{-1} \cdot G_{n-1}.

Por consiguiente, el coset $Q \cdot G_n$ se puede escribir como la unión de dos cosets disjuntos: uno por $Q$ , el otro por $Q^{-1}$ , cada uno sobre el subgrupo más pequeño $G_{n-1}$ . Esta es exactamente la definición de un twin-coset.

Pero no todos los twin-cosets surgen de esta manera. Para asegurar que esta construcción funcione correctamente, requerimos:

Disyunción: $Q^2 \notin G_{n-1}$ . De lo contrario, los dos cosets se solaparían.
Sin puntos fijos bajo la involución: El conjunto resultante $D$ debe evitar los puntos con $y = 0$ , para que la involución $J(x, y) = (x, -y)$ no tenga puntos fijos en $D$ .
Orden correcto: $Q$ debe tener orden $2^{n+1}$ para garantizar que $Q \cdot G_n$ abarque exactamente $2^n$ elementos distintos.

Cuando se satisfacen estos requisitos, el coset $D = Q \cdot G_n$ proporciona un coset en posición estándar: un dominio de tamaño $2^n$ que es simultáneamente un twin-coset y un solo coset de un subgrupo más grande.

5.4 Ejemplo Calculado a Mano: Twin-Cosets y Cosets en Posición Estándar en $p=31$

A continuación, ilustramos cómo se aplican las nociones de twin-cosets y cosets en posición estándar cuando $p=31.$ Tenemos $p+1=32=2^5$ , por lo que existen los subgrupos $G_1,\,G_2,\,G_3,\,G_4,\,G_5$ , donde $|G_3|=8$ y $|G_2|=4$ . Mostraremos el coset en posición estándar para $G_3$ que es $D=Q \cdot G_2 \;\cup\; Q^{-1} \cdot G_2=Q \cdot G_3$ .

5.4.1 Construcción del Twin-Coset

Configuración
Sea $n=3$ . Entonces $G_2$ tiene tamaño 4. Escoge un punto $Q$ de orden 16 (por lo tanto $Q\notin G_3$ , pero $Q \in G_4$ ). Concretamente, uno puede elegir $Q = (13,\,7)$
Formando el Twin-Coset

$D= \bigl(Q \cdot G_2\bigr) \;\cup\; \bigl(Q^{-1}\cdot G_2\bigr).$

Puesto que $G_2$ tiene los cuatro puntos $(1,0)$ , $(0,30)$ , $(30,0)$ , y $(0,1)$ , cada punto se multiplica por $Q = (13,\,7)$ o $Q^{-1}=(13,24)$ .
1. $Q \cdot (1,0)=(13,7)$ ,
2. $Q \cdot (0,30)=(7,18)$ ,
3. $Q \cdot (30,0)=(18,24)$ ,
4. $Q \cdot (0,1)=(24,13)$ ,
5. $Q^{-1}\cdot(1,0)=(13,24)$ ,
6. $Q^{-1}\cdot(0,30)=(24,18)$ ,
7. $Q^{-1}\cdot(30,0)=(18,7)$ ,
8. $Q^{-1}\cdot(0,1)=(7,13)$ .

D= \bigl(Q \cdot G_2\bigr) \;\cup\; \bigl(Q^{-1}\cdot G_2\bigr)= \{(13,7),(7,18),(18,24),(24,13),(13,24),(24,18),(18,7),(7,13)\}

Combinar estos produce 8 puntos distintos. Ningún elemento de $D$ está fijo por $J$ , por lo tanto $D$ es un twin-coset de tamaño $2^3=8$ . Combinar estos produce 8 puntos distintos. Ningún elemento de $D$ está fijo por $J$ , por lo tanto $D$ es un twin-coset de tamaño $2^3 = 8$ .

En el diagrama a continuación, los puntos rojos 🔴 representan $Q \cdot G_2$ y los puntos azules 🔵 representan $Q^{-1} \cdot G_2$ . Juntos, forman el twin-coset $D$ de 8 puntos.

5.4.2 Verificación del Coset en Posición Estándar

Este mismo $D$ también es igual a $Q\cdot G_3$ para algún subgrupo $G_3$ de tamaño 8, lo que significa que $D$ es un coset en posición estándar.

$G_3$ es el subgrupo $\{(1,0),(4,27),(0,30),(27,27),(30,0),(27,4),(0,1),(4,4)\}$ , entonces multiplicar cada elemento por $Q=(13,7)$ produce exactamente los 8 puntos en $D$ .

$Q \cdot (1,\,0) = (13,\,7)$
$Q \cdot (4,\,27) = (18,\,7)$
$Q \cdot (0,\,30) = (7,\,18)$
$Q \cdot (27,\,27) = (7,\,13)$
$Q \cdot (30,\,0) = (18,\,24)$
$Q \cdot (27,\,4) = (13,\,24)$
$Q \cdot (0,\,1) = (24,\,13)$
$Q \cdot (4,\,4) = (24,\,18)$

Q \cdot G_3 \;=\; \{ (13,7),\,(18,7),\,(7,18),\,(7,13), (18,24),\,(13,24),\,(24,13),\,(24,18) \}.

Por lo tanto

D= Q\cdot G_3 = Q\cdot G_2 \;\cup\; Q^{-1}\cdot G_2.

Debido a que $D$ es tanto un twin-coset de $G_2$ como un coset único de $G_3$ , lo llamamos un coset en posición estándar de tamaño 8.

En el diagrama a continuación, los puntos verdes 🟢 representan el subgrupo $G_3$ , y los puntos rojos 🔴 y azules 🔵 representan los dos cosets disjuntos $Q \cdot G_2$ y $Q^{-1} \cdot G_2$ , respectivamente. Su unión forma el twin-coset $D$ , y el conjunto completo de 8 puntos constituye el coset en posición estándar $Q \cdot G_3$ .

Por lo tanto, siempre que $Q$ tenga un orden de $2^{n+1}$ , podemos construir un coset en posición estándar de tamaño $2^n$ . Esta estructura es importante en Circle STARK, ya que proporciona un dominio limpio de $2^n$ puntos incluso si $p-1$ no es lo suficientemente 2-ádico.

6. Código Python 2: Dominio del Círculo

Ahora revisaremos el código del Dominio del Círculo a través de una implementación sencilla en Python. La construcción del dominio (tal como twin-coset y el coset en posición estándar) también está implementada en el mismo notebook de Python. Puedes ejecutar e inspeccionar cómo se construyen estos conjuntos paso a paso.

6.1 Twin-Coset

Esta función genera un dominio aplicando las operaciones de grupo add a $Q$ y su inverso $Q^{-1}$ sobre el subgrupo, asegurando simetría y un tamaño $2^n$ .

def generate_twin_coset(Q, G_n_minus_1):
    """Generate twin-coset: D = Q・G_(n-1) ∪ Q^{-1}・G_(n-1)."""
    Q_inv = Q.inverse()
    coset_Q = [Q.add(g) for g in G_n_minus_1]
    coset_Q_inv = [Q_inv.add(g) for g in G_n_minus_1]
    return coset_Q + coset_Q_inv

G2 = generate_subgroup(2)
Q = CirclePoint(FieldElement(13), FieldElement(7))
twin_cosets = generate_twin_coset(Q, G2)
print(twin_cosets)

[Point(13, 7), Point(7, 18), Point(18, 24), Point(24, 13), Point(13, 24), Point(24, 18), Point(18, 7), Point(7, 13)]

6.2 Coset en Posición Estándar

Esta función genera el coset en posición estándar aplicando la operación de grupo add para $Q$ y el subgrupo.

def generate_standard_position_coset(Q, G_n):
    """Generate standard position coset D = Q・G_n."""
    return [Q.add(g) for g in G_n]

G3 = generate_subgroup(3)
Q = CirclePoint(FieldElement(13), FieldElement(7))
D = generate_standard_position_coset(Q, G3)

[Point(13, 7), Point(18, 7), Point(7, 18), Point(7, 13), Point(18, 24), Point(13, 24), Point(24, 13), Point(24, 18)]

Con este tipo de código, puedes comprobar la igualdad del coset en posición estándar $D \;=\;Q \,\cdot\, G_{n-1}\;\cup\;Q^{-1} \,\cdot\, G_{n-1}\;=\;Q \,\cdot\, G_n.$

D_std = generate_standard_position_coset(Q, G3)
D_twin = generate_twin_coset(Q, G2)
print("Q・G3:", D_std)
print("(Q・G2) ∪ (Q^-1・G2):", D_twin)
if set(D_std) == set(D_twin):
    print("Equal: standard position coset Q·G3 = Q·G2 ∪ Q^-1·G2")
else:
    print("Not Equal")

7. Descomposición de un Coset en Posición Estándar Mayor en Twin-Cosets Menores

En muchos pasos de la Circle FFT y FRI, necesitamos gestionar dominios de evaluación de diferentes tamaños, todos los cuales se encuentran en la curva del círculo. Un método clave para lograr esto es el Lema 2 del documento de Circle STARKs, el cual asegura que un coset en posición estándar de tamaño $2^m$ puede dividirse en twin-cosets más pequeños de tamaño $2^n$ para cualquier $n \le m$ .

7.1 Enunciado del Lema 2

Sea $D \subset C(\mathbb{F}_p)$ un coset en posición estándar de tamaño $2^m$ . Entonces, para cualquier $n \le m$ , se puede descomponer $D$ en twin-cosets de tamaño $2^n$ . Concretamente, si

D \;=\; Q \cdot G_m \quad \text{donde}\quad |G_m| = 2^m,

entonces

D = \bigcup_{k=0}^{\left(\frac{2^m}{2^n}\right)-1} \Bigl( Q^{4k+1} \cdot G_{n-1} \cup Q^{-(4k+1)} \cdot G_{n-1} \Bigr)

En términos más simples, si $D$ es un coset en posición estándar de tamaño $2^m$ , podemos cortarlo en twin-cosets más pequeños (cada uno de tamaño $2^n$ ) utilizando potencias de $Q$ . Este particionamiento permite crear precisamente las partes de $D$ que se necesitan en un paso dado del protocolo Circle FFT.

7.2 Ejemplo Calculado a Mano: Dividiendo un coset en posición estándar de Tamaño $8$ en 2 Twin-Cosets de Tamaño $4$

Supongamos que $p = 31$ , de modo que $p+1 = 32 = 2^5$ . Tenemos subgrupos $G_1, G_2, G_3, \dots$ , donde $\lvert G_3\rvert=8$ .

Nuestro coset en posición estándar
Sea $D = Q \cdot G_3$ con $\lvert D\rvert=8$ . Aquí, $Q$ tiene orden $16$ , lo que significa que $Q\notin G_3$ pero $Q \cdot G_3$ forma un coset de tamaño $8$ .

D= \bigl(Q \cdot G_2\bigr) \;\cup\; \bigl(Q^{-1}\cdot G_2\bigr)= Q\cdot G_3 = \{(13,7),(7,18),(18,24),(24,13),(13,24),(24,18),(18,7),(7,13)\}

Objetivo
Romper $D$ en twin-cosets de tamaño $2^n=4$ . Sea $n=2$ , así que $\lvert G_2\rvert=4$ y $\lvert G_1\rvert=2$ .
Entonces el Lema 2 sugiere

$D= \bigcup_{k=0}^{(8/4)-1} \Bigl( Q^{\,4k+1}\cdot G_{1} \;\cup\; Q^{-\,\bigl(4k+1\bigr)}\cdot G_{1} \Bigr).$

Dado que $8/4=2$ , tenemos $k=0$ y $k=1$ .

7.2.1 Caso $k=0$

$Q^{4\cdot0+1}=Q^1=Q$ .
$G_1=\{(1,0), (30,0)\}$ .

Calculamos:

$Q\cdot(1,0) = (13,7)$
$Q\cdot(30,0) = (18,24)$
$Q^{-1}\cdot(1,0) = (13,24)$
$Q^{-1}\cdot(30,0) = (18,7)$

Así, el primer twin-coset tiene 4 puntos distintos.

7.2.2 Caso $k=1$

$Q^{4\cdot1+1} = Q^5$ .
Eso es $Q^5 = (24,13)$ .
Del mismo modo, $Q^{-5} = (24, -13)\equiv (24,18)$ .

De nuevo, multiplicamos cada uno por $(1,0)$ y $(30,0)$ :

$Q^5\cdot(1,0) = (24,13)$
$Q^5\cdot(30,0) = (7,18)$
$Q^{-5}\cdot(1,0) = (24,18)$
$Q^{-5}\cdot(30,0) = (7,13)$

Esto produce otros 4 puntos, formando el segundo twin-coset de tamaño 4.

7.2.3 Unión de los Dos Twin-Cosets

Tomar la unión de ambos conjuntos de 4 puntos (para $k=0$ y $k=1$ ) recupera todo el coset de 8 elementos $D$ . Por lo tanto:

D=\Bigl( Q^1 \cdot G_1 \;\cup\; Q^{-1} \cdot G_1 \Bigr) \;\;\cup\;\; \Bigl( Q^5 \cdot G_1 \;\cup\; Q^{-5} \cdot G_1 \Bigr).

Esto coincide exactamente con el enunciado del Lema 2, mostrando cómo un coset en posición estándar de 8 puntos puede ser descompuesto en dos twin-cosets, cada uno de tamaño 4.

7.3 Ejemplo Calculado a Mano: Dividiendo un coset en posición estándar de Tamaño $8$ en 4 Twin-Cosets de Tamaño $2$

Y también podemos dividir este coset en posición estándar de tamaño 8 en múltiples twin-cosets más pequeños.

Sea $n=1$ , así que $\lvert G_1\rvert=2$ . El Lema 2 da:

D = \bigcup_{k=0}^{(8/2)-1} \Bigl( Q^{4k+1}\cdot G_0 \;\cup\; Q^{-\,(4k+1)}\cdot G_0 \Bigr).

Dado que $G_0 = \{(1,0)\}$ , cada twin-coset tiene 2 puntos:

$k=0$ : $\{Q^1 \cdot G_0 = Q, Q^{-1} \cdot G_0 = Q^{-1}\}$ $=\{(13, 7), (13, 24)\}$
$k=1$ : $\{Q^5 \cdot G_0 = Q^5, Q^{-5} \cdot G_0 = Q^{-5}\}$ $
={(24, 13), (24, 18)}$
$k=2$ : ${Q^9 \cdot G_0 = Q^9, Q^{-9} \cdot G_0 = Q^{-9}}
$ $=\{(18, 24), (18, 7)\}$
$k=3$ : $\{Q^{13} \cdot G_0 = Q^{13}, Q^{-13} \cdot G_0 = Q^{-13}\}$ $
={(7, 18), (7, 13)}$
$D = \{(13,7),(13,24)\} \cup \{(24,13),(24,18)\} \cup \{(18,24),(18,7)\} \cup \{(7,18),(7,13)\}$
Esto descompone $D$ en cuatro twin-cosets de tamaño $2$ .

8. El Mapeo de Cuadratura Reduce a la Mitad un Twin-Coset

Mientras que el Lema 2 se centra en dividir cosets grandes en twin-cosets más pequeños, el Lema 3 explota un mapeo de cuadratura para reducir a la mitad el tamaño de un twin-coset. Este proceso se utiliza para los pasos de reducción a la mitad del dominio en la Circle FFT, donde reducimos iterativamente el tamaño del dominio.

8.1 Enunciado del Lema 3

Este lema aparece en el documento de Circle STARKs, donde se utiliza para formalizar la reducción iterativa del dominio que es habilitada por el mapeo de cuadratura.
Supongamos que $D$ es un twin-coset de tamaño $2^n$ (con $n \ge 2$ ). Entonces la aplicación del mapeo de cuadratura $\pi(x,y) = (x^2 - y^2,\,2xy)$ transforma a $D$ en otro twin-coset $\pi(D)$ de tamaño $2^{n-1}$ . Además, si $D$ era un coset en posición estándar, entonces $\pi(D)$ también sigue siendo un coset en posición estándar.
Intuitivamente, $\pi$ es un endomorfismo de grupo, y mapea un subgrupo $G_{n-1}$ hacia $G_{n-2}$ . Por lo tanto, un twin-coset de tamaño $2^n$ produce naturalmente otro twin-coset de tamaño $2^{n-1}$ .

8.1.1 Vista Abstracta de la Demostración del Lema 3

Sea $D$ un twin-coset de tamaño $2^n$ , que en notación abstracta significa

D = Q \cdot G_{n-1} \;\cup\; Q^{-1}\cdot G_{n-1},

donde

|G_{n-1}| = 2^{n-1}

.
En particular,

\pi

mapea el subgrupo

G_{n-1}

hacia

G_{n-2}

debido a un endomorfismo de grupo.

\pi(D) \;=\; \pi\!\Bigl(Q \cdot G_{n-1} \cup Q^{-1}\cdot G_{n-1}\Bigr)= \bigl(\pi(Q) \cdot G_{n-2}\bigr) \;\cup\; \bigl(\pi(Q)^{-1} \cdot G_{n-2}\bigr).

Esta es exactamente la definición de un twin-coset en el subgrupo

G_{n-2}

, que tiene un tamaño de

2^{n-2}

. En consecuencia,

\pi(D)

es en sí mismo un twin-coset de tamaño

2^{n-1}

.
Si

D

fue originalmente un coset en posición estándar, entonces la aplicación de

\pi

preserva esa propiedad de posición estándar, porque

\pi(G_n) = G_{n-1}

. Así,

\pi(D)

es nuevamente un coset en posición estándar, pero ahora de tamaño

2^{n-1}

8.2 Ejemplo Calculado a Mano (Reduciendo un Twin-Coset de Tamaño $8$ a Tamaño $4$ )

Asume $p=31$ y sea $D$ un twin-coset de tamaño $2^3=8$ . Concretamente,

D = Q\cdot G_2 \;\cup\; Q^{-1}\cdot G_2 \quad\text{con}\quad Q=(13,7).

Dado que

\lvert G_2\rvert=4

, tenemos

\lvert D\rvert=8

. Verificamos cómo

\pi

afecta a

D

8.2.1 Cálculo de $\pi(Q)$ y $\pi(Q^{-1})$

\pi(Q)= \bigl(13^2 - 7^2,\;2\cdot13\cdot7\bigr)= (27,\,27),

\pi(Q^{-1})= (27,\,4).

8.2.2 Aplicación de $\pi$ a $D$

El subgrupo $G_1$ tiene un tamaño de 2, digamos $G_1 = \{(1,0), (30,0)\}$ . Por el Lema 3,

\pi(D) = \bigl(\pi(Q)\cdot G_1\bigr) \cup \bigl(\pi(Q)^{-1}\cdot G_1\bigr).

$$
\begin{align*}
\pi(Q)\cdot(1,0) &= (27,27)\
\pi(Q)\cdot(30,0) &= (4,4)\
\pi(Q^{-1})\cdot(1,0) &= (27,4)\
\pi(Q^{-1})\cdot(30,0) &= (4,27)

\end{align*}

{(27,27), (4,4)}
\cup
{(27,4), (4,27)}$$
el cual es un twin-coset de tamaño 4.
Por lo tanto,

\pi

reduce

D

a la mitad, pasando de 8 elementos a 4, exactamente como afirma el Lema 3. La aplicación repetida de

\pi

continúa reduciendo el dominio en potencias de 2, desempeñando un papel crítico en la estructura recursiva de la Circle FFT.
En el diagrama a continuación:

El círculo izquierdo muestra el twin-coset original $D = Q \cdot G_2 \cup Q^{-1} \cdot G_2$ , donde el rojo 🔴 = $Q \cdot G_2$ y el azul 🔵 = $Q^{-1} \cdot G_2$ .
El círculo derecho muestra el twin-coset reducido a la mitad $\pi(D)$ , donde el azul 🔵 = $\pi(Q) \cdot G_1$ y el rojo 🔴 = $\pi(Q^{-1}) \cdot G_1$ .
Los puntos negros ⚫ marcan el subgrupo $G_1 = \{(1, 0), (30, 0)\}$ .
Este visual ilustra cómo $\pi$ mapea el dominio original de tamaño $2^3 = 8$ a un nuevo twin-coset de tamaño $2^2 = 4$ mediante el endomorfismo de grupo.

9. Lo Que Construimos en la Parte 1

En este artículo, nos centramos en cómo la curva del círculo $x^2 + y^2 = 1$ sobre $\mathbb{F}_p$ puede convertirse en un grupo cíclico de tamaño $p + 1$ , y discutimos los twin-cosets y cosets en posición estándar con ejemplos concretos. También mostramos dos técnicas clave: una para dividir un coset en posición estándar más grande en twin-cosets más pequeños, y otra para reducir a la mitad el tamaño de un twin-coset aplicando el mapeo de cuadratura. Juntas, estas técnicas nos permiten remodelar dominios de tamaño $2^n$ a voluntad.
En la próxima parte, nos sumergiremos más a fondo en la propia Circle FFT, mostrando cómo estos dominios de tamaño $2^n$ —junto con la capacidad de dividirlos o reducirlos a la mitad—permiten una rápida evaluación e interpolación de polinomios, incluso cuando $p - 1$ no es suficientemente 2-ádico.

Referencias

Circle STARKs
https://eprint.iacr.org/2024/278
Plonky3
https://github.com/Plonky3/Plonky3
ZK11: Circle STARKs - Ulrich Haböck & Shahar Papini
https://youtu.be/NAhLYMysSdk?si=OlzNKS1DSTRkPnUR
Circle STARKs: Part I, Mersenne
https://blog.zksecurity.xyz/posts/circle-starks-1/
Why I’m Excited By Circle Stark And Stwo
https://starkware.co/integrity-matters-blog/why-im-excited-by-circle-stark-and-stwo/
Exploring circle STARKs
https://vitalik.eth.limo/general/2024/07/23/circlestarks.html
An introduction to circle STARKs
https://blog.lambdaclass.com/an-introduction-to-circle-starks/
Yet another circle STARK tutorial
https://research.chainsafe.io/blog/circle-starks/
Deep dive into Circle-STARKs FFT
https://ihagopian.com/posts/deep-dive-into-circle-starks-fft
Coset’s Circle STARKs lecture videos
https://youtube.com/playlist?list=PLbQFt1T_44DyihAOawprEABRPWgYeXB5u&si=AJe0dP7FUfp2Bebe
Ethereum/research/circlestark(Python implementation)
https://github.com/ethereum/research/tree/master/circlestark
Rust Implementation Demo of Circle Domain and Circle FFT
https://youtu.be/ur3c4mIi1Jc?si=lxU10mZ6vOFCrzvw
https://github.com/0xxEric/CircleFFT
STARKの原理
https://zenn.dev/qope/articles/8d60f77e3a7630

Apéndice

A continuación, introducimos la vista Proyectiva vs Afín de la curva del círculo, y luego explicamos por qué los Circle STARKs eligen específicamente los primos $p \equiv 3 \pmod{4}$ para evitar complicaciones proyectivas como los puntos en el infinito.

A.1 Proyectiva y Afín

En un plano afín sobre $\mathbb{F}_p$ , un punto simplemente se escribe como $(x,y)$ con $x,y \in \mathbb{F}_p$ . Por el contrario, en el plano proyectivo $\mathbb{P}^2(\mathbb{F}_p)$ , cada punto se denota por $(X : Y : Z)$ , pero todos los múltiplos escalares no nulos representan la misma ubicación. Formalmente,

(X : Y : Z) \;\equiv\; (\lambda X : \lambda Y : \lambda Z)\quad (\lambda \neq 0).

Cuando $Z \neq 0$ , podemos reescalar dividiendo cada coordenada entre $Z$ , lo que nos da un punto afín $\bigl(X/Z,\;Y/Z\bigr)$ .
Cuando $Z=0$ , obtenemos un punto en el infinito, que no tiene homólogo afín.

A.2 ¿Por qué Evitar los Puntos en el Infinito?

Para ver cómo surgen los puntos en el infinito, reescribe $x^2 + y^2 = 1$ en forma proyectiva:

X^2 + Y^2 \;=\; Z^2.

Aquí, si

Z \neq 0

, consideramos

x = X/Z

y = Y/Z

, de modo que

x^2 + y^2 = 1

se convierte en

X^2 + Y^2 = Z^2

.
Un punto en el infinito es cualquier solución con

Z=0

. Que tales soluciones existan depende de si

-1

es un cuadrado en

\mathbb{F}_p

Por ejemplo, si $p \equiv 1 \pmod{4}$ , entonces $-1$ es un cuadrado en $\mathbb{F}_p$ .
Concretamente, hay algún $a$ con $a^2 \equiv -1 \pmod{p}$ , lo que implica que $X^2 + Y^2 \equiv 0 \pmod{p}$ puede tener $(X,Y)$ distintos de cero en $Z=0$ .
Esto produce puntos infinitos adicionales en el círculo, complicando las operaciones de grupo y su implementación.
Ejemplo: $p=5$
- Aquí, $-1 \equiv 4$ en $\mathbb{F}_5$ , y $4$ es en efecto $(2^2)$ .
- Entonces $X^2 + Y^2 \equiv 0 \pmod{5}$ admite $(X,Y)$ distintos de cero en $Z=0$ , lo que da dos puntos en el infinito.
- La ecuación afín $x^2 + y^2=1$ tiene exactamente cuatro soluciones afines:
  
  $\{(0,1),\,(0,4),\,(1,0),\,(4,0)\}.$
Y los puntos proyectivos en el infinito son
$\{(2:1:0), (3:1:0)\}$ , hay $6$ soluciones en total — coincidiendo con $p+1=6$ ( $4$ afines + $2$ infinitos).
Si $p \equiv 3 \pmod{4}$ , entonces $-1$ no es un cuadrado en $\mathbb{F}_p$ .
En consecuencia, $X^2 + Y^2 \equiv 0 \pmod{p}$ no tiene soluciones distintas de cero en $Z=0$ . No obtenemos puntos en el infinito, y todas las soluciones permanecen siendo afines.
Ejemplo: $p=3$
- Dado que $-1 \equiv 2 \pmod{3}$ no es un cuadrado (tenemos $1^2 \equiv 1$ y $2^2 \equiv 1$ ), ningún $(X,Y)$ satisface $X^2+Y^2\equiv0$ en $Z=0$ .
- La ecuación $x^2 + y^2=1$ tiene entonces solo soluciones afines. Comprobar $x,y \in \{0,1,2\}$ produce:
  
  $\{(0,1),\,(0,2),\,(1,0),\,(2,0)\},$
  para un total de $4$ soluciones, lo que coincide con $p+1=4$ .

En Circle STARK, elegimos específicamente $p \equiv 3 \pmod{4}$ para que $-1$ no sea un cuadrado en $\mathbb{F}_p$ . Esto asegura que nuestro círculo $x^2 + y^2=1$ no tenga puntos infinitos (proyectivos), manteniendo cada solución en coordenadas afines y evita las complejidades de manejar puntos en el infinito.