ZKP & ZK-SNARKS
要約
- zk-SNARKs = Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge
- 情報そのものを明かさずに、一方が何かを知っていることを証明できる
- Zcash は zk-SNARKs を使用し、送信者、受信者、金額を明かすことなく、取引が有効であること（正しい金額、未使用の入力）を証明する
- 「Succinct」とは、複雑な主張であっても証明が非常に小さく、迅速に検証できることを意味する
- Orchard プールは、信頼できるセットアップを必要としない zk-SNARK システムである Halo 2 を使用する
証明とは？
証明はすべての数学の基盤です。証明とは、証明しようとする主張または定理と、その定理が証明されたことを示すために行われる導出の連鎖です。たとえば、三角形の内角の和が180°であることは、誰でも（検証者として）独立して確認できます。
証明
証明者 ---> 主張を行う ---> 検証者が選択 ---> 受理/拒否
（証明者と検証者はどちらもアルゴリズムです）
コンピュータサイエンスでは、効率的に検証可能な証明をNP証明と呼びます。これらの短い証明は多項式時間で検証できます。大まかな考え方は、「定理の解が存在し、それが検証者に渡されて確認される」というものです。
NP言語では、次の2つの条件を満たす必要があります。
完全性：真の主張は検証者に受理される（正直な証明者が検証に到達できる）
健全性：偽の主張には証明が存在しない（不正な証明者のどのような戦略でも、不正確な主張の正しさを証明することはできない）。
対話的・確率的証明
対話性：検証者は証明を読むだけでなく、複数のメッセージラウンドにわたって証明者とやり取りします。
ランダム性：検証者から証明者への要求はランダム化されており、証明者はそれぞれに正しく答えられなければなりません。
対話性とランダム性を組み合わせることで、確率的多項式時間（PPT）で、何も知らない検証者に主張を証明できます。
対話的証明は、NP証明より効率的に多くのことを検証できるでしょうか？
NP証明とIP証明：
| 命題 | NP | IP |
|---|
| NP | はい | はい |
| CO-NP | いいえ | はい |
| #P | いいえ | はい |
| PSPACE | いいえ | はい |
NP - 命題に対する解が存在すること
CO-NP - 命題に対する解が存在しないことを証明すること
#P - 命題に対して存在する解の数を数えること
PSPACE - 異なる命題の交替を証明すること
ゼロ知識とは？
検証者が対話後に計算できることは、対話前に証明できたことと同一です。証明者と検証者の複数ラウンドにわたる対話は、検証者の計算能力を向上させません。
シミュレーション Paradigm
この実験は暗号学全体で用いられます。「実際のビュー」と「シミュレートされたビュー」を提示します。
実際のビュー：証明者と検証者（P,V）間で起こりうるすべての対話履歴
シミュレートされたビュー：検証者が、証明者と検証者間で起こりうるすべての対話をシミュレートするもの
多項式時間の識別器は、見ているものが実際のビューかシミュレートされたビューかを判断しようとし、両方から繰り返しサンプルを要求します。
実際またはシミュレートされたビューから多項式個のサンプルを受け取った後でも、すべての識別アルゴリズム/戦略に対して確率が>1/2である場合、この2つのビューは「計算量的に識別不可能」であるといわれます。
ゼロ知識知識主張
すべての確率的多項式時間検証者に対して（定理が正しい場合）、実際のビューとシミュレートされたビューを決定する確率分布が計算量的に識別不可能となるシミュレータ（アルゴリズム）が存在する場合、対話型プロトコル（P,V）はゼロ知識です。
対話型プロトコルは、検証者が1人の場合に役立ちます。例として、ゼロ知識の「納税証明」アプリケーションにおける税務監査人が挙げられます。
SNARKとは？
簡潔な非対話型知識主張
広義の定義 - 命題が真であることを示す簡潔な証明です。証明は短く、迅速に検証できなければなりません。SNARKSでは、証明者から検証者へ単一のメッセージが送信されます。検証者はその後、受理または拒否を選択できます。
命題の例：「SHA256(m)=0となるメッセージ（m）を私は知っている」
zk-SNARK では、証明はメッセージ（m）について何も明かしません。
多項式：定数（1、2、3など）、変数（x、y、zなど）、および変数の指数（x²、y³など）を含む項の和。
例：「3x² + 8x + 17」
算術回路：多項式を計算するためのモデルです。より一般的には、グラフの各ノードで算術演算が実行される有向非巡回グラフとして定義できます。回路は加算ゲート、乗算ゲート、およびいくつかの定数ゲートで構成されます。ブール回路がワイヤ上でビットを運ぶのと同様に、算術回路は整数を運びます。
この例では、証明者は算術回路の解を知っていることを検証者に納得させたいと考えています。
コミットメント：これを行うため、証明者は回路に関連するすべての値（非公開と公開）をコミットメントに入れます。コミットメントは、出力が不可逆な関数を使用して入力を隠します。
Sha256は、コミットメントスキームで使用できるハッシュ関数の一例です。
証明者が値にコミットした後、そのコミットメントは検証者に送信されます（検証者は元の値を一切明らかにできないと確信しています）。その後、証明者はグラフのノード上にある各値についての知識を検証者に示すことができます。
Fiat-Shamir変換
プロトコルを非対話型にするため、証明者は暗号学的ハッシュ関数を使用し、検証者に代わってランダム性（隠されたチャレンジに使用される）を生成します。これはランダムオラクルとして知られています。証明者は単一のメッセージを検証者に送信でき、検証者はそれが正しいか確認できます。
一般的な回路に使用できるSNARKを構成するには、2つの要素が必要です。
関数型コミットメントスキーム：コミッターが短い文字列で多項式にコミットでき、それを検証者が使用してコミット済み多項式の主張された評価を確認できるようにします。
多項式対話型オラクル：検証者は、選択したさまざまな点で、証明者（アルゴリズム）に多項式コミットメントスキームを用いてすべてのコミットメントを開くよう求め、それらの間で恒等式が成り立つことを確認します。
セットアップ
セットアップ手順は、回路を要約し公開パラメータを出力することで、検証者を支援します。
前処理セットアップの種類：
回路ごとの信頼できるセットアップ - 回路ごとに一度実行されます。回路固有であり、秘密のランダム性（共通参照文字列）は秘密に保持し、破棄しなければなりません。
この方法でセットアップが侵害されると、不正な証明者が偽の命題を証明できてしまいます。
信頼できるユニバーサルセットアップ - 信頼できるセットアップを一度だけ実行すればよく、その後は複数の回路を決定論的に前処理できます。
透明なセットアップ（信頼できるセットアップなし）- 前処理アルゴリズムは秘密のランダム性を一切使用しません。
SNARK証明構成の種類：
Groth16：信頼できるセットアップを必要としますが、迅速に検証できる非常に短い証明を持ちます。
Sonic/Marlin/PLONK：ユニバーサルな信頼できるセットアップ。
DARK/Halo/STARK：信頼できるセットアップは不要ですが、やや長い証明を生成するか、証明者の実行により長い時間がかかる場合があります。
SNARKSは、Zcash のようなブロックチェーンや Aztec のようなzk-Rollupなど、複数の検証者が必要な場合に役立ちます。これにより、複数の検証ノードが各証明について複数ラウンドで対話する必要がなくなります。
zk-SNARK は Zcash でどのように実装されていますか？
一般に、ゼロ知識証明は、情報を一切明かさずにプロトコル内での正直な行動を強制するためのツールです。
Zcash は、プライベート取引を可能にするパブリックブロックチェーンです。zk-SNARK は、取引に関する他の詳細を明かすことなく、プライベート取引がネットワークのコンセンサスルールの範囲内で有効であることを証明するために使用されます。
動画解説 - この講義では、Ariel Gabizonが Zcash Note Commitment Tree、Blind Polynomial Evaluation、Homomorphically Hidden Challengesと、それらがネットワーク上でどのように実装されているかを説明しています。
詳細については、Halo2 bookをお読みください。
その他のゼロ知識アプリケーション
zk-SNARKs は、多種多様なアプリケーションにおいていくつかの利点をもたらします。いくつかの例を見てみましょう。
スケーラビリティ：これは「計算のアウトソーシング」によって実現されます。L1チェーンがオフチェーンサービスの処理を検証するために、ゼロ知識が厳密に必要なわけではありません。取引はzk-EVM上で必ずしもプライベートではありません。
証明ベースのRollup（zk-Rollup）サービスの利点は、数百または数千件の取引のバッチを処理でき、L1がすべての取引が正しく処理されたことを示す簡潔な証明を検証できることです。これによりネットワークの取引スループットは100倍または1000倍にスケールします。
相互運用性：これはzk-Bridgeで、ソースチェーン上の資産を「ロック」し、その資産がロックされたことをターゲットチェーンに証明することで実現されます（コンセンサスの証明）。
コンプライアンス：Espresso のようなプロジェクトは、取引の詳細を明かすことなく、プライベート取引が地域の銀行法に準拠していることを証明できます。
偽情報との戦い：ブロックチェーンや暗号通貨以外のいくつかの例として、ニュースやメディアが処理した画像に証明生成を利用し、視聴者が画像の出所と、その画像に対して実行されたすべての操作を独立して検証できるようにすることがあります。https://medium.com/@boneh/using-zk-proofs-to-fight-disinformation-17e7d57fe52f
さらに学ぶ：
ゼロ知識文献一覧 - a16z Crypto
Hanh Huynh HuuによるzkSNARK
Zcash：Halo 2と信頼できるセットアップなしのSNARK - Dystopia labsのSean Bowe
Avi Wigdersonによるゼロ知識証明 - Numberphile
対話型ゼロ知識証明 - Chainlinkの記事
講義1：ZKPの導入と歴史 - zklearning.org
算術回路の簡単な説明 - Medium
スケーラビリティは退屈、プライバシーは死んだ：ZK証明、それは何の役に立つのか？
関連ページ
