証明プロトコル
今回は、一般的な証明プロトコルについて見ていきます。証明プロトコルには、大きく分けて「対話型」「非対話型」の2種類があります。
対話型証明プロトコルとは
概要
対話型証明プロトコルにおいて、登場人物は証明者(Prover)と検証者(Verifier)の2人です。証明者は検証者に対して、$${C(x,w)=0}$$を満たすようなwを知っていることを証明し、検証者はそれを元に証明が真であるか偽であるかを判断します。$${x}$$,$${w}$$はそれぞれ有限体上の値をすべて代入したもので、1つだけではありません。イメージとしては、$${x={0,1,2,…,p-1}}$$のようなものです。また、$${x}$$は公開情報、$${w}$$は秘密情報として扱います。
証明プロトコルにおけるゴールは、証明者は検証者に対し$${C(x,w)=0}$$を満たすようなwを知っていることを証明することと先ほど述べましたが、1回のやり取りでは真偽は判定できません。かといって、有限体上のすべての要素$${x}$$に対して、証明者に証明を求めても、時間がかかり現実的ではありません。
ここでよく使用される方法はランダムサンプリングです。検証者が有限体上からランダムにサンプリングした$${x}$$に対して、証明者は$${C(x,w)=0}$$となるような$${w}$$を知っていることを示す、というセットを何度か繰り返します。
具体的なステップ
それぞれ①~⑤は以下の通りです。
① 検証者は、公開情報からランダムに値を選択する
② 検証者は、証明者に①で選択した値を渡す
③ 証明者は、受け取った値($${x}$$)と一緒に入力すると$${C(x,w)=0}$$を満たす値を、秘密情報の中から選択する
⑤ 証明者は、受け取った値($${x}$$)と自身が選択した秘密の値($${w}$$)を関数に入力した結果が、$${C(x,w)=0}$$となることを検証者に渡す
すべての検証者のリクエストに対して証明者が応えることができれば、証明者が$${C(x,w)=0}$$となる有限体上の$${w}$$を知っていることが、かなり高い確率で真であると言えるため、しらみつぶしに調べるよりも効率的に真偽を判断することができます。
検証者が選んだ値$${x}$$に対して、証明者が適切な$${w}$$を選ぶことができる確率は
公開情報はn個,リクエストをm回送る時：$${(1/n)^m}$$
となり、適切な秘密情報を知らない状態でm回のリクエストに対して適切な証明を渡し続けられる確率がとても低いことに基づいています。
ここで見た証明プロトコルは、検証者と証明者の間で何度もやり取りが発生するため、対話型証明プロトコルと呼ばれることもあります。
非対話型証明プロトコルとは
具体的なステップ
先ほどの対話型証明プロトコルに対し、非対話型、つまり検証者と証明者間のやり取りが1度で終了する証明プロトコルでは、登場人物は検証者と証明者に加え、(信頼できる)第三者の3人になります。また、新しいステップとして前処理が第三者によって追加されます。前処理では、公開パラメーター$${S_p, S_v}$$が生成され、$${S_p}$$は証明者が、$${S_v}$$は検証者が使用するためのものです。
それぞれ①~③は以下の通りです。
① 信頼される第三者(a trusted third party)が、前処理によって関数$${C(x,w)}$$から公開パラメーター$${(S_p, S_v)}$$を生成します。
② 証明者は、$${S_p, x, w}$$から$${P(S_p, x, w)}$$証明$${\pi}$$を生成し、検証者に渡します。
③ 検証者は、受け取った$${\pi}$$も引数にした$${V(S_v, x, \pi)}$$の出力から真偽を判定します。
対話型との一番の違いは、1度のやり取り(証明$${\pi}$$を渡す)のみで検証者が真偽を判定することです。
満たすべき性質
非対話型が満たすべき条件としては、どのようなものがあるでしょうか？例えば、検証者が正しい$${\pi}$$ (証明者が生成した正しい証明) を利用して、真と判定できる確率が70%であると仮定します。この場合、正しい証明にもかかわらず検証者が偽と判定する確率が30%となり、証明システムとして信頼できません。
70%の確率で真判定
30%の確率で偽判定
をする図
同様に、検証者が偽の$${\pi}$$ (証明者が悪意を持ち、秘密情報を知らないのに作成した証明) を利用して、偽と判定できる確率を70%と仮定します。この場合、証明者が秘密情報を知らずに生成した証明が検証者に受け入れられる確率が30%となり、先ほどと同じく証明システムとして信頼できません。
30%の確率で真判定
70%の確率で偽判定
をする図
この2つの観点から、非対話式証明システムに必要な条件として以下の2つが挙げられます。
・完全性 (Completeness)：正しい証明($${\pi}$$)に対して、常に検証者が真と判定できるという性質
$${\forall x,w: C(x,w)=0}$$ $${\to}$$ $${P_r[V(S_v, x, P(S_p, x,w))=accept] = 1}$$
・健全性 (Knowledge Soundness) : 不正な証明($${{\pi}'}$$)に対して、ほぼ確実に検証者は見破って偽と判定できるという性質
証明者が$${w}$$を知らない $${\to}$$ $${P_r[V(S_v, x, P(S_p, x, w')) = accept] < {\epsilon} }$$
ゼロ知識非対話式証明プロトコルでは、これらにゼロ知識性 (Zero Knowledge)が追加されます。
・ゼロ知識性 (Zero Knowledge) : 使用される$${C, S_p, S_v, x, w}$$から、$${w}$$に関する情報が何も得られないという性質
このように、ゼロ知識非対話式証明プロトコルは
・完全性
・健全性
・ゼロ知識性
の3つの性質を満たしていることが条件となります。
最後に
今回は、対話型、非対話型の証明プロトコルの中身とその性質について確認しました。この2つのモデルの大きな違いは、検証者と証明者以外に第三者が登場するか、そして検証者と証明者のやり取りの回数で、これは公開パラメーターを生成することに起因するものでした。次回以降、SNARKとは何か、そして今回登場した健全性とゼロ知識性の厳密な定義について見ていきます。ぜひチェックしてください！
[参照]
この記事は、『ZK Hack Whiteboard Session1 Module1: What is a SNARK?』の動画の内容を編集し、図や説明を加えたものです。
ZK Hackとは、ZKに関するビデオやニュースレターの発信や、イベントを開催するコミュニティです。今回のビデオは、Stanford大学のDan Boneh教授によるSNARKの入門動画になります。