ゼロ知識証明ものがたり

これはあくまでも個人の調査の上で、ゼロ知識証明の研究の流れを物語形式に自分なりに表現したものです。ざっくりと外観を捉えたい時にご参照ください。ご指摘も歓迎しております。

第一章：ゼロ知識証明の始まり - （1985-1992）

1985年暗号理論の世界に、Goldwasser、Micali、Rackoffという3人の研究者による、ある論文が発表されました。それは「特定の情報を知っていること」を、他の一切の情報を明らかにせず他者に数学的に証明することができる技術でした。

この論文は、完全性、健全性、ゼロ知識性という3つの重要な概念を導入し、二次剰余と二次非剰余の構成を提供し、二次剰余性を判定する問題を使って、ゼロ知識証明プロトコルを具体的に構築しました。これは、後の暗号学の発展に大きな影響を与えることになります。

1992年、この分野に新たな革新が加わります。Lund、Fortnow、Karloff、Nisanによって提案されたSumcheckプロトコルです。このプロトコルは、多変数多項式の評価の和に関する主張を、ランダムに選ばれた点での単一の評価に減らすことを可能にしました。つまり、多項式の評価の総和を効率的に検証できるようになりました。この発見は、後にSNARKsの基礎となる重要な構成要素となりました。

第二章：基礎の確立 - GKRプロトコルとKGZ多項式コミットメントスキーム（2007-2010）

2007年、Goldwasser、Kalai、Rothblumによって、画期的なGKRプロトコルが提案されます。このプロトコルは、回路の出力に関する主張から始まり、これを前の層の値に関する主張に還元していくというものです。

特筆すべきは、このプロトコルが証明者の計算時間が線形で、検証者の計算時間が準線形であるということです。これは、効率的な証明システムへの重要な一歩となりました。

2010年には、Kate、Zaverucha、Goldbergが、後にKZGとして知られることになる多項式コミットメントスキームを導入します。このスキームは、楕円曲線におけるペアリング写像を使用して、効率的な多項式のコミットメントを可能にしました。これは、後のPinocchio、Groth16、Plonkなどの効率的なSNARKsの重要な構成要素となりました。

第三章：実用化への第一歩 - 初期のSNARKs（2013-2016）

2013年、最初の実用的なzk-SNARKとしてPinocchioが登場します。このシステムは、Cコードから算術回路へのコンパイラを提供し、これを二次算術プログラム（QAP）に変換する革新的なアプローチを採用しました。ただし、回路サイズに制限があったり、証明生成時間が比較的遅かったりと実際にプロジェクトで使われるということはあまりありませんでした。

2016年、Jens Grothによる画期的なプロトコル、Groth16が登場します。このプロトコルは、わずか3つの群要素からなる最小の証明サイズと、3つのペアリングだけで済む高速な検証を実現しました。ZcashでのGroth16の採用は、ゼロ知識証明の実用化における重要なマイルストーンとなりました。

これらは、Trusted Setup（証明鍵と検証鍵を生成するための前処理ステップ）を必要とし、プログラム/回路に特化していました。これらの鍵は、当事者に知られてはならない秘密のパラメータに依存しており、これが公開されると証明を偽造できてしまいます。これからの流れでは主に3つの問題を解決していきます。

• より効率的な証明生成
• Trusted Setupの改善

第四章：Trusted Setupの改善 - Bulletproofs・STARKs（2016-2018）

しかし、同じ年、異なるアプローチを模索する動きも始まっていました。Bootleらは、Bulletproofsを通じて、Trusted Setupを必要としない新しい方向性を示します。ベクトルの内積に関する関係を、Pedersenコミットメントを使って効率的に証明できるゼロ知識証明システムを導入しました。後のHalo2やKimchiといったプロジェクトに大きな影響を与えることになります。

ここでSNARKsの一つの欠点であったTrusted Setupを必要としないメリットはあったものの、証明生成時間や検証時間が遅いというデメリットがあったため、複雑なアプリケーションには向かず現状は、RangeProof（送金額などがある値の範囲以下に収まっているかの証明）のユースケースが主な使用用途になっています。

