zk-SNARKに関するノート

zk-SNARK に関する学習ノートで、主に zk-SNARK の方程式に焦点を当てています。

ZK-SNARK はゼロ知識簡潔非対話的知識の主張を意味します。

zk-SNARK の三つの特性

完全性：有効な証人を持つすべての命題には、検証者を納得させる証明があります。
健全性：無効な証人を持つ命題には、検証者を納得させる証明がありません。
ゼロ知識：証明は命題の有効性に関する情報のみを伝え、証明者の証人に関する情報は何も伝えません。

前提知識#

算術回路#

算術回路は多項式を計算するためのモデルです。有限体 $F=\{0,\cdots,p-1\}$ (素数 $p>2$ ) に対して、算術回路 $C:F^n\rightarrow F$ は、ノードが加算および乗算ゲートであり、エッジがワイヤである有向非循環グラフ（DAG）です。DAG の各ノードには二つの入力と出力があります。DAG には一つの最終出力があります。

Pasted 2023-10-01T05!48!45.358Z

$m$ - ゲート、 $n$ - ワイヤの算術回路において、証人は $s=(s_1,s_2,\cdots, s_n)$ と定義され、ここで $s_i$ は $i$ - 番目のワイヤの値です。

ランク - 1 制約 (R1CS) は次のように定義されます：一部の定数 $\{u_{i,q},v_{i,q},w_{i,q}\}_{1\le i\le n,1\le q\le m}$ に対して、 $\sum_{i=1}^ns_iu_{i,q}\cdot \sum_{i=1}^ns_iv_{i,q}=\sum_{i=1}^ns_iw_{i,q}$ 。例えば、図 1 では、 $s_1\cdot s_2=s_4$ は R1CS であり、ここで $u_{1,1}=1,v_{2,1}=1,w_{4,1}=1$ 、他は $=0$ です。

二次算術プログラム (QAP)#

まず、ターゲットポイントを $r_1,r_2,\cdots,t_m\in F_p$ と定義します。各ターゲットポイントは算術回路のゲートに対応します。次に、消失関数 $t(x)=\Pi_{q=1}^m(x-r_q)$ を定義し、 $t(x)=0$ がターゲットポイント $r_1,r_2,\cdots,t_m$ で成り立つようにします。

二次算術プログラムは $s=(s_1,s_2,\cdots, s_n)$ に関する関係であり、次のように表されます: $\sum_{i=1}^ns_iu_{i}(x)\cdot \sum_{i=1}^ns_iv_{i}(x)-\sum_{i=1}^ns_iw_{i}(x)\equiv 0~(\bmod~t(x))$ 、ここで $u_i(x),v_i(x),w_i(x)$ は次数 $m-1$ の多項式であり、 $1\le i\le n,1\le q\le m$ に対して、 $u_i(r_q)=u_{i,q}$ 、 $v_i(r_q)=v_{i,q}$ 、 $w_i(r_q)=w_{i,q}$ です。

$x=r_q$ のとき、この方程式は $q$ 番目のゲートの R1CS です。したがって、この方程式をチェックすることは、 $m$ のランク - 1 制約を同時にチェックすることに相当します。

ホモモルフィックエンコーディング#

ホモモルフィックエンコーディングは、 $E: F_p\rightarrow G$ という単射ホモモルフィズムであり、 $E(x)$ が与えられたときに $x$ を見つけるのが難しいです。

例えば、素数の順序 $p$ を持つ循環群 $G$ があり、 $g$ を生成元、乗算を群の演算とすると、ホモモルフィックエンコーディングは $E(a)=g^a$ です。これはホモモルフィックであり、単射です。また、離散対数問題の難しさにより、 $E(x)$ が与えられたときに $x$ を見つけるのも難しいです。

ペアリング関数、または双線形写像#

ペアリング関数、または双線形写像は次のように定義されます:

$G_1,G_2$ および $G_T$ は素数の順序 $p$ の群であり、ペアリング関数は $e:G_1\times G_2\rightarrow G_T$ であり、次の条件を満たします:

$g,h$ がそれぞれ $G_1$ および $G_2$ の生成元である場合、 $e(g,h)\not= 1$ は $G_T$ の生成元です。
$e(g^a,h^b)=e(g,h)^{ab}$ です。

双線形写像にはいくつかの特性があり、次のように示されます:

$e(u,vw)=e(g^a,h^bh^c)=e(g,h)^{a(b+c)}=e(g^a,h^b)e(g^a,h^c)=e(u,v)e(u,w)$
$e(vw,u)=e(v,u)e(w,u)$
$e(u^x,v)=e(g,h)^{xab}=e(u,v^x)$

Pinocchio 実装（zk-SNARK の実装）では、対称双線形写像が使用され、 $G:=G_1=G_2$ です。

zk-SNARK#

証明者と検証者が事前に合意した任意の NP 計算に対して、彼らはこの計算のための算術回路を構築でき、その回路の証人は元の計算の証人となります。算術回路は QAP に還元でき、QAP の証人を検証することは算術回路の証人を検証することに相当します。したがって、QAP の証人を検証することは元の計算の証人を検証することに等しいです。

算術回路から QAP への一般的な還元#

$m$ - ゲートおよび $n$ - ワイヤの算術回路に対して、証人は $s=(s_1,s_2,\cdots,s_n)\in R^n$ と定義されます。 $s$ に対する R1CS $(a_i,b_i,c_i)$ は次のように定義されます: $(s\cdot a_i)\times(s\cdot b_i)-s\cdot c_i=0$ 、ここで $1\le i\le m$ および $a_i,b_i,c_i\in R^n$ です。

一般的な還元は三つのステップから成ります:

$m$ の制約ベクトルをスタックして、行列 $A,B,C\in R^{m\times n}$ を取得します。ここで
- $A=\begin{pmatrix}a_1^T\\a_2^T\\\vdots\\a_m^T\end{pmatrix}B=\begin{pmatrix}b_1^T\\b_2^T\\\vdots\\b_m^T\end{pmatrix}C=\begin{pmatrix}c_1^T\\c_2^T\\\vdots\\c_m^T\end{pmatrix}$
ラグランジュ補間を使用して、 $3$ つの $n$ 多項式のセット $\{u_i\}_{i=1}^n,\{v_i\}_{i=1}^n,\{w_i\}_{i=1}^n$ を見つけます。これにより
- すべての $i\in[n]$ および $x\in[m]$ に対して
- $\begin{aligned}u_i(x)&=A[x][i]\\v_i(x)&=B[x][i]\\w_i(x)&=C[x][i]\end{aligned}$
多項式 $h(x)$ を見つけます。これにより
- $\left(\sum_{i=1}^ns_iu_i(x)\right)\cdot\left(\sum_{i=1}^ns_iv_i(x)\right)-\left(\sum_{i=1}^ns_iw_i(x)\right)=h(x)t(x)$
- ここで $t(x)=(x-1)(x-2)\cdots(x-n)$ です。

したがって、 $\left(\sum_{i=1}^ns_iu_i(x)\right)\cdot\left(\sum_{i=1}^ns_iv_i(x)\right)-\left(\sum_{i=1}^ns_iw_i(x)\right)=h(x)t(x)$ をチェックすることは、算術回路内の R1CS 関係をチェックすることに相当します。つまり、証人は各ノード内のすべての R1CS 関係を満たすことができます。

Pinocchio プロトコル#

Pinocchio プロトコルは zk-SNARK の実装です。

このプロトコルは、生成元 $g$ を持つ素数の順序 $p$ の群 $G$ に基づいて構築されます。ホモモルフィックエンコーディングを $E:F_p\rightarrow G$ 、 $E(x)=g^x$ と定義します。楕円曲線の双線形写像を $e:G\times G\rightarrow G_T$ と定義します。証明者は証人 $\{s_i\}_{i=1}^n$ を知っており、彼は次の方程式を還元によって得ることができます: $\left(\sum_{i=1}^ns_iu_i(x)\right)\cdot\left(\sum_{i=1}^ns_iv_i(x)\right)-\left(\sum_{i=1}^ns_iw_i(x)\right)=h(x)t(x)$ 。

主なアイデアは次のとおりです:

$V$ は多項式のためにランダムポイント $z\in F_p$ で $P$ をテストします。
$P$ は $u(z)=\sum_{i=1}^{n}s_{i}u_{i}(z),v(z)=\sum_{i=1}^{n}s_{i}v_{i}(z),w(z)=\sum_{i=1}^{n}s_{i}w_{i}(z)$ および $h(z)$ を計算し、これらの値をホモモルフィックにエンコードして $V$ に送信します。
$V$ は、ホモモルフィックにエンコードされた値が証人自体を学ぶことなく同じ方程式を満たすことを確認できます。

Pinocchio プロトコルは三つのステップから成ります: (1) 信頼できる第三者が共通参照文字列（CRS）を生成します；(2) 証明者が証明を生成します；(3) 検証者が証明をチェックし、受け入れるか拒否するかを決定します。

CRS 生成プロセスでは、信頼できる第三者がランダムな $\alpha, \beta_u,\beta_v,\beta_w,\gamma,z\in F_p^*$ を選択し、CRS を公開します。その後、信頼できる第三者は生成に使用したすべてのサンプル群要素（有害廃棄物）を破棄します。CRS は証明者の評価キーと検証者の検証キーで構成されます。

評価キーは次のように定義されます:

$\{E(z^{i})\}_{i=0}^{n},\{E(\alpha z^{i})\}_{i=0}^{n}$
$\{E(u_i(z)\}_{i=1}^n,\{E(\alpha u_i(z)\}_{i=1}^n,\{E(\beta_uu_i(z)\}_{i=1}^n$
$\{E(v_{i}(z)\}_{i=1}^{n},\{E(\alpha v_{i}(z)\}_{i=1}^{n},\{E(\beta_{v}v_{i}(z)\}_{i=1}^{n}$
$\{E(w_i(z)\}_{i=1}^n,\{E(\alpha w_i(z)\}_{i=1}^n,\{E(\beta_ww_i(z)\}_{i=1}^n$

検証キーは次のように定義されます:

$E(1),E(\alpha),E(t(z))$
$E(\gamma),E(\beta_u\gamma),E(\beta_v\gamma),E(\beta_w\gamma)$

証明生成プロセスでは、証明者は多項式 $\left(\sum_{i=1}^ns_iu_i(x)\right)\cdot\left(\sum_{i=1}^ns_iv_i(x)\right)-\left(\sum_{i=1}^ns_iw_i(x)\right)=h(x)t(x)$ を知っているため、最初に $h(x)$ を計算します。次に、証明者は評価キーを使用して証明を生成します:

$E(u(z)),E(\alpha u(z)),\mathrm{~where~}u(z)=\sum_{i=1}^ns_iu_i(z)$
$E(v(z)),E(\alpha v(z)),\mathrm{~where~}v(z)=\sum_{i=1}^ns_iv_i(z)$
$E(w(z)),E(\alpha w(z)),\text{ where }w(z)=\sum_{i=1}^ns_iw_i(z)$
$E(h(z)),E(\alpha h(z))$
$E(\beta_uu(z)+\beta_vv(z)+\beta_ww(z))$

例えば、

$E(u(z))=E(\sum_{i=1}^ns_iu_i(z))=g^{\sum_{i=1}^ns_iu_i(z)}=\Pi_{i=1}^ng^{s_iu_i(z)}=\Pi_{i=1}^n(g^{u_i(z)})^{s_i}=\Pi_{i=1}^n(E(u_i(z))^{s_i})$
$E(\alpha u(z))=E(\sum_{i=1}^ns_i\alpha u_i(z))=\Pi_{i=1}^n(E(\alpha u_i(z))^{s_i})$
$E(h(z))$ : $z^i$ の線形結合は、 $E(z^i)$ から計算できます。
$E(\beta_uu(z)+\beta_vv(z)+\beta_ww(z))=E(\beta_uu(z))E(\beta_vv(z))E(\beta_ww(z))$

証明検証プロセスでは、検証者は三つの検証を行います。

最初に、検証者は $u(z), v(z), w(z), h(z)$ の項が CRS 内の項の線形結合として構築されたことを確認するために、次の方程式をチェックします:

$e(E(u(z)),E(\alpha u_{1}(z))) =e(E(\alpha u(z)),E(u_1(z)))$
$e(E(v(z)),E(\alpha v_1(z))) =e(E(\alpha v(z)),E(v_1(z)))$
$e(E(w(z)),E(\alpha w_{1}(z))) =e(E(\alpha w(z)),E(w_1(z)))$
$e(E(h(z)),E(\alpha)) =e(E(\alpha h(z)),E(1))$

次に、検証者は各項 $u(z), v(z), w(z)$ が同じ線形係数 $\{s_i\}^n_{i=1}$ を使用して生成されたことを確認します。つまり、 $u(z)=\sum_{i=1}^{n}s_{i}u_{i}(z),v(z)=\sum_{i=1}^{n}s_{i}v_{i}(z),w(z)=\sum_{i=1}^{n}s_{i}w_{i}(z)$ をチェックします。

$e(E(\beta_uu(z)+\beta_vv(z)+\beta_ww(z)),E(\gamma))=e(E(u(z)),E(\beta_u\gamma))e(E(v(z)),E(\beta_v\gamma))e(E(w(z)),E(\beta_w\gamma))$

最後に、検証者は多項式の除算基準を特徴付けるキー条件をチェックするために、次の方程式をチェックします:

$e(E(u(z)),E(v(z)))=e(E(w(z)),E(1))\cdot e(E(t(z)),E(h(z)))$
すなわち、 $e(E(u(z)),E(v(z)))/e(E(w(z)),E(1))= e(E(t(z)),E(h(z)))$
すなわち、 $\left(\sum_{i=1}^ns_iu_i(x)\right)\cdot\left(\sum_{i=1}^ns_iv_i(x)\right)-\left(\sum_{i=1}^ns_iw_i(x)\right)=h(x)t(x)$ をチェックします。

検証者は、すべてのチェックが成立すれば受け入れます。

これまでのプロセスはゼロ知識ではありません。もし $V$ が独自の証人 $s^\prime=(s_1^\prime,s_2^\prime,\cdots,s_n^\prime)$ を考え出した場合、彼らは $E(u^\prime(z)),E(v^\prime(z)),E(w^\prime(z)),E(h^\prime(z))$ を計算できます。これらの値が $E(u(z)),E(v(z)),E(w(z)),E(h(z))$ と異なる場合、検証者は証明者の証人が $s^\prime$ ではないと結論します。

ゼロ知識は、多項式 $u,v,w$ にランダムシフトを追加することで達成できます。ランダムシフトは $t(x)$ の倍数であるため、すべてがまだ $\bmod~t(x)$ の下で同じです。ランダムな $\delta_1,\delta_2,\delta_3\in F_p$ に対して、シフトされた多項式は次のように定義されます。

$u_z(x)=u(x)+\delta_1 t(x)$
$v_z(x)=v(x)+\delta_2t(x)$
$w_z(x)=w(x)+\delta_3t(x)$

その後、 $P$ は証明内でシフトされていない項をシフトされた項に置き換えます。例えば、 $E(u_z(x))=E(u(x)+\delta_1t(x))=E(u(x))E(\delta_1t(x))$

Groth-16 プロトコル#

Groth-16 プロトコルは、zk-SNARK のより簡潔な実装です。証明のサイズと検証者の複雑さは、Groth-16 の Pinocchio よりも大幅に低くなります。

Groth-16 では、証明者が多項式 $\left(\sum_{i=1}^ns_iu_i(x)\right)\cdot\left(\sum_{i=1}^ns_iv_i(x)\right)-\left(\sum_{i=1}^ns_iw_i(x)\right)=h(x)t(x)$ を知っているため、証明は次のように定義されます:

$E(\alpha+u(z))$
$E(\beta+v(z))$
$E(\sum s_i\times(\beta u_i(z)+\alpha v_i(z)+w_i(z))+h(z)t(z))$

検証者は次をチェックします: $e(E(\alpha+u(z)), E(\beta+v(z)))=e(E(\sum s_i\times(\beta u_i(z)+\alpha v_i(z)+w_i(z))+h(z)t(z)), E(1))e(E(\alpha), E(\beta))$

参考文献#

zk-SNARKs のレビュー

ゼロ知識証明 MOOC