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  e lo ha implementato in Rust con il loro progetto, Binius: uno SNARK ottimizzato per l'hardware  .   [1]     [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  In questo articolo esploreremo le basi di Binius, concentrandoci sulle Torri dei Campi Binari, sia da una prospettiva tecnica che di implementazione.   [7]   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 è   , che contiene solo due elementi   , 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   , possiamo formare il campo   , dove gli elementi sono resti di polinomi di grado al massimo 1,   ). ${{\mathbb{F}}{2}}$ ${0,1}$ $m(x) = x^{2} + x + 1$ over ${{\mathbb{F}}{2}}$ ${{\mathbb{F}}_{{2^{2}}}}$ $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,   ; quindi,   ; quindi,  ${{\tau }{0}} = {{\mathbb{F}}{2}}$ ${{\tau }{1}} = \frac{{{\mathbb{F}}{2}}[{{x}{0}}]}{(x{0}^{2} + {{x}_{0}} + 1)}$ ${{\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:   . Per   , l'estensione del campo può anche essere espressa nella forma diretta di un anello come:  ${{\tau }{0}} \subset {{\tau }{1}} \subset {{\tau }{2}} \subset \cdots \subset {{\tau }{m}}$ $k \ge 0$ ${{\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   derivato da   , può essere scomposto nella somma di due parti:   . Ad esempio,    ${{b}{0}}{{b}{1}}{{b}{2}}\ldots {{b}{{{2}^{k}}-1}}$ ${{\tau }{k}}$ ${{b}{lo}} + {{x}{k-1}}{{b}{hi}}$ (where ${{b}{lo}}, {{b}{hi}} \in {{\tau }{k-1}}$) $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   , poiché   , l'addizione e la moltiplicazione possono essere implementate in modo efficiente nel campo binario esteso. $k > 0$ $x_{k}^{2} = {{x}{k}}{{x}{k-1}} + 1$   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:   Inoltre, [8] fornisce codice di test e verifica per la Torre dei Campi Binari e le operazioni correlate.   Riferimenti  [1]   https://eprint.iacr.org/2023/1784  [2]   https://www.irreducible.com/posts/binius-hardware-optimized-snark  [3]   https://gitlab.com/IrreducibleOSS/binius  [4] SNARK sui campi binari: Binius - Parte 1 (lambdaclass.com)  [5] SNARK sui campi binari: Binius - Parte 2 (lambdaclass.com)  [6] Come Binius sta aiutando a far progredire l'industria ZK (lambdaclass.com)  [7]   https://vitalik.eth.limo/general/2024/04/29/binius.html  [8] binius/crates/field/src/binary_field.rs nella directory principale · IrreducibleOSS/binius · GitHub  [9] binius/crates/field/src/binary_field_arithmetic.rs nella directory principale · IrreducibleOSS/binius · GitHub  [10] binius/crates/field/src/extension.rs nella directory principale · IrreducibleOSS/binius · GitHub

This story will praise and/or roast a product, company, service, game, or anything else people like to review on the Internet.

2022 - HackerNoon Contributor of the Year - Algorithms

2022 - HackerNoon Contributor of the Year - Architecture

2022 - HackerNoon Contributor of the Year - Blockchain

2022 - HackerNoon Contributor of the Year - Optimization

2022 - HackerNoon Contributor of the Year - Privacy

Nominated for 2022 - HackerNoon Contributor of the Year - Optimization

Nominated for 2022 - HackerNoon Contributor of the Year - Algorithms

Nominated for 2022 - HackerNoon Contributor of the Year - Privacy

Nominated for 2022 - HackerNoon Contributor of the Year - Architecture

Nominated for 2022 - HackerNoon Contributor of the Year - Blockchain

Questo audio è prodotto nella lingua originale della storia!

Troppo lungo; Leggere

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

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

About Author

COMMENTI

CARTELLINI

QUESTO ARTICOLO È STATO PRESENTATO IN

Related Stories

Streamlining Network Policy Management - Interview with Startups of the Year Nominee, Otterize

Meet Dealscard, Winner of Startups of The Year 2024 in Ghaziabad/Deal Aggregator

The Ultimate FAQ Guide to HackerNoon's Business Blogging

Coding with Latenode's AI + JavaScript Assistant: A Low-Code Platform for Simplified Development

Streamlining Network Policy Management - Interview with Startups of the Year Nominee, Otterize

Meet Dealscard, Winner of Startups of The Year 2024 in Ghaziabad/Deal Aggregator

The Ultimate FAQ Guide to HackerNoon's Business Blogging

Coding with Latenode's AI + JavaScript Assistant: A Low-Code Platform for Simplified Development

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps