ゼロ知識証明が長年にわたり新しく、斬新なイノベーションを生み出し続けている理由は何でしょうか？

執筆：LambdaClass

翻訳：mutourend；Yiping，IOSG Ventures

1. はじめに

ゼロ知識、簡潔かつ非対話型の知識証明（zk-SNARKs）は、ある命題が正しいことを証明者が検証者に納得させつつ、その命題以外の情報を一切漏らさない強力な暗号学的プリミティブである。可視化可能なプライベート計算、コンピュータプログラム実行の正しさの証明、およびブロックチェーンのスケーラビリティへの応用により、zk-SNARKsは広く注目されている。我々は、この記事で述べるように、zk-SNARKsが世界を形作る上で大きな影響を与えると考えている。zk-SNARKsには、異なる多項式コミットメント方式、算術化スキーム、対話型オラクル証明または確率的検証可能証明を用いたさまざまなタイプの証明システムが含まれる。しかし、これらの基本的なアイデアや概念は1980年代半ばまで遡ることができる。

ビットコインやイーサリアムの登場以来、zk-SNARKsの発展は大きく加速した。これは、ゼロ知識証明（通常この特定の用途では有効性証明と呼ばれる）を用いてスケーリングできるためである。zk-SNARKsはブロックチェーンのスケーラビリティにおいて極めて重要な役割を果たしている。Ben-Sassonが述べたように、近年は暗号証明の「カンブリア爆発」が見られた。各証明システムには長所と短所があり、特定のトレードオフを念頭に置いて設計されている。ハードウェア、アルゴリズム、新たな証明手法、ツールの進歩が性能を常に向上させ、新しいシステムの誕生を促している。こうしたシステムの多くはすでに実用化されており、我々は境界を押し広げ続けている。すべてのアプリケーションに適した汎用的な証明システムが生まれるのか、それとも異なるニーズに対応する複数のシステムが共存するのか？　我々は、以下のような理由から、一つの証明システムが他のすべてを支配する可能性は低いと考えている。

1）アプリケーションの多様性。

2）制約の種類の違い（メモリ、検証時間、証明生成時間に関するもの）。

3）堅牢性の必要性（ある証明システムが破られた場合でも、代替となる他のシステムがあること）。

証明システムは大きく変化しても、すべてが重要な特性を提供している：証明は高速に検証可能であるということだ。証明を検証でき、新しく登場する証明システムにも容易に適応可能なレイヤーを持つことで、ベースレイヤー（例えばイーサリアム）の変更に関連する困難を解決できる。本稿では、SNARKsの異なる特徴について概説する。

1）暗号学的仮定：衝突耐性ハッシュ関数、楕円曲線上の離散対数問題、knowledge of exponent。

2）透明 vs 信頼されたセットアップ。

3）証明生成時間：線形 vs 超線形。

4）検証者時間：定数時間、対数時間、準線形、線形。

5）proof size（証明サイズ）。

6）再帰のしやすさ。

7）算術化スキーム。

8）単変数多項式 vs 多変数多項式。

本稿では、SNARKsの起源、いくつかの基本構成要素、および異なる証明システムの台頭（および衰退）について考察する。本稿は証明システムの網羅的分析を意図したものではない。むしろ、我々にとって影響の大きかったものに焦点を当てる。もちろん、こうした発展は、分野の先駆者たちの偉大な仕事とアイデアがあってこそ可能となったものである。

2. 基礎知識

ゼロ知識証明は新しいものではない。定義、基礎、重要な定理、重要なプロトコルの多くは1980年代半ばにすでに策定されていた。現代のSNARKs構築に使われるいくつかの鍵となるアイデアやプロトコルも1990年代に提唱されている（sumcheckプロトコル）、あるいはビットコイン登場以前（2007年のGKR）にまで遡る。その主な利用障壁は、強力なユースケースの欠如（1990年代のインターネットは未発達だった）と、必要な計算能力の高さにあった。

1）ゼロ知識証明：起源 (1985/1989)。

ゼロ知識証明の分野は、Goldwasser、Micali、Rackoffによる論文『The knowledge complexity of interactive proof systems』によって学術文献に登場した。起源については、2023年1月の動画 ZKP MOOC Lecture 1: Introduction and History of ZKP を参照。この論文は完全性、健全性、ゼロ知識性の概念を導入し、quadratic residuosityおよびquadratic non-residuosityに対する構成を提示した。

2）Sumcheck プロトコル (1992)。

sumcheckプロトコルは、Lund、Fortnow、Karloff、Nisanによる1992年の論文『Algebraic Methods for Interactive Proof Systems』で提案された。これは簡潔な対話型証明における最も重要な構成要素の一つであり、多変数多項式の評価和に関する要求を、ランダムに選ばれた一点での単一評価に還元するのに役立つ。

