Greetings! New to 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!

言語

SNARKsの説明 パート6: ピノキオプロトコル

Ariel Gabizon | May 10, 2017

<< Part V

パート5では、アリスがボブに証明したい命題をQuadratic Arithmetic Program(二次方程式計算プログラム、QAP) と呼ばれる "多項式の言語" に変換する方法を取り上げました。

このパートでは、アリスがボブにQAPへの条件を満たす割り当ての所有を示す短い証明を送る方法を解説します。ここではParno、Howell、GentryおよびRaykova氏による Pinocchioプロトコル を使用します。 始める前に前回取り上げた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=summ, R=summ, O=summ| および |P=LR-O| と定義した場合に満たし、 |t||P| を割ります。

パート5で見てきた通り、通常アリスはいくつかの追加の制限( \(c_m=7\); )を所有する、条件を満たす代入を証明することを望みますが、ここでは簡略化のためにこれを無視し、 一部 の条件を満たす代入についての知識を証明する方法を説明します。

アリスが条件を満たす代入を得ている場合は、上記のように \(L,R,O,P\) を定義したうえで、 \(P=H\cdot T\) であるような多項式 \(H\) が存在することを意味します。具体的には、すべての \(s\in\mathbb{F}_p\)\(P(s)=H(s)\cdot T(s)\) になります。

次にアリスが条件を満たす代入を得て いない 場合を想定します。 彼女はそれでも条件を満たさない代入 \((c_1,\ldots,c_m)\) から上記の通り \(L,R,O,P\) を構築します。 その後、私たちは \(T\)\(P\) を割らないことを保証されました。 これは、あらゆる最大 \(d\) 度の多項式 \(H\) では \(P\) および \(H\cdot T\) が異なる多項式になることを意味します。 ここでの \(P\) および \(H\cdot T\) は両方とも最大 \(2d\) です。

次に有名な Schwartz-Zippel Lemma を使用できます。これにより 2つの異なる最大 \(2d\) 度の多項式は最大 \(2d\)\(s\in\mathbb{F}_p\) で合意できることがわかります。 このため、 \(p\)\(2d\) よりとても大きくなる場合 \(P(s)=H(s)\cdot T(s)\) は無作為に選択された \(s\in\mathbb{F}_p\) でとても小さくなる可能性が高くなります。

これは、アリスが条件を満たす代入を得られているかどうかを試験する以下のプロトコルスケッチを示唆します。

  1. アリスは最大 \(d\) 度の多項式 \(L,R,O,H\) を選択します。
  2. ボブは無作為の点 \(s\in\mathbb{F}_p\) を選択し、 \(E(T(s))\) を計算します。
  3. アリスはボブにこれらすべての多項式の 隠匿数\(s\) で評価、つまり \(E(L(s)),E(R(s)),E(O(s)),E(H(s))\) で送ります。
  4. ボブは \(s\) で希望の方程式が成立するか確認します。つまり、 \(E(L(s)\cdot R(s)-O(s))=E(T(s)\cdot H(s))\) であるかを確認します。

ここでも、アリスが条件を満たす代入を得られていないと、彼女は最終的に多項式を 方程式があらゆる点で等しく成立しない状態で使用することになり、このためほとんどの \(s\) の選択で成立しません。このような場合、ボブは選択した \(s\) により高い確率で拒否するでしょう。

問題は、このスケッチを実装するツールがあるかどうかです。 最も重要な点はアリスが \(s\)知らずに 使用する多項式を選択しなくてはならないことです。 ただしこれは、私たちがパート2-4で展開した 証明可能な盲目評価のためのプロトコル を使って解決した問題とまったく同じ問題です。

このスケッチをzk-SNARKに変えるために対処する必要のあるポイントは主に4つあります。 ここでそのうち2点を対処し、次のパートで残り2点に対処します。

アリスが代入により多項式を選択するようにする

ここに重要な点があります:アリスが条件を満たす代入を得られていない場合でも 一つも 多項式を見つけられないわけではありません。 \(L\cdot R-O=T\cdot H\) で最大 \(d\) 度の \(L,R,O,H\) では、彼女が "代入から導き出された"; \(L,R\)\(O\) の多項式を見つけられないことを意味します。 すなわち、同じ \((c_1,\ldots,c_m)\)\(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\) ということです。

パート4のプロトコルはただ彼女が正しい度数の \(L,R,O\) を使用していることだけを保証し、 代入から導き出されたものであることは保証しません。 これが、正式な証明が少しあいまいになる点です。ここで、私たちはソリューションを不正確にスケッチ化しています。

多項式 \(L,R,O\) を以下の通り一つの多項式 \(F\) にまとめます:

\(F=L+X^{d+1}\cdot R+X^{2(d+1)}\cdot O\)

\(R\)\(X^{d+1}\)\(O\)\(X^{2(d+1)}\) を乗算する目的は \(L,R,O\) の係数が \(F\) では "混在しない" : \(F\)\(1,X,\ldots,X^d\) の係数は \(L\) の係数とまったく同一であり 次の \(d+1\)\(X^{d+1},\ldots,X^{2d+1}\) の係数は \(R\) の係数とまったく同一で、最後の \(d+1\) の係数は \(O\) のそれと一致します。

同じようなやり方でQAP定義内の多項式をまとめてみましょう。 各 \(i\in \{1,\ldots,m\}\) に最初の係数 \(d+1\)\(L_i\) の係数となり、 次に \(R_i\) 、その後|Oi| と続くように多項式 \(F_i\) を定義します。 すなわち、各 \(i\in \{1,\ldots,m\}\) に次の多項式を定義します。

\(F_i=L_i+X^{d+1}\cdot R_i+X^{2(d+1)}\cdot O_i\)

\(F_i\) のうち2つを合計するときに \(L_i\)\(R_i\)\(O_i\) は "個別に合計" することに注意してください。 例えば、 \(F_1+F_2 = (L_1+L_2)+X^{d+1}\cdot (R_1+R_2)+X^{2(d+1)}\cdot(O_1+O_2)\) となります。

さらに一般的なケースとして、ある \((c_1,\ldots,c_m)\)\(F=\sum_{i=1}^mc_i\cdot F_i\) と仮定してください。 その場合同じ係数 \((c_1,\ldots,c_m)\)\(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\) となります。 言い換えると、 \(F\) が一連の \(F_i\) の線形結合である場合 \(L,R,O\) が明らかに代入から導き出されたことを意味します。

このため、ボブはアリスに \(F\)\(F_i\) の線形結合であることを証明するよう求めるでしょう。 これは、証明可能な評価のプロトコルと同じような方法で行われます:

ボブは無作為の \(\beta\in\mathbb{F}^*_p\) を選択し、アリスに隠匿数 \(E(\beta\cdot F_1(s)),\ldots,E(\beta\cdot F_m(s))\) を送ります。 彼はその後アリスに要素 \(E(\beta\cdot F(s))\) を送るように求めます。 アリスがこれに成功した場合、 係数仮定の知識 の拡張されたバージョンが、アリスが \(F_i\) の線形結合として \(F\) を書く方法を知っていることを示します。

ゼロ値意識部分の追加 - 代入の隠匿

zk-SNARK内で、アリスは彼女の代入についての情報を隠匿したいと希望します。 しかし、隠匿数 \(E(L(s)),E(R(s)),E(O(s)),E(H(s))\) から 一部の 代入についての情報が判明してしまいます。

例として、ある別の条件を満たす代入 \((c'_1,\ldots,c'_m)\) を前提にボブは対応する \(L',R',O',H'\) と隠匿数 \(E(L'(s)),E(R'(s)),E(O'(s)),E(H'(s))\) が計算できます。 これらがアリスの隠匿数と異なる結果になる場合、 \((c'_1,\ldots,c'_m)\) がアリスの代入と違うことが演繹できます。

代入についての情報漏洩を防ぐために、アリスは "無作為のシフト \(T\)" を各多項式に追加することで代入を隠匿します。 すなわち、アリスは無作為の \(\delta_1,\delta_2,\delta_3\in\mathbb{F}^*_p\) を選択し、 \(L_z:=L+\delta_1\cdot T,R_z:=R+\delta_2\cdot T,O_z:=O+\delta_3\cdot T\) を定義します。

\(L,R,O\) が条件を満たす代入から導き出されたと仮定します。従って、ある多項式 \(H\) では \(L\cdot R-O = T\cdot H\) になります。 つい先ほど全箇所に \(T\) の乗数を追加したことから、 \(T\)\(L_z\cdot R_z-O_z\) を割ります。 この様子を見るために計算をしてみましょう:

\(L_z\cdot R_z-O_z = (L+\delta_1\cdot T)(R+\delta_2\cdot T) - O-\delta_3\cdot T\) \(= (L\cdot R-O) + L\cdot \delta_2\cdot T + \delta_1\cdot T\cdot R + \delta_1\delta_2\cdot T^2 - \delta_3\cdot T\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\) \(=T\cdot (H+L\cdot \delta_2 + \delta_1\cdot R + \delta_1 \delta_2\cdot T)\)

このため、 \(H'=H+L\cdot\delta_2 + \delta_1\cdot R + \delta_1\delta_2\cdot T\) を定義することで、 \(L_z\cdot R_z-O_z=T\cdot H_z\) となります。 つまり、アリスが多項式 \(L,R,O,H\) の代わりに \(L_z,R_z,O_z,H_z\) を使用した場合、ボブは常に許容するでしょう。

一方、( \(d\) \(s\) 以外のすべてである) \(T(s)\neq 0\)\(s\in\mathbb{F}_p\) で評価された、このような多項式は代入について情報を明らかにしません。 例として、 \(T(s)\) がノンゼロで \(\delta_1\) が無作為であるため、 \(\delta_1\cdot T(s)\) も無作為の値であり、 つまり \(L_z(s)=L(s)+\delta_1\cdot T(s)\) は無作為の値によりマスクされているため \(L(s)\) についての情報を明らかにしません。

次回にはどのような問題が残っていますか?

今回は、アリスがボブに自分がQAPのための条件を満たす代入を持っていることを、 その代入の情報を明らかにせずに納得させるPinocchioプロトコルのスケッチをお見せしました。 zk-SNARKを取得するために解決する必要のある主な問題があと2件残っています:

  • スケッチ内で、ボブは "乗算を裏付ける" HH が必要とします。例えば、 \(E(H(s)\cdot T(s))\) from \(E(H(s))\)\(E(T(s))\) を計算する必要があります。ただし、私たちはこれを可能にするHHをまだ見ていません。今まで見てきたのは加算と線形結合を裏付けるHHだけです。
  • このシリーズを通して、私たちはアリスとボブの間で 相互作用する プロトコルを見てきました。ただし、最終的な目標はアリスが単一のメッセージで 公に証明可能な相互作用しない証明 を送ることであり、それはこの単一のメッセージを見て、ボブ(アリスと事前に連絡を取っていた)だけでなく誰もがその有効性に納得できることを意味します。

これらの両問題は、次の最終パートで取り上げる楕円曲線の対合を使用することで解決できます。

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