Las Crónicas de ZK: Transformada Rápida de Fourier

Al principio dudé bastante en dedicarle un artículo entero a este tema. Generalmente me gusta cubrir temas más amplios en cada entrega. Algo así como paquetes temáticos que se sientan "cohesivos".

Lo que pasa es que, además de ser extremadamente útil, este algoritmo es uno de los más elegantes y útiles que pueden encontrar por ahí.

Es tan omnipresente, que lo más probable es que nunca tengan que implementarlo ustedes mismos. Y aun así, hay muchísimo valor en entender los detalles de su fantástico diseño.

Por supuesto, estoy hablando de la Transformada Rápida de Fourier, o FFT para abreviar (por sus siglas en inglés, Fast Fourier Transform).

Como mencioné anteriormente, esto permite una interpolación de polinomios eficiente, y dado que esta es una actividad que vamos a usar muchísimo en los próximos sistemas de prueba, la FFT se convierte esencialmente en la columna vertebral de dichos protocolos.

No creo poder generarles mucho más hype que esto, así que pongamos toda esa energía a buen uso, ¡y veamos qué nos espera hoy!

El Desafío Central

Empecemos por volver rápidamente al artículo anterior.

Nuestro análisis de los protocolos Sigma reveló que podíamos construir un mecanismo sorprendentemente simple para probar el conocimiento de un circuito entero. Sin embargo, hacerlo requería una cantidad de compromisos (commitments) proporcional a la cantidad de compuertas de multiplicación. Y eso no es nada conveniente.

Para evitar esto, otros protocolos optan por codificar los circuitos como polinomios en su lugar.

¿Cómo hacen eso? Bueno, no quiero arruinarles la sorpresa, así que acá va solo un pequeño adelanto:

Imaginemos que codificamos la entrada izquierda ($a$) de cada compuerta de multiplicación $i$ en un polinomio $A(X)$, requiriendo que $A(i) = a_i$. De igual manera, la entrada derecha ($b$) se codifica en $B(X)$ de forma que $B(i) = b_i$. Y la salida, la codificamos en $C(X)$.

Luego, ¡solamente necesitaríamos probar que $A(X) \cdot B(X) = C(X)$ se cumple para todos los valores posibles de $i$!

Este simple ejemplo (que, a pesar de su simplicidad, está detrás de uno de los protocolos ZK modernos más populares, Groth16) nos dice algo importante: cuando trabajamos con polinomios, a menudo vamos a necesitar realizar operaciones con ellos, ya sea sumando polinomios entre sí o calculando su producto.

Cada una de estas operaciones resulta ser eficiente cuando se realiza con cierta representación de los polinomios involucrados.

Ah, momento, no creo que hayamos hablado de eso explícitamente hasta ahora. Resulta que hay dos estrategias principales para representar polinomios:

• Como un conjunto de coeficientes, dados por la típica representación $A(X) = a_0 + a_1X + a_2X^2 + ... + a_{n-1}X^{n-1}$. Podemos elegir distintas bases al hacer esto, como por ejemplo las bases de Lagrange.
• O como un conjunto de evaluaciones: pares de puntos $(i, A(x_i))$, que en definitiva interpolan al mismo polinomio. La primera coordenada es el índice, y la segunda es el valor funcional.

Los coeficientes hacen que la suma sea trivial, mientras que la multiplicación es más dócil usando evaluaciones, porque simplemente multiplicamos los valores funcionales en cada índice.

Entonces, cuando algún protocolo (o cualquier otro tipo de aplicación, en realidad) nos requiere realizar varias de estas operaciones, tener la libertad de ir y venir entre estas formas es deseable. La pregunta, sin embargo, es si podemos hacer esto de manera eficiente: si los costos de conversión son más altos que simplemente correr los cómputos en bruto, ¡entonces no tiene ningún sentido cambiar entre representaciones!

Entonces, ¿qué onda? ¿Los costos se justifican?

El Camino Ingenuo

Analicemos el método más directo que se nos puede ocurrir, y así vamos a ver cómo enseguida nos topamos con problemas.

Empecemos analizando la conversión de coeficientes a evaluaciones. Nuestro objetivo es evaluar algún polinomio de grado $n$ en $n + 1$ puntos distintos (para poder interpolar luego). Una sola evaluación requiere que al menos calculemos $X^n$, así que toma $\mathcal{O}(n)$ pasos. Y como necesitamos evaluar $n + 1$ puntos, la conversión completa es $\mathcal{O}(n^2)$.

