3,593 показания

Как Binius намалява изчислителната сложност с кули от двоични полета

от Sin7Y3m2024/09/13

Твърде дълго; Чета

Екипът на Ulvetanna (IRREDUCIBLE) разгледа този въпрос в своята изследователска статия, озаглавена Кратки аргументи над кули от двоични полета. Те го внедриха в Rust с техния проект Binius: хардуерно оптимизиран SNARK. В Binius двоичните полета се конструират с помощта на кули от разширения на полета.

featured image - Как Binius намалява изчислителната сложност с кули от двоични полета

Намаляването на изчислителната сложност винаги е била една от основните цели на блокчейн технологията. Един ефективен подход за постигане на това е чрез намаляване на битовата ширина на изчислителното поле. Например, SNARK, базирани на елиптични криви, извършват аритметични операции в полета с битова ширина от 256 или по-висока, докато STARKs са еволюирали от използването на 64-битовото поле Goldilocks до 31-битовите полета Mersenne31 и BabyBear. Освен ефективността на простите числа по време на модулни операции, значителното намаляване на битовата ширина доведе до това, че Plonky2 е стотици пъти по-бърз от своя предшественик, Plonky. Следвайки тази траектория, някой може да се запита: възможно ли е да зададете ширината на полето на 1, по-специално ${\mathbb{F}}_{2}$? Екипът на Ulvetanna (IRREDUCIBLE) разгледа този въпрос в своята изследователска статия, озаглавена Кратки аргументи над кули от двоични полета [1] , и го внедриха в Rust с техния проект, Binius: хардуерно оптимизиран SNARK [2] [3] .

От пускането си на пазара Binius привлече значително внимание в ZK (Zero-Knowledge) общността. Екипът на LambdaClass предостави няколко технически анализа [4][5][6], а Виталик Бутерин предложи по-достъпно обяснение [7] . В тази статия ще изследваме основите на Binius, като се фокусираме върху кулите на двоичните полета, както от техническа, така и от гледна точка на изпълнение.

Двоични полета

Внедряването на Binius се основава на двоични полета. В Binius двоичните полета се конструират с помощта на кули от разширения на полета.

Най-простото двоично поле е ${{\mathbb{F}}{2}}$ , което съдържа само два елемента ${0,1}$ , като операциите се извършват по модул 2: събирането съответства на побитово XOR, а умножението съответства на побитово И. Като изберем нередуцируем полином $m(x) = x^{2} + x + 1$ over ${{\mathbb{F}}{2}}$ , можем да формираме полето ${{\mathbb{F}}_{{2^{2}}}}$ , където елементите са остатъци от полиноми със степен най-много 1, $r(x) = ax + b$ (with $a, b \in {0, 1}$ ).

Докато един метод за разширяване на полета включва вземане на остатъци с помощта на нередуцируеми полиноми, Binius използва по-ефективен подход: използването на мултилинейни полиноми на Лагранж като основа за разширения на кула. Този метод позволява рекурсивни разширения на полето, където всяко поле за разширение е вложено в предишното.

Специфичното изпълнение на разширенията на Tower е както следва: Първо, ${{\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)}$.

От процеса на изграждане на разширенията на полето става ясно, че разширенията отговарят на следната връзка: ${{\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)}$.

Въз основа на тази реализация могат да се получат различни разширения, както следва:

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

От елементите, съдържащи се в разширеното поле, е очевидно, че за елемент ${{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}}$ .

Чрез итеративно разлагане най-накрая можем да изразим: $$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}}$$

Освен това, за $k > 0$ , тъй като $x_{k}^{2} = {{x}{k}}{{x}{k-1}} + 1$ , събирането и умножението могат да бъдат ефективно приложени в двоичното разширено поле.

Внедряване на двоични полета

Irreducible предоставя внедряването на Rust с отворен код на Binius [3]. Изходният код включва пълни реализации и операции за Кулата от двоични полета [8,9,10].

В [8], както е показано на Фигура 1, изпълнението включва пълната дефиниция на операциите за двоични полета и изграждането на кулата от двоични полета. Кулата от двоични полета, поддържаща до 128-битово двоично поле, се дефинира, както следва: