ゼロ知識証明入門ガイド：発展の歴史、応用、基本原理

2023.12.07

共有先

TechFlow厳選深潮セレクト

ゼロ知識証明入門ガイド：発展の歴史、応用、基本原理

ZKPの理論的および応用面でのいくつかの変化を最初から整理する。

2023.12.07 - 09:33:41

Web3業界の深掘り報道に専念し潮流を洞察

ZKPの理論的および応用面でのいくつかの変化を最初から整理する。

執筆：HashKey Capital

現在のブロックチェーン業界において、ゼロ知識証明（ZKP）プロジェクトは驚異的なスピードで増加しており、特にZKPがスケーラビリティとプライバシー保護という二つの側面で応用されるようになったことで、多種多様なゼロ知識証明プロジェクトが登場しています。ZKPは非常に数学的性質が強いため、暗号愛好家にとってZKを深く理解することは難しくなっています。そこで本稿では、ZKPの理論および応用における変化を一から整理し、読者とともにCrypto業界への影響や価値について探求したいと思います。複数回にわたるレポート形式で学びを共有するとともに、HashKey Capitalリサーチチームの思考をまとめます。本稿はそのシリーズ第一弾であり、ZKPの歴史、応用、および基本原理を中心に紹介します。

一、ゼロ知識証明の歴史

現代的なゼロ知識証明体系の起源は、Goldwasser、Micali、Rackoffが共同で発表した論文『The Knowledge Complexity of Interactive Proof Systems』（通称GMR85）にあります。この論文は1985年に提出され、1989年に正式に発表されました。この論文では、ある証言（statement）が正しいことを証明するために、Kラウンドのやり取りを通じてどれだけの「知識」が交換される必要があるかを考察しています。もし交換される知識をゼロにできるならば、それを「ゼロ知識証明」と呼びます。ここでは、証明者（prover）は無限のリソースを持つと仮定し、検証者（verifier）は有限のリソースしか持たないと仮定します。しかし交互型システムには問題があり、証明は数学的に完全に証明されるわけではなく、確率的に正しい（ただしその誤り確率は非常に小さい：1/2^n）にすぎません。

そのため、交互型システムは完全ではなく、近似的な完全性しか持ちません。これに対して、非交互型（NP）システムは完全性を持つため、ゼロ知識証明システムとして理想的な選択となります。

初期のゼロ知識証明システムは効率性や実用性に欠けていたため、長らく理論の範疇に留まっていました。しかし過去10年間で急速に発展し、暗号学がCrypto分野の中心的テーマとなる中で、ゼロ知識証明は注目を集める重要な分野となりました。特に、汎用的で、非交互型かつ証明サイズが限定されたゼロ知識証明プロトコルの開発は、最も重要な研究課題の一つです。

基本的にゼロ知識証明とは、証明速度、検証速度、証明サイズの三者のトレードオフの問題です。理想のプロトコルとは、証明が速く、検証も速く、証明サイズが小さいものです。

ゼロ知識証明における最も重要なブレイクスルーは、Grothが2010年に発表した論文『Short Pairing-based Non-interactive Zero-Knowledge Arguments』です。これは、今日広く使われるzk-SNARKの理論的先駆けとなりました。

応用面での最大の進展は、2015年にZcashが採用したゼロ知識証明システムです。これは取引内容および金額のプライバシーを保護するもので、その後zk-SNARKとスマートコントラクトの統合へと発展し、より広範な応用シーンに拡大しました。

この期間に生まれた主な学術的成果は以下の通りです：

2013年：Pinocchio (PGHR13) 『Nearly Practical Verifiable Computation』。証明および検証時間を実用可能なレベルまで圧縮。Zcashの基盤プロトコルとしても使用。
2016年：Groth16 『On the Size of Pairing-based Non-interactive Arguments』。証明サイズを削減し、検証効率を向上。現在最も広く使われているZK基礎アルゴリズム。
2017年：Bulletproofs (BBBPWM17) 『Bulletproofs: Short Proofs for Confidential Transactions and More』。信頼できるセットアップを必要としない短い非交互型ゼロ知識証明を提案。6ヶ月後にはMoneroに適用され、理論から実装までのスピードが非常に速かった。
2018年：zk-STARKs (BBHR18) 『Scalable, transparent, and post-quantum secure computational integrity』。信頼できるセットアップを不要とするZK-STARKプロトコルを提案。現在のZK技術のもう一つの注目すべき方向性であり、StarkWareという最重要ZKプロジェクトの基盤となった。

その他にもPLONK、Halo2などが極めて重要な進展であり、zk-SNARKのいくつかの側面を改善しています。

二、ゼロ知識証明の応用概要

ゼロ知識証明の最も広範な応用は、プライバシー保護とスケーラビリティの二つです。初期にはZcashやMoneroといった有名プロジェクトによるプライベート取引が登場し、一時期非常に重要なカテゴリとなりましたが、プライバシー取引の必要性が業界の期待ほど顕著ではなかったため、こうした代表的なプロジェクトは次第に第二・第三ラインに退いています（歴史から消えたわけではない）。一方、アプリケーション層では、スケーラビリティの必要性が極めて高まり、2020年に以太坊2.0（現コンセンサスレイヤー）がRollup中心の路線に転換したことで、ZK技術が再び注目を集め、焦点となっています。

プライベート取引：既に実装されているプライベート取引プロジェクトには、SNARKを使用するZcashやTornado、Bulletproofを使用するMonero、およびDashなどがあります。ただし、Dashは厳密にはZKPではなく、単純な混在（mixing）システムであり、アドレスは隠せるものの金額は隠せないため、本稿では割愛します。

Zcashが使用するzk-SNARKsの取引手順は以下の通りです：

出典: Demystifying the Role of zk-SNARKs in Zcash

System setup段階で、証明鍵（証明多項式の暗号化）と検証鍵をKeyGen関数を用いて生成
CPA段階で、ECIES暗号方式（楕円曲線統合暗号方式）を用いて公開鍵と秘密鍵を生成
Minting Coins段階で、新規コインの数量、公開アドレス、コインのコミットメントを生成
Pouring段階で、zk-SNARK証明を生成し、pour取引台帳に追加
Verification段階で、検証者がMintおよびPour取引量が正しいかを検証
Receiving段階で、受信者がコインを受け取る。受け取ったコインを使用する場合は、再度Pouringを呼び出してzk-SNARK検証を行い、上記4〜6のステップを繰り返して取引を完了。

ただしZcashのゼロ知識証明には制限があります。UTXOに基づいているため、一部の取引情報はshielded（遮蔽）されているだけで、完全に隠ぺいされているわけではないのです。また、ビットコイン設計を踏襲した独立ネットワークであるため、拡張性に乏しく（他のアプリとの統合が難しい）です。実際にshielding（プライベート取引）を利用しているのは10%未満であり、プライベート取引はそれほど成功した拡張とは言えない状況です。（出典: 2202）

Tornadoはより汎用的な大規模ミキシングプールを採用しており、しかもイーサリアムという「実績ある」ネットワーク上に構築されています。Tornadoの本質は、zk-SNARKを用いたミキシングプールであり、信頼できるセットアップはGroth16の論文に基づいています。Tornado Cashが提供する機能は以下の通りです：

預け入れたコインのみ引き出し可能
同一のコインが二度引き出されることはない
証明プロセスとコインの無効通知（Nullifier）が紐づけられており、同じ証明でも異なるNullifierのハッシュでは引き出しが許可されない
セキュリティは126ビットあり、組み合わせによって低下することはない

Vitalikは述べています。スケーラビリティと比較すれば、プライバシーの実現は相対的に容易であり、いくつかのスケーリングプロトコルが成立すれば、プライバシーはもはや問題にならないだろう、と。

スケーラビリティ：ZKによるスケーリングはレイヤー1上で行うことも可能（例：Mina）、またレイヤー2上で行うことも可能で、つまりzk-Rollupです。zk-Rollupのアイデアはおそらく、Vitalikが2018年に投稿した「On-chain scaling to potentially ~500 tx/sec through mass tx validation」にさかのぼります。

zk-Rollupには二種類の役割があります。一つはSequencer、もう一つはAggregatorです。Sequencerは取引の集約を担当し、Aggregatorは多数の取引をまとめてRollupを作成し、SNARK証明（または他のアルゴリズムに基づくゼロ知識証明）を生成します。この証明はLayer1の以前の状態と比較され、イーサリアムのMerkleツリーを更新し、新しい状態ツリーを計算します。

出典: Polygon

zk-Rollupの利点と欠点：

利点：手数料が低く、OPのように経済的攻撃を受けにくく、遅延が不要、プライバシー保護が可能、最終性が迅速
欠点：ZK証明の生成には大量の計算が必要、セキュリティ上の課題（SNARKには信頼できるセットアップが必要）、量子攻撃に弱い（SNARKは脆弱だが、STARKは耐性あり）、取引順序が変更される可能性

出典: イーサリアム research

データ可用性および証明方法に応じて、StarkwareがL2に対する古典的な分類図を提示しています（Volitionのデータ可用性層はオンチェーンとオフチェーンを選択可能）：

出典: Starkware

現在市場で最も競争力のあるzk-Rollupプロジェクトには、StarkwareのStarkNet、MatterlabsのzkSync、AztecのAztec Connect、PolygonのHermezおよびMiden、Loopring、Scrollなどがあります。

技術的路線は基本的に、SNARK（およびその改良版）とSTARKの選択、そしてEVMサポート（互換性または同等性）に分かれます。

Aztecは汎用的なSNARKプロトコルであるPlonkを開発。開発中のAztec3はEVMをサポートする可能性があるが、EVM互換性よりもプライバシーを優先
StarkNetはzk-STARKを使用。信頼できるセットアップを必要としないZKPだが、現時点ではEVMをサポートせず、独自のコンパイラと開発言語を持つ
zkSyncもPlonkを使用。EVMをサポート。zkSync 2.0はEVM互換であり、独自のzkEVMを持つ
ScrollはEVM互換のZK Rollup。チームはイーサリアム財団のzkEVMプロジェクトにおいて重要な貢献者

ここでEVM互換性問題について簡単に議論します：

ZKシステムとEVMの互換性は常に難題でした。多くのプロジェクトは両者の間で選択を迫られています。ZK重視のプロジェクトは独自の仮想マシンを構築し、ZK向けの言語とコンパイラを持つ傾向がありますが、これにより開発者の学習コストが高まり、ほぼすべてが非オープンソースであるため「ブラックボックス」となりがちです。現在業界では主に二つのアプローチがあります。一つはSolidityのオペコードと完全に互換、もう一つはSolidityに互換性を持ちつつZKフレンドリーな新しい仮想マシンを設計するものです。当初はこのような高速な融合が可能だとは誰も予想していませんでしたが、ここ1〜2年の技術の急速な進化により、EVM互換性は新たな高みに達し、開発者はある程度シームレスに移行（イーサリアムメインチェーンからzk-Rollupへ）できるようになり、これは非常に前向きな進展です。このことはZKの開発エコシステムと競争構造に大きな影響を与えます。今後のレポートでこの問題を詳しく考察する予定です。

三、ZK SNARKの実現原理

Goldwasser、Micali、Rackoffは、ゼロ知識証明が以下の三つの性質を持つと提唱しました：

完全性（Completeness）：正当な証拠（witness）を持つすべての声明（statement）は、検証者によって検証可能であること
健全性（Soundness）：不当な証拠を持つ声明は、検証者によって検証されてはならないこと
ゼロ知識性（Zero-knowledgeness）：検証プロセスがゼロ知識であること

したがってZKPを理解するには、zk-SNARKから始めましょう。なぜなら現在の多くのブロックチェーン応用はSNARKから始まっているからです。まず、zk-SNARKについて理解しましょう。

zk-SNARKとは、「zero-knowledge Succinct Non-interactive ARguments of Knowledge」の略です。

Zero Knowledge：証明プロセスはゼロ知識であり、余計な情報を漏らさない
Succinct：証明サイズが小さい
Non-interactive：非交互型プロセス
ARguments：計算的健全性を持つ。つまり、有限の計算能力を持つ証明者は証明を偽造できないが、無限の計算能力を持つ証明者は偽造可能
of Knowledge：証明者は、有効な情報を知らずにパラメータと証明を構築することはできない
つまり証明者にとって、証拠（Witness、例えばハッシュ関数の入力や特定のMerkle-treeノードのパス）を知らない状態で、パラメータと証明を構築することは不可能である。