ZKPの直観：アリババの洞窟

ゼロ知識証明（ZKP）を使うと、証明者は秘密そのものを明かさずに、秘密を知っていること（またはある命題が真であること）を検証者に納得させられます。3 つの性質は、完全性、健全性、ゼロ知識性です。

証明者が秘密を知っていれば、常に検証者を納得させられます。プロトコルに従う正直な証明者は、確率 1（または圧倒的に高い確率）で成功します。検証者が正しい証明を拒否することはありません。

不正な証明者（秘密を知らない証明者）が検証者を納得させられる確率は、無視できるほど小さいものです。対話を 1 ラウンド行うたびに不正の成功確率は低下し、k ラウンド後の不正な証明者の成功確率は最大でも 2^{-k} です。

検証者は、命題が真であるという事実を超える情報を何も得ません。形式的には、秘密を知らなくても、実際の証明者と検証者の対話記録と見分けのつかない記録を生成できるシミュレーターが存在します。検証者が得る追加の知識はゼロです。

洞窟には輪状の通路があり、その中央に魔法の扉があります。証明者の Alice は、パスワードを知っていると主張します。検証者の Bob は洞窟の外で待ちます。Alice が中に入り、左または右へ進みます。Bob は、どちら側から出てくるかを叫んで指定します。Alice がパスワードを知っていれば、必ず指定された側から出てこられます。1 ラウンドあたりの不正の成功確率は 1/2 です。

20 ラウンド後には、不正な証明者が成功する確率は 2^{-20}、およそ 100 万分の 1 です。パスワードを知っている Alice は毎回成功します。Bob はパスワードを知ることなく、指定した側から Alice が出てくるのを見るだけです。これがゼロ知識性です。

対話型 ZKP では、証明者と検証者が何度もやり取りします。非対話型 ZKP（NIZK）では Fiat-Shamir 変換を使用し、検証者によるランダムなチャレンジをコミットメントのハッシュに置き換えます（ハッシュ = ランダムオラクル）。これにより、誰でも検証できる単一の証明文字列が生成されます。

ZKP が知識の証明（PoK）であるとは、証明者の戦略から、証明者が秘密を抽出できることが導かれる場合をいいます。これは、命題が真であることを証明するだけの場合より強い性質です。ECDSA 署名と Schnorr 署名は、秘密鍵を知っていることの非対話型の知識の証明です。

パスワードを送信せずに認証する。生年月日を明かさずに年齢を証明する。給与を明かさずに、給与がある範囲内にあることを範囲証明で示す。ブロックチェーンで、トランザクション自体を明かさずに、有効なトランザクションを知っていることを証明する。

完全ゼロ知識では、シミュレーターの出力は実際のトランスクリプトと同一です。統計的ゼロ知識では、無視できる確率を除いて識別不能です。計算量的ゼロ知識では、多項式時間の検証者にとって識別不能です。保証が弱いほど、証明は効率的になります。

洞窟プロトコルは、コミット → チャレンジ → 応答という3つの手順で構成されます。正式にはΣプロトコルと呼ばれます。実用的なZKPの多く（Schnorr、Pedersen、Fiat-Shamir）は、Σプロトコルまたはその合成です。この名前は、メッセージフロー図がΣの形になることに由来します。

アリババの洞窟プロトコルでは、何ラウンド実行すると、だます側の成功確率が1/1000未満になりますか？

ZKPは、秘密を明かさずに、その秘密を知っていることを証明します。3つの性質は、完全性、健全性、ゼロ知識性です。アリババの洞窟は、対話型ZKPを説明する例です。次は、ΣプロトコルとSchnorr識別です。