Аналіз принципів Binius STARKs та роздуми щодо їх оптимізації

1 Вступ

Основною причиною низької ефективності STARKs є те, що більшість чисел у фактичних програмах є досить малими, але для забезпечення безпеки доказів на основі дерева Меркла, під час розширення даних за допомогою кодування Ріда-Соломона, багато додаткових надмірних значень займають цілу область. Щоб вирішити цю проблему, зменшення розміру області стало ключовою стратегією.

Перший покоління STARKs має ширину коду 252 біт, друге покоління - 64 біт, третє покоління - 32 біти, але 32-бітна ширина коду все ще має багато невикористаного простору. У порівнянні з цим, двійкове поле дозволяє безпосередньо виконувати операції над бітом, кодування компактне, ефективне і не має будь-якого невикористаного простору, тобто четверте покоління STARKs.

Коли використовуються менші поля, операція розширення поля стає все більш важливою для забезпечення безпеки. А двійкове поле, що використовується Binius, повністю покладається на розширення поля для забезпечення своєї безпеки та фактичної придатності. Більшість поліномів, що беруть участь у обчисленнях Prover, не потребують переходу в розширене поле, а лише виконуються в базовому полі, що дозволяє досягти високої ефективності в малих полях. Проте випадкові перевірки точок і обчислення FRI все ще потребують заглиблення у більше розширене поле для забезпечення необхідної безпеки.

При побудові системи доказів на основі бінарного поля виникає 2 практичні проблеми: під час обчислення представлення сліду в STARKs розмір поля, що використовується, повинен бути більшим за ступінь полінома; під час зобов'язання Merkle tree в STARKs необхідно виконати кодування Ріда-Соломона, розмір поля, що використовується, повинен бути більшим за розмір після розширення коду.

Binius запропонував інноваційне рішення для окремого вирішення цих двох проблем і реалізації однакових даних двома різними способами: по-перше, використовуючи багатовимірні (конкретно, багатолінійні) поліноми замість одновимірних поліномів, представляючи всю обчислювальну траєкторію через їх значення на "гіперкубах" (hypercubes); по-друге, оскільки довжина кожного виміру гіперкуба дорівнює 2, стандартне розширення Ріда-Соломона не може бути реалізоване, як у випадку STARKs, але гіперкуб можна розглядати як квадрат (square), ґрунтуючись на якому можна здійснити розширення Ріда-Соломона. Цей підхід значно підвищує ефективність кодування та обчислювальну продуктивність при забезпеченні безпеки.

! Дослідження Bitlayer: Аналіз принципів Бініуса Старка та оптимізаційне мислення

2 Принципи аналізу

Поточна більшість систем SNARKs зазвичай складається з двох частин:

• Інформаційно-теоретичне поліно́мне інтерактивне оракульне доведення (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP)
• Схема полінономних зобов'язань (Polynomial Commitment Scheme, PCS)

Binius: HyperPlonk PIOP + Brakedown PCS + бінарна область. Конкретно кажучи, Binius включає п'ять ключових технологій для забезпечення своєї ефективності та безпеки:

1. Армування на основі баштової двійкової області
2. Адаптована версія перевірки добутку та перестановки HyperPlonk
3. Нова множинна теорія зсуву
4. Поліпшена версія аргументації пошуку Lasso
5. Схема обіцянки малих многочленів

2.1 Кінцеві поля: арифметика на основі веж бінарних полів

Бінарна область з塔式 є ключем до реалізації швидких перевіряємих обчислень, що обумовлено двома аспектами: ефективними обчисленнями та ефективною алгеброю. Бінарна область в своїй суті підтримує надзвичайно ефективні алгебричні операції, що робить її ідеальним вибором для криптографічних застосувань, чутливих до продуктивності. Крім того, структура бінарної області підтримує спрощений алгебраїчний процес, тобто операції, що виконуються в бінарній області, можуть бути представлені у компактній та легкій для перевірки алгебраїчній формі.

У полях простих чисел Fp поширені методи редукції включають редукцію Барретта, редукцію Монтгомері, а також спеціальні методи редукції для певних скінченних полів, таких як Mersenne-31 або Goldilocks-64. У бінарному полі F2k зазвичай використовують методи редукції, зокрема спеціальну редукцію (як у AES), редукцію Монтгомері (як у POLYVAL) та рекурсивну редукцію (як Tower).

Двійкове поле не потребує переносу в операціях додавання та множення, а квадратування в двійковому полі є дуже ефективним, оскільки воно підпорядковується спрощеному правилу (X + Y )2 = X2 + Y 2.

! Дослідження Bitlayer: Аналіз принципів Бініуса Старка та оптимізаційне мислення

2.2 PIOP: адаптований продукт HyperPlonk і PermutationCheck

Дизайн PIOP в протоколі Binius запозичив HyperPlonk і використовує ряд основних перевірочних механізмів для верифікації правильності поліномів і множин змінних. Ці основні перевірки включають:

1. Перевірка воріт
2. Перевірка перестановки
3. Перевірка пошуку
4. Функція MultisetCheck
5. Перевірка товару
6. Перевірка нуля
7. Перевірка суми
8. Пакетна перевірка

Binius зробив такі покращення в порівнянні з HyperPlonk:

• Оптимізація ProductCheck
• Обробка проблеми поділу на нуль
• Перевірка перестановок через стовпці

2.3 PIOP: новий багаторівневий зсув аргумент

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

• Упаковка
• Оператори зсуву

2.4 PIOP：адаптована версія аргументу пошуку Lasso

Протокол Lasso дозволяє стороні, що доводить, зобов'язатися вектором a ∈ Fm і довести, що всі його елементи існують у заздалегідь визначеній таблиці t ∈ Fn. Протокол Lasso складається з трьох компонентів:

• Віртуальна поліноміальна абстракція великої таблиці
• Малий пошук
• Перевірка множин

Протокол Binius адаптує Lasso для операцій у бінарному полі, вводячи множинну версію протоколу Lasso.

2.5 PCS：адаптована версія Brakedown PCS

Основна ідея побудови BiniusPCS полягає в пакуванні. У статті Binius представлені 2 схеми обіцянки поліномів Brakedown на основі бінарних полів:

1. Використовувати конкатенований код для інстанціювання
2. Використовуючи технологію кодування на рівні блоків, підтримує окреме використання кодів Ріда-Соломона

Binius полігональні зобов'язання в основному використовують такі технології:

• Малий поліноміальний обіцянки та оцінка розширеного поля
• Малий загальний конструкція
• Блочне кодування та коди Ріда-Соломона

3 Оптимізація мислення

Щоб подальше підвищити продуктивність протоколу Binius, у цій статті запропоновано чотири ключові оптимізаційні моменти:

1. PIOP на основі GKR: для бінарних доменних множення
2. Оптимізація ZeroCheck PIOP: балансування витрат обчислень між Prover та Verifier
3. Оптимізація Sumcheck PIOP: оптимізація для малих областей Sumcheck
4. Оптимізація PCS: оптимізація через FRI-Binius

3.1 GKR-based PIOP: Бінарне множення полів на основі GKR

Алгоритм цілочисельного множення на основі GKR, шляхом перетворення "перевірити, чи два 32-бітних цілочисельних числа A і B задовольняють A·B =? C" на "перевірити, чи (gA)B =? gC є істинним", значно зменшує витрати на зобов'язання завдяки протоколу GKR.

3.2 ZeroCheck PIOP оптимізація: баланс витрат на обчислення Prover та Verifier

Стаття «Деякі поліпшення PIOP для ZeroCheck» пропонує кілька оптимізацій для розподілу обсягу роботи між довіреною стороною (P) та перевіряючою стороною (V), щоб зменшити витрати. Основні оптимізації включають:

• Зменшити передачу даних з боку доказувача
• Зменшити кількість оцінювальних пунктів для сторони, що підтверджує
• Алгебраїчна інтерполяційна оптимізація

! Дослідження Bitlayer: Аналіз принципів Бініуса Старка та оптимізаційне мислення

3.3 Оптимізація PIOP Sumcheck: протокол Sumcheck на основі малих областей

Ingonyama у 2024 році представив вдосконалену версію протоколу Sumcheck на основі малих областей та опублікував код реалізації з відкритим вихідним кодом. Основні оптимізації включають:

• Вплив та фактори покращення зміни раундів
• Вплив розміру базової області на продуктивність
• Оптимізаційні вигоди алгоритму Карацуби
• Підвищення ефективності пам'яті

3.4 PCS оптимізація: FRI-Binius зменшення розміру доказу Binius

Стаття «Полілогарифмічні доведення для мультилінійних функцій над бінарними вежами», скорочено FRI-Binius, реалізує механізм складання FRI для бінарного поля, що приносить 4 аспекти інновацій:

• Плоский многочлен
• Поліном зникнення підпростору
• Пакування алгебраїчної бази
• Обмін сумою SumCheck

За допомогою FRI-Binius можна зменшити розмір доказу Binius на один порядок.

4 Підсумок

Binius є "спільним проєктом, що використовує апаратне, програмне забезпечення та прискорений протокол Sumcheck на FPGA", який може швидко доводити при дуже низькому використанні пам'яті. У Binius практично повністю усунуто вузьке місце з коміту Prover, новим вузьким місцем є протокол Sumcheck, де багато оцінок многочленів та проблеми доменного множення можуть бути ефективно розв'язані за допомогою спеціалізованого апаратного забезпечення.

FRI-Binius рішення, для варіанту FRI, може запропонувати дуже привабливий вибір — усунути вбудовані витрати з рівня доказів домену, не призводячи до різкого зростання витрат на рівні агрегованих доказів. Наразі команда Irreducible працює над своїм рекурсивним рівнем і оголосила про співпрацю з командою Polygon для створення zkVM на базі Binius; JoltzkVM переходить з Lasso на Binius, щоб покращити свою рекурсивну продуктивність; команда Ingonyama реалізує версію Binius на FPGA.

! Дослідження Bitlayer: Аналіз принципів Бініуса Старка та оптимізаційне мислення