Después tenemos el camino inverso, yendo de evaluaciones a coeficientes. La forma estándar de hacer esto implica construir polinomios base de Lagrange, y combinarlos. Sin entrar en los detalles, este proceso requiere incluso más trabajo, entre $\mathcal{O}(n^2)$ y $\mathcal{O}(n^3)$ operaciones.

Dados esos números, ¿qué tan mala es la situación? Bueno, considerando que queremos codificar circuitos con potencialmente millones de compuertas, estaríamos lidiando con polinomios enormes, y los costos de conversión serían sencillamente una locura.

Lo que significa que, sin una estrategia más eficiente, estas conversiones están completamente fuera de alcance.

Y así, nos hacemos la misma pregunta que nos hicimos muchas veces a lo largo de la serie: ¿podemos hacerlo mejor?

La respuesta es, por supuesto, un rotundo sí, gracias a una observación inteligente sobre algo que pasamos por alto hasta ahora: que podemos elegir dónde evaluar los polinomios.

Quizás la elección más natural para esto sea simplemente usar números enteros consecutivos como índices: $0$, $1$, $2$, $3$, y así sucesivamente. Eso funciona perfectamente bien. Pero... ¿Y si les dijera que hay una opción mucho mejor?

Las Propiedades Mágicas

¿Se acuerdan?

¡Sí! ¡Raíces de la unidad!

Cuando hablamos de ellas hace algunos artículos, fue en el contexto de grupos. En realidad, esta vez nos interesan las raíces de la unidad del grupo multiplicativo de enteros módulo $p$. Porque estas van a ser las entradas de nuestros polinomios, y estos toman enteros como entradas.

Como pequeño repaso, las raíces n-ésimas de la unidad de un grupo son el conjunto de valores $\omega$ tales que:

$$\omega^n = 1$$

Sí, genial. Pero al final esos son solo números. ¿Qué los hace tan especiales?

El secreto está en un par de propiedades especiales de estos muchachines: la simetría y la clausura bajo elevación al cuadrado.

Simetría

Para entender a qué me refiero con esto, es conveniente empezar por el final de la película, y hacer el camino hacia atrás. Sabemos que cuando tenemos una raíz primitiva $n$-ésima de la unidad, elevarla a la $n$-ésima potencia nos da la identidad, que en nuestro caso es simplemente $1$.

Con esa información en mente, ¿qué pasaría si en lugar de elevar a la $n$-ésima potencia, probamos con la mitad de eso?

$$\omega^{\frac{n}{2}} = ?$$

Siempre y cuando, obviamente, ¡$n/2$ sea un entero!

Como es una raíz primitiva de la unidad, el resultado no puede ser $1$. Es más, debe ser un número tal que:

$$(\omega^{\frac{n}{2}})^{2} = 1$$

Ah, esperen. Entonces hay un candidato claro: ¡$-1$!

O bueno, en nuestro caso, $-1 \bmod p$.

Gracias a esta observación, podemos hacer algo increíble: dividir el grupo de $n$ raíces de la unidad en pares de opuestos, ya que:

$$\omega^{k + \frac{n}{2}} = \omega^k \omega^{\frac{n}{2}} =-\omega^k$$

Como simplemente estamos multiplicando por $-1$, tenemos una forma muy rápida de obtener el opuesto (modular) de una raíz de la unidad. Esto va a ser muy importante al momento de agregar resultados, pero en realidad es la otra propiedad que les mencionaba antes, la que es el verdadero ingrediente secreto detrás del algoritmo.

Clausura Bajo Elevación al Cuadrado

De manera similar, podemos preguntarnos qué pasa cuando elevamos al cuadrado una raíz de la unidad:

$$(\omega^k)^2 = \omega^{2k}$$

Lo cual podemos responder con una manipulación simple:

$$1 = (\omega^k)^n = (\omega^{2k})^{\frac{n}{2}}$$

¿Lo pueden ver? ¡Elevar al cuadrado cualquier raíz de la unidad la transforma en una raíz $(n/2)$-ésima de la unidad!

No es difícil deducir que tendremos exactamente la mitad de raíces $(n/2)$-ésimas de la unidad que raíces $n$-ésimas de la unidad. Lo cual es interesante porque, si vamos un paso más allá y elevamos al cuadrado todas las raíces $n$-ésimas de la unidad, sucede algo bastante mágico.

