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

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

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

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

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

Например, доказательная система может требовать генерации обязательства многочлена A, удовлетворяющего уравнению A^3(x) + x - A(ωx) = x^N. Протокол может требовать выбора случайных координат r и доказательства, что A(r) + r - A(ωr) = r^N.

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

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

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

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

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

Регулярная пятница

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

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

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

Круг ПТ

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

Эти точки следуют правилу сложения: (x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1)

Двойная форма: 2*(x,y) = (2x^2 - 1, 2xy)

Отображение Circle FRI изменяется со второго раунда на: f0(2x^2-1) = (F(x) + F(-x))/2

Это отображение каждый раз уменьшает размер множества вдвое, x представляет собой две точки: (x, y) и (x, -y). (x → 2x^2 - 1) является правилом удвоения точек.

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

Круговые БПФ

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

Коэффициенты Circle FFT являются определенной основой: {1, y, x, xy, 2x^2 - 1, 2x^2y - y, 2x^3 - x, ...}

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

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

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

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

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

Исчезающая многочлен в Circle STARK: Z1(x,y) = y Z2(x,y) = x
Zn+1(x,y) = (2 * Zn(x,y)^2) - 1

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

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

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

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

Circle STARKs очень эффективны, вычисления обычно включают:

1. Нативная арифметика бизнес-логики
2. Нативная аритметика криптографии (, такая как хэш Poseidon )
3. Найти параметры

Поля размером 2^31 уменьшают потери пространства. Binius более эффективен в смешивании размеров полей, но концепция более сложная.

! Новая работа Виталика: Exploring Circle STARKs

Заключение

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

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

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