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

1 Вступ

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

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

Бінарна область широко використовується в криптографії, наприклад, у AES, GMAC, QR-кодах, первинному FRI та протоколах zk-STARK.

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

Binius пропонує інноваційні рішення:

1. використовуючи багатозмінні поліноми замість однозмінних поліномів, представляє всю обчислювальну траєкторію через їх значення на "гіперкубі"
2. Розглядати гіперкуб як квадрат для розширення Ріда-Соломона

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

Binius = HyperPlonk, PIOP + Brakedown PCS + Binary Domain

Включаючи п'ять ключових технологій:

1. арифметизація на основі баштової бінарної області
2. адаптація перевірки добутку та перестановки HyperPlonk
3. нова багатолінійна зміщувальна теорія
4. Поліпшена версія Lasso пошуку доказів
5. Малодоменна поліноміальна угода

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

Баштовий бінарний простір підтримує високоефективні арифметичні операції та спрощений арифметичний процес.

128-бітний рядок може бути розглянутий як елемент в 128-бітній бінарній області або бути проаналізованим як два 64-бітних елементи області, чотири 32-бітних елементи області, шістнадцять 8-бітних елементів області або 128 елементів F2. Ця гнучкість представлення не потребує додаткових обчислювальних витрат.

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

Дизайн PIOP в протоколі Binius запозичує HyperPlonk, використовуючи ряд основних механізмів перевірки:

• Перевірка воріт
• Перевірка перестановки
• Перевірка пошуку
• Функція MultisetCheck
• Перевірка товару
• Нульовий чек
• Перевірка суми
• Пакетна перевірка

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

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

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

Ключові методи побудови та обробки віртуальних多项式 у протоколі Binius:

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

2.4 PIOP：адаптоване Lasso lookup аргумент

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

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

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

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

Біниус у своїй статті пропонує 2 схеми поліноміальних зобов'язань Brakedown на основі бінарних полів:

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

Малі поліноміальні зобов'язання та оцінка в розширених полях, загальні конструкції малих полів та блочне кодування з кодами Ріда-Соломона та інші технології використовуються для побудови поліноміальних зобов'язань Binius.

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

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

Чотири ключові точки оптимізації:

1. PIOP на основі GKR: замість алгоритму Lasso Lookup використовуємо протокол GKR для бінарних множення.

2. Оптимізація ZeroCheck PIOP: балансування витрат на обчислення між Prover та Verifier

3. Оптимізація Sumcheck PIOP: оптимізація для малих доменів Sumcheck

4. Оптимізація PCS: зменшення розміру доказів за допомогою оптимізації FRI-Binius

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

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

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

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

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

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

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

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

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

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

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

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

4 Підсумок

Ціннісна пропозиція Binius полягає в тому, що вона може використовувати мінімальні області power-of-two для свідків. У Binius майже повністю усунено вузьке місце зобов'язання Prover, нове вузьке місце знаходиться в протоколі Sumcheck.

FRI-Binius рішення є варіантом FRI, який дозволяє усунути накладні витрати на вбудовування з рівня доказу домену, не призводячи до різкого зростання витрат на агрегований рівень доказу.

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

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