ZK-SNARKs 多項式への変換
式の分割
例えば
$ x^3 +x + 5 == 35
をみたす$ xの解（この場合は3) を知っていることを証明したい。
上の式を、以下のように分割する。
code:steps
sym_1= x * x
y = sym_1 * x
sym_2 = y + x
~out = sym_2 + 5
このように分割すると、上の問題は、「stepsの全ての式をみたすような変数群 x, sym_1, y, sym_2, y, ~out (ただし~out=35) を知っていることを証明する」という風に置き換えられる。
分割した式をベクトルで表現
1およびstepsの式で出てくる各変数を要素にもつベクトルsを作る。
$ \bold c=(1, x, ~out, sym_1, y, sym_2)とおくと、例えば、$ \bold L(0) =(0,1,0,0,0,1), \bold R(0)=(0,1,0,0,0,0), \bold O(0)=(0,0,0,1,0,0)のとき、$ \bold L(0) \cdot \bold c * \bold R(0) \cdot \bold c - \bold O(0) \cdot \bold c = 0という式は、 sym_1= x * x に対応する。($ \cdot は内積)
まとめると、
code:a
とおいたとき、$ \bold L(i) \cdot \bold c * \bold R(i) \cdot \bold c - \bold O(i) \cdot \bold c = 0がそれぞれstepsの i 番目の式に対応する。$ (i = 0,1,2,3 )
ベクトルでの表現を多項式に変換
ここで、$ X=iの時に$ \bold L_X(X) = \bold L(i), \bold R_X(X) = \bold R_X(i) ,\bold O_X(X)= \bold O(i)を満たすような、多項式を成分に持つベクトル$ \bold L_X, \bold R_X, \bold O_Xを求めたい。
たとえば、$ \bold L_X の第0成分$ L_0(X)は、X=0,1,2,3のときに、それぞれ$ L_0(X) = 0,0,0,5 となって欲しいので、
$ L_0(X) = \frac{5}{6} X(X-1)(X-2)
また、$ L_Xの第1成分は、X=0,1,2,3のときに、それぞれ$ L_0(X) = 1,0,1,0となって欲しいので、
$ L_1(X) = \frac{1}{-6}(X-1)(X-2)(X-3) + \frac{1}{-2}X(X-1)(X-3)
第2-第5成分についても計算して、
$ L_2(X) = 0
$ L_3(X) = \frac{1}{2}X(X-2)(X-3)
$ L_4(X) = \frac{1}{-2}X(X-1)(X-3) + \frac{1}{6}X(X-1)(X-2)
$ L_5(X) = 0
と、$ \bold L_Xの各成分の多項式が得られた。
$ \bold R_X, $ \bold O_Xについても同様に求められる。stepsの式は全部で4つなので、各成分は全てXの3次以下の多項式になっている。
上で定義したベクトルを用いて、スカラーのXの多項式L(X), R(X), O(X)を
$ L(X) = \bold L_X \cdot \bold c = \sum_{j=0}^{5} c_j L_j(X)
$ R(X) = \bold R_X \cdot \bold c = \sum_{j=0}^{5} c_j R_j(X)
$ O(X) = \bold O_X \cdot \bold c = \sum_{j=0}^{5} c_j O_j(X)
のように定義する。
これらを用いて多項式P(X)を
$ P(X) = L(X) * R(X) - O(X)
のように定義する。
もし、cがstepsの全ての式を満たすような値であれば（この場合はs=(1,3,35,9,27,30)であれば）
$ \bold L(i) \cdot \bold c * \bold R(i) \cdot \bold c - \bold O(i) \cdot \bold c = 0 が $ i = 0,1,2,3について成り立ので、このcで生成した多項式P(X)は$ X = 0,1,2,3で P(X)=0 を満たす。
言い換えると、cがstepsの全ての式を満たすような値であれば、cの成分を係数に含む多項式P(X)はX(X-1)(X-2)(X-3)で割り切れる。
問題の変換
$ x^3 +x + 5 == 35 を満たすx (ここでは x=3)を知っていることを証明する
↓
sの成分を係数に含む多項式P(X)がX(X-1)(X-2)(X-3)で割り切れるようなc(ここでは c=(1,3,35,9,27,30) )を知っていることを証明する。
参考