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

1. Вступ

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

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

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

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

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

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

2.1 Арфметизація на основі баштової двійкової області

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

2.2 адаптована версія перевірки добутків та перестановок HyperPlonk

Binius запозичив основний механізм перевірки HyperPlonk, включаючи GateCheck, PermutationCheck, LookupCheck тощо, і вніс покращення в наступних аспектах:

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

2.3 Новий багатолінійний зсувний доказ

Binius впровадив два ключові методи Packing і зсуву для побудови та обробки віртуальних многочленів.

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

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

2.5 малий многочлен обіцянки

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

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

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

3.1 PIOP на базі GKR

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

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

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

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

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

Ingonyama запропонував вдосконалену версію протоколу Sumcheck на основі малих областей, зосереджуючи увагу на виборі переключення раундів t.

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

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

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

4. Підсумок

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

FRI-Binius схема є варіантом FRI, яка дозволяє усунути витрати на вбудовування з рівня доказів області, не призводячи до різкого зростання витрат на рівні агрегованих доказів. Наразі кілька команд працюють над технологіями, пов'язаними з Binius, включаючи рекурсивний рівень, zkVM тощо.

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