Explaining SNARKs(https://z.cash/blog/snark-explain) by Ariel Gabizon
の解説
zk-SNARKs(Zero-Knowledge Succinct Non-Interactive Argument of Knowledgeのアクロニム)とは、
特定の問題の答えを持っていることを、
その答えを教えず(ゼロ知識)、事前のコミュニケーションなく（非インタラクティブ）証拠を発表するのみで、証明する方法である。
この記事ではzk-SNARKsの解説をする。
証明は2段階のステップを踏む。
第１ステップ 問題の答えを知っていることを、ある多項式の組を知っていることに帰着する。（QAP）（Quadratic Arithmetic Programs）
第２ステップ その多項式を知っていることをゼロ知識で非インタラクティブに示す。
第１ステップ
まず、問題の帰着についての話をしよう。
ここで問題とは、ループのないプログラムで検証できるようなものを指す。例えば、「(c_1*c_2)*(c_1+c_3)=7を満たすc_1,c_2,c_3∈F_pは何か。」という問題を考える。
この場合、答え(c_1,c_2,c_3)を検証するには、(c_1*c_2)*(c_1+c_3)を計算すればよい。
第一歩として、この計算をArithmetic circuitと呼ばれる形式に直す。
(Σa_i l_i)*(Σ b_i r_i)のような積の計算ごとに１つの方程式を立てて、
各計算の方程式を連立する形がArithmetic circuitである。
今回の場合には、
g_1=c_1*c_2
g_2=g_1*(c_1+c_3)
連立方程式(A)
(g_2=7を加えてもよいが、元記事ではこの方程式を立てていない。今回は元記事に沿って進行する。)
と方程式を連立すればよい。
この方程式の数をdとする。この例ではd=2である。
正しい(c_1,c_2,c_3)を知っていれば、g_1,g_2も求められるので、証明者は解となる(c_1,c_2,c_3,g_1,g_2)を知っている。
後の表記を簡潔にするため、c_4=g_1,c_5=g_2と置き直す。
この変数の数をnとする。この例ではn=5である。
定数との和を取る場合などのために、c_0=1とおく場合もあるが、今回の例では使用しない。
一般には、
１≦j≦dについて項X_j,Y_jと変数Z_jについて
Z_1 =X_1*Y_1
…
Z_d=X_d*Y_d
の連立方程式で表せる。ここで、ベクトルL’_1, … ,L’_n,R’_1, … ,R’_n,O’_1, … ,O’_nを次のように定める
L’_iについて、第j成分l’_i,jは方程式jの*の左の総和（つまりX_j）にc_iの何倍が入っているかを表す。つまり、
式で書くと、L’_i=(L’_i,1 , … , L’_i,d)として、
j番目の方程式が … = ( c_i + …) * (… + …)であるとき
L’_i,j=1である。
R’_iについて、第j成分R’_i,jは方程式jの*の右の総和(つまりY_j）にc_iの何倍が入っているかを表す。
O’_iについて、第j成分O’_i,jは方程式jの左辺（つまりZ_j）にc_iの何倍が入っているかを表す。
つまり、X_j=ΣL’_i,j c_i Y_j=ΣR’_i,j c_i Z_j=ΣO’_i,j c_iである。この例では
L’_1=(1,0) L’_4=(0,1)
R’_2=(1,0) R’_1=(0,1) R’_3=(0,1)
O’_4=(1,0) O’_5=(0,1) 他は(0,0)となる。
このとき、多項式L_1(x), … ,L_n(x),R_1(x), … ,R_n(x),O_1(x), … ,O_n(x)で次をみたすものが一意に存在するので、それを求める。
1≦j≦dについて、L_i(j)=L’_i,j R_i(j)=R’_i,j O_i(j)=O’_i,jかつ各多項式はd次未満
つまり、L’i=(0,1)ならL_i(x)=x-1,L’_i=(1,0)ならL_i(x)=2-x,L’_i=(1,1)ならL’_i=1
といった具合である。
さらに、証明者は上記の連立方程式(A)の解(c_1,c_2,c_3,c_4,c_5)を用いて、多項式L(x),R(x),O(x)を次の式で得る。
L(x)=Σc_i L_i(x)
R(x)=Σc_i R_i(x)
O(x)=Σc_i O_i(x)
さらに、P(x)=L(x)R(x)-O(x)とする。
ここで、1≦j≦dについて
L(j)=Σc_i L_i(j)=Σc_i L’_i,j=X_j
R(j)=Σc_i R_i(j)=Σc_i R’_i,j=Y_j
O(j)=Σc_i O_i(j)=Σc_i O’_i,j=Z_j
だから、
1≦j≦dについてP(j)=X_j Y_j-Z_j=0
である。
よって、T(x)=Π(1≦j≦d)(x-j)として、P(x)=H(x)T(x)となる
H(x)が存在する。
ここで、(A)の解を知らなければ、L_i(x),R_i(x),O_i(x)の組の一次結合でL(x),R(x),O(x)を作り、かつ、P(x)=L(x)R(x)-O(x)をT(x)の倍数にすることは困難であるから、
最初の問題の答えを知っていることを、L(x),R(x),O(x),H(x)を知っていることに帰着できた。これがQAPである。
第２ステップ
ここでは、QAPで帰着した等式について検証する方法を考える。
(2d-2)次の多項式は2d-1個の点が与えられれば一意に決まる。逆に、異なる(2d-2)次の多項式は最大でも2d個の点しか一致しない。多項式の恒等式が成り立っていることを証明したいのだが、代わりに一点だけを調べる。F_pが十分に大きければ、間違った多項式が検証をパスする確率を十分に小さくできる。
例えば、次のようにすれば、証明者が正しく答えを知っているときに承認できる。
基本の流れ
Eを準同型暗号として、
1.検証者は証明者にsを送る。
2.証明者は検証者にE(L(s)),E(R(s)),E(O(s)),E(H(s))を送る。
3.検証者はE(L(s)R(s)-O(s))=E(T(s)H(s))を確認する。
ただしこの方法では、証明者がab-c=E(T(s))dをみたすa,b,c,d適当に送れば承認されてしまう等の問題がある。
そのため証明者は、加えて、「L(s),R(s),O(s)をそれぞれL_i(s),R_i(s),O_i(s)の同じ一次結合の形で計算したこと」、「H(s)を多項式の形で計算したこと」を証明する必要がある。
さて、上に書いたとは準同型暗号とは、暗号関数Eが二項演算△に対し、E(a△b)=E(a)△E(b)となるものである。多くの準同型暗号は加法と乗法のうち一方のみに対応するが、zkSNARKsには両方に対応する準同型暗号が必要である。
そこで、加法に対応する準同型暗号にペアリングという関数を用いて、1回だけ乗法に対応できる準同型暗号を作れる。今回は1回乗算ができれば用が足りるので、これを用いる。
ここでは、ペアリングに関する詳しい説明を省略する。
「L(s),R(s),O(s)をそれぞれL_i(s),R_i(s),O_i(s)の同じ一次結合の形で計算したこと」を示すには、
F(s)=L(s)+s^d R(s)+s^2d O(s),F_i(s)=L_i(s)+s^d R_i(s)+s^2d O_i(s)として
「F(s)をF_i(s)の一次結合の形で計算したこと」を示せばよい。
また、「H(s)を多項式の形で計算したこと」とは、
「H(s)が1,s,s², … ,s^(d-1) の一次結合の形で計算したこと」である。
ここで、yが(x_1,x_2, … ,x_n)の一次結合の形で計算したことを示すためには次の様な方法が採られる。
E_1,E_2を異なる準同型暗号として
1.証明者は、未知のαについて、
E_1(x_1), … ,E_1(x_n),
E_2(αx_1), … ,E_2(α x_n)を受け取り、a=E_1(y)とb=E_2(αy)を一次結合で計算し検証者に送る。
2.検証者はa,b,E_1(1),E_2(α)から、a=E_1(v),b=E_2(w)なるv,wについて、v,wを直接知ることなく、v:w=1:αであることをペアリングを用いて確認する。
また、非インタラクティブの実現の為には、この未知のαを、検証者によることなく、証明者に知られることなく、ランダムに生成する必要がある。[具体的にどうするのかは、元の記事を呼んだ限りでは分からなかった。]
以上をまとめて、zk-SNARKsは次のように行われる。
E_1,E_2は加法と乗法に対応する異なる準同型暗号
Tateはab=cd⇒Tate(E_1(a),E_2(b))=Tate(E_1(c),E_2(d))をみたすペアリング
1.誰にも秘密でランダムにαとsを選び、
E_1(1),E_1(s), … ,E_1(s^(d-1)),
E_2(α),E_2(αs), … ,E_2(αs^(d-1)),
E_1(F_1(s)), … ,E_1(F_n(s)),
E_2(α F_1(s)), … ,E_2(α F_n(s))が発表される。
これをCRS(common reference string)という。
2.証明者はCRSを元に
l=E_1(L(s)),r=E_1(R(s)),o=E_1(O(s)),h=E_1(H(s)),f=E_1(F(s)),f_2=E_2(αF(s)),h_2=E_2(αH(s))
を計算し、発表する。
3.検証者は
lr-o=E_1(T(x)) h
f=l+E_1(s^d) r+E_1(s^2d) o
Tate(f,E_2(α))=Tate(E_1(1),f_2)
Tate(h,E_2(α))=Tate(E_1(1),h_2)
が全て成り立つことを確認する。
また、元の記事によると次を行う必要があると記されている。
まず、証明のゼロ知識性のため、L(x),R(x),O(x)に手を加える。
L(x)R(x)-O(x)がT(x)の倍数であることが重要なので、L(x),R(x),O(x)にT(x)の適当な倍数を加えても問題ない。そこで適当なδ_1,δ_2,δ_3をとって、
Lz(x)=L(x)+δ_1 T(x),Rz(x)=R(x)+δ_2 T(x),Oz(x)=O(x)+δ_3 T(x)とし、
Lz(x)Rz(x)-Oz(x)=T(x)Hz(x)となるHz(x)を求める。
そして、このLz(x),Rz(x),Oz(x),Hz(x)を用いて証明を行う。
しかし、この方法を行うとL(x),R(x),O(x)がそれぞれL_i(x),R_i(x),O_i(x)の一次結合であるという性質が失われてしまう。
[そうなると、「L(s),R(s),O(s)をそれぞれL_i(s),R_i(s),O_i(s)の同じ一次結合の形で計算したこと」を確認できないのでは、という疑問点がある。→疑問は解決した。「Lz(s)をL_i(s)とT(s)の一次結合で計算したこと」（Rz(s),Oz(s)についても同様)を証明すれば問題ない。]
Lz(x),Rz(x),Oz(x),Hz(x)を用いた方法(2018/12/02 0:16追記)
改めて、zk-SNARKsは次のように行われる。
E_1,E_2は加法と乗法に対応する異なる準同型暗号
Tateはab=cd⇒Tate(E_1(a),E_2(b))=Tate(E_1(c),E_2(d))をみたすペアリング
1.誰にも秘密でランダムにαとsを選び、
E_1(1),E_1(s), … ,E_1(s^(d-1)),
E_2(α),E_2(αs), … ,E_2(αs^(d-1)),
E_1(F_1(s)), … ,E_1(F_n(s)),
E_2(α F_1(s)), … ,E_2(α F_n(s))
E_1(T(s))が発表される。
これをCRS(common reference string)という。
2.証明者はCRSを元に
l=E_1(Lz(s)),r=E_1(Rz(s)),o=E_1(Oz(s)),h=E_1(Hz(s)),f=E_1(F(s)),f_2=E_2(αF(s)),h_2=E_2(αH(s))
を計算し、発表する。
3.検証者は
lr-o=E_1(T(x)) h
f=l+E_1(s^d) r+E_1(s^2d) o
Tate(f,E_2(α))=Tate(E_1(1),f_2)
Tate(h,E_2(α))=Tate(E_1(1),h_2)
が全て成り立つことを確認する。