Análisis de los principios de Binius STARKs y reflexión sobre su optimización
1. Introducción
Una de las principales razones de la ineficiencia de STARKs es que la mayoría de los valores en los programas reales son bastante pequeños. Sin embargo, para garantizar la seguridad de las pruebas basadas en árboles de Merkle, al usar codificación de Reed-Solomon para expandir los datos, muchos valores redundantes adicionales ocuparán todo el dominio. Reducir el tamaño del dominio se ha convertido en una estrategia clave.
La primera generación de codificación STARKs tiene un ancho de banda de 252 bits, la segunda generación de 64 bits y la tercera generación de 32 bits, pero el ancho de banda de 32 bits todavía presenta un gran desperdicio de espacio. En comparación, el dominio binario permite operaciones bit a bit directamente, con una codificación compacta y eficiente sin desperdicio alguno, es decir, la cuarta generación de STARKs.
En comparación con los campos finitos investigados en los últimos años, como Goldilocks, BabyBear y Mersenne31, la investigación en campos binarios se remonta a la década de 1980 y se ha aplicado ampliamente en la criptografía, como en el campo AES(F28, el campo GMAC)F2128, el código QR( y la codificación Reed-Solomon).
Binius utiliza el dominio binario, y depende completamente de la extensión del dominio para garantizar la seguridad y la disponibilidad. La mayoría de los cálculos de Prover operan de manera eficiente en el campo base, mientras que la verificación de puntos aleatorios y el cálculo de FRI requieren una extensión profunda del dominio para garantizar la seguridad.
Binius representa la trayectoria de cálculo mediante polinomios multivariables en el "hipercubo", tratando el hipercubo como un cuadrado para la extensión de Reed-Solomon, lo que mejora enormemente la eficiencia de codificación y el rendimiento computacional, al tiempo que garantiza la seguridad.
Fundamento de cálculo aritmético basado en dominios binarios en torre.
Adaptar la verificación de producto y permutación de HyperPlonk, asegurando la consistencia en la verificación de variables y permutaciones
Nueva prueba de desplazamiento multilineal, optimización de la eficiencia de verificación de relaciones multilineales en pequeños dominios.
Versión mejorada de la prueba de búsqueda Lasso, que proporciona flexibilidad y seguridad al mecanismo de búsqueda
Esquema de compromiso de polinomios de pequeño dominio, que implementa un sistema de prueba eficiente sobre un campo binario.
( 2.1 Campo finito: aritmética basada en torres de campos binarios
El dominio binario en torre soporta operaciones aritméticas eficientes y simplifica el proceso aritmético, siendo especialmente adecuado para sistemas de prueba escalables como Binius.
Una cadena de 128 bits puede considerarse un elemento único en un campo binario de 128 bits, o descomponerse en dos elementos de campo de 64 bits, cuatro elementos de campo de 32 bits, dieciséis elementos de campo de 8 bits, o 128 elementos de campo F2. Esta flexibilidad no requiere sobrecarga de cálculo, solo una conversión de tipo de cadena de bits.
![Bitlayer Research: Análisis de los principios de Binius STARKs y reflexiones sobre su optimización])https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp###
( 2.2 PIOP: versión adaptada del producto HyperPlonk y PermutationCheck
Binius PIOP se inspira en HyperPlonk y utiliza un mecanismo de verificación central para validar la corrección de polinomios y conjuntos multivariables, incluyendo GateCheck, PermutationCheck, LookupCheck, MultisetCheck, ProductCheck, ZeroCheck, SumCheck y BatchCheck.
Binius ha realizado mejoras en las siguientes 3 áreas:
Optimización de ProductCheck: especializar el valor en 1, simplificar el proceso de verificación y reducir la complejidad computacional
Manejo del problema de división por cero: manejar correctamente la situación en la que el denominador es cero, permitiendo la extensión a cualquier valor de producto
Comprobación de Permutación entre columnas: soporta la Comprobación de Permutación entre múltiples columnas, manejando situaciones de arreglos polinómicos más complejos.
) 2.3 PIOP: nuevo argumento de desplazamiento multilineal
La construcción y el procesamiento de polinomios virtuales en Binius son tecnologías clave:
Packing: empaquetar elementos más pequeños en posiciones adyacentes del diccionario en elementos más grandes para optimizar la operación
Operador de desplazamiento: reorganiza los elementos dentro del bloque, desplazándolos cíclicamente según el desplazamiento dado
![Bitlayer Research: Análisis de los principios de Binius STARKs y reflexiones sobre su optimización]###https://img-cdn.gateio.im/webp-social/moments-a5d031be4711f29ef910057f4e44a118.webp###
( 2.4 PIOP: Versión adaptada del argumento de búsqueda Lasso
El protocolo Lasso permite que la parte que prueba se comprometa a un vector a ∈ Fm y demuestre que todos los elementos existen en una tabla previamente especificada t ∈ Fn.
Binius adapta Lasso a operaciones en el campo binario, introduciendo la versión multiplicativa del protocolo Lasso, que requiere que el probador y el verificador unan el protocolo de incremento "conteo de memoria", generando un incremento de los generadores a través de la multiplicación en el campo binario.
) 2.5 PCS: versión adaptada Brakedown PCS
La idea central de BiniusPCS es el packing. Se ofrecen 2 esquemas de compromiso de polinomios Brakedown basados en el campo binario:
Instanciar utilizando el código concatenado
Utilizando la tecnología de codificación a nivel de bloque, soporta el uso independiente de códigos de Reed-Solomon.
La segunda opción simplifica el proceso de prueba y verificación, el tamaño de la prueba es un poco más grande, pero las ventajas de simplificación e implementación valen la pena.
![Investigación de Bitlayer: Análisis de los principios de Binius STARKs y reflexiones sobre su optimización]###https://img-cdn.gateio.im/webp-social/moments-d74bdd8bc21dcfc05e21f9c0074461c3.webp###
3. Optimización del pensamiento
( 3.1 PIOP basado en GKR: multiplicación de dominios binarios basada en GKR
Convierte "Verificar si A·B =? C para 2 enteros de 32 bits A y B" en "Verificar si )gA###B =? gC es cierto", reduciendo significativamente el costo de compromiso con el protocolo GKR.
La operación de multiplicación basada en GKR solo requiere un compromiso auxiliar, lo que hace que el algoritmo sea más eficiente al reducir el costo de los Sumchecks, especialmente en escenarios donde las operaciones de Sumchecks son más baratas que la generación de compromisos.
( 3.2 ZeroCheck PIOP optimización: compensación de costos de Prover y Verifier
Reducir la transmisión de datos del demostrador: trasladar parte del trabajo al validador, reduciendo la cantidad de datos enviados por el demostrador.
Reducir el número de puntos de evaluación del probador: modificar el método de envío del polinomio y reducir el número de puntos de evaluación.
Optimización de interpolación algebraica: construir una descomposición ordenada mediante la división larga de polinomios para lograr la optimización de la interpolación.
![Bitlayer Research: Análisis de los principios de Binius STARKs y consideraciones de optimización])https://img-cdn.gateio.im/webp-social/moments-7f96976952fd0f8da0e93ff1042a966d.webp###
( 3.3 Optimización de PIOP de Sumcheck: protocolo Sumcheck basado en pequeños dominios
El impacto y el factor de mejora de los cambios de ronda: la selección de cambios de ronda t afecta el rendimiento, el factor de mejora del mejor punto de cambio alcanza su valor máximo.
Impacto del tamaño del campo base en el rendimiento: un campo base más pequeño ), como GF###(, muestra ventajas más significativas en el algoritmo de optimización.
Optimización de beneficios del algoritmo Karatsuba: mejora significativa en el rendimiento del Sumcheck basado en pequeños dominios, el algoritmo 4 es cinco veces más eficiente que el algoritmo 3.
Mejora de la eficiencia de la memoria: La demanda de memoria del algoritmo 4 es O[2]d·t), mientras que la del algoritmo 3 es O(2d·t), adecuado para entornos con recursos limitados.
( 3.4 PCS Optimización: FRI-Binius reduce el tamaño de prueba de Binius
FRI-Binius implementa el mecanismo de pliegue de dominio binario FRI, que trae 4 innovaciones:
Polinomio plano
Polinomio de desaparición del subespacio
Paquete de base algebraica
Intercambio de suma de verificación
Con FRI-Binius, se puede reducir el tamaño de prueba de Binius en un orden de magnitud, acercándose a los sistemas más avanzados.
![Bitlayer Research: Análisis de los principios de Binius STARKs y reflexiones sobre su optimización])https://img-cdn.gateio.im/webp-social/moments-16690fad3bc761b99c40e8e82ab2297c.webp###
4. Resumen
Binius ha eliminado básicamente el cuello de botella de compromiso Prover, el nuevo cuello de botella está en el protocolo Sumcheck. El esquema FRI-Binius es una variante de FRI que puede eliminar el costo de incrustación de la capa de prueba de dominio.
El equipo de Irreducible desarrolla capas recursivas, en colaboración con Polygon para construir un zkVM basado en Binius. JoltzkVM pasa de Lasso a Binius para mejorar el rendimiento recursivo. Ingonyama implementa la versión FPGA de Binius.
Ver originales
Esta página puede contener contenido de terceros, que se proporciona únicamente con fines informativos (sin garantías ni declaraciones) y no debe considerarse como un respaldo por parte de Gate a las opiniones expresadas ni como asesoramiento financiero o profesional. Consulte el Descargo de responsabilidad para obtener más detalles.
9 me gusta
Recompensa
9
5
Compartir
Comentar
0/400
Anon4461
· 07-12 02:37
¿Qué es esto? Tan profundo que me duele la cabeza.
Ver originalesResponder0
faded_wojak.eth
· 07-09 12:09
No entiendo nada, esto es demasiado avanzado.
Ver originalesResponder0
DataPickledFish
· 07-09 07:26
Tsk tsk, el destino se basa en operaciones de desplazamiento.
Ver originalesResponder0
LiquidatedDreams
· 07-09 07:23
¿Alguien entiende lo que dijo Stark claramente?
Ver originalesResponder0
TokenToaster
· 07-09 07:14
Otra vez mostrando la técnica, el algoritmo debe ser explicado de manera que el novato lo entienda.
Binius: Exploración de los principios de STARKs y optimización de dominios binarios
Análisis de los principios de Binius STARKs y reflexión sobre su optimización
1. Introducción
Una de las principales razones de la ineficiencia de STARKs es que la mayoría de los valores en los programas reales son bastante pequeños. Sin embargo, para garantizar la seguridad de las pruebas basadas en árboles de Merkle, al usar codificación de Reed-Solomon para expandir los datos, muchos valores redundantes adicionales ocuparán todo el dominio. Reducir el tamaño del dominio se ha convertido en una estrategia clave.
La primera generación de codificación STARKs tiene un ancho de banda de 252 bits, la segunda generación de 64 bits y la tercera generación de 32 bits, pero el ancho de banda de 32 bits todavía presenta un gran desperdicio de espacio. En comparación, el dominio binario permite operaciones bit a bit directamente, con una codificación compacta y eficiente sin desperdicio alguno, es decir, la cuarta generación de STARKs.
En comparación con los campos finitos investigados en los últimos años, como Goldilocks, BabyBear y Mersenne31, la investigación en campos binarios se remonta a la década de 1980 y se ha aplicado ampliamente en la criptografía, como en el campo AES(F28, el campo GMAC)F2128, el código QR( y la codificación Reed-Solomon).
Binius utiliza el dominio binario, y depende completamente de la extensión del dominio para garantizar la seguridad y la disponibilidad. La mayoría de los cálculos de Prover operan de manera eficiente en el campo base, mientras que la verificación de puntos aleatorios y el cálculo de FRI requieren una extensión profunda del dominio para garantizar la seguridad.
Binius representa la trayectoria de cálculo mediante polinomios multivariables en el "hipercubo", tratando el hipercubo como un cuadrado para la extensión de Reed-Solomon, lo que mejora enormemente la eficiencia de codificación y el rendimiento computacional, al tiempo que garantiza la seguridad.
2. Análisis de principios
Binius: HyperPlonk PIOP + Brakedown PCS + dominio binario.
Incluye cinco tecnologías clave:
Fundamento de cálculo aritmético basado en dominios binarios en torre.
Adaptar la verificación de producto y permutación de HyperPlonk, asegurando la consistencia en la verificación de variables y permutaciones
Nueva prueba de desplazamiento multilineal, optimización de la eficiencia de verificación de relaciones multilineales en pequeños dominios.
Versión mejorada de la prueba de búsqueda Lasso, que proporciona flexibilidad y seguridad al mecanismo de búsqueda
Esquema de compromiso de polinomios de pequeño dominio, que implementa un sistema de prueba eficiente sobre un campo binario.
( 2.1 Campo finito: aritmética basada en torres de campos binarios
El dominio binario en torre soporta operaciones aritméticas eficientes y simplifica el proceso aritmético, siendo especialmente adecuado para sistemas de prueba escalables como Binius.
Una cadena de 128 bits puede considerarse un elemento único en un campo binario de 128 bits, o descomponerse en dos elementos de campo de 64 bits, cuatro elementos de campo de 32 bits, dieciséis elementos de campo de 8 bits, o 128 elementos de campo F2. Esta flexibilidad no requiere sobrecarga de cálculo, solo una conversión de tipo de cadena de bits.
![Bitlayer Research: Análisis de los principios de Binius STARKs y reflexiones sobre su optimización])https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp###
( 2.2 PIOP: versión adaptada del producto HyperPlonk y PermutationCheck
Binius PIOP se inspira en HyperPlonk y utiliza un mecanismo de verificación central para validar la corrección de polinomios y conjuntos multivariables, incluyendo GateCheck, PermutationCheck, LookupCheck, MultisetCheck, ProductCheck, ZeroCheck, SumCheck y BatchCheck.
Binius ha realizado mejoras en las siguientes 3 áreas:
Optimización de ProductCheck: especializar el valor en 1, simplificar el proceso de verificación y reducir la complejidad computacional
Manejo del problema de división por cero: manejar correctamente la situación en la que el denominador es cero, permitiendo la extensión a cualquier valor de producto
Comprobación de Permutación entre columnas: soporta la Comprobación de Permutación entre múltiples columnas, manejando situaciones de arreglos polinómicos más complejos.
) 2.3 PIOP: nuevo argumento de desplazamiento multilineal
La construcción y el procesamiento de polinomios virtuales en Binius son tecnologías clave:
Packing: empaquetar elementos más pequeños en posiciones adyacentes del diccionario en elementos más grandes para optimizar la operación
Operador de desplazamiento: reorganiza los elementos dentro del bloque, desplazándolos cíclicamente según el desplazamiento dado
![Bitlayer Research: Análisis de los principios de Binius STARKs y reflexiones sobre su optimización]###https://img-cdn.gateio.im/webp-social/moments-a5d031be4711f29ef910057f4e44a118.webp###
( 2.4 PIOP: Versión adaptada del argumento de búsqueda Lasso
El protocolo Lasso permite que la parte que prueba se comprometa a un vector a ∈ Fm y demuestre que todos los elementos existen en una tabla previamente especificada t ∈ Fn.
Binius adapta Lasso a operaciones en el campo binario, introduciendo la versión multiplicativa del protocolo Lasso, que requiere que el probador y el verificador unan el protocolo de incremento "conteo de memoria", generando un incremento de los generadores a través de la multiplicación en el campo binario.
) 2.5 PCS: versión adaptada Brakedown PCS
La idea central de BiniusPCS es el packing. Se ofrecen 2 esquemas de compromiso de polinomios Brakedown basados en el campo binario:
Instanciar utilizando el código concatenado
Utilizando la tecnología de codificación a nivel de bloque, soporta el uso independiente de códigos de Reed-Solomon.
La segunda opción simplifica el proceso de prueba y verificación, el tamaño de la prueba es un poco más grande, pero las ventajas de simplificación e implementación valen la pena.
![Investigación de Bitlayer: Análisis de los principios de Binius STARKs y reflexiones sobre su optimización]###https://img-cdn.gateio.im/webp-social/moments-d74bdd8bc21dcfc05e21f9c0074461c3.webp###
3. Optimización del pensamiento
( 3.1 PIOP basado en GKR: multiplicación de dominios binarios basada en GKR
Convierte "Verificar si A·B =? C para 2 enteros de 32 bits A y B" en "Verificar si )gA###B =? gC es cierto", reduciendo significativamente el costo de compromiso con el protocolo GKR.
La operación de multiplicación basada en GKR solo requiere un compromiso auxiliar, lo que hace que el algoritmo sea más eficiente al reducir el costo de los Sumchecks, especialmente en escenarios donde las operaciones de Sumchecks son más baratas que la generación de compromisos.
( 3.2 ZeroCheck PIOP optimización: compensación de costos de Prover y Verifier
Reducir la transmisión de datos del demostrador: trasladar parte del trabajo al validador, reduciendo la cantidad de datos enviados por el demostrador.
Reducir el número de puntos de evaluación del probador: modificar el método de envío del polinomio y reducir el número de puntos de evaluación.
Optimización de interpolación algebraica: construir una descomposición ordenada mediante la división larga de polinomios para lograr la optimización de la interpolación.
![Bitlayer Research: Análisis de los principios de Binius STARKs y consideraciones de optimización])https://img-cdn.gateio.im/webp-social/moments-7f96976952fd0f8da0e93ff1042a966d.webp###
( 3.3 Optimización de PIOP de Sumcheck: protocolo Sumcheck basado en pequeños dominios
El impacto y el factor de mejora de los cambios de ronda: la selección de cambios de ronda t afecta el rendimiento, el factor de mejora del mejor punto de cambio alcanza su valor máximo.
Impacto del tamaño del campo base en el rendimiento: un campo base más pequeño ), como GF###(, muestra ventajas más significativas en el algoritmo de optimización.
Optimización de beneficios del algoritmo Karatsuba: mejora significativa en el rendimiento del Sumcheck basado en pequeños dominios, el algoritmo 4 es cinco veces más eficiente que el algoritmo 3.
Mejora de la eficiencia de la memoria: La demanda de memoria del algoritmo 4 es O[2]d·t), mientras que la del algoritmo 3 es O(2d·t), adecuado para entornos con recursos limitados.
( 3.4 PCS Optimización: FRI-Binius reduce el tamaño de prueba de Binius
FRI-Binius implementa el mecanismo de pliegue de dominio binario FRI, que trae 4 innovaciones:
Con FRI-Binius, se puede reducir el tamaño de prueba de Binius en un orden de magnitud, acercándose a los sistemas más avanzados.
![Bitlayer Research: Análisis de los principios de Binius STARKs y reflexiones sobre su optimización])https://img-cdn.gateio.im/webp-social/moments-16690fad3bc761b99c40e8e82ab2297c.webp###
4. Resumen
Binius ha eliminado básicamente el cuello de botella de compromiso Prover, el nuevo cuello de botella está en el protocolo Sumcheck. El esquema FRI-Binius es una variante de FRI que puede eliminar el costo de incrustación de la capa de prueba de dominio.
El equipo de Irreducible desarrolla capas recursivas, en colaboración con Polygon para construir un zkVM basado en Binius. JoltzkVM pasa de Lasso a Binius para mejorar el rendimiento recursivo. Ingonyama implementa la versión FPGA de Binius.