ゼロ知識証明の新しい革新が生まれ続ける真の理由を探求する

執筆：LambdaClass

編纂：mutourend；Yiping，IOSG Ventures

1. はじめに

ゼロ知識、簡潔、非対話型証明（zk-SNARKs）は、証明者が検証者に対してある主張の正しさを証明することを可能にする強力な暗号学的原理であり、主張以外の情報を開示することなく行われます。zk-SNARKsは、検証可能なプライベート計算、コンピュータプログラムの実行の正しさの証明、ブロックチェーンのスケーラビリティにおいて広く注目されています。私たちは、この記事で述べるように、zk-SNARKsが世界を形作る上で重要な影響を与えると信じています。zk-SNARKsは、異なる多項式コミットメントスキーム、算術化スキーム、対話型オラクル証明、または確率的に検証可能な証明を使用する異なるタイプの証明システムを含んでいますが、これらの基本的なアイデアと概念は1980年代中頃に遡ります。

ビットコインとイーサリアムの登場以来、zk-SNARKsの発展は大きく加速しました。これは、ゼロ知識証明（通常はこの特定のユースケースの有効性証明と呼ばれる）を使用してスケーラビリティを実現できるからです。zk-SNARKsは、ブロックチェーンのスケーラビリティにおいて重要な役割を果たしています。Ben-Sassonが述べたように、近年、暗号証明のカンブリア爆発が見られました。各証明システムには利点と欠点があり、設計時には特定のトレードオフが考慮されています。ハードウェア、アルゴリズム、新しい証明とツールの進歩は、性能を向上させ、新しいシステムの誕生を促進しています。これらのシステムの多くはすでに実用化されており、私たちは限界を常に突破しています。すべてのアプリケーションに適した汎用証明システムを持つことができるのか、それとも異なるニーズに適したいくつかのシステムが存在するのか？私たちは、1つの証明システムが他のすべてのシステムを支配する可能性は低いと考えています。その理由は以下の通りです：

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

2）異なる制約の種類（メモリ、検証時間、証明時間に関する）。

3）ロバスト性の要求（ある証明システムが破損した場合、他の証明システムが存在する）。

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

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

2）透明性 vs 信頼できる設定。

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

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

5）証明サイズ。

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を視聴することで確認できます。この論文は、完備性、信頼性、ゼロ知識性の概念を導入し、二次残余性と二次非残余性の構成を提供しました。

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

sumcheckプロトコルは、Lund、Fortnow、Karloff、Nisanによって1992年の論文「Algebraic Methods for Interactive Proof Systems」で提案されました。これは、簡潔な対話型証明の最も重要な構成要素の1つです。これは、多変数多項式の評価の要求をランダムに選択された点の単一の評価に減らすのに役立ちます。

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

GKRプロトコル（論文「Delegating Computation: interactive Proofs for Muggles」を参照）は、証明者が回路のゲート数に対して線形に動作し、検証者が回路のサイズに対して亜線形に動作する対話型プロトコルです。このプロトコルでは、証明者と検証者は、深さdの有限体のファンイン2演算回路に合意します。ここで、層dは入力層に対応し、層0は出力層に対応します。このプロトコルは、回路出力に関する声明から始まり、その声明は前の層の値に関する声明に簡略化されます。再帰を使用すると、これを回路入力に関する声明に変換でき、簡単に検証できます。これらの削減は、sumcheckプロトコルを通じて実現されます。

4）KZG多項式コミットメントスキーム (2010)。

Kate、Zaverucha、Goldbergは、2010年の論文「Constant-Size Commitments to Polynomials and Their Applications」で、双線形ペアリング群を使用した多項式コミットメントスキームを導入しました。コミットメントは単一の群要素で構成され、コミット者は多項式の任意の正しい評価を効果的に開くことができます。さらに、バッチ処理技術により、複数の評価を開くことができます。KZGコミットメントは、Pinocchio、Groth16、Plonkなどのいくつかの効率的なSNARKの基本構成要素の1つを提供します。また、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、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の弱点の1つは、それが信頼できる設定を必要とすることです。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、Plonk (2019)

Sonic、Plonk、Marlinは、Groth16における各プログラムの信頼できる設定の問題を解決するために、汎用かつ更新可能な構造化リファレンス文字列を導入しました。MarlinはR1CSに基づく証明システムを提供し、Aleoの核心です。

Plonkは新しい算術化スキーム（後にPlonkishと呼ばれる）を導入し、コピー制約にグランドプロダクトチェックを使用します。Plonkishは、特定の操作のために特別なゲート、いわゆるカスタムゲートを導入することも許可します。複数のプロジェクトには、Aztec、ZK-Sync、Polygon ZKEVM、MinaのKimchi、Plonky2、Halo 2、ScrollなどのPlonkのカスタムバージョンがあります。ブログ「All you wanted to know about Plonk」を参照してください。

3.5 Lookups (2018/2020)

GabizonとWilliamsonは2020年にplookupを導入し、グランドプロダクトチェックを使用して特定の値が事前に計算された値のリストに含まれていることを証明します。以前にAryaで提案されたlookup argumentsはありましたが、その構成はlookupの重複を特定する必要があり、効率が低いものでした。PlonkUp論文は、plookup argumentをPlonkに導入する方法を示しています。これらのlookup argumentsの問題は、証明者が全体のテーブルに対して費用を支払うことを強制されることであり、lookupの回数に関係なく発生します。これは、大型テーブルのコストが非常に大きくなることを意味し、証明者のコストを使用するlookupの数にまで引き下げるために多くの努力が投入されています。

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

3.6 Spartan (2019)

Spartanは、R1CSで記述された回路に対してIOPを提供し、多変数多項式とsumcheckプロトコルの特性を利用します。適切な多項式コミットメントスキームを使用すると、線形時間の証明者を持つ透明なSNARKを生成します。

3.7 HyperPlonk (2022)

HyperPlonkは、多変数多項式を使用したPlonkのアイデアに基づいて構築されています。これは、制約の実行をチェックするために商に依存するのではなく、sumcheckプロトコルに依存します。また、証明者の実行時間を損なうことなく、高次の制約をサポートします。多変数多項式に依存しているため、FFTを実行する必要がなく、証明者の実行時間は回路サイズに対して線形関係を持ちます。HyperPlonkは、小さな体に適した新しい順列IOPと、sumcheckに基づくバッチオープニングプロトコルを導入し、証明者の作業量、証明サイズ、検証者の時間を削減します。

3.8 Folding schemes (2008/2021)

Novaは、増分検証可能計算（IVC）を実現する新しい方法としてfoldingスキームのアイデアを導入しました。IVCの概念はValiantに遡り、長さkの2つの証明を長さkの証明に統合する方法を示しました。このアイデアは、再帰的な証明を通じて、ステップiからステップi + 1の実行が正しいことを証明し、ステップi - 1からステップiへの遷移証明が正しいことを検証することによって、長時間実行される計算を証明することができます。

Novaは均一な計算をうまく処理できますが、その後Supernovaの導入により、さまざまなタイプの回路を処理するように拡張されました。NovaはR1CSの緩やかなバージョンを使用し、友好的な楕円曲線上で動作します。友好的な曲線サイクル（例えば、Pasta曲線）を使用してIVCを実現することは、Picklesでも使用され、PicklesはMinaの主要な基盤モジュールであり、簡潔な状態を実現します。しかし、foldingのアイデアは再帰的SNARK検証とは異なります。累積器のアイデアは、バッチ証明の概念とより深く関連しています。Haloは、再帰的証明の組み合わせの代替手段として累積の概念を導入しました。Protostarは、Plonkに対して非均一IVCスキームを提供し、高次ゲートとベクトルルックアップをサポートします。

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

Pinocchioの開発と同時に、仮想マシンの実行の正しさを証明するための回路/算術スキームを生成するいくつかのアイデアが登場しました。仮想マシンの算術を開発することは、特定のプログラムのために専用回路を作成するよりも複雑または効率が低いかもしれませんが、どんなに複雑なプログラムでも、仮想マシン内で正しく実行されることを証明することで証明できるという利点があります。TinyRAMのアイデアは、その後Cairo vmや後続の仮想マシン（zk-evmsや汎用zkvms）の設計とともに改善されました。衝突耐性ハッシュ関数を使用することで、信頼できる設定や楕円曲線演算の使用が不要になりますが、その代償としてより長い証明が必要になります。

1）TinyRAM (2013)

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

2）STARKs (2018)

STARKsは、Ben Sassonらによって2018年に提案されました。その実現した証明サイズはO(log2n)であり、迅速な証明者と検証者を持ち、信頼できる設定を必要とせず、後量子安全と見なされています。最初に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は回路サイズです。これは、多項式の係数を行列形式に配置し、線形符号を使用します。

BrakedownはLigeroに基づいて構築され、体に依存しない多項式コミットメントスキームのアイデアを導入しました。

5. ZKPのいくつかの新しい進展

さまざまな証明システムを生産で使用することで、各アプローチの利点が示され、新しい進展がもたらされました。たとえば、plonkish算術化はカスタムゲートやlookup argumentsを含めるための簡単な方法を提供し、FRIはPCSとして優れた性能を示し、Plonkyをリードしています。同様に、AIRでのグランドプロダクトチェックの使用（前処理されたランダム化AIRをもたらす）は、その性能を向上させ、メモリアクセスargumentsを簡素化しました。ハッシュ関数に基づくコミットメントは人気を博し、ハードウェアにおけるハッシュ関数の速度や新しいSNARKフレンドリーハッシュ関数の導入に基づいています。

1）新しい多項式コミットメントスキーム（2023）

多変数多項式に基づく効率的なSNARK（SpartanやHyperPlonkなど）の登場に伴い、このような多項式に適した新しいコミットメントスキームへの関心が高まっています。Binius、Zeromorph、Basefoldは、マルチリニア多項式に取り組む新しい形式を提案しました。Biniusは、データ型を表現するためのゼロコストの利点を持ち（多くの証明システムが単一のビットを表現するために少なくとも32ビットの体要素を使用するのに対し）、バイナリ体で動作します。BiniusコミットメントはBrakedownに基づいており、体に依存しないことを目的としています。BasefoldはFRIをReed-Solomon以外のコードに拡張し、体に依存しないPCSを形成します。

2）カスタマイズ可能な制約システム（CCS） (2023)

CCSはR1CSを要約し、R1CS、Plonkish、AIRの算術をキャプチャし、オーバーヘッドなしで行います。CCSをSpartan IOPと組み合わせることで、SuperSpartanが生成され、高次制約をサポートし、証明者が制約の次数に応じて拡張される暗号コストを負担する必要がなくなります。特に、SuperSpartanは線形時間の証明者を持つAIRにSNARKを生成します。

6. 結論

本稿では、SNARKが1980年代中頃に登場して以来の進展を説明しました。計算機科学、数学、ハードウェアの進歩に加え、ブロックチェーンの導入が新しい、より効率的なSNARKを生み出し、私たちの社会を変える可能性のある多くのアプリケーションへの扉を開きました。研究者やエンジニアは、自身のニーズに基づいてSNARKsの改善や調整を提案し、証明サイズ、メモリ使用量、透明な設定、後量子安全性、証明者時間、検証者時間に重点を置いています。

最初は2つの主要なライン（SNARKとSTARK）がありましたが、両者の境界は薄れ始め、異なる証明システムの利点を組み合わせようとしています。たとえば、異なる算術スキームと新しい多項式コミットメントスキームを組み合わせることが挙げられます。新しい証明システムが引き続き登場し、性能が向上することが予想されますが、いくつかのシステムは適応に時間がかかるため、これらの進展に追いつくのは難しいでしょう。これらのツールを簡単に使用できるようにし、コアインフラストラクチャの一部を変更することなく行えるようにする必要があります。