Анализ и оптимизация Binius STARKs

1. Введение

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

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

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

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

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

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

2.1 Артификация на основе башенной двоичной области

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

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

2.2 переработанная версия проверки произведения и перестановки HyperPlonk

Binius заимствовал основную проверочную механику HyperPlonk, включая GateCheck, PermutationCheck, LookupCheck и внес следующие улучшения:

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

2.3 Новая многолинейная сдвиговая теорема

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

2.4 адаптированная версия Lasso поиска доказательства

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

2.5 малый многочленный коммитмент

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

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

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

3.1 GKR-основанный PIOP

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

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

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

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

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

3.3 Sumcheck PIOP оптимизация

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

Оптимизация 3.4 ШТ: FRI-Binius

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

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

4. Итоги

Binius – это совместная проектная схема, использующая "аппаратное обеспечение, программное обеспечение и ускоренный протокол Sumcheck на FPGA", что позволяет быстро доказывать с очень низким потреблением памяти. В Binius практически полностью устранена узкая связь с коммитом Prover, новая узкая связь связана с протоколом Sumcheck, и это можно эффективно решить с помощью специализированного оборудования.

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

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