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

1. Вступ

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

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

Binius використовує такі основні технології:

• Армування на основі бінарної області з висоти
• Покращена версія перевірки добутку та перестановки HyperPlonk
• Нова багатоосна зміщення доказ
• Покращена версія теорії пошуку Lasso
• Малий поліноміальний комітет

2. Аналіз принципу

2.1 Армізація на основі веж бінарних полів

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

• Ефективне обчислення
• Ефективна арифметизація
• Підтримка спрощеного арифметичного процесу
• Можна повністю використати його ієрархічні властивості через баштову структуру

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

2.2 адаптована версія HyperPlonk Product та PermutationCheck

Binius покращив HyperPlonk у таких аспектах:

• Оптимізація ProductCheck: спеціалізація значення на 1, спрощення процесу перевірки
• Обробка проблеми ділення на нуль: можна продовжувати обробку, навіть якщо знаменник дорівнює нулю.
• Перемішування між колонками PermutationCheck: підтримує PermutationCheck між кількома колонками

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

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

Binius впровадив два ключові методи:

• Упаковка: оптимізація операцій шляхом упаковки сусідніх елементів
• Оператори зсуву: переставлення елементів у блоці на основі заданого зсуву

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

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

2.5 адаптоване видання Brakedown PCS

Binius пропонує два варіанти багаточленного зобов'язання Brakedown на основі двійкових областей:

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

3. Оптимізація думки

3.1 PIOP на базі GKR

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

3.2 ZeroCheck PIOP оптимізація

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

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

3.3 Sumcheck PIOP оптимізація

Ingonyama запропонував вдосконалену версію протоколу Sumcheck на основі малих областей:

• Вибір зміни раундів впливає на продуктивність
• Менші базові області виявляють більш виражені переваги
• Алгоритм Карацуби покращив продуктивність
• Підвищено ефективність пам'яті

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

3.4 PCS оптимізація: FRI-Binius

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

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

4. Підсумок

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