Исследование 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. Затем следует обратное преобразование A(r) = c, и доказательство Q = (A - c)/(X - r) является многочленом.

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

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

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

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

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

Обычный FRI

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

1. Предположим, что есть значение оценки многочлена A, нужно доказать, что степень < 2^20
2. Рассмотрим B(x^2) = A(x) + A(-x), C(x^2) = (A(x) - A(-x))/x
3. D является случайной линейной комбинацией B и C: D=B+rC

B изолирует четные коэффициенты A, C изолирует нечетные коэффициенты. Дано B и C можно восстановить A: A(x) = B(x^2) + xC(x^2). Если степень A < 2^20, степени B и C соответственно равны степени A и степени A - 1. D как случайная комбинация, степень должна быть равна степени A.

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

FRI на каждом шаге уменьшает степень полинома и размер множества точек вдвое. Первое является ключевым для работы FRI, а второе делает алгоритм очень быстрым: общая вычислительная сложность составляет O(N), а не O(N*log(N)).

Для достижения постепенного уменьшения области используется двустороннее отображение. Это отображение позволяет уменьшить размер набора данных вдвое и является повторяемым. Начинается с мультипликативной подгруппы, где каждый элемент x также имеет двойное значение 2x в наборе. Квадрат набора S, новый набор S^2, сохраняет те же свойства. Это позволяет непрерывно уменьшать размер набора данных до тех пор, пока не останется только одно значение.

Модуль BabyBear позволяет его максимальной мультипликативной подсистеме включать все ненулевые значения, размером 2^k-1. Это очень подходит для указанной технологии, так как с помощью многократного отображения можно эффективно уменьшить степень многочлена. Размер мультипликативной подсистемы Mersenne31 составляет 2^31-1, и он может быть делим только на 2 один раз, после чего эту технологию использовать невозможно.

Поле Mersenne31 идеально подходит для вычислений на 32-битных CPU/GPU. Его модульные свойства (, такие как 2^31-1), позволяют многим операциям использовать эффективные побитовые операции: результаты, превышающие модуль, могут быть уменьшены с помощью сдвига. Умножение может быть эффективно обработано с использованием специализированных команд CPU. Арифметические операции Mersenne31 примерно в 1,3 раза быстрее, чем у BabyBear. Если FRI удастся реализовать в Mersenne31, это значительно повысит эффективность.

! [Новая работа Виталика: Исследуйте круглые СТАРКИ (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)

Мы сосредоточены на точках на нечетных позициях круга. Сначала сводим все точки к одной прямой: f0(x) = (F(x,y) + F(x,- y))/2

Затем выполняется случайная линейная комбинация, получая одномерный многочлен P(x).

С начала второго раунда маппинг изменяется на: f0(2x^2-1) = (F(x) + F(-x))/2

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

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

Круговые БПФ

Circle group также поддерживает FFT, метод конструкции аналогичен FRI. Ключевое отличие заключается в том, что Circle FFT обрабатывает не строгие многочлены, а пространство Римана-Роша: многочлен по кругу (x^2 + y^2 - 1 = 0).

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

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

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

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

STARK часто выполняет операции деления на определенные точки. Например, доказательство P(x)=y можно осуществить следующими шагами:

1. Вычисление коэффициента: Q = (P - y)/(X - x)
2. Докажите, что Q является многочленом, а не дробью.

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

Если P в x1 равно y1, а в x2 равно y2, мы выбираем интерполяционную функцию L, которая равна в этих двух точках. Затем докажем, что P-L в этих двух точках равно нулю, доказав, что частное Q, полученное делением L на L, является многочленом.

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

Многочленное уравнение, которое пытается доказать STARK, обычно имеет вид C(P(x), P(next(x))) = Z(x) · H(x), Z(x) равно нулю в исходной области оценки.

В круглом STARK соответствующая функция: Z1(x,y) = y Z2(x,y) = x Zn+1(x,y) = (2 * Zn(x,y)^2) - 1

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

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

Оценка многочленов в STARKs обычно выполняется в обратном порядке. В circle STARKs структура сворачивания немного отличается:

• Шаг первый: (x,y) и (x,-y) парные
• Второй шаг: x паруется с -x
• Последующие шаги: сопоставление p и q, чтобы Q^i(p) = -Q^i(q)

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

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

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

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

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

Ключ к эффективности заключается в полном использовании вычислительного отслеживания пространства. Здесь размер поля составляет 2^31, поэтому потери пространства незначительны. Хеши, такие как Poseidon, полностью используют каждую цифру в каждом поле.

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

Заключение

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

Понимание Circle FRI и FFT может стать путем к пониманию других специальных FFT, таких как FFT в двоичных полях и FFT на эллиптических кривых.

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

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

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