Намаляването на изчислителната сложност винаги е била една от основните цели на блокчейн технологията. Един ефективен подход за постигане на това е чрез намаляване на битовата ширина на изчислителното поле. Например, SNARK, базирани на елиптични криви, извършват аритметични операции в полета с битова ширина от 256 или по-висока, докато STARKs са еволюирали от използването на 64-битовото поле Goldilocks до 31-битовите полета Mersenne31 и BabyBear. Освен ефективността на простите числа по време на модулни операции, значителното намаляване на битовата ширина доведе до това, че Plonky2 е стотици пъти по-бърз от своя предшественик, Plonky. Следвайки тази траектория, някой може да се запита: възможно ли е да зададете ширината на полето на 1, по-специално ${\mathbb{F}}_{2}$? Екипът на Ulvetanna (IRREDUCIBLE) разгледа този въпрос в своята изследователска статия, озаглавена Кратки аргументи над кули от двоични полета  , и го внедриха в Rust с техния проект, Binius: хардуерно оптимизиран SNARK  .   [1]     [2] [3]  От пускането си на пазара Binius привлече значително внимание в ZK (Zero-Knowledge) общността. Екипът на LambdaClass предостави няколко технически анализа [4][5][6], а Виталик Бутерин предложи по-достъпно обяснение  . В тази статия ще изследваме основите на Binius, като се фокусираме върху кулите на двоичните полета, както от техническа, така и от гледна точка на изпълнение.   [7]   Двоични полета  Внедряването на Binius се основава на двоични полета. В Binius двоичните полета се конструират с помощта на кули от разширения на полета.  Най-простото двоично поле е   , което съдържа само два елемента   , като операциите се извършват по модул 2: събирането съответства на побитово XOR, а умножението съответства на побитово И. Като изберем нередуцируем полином   , можем да формираме полето   , където елементите са остатъци от полиноми със степен най-много 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}$  Докато един метод за разширяване на полета включва вземане на остатъци с помощта на нередуцируеми полиноми, 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-битово двоично поле, се дефинира, както следва:   Освен това [8] предоставя код за тест и проверка за Кулата на двоичните полета и свързаните с нея операции.   Референции  [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 върху двоични полета: Binius - Част 1 (lambdaclass.com)  [5] SNARK върху двоични полета: Binius - Част 2 (lambdaclass.com)  [6] Как Binius помага за напредъка на ZK индустрията (lambdaclass.com)  [7]   https://vitalik.eth.limo/general/2024/04/29/binius.html  [8] binius/crates/field/src/binary_field.rs основно · IrreducibleOSS/binius · GitHub  [9] binius/crates/field/src/binary_field_arithmetic.rs на главния · IrreducibleOSS/binius · GitHub  [10] binius/crates/field/src/extension.rs на главния · IrreducibleOSS/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

Това аудио е създадено на оригиналния език на историята!

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

Download free Tech Leaders Productivity Report!

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

About Author

КОМЕНТАРИ

ЗАКАЧВАЙТЕ ЕТИКЕТИ

ТАЗИ СТАТИЯ Е ПРЕДСТАВЕНА В

Related Stories

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps