知識ゼロが歴史を証明する

出典：Denchainコミュニティ

ゼロ知識・簡潔・非対話的知識証明（zk-SNARKs）は、一方の当事者（証明者）が、もう一方の当事者（検証者）に対して、ある文が真実であることを、その文の正当性以外を明らかにすることなく納得させることができる強力な暗号プリミティブです。検証可能な私的計算への応用、コンピュータプログラムの実行が正しいことの証明、ブロックチェーンの拡張に役立つことから、多くの注目を集めている。SNARKは、私たちの論文^[6]で説明したように、私たちの世界を形成する上で重要な影響を持つと私たちは信じています。SNARKは、異なる多項式コミットメントスキーム（PCS）、算術化スキーム、対話型オラクル証明（IOP）、または確率的にチェック可能な証明（PCP）を使用するさまざまなタイプの証明システムの包括的な用語として機能します。PCP)などがある。しかし、これらの基本的なアイデアやコンセプトは1980年代半ばにさかのぼる。SNARKはブロックチェーンのスケーラビリティにとって重要なツールである。Ben-Sasson氏が説明するように、ここ数年、暗号証明のカンブリア爆発^[7]が起きています。どの証明システムにも利点と欠点があり、特定のトレードオフを念頭に置いて設計されている。ハードウェアの進歩、より優れたアルゴリズム、新しい議論や小道具によって、性能が向上し、新しいシステムが登場している。これらのシステムの多くは実戦で使用されており、我々はその限界を押し広げ続けている。すべてのアプリケーションに対応する普遍的な証明システムは1つになるのだろうか、それとも異なるニーズに対応する複数のシステムができるのだろうか？

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

2. さまざまな種類の制約がある（メモリ、検証時間、証明時間）。

3. 堅牢性の必要性（証明システムが壊れても、他のシステムがある）。

証明システムが大きく変わったとしても、証明は素早く検証できるという重要な特性があります。基礎となるレイヤー(例えばイーサネット)を変更することに伴う困難も、証明を検証し、新しい証明システムを扱うために簡単に適応できるレイヤーを持つことで対処できます。

SNARKのさまざまな機能の概要を説明します：

• 暗号の仮定：衝突に強いハッシュ関数、楕円曲線上の離散対数問題、指数関数的知識。

• 透明な設定と信頼できる設定。

• 証明時間：線形対超線形。

• プローバ時間：一定時間、対数、準線形、線形。

• 証明サイズ。

• 再帰的な利便性。

• 算術スキーム。

• 単調多項式と多変量多項式。

この論文では、SNARKの起源、基本的な構成要素、さまざまな証明システムの台頭（と衰退）について見ていきます。本稿は、証明システムの網羅的な分析を意図しているわけではない。その代わり、現在の私たちに影響を与えたものに焦点を当てる。もちろん、これらの発展は、この分野の先駆者たちの偉大な仕事とアイデアによってのみ可能となったものである。

基礎

述べたように、知識ゼロ証明は新しいものではありません。定義、基礎、重要な定理、さらには重要なプロトコルは1980年代半ばから確立されていました。現代のSNARKを構築するために使用されている重要なアイデアやプロトコルのいくつかは、ビットコインの登場（2007年のGKR）よりも前の1990年代に提案されていました（sumcheckプロトコル）。当時の採用における主な問題は、堅牢なユースケースの欠如（1990年代はインターネットが現在ほど発達していなかった）と、必要とされる計算能力に関するものでした。

ゼロ知識証明：起源（1985/1989）

