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

1 Введение

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

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

Двоичные поля широко используются в криптографии,典型例子包括:

• Стандарт высокоуровневого шифрования ( AES ), основанный на поле F28
• Galois сообщение аутентификации ( GMAC ), основанное на поле F2128
• QR-код, использующий кодирование Рида-Соломона на основе F28
• Исходные протоколы FRI и zk-STARK, а также хеш-функция Grøstl, вышедшая в финал SHA-3

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

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

• Использовать многовариантные (в частности, многолинейные) многочлены вместо одновариантных многочленов, чтобы представить всю вычислительную траекторию через их значения на "гиперкубе".
• Рассматривать гиперкуб как квадрат, основываясь на этом квадрате для расширения Рида-Соломона

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

2 Принципиальный анализ

Binius = HyperPlonk PIOP + Brakedown PCS + Binary Domain

Binius включает пять ключевых технологий:

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

2.1 Конечные поля: арифметика на основе башен двоичных полей

Преимущества башенной двоичной области:

• Высокоэффективные вычисления: Бинарное поле по своей сути поддерживает высокоэффективные арифметические операции
• Эффективная арифметизация: структура двоичного поля поддерживает упрощенный процесс арифметизации
• Гибкое представление: одна и та же строка может быть интерпретирована несколькими способами в контексте двоичного поля
• Не требуется сокращение: бинарная область не требует переноса при операциях сложения и умножения.
• Эффективные квадратные вычисления:(X + Y)2 = X2 + Y2

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

Механизм проверки ядра:

1. Проверка ворот
2. Проверка перестановок
3. LookupCheck
4. МультисетЧек
5. Проверка продукта
6. Нузерчек
7. Суммчек
8. Пакетная проверка

По сравнению с улучшениями HyperPlonk:

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

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

Ключевые методы:

• Упаковка: оптимизация операции путем упаковки меньших элементов, находящихся на соседних позициях в лексикографическом порядке, в более крупные элементы.
• Операторы сдвига: перестановка элементов внутри блока с циклическим сдвигом на заданное смещение

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

Преимущества протокола Lasso:

• Эффективное доказательство: для m поисков в таблице размером n требуется всего лишь пообещать m+n элементов поля
• Не требуется обязательство по большой таблице: если таблица t структурирована, нет необходимости в обязательстве, можно обрабатывать очень большие таблицы.

Состав протокола Lasso:

• Виртуальное полиномиальное абстрагирование больших таблиц
• Поиск по малой таблице
• Многосетевое обследование

Адаптация Binius к Lasso:

• Внедрение версии Lasso протокола с умножением
• Требуется, чтобы сторона, предоставляющая доказательства, обязалась на вектор счётчика чтения, который ненулевой везде.

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

Основная идея: упаковка

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

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

Основные технологии:

• Малые многочленные обязательства и оценка расширенной области
• Универсальная конструкция малой области
• Блочная кодировка и код Рида-Соломона

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

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

1. PIOP на основе GKR: для двоичных операций умножения
2. Оптимизация ZeroCheck PIOP: балансировка вычислительных затрат между Prover и Verifier
3. Оптимизация Sumcheck PIOP: протокол Sumcheck на основе малых полей
4. Оптимизация PCS: FRI-Binius снижает размер доказательства Binius

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

Основная идея:

Проверить, удовлетворяют ли два 32-битных целых числа A и B условию A·B =? C Преобразовать в
"Проверка (gA)B =? gC на выполнение"

Преимущества:

• Нужно всего лишь одно вспомогательное обещание
• Сокращение расходов на Sumchecks

3.2 Оптимизация PIOP в ZeroCheck

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

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

3.3 Суммирование PIOP оптимизация

Улучшение акцентов:

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

Конкретные результаты:

• В случае, когда базовое поле равно GF[2], производительность алгоритма 4 превышает производительность наивного алгоритма почти в 30 раз.
• Алгоритму 4 требуется всего 0,26 МБ памяти, в то время как алгоритму 3 требуется 67 МБ.

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

Четыре инновационных момента:

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

Эффективность: Уменьшите размер доказательства Binius на один порядок

4 Итоги

Преимущества Binius:

• Может использовать минимальные поля степени двойки для свидетелей
• Низкое использование памяти, быстрая проверка
• Практически полностью устранена瓶颈 обязательств Prover.

Решение FRI-Binius: Устранение накладных расходов на внедрение из уровня доказательства домена без резкого увеличения затрат на уровень агрегированного доказательства.

Последние новости:

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