ゼロ知識証明の歴史を理解してください

出典：Denglian Community

ゼロ知識、簡潔な、非対話的な知識の証明（ZK-snarks）は、一方の当事者、つまり、他の情報を明らかにすることなく声明が真実であることを証明する強力な暗号化のプリミティブですこの声明の妥当性よりも。彼らは、検証可能なプライベートコンピューティングのアプリケーション、コンピュータープログラムの実行の正確性の証拠を提供し、ブロックチェーンの拡大を支援するために、広範囲の注目を集めています。私たちは、私たちの記事のように、私たちの世界の形成に、スナークスが大きな影響を与えると信じています^[6]で説明されているように。スナークは、さまざまな多項式コミットメントスキーム（PC）、算術スキーム、インタラクティブオラクルプルーフ（IOP）、または確率的チェック可能な証明（PCP）を使用して、さまざまな種類の証明システムの一般的な用語です。ただし、これらの基本的なアイデアと概念は、1980年代半ばにさかのぼります。ビットコインとイーサリアムの導入後、開発の取り組みは大幅に加速しました。これは、ゼロ知識証明（この特定のユースケースの妥当性の証明と呼ばれることが多い）を使用できるため、エキサイティングで強力なユースケースであることを証明しています。スナークは、ブロックチェーンのスケーラビリティのための重要なツールです。ベン・サッソンが説明しているように、過去数年間は暗号防止のカンブリア紀の発生を目撃してきました^[7]。各証明システムには利点と短所があり、特定のトレードオフは設計時に考慮されます。ハードウェアの進歩、より良いアルゴリズム、新しい引数、ガジェットは、パフォーマンスの改善と新しいシステムの誕生につながりました。これらのシステムの多くは生産に使用されており、境界を押し続けています。すべてのアプリケーション用のユニバーサルプルーフシステム、またはさまざまなニーズのためのいくつかのシステムがありますか？プルーフシステムがすべてのアプリケーションを支配する可能性はほとんどないと思います。

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

2. さまざまな制約タイプがあります（メモリ、検証時間、証明時間について）。

3. 堅牢性の必要性（証明システムが割れている場合、まだ他のシステムがあります）。

証明システムが大きく変化したとしても、それらはすべて重要な機能を持っています。証明は迅速に検証できます。基礎となる層の変更（イーサリアムなど）の変更に関連する困難は、ヴェーキングの証明の証明層を持つことで解決され、新しい作業証明システムを処理する層に簡単に適応します。

お知らせのさまざまな特性の概要を説明します。

• パスワード仮説：衝突防止ハッシュ関数、楕円曲線の離散対数問題、指数知識。

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

• 校正時間：リニア対ハイパーリニア。

• 検証時間：一定の時間、対数、サブリン、線形。

• 証明サイズ。

• 再帰の利便性。

• 算術スキーム。

• 統一vs多変量多項式。

この記事では、スナークの起源、いくつかの基本的なビルディングブロック、およびさまざまなプルーフシステムの上昇（および衰退）について説明します。この記事では、証明システムの詳細な分析を実施するつもりはありません。代わりに、私たちは現時点で私たちに影響を与えている人々に焦点を当てています。もちろん、これらの開発は、この分野の先駆者の素晴らしい仕事とアイデアに基づいてのみ達成できます。

基本的な知識

述べたように、ゼロ知識の証明は新しいものではありません。1980年代半ばに定義、基礎、重要な定理、さらには重要なプロトコルさえ確立されました。ビットコインが出現する前でさえ、1990年代（SumCheck Protocol）（2007年のGKR）には、最新の嗅覚を構築するために使用された重要なアイデアとプロトコルのいくつかが提案されました。当時採用されていた主な問題は、主に強いユースケースの欠如に関連していました（インターネットは1990年代ほど開発されていませんでした）、および必要なコンピューティングパワーでした。

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

ゼロ知識証明の分野は、[Goldwasser、Micali、およびRackoff]（https://people.csail.mit.edu/silvio/selected Scientific Papers/Proof Systems/the_kno wledge_complexity_of_of_of_of_of_interactive_proof_systems.pdf ref = ref = ref = reft = reft = reft = reft = reft = reft = reft = reft = refedの学術文献に最初に登場しました。 blog.lambdaclass .com “Goldwasser、Micali and Rackoff”）論文。起源の議論については、次のビデオを参照できます^[8]。このペーパーでは、完全性、正確性、ゼロ知識の概念を紹介し、二次の残留性と二次非抵抗性の構築を提供します。

Sumcheck契約（1992）

Sumcheckプロトコル^[9]Lund、Fortnow、Karloff、Nisanによるものです^[10]1992年に提案されました。これは、簡潔な相互作用の証明のための最も重要な構成要素の1つです。これは、ランダムに選択されたポイントでの単一の評価に対する複数の多項式の評価の合計の宣言を減らすのに役立ちます。

Goldwasser-Kalai-Rothblum（GKR）（2007）

GKRプロトコル^[11]これはインタラクティブなプロトコルであり、プロバーの実行時間は回路のゲートの数に直線的に関連していますが、検証剤の実行時間は回路のサイズに直線的に関連しています。このプロトコルでは、ProverとVerifierは、深さDの有限ドメイン上の2人のファンの算術回路に同意します。ここで、レイヤーdは入力層に対応し、レイヤー0は出力層に対応します。プロトコルは、回路出力の宣言から始まり、それを以前のレイヤー値の宣言に減らします。再帰により、回路入力の宣言に変換できます。これは簡単に確認できます。これらの削減は、Sumcheckプロトコルを通じて達成されます。

KZG多項式コミットメントソリューション（2010）

KZG多項式コミットメントスキーム（PCS）Kate、Zaverucha、およびGoldberg^[12]2010年には、双線形ペアリンググループを使用した多項式コミットメントスキームが導入されました。このコミットメントは単一のグループ要素で構成され、コミッターは多項式の正しい評価に対するコミットメントを効果的に開くことができます。さらに、バッチテクノロジーにより、複数の評価をオンにすることができます。KZGは、Pinocchio、Groth16、Plonkなどのいくつかの効率的なスナークが基本的なビルディングブロックを提供することを約束します。また、EIP-4844です^[13]の中核。バッチ処理テクノロジーを直感的に理解するために、あなたは私たちのミナ・エチョウム・ブリッジを見ることができます^[14]記事。

楕円曲線を使用した実用的な嗅覚

2013年に最初の実用的なスナークコンストラクトが登場しました。これらの構成には、証明キーと検証キーを生成するための前処理手順が必要であり、プログラム/回路固有です。これらのキーは非常に大きく、保持する必要がある未知の秘密のパラメーターに依存します。コードを妥当なコンテンツに変換するには、コードを一連の多項式制約システムにコンパイルする必要があります。最初は、これを手動で行う必要がありますが、これは時間がかかり、エラーが発生しやすいです。この分野の進歩は、主要な問題のいくつかを排除しようとします。

1. より効率的なプロバーがあります。

2. 前処理の数を減らします。

3. 特定の回路ではなく一般的な設定。

4. 信頼の設定は避けてください。

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

ピノキオ（2013）

ピノキオ^[15]最初の実用的で使用可能なZK-Snarkです。スナークは、二次算術プログラム（QAP）に基づいています。プルーフサイズは最初は288バイトです。Pinocchioのツールチェーンは、Cコードから算術回路までのコンパイラを提供し、さらにQAPに変換されます。プロトコルでは、回路固有のキーを生成するために検証者が必要です。楕円曲線ペアリングを使用して方程式を確認します。生成設定とキー設定の漸近性が計算サイズに直線的に関連しており、検証時間が共通の入力と出力のサイズに直線的に関連していることを証明します。

グロス16（2016）

