シンプルで実用的な観点から、ゼロ知識証明を一文で理解する

著者：benlaw.eth

あなたは以前、ゼロ知識証明に関するいくつかの記事を読んだことがありますが、まだ混乱していますか？これらの記事は次のようなことがあるかもしれません：

• 物語や童話の例を用いてZKPを論じており、その本質に深く迫ることができない。
• 大量の暗号学用語、数学公式、学術論文などが含まれており、初心者には複雑すぎる。

この記事では、ZKPの簡潔な概要を提供し、数学、暗号学、プログラミングの観点からZKPの核心要素をさらに詳しく説明します。

色盲に対する色の証明

色盲の患者に対して、2つのボールの色が異なることをどのように証明できますか？実はそれは複雑ではありません：

彼に2つのボールを手に持たせ、背中の後ろに隠し、ランダムにボールの位置を交換するかどうかを選ばせてから、あなたに見せます。あなたは彼にこの2つのボールの位置に変化があったかどうかを伝えます。

彼の目には、あなたは単に推測で証明を行っているように見えるでしょう。しかし、もしこのプロセスを何千回も繰り返すなら、あなたが常に正しい答えを言い続けることができるなら、純粋な推測で常に正しい状態を維持する確率は無視できるほど小さいです。したがって、この方法を通じて色盲の患者に対して、2つのボールの色が確かに異なり、私たちにはそれを認識し区別する能力があることを証明できます。

色の証明

上記の証明プロセスは典型的なゼロ知識証明です：

• 検証者は証明プロセス中に色に関する知識を得ることができません。なぜなら、検証プロセスの後でも彼は色を区別する能力を持っていないからです。
• この検証プロセスは確率的であり、決定的ではありません。
• このプロセスはインタラクティブであり、複数回のインタラクションが必要です。しかし、ゼロ知識証明には、証明プロセスを非インタラクティブに変換する高度な技術を用いた多くのプロトコルもあります。

知識の証明を掌握する

私たちは現実世界におけるゼロ知識証明の例を共有しましたが、次にバイナリ世界でゼロ知識証明をどのように実現するかを見てみましょう。

アーサーはイーロンの友人であり、彼の電話番号を知っています。ベティはイーロンの番号を知りません。アーサーがベティに自分がその番号を知っていることを証明したいが、番号を漏らしたくない場合、どうすればよいでしょうか？

知識の証明

未成熟な解決策の一つは、イーロンが自分の電話番号のハッシュを公開し、アーサーがプログラムを通じてハッシュの原像を入力し、プログラムが計算を行い結果を確認するというものです。この方法にはいくつかの致命的な欠陥があります：

• ハッシュに基づいて、ベティはブルートフォース攻撃を通じて原像を得ることができ、その確率は無視できないほど高く、得られる結果はほぼ決定的です。
• アーサーはそのプログラムに原像を入力する必要があります。もしプログラムがアーサーのコンピュータ上で動作している場合、ベティは疑問を抱くでしょう：あなたが不正をしていないとどうやってわかるの？あなたのコンピュータは常にあなたの証明が正しいと主張するかもしれません。
• もしプログラムがベティのコンピュータ上で動作している場合、アーサーも心配します。自分が入力した情報が盗まれるのではないかと。たとえプログラムの目に見えるコードに情報を盗む命令が含まれていなくても。
• プログラムを異なる環境で分けて実行できないため、この信頼の問題は解決が難しいです。

従来の方法はここで行き詰まりました。ゼロ知識証明の出番です！

暗号学に基づくゼロ知識証明の実装方案

ここでは、ゼロ知識証明の中のシグマプロトコルを用いて問題を解決します。これは比較的簡単です。また、簡潔で理解しやすくするために、厳密な暗号学や数学の定義、用語、導出過程などは使用しません。

核心プロセス

ゼロ知識証明を用いて特定の知識を持っていることを証明するために、次の方法を取ります：

シグマプロトコル

1. P階の有限群とその生成元gを定義します。これらの奇妙な用語が具体的に何を意味するかは一時的に無視します。
2. 上記の定義に基づいて、知識を持つか、知識にアクセスできる第三者が、知識（wと記す）をh = g\^w (mod P)の方法で暗号化し、hを公開します。
3. 証明者がゼロ知識証明プロセスを開始します。ランダム数rを生成し、a = g\^rを計算し、aを検証者に送信します。
4. 検証者がランダム数eを生成し、証明者に送信します。
5. 証明者がz = r + ewを計算し、検証者に送信します。
6. 検証者がg\^z == a·h\^e(mod P)を確認します。もし真であれば、検証者は確かに彼が主張する知識を持っていることを確認します。

さて、この証明プロトコルはここで終了です！非常に短いですが、あなたは上記のいくつかの数学的な計算に困惑しているかもしれませんが、それは問題ありません。まずは大まかな印象を持ち、後で深く理解しましょう。

数学原理