ゼロ知識証明の分野が初めて学術文献に登場したのは、[Goldwasser, Micali and Rackoff](https://people.csail.mit.edu/silvio/Selected Scientific Papers/Proof Systems/The_Knowledge_Complexity_Of_Interactive_Proof_Systems.pdf?ref=blog.lambdaclass.com「Goldwasser, Micali and Rackoff」）を参照されたい。その起源については、以下のビデオをご覧ください^[8]。この論文では、完全性、正しさ、ゼロ知識という概念を紹介し、二次残差性と二次非残差性の構成を示しています。

Sumcheck Protocol (1992)

Sumcheck Protocol ^[9]は1992年にLund、Fortnow、Karloff、Nisan^[10]によって提案された。これは、簡潔な相互作用証明のための最も重要な構成要素の1つである。これは、多変数多項式の和の記述を、ランダムに選ばれた点における単一の和に減らすのに役立ちます。

Goldwasser-Kalai-Rothblum (GKR) (2007)

^{GKR protocol[11]は対話型プロトコルで、証明者の実行時間は回路のゲート数に対して線形であり、検証者の実行時間は回路のサイズに対して非線形である。このプロトコルでは、深さdの有限領域上のfan-in-twoの算術回路について、証明者と検証者が合意する。合意は回路の出力の宣言から始まり、それを前の層の値の宣言に還元する。再帰によって、これを回路の入力の宣言に変換することができ、簡単にチェックすることができる。これらの削減はsumcheckプロトコルによって達成される。}

KZG多項式コミットメント方式（2010年）

KZG多項式コミットメント方式（KZG polynomial commitment scheme、略称PCS）Kate、Zaverucha、およびGoldberg^[12]は、2010年に、二項式を使用する多項式コミットメント方式を導入した。多項式コミットメントスキームを紹介した。コミットメントは1つのグループ要素で構成され、コミッターは多項式の正しい評価に対して効果的にコミットメントを開くことができる。KZGコミットメントは、Pinocchio、Groth16、Plonkなどのいくつかの効率的なSNARKが提供する基本的な構成要素です。また、EIP-4844^[13]の中核でもある。バッチ処理技術の直感的な理解については、Mina-Ethereumブリッジ^[14]の記事をご覧ください。

楕円曲線を使った実用的なSNARK

最初の実用的なSNARKの構成は2013年に登場しました。これらの構成は、証明鍵と検証鍵を生成するための前処理ステップを必要とし、プログラム/回路に固有です。これらのキーは非常に大きくなる可能性があり、未知のままであるべき秘密のパラメータに依存します。コードを証明可能な内容に変換するには、コードを一連の多項式制約系にコンパイルする必要がある。当初は、これを手作業でコーディングする必要があり、時間がかかり、エラーも発生しやすかった。

1. There are more efficient provers.

2. 前処理の量を減らす。

3. 回路に特化したセットアップではなく、汎用的なセットアップを持っています。

4. 信頼設定を避ける。

5. 多項式制約を手作業で書くのではなく、高レベル言語を使って回路を記述する方法を開発する。

Pinocchio(2013)

Pinocchio^[15]は最初の実用的で使用可能なzk-SNARKでした。 SNARKはQuadratic Arithmetic Program (QAP)に基づいています。pinocchioのツールチェーンは、Cコードから算術回路へのコンパイラを提供し、その回路はさらにQAPに変換される。楕円曲線ペアリングを使用して方程式をチェックする。証明の生成と鍵の設定の漸近は計算のサイズに線形に関係し、検証時間は共通の入力と出力のサイズに線形に関係する。

Groth 16 (2016)

Groth^[16] は、R1CSの問題を記述するための性能を強化した新しい知識アーギュメント^[17]を導入した。これは、最小の証明サイズ（3つのグループ要素のみ）と3つのペアリングを含む高速な検証を持つ。また、構造化参照文字列を得るための前処理ステップを含む。Groth16はZCashで使用されている。

Bulletproofs & IPA (2016)

KZG PCSの弱点の1つは、信頼設定を必要とすることです。Bootleら^[18]は、内積関係を満たすPedersenコミットメントオープニングに対する効率的なゼロ知識引数のシステムを導入しました。この内積論証は、線形的な証明者、対数的な通信と相互作用を持つが、線形的な検証時間を持つ。また、信頼設定を必要としない多項式コミットメントスキームを開発した。これらのアイデアを用いた多項式コミットメントスキーム（PCS）は、Halo 2やキムチで使用されている。

Sonic, Marlin, and Plonk (2019)

Sonic^[19], Plonk^[20], Marlin^[21]は、Groth16で遭遇した、信頼設定を必要とするという問題を解決した。Marlinは、Aleoの心臓部であるR1CS（Rank-1 Constraint System）に基づく証明システムを提供する。

Plonk^[22]は、新しい算術スキーム（後にPlonkishと呼ばれる）と、コピー制約をチェックするための大積チェックの使用を導入した。いくつかのプロジェクトがPlonkをカスタマイズしており、Aztec、ZK-Sync、Polygon ZKEVM、Mina's Kimchi、Plonky2、Halo 2、Scrollなどがある。

ルックアップ（2018/2020）

GabizonとWilliamsonは2020年にplookup^[23]を導入しました。これはマクロ積チェックを使用して、値が事前に計算された値の表に含まれていることを証明するものです。ルックアップパラメータは以前Arya^[24]で導入されていたが、この構成ではルックアップの多重度を決定する必要があり、構成が効率的でなくなる。PlonkUp^[25]論文では、Plonkにplookupパラメータを導入する方法を示している。これらのルックアップパラメータの問題点は、証明者にテーブル全体に対する支払いを強いることである。ルックアップの回数とは無関係に、そのコストを支払わなければならない。HaböckはLogUp^[26]を導入した。これは対数導関数を使用して、大積チェックを逆数の和に変換するものである。^[27]はPolygon ZKEVMのパフォーマンスにとって重要である。彼らはテーブル全体をいくつかのSTARKモジュールに分割する必要がある。これらのモジュールは正しくリンクされている必要があり、クロステーブル・ルックアップはこれを強制します。LogUp-GKRの導入^[28]は、GKRプロトコルを使用してLogUpのパフォーマンスを向上させる。 Caulk^[29]は、前処理時間O(NlogN)とストレージO(N)（Nはテーブルサイズ）を使用して、証明者の時間がテーブルサイズに対して非線形であることを証明した最初のスキームである。その後、Baloo^[30]、flookup^[31]、cq^[32]、caulk+^[33]などのスキームが登場した。が与えられた構造を持つ時にそれにコミットする際に、テーブルを実行する必要性を回避するためのいくつかの改良を提案しました。さらに、Lassoの証明者は、ルックアップ操作によってアクセスされたテーブル・エントリに対してのみ支払いを行います。jolt^[35]は、ルックアップを通して仮想マシンの実行を証明するためにLassoを使用しています。

Spartan (2019)

Spartan^[36] は、R1CSを用いて記述された回路に対して、多変数多項式とsumcheck protocolの特性を利用したIOP("Interactive Oracle Proof.")を提供する。

HyperPlonk (2022)

HyperPlonk^[37] Plonkの多変数多項式を使うというアイデアに基づいています。多項式)を使用する。制約の実行をチェックするために、商ではなくsumcheckプロトコルに依存しています。また、証明者の実行時間に影響を与えることなく、高次の制約をサポートします。HyperPlonkは、小さいフィールド用の新しい置換IOPと、sumcheckベースのバッチオープンプロトコルを導入しており、証明者の作業、証明のサイズ、検証者の時間を削減します。

フォールディングスキーム（2008/2021）

Nova^[38]は、漸進的に検証可能な計算（IVC: incrementally verifiable computation）を実装する新しい方法であるフォールディングスキームの概念を導入した。IVCの概念はValiant^[39]に遡り、彼は長さkの2つの証明を再帰によって長さkの1つの証明に結合する方法を示した。このアイデアは、ステップiからステップI + 1への実行が正しいことを再帰的に証明し、ステップi-1からステップiへの変換が正しいという証明を検証することで、どのような長く実行される計算でも証明できるというものであった。Supernova^[40].NovaはR1CSの緩和版を使用し、友好的な楕円曲線上で動作する。IVCのための曲線（例えばPasta曲線）を使用したフレンドリーなループは、クリーン・ステートのMinaの実装の主要な構成要素であるPicklesでも使用されている。しかし、折りたたみの概念は再帰的SNARK検証とは異なります。[41]は、再帰的な証明の組み合わせの代替として累積の概念を導入しました。

Using collision-resistant hash functions

Pinocchio が開発されている間、仮想マシンの実行の正しさを証明できる回路/算術スキームを生成することが考えられていました。TinyRAMのアイデアはその後、Cairo vmの設計によって改良され、後続のVM（zk-evmsや汎用zkvmsなど）も改良されました。TinyRAMのアイデアはその後Cairo vmの設計によって改良され、その後の仮想マシン（zk-evmsや汎用zkvmsなど）も改良された。衝突に強いハッシュ関数を使うことで、信頼できるセットアップや楕円曲線操作は不要になったが、その代償として証明は長くなった。

TinyRAM (2013)

SNARKs for C^[43]では、TinyRAM（Thin Instruction Set Computer）用にコンパイルされたCプログラムの実行の正しさを証明するために、PCPベースのSNARKを開発しました。

注：PCP、 Probabilistically Checkable Proof 確率的にチェック可能な証明は、検証者が証明の無作為に選ばれた小さな部分だけを読むことによって、高い信頼度で証明の妥当性をチェックすることを可能にします。検証者が証明全体をチェックしなければならない従来の証明システムとは異なり、PCPは効率的な検証のために限られたランダム性しか必要としません。

コンピュータは、バイトレベルのアドレス可能なランダムメモリを備えたハーバードアーキテクチャを採用しています。非決定性を用いることで、回路のサイズは計算のサイズにほぼ線形に関係し、任意かつデータに依存したループ、制御フロー、メモリアクセスを効率的に扱うことができる。

STARKs (2018)

STARKs^[44] はBen Sassonらによって2018年に提案された。これらは0 (log^2 n)の証明サイズを達成し、高速な証明者と検証者を持ち、もっともらしいセットアップを必要とせず、ポスト量子セキュアであると仮定されている。これらはStarkware/StarknetがCairo vmで最初に使った。代数的中間表現(Algebraic Intermediate Representation: AIR)やFRIプロトコル^[45](Fast Reed-Solomon Interactive Oracle Proof of Proximity Fast Reed-Solomon Interactive Oracle Proof of Proximity)などがある。また、他のプロジェクト(Polygon Miden、Risc0、Winterfell、Neptune)で使用されたり、いくつかのコンポーネント(ZK-SyncのBoojum、Plonky2、Starky)で採用されたりしています。

Ligero (2017)

Ligero ^[46]は、サイズO(√n)の証明を実装する証明システムを提案した。Brakedown^[47]はLigeroの研究を基に、ドメインに依存しない多項式コミットメントスキームの概念を導入している。

いくつかの新展開

生産における異なる証明システムの使用は、各アプローチの利点を示し、新たな発展につながる。FRIはPCSとして優れた性能を示し、Plonkyにつながりました。同様に、AIR（前処理されたランダム化AIRをもたらす）におけるマクロ積チェックの使用は、その性能を向上させ、メモリアクセス引数を単純化します。ハッシュ関数ベースの約束は、ハードウェアでのスピードや、SNARKに適した新しいハッシュ関数の導入により、人気が出ました。

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

SpartanやHyperPlonkのような多変数多項式に基づく効率的なSNARKの出現により、そのような多項式に適用可能な新しいコミットメントスキームへの関心が高まっています、Zeromorph^[49]やBasefold^[50]はすべて、多項式へのコミットの新しい形式を提案している。動作させることができる。basefoldはFRIをReed-Solomon以外のコードに拡張し、ドメインに依存しないPCSを実現しました。

注ドメインに依存しない：ドメインに依存しない多項式コミットメントスキームでは、コミットメントプロセスは特定のドメインの特定の特性には依存しません。特定の特性に依存しない。つまり、有限体、楕円曲線、整数の環など、あらゆる代数構造の多項式にコミットすることが可能です。

Customisable constraint systems (2023)

