лвл степень тестированияотносится к проблеме определения того, является ли данная функция полиномом некоторой ограниченной степени, путем выполнения лишь небольшого количества запросов к функции. Проверка низкой степени изучается более двух десятилетий и является центральным инструментом теории вероятностных доказательств. Цель этой записи в блоге — более подробно объяснить низкоуровневое тестирование и описать FRI , протокол, который мы используем для низкоуровневого тестирования в STARK. Этот пост предполагает знакомство с полиномами над конечными полями.

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

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

Тестирование низкой степени

Прежде чем мы обсудим тестирование низкой степени, мы сначала представим немного более простую задачу в качестве разминки: нам дана функция, и нас просят решить, равна ли эта функция некоторому многочлену степени меньше, чем некоторая константа d, запрашивая функционируют в «небольшом» количестве мест. Формально, учитывая подмножество L поля F и границу степени d, мы хотим определить, равно ли f: L ➝ F многочлену степени меньше d, а именно, существует ли многочлен

над F, для которого p(a) = f(a) для каждого a в L. Для конкретных значений вы можете представить себе поле очень большого размера, скажем, 2¹²⁸, и L размером примерно 10 000 000.

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

По этой причине задача проверки низкой степени фактически относится к приближенной релаксации указанной выше задачи, которая достаточна для построения вероятностных доказательств, а также может быть решена с логарифмическим по |L| числом запросов. (обратите внимание, что если L≈10 000 000, то log₂(L)≈23). Более подробно мы хотим различать следующие два случая.

• Функция f равна полиному низкой степени. А именно, существует полином p(x) над F степени меньше d, совпадающий с f всюду на L.
• Функция f далеко не ВСЕ полиномы низкой степени. Например, нам нужно изменить не менее 10% значений f, прежде чем мы получим функцию, которая согласуется с полиномом степени меньше d.

Обратите внимание, что есть еще одна возможность — функция f может быть немного близка к полиному низкой степени, но не равна единице. Например, функция, у которой 5% значений отличаются от полинома низкой степени, не попадает ни в один из двух описанных выше случаев. Однако предыдущий шаг арифметизации (обсуждаемый в наших предыдущих сообщениях) гарантирует, что третий случай никогда не возникнет. Более подробно арифметизация показывает, что честный доказывающий, имеющий дело с истинным утверждением, попадет в первый случай, тогда как (возможно, злонамеренный) доказывающий, пытающийся «доказать» ложное утверждение, с высокой вероятностью попадет во второй случай.

Чтобы различить эти два случая, мы будем использовать вероятностный полиномиальный тест, который запрашивает f в небольшом количестве местоположений (позже мы обсудим, что означает слово «маленький»).

Если f действительно имеет низкую степень, то тест должен быть принят с вероятностью 1. Если вместо этого f далеко от низкой степени, то тест должен быть отклонен с высокой вероятностью. В более общем смысле мы ищем гарантию того, что если f δ-далеко от любой функции степени меньше d (т. е. нужно изменить по крайней мере δ|L| местоположений, чтобы получить полином степени меньше d), то проверка отклоняет с вероятностью не менее Ω(δ) (или какой-либо другой «хорошей» функции от δ). Интуитивно понятно, что чем ближе δ к нулю, тем труднее различить эти два случая.

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

Прямой тест

Первый тест, который мы рассматриваем, прост: он проверяет, является ли функция (близкой) полиномом степени меньше d, используя d+1 запросов. Тест основан на основном факте о многочленах: любой многочлен степени меньше d полностью определяется своими значениями в любых d различных местах F . Этот факт является прямым следствием того, что многочлен степени k может иметь не более k корней в F. Важно отметить, что количество запросов, равное d+1, может быть значительно меньше размера области определения f, т.е. то есть |L|.

Сначала мы обсудим два простых частных случая, чтобы понять, как тест будет работать в общем случае.

• Случай постоянной функции (d=1). Это соответствует проблеме различения между случаем, когда f — постоянная функция (f(x)=c для некоторого c в F), и случаем, когда f — далеко не какая-либо постоянная функция. В этом особом случае может работать естественный тест с двумя запросами: запросить f в фиксированном местоположении z1, а также в случайном месте w, а затем проверить, что f(z1)=f(w). Интуитивно, f(z1) определяет (предполагаемое) постоянное значение f, а f(w) проверяет, все ли f близко к этому постоянному значению или нет.
• Случай линейной функции (d=2). Это соответствует проблеме различия между случаем, когда f является линейной функцией (f(x)=ax+b для некоторых a,b в F), и случаем, когда f далека от какой-либо линейной функции. В этом особом случае может работать естественный тест с тремя запросами: запросить f в двух фиксированных точках z1,z2, а также в произвольной точке w, а затем проверить, что (z1,f(z1)), (z2,f (z2)), (w,f(w)) коллинеарны, а именно через эти точки можно провести прямую. Интуитивно понятно, что значения f(z1) и f(z2) определяют (предполагаемую) линию, а f(w) проверяет, все ли f близко к этой линии или нет.

Приведенные выше частные случаи предлагают тест для общего случая оценки степени d . Запросите f в d фиксированных точках z1,z2,…,zd, а также в произвольной точке w. Значения f в точках z0,z1,…,zd определяют единственный многочлен h(x) степени меньше d над F, который совпадает с f в этих точках . Затем тест проверяет, что h(w)=f(w). Мы называем это прямым тестом .

По определению, если f(x) равно многочлену p(x) степени меньше d, то h(x) будет идентично p(x) и, таким образом, прямой тест проходит с вероятностью 1. Это свойство называется «совершенная полнота», а это означает, что этот тест имеет только одностороннюю ошибку.

Остается выяснить, что произойдет, если f δ-далеко от любой функции степени меньше d. (Например, подумайте о δ = 10%.) Теперь мы утверждаем, что в этом случае прямой тест отклоняет с вероятностью не менее δ. В самом деле, пусть 𝞵 будет вероятностью при случайном выборе w того, что h(w)≠f(w). Обратите внимание, что 𝞵 должно быть не менее δ.

Это связано с тем, что если мы предположим, что 𝞵 меньше, чем δ, то мы выведем, что f δ-близко к h, что противоречит нашему предположению, что f δ-далеко от любой функции степени меньше d.

Прямого теста нам недостаточно

В нашей ситуации нас интересует проверка функций f:L➝F, которые кодируют следы вычислений и, следовательно, степень d (и область определения L) которых достаточно велики. Просто запустить прямой тест, который делает d+1 запросов, было бы слишком дорого. Чтобы получить экспоненциальную экономию STARK (время проверки по сравнению с размером трассировки вычислений), нам нужно решить эту проблему только с запросами O (log d), что экспоненциально меньше, чем граница степени d.

Это, к сожалению, невозможно, потому что если мы запросим f менее чем в d+1 местах , мы не сможем ничего сделать .

Один из способов убедиться в этом — рассмотреть два различных распределения функций f:L➝F. В одном распределении мы равномерно выбираем многочлен степени точно d и оцениваем его на L. В другом распределении мы равномерно выбираем многочлен степени меньше d и оцениваем его на L. В обоих случаях для любых d местоположений z1,z2 …,z d , значения f(z1),f(z2),…,f(z d) распределены равномерно и независимо. (Мы оставляем этот факт в качестве упражнения для читателя.) Это означает, что теоретически мы не можем различить эти два случая, даже если для этого потребуется тест (поскольку полиномы из первого распределения должны быть приняты тестом, в то время как те степени ровно d очень далеки от всех полиномов степени меньше d, поэтому их следует отбросить).

Кажется, перед нами стоит сложная задача.

Доказательство приходит на помощь

Мы видели, что нам нужно d+1 запросов, чтобы проверить, что функция f:L➝F близка к многочлену степени меньше d, но мы не можем позволить себе такое количество запросов. Мы избегаем этого ограничения, рассматривая немного другую настройку, которая для нас достаточна. А именно, мы рассматриваем проблему тестирования с низкой степенью, когда имеется доказывающее средство, предоставляющее полезную вспомогательную информацию о функции f. Мы увидим, что в этой «поддерживающей» настройке низкоуровневого тестирования мы можем добиться экспоненциального увеличения количества запросов до O(log d).

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

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

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

Уменьшение вдвое количества запросов для случая двух многочленов

Давайте начнем с простого примера, который иллюстрирует, как доказывающий может помочь уменьшить количество запросов в 2 раза. Позже мы будем основываться на этом примере. Предположим, что у нас есть два многочлена f и g, и мы хотим проверить, что они оба имеют степень меньше d. Если мы просто запустим прямой тест отдельно для f и g, нам нужно будет сделать 2 * (d + 1) запросов. Ниже мы опишем, как с помощью доказывающего мы можем уменьшить количество запросов до (d + 1) плюс член меньшего порядка.

Сначала верификатор выбирает случайное значение 𝛼 из поля и отправляет его проверяющему. Затем доказывающая сторона отвечает выполнением оценки области L (напомним, что L — область определения функции f) многочлена h(x) = f(x) + 𝛼g(x) (другими словами, Prover вычислит и отправит корень дерева Меркла, листья которого являются значениями h на L). Теперь верификатор проверяет, что h имеет степень меньше d, с помощью прямой проверки, которая требует d+1 запросов.

Интуитивно, если f или g имеет степень не ниже d, то с высокой вероятностью и h тоже. Например, рассмотрим случай, когда коэффициент xⁿ в f не равен нулю для некоторого n≥d. Тогда существует не более одного выбора 𝛼 (присланного верификатором), для которого коэффициент xⁿ в h равен нулю, а это означает, что вероятность того, что h имеет степень меньше d, примерно равна 1/|F|. Если поле достаточно велико (скажем, |F|>2¹²⁸), вероятность ошибки незначительна.

Однако ситуация не так проста. Причина в том, что, как мы объясняли, мы не можем буквально проверить, является ли h многочленом степени меньше d. Вместо этого мы можем только проверить, что h близок к такому многочлену. Это означает, что приведенный выше анализ не является точным. Возможно ли, что f будет далеко от полинома низкой степени, а линейная комбинация h будет близка к единице с пренебрежимо малой вероятностью над 𝛼? В мягких условиях ответ отрицательный (это то, что нам нужно), но это выходит за рамки этого поста; мы отсылаем заинтересованного читателя к этой статье и этой статье .

Более того, откуда верификатор узнает, что полином h , посланный проверяющим, имеет вид f(x)+𝛼g(x)? Злонамеренный доказывающий может обмануть, отправив полином, который действительно имеет низкую степень, но отличается от линейной комбинации, которую запросил проверяющий. Если мы уже знаем, что h близок к полиному низкой степени, то проверить правильность формы этого полинома низкой степени несложно: верификатор случайным образом выбирает местоположение z в L, запрашивает f , g, hв точке z и проверяет выполнение уравнения h(z)=f(z)+𝛼g(z). Этот тест следует повторять несколько раз, чтобы повысить точность теста, но ошибка уменьшается экспоненциально с увеличением количества образцов, которые мы делаем. Следовательно, этот шаг увеличивает количество запросов (которое до сих пор было d+1) только на член меньшего порядка.

Разделение polynomials на два polynomials меньшей степени

Мы увидели, что с помощью доказывающего мы можем проверить, что два полинома имеют степень меньше d, выполнив менее 2*(d+1) запросов. Теперь опишем, как можно превратить один многочлен степени меньше d в два многочлена степени меньше d/2.

Пусть f(x) — многочлен степени меньше d и предположим, что d четно (в нашем случае это получается без ограничения общности). Мы можем написать f(x)=g(x²)+xh(x²) для двух полиномов g(x) и h(x) степени меньше d/2. В самом деле, мы можем сделать так, чтобы g(x) был многочленом, полученным из четных коэффициентов f(x), а h(x) был полиномом, полученным из нечетных коэффициентов f(x). Например, если d=6, мы можем написать

что обозначает

а также

который представляет собой алгоритм n * log (n) для полиномиальной оценки (улучшенный по сравнению с наивным алгоритмом n2).

Протокол FRI

Теперь мы объединим две приведенные выше идеи (проверка двух полиномов с половиной запросов и разбиение полинома на два меньших) в протокол, который использует только O(log d) запросов для проверки того, что функция f имеет (точнее, близка к в функции) степени меньше, чем d. Этот протокол известен как FRI (что расшифровывается как Fast Reed — Solomon Interactive Oracle Proof of Proximity), и заинтересованный читатель может подробнее прочитать о нем здесь . Для простоты ниже мы предполагаем, что d является степенью числа 2. Протокол состоит из двух фаз: фазы фиксации и фазы запроса .

Фаза фиксации

Доказательство разбивает исходный многочлен f₀(x)=f(x) на два многочлена степени меньше d/2, g₀(x) и h₀(x), удовлетворяющие условию f₀(x)=g₀(x²)+xh₀(x² ). Верификатор выбирает случайное значение 𝛼₀, отправляет его доказывающему и просит доказывающего зафиксировать полином f₁(x)=g₀(x) + 𝛼₀h₀(x). Обратите внимание, что степень f₁(x) меньше d/2.

Мы можем продолжить рекурсивно, разделив f₁(x) на g₁(x) и h₁(x), затем выбрав значение 𝛼₁, построив f₂(x) и так далее. Каждый раз степень многочлена уменьшается вдвое. Следовательно, после log(d) шагов у нас остается постоянный многочлен, и доказывающая сторона может просто отправить постоянное значение верификатору.

Замечание о доменах: для работы приведенного выше протокола нам необходимо свойство, состоящее в том, что для каждого z в домене L верно, что -z также находится в L. Более того, обязательство по f₁(x) не будет превышать L но над L²={x²: x ∊ L}. Поскольку мы итеративно применяем шаг FRI, L² также должен удовлетворять свойству {z, -z} и т. д. Эти естественные алгебраические требования легко удовлетворяются за счет естественного выбора областей L (скажем, мультипликативной подгруппы, размер которой равен степени двойки) и фактически совпадают с теми, которые нам так или иначе нужны, чтобы извлечь выгоду из эффективных алгоритмов БПФ (которые используются в другом месте STARK, например, для кодирования трасс выполнения).

Фаза запроса

Теперь нам нужно проверить, не обманул ли доказывающий. Верификатор выбирает случайный z из L и запрашивает f₀(z) и f₀(-z). Этих двух значений достаточно, чтобы определить значения g₀(z²) и h₀(z²), как это видно из следующих двух линейных уравнений с двумя «переменными» g₀(z²) и h₀(z²):

Проверяющий может решить эту систему уравнений и вывести значения g₀(z²) и h₀(z²). Отсюда следует, что он может вычислить значение f₁(z²), которое представляет собой линейную комбинацию двух. Теперь верификатор запрашивает f₁(z²) и убеждается, что оно равно значению, вычисленному выше. Это служит признаком того, что подтверждение f₁(x), которое было отправлено доказывающим на этапе фиксации, действительно правильное. Верификатор может продолжить, запросив f₁(-z²) (напомним, что (-z²)∊ L² и что обязательство по f₁(x) было дано на L²) и вывести из него f₂(z⁴).

Верификатор продолжает таким образом, пока не использует все эти запросы для окончательного вывода значения f_{log d}(z) (обозначая f с индексом log d, который мы не можем записать из-за отсутствия в Medium поддержки полноценных математические обозначения). Но вспомните, что f_{log d}(z) — это постоянный многочлен, постоянное значение которого было отправлено доказывающим на этапе фиксации до выбора z. Верификатор должен проверить, что значение, отправленное проверяющим, действительно равно значению, которое верификатор вычислил из запросов к предыдущим функциям.

В целом, количество запросов логарифмично только в степени d.

Чтобы понять, почему доказывающий не может жульничать, рассмотрим игрушечную задачу, где f₀ равно нулю на 90% пар вида {z, -z}, т. е. f₀(z) = f₀(-z) = 0 (назовем это «хорошие» пары) и ненулевые на оставшихся 10% («плохие» пары). С вероятностью 10% случайно выбранный z попадает в плохую пару. Обратите внимание, что только один 𝛼 приведет к f₁(z²)=0, а остальные приведут к f₁(z²)≠0. Если доказывающий мошенничает со значением f₁(z²), он будет пойман, поэтому мы предполагаем обратное. Таким образом, с большой вероятностью (f₁(z²), f₁(-z²)) также будет плохой парой в следующем слое (значение f₁(-z²) не важно, так как f₁(z²)≠0). Это продолжается до последнего слоя, где значение с высокой вероятностью будет ненулевым.

С другой стороны, поскольку мы начали с функции с 90% нулей, маловероятно, что доказывающий сможет подобраться к полиному низкой степени, отличному от нулевого полинома (здесь мы не будем доказывать этот факт). В частности, это означает, что прувер должен отправить 0 в качестве значения последнего слоя. Но тогда у верификатора есть вероятность примерно 10% поймать доказывающего. Это был лишь неофициальный аргумент, заинтересованный читатель может найти здесь строгое доказательство .

В тесте, описанном до сих пор (и приведенном выше анализе), вероятность того, что верификатор поймает злонамеренного проверяющего, составляет всего 10%. Другими словами, вероятность ошибки составляет 90%. Это можно экспоненциально улучшить, повторив описанную выше фазу запроса для нескольких независимых выборок z. Например, выбрав 850 z, мы получим вероятность ошибки 2^{-128}, что практически равно нулю.

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

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

Алессандро Кьеза и Лиор Голдберг
StarkWare