$$\{(\omega^0)^2, \omega^2, (\omega^2)^2, (\omega^3)^2, ..., (\omega^{n-1})^2 \} = \{1, \omega^2, \omega^4, \omega^6, ..., {\omega}^{2(n-1)} \}$$

¡Este conjunto de cuadrados tiene tamaño $n$, pero solo contiene raíces $(n/2)$-ésimas de la unidad... Así que debe haber valores repetidos ahí adentro! De hecho, ¡obtenemos cada una de estas raíces exactamente dos veces!

¡Intenten ver cómo se ve eso ustedes mismos con un ejemplo!

Creo que sería completamente razonable asumir que esto es solo un dato curioso, pero estaríamos completamente equivocados: ¡esta es la razón entera por la que la Transformada Rápida de Fourier funciona!

Lo único que necesitamos es encontrar una forma inteligente de explotar estas propiedades.

Divide y Reinarás

La técnica que estamos por usar es una a la que ya recurrimos en el pasado: la recursión.

En resumen, lo que vamos a intentar hacer acá es reducir un problema más grande a una versión más chica de sí mismo, y al hacerlo, recortar considerablemente los costos de cómputo. Es una idea maravillosamente simple, y en ciertas situaciones donde las estrellas se alinean de la manera justa, puede ser inmensamente poderosa.

¡Y esta resulta ser una de esas situaciones!

Bien, entonces la configuración es la siguiente: digamos que tenemos un polinomio $A(X)$ de grado $n {-} 1$, que queremos transformarlo de su forma de coeficientes, a su forma de evaluación.

Vamos a empezar dividiendo $A(X)$ en potencias pares e impares. Luego seleccionamos los coeficientes correspondientes, y construimos un par de polinomios nuevos, así:

• De los términos de potencia par: $A_E(X) = a_0 + a_2X + a_4X^2 + a_6X^3 + ...$
• De los términos de potencia impar: $A_O(X) = a_1 + a_3X + a_5X^2 + a_7X^3 + ...$

El desfasaje entre los índices de los coeficientes y las potencias puede confundir un poco al principio, pero en realidad no es arbitrario. La razón de esto es que el polinomio original $A(X)$ se puede expresar como una combinación inteligente de estos dos nuevos polinomios:

$$A(X) = A_{E}(X^2) + X.A_{O}(X^2)$$

Ese es un truco genial — pero por sí solo, no tiene mucha utilidad. La verdadera diversión empieza cuando combinamos esto con nuestro conocimiento sobre raíces de la unidad.

Evaluación

Intentemos insertar una raíz de la unidad en esa forma de $A(X)$, y veamos qué pasa:

$$A(\omega^k) = A_{E}(\omega^{2k}) + \omega^k A_{O}(\omega^{2k})$$

En lugar de evaluar $A(X)$ directamente en cada raíz n-ésima de la unidad, la expresión de arriba sugiere que podemos obtener el mismo resultado evaluando un par de otros polinomios en las raíces $(n/2)$-ésimas de la unidad.

Y acá, nuestra propiedad de clausura nos viene como anillo al dedo: ¡sabemos que la cantidad de raíces $(n/2)$-ésimas de la unidad es la mitad de la de las raíces $n$-ésimas de la unidad!

La consecuencia es muy agradable: algunas evaluaciones de $A_E(X)$ y $A_O(X)$ se pueden reutilizar, ¡ya que se repiten! O, para decirlo de forma aún más visual, pueden verificar fácilmente que:

$$A(\omega^{k + n/2}) = A_{E}(\omega^{2k}) + \omega^{k + n/2} A_{O}(\omega^{2k})$$

¡Ajá! Nuestro problema de evaluar $A(X)$ en $n$ puntos se redujo a evaluar $A_E(X)$ y $A_O(X)$ en la mitad de puntos, y realizar algunas operaciones simples. Esto lo podemos hacer siempre y cuando también podamos evaluar $A_E(X)$ y $A_O(X)$ de manera eficiente... Pero esperen...

¡Ese era nuestro problema original, con aproximadamente la mitad del tamaño!¡Ese era nuestro problema original, con aproximadamente la mitad del tamaño!

¡Sí! Es exactamente acá donde entra en juego la recursión: ¡podemos seguir haciendo esto una y otra vez gracias a las propiedades tan convenientes de las raíces de la unidad!

Y como si eso no fuera suficiente, la cereza del postre nos la da la propiedad de simetría que estudiamos antes. Ya que sabemos que:

$$\omega^{k+n/2}=-\omega^k$$

Entonces nuestra segunda evaluación se convierte en:

$$A({-}\omega^{k}) = A_{E}(\omega^{2k}) {-} \omega^{k} A_{O}(\omega^{2k})$$

¡Lo cual se ve exactamente igual que la evaluación en $\omega^k$, pero con un signo menos ahí!

En resumen, necesitamos ejecutar estos pasos para cada $k$ desde $0$ hasta $n/2 {-} 1$:

1. Evaluar $A_E(\omega^{2k})$ una vez
2. Evaluar $A_O(\omega^{2k})$ una vez
3. Calcular $\omega^k A_O(\omega^{2k})$$ una vez
4. Calcular $A(\omega^k)$ sumando los resultados
5. Calcular $A({-}\omega^k)$ restando en su lugar

¡Y obtenemos las dos evaluaciones por apenas un poco más que el costo de una sola, ya que estamos evaluando dos polinomios de la mitad del grado, en la mitad de puntos!

Es increíble cómo las piezas encajan, como si estuvieran guiadas por alguna mano matemática mágica invisible. Tanto es así, que uno tal vez no pueda evitar seguir teniendo dudas, hasta ver un ejemplo funcionando.

¡Así que hagamos eso!

Un Ejemplo Concreto

Vamos a trabajar en $\mathbb{F}_{17}$, cuyo grupo multiplicativo es $\mathbb{Z}_{17}^*$. Este campo es conveniente porque tiene raíces cuartas primitivas de la unidad, lo que significa que podemos hacer un pequeño ejemplo usando $n = 4$.

Primero, vamos a necesitar los valores concretos para las raíces de la unidad. El valor $\omega = 4$ resulta ser una raíz primitiva de la unidad en este caso, así que si hacen las operaciones ustedes mismos, van a encontrar que el conjunto de raíces se ve así:

$$H = \{1,4,16,13\}$$

¡Perfecto! Luego, tomemos un polinomio simple, como: $A(X) = 3 + 2X + 5X^2 + 7X^3$. Queremos evaluar esto en los puntos de $H$ (nuestras raíces de la unidad), así que procedemos según nuestro proceso recursivo:

• Primero, separamos en coeficientes pares e impares, resultando en $A_E(X) = 3 + 5X$ y $A_O(X) = 2 + 7X$.
• Lo siguiente es evaluar estos dos polinomios en las raíces segundas de la unidad, que son simplemente $\{1, 16\}$. Estas son operaciones muy básicas (ya que los polinomios tienen grado $1$) que resultan en:

$$A_{E}(1) = 8, \ A_{E}(16) = 15, \ A_{O}(1) = 9, \ A_{O}(16) = 12$$

• Luego combinamos usando la propiedad de simetría. Por ejemplo, para $k = 0$ tenemos: $A(1) = 8 + 9 \bmod 17 = 0$, y $A({-}1) = A(16) = 8 – 9 \bmod 17 = 16$. ¡Solo hay que repetir con $k = 1$, y listo!

El resultado final es $A(1) = 0$, $A(4) = 12$, $A(16) = 16$, y $A(13) = 1$, ¡por si acaso lo estuvieron siguiendo con lápiz y papel y quieren verificar!

¡Y si ya están haciendo eso, asegúrense también de verificar que esto coincide con la evaluación directa!

¡Eso es todo! Solo hay que dividir, evaluar, y combinar. Repetir una y otra vez, ¡y tenemos nuestro algoritmo FFT!

Este pequeño ejemplo puede no parecer una gran mejora, pero aun así, ya pueden ver algunas ganancias:

• el camino directo requiere 4 evaluaciones, con 4 operaciones cada una (calculando $X^3$ y luego sumando todos los términos), así que aproximadamente 16 pasos de cómputo en total.
• en contraste, la FFT tomó 4 evaluaciones (de los polinomios divididos) más 4 combinaciones, así que 8 operaciones en total.

¡Es la mitad del esfuerzo! Y se pone aún mejor a medida que probamos con polinomios más grandes: cada paso recursivo va a tomar $\mathcal{O}(n)$ operaciones, y la cantidad de pasos es logarítmica con respecto a $n$ (¡dividimos la cantidad de evaluaciones por dos en cada paso!), así que la complejidad general del algoritmo es $\mathcal{O}(n.log_2(n))$.

