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

1. Введение

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

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

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

Binius предложил инновационное решение: во-первых, использовать многомерные (а именно, многолинейные) многочлены вместо однородных многочленов, представляя всю вычислительную траекторию через их значения на "гиперкубе"; во-вторых, рассматривать гиперквадрат как квадрат и проводить расширение Рида-Соломона на основе этого квадрата. Этот метод значительно повышает эффективность кодирования и вычислительную производительность при обеспечении безопасности.

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

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

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

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

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

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

Binius использует ряд основных механизмов проверки, включая GateCheck, PermutationCheck, LookupCheck, MultisetCheck, ProductCheck, ZeroCheck, SumCheck и BatchCheck.

По сравнению с HyperPlonk, Binius улучшил следующие аспекты:

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

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

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

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

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

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

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

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

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

Binius многочленное обязательство в основном использует:

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

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

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

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

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

3.2 ZeroCheck PIOP оптимизация: баланс затрат на вычисления Prover и Verifier

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

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

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

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

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

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

4. Резюме

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

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