Исследование Circle STARKs

В последние годы тенденция проектирования протоколов STARKs заключается в переходе на использование более мелких полей. В самых ранних реализациях STARKs использовалось 256-битное поле, но такая конструкция была менее эффективной. Чтобы решить эту проблему, STARKs начали использовать более мелкие поля, такие как Goldilocks, Mersenne31 и BabyBear.

Это преобразование значительно увеличило скорость доказательства. Например, Starkware может доказывать 620 000 хешей Poseidon2 в секунду на ноутбуке M3. Это означает, что при доверии к Poseidon2 как хеш-функции можно решить проблему эффективного ZK-EVM.

В данной статье будут рассмотрены принципы работы этих технологий, с особым вниманием на решение Circle STARKs, совместимое с полем Mersenne31.

Часто задаваемые вопросы по использованию небольших полей

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

Чтобы предотвратить атаки, нам нужно выбирать случайные точки только после того, как атакующий предоставит многочлен. В 256-битном поле это очень просто, но в малом поле доступных случайных значений слишком мало, что делает их уязвимыми для полного перебора атакующим.

Существует два решения:

1. Провести несколько случайных проверок
2. Расширенное поле

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

! Новая работа Виталика: исследование круга STARKs

Регулярный FRI

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

FRI проверяет, упрощая задачу доказательства многочлена степени d до задачи доказательства степени d/2. Этот процесс можно повторять несколько раз, каждый раз упрощая задачу вдвое.

Ключом к FRI является использование двухкратного отображения для уменьшения размера набора данных вдвое. Это отображение должно быть способно повторно применяться, пока не останется только одно значение.

! [Новая работа Виталика: Исследуйте круглые СТАРКИ (https://img-cdn.gateio.im/webp-social/moments-b32679a50fc463cfc1c831d30ab2d7e2.webp)

Круг ПТ

Умность Circle STARKs заключается в том, что для простого числа p можно найти группу размером p, обладающую аналогичными свойствами двусторонней связи. Эта группа состоит из точек, удовлетворяющих определенным условиям.

Эти точки следуют аддитивному правилу, аналогичному тригонометрическим функциям или умножению комплексных чисел.

С второго раунда отображение изменяется. Каждое x представляет две точки: (x,y) и (x,-y). (x → 2x^2 - 1) это правило умножения точек.

Круговые БПФ

Группа Circle также поддерживает FFT, способ построения схож с FRI. Однако объектом, обрабатываемым Circle FFT, не являются строго полиномы, а пространство Римана-Роша.

Как разработчику, почти можно игнорировать эти детали. Просто храните полиномы как значения для оценки и используйте БПФ, когда требуется низкая степень расширения.

! Новая работа Виталика: Исследование круга СТАРКОВ

Квотирование

В STARK группы circle, из-за отсутствия однопунктной линейной функции, необходимо использовать различные приемы для замены традиционных коммерческих операций.

Мы доказываем, добавляя виртуальную точку, оценивая в двух точках.

Исчезающие многочлены

В круглом STARK, многочлен исчезновения равен:

Z_1(x,y) = y Z_2(x,y) = х
Z_{n+1}(x,y) = (2 * Z_n(x,y)^2) - 1

Обратный порядок битов

В STARKs полиномиальная оценка обычно располагается в обратном порядке. В Circle STARKs необходимо скорректировать этот порядок, чтобы отразить их особую структуру сворачивания.

Эффективность

Circle STARKs очень эффективны. Ключевое значение имеет полное использование пространства в вычислительном отслеживании для выполнения полезной работы, не оставляя при этом большого количества свободного места.

По сравнению с Binius, концепция Circle STARKs проще, но эффективность немного ниже.

Заключение

Circle STARKs не сложнее обычных STARKs для разработчиков. Понимание Circle FRI и FFTs помогает понять другие специальные FFTs.

Будущая оптимизация STARK может сосредоточиться на:

1. Максимизация эффективности основных криптографических примитивов, таких как хеш-функции
2. Рекурсивная конструкция для повышения параллелизма
3. Арфмизированная виртуальная машина для улучшения опыта разработки