多項式コミットメント
今回は、ZK-SNARKの構成要素である「関数を用いたコミットメントスキーム」と「適切なIOP(Interactive Oracle Proof)」のうち、「関数を用いたコミットメントスキーム」の代表例である多項式コミットメントについてみていきます。
多項式コミットメント
前回の内容の復習です。
多項式コミットメントは、$${\mathcal{F} = \mathbb{F}_p^{\le{d}}[X]}$$に対するコミットメントです。証明者は、ある1変数多項式$${f \in \mathbb{F}_p^(\le{d})[X]}$$に対してコミットを行います。その後、ある公開された値$${u}$$に対して$${f(u)=v}$$が成り立つことを証明するという流れです。
生成される証明$${\pi}$$のサイズと検証時間は$${o_{\lambda}(logd)}$$となることから、多項式のサイズ(次数)が大きくても検証コストが比較的抑えられることが確認できます。
KZGコミットメント
1変数の場合
KZGコミットメントの大まかな流れは、以前見た多項式コミットメントと変わらず
① 公開パラメータの生成
② コミットメントの生成
③ 評価点$${u \in {\mathbb F}_p}$$の共有
④ 証明$${\pi}$$の生成と共有
⑤ 検証$${\to}$$受理 or 拒否
です。それでは、順番に見ていきましょう。
① 公開パラメータの生成：$${setup(\lambda)\to pp}$$
ここで使用する有限群を、位数$${p}$$、$${\mathbb{G}:= {0, G, 2・G, …,(p-1)・G}}$$と置きます。
(i) ランダムな値$${\alpha \in {\mathbb F}_p}$$を有限群$${\mathbb{G}}$$に対して作用させる
$${pp = (G,{\alpha}・G, {\alpha}^2・G, …, {\alpha}^d・G)}$$
$${ = (H_0, H_1, H_2 …, H_d)}$$
(ii) $${{\alpha}}$$を消去する
$${\alpha}$$は秘密の値であるため適切に削除される必要があり、これはTrusted Setupの要件を満たすためです。次回以降、なぜこれが必要なのか、どのようにして安全性に寄与するのかを見ていきます。
② コミットメントの生成：$${commit(pp,f) \to com_f}$$
コミットメントする関数を$${f(X)=f_0+f_1X+…+f_dX_d}$$と置きます。$${com_f := f({\alpha})・G }$$
$${ = f_0・G+f_1{\alpha}・G+…+f_d{\alpha}^d・G }$$
$${ = f_0・H_0+f_1・H_1+…+f_d・H_d}$$
③ 評価点$${u \in {\mathbb F}_p}$$の共有
検証者から証明者に、証明を生成するための$${u \in {\mathbb F}_p}$$を共有します。
④ 証明$${\pi}$$の生成と共有
証明$${\pi}$$は$${\pi := com_q}$$で計算しますが、証明の生成に利用する関数$${q(X) \in {\mathbb{F}}_p[X]}$$は、$${q(X)={f(X) - v}/(X-u)}$$とします。これは以下のように導出されます。
③で検証者が選んだ$${u}$$に対して$${f(u)=v}$$とおくと、$${f(u)-v=0}$$から、$${f(X)-v}$$は$${u}$$を因数に持つことがわかります。
つまり、$${f(X)-v =q(X)(X-u)}$$を満たすような$${q \in {\mathbb{F}}_p[X]}$$が存在する、という流れから、証明の生成に利用される関数$${q(X) \in {\mathbb{F}}_p[X]}$$は定義されます。
⑤ 検証$${\to}$$受理 or 拒否
検証者は、②④で証明者から共有された$${u, v, com_f}$$を利用して検証します。
ここで$${f(u)=v}$$を式変形していきます。
先ほどの通り$${f(u)-v=0}$$から$${f(X)-v=0}$$は$${X=u}$$を因数にもつので
$${f(X)-v=(X-u)q(X)}$$
Xに$${\alpha}$$を代入して
$${f(\alpha)-v=(\alpha-u)q(\alpha)}$$
両辺に$${G}$$を作用させると
$${com_f - v・G = (\alpha-u)com_q}$$
つまり、$${f(u)=v}$$を確かめることと$${com_f - v・G = (\alpha-u)com_q}$$を確かめることは同義であるということがわかります。
しかし、この式をそのまま検証者が計算することはできません！それは、$${\alpha}$$は秘密の値で検証者が知ることができない値だからです。
実は、ここでペアリングという計算手法が登場します。これを使用することで、検証者は秘密の値$${\alpha}$$について知らないまま上記の式を計算することができます。次回以降詳しく見ていくので、ここでは「ペアリングによって計算可能である」ということだけ抑えてください。
一般化した場合
(i) 変数の種類
先ほど確認した例では、$${f(X)=f_0+f_1X+…+f_dX^d}$$のような1変数でした。これをk変数の多項式$${f(x_1,x_2,…,x_k)}$$のように拡張した場合、証明サイズはk個のグループ要素が証明に必要になります。
(ii) コミットメント数
先ほど確認した例では、$${f}$$に対してコミットメント$${com_f}$$のように、1つの多項式に対して1つのコミットメントでした。これを複数の多項式$${f_1,f_2,…,f_n}$$に対して、それぞれのコミットメント$${com_{f_1}, com_{f_2}, …, com_{f_n}}$$を生成する場合、証明者が成立を確かめる式は
$${f_i(u_{i,j})=v_{i,j}}$$であるため、一括して検証できることで効率が向上します。
Doryコミットメント
ここまで見てきたKZGコミットメントの課題を解決するために設計されたDoryコミットメントについて、KZGと比較しながら特徴を確認します。
セットアップ時に信頼が担保できる環境であれば、検証時間などの効率も良いKZGコミットメントが適していますが、そうでない場合は多少効率が低下してもDoryコミットメントが有効です。
ここまでは、SNARKの構成要素の1つである「多項式コミットメントスキーム(PCS)」について確認しました。次に、もう一つの構成要素である「PIOP (Polynomial Interactive Oracle Proofs)」について見ていきます。
PIOP
多項式を用いた対話型のオラクル証明システムを指すPIOPでは、以下の特徴があります。
・対話型であること
今までも登場した通り、証明者と検証者で何度かやり取りを行ってから検証に入る「対話型」に分類されます。
・検証者が多項式へのオラクルアクセスを持つ
証明者がコミットした多項式に対して任意の点での評価を、検証者が得られるという仮定のもとで、多項式IOPは成立します。ここで重要なことは、多項式自体を完全に知っているわけではないが、必要な評価点での値を問い合わせることができるという点です。
次に、一般的なPIOPの各ステップを詳しく見ていきます。(プロトコルによって違いはありますが、一般化したものを図式化しています)
① 公開パラメータの生成
② 1個目のコミットメント生成
証明者は、$${S_p, x, w}$$を用いて最初のコミットメントを生成します。
③ 1個目のランダムな値を選択&共有
検証者は、有限体$${{\mathbb F}_p}$$からランダムに選択した値を証明者に渡します。
④ 2個目のコミットメント生成
証明者は、③で受け取った$${r_1}$$を含めた$${r_1, x, w}$$を用いて、2個目のコミットメントを生成します。
⑤ t-1個目のランダムな値を選択&共有
検証者は、有限体$${{\mathbb F}_p}$$からランダムに選択した値を証明者に渡します。
⑥ t個目のコミットメント生成
証明者は、③で受け取った$${r_{t-1}}$$を含めた$${r_{t-1}, x, w}$$を用いて、t個目のコミットメントを生成します。
⑦ 検証
検証者は、
・前処理で生成した公開パラメータ$${f_0, f_{-1},…,f_{-s}}$$
・今まで受け取ったコミットメント$${f_1, f_2, …, f_t}$$
・今まで選択した値$${r_1, r_2,…,r_{t-1}}$$
・公開情報$${\boldsymbol{X}}$$
を活用し、コミットメントを検証します。
ここまで見てきたPIOPは、実際に使用するとなると対話型であることやオラクルアクセスの実現によるセキュリティの低下が問題となります。しかしそれぞれ解決に向けて、以下のようなアプローチを取ることができます。
・対話型であること $${\to}$$ Fiat-Shamir変換の活用
・オラクルアクセスを前提としていること $${\to}$$ 多項式コミットメントの活用
参照：「Fiat-Shamir Transformation of Multi-Round Interactive Proofs」
最後に
今回は、SNARKの構成要素である「多項式コミットメント」「Interactive Oracle Proof (IOP)」について確認しました。次回は、IOPの中でもPlonkと呼ばれるシステムについて見ていきます。ぜひチェックしてください！
[参照]
この記事は、『ZK Hack Whiteboard Session1 Module2: Building a SNARK, pt1 by Dan Boneh』の動画の内容を編集し、図や説明を加えたものです。
ZK Hackとは、ZKに関するビデオやニュースレターの発信や、イベントを開催するコミュニティです。今回のビデオは、Stanford大学のDan Boneh教授によるSNARKの入門動画になります。