CCS^[51] はR1CSを一般化したもので、余分なオーバーヘッドなしにR1CS、Plonkish、AIRの両方の算術化を行うことができます。CCSをSpartan IOPと組み合わせて使用することで、高次元制約をサポートするSuperSpartanが生成され、制約メトリックが増加しても、証明者はスケーリングの暗号化コストを負担する必要がありません。特に、SuperSpartanはAIRのSNARKの線形時間証明を提供する。

結論

本稿では、1980年代半ば以降のSNARKの進歩について述べる。コンピュータサイエンス、数学、ハードウェアの進歩、そしてブロックチェーンの導入により、より効率的な新しいSNARKが登場し、社会を変革しうる多くのアプリケーションへの扉が開かれました。研究者やエンジニアたちは、証明サイズ、メモリ使用量、透過設定、ポスト量子セキュリティ、証明時間、検証時間などに着目し、ニーズに基づいたSNARKの改良と適応を提案してきました。当初は2つの主要な路線（SNARKs対STARKs）があったが、異なる証明システムの利点を組み合わせる試みにより、両者の境界はなくなり始めている。例えば、異なる算術化スキームと新しい多項式コミットメントスキームの組み合わせなどである。今後も新しい証明システムが登場し、性能も向上していくことが予想されますが、コアとなるインフラの一部を変更することなく、これらのツールを簡単に使えるようにならない限り、慣れるまでに時間がかかるシステムによっては、これらの開発に追いつくことは難しいでしょう。

References

[1]Link: https://blog.lambdaclass.com/our-highly-subjective-view-on-the-history-of-zero-knowledge-proofs/

[2]Dengchuan Translation Project: https://github.com/lbc-team/Pioneer

[3]Translation Team:  style="font-align: left;">[2]Dengchuan Translation Project: https://github.com/lbc-team/Pioneer[3]翻訳チーム: https://learnblockchain.cn/people/412

[4]Tiny Bear:&。nbsp;https://learnblockchain.cn/people/15

[5]learnblockchain.co.jp/article...: https://learnblockchain.cn/article/7422

[7]Cryptographic proofs of the Cambrian explosion: https://medium.com/starkware/cambrian-explosion-of-cryptographic-proofs-5740a41cdbd2?ref=blog.lambdaclass.com

[7]カンブリア爆発の暗号証明: 。align: left;">[8]次の動画： https://www.youtube.com/watch?v=uchjTIlPzFo&ref=blog.lambdaclass.com

[9]sumcheck protocol: https://blog.lambdaclass.com/have-you-checked。-your-sums/

[10]Lund, Fortnow, Karloff, and Nisan: https://dl.acm.org/doi/pdf/10.1145/146585.146605?ref=blog.lambdaclass.com

[.11]GKRプロトコル: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/12/2008-DelegatingComputation.pdf?ref=blog.lambdaclass.com

[12]Kate, Zaverucha, and Goldberg: https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf?ref=blog.lambdaclass.com

[13]EIP-4844: https://github.com/ethereum/EIPs/blob/master/EIPS/eip-4844.md?ref=blog.lambdaclass.com

[14]Mina-Ethereum bridge: https://blog.lambdaclass.com/mina-to-ethereum-bridge/

[15]Pinocchio: https://eprint.iacr.org/2013/279?ref=blog.lambdaclass.com

[16]Groth: https://eprint.iacr.org/2016/260.pdf?ref=blog.lambdaclass.com

[17]New Knowledge Arguments with Enhanced Performance: ；https://blog.lambdaclass.com/groth16/

[18]Bootle et al: https:/./eprint.iacr.org/2016/263?ref=blog.lambdaclass.com

[19]Sonic: https://eprint.iacr.org/2019/099?ref=blog.lambdaclass.com

[20]Plonk: https://eprint.iacr.org/2019/953?ref=blog.lambdaclass.com

[21]Marlin: https://eprint.iacr.org/2019/1047?ref=blog.lambdaclass.com

[22]Plonk: https://blog.lambdaclass.com/all-you-wanted-to-know-about-plonk/

[23]Plookup: https://eprint.iacr.org/2020/315?ref=blog.lambdaclass.com