3,593 lecturi

Cum reduce Binius complexitatea computațională cu turnuri de câmpuri binare

de Sin7Y3m2024/09/13

Prea lung; A citi

Echipa Ulvetanna (IRREDUCIBILĂ) a abordat această întrebare în lucrarea lor de cercetare intitulată Argumente succinte asupra turnurilor câmpurilor binare. L-au implementat în Rust cu proiectul lor, Binius: un SNARK optimizat pentru hardware. În Binius, Câmpurile Binare sunt construite folosind turnuri de extensii de câmp.

featured image - Cum reduce Binius complexitatea computațională cu turnuri de câmpuri binare

Reducerea complexității de calcul a fost întotdeauna unul dintre obiectivele principale ale tehnologiei blockchain. O abordare eficientă pentru a realiza acest lucru este prin reducerea lățimii de biți a câmpului de calcul. De exemplu, SNARK-urile bazate pe curbe eliptice efectuează operații aritmetice în câmpuri cu lățimi de biți de 256 sau mai mari, în timp ce STARK-urile au evoluat de la utilizarea câmpului Goldilocks pe 64 de biți la câmpurile Mersenne31 și BabyBear pe 31 de biți. Dincolo de eficiența numerelor prime în timpul operațiilor modulare, reducerea semnificativă a lățimii de biți a făcut ca Plonky2 să fie de sute de ori mai rapid decât predecesorul său, Plonky. Urmând această traiectorie, cineva s-ar putea întreba: este posibil să setați lățimea câmpului la 1, în special ${\mathbb{F}}_{2}$? Echipa Ulvetanna (IRREDUCIBILĂ) a abordat această întrebare în lucrarea lor de cercetare intitulată Argumente succinte asupra turnurilor câmpurilor binare [1] și l-au implementat în Rust cu proiectul lor, Binius: un SNARK optimizat pentru hardware [2] [3] .

De la lansare, Binius a atras o atenție semnificativă în comunitatea ZK (Zero-Knowledge). Echipa LambdaClass a oferit mai multe analize tehnice [4][5][6], iar Vitalik Buterin a oferit o explicație mai accesibilă [7] . În acest articol, vom explora bazele lui Binius, concentrându-ne pe Turnurile Câmpurilor Binare, atât din punct de vedere tehnic, cât și din perspectiva implementării.

Câmpuri Binare

Implementarea lui Binius se bazează pe Câmpuri Binare. În Binius, Câmpurile Binare sunt construite folosind turnuri de extensii de câmp.

Cel mai simplu Câmp Binar este ${{\mathbb{F}}{2}}$ , care conține doar două elemente ${0,1}$ , cu operații efectuate modulo 2: adunarea corespunde XOR pe biți, iar înmulțirea corespunde cu biți. ŞI. Alegând un polinom ireductibil $m(x) = x^{2} + x + 1$ over ${{\mathbb{F}}{2}}$ , putem forma câmpul ${{\mathbb{F}}_{{2^{2}}}}$ , unde elementele sunt resturi de polinoame de gradul cel mult 1, $r(x) = ax + b$ (with $a, b \in {0, 1}$ ).

În timp ce o metodă de extindere a câmpurilor implică preluarea resturilor folosind polinoame ireductibile, Binius folosește o abordare mai eficientă: utilizarea polinoamelor Lagrange multiliniare ca bază pentru extensiile turnului. Această metodă permite extensii de câmp recursive, în care fiecare câmp de extensie este imbricat în cel anterior.

Implementarea specifică a extensiilor de turn este următoarea: în primul rând, ${{\tau }{0}} = {{\mathbb{F}}{2}}$ ; Apoi, ${{\tau }{1}} = \frac{{{\mathbb{F}}{2}}[{{x}{0}}]}{(x{0}^{2} + {{x}_{0}} + 1)}$ ; Apoi, ${{\tau }{k}} = \frac{{{\mathbb{F}}{2}}[{{x}{k-1}}]}{(x{k-1}^{2} + {{x}{k-1}}{{x}{k-2}} + 1)}$.

Din procesul de construcție al extensiilor de câmp, este clar că extensiile satisfac următoarea relație: ${{\tau }{0}} \subset {{\tau }{1}} \subset {{\tau }{2}} \subset \cdots \subset {{\tau }{m}}$ . Pentru $k \ge 0$ , extensia câmpului poate fi exprimată și sub forma directă a unui inel ca: ${{\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)}$.

Pe baza acestei implementări, pot fi obținute diferite extensii, după cum urmează:

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

Din elementele conținute în câmpul extins Este evident că pentru un element ${{b}{0}}{{b}{1}}{{b}{2}}\ldots {{b}{{{2}^{k}}-1}}$ derivat din ${{\tau }{k}}$ , poate fi descompus în suma a două părți: ${{b}{lo}} + {{x}{k-1}}{{b}{hi}}$ (where ${{b}{lo}}, {{b}{hi}} \in {{\tau }{k-1}}$) . De exemplu, $1100101010001111 = 11001010 + 1000111 \times {{x}{3}}$, where $11001010, 10001111 \in {{\tau }{2}}$ .

Prin descompunerea iterativă, putem exprima în sfârșit: $$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}}$$

În plus, pentru $k > 0$ , deoarece $x_{k}^{2} = {{x}{k}}{{x}{k-1}} + 1$ , adunarea și înmulțirea pot fi implementate eficient în câmpul binar extins.

Implementarea Câmpurilor Binare

Irreductible oferă implementarea Rust open-source a lui Binius [3]. Codul sursă include implementări și operațiuni complete pentru Turnul Câmpurilor Binare [8,9,10].

În [8], așa cum se arată în Figura 1, implementarea include definirea completă a operațiunilor pentru câmpurile binare și construcția Turnului Câmpurilor Binare. Turnul Câmpurilor Binare, care acceptă un câmp binar de până la 128 de biți, este definit după cum urmează: