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

1. Вступ

У процесі еволюції STARKs ефективність кодування поступово зростає, але все ще існує марнотратство. Binius реалізував більш компактне та ефективне кодування, безпосередньо застосувавши побітові операції, що має потенціал стати STARK 4-го покоління. Binius використовує технології, такі як аритметика в двійкових полях, вдосконалений HyperPlonk для перевірки добутків і перестановок, зобов'язання до многочленів малого поля та інші, щоб підвищити ефективність з різних сторін. Ще є можливості для подальшої оптимізації в таких аспектах, як множення в двійкових полях, ZeroCheck, SumCheck, PCS тощо, щоб покращити швидкість доказу та зменшити його розмір.

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

Binius поєднує HyperPlonk PIOP, Brakedown PCS та двійкову область, містить п'ять ключових технологій:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Завдяки протоколу GKR, що замінює алгоритм Lasso Lookup, можна значно зменшити витрати на зобов'язання.

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

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

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

Оптимізація для малих полів Sumcheck, подальше зменшення обчислювального навантаження на малих полях.

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

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

4. Підсумок

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

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