ZK-SNARKs 多項式のブラインド評価を検証可能にする方法
要約
ブラインド評価：Aliceが多項式Pと次元dが与えられている状況下でBobが持っているsを知らずしてE(P(s))を求めること。
ここではZK-SNARKs 多項式のブラインド評価に見たようにAliceはE(P(s))を算出可能だがAliceがE(P(s))をBobに送ることまでは保証されていない。E(P(s))の結果を知ってたから送っただけで、本当はsとPを使って計算していないかもしれない。 ZCashチームによると、Knowledge of Coefficient Test (a.k.a KC Test)と呼ばれるものでAliceがちゃんと多項式を使って計算したかを確かめることができる。 多項式
Aliceが多項式Pをdegree dで持っていると仮定する。
$ P(x) = a_0 + a_1\cdot X + a_2\cdot X^2 + ...... + a_d\cdot X^d
Bobは彼がランダムで選んだ$ s \in \mathbb{F}_pを持っているとする。
上記の状態で、Bobが$ E(P(s))を当てるためにはどうすればよいか？
Aliceは$ sをしらず、Bobは$ Pをしらない。（ブラインド性）
Aliceが$ E(P(s))を送らずBobが$ sから$ E(P(s))を見つける可能性は無視できる。（検証性）
上記の条件が揃う時、verifiable blind evaluation of a polynomialという。
Knowledge of Coefficient Assumption (KCA)
BobがAliceに$ \alphaペア$ (a,b) = (a,\alpha*a)を送る。
それを基にAliceは$ \alphaペア$ (a', b')を作成する。
Aliceは$ a' = c*aを計算するための$ c($ aと$ a'の比率を)を知っていることをボブに対して証明できる。
ここから前回の発展。
BobがAliceに複数の$ \alphaペアを送るとする。これを$ (a,b),(a_1,b_1),......(a_d, b_d)とする
Aliceは$ \alphaペアを受け取ったあと他の$ \alphaペアである$ a', b'を作成する
$ (a',b') = (c_1*a_1 \cdot c_2*a_2,\cdot c_1*b_1+c_2*b_2)も$ \alphaペア
$ b' = c_1*b_1 \cdot c_2*b_2 = c_1*\alpha*a_1 \cdot c_2*\alpha*a_2 = \alpha*(c_1*a_1\cdot c_2*a_2) = \alpha*a'
検証可能なブラインド評価プロトコル
⚠️先ほどまでは$ E(x) = g^x\ ({\rm mod}\ p)と表記していた。
Bobは$ \alpha を選び、$ E(1),E(s),E(s^2),...E(s^d)および$ E(\alpha),E(\alpha*s),E(\alpha*s^2),...E(\alpha*s^d)をAliceに送る。
Aliceは、$ a=E(P(s))および$ b=E(P(\alpha*s))を、送られたデータとP保持しているPを元に計算することができる。これをBobに送る。
Bobは、$ b = \alpha * aであれば、Aliceが多項式を用いて計算したと検証できる。