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

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

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

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

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

Общие вопросы по использованию малых полей

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

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

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

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

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

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

Круг ПТ

Умение 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 сводит все точки к одной прямой, а затем выполняет случайную линейную комбинацию, получая одномерный многочлен P(x).

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

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

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

Круговые БПФ

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

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

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

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

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

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

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

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

В круге 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. Нативная арифметика для шифрования
3. Найти параметры

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

Заключение

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

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

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