Аналіз принципів Binius STARKs та його оптимізаційні роздуми

1 Вступ

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

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

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

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

2 Аналіз принципів

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

1. Аріфметика на основі веж бінарних полів (towers of binary fields)
2. Адаптовано перевірку добутку та перестановки HyperPlonk
3. Нова багатолінійна довідка
4. Покращена версія доведення пошуку Lasso
5. Схема обіцянок малих полів (Small-Field PCS)

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

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

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

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

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

Binius покращився в трьох аспектах:

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

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

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

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

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

Протокол Lasso складається з трьох компонентів:

• Віртуальна багаточленна абстракція великої таблиці
• Пошук малих таблиць
• Багаторазова перевірка

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

2.5 PCS：перероблена версія Brakedown PCS

Основна ідея побудови BiniusPCS полягає в упаковці. Багаточленне зобов'язання Binius в основному використовує:

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

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

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

Для подальшого підвищення продуктивності протоколу Binius у цій статті пропонуються чотири ключові точки оптимізації:

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

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

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

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

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

Основні напрямки оптимізації включають:

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

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

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

Основні пункти оптимізації включають:

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

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

FRI-Binius реалізував механізм згортання FRI бінарної області, що приносить 4 аспекти інновацій:

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

4 Підсумок

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

У Binius практично повністю усунено вузьке місце комітменту Prover, новим вузьким місцем є протокол Sumcheck, а численні обчислення багаточленів і проблеми множення в полі в протоколі Sumcheck можна ефективно вирішити за допомогою спеціалізованого апаратного забезпечення. Рішення FRI-Binius є варіантом FRI, яке пропонує дуже привабливий вибір — усунути накладні витрати на вбудовані витрати на рівні доказів у полі, не призводячи до різкого зростання витрат на рівні агрегованих доказів.

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

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