さらに2018年、Ben-Sassonらによって、STARKsという革新的な技術が導入されます。STARKsの核となる2つの重要な技術的革新があります：

• 代数的中間表現（AIR）：
  Algebraic Intermediate Representationの略で、これは計算を代数的制約の集合として表現する方法で、任意の計算を多項式の関係として表現できます。AIRにより、複雑なプログラムの実行を効率的に証明可能な形式に変換できます。
• FRIプロトコル：
  Fast Reed-Solomon Interactive Oracle Proof of Proximityの略で、多項式の次数が特定の制限以下であることを効率的に証明するプロトコルです。AIRで生成された多項式の整合性を検証する際に使用されます。

STARKsは、これらの技術を組み合わせることで、証明メカニズムを楕円曲線ではなくハッシュ関数に依存する形で実現しました。そのため耐量子セキュアであり、高速な証明者と検証者を持ち、Trusted Setupを必要としないこのプロトコルは、暗号証明の新時代を予感させるものでした。
ただし証明サイズが大きいO{(log n)^2}のために、ブロックチェーンへの格納が難しく、スマートコントラクト上での検証などが高コストになってしまうので、ブロックチェーンには不向きでした。ただし後にSTARKsはSNARKsにステップアップを促し、Trusted Setupから脱却させることになります。

第五章：柔軟性への挑戦 - ユニバーサルセットアップとカスタムゲート（2019）

2019年は、ゼロ知識証明の歴史における転換点となりました。Sonic、Marlin、そしてPlonkという3つの重要なプロトコルが、ほぼ同時期に登場したのです。というのもMarlinはSonicの大幅な改良版で、証明生成時間を10倍に短縮し、Plonk 「Permutations over Lagrange-bases for Oecumenical Non Interactive Arguments of Knowledge 」の略で、これもまたSONICの改良版でした。

ユニバーサルセットアップ

Groth16では回路ごとに構造化された参照文字列（Structured Reference String）が必要だったのに対して、これらのプロトコルは普遍的で更新可能な構造化された参照文字列（Universal Structured Reference String）を導入することで、Groth16が抱えていたプログラムごとのTrusted Setupという課題に解決策を提示しました。つまり、一度Trusted Setupを行えば、すべてのプログラムに同じパラメーターを使うことができるようになったのです。これによってTrusted Setupの欠点が完全になくなったという訳ではありませんが、間違いなく大きく改善されたと言って良いでしょう。特にPlonkは、新しい算術化スキーム（後にPlonkishと呼ばれる）とコピー制約のためのグランドプロダクトチェックの使用を導入し、カスタムゲートという革新的な概念を実現しました。

カスタムゲート

ここでの大きな革新は、Plonkが通常の加算/乗算以外のカスタムゲートを可能にしたことで、より複雑なプログラムに対してzk証明を構築できるようになったということです。

従来のシステム(例：Groth16など)では、算術回路は主に加算と乗算の基本演算のみで構成されていました。これは複雑な計算を表現する際に、多くの基本演算を組み合わせる必要があり、非効率でした。Plonkは、加算/乗算以外の複雑な演算を直接1つのゲートとして定義できるようになりました。例えば：

• ビット演算（AND, OR, XORなど）
• 条件分岐
• ルックアップテーブル
• より複雑な数学的関数

これにより、下記のメリットをもたらしました。

• 回路サイズの削減：複数の基本演算を1つのカスタムゲートにまとめることで、全体の回路サイズが小さくなります。
• 検証の効率化：より少ないゲートで同じ計算を表現できるため、証明生成と検証が高速化されました。
• 柔軟性の向上：様々な種類の演算を直接表現できるようになり、より複雑なプログラムの証明が可能に。
  EVMのすべての演算（スマートコントラクトの実行に必要な命令セット）をカスタムゲートとして実装できるようになったのです。これは、Ethereum上のあらゆるスマートコントラクトをゼロ知識証明に変換できるようにするものです！

第六章：Lookup Argumentによる効率性の向上

2020年、GabizonとWilliamsonによって導入されたplookupは、ZKPの効率性を大きく向上させる画期的な進展でした。

