3,593 mga pagbabasa

Paano Binabawasan ng Binius ang Computational Complexity gamit ang Towers of Binary Fields

sa pamamagitan ng Sin7Y3m2024/09/13

Masyadong mahaba; Upang basahin

Tinugunan ng pangkat ng Ulvetanna (IRREDUCIBLE) ang tanong na ito sa kanilang research paper na pinamagatang Succinct Arguments over Towers of Binary Fields. Ipinatupad nila ito sa Rust kasama ang kanilang proyekto, Binius: isang Hardware-Optimized SNARK. Sa Binius, ang mga Binary Field ay itinayo gamit ang mga tore ng mga extension ng field.

featured image - Paano Binabawasan ng Binius ang Computational Complexity gamit ang Towers of Binary Fields

Ang pagbabawas ng computational complexity ay palaging isa sa mga pangunahing layunin ng blockchain technology. Ang isang epektibong diskarte sa pagkamit nito ay sa pamamagitan ng pagbawas ng bit width ng field ng pagtutuos. Halimbawa, ang mga SNARK na nakabatay sa mga elliptic curve ay nagsasagawa ng mga pagpapatakbo ng arithmetic sa mga field na may bit width na 256 o mas mataas, habang ang mga STARK ay nag-evolve mula sa paggamit ng 64-bit na Goldilocks na field patungo sa 31-bit na Mersenne31 at BabyBear na mga field. Higit pa sa kahusayan ng mga pangunahing numero sa panahon ng mga modular na operasyon, ang makabuluhang pagbawas sa bit width ay humantong sa Plonky2 na daan-daang beses na mas mabilis kaysa sa hinalinhan nito, si Plonky. Kasunod ng trajectory na ito, maaaring magtaka ang isa: posible bang itakda ang lapad ng field sa 1, partikular na ${\mathbb{F}}_{2}$? Tinugunan ng pangkat ng Ulvetanna (IRREDUCIBLE) ang tanong na ito sa kanilang research paper na pinamagatang Succinct Arguments over Towers of Binary Fields [1] , at ipinatupad ito sa Rust kasama ang kanilang proyekto, Binius: isang Hardware-Optimized SNARK [2] [3] .

Mula nang ilabas ito, nakakuha ng makabuluhang atensyon si Binius sa komunidad ng ZK (Zero-Knowledge). Nagbigay ang LambdaClass team ng ilang teknikal na pagsusuri [4][5][6], at nag-alok si Vitalik Buterin ng mas madaling paliwanag [7] . Sa artikulong ito, tutuklasin natin ang mga pundasyon ng Binius, na tumutuon sa Towers of Binary Fields, mula sa parehong teknikal at pagpapatupad na pananaw.

Binary Fields

Ang pagpapatupad ng Binius ay batay sa Binary Fields. Sa Binius, ang mga Binary Field ay itinayo gamit ang mga tore ng mga extension ng field.

Ang pinakasimpleng Binary Field ay ${{\mathbb{F}}{2}}$ , na naglalaman lamang ng dalawang elemento ${0,1}$ , na may mga operasyon na isinagawa modulo 2: ang karagdagan ay tumutugma sa bitwise XOR, at multiplikasyon ay tumutugma sa bitwise AT. Sa pamamagitan ng pagpili ng hindi mababawasan na polynomial $m(x) = x^{2} + x + 1$ over ${{\mathbb{F}}{2}}$ , mabubuo natin ang field na ${{\mathbb{F}}_{{2^{2}}}}$ , kung saan ang mga elemento ay mga natitirang polynomial ng degree na hindi hihigit sa 1, $r(x) = ax + b$ (with $a, b \in {0, 1}$ ).

Habang ang isang paraan ng pagpapalawak ng mga field ay nagsasangkot ng pagkuha ng mga natitira gamit ang hindi mababawasan na mga polynomial, ang Binius ay gumagamit ng isang mas mahusay na diskarte: ang paggamit ng mga Multilinear Lagrange polynomial bilang batayan para sa mga extension ng tower. Ang pamamaraang ito ay nagbibigay-daan para sa mga recursive na extension ng field, kung saan ang bawat field ng extension ay naka-nest sa loob ng nauna.

Ang Tiyak na Pagpapatupad ng Mga Extension ng Tower ay ang mga sumusunod: Una, ${{\tau }{0}} = {{\mathbb{F}}{2}}$ ; Pagkatapos, ${{\tau }{1}} = \frac{{{\mathbb{F}}{2}}[{{x}{0}}]}{(x{0}^{2} + {{x}_{0}} + 1)}$ ; Susunod, ${{\tau }{k}} = \frac{{{\mathbb{F}}{2}}[{{x}{k-1}}]}{(x{k-1}^{2} + {{x}{k-1}}{{x}{k-2}} + 1)}$.

Mula sa proseso ng pagbuo ng mga extension ng field, malinaw na natutugunan ng mga extension ang sumusunod na relasyon: ${{\tau }{0}} \subset {{\tau }{1}} \subset {{\tau }{2}} \subset \cdots \subset {{\tau }{m}}$ . Para sa $k \ge 0$ , ang extension ng field ay maaari ding ipahayag sa direktang anyo ng isang singsing bilang: ${{\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)}$.

Batay sa pagpapatupad na ito, maaaring makuha ang iba't ibang mga extension tulad ng sumusunod:

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

Mula sa Mga Elementong Nakapaloob sa Pinalawak na Patlang Ito ay maliwanag na para sa isang elementong ${{b}{0}}{{b}{1}}{{b}{2}}\ldots {{b}{{{2}^{k}}-1}}$ na nagmula sa ${{\tau }{k}}$ , maaari itong mabulok sa kabuuan ng dalawang bahagi: ${{b}{lo}} + {{x}{k-1}}{{b}{hi}}$ (where ${{b}{lo}}, {{b}{hi}} \in {{\tau }{k-1}}$) . Halimbawa, $1100101010001111 = 11001010 + 1000111 \times {{x}{3}}$, where $11001010, 10001111 \in {{\tau }{2}}$ .

Sa pamamagitan ng paulit-ulit na nabubulok, sa wakas ay maipahayag natin ang: $$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}}$$

Bukod pa rito, para sa $k > 0$ , dahil $x_{k}^{2} = {{x}{k}}{{x}{k-1}} + 1$ , ang pagdaragdag at pagpaparami ay maaaring maipatupad nang mahusay sa ang binary extended field.

Pagpapatupad ng Binary Fields

Ang Irreducible ay nagbibigay ng open-source Rust na pagpapatupad ng Binius [3]. Kasama sa source code ang kumpletong pagpapatupad at pagpapatakbo para sa Tower of Binary Fields [8,9,10].

Sa [8], tulad ng ipinapakita sa Figure 1, kasama sa pagpapatupad ang kumpletong kahulugan ng mga operasyon para sa mga binary field at ang pagtatayo ng Tower of Binary Fields. Ang Tower of Binary Fields, na sumusuporta hanggang sa isang 128-bit na binary field, ay tinukoy bilang sumusunod: