El nuevo trabajo de Vitalik: Explora Circle STARKs

Título original: "Explorando el círculo STARKs"

Escrito por: Vitalik Buterin, cofundador de Ethereum

Compilado por: Chris, Techub News

El requisito previo para comprender este artículo es que ya comprenda los principios básicos de SNARK y STARK. Si no está familiarizado con esto, le sugiero que lea las primeras partes de este artículo para comprender los conceptos básicos.

En los últimos años, la tendencia en el diseño del protocolo STARK ha sido hacia el uso de campos más pequeños. Las primeras implementaciones de producción de STARK utilizaron campos de 256 bits, es decir, módulo aritmético en números grandes (como 21888...95617), lo que hizo que estos protocolos fueran compatibles con firmas basadas en curvas elípticas. Sin embargo, la eficiencia de este diseño es relativamente baja. En circunstancias normales, procesar y calcular estos números grandes no tiene ningún uso práctico y desperdiciará mucha potencia informática, como procesar X (que representa un cierto número) y procesar cuatro veces X. , procesamiento Solo se requiere una novena parte del tiempo de cálculo. Para resolver este problema, STARK comenzó a trasladarse a campos más pequeños: primero Goldilocks, luego Mersenne31 y BabyBear.

Este cambio ha mejorado las velocidades de prueba, como que Starkware puede probar 620.000 hashes Poseidon2 por segundo en una computadora portátil M3. Esto significa que siempre que estemos dispuestos a confiar en Poseidon2 como función hash, podemos resolver el difícil problema de desarrollar ZK-EVM eficiente. Entonces, ¿cómo funcionan estas tecnologías? ¿Cómo se basan estas pruebas en campos más pequeños? ¿Cómo se comparan estos protocolos con soluciones como Binius? Este artículo explorará estos detalles, enfocándose específicamente en un esquema llamado Circle STARK (implementado en stwo de Starkware, plonky3 de Polygon y mi propia versión en Python), que tienen la propiedad única de ser compatibles con los campos Mersenne31.

Problemas comunes al trabajar con campos matemáticos más pequeños

Un truco muy importante al crear pruebas basadas en hash (o pruebas de cualquier tipo) es poder verificar indirectamente las propiedades de un polinomio evaluando el polinomio en puntos aleatorios. Este enfoque puede simplificar enormemente el proceso de prueba, ya que la evaluación en puntos aleatorios suele ser mucho más fácil que tratar con el polinomio completo.

Por ejemplo, supongamos que un sistema de prueba requiere que usted genere un compromiso con un polinomio, A, que debe satisfacer A^3 (x) + x - A (\omega*x) = x^N (uno muy común en ZK). -Protocolo tipo SNARK). ¿El protocolo podría pedirle que elija una coordenada aleatoria y demuestre que A (r) + r - A (\omega*r) = r^N. Luego trabaja hacia atrás hasta A (r) = c, y demuestras que Q = \frac {A - c}{X - r} es un polinomio.

Si conoce los detalles o los aspectos internos de los protocolos de antemano, es posible que pueda encontrar formas de evitarlos o piratearlos. A continuación se pueden mencionar acciones o métodos específicos para lograrlo. Por ejemplo, para satisfacer la ecuación A (\omega * r), podrías establecer A (r) en 0 y dejar que A sea una línea recta que pasa por estos dos puntos.

Para evitar estos ataques, debemos elegir r después de que el atacante haya proporcionado A (Fiat-Shamir es una técnica utilizada para mejorar la seguridad del protocolo estableciendo ciertos parámetros en algún valor hash para evitar ataques. Elija Los parámetros deben provenir de un valor suficientemente grande configurado para garantizar que un atacante no pueda predecir o adivinar estos parámetros, mejorando así la seguridad del sistema.

En los protocolos basados ​​en curvas elípticas y STARK en el período 2019, el problema es simple: todas nuestras operaciones matemáticas se realizan en números de 256 bits, por lo que podemos elegir r como un número aleatorio de 256 bits, de modo que. Sin embargo, en STARK en campos más pequeños, nos encontramos con un problema: solo hay alrededor de 2 mil millones de valores posibles de r para elegir, por lo que un atacante que quiera falsificar una prueba solo necesita intentarlo 2 mil millones de veces, lo cual es un Mucho trabajo, pero para un atacante decidido, ¡todavía es completamente posible!

Hay dos soluciones para este problema:

• Realizar múltiples controles aleatorios

• No

La forma más sencilla y eficaz de realizar múltiples comprobaciones aleatorias es: en lugar de comprobar en una coordenada, repita la comprobación en cuatro coordenadas aleatorias. Esto es teóricamente posible, pero existen problemas de eficiencia. Si se trata de un polinomio de grado menor que un cierto valor y se opera en un dominio de cierto tamaño, un atacante puede construir un polinomio malicioso que parezca normal en esas posiciones. Por lo tanto, si pueden romper con éxito el protocolo es una cuestión probabilística, por lo que es necesario aumentar el número de rondas de comprobaciones para mejorar la seguridad general y garantizar que los atacantes puedan defenderse eficazmente contra los ataques.

Esto lleva a otra solución: los campos extendidos son como números complejos, pero se basan en campos finitos. Introducimos un nuevo valor, denotado como α\alphaα, y declaramos que satisface una determinada relación, como α2=algún valor\alpha^2 = \text {algún valor}α2=algún valor. De esta forma, creamos una nueva estructura matemática capaz de realizar operaciones más complejas en campos finitos. En este dominio extendido, el cálculo de la multiplicación se convierte en una multiplicación utilizando el nuevo valor α\alphaα. Ahora podemos operar con pares de valores en un dominio extendido, no solo con números individuales. Por ejemplo, si estamos trabajando en un campo como Mersenne o BabyBear, dicha extensión nos permite tener más opciones de valor, mejorando así la seguridad. Para aumentar aún más el tamaño del campo, podemos aplicar repetidamente la misma técnica. Como ya hemos usado α\alphaα, necesitamos definir un nuevo valor, que en Mersenne31 se representa eligiendo α\alphaα tal que α2=algún valor\alpha^2 = \text {algún valor}α2=algún valor.

Código (puedes mejorarlo con Karatsuba)

Al ampliar el dominio, ahora tenemos suficientes valores para elegir que satisfacen nuestras necesidades de seguridad. Si se trata de polinomios de grado menor que ddd, esto proporciona 104 bits de seguridad por ronda. Esto significa que tenemos la seguridad adecuada. Si se requiere un nivel de seguridad más alto, como 128 bits, podemos agregar algo de trabajo computacional adicional al protocolo para mejorar la seguridad.

Los dominios extendidos solo se utilizan en realidad en protocolos FRI (Fast Reed-Solomon Interactive) y otros escenarios que requieren combinaciones lineales aleatorias. La mayor parte de los cálculos todavía se realizan en los campos subyacentes, que suelen ser campos módulo ppp o qqq. Además, casi todos los datos codificados se realizan en los campos subyacentes, por lo que solo se procesan cuatro bytes por valor. Al hacerlo, se aprovecha la eficiencia de los campos pequeños y al mismo tiempo se permite el uso de campos más grandes cuando se necesitan mejoras de seguridad.

Viernes normal

Al construir un SNARK o STARK, el primer paso suele ser la aritmetización. Esta es la conversión de cualquier problema computacional en una ecuación donde algunas de las variables y coeficientes son polinomios. Específicamente, esta ecuación normalmente se verá así: P (X,Y,Z)=0P (X,Y,Z) = 0P (X,Y,Z)=0, donde P es un polinomio y Z es un parámetro dado, y el solucionador debe proporcionar los valores X e Y. Una vez que tenga dicha ecuación, la solución de esa ecuación corresponde a la solución del problema computacional subyacente.

Para demostrar que tiene una solución, debe demostrar que los valores que obtuvo son polinomios legítimos (a diferencia de fracciones, o parecen un polinomio en algunos lugares y un polinomio diferente en otros, etc.), Y estos polinomios tienen un cierto grado máximo. Para ello utilizamos una técnica de combinación lineal estocástica aplicada paso a paso:

• Supongamos que tienes una evaluación de un polinomio A y quieres demostrar que su grado es menor que 2^{20}

• Considere el polinomio B (x^2) = A (x) + A (-x), C (x^2) = \frac {A (x) - A (-x)}{x}

• D es una combinación lineal aleatoria de B y C, es decir, D=B+rCD = B + rCD=B+rC, donde r es un coeficiente aleatorio.

Básicamente, lo que sucede es que B aísla los coeficientes pares de A y ? aísla los coeficientes impares. Dados B y C, puedes recuperar el polinomio original A: A (x) = B (x^2) + xC (x^2). Si el grado de A es efectivamente menor que 2^{20}, entonces los grados de B y C serán el grado de A y el grado de A menos 1 respectivamente. Porque la combinación de términos pares e impares no aumenta el grado. Dado que D es una combinación lineal aleatoria de B y C, el grado de D también debe ser el grado de A, lo que le permite utilizar el grado de D para verificar que el grado de A cumple con los requisitos.

Primero, FRI simplifica el proceso de verificación al reducir el problema de demostrar un polinomio con grado d al problema de demostrar un polinomio con grado d/2. Este proceso se puede repetir muchas veces, simplificando el problema a la mitad cada vez.

FRI funciona repitiendo este proceso de simplificación. Por ejemplo, si comienzas demostrando que el grado de un polinomio es d, a través de una serie de pasos eventualmente demostrarás que el grado del polinomio es d/2. Después de cada simplificación, el grado del polinomio resultante disminuye gradualmente. Si la salida de una etapa no tiene el grado polinómico esperado, esta ronda de comprobaciones fallará. Si alguien intenta impulsar un polinomio que no es de grado d a través de esta técnica, entonces en la segunda ronda de producción, su grado no cumplirá las expectativas con cierta probabilidad, y en la tercera ronda será más probable que sea inconsistente. y finalmente la verificación fallará. Este diseño puede detectar y rechazar eficazmente entradas que no cumplan con los requisitos. Es probable que un conjunto de datos pase la validación FRI si es igual a un polinomio de grado d en la mayoría de las ubicaciones. Sin embargo, para construir tal conjunto de datos, el atacante necesita conocer los polinomios reales, por lo que incluso una prueba levemente defectuosa muestra que el probador es capaz de generar una prueba "real".

Echemos un vistazo más de cerca a lo que está sucediendo aquí y a las propiedades necesarias para que todo esto funcione. En cada paso, reducimos el grado del polinomio a la mitad y también reducimos el conjunto de puntos (el conjunto de puntos que nos interesa) a la mitad. Lo primero es clave para que el protocolo FRI (Fast Reed-Solomon Interactive) funcione correctamente. Esto último hace que el algoritmo se ejecute extremadamente rápido: dado que el tamaño de cada ronda se reduce a la mitad en comparación con la ronda anterior, el costo computacional total es O (N) en lugar de O (N*log (N)).

Para lograr una reducción progresiva del dominio, se utiliza un mapeo de dos a uno, es decir, cada punto se mapea a uno de dos puntos. Este mapeo nos permite reducir el tamaño del conjunto de datos a la mitad. Una ventaja importante de este mapeo dos a uno es que es repetible. Es decir, cuando aplicamos este mapeo, el conjunto de resultados resultante aún conserva las mismas propiedades. Supongamos que comenzamos con un subgrupo multiplicativo. Este subgrupo es un conjunto S donde cada elemento x tiene su múltiplo 2x también en el conjunto. Si eleva al cuadrado el conjunto S (es decir, asigna cada elemento x del conjunto a x^2), el nuevo conjunto S^2 conservará las mismas propiedades. Esta operación nos permite continuar reduciendo el tamaño del conjunto de datos hasta que finalmente solo quede un valor. Si bien en teoría podríamos reducir el conjunto de datos a un solo valor, en la práctica normalmente nos detenemos antes de llegar a un conjunto más pequeño.

Puedes pensar en esta operación como el proceso de estirar una línea (por ejemplo, un segmento de línea o un arco) en la circunferencia de un círculo para que haga dos revoluciones alrededor del círculo. Por ejemplo, si un punto está a x grados en la circunferencia, se moverá a 2x grados después de esta operación. Cada punto del círculo de 0 a 179 grados tiene un punto correspondiente de 180 a 359 grados, y estos dos puntos coincidirán. Esto significa que cuando asigna un punto de x grados a 2x grados, coincidirá con una posición en x+180 grados. Este proceso se puede repetir. Es decir, puede aplicar esta operación de mapeo varias veces, moviendo cada vez los puntos de la circunferencia a sus nuevas posiciones.

Para que la técnica de mapeo sea efectiva, el tamaño del subgrupo multiplicativo original debe tener potencias grandes de 2 como factores. BabyBear es un sistema con un cierto módulo tal que su subgrupo multiplicativo máximo contiene todos los valores distintos de cero, de modo que el tamaño del subgrupo es 2k−1 (donde k es el número de dígitos en el módulo). Los subgrupos de este tamaño se adaptan bien a la técnica anterior ya que permite una reducción eficiente del grado del polinomio mediante la aplicación repetida de la operación de mapeo. En BabyBear, puede seleccionar un subgrupo de tamaño 2^k (o simplemente usar el conjunto completo), luego aplicar el método FRI para reducir gradualmente el grado del polinomio a 15 y verificar el grado del polinomio al final. Este método aprovecha las propiedades del módulo y el tamaño del subgrupo multiplicativo, haciendo que el proceso de cálculo sea muy eficiente. Mersenne31 es otro sistema cuyo módulo es algún valor tal que el tamaño del subgrupo multiplicativo es 2^31 - 1. En este caso, el tamaño del subgrupo multiplicativo tiene solo una potencia de 2 como factor, lo que permite dividirlo por 2 una sola vez. El procesamiento posterior ya no es adecuado para las técnicas anteriores, es decir, no es posible utilizar FFT para una reducción de grado polinomial eficiente como BabyBear.

Los campos Mersenne31 son muy adecuados para operaciones aritméticas en operaciones de CPU/GPU de 32 bits existentes. Debido a sus propiedades de módulo (como 2^{31} - 1), muchas operaciones se pueden completar usando operaciones de bits eficientes: si el resultado de sumar dos números excede el módulo, la operación de módulo puede desplazar el resultado para reducirlo. a un rango apropiado. La operación de desplazamiento es una operación muy eficiente. En las operaciones de multiplicación, se utilizan instrucciones específicas de la CPU (a menudo llamadas instrucciones de desplazamiento de orden superior) para procesar el resultado. Estas instrucciones pueden calcular de manera eficiente la parte de orden superior de la multiplicación, mejorando así la eficiencia de la operación. En el dominio Mersenne31, las operaciones aritméticas son aproximadamente 1,3 veces más rápidas que en el dominio BabyBear debido a las propiedades descritas anteriormente. Mersenne31 proporciona una mayor eficiencia computacional. Si se puede implementar FRI en el dominio Mersenne31, esto mejorará significativamente la eficiencia computacional y hará que las aplicaciones FRI sean más eficientes.

Círculo VIE

Esto es lo bueno de los Circle STARK: dado un número primo p, puedes encontrar una población de tamaño p que tenga propiedades similares de dos a uno. Esta población está compuesta por todos los puntos que satisfacen ciertas condiciones, por ejemplo, el conjunto de puntos donde x^2 mod p es igual a un cierto valor.

Estos puntos siguen un patrón aditivo, que puede resultarle familiar si ha hecho algo relacionado con la trigonometría o la multiplicación compleja recientemente.

(x_1, y_1) + (x_2, y_2) = (x_1x_2 - y_1y_2, x_1y_2 + x_2y_1)

La forma duplicada es:

2 * (x, y) = (2x^2 - 1, 2xy)

Ahora, centrémonos en los puntos impares de este círculo:

Primero, hacemos converger todos los puntos en una línea recta. La forma equivalente de las fórmulas B (x²) y C (x²) que usamos en el FRI habitual es:

f_0 (x) = \frac {F (x,y) + F (x,-y)}{2}

Luego podemos realizar combinaciones lineales aleatorias para obtener un polinomio unidimensional P(x) definido sobre un subconjunto de las líneas x:

A partir de la segunda ronda, el mapeo cambia:

f_0 (2x^2-1) = \frac {F (x) + F (-x)}{2}

Este mapeo en realidad reduce el tamaño del conjunto anterior a la mitad cada vez, lo que sucede aquí es que cada x representa dos puntos en cierto sentido: (x, y) y (x, -y). Y (x → 2x^2 - 1) es la regla de duplicación de puntos anterior. Por lo tanto, convertimos las coordenadas x de dos puntos opuestos en el círculo en las coordenadas x del punto multiplicado.

Por ejemplo, si tomamos el segundo valor en el círculo desde la derecha, 2, y aplicamos la asignación 2 → 2 (2^2) - 1 = 7, obtenemos 7 como resultado. Si volvemos al círculo original, (2, 11) es el tercer punto desde la derecha, por lo que al duplicarlo obtenemos el sexto punto desde la derecha, que es (7, 13).

Esto podría haberse hecho en dos dimensiones, pero operar en una dimensión hace que el proceso sea más eficiente.

FFT circulares

Un algoritmo estrechamente relacionado con FRI es FFT, que convierte n evaluaciones de un polinomio de grado menor que n en n coeficientes de ese polinomio. El proceso de FFT es similar a FRI, excepto que en lugar de generar combinaciones lineales aleatorias f_0 y f_1 en cada paso, FFT realiza recursivamente una FFT de tamaño medio sobre ellas y toma la salida de FFT (f_0) como coeficientes pares. Trate la salida. de FFT (f_1) como coeficientes impares.

Los grupos circulares también apoyan las FFT, que se construyen de manera similar a las FRI. Sin embargo, una diferencia clave es que Circle FFT (y Circle FRI) tratan con objetos que no son estrictamente polinomios. En cambio, son lo que matemáticamente se llaman espacios de Riemann-Roch: en este caso, los polinomios son módulo circular (x^2 + y^2 - 1 = 0). Es decir, tratamos cualquier múltiplo de x^2 + y^2 - 1 como cero. Otra forma de verlo es: solo permitimos que y se eleve a una potencia: tan pronto como aparece un término y^2, lo reemplazamos con 1 - x^2.

Esto también significa que los coeficientes generados por Circle FFT no son monomios como el FRI normal (por ejemplo, si el FRI normal genera [6, 2, 8, 3], entonces sabemos que esto significa P (x) = 3x^3 + 8x ^2 + 2x + 6). Por el contrario, los coeficientes de la FFT circular son específicos de la base FFT circular: {1, y, x, xy, 2x^2 - 1, 2x^2y - y, 2x^3 - x, 2x^3y - xy, 8x^4 - 8x^2 + 1...}

La buena noticia es que, como desarrollador, puedes ignorar esto casi por completo. STARKs nunca requiere que conozcas los coeficientes. En su lugar, simplemente almacena el polinomio como un conjunto de valores de evaluación en un dominio específico. El único lugar donde necesita usar FFT es hacer una extensión de bajo grado (similar a los espacios de Riemann-Roch): dados N valores, genere valores k*N, todos en el mismo polinomio. En este caso, puede usar una FFT para generar los coeficientes, agregar (k-1) n ceros a estos coeficientes y luego usar la FFT inversa para obtener un conjunto más grande de valores evaluados.

Las FFT circulares no son el único tipo especial de FFT. Las FFT de curva elíptica son más poderosas porque pueden funcionar en cualquier campo finito (campo primo, campo binario, etc.). Sin embargo, ECFFT es más complejo y menos eficiente, por lo que como podemos usar Circle FFT en p = 2^{31}-1, elegimos usarlo.

A partir de aquí, profundizaremos en algunos de los detalles más oscuros que hacen que la implementación de Circle STARK sea diferente de la de STARK normal.

Cociente

En el protocolo STARK, una operación común es realizar operaciones de cociente en puntos específicos. Estos puntos se pueden seleccionar de forma deliberada o aleatoria. Por ejemplo, si desea demostrar que P (x) = y, puede hacerlo siguiendo estos pasos:

Calcular el cociente: Dado un polinomio P (x) y una constante y, calcular el cociente Q ={P - y}/{X - x}, donde X es el punto elegido.

Demostrar polinomios: demostrar que Q es un polinomio, no una fracción. De esta forma se demuestra que P (x) = y es cierto.

Además, en el protocolo DEEP-FRI, los puntos de evaluación se seleccionan aleatoriamente para reducir la cantidad de sucursales de Merkle, mejorando así la seguridad y eficiencia del protocolo FRI.

Cuando se trata del protocolo STARK del grupo circular, dado que no existe una función lineal que pueda pasar por un solo punto, se deben utilizar diferentes técnicas para reemplazar el método tradicional de operación de cociente. Esto a menudo requiere diseñar nuevos algoritmos utilizando las propiedades geométricas únicas de los grupos de círculos.

En un grupo circular, puedes construir una función tangente que sea tangente a un cierto punto (P_x, P_y), pero esta función tendrá multiplicidad 2 a través del punto, es decir, un polinomio se convierte en el múltiplo de una función lineal que debe satisfacer condiciones más estrictas que simplemente ser cero en ese punto. Por lo tanto, no se pueden probar los resultados de la evaluación en un solo momento. Entonces, ¿cómo lidiamos con esto?

Tuvimos que aceptar este desafío y probarlo evaluando dos puntos, agregando así un punto ficticio en el que no necesitábamos concentrarnos.

Función de línea: ax + by + c. Si lo convertiste en una ecuación, forzándola a ser igual a 0, entonces podrías reconocerla como una línea en lo que se llama forma estándar en matemáticas de secundaria.

Si tenemos un polinomio P que es igual a y_1 en x_1 e y_2 en x_2, podemos elegir una función de interpolación L que es igual a y_1 en x_1 e y_2 en x_2. Esto se puede expresar simplemente como L = \frac {y_2 - y_1}{x_2 - x_1} \cdot (x - x_1) + y_1.

Luego demostramos que P es igual a y_1 en x_1 e y_2 en x_2 restando L (haciendo que P - L sea cero en ambos puntos) y por L (es decir, una función lineal entre x_2 - x_1). Dividimos por L para demostrar que el cociente Q es un polinomio.

Polinomios de fuga

En STARK, la ecuación polinómica que estás tratando de demostrar generalmente se ve así C (P (x), P ({next}(x))) = Z (x) ⋅ H (x) , donde Z (x) es una A polinomio igual a cero en todo el dominio de evaluación original. En STARK normal, esta función es x^n - 1. En STARK circular, la función correspondiente es:

Z_1 (x,y) = y

Z_2 (x,y) = x

Z_{n+1}(x,y) = (2 * Z_n (x,y)^2) - 1

Tenga en cuenta que puede derivar el polinomio de fuga a partir de la función de plegado: en STARK normal reutiliza x → x^2 , mientras que en STARK circular reutiliza x → 2x^2 - 1 . Para la primera ronda, sin embargo, lo haces de manera diferente porque la primera ronda es especial.

Orden de bits inverso

En STARK, los polinomios generalmente no se evalúan en el orden "natural" (por ejemplo, P (1), P (ω), P (ω2),…, P (ωn−1)), sino en lo que yo llamo el inverso. orden de bits inverso:

P (\omega^{\frac {3n}{8}})

Si establecemos n=16 y solo nos centramos en qué potencias de ω evaluamos, la lista se ve así:

{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}

Esta clasificación tiene la propiedad clave de que los valores agrupados al principio del proceso de evaluación FRI se vuelven adyacentes en la clasificación. Por ejemplo, el primer paso de los grupos FRI x y -x. En el caso de n = 16, ω^8 = -1, lo que significa P (ω^i) ) y ( P (-ω^i) = P (ω^{i+8}) \). Como podemos ver, estos son exactamente los pares uno al lado del otro. El segundo paso de los grupos FRI P (ω^i) , P (ω^{i+4}) , P (ω^{i+8}) y P (ω^{i+12}). Esto es exactamente lo que vemos en grupos de cuatro, y así sucesivamente. Hacer esto hace que FRI sea más eficiente en cuanto a espacio, ya que le permite proporcionar una prueba de Merkle para los valores plegados (o, si suma k rondas a la vez, para los 2^k valores).

En los STARK circulares, la estructura de pliegue es ligeramente diferente: en el primer paso, emparejamos (x, y) con (x, -y, en el segundo paso, emparejamos x con -x, en el paso siguiente, emparejamos p); con q, y elija p y q tales que Q^i (p) = -Q^i (q), donde Q^i es un mapeo que se repite x → 2x^2-1 i veces. Si pensamos en los puntos en términos de su posición en el círculo, entonces en cada paso parece que el primer punto está emparejado con el último, el segundo con el penúltimo, y así sucesivamente.

Para ajustar el orden inverso de los bits para reflejar esta estructura plegable, debemos invertir todos los bits excepto el último. Guardamos el último bit y lo usamos para decidir si volteamos los otros bits.

Un pliegue de tamaño 16 en orden de bits inverso es el siguiente:

{0, 15, 8, 7, 4, 11, 12, 3, 2, 13, 10, 5, 6, 9, 14, 1}

Si observas el círculo de la sección anterior, verás que los puntos 0, 15, 8 y 7 (en el sentido contrario a las agujas del reloj desde la derecha) son (x, y), (x, -y), (-x, - y) y (-x, y), que es exactamente lo que necesitamos.

eficiencia

En los Circle STARK (y en los STARK principales de 31 bits en general), estos protocolos son muy eficientes. Un cálculo probado en Circle STARK normalmente implica varios tipos de cálculos:

