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

Автор: Vitalik Buterin

Оригинальное название: 《Квадратичные арифметические программы: от нуля до героя》

Дата публикации: 10 декабря 2016 года

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

Цель этой статьи не является полным введением в zk-SNARKs, она предполагает, что у вас есть следующие базовые знания:

1- Вы знаете о zk-SNARKs и их основных принципах;

2- У вас достаточно математических знаний, чтобы понять некоторые основные полиномиальные концепции. (Например, если P(x) + Q(x) = (P + Q)(x), P и Q представляют собой полиномы, и если вы очень хорошо знакомы с таким представлением полиномов, это означает, что вы соответствуете требованиям для продолжения чтения).

Схема знаний о zk-SNARK, нарисованная Эраном Тромером

Как показано на рисунке, вышеупомянутое доказательство с нулевым разглашением можно разделить на два этапа сверху вниз. Во-первых, zk-SNARK не может быть непосредственно применен к любой вычислительной задаче; наоборот, вы должны преобразовать задачу в правильную "форму" для выполнения. Эта форма называется "квадратичной арифметической программой" (QAP), и преобразование кода функции в эти коды само по себе очень важно. Вместе с процессом преобразования кода функции в QAP выполняется еще один процесс, который позволяет создать соответствующее решение (иногда называемое "свидетельством" QAP), если есть входные данные кода. Это то, о чем нужно рассказать в этой статье.

После этого есть еще один довольно сложный процесс для создания фактического "доказательства с нулевым разглашением" для этого QAP, а также отдельный процесс для проверки доказательства, переданного вам другим человеком, но эти детали выходят за рамки данной статьи.

В следующем примере мы выберем очень простую задачу:

Найдите решение кубического уравнения: x**3 + x + 5 == 35 (подсказка: ответ 3).

Эта задача проста, но важно, что вы можете увидеть, как все функции работают на этом примере.

Опишите вышеуказанное уравнение на языке программирования следующим образом:

def qeval(x):
y = x**3
return x + y + 5
Простой язык программирования, который мы используем здесь, поддерживает базовую арифметику (+, -, *, /), постоянные степени (x7, но не x*y) и присваивание переменных, что достаточно мощно, чтобы теоретически выполнять любые вычисления (при условии, что количество шагов вычисления ограничено; циклы не допускаются). Обратите внимание, что операции взятия остатка (%) и сравнения (<, >, ≤, ≥) не поддерживаются, поскольку нет эффективного способа выполнять операции взятия остатка или напрямую сравнивать алгоритмы конечных циклических групп (спасибо; если бы был какой-либо способ сделать это, скорость взлома криптографии на основе эллиптических кривых превысила бы "двоичный поиск" и "теорему о китайской остатке").

Вы можете расширить язык до операций взятия остатка и сравнения с помощью разложения битов (например: 13 = 2**3 + 2**2 + 1 = 8 + 4 + 1) в качестве вспомогательного ввода, доказать правильность этих разложений и выполнять математические операции в двоичных схемах; в алгоритмах конечных полей также возможно выполнение проверки равенства (==), на самом деле это даже немного проще, но мы сейчас не будем обсуждать эти два момента. Мы можем расширить язык, чтобы поддерживать условные операторы (например, преобразовать оператор: if x < 5: y = 7; else: y = 9; в арифметическую форму: y = 7 * (x < 5) + 9 * (x >= 5);) однако обратите внимание, что оба "пути" условия должны быть выполнены, если у вас много вложенных условий, это приведет к значительным накладным расходам.

Теперь давайте шаг за шагом пройдем через этот процесс. Если вы хотите написать любой код самостоятельно, я здесь реализовал код на Python (только для образовательных целей; QAP для реального мира еще не готово!)

Шаг 1: Упрощение

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

1- x = y (y может быть переменной или числом)
2- x = y(op)z (op может быть +, -, *, /, y и z могут быть переменными, числами или подвыражениями).

Вы можете рассматривать эти выражения как логические ворота в схеме. Результат процесса упрощения выражения x**3 + x + 5 выглядит следующим образом:

sym1 = x * x y = sym1 * x // эквивалентно реализации функции степени y = x**3
sym2 = y + x ~out = sym2 + 5

Вы можете считать каждую строку вышеупомянутого объявления логическим воротом в схеме, и, по сравнению с исходным кодом, здесь мы ввели две промежуточные переменные sym1 и sym2, а также один избыточный переменный ~out, представляющий выход, и нетрудно заметить, что последовательность объявлений после "упрощения" эквивалентна исходному коду.

