多項式コミットメントを用いた有用な証明ガジェット
今回は、ZK-SNARKの構成要素の1つである「適切なIOP(Interactive Oracle Proof)」のうち、「PLONK」と呼ばれるプロトコルを学ぶために必要な事項を確認していきます。
前提の確認
$${f \in {\mathbb F}_p^{\le d}[X]}$$で$${f \ne 0}$$の場合、以下が成立します。(多変数でも同様)
$${for r \Leftarrow {\mathbb F}_p : Pr[f(r)=0] \le d/p}$$
例えば、$${p \thickapprox 2^{256}}$$、$${d \le 2^{40}}$$の場合を考えると$${d/p \thickapprox 1/{2^{216}}}$$となり、有限体$${\mathbb F_p}$$から選んだ$${r}$$が$${f(r)=0}$$を満たす確率は、限りなく0に近いことがわかります。
これは裏を返すと、有限体$${\mathbb F_p}$$から選んだ$${r}$$で
$${f(r)=0}$$
となる場合は、$${f}$$がほぼ確実にゼロ多項式であると見なせるということです。(ゼロ多項式とは全ての係数が0である多項式のことを指します)
このことを利用すると、$${f, g \in {\mathbb F}_p^{\le d}[X]}$$に対して、以下のことが成り立つことが言えます。
$${for r \Leftarrow {\mathbb F}_p : if f(r) = g(r) then f=g}$$
これは$${f(r)-g(r)=0}$$が成り立つ時、$${f-g}$$という多項式が$${r}$$で0になると言い換えることができるため、先ほどの①から$${f-g=0}$$がほぼ確実にゼロ多項式であることがわかり、$${f=g}$$となります。
ここまでは、「多項式同士が等しいかどうかの検査は、1つのランダムな点での評価だけでほぼ確実な判断できる」ということを確認しました。(有限体の位数や多項式の次数の選び方は注意)
証明ガジェット
次に、Poly-IOP(Polynomial Interactive Oracle Proofs)を用いて解決できるタスクを3つ見ていきます。
・ゼロテスト
多項式$${f}$$が、集合$${H}$$の全ての点で0になるか(ゼロ多項式であるか)を証明
・総和の確認：$${{\sum_{a \in H}}f(a)=b}$$
集合$${H}$$の全ての点での$${f}$$の値の総和がbに等しいことを証明
・積の確認：$${{\prod_{a \in H}}f(a)=c}$$
集合$${H}$$の全ての点での$${f}$$の値の積がcに等しいことを証明
以下
・原始k乗根$${w \in {\mathbb F}_p}$$を用いた集合$${H}$$
$${H := {1, w, w^2, …, w^{k-1}} \subseteq {\mathbb F}_p}$$
(原始k乗根とは、$${w^k=1}$$を満たす数のことを指します。)
・多項式$${f \in {\mathbb F}_p^{\le d}[X]}$$ ($${d \geq k}$$)
・$${b,c \in {\mathbb F}_p}$$
を用いて、それぞれどのように証明されるのかを確認します。
ゼロテスト
ここでは、集合$${H}$$の全ての点で多項式$${f}$$が0になるか(ゼロ多項式であるか)を確かめます。これは$${H=\{1, w, w^2,…,w^{k-1}\}}$$のすべての要素を解に持つ場合を調べればよく、$${X^k-1}$$を因数に持つかどうかに言い換えることができます。($${w^k=1}$$のため)
つまり、$${f(X)/(X^k-1)=q(X)}$$と表現できる$${q(X)}$$が存在することに帰着できます。
① $${f(X)/(X^k-1)=q(X)}$$を計算する
② $${q(X)}$$をコミットする
③ ランダムに選択した点$${r}$$を共有する
④ 点$${r}$$での$${q(X), f(X)}$$の評価を共有する
⑤ $${f(r)=q(r)(r^k-1)}$$の成立を確認し、受理/拒否を判断する
総和の確認
$${H := {1, w, w^2, …, w^{k-1}} \subseteq {\mathbb F}_p}$$、$${{\sum_{a \in H}}=1}$$を満たす集合$${H}$$上の全ての点での$${f}$$の値の総和がbに等しいことを証明します。
まず、次の条件を満たすような多項式$${t \in {\mathbb F}_p^{\le k}[X]}$$を用意します。
$${t(1)=f(1)}$$
$${t(w^s)= {\sum_{i=0}^s}f(w^i)}$$ ($${s=1,2,…,k-1}$$)
このとき、それぞれの$${t(w^s)}$$を書き下すと以下のようになります。
$${t(w)=f(1)+f(w)}$$
$${t(w^2)=f(1)+f(w)+f(w^2)}$$
:
$${f(w^{k-1})=f(1)+f(w)+…+f(w^{k-1})={\sum_{a \in H}}}$$
以上より、t(X)が累積和の構造を持っていることの補題として、以下の条件を利用します。
[補題]
1. $${f(w^{k-1})=1}$$
2. $${t(w・X)=t(X)+f(t・X)}$$
1,2を満たすとき、$${{\sum_{a \in H}}=1}$$が成り立つ。
この補題2について、すべての項を左辺に集めると
$${t(w・X)-\{t(X)+f(t・X)=0\}}$$ …(*)
(*)はある式が0となることの証明と捉えると、先ほど確認したゼロテストを使用することができます！
よって、補題は
1. $${f(w^{k-1})=1}$$
2'. $${t(w・X)-t(X)-f(t・X)=0}$$
に帰着できます。
① 前提条件を満たすような多項式$${t(X)}$$を構築し、$${t_1(X)}$$を定義する
② $${f(X)/(X^k-1)=q(X)}$$を計算する
③ 多項式$${t,q}$$をコミットする
④ ランダムに選択した点$${r}$$、$${wr}$$、$${w^{k-1}}$$を共有する
⑤ ④で共有された各点の多項式$${t}$$上での評価を共有する
⑥ ④で共有された2点の多項式$${q}$$上での評価を共有する
⑦ 累積和の補題である$${t(w・X)-t(X)-f(t・X)=q(r)(r^k-1)}$$、$${f(w^{k-1})=1}$$の成立を確認し、受理/拒否を判断する
積の確認
$${H := {1, w, w^2, …, w^{k-1}} \subseteq {\mathbb F}_p}$$、$${{\prod_{a \in \H}}=1}$$を満たす集合$${H}$$上の全ての点での$${f}$$の値の積が1に等しいことを証明します。
まず、次の条件を満たすような多項式$${t \in {\mathbb F}_p^{\le k}[X]}$$を用意します。
$${t(1)=f(1)}$$
$${t(w^s)= {\prod_{i=0}^s}f(w^i)}$$ ($${s=1,2,…,k-1}$$)
このとき、それぞれの$${t(w^s)}$$を書き下すと以下のようになります。
$${t(w)=f(1)・f(w)}$$
$${t(w^2)=f(1)・f(w)・f(w^2)}$$
:
$${f(w^{k-1})=f(1)・f(w)・…・f(w^{k-1})={\prod_{a \in H}}}$$
以上より、t(X)が積の構造を持っていることの補題として、以下の条件を利用します。
[補題]
1. $${f(w^{k-1})=1}$$
2. $${t(w・X)=t(X)・f(t・X)}$$
1,2を満たすとき、$${{\prod_{a \in H}}=1}$$が成り立つ。
この補題2について、すべての項を左辺に集めると
$${t(w・X)-t(X)・f(t・X)=0}$$ …(*)
(*)はある式が0となることの証明と捉えると、最初に確認したゼロテストを使用することができます！
よって、補題は
1. $${f(w^{k-1})=1}$$
2'. $${t(w・X)-t(X)・f(t・X)=0}$$
に帰着できます。
① 前提条件を満たすような多項式$${t(X)}$$を構築し、$${t_1(X)}$$を定義する
② $${f(X)/(X^k-1)=q(X)}$$を計算する
③ 多項式$${t,q}$$をコミットする
④ ランダムに選択した点$${r}$$、$${wr}$$、$${w^{k-1}}$$を共有する
⑤ ④で共有された各点の多項式$${t}$$上での評価を共有する
⑥ ④で共有された2点の多項式$${q}$$上での評価を共有する
⑦ 累積和の補題である$${t(w・X)-t(X)・f(t・X)=q(r)(r^k-1)}$$、$${f(w^{k-1})=1}$$の成立を確認し、受理/拒否を判断する
ここまで見てきた
・ゼロテスト
・総和の確認
・積の確認
はいずれも有用なガジェットとして、次回以降見ていくPlonkなどにも登場します。
最後に
今回は、ZK-SNARKの構成要素である「適切なIOP(Interactive Oracle Proof)」のうち、「Plonk」と呼ばれるプロトコルを学ぶために有用なガジェットを確認しました。次回はついに「Plonk」について見ていきます。ぜひチェックしてください！
[参照]
この記事は、『ZK Hack Whiteboard Session1 Module3: Building a SNARK, pt2 by Dan Boneh』の動画の内容を編集し、図や説明を加えたものです。
ZK Hackとは、ZKに関するビデオやニュースレターの発信や、イベントを開催するコミュニティです。今回のビデオは、Stanford大学のDan Boneh教授によるSNARKの入門動画になります。