1. Aritmética nativa: se utiliza para la lógica empresarial, como contar.

2. Aritmética nativa: utilizada en criptografía, como funciones hash como Poseidón.

3. Parámetros de búsqueda: un método de cálculo general y eficiente que implementa varios cálculos leyendo valores de la tabla.

La medida clave de la eficiencia es si está utilizando completamente todo el espacio para realizar un trabajo útil en un seguimiento informático o si está dejando mucho espacio libre. En los SNARK para campos grandes, suele haber mucho espacio libre: la lógica empresarial y las tablas de búsqueda a menudo implican cálculos con números pequeños (estos números tienden a ser menores que N, donde N es el número total de pasos en un cálculo, por lo que en practica menos de 2^{25 }), pero aún tienes que pagar el costo de usar un campo de tamaño 2^{256} bits. Aquí, el tamaño del campo es 2^{31}, por lo que el espacio desperdiciado no es enorme. Los hashes de baja complejidad aritmética diseñados para SNARK (como Poseidon) aprovechan al máximo cada bit de cada número en la traza en cualquier campo.

Binius es una mejor solución que Circle STARK porque le permite mezclar campos de diferentes tamaños, lo que resulta en un empaquetado de bits más eficiente. Binius también ofrece la opción de realizar adiciones de 32 bits sin la sobrecarga de las tablas de búsqueda. Sin embargo, estas ventajas tienen el costo (en mi opinión) de hacer el concepto más complejo, mientras que los Circle STARK (y los STARK normales basados ​​en BabyBear) son conceptualmente mucho más simples.

