1. IntroducciónA diferencia de los SNARKs basados en curvas elípticas, los STARKs se pueden ver como SNARKs basados en hash. Uno de los principales desafíos que contribuyen a la ineficiencia actual de los STARKs es que la mayoría de los valores en programas reales son relativamente pequeños, como los índices en los bucles for, los valores booleanos y los contadores. Sin embargo, para garantizar la seguridad de las pruebas basadas en árboles de Merkle, se utiliza la codificación de Reed-Solomon para ampliar los datos, lo que resulta en muchos valores redundantes que ocupan todo el campo, incluso cuando los valores originales son pequeños. Para abordar esta ineficiencia, reducir el tamaño del campo se ha convertido en una estrategia clave.
Como se muestra en la Tabla 1, la primera generación de STARKs tenía un ancho de codificación de 252 bits, la segunda generación 64 bits y la tercera generación 32 bits. A pesar del ancho de codificación reducido en la tercera generación, aún queda un espacio significativo desperdiciado. En contraste, los campos binarios permiten la manipulación directa a nivel de bit, lo que permite una codificación compacta y eficiente con un desperdicio mínimo. Esta eficiencia se realiza en la cuarta generación de STARKs.
Tabla 1: Ruta de derivación STARKsEn comparación con campos finitos como Ricitos de Oro, BabyBear y Mersenne31, que han ganado atención recientemente, la investigación de campo binario se remonta a la década de 1980. Hoy en día, los campos binarios se utilizan ampliamente en criptografía, con ejemplos notables que incluyen:
- Estándar de Cifrado Avanzado (AES), basado en el - 𝐹28- campo;- Código de Autenticación de Mensaje Galois (GMAC), basado en el - 𝐹2128- campo;- Códigos QR, que utilizan codificación Reed-Solomon basada en - 𝐹28- campo;- Los protocolos originales FRI y zk-STARK, así como la función hash Grøstl, finalista en la competencia SHA-3, que se basa en el - 𝐹28- campo y es adecuado para algoritmos de hash recursivos.Cuando se usan campos más pequeños, las operaciones de extensión de campo se vuelven cada vez más importantes para garantizar la seguridad. El campo binario utilizado por Binius se basa por completo en la extensión de campo para garantizar tanto la seguridad como la usabilidad práctica. La mayoría de los cálculos polinómicos involucrados en las operaciones de Prover no necesitan ingresar al campo extendido, ya que solo necesitan operar en el campo base, logrando así una alta eficiencia en el campo pequeño. Sin embargo, todavía se deben realizar verificaciones de punto aleatorias y cálculos FRI en un campo extendido más grande para garantizar el nivel necesario de seguridad.
Hay dos desafíos prácticos al construir un sistema de prueba basado en campos binarios: Primero, el tamaño del campo utilizado para la representación de trazas en STARKs debe ser mayor que el grado del polinomio. Segundo, el tamaño del campo utilizado para la confirmación del árbol de Merkle en STARKs debe ser mayor que el tamaño después de la extensión de codificación de Reed-Solomon.
Binius es una solución innovadora para abordar estos dos problemas al representar los mismos datos de dos formas diferentes: primero, mediante el uso de polinomios multivariados (específicamente polinomios multilineales) en lugar de polinomios univariados, representando toda la traza de cálculo a través de sus evaluaciones sobre 'hipercubos'. Segundo, dado que cada dimensión del hipercubo tiene una longitud de 2, no es posible realizar extensiones estándar de Reed-Solomon como en STARKs, pero el hipercubo puede tratarse como un cuadrado y se puede realizar una extensión de Reed-Solomon basada en este cuadrado. Este método no solo garantiza la seguridad, sino que también mejora considerablemente la eficiencia de codificación y el rendimiento computacional.
2. Principios de BiniusLa construcción de la mayoría de los sistemas SNARK modernos generalmente consta de los siguientes dos componentes:
-
Polinomio Interactivo de Prueba Oráculo (PIOP) de Teoría de la Información: Como núcleo del sistema de prueba, PIOP transforma relaciones computacionales desde la entrada en ecuaciones polinomiales verificables. Diferentes protocolos PIOP permiten al demostrador enviar polinomios de forma incremental a través de interacciones con el verificador. Esto permite al verificador confirmar la corrección de una computación mediante la consulta de solo un pequeño número de evaluaciones polinomiales. Varios protocolos PIOP, como PLONK PIOP, Spartan PIOP y HyperPlonk PIOP, manejan expresiones polinomiales de manera diferente, lo que impacta en el rendimiento y la eficiencia del sistema SNARK en general.- Esquema de Compromiso Polinomial (PCS): El PCS es una herramienta criptográfica utilizada para demostrar que las ecuaciones polinomiales generadas por el PIOP son válidas. Permite al probador comprometerse con un polinomio y verificar sus evaluaciones sin revelar información adicional sobre el polinomio. Los esquemas PCS comunes incluyen KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP) y Brakedown, cada uno ofreciendo características de rendimiento distintas, garantías de seguridad y escenarios aplicables.Al seleccionar diferentes esquemas PIOP y PCS y combinarlos con campos finitos o curvas elípticas adecuados, se pueden construir sistemas de prueba con propiedades distintas. Por ejemplo:
-
Halo2: Combina PLONK PIOP con Bulletproofs PCS y opera en la curva Pasta. Halo2 está diseñado teniendo en cuenta la escalabilidad y elimina la configuración de confianza utilizada anteriormente en el protocolo ZCash.- Plonky2: Combina PLONK PIOP con FRI PCS y se basa en el campo Goldilocks. Plonky2 está optimizado para una recursión eficiente.Al diseñar estos sistemas, la compatibilidad entre el PIOP, PCS y el campo finito o la curva elíptica elegidos es fundamental para garantizar la corrección, el rendimiento y la seguridad. Estas combinaciones influyen en el tamaño de la prueba SNARK, la eficiencia de la verificación y determinan si el sistema puede lograr transparencia sin una configuración confiable, así como admitir funciones avanzadas como pruebas recursivas o agregación de pruebas.
Binius combina HyperPlonk PIOP con Brakedown PCS y opera en un campo binario. Específicamente, Binius incorpora cinco tecnologías clave para lograr tanto eficiencia como seguridad:
- Aritmética basada en torres de campos binarios: esto forma la base computacional de Binius, permitiendo operaciones simplificadas dentro del campo binario.- Verificaciones de producto y permutación de HyperPlonk: Binius adapta las verificaciones de producto y permutación de HyperPlonk en su PIOP para garantizar una consistencia segura y eficiente entre variables y sus permutaciones.- Nuevo argumento de cambio multilineal: esta optimización mejora la verificación de relaciones multilineales dentro de campos pequeños, mejorando la eficiencia general.- Argumento de búsqueda de Lasso mejorado: El protocolo incorpora un mecanismo de búsqueda más flexible y seguro con este argumento avanzado.- Esquema de Compromiso de Polinomio de Campo Pequeño (PCS): Binius utiliza un PCS adaptado para campos pequeños, reduciendo la sobrecarga comúnmente asociada con campos más grandes y permitiendo un sistema de prueba eficiente en el campo binario.Estas innovaciones permiten a Binius ofrecer un sistema SNARK compacto y de alto rendimiento, optimizado para campos binarios, al mismo tiempo que mantiene una seguridad y escalabilidad sólidas.
2.1 Campos finitos: Aritmética basada en torres de campos binariosLas torres de campos binarios desempeñan un papel crítico en la realización de cálculos rápidos y verificables debido a dos factores principales: cálculos eficientes y aritmetización eficiente. Los campos binarios inherentemente admiten operaciones aritméticas altamente eficientes, lo que los hace ideales para aplicaciones criptográficas sensibles al rendimiento. Además, su estructura permite un proceso de aritmetización simplificado, donde las operaciones realizadas en campos binarios se pueden representar en formas algebraicas compactas y fácilmente verificables. Estas características, combinadas con la estructura jerárquica de las torres de campos binarios, las hacen particularmente adecuadas para sistemas de prueba escalables como Binius.
El término "canónico" se refiere a la representación única y directa de elementos en un campo binario. Por ejemplo, en el campo binario más básico $\mathbb{F}2
Esto difiere de los campos primos, que no ofrecen una representación canónica dentro de un número dado de bits. Aunque un campo principal de 32 bits puede caber dentro de 32 bits, tenga en cuenta que 32 bits pueden corresponder de forma única a un elemento de campo, mientras que los campos binarios proporcionan esta asignación de uno a uno.
\mathbb{F}_p$, los métodos comunes de reducción incluyen la reducción de Barrett, la reducción de Montgomery, así como métodos de reducción especializados para ciertos campos finitos como Mersenne-31 o Goldilocks-64. En campos binarios $\mathbb{F}{2^k}$, los métodos comunes de reducción incluyen la reducción especial (como se utiliza en AES), la reducción de Montgomery (como se utiliza en POLYVAL) y la reducción recursiva (como se utiliza en campos de Torre). El documento Explorando el espacio de diseño de implementaciones de hardware ECC en campo primo vs. campo binarioobserva que los campos binarios no requieren propagación de acarreo en la suma o multiplicación, y el cuadrado en campos binarios es altamente eficiente debido a la regla de simplificación
(𝑋+𝑌)2=𝑋2+𝑌2
.
Figura 1. Torres del Campo Binario
Como se muestra en la Figura 1, una cadena de 128 bits puede ser interpretada de múltiples maneras dentro del contexto de un campo binario. Puede ser vista como un elemento único en el campo binario de 128 bits, o puede ser analizada como dos elementos de campo de torre de 64 bits, cuatro elementos de campo de torre de 32 bits, dieciséis elementos de campo de torre de 8 bits, o 128 elementos de.
𝐹2
. Esta flexibilidad en la representación no conlleva ningún gasto computacional, ya que es simplemente una conversión de tipo de la cadena de bits. Esta es una propiedad muy interesante y útil, ya que elementos de campo más pequeños pueden ser empaquetados en elementos de campo más grandes sin coste computacional adicional. El protocolo Binius aprovecha esta propiedad para mejorar la eficiencia computacional. Además, el artículo En la inversión eficiente en campos de torres de característica dosexplora la complejidad computacional de la multiplicación, el cuadrado y la inversión en
𝑛
-bit torres de campos binarios (descomponibles en
𝑚
-bit subcampos).
2.2 PIOP: Producto HyperPlonk Adaptado y Verificación de Permutación - Adecuado para Campos BinariosEl diseño de PIOP en el protocolo Binius se inspira en HyperPlonk e incorpora una serie de comprobaciones básicas para verificar la corrección de polinomios y conjuntos multivariables. Estas comprobaciones son esenciales para garantizar la integridad de los cálculos dentro del sistema de prueba, especialmente cuando se opera en campos binarios. Las comprobaciones clave incluyen:
-
gateCheck: Asegura que el testigo privado - 𝜔- y entrada pública- 𝑥- satisfacer la relación de operación del circuito- 𝐶(𝑥,𝜔)=0- , verificando la ejecución correcta del circuito.- PermutationCheck: Verifica que los resultados de evaluación de dos polinomios multivariados sean- 𝑓- y - 𝑔- en el hipercaubo booleano forman una relación de permutación- 𝑓(𝑥)=𝑓(𝜋(𝑥))- , asegurando la consistencia entre las variables polinómicas.- LookupCheck: Comprueba si la evaluación de un polinomio está dentro de una tabla de búsqueda dada, es decir, - 𝑓(𝐵𝜇)⊆𝑇(𝐵𝜇)- , asegurando que ciertos valores se encuentren dentro de un rango especificado.- MultisetCheck: Confirms whether two multivariate sets are equal, i.e., ${(x*{1,i},x*{2,i})}{i \in H} = {(y{1,i},y*{2,i})}*{i \in H}$, asegurando consistencia entre diferentes conjuntos.- ProductCheck: Asegura que la evaluación de un polinomio racional en el hipercubo booleano sea igual a un valor declarado, es decir,- ∏𝑥∈𝐻𝜇𝑓(𝑥)=𝑠- , confirmando la corrección del producto polinómico.- ZeroCheck: Verifica si un polinomio multivariado se evalúa en cero en algún punto en el hipercubo booleano, es decir, - ∏x∈Hμf(x)=0- para todos- 𝑥∈𝐵𝜇- , asegurando la distribución adecuada de ceros en el polinomio.- SumCheck: Confirma si la suma de las evaluaciones de un polinomio multivariado es igual al valor declarado, es decir, - ∑𝑥∈𝐻𝜇𝑓(𝑥)=𝑠- . Al reducir la evaluación de polinomios multivariados a la evaluación de polinomios univariados, se reduce la complejidad computacional del verificador. SumCheck también permite el procesamiento por lotes, que construye combinaciones lineales utilizando números aleatorios para procesar múltiples instancias en lotes.- BatchCheck: Una extensión de SumCheck, verifica la corrección de múltiples evaluaciones de polinomios multivariados, aumentando la eficiencia del protocolo.Si bien Binius y HyperPlonk comparten varias similitudes en sus diseños de protocolo, Binius introduce las siguientes mejoras clave:
-
Optimización de ProductCheck: En HyperPlonk, ProductCheck requiere el denominador- 𝑈- ser distinto de cero en todo el hipercubo y que el producto coincida con un valor específico. Binius simplifica esta verificación estableciendo el valor del producto en 1, reduciendo la complejidad computacional general.- Manejo de problemas de división por cero: HyperPlonk no aborda eficazmente los problemas de división por cero, lo que dificulta garantizar que - 𝑈- permanece no nulo sobre el hipercubo. Binius resuelve esto manejando adecuadamente los escenarios de división por cero, permitiendo que ProductCheck funcione incluso cuando el denominador es cero, permitiendo extensiones a valores de productos arbitrarios.- Verificación de permutación entre columnas: HyperPlonk no admite verificaciones de permutación entre columnas. Binius aborda esta limitación al introducir soporte para la comprobación de permutación entre columnas, lo que permite que el protocolo gestione permutaciones polinómicas más complejas en varias columnas.Así, Binius mejora la flexibilidad y eficiencia del protocolo al mejorar el mecanismo existente de PIOP SumCheck, especialmente al proporcionar una funcionalidad más sólida para verificar polinomios multivariados más complejos. Estas mejoras no solo abordan las limitaciones de HyperPlonk, sino que también sientan las bases para sistemas futuros a prueba de fallos basados en campos binarios.
2.3 PIOP: Un nuevo argumento de cambio multilínea — Aplicable a Hypercube BooleanoEn el protocolo Binius, la manipulación y construcción de polinomios virtuales juegan un papel crucial para permitir la manipulación eficiente de polinomios. Se emplean dos técnicas principales para estas operaciones:
- Empaque: El método de empaque optimiza el manejo de elementos más pequeños agrupándolos en un dominio más grande. Específicamente, los elementos adyacentes en orden lexicográfico se empaquetan en bloques más grandes, típicamente de tamaño - 2𝜅- . Al aprovechar la Extensión Multilineal (MLE), los elementos empaquetados se transforman en un nuevo polinomio virtual, que luego se puede evaluar y procesar eficientemente. Este método mejora el rendimiento de las operaciones en el hipercubo booleano al reestructurar la función - 𝑡- en una forma computacionalmente eficiente.- Operador de cambio : El operador de cambio reorganiza elementos dentro de un bloque desplazándolos cíclicamente según un desplazamiento dado- 𝑜- . Este cambio se aplica a bloques de tamaño - 2𝑏- asegurando que todos los elementos en un bloque se desplacen de manera uniforme según el desplazamiento predefinido. Este operador es especialmente útil cuando se trata de polinomios virtuales en espacios de alta dimensión, ya que su complejidad aumenta linealmente con el tamaño del bloque, lo que lo convierte en una técnica ideal para conjuntos de datos grandes o cálculos complejos de hipercubos booleanos.### 2.4 PIOP: Un argumento de búsqueda de Lasso adaptado - Aplicable a campos binariosEl protocolo Lasso en Binius ofrece un método altamente eficiente para demostrar que los elementos en un vector
𝑎∈𝐹𝑚
se encuentran dentro de una tabla predefinida
𝑡∈𝐹𝑛
. Este argumento de búsqueda introduce el concepto de "Singularidad de Búsqueda" y es adecuado para esquemas de compromiso polinómico multilineales. La eficiencia de Lasso se destaca en dos aspectos principales:
-
Eficiencia de prueba: al llevar a cabo - 𝑚- búsquedas en una tabla de tamaño - 𝑛- , el probador solo necesita comprometerse a - 𝑚+𝑛- elementos de campo pequeños, con el tamaño de campo extraído del conjunto- 0,...,𝑚- . En los esquemas criptográficos que dependen de la exponenciación, el costo del probador es - 𝑂(𝑚+𝑛)- operaciones de grupo (por ejemplo, adiciones de puntos de curvas elípticas). Esta eficiencia se suma al costo de verificar si un polinomio multilineal evaluado en el hipercubo booleano coincide con un elemento de la tabla.- Sin compromiso con las mesas grandes: si la mesa...- 𝑡- está estructurado, Lasso no requiere un compromiso directo con la mesa, lo que hace posible manejar mesas muy grandes (por ejemplo, - 2128- o más). El tiempo de ejecución del probador depende únicamente de las entradas específicas a las que se accede en la tabla. Para cualquier parámetro entero - 𝑐>1- El costo principal involucra el tamaño de la prueba, que aumenta a medida que - 3⋅𝑐⋅𝑚+𝑐⋅𝑛1/𝑐- elementos de campo comprometidos. Estos elementos también son pequeños, extraídos del conjunto - 0,…,max𝑚,𝑛1/𝑐,𝑞−1- , donde - 𝑞- es el valor más grande en el vector- a- .El protocolo Lasso consta de tres componentes principales:
-
Abstracción polinomial virtual de tablas grandes: el protocolo Lasso combina polinomios virtuales para permitir búsquedas y operaciones eficientes en tablas grandes, asegurando escalabilidad sin degradación del rendimiento.- Búsqueda de tabla pequeña: En el corazón de Lasso se encuentra la búsqueda de tabla pequeña, que verifica si un polinomio virtual evaluado en un hipercubo booleano es un subconjunto de las evaluaciones de otro polinomio virtual. Este proceso es similar a la detección de memoria sin conexión y se reduce a una tarea de detección multiconjunto.- Verificación de multiconjunto: El protocolo también incorpora un mecanismo virtual para realizar verificaciones de multiconjuntos, asegurando que dos conjuntos de elementos coincidan o cumplan condiciones predefinidas.El protocolo Binius adapta Lasso para operaciones de campo binario, asumiendo que el campo actual es un campo primario de gran característica (mucho mayor que la longitud de la columna que se está buscando). Binius introduce una versión multiplicativa del protocolo Lasso, que requiere que el probador y el verificador incrementen la operación de "contador de memoria" del protocolo no simplemente agregando 1, sino incrementando el uso de un generador multiplicativo dentro del campo binario. Sin embargo, esta adaptación multiplicativa introduce una complejidad adicional: a diferencia de un incremento aditivo, el generador multiplicativo no se incrementa en todos los casos, sino que tiene una sola órbita en 0, lo que puede presentar un vector de ataque. Para mitigar este posible ataque, el probador debe comprometerse con un vector de contador de lectura distinto de cero en todas partes para garantizar la seguridad del protocolo.
2.5 PCS: Adaptado Brakedown PCS - Aplicable a Campos PequeñosLa idea central detrás de la construcción del Binius PCS (Esquema de Compromiso Polinomial) es el empaquetado. El documento de Binius presenta dos esquemas de PCS de Brakedown basados en campos binarios: uno instantiado usando códigos concatenados y otro usando codificación a nivel de bloque, que admite el uso independiente de códigos Reed-Solomon. El segundo esquema de PCS de Brakedown simplifica el proceso de prueba y verificación, aunque produce un tamaño de prueba ligeramente mayor que el primero; sin embargo, esta compensación vale la pena debido a las ventajas de simplificación e implementación que ofrece.
El compromiso polinomial de Binius utiliza principalmente el compromiso polinomial de campo pequeño con evaluaciones en un campo extendido, construcción universal de campo pequeño y codificación a nivel de bloque con técnicas de código Reed-Solomon.
Compromiso de polinomio de campo pequeño con evaluación de campo extendido En el protocolo Binius, se realizan compromisos de polinomios sobre un campo pequeño.
K
con evaluaciones que tienen lugar en un campo extendido
L/K
. Esta técnica asegura que un polinomio multilíneo
𝑡(𝑋0,…,𝑋ℓ−1)
pertenece al dominio
𝐾[𝑋0,…,𝑋ℓ−1]
, mientras que los puntos de evaluación están en el campo más grande
𝐿
. Esta estructura de compromiso permite consultas eficientes dentro del campo extendido, equilibrando la seguridad y la eficiencia computacional.
Construcción Universal de Pequeño Campo Esta construcción define parámetros clave como el campo
𝐾
, su dimensión
ℓ
, y el código de bloque lineal asociado
𝐶
, mientras se asegura de que el campo extendido
𝐿
es lo suficientemente grande para evaluaciones seguras. Al aprovechar las propiedades del campo extendido, Binius logra compromisos robustos a través de códigos de bloque lineales, manteniendo un equilibrio entre eficiencia computacional y seguridad.
Codificación a nivel de bloque con códigos de Reed-Solomon para polinomios definidos sobre campos pequeños como $\mathbb{F}2
,𝑡ℎ𝑒𝐵𝑖𝑛𝑖𝑢𝑠𝑝𝑟𝑜𝑡𝑜𝑐𝑜𝑙𝑒𝑚𝑝𝑙𝑜𝑦𝑠𝑏𝑙𝑜𝑐𝑘−𝑙𝑒𝑣𝑒𝑙𝑒𝑛𝑐𝑜𝑑𝑖𝑛𝑔𝑢𝑠𝑖𝑛𝑔𝑅𝑒𝑒𝑑−𝑆𝑜𝑙𝑜𝑚𝑜𝑛𝑐𝑜𝑑𝑒𝑠.𝑇ℎ𝑖𝑠𝑠𝑐ℎ𝑒𝑚𝑒𝑎𝑙𝑙𝑜𝑤𝑠𝑒𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑡𝑐𝑜𝑚𝑚𝑖𝑡𝑚𝑒𝑛𝑡𝑜𝑓𝑠𝑚𝑎𝑙𝑙−𝑓𝑖𝑒𝑙𝑑𝑝𝑜𝑙𝑦𝑛𝑜𝑚𝑖𝑎𝑙𝑠𝑏𝑦𝑒𝑛𝑐𝑜𝑑𝑖𝑛𝑔𝑡ℎ𝑒𝑚𝑟𝑜𝑤−𝑏𝑦−𝑟𝑜𝑤𝑖𝑛𝑡𝑜𝑙𝑎𝑟𝑔𝑒𝑟𝑓𝑖𝑒𝑙𝑑𝑠(𝑠𝑢𝑐ℎ𝑎𝑠
\mathbb{F}{2^{16}}$ ), utilizando la eficiencia y las propiedades de separación de máxima distancia de los códigos de Reed-Solomon. Después de la codificación, estas filas se comprometen utilizando un árbol de Merkle, lo que simplifica la complejidad operativa de los compromisos polinomiales de campos pequeños. Este enfoque permite el manejo eficiente de polinomios en campos pequeños sin la carga computacional normalmente asociada con campos más grandes.
3. Optimizaciones BiniusPara mejorar aún más el rendimiento, Binius incorpora cuatro grandes optimizaciones:
- Basado en GKR PIOP: El protocolo GKR (Goldreich-Kalai-Rothblum) se utiliza para reemplazar el algoritmo de búsqueda de Lasso en la multiplicación de campos binarios, lo que reduce significativamente los costos generales en el proceso de compromiso.- Optimización ZeroCheck PIOP: Esta optimización aborda el equilibrio entre los costos computacionales del Probador y el Verificador, haciendo que la operación ZeroCheck sea más eficiente al distribuir la carga de trabajo de manera más efectiva.- Optimización de PIOP de Sumcheck: Al optimizar el proceso de Sumcheck de campo pequeño, Binius reduce la carga computacional general al operar en campos pequeños.- Optimización PCS: Utilizando la optimización FRI-Binius (Pruebas de proximidad interactivas de oráculo de Reed-Solomon rápido), Binius reduce el tamaño de la prueba y mejora el rendimiento del protocolo, mejorando la eficiencia general tanto en la generación de pruebas como en la verificación.### 3.1 PIOP basado en GKR: multiplicación de campos binarios utilizando GKREn el protocolo original de Binius, la multiplicación de campos binarios se maneja a través de un esquema basado en búsqueda, que vincula la multiplicación con operaciones de suma lineales basadas en el número de segmentos en una palabra. Si bien este método optimiza la multiplicación binaria hasta cierto punto, aún introduce compromisos auxiliares linealmente relacionados con el número de segmentos. Al adoptar un enfoque basado en GKR, el protocolo de Binius puede reducir significativamente el número de compromisos requeridos, lo que conduce a una mayor eficiencia en las operaciones de multiplicación de campos binarios.
La idea principal del protocolo GKR (Goldwasser-Kalai-Rothblum) es lograr un acuerdo entre el Probador (P) y el Verificador (V) sobre un circuito aritmético en capas en un campo finito.
𝐹
. Cada nodo de este circuito tiene dos entradas para calcular la función requerida. Para reducir la complejidad computacional del verificador, el protocolo emplea el protocolo SumCheck, que reduce progresivamente las afirmaciones sobre los valores de la puerta de salida del circuito a valores de puerta de capa inferior, lo que finalmente simplifica las afirmaciones sobre las declaraciones sobre las entradas. De esta manera, el verificador solo necesita verificar la corrección de las entradas del circuito.
El Algoritmo de multiplicación de enteros basado en GKRen Binius transforma la comprobación de si dos enteros de 32 bits
Un
y
𝐵
satisfacer
𝐴⋅𝐵=?𝐶
en la verificación de si
(𝑔𝐴)𝐵=?𝑔𝐶
mantiene en
𝐹264∗
Esta transformación, combinada con el protocolo GKR, reduce significativamente los costos asociados con los compromisos polinomiales. En comparación con el esquema anterior basado en la búsqueda de Binius, el enfoque de multiplicación basado en GKR requiere solo un compromiso auxiliar y reduce el costo de SumChecks, lo que hace que el algoritmo sea más eficiente, especialmente en casos donde SumChecks son más económicos que compromisos adicionales. Este método se está convirtiendo en una solución prometedora para minimizar los costos de compromiso polinomial en campos binarios a medida que avanzan las optimizaciones de Binius.
3.2 Optimización PIOP de ZeroCheck: Equilibrio de los costes computacionales entre el probador y el verificadorEl papel Algunas mejoras para PIOP para ZeroCheckpropone estrategias para equilibrar los costos computacionales entre el Probador (P) y el Verificador (V), centrándose en reducir la transmisión de datos y la complejidad computacional. A continuación se presentan las técnicas clave de optimización:
- Reduciendo la transmisión de datos del probadorAl transferir parte de la carga computacional al Verificador, se puede minimizar la transmisión de datos del Probador. Por ejemplo, en la ronda
Yo
, el Prover envía
𝑣𝑖+1(𝑋)
para
X=0,...,d+1
, y el Verificador comprueba si
vi=vi+1(0)+vi+1(1)
mantiene.
Optimización: El Prover puede evitar enviar
𝑣𝑖+1(1)
, como el Verificador puede calcularlo como
𝑣𝑖+1(1)=𝑣𝑖−𝑣𝑖+1(0)
.
En la ronda inicial, el Prover envía
𝑣1(0)=𝑣1(1)=0
eliminando algunos cálculos de evaluación, lo que reduce tanto los costos computacionales como los de transmisión a
𝑑2𝑛−1𝐶𝐹+(𝑑+1)2𝑛−1𝐶𝐺
.
- Reduciendo el número de puntos de evaluación para el ProverDurante la ronda
𝑖
, el Prover debe enviar
𝑣𝑖+1(𝑋)
, calculado como
𝑣𝑖+1(𝑋)=∑𝑥∈𝐻𝑛−𝑖−1𝛿^𝑛(𝛼,(𝑟,𝑋,𝑥))𝐶(𝑟,𝑋,𝑥)
.
Optimización: En su lugar, el probador puede enviar
𝑣𝑖+1′(𝑋)=∑𝑥∈𝐻𝑛−𝑖−1𝛿^𝑛(𝛼𝑖+1,…,𝛼𝑛−1,𝑥)𝐶(𝑟,𝑋,𝑥),
donde $v_i(X) = v_i’(X) \cdot \hat{\delta}{i+1}((\alpha_0, \dots, \alpha_i), (r, X))
.𝐴𝑠𝑡ℎ𝑒𝑉𝑒𝑟𝑖𝑓𝑖𝑒𝑟ℎ𝑎𝑠𝑎𝑐𝑐𝑒𝑠𝑠𝑡𝑜
\Alfa
𝑎𝑛𝑑
r
,𝑡ℎ𝑒𝑑𝑒𝑔𝑟𝑒𝑒𝑜𝑓
v_i'(X)
𝑖𝑠𝑙𝑜𝑤𝑒𝑟𝑡ℎ𝑎𝑛𝑡ℎ𝑎𝑡𝑜𝑓
v_i(X)
, redactando la reseñadevaluación de puntos. Theinter-roundcheckcan thenbe simplifiedas
(1 - \alphai)v{i+1}’(0) + \alpha_i v{i+1}’(1) = v_i’(X),
𝑡ℎ𝑒𝑟𝑒𝑏𝑦𝑙𝑜𝑤𝑒𝑟𝑖𝑛𝑔𝑑𝑎𝑡𝑎𝑡𝑟𝑎𝑛𝑠𝑚𝑖𝑠𝑠𝑖𝑜𝑛𝑛𝑒𝑒𝑑𝑠𝑎𝑛𝑑𝑒𝑛ℎ𝑎𝑛𝑐𝑖𝑛𝑔𝑒𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑐𝑦.𝑊𝑖𝑡ℎ𝑡ℎ𝑒𝑠𝑒𝑖𝑚𝑝𝑟𝑜𝑣𝑒𝑚𝑒𝑛𝑡𝑠,𝑡ℎ𝑒𝑜𝑣𝑒𝑟𝑎𝑙𝑙𝑐𝑜𝑠𝑡𝑖𝑠𝑎𝑝𝑝𝑟𝑜𝑥𝑖𝑚𝑎𝑡𝑒𝑙𝑦
2^{n-1}(d - 1)C_F + 2^{n-1}dC_G.
Para
d = 3$ , estas optimizaciones dan como resultado una reducción de costos por un factor de 5/3.
- Optimización de Interpolación AlgebraicaPara un Probador honesto, el polinomio
𝐶(𝑥0,…,𝑥𝑛−1)
es cero en
Hn
y se puede expresar como
𝐶(𝑥0,…,𝑥𝑛−1)=∑𝑖=0𝑛−1𝑥𝑖(𝑥𝑖−1)𝑄𝑖(𝑥0,…,𝑥𝑛−1)
. Donde
𝑄𝑖
se calcula mediante una división polinómica ordenada, comenzando desde
𝑅𝑛=𝐶
. División secuencial por
𝑥𝑖(𝑥𝑖−1)
calcula
QI
y
𝑅𝑖
con
R0
representando la extensión multilineal de
𝐶
en
𝐻𝑛
, supuesto que es cero.
Analizando los grados de
𝑄𝑖
. Para
𝑗>𝑖
,
𝑄𝑗
conserva el mismo grado en
xi
como
𝐶
. Para
𝑗=𝑖
, el grado se reduce en 2, y para
J- Impacto de las rondas de cambio y factores de mejora. La optimización del protocolo de Sumcheck de campos pequeños depende de la selección de la ronda de cambio óptima.𝑡
, que marca cuando el protocolo se revierte de la versión optimizada al algoritmo ingenuo. Los experimentos indican que el factor de mejora alcanza su máximo en el punto de cambio óptimo y luego sigue una tendencia parabólica. Cuando se supera este punto, la eficiencia disminuye porque la relación entre las multiplicaciones de campo base y campo de extensión es mayor en campos más pequeños, lo que requiere una reversión oportuna al algoritmo ingenuo.
Para ciertas aplicaciones, como el Cubic Sumcheck (
𝑑=3
) el protocolo Sumcheck de campo pequeño ofrece una mejora de un orden de magnitud sobre el enfoque ingenuo. Por ejemplo, en el campo base
𝐺𝐹[2]2. Impact of Base Field Size on Performance Smaller base fields (e.g.,
, El algoritmo 4 supera al algoritmo ingenuo casi 30 veces.
𝐺𝐹[2]
) mejorar significativamente la eficiencia del algoritmo optimizado debido a la mayor disparidad entre los costos de las multiplicaciones en el campo de extensión y el campo base. Esto conduce a un factor de mejora más sustancial para el algoritmo optimizado.
- Beneficios de optimización del algoritmo Karatsuba El algoritmo Karatsuba juega un papel crucial en la mejora del rendimiento del protocolo de verificación de suma de campo pequeño. Para un campo base de 𝐺𝐹[2]
, El Algoritmo 4 alcanza factores de mejora máximos de 6 para el Algoritmo 3 y 30 para el Algoritmo 4, lo que indica que el Algoritmo 4 es cinco veces más eficiente que el Algoritmo 3. El algoritmo de Karatsuba mejora la eficiencia de tiempo de ejecución y optimiza el punto de cambio para ambos algoritmos, con puntos óptimos en,
𝑡=5
para el Algoritmo 3 y
t = 8
para el algoritmo 4.
- Mejoras en la eficiencia de la memoria El protocolo de verificación de suma de campo pequeño también mejora la eficiencia de la memoria. El algoritmo 4 requiere𝑂(𝑑⋅𝑡)
la memoria, mientras que el Algoritmo 3 necesita
𝑂(2𝑑⋅𝑡)
memoria. Para
𝑡=8
, El algoritmo 4 utiliza solo 0.26 MB de memoria, en comparación con los 67 MB requeridos por el algoritmo 3. Esto hace que el algoritmo 4 sea particularmente adecuado para entornos con restricciones de memoria, como la demostración del lado del cliente con recursos limitados.
3.4 PCS Optimization: FRI-Binius Reducing Binius Proof SizeUno de los principales desafíos del protocolo Binius es su tamaño de prueba relativamente grande, que escala con la raíz cuadrada del tamaño del testigo en
𝑂(𝑁)
Esta escala de raíz cuadrada limita su competitividad en comparación con los sistemas que ofrecen pruebas más sucintas. En contraste, los tamaños de prueba polilogarítmicos, como los logrados por sistemas avanzados como Plonky3 a través de técnicas como FRI, son esenciales para garantizar verificadores verdaderamente 'sucintos'. La optimización de FRI-Binius tiene como objetivo reducir el tamaño de prueba de Binius y mejorar su rendimiento general en comparación con sistemas más eficientes.
El papel Pruebas polilogarítmicas para multilíneas sobre torres binarias, conocido como FRI-Binius, introduce un mecanismo de plegado FRI (Prueba Interactiva de Oráculo de Proximidad de Reed-Solomon Rápida) basado en campos binarios novedoso con cuatro innovaciones clave:
- Polinomios aplanados: Transforma el polinomio multilinear inicial en una base polinómica de Low Code Height (LCH) para una computación optimizada.- Polinomios de Desaparición de Subespacio: Utiliza estos polinomios en conjunción con una NTT aditiva (Transformada Teórica de Números) para habilitar una descomposición similar a FFT, optimizando operaciones sobre el campo de coeficientes.- Empaquetado de base algebraica: facilita el empaquetado eficiente de datos, minimizando la sobrecarga del protocolo relacionada con la incrustación.- Ring-Switching SumCheck: Una nueva optimización de SumCheck utilizando técnicas de cambio de anillo para mejorar aún más el rendimiento.Proceso central del Esquema de Compromiso Polinomial Multilineal (PCS) de FRI-Binius
El protocolo FRI-Binius optimiza los esquemas de compromiso de polinomios multilineales (PCS) de campo binario al transformar el polinomio multilineal inicial, definido sobre el campo binario
𝐹2
, en un polinomio multilineal sobre un campo más grande
𝐾
.
- Fase de compromiso La fase de compromiso transforma un - ℓ- -polinomio multilineal variable (sobre $\mathbb{F}2- )𝑖𝑛𝑡𝑜𝑎𝑐𝑜𝑚𝑚𝑖𝑡𝑚𝑒𝑛𝑡𝑓𝑜𝑟𝑎𝑝𝑎𝑐𝑘𝑒𝑑- \ell’- −variablepolinomial multilineal (sobre- (\mathbb{F}{2^{128}}$ ). Este proceso reduce el número de coeficientes en un factor de 128, lo que permite una generación de pruebas más eficiente.- Fase de evaluación En esta fase, el probador y verificador ejecutan - ℓ′- rondas de un protocolo de SumCheck de conmutación de anillo cruzado combinado con pruebas oráculas interactivas de proximidad (IOPP) de FRI. Los detalles clave incluyen:Pruebas de apertura FRI: Estas constituyen la mayor parte del tamaño de la prueba y se manejan de manera similar a las pruebas FRI estándar sobre campos grandes.- Costo de verificación de suma del probador: Comparable al costo de ejecutar SumCheck en un campo grande.- Costo FRI del probador: coincide con los costos FRI estándar observados en implementaciones de campos grandes.- Operaciones del Verificador: El verificador recibe 128 elementos de - 𝐹2128- y realiza 128 multiplicaciones adicionales, lo que permite una verificación eficiente.Beneficios de FRI-Binius
Aplicando este método, Binius es capaz de reducir el tamaño de su prueba en un orden de magnitud, acercándose al rendimiento de los sistemas criptográficos más avanzados, al mismo tiempo que sigue siendo compatible con campos binarios. El método de plegado FRI, optimizado para campos binarios, combinado con empaquetamiento algebraico y optimizaciones SumCheck, ayuda a Binius a generar pruebas más pequeñas sin comprometer la eficiencia de verificación.
Esta transformación marca un paso significativo hacia la mejora del tamaño de la prueba en Binius, asegurando que sea más competitivo con otros sistemas de vanguardia, especialmente aquellos centrados en tamaños de prueba polilogarítmicos.
Tabla 2: Comparación del tamaño de la prueba Binius vs. FRI-Binius
Tabla 3: Comparación de Plonky3 FRI vs. FRI-Binius## 4. ConclusionToda la propuesta de valor de Binius radica en su capacidad para utilizar el tamaño de campo más pequeño posible para los testigos, seleccionando el tamaño del campo según sea necesario. Binius es un esquema de co-diseño para "protocolos de Sumcheck acelerados por hardware, software y FPGA", que permite pruebas rápidas con un uso de memoria muy bajo.
Los sistemas de prueba como Halo2 y Plonky3 involucran cuatro pasos clave intensivos en cómputo: generar datos de testigo, comprometerse con los datos de testigo, realizar un argumento de desaparición y generar la prueba de apertura.
Por ejemplo, con la función hash Keccak en Plonky3 y la función hash Grøstl en Binius, la distribución computacional para estos cuatro pasos clave se ilustra en la Figura 3.
Figura 3. Menor Costo de Compromiso
Esta comparación muestra que Binius ha eliminado esencialmente el cuello de botella del compromiso del probador. El nuevo cuello de botella es el protocolo Sumcheck, donde problemas como numerosas evaluaciones polinómicas y multiplicaciones de campos se pueden abordar de manera eficiente con hardware especializado.
El esquema FRI-Binius, una variante de FRI, ofrece una opción muy atractiva al eliminar la sobrecarga de incrustación de la capa de prueba de campo sin causar un aumento significativo de costos en la capa de prueba agregada.
Actualmente, el equipo de Irreducible está desarrollando su capa recursiva y tieneanunció una asociación con el equipo de Polygon para construir un zkVM basado en Binius; el Jolt zkVM está haciendo la transición de Lasso a Binius para mejorar su rendimiento recursivo; y el El equipo de Ingonyama está implementando una versión FPGA de Binius.