Шаг 2: Преобразование в R1CS

Теперь мы преобразуем это в то, что называется R1CS (Rand-1 Constraint System). R1CS состоит из последовательности трех векторов (a, b, c), решение R1CS - это вектор s, который должен удовлетворять уравнению

s . a * s . b - s . c = 0

где . представляет собой операцию скалярного произведения.

Например, вот удовлетворительный R1CS:

a = (5,0,0,0,0,1),
b = (1,0,0,0,0,0),
c = (0,0,1,0,0,0),
s = (1,3,35,9,27,30),

（Примечание переводчика: первое 35=1*5 + 30*1, второе 35=35 * 1）

Приведенный выше пример - это всего лишь одно ограничение, далее мы должны преобразовать каждую логическую ворота (то есть каждое упрощенное объявление) в ограничение (то есть набор векторов (a, b, c)), и способ преобразования зависит от того, какая операция выполняется (+, -, *, /) и являются ли параметры объявления переменными или числами. В нашем примере, кроме пяти переменных после "упрощения" ('x', '~out', 'sym1', 'y', 'sym2'), нам также нужно ввести избыточную переменную ~one на первой компоненте, чтобы представить число 1, так что для нашей системы вектор, соответствующий 6 компонентам, будет (может быть в другом порядке, главное, чтобы соответствовало):

'~one', 'x', '~out', 'sym1', 'y', 'sym2'

Первое ворота

sym1 = x * x, то есть x*x - sym1 = 0

Мы можем получить следующий набор векторов:

a = [0, 1, 0, 0, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 1, 0, 0]

Если второй скаляр в векторе решения s равен 3, а четвертый скаляр равен 9, то это будет верно независимо от того, сколько других скаляров, поскольку: a = 3 * 1, b = 3 * 1, c = 9 * 1, то есть a * b = c. Точно так же, если второй скаляр s равен 7, а четвертый скаляр равен 49, это также пройдет проверку, первый раз проверка предназначена только для проверки согласованности входов и выходов первого ворота.

Второе ворота

y = sym1 * x, то есть sym1 * x - y = 0
Можно получить следующий набор векторов:

a = [0, 0, 0, 1, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 0, 1, 0]

Третье ворота

sym2 = y + x, ворота сложения нужно преобразовать в: (x + y) * 1 - sym2 = 0
Получаем следующий набор векторов:

a = [0, 1, 0, 0, 1, 0]
b = [1, 0, 0, 0, 0, 0] соответствует константе 1, используя ~one
c = [0, 0, 0, 0, 0, 1]

Четвертое ворота

~out = sym2 + 5, то есть (sym2 + 5) * 1 - ~out = 0
Получаем следующий набор векторов:

a = [5, 0, 0, 0, 0, 1]
b = [1, 0, 0, 0, 0, 0]
c = [0, 0, 1, 0, 0, 0]

Теперь предположим, что x = 3, согласно первому ворота, получаем sym1 = 9, согласно второму ворота получаем y = 27, согласно третьему ворота получаем sym2 = 30, согласно четвертому ворота получаем ~out = 35, таким образом, согласно: '~one', 'x', '~out', 'sym1', 'y', 'sym2', мы можем получить:

s = [1, 3, 35, 9, 27, 30]

Если предположить другое значение x, можно получить разные значения s, но все s могут быть использованы для проверки (a, b, c)

Теперь у нас есть R1CS для четырех ограничений, полный R1CS выглядит следующим образом:

A
[0, 1, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 1, 0]
[5, 0, 0, 0, 0, 1]

B
[0, 1, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]

C
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0]

Шаг 3: Из R1CS в QAP

Следующий шаг - преобразовать этот R1CS в форму QAP, которая реализует абсолютно ту же логику, просто используя полиномы вместо скалярного произведения. Мы делаем это следующим образом: от 4 наборов векторов длиной 6 до 6 наборов полиномов степени 3, в каждой координате x полином представляет собой ограничение. То есть, если мы вычислим полином в точке x=1, мы получим первый набор векторов, если мы вычислим полином в точке x=2, мы получим второй набор векторов и так далее.

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

Давайте сделаем пример. Предположим, мы хотим полином, проходящий через (1,3), (2,2) и (3,4). Сначала мы делаем полином, проходящий через (1,3), (2,0) и (3,0). На самом деле, полином, "растягивающий" x = 1 и 0 для других интересующих нас точек, легко сделать, нам просто нужно сделать следующий полином:

y = (x - 2) * (x - 3)

Как показано на рисунке:

Затем "растягиваем" по оси y, используя следующее уравнение:

y = (x - 2) * (x - 3) * 3 / ((1 - 2) * (1 - 3))

После упрощения получаем:

y = 1.5 * x**2 - 7.5 * x + 9

Который проходит через (1,3), (2,0) и (3,0), как показано на рисунке:

Подставив точки (2,2) и (3,4) в вышеуказанное уравнение, мы можем получить:

y = 1.5 * x**2 - 5.5 * x + 7

Это именно то, что мы хотим получить в виде координатного уравнения. Указанный алгоритм требует O(n3) времени, поскольку есть n точек, и для каждой точки требуется O(n2) времени для умножения полиномов. Немного подумав, это можно сократить до O(n**2) времени, еще немного подумав, используя быстрые алгоритмы преобразования Фурье и так далее, это можно еще больше сократить ------ это ключевая оптимизация, когда функции, используемые в zk-SNARKs, обычно имеют тысячи ворот.

Здесь я сразу приведу формулу интерполяции Лагранжа:

n-1-й полином через n точек (x1,y1),(x2,y2),(x3,y3),…,(xn,yn) будет:

Например, полином, проходящий через точки (1,3), (2,2), (3,4), будет:

Научившись использовать эту формулу, мы можем продолжить наши шаги. Теперь мы должны преобразовать четыре группы векторов длиной шесть в шесть групп полиномов, каждая группа полиномов включает три полинома третьей степени, мы будем оценивать различные ограничения в каждой точке x, здесь у нас всего четыре ограничения, поэтому мы будем оценивать эти четыре группы векторов с полиномами в x = 1, 2, 3, 4.

Теперь мы используем формулу интерполяции Лагранжа, чтобы преобразовать R1CS в форму QAP. Сначала мы находим полиномы, соответствующие каждому первому значению вектора a для четырех ограничений, то есть используя теорему интерполяции Лагранжа, чтобы найти полином, проходящий через точки (1,0), (2,0), (3,0), (4,0), аналогично мы можем найти полиномы для остальных четырех ограничений, соответствующие каждому i-му значению вектора.

Здесь сразу даю ответы:

A полиномы
[-5.0, 9.166, -5.0, 0.833]
[8.0, -11.333, 5.0, -0.666]
[0.0, 0.0, 0.0, 0.0]
[-6.0, 9.5, -4.0, 0.5]
[4.0, -7.0, 3.5, -0.5]
[-1.0, 1.833, -1.0, 0.166]

B полиномы
[3.0, -5.166, 2.5, -0.333]
[-2.0, 5.166, -2.5, 0.333]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]

C полиномы
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[-1.0, 1.833, -1.0, 0.166]
[4.0, -4.333, 1.5, -0.166]
[-6.0, 9.5, -4.0, 0.5]
[4.0, -7.0, 3.5, -0.5]

Эти коэффициенты отсортированы в порядке возрастания, например, первый полином выше - это 0.833 * x**3 - 5 * x**2 + 9.166 * x - 5. Если мы подставим x=1 в вышеуказанные восемнадцать полиномов, мы можем получить три вектора первого ограничения

(0, 1, 0, 0, 0, 0),
(0, 1, 0, 0, 0, 0),
(0, 0, 0, 1, 0, 0),
…
Аналогично, подставив x = 2, 3, 4 в вышеуказанные полиномы, мы можем восстановить оставшуюся часть R1CS.

Шаг 4: Проверка QAP

Преобразовав R1CS в QAP, мы можем одновременно проверять все ограничения через операции скалярного произведения полиномов, а не проверять каждое ограничение по отдельности, как в R1CS. Как показано на рисунке:

Поскольку в этом случае проверка скалярного произведения представляет собой серию сложений и умножений полиномов, результатом является сам полином. Если полученный полином, в каждой точке x, используемой для представления логических ворот, равен 0, это означает, что все проверки пройдены; если результат полинома хотя бы в одной точке не равен нулю, это означает, что значения на входе и выходе логических ворот не согласованы.

Стоит отметить, что полученный полином сам по себе не обязательно равен нулю, на самом деле в большинстве случаев это не так; он может вести себя как угодно в точках, не соответствующих никаким логическим воротам, при этом в точках, соответствующих некоторым воротам, результат будет равен нулю. Для проверки корректности мы не вычисляем полином t = A . s * B . s - C . s в каждой точке, соответствующей воротам; вместо этого мы делим t на другой полином Z и проверяем, делится ли Z на t без остатка, то есть деление t / Z не имеет остатка.

Z определяется как (x - 1) * (x - 2) * (x - 3)… - самый простой полином, который равен 0 во всех точках, соответствующих логическим воротам. Это основное алгебраическое свойство: любой полином, равный нулю во всех этих точках, должен быть кратным этому минимальному полиному, если полином является кратным Z, то его значение в любой из этих точек равно нулю; это равенство значительно упрощает нашу работу.

Теперь давайте проведем проверку скалярного произведения с помощью вышеуказанных полиномов.

Сначала мы получаем промежуточные полиномы:

A . s = [43.0, -73.333, 38.5, -5.166]
B . s = [-3.0, 10.333, -5.0, 0.666]
C . s = [-41.0, 71.666, -24.5, 2.833]
（Примечание переводчика: вышеуказанный процесс вычисления:
43.0 = -5 * 1 + 8 * 3 + 0 * 35 - 6 * 9 + 4 * 27 - 1 * 30，
-73.333 = 9.166 * 1 - 11.333 * 3 + 0 * 35 + 9.5 * 9 - 7 * 27 + 1.833 * 30,
…
-3 = 3 * 1 - 2 * 3 + 0 * 35 + 0 * 9 + 0 * 27 + 0 * 30
…)

После вычисления A . s * B . s - C . s получаем:

t = [-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444]
（Примечание переводчика: процесс вычисления:
A . s = [43.0, -73.333, 38.5, -5.166] = -5.166 * x3 + 38.5 * x2 - 73.333 * x + 43,
B . s = [-3.0, 10.333, -5.0, 0.666] = 0.666 * x3 - 5 * x2 + 10.333 * x - 3.0,
C . s = [-41.0, 71.666, -24.5, 2.833] = 2.833 * x3 - 24.5 * x2 + 71.666 * x - 41.0
A . s * B . s - C . s - это вычисление вышеуказанных полиномов, после вычисления, упорядочиваем коэффициенты по степени от низшей к высшей, получаем: [-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444]

Нажмите здесь, чтобы увидеть процесс вычисления-%5Cleft(2.833x%5E%7B3%7D-24.5x%5E%7B2%7D%2B71.666x-41%5Cright))

Минимальный полином:

Z = (x - 1) * (x - 2) * (x - 3) * (x - 4)

то есть:

Z = [24, -50, 35, -10, 1]

Процесс вычисления выше нажмите здесь, чтобы увидеть%20%5Ccdot%20%5Cleft(x%20-%203%5Cright)%20%5Ccdot%20%5Cleft(x%20-%204%5Cright))

Теперь вычисляем деление полиномов:

h = t / Z = [-3.666, 17.055, -3.444]

h должно быть целым делением без остатка.

Вы можете нажать здесь, чтобы проверить%20%5Ccdot%5Cleft(x%20-%203%5Cright)%20%5Ccdot%5Cleft(x%20-%204%5Cright)%5Ccdot%5Cleft(-3.444x%5E%7B2%7D%2B17.055x-3.666%5Cright)).

У нас есть решение QAP. Если мы попытаемся подделать переменные в R1CS, и этот R1CS выведет решение QAP ------ например, установив последнее число s равным 31 вместо 30, мы получим полином t, который не пройдет проверку (в определенных случаях, в x = 3 = 1, а не 0), и он не будет кратным Z; наоборот, деление t / Z даст остаток [-5.0, 8.833, -4.5, 0.666].

Обратите внимание, что вышеуказанный пример является очень простым; в реальном мире операции сложения, вычитания, умножения и деления обычно сопровождаются неординарными числами, поэтому все известные и любимые алгебраические законы все еще полезны, однако все ответы представляют собой элементы ------ обычно целые числа в диапазоне от 0 до n - 1. Например, если n = 13, то 1 / 2 = 7 (7 * 2 = 1), 3 * 5 = 2 и так далее. Использование алгоритмов конечных полей устраняет беспокойство о погрешностях округления и позволяет системе хорошо работать с эллиптическими кривыми, что в конечном итоге делает протоколы zk-SNARK действительно безопасными.