Приветствуем! Впервые на сайте Zcash?
The Zcash network is young, but evolving quickly! Sign up and we'll be in touch with monthly highlights on ecosystem growth, network development and how to get started with Zcash!

Язык

Объяснение SNARK Часть V: от вычислений к многочленам

Ariel Gabizon | Apr 25, 2017

<< Часть IV

В трех предыдущих частях, мы разработали определенное оборудование для контакта с многочленами. В этой части, мы покажем, как перевести заявления, которые мы бы хотели доказать и их проверку на язык многочленов. Идея использования многочленов таким способом основывается на фундаментальной работе Лунда, Фортноу, Карлоффа и Нисана.

В 2013 году, another breakthrough work of Gennaro, Gentry, Парно и Райкова определили очень полезный перевод вычислений в многочлены, который называется Квадратичная Арифметическая Программа (QAP). QAP стали основой новых zk-SNARK конструкций, которые частично используются в Zcash.

В этой статье мы объясним перевод в QAP на примере. Сосредоточимся на небольшом примере перед тем, как перейти к общему определению, и неизбежно объем описаний будет большим. Так что готовьтесь приложить некоторые умственные усилия :).

Предположим, Алиса хочет доказать Бобу, что она знает \(c_1,c_2,c_3 \in \mathbb{F}_p\) так что \((c_1\cdot c_2)\cdot (c_1 + c_3) = 7\). Первый шаг это представить выражение, вычисленное из \(c_1,c_2,c_3\) как арифметическую схему.

Арифметические схемы

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

An example of an arithmetic circuit

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

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

  • Когда один и тот же провод входит более чем в одни ворота, мы продолжаем думать о нём как об одном проводе - подобно \(\mathsf{w_1}\) в примере.
  • Мы предполагаем, что у ворот умножения есть только два входных провода, которые мы назвали левым проводом и правым проводом.
  • Мы не маркировали провода идущие от ворот сложения к воротам умножения, а также идущие к воротам сложения; мы думаем о входах ворот сложения как о входах, идущих непосредственно в ворота умножения. Так что в примере мы думаем, что \(\mathsf{w_1}\) и \(\mathsf{w_3}\) оба будут правыми входами \(\mathsf{g_2}\).

A legal assignment для схемы, это assignment of values to the labeled wires where the output value of each multiplication gate is indeed the product of the corresponding inputs.

Таким образом в нашей схеме, правильное решение примет форму: \((c_1,\ldots,c_5)\) где \(c_4=c_1\cdot c_2\) и \(c_5=c_4\cdot (c_1+c_3)\).

В этой терминологии, Алиса хочет доказать то, что она знает правильное решение \((c_1,\ldots,c_5)\) таким образом, что \(c_5=7\). Следующим шагом станет перевод этого умозаключения в многочлены, используя QAP.

Сокращение до QAP

Мы связываем каждый из входов умножения с элементом поля: \(\mathsf{g_1}\) будет связан с \(1\in\mathbb{F}_p\) и \(\mathsf{g_2}\) с \(2\in\mathbb{F}_p\). Мы можем назвать точки \(\{1,2\}\) нашими точками назначения. Сейчас мы должны определить набор "многочленов левого провода" \(L_1,\ldots,L_5\), "многочленов правого провода" \(R_1,\ldots,R_5\) и "многочленов выходного провода" \(O_1,\ldots,O_5\).

The idea for the definition is that the polynomials will usually be zero on the target points, except the ones involved in the target point's corresponding multiplication gate.

Конкретно, as \(\mathsf{w_1},\mathsf{w_2},\mathsf{w_4}\) это, соответственно, левый, правый и output wire of \(\mathsf{g_1}\); мы определяем \(L_1=R_2=O_4=2-X\), как многочлен \(2-X\) is one on the point \(1\) corresponding to \(\mathsf{g_1}\) and zero on the point \(2\) corresponding to \(\mathsf{g_2}\).

Note that \(\mathsf{w_1}\) and \(\mathsf{w_3}\) are both right inputs of \(\mathsf{g_2}\). Therefore, we define similarly \(L_4=R_1=R_3=O_5=X-1\) - as \(X-1\) is one on the target point \(2\) corresponding to \(\mathsf{g_2}\) and zero on the other target point.

Мы задаём, что остальные многочлены будут нулевыми.

Учитывая постоянные значения \((c_1,\ldots,c_5)\) мы используем их в качестве коэффициентов для определения многочленов левого, правого, и выходного "суммирующего". Таким образом мы определяем

\(L:=\sum_{i=1}^5 c_i\cdot L_i, R:=\sum_{i=1}^5 c_i\cdot R_i, O:=\sum_{i=1}^5 c_i\cdot O_i\),

и затем мы определяем многочлен \(P:=L\cdot R -O\).

Теперь, после всех этих определений, Центральная мысль такая: \((c_1,\ldots,c_5)\) это действительное тождество для схемы если и только если * |P| *исчезает во всех точках назначения.

Давайте проверим использование нашего примера. Предположим, мы определили \(L,R,O,P\) как уже делали выше с \(c_1,\ldots,c_5\). Давайте оценим все эти многочлены в точке назначения \(1\):

Из всех \(L_i\)'s только \(L_1\) отличается от нуля в \(1\). Таким образом мы получаем \(L(1)=c_1\cdot L_1(1)=c_1\). Похожим образом получаем \(R(1)=c_2\) и \(O(1)=c_4\).

Следовательно, \(P(1)=c_1\cdot c_2-c_4\). Подобное вычисление показывает \(P(2)= c_4\cdot (c_1+c_3) - c_5\).

Другими словами, \(P\) исчезает на точках назначения, если и только если \((c_1,\ldots,c_5)\) действительно задано.

Сейчас мы используем следующий алгебраический факт: для многочлена \(P\) и точки \(a\in\mathbb{F}_p\), у нас есть \(P(a)=0\) если и только если многочлен \(X-a\) делится на \(P\), то есть \(P=(X-a)\cdot H\) для некоторого многочлена \(H\).

Определим нужный многочлен \(T(X):=(X-1)\cdot (X-2)\), который есть у нас, когда \(T\) делит \(P\) если и только если \((c_1,\ldots,c_5)\) это действительное тождество.

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

Квадратическая Арифметическая Программа \(Q\) степени \(d\) и размера \(m\) состоит из многочленов \(L_1,\ldots,L_m\), \(R_1,\ldots,R_m\), \(O_1,\ldots,O_m\) и целевого многочлена \(T\) степени \(d\).

An assignment \((c_1,\ldots,c_m)\) satisfies \(Q\) if, defining \(L:=\sum_{i=1}^m c_i\cdot L_i, R:=\sum_{i=1}^m c_i\cdot R_i, O:=\sum_{i=1}^m c_i\cdot O_i\) и \(P:=L\cdot R -O\), we have that \(T\) divides \(P\).

В этой терминологии, Алиса хочет доказать, что она знает о том, что тождество \((c_1,\ldots,c_5)\) удовлетворяет QAP, описанному выше с \(c_5=7\).

Подытожим, что мы видим, как заявления, подобные "я знаю \(c_1,c_2,c_3\) и это значит что \((c_1\cdot c_2)\cdot (c_1 + c_3) = 7\)" можно перевести в эквивалентные заявления на многочленах, используя QAP. В следующей части, мы увидим эффективный протокол для проверки знания удовлетворения условиям QAP.

[1]В этой статье мы хотели дать самый краткий пример сокращения до QAP; мы также рекомендуем прекрасную статью Виталика Бутерина <https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649>`_ для получения дополнительной информации о преобразовании программы в QAP.

cryptography, zkSNARKs, explainers | Просмотреть все тэги