知識の健全性とゼロ知識性の定義
今回は、ZK-SNARKにおける「Knowledge Soundness(知識の健全性)」と「Zero Knowledge(ゼロ知識性)」についての定義を見ていきます。
知識の健全性(Knowledge Soundness)の定義
健全性(Soundness)の定義は、3本目の記事でも見た通り
「検証者が真と判断する場合、証明者は$${C(x,w)=0}$$を満たすような$${w}$$を知っている」
ということです。
ここからは知識の健全性、つまり「know : 知っている」ことの定義について深掘りしていきます。
非形式的定義
「証明者が$${w}$$を知っていることは、証明者から$${w}$$を『extract : 抽出できる』時に成立する」
というもので、情報を取り出す/抜き取る、に近いニュアンスがあることがわかります。
形式的定義
では、形式的定義はどのようになるのでしょうか？「証明が受理された場合、その証明の裏に実際に解が存在すること」を、これを数式を用いて定義していきます。ポイントは、仮定と保証のどちらにも同じ$${10^-6}$$という数値が登場することです。
以下の条件を満たすとき、$${(S,P,V)}$$は知識の健全性があると言えます。
攻撃者$${A={A_0,A_1)}$$が任意の多項式時間で動くとします。この前提で、各式の意味を見ていきます。
① $${S(C) \to (S_p, S_v)}$$
回路の情報から公開パラメータを生成する
② $${(x, state) \gets A_o(S_p)}$$
公開パラメータ$${S_p}$$から、初期状態$${xx, state}$$を生成する
③ $${\pi \gets A_1(S_p, x, state)}$$
$${A_0}$$が生成した$${x, state}$$を使用し、証明$${\pi}$$を生成する
④ $${Pr[V(S_v, x, \pi) = accept] > 10^{-6}}$$
攻撃者$${A_0, A_1}$$が不正に生成した証明$${\pi}$$が、無視できない確率で検証者Vによって受理される
各式の意味を見ていきます。
① $${S(C) \to (S_p, S_v)}$$
回路の情報から公開パラメータを生成する
② $${(x, state) \gets A_o(S_p)}$$
公開パラメータ$${S_p}$$から、初期状態$${xx, state}$$を生成する
③ $${w \gets E^{A_1(S_p, x, state)}(S_p, x)}$$
公開パラメータ$${S_p}$$と$${x}$$に加え、攻撃者の偽装した証明をブラックスボックスとして利用して、抽出器$${E}$$によって秘密情報$${w}$$を取り出す
④ $${Pr[C(x,w)=0] > 10^{-6} - \epsilon}$$
抽出器で取り出した$${w}$$が、検証者が偽造した証明を受理する確率とほぼ同じ確率で公開情報$${x}$$に対して$${C(x,w)=0}$$が成り立つ
まとめ
つまり知識の健全性とは、
・「検証者が証明を受理する場合、証明者は本当に正しい解$${w}$$を知っている」
・「攻撃者が証明を偽造できたとしても、その攻撃者の行動を利用して秘密情報を効率的に取り出すことができる」
= 「抽出器が解を取り出すことができない場合、攻撃者は証明を偽造できていない」
ということです。
ゼロ知識性の定義
ゼロ知識性(Zero Knowledge)は、1本目の記事でも見た通り
「ある主張が真であることを、その主張を裏付ける秘密情報について一切明かさずに主張する」
ということでした。
今までの証明システムなどの内容を踏まえると、「$${(S, P, V)}$$がゼロ知識であるということは、$${\pi}$$が秘密情報$${w}$$が存在すること以外何も明かさない」と言えます。
この「証明$${\pi}$$が何も明かさない」の非形式的定義は、
「検証者が自力で証明$${\pi}$$を生成できる場合、受け取った証明$${\pi}$$から得られる情報は検証者にとっては何も新しくない」
というものです。つまり自分で同じものを作れるなら、誰かからそれを受け取っても新しいことは学べないという意味です。
ではこの「明かさない」の定義を踏まえて、ゼロ知識性の非形式定義はどうなるでしょうか？
非形式的定義
「本物の$${S_p, S_v, \pi}$$と見分けがつかない$${(S_p, S_v, \pi))}$$を生成できる、効率的なアルゴリズム$${Sim(C,x)}$$が存在するとき、$${(S,P,V)}$$はゼロ知識である」
というものです。先ほどの「明かさない」の定義に戻ると、効率的なアルゴリズムが存在する場合はそれを使用することで実際の証明$${\pi}$$と同じものを作ることができるので、検証者は実際の証明$${\pi}$$から得られる情報は何も学ばなかったことになります。
形式的定義
では、形式定義はどうなるでしょうか？今回は知識の健全性とは違い、非形式的定義とほぼ同じことを言っていて、理解しやすいです。
以下の条件を満たすとき、$${(S,P,V)}$$は回路$${C}$$に対してゼロ知識であると言えます。
① $${(C, S_p, S_v, x, \pi): where (S_p, S_v) \gets S(C), \pi \gets P(S_p, x, w)}$$
実際の手続きで証明$${\pi}$$を生成した場合の$${(C,S_p, S_v, x, \pi)}$$
② $${(C, S_p, S_v, x, \pi): where (S_p, S_v, \pi) \gets Sim(C,x)}$$
シュミレーターを使用し、秘密情報なしに証明$${\pi}$$を生成した場合の$${(C,S_p, S_v, x, \pi)}$$
まとめ
つまり、「本物の証明の分布」と「シュミレーターが生成した証明の分布」の見分けがつかないような出力ができるシュミレーターが存在することが、ゼロ知識の条件と言えることがわかります。
最後に
今回は、知識の健全性とゼロ知識性の形式的定義について見ました。今回の内容は派手さはないですが、これからZKを深めていくための基盤となると思います。Zero Knowledgeの定義に立ちかえる際は、この記事に戻ってきてもらえると嬉しいです！次回以降もぜひチェックしてください！
[参照]
この記事は、『ZK Hack Whiteboard Session1 Module1: What is a SNARK?』の動画の内容を編集し、図や説明を加えたものです。
ZK Hackとは、ZKに関するビデオやニュースレターの発信や、イベントを開催するコミュニティです。今回のビデオは、Stanford大学のDan Boneh教授によるSNARKの入門動画になります。