Conclusión: Mis pensamientos sobre Circle STARK

Los Circle STARK no son más complicados para los desarrolladores que los STARK. Durante el proceso de implementación, los tres problemas mencionados anteriormente son básicamente las diferencias con el FRI convencional. Aunque las matemáticas detrás de los polinomios con los que opera Circle FRI son muy complejas y lleva algún tiempo comprenderlas y apreciarlas, esta complejidad en realidad está tan oculta que los desarrolladores no la sienten directamente.

Comprender Circle FRI y Circle FFT también puede ser una puerta de entrada para comprender otras FFT especiales: en particular las FFT de dominio binario, como las utilizadas por Binius y anteriormente LibSTARK, pero también algunas construcciones más complejas, como las FFT de curva elíptica, que utilizan pocas FFT. El mapeo de muchos se puede combinar bien con operaciones de puntos de curvas elípticas.

Combinado con Mersenne31, BabyBear y tecnologías de dominio binario como Binius, realmente sentimos que nos estamos acercando a los límites de eficiencia de la capa base de STARK. En este punto, predigo que la dirección de optimización de STARK se centrará en los siguientes puntos:

Aritmetización de funciones hash, firmas, etc. para maximizar la eficiencia: Optimice las primitivas criptográficas básicas, como funciones hash y firmas digitales, en sus formas más eficientes para que puedan lograr un rendimiento óptimo cuando se utilicen en pruebas STARK. Esto significa optimizaciones especiales para estas primitivas para reducir el esfuerzo computacional y aumentar la eficiencia.

Construcción recursiva para permitir una mayor paralelización: la construcción recursiva se refiere a la aplicación recursiva del proceso de prueba STARK a diferentes niveles, aumentando así las capacidades de procesamiento paralelo. De esta manera, los recursos informáticos se pueden utilizar de manera más eficiente y se puede acelerar el proceso de prueba.

Aritmetizar máquinas virtuales para mejorar la experiencia del desarrollador: la aritmetización de máquinas virtuales permite a los desarrolladores crear y ejecutar tareas informáticas de manera más eficiente y sencilla. Esto incluye optimizar la máquina virtual para su uso en pruebas STARK y mejorar la experiencia del desarrollador al crear y probar contratos inteligentes u otras tareas informáticas.