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

1. Вступ

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

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

Двійкові поля широко застосовуються в криптографії, такі як AES(F28), GMAC(F2128), QR-коди(F28) тощо. Коли використовуються менші поля, операції розширення стають все важливішими для забезпечення безпеки. Двійкове поле, яке використовує Binius, повністю покладається на розширення для забезпечення безпеки та доступності. Більшості обчислень Prover виконується в основному полі, що є ефективним; перевірки випадкових точок і обчислення FRI вимагають глибшого дослідження більшого розширеного поля, щоб забезпечити безпеку.

Інноваційні рішення Binius:

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

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

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

Binius = HyperPlonk, PIOP + Brakedown PCS + Binary Domain

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

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

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

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

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

128-символьний ряд можна гнучко інтерпретувати:

• Унікальний елемент в 128-бітному бінарному полі
• Два 64-бітних елементи області башти
• Чотири елементи 32-бітної області
• 16 елементів з 8-бітних торових областей
• 128 елементів F2

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

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

Ядро механізмів перевірки Binius:

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

Покращення HyperPlonk від Binius:

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

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

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

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

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

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

• Висока ефективність доказів: зобов'язання n+m елементів області
• Не потрібно зобов'язуватися до великих таблиць: можна обробляти надвеликі таблиці

Binius впроваджує множинну версію протоколу Lasso:

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

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

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

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

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

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

Малі поліноміальні обіцянки та оцінка розширених полів:

• Обіцянка на малому домені K
• Оцінка у більшій області розширення L/K

Блочне кодування та коди Ріда-Соломона:

• Дозволити малим доменам (, як F2), використовувати велику алфавіт (, як F216), для ефективного зобов'язання кодів Ріда-Соломона.

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

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

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

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

Перетворити "перевірка A·B =? C" на "перевірка (gA)B =? gC"

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

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

Оптимізаційні методи:

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

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

Покращення ключових моментів:

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

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

Чотири інновації:

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

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

4. Підсумок

Переваги Binius:

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

Нова проблема: Протокол Sumcheck

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

ФРІ-Бініус:

• Усунення накладних витрат на вбудовану перевірку домену
• Не призводить до різкого зростання витрат на рівні агрегованого доказу

Поточний прогрес:

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

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