グロス^[16]パフォーマンスが向上した新しい知識の議論が導入されました^[17]、R1Cの問題を説明するために使用されます。最小のプルーフサイズ（3つのグループ要素のみ）と3つのペアリングを含む高速検証があります。また、構造化された参照文字列を取得するための前処理ステップも含まれます。主な欠点は、証明したいプログラムごとに異なる信頼設定が必要であることです。これは不便です。GROTH16はZCASHによって使用されます。

防弾＆amp;

KZG PCSの弱点の1つは、信頼設定が必要であることです。Bootle et al。^[18]内部製品関係を満たす効果的なゼロ知識の議論システムが導入されます。内部製品の引数には、線形の得点、対数通信、および相互作用がありますが、線形時間の検証があります。彼らはまた、信頼の設定を必要としない多項式コミットメントスキームを開発しました。これらのアイデアを使用した多項式コミットメントスキーム（PCS）は、Halo 2とKimchiで使用されました。

Sonic、Marlin、およびPlonk（2019）

ソニック^[19]、plonk^[20]とマーリン^[21]GROTH16で遭遇するすべてのプログラムには、一般的な参照文字列を導入して信頼設定が必要な問題に対処します。マーリンは、アレオの中心にあるR1C（ランク1制約システム）に基づくプルーフシステムを提供します。

plonk^[22]新しい算術スキーム（後にPlonkishと呼ばれる）が導入され、複製の制約をチェックするために壮大な製品チェックが使用されました。Plonkishでは、特定の操作、いわゆるカスタムドア向けに特殊なドアを導入することもできます。いくつかのプロジェクトには、Aztec、ZK-Sync、Polygon Zkevm、MinaのKimchi、Plonky2、Halo 2、Scrollなど、Plonkのカスタマイズバージョンがあります。

ルックアップ（2018/2020）

GabizonとWilliamsonは2020年にPlookupを紹介します^[23]、マクロ製品チェックを使用して、値が事前に計算された値テーブルに含まれていることを証明します。検索パラメーターは以前はARYAであっていましたが^[24]ただし、この構造では、検索の多様性を決定する必要があり、構造が十分に非効率的になります。plonkup^[25]このペーパーは、PlookupパラメーターをPlonkに導入する方法を示しています。これらのルックアップパラメーターの問題は、検索数に関係なく、得点者がテーブル全体の支払いを強制することです。これは、大きなテーブルのコストが非常に大きく、人々が使用する検索数のみを支払うためにプロのコストを削減するために多くの努力を払っていることを意味します。Haböckはログアップを紹介します^[26]、grand-productチェックを対数導関数を使用して逆の合計に変換します。Polygon Zkevmのログアップ^[27]それらのパフォーマンスは重要であり、テーブル全体をいくつかのスタークモジュールに分割する必要があります。これらのモジュールは正しくリンクされている必要があり、クロステーブルルックアップはこれを強制します。logup-gkrの紹介^[28]GKRプロトコルを使用して、ログアップのパフォーマンスを向上させます。コーキング^[29]テーブルサイズで時間をサブリニアで証明する最初のスキームであり、前処理時間o（nlogn）とストレージo（n）を使用して、nはテーブルサイズです。Balooなど、他のいくつかのオプションが続きました^[30]、flookup^[31]、cq^[32]とコーキング+^[33]。ラッソ^[34]特定の構造がある場合、テーブルがコミットしないように、いくつかの改善が提案されています。さらに、Lasso’s Proverは、ルックアップ操作によってアクセスされるテーブルエントリのみを支払います。衝撃^[35]ラッソを使用して、ルックアップを通じて仮想マシンの実行を証明します。

Spartan（2019）

スパルタン^[36]IOP（ “Interactive Oracle Proof。”）は、多変量多項式とSumcheckプロトコルの特性を利用して、R1Cを使用して記述された回路に提供されます。適切な多項式コミットメントスキームを使用して、線形時間証明透明なスナークを生成します。

HyperPlonk（2022）

HyperPlonk^[37]Plonkのアイデアに基づいて、多変量多項式が使用されます。制約の実行を確認するために、商ではなくSumCheckプロトコルに依存しています。また、プローバーのランタイムに影響を与えることなく、高次の制約をサポートします。多変量多項式に依存しているため、FFTを実行する必要はなく、プローバーの実行時間は回路サイズに直線的に関連しています。HyperPlonkは、より小さなフィールドに新しい順列IOPを導入し、Proverの作業、証明サイズ、および検証時間を短縮するSumCheckベースのバッチオープニングプロトコルを導入します。

折りたたみスキーム（2008/2021）

ノバ^[38]折り畳みスキームの概念が導入されています。これは、段階的に検証可能なコンピューティングを実装する新しい方法です。IVCの概念はValiantにまでさかのぼることができます^[39]、彼は、長さkの2つの証明を長さkの単一の証明に組み合わせる方法を示しています。アイデアは、ステップIからステップI +1への実行が正しいことを証明できるということです。ステップI-1からステップIへの変換が正しいことを再帰的に証明していることを証明できます。novaは、統合されたコンピューティングをよく処理します。^[40]。NovaはR1CSのリラックスバージョンを使用し、フレンドリーな楕円曲線に取り組んでいます。IVCは、曲線に優しいループ（パスタ曲線など）を使用して実装され、簡潔なピクルスのミナの実装のメインビルディングブロックとしても使用されます。ただし、折り畳みの概念は、再帰的なスナークの検証とは異なります。

アキュムレータのアイデアは、バッチプルーフの概念により深く接続されています。ハロー^[41]蓄積の概念は、再帰的な証明の組み合わせに代わるものとして導入されます。プロトスタル^[42]高次のゲートとベクトル検索をサポートするPlonkに不均一なIVCソリューションを提供します。

衝突防止ハッシュ関数を使用します

Pinocchioが開発中に、仮想マシンの実行を正しく証明できる回路/算術スキームを生成するためのいくつかのアイデアがありました。仮想マシンの開発の算術は、一部のプログラムに専用サーキットを作成するよりも複雑であるか、効率的ではない場合がありますが、その利点は、プログラムが仮想マシンで正しく実行されていることを実証することで複雑なプログラムを証明できることです。Tinyramのアイデアは、Cairo VMの設計と、ZK-EVMSや汎用ZKVMSなどのその後の仮想マシンを通じて改善されます。衝突耐性ハッシュ関数を使用すると、信頼できる設定または楕円曲線操作の必要性がなくなりますが、証明の犠牲を払って長くなります。

Tinyram（2013）

cのスナークで^[43]この記事では、PCPベースのSnarkを開発して、Cプログラムの実行の正しさを証明しました。これは、薄い命令セットコンピューターであるTinyramにまとめられています。

注：PCP、確率的に確認可能な確率は、ランダムに選択されたコンテンツの小さな部分を読み取ることで、証明の妥当性を高い状態で確認できます。検証者が証明全体を確認する必要がある従来の証明システムとは異なり、PCPは効率的な検証を有効にするために限定的なランダム性のみを必要とします。

コンピューターは、バイトレベルでアドレス指定できるランダムメモリを備えたハーバード構造を採用しています。非決定的を使用すると、回路のサイズは計算されたサイズにほぼ直線的に関連しており、データ関連のループ、制御フロー、メモリアクセスを効率的に処理できます。

スタークス（2018）

スタークス^[44]2018年にBen Sassonらによって提案されました。それらは、0（log^2 n）のプルーフサイズを実装し、高速プローバーとバリデーターを持ち、信頼できるセットアップを必要とせず、Quantum後のセキュリティであると仮定されています。それらは、カイロVMとともに、Starkware/Starknetによって初めて使用されます。その重要な紹介には、代数中間表現（AIR）およびFRIプロトコルが含まれます^[45]（高速リードソロモンインタラクティブなオラクルの近接性の証明）。また、他のプロジェクト（Polygon Miden、Risc0、Winterfell、Neptune）でも使用されているか、コンポーネント（boojum、plonky2、Zk-sync of Starky）の適応が見られます。

ligero（2017）

ligero^[46]nは回路のサイズであるo（√n）のプルーフサイズを実装するためのプルーフシステムが提案されています。多項式係数をマトリックス形式に配置し、線形コードを使用します。ブレイクダウン^[47]Ligeroに基づいて、ドメインに依存しない多項式コミットメントスキームの概念が導入されました。

いくつかの新しい開発

生産におけるさまざまなプルーフシステムの使用は、各方法の利点を示し、新しい開発を推進します。たとえば、Plonkish Arithmeticは、カスタムゲートとルックアップ引数を簡単に含める方法を提供します。同様に、空気中のマクロプロダクトチェック（前処理をもたらすランダム化空気）の使用は、そのパフォーマンスを改善し、メモリアクセスパラメーターを簡素化します。ハッシュ機能の約束は、ハードウェアの速度やスナークの新しいハッシュ関数の導入により、一般的になりました。

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

SpartanやHyperplonkなどの多変量多項式に基づいた効率的な精神の出現により、このような多項式に適用される新しいコミットメントスキームに大きな関心が寄せられています。ビニウス^[48]ゼロモルフ^[49]とベースフォールド^[50]すべてが多重線形多項式への新しい形式のコミットメントを提案しています。Biniusには、データ型を示すときに余分なオーバーヘッドがないという利点があり（多くのプルーフシステムが単一ビットを表すために少なくとも32ビットフィールド要素を使用します）、バイナリドメインで動作することができます。コミットメントスキームは、フィールドに依存しない目的で設計されたBrakedownを使用します。BaseFoldは、Reed-Solomon以外のコードにFRIを宣伝し、ドメインに依存しないPCをもたらします。

ノートドメインに依存しない：ドメインに依存しない多項式コミットメントスキームでは、コミットメントプロセスは特定のドメインの特定の特性に依存しません。これは、有限ドメイン、楕円曲線、さらには整数リングなど、代数構造の多項式にコミットメントを行うことができることを意味します。

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

CCS^[51]一般化されたR1Cは、R1C、Plonkish、およびAir Arithmeticsをキャプチャしながら、オーバーヘッドを追加せずにキャプチャします。Spartan IOPと一緒にCCSを使用すると、SuperSpartanが生成されます。これは、高次元の制約をサポートし、プロバーは制約メトリックが増加するにつれてスケーリングする暗号化コストを負担する必要はありません。特に、Superspartanには、線形時間証明のスナークを空気に提供します。

結論は

この記事では、1980年代半ば以降の嗅覚の進歩について説明しています。コンピューターサイエンス、数学、ハードウェア、およびブロックチェーンの導入の進歩により、新しいより効率的なおしゃべりが出現し、社会を変える可能性のある多くのアプリケーションへの扉を開きました。研究者とエンジニアは、自分のニーズに基づいて、賢明なサイズ、メモリの使用状況、透明な設定、質量後のセキュリティ、証明時間、検証時間に焦点を当てた、narkへの改善と適応を提案しました。最初は2つの主要なライン（Snarks vs Starks）がありましたが、2つの境界が消え始め、異なるプルーフシステムの利点を組み合わせようとしました。たとえば、異なる算術スキームと新しい多項式コミットメントスキームの組み合わせ。新しいプルーフシステムが出現し続け、パフォーマンスが向上することが期待でき、コアインフラストラクチャを変更せずにこれらのツールを簡単に使用できない限り、これらの開発に遅れないように適応するのに時間がかかるシステムにとっては困難です。

参照

[1]リンク：https：//blog.lambdaclass.com/our-highly-subjective-view-on-the-history-of-zero-knowledge-proofs/

[2]リンク翻訳計画：https：//github.com/lbc-team/pioneer

[3]翻訳チーム：https：//learnblockchain.cn/people/412

[4] Tiny Bear：https：//learnblockchain.cn/people/15

[5]LearnBlockChain.cn/article…：https：//learnblockchain.cn/article/7422

[6]記事：https：//blog.lambdaclass.com/transforming-the-future-with- zero-knowledge-proofs-fully-homomorphic-encryption-and-new-distribued-syst ems-algorithms/

[7]暗号化のカンブリア紀の発生：https：//medium.com/starkware/cambrian-explosion-of-cryptographic-proofs-5740a41cdbd2？ref=blog.lambdaclass.com

[8]次のビデオ：https：//www.youtube.com/watch?v=uchjtilpzfo& ref=blog.lambdaclass.com

[9] SumCheckプロトコル：https：//blog.lambdaclass.com/have-you-checked-your-sums/

[10] Lund、Fortnow、Karloff、および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/12/2008-delegatingcomputation.pdf?ref=blog.lambdaclass.com

[12] Kate、Zaverucha、および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]グロス：https：//eprint.iacr.org/2016/260.pdf?ref=blog.lambdaclass.com

[17]パフォーマンスの強化による新しい知識の議論：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]マーリン：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

[24] Arya：https：//eprint.iacr.org/2018/380?ref=blog.lambdaclass.com

[25] Plonkup：https：//eprint.iacr.org/2022/086?ref=blog.lambdaclass.com

[26] logup：https：//eprint.iacr.org/2022/1530?ref=blog.lambdaclass.com

[27] Polygon Zkevm：https：//toposware.medium.com/beyond-limits-pushing-the-boundaries-of-zk-evm-9dd0c5ec9fca?ref=blog.lambdaclass.com

[28] logup-gkr：https：//eprint.iacr.org/2023/1284?ref=blog.lambdaclass.com

[29] caulk：https：//eprint.iacr.org/2022/621?ref=blog.lambdaclass.com

[30] Baloo：https：//eprint.iacr.org/2022/1565?ref=blog.lambdaclass.com

[31] flookup：https：//eprint.iacr.org/2022/1447?ref=blog.lambdaclass.com

[32] CQ：https：//eprint.iacr.org/2022/1763?ref=blog.lambdaclass.com

[33] caulk+：https：//eprint.iacr.org/2022/957?ref=blog.lambdaclass.com

[34] lasso：https：//eprint.iacr.org/2023/1216？ref=blog.lambdaclass.com

[35] Jolt：https：//eprint.iacr.org/2023/1217?ref=blog.lambdaclass.com

[36] Spartan：https：//eprint.iacr.org/2019/550?ref=blog.lambdaclass.com

[37] HyperPlonk：https：//eprint.iacr.org/2022/1355.pdf?ref=blog.lambdaclass.com

[38] nova：https：//eprint.iacr.org/2021/370?ref=blog.lambdaclass.com

[39] Valiant：https：//https//iacr.org/archive/tcc2008/49480001/49480001.pdf？ref = blog.lambdaclass.com

[40] Supernova：https：//eprint.iacr.org/2022/1758?ref=blog.lambdaclass.com

[41] Halo：https：//eprint.iacr.org/2019/1021.pdf?ref=blog.lambdaclass.com

[42] Protostar：https：//eprint.iacr.org/2023/620？ref=blog.lambdaclass.com

[43] CのSnarks：https：//eprint.iacr.org/2013/507?ref=blog.lambdaclass.com

[44] Starks：https：//eprint.iacr.org/2018/046?ref=blog.lambdaclass.com

[45] FRIプロトコル：https：//blog.lambdaclass.com/how-to-code-fri-from-scratch/

[46] ligero：https：//eprint.iacr.org/2022/1608?ref=blog.lambdaclass.com

[47] Brakedown：https：//eprint.iacr.org/2021/1043?ref=blog.lambdaclass.com

[48] binius：https：//blog.lambdaclass.com/snarks-on-fields-binius/

[49] Zeromorph：https：//eprint.iacr.org/2023/917?ref=blog.lambdaclass.com

[50] baseFold：https：//blog.lambdaclass.com/how-does-basefold-polynomial-commitment-scheme-generalize-fri//

[51] CCS：https：//eprint.iacr.org/2023/552?ref=blog.lambdaclass.com

[52] decert.me：https：//decert.me/