Análisis de los principios de Binius STARKs y reflexiones 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, pero para garantizar la seguridad de las pruebas basadas en árboles de Merkle, al utilizar la codificación de Reed-Solomon para expandir los datos, muchos valores redundantes adicionales ocuparán todo el dominio. Para abordar este problema, 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 campo binario permite operar directamente sobre los bits, con una codificación compacta y eficiente sin ningún espacio desperdiciado, es decir, la cuarta generación de STARKs.
Cuando se utilizan campos más pequeños, la operación de extensión de campo se vuelve cada vez más importante para garantizar la seguridad. El campo binario utilizado por Binius depende completamente de la extensión de campo para garantizar su seguridad y viabilidad práctica. La mayoría de los polinomios involucrados en los cálculos de Prover no necesitan entrar en la extensión de campo, sino que operan solo en el campo base, logrando así una alta eficiencia en campos pequeños. Sin embargo, la verificación de puntos aleatorios y el cálculo de FRI aún necesitan profundizar en un campo de extensión más grande para garantizar la seguridad requerida.
Al construir un sistema de prueba basado en el dominio binario, existen 2 problemas prácticos: al calcular la representación de la traza en STARKs, el tamaño del dominio utilizado debe ser mayor que el grado del polinomio; al comprometer el árbol de Merkle en STARKs, se debe realizar la codificación de Reed-Solomon, y el tamaño del dominio utilizado debe ser mayor que el tamaño después de la expansión de la codificación.
Binius propuso una solución innovadora que aborda estos dos problemas de forma separada y logra representar los mismos datos de dos maneras diferentes: en primer lugar, utilizando polinomios multivariables (específicamente polinomios multilineales) en lugar de polinomios univariables, representando toda la trayectoria de cálculo a través de sus valores en "hipercubos"; en segundo lugar, dado que la longitud de cada dimensión del hipercubo es 2, no se puede realizar la expansión estándar de Reed-Solomon como en STARKs, pero se puede considerar el hipercubo como cuadrado, basando la expansión de Reed-Solomon en ese cuadrado. Este método, al tiempo que garantiza la seguridad, mejora enormemente la eficiencia de codificación y el rendimiento de cálculo.
2 Análisis de principios
La construcción de la mayoría de los sistemas SNARKs actuales generalmente incluye las siguientes dos partes:
Prueba de Oracle Interactiva Polinómica Teórica de la Información (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP)
Esquema de Compromiso Polinómico (Polynomial Commitment Scheme, PCS)
Binius: HyperPlonk PIOP + Brakedown PCS + dominio binario. En concreto, Binius incluye cinco tecnologías clave para lograr su eficiencia y seguridad:
Arithmetización basada en el dominio binario en torre
Versión adaptada de la verificación de productos y permutaciones de HyperPlonk
Nueva prueba de desplazamiento multilineal
Versión mejorada del teorema de búsqueda Lasso
Esquema de compromiso de polinomios de pequeño dominio
2.1 Campos finitos: aritmética basada en torres de campos binarios
El campo binario en forma de torre es clave para implementar cálculos verificables rápidos, principalmente debido a dos aspectos: cálculos eficientes y aritmética eficiente. El campo binario, en esencia, soporta operaciones aritméticas altamente eficientes, lo que lo convierte en una opción ideal para aplicaciones criptográficas sensibles a la demanda de rendimiento. Además, la estructura del campo binario admite un proceso de aritmética simplificado, es decir, las operaciones realizadas en el campo binario pueden representarse en una forma algebraica compacta y fácil de verificar.
En el campo de los números primos Fp, los métodos de reducción comunes incluyen la reducción de Barrett, la reducción de Montgomery, así como métodos de reducción especiales para campos finitos específicos como Mersenne-31 o Goldilocks-64. En el campo binario F2k, los métodos de reducción comunes incluyen reducciones especiales (como las utilizadas en AES), reducción de Montgomery (como se utiliza en POLYVAL) y reducción recursiva (como Tower).
El campo binario no requiere llevar en las operaciones de suma y multiplicación, y la operación de cuadrado en el campo binario es muy eficiente, ya que sigue la regla simplificada (X + Y )2 = X2 + Y 2.
2.2 PIOP: versión adaptada de HyperPlonk Product y PermutationCheck
El diseño de PIOP en el protocolo Binius se basa en HyperPlonk y utiliza una serie de mecanismos de verificación fundamentales para validar la corrección de polinomios y conjuntos de múltiples variables. Estas verificaciones fundamentales incluyen:
GateCheck
PermutationCheck
LookupCheck
MultisetCheck
ProductCheck
ZeroCheck
SumCheck
BatchCheck
Binius ha realizado las siguientes mejoras en comparación con HyperPlonk:
Optimización de ProductCheck
Manejo del problema de división por cero
Comprobación de Permutación de Filas
2.3 PIOP: nuevo argumento de desplazamiento multilineal
En el protocolo Binius, la construcción y el manejo de polinomios virtuales es una de las tecnologías clave, que permite generar y operar de manera efectiva los polinomios derivados de un manejador de entrada u otros polinomios virtuales. A continuación se presentan dos métodos clave:
Empacando
Operador de desplazamiento
2.4 PIOP: argumento de búsqueda Lasso adaptado
El protocolo Lasso permite que la parte que prueba se comprometa a un vector a ∈ Fm y demuestre que todos sus elementos existen en una tabla previamente especificada t ∈ Fn. El protocolo Lasso se compone de los siguientes tres componentes:
Abstracción de polinomios virtuales en tablas grandes
Búsqueda de tabla pequeña
Comprobación de múltiples conjuntos
El protocolo Binius adapta Lasso a operaciones en el dominio binario, introduciendo una versión multiplicativa del protocolo Lasso.
2.5 PCS: Versión adaptada Brakedown PCS
La idea central de construir BiniusPCS es el packing. El documento de Binius proporciona 2 esquemas de compromiso de polinomios Brakedown basados en dominios binarios:
Utilizar código concatenado para instanciar
Utiliza la tecnología de codificación a nivel de bloque, que admite el uso independiente de códigos de Reed-Solomon.
El compromiso polinómico de Binius utiliza principalmente las siguientes tecnologías:
Compromisos de polinomios de pequeño dominio y evaluación en dominios ampliados
Construcción general de pequeños dominios
Codificación de bloques y código de Reed-Solomon
3 Optimización del pensamiento
Para mejorar aún más el rendimiento del protocolo Binius, este artículo propone cuatro puntos clave de optimización:
PIOP basado en GKR: para operaciones de multiplicación en el dominio binario
Optimización de ZeroCheck PIOP: equilibrio del costo de cálculo entre Prover y Verifier
Optimización de Sumcheck PIOP: Optimización para Sumcheck en dominios pequeños
Optimización de PCS: optimización a través de FRI-Binius
3.1 PIOP basado en GKR: multiplicación de campos binarios basada en GKR
El algoritmo de multiplicación de enteros basado en GKR convierte "verificar si 2 enteros de 32 bits A y B satisfacen A·B =? C" en "verificar si (gA)B =? gC es válido", lo que reduce significativamente el costo de compromiso gracias al protocolo GKR.
3.2 Optimización de ZeroCheck PIOP: Compensación de costos de cálculo entre Prover y Verifier
El artículo "Some Improvements for the PIOP for ZeroCheck" propone diversas soluciones de optimización para ajustar la distribución de la carga de trabajo entre la parte que prueba (P) y la parte que verifica (V), con el fin de equilibrar los costos. Las principales optimizaciones incluyen:
Reducir la transmisión de datos del probador
Reducir la cantidad de puntos de evaluación del probador.
Optimización de interpolación algebraica
3.3 Optimización de PIOP de Sumcheck: Protocolo Sumcheck basado en pequeños dominios
Ingonyama propuso en 2024 una mejora del protocolo Sumcheck basado en pequeños dominios y publicó el código de implementación como código abierto. Las principales optimizaciones incluyen:
Efecto del cambio de ronda y factor de mejora
El impacto del tamaño del dominio en el rendimiento
Beneficios de la optimización del algoritmo de Karatsuba
Mejora de la eficiencia de la memoria
3.4 PCS Optimización: FRI-Binius reduce el tamaño de prueba de Binius
El artículo "Pruebas polilogarítmicas para multilínea sobre torres binarias", abreviado como FRI-Binius, implementa el mecanismo de plegado FRI sobre el campo binario, aportando innovaciones en 4 aspectos:
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 la prueba de Binius en un orden de magnitud.
4 Resumen
Binius es un "esquema de diseño colaborativo que utiliza hardware, software y el protocolo Sumcheck acelerado en FPGA", que puede probar rápidamente con un uso de memoria muy bajo. En Binius se ha eliminado prácticamente el cuello de botella del compromiso del Prover, el nuevo cuello de botella está en el protocolo Sumcheck, y los problemas de evaluaciones polinómicas y multiplicación de campos en el protocolo Sumcheck se pueden resolver de manera eficiente con hardware especializado.
El plan FRI-Binius, una variante de FRI, ofrece una opción muy atractiva: eliminar los costos de incrustación de la capa de prueba de dominio sin provocar un aumento de costos en la capa de prueba agregada. Actualmente, el equipo de Irreducible está desarrollando su capa recursiva y ha anunciado una colaboración con el equipo de Polygon para construir un zkVM basado en Binius; JoltzkVM está pasando de Lasso a Binius para mejorar su rendimiento recursivo; el equipo de Ingonyama está implementando una versión de Binius en FPGA.
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.
26 me gusta
Recompensa
26
8
Republicar
Compartir
Comentar
0/400
AirdropF5Bro
· hace19h
Oh oh, esta ola de starknet es impresionante.
Ver originalesResponder0
¯\_(ツ)_/¯
· 08-12 16:41
Esta optimización es demasiado impresionante, de 252 a binario.
Ver originalesResponder0
SerumSquirter
· 08-10 20:16
La eficiencia es cada vez mayor y el dominio es cada vez más pequeño.
Ver originalesResponder0
GateUser-afe07a92
· 08-10 09:35
Qué aburrido, el siguiente
Ver originalesResponder0
ForkTongue
· 08-10 09:20
Está muy bien escrito, pero no lo entendí de manera profesional...
Ver originalesResponder0
NullWhisperer
· 08-10 09:16
hmm... la optimización de campos binarios parece teóricamente elegante, pero hablemos de esos casos límite en las operaciones de campo de extensión...
Ver originalesResponder0
HalfBuddhaMoney
· 08-10 09:15
¿Cuánto tiempo ha pasado sin traducir el dominio de ancho cero? Esta vez lo haré claro.
Ver originalesResponder0
NonFungibleDegen
· 08-10 09:08
ser esta cosa stark se basa en... binarios = el número sube, finalmente algo de verdadero alpha no esta copia del árbol merkle
Análisis del principio de Binius STARKs: optimización de dominios binarios y compromisos polinómicos eficientes
Análisis de los principios de Binius STARKs y reflexiones 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, pero para garantizar la seguridad de las pruebas basadas en árboles de Merkle, al utilizar la codificación de Reed-Solomon para expandir los datos, muchos valores redundantes adicionales ocuparán todo el dominio. Para abordar este problema, 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 campo binario permite operar directamente sobre los bits, con una codificación compacta y eficiente sin ningún espacio desperdiciado, es decir, la cuarta generación de STARKs.
Cuando se utilizan campos más pequeños, la operación de extensión de campo se vuelve cada vez más importante para garantizar la seguridad. El campo binario utilizado por Binius depende completamente de la extensión de campo para garantizar su seguridad y viabilidad práctica. La mayoría de los polinomios involucrados en los cálculos de Prover no necesitan entrar en la extensión de campo, sino que operan solo en el campo base, logrando así una alta eficiencia en campos pequeños. Sin embargo, la verificación de puntos aleatorios y el cálculo de FRI aún necesitan profundizar en un campo de extensión más grande para garantizar la seguridad requerida.
Al construir un sistema de prueba basado en el dominio binario, existen 2 problemas prácticos: al calcular la representación de la traza en STARKs, el tamaño del dominio utilizado debe ser mayor que el grado del polinomio; al comprometer el árbol de Merkle en STARKs, se debe realizar la codificación de Reed-Solomon, y el tamaño del dominio utilizado debe ser mayor que el tamaño después de la expansión de la codificación.
Binius propuso una solución innovadora que aborda estos dos problemas de forma separada y logra representar los mismos datos de dos maneras diferentes: en primer lugar, utilizando polinomios multivariables (específicamente polinomios multilineales) en lugar de polinomios univariables, representando toda la trayectoria de cálculo a través de sus valores en "hipercubos"; en segundo lugar, dado que la longitud de cada dimensión del hipercubo es 2, no se puede realizar la expansión estándar de Reed-Solomon como en STARKs, pero se puede considerar el hipercubo como cuadrado, basando la expansión de Reed-Solomon en ese cuadrado. Este método, al tiempo que garantiza la seguridad, mejora enormemente la eficiencia de codificación y el rendimiento de cálculo.
2 Análisis de principios
La construcción de la mayoría de los sistemas SNARKs actuales generalmente incluye las siguientes dos partes:
Binius: HyperPlonk PIOP + Brakedown PCS + dominio binario. En concreto, Binius incluye cinco tecnologías clave para lograr su eficiencia y seguridad:
2.1 Campos finitos: aritmética basada en torres de campos binarios
El campo binario en forma de torre es clave para implementar cálculos verificables rápidos, principalmente debido a dos aspectos: cálculos eficientes y aritmética eficiente. El campo binario, en esencia, soporta operaciones aritméticas altamente eficientes, lo que lo convierte en una opción ideal para aplicaciones criptográficas sensibles a la demanda de rendimiento. Además, la estructura del campo binario admite un proceso de aritmética simplificado, es decir, las operaciones realizadas en el campo binario pueden representarse en una forma algebraica compacta y fácil de verificar.
En el campo de los números primos Fp, los métodos de reducción comunes incluyen la reducción de Barrett, la reducción de Montgomery, así como métodos de reducción especiales para campos finitos específicos como Mersenne-31 o Goldilocks-64. En el campo binario F2k, los métodos de reducción comunes incluyen reducciones especiales (como las utilizadas en AES), reducción de Montgomery (como se utiliza en POLYVAL) y reducción recursiva (como Tower).
El campo binario no requiere llevar en las operaciones de suma y multiplicación, y la operación de cuadrado en el campo binario es muy eficiente, ya que sigue la regla simplificada (X + Y )2 = X2 + Y 2.
2.2 PIOP: versión adaptada de HyperPlonk Product y PermutationCheck
El diseño de PIOP en el protocolo Binius se basa en HyperPlonk y utiliza una serie de mecanismos de verificación fundamentales para validar la corrección de polinomios y conjuntos de múltiples variables. Estas verificaciones fundamentales incluyen:
Binius ha realizado las siguientes mejoras en comparación con HyperPlonk:
2.3 PIOP: nuevo argumento de desplazamiento multilineal
En el protocolo Binius, la construcción y el manejo de polinomios virtuales es una de las tecnologías clave, que permite generar y operar de manera efectiva los polinomios derivados de un manejador de entrada u otros polinomios virtuales. A continuación se presentan dos métodos clave:
2.4 PIOP: argumento de búsqueda Lasso adaptado
El protocolo Lasso permite que la parte que prueba se comprometa a un vector a ∈ Fm y demuestre que todos sus elementos existen en una tabla previamente especificada t ∈ Fn. El protocolo Lasso se compone de los siguientes tres componentes:
El protocolo Binius adapta Lasso a operaciones en el dominio binario, introduciendo una versión multiplicativa del protocolo Lasso.
2.5 PCS: Versión adaptada Brakedown PCS
La idea central de construir BiniusPCS es el packing. El documento de Binius proporciona 2 esquemas de compromiso de polinomios Brakedown basados en dominios binarios:
El compromiso polinómico de Binius utiliza principalmente las siguientes tecnologías:
3 Optimización del pensamiento
Para mejorar aún más el rendimiento del protocolo Binius, este artículo propone cuatro puntos clave de optimización:
3.1 PIOP basado en GKR: multiplicación de campos binarios basada en GKR
El algoritmo de multiplicación de enteros basado en GKR convierte "verificar si 2 enteros de 32 bits A y B satisfacen A·B =? C" en "verificar si (gA)B =? gC es válido", lo que reduce significativamente el costo de compromiso gracias al protocolo GKR.
3.2 Optimización de ZeroCheck PIOP: Compensación de costos de cálculo entre Prover y Verifier
El artículo "Some Improvements for the PIOP for ZeroCheck" propone diversas soluciones de optimización para ajustar la distribución de la carga de trabajo entre la parte que prueba (P) y la parte que verifica (V), con el fin de equilibrar los costos. Las principales optimizaciones incluyen:
3.3 Optimización de PIOP de Sumcheck: Protocolo Sumcheck basado en pequeños dominios
Ingonyama propuso en 2024 una mejora del protocolo Sumcheck basado en pequeños dominios y publicó el código de implementación como código abierto. Las principales optimizaciones incluyen:
3.4 PCS Optimización: FRI-Binius reduce el tamaño de prueba de Binius
El artículo "Pruebas polilogarítmicas para multilínea sobre torres binarias", abreviado como FRI-Binius, implementa el mecanismo de plegado FRI sobre el campo binario, aportando innovaciones en 4 aspectos:
Con FRI-Binius, se puede reducir el tamaño de la prueba de Binius en un orden de magnitud.
4 Resumen
Binius es un "esquema de diseño colaborativo que utiliza hardware, software y el protocolo Sumcheck acelerado en FPGA", que puede probar rápidamente con un uso de memoria muy bajo. En Binius se ha eliminado prácticamente el cuello de botella del compromiso del Prover, el nuevo cuello de botella está en el protocolo Sumcheck, y los problemas de evaluaciones polinómicas y multiplicación de campos en el protocolo Sumcheck se pueden resolver de manera eficiente con hardware especializado.
El plan FRI-Binius, una variante de FRI, ofrece una opción muy atractiva: eliminar los costos de incrustación de la capa de prueba de dominio sin provocar un aumento de costos en la capa de prueba agregada. Actualmente, el equipo de Irreducible está desarrollando su capa recursiva y ha anunciado una colaboración con el equipo de Polygon para construir un zkVM basado en Binius; JoltzkVM está pasando de Lasso a Binius para mejorar su rendimiento recursivo; el equipo de Ingonyama está implementando una versión de Binius en FPGA.