3）Goldwasser-Kalai-Rothblum (GKR) (2007)。

GKRプロトコル（論文『Delegating Computation: interactive Proofs for Muggles』参照）は、回路のゲート数に対して線形時間で動作する証明者と、回路サイズに対して準線形時間で動作する検証者を持つ対話型プロトコルである。このプロトコルでは、深さ d の有限体上の二分木演算回路について、証明者と検証者が合意する。ここでlayer dが入力層、layer 0が出力層に対応する。プロトコルは回路出力に関する主張から始まり、それが前の層の値に関する主張に還元される。再帰的に適用することで、最終的に回路入力に関する主張に変換され、簡単に検証できるようになる。これらの還元はsumcheckプロトコルを通じて実現される。

4）KZG 多項式コミットメント方式 (2010)。

Kate、Zaverucha、Goldbergは2010年の論文『Constant-Size Commitments to Polynomials and Their Applications』で、双線形ペアリング群を用いた多項式コミットメント方式を導入した。コミットメントは単一の群要素からなり、コミットメント保持者は多項式の任意の正しい評価に対して効率的に開示できる。また、バッチング技術により、複数の評価を同時に開示することも可能である。KZGコミットメントはPinocchio、Groth16、Plonkなど、いくつかの効率的なSNARKsの基本構成要素の一つとなっている。また、EIP-4844の中心にもなっている。バッチング技術の直感的理解は、Mina to Ethereum ZK bridgeを参照。

3. 楕円曲線を用いた実用的な SNARKs

SNARKsの最初の実用的な構成は2013年に登場した。これらの構成は、証明鍵と検証鍵を生成する前処理ステップを必要とし、プログラム／回路固有のものである。これらの鍵は非常に大きくなる可能性があり、全当事者が知らない秘密パラメータに依存する。そうでなければ、証明を偽造できる。コードを証明可能な形式に変換するには、コードを多項式制約系にコンパイルする必要がある。当初はこれを手動で行う必要があり、時間と労力を要し、エラーが起こりやすかった。この分野の進展は、以下の主要な問題を解消しようとしている。

1）より効率的な証明者を持つこと。

2）前処理量の削減。

3）回路固有ではなく汎用的なセットアップを持つこと。

4）信頼されたセットアップの回避。

5）多項式制約を手書きするのではなく、高水準言語で回路を記述する方法を開発すること。

現在、楕円曲線を用いた実用的なSNARKsの方式には以下がある。

1）Pinocchio (2013)

2）Groth 16 (2016)

3）Bulletproofs & IPA (2016)

4）Sonic, Marlin, and Plonk (2019)

5）Lookups (2018/2020)

6）Spartan (2019)

7）HyperPlonk (2022)

8）Folding schemes (2008/2021)

3.1 Pinocchio (2013)

Pinocchio（論文『Pinocchio: Nearly Practical Verifiable Computation』参照）は、最初の実用的かつ利用可能なzk-SNARKである。このSNARKは二次算術プログラム（quadratic arithmetic programs, QAP）に基づいている。証明サイズは当初288バイトであった。PinocchioのツールチェーンはCコードから算術回路へのコンパイラを提供し、さらにそれをQAPへ変換する。このプロトコルでは、検証者が回路固有の鍵を生成する必要がある。方程式のチェックには楕円曲線ペアリングを使用する。証明生成と鍵設定の漸近的計算量は計算サイズに対して線形であり、検証時間は公開入出力のサイズに対して線形である。

3.2 Groth 16 (2016)

Grothの2016年論文『On the Size of Pairing-based Non-interactive Arguments』は、R1CSで記述された問題の性能を向上させる新しい知識証明を導入した。これは最小の証明サイズ（わずか3つの群要素）と、3つのペアリングを含む高速な検証を特徴とする。また、構造化されたリファレンス文字列を取得する前処理ステップを含む。主な欠点は、証明対象の各プログラムごとに異なる信頼されたセットアップが必要なことであり、これは不便である。Groth16はZCashで使用された。詳細はブログ『An overview of the Groth 16 proof system』を参照。

3.3 Bulletproofs & IPA (2016)

KZG PCSの弱点の一つは信頼されたセットアップが必要なことである。Bootleらの2016年論文『Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting』では、内積（inner product）関係を満たすPedersenコミットメントの開示に対する、効率的なゼロ知識証明システムを導入した。内積証明システムは線形時間の証明者を持ち、対数通信・対話的だが、検証時間は線形である。また、信頼されたセットアップを必要としない多項式コミットメント方式も開発された。Halo 2およびKimchiは、IPA PCSのアイデアを採用している。

3.4 Sonic, Marlin, and Plonk (2019)

Sonic、Plonk、Marlinは、汎用的かつ更新可能な構造化リファレンス文字列を導入することで、Groth16における各プログラムごとの信頼されたセットアップの問題を解決した。MarlinはR1CSに基づく証明システムを提供し、Aleoの基盤となっている。

Plonkは新しい算術化スキーム（後にPlonkishと呼ばれる）を導入し、copy constraintsに対してgrand-product checkを使用した。Plonkishは特定の操作のために特別なゲート（いわゆるカスタムゲート）を導入することも可能にする。複数のプロジェクトがPlonkのカスタム版を採用しており、Aztec、ZK-Sync、Polygon ZKEVM、Mina's Kimchi、Plonky2、Halo 2、Scrollなどが含まれる。ブログ『All you wanted to know about Plonk』を参照。

3.5 Lookups (2018/2020)

GabizonとWilliamsonは2020年にplookupを導入し、grand product checkを用いてある値が事前に計算された値のテーブルに含まれることを証明した。以前にAryaでlookup引数が提案されていたが、その構成はmultiplicitiesを決定する必要があり、効率が低かった。PlonkUp論文は、plookup引数をPlonkに組み込む方法を示した。これらのlookup引数の問題は、証明者が使用頻度に関係なくテーブル全体のコストを負担しなければならないことにある。つまり、大規模なテーブルではコストがかなり大きくなるため、証明者のコストを実際のlookup数に比例させるよう多くの努力が払われてきた。

HaböckはLogUpを導入し、対数微分を用いて積のチェックを逆数の和に変換した。LogUpはPolygon plonky2 ZKEVM（Beyond Limits: Pushing the Boundaries of ZK-EVM）の性能にとって不可欠であり、ここではテーブル全体を複数のSTARKモジュールに分割する必要がある。これらのモジュールは正しくリンクされ、クロステーブルのlookupによって操作が補強される。LogUp-GKRの導入はGKRプロトコルを活用してLogUpの性能を向上させた。Caulkは、証明者の時間 complexity がテーブルサイズに対して準線形となる最初のlookup引数であり、前処理時間はO(N log N)、ストレージはO(N)である（Nはテーブルサイズ）。その後、Baloo、flookup、cq、caulk+などの他のスキームが続いた。Lassoは、表が特定の構造を持つ場合にcommitを回避するといったいくつかの改善を提案した。さらに、Lassoの証明者はlookup操作でアクセスした表エントリのみに課金される。JoltはLassoを利用して、lookupを通じて仮想マシンの実行を証明する。

3.6 Spartan (2019)

SpartanはR1CSで記述された回路に対してIOPを提供し、多変数多項式とsumcheckプロトコルの性質を利用する。適切な多項式コミットメント方式を用いれば、証明者が線形時間で動作する透明なSNARKを生成する。

3.7 HyperPlonk (2022)

HyperPlonkは、多変数多項式を用いたPlonkの思想に基づいて構築されている。制約のチェックには商に依存せず、sumcheckプロトコルに依存している。また、証明者の実行時間を損なうことなく高次制約をサポートする。多変数多項式に依存するため、FFTを実行する必要がなく、証明者の実行時間は回路サイズに対して線形である。HyperPlonkは、小さな体に適した新しいpermutation IOPおよびsumcheckに基づくバッチ開示プロトコルを導入しており、これにより証明者の作業量、証明サイズ、検証者時間の削減を実現している。

3.8 Folding schemes (2008/2021)

Novaはfolding schemeの概念を導入し、これは増分的検証可能計算（IVC）を実現する新しい手法である。IVCの概念はValiantに遡り、長さkの2つの証明を、長さkの1つの証明に統合する方法を示している。考え方は、step iからstep i+1への実行が正しく、かつstep i-1からstep iへの遷移証明が正しいことを再帰的に証明することで、長期間にわたる任意の計算を証明できるというものである。

Novaはuniform computationをうまく扱える。その後Supernovaの導入により、異なる種類の回路を扱えるように拡張された。NovaはR1CSの緩いバージョンを使用し、友好的な楕円曲線上で動作する。Picklesでは、IVCを実現するために友好的な曲線サイクル（例：Pasta曲線）が使用されており、これはMinaの主要な基盤モジュールとして、簡潔な状態を実現している。しかし、foldingの考え方は再帰的SNARK検証とは異なる。アキュムレータの考え方は、proofsのバッチングという概念とより深く関連している。Haloは、累積の概念を再帰的証明合成の代替案として導入した。ProtostarはPlonk向けにnon-uniform IVCスキームを提供し、high-degree gatesおよびvector lookupsをサポートしている。

4. 衝突耐性ハッシュ関数を用いた SNARKs