このプロセスの背後にある核心的な数学原理は離散対数問題です：Pが非常に大きな素数であるとき、与えられたhに対して、h = g\^w(mod P)を満たすwを見つけることは難しいです。この原理は上記のすべての類似の式に適用されます。

一歩一歩解析してみましょう：

暗号化された知識h = g\^w (mod P)はブルートフォース攻撃で解読することが難しいです。余剰計算の特性により、たとえ解読されても単一の決定的な解を持ちません。これは、証明者にとって、ブルートフォース攻撃で不正を行い、検証者を欺くことが不可能であることを意味します。

次に、3、4、5のステップを一つの全体として見て、なぜこれらのランダム数を交換する必要があるのかを考えてみましょう：

I. 証明者は秘密を暴露したくないので、彼はランダム数で包み隠す必要があります。また、検証者もランダム数を追加することで、その知識を自分で検証できるようにしつつ、証明者が不正を行うのを防ぎ、証明者の秘密を覗き見しないようにする必要があります。

II. 検証者が先にランダム数eを送信した場合（つまり、3と4のステップを入れ替えた場合）、明らかに証明者はa = g\^z·h\^-eを作り上げて最終的な検査で検証者を欺くことができます。知識がなくてもそうできるのです。したがって、証明者は最初に約束を送信する必要があります（a=g\^r）、しかしrそのものではなく、可変なシナリオを避けるために、同時に検証者がw = (z - r)/eを通じて秘密を引き出すことを防ぎます。

III. 約束を受け取った後、検証者は証明者にランダム数eを送信します。その数は、どちらの情報も漏らさないため、暗号化する必要はありません。その後、証明者はz = r + ewを計算し、zを検証者に送信します。検証者は最終的にg\^z= g\^(r+ew)= g\^r·(g\^w)\^e= a·h\^eを確認することで、証明者が知識を持っているかどうかを判断します。

この往復交錯の構造を通じて、私たちは3つの特性を得ました：

完全性：証明者が正しい知識を入力したときにのみ、検証が通過します。

信頼性：証明者が間違った知識を入力したときにのみ、検証が失敗します。

ゼロ知識性：検証者は検証プロセス中に何の知識も得ることができません。

上記の3点がゼロ知識証明の核心的特性です。数学と暗号学を通じて、私たちは奇妙な証明体系を構築しました。おめでとうございます、あなたはここまで来ました。今や、華麗で奥深いZKPの聖殿に正式に足を踏み入れたと言えるでしょう。

楽しんでください！

さらに学ぶ

シミュレーターとゼロ知識性

私たちは今、いくつかの魔法のシナリオを考えてみましょう。もし証明者が予言や検証者が生成したランダム数を改ざんする超能力を持っているとしたら、私たちはそれをシミュレーターと呼びます。

シミュレーター vs 検証者

想像してみてください。シミュレーターが検証者のランダム数eが生成される前にそれを改ざんし、生成後に自分が設定した値になるようにします。上記のIIで述べたように、この能力によりシミュレーターは約束aを作り上げて検証者を欺くことができます。シミュレーターの入力が何であれ、検証者は常にシミュレーターが知識を持っていると結論づけますが、実際には彼は持っていません。

明らかに、この思考実験を通じて、検証者はこのゼロ知識証明プロトコルの中で何の知識も得ることができない、つまりそのゼロ知識性が成立することがわかります：

ゼロ知識性 \<== ∀シミュレーターS、S(x)が実際のプロトコルの実行と区別できないようにする、ここでS(x)：ランダムなzとeを選択し、a = g\^z·h\^-eとし、(a,e,z)の分布が実際のランダム数環境と一致し、g\^z=a·h\^eを満たします。

抽出器と信頼性

次に、別の超能力者------抽出器を想像してみましょう。彼は時間を逆行させる能力を持っています。しかし今回は、抽出器が検証者として、通常の証明者に対峙します。

プロトコルが終了したとき、抽出器は時間を逆行させ、プロトコルの起点に戻り、前のラウンドで得た(z, e, a)を保持します。今、プロトコルを再度実行します。証明者は超能力を持たず、固定された時間軸上で確定的なことを行うしかないため、彼は同じランダム数rと約束a = g\^rを生成しますが、抽出器は証明者に新しいランダム数e'を生成することができます。

証明者 vs 抽出器

今、抽出器は次のことを得ました：g\^z= a·h\^e, g\^z'=a·h\^e => g\^(z-z') = h(e-e') => 暗号化された知識 h = g\^((z-z')/(e-e')) => 知識 w = (z-z')/(e-e')。

明らかに、証明者が本当に知識を持っている限り、抽出器は常にそれを抽出することができ、つまり完全性が成立します：完全性 \<== ∀抽出器E、与えられた任意のhに対して、(a,e,z),(a,e',z')を掌握し、e≠e'の場合、wを出力できることができます s.t. (h,w) ∈ R。

完全性

完全性は、特別な役割を必要としません。なぜなら：g\^z = g\^r+ew = g\^r·(g\^w)\^e = a·h\^eだからです。