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

1 Вступ

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

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

Двійкові домени вже широко використовуються в криптографії, типовими прикладами є:

• Стандарт високої криптографії (AES), оснований на полі F28
• Galois повідомлення аутентифікації ( GMAC ), оснований на полях F2128
• QR-код, що використовує кодування Ріда-Соломона на основі F28
• Оригінальний протокол FRI та zk-STARK, а також хеш-функція Grøstl, яка потрапила до фіналу SHA-3

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

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

• Використання багатоваріантного (конкретно, багатолінійного) многочлена замість одноваріантного многочлена, через його значення на "гиперкубі" для представлення всієї обчислювальної траєкторії
• Розглядати гіперкуб як квадрат, на основі якого проводити розширення Ріда-Соломона

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

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

Binius = HyperPlonk, PIOP + Brakedown PCS + Binary Domain

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

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

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

Переваги баштової двійкової області:

• Висока ефективність обчислень: бінарна область за суттю підтримує високоефективні аритметичні операції
• Ефективна арифметизація: структура бінарного поля підтримує спрощений арифметичний процес
• Гнучке представлення: той самий рядок може бути проінтерпретований кількома способами в контексті бінарної області
• Не потрібно зменшувати: двійкове поле не потребує перенесення в операціях додавання та множення
• Високоефективні квадратні обчислення:(X + Y)2 = X2 + Y2

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

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

Основний механізм перевірки:

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

Порівняно з покращеннями HyperPlonk:

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

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

Ключові методи:

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

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

Переваги протоколу Lasso:

• Ефективне доведення: для m пошуків у таблиці розміром n потрібно лише зобов'язатися m+n елементами області.
• Не потрібно зобов'язуватися до великої таблиці: якщо таблиця t є структурованою, то не потрібно зобов'язуватися до неї, можна обробляти надвеликі таблиці.

Склад протоколу Lasso:

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

Переклад Binius до Lasso:

• Введення множинної версії протоколу Lasso
• Вимагається, щоб сторона, що доводить, зобов'язалася надати вектор лічильників читання, який завжди ненульовий.

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

Основна ідея: packing

Два варіанти:

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

Основні технології:

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

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

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

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

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

Основна ідея:

Перевірте, чи задовольняють два 32-бітних цілі числа A і B рівняння A·B =? C Перетворити на
"Перевірка (gA)B =? gC чи дійсно це так"

Переваги:

• Потрібен лише один допоміжний зобов'язання
• Зменшити витрати на Sumchecks

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

Оптимізаційний напрямок:

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

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

Поліпшення акцентів:

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

Конкретні результати:

• У випадку базового поля GF[2], продуктивність алгоритму 4 перевищує наївний алгоритм майже в 30 разів.
• Алгоритм 4 потребує лише 0,26 МБ пам'яті, тоді як алгоритм 3 потребує 67 МБ

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

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

Чотири інноваційні моменти:

1. Плоский многочлен
2. Поліном зникнення підпростору
3. Пакування алгебраїчної бази
4. Обмін环SumCheck

Ефективність: Зменшити розмір доказу Binius на один порядок величини

4 Підсумок

Переваги Binius:

• Може використовувати найменше поле степеня двійки для свідків
• Низьке використання пам'яті, швидке підтвердження
• Практично повністю усунено вузьке місце зобов'язання комітету Prover

Розчин FRI-Binius: Видалення витрат на вбудовування з шару підтвердження домена без виклику різкого зростання витрат шару агрегованого підтвердження.

Останні новини:

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