Para poner esto en perspectiva, cuando $n = 100$, la evaluación directa tomaría alrededor de $10000$ pasos, ¡mientras que la FFT solo requeriría alrededor de $650$ pasos!

Interpolación

Con esto, tenemos una forma eficiente de ir desde coeficientes hacia evaluaciones.

¿No podríamos intentar ir en la otra dirección? Ya saben, para poder realmente transformar de un lado al otro entre formas. ¿Hay un truco similar para eso?

Bueno, sorprendentemente, ¡esto también funciona al revés!

La FFT inversa usa casi exactamente el mismo algoritmo, con solo un par de pequeños ajustes. Para entender cómo funciona, necesitamos cambiar un poco de perspectiva, e imaginar el proceso de obtener evaluaciones como una multiplicación de matrices:

$$\begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & \omega & \omega^2 & \omega^3 \\ 1 & \omega^2 & \omega^4 & \omega^6 \\ 1 & \omega^3 & \omega^6 & \omega^9 \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ a_2 \\ a_3 \end{bmatrix} = \begin{bmatrix} A(\omega^0) \\ A(\omega^1) \\ A(\omega^2) \\ A(\omega^3) \end{bmatrix}$$

A la matriz de esa ecuación de ahí arriba se le llama la matriz de la Transformada Discreta de Fourier (DFT). Desde este punto de vista, es bastante obvio que todo lo que tenemos que hacer para resolver esta ecuación es calcular la inversa de esta matriz, y luego multiplicar acordemente.

Es más, ¡la estructura de la inversa es bastante simple! Para nuestro ejemplo con $n = 4$, obtendríamos:

$$\frac{1}{4}\begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & \omega^{-1} & \omega^{-2} & \omega^{-3} \\ 1 & \omega^{-2} & \omega^{-4} & \omega^{-6} \\ 1 & \omega^{-3} & \omega^{-6} & \omega^{-9} \end{bmatrix}$$

La generalización de esto es justo lo que esperarían: ¡una matriz más grande, y un factor escalar de $1/n$!

Y con eso, ¡obtenemos el algoritmo para recuperar los coeficientes a partir de las evaluaciones casi gratis!

Resumen

La FFT es uno de esos algoritmos que se siente casi mágico. Las piezas encajan demasiado bien.

¡No es de extrañar que se lo debamos a los esfuerzos de grandes matemáticos como Gauss o Fourier!

Todo empezó con la observación más bien poco inspiradora de que podemos elegir dónde evaluar nuestros polinomios. Y fue a través de la elección de un conjunto con propiedades muy particulares, que terminamos con este algoritmo genuinamente hermoso.

La FFT es enormemente importante para ZK por su capacidad de hacer que las operaciones con polinomios grandes sean computacionalmente viables. Y como mencioné al principio del artículo, probablemente nunca tengan que implementarla ustedes mismos: prácticamente toda librería de ZK que usen va a incluir una versión altamente optimizada del algoritmo, con incluso más trucos como paralelismo, caches, y más.

Además, hay varios matices a tener en cuenta que no mencioné explícitamente. Por ejemplo, necesitan asegurarse de evaluar en una cantidad de puntos que sea una potencia de $2$, lo cual requiere que los polinomios tengan grados específicos, ¡y que los campos finitos elegidos contengan el conjunto apropiado de raíces de la unidad!

Así que sí, hay más que decir en esta historia — pero creo que lo que hemos cubierto debería ser suficiente para nosotros.

Y ya que estamos en el tema de los polinomios, me gustaría que nuestra próxima parada muestre otro ingrediente más que vamos a necesitar en nuestro camino.

Lo que estamos por estudiar es lo que nos permite dar el salto de calidad desde nuestros protocolos Sigma, hacia las técnicas más modernas que pueden explotar completamente la FFT, y así proveer un grado de eficiencia que finalmente lleva a ZK al dominio de lo práctico.

Así que, en nuestro próximo encuentro vamos a hablar sobre esquemas de compromiso de polinomios, uno de los últimos artefactos restantes antes de que vayamos con todo hacia los algoritmos modernos de ZK.

¡Y finalmente vamos a dar un poco de claridad sobre aquel acceso de oráculo que mantuvimos en el freezer durante tanto tiempo!

¡Hasta entonces!