В последние годы тенденция проектирования протоколов STARKs заключается в переходе на использование меньших полей. В самых ранних реализациях STARKs использовалось 256-битное поле, то есть для больших чисел выполнялись операции по модулю. Однако такая эффективность низка, обработка больших чисел будет тратить много вычислительной мощности. Чтобы решить эту проблему, STARKs начали использовать более мелкие поля: сначала Goldilocks, затем Mersenne31 и BabyBear.
Это преобразование значительно увеличивает скорость доказательства. Например, Starkware теперь может доказывать 620,000 хешей Poseidon2 в секунду на ноутбуке M3. Это означает, что если мы доверяем Poseidon2 в качестве хеш-функции, мы можем решить задачу эффективной разработки ZK-EVM. Как работают эти технологии? Как строятся доказательства на малых полях? В этой статье будут рассмотрены эти детали, с особым вниманием к Circle STARKs, совместимым с полем Mersenne31.
Общие вопросы при использовании малых полей
При создании доказательства на основе хэширования важным приемом является косвенная проверка свойств многочлена через оценку многочлена в случайных точках. Это может значительно упростить процесс доказательства.
Например, предположим, что протокол требует от вас сгенерировать коммитмент многочлена A, удовлетворяющий A^3(x) + x - A(ωx) = x^N. Протокол может требовать, чтобы вы выбрали случайные координаты r и доказали, что A(r)^3 + r - A(ωr) = r^N. Затем вы можете вывести A(r) = c, и вы докажете, что Q = (A - c)/(X - r) является многочленом.
Чтобы предотвратить атаку, нам нужно выбрать r после того, как атакующий предоставит A. В протоколах на основе эллиптических кривых это просто: мы можем выбрать случайное 256-битное число в качестве r. Но в малых полях STARKs доступно всего около 2 миллиардов вариантов r, и атакующий может взломать их методом перебора.
Эту проблему можно решить двумя способами:
Провести несколько случайных проверок
Расширенное поле
Множественные случайные проверки просты и эффективны, но могут возникнуть проблемы с эффективностью. Расширенное поле похоже на множественное, но основано на конечном поле. Мы вводим новое значение α, утверждая, что α^2=некоторое значение. Таким образом создается новая математическая структура, позволяющая выполнять более сложные вычисления в конечном поле.
Расширяя область, мы получили достаточно значений для выбора, чтобы удовлетворить требования безопасности. Большинство математических операций по-прежнему выполняется в базовом поле, только при необходимости повышения безопасности используются более крупные поля.
FRI (Fast Reed-Solomon Interactive) протокол является важным шагом в построении SNARK или STARK. Он упрощает процесс верификации, сводя задачу доказательства многочлена степени d к задаче доказательства многочлена степени d/2. Этот процесс можно повторять несколько раз, каждый раз упрощая задачу вдвое.
Принцип работы FRI заключается в повторении процесса упрощения. Начинается с доказательства того, что многочлен имеет степень d, и через серию шагов в конечном итоге доказывается, что степень равна d/2. После каждого упрощения степень получаемого многочлена постепенно уменьшается. Если на каком-то этапе выходные данные не соответствуют ожиданиям, то этот раунд проверки потерпит неудачу.
Для поэтапного уменьшения области использовалось двоичное отображение. Это отображение позволяет уменьшить размер набора данных вдвое, одновременно сохраняя те же свойства. Эту операцию можно представить как процесс, при котором отрезок на окружности растягивается по окружности на два круга.
Чтобы сделать технологию отображения эффективной, размер исходной мультипликативной подсгруппы должен иметь большой фактор степени 2. Модуль BabyBear позволяет его максимальной мультипликативной подсгруппе содержать все ненулевые значения, что очень подходит для этой технологии. Размер мультипликативной подсгруппы Mersenne31 имеет только один фактор степени 2, что ограничивает его область применения.
Поле Mersenne31 идеально подходит для арифметических операций на 32-битных ЦПУ/ГПУ, примерно в 1,3 раза быстрее, чем поле BabyBear. Если удастся реализовать FRI в поле Mersenne31, это значительно повысит вычислительную эффективность.
! [Новая работа Виталика: Исследуйте круглые СТАРКИ (https://img-cdn.gateio.im/webp-social/moments-b32679a50fc463cfc1c831d30ab2d7e2.webp)
Круг ПТ
Умелость Circle STARKs заключается в том, что, задано простое число p, можно найти группу размером p, обладающую аналогичными свойствами отношения «один к одному». Эта группа состоит из точек, удовлетворяющих определённым условиям, таким как множество точек, для которых x^2 mod p равно некоторому значению.
Сначала Circle FRI сводит все точки на одну прямую, затем выполняет случайную линейную комбинацию, чтобы получить одномерный многочлен P(x). Начиная со второго раунда, отображение становится: f0(2x^2-1) = (F(x) + F(-x))/2
Это отображение каждый раз уменьшает размер множества вдвое, преобразуя x-координаты двух противоположных точек на круге в x-координаты точек после увеличения. Это можно было бы сделать в двумерном пространстве, но одномерные операции более эффективны.
Circle group также поддерживает FFT, способ построения схож с FRI. Объектом обработки Circle FFT является пространство Римана-Роша, а не строгие многочлены. Коэффициенты, выходящие из Circle FFT, специфичны для основы Circle FFT.
Как разработчик, вы почти можете полностью игнорировать этот момент. STARKs просто хранят многочлены как наборы значений для оценки. Единственное место, где требуется FFT, это для выполнения низкой степени расширения: дано N значений, создаются k*N значений на одном и том же многочлене.
В Circle STARKs, поскольку нет линейной функции, которую можно использовать через одну точку, необходимо применять различные техники вместо традиционных коммерческих операций. Мы вынуждены доказывать, добавляя виртуальную точку, оценку в двух точках.
Если многочлен P равен y1 в x1 и y2 в x2, мы выбираем интерполяционную функцию L, которая равна этим двум точкам. Затем докажем, что P-L равен нулю в этих двух точках, доказав, что частное Q, полученное делением L на L, является многочленом.
Исчезающие многочлены
В Circle STARKs исчезающие многочлены равны:
Z1(x,y) = y
Z2(x,y) = x
Zn+1(x,y) = (2 * Zn(x,y)^2) - 1
Это можно вывести из сворачивающей функции: в Circle STARKs повторно используется x → 2x^2 - 1. Первый раунд требует специальной обработки.
Обратить порядок битов
Circle STARKs используют измененный обратный порядок бит, переворачивая все биты, кроме последнего, и используя последний бит для определения, следует ли перевернуть другие биты. Это отражает уникальную структуру сворачивания Circle STARKs.
Эффективность
Circle STARKs очень эффективны. Вычисления обычно включают:
Нативная арифметика: используется для бизнес-логики
Нативная арифметика: используется в криптографии (, например, хэш Poseidon )
Поиск параметров: выполнение различных расчетов с помощью таблицы значений
Круговые STARKs максимально используют вычислительное пространство, тратят меньше. Немного уступают Binius, но концепция проще.
Вывод
Circle STARKs не сложнее обычных STARKs для разработчиков. Понимание Circle FRI и FFT может помочь в понимании других специальных FFT. В настоящее время эффективность базового уровня STARKs близка к пределу, возможные направления оптимизации в будущем могут включать:
Максимизация арифметической эффективности хэш-функций и подписей
Рекурсивная конструкция для повышения параллелизма
Арифметическая виртуальная машина для улучшения опыта разработки
На этой странице может содержаться сторонний контент, который предоставляется исключительно в информационных целях (не в качестве заявлений/гарантий) и не должен рассматриваться как поддержка взглядов компании Gate или как финансовый или профессиональный совет. Подробности смотрите в разделе «Отказ от ответственности» .
19 Лайков
Награда
19
4
Репост
Поделиться
комментарий
0/400
NftBankruptcyClub
· 08-09 22:10
Шрифт стал меньше, но эффективность, наоборот, возросла...666
Посмотреть ОригиналОтветить0
GasWhisperer
· 08-09 22:08
хмм... меньшие поля = более быстрые доказательства, но можем ли мы доверять poseidon2? если честно, я испытываю противоречивые чувства по поводу этого компромисса между эффективностью и безопасностью.
Посмотреть ОригиналОтветить0
alpha_leaker
· 08-09 21:58
Старк немного пугает.
Посмотреть ОригиналОтветить0
ChainDetective
· 08-09 21:54
Только что понял, в основном это сокращенный объем для быстрого расчета.
Circle STARKs: Исследование и прорыв в области эффективных ZK-доказательств с малым полем
Исследование Circle STARKs
В последние годы тенденция проектирования протоколов STARKs заключается в переходе на использование меньших полей. В самых ранних реализациях STARKs использовалось 256-битное поле, то есть для больших чисел выполнялись операции по модулю. Однако такая эффективность низка, обработка больших чисел будет тратить много вычислительной мощности. Чтобы решить эту проблему, STARKs начали использовать более мелкие поля: сначала Goldilocks, затем Mersenne31 и BabyBear.
Это преобразование значительно увеличивает скорость доказательства. Например, Starkware теперь может доказывать 620,000 хешей Poseidon2 в секунду на ноутбуке M3. Это означает, что если мы доверяем Poseidon2 в качестве хеш-функции, мы можем решить задачу эффективной разработки ZK-EVM. Как работают эти технологии? Как строятся доказательства на малых полях? В этой статье будут рассмотрены эти детали, с особым вниманием к Circle STARKs, совместимым с полем Mersenne31.
Общие вопросы при использовании малых полей
При создании доказательства на основе хэширования важным приемом является косвенная проверка свойств многочлена через оценку многочлена в случайных точках. Это может значительно упростить процесс доказательства.
Например, предположим, что протокол требует от вас сгенерировать коммитмент многочлена A, удовлетворяющий A^3(x) + x - A(ωx) = x^N. Протокол может требовать, чтобы вы выбрали случайные координаты r и доказали, что A(r)^3 + r - A(ωr) = r^N. Затем вы можете вывести A(r) = c, и вы докажете, что Q = (A - c)/(X - r) является многочленом.
Чтобы предотвратить атаку, нам нужно выбрать r после того, как атакующий предоставит A. В протоколах на основе эллиптических кривых это просто: мы можем выбрать случайное 256-битное число в качестве r. Но в малых полях STARKs доступно всего около 2 миллиардов вариантов r, и атакующий может взломать их методом перебора.
Эту проблему можно решить двумя способами:
Множественные случайные проверки просты и эффективны, но могут возникнуть проблемы с эффективностью. Расширенное поле похоже на множественное, но основано на конечном поле. Мы вводим новое значение α, утверждая, что α^2=некоторое значение. Таким образом создается новая математическая структура, позволяющая выполнять более сложные вычисления в конечном поле.
Расширяя область, мы получили достаточно значений для выбора, чтобы удовлетворить требования безопасности. Большинство математических операций по-прежнему выполняется в базовом поле, только при необходимости повышения безопасности используются более крупные поля.
! Новая работа Виталика: исследование круга STARKs
Регулярное FRI
FRI (Fast Reed-Solomon Interactive) протокол является важным шагом в построении SNARK или STARK. Он упрощает процесс верификации, сводя задачу доказательства многочлена степени d к задаче доказательства многочлена степени d/2. Этот процесс можно повторять несколько раз, каждый раз упрощая задачу вдвое.
Принцип работы FRI заключается в повторении процесса упрощения. Начинается с доказательства того, что многочлен имеет степень d, и через серию шагов в конечном итоге доказывается, что степень равна d/2. После каждого упрощения степень получаемого многочлена постепенно уменьшается. Если на каком-то этапе выходные данные не соответствуют ожиданиям, то этот раунд проверки потерпит неудачу.
Для поэтапного уменьшения области использовалось двоичное отображение. Это отображение позволяет уменьшить размер набора данных вдвое, одновременно сохраняя те же свойства. Эту операцию можно представить как процесс, при котором отрезок на окружности растягивается по окружности на два круга.
Чтобы сделать технологию отображения эффективной, размер исходной мультипликативной подсгруппы должен иметь большой фактор степени 2. Модуль BabyBear позволяет его максимальной мультипликативной подсгруппе содержать все ненулевые значения, что очень подходит для этой технологии. Размер мультипликативной подсгруппы Mersenne31 имеет только один фактор степени 2, что ограничивает его область применения.
Поле Mersenne31 идеально подходит для арифметических операций на 32-битных ЦПУ/ГПУ, примерно в 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)
Сначала Circle FRI сводит все точки на одну прямую, затем выполняет случайную линейную комбинацию, чтобы получить одномерный многочлен P(x). Начиная со второго раунда, отображение становится: f0(2x^2-1) = (F(x) + F(-x))/2
Это отображение каждый раз уменьшает размер множества вдвое, преобразуя x-координаты двух противоположных точек на круге в x-координаты точек после увеличения. Это можно было бы сделать в двумерном пространстве, но одномерные операции более эффективны.
! Новая работа Виталика: исследование круга STARKs
Круговые БПФ
Circle group также поддерживает FFT, способ построения схож с FRI. Объектом обработки Circle FFT является пространство Римана-Роша, а не строгие многочлены. Коэффициенты, выходящие из Circle FFT, специфичны для основы Circle FFT.
Как разработчик, вы почти можете полностью игнорировать этот момент. STARKs просто хранят многочлены как наборы значений для оценки. Единственное место, где требуется FFT, это для выполнения низкой степени расширения: дано N значений, создаются k*N значений на одном и том же многочлене.
! Новая работа Виталика: Исследование круга СТАРКОВ
Квотирование
В Circle STARKs, поскольку нет линейной функции, которую можно использовать через одну точку, необходимо применять различные техники вместо традиционных коммерческих операций. Мы вынуждены доказывать, добавляя виртуальную точку, оценку в двух точках.
Если многочлен P равен y1 в x1 и y2 в x2, мы выбираем интерполяционную функцию L, которая равна этим двум точкам. Затем докажем, что P-L равен нулю в этих двух точках, доказав, что частное Q, полученное делением L на L, является многочленом.
Исчезающие многочлены
В Circle STARKs исчезающие многочлены равны: Z1(x,y) = y Z2(x,y) = x Zn+1(x,y) = (2 * Zn(x,y)^2) - 1
Это можно вывести из сворачивающей функции: в Circle STARKs повторно используется x → 2x^2 - 1. Первый раунд требует специальной обработки.
Обратить порядок битов
Circle STARKs используют измененный обратный порядок бит, переворачивая все биты, кроме последнего, и используя последний бит для определения, следует ли перевернуть другие биты. Это отражает уникальную структуру сворачивания Circle STARKs.
Эффективность
Circle STARKs очень эффективны. Вычисления обычно включают:
Круговые STARKs максимально используют вычислительное пространство, тратят меньше. Немного уступают Binius, но концепция проще.
Вывод
Circle STARKs не сложнее обычных STARKs для разработчиков. Понимание Circle FRI и FFT может помочь в понимании других специальных FFT. В настоящее время эффективность базового уровня STARKs близка к пределу, возможные направления оптимизации в будущем могут включать:
! Новое творение Виталика: исследование круга STARKs