Резюме

В предыдущем посте мы представили арифметизацию — процесс преобразования оператора вычислительной целостности (CI) в проверку того, имеет ли полином низкую степень. Это преобразование позволяет нам добиться краткой проверки, когда верификатор оператора CI требует экспоненциально меньших ресурсов, чем те, которые необходимы для наивного воспроизведения. В предыдущем посте мы рассмотрели первый шаг в этом преобразовании на примере преобразования оператора CI о последовательности Коллатца в трассировку выполнения и набор полиномиальных ограничений. В этом посте мы делаем следующий шаг и показываем — используя последовательность Фибоначчи .на этот раз — как доказывающая сторона может объединить трассировку выполнения и полиномиальные ограничения, чтобы получить полином, который гарантированно имеет низкую степень, если и только если трасса выполнения удовлетворяет полиномиальным ограничениям, с которых мы начали. Более того, мы покажем, как область, в которой рассматривается полином, позволяет верификатору лаконично его оценить. Мы также кратко обсудим, как коды исправления ошибок играют роль в STARK.
Мы предполагаем, что знакомы с конечными группами, полиномами над конечными полями и предыдущими статьями этой серии.

Запросы и коды исправления ошибок

Напомним, что наша цель — дать проверяющему возможность задать доказывающему очень небольшое количество вопросов и решить, принять или отклонить доказательство с гарантированно высоким уровнем точности. В идеале верификатор хотел бы попросить доказывающего предоставить значения в нескольких (случайных) местах трассировки выполнения и проверить, что полиномиальные ограничения выполняются для этих мест. Корректная трассировка выполнения естественным образом пройдет этот тест. Однако нетрудно построить совершенно неверную трассу выполнения, нарушающую ограничения только в одном месте, и при этом достичь совершенно другого и далекого результата. Идентификация этой ошибки с помощью небольшого количества случайных запросов крайне маловероятна.

Распространенными методами решения подобных проблем являются коды исправления ошибок .

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

Интересно, что полиномы можно использовать для построения хороших кодов с исправлением ошибок, поскольку два полинома степени d, вычисленные в области, значительно большей, чем d, различны почти везде¹. Такие коды называются кодами Рида-Соломона .

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

Поэтому наш план состоит в том, чтобы 1) перефразировать трассировку выполнения в виде полинома, 2) расширить ее до большой области и 3) преобразовать ее, используя полиномиальные ограничения, в еще один полином, который гарантированно имеет низкую степень, если и только если трассировка выполнения действительна.

Пример : логическая трассировка выполнения

Предположим, что рассматриваемое утверждение КИ звучит так: «У доказывающего есть последовательность из 512 чисел, все из которых равны либо 0, либо 1», которую мы хотели бы проверить, прочитав значительно меньше 512 чисел. Давайте посмотрим, какую трассировку выполнения и полиномиальные ограничения выражают этот игрушечный пример:

1. Трассировка выполнения содержит 512 строк, каждая из которых содержит одну ячейку с нулем или единицей.
2. Полиномиальное ограничение, которое мы используем здесь, это просто Aᵢ ⋅ Aᵢ-Aᵢ=0 , где Aᵢ обозначает i-ю ячейку в этой трассировке выполнения с одним столбцом (число равно своему квадрату тогда и только тогда, когда оно равно 0 или 1) .

Чтобы перефразировать эту трассу выполнения в терминах полиномов, мы указываем поле, в котором мы будем работать — мы идем с Z₉₆₇₆₉ , полученным из набора целых чисел 0,1,…,96768 сложением и умножением по модулю 96769. Далее мы выбираем подгруппа G группы Z₉₆₇₆₉* (мы используем F* для обозначения мультипликативной группы² группы F ) такая, что |G|=512 , и некоторая образующая³ g группы G . Существование такой подгруппы гарантировано, так как 512 делит размер этой группы (что равно 96768).

