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

1. Введение

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

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

Двоичные поля широко применяются в криптографии, такие как AES(F28), GMAC(F2128), QR-код(F28) и др. При использовании меньших полей операции расширения становятся все более важными для обеспечения безопасности. Двоичное поле, используемое Binius, полностью зависит от расширения для обеспечения безопасности и доступности. Большинство расчетов Prover выполняются в базовом поле, что эффективно; случайные проверки точек и вычисления FRI требуют углубления в более широкое расширение для обеспечения безопасности.

Binius инновационное решение:

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

![Bitlayer Research: Анализ принципов Binius STARKs и размышления об их оптимизации])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(

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

Binius = HyperPlonk PIOP + Brakedown PCS + Binary Domain

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

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

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

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

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

128-значная строка может быть интерпретирована гибко:

• Уникальный элемент в 128-битном двоичном поле
• Два элемента 64-битного башенного поля
• Четыре элемента 32-битной башни
• 16 восьмибитных элементов塔域
• 128 элементов в поле F2

![Bitlayer Research: Анализ принципов Binius STARKs и размышления об их оптимизации]###https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp(

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

Ядро проверки механизма Binius:

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

Улучшения Binius для HyperPlonk:

• Оптимизация ProductCheck
• Правильная обработка деления на ноль
• Поддержка перекрестной проверки перестановок (PermutationCheck)

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

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

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

![Bitlayer Research: Анализ принципов Binius STARKs и размышления об их оптимизации]###https://img-cdn.gateio.im/webp-social/moments-a5d031be4711f29ef910057f4e44a118.webp(

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

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

• Высокая эффективность доказательства: обязательство m+n элементов поля
• Нет необходимости в обязательствах по большим таблицам: может обрабатывать очень большие таблицы

Binius вводит мультипликаторную версию протокола Lasso:

• Генерация элемента "память счетчик" с помощью бинарного умножения
• Сторона доказательства обязуется обеспечить безопасность, предоставив ненулевой вектор считывания.

! [Исследование битlayer: анализ принципов Биниуса СТАРКСА и оптимизационное мышление]###https://img-cdn.gateio.im/webp-social/moments-d74bdd8bc21dcfc05e21f9c0074461c3.webp(

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

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

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

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

Малое многочленное обязательство и оценка расширенной области:

• Обещание на малом домене K
• Оценка в более широком диапазоне L/K

Блочная кодировка и коды Рида-Соломона:

• Разрешить малую область ###, такую как F2(, использовать большой алфавит ), такой как F216(, для эффективного обязательства кода Рида-Соломона.

! [Исследование Bitlayer: Анализ принципов Биниуса СТАРКСА и оптимизационное мышление])https://img-cdn.gateio.im/webp-social/moments-7f96976952fd0f8da0e93ff1042a966d.webp(

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

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

) 3.1 PIOP на основе GKR: двоичное умножение по полям на основе GKR

Преобразовать "Проверка A·B =? C" в "Проверка ###gA(B =? gC"

• Нужно всего лишь одно вспомогательное обязательство
• Уменьшить расходы на Sumchecks

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

Оптимизационный метод:

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

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

Улучшенные акценты:

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

![Bitlayer Research: Анализ принципов Binius STARKs и размышления об их оптимизации]###https://img-cdn.gateio.im/webp-social/moments-1db509abaa79939b9e42dcf674a3845a.webp(

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

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

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

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

![Bitlayer Research: Анализ принципов Binius STARKs и размышления об их оптимизации]###https://img-cdn.gateio.im/webp-social/moments-16690fad3bc761b99c40e8e82ab2297c.webp(

4. Итоги

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

• Может использоваться минимальное поле степеней двойки для свидетелей
• Низкое использование памяти для быстрой проверки
• Основное устранение узкого места в обязательстве Prover commit

Новая проблема: Протокол Sumcheck

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

FRI-Binius:

• Устранение накладных расходов на внедрение доказательства области
• Не приводит к резкому увеличению затрат на уровень агрегированного доказательства.

Текущий прогресс:

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

![Bitlayer Research: Анализ принципов Binius STARKs и размышления об их оптимизации])https://img-cdn.gateio.im/webp-social/moments-124ffc8ca976b525ccb8efa8d5ad4af1.webp(