Зменшення обчислювальної складності завжди було однією з головних цілей технології блокчейн. Одним з ефективних підходів до досягнення цього є зменшення бітової ширини обчислювального поля. Наприклад, SNARK, засновані на еліптичних кривих, виконують арифметичні операції в полях з бітовою шириною 256 або вище, тоді як STARK еволюціонували від використання 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}$  У той час як один із методів розширення полів передбачає отримання залишків за допомогою незвідних поліномів, Бініус використовує більш ефективний підхід: використання багатолінійних поліномів Лагранжа як основи для розширення вежі. Цей метод дозволяє рекурсивні розширення полів, де кожне поле розширення вкладено в попереднє.  Конкретна реалізація розширень 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 забезпечує реалізацію Binius із відкритим кодом Rust [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

Це аудіо створено мовою оригіналу історії!

Надто довго; Читати

Як Binius зменшує обчислювальну складність за допомогою веж бінарних полів

Як Binius зменшує обчислювальну складність за допомогою веж бінарних полів

About Author

КОМЕНТАРІ

ПОВІСИТИ БИРКИ

ЦЯ СТАТТЯ БУЛА ПРЕДСТАВЛЕНА В

Related Stories

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps