zkSNARKs
Japanese explanation of zksnarks.
この文章の目的
snarksを理解したい
roll_upを理解したい
starksを理解したい
accumulator実装したい
プロジェクトに応用したい
References
はじめに
これを読みます。
前提条件が書かれてますが、1次式同士の足し算について$ P(x) + Q(x) = (P + Q)(x)となるのがわかること。こういう書き方であってるのかは知りませんが、あらかじめ式を足した場合と、答えを足す場合で等しくなるのは確かです。
その下にはzkSNARKsの処理のパイプラインが書かれています。
その下にはzkSNARKSはコンピューテーションをなんでも解決しない、問題をQAPという表現にする必要がある。まあループとかきつそうなのは直感的にわかりますよね。
Note that modulo (%) and comparison operators (<, >, ≤, ≥) are NOT supported
この辺までぼーっと読み進めました、四則演算と定数のべき乗ができるって書いてるのかな。
眠いので段落の最後の方から読む
We can extend the language to support conditionals (eg. if x < 5: y = 7; else: y = 9) by converting them to an arithmetic form: y = 7 * (x < 5) + 9 * (x >= 5); though note that both “paths” of the conditional would need to be executed, and if you have many nested conditionals then this can lead to a large amount of overhead.
if分表現できるけど全部実行する必要があるらしい。x<5はxが5より小さいときに1になってそれ以外0になるの??
おお、コードがあった
codeをr1csにして、それをqapにしてるっぽいことはわかった。
この辺がentry point。
問題の組み立て
例として、こういう問題を扱います。
def qeval(x):
y = x**3
return x + y + 5
これに対して qeval(x)からのQAPの組み立てと、qeval(3) = 35をqevalを知らない状態でverifyできる方法を説明します。
この検証をEVMで行うことによって、onchainで少ない検証コストで、計算結果を検証することができます。
基本的な流れは
問題->flatting->R1CS->QAP->verify(pinoccio protocol or groth16?)
ちなみにSTARKSはR1CSから違うらしい。
flattening
最初のステップは"flattening"と呼ばれます。
x = y か x = y (op) z の形に直していきます。
なんやかんやで以下の形にできます。ひとつの式での演算子の出現回数が制限されてるはず。
sym_1 = x * x
y = sym_1 * x
sym_2 = y + x
~out = sym_2 + 5
Gates to R1CS to QAP
$ A(x) * B(x) - C(x) = H(x) * Z(x)
問題の検証
基本的なこと
P(x) * k = Q(x)
a * G = A
b * G = B
楕円曲線のスカラ乗算なので、kは秘密鍵で捨てる
ここでQAPは
$ A(x) * B(x) - C(x) = H(x) * Z(x)
なのを覚えておく。
verifierは以下を計算する
G * A_1(t), G * A_1(t) * k_a
G * A_2(t), G * A_2(t) * k_a
...
ここでGはGenerator。1と同じ性質を持つ?Gの値は知られている。
some random elliptic curve point that is specified as part of the protocol
P = G * p, Q = G * q and R = G * rの時に、p*q=rである事をP,Q,Rから知れる
つまりp, q, rが秘密鍵で、P, Q, Rが公開鍵のようなもの?
$ e(P, Q) * e(G, G * 5) = 1は$ p * q + 5 = 0
e(x, y) = 2^xy
$ 2^{PQ+G*G*5}=1
$ PQ+1*1*5 = 0
tは多項式が成立するsecret point
t, k_a, k_b , k_cは捨てる必要がある。(これがあるとfake proofを作れる)
証明するために適当な点Gをとる
proverはk_a, k_b, k_cを知る必要はない、$ \pi'_a, \pi'_b, \pi'_cだけで良い
π_a = G * A(t), π’_a = G * A(t) * k_a
π_b = G * B(t), π’_b = G * B(t) * k_b
π_c = G * C(t), π’_c = G * C(t) * k_c
次のステップ
kとはまた別のbを使用する(trusted setup)
G * (A_i(t) + B_i(t) + C_i(t)) * b
e(π_a, π_b) / e(π_c, G) ?= e(π_h, G * Z(t))
元をたどると
$ 2^{\pi_a * \pi_b} / 2^{\pi_c * G} = 2^{\pi_h * Z(t)}
$ \pi_a * \pi_b - \pi_c = \pi_h * Z(t)
$ \pi_h = G * H(t)
が楕円曲線演算上は$ A * B - C = H * Zと同じ意味。
ちなみにこれはpinocchio protocolで、他にgroth16と言うのがあるらしい
ethsnarksはGroth16 Protocol (3 point only and 3 pairings)でgas削減している。 最終的な3つの検証
まず$ \pi_a' = ka * \pi_a, \pi_b' = kb * \pi_b, \pi_c' = kc * \pi_cである事をチェック
同じ係数が使われているかをチェックする。
$ e(full\pi_a + \pi_c, vk.G_2) * e(vk.G_1, \pi_b) = e(\pi_k, vk.G)
QAPが割切れる事をチェック
$ e(full\pi_A, \pi_B) = e(\pi_H, vk_z)*e(\pi_C, G)
ここで$ full\pi_A = vk_x + \pi_aです。
snarkjsのコードを読む
まずは$ full\pi_a = vk_x + \pi_aを計算する
code:js
let full_pi_a = vk_verifier.A0; for (let s= 0; s< vk_verifier.nPublic; s++) {
full_pi_a = G1.add( full_pi_a, G1.mulScalar( vk_verifier.As+1, publicSignalss)); }
full_pi_a = G1.add( full_pi_a, proof.pi_a);
QAPが割切れる事を確認する。
$ e(full\pi_A, \pi_B) = e(\pi_H, vk_z)*e(\pi_C, G)
code:js
if (! bn128.F12.equals(
bn128.pairing( full_pi_a , proof.pi_b ),
bn128.F12.mul(
bn128.pairing( proof.pi_h , vk_verifier.vk_z ),
bn128.pairing( proof.pi_c , G2.g ),
)))
以下は、$ \pi_{ap}, $ \pi_{bp}, $ \pi_{cp}が$ k\pi_a,$ k\pi_b,$ k\pi_cであることをペアリングで検証する。
code:js
if (! bn128.F12.equals(
bn128.pairing( proof.pi_a , vk_verifier.vk_a ),
bn128.pairing( proof.pi_ap , G2.g )))
return false;
if (! bn128.F12.equals(
bn128.pairing( vk_verifier.vk_b, proof.pi_b ),
bn128.pairing( proof.pi_bp , G2.g )))
return false;
if (! bn128.F12.equals(
bn128.pairing( proof.pi_c , vk_verifier.vk_c ),
bn128.pairing( proof.pi_cp , G2.g )))
return false;
同じ係数が使われているかをチェックする。
$ e(\pi_a + \pi_c, vk.G_2) * e(vk.G_1, \pi_b) = e(\pi_kp, vk.G)
code:js
if (! bn128.F12.equals(
bn128.F12.mul(
bn128.pairing( G1.add(full_pi_a, proof.pi_c) , vk_verifier.vk_gb_2 ),
bn128.pairing( vk_verifier.vk_gb_1 , proof.pi_b ),
),
bn128.pairing( proof.pi_kp , vk_verifier.vk_g )))
return false;
new hash function