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  și l-au implementat în Rust cu proiectul lor, Binius: un SNARK optimizat pentru hardware  .   [1]     [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ă  . Î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.   [7]   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   , care conține doar două elemente   , 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   , putem forma câmpul   , unde elementele sunt resturi de polinoame de gradul cel mult 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}$  Î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,   ; Apoi,   ; Apoi,  ${{\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)}$.  Din procesul de construcție al extensiilor de câmp, este clar că extensiile satisfac următoarea relație:   . Pentru   , extensia câmpului poate fi exprimată și sub forma directă a unui inel ca:  ${{\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)}$.   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   derivat din   , poate fi descompus în suma a două părți:   . De exemplu,    ${{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}}$ .  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   , deoarece   , adunarea și înmulțirea pot fi implementate eficient în câmpul binar extins. $k > 0$ $x_{k}^{2} = {{x}{k}}{{x}{k-1}} + 1$   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ă:   În plus, [8] oferă cod de testare și verificare pentru Turnul Câmpurilor Binare și operațiunile conexe.   Referințe  [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-uri pe câmpuri binare: Binius - Partea 1 (lambdaclass.com)  [5] SNARK-uri pe câmpuri binare: Binius - Partea 2 (lambdaclass.com)  [6] Cum ajută Binius să avanseze industria ZK (lambdaclass.com)  [7]   https://vitalik.eth.limo/general/2024/04/29/binius.html  [8] binius/crates/field/src/binary_field.rs la principal · IrreductibleOSS/binius · GitHub  [9] binius/crates/field/src/binary_field_arithmetic.rs la principal · IrreductibleOSS/binius · GitHub  [10] binius/crates/field/src/extension.rs la principal · IrreductibleOSS/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

Acest audio este produs în limba originală a poveștii!

Prea lung; A citi

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

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

About Author

COMENTARII

Etichete suspendate

ACEST ARTICOL A FOST PREZENTAT IN

Related Stories

The Robots Are Taking Over

The TechBeat: Digital Transformation Success Stories in Mezzanine Lending (2/28/2024)

Elon Just Made Gambling Define the News - And It's More Honest Than Journalism Ever Was

The #bitcoin Writing Contest by Rootstock and HackerNoon: Round 2 Results 🎉

The Robots Are Taking Over

The TechBeat: Digital Transformation Success Stories in Mezzanine Lending (2/28/2024)

Elon Just Made Gambling Define the News - And It's More Honest Than Journalism Ever Was

The #bitcoin Writing Contest by Rootstock and HackerNoon: Round 2 Results 🎉

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps