3,593 kuverenga

Maitiro eBinius Anoderedza Computational Complexity neTowers yeBinary Fields

by Sin7Y3m2024/09/13

Kurebesa; Kuverenga

Chikwata cheUlvetanna (IRREDUCIBLE) chakapindura mubvunzo uyu mubepa ravo rekutsvagisa rakanzi Succinct Arguments pamusoro peTowers of Binary Fields. Vakazviita muRust nepurojekiti yavo, Binius: a Hardware-Optimized SNARK. MuBinius, Binary Minda inovakwa uchishandisa shongwe dzemawedzero emunda.

featured image - Maitiro eBinius Anoderedza Computational Complexity neTowers yeBinary Fields

Kuderedza computational kuomarara kwagara kuri chimwe chezvinangwa zvekutanga zve blockchain tekinoroji. Imwe nzira inoshanda yekuita izvi ndeyekudzikisa hupamhi hwemunda wekuverenga. Semuyenzaniso, maSNARK anoenderana nema elliptic curves anoita masvomhu muminda ine bit wides ye 256 kana kupfuura, ukuwo maSTARK akashanduka kubva pakushandisa 64-bit Goldilocks munda kuenda ku31-bit Mersenne31 uye BabyBear ndima. Kupfuura kugona kwenhamba dzepamusoro panguva yekushanda kwemodular, kudzikiswa kwakakosha kwehupamhi hwaita kuti Plonky2 iite mazana ekukurumidza kupfuura yakatangira, Plonky. Kutevera nzira iyi, munhu angashamisika: zvinokwanisika here kuseta hupamhi hwemunda kune 1, kunyanya ${\mathbb{F}}_{2}$? Chikwata cheUlvetanna (IRREDUCIBLE) chakapindura mubvunzo uyu mubepa ravo rekutsvagisa rakanzi Succinct Arguments pamusoro peTowers of Binary Fields. [1] , uye vakaishandisa muRust nepurojekiti yavo, Binius: a Hardware-Optimized SNARK [2] [3] .

Kubva pakaburitswa, Binius akawana kutariswa kwakakosha munharaunda yeZK (Zero-Knowledge). Chikwata cheLambdaClass chapa ongororo dzakati wandei [4][5][6], uye Vitalik Buterin akapa tsananguro inowanika. [7] . Muchikamu chino, tichaongorora nheyo dzeBinius, tichitarisa paTowers yeBinary Fields, kubva kune zvese zvehunyanzvi uye kuita maonero.

Binary Fields

Kuitwa kweBinius kwakavakirwa paBinary Fields. MuBinius, Binary Fields inovakwa uchishandisa shongwe dzemawedzero emunda.

Yakareruka Binary Field is ${{\mathbb{F}}{2}}$ , iyo ine zvinhu zviviri chete ${0,1}$ , ine ma operation akaitwa modulo 2: kuwedzera kunoenderana ne bitwise XOR, uye kuwanda kunoenderana ne bitwise. UYE. Nekusarudza polynomial isingachinjiki $m(x) = x^{2} + x + 1$ over ${{\mathbb{F}}{2}}$ , tinogona kugadzira ndima ${{\mathbb{F}}_{{2^{2}}}}$ , apo zvinhu zvinenge zvasara zvepolynomials edhigirii zvakanyanya 1, $r(x) = ax + b$ (with $a, b \in {0, 1}$ ).

Nepo imwe nzira yekuwedzera minda ichisanganisira kutora zvakasara uchishandisa irreducible polynomials, Binius anoshandisa nzira inoshanda: kushandiswa kweMultilinear Lagrange polynomials sehwaro hwekuwedzera shongwe. Iyi nzira inobvumira kudzokororwa kwemunda wekuwedzera, uko imwe neimwe ndima yekuwedzera inoiswa mukati meiyo yapfuura.

Iko Kunyatsoitwa kweTower Extensions kunotevera: Kutanga, ${{\tau }{0}} = {{\mathbb{F}}{2}}$ ; Zvadaro, ${{\tau }{1}} = \frac{{{\mathbb{F}}{2}}[{{x}{0}}]}{(x{0}^{2} + {{x}_{0}} + 1)}$ ; Zvadaro, ${{\tau }{k}} = \frac{{{\mathbb{F}}{2}}[{{x}{k-1}}]}{(x{k-1}^{2} + {{x}{k-1}}{{x}{k-2}} + 1)}$.

Kubva pakuvakwa kwekuwedzerwa kwemunda, zviri pachena kuti mawedzero anogutsa hukama hunotevera: ${{\tau }{0}} \subset {{\tau }{1}} \subset {{\tau }{2}} \subset \cdots \subset {{\tau }{m}}$ . Kune $k \ge 0$ , kuwedzera kwemunda kunogonawo kuratidzwa nenzira yakananga yemhete se: ${{\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)}$.

Zvichienderana nekushandiswa uku, kuwedzera kwakasiyana kunogona kuwanikwa sezvinotevera:

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

Kubva muZvinhu Zviri Mundima Yakawedzerwa Zviripachena kuti chinhu ${{b}{0}}{{b}{1}}{{b}{2}}\ldots {{b}{{{2}^{k}}-1}}$ yakabva pa ${{\tau }{k}}$ , inogona kuderedzwa kuita zvikamu zviviri zvinoti: ${{b}{lo}} + {{x}{k-1}}{{b}{hi}}$ (where ${{b}{lo}}, {{b}{hi}} \in {{\tau }{k-1}}$) . Semuyenzaniso, $1100101010001111 = 11001010 + 1000111 \times {{x}{3}}$, where $11001010, 10001111 \in {{\tau }{2}}$ .

Nekuwora kwadzokorodza, tinogona pakupedzisira kutaura: $$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}}$$

Pamusoro pezvo, ye $k > 0$ , sezvo $x_{k}^{2} = {{x}{k}}{{x}{k-1}} + 1$ , kuwedzera nekuwanda kunogona kuitwa nemazvo mu iyo binary yakawedzerwa munda.

Kuitwa kweBinary Fields

Irreducible inopa yakavhurika-sosi Rust kuitiswa kweBinius [3]. Iyo kodhi kodhi inosanganisira kuita kwakazara uye mashandiro eShongwe yeBinary Fields [8,9,10].

Mu [8], sezvakaratidzwa muMufananidzo 1, kushandiswa kunosanganisira tsanangudzo yakazara yekushanda kwebinary fields uye kuvaka Tower of Binary Fields. The Tower of Binary Fields, inotsigira kusvika ku128-bit binary field, inotsanangurwa sezvinotevera: