概要

zk-SNARKs に関する ELECTRIC COIN CO. の解説記事に簡単に補足をしながら紹介するシリーズ Part 4 です。

Part 4 では Part 1, 2, 3 に基づいて、検証可能な多項式の盲検のプロトコルを構築します。次の Part 5 ではこのプロトコルを用いて SNARK を構築する話に移ります。

Blind Evaluation of Polynomials Verifiable

対応する記事

Explaining SNARKs Part IV: How to make Blind Evaluation of Polynomials Verifiable

一言でいうと

Part 2 と同様、アリスが多項式 $P$ を持っていて、ボブが $\mathbb{F}_p$ からランダムに選択した $s$ を持っているとします。

検証可能な多項式の盲検 のプロトコルでは、ボブが $E(P(s))$ の値を知ることができると同時に、以下の 1, 2 が満たされます。

盲目性: アリスは $s$ 知ることはありません (そしてボブは $P$ を知ることはありません）
検証可能性: アリスが $P$ を元に算出した $E(P(s))$ を送っているかをボブは検証できます

Part 2 のプロトコルは 1 番目の盲目性を提供しましたが、2 番目の検証可能性を提供しませんでした。検証可能性を得るには Part 3 で提示された KCA (係数知識の仮設) の拡張バージョンが必要です。

検証可能性と盲目性はどちらも、アリスに $s$ を見ることなく多項式 $P$ を決めさせることに役立ちます¹。このことはある意味で、アリスに "チャレンジポイント" $s$ 無しに "回答となる多項式" $P$ を返す約束をさせるようなものです。この点については今後の Part でより明らかになります。

拡張 KCA

Part 3 の振り返り

Part 3 で定義した KCA は基本的に次のようなことを主張します。もしボブがアリスに $\alpha$-ペア $(a, b = \alpha\cdot a)$ を送り、アリスがそれとは別の $\alpha$-ペア $(a', b')$ を生成したとします。するとアリスは $a' = c \cdot a$ のような $c$ を知っていることになります。言いかえると、アリスは $a'$ と $a$ の関係性を知っています。

KCA の拡張方針

Part 3 ではボブは 1 つの $\alpha$-ペアを送りましたが、拡張 KCA では複数の $\alpha$-ペアを送ります。そしてアリスは送られた複数のペアを同時に使って別の $\alpha$-ペアを生成します。複数のペアを同時に使う方法は、Part 2 で説明した線形結合です。

ここでは、まず $\alpha$-ペアを 2 つ使うケースで考えてみます。

ボブはアリスに 2 つの $\alpha$-ペア $(a_1, b_1), (a_2, b_2)$ を送ります。アリスは $c_1, c_2 \in \mathbb{F_p}$ を選び、$(a', b') = (c_1 \cdot a_1 + c_2 \cdot a_2, c_1 \cdot b_1 + c_2 \cdot b_2)$ を計算します。 $a'$ がゼロでなければこのペアは $\alpha$-ペアとなります。これが $\alpha$-ペアであることは以下のように確認できます。

$b' = c_1 \cdot b_1 + c_2 \cdot b_2 = c_1 \alpha \cdot a_1 + c_2 \alpha \cdot a_2 = \alpha (c_1 \cdot a_1 + c_2 \cdot a_2) = \alpha \cdot a'$

一般化

ボブがアリスに d 個の $\alpha$-ペア $(a_1, b_1),...,(a_d, b_d)$を送るとします。するとアリスは、 $c_1,...,c_d \in \mathbb{F_p}$ において $(a', b') = (\sum_{i=1}^{d} c_i a_i, \sum_{i=1}^{d} c_i b_i )$ と定義することで、与えられた d 個のペアの線形結合を取ることができます。

言い換えると、アリスがこの方法で $\alpha$-ペアを生成する場合、アリスは $a'$ と $a_1,...,a_d$ の線形結合の関係を知っていることになります。つまり彼女は $a' = \sum_{i=1}^{d} c_i \cdot a_i$ となる $c_1,...,c_d$ を知っています。

拡張 KCA は、本質的にこれがアリスが $\alpha$-ペアを生成できる唯一の方法であり、彼女が生成に成功するときはいつでも $a'$ と $a_1,...,a_d$ の関係を知っている、ということを述べています。

もう少しフォーマルに書くと

サイズ $p$ の群 $G$ において生成子 $g$ の演算を Part 3 のように足し算的に記述するとして、$G$ における冪指数 $d$ での係数知識の仮設 (d-KCA)² は以下のようになります。

d-KCA: ボブがランダムに $\alpha \in \mathbb{F_p^*}$ と $s \in \mathbb{F_p}$ を選び、アリスに $(g, \alpha \cdot g), (s \cdot g, \alpha s \cdot g),...,(s^d \cdot g, \alpha s^d \cdot g)$ の $\alpha$-ペアを送り、アリスが別の $\alpha$-ペア $(a', b')$ を出力したとする。その時アリスは(無視できる確率を除き)、$\sum_{i=0}^{d} c_i s^i \cdot g = a'$ となるような $c_0...,c_d \in \mathbb{F_p}$ を知っている。

この d-KCA では、ボブは任意の $\alpha$-ペアのセットを送るのではなく、ある特定の "多項式構造" のものを送ることに注意してください。これは以下のプロトコルで役立ちます。

検証可能な多項式の盲検のプロトコル

ここまでの説明で、ようやくプロトコル構築の準備が整いました。

上記の $G$ の生成子 $g$ を用いた $E(x) = x \cdot g$ を HH³ とします。簡単のため、この $E$ を利用したプロトコルを示します。

ボブはランダムに $\alpha \in \mathbb{F_p^*}$ を選び、アリスに $g, s \cdot g,..., s^d \cdot g$ (これらは $1, s,..., s^d$ の HH の計算結果)と、 $\alpha \cdot g, \alpha s \cdot g,..., \alpha s^d \cdot g$ (これらは $\alpha, \alpha s,..., \alpha s^d$ の　HH の計算結果) を送ります。
アリスは受け取った情報を使って $a = P(s) \cdot g$ と $b = \alpha P(s) \cdot g$ を計算して両方をボブに送ります。
ボブは $b = \alpha \cdot a$ となることを確認して、等式が成り立つ場合のみ受け入れます。

ステップ 2 で

$a = P(s) \cdot g$ と $b = \alpha P(s) \cdot g$ を計算して

と書かれていますが、アリスは $s$ も $\alpha$ も知らないため、上記の式を直接計算出来ないことに注意してください。

多項式 $P$ の係数が与えられると、$P(s) \cdot g$ は $g, s \cdot g,..., s^d \cdot g$ の線形結合になり、$\alpha P(s) \cdot g$ は $\alpha \cdot g, \alpha s \cdot g,..., \alpha s^d \cdot g$ の線形結合になります。Part 2 のプロトコルと同様に、アリスはボブから受け取った情報から、$P$ を使ってこれらの値を計算することができます。

次に、d-KCA によって、アリスが $b = \alpha \cdot a$ となる $a, b$ を送った場合、ほぼ確実に彼女が $a = \sum_{i=0}^{d} c_i s^i \cdot g$ となる $c_0,...,c_d \in \mathbb{F_p}$ を知っていることが言えます。この場合、アリスが知っている多項式が $P(X) = \sum_{i=0}^{d} c_i \cdot X^i$ の場合は、 $a = P(s) \cdot g$ となります。言い換えると、ボブがステップ 3 で受け入れた時(つまりは等式が成立することが確認できた時)、アリスが $P$ を知らないという可能性は無視できる、ということです。

まとめ

お疲れさまでした！
前回までの Part の内容を元に、やや駆け足気味でしたが d-KCA を用いて多項式の検証可能な盲検のプロトコルを開発することができました。
次の Part 5(From Computations to Polynomials(計算から多項式へ)) では、ここで構築した内容が SNARK 構造内でどのように機能するかを見ていきます。

実際にはアリスは $P$ を決める前に $s$ についてのいくらかの情報(例えば $s,...,s^d$ それぞれの HH 計算値)を得ることができるため、正式な証明では状況はもう少し込み入っています ↩
d-KCA は Jens Groth の論文で紹介されているとのこと。 ↩
Part 1 で解説されている準同型隠蔽のことです。 ↩