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

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

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

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

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

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

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

Эта проблема имеет два решения:

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

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

Это приводит к другому решению: расширенные поля, расширенные поля похожи на множества, но они основаны на конечных полях. Мы вводим новое значение, обозначаемое как α, и утверждаем, что оно удовлетворяет некоторым отношениям, например, α2=некоторое значение. Таким образом, мы создаем новую математическую структуру, способную выполнять более сложные операции в конечных полях. В этом расширенном поле умножение становится умножением с использованием нового значения α. Теперь мы можем оперировать парами значений в расширенном поле, а не только отдельными числами. Например, если мы работаем в полях, таких как Mersenne или BabyBear, такое расширение позволяет нам иметь большее количество вариантов значений, что повышает безопасность. Чтобы дальше увеличить размер поля, мы можем повторно применять ту же технику. Поскольку мы уже использовали α, нам нужно определить новое значение, что в Mersenne31 проявляется в выборе α так, чтобы α2=некоторое значение.

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

С помощью расширенной области у нас теперь есть достаточно значений для выбора, чтобы удовлетворить наши потребности в безопасности. Если обрабатывать многочлены степени меньше d, то на каждом раунде можно обеспечить безопасность на уровне 104 бит. Это означает, что у нас есть достаточная защита. Если необходимо достичь более высокого уровня безопасности, например, 128 бит, мы можем добавить в протокол дополнительные вычислительные работы для повышения безопасности.

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

Регулярная ПЯ

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

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

• Предположим, у вас есть значение оценки многочлена A, и вы хотите доказать, что его степень меньше 2^20
• Рассматриваем многочлен B(x^2) = A(x) + A(-x), C(x^2) = (A(x) - A(-x))/x
• D является случайной линейной комбинацией B и C, то есть D=B+rC, где r является случайным коэффициентом.

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

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

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

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

Чтобы достичь постепенного уменьшения области, используется отображение два в одно, то есть каждая точка отображается в одну из двух точек. Это отображение позволяет нам уменьшить размер набора данных вдвое. Одним из важных преимуществ этого отображения два в одно является его повторяемость. То есть, когда мы применяем это отображение, полученный результирующий набор по-прежнему сохраняет те же свойства. Предположим, что мы начинаем с мультипликативной подсгруппы. Эта подсгруппа представляет собой множество S, в котором каждый элемент x имеет свой множитель 2x, также находящийся в множестве. Если мы применим операцию возведения в квадрат к множеству S (то есть отобразим каждый элемент x из множества в x^2), новое множество S^2 также будет сохранять те же свойства. Эта операция позволяет нам продолжать уменьшать размер набора данных, пока в конечном итоге не останется только одно значение. Хотя теоретически мы можем уменьшить набор данных до одного единственного значения, на практике обычно останавливаются до достижения меньшего множества.

Вы можете представить эту операцию как процесс, при котором линия (например, отрезок или дуга) на окружности растягивается вдоль окружности, заставляя её вращаться на два оборота. Например, если точка находится на окружности в позиции x градусов, то после этой операции она переместится в позицию 2x градусов. Каждая точка на окружности от 0 до 179 градусов имеет соответствующую точку в позиции от 180 до 359 градусов, и эти две точки совпадают. Это означает, что когда вы отображаете точку с x градусов на 2x градусов, она совпадет с точкой, находящейся в позиции x+180 градусов. Этот процесс можно повторять. То есть вы можете многократно применять эту операцию отображения, каждый раз перемещая точки на окружности в их новые позиции.

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

Чтобы сделать технику отображения эффективной, размер исходной мультипликативной подсистемы должен иметь большой множитель степени 2. BabyBear - это система с определенным модулем, модуль которого равен некоторому значению, что позволяет максимальной мультипликативной подсистеме содержать все ненулевые значения, поэтому размер подсистемы равен 2k−1 (где k - это количество бит в модуле). Подсистема такого размера очень подходит для вышеупомянутой техники, поскольку она позволяет эффективно уменьшать степень многочлена путем многократного применения операций отображения. В BabyBear вы можете выбрать подсистему размером 2^k (или использовать весь набор) и затем применить метод FRI, чтобы постепенно уменьшить степень многочлена до 15 и в конце проверить степень многочлена. Этот метод использует свойства модуля и размер мультипликативной подсистемы, что делает вычислительный процесс очень эффективным. Mersenne31 - это еще одна система, модуль которой равен некоторому значению, что делает размер мультипликативной подсистемы равным 2^31 - 1. В этом случае размер мультипликативной подсистемы имеет только один множитель степени 2, что позволяет делить его только на 2 один раз. Дальнейшая обработка больше не применима к вышеупомянутой технике, то есть невозможно использовать FFT для эффективного уменьшения степени многочлена, как в BabyBear.

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