3,656 lecturas

Cómo Binius reduce la complejidad computacional con torres de campos binarios

por Sin7Y3m2024/09/13

Demasiado Largo; Para Leer

El equipo de Ulvetanna (IRREDUCIBLE) abordó esta cuestión en su artículo de investigación titulado Argumentos sucintos sobre torres de campos binarios. Lo implementaron en Rust con su proyecto, Binius: un SNARK optimizado para hardware. En Binius, los campos binarios se construyen utilizando torres de extensiones de campo.

featured image - Cómo Binius reduce la complejidad computacional con torres de campos binarios

Reducir la complejidad computacional siempre ha sido uno de los objetivos principales de la tecnología blockchain. Un enfoque eficaz para lograrlo es reducir el ancho de bits del campo computacional. Por ejemplo, los SNARK basados en curvas elípticas realizan operaciones aritméticas en campos con anchos de bits de 256 o más, mientras que los STARK han evolucionado desde el uso del campo Goldilocks de 64 bits hasta los campos Mersenne31 y BabyBear de 31 bits. Más allá de la eficiencia de los números primos durante las operaciones modulares, la reducción significativa del ancho de bits ha llevado a que Plonky2 sea cientos de veces más rápido que su predecesor, Plonky. Siguiendo esta trayectoria, uno podría preguntarse: ¿es posible establecer el ancho del campo en 1, específicamente ${\mathbb{F}}_{2}$? El equipo de Ulvetanna (IRREDUCIBLE) abordó esta cuestión en su artículo de investigación titulado Succinct Arguments over Towers of Binary Fields (Argumentos sucintos sobre torres de campos binarios). [1] , y lo implementaron en Rust con su proyecto, Binius: un SNARK optimizado para hardware [2] [3] .

Desde su lanzamiento, Binius ha obtenido una atención significativa en la comunidad ZK (Zero-Knowledge). El equipo de LambdaClass ha proporcionado varios análisis técnicos [4][5][6], y Vitalik Buterin ofreció una explicación más accesible. [7] En este artículo, exploraremos los fundamentos de Binius, centrándonos en las Torres de Campos Binarios, tanto desde una perspectiva técnica como de implementación.

Campos binarios

La implementación de Binius se basa en campos binarios. En Binius, los campos binarios se construyen utilizando torres de extensiones de campo.

El campo binario más simple es ${{\mathbb{F}}{2}}$ , que contiene solo dos elementos ${0,1}$ , con operaciones realizadas módulo 2: la suma corresponde a XOR bit a bit, y la multiplicación corresponde a AND bit a bit. Al elegir un polinomio irreducible $m(x) = x^{2} + x + 1$ over ${{\mathbb{F}}{2}}$ , podemos formar el campo ${{\mathbb{F}}_{{2^{2}}}}$ , donde los elementos son restos de polinomios de grado como máximo 1, $r(x) = ax + b$ (with $a, b \in {0, 1}$ ).

Si bien un método para extender campos implica tomar residuos utilizando polinomios irreducibles, Binius emplea un enfoque más eficiente: el uso de polinomios de Lagrange multilineales como base para extensiones de torres. Este método permite extensiones de campo recursivas, donde cada campo de extensión está anidado dentro del anterior.

La implementación específica de las extensiones de torre es la siguiente: primero, ${{\tau }{0}} = {{\mathbb{F}}{2}}$ ; luego, ${{\tau }{1}} = \frac{{{\mathbb{F}}{2}}[{{x}{0}}]}{(x{0}^{2} + {{x}_{0}} + 1)}$ ; a continuación, ${{\tau }{k}} = \frac{{{\mathbb{F}}{2}}[{{x}{k-1}}]}{(x{k-1}^{2} + {{x}{k-1}}{{x}{k-2}} + 1)}$.

Del proceso de construcción de las extensiones de campo, es claro que las extensiones satisfacen la siguiente relación: ${{\tau }{0}} \subset {{\tau }{1}} \subset {{\tau }{2}} \subset \cdots \subset {{\tau }{m}}$ . Para $k \ge 0$ , la extensión de campo también se puede expresar en la forma directa de un anillo como: ${{\tau }{k}}={{{\mathbb{F}}{2}}[{{x}{0,}}\ldots ,{{x}{k-1}}]}/{\left( x_{0}^{2}+{{x}{0}}+1,\ldots ,x{k-1}^{2}+{{x}{k-2}}{{x}{k-1}}+1 \right)}$.

En base a esta implementación se pueden obtener diferentes extensiones como las siguientes:

${{\tau }_{0}}=\left{ 0,1 \right}$
${{\tau }{1}}=\left{ 0+0{{x}{0}},1+0{{x}{0}},0+1{{x}{0}},1+1{{x}{0}} \right}$, or ${{\tau }{1}}=\left{ {{\tau }{0}},0+1{{x}{0}},1+1{{x}_{0}} \right}$
$${{\tau }{2}}=\left{ \begin{align} & 0+0{{x}{0}}+0{{x}{1}}+0{{x}{0}}{{x}{1}},1+0{{x}{0}}+0{{x}{1}}+0{{x}{0}}{{x}{1}},0+1{{x}{0}}+0{{x}{1}}+0{{x}{0}}{{x}{1}}, \ & 1+1{{x}{0}}+0{{x}{1}}+0{{x}{0}}{{x}{1}},\ldots ,1+1{{x}{0}}+1{{x}{1}}+1{{x}{0}}x \ \end{align} \right}$$, Or ${{\tau }{2}}=\left{ {{\tau }{1}},0+0{{x}{0}}+1{{x}{1}}+0{{x}{0}}{{x}{1}},\ldots ,1+1{{x}{0}}+1{{x}{1}}+1{{x}{0}}{{x}{1}} \right}$

De los elementos contenidos en el cuerpo extendido Es evidente que para un elemento ${{b}{0}}{{b}{1}}{{b}{2}}\ldots {{b}{{{2}^{k}}-1}}$ derivado de ${{\tau }{k}}$ , se puede descomponer en la suma de dos partes: ${{b}{lo}} + {{x}{k-1}}{{b}{hi}}$ (where ${{b}{lo}}, {{b}{hi}} \in {{\tau }{k-1}}$) . Por ejemplo, $1100101010001111 = 11001010 + 1000111 \times {{x}{3}}$, where $11001010, 10001111 \in {{\tau }{2}}$ .

Al descomponer iterativamente, finalmente podemos expresar: $$1100101010001111=1+{{x}{0}}+{{x}{2}}+{{x}{2}}{{x}{1}}+{{x}{3}}+{{x}{2}}{{x}{3}}+{{x}{0}}{{x}{2}}{{x}{3}}+{{x}{1}}{{x}{2}}{{x}{3}}+{{x}{0}}{{x}{1}}{{x}{2}}{{x}{3}}$$

Además, para $k > 0$ , dado que $x_{k}^{2} = {{x}{k}}{{x}{k-1}} + 1$ , la suma y la multiplicación se pueden implementar de manera eficiente en el campo binario extendido.

Implementación de campos binarios

Irreducible proporciona la implementación de código abierto de Binius en Rust [3]. El código fuente incluye implementaciones y operaciones completas para la Torre de campos binarios [8,9,10].

En [8], como se muestra en la Figura 1, la implementación incluye la definición completa de operaciones para campos binarios y la construcción de la Torre de Campos Binarios. La Torre de Campos Binarios, que admite un campo binario de hasta 128 bits, se define de la siguiente manera: