Greetings! New to Zcash?
The Zcash network is young, but evolving quickly! Sign up and we'll be in touch with more information about how you can get started with Zcash!

言語

SNARKsの説明 パート5: 計算から多項式へ

Ariel Gabizon | Apr 25, 2017

<< パート IV

これ以前の3パートでは、多項式を取り扱うための特定の機械を開発しました。 このパートでは、証明したいステートメントを翻訳する方法、多項式の言語に対して検証する方法を説明します。 この方法で多項式を使用するという考えはLund、Fortnow、Karloff、Nisanの 革新的な仕事 から始まりました。

2013年には、Gennaro、Gentry、Parno、およびRaykovaによる もう一つのブレイクスルー が大変有用な多項式への計算の翻訳である Quadratic Arithmetic Program二次方程式計算プログラム (QAP) を定義しました。 QAPは特にZcashで使用される現在のzk-SNARK構築の基盤となりました。

この投稿ではQAPへの翻訳を例示して解説します。一般的な定義ではなく小さな例に注目しているときでも、はじめのうちは理解すべきことがどうしても多くなりますので、ある程度の精神的努力に取り組む心づもりでいてください :)。

アリスがボブに \((c_1\cdot c_2)\cdot (c_1 + c_3) = 7\) であるような \(c_1,c_2,c_3 \in \mathbb{F}_p\) について知っていることを証明したいとします。 はじめに、 \(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}\) にとって正しい入力であるとみなします。

回路の 法的割当 とは、各乗算ゲートの出力値が対応する入力の計算結果になるようにラベル付けされたワイヤに値を割り当てることです。

この回線では、法的割当は次の形式をとります: \((c_1,\ldots,c_5)\) ここでは \(c_4=c_1\cdot c_2\) および \(c_5=c_4\cdot (c_1+c_3)\) となる。

この用語では、アリスが証明したい内容は \(c_5=7\) となる \((c_1,\ldots,c_5)\) です。 次に、この命題をQAPを使用した多項式に翻訳します。

QAPへの削減

各乗算ゲートをフィールド要素に関連付けます。 \(\mathsf{g_1}\)\(1\in\mathbb{F}_p\) および \(2\in\mathbb{F}_p\)\(\mathsf{g_2}\) と関連付けられます。 \(\{1,2\}\) のポイントを ターゲットポイント と呼びます。 次に一連の「左ワイヤ多項式」 \(L_1,\ldots,L_5\) 、「右ワイヤ多項式」 \(R_1,\ldots,R_5\) および「出力ワイヤ多項式」 \(O_1,\ldots,O_5\) を定義する必要があります。

定義とは、ターゲットポイントに対応する乗算ゲートに関連するもの以外は、 多項式はターゲットポイントでは通常ゼロになるということを意味します。

具体的に言うと、 \(\mathsf{w_1},\mathsf{w_2},\mathsf{w_4}\) がそれぞれ \(\mathsf{g_1}\) の左、右、出力ワイヤのとき、 多項式 \(2-X\)\(\mathsf{g_1}\) に対応するポイント \(1\) では1で、 \(\mathsf{g_2}\) に対応するポイント \(2\) ではゼロになるため \(L_1=R_2=O_4=2-X\) と定義します。

\(\mathsf{w_1}\)\(\mathsf{w_3}\)両方とも \(\mathsf{g_2}\) の右入力であることに注意してください。 つまり、同様に \(\mathsf{g_2}\) に対応するターゲットポイント \(2\) では \(X-1\) が 1になるため \(L_4=R_1=R_3=O_5=X-1\) - と定義します。

残りの多項式もゼロ多項式になるように設定します。

固定値 \((c_1,\ldots,c_5)\) を係数として、 左、右、出力「sum(合計)」多項式を定義するため使用します。 つまり、以下のように定義します。

\(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\) がすべてのターゲットポイントで消滅する場合のみ回路の法的割当になります

今回の例を使ってこれを検証してみましょう。 \(c_1,\ldots,c_5\) という前提で、 \(L,R,O,P\) を上記の通り定義したと想定します。 ターゲットポイント \(1\) でのこれらすべての多項式を検証しましょう。

すべての \(L_i\) のうち、 \(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\) に対し、
多項式 \(X-a\)\(P\)割る 場合のみ \(P(a)=0\) となります。つまり一部の多項式 \(H\) に対し \(P=(X-a)\cdot H\) となります。

ターゲット多項式 \(T(X):=(X-1)\cdot (X-2)\) を定義することで、 \((c_1,\ldots,c_5)\) が法的割当である場合のみ \(T\)\(P\) を割ることになります。

上記の考察に従い、QAPを以下のように定義します:

Quadratic Arithmetic Program二次方程式計算プログラム \(Q\)\(d\) 度およびサイズ \(m\) は、多項式 \(L_1,\ldots,L_m\)\(R_1,\ldots,R_m\)\(O_1,\ldots,O_m\) およびターゲット多項式 \(T\)\(d\) 度で構成されています。

割当 \((c_1,\ldots,c_m)\) \(Q\) を * * \(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\) と定義した場合に満たし、 \(T\) \(P\) を割ります。

この用語集では、アリスは上記に説明されたQAPを \(c_5=7\) で満たす割り当て \((c_1,\ldots,c_5)\) を知っていることを証明したいと思っています。

まとめると「私は \((c_1\cdot c_2)\cdot (c_1 + c_3) = 7\) となるような \(c_1,c_2,c_3\) を知っています」のような命題は QAPを使用する多項式についての同等の命題に翻訳できます。 次の部分では、QAP を満たす割り当ての知識を提供する効率的なプロトコルを見ていきます。

[1]この投稿ではQAPへの削減の最も簡潔な事例を挙げようと試みました。また、プログラムからQAPへの変換の詳細については、Vitalik Buterinの 優れた投稿 をお勧めします。

cryptography, zkSNARKs, explainers | 全てのタグを見る