Теперь мы будем думать об элементах трассы выполнения как об оценках некоторого полинома f(x) степени меньше 512 следующим образом: i-я ячейка содержит оценку f на i-й степени генератора.

Формально:

Такой многочлен степени не выше 512 можно вычислить путем интерполяции, а затем мы приступаем к его оценке в гораздо большей области⁴, формируя частный случай кодового слова Рида-Соломона.

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

Для этого мы должны пойти по касательной и обсудить корни многочленов.

Корни Polynomials

Основной факт о полиномах и их корнях состоит в том, что если p(x) является многочленом, то p(a)=0 для некоторого конкретного значения a тогда и только тогда , когда существует многочлен q(x) такой, что (xa)q (x)=p(x) и deg(p)=deg(q)+1 .

Более того, для всех x≠a мы можем оценить q(x) , вычислив:

По индукции аналогичный факт верен для k корней. А именно, если aᵢ является корнем p для всех i=0..k-1 , то существует многочлен q степени deg(p)-k , и во всех значениях k , кроме этих , он в точности равен

Собираем вместе

Перефразируя полиномиальное ограничение с точки зрения f , мы получаем следующий полином:

Мы определили f таким образом, что корнями этого выражения являются 1, g, g², …, g⁵¹¹ тогда и только тогда, когда ячейки в трассировке выполнения равны 0 или 1. Мы можем определить:

А из предыдущего абзаца мы знаем, что существует многочлен степени не выше 2 · deg(f)-512 , который согласуется с p при всех x ∉{ 1, g, g², …, g⁵¹¹} тогда и только тогда , когда трасса выполнения действительно является списком из 512 бит (т. е. 0 или 1). Обратите внимание, что ранее средство проверки расширило трассировку выполнения до более крупного домена, поэтому запрос полиномиальных значений в этом домене четко определен.

Если существует протокол, с помощью которого доказывающий может убедить⁵ верификатора в том, что этот полином имеет низкую степень, так что в нем верификатор запрашивает только значения вне трассы выполнения, тогда действительно верификатор будет убежден в правдивости утверждения CI. только когда это правда. Фактически, в следующем посте мы покажем протокол, который делает именно это с очень небольшой вероятностью ошибки. А пока — давайте взглянем на другой пример, пока еще простой, но не совсем тривиальный, и посмотрим, как в этом случае работает редукция.

Fibonacci

Пример, который мы используем далее, - это правильное вычисление последовательности Фибоначчи в Z₉₆₇₆₉ до 512-го места. Последовательность определяется формально следующим образом:

И наше утверждение (т. е. утверждение КИ) состоит в том, что a₅₁₁=62215.

Мы можем создать трассировку выполнения для этого оператора CI, просто записав все 512 чисел:

Полиномиальные ограничения , которые мы используем,

Перевести в Polynomials

Здесь мы также определяем полином f(x) степени не выше 512, такой, что элементы трассы выполнения являются оценками f по степеням некоторого генератора g.

Формально:

Выражая полиномиальные ограничения через f вместо A , мы получаем:

Поскольку композиция полиномов по-прежнему является полиномом, замена Aᵢ в ограничениях на f (gⁱ) по- прежнему означает, что это полиномиальные ограничения.

Обратите внимание, что 1, 2 и 4 — это ограничения, которые относятся к одному значению f , мы называем их граничными ограничениями .

Рекуррентное соотношение Фибоначчи, напротив, воплощает в себе набор ограничений для всей трассировки выполнения, и его можно альтернативно перефразировать следующим образом:

Использование генератора для индексации строк трассировки выполнения позволяет нам закодировать понятие «следующая строка» как простое алгебраическое отношение. Если x — некоторая строка в трассировке выполнения, то gx — следующая строка, g²x — следующая за ней строка, g⁻¹x — предыдущая строка и так далее.

Полином рекуррентного отношения: f(g²x)-f(gx)-f(x) равен нулю для каждого x , который индексирует строку в трассировке выполнения, кроме двух последних. Это означает, что 1, g, g², …, g⁵⁰⁹ являются корнями этого многочлена рекуррентного отношения (и он имеет степень не выше 510), поэтому мы можем построить q(x) следующим образом:

В знаниях СТАРКа это часто называют полиномиальной композицией . В самом деле, когда исходная трасса выполнения подчиняется рекуррентному соотношению Фибоначчи, это выражение согласуется с некоторым многочленом, степень которого не превышает 2 (напомним, что степень f не превышает 512) для всех 510 значений, кроме следующих: 1, g, g², …, г⁵⁰⁹ . Однако термин полином композиции несколько вводит в заблуждение, например, когда трассировка выполнения не удовлетворяет полиномиальному ограничению — оценки этого выражения во многих местах отличаются от любого полинома низкой степени . Другими словами — он близок к полиному низкой степени тогда и только тогда, когда исходный КИ верен, что и было нашей целью.

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

Краткость

Наличие очень эффективной техники проверки является ключом к STARK, и ее можно рассматривать как состоящую из двух частей — использование небольшого количества запросов и выполнение верификатором небольших вычислений по каждому запросу. Первое достигается с помощью кодов исправления ошибок, которые позволяют выполнять запросы в очень немногих местах, а второе мы как бы замалчивали в этом посте до сих пор. Работа верификатора может быть суммирована как 1) запрос полинома композиции в случайных местах и ​​2) проверка низкой степени на основе этих запросов. Сжатая проверка низкой степени будет рассмотрена в следующем посте, но что именно мы подразумеваем под «запросом полинома композиции»? Заядлый читатель мог с подозрением отнестись к этому выражению, и это правильно. Доказывающий, в конце концов, может быть злонамеренным.композиционный полином.

Чтобы предотвратить это, верификатор явно запрашивает трассировку выполнения Фибоначчи в некоторой строке w , запрашивая значения f в трех местах: f(w), f(gw), f(g²w) .

Теперь верификатор может вычислить значение полинома композиции в точке w следующим образом:

Где числитель можно вычислить, используя значения, полученные от прувера, а знаменатель… ну, вот загвоздка (которая была заметена под ковер).

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

С другой стороны, на практике трассировка может состоять из сотен тысяч строк, и вычисление знаменателя дорого обойдется верификатору во времени работы.

Вот где арифметизация имеет решающее значение для краткости, поскольку вычисление этого выражения для особого случая, когда степени g образуют подгруппу, может быть выполнено очень эффективно, если заметить, что:

Это равенство верно, поскольку обе части являются полиномами степени |G| корни которого в точности являются элементами группы G.

Кажется, что для вычисления правой части этого уравнения требуется ряд операций, линейных относительно |G|. Однако, если мы прибегнем к возведению в степень путем возведения в квадрат , левая часть этого уравнения может быть вычислена за время выполнения, логарифмическое по |G|.

И фактический знаменатель рассматриваемого полинома композиции Фибоначчи можно получить, переписав его как:

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

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

Больше ограничений, больше столбцов!

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

Подведение итогов

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

В следующем посте, который будет посвящен деталям тестирования низкой степени, будет показано, как выполняется это волшебство — запрос небольшого количества значений и определение того, имеет ли какой-либо полином низкую степень.

Шир Пелед
StarkWare

¹ Чтобы убедиться в этом, обратите внимание, что разность между различными многочленами степени d является ненулевым многочленом степени d, следовательно, имеет не более d нулей.

² Напоминание: мультипликативная группа получается путем исключения нулевого элемента из поля.

³ Генератор — это элемент подгруппы, мощности которого охватывают всю подгруппу.

⁴ Выбор размера этого домена напрямую влияет на ошибку надежности, чем она больше — тем меньше ошибка надежности.

⁵ Таким образом, проверяющий убежден тогда и только тогда, когда доказывающий не жульничает.