もしa=1の場合、証明者はg=rs mod nを計算して送信します。検証者が送信するランダムビットaを設定し、aの値に基づいて、証明者はgを計算します；
最後に、検証者は受け取ったgに基づいてg^2 mod nがxa^v mod nに等しいかどうかを検証します。等式が成り立つ場合、検証者はこの証明を受け入れます。a=0のとき、検証者はg^2 mod nを計算し、右側でxa^v mod nを検証します；a=1のとき、検証者はg^2 mod nを計算し、右側でxa^v mod nを検証します。
ここでは、検証者が計算したg^2 mod n=xa^v mod nが、証明者が検証プロセスを成功裏に通過したことを示しており、同時に彼の秘密の数字sを漏らしていないことを示しています。ここで、aは0または1のいずれかしか取れず、2つの可能性しかないため、証明者が運に頼って検証を通過する確率(がaが0の場合)で1/2であることがわかります。しかし、検証者はその後、証明者にn回挑戦し、証明者は関連する数字を次々と変更し、検証者に提出し、常に成功裏に検証プロセスを通過することができます。これにより、証明者が運に頼って検証を通過する確率(1/2)^n(は無限に0)に近づき、証明者が確かにある秘密の数字sを知っているという結論が証明されます。この例は、零知识证明システムの完全性、信頼性、及び零知識性を証明しています。
40年にわたるゼロ知識証明技術の包括的なレビュー:ZKSNARKからZKEVMまでの開発と将来の展望
ゼロ知識証明技術の総合的なレビューと今後の展望
###概要
zk-SNARKs(ZKP)技術は、ブロックチェーン分野において分散台帳技術に次ぐ最も重要な技術革新の一つとして広く見なされており、同時にリスク投資の重点的な関心分野でもあります。本稿では、zk-SNARKs技術の近40年の歴史文献と最新の研究を体系的にレビューします。
まず、zk-SNARKsの基本概念と歴史的背景を紹介します。その後、回路ベースのzk-SNARKs技術に重点を置き、zkSNARK、Ben-Sasson、Pinocchio、Bulletproofs、Ligeroなどのモデルの設計、応用、最適化方法を分析します。計算環境の分野では、ZKVMとZKEVMを紹介し、取引処理能力の向上、プライバシーの保護、検証効率の向上について探ります。記事では、零知识Rollup(ZK Rollup)がLayer 2拡張ソリューションとしての動作メカニズムと最適化方法、さらにハードウェアアクセラレーション、ハイブリッドソリューション、専用ZK EVMの最新の進展についても紹介しています。
最後に、本稿ではZKCoprocessor、ZKML、ZKThreads、ZK Sharding、ZK StateChannelsなどの新興概念を展望し、それらがブロックチェーンのスケーラビリティ、相互運用性、プライバシー保護において持つ可能性について探討しました。
最新の技術と発展のトレンドを分析することによって、本稿はzk-SNARKs技術の理解と応用に対する包括的な視点を提供し、ブロックチェーンシステムの効率と安全性を向上させる上でのその巨大な潜在能力を示し、将来の投資判断に重要な参考を提供します。
目次
前書き
ゼロ知識証明の基礎知識
概要
ゼロ知識証明の例
非対話型のゼロ知識証明
背景
NIZKの提案
フィアット・シャミール変換
ジェンス・グロスとその研究
その他の研究
回路ベースのゼロ知識証明
背景 2.回路モデルの基本概念と特徴
ゼロ知識証明における回路設計と応用
潜在的な落とし穴と課題
第四に、ゼロ知識証明モデル
背景 2.一般的なアルゴリズムモデル
線形PCPおよび離散対数問題に基づくスキーム
一般人の証明に基づくスキーム
ゼロ知識に基づく確率論的検証可能な証明(PCP)
CPC( Universal Proof Construction )のセットアップ段階に基づいて分類します
ゼロ知識仮想マシンの概要と開発
背景
既存のZKVMの分類
フロントエンドとバックエンドのパラダイム
ZKVMパラダイムの長所と短所
六、zk-SNARKsイーサリアム仮想マシンの概要と発展
背景
ZKEVMのしくみ
ZKEVMの実装プロセス
ZKEVMの特徴
ゼロ知識レイヤー2ネットワークソリューションの概要と開発
背景
ZK Rollupの動作メカニズム
ZK Rollupの欠点と最適化
ゼロ知識証明の今後の展開方向
コンピューティング環境の開発を加速する
ZKMLの提案・開発
ZKP拡張技術の開発
ZKPの相互運用性の開発
まとめ
参照
###イントロダクション
インターネットはWeb3時代に突入しており、ブロックチェーンアプリケーション(DApps)が急速に発展しており、毎日新しいアプリケーションが登場しています。近年、ブロックチェーンプラットフォームは毎日数百万のユーザーの活動を支え、数十億の取引を処理しています。これらの取引から生成される膨大なデータには、通常、ユーザーの身元、取引額、アカウントアドレス、アカウント残高などの敏感な個人情報が含まれています。ブロックチェーンのオープン性と透明性の特性を考慮すると、これらの保存されたデータはすべての人に開放されているため、さまざまなセキュリティとプライバシーの問題が引き起こされています。
現在、これらの課題に対処するためのいくつかの暗号技術があります。これには、同型暗号、リング署名、安全なマルチパーティ計算、そしてzk-SNARKsが含まれています。同型暗号は、暗号文を解読することなく演算を実行でき、アカウントの残高と取引金額の安全を保護するのに役立ちますが、アカウントアドレスの安全を保護することはできません。リング署名は、署名者の身元を隠すことができる特別なデジタル署名形式を提供し、アカウントアドレスの安全を保護しますが、アカウントの残高や取引金額の保護には無力です。安全なマルチパーティ計算は、参加者間で計算タスクを分配でき、いかなる参加者も他の参加者のデータを知ることなく、アカウントの残高と取引金額の安全を効果的に保護しますが、同様にアカウントアドレスの安全を保護することはできません。さらに、同型暗号、リング署名、安全なマルチパーティ計算は、取引金額、アカウントアドレス、アカウント残高を漏洩することなく、ブロックチェーン環境において証明者が十分な取引金額を持っているかどうかを検証するために使用することはできません。
zk-SNARKsは、より包括的なソリューションであり、この検証プロトコルは、仲介データを開示することなく特定の命題の正しさを検証することを可能にします。このプロトコルは、複雑な公開鍵インフラストラクチャを必要とせず、その繰り返しの実施は悪意のあるユーザーに追加の有用な情報を取得する機会を提供しません。ZKPを通じて、検証者はプライベートな取引データを漏らすことなく、証明者が十分な取引金額を持っているかどうかを検証できます。検証プロセスには、証明者が主張する取引金額を含む証明を生成し、その証明を検証者に渡した後、検証者が事前に定義された計算を行い、最終的な計算結果を出力して、証明者の主張を受け入れるかどうかの結論を導き出します。証明者の主張が受け入れられた場合、それは彼らが十分な取引金額を持っていることを意味します。上述の検証プロセスはブロックチェーンに記録され、偽造はありません。
ZKPのこの特性は、ブロックチェーン取引や暗号通貨アプリケーションにおいて核心的な役割を果たし、特にプライバシー保護とネットワーク拡張の面で、学術研究の焦点となるだけでなく、分散型台帳技術、特にビットコインが成功裏に実施されて以来、最も重要な技術革新の一つであると広く見なされています。同時に、業界アプリケーションとベンチャーキャピタルの重点的な分野でもあります。
このように、ZKPに基づく多くのネットワークプロジェクトが次々と現れました。例えば、ZkSync、StarkNet、Mina、Filecoin、Aleoなどです。これらのプロジェクトの発展に伴い、ZKPに関するアルゴリズムの革新が次々と生まれており、報告によればほぼ毎週新しいアルゴリズムが発表されています。さらに、ZKP技術に関連するハードウェアの開発も急速に進展しており、ZKPに最適化されたチップが含まれています。例えば、Ingonyama、Irreducible、Cysicなどのプロジェクトは大規模な資金調達を完了しており、これらの発展はZKP技術の急速な進歩を示すだけでなく、汎用ハードウェアからGPU、FPGA、ASICなどの専用ハードウェアへの移行を反映しています。
これらの進展は、zk-SNARKs技術が暗号学の分野における重要な突破口であるだけでなく、特にプライバシー保護と処理能力の向上において、より広範なブロックチェーン技術の応用を実現するための重要な推進力であることを示しています。
したがって、私たちは、将来の投資判断をより良く支援するために、零知识证明(ZKP)に関連する知識を体系的に整理することを決定しました。そのために、私たちは、関連性と引用回数に基づいてZKPに関連する主要な学術論文(を総合的にレビューしました。同時に、私たちは、その資金調達規模に基づいて、この分野の主要なプロジェクトの資料とホワイトペーパー)を詳細に分析しました。これらの総合的な資料の収集と分析は、本稿の執筆に堅実な基礎を提供しました。
( 1. ゼロ知識証明の基礎知識
)# 1. 概要
1985年、学者Goldwasser、MicaliとRackoffは論文《The Knowledge Complexity of Interactive Proof-Systems》中で初めてzk-SNARKs###Zero-Knowledge Proof、ZKP###およびインタラクティブな知識証明(Interactive Zero-Knowledge、IZK)を提唱しました。この論文はzk-SNARKsの基盤となるものであり、後続の学術研究に影響を与える多くの概念を定義しました。例えば、知識の定義は「不可行計算(unfeasible computation)の出力」であり、つまり知識は出力でなければならず、不可行計算であることを意味します。これは単純な関数ではなく、複雑な関数である必要があります。不可行計算は通常、NP問題として理解され、これは多項式時間内にその解の正当性を検証できる問題を指します。多項式時間とは、アルゴリズムの実行時間が入力サイズの多項式関数で表されることを意味します。これは計算機科学においてアルゴリズムの効率と可行性を測る重要な基準です。NP問題の解決プロセスは複雑であるため、不可行計算と見なされますが、その検証プロセスは比較的簡単であるため、zk-SNARKsの検証に非常に適しています。
NP問題の一つの古典的な例は旅行商問題であり、ここでは一連の都市を訪問して出発点に戻る最短パスを見つける必要があります。最短パスを見つけることは難しいかもしれませんが、与えられたパスが最短であるかどうかを検証することは比較的容易です。特定のパスの総距離を検証することは多項式時間内で完了できます。
Goldwasserらは彼らの論文の中で「知識の複雑さ」(knowledge complexity)という概念を導入し、インタラクティブ証明システムにおいて、証明者が検証者に漏らす知識の量を定量化するために使用しました。彼らはまた、インタラクティブ証明システム(Interactive Proof Systems,IPS)を提案し、証明者(Prover)と検証者(Verifier)が複数回のインタラクションを通じてある文の真実性を証明する方法を示しました。
以上のように、Goldwasserらがまとめたzk-SNARKsの定義は、特定のインタラクティブな証明であり、その中で検証者は検証プロセスにおいて文の真偽以外の追加情報を得ることはない。また、3つの基本的な特性を提案している。
1.完備性(completeness):もし証明が真実であれば、誠実な証明者は誠実な検証者にこの事実を納得させることができる;
2.信頼性(サウンドネス): もし証明者が声明の内容を知らない場合、彼は検証者を欺く確率は微小である。
3.zk-SNARKs(ゼロ知識):証明プロセスが完了した後、検証者は「証明者がこの知識を持っている」という情報のみを得ることができ、追加の内容は得られません。
(# 2.ゼロ知識証明例
より良く理解するためにzk-SNARKsおよびその属性を、以下は証明者が特定のプライベート情報を所有しているかどうかを検証する例であり、この例は3つの段階に分かれています: セットアップ、チャレンジ、レスポンス。
ステップ 1: )Setup###を設定する
このステップでは、証明者の目標は、特定の秘密の数字sを知っていることを証明する証拠を作成することですが、sを直接表示しないことです。秘密の数字sを設定します。
2つの大きな素数pとqを選び、それらの積nを計算します。素数pとqを設定し、得られたnを計算します;
v=s^2 mod nを計算します。ここで、vは証明の一部として検証者に送信されますが、検証者や他の観察者がsを推測するには不十分です。
ランダムに整数rを選び、x=r^2 mod nを計算して検証者に送信します。この値xは後続の検証プロセスに使用されますが、同様にsは公開されません。ランダムな整数rを設定し、得られたxを計算します。
第二ステップ: チャレンジ(Challenge)
検証者はランダムに位置a(を選択します。これは0または1)であり、その後、証明者に送信されます。この「チャレンジ」は、証明者が次に取るべきステップを決定します。
第三ステップ: (に応答する)
バリデーターが発行したa値に基づいて、プローバーが応答します:
もしa=0の場合、証明者はg=r(を送信します。ここでrは彼が以前にランダムに選択した数)です。
もしa=1の場合、証明者はg=rs mod nを計算して送信します。検証者が送信するランダムビットaを設定し、aの値に基づいて、証明者はgを計算します；
最後に、検証者は受け取ったgに基づいてg^2 mod nがxa^v mod nに等しいかどうかを検証します。等式が成り立つ場合、検証者はこの証明を受け入れます。a=0のとき、検証者はg^2 mod nを計算し、右側でxa^v mod nを検証します；a=1のとき、検証者はg^2 mod nを計算し、右側でxa^v mod nを検証します。
ここでは、検証者が計算したg^2 mod n=xa^v mod nが、証明者が検証プロセスを成功裏に通過したことを示しており、同時に彼の秘密の数字sを漏らしていないことを示しています。ここで、aは0または1のいずれかしか取れず、2つの可能性しかないため、証明者が運に頼って検証を通過する確率(がaが0の場合)で1/2であることがわかります。しかし、検証者はその後、証明者にn回挑戦し、証明者は関連する数字を次々と変更し、検証者に提出し、常に成功裏に検証プロセスを通過することができます。これにより、証明者が運に頼って検証を通過する確率(1/2)^n(は無限に0)に近づき、証明者が確かにある秘密の数字sを知っているという結論が証明されます。この例は、零知识证明システムの完全性、信頼性、及び零知識性を証明しています。
( 2. 非対話型のゼロ知識証明
)# 1. バックグラウンド
zk-SNARKs###ZKP###は、従来の概念では通常、インタラクティブでオンラインのプロトコル形式です。たとえば、Sigmaプロトコルは認証を完了するために通常3〜5回のインタラクションを必要とします。しかし、即時取引や投票などのシナリオでは、複数回のインタラクションを行う機会がないことが多く、特にブロックチェーン技術の応用において、オフライン認証機能が非常に重要になります。
(# 2. NIZKのご提案
1