ゼロ知識、簡潔化、非対話的知識記述(zk-SNARK)は、一方の当事者である証明者が、特定のステートメントの有効性以外の何も明らかにすることなく、特定のステートメントが真実であることを別の当事者である検証者に納得させることを可能にする強力な暗号化プリミティブです。 これらは、検証可能なプライベート計算への応用により広く注目を集めており、コンピュータープログラムの実行の正しさを証明し、ブロックチェーンのスケーリングを支援しています。 SNARKは、私たちの 投稿で説明しているように、私たちの世界を形作る上で大きな影響を与えると考えています。 SNARKsは、さまざまな多項式コミットメントスキーム(PCS)、算術化スキーム、インタラクティブオラクルプルーフ(IOP)、または確率的にチェック可能なプルーフ(PCP)を使用して、さまざまなタイプのプルーフシステムの傘として機能します。 しかし、基本的な考え方やコンセプトは1980年代半ばにさかのぼります。 ビットコインとイーサリアムの導入後、開発は大幅に加速し、ゼロ知識証明(この特定のユースケースでは一般に有効性証明と呼ばれます)を使用して拡張できるため、エキサイティングで強力なユースケースであることが証明されました。 SNARKは、ブロックチェーンのスケーラビリティに不可欠なツールです。 Ben-Sassonが述べているように、ここ数年で 暗号証明がカンブリア紀に爆発的に増加しました。 各プルーフシステムには長所と短所があり、特定のトレードオフを念頭に置いて設計されています。 ハードウェアの進歩、より優れたアルゴリズム、新しい引数、ガジェットにより、パフォーマンスが向上し、新しいシステムが誕生しました。 それらの多くは生産に使用されており、私たちは限界を押し広げ続けています。 すべてのアプリケーションに対応する一般的なプルーフシステムがあるのか、それとも異なるニーズに適した複数のシステムがあるのか? 1つの証明システムがそれらすべてを支配する可能性は低いと考えています。

1. アプリケーションの多様性。
2. 制約の種類 (メモリ、検証時間、証明時間など)。
3. 堅牢性の必要性(1つの証明システムが壊れても、他のシステムがまだ残っています)。

証明システムは大きく変化しますが、証明は迅速に検証できるという重要な特性があります。 証明を検証し、新しい証明システムを扱うために簡単に適応できるレイヤーを持つことで、イーサリアムなどのベースレイヤーの変更に伴う困難を解決できます。 SNARKのさまざまな特性を概観すると、次のようになります。

• 暗号の仮定:衝突耐性ハッシュ関数、楕円曲線上の離散対数問題、指数の知識。
• 透過的なセットアップと信頼できるセットアップ。
• 証明時間:線形と超線形。
• 検証器の時間:一定時間、対数、準線形、線形。
• プルーフサイズ。
• 再帰の容易さ。
• 算術化スキーム。
• 単変量多項式と多変量多項式。

この記事では、SNARKの起源、いくつかの基本的な構成要素、およびさまざまな証明システムの台頭(および衰退)について見ていきます。 この投稿は、証明システムの徹底的な分析を意図したものではありません。 その代わりに、私たちに影響を与えたものに焦点を当てます。 もちろん、これらの開発は、この分野のパイオニアの偉大な仕事とアイデアによってのみ可能になりました。

基礎

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

ゼロ知識証明:起源(1985/1989)

ゼロ知識証明の分野は 、Goldwasser、Micali、Rackoffの論文で学術文献に登場しました。 起源に関する議論については、 次のビデオをご覧ください。 この論文では、完全性、健全性、ゼロ知識の概念を導入し、二次残差性と二次非残差性の構成を提供しました。

Sumcheckの議定書(1992年)

sumcheckプロトコルは、1992年にLund、Fortnow、Karloff、およびNisanによって提案されました。これは、簡潔でインタラクティブな証明のための最も重要な構成要素の1つです。 これは、多変量多項式の評価の合計に対する主張を、ランダムに選択された点での単一の評価に減らすのに役立ちます。

Goldwasser-Kalai-Rothblum (GKR) (2007年)

GKRプロトコルは、回路のゲート数で線形に実行されるプローバーを持つインタラクティブプロトコルであり、検証器は回路のサイズで亜線形に実行されます。プロトコルでは、証明者と検証者は、深さdの有限フィールド上でファンインツーの演算回路に同意し、層dは入力層に対応し、層0は出力層です。 プロトコルは、回路の出力に関するクレームから始まり、前の層の値に対するクレームに縮小されます。 再帰を使用すると、これを回路の入力に対するクレームに変えることができ、簡単にチェックできます。 これらの削減は、sumcheckプロトコルによって達成されます。

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

Kate、Zaverucha、Goldberg は、2010年に双線形対群を用いた多項式のコミットメントスキームを導入しました。 コミットメントは 1 つのグループ要素で構成され、コミッターは多項式の正しい評価に対してコミットメントを効率的に開くことができます。 さらに、バッチ処理技術により、いくつかの評価にオープニングを行うことができます。 KZGのコミットメントは、ピノキオ、グロス16、プロンクなど、いくつかの効率的なSNARKの基本的な構成要素の1つを提供しました。 また、 EIP-4844の心臓部でもあります。 バッチ処理のテクニックを直感的に理解するには、 Mina-Ethereumブリッジに関する投稿をご覧ください。

楕円曲線を用いた実用的なSNARK

SNARKの最初の実用的な構造は2013年に登場しました。 これらには、証明鍵と検証鍵を生成するための前処理ステップが必要であり、プログラム/回路固有でした。 これらのキーは非常に大きくなる可能性があり、当事者に知られていないはずの秘密のパラメータに依存しています。そうでなければ、彼らは証拠を偽造する可能性があります。 コードを証明できるものに変換するには、コードを多項式制約のシステムにコンパイルする必要がありました。 最初は、これは手作業で行う必要があり、時間がかかり、エラーが発生しやすくなっていました。 この分野の進歩は、いくつかの主要な問題を取り除こうとしました。

1. より効率的な証明者を持つ。
2. 前処理の量を減らします。
3. 回路固有のセットアップではなく、ユニバーサルなセットアップ。
4. 信頼できるセットアップは避けてください。
5. 多項式制約を手動で記述する代わりに、高水準言語を使用して回路を記述する方法を開発します。

ピノキオ(2013)

ピノキオ は、実用的で使用可能な最初のzk-SNARKです。 SNARKは、二次演算プログラム(QAP)に基づいています。 プルーフのサイズは、もともと 288 バイトでした。 ピノキオのツールチェーンは、Cコードから演算回路へのコンパイラを提供し、さらにQAPに変換されました。 プロトコルでは、検証者が回線固有のキーを生成する必要がありました。 楕円曲線のペアを使用して方程式を確認しました。 証明生成と鍵設定の漸近は計算サイズで線形であり、検証時間は公開入力と出力のサイズで線形でした。

グロス16(2016)

Grothは 、R1CSによって記述された問題に対する パフォーマンスを向上させた知識の新しい議論 を導入しました。 プルーフサイズが最小(3つのグループ要素のみ)で、3つのペアを含む高速検証が可能です。 また、構造化された参照文字列を取得するための前処理手順も含まれます。 主な欠点は、証明したいプログラムごとに異なる信頼できるセットアップが必要であり、不便であることです。 Groth16はZCashで使用されました。

防弾とIPA (2016)

KZG PCSの弱点の1つは、信頼できるセットアップが必要なことです。 ブートル等。 内積関係を満たすペダーセンコミットメントの開口部の効率的なゼロ知識論証システムを導入した。 内積引数は、対数通信と相互作用を伴う線形証明を持ちますが、線形時間検証を伴います。 また、信頼できるセットアップを必要としない多項式コミットメントスキームも開発しました。 これらのアイデアを使ったPCSは、Halo 2やキムチで使われています。

ソニック、マーリン、プロンク(2019)

Sonic、 Plonk、 Marlin は、普遍的で更新可能な構造化参照文字列を導入することで、Groth16 で持っていたプログラムごとの信頼できるセットアップの問題を解決します。 Marlinは、R1CSをベースにしたプルーフシステムを提供し、Aleoの中核をなすものです。

プロンクは 新しい算術化スキーム(後にプロンキッシュと呼ばれる)を導入し、コピー制約に大積チェックを使用した。 プロンキッシュは、特定の操作のための特殊なゲート、いわゆるカスタムゲートの導入も許可しました。 Aztec、zkSync、Polygon ZKEVM、Mina's Kimchi、Plonky2、Halo 2、Scrollなど、いくつかのプロジェクトがPlonkのカスタマイズバージョンを持っています。

ルックアップ(2018/2020)

Gabizon と Williamson は 2020 年に plookup を導入し、グランド プロダクト チェックを使用して、値が事前計算された値テーブルに含まれていることを証明しました。 ルックアップ引数は以前は Aryaで提供されていましたが、構築にはルックアップの多重度を決定する必要があり、構築の効率が低下します。 PlonkUp の論文では、plookup 引数を Plonk に導入する方法が示されました。これらのルックアップ引数の問題は、ルックアップの数とは無関係に、証明者にテーブル全体の価格を支払うことを強制することでした。 これは、大きなテーブルにはかなりのコストがかかることを意味し、証明者のコストを、使用するルックアップの数だけに減らすために多くの努力が払われてきました。
Haböck は、対数微分を使用して大積小切手を逆数の和に変換する LogUp を導入しました。 LogUpは、テーブル全体を複数のSTARKモジュールに分割する必要がある Polygon ZKEVMのパフォーマンスにとって非常に重要です。 これらのモジュールは正しくリンクする必要があり、クロステーブルルックアップはこれを強制します。 LogUp-GKR の導入により、GKR プロトコルを使用して LogUp のパフォーマンスが向上します。コーキング は、前処理時間O(NlogN)と貯蔵量O(N)(Nはテーブルサイズ)を使用して、テーブルサイズにプルーバー時間サブリニアを持つ最初のスキームでした。 その後、 Baloo、 flookup、 cq 、 caulk+など、いくつかのスキームが続きました。 Lasso にはいくつかの改善点があり、テーブルが特定の構造を持っている場合にテーブルにコミットすることを回避します。 その上、Lassoの証明者は、ルックアップ操作によってアクセスされたテーブルエントリに対してのみ支払います。 Jolt はLassoを利用して、ルックアップによって仮想マシンの実行を証明します。

スパルタン(2019)

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

ハイパープロンク(2022)

HyperPlonk は、多変量多項式を使用する Plonk のアイデアに基づいて構築されています。 制約の適用をチェックする商の代わりに、sumcheck プロトコルに依存しています。 また、プルーバーの稼働時間を損なうことなく、高度な制約をサポートします。 多変量多項式に依存しているため、FFTを実行する必要はなく、証明器の実行時間は回路サイズで線形です。 HyperPlonkは、より小さなフィールドに適した新しい順列IOPと、証明者の作業、プルーフサイズ、および検証者の時間を削減する合計チェックベースのバッチオープンプロトコルを導入しています。

折り畳み方式(2008/2021)

Nova は、インクリメンタル検証可能な計算(IVC)を実現するための新しいアプローチであるフォールディングスキームのアイデアを導入しています。 IVCの概念は、長さkの2つの証明を長さkの1つの証明にマージする方法を示した Valiant にまでさかのぼります。 この考え方は、ステップ i からステップ I+1+1 への実行が正しいことを再帰的に証明し、ステップ i からの遷移を示す証明を検証することで、実行時間の長い計算を証明できるというものです。

−1−1をステップiに修正することは正解でした。 Novaは一様計算をうまく処理します。その後、 Supernovaの導入により、さまざまなタイプの回路を処理できるように拡張されました。 NovaはR1CSのリラックスしたバージョンを使用し、友好的な楕円曲線で動作します。 円満な曲線サイクル(パスタ曲線など)でIVCを達成することは、簡潔な状態を実現するためのMinaの主要な構成要素であるPicklesでも使用されています。 ただし、折り畳みの考え方は、再帰的なSNARK検証とは異なります。 アキュムレータのアイデアは、証明のバッチ処理の概念とより深く関連しています。 Halo は、再帰的証明合成の代替として蓄積の概念を導入しました。 Protostar は、高次ゲートとベクトルルックアップをサポートする不均一なIVCスキームをPlonkに提供します。

衝突耐性ハッシュ関数の使用

ピノキオが開発されたのとほぼ同時期に、仮想マシンの実行の正しさを証明できる回路/演算スキームを生成するためのアイデアがいくつかありました。 仮想マシンの演算化の開発は、一部のプログラムに対して専用の回路を作成するよりも複雑であったり、効率が悪かったりする可能性がありますが、どんなに複雑なプログラムでも、仮想マシンで正しく実行されたことを示すことで証明できるという利点がありました。 TinyRAMのアイデアは、後にCairo vmとそれに続く仮想マシン(zk-evmsや汎用zkvmsなど)の設計で改善されました。 衝突に強いハッシュ関数を使用することで、より長い証明を犠牲にして、信頼できるセットアップや楕円曲線演算を使用する必要がなくなりました。

タイニーラム (2013)

SNARKs for Cでは、C言語プログラムの実行の正しさを証明するPCPをベースにしたSNARKを開発し、それを縮小命令セットコンピュータであるTinyRAMにコンパイルしました。このコンピュータはハーバードアーキテクチャを採用しており、バイトレベルのアドレス指定可能なランダムアクセスメモリが採用されていた。 非決定性を利用して、回路のサイズは計算のサイズが準線形になり、任意のループとデータ依存のループ、制御フロー、およびメモリアクセスを効率的に処理します。

スタークス(2018)

STARKは 、2018年にBen Sassonらによって導入されました。 彼らはO(log2n)(log2)を達成します

Proofサイズは、Fast ProverとVerifierを備えているため、信頼できるセットアップを必要とせず、耐量子後の安全性が高いと推測されます。 これらは、Starkware/Starknetによって、Cairo vmとともに最初に使用されました。 その主な導入には、代数的中間表現(AIR)と FRIプロトコル (Fast Reed-Solomon Interactive Oracle Proof of Proximity)があります。 また、他のプロジェクト(Polygon Miden、Risc0、Winterfell、Neptune)でも使用されていたり、一部のコンポーネント(zkSyncのBoojum、Plonky2、Starky)の適応が見られたりしています。

リジェロ (2017)

Ligero は、サイズが

O(√n)、ここでnは回路のサイズです。 多項式係数を行列形式で配置し、線形コードを使用します。
Brakedown はLigeroに基づいて構築されており、フィールドに依存しない多項式コミットメントスキームのアイデアを導入しています。

いくつかの新しい開発

生産に異なるプルーフシステムを使用することで、それぞれのアプローチのメリットが示され、新しい開発につながりました。 たとえば、plonkish 算術化は、カスタム ゲートとルックアップ引数を含める簡単な方法を提供します。FRIはPCSとして素晴らしいパフォーマンスを示しており、Plonkyにつながっています。 同様に、AIR で大積チェック(前処理によるランダム化された AIR につながる)を使用すると、パフォーマンスが向上し、メモリアクセス引数が簡素化されました。 ハッシュ関数に基づくコミットメントは、ハードウェアのハッシュ関数の速度や、SNARKに適した新しいハッシュ関数の導入に基づいて、人気を博しています。

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

Spartan や HyperPlonk などの多変量多項式に基づく効率的な SNARK の出現により、この種の多項式に適した新しいコミットメント スキームへの関心が高まっています。 Binius、 Zeromorph、 Basefold はすべて、多重線形多項式にコミットするための新しい形式を提案しています。 Biniusには、データ型を表すためのオーバーヘッドがゼロであるという利点があり(多くの証明システムは、少なくとも32ビットのフィールド要素を使用して1ビットを表します)、バイナリフィールドで動作します。 このコミットメントは、現場にとらわれないように設計されたブレーキダウンを適応させます。 Basefold は FRI を Reed-Solomon 以外の符号に一般化し、フィールドに依存しない PCS を導きます。

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

CCS は、R1CS、Plonkish、および AIR 演算をオーバーヘッドなしでキャプチャしながら、R1CS を一般化します。 CCS を Spartan IOP で使用すると、制約の度合いに応じてスケーリングされる暗号化コストを負担することなく、高度な制約をサポートする SuperSpartan が得られます。 特に、SuperSpartanは、線形時間証明器を持つAIRのSNARKを生成します。

結論

本稿では、1980年代半ばにSNARKが導入されて以来のSNARKの進歩について解説する。 コンピュータサイエンス、数学、ハードウェアの進歩は、ブロックチェーンの導入と相まって、新しく、より効率的なSNARKにつながり、私たちの社会を変革する可能性のある多くのアプリケーションへの扉を開きました。 研究者やエンジニアは、プルーフサイズ、メモリ使用量、透過的なセットアップ、ポスト量子セキュリティ、プルーバー時間、検証時間など、ニーズに応じてSNARKの改善や適応を提案してきました。 もともとは2つの主要な路線(SNARKとSTARKs)がありましたが、両者の境界は薄れ始めており、異なる証明システムの利点を組み合わせようとしています。 たとえば、異なる算術化スキームと新しい多項式コミットメントスキームの組み合わせなどです。 新しいプルーフシステムは、パフォーマンスの向上とともに増加し続けることが予想されますが、コアインフラストラクチャを変更することなく、これらのツールを簡単に使用できるようにしない限り、適応に時間がかかる一部のシステムは、これらの開発に追いつくことが困難になります。

免責事項：

1. この記事は[lambdaclass]から転載したもので、すべての著作権は原作者[LambdaClass]に帰属します。 この転載に異議がある場合は、 Gate Learn チームに連絡していただければ、迅速に対応いたします。
2. 免責事項:この記事で表明された見解や意見は、著者のものであり、投資アドバイスを構成するものではありません。
3. 記事の他言語への翻訳は、Gate Learnチームによって行われます。 特に明記されていない限り、翻訳された記事を複製、配布、盗用することは禁止されています。