Pinocchioの開発とほぼ同時に、仮想マシンの実行の正当性を証明できるような回路／算術スキームを生成するアイデアが登場した。専用回路を書くよりも仮想マシンの算術化の方が複雑または非効率的かもしれないが、利点は、いかに複雑なプログラムであっても、それが仮想マシン内で正しく実行されることを証明できることにある。TinyRAMのアイデアは、Cairo VMやその後継の仮想マシン（zk-EVMや汎用zkVMなど）の設計とともに改良されてきた。衝突耐性ハッシュ関数の使用は、信頼されたセットアップや楕円曲線演算の必要性を排除するが、その代償として証明が長くなる。

1）TinyRAM (2013)

『SNARKs for C』では、Cプログラムの実行の正当性を証明するための、PCPに基づくSNARKが開発された。これはTinyRAM（精簡命令セットコンピュータ）にコンパイルされる。このコンピュータはハーバードアーキテクチャを持ち、バイト単位でアドレス指定可能なランダムアクセスメモリを持つ。非決定性を利用することで、回路サイズは計算サイズに対して準線形（quasilinear）の関係となり、任意のデータ依存ループ、制御フロー、メモリアクセスを効率的に処理できる。

2）STARKs (2018)

STARKsはBen Sassonらにより2018年に提案された。実装された証明サイズはO(log²n)であり、高速な証明者と検証者を持ち、信頼されたセットアップが不要で、後量子安全と見なされている。最初にStarkware/StarknetがCairo仮想マシンとともに使用した。主な構成要素は以下の通り。

• 代数中間表現 (AIR)

• およびFRIプロトコル（Fast Reed-Solomon Interactive Oracle Proof of Proximity）。

STARKsは他のプロジェクト（Polygon Miden、Risc0、Winterfell、Neptune）でも使用されている、あるいはその派生（ZK-SyncのBoojum、Plonky2、Starky）が存在する。

3）Ligero (2017)

• Ligeroは証明サイズがO(√n)の証明システムを導入した（nは回路サイズ）。多項式係数を行列形式に並べ、線形符号（linear codes）を使用する。

• BrakedownはLigeroを基盤とし、体に依存しない多項式コミットメント方式の考えを導入した。

5. ZKP の新たな進展

異なる証明システムを実運用で使うことで、それぞれのアプローチの長所が明らかになり、新たな発展をもたらした。たとえば、plonkish算術化はカスタムゲートやlookup引数を簡単に含める方法を提供した。FRIはPCSとして優れた性能を示し、Plonkyを凌駕した。同様に、AIRにgrand product checkを用いることで（事前処理付きのランダム化AIRにつながる）性能が向上し、メモリアクセス引数が簡素化された。ハッシュ関数に基づくコミットメントは普及した――ハードウェア上でのハッシュ関数の速度の高さ、あるいは新しいSNARKフレンドリーなハッシュ関数の導入によるものだ。

1）新しい多項式コミットメント方式（2023）

SpartanやHyperPlonkのような多変数多項式に基づく効率的なSNARKの登場により、このような多項式に適した新しいコミットメント方式への関心が高まっている。Binius、Zeromorph、Basefoldはいずれも、多線形多項式に取り組むための新しい形式を提案している。Biniusはデータ型をゼロオーバーヘッドで表現できる利点を持つ（多くの証明システムは1bitを表現するために少なくとも32bitの体要素を使用する）だけでなく、バイナリ体上で動作する。BiniusコミットメントはBrakedownに基づき、体に依存しない設計である。BasefoldはFRIをReed-Solomon以外の符号に一般化することで、体に依存しないPCSを形成する。

2）Customizable Constraint Systems（CCS） (2023)

CCSはR1CSを一般化し、オーバーヘッドなしにR1CS、Plonkish、AIR算術を捉える。CCSをSpartan IOPと組み合わせるとSuperSpartanが得られ、high-degree制約をサポートしつつ、証明者が制約次数に比例して暗号コストを負担することはない。特に、SuperSpartanは証明者が線形時間で動作するAIR向けSNARKを生成する。

6. 結論

本稿では、1980年代半ば以降のSNARKの進歩を述べた。コンピュータ科学、数学、ハードウェアの進歩に加え、ブロックチェーンの導入が、新しい、より効率的なSNARKを生み出し、社会を変える多くのアプリケーションへの扉を開いた。研究者やエンジニアは自らのニーズに応じてSNARKsの改良や調整を行い、証明サイズ、メモリ使用量、透明なセットアップ、後量子安全性、証明者時間、検証者時間に重点を置いている。

当初は二つの流れ（SNARKとSTARK）があったが、両者の境界は曖昧になり始め、異なる証明システムの長所を組み合わせようとする動きがある。たとえば、異なる算術化スキームと新しい多項式コミットメント方式を組み合わせることなどである。今後も新たな証明システムが登場し、性能が向上していくことが予想される。一方で、一部のシステムはこれらの発展に追いつくのが難しくなるだろう。ただし、コアインフラを変更せずにこれらのツールを容易に使えるようにすれば、状況は変わるかもしれない。