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

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

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

! Новая работа Виталика: исследование круга 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-битное число. Однако в STARKs с меньшим полем доступно всего около 2 миллиардов значений r, и злоумышленник может попытаться взломать его методом полного перебора.

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

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

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

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

Обычный FRI

При построении SNARK или STARK первым шагом является арифметизация, превращение вычислительной задачи в полиномиальное уравнение. Чтобы доказать, что решение существует, необходимо доказать, что предложенные значения являются разумными полиномами и имеют максимальную степень. Для этого используется техника случайной линейной комбинации, применяемая пошагово:

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 изолирует четные коэффициенты, а C изолирует нечетные коэффициенты. Даны B и C, можно восстановить A. Если степень A < 2^20, степени B и C соответственно равны степени A и степени A-1. D является случайной линейной комбинацией, степень должна быть равна степени A.

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

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

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

Область Mersenne31 подходит для вычислений на 32-битных CPU/GPU. Ее модульные свойства позволяют выполнять многие операции с использованием эффективных битовых операций. В области Mersenne31 арифметические операции быстрее, чем в области BabyBear, примерно в 1,3 раза. Если удастся реализовать 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) это закон удвоения точек.

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

Круговые БПФ

Группировка Circle также поддерживает 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 необходимо использовать различные методы вместо традиционных операций, поскольку нет линейной функции с одним единственным значением. Доказав это, добавляя виртуальную точку, на которую не нужно обращать внимание, через оценку в двух точках.

Если многочлен P равен y1 при x1, и равен y2 при x2, выберите интерполяционную функцию L, равную y1 при x1 и равную y2 при x2: L = ((y2 - y1)/(x2 - x1)) * (x - x1) + y1

Затем докажите, что 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

Исчезающие многочлены могут быть выведены из сворачивающей функции: обычный STARK повторно использует x → x^2, круговой STARK повторно использует x → 2x^2 - 1.

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

В STARKs оценка полиномов обычно выполняется в обратном порядке битов. Например, при n=16: {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}

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

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

Размер 16 обратного порядка: {0, 15, 8, 7, 4, 11, 12, 3, 2, 13, 10, 5, 6, 9, 14, 1}

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

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

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

Ключ к эффективности заключается в полном использовании пространства для отслеживания вычислений. Размер поля Circle STARKs составляет 2^31, что минимизирует desperdicio пространства.

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

Заключение

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

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

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