В последние годы тенденция в проектировании протоколов STARKs заключается в переходе на использование более мелких полей. Первые реализации STARKs использовали поля размером 256 бит, что делало эти протоколы совместимыми с подписями на основе эллиптических кривых. Однако такая конструкция имеет низкую эффективность, и обработка больших чисел требует много вычислительных ресурсов. Чтобы решить эту проблему, STARKs начали переходить на использование более мелких полей: сначала Goldilocks, затем Mersenne31 и BabyBear.
Это преобразование значительно увеличивает скорость доказательства. Например, Starkware может доказывать 620 000 хешей Poseidon2 в секунду на ноутбуке M3. Это означает, что если доверять Poseidon2 как хеш-функции, то можно решить проблему эффективного ZK-EVM. Как работают эти технологии? Как создать доказательства в малых полях? В этой статье будут исследованы эти детали, с особым вниманием к решению Circle 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-битное число в качестве r. Но в малом поле STARKs доступно только около 2 миллиардов вариантов r, и злоумышленник может попробовать все возможные.
Эта проблема имеет два решения:
Провести несколько случайных проверок
Расширенное поле
Множественные случайные проверки просты и эффективны, но имеют проблемы с эффективностью. Расширенные поля аналогичны множествам, но основаны на конечном поле. Вводится новое значение α, удовлетворяющее α^2=определенному значению, создавая новую математическую структуру. Это позволяет нам иметь больше значений на выбор, повышая безопасность.
Первый шаг FRI-протокола обычно заключается в арифметизации, преобразовании вычислительной задачи в уравнение P(X,Y,Z)=0, где P является многочленом, а X, Y, Z — параметрами. Решение уравнения соответствует решению исходной задачи.
Чтобы доказать правильность решения, необходимо доказать, что предложенное значение является разумным многочленом и имеет максимальную степень. Используя технику случайной линейной комбинации:
Предположим, что есть значение оценки многочлена A, необходимо доказать, что его степень < 2^20
D является случайной линейной комбинацией B и C: D = B + rC
По сути, B изолирует четные коэффициенты, а C изолирует нечетные коэффициенты. B и C могут восстановить A. Если степень A < 2^20, степени B и C соответственно равны степени A и степени A - 1. D как случайная комбинация, ее степень должна быть равна степени A.
FRI повторяет этот процесс упрощения, каждый раз упрощая проблему вдвое. Этот дизайн эффективно обнаруживает некорректный ввод.
! [Новая работа Виталика: Исследуйте круглые СТАРКИ (https://img-cdn.gateio.im/webp-social/moments-b32679a50fc463cfc1c831d30ab2d7e2.webp)
Круг ПТ
Вот в чем заключается хитрость Circle STARKs. Для данного простого числа p можно найти группу размером p с подобным свойству «два к одному». Эта группа состоит из точек, которые соответствуют определенным условиям, таким как набор точек, для которых x^2 mod p равно определенному значению.
Мы сосредоточены на точках на нечетных позициях окружности, сводя все точки к одной прямой:
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) — это правило удвоения точек.
Группы Circle также поддерживают FFT, способ построения аналогичен FRI. Однако Circle FFT обрабатывает объекты пространства Римана-Роша, а не строгие многочлены.
Как разработчик, можно в значительной степени игнорировать этот момент. STARKs просто требуют хранения многочлена в виде набора оценочных значений. FFT в основном используется для низкой степени расширения: заданное N значений, генерирует k*N значений на одном и том же многочлене.
В Circle STARKs, из-за отсутствия одноприводной линейной функции, необходимо использовать различные приемы вместо традиционных операций умножения. Доказывается через оценку в двух точках, добавляя виртуальную точку.
Если многочлен P равен y1 при x1 и y2 при x2, выберите интерполяционную функцию L, которая равна в этих двух точках. Затем докажите, что P - L равно нулю в обеих точках, и, разделив L, получаем частное Q, которое является многочленом.
Многочлен исчезновения в Circle STARKs:
Z1(x,y) = y
Z2(x,y) = x
Zn+1(x,y) = (2 * Zn(x,y)^2) - 1
Это можно вывести из сворачивающей функции: повторное использование x → 2x^2 - 1.
Обратный порядок битов
Необходима корректировка обратного порядка битов в Circle STARKs: инвертировать каждый бит, кроме последнего, и использовать последний бит для определения, следует ли инвертировать другие биты.
Circle STARKs очень эффективны. Вычисления обычно включают:
Нативная арифметика бизнес-логики
Нативная арифметика криптографии
Поиск параметров
Ключ к эффективности заключается в полном использовании вычислительного отслеживания пространства. 31-битное поле цифр снижает потери. Binius комбинирует поля разных размеров с большей эффективностью, но концепция более сложная.
Вывод
Круговые STARKs не сложны для разработчиков. Понимание задней математической стороны требует времени, но сложность хорошо скрыта. Это также путь к пониманию других специальных FFT.
На данный момент эффективность базового уровня STARKs близка к пределу. Будущие направления оптимизации могут включать:
Максимизация эффективности основных криптографических примитивов, таких как хэш-функции
Рекурсивная конструкция для увеличения параллелизма
Арфметическая виртуальная машина для улучшения опыта разработки
На этой странице может содержаться сторонний контент, который предоставляется исключительно в информационных целях (не в качестве заявлений/гарантий) и не должен рассматриваться как поддержка взглядов компании Gate или как финансовый или профессиональный совет. Подробности смотрите в разделе «Отказ от ответственности» .
Тайны Circle STARKs: революция эффективных доказательств благодаря малым полям
Глубокое исследование 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-битное число в качестве r. Но в малом поле STARKs доступно только около 2 миллиардов вариантов r, и злоумышленник может попробовать все возможные.
Эта проблема имеет два решения:
Множественные случайные проверки просты и эффективны, но имеют проблемы с эффективностью. Расширенные поля аналогичны множествам, но основаны на конечном поле. Вводится новое значение α, удовлетворяющее α^2=определенному значению, создавая новую математическую структуру. Это позволяет нам иметь больше значений на выбор, повышая безопасность.
! Новая работа Виталика: исследование круга STARKs
Регулярная ПЯТНИЦА
Первый шаг FRI-протокола обычно заключается в арифметизации, преобразовании вычислительной задачи в уравнение P(X,Y,Z)=0, где P является многочленом, а X, Y, Z — параметрами. Решение уравнения соответствует решению исходной задачи.
Чтобы доказать правильность решения, необходимо доказать, что предложенное значение является разумным многочленом и имеет максимальную степень. Используя технику случайной линейной комбинации:
По сути, B изолирует четные коэффициенты, а C изолирует нечетные коэффициенты. B и C могут восстановить A. Если степень A < 2^20, степени B и C соответственно равны степени A и степени A - 1. D как случайная комбинация, ее степень должна быть равна степени A.
FRI повторяет этот процесс упрощения, каждый раз упрощая проблему вдвое. Этот дизайн эффективно обнаруживает некорректный ввод.
! [Новая работа Виталика: Исследуйте круглые СТАРКИ (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 обрабатывает объекты пространства Римана-Роша, а не строгие многочлены.
Как разработчик, можно в значительной степени игнорировать этот момент. STARKs просто требуют хранения многочлена в виде набора оценочных значений. FFT в основном используется для низкой степени расширения: заданное N значений, генерирует k*N значений на одном и том же многочлене.
! Новая работа Виталика: Исследование круга СТАРКОВ
Квотирование
В Circle STARKs, из-за отсутствия одноприводной линейной функции, необходимо использовать различные приемы вместо традиционных операций умножения. Доказывается через оценку в двух точках, добавляя виртуальную точку.
Если многочлен P равен y1 при x1 и y2 при x2, выберите интерполяционную функцию L, которая равна в этих двух точках. Затем докажите, что P - L равно нулю в обеих точках, и, разделив L, получаем частное Q, которое является многочленом.
! Новая работа Виталика: Исследование круговых СТАРКОВ
Исчезающие многочлены
Многочлен исчезновения в Circle STARKs: Z1(x,y) = y Z2(x,y) = x
Zn+1(x,y) = (2 * Zn(x,y)^2) - 1
Это можно вывести из сворачивающей функции: повторное использование x → 2x^2 - 1.
Обратный порядок битов
Необходима корректировка обратного порядка битов в Circle STARKs: инвертировать каждый бит, кроме последнего, и использовать последний бит для определения, следует ли инвертировать другие биты.
16 размеров складного обратного порядка: {0, 15, 8, 7, 4, 11, 12, 3, 2, 13, 10, 5, 6, 9, 14, 1}
! Новая работа Виталика: Exploring Circle STARKs
Эффективность
Circle STARKs очень эффективны. Вычисления обычно включают:
Ключ к эффективности заключается в полном использовании вычислительного отслеживания пространства. 31-битное поле цифр снижает потери. Binius комбинирует поля разных размеров с большей эффективностью, но концепция более сложная.
Вывод
Круговые STARKs не сложны для разработчиков. Понимание задней математической стороны требует времени, но сложность хорошо скрыта. Это также путь к пониманию других специальных FFT.
На данный момент эффективность базового уровня STARKs близка к пределу. Будущие направления оптимизации могут включать: