3,663 letture

Come Binius riduce la complessità computazionale con torri di campi binari

di Sin7Y3m2024/09/13

Troppo lungo; Leggere

Il team Ulvetanna (IRREDUCIBLE) ha affrontato questa questione nel suo documento di ricerca intitolato Succinct Arguments over Towers of Binary Fields. L'hanno implementato in Rust con il loro progetto, Binius: a Hardware-Optimized SNARK. In Binius, i Binary Fields sono costruiti utilizzando torri di estensioni di campo.

featured image - Come Binius riduce la complessità computazionale con torri di campi binari

La riduzione della complessità computazionale è sempre stato uno degli obiettivi principali della tecnologia blockchain. Un approccio efficace per raggiungere questo obiettivo è ridurre la larghezza di bit del campo di calcolo. Ad esempio, gli SNARK basati su curve ellittiche eseguono operazioni aritmetiche in campi con larghezze di bit pari o superiori a 256, mentre gli STARK si sono evoluti dall'utilizzo del campo Goldilocks a 64 bit ai campi Mersenne31 e BabyBear a 31 bit. Oltre all'efficienza dei numeri primi durante le operazioni modulari, la significativa riduzione della larghezza di bit ha portato Plonky2 a essere centinaia di volte più veloce del suo predecessore, Plonky. Seguendo questa traiettoria, ci si potrebbe chiedere: è possibile impostare la larghezza di campo su 1, in particolare ${\mathbb{F}}_{2}$? Il team Ulvetanna (IRREDUCIBLE) ha affrontato questa domanda nel suo documento di ricerca intitolato Succinct Arguments over Towers of Binary Fields [1] e lo ha implementato in Rust con il loro progetto, Binius: uno SNARK ottimizzato per l'hardware [2] [3] .

Sin dalla sua uscita, Binius ha attirato una notevole attenzione nella comunità ZK (Zero-Knowledge). Il team LambdaClass ha fornito diverse analisi tecniche [4][5][6] e Vitalik Buterin ha offerto una spiegazione più accessibile [7] In questo articolo esploreremo le basi di Binius, concentrandoci sulle Torri dei Campi Binari, sia da una prospettiva tecnica che di implementazione.

Campi binari

L'implementazione di Binius si basa su Binary Fields. In Binius, i Binary Fields sono costruiti utilizzando torri di estensioni di campo.

Il campo binario più semplice è ${{\mathbb{F}}{2}}$ , che contiene solo due elementi ${0,1}$ , con operazioni eseguite modulo 2: l'addizione corrisponde a XOR bit a bit e la moltiplicazione corrisponde a AND bit a bit. Scegliendo un polinomio irriducibile $m(x) = x^{2} + x + 1$ over ${{\mathbb{F}}{2}}$ , possiamo formare il campo ${{\mathbb{F}}_{{2^{2}}}}$ , dove gli elementi sono resti di polinomi di grado al massimo 1, $r(x) = ax + b$ (with $a, b \in {0, 1}$ ).

Mentre un metodo per estendere i campi comporta l'assunzione di resti usando polinomi irriducibili, Binius impiega un approccio più efficiente: l'uso di polinomi di Lagrange multilineare come base per le estensioni di torre. Questo metodo consente estensioni di campo ricorsive, in cui ogni campo di estensione è annidato all'interno del precedente.

L'implementazione specifica delle estensioni della torre è la seguente: innanzitutto, ${{\tau }{0}} = {{\mathbb{F}}{2}}$ ; quindi, ${{\tau }{1}} = \frac{{{\mathbb{F}}{2}}[{{x}{0}}]}{(x{0}^{2} + {{x}_{0}} + 1)}$ ; quindi, ${{\tau }{k}} = \frac{{{\mathbb{F}}{2}}[{{x}{k-1}}]}{(x{k-1}^{2} + {{x}{k-1}}{{x}{k-2}} + 1)}$.

Dal processo di costruzione delle estensioni di campo, è chiaro che le estensioni soddisfano la seguente relazione: ${{\tau }{0}} \subset {{\tau }{1}} \subset {{\tau }{2}} \subset \cdots \subset {{\tau }{m}}$ . Per $k \ge 0$ , l'estensione del campo può anche essere espressa nella forma diretta di un anello come: ${{\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)}$.

Sulla base di questa implementazione, è possibile ottenere diverse estensioni come segue:

${{\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}$

Dagli elementi contenuti nel campo esteso È evidente che per un elemento ${{b}{0}}{{b}{1}}{{b}{2}}\ldots {{b}{{{2}^{k}}-1}}$ derivato da ${{\tau }{k}}$ , può essere scomposto nella somma di due parti: ${{b}{lo}} + {{x}{k-1}}{{b}{hi}}$ (where ${{b}{lo}}, {{b}{hi}} \in {{\tau }{k-1}}$) . Ad esempio, $1100101010001111 = 11001010 + 1000111 \times {{x}{3}}$, where $11001010, 10001111 \in {{\tau }{2}}$ .

Decomponendo iterativamente, possiamo infine esprimere: $$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}}$$

Inoltre, per $k > 0$ , poiché $x_{k}^{2} = {{x}{k}}{{x}{k-1}} + 1$ , l'addizione e la moltiplicazione possono essere implementate in modo efficiente nel campo binario esteso.

Implementazione dei campi binari

Irreducible fornisce l'implementazione Rust open source di Binius [3]. Il codice sorgente include implementazioni e operazioni complete per la Torre dei campi binari [8,9,10].

In [8], come mostrato nella Figura 1, l'implementazione include la definizione completa delle operazioni per i campi binari e la costruzione della Torre dei campi binari. La Torre dei campi binari, che supporta fino a un campo binario di 128 bit, è definita come segue: