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

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

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

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

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

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

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

Однако такая случайная выборка на малых полях представляет собой проблему безопасности. Например, поле Mersenne31 имеет только около 2 миллиардов возможных выборочных точек, что осуществимо для решительно настроенного злоумышленника.

Есть два решения:

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

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

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

Обычный FRI

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

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

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

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

Круг ПТ

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

С второго раунда начинается изменение отображения:

f_0(2x^2-1) = (F(x) + F(-x))/2

Это отображение каждый раз уменьшает размер множества точек вдвое.

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

Круговые БПФ

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

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

Торговые операции

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

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

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

В Circle STARKs форма исчезающего многочлена выглядит следующим образом:

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

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

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

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

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

Binius лучше, чем Circle STARKs в некоторых аспектах, но цена это более сложная концепция. В сравнении, Circle STARKs концептуально относительно просты.

Заключение

Circle STARKs не сложнее обычных STARKs для разработчиков. Несмотря на то, что математика, стоящая за этим, довольно сложна, эта сложность хорошо скрыта.

С учетом технологий Mersenne31, BabyBear и Binius, мы, похоже, приближаемся к пределу эффективности базового уровня STARKs. Возможные направления оптимизации в будущем могут включать:

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

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