Lookupの背景と意義

• Plonkの制約は基本的な加算/乗算に限定されており、ビット演算やハッシュ関数など複雑な計算の実装が非効率的でした。特に、SHA-256やAES-128など、ビット単位の操作を多用する暗号アルゴリズムの実装が課題でした。plookupは、頻繁に使用される計算を事前計算されたルックアップテーブルとして扱うことで、この課題を解決しました。

plookupのメカニズム

1. ルックアップテーブル
   • 3列（入力2つと出力1つ）からなる公開テーブルを定義
   • 頻出する計算パターンを事前計算して格納
2. グランドプロダクトチェック
   • テーブル内の値の存在を効率的に証明
   • 値の検索をゼロ知識で実現

発展と影響

plookupの導入は多くのプロジェクトの実装に革新をもたらしました。中でも後に出てくるPlonky2やHalo2などにも影響を与えました。この技術革新により、複雑な暗号計算の実装が大幅に効率化され、ZKPの実用性が飛躍的に向上しました。

第七章：Recursive Proofの登場 - Halo2とPlonky2

ブロックチェーンのスケーラビリティ課題

ブロックチェーンの普及に伴い大きな課題が顕在化していました。メインチェーン上で処理できるトランザクション数には限界があるということです。この課題に対し、メインチェーン外で大量のトランザクションを処理し、その結果だけをメインチェーンに記録するLayer 2ソリューションが注目されていました。しかし、大量のトランザクションの正当性を証明する際、証明自体が巨大になり、検証コストも膨大になるという問題に直面していました。

Recursive Proofによる革新

この課題を解決するために登場したのが、Recursive Proofという革新的な概念です。これは、ある証明の検証自体を別の証明の中で行うことを可能にする技術です。具体的には：

• 大量のトランザクションを小さな単位に分割し、それぞれの証明を生成
• それらの証明の検証を新しい証明の中で行う
• 最終的に、どんなに大きな計算でも、コンパクトな一つの証明にまとめることが可能に

この技術により、Layer 2で処理された大量のトランザクションを、効率的にメインチェーンに反映させることが可能になりました。2020年から2022年にかけて、Recursive Proofの先駆けとなった2つの重要なプロトコルを紹介しましょう。Halo2とPlonky2です。

Halo2の登場（2020）

2020年、ZcashチームはPlonkとBulletproofsの両方の長所を組み合わせ、またRecursive Proofを実現したHalo2（Haloの後継）を発表しました。このプロトコルの革新的な点は：

• Trusted Setupが不要：従来のRecursive Proofで必要だったペアリングベースの高コストな方式とTrusted Setupを不要にしました。（IPAは楕円曲線上の離散対数問題に基づいており、特別なセットアップを必要としない離散対数の仮定のみに依存するため）
• 効率的な実装：Inner Product Argument（IPA）ベースの多項式コミットメントを採用し、Plonkベースの効率的な実装を実現。
• 実用性の向上：より小さな楕円曲線の使用を可能にし、カスタムゲートとルックアップテーブルをサポート。

これらの特徴により、Zcashのスケーラビリティを大幅に向上させ、プライバシー保護と効率性の両立を実現しました。

Plonky2による更なる革新（2022）

2022年、Polygon ZKチームは再帰的証明の性能を劇的に向上させるPlonky2を開発しました。主な特徴は：

• 革新的な組み合わせ：PlonkとFRIプロトコルを組み合わせることで、STARKsの利点とSNARKsの効率性を両立
• 驚異的な速度：64ビットフィールドを効率的に利用し、わずか300ミリ秒という速度でのRecursive Proofを実現
• コンパクトな証明：任意の大きさの計算の証明を約43キロバイトに圧縮
• 将来への対応：FRIの採用により量子コンピュータへの耐性を実現

実用化への影響

Halo2とPlonky2の登場により、ゼロ知識証明の実用性は飛躍的に向上しました。特にブロックチェーンのスケーリングにおいて、Layer 2ソリューションの実用化を大きく前進させました。これらのプロトコルは、それぞれ異なるアプローチでRecursive Proofの課題を解決しブロックチェーン技術の新たな可能性を切り開いたと言えるでしょう。

第八章：Folding schemesの登場 - NovaからSupernovaへ（2021-2023）

2021年までに、ゼロ知識証明の分野では様々なアプローチが提案されていました。STARKsは量子耐性を、Plonkは柔軟性を、そしてHalo2は効率的なRecursive Proofを実現していました。しかし、長時間の計算を効率的に証明するという課題は依然として残されていました。この課題に対して、全く新しいアプローチを提示したのが、NovaのFolding schemesでした。
Folding schemesは、増分的に検証可能な計算（IVC：Incrementally Verifiable Computation）を実現するための画期的なアプローチでした。その特徴は：

1. 証明の合成方法：
   • 長さkの2つの証明を、単一の長さkの証明にマージする
   • 前のステップの証明を新しいステップの証明に「折りたたむ（Folding）」ことで、証明サイズを一定に保つ
2. 効率的な検証：
   • 各ステップでの証明は、前のステップの証明を検証しながら新しい計算の正当性を示す
   • 最終的な証明は、すべてのステップの正当性を保証
3. 技術的特徴：
   • R1CSの緩和バージョンを使用
   • ZKフレンドリーな楕円曲線上で動作
   • 証明者の作業が各ステップで一定

Novaの実装と特徴

Novaの主な特徴は：

• 均一な計算の効率的な処理：同じ種類の計算を繰り返し行う場合に特に効果的
• 小さな検証回路：検証に必要な計算量が非常に少ない
• 柔軟な構造：様々な種類の計算に適用可能

SupernovaによるNovaの拡張

Novaの制限の一つは、均一な計算（同じ種類の計算の繰り返し）しか扱えないことでした。この制限を解決するために開発されたのが2022年 Supernovaです。Supernovaの革新な点は、異なる種類の計算を含む証明も可能にしたことでした。

これはzkVMの実装に多くの貢献をもたらした。

Folding SchemesとVMの関係：

1. IVCの基本概念：

• IVCは「ステップごとに検証可能な計算」を実現する仕組み
• 各ステップの証明を生成し、それらを順次検証していく

2. VMへの応用：

• VMの各命令（ADD, MUL, SUBなど）を「1つのステップ」として扱う
• つまり、各命令の実行を1つのIVCステップとして表現する

3. Novaの制限とSupernovaの重要性：

• Novaは「均一な計算」（同じ種類の計算の繰り返し）のみ扱える
• これはVMの命令セットには適していない（VMは様々な種類の命令を実行する）
• Supernovaは異なる種類の計算を扱えるように拡張された
  • これによりVMの異なる命令（ADD, MUL, SUBなど）をそれぞれ個別のステップとして扱える

4. マッピングの具体例：

VM実行: ADD → MUL → SUB → ADD
↓
IVCステップ: Step1(ADD) → Step2(MUL) → Step3(SUB) → Step4(ADD)

このように、VMの各命令をIVCの個別のステップとして「マッピング（対応付け）」することで、VM全体の実行を効率的に証明することが可能になります。Supernovaによって、異なる種類の命令を効率的に扱えるようになったことが、これを実現可能にした重要なブレークスルーでした。

第九章：新たな地平線 - より効率的な証明を目指して（2023-2024）

2023年から2024年にかけて、ゼロ知識証明の研究は新たな効率化への挑戦を見せています。特に注目すべきは、STIRとBiniusという2つの重要な研究成果です。

STIRによる証明サイズの削減

2023年、STIRという新しい手法が提案されました。これは、STARKsで使用されているFRIプロトコルを改良したものです。FRIプロトコルでは、計算の正しさを証明するために、多項式の評価値を複数のポイントでチェックします。この時、多項式をどの点で評価するかを定めた集合を「評価ドメイン」と呼びます。FRIでは、このチェックに多くのデータが必要で、結果として証明サイズが大きくなってしまうという課題がありました。
STIRは以下のような改善を行いました：

• チェック方法の効率化：
  • 従来のFRIでは、同じサイズの評価ポイント集合を使用
  • STIRでは、段階的により小さな集合でのチェックを可能に
  • この結果、必要なデータ量を大幅に削減
