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

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

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

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

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

Например, предположим, что система доказательства требует от вас сгенерировать обязательство к многочлену A, которое должно удовлетворять A^3(x) + x - A(ωx) = x^N(. Это очень распространенный тип доказательства в протоколе ZK-SNARK. Протокол может требовать от вас выбрать случайную координату r и доказать, что A)r( + r - A)ωr( = r^N. Затем, обратным образом, вы получаете A)r( = c, и вы доказываете, что Q = )A - c(/)X - r( является многочленом.

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

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

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

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

! [Новая работа Виталика: исследование круга STARKs])https://img-cdn.gateio.im/webp-social/moments-fdfa1b29fc7f12d9ab7c1ec0449e654c.webp(

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

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

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

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

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

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

При построении 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 — случайный коэффициент.

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

! [Новая работа Виталика: исследование круга STARKs])https://img-cdn.gateio.im/webp-social/moments-cb343bb0791734002ef1a3b813eea1e2.webp(

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

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

Давайте более подробно рассмотрим, что здесь происходит, а также свойства, необходимые для нормальной работы всего этого. На каждом шаге мы уменьшаем степень многочлена вдвое, одновременно сокращая набор точек ), который нас интересует, также вдвое. Первое является ключевым для нормальной работы протокола FRI( Fast Reed-Solomon Interactive). Второе позволяет алгоритму работать очень быстро: поскольку размер каждой итерации уменьшается вдвое по сравнению с предыдущей, общая вычислительная сложность составляет 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 градусов. Этот процесс можно повторять. То есть вы можете многократно применять эту операцию отображения, каждый раз перемещая точки на окружности в их новые позиции.

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

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

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