A 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 STARKs
En 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:
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.
La construcción de la mayoría de los sistemas SNARK modernos generalmente consta de los siguientes dos componentes:
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:
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:
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.
Las 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).
El 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:
Si bien Binius y HyperPlonk comparten varias similitudes en sus diseños de protocolo, Binius introduce las siguientes mejoras clave:
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.
En 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:
El 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:
El protocolo Lasso consta de tres componentes principales:
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.
La 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.
Para mejorar aún más el rendimiento, Binius incorpora cuatro grandes optimizaciones:
En 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.
El 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:
Al 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𝐶𝐺
.
Durante 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.
Para 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
, el grado es como máximo 1. Dado un vector
𝑟=(𝑟0,…,𝑟𝑖)
,
𝑄𝑗(𝑟,𝑋)
es multilínea para todos
𝑗≤𝑖
. Además,
𝑄𝑖(𝑟,𝑋)=∑𝑗=0𝑖𝑟𝑗(𝑟𝑗−1)𝑄𝑗(𝑟,𝑋)
es el único polinomio multilineal que coincide con
𝐶(𝑟,𝑋)
en
𝐻𝑛−𝑖
. Para cualquier
𝑋
y
x∈Hn−i−1
se puede representar como
𝐶(𝑟,𝑋,𝑥)−𝑄𝑖(𝑟,𝑋,𝑥)=𝑋(𝑋−1)𝑄𝑖+1(𝑟,𝑋,𝑥).
Así, durante cada ronda del protocolo, un nuevo
𝑄
se introduce, y su evaluación puede derivarse de
𝐶
y el anterior
𝑄
, permitiendo la optimización de interpolación.
En el protocolo STARKs implementado por Binius, el principal cuello de botella para el probador suele ser el protocolo de verificación de sumas en lugar del Esquema de Compromiso Polinómico (PCS), debido al bajo costo de compromiso.
Figura 2. Relación entre la ronda de cambio y la mejora del factor
En 2024, Ingonyama propusomejoras para protocolos de Sumcheck basados en campos pequeños, centrándose en los Algoritmos 3 y 4. Estas mejoras se implementaron y se pusieron a disposición del público.aquíEl Algoritmo 4 incorpora el algoritmo de Karatsuba en el Algoritmo 3, reduciendo el número de multiplicaciones de campo de extensión a cambio de más multiplicaciones de campo base. Este enfoque es más eficiente cuando las multiplicaciones de campo de extensión son más caras que las de campo base.
𝑡
, 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.
𝐺𝐹[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.
𝑂(𝑑⋅𝑡)
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.
Uno 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:
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
𝐾
.
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
Toda 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.
A 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 STARKs
En 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:
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.
La construcción de la mayoría de los sistemas SNARK modernos generalmente consta de los siguientes dos componentes:
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:
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:
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.
Las 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).
El 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:
Si bien Binius y HyperPlonk comparten varias similitudes en sus diseños de protocolo, Binius introduce las siguientes mejoras clave:
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.
En 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:
El 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:
El protocolo Lasso consta de tres componentes principales:
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.
La 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.
Para mejorar aún más el rendimiento, Binius incorpora cuatro grandes optimizaciones:
En 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.
El 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:
Al 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𝐶𝐺
.
Durante 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.
Para 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
, el grado es como máximo 1. Dado un vector
𝑟=(𝑟0,…,𝑟𝑖)
,
𝑄𝑗(𝑟,𝑋)
es multilínea para todos
𝑗≤𝑖
. Además,
𝑄𝑖(𝑟,𝑋)=∑𝑗=0𝑖𝑟𝑗(𝑟𝑗−1)𝑄𝑗(𝑟,𝑋)
es el único polinomio multilineal que coincide con
𝐶(𝑟,𝑋)
en
𝐻𝑛−𝑖
. Para cualquier
𝑋
y
x∈Hn−i−1
se puede representar como
𝐶(𝑟,𝑋,𝑥)−𝑄𝑖(𝑟,𝑋,𝑥)=𝑋(𝑋−1)𝑄𝑖+1(𝑟,𝑋,𝑥).
Así, durante cada ronda del protocolo, un nuevo
𝑄
se introduce, y su evaluación puede derivarse de
𝐶
y el anterior
𝑄
, permitiendo la optimización de interpolación.
En el protocolo STARKs implementado por Binius, el principal cuello de botella para el probador suele ser el protocolo de verificación de sumas en lugar del Esquema de Compromiso Polinómico (PCS), debido al bajo costo de compromiso.
Figura 2. Relación entre la ronda de cambio y la mejora del factor
En 2024, Ingonyama propusomejoras para protocolos de Sumcheck basados en campos pequeños, centrándose en los Algoritmos 3 y 4. Estas mejoras se implementaron y se pusieron a disposición del público.aquíEl Algoritmo 4 incorpora el algoritmo de Karatsuba en el Algoritmo 3, reduciendo el número de multiplicaciones de campo de extensión a cambio de más multiplicaciones de campo base. Este enfoque es más eficiente cuando las multiplicaciones de campo de extensión son más caras que las de campo base.
𝑡
, 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.
𝐺𝐹[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.
𝑂(𝑑⋅𝑡)
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.
Uno 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:
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
𝐾
.
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
Toda 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.