3,663 показання

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

за Sin7Y3m2024/09/13

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

Команда Ulvetanna (IRREDUCIBLE) розглянула це питання у своїй дослідницькій статті під назвою «Стислі аргументи над вежами бінарних полів». Вони реалізували це в Rust у своєму проекті Binius: апаратно-оптимізований SNARK. У Binius двійкові поля будуються за допомогою веж розширень поля.

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

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

У той час як один із методів розширення полів передбачає отримання залишків за допомогою незвідних поліномів, Бініус використовує більш ефективний підхід: використання багатолінійних поліномів Лагранжа як основи для розширення вежі. Цей метод дозволяє рекурсивні розширення полів, де кожне поле розширення вкладено в попереднє.

Конкретна реалізація розширень 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-бітного двійкового поля, визначається наступним чином: