zk-SNARKs勉強会
zk-SNARKsを勉強した結果を残していく。このページでは雑記の形式で思いついたことをつらつらと書くため、情報の信頼性は低いです。ある程度、理解が進んだら別ページで清書したい。
参考にするページ
決定版！
ピノキオプロトコル
あるすごいでかい計算を外部のちょーすごいPCを持っている人に頼む時、帰ってきた結果が本当に計算した結果なのか？を検証するためのプロトコル
つまり、この数式を実際に計算したか？ を検証が可能。
どうやって検証するの？
2018/11/14時点の理解
よくわかってないけど、まずは数式を小さな式に分解
(a+b) * (b * c)の例とかみた。この時、+と*と*がそれぞれノードとなって、入力としてはa,b,c
a + b -> out1
b * c -> out2
out1 * out2 -> out3
＋とか＊に注目することで簡単な式が出てくる。この式をバラバラにして、適当に組み合わせると元々の式とは全く違う式ができる。この求まった式にパラメータと結果をぶち込んだらなんかいい感じにしてくれるっていうもの？
他の説明を見ると、(a-out1)(b-out2)とか出てくるので、ぐちゃぐちゃにして作る式の結果が０になるようなout put?というかproof？を計算結果と合わせて提出すれば確かにそれだね！みたいな話になるのかな？
上記の理解が正しいとして問題となるのは、各四則演算をポイントとして組み立て直した式が元の式よりも複雑ではないこととを保証することなどかな？
式の組み立て方とかは２章以降に書いてるので読み進める。
2018/11/15時点の理解
https://gyazo.com/46d5efdce63336e847ca3550ad3dea87
上記の図について
QAPは3種類の多項式から構築される（3つではない。。。はず？）
V, W, Yとあらわされる
それぞれの多項式は積算のゲートを基準にして構築される。上記の図の場合は、積算ゲートは2つあり、それぞれの入力はC1, C2, C3, C4となり、出力はC5, C6となる。
多項式Vの要素vkはゲートrkの左側の入力が与えられたときに1を出力し、それ以外の時は０を出力する。なので、上記の図では、r5とr6(rは出力につながるゲートになる。なんでr1, r2じゃないんだろか？添え字を合わせるためかな）に対して考えると、v3(つまり入力C3)はゲートr5の左の入力なので、r5の時だけ1となる。v1(つまり入力C1)とv2(入力C2)は加算ゲートにつながっているが、QAPの時は加算はその後の積算への入力とみなされるので、r6の左側の入力とみなされている。
Wはゲートの右側の入力の時に1となるので、同様に考えると、w4がr5の右側の入力なので１、w5はr6に対しての右側の入力なので１、それ以外は０となる。
Yはゲートの出力の場合にのみ1となるので、y5はr5の時だけ１、y6はr6の時だけ1となる
加算ゲートはQAPの一般式を単純化すると積算しか現れないため無視してよいっていうのは式ではわかるけど、ほんとかな？という疑問が残る。
QSPの意味が分からなかったけど理解した。なるほど。入力に対して1か0しか出さないような単式を組み合わせる（and, or）することで、多項式がbool値のみを扱う論理式と同等なものに変換できるのか。
とはいえ、基本的にはand回路でしかない気がするが。。。。
2018/11/22時点の理解
P = L*R - O（ピノキオプロトコルでは P = V*W - Y) の意味が分かった。Lは積算ゲートの左入力を集めた多項式で、Rが同じく右入力を集めた多項式、そしてOがアウトプットを集めた多項式なので、この多項式同士の関係がそもそもL*R＝Oが成り立つってことか。ここでOを左辺に展開して$ L*R-O=0になると。で、$ P=0って考えるとそのあとのP=(X-N)*Hとかになるのか。
$ (a+b)\times(b\times c)で考える
1. $ r_5に注目すると、$ L=b, R=c, O=b\times c
2. $ r_6に注目すると、$ L=a+b, R=b+c, O=(a+b)\times(b \times c)
3. で、この2つのゲートを通る証明式を$ P=L*R - Oとした場合、$ r_5では$ b\times c-b\times c=0となり、$ r_6では$ (a+b)\times(b\times c) - (a+b)\times(b\times c)=0となるので、$ P=0である。これを、$ r_5と$ r_6どちらの値を入れたときも満たす$ Pの多項式を考えると$ P(x) = (X-r_5)(X-r_6)となる。 この説明は間違いで、0と等価になればいいので、$ T(x) = (x-1)(x-2)となる。この時、$ P(x) = L(x) \times R(x) - O(x) = H(x) \times T(x)を満たすH(x)が存在するということ。
2018/12/01時点の理解
数学に疎いので僕がぱっと見でわからなかったところを以下で細かく検証してみた
QAPの具体例
QAPの解説では全て$ \mathbb{F_p}(=有限体）上の整数で考えるので、式の最後にすべて$ mod \space pされている。
(a+b)*(b*c)の式を元にQAPを組み立ててみる。
連立方程式の数は掛け算の数なので、この場合はd=2となる。
上の方にある図の回路に合わせるために変数をそれぞれ次の通りに定義し直す。$ c_1 = a, c_2 = b, c_3 = b, c_4 = c, c_5=(b*c), c_6=(a+b)*(b*c)
置き直した変数で2つの連立方程式$ A(x)を組み直すと次の通りになる。$ A(1): c_5=c_3*c_4, $ A(2): c_6=(c_1+c_2)*c_5]
なので、QAPで生成する$ P = L \times R - O は$ P_1 = L_1 \times R_1 - O_1と$ P_2 = L_2 \times R_2 - O_2の2つになる。
変数の個数をnとすると今回の式では変数が$ c_1, c_2, c_3, c_4, c_5, c_6の6個あるので、n=6となる。
$ 1 \le n \le 6の全ての$ L_i(x)の式を考える。この式はつまり、$ L_1(1)=0, L_2(1)=0, L_3(1)=1, L_4(1)=0, L_5(1)=0, L_6(1)=0, L_1(2)=1, L_2(2)=1, L_3(2)=0, L_4(2)=0, L_5(2)=0, L_6(2)=0を満たす式である。
つまり$ L_1(x)=(x-1), L_2(x)=(x-1), L_3(x)=(2-x), L_4(x)=0, L_5(x)=0, L_6(x)=0となる。
同様に考えると、$ R_i(x)は$ R_1(x)=0, R_2(x)=0, R_3(x)=0, R_4(x)=(2-x), R_5(x)=(x-1), R_6(x)=0
また$ O_i(x)は$ O_1(x)=0, O_2(x)=0, O_3(x)=0, O_4(x)=0, O_5(x)=(2-x), O_6(x)=(x-1)
これらを１次線形結合するので、$ L(x)=c_1(x-1)+c_2(x-1)+c_3(2-x), R(x)=c_4(2-x)+c_5(x-1), O(x)=c_5(2-x)+c_6(x-1)となる。
次に$ P(x)=L(x) \times R(x) - O(x)を考えると、$ P(1)=c_3 \times c_4 - c_5 = b \times c - (b \times c) = 0であり、$ P(2)=(c_1+c_2) \times c_5 - c_6 = (a+b) \times (b \times c) - (a+b) \times (b \times c) = 0となる
上記の通り、$ P(1)=0, P(2)=0なので、これを満たす式として、$ T(x)=(x-1)(x-2)が求まる。あとの式がめんどくさくなるので今回は$ T(x)=(x-1)(2-x)としておく。
さらに、$ P(x)=T(x)=0なので、0に何をかけても0であることから$ P(x)=H(x)\times T(x)も成り立つ。
というか$ P(x) = L(x) \times R(x) - O(x) = H(x)\times T(x)を成立させないといけないので、$ H(x)は存在する。
今回の場合では、$ P(x)=(c_1(x-1)+c_2(x-1)+c_3(2-x)) \times (c_4(2-x)+c5(x-1)) - (c_5(2-x)+c_6(x-1))=H(x)\times(x-1)(2-x)をとけば求められる（解くのめんどくさそう。。。）
$ = c_1c_4(x-1)(2-x)+c_1c_5(x-1)^2+c_2c_4(x-1)(2-x)+c_2c_5(x-1)^2+c_3c_4(2-x)^2+c_3c_5(x-1)(2-x)
$ - (c_5(2-x)+c_6(x-1))=H(x)\times(x-1)(2-x)
$ = (c_1c_4+c_2c_4+c_3c_5)(x-1)(2-x)+(c_1c_5+c_2c_5)(x-1)^2+c_3c_4(2-x)^2
$ - (c_5(2-x)+c_6(x-1))=H(x)\times(x-1)(2-x)
$ = (c_1c_4+c_2c_4+c_3c_5)+(c_1c_5+c_2c_5)(x-1)/(2-x)+c_3c_4(2-x)/(x-1)
$ - (c_5/(x-1)+c_6/(2-x))=H(x)
L(x), R(x), O(x), P(x), T(x), H(x)の次数について
この$ L(x), R(x), O(x)の次数はd-1になる。
これは$ L'_i, j, 1 \le j \le dのベクトルを考えた時に、d=2のときは(1, 0), d=3の時は(1, 0 ,0)となり、d=kの時は(1, 0, 0, ....,0)となる。つまり、d個の要素を持つベクトルになる。
このベクトルを満たす式を考えた時、まず全てが1の場合はL(x)=1になる。また全てが０の時はL(x)=0である。それ以外の場合は0の個数がそのままxの次数となる。
d=2の時であれば、(1, 0)であれば$ L(1)=1, L(2)=0より$ L(x)=(2-x)であり、(0.1)の時は$ L(1)=0, L(2)=1より$ L(x)=(x-1)である。
d=3の時は(1,0,0)であれば$ L(1) = 1, L(2)=0, L(3)=0を満たす必要があるので、$ L(x)=(2-x)(3-x)/2である。
つまり、$ L(x), R(x), O(x)の最大の次数は0がd-1個ある時だけである。ちなみに、(1,1,0)の時のL(x)は(1,0,0)のL(x)と(0,1,0)のL(x)を加算して求められる。
でもzcashのブログだと最大dってなってる。まぁベクトルの要素が全て0の時でも多項式作ると次数dの式ができるのでそれを含めてるのかな？
なので、$ P(x)の次数は$ P(x)=L(x) \times R(x)-O(x)より、最大でも2dとなる。
次に、$ T(x)の次数は全ての$ 1\le x \le dのxに置いて0になる必要があるため、$ T(x)=(x-1)(x-2)(x-3)...(x-d)となる。つまり$ T(x)の次数は最大でdである。
以上のことから、$ H(x)の次数は$ P(x)=H(x)\times T(x)より、最大でも$ 2d - d= dとなる。
河合くんブログの第２ステップ、Zcashブログのパート３、４と6で説明しているveirifiableの話
QAPで変換した多項式だと$ a \times b-c=E(T(x)) \times dを満たすa,b,c,dの組みであれば検証を通っちゃう。なので、実際はいろんな値を提出させる必要がある。つまりここまでだとまだインタラクティブなゼロ知識
次はこれをノンインタラクティブにするっていう話
キーワードはクソ馬鹿でかい数の計算に変換しちゃえば、たまたま当たったっていうのが無視できるよね。ってこと
zcashのパート６にある多項式$ F=L+X^{d+1}R+X^{2(d+1)}Oは違う値の足し算にするための係数っぽい。
L, R, Oの次数は最大でもdになる。なので、Lの取りうるXの次数は最大dまで、Rに$ X^{d+1}をかけるので$ X^{d+1}RがとるXの次数はd+1*dで2d+1になる。$ X^dと$ X^{2d+1}だとあらゆるXで係数がなんであれ値がかぶることはなくなる。ってことかな。$ Oも同様
2018/12/04時点の理解
証明書作成のフェーズでは$ E_1(P(s)), E_2(\alpha P(s))を計算する必要がある。
証明者は$ E(P(x))=E(H(x) \times T(x))を満たす$ E(L(x)), E(R(x)), E(O(x)), E(H(x))を提出すればいいのだけど、これは$ a \times b - c = E(T(x) \times dを満たす適当な$ a, b, c, dを提出できてしまう。つまり$ L(s), R(s), O(s)を生成するための元の問題を知らなくても検証を通る値を提出できてしまう。これだと困るので$ a,b,c,dが紛れ当たりするのを無視できる確率に下げるための変換を行う。
つまり$ 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)の一時結合。
自明ではあるが、次の通りにまとめられる。
$ \sum_{i=1}^{n}(L_i(s)+s^d R_i(s)+s^{2d}O_i(s))
$ = (L_1(s)+s^d R_1(s)+s^{2d}O_1(s)) + (L_2(s)+s^d R_2(s)+s^{2d}O_2(s)) + ... + (L_n(s)+s^d R_n(s)+s^{2d}O_n(s))
$ = (L_1(s)+L_2(s)+...+L_n(s))+s^d(R_1(s)+R_2(s)+...+R_n(s))+s^{2d}(O_1(s)+O_2(s)+...+O_n(s))
$ = \sum_{i=1}^n L_i(s)+s^d\sum_{i=1}^nR_i(s)+s^{2d}\sum_{i=1}^nO_i(s)
2018/12/05時点の理解
次数dの多項式があった時、別の同じ次数dの多項式と交わる点は最大でもd個まで。なので交わる点がd+1個であればほぼ確実に同じ関数。文字だとよくわからないけど図を書いたらすごく当たり前だった。
https://gyazo.com/5631a2a28d52db7ae31c2047d648d536
なので１点だけ調べるというのは、多分全く同じ多項式だと全ての点で一致するので、この時調べる点をすごくでかい$ \mathbb{F}_pの中から選ぶとするならそのうちd個のたまたま一致しちゃう点が選択される確率はすごい低いってことか。まぁここはあんまり本質ではないのでそこまで気にしなくても良さそう。 よく考えるとゼロ知識証明の性質を表すコアな定義だと思うので重要かも。
zcashブログパート４で述べているd-KCAの話
BobとAliceはある多項式、$ y=3x^2+2x+5 を知っている。この状態で、BobはAliceがこの多項式を知っているかを知りたい（ゼロ知識証明）。
なので、Bobは$ s, \alphaを決めた上で、Aliceに$ (s^0, s^1, s^2), ( \alpha s^0, \alpha s^1, \alpha s^2)を送る。
具体的に$ s=2, \alpha=10として考える。この場合はBobがAliceに提示する集合は(1, 2, 4), (10, 20, 40)となる。ただし、実際は有限体$ \mathbb{F}_p上の数なので、$ mod_pされることに注意。ここではわかりやすくするためにmodは考えない。
AliceはBobから受け取った数を一次結合する。つまり加算していく。これはつまり、$ s^0+s^1+s^2 を作るということである。
さらにAliceは元の問題である$ y=3x^2+2x+5を知っているので、係数$ y=c_0s^0+c_1s^1+c_2s^2とすると、$ c_0=5, c_1=2, c_2=3であることを知っているということである。
なので、これらを組み合わせると、Aliceは$ (y, \alpha y)を求めることができる。具体的に値を代入すると、$ y=5+2\times2+3\times4=21, \alpha y=5\times10+2\times20+3\times40=210となる。
Bobはこの2つの値$ (y, \alpha y)を自分が知っている多項式式$ P(s), \alpha P(s)の結果と一致するかを検証する。
これは、つまりある1つの点$ x=2について検証を行なっているだけである。が、この時の点sを十分に大きな$ \mathbb{F}_pから選ぶことで、偶然一致する確率は無視できるほど小さくなるということである。同じ次数dの違う多項式であれば、交わる点はたかだかd個しかないからである。