Анализ принципов Binius STARKs и размышления об их оптимизации

1. Введение

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

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

Binius использует следующие ключевые технологии:

• Артикуляция на основе башенной двоичной области
• Улучшенная версия проверки произведений и перестановок HyperPlonk
• Новая многолинейная смещенная демонстрация
• Улучшенная версия доказательства поиска Lasso
• Малые многочленные обязательства

! Исследование битlayer: анализ принципов и оптимизационное мышление Binius STARKs

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

2.1 Артикуляция на основе башен бинарных полей

Башенная двоичная область поддерживает высокоэффективные арифметические операции, что является ключом к реализации быстрого проверяемого вычисления. Ее преимущества включают:

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

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

Binius улучшил HyperPlonk в следующих аспектах:

• Оптимизация ProductCheck: значение специализировано на 1, упрощение процесса проверки
• Обработка деления на ноль: даже если знаменатель равен нулю, обработка может продолжаться.
• Перекрестная проверка перестановок: поддержка проверки перестановок между несколькими колонками

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

Binius ввел два ключевых метода:

• Упаковка: Оптимизация операций путем упаковки соседних элементов
• Оператор сдвига: перестановка элементов в блоке на основе заданного смещения

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

Binius адаптировал Lasso для операций с двоичными полями, введя версию протокола Lasso для умножения. Доказатель должен заверить вектор счётчиков чтения, который всегда не равен нулю, чтобы обеспечить безопасность протокола.

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

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

Binius предлагает две схемы обещаний многочленов Brakedown, основанные на двоичных областях:

• Использовать экземпляр concatenated code
• Использует технологию кодирования на уровне блоков, поддерживает отдельное использование кодов Рида-Соломона

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

3.1 PIOP на основе GKR

Умножение в двоичной области на основе GKR требует только одного вспомогательного обязательства, повышая эффективность за счет сокращения затрат на Sumchecks.

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

Предложено несколько оптимизационных решений путем регулирования распределения рабочей нагрузки между доказательной стороной и проверяющей стороной:

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

3.3 Проверка суммы оптимизации PIOP

Ingonyama предложил улучшение протокола Sumcheck, основанного на малых областях:

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

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

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

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

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

4. Резюме

Binius устранил узкое место в коммитментах Prover, новое узкое место связано с протоколом Sumcheck. Решение FRI-Binius является вариантом FRI и может устранить накладные расходы на внедрение в слой доменных доказательств. В настоящее время несколько команд разрабатывают приложения, связанные с Binius.