• この工夫により、以下のような改善を実現：
  • 証明サイズの大幅な削減
  • 検証にかかる時間の短縮
  • ブロックチェーン上での検証コストの削減
    ただし、証明の生成時間は約15%増加するというトレードオフがあります。しかし、多くの計算をまとめて処理する場合、この増加は実質的にはほとんど影響がないとされています。

Biniusによるデータ型表現の効率化

同時期に登場したBiniusは、計算を行う体（フィールド）としてバイナリ体（要素が0と1のみの体）を使用することで、新しいアプローチを提案しました。従来のシステムでは、1ビットの情報を表現するのに、より大きなフィールド（例：256ビットの素体）の要素を使用する必要がありました。
Biniusはこの課題に対して：

• より効率的なデータ表現：
  • バイナリ体を使うことで、1ビットの情報を1ビットのまま扱える
  • 結果として、メモリ使用量を大幅に削減
  • ハードウェアでの実装も容易に
• この結果、以下のような利点が得られました：
  • メモリ使用量の大幅な削減：
    • 1ビットの情報を256ビットで表現する必要がなくなった
    • データ構造がよりコンパクトに
  • 処理速度の向上：
    • バイナリ演算はハードウェアで非常に効率的に実行可能
    • キャリー伝播が不要なため、演算がシンプル
  • 既存のハッシュ関数との相性が良い：
    • SHA-2やKeccakなど、広く使われているハッシュ関数と親和性が高い
    • 従来のPoseidonハッシャーと比べて50-200倍の効率性
  • 柔軟なデータ型の提供：
    • 1ビット、8ビット、16ビットなど、必要に応じて最適なサイズを選択可能
    • それぞれのデータ型に対して効率的な演算が可能
      このように、Biniusはデータをよりナチュラルな形で表現することで、計算効率とメモリ効率の両面で大きな改善を実現しました。これは特にブロックチェーンのようなリソースが制限された環境での応用において、重要な進歩となっています。

エピローグ：継続する革新

ゼロ知識証明は、1985年のGoldwasserらの論文から始まり、約40年の間に驚くべき進化を遂げてきました。この技術は、当初は純粋な暗号理論の研究対象でしたが、今や実用的なシステムとして、プライバシー保護やブロックチェーンのスケーラビリティ向上など、現実世界の課題解決に貢献しています。

この進化の過程で、私たちは多くの重要な革新を目にしてきました。Groth16による効率的な証明生成、Plonkによるカスタムゲートの導入、Halo2とPlonky2によるRecursive Proofの実現、NovaとSupernovaによるFolding Schemesの確立、そして最近のSTIRとBiniusによる更なる効率化など、各時代の研究者たちは常に新しい課題に挑戦し続けてきました。

これらの大切な点は、革新が単なる理論的な進歩にとどまらず、常に実用性を意識して進められてきたことです。例えば、Trusted Setupの改善、証明サイズの削減、計算効率の向上など、実装上の課題を一つずつ解決してきました。初めはSTARKsの技術だと思われていたFRIをSNARKsに応用して、そうすることでSTIRとしてFRIの改良版ができたりしています。すでにTrusted SetupがないSNARKsもあるなど、SNARKsかSTARKsかという判別ではなく、証明システムにおけるさまざまな部品が融合しながら、技術全体を豊かにしてきました。

現在、ゼロ知識証明は新たな応用の地平を広げつつあります。プライバシー保護やスケーラビリティの向上だけでなく、分散型アイデンティティ、オンライン投票システム、さらにはAIモデルの検証など、その可能性は私たちの想像を超えて広がっています。
この技術の未来は、まさに今も形作られ続けています。研究者たちは、より効率的で使いやすく、そして安全な証明システムの開発に取り組んでいます。そして、この技術が私たちの社会にもたらす変革は、おそらくまだ始まったばかりなのでしょう。
ゼロ知識証明の歴史は、純粋な理論研究から始まり、実用的な技術へと発展してきた、知的探求と技術革新の壮大な物語です。そして、この物語は今なお続いているのです。