Skip to content

ゼロ知識証明の概要

ゼロ知識証明アプリケーションを開発する際に、ゼロ知識証明について知っておくべき最低限の知識を共有します。ゼロ知識証明についてのより深い話は、次の章「ゼロ知識証明の理論」で説明します。

ゼロ知識証明とは

ゼロ知識証明とは、ある人が他の人に対して証明したいステートメントを、そのステートメントが真である以外の情報（知識）を開示することなく証明する技術のことです。ここでの「ある人」を証明者（prover）、「他の人」を検証者（verifier）と呼びます。ステートメントは日本語で命題とも呼ばれ、例えば「この金庫のパスワードを知っている」や「この方程式には解が存在する」のような主張のことを指します。

ゼロ知識証明はその便利な性質が注目され、プライバシー保護技術として利用されています。また、プライバシー保護だけでなく計算結果を高速に検算できるという性質を持つものもあり、特にブロックチェーンにおいてスケーラビリティを向上する技術としても利用されています。

完全性、健全性、ゼロ知識性

ゼロ知識証明は「完全性」「健全性」「ゼロ知識性」の3つの性質を満たすプロトコルです。

  • 完全性（completeness） とは、証明者が提示するステートメントが真である場合、検証者は真であることがわかる性質です。
  • 健全性（soundness） とは、証明者が提示するステートメントが偽である場合、検証者は偽であることがわかる性質です。
  • ゼロ知識性（zero-knowledge） とは、証明者が提示するステートメントが真である場合、検証者は真である以外の情報がわからない性質です。

具体例として、これら3つの性質をAliceからBobへの匿名送金で考えてみましょう。

  • 完全性: Bobが正当な出金要求を送った場合、プールはBobが送信してきた出金要求が正しいものであるとわかること。
  • 健全性: Bobが不正な出金要求を送った場合、プールはBobが送信してきた出金要求が正しくないものであるとわかること。
  • ゼロ知識性: Bobが正当な出金要求を送った場合、プールはBobが送信してきた出金要求が正しいものであること以外の情報がわからないこと。ここでの情報とは、例えば「入金者が誰であるか」「いつ入金されたか」などです。

ちなみに、この3つの性質はその程度によってパーフェクトか統計的か計算量的かの3つの定義ができます。例えば、計算量的ゼロ知識性があるならとてつもない計算資源を持つ人が情報を獲得できる可能性がありますが、パーフェクトゼロ知識性があるならどんな高性能がコンピューターを将来的に誕生しようとも情報理論的に情報が流出しません。3つの性質に3つのパターンがあるので、「パーフェクト完全性」「統計的完全性」「計算量的完全性」「パーフェクト健全性」「統計的健全性」「計算量的健全性」「パーフェクトゼロ知識性」「統計的ゼロ知識性」「計算量的ゼロ知識性」の合計9つの定義が可能です。それら定義については後述しますので、今は深く気にしなくてよいです。

ゼロ知識証明の例

ステートメントの定義

まず、ステートメントを定義します。 \(p\) を素数、 \(q\) を \(g^q = 1\) となる最小の自然数とします。証明者が \(w\) を \(1\) から \(q-1\) の中からランダムに選び、 \(h = g^w \mod p\) を公開したとします。 \(g,p\) は証明者と検証者で共有されています。証明者が「 \(w\) を知っていること」（= ステートメント）を検証者に証明するには、どうしたらよいでしょうか。

Schnorrプロトコル

Schnorrプロトコルは、検証者がプロトコルに正直に従うとしたときに、計算量的ゼロ知識性を達成するプロトコルの一つで、離散対数問題の解を知っていることをゼロ知識証明できるプロトコルです。計算量的ゼロ知識性とは、簡単に言えば計算能力に制限のある検証者に対して、ステートメントが真であること以外の情報が漏れない性質です。（計算能力に制限があるとは、形式的に言えば任意の確率的多項式時間アルゴリズムを実行できるということです。）

上記のステートメントを証明するには、次のような手順を踏めば良いです。

  1. Aliceは一時的な乱数 \(r\) を生成します。この \(r\) は \(0\) から \(q-1\) の範囲で選びます。そして \(c = g^r\) をBobに送ります。
  2. Bobは一時的な乱数 \(e\) を \(0\) から \(q-1\) の範囲で生成し、Aliceに送ります。
  3. Aliceは \(z = r + ew\) をBobに送ります。
  4. Bobは \(g^z = cy^e\) が真か確かめます。 \(g^z\) は、 \(g^z = g^{r+ew}=g^r\cdot (g^w)^e = cy^e\) と変形でき、もしAliceが \(w\) を知っているならば、これは一致します。

この手順はSchnorrプロトコルと呼ばれ、Bobが一時的な乱数 \(e\) を正直に生成するとしたとき、先程紹介した3つの性質を満たしたしています。

現実的には検証者がプロトコルに正直に従うとは限らないので、このプロトコルは実用的にはほとんど意味がありませんが、この弱い性質を持つプロトコルは他のプロトコルの構成要素として使えます。この正直な検証者に対するゼロ知識性は正直検証者ゼロ知識性（honest-verifier zero-knowledge）と呼ばれます。

非対話型ゼロ知識証明

Schnorrプロトコルは見たら分かるとおり、AliceとBobが対話しているため対話型ゼロ知識証明と呼ばれます。ただ、この対話型という性質は分散システム、特にブロックチェーンのスマートコントラクトと非常に相性が悪いです。トランザクションを送信して、トランザクションがブロックに含まれて実行されて、その実行された結果を見てまたトランザクションを送信して、……と考えただけで嫌になります。また、そもそも1つのトランザクションで完結しなければいけない場合に対応できません。

そのような課題を解決するために、非対話型ゼロ知識証明があります。ペアリングを使ったり、ハッシュ関数を利用したりすると、対話型ゼロ知識証明を非対話型ゼロ知識証明に変換できます。この資料では、2016年にJens Grothが発表したGroth16という非対話型ゼロ知識証明を利用しますが、ペアリングを用いています。

zk-SNARK

Zero-Knowledge Succinct Non-Interactive Argument of Knowledge、略してzk-SNARKは、非対話型ゼロ知識証明のカテゴリーの一つです。zk-SNARKは、完全性、健全性、ゼロ知識性に加えて、簡潔性（succinct）を持ち、名前の由来にもなっています。zk-SNARKであるプロトコルをまとめてzk-SNARKsと呼びます。この資料で利用するGroth16もzk-SNARKです。

簡潔性とは、証明のサイズが短いという性質です。特にGroth16は証明サイズが短いことに加え一定であり、これはブロックチェーンと非常に相性が良い性質です。ブロックチェーンでは処理するデータのサイズによってトランザクション手数料が増加します。証明サイズが一定であるので、どれだけステートメントが複雑であろうとも、その証明のサイズに関わる手数料が一定であることが保証されるのです。