Анализ принципов Binius STARKs и его оптимизация

1 Введение

Основная причина низкой эффективности STARK состоит в том, что большинство чисел в реальных программах довольно малы, но для обеспечения безопасности доказательства на основе дерева Меркла, при использовании кодирования Рида-Соломона для расширения данных многие дополнительные избыточные значения занимают весь корпус. Снижение размера корпуса стало ключевой стратегией.

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

Двоичные поля широко применяются в криптографии, такие как AES, GMAC, QR-коды, оригинальный FRI и протоколы zk-STARK.

При использовании двоичных полей Binius полностью полагается на расширение полей для обеспечения безопасности и фактической доступности. Большинство многочленов, участвующих в вычислениях Prover, не требуют перехода в расширенные поля и могут работать только в базовом поле, что обеспечивает высокую эффективность в малых полях.

Binius предложил инновационное решение:

1. Использование многопараметрического многочлена вместо однопараметрического многочлена для представления всей вычислительной траектории через его значения на "гиперкубе".
2. Рассмотрим гиперкуб как квадрат для расширения Рида-Соломона

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. Эта гибкость представления не требует дополнительных вычислительных затрат.

! Исследование битlayer: Анализ принципов Биниуса СТАРКСА и оптимизационное мышление

2.2 PIOP: адаптированная версия HyperPlonk Product и PermutationCheck

Дизайн PIOP в протоколе Binius заимствовал HyperPlonk и использует ряд основных механизмов проверки:

• ГейтЧек
• Проверка перестановок
• LookupCheck (LookupCheck)
• МультисетЧек
• Проверка продукта
• Нулевой чек
• СуммЧек
• Пакетная проверка

Binius внес улучшения в следующих 3 областях:

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

2.3 PIOP：новый многолинейный сдвиг аргумента

Ключевые методы построения и обработки виртуальных многочленов в протоколе Binius:

• Упаковка
• Операторы сдвига

2.4 PIOP：адаптированная версия аргумента поиска Lasso

Протокол Lasso состоит из трех компонентов:

• Виртуальная полиномиальная абстракция большой таблицы
• Поиск малой таблицы
• Множественная проверка

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

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

Binius статья предлагает 2 схемы полиномиальной приверженности Brakedown на основе двоичных полей:

1. использует объединённый код для инстанцирования
2. использует технологию кодирования на уровне блоков и поддерживает отдельное использование кодов Рида-Соломона

Малые полиномиальные обязательства и оценки в расширенных полях, общие конструкции малых полей и блочное кодирование с использованием кодов Рида-Соломона и другие технологии используются для построения полиномиальных обязательств Binius.

3 Оптимизация мышления

Четыре ключевых момента оптимизации:

1. PIOP на основе GKR: для бинарных операций умножения с помощью протокола GKR заменяется алгоритм Lasso Lookup

2. Оптимизация ZeroCheck PIOP: балансировка вычислительных затрат между Prover и Verifier

3. Оптимизация Sumcheck PIOP: оптимизация для малых областей Sumcheck

4. Оптимизация PCS: снижение размера доказательства за счет оптимизации FRI-Binius

3.1 PIOP на основе GKR: бинарное умножение в поле на основе GKR

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

! Исследование битlayer: анализ принципов Биниуса СТАРКСА и оптимизационное мышление

3.2 Оптимизация ZeroCheck PIOP: балансировка вычислительных затрат между Prover и Verifier

Основные направления оптимизации:

• Уменьшение передачи данных со стороны доказателя
• Уменьшить количество оценочных точек для доказательной стороны
• Алгебраическая интерполяция оптимизации

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

Основные точки оптимизации:

• Влияние и коэффициенты улучшения переключения раундов
• Влияние размера области на производительность
• Оптимизация алгоритма Карацубы
• Повышение эффективности использования памяти

3.4 PCS оптимизация: FRI-Binius уменьшение размера доказательства Binius

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

• Упрощенный многочлен
• Полиномы исчезновения подпространства
• Упаковка алгебраической базы
• Обмен кольца SumCheck

! Исследование Bitlayer: Анализ принципов Биниуса СТАРКСА и оптимизационное мышление

4 Итоги

Ценностное предложение Binius заключается в том, чтобы для свидетелей использовать минимальные области power-of-two. В Binius практически полностью устранена узкая горловина обязательств Prover, новой узкой горловиной является протокол Sumcheck.

FRI-Binius решение является вариантом FRI, позволяющим исключить накладные расходы на внедрение из уровня доказательства области, не приводя к резкому увеличению затрат на уровень агрегированных доказательств.

В настоящее время команда Irreducible разрабатывает свой рекурсивный уровень и сотрудничает с командой Polygon для создания zkVM на основе Binius; JoltzkVM переходит с Lasso на Binius; команда Ingonyama реализует FPGA-версию Binius.