jakiro
ZK Proofsは、一方の当事者（Proverb）が、個人情報を明らかにすることなく真実で有効であることを納得させる強力な暗号化の原始です。近年、ZKは検証可能なプライベートコンピューティングの分野で広く注目を集めており、コンピュータープログラムとブロックチェーンの有効性の証拠を提供し、世界の発展において重要な肯定的な役割を果たしています。
ZKは新興技術ですが、その基本的なアイデアと概念は1980年代にさかのぼります。ビットコインやイーサリアムなどのブロックチェーンと組み合わされた後、ZKテクノロジーの開発は大幅に加速しました。ブロックチェーンは、スナークとスタークを通じてその効果を証明し、そのスケーラビリティを大幅に向上させることができるため、これによりZKはブロックチェーンフィールドで人気があります。
Starkwareの創設者であるEli Ben-Sassonが言ったように、近年、暗号化された証明システムの「カンブリア紀爆発」を目撃しました。各プルーフシステムには独自の長所と短所があり、設計時にトレードダウンされます。ハードウェアの進歩、より良いアルゴリズム、新しい引数、および周辺ツールはすべて、ZKシステムのパフォーマンス改善と新しいシステムの誕生を刺激しました。多くの証明システムが実際のアプリケーションで採用されており、人々はまだZKの境界を拡大しています。
これにより、人々は質問について深く考えるように促します。すべてのアプリケーションに普遍的なZKプルーフシステムはありますか？これが可能性が高いとは思わない。3つの理由があります。
1。アプリケーションの多様性。
2。異なる制約タイプ（メモリ、検証時間、および証明時間を含む）。
3.堅牢性の必要性（1つの証明システムがハッキングされている場合、保険として他のシステムに切り替えることができます）。
上記の理由に基づいて、ZKはシステムが多様であることを証明しています。しかし、多くの種類のプルーフシステムがある場合でも、重要な共通性がある必要があります。ZKプルーフを迅速に検証できます。検証層を持つことは、新しい証明システムに簡単に適応して、依存する基礎となる層の関連する困難を解決することができます（イーサリアムなど）。
ZKフィールドでは、ZK-SNARKが頻繁に言及されています。これは、ゼロ知識証明を実現する一形態であり、双線形ペアリングや算術回路などの複雑な数学ツールを使用することにより、効率的なゼロ知識証明を可能にします。ZK-SNARKの特徴は、証明プロセスが単純で非対話的であり、プロバーと検証剤と検証剤の間に単一の通信のみが必要であることです。複数の相互作用は必要ありません。また、ZK-SNARKの証明サイズは非常に短く、検証効率が高く、リソースに制約のある環境での使用に適しています。
ZK-Starkは、Zk-Snarkのいくつかの制限を克服するために設計されたもう1つの一般的な形式です。ZK-Starkは信頼できる設定に依存せず、多項式のコミットメントや有限ドメイン操作、ハッシュ衝突などのより透明な数学的建設システムを使用して、証明を生成および検証します。ZK-StarkはZk-Snarkよりもスケーラブルで、大規模なコンピューティングに適しており、より速く生成することが証明されていますが、通常はサイズが大きいです。
Zk-SnarkとZk-Starkはどちらもゼロ知識証明で一般的に使用される形式であると言えますが、透明性、スケーラビリティ、証明サイズなどの点で異なります。
全体、ZKプルーフシステムには、通常、PIOP（多項式インタラクティブオラクル）とPC（多項式コミットメントスキーム）の2つの部分が含まれます。一般的なPIOPソリューションには、Plonkish、GKRなどが含まれますが、一般的なPCSソリューションにはFRI、KZG、IPAなどが含まれます。たとえば、HALO2のZCASHバージョンは、ZK-Starkの実装方法を使用しますFRIベースの特別なZK-SNARKと見なされます。
より詳細な場合、さまざまなタイプのプルーフシステムが、異なる多項式コミットメントスキーム（PC）、算術スキーム、インタラクティブオラクルプルーフ（IOP）、または確率チェック可能な証明（PCP）を使用します。
さらに遠く、さまざまなZKプルーフシステムは、多くの場合、次の指標で異なります。
-
暗号化仮説：反衝突ハッシュ機能、楕円曲線の離散対数問題、指数知識
-
透明な設定と信頼できる設定
-
プルーフを生成するために時間がかかります：線形vsハイパーリニア
-
証明の検証に時間がかかる：一定の時間、ログ時間、サブリン、線形
-
サイズのサイズを証明します
-
再帰のシンプルさ
-
算術スキーム
-
単変量と多変量多項式
以下に、ZKテクノロジーの起源について簡単に説明し、その基本的な構成要素を探索し、さまざまなZKプルーフシステムの上昇と下降の概要を説明します。同時に、この記事では、証明システム自体の詳細な分析を実施していませんが、フィールドに大きな影響を与えた人に焦点を当てています。結局のところ、あらゆる業界の発展は、先駆者と実践に魅力的な素晴らしいアイデアを通してのみ可能です。
Zk-Snarkの歴史的発展の文脈
起源：1980年代から1990年代
述べたように、ゼロ知識の証明は、その定義、基礎、重要な定理、さらには1980年代半ばにさえ登場しました。最初の登場は、ゴールドワッサー、ミカリ（アルゴランドの創設者）とラックフの論文にありましたインタラクティブプルーフシステムの知識の複雑さ“真ん中。
そしてZK-SNARKテクノロジーの構築に使用する重要なアイデアとプロトコルは、1990年代にリリースされました。たとえば、SumCheckプロトコルは、ZKテクノロジーの重要な基盤を築く楕円曲線上のランダムに選択された点の単一の評価に対する複数の多項式の評価の合計宣言を簡素化します。
したがって、ZKのアイデアの出現は、実際にはビットコインの出現よりもはるかに早いです。ただし、当時、ZKには一般的なケースが不足しており、ZKプルーフシステムを満たすために必要な強力なコンピューティングパワーを提供できませんでした。
GKRプロトコル（2007）
GKR（Goldwasser-Kalai-Rothblum）は、プロバーの実行時間は回路のロジックゲートの数と直線的に相関していますが、検証剤の時間は回路サイズとサブリニアル相関があります。GKRプロトコルでは、有限ドメインのデュアル入力算術回路の動作結果にProverと検証者が同意する必要があります。レイヤーは出力層です。プロトコルは、回路の出力に関する宣言から始まり、再帰的に前のレイヤーの宣言に単純化します。最後に、宣言を出力に変換して、回路の入力パラメーターの宣言に変換できます。これは簡単に検証できます。GKRプロトコルは、前述のSumcheckプロトコルに基づいて非常に簡素化されていると言えます。
KZG多項式コミットメントソリューション（2010）
2010年、ZK分野の3人の専門家– ドイツの研究機関MPI-SWSのケート、カナダの暗号化会社Certicom ResearchのZaverucha、およびWaterloo大学のGoldbergは、「多項式に対する一定のサイズのコミットメントと彼らの応用の適用に対する」この論文KZGと呼ばれる双線形ペアグループを使用した多項式コミットメントスキームが提案されています。
この約束は別のグループ要素で構成されており、コミッターは多項式の正しい評価を効率的に明らかにすることができ、バッチ処理技術の助けを借りて、複数の多項式の評価を明らかにすることができます。KZGは、いくつかの有名なZKプルーフシステム（Ethereum PES Groupが使用するHALO2など）の基本的なビルディングブロックの1つになることを約束し、EthereumのEIP-4844でも中核的な役割を果たしました。バッチ処理テクノロジーの概念をより直感的に理解するために、Mina-Ethereum Bridgeの記事を参照できます。
参照：https：//blog.lambdaclass.com/mina-to-ethereum-bridge/
楕円曲線に基づく実用的なZK-SNARKシステム（2013）
ZK-SNARKの最初の実用的な構造が2013年に登場し、証明キーと検証キーを生成するために前処理ステップを必要とし、プログラムまたは回路固有であり、普遍的ではありません。これらのキーは、サイズが大きくなり、秘密のパラメーター自体に依存します。この実用的なZK-SNARKシステムでは、コードを実証済みのフォームに変換するには、コードを多項式制約の数学的形式のセットにコンパイルする必要があります。
最初は、上記のプロセスを手動で完了する必要があります。これは時間がかかり、エラーが発生しやすいです。その後、この方向の技術的変化に応えて、私たちは主に次のコアの問題を解決しようとしました。
-
より効率的な証拠を提供します
-
前処理の数を減らします
-
回路固有の設定ではなく、ユニバーサルを実装します
-
信頼できる設定は避けてください
-
多項式の制約を手動で書くのではなく、高レベルの言語の回路を記述する方法を開発する
Pinocchioプロトコル（2013）
Pinocchioプロトコルは、実際に利用できる最初のZK-SNARKシステムです。二次算術プログラム（QAP）に基づいて、初期の証明サイズは288バイトです。Pinocchioのツールチェーンは、c言語を算術回路にコンパイルするコンパイラを提供します。これをQAPにさらに変換できます。Pinocchioプロトコルでは、検証者が普遍的ではなく回路固有のキーを生成する必要があります。システム生成の進行時間の複雑さとプルーフシステムのキー設定は、計算スケールに直線的に関連しており、検証時間は共通の入力と出力のサイズに直線的に関連しています。
GROTH16（2016）
Grothは、R1Cの取り扱いにより高いパフォーマンスを持つ新しいZK-ILMアルゴリズムを導入しました。R1CSは、ZK-SNARKの多項式制約形式である1次制約システムです。ゴースの証明は、最小のデータサイズ（3つのグループ要素のみを含む）であり、検証速度は非常に高速です。3つのペアリング操作と、参照文字列を構成する前処理ステップを実行します。しかし、Gorthの主な欠点は、証明する必要がある各プログラムには、実際のアプリケーションでは非常に不便なさまざまな信頼できる設定が必要であることです。
その後、GROTH16は、比較的有名なプライバシーブロックチェーンプロジェクト（Starkware Founder ELIが関与）であるZCASHで使用されました。
防弾とIPA（2016）
前述のKZG多項式コミットメントスキームの主要な弱点の1つは、信頼できる設定の必要性です。Bootle et al。線形の複雑さによる内部産物証明の証明には時間がかかります。プローバーと検証剤の間の相互作用の数は対数ですが、検証時間は線形です。さらに、Bootleら。これらのアイデアは、後にHalo2とKimchiによって採用されました。
Sonic、Marlin、およびPlonk（2019）
Sonic、Plonk、およびMarlinは、GROTH16アルゴリズムのすべてのプログラムが信頼できる設定を必要とする問題を解決し、共通および更新された構造化参照文字列（1回しか必要ない信頼できる設定を実装するために使用されます）を導入します。で、MarlinはR1CSに基づいたプルーフシステムを提供し、Aleoのコアテクノロジーになりました。
Plonkは、新しい算術スキーム（後にPlonkishとして知られる）を導入し、壮大な製品を使用して複製の制約を確認します。Plonkishでは、特定の操作、いわゆる「カスタムゲート」の専用回路ロジックゲートを導入することもできます。多くの有名なブロックチェーンプロジェクトでは、Aztec、Zksync、Polygon Zkevm、Mina、Ethereum PSE Group、Scrollなど、Plonkのカスタマイズバージョンを使用しています。
スパルタン（2019）
Spartanは、多変量多項式とSumテストプロトコルの特性を利用して、R1Cを使用して記述された回路用のIOPを提供します。適切な多項式コミットメントスキームを使用することにより、透明なZK-SNARKシステムを実装し、証明を生成する時間の複雑さは線形です。
ルックアップ（2020）
GabizonとWilliamsonは2020年に彼らの論文でPlookupを提案しました、Grand-Productを使用して、値が事前に計算されたTruth Tableに含まれていることを証明し、PlookupパラメーターをPlonkアルゴリズムに導入する方法を示します。
ただし、これらのルックアップ引数には共通の問題があり、Proversは完全な真理テーブルを構築するために多額のお金を費やす必要があるため、検索に関する以前の研究は、証明のコストを削減することに専念しています。
その後、Haböckは彼の論文にログアップを導入しました。これは、ログデリバティブを使用して、壮大な製品チェックを往復の合計に変換します。ログアップは、真理テーブル全体を複数のスタークモジュールに分割する必要があるため、ポリゴンZKEVMSのパフォーマンスの改善に重要です。これらのモジュールは正しくリンクする必要があり、クロステーブルルックアップはこれを強制することができます。それ以来、Logup-GKRの導入により、GKRプロトコルを介したログアップのパフォーマンスが向上しました。
Caulkは、実証済みのタイムサブリンの関係を実証済みのテーブルサイズとするための解決策です。Baloo、flookup、CQ、Caulk+など、他のソリューションが続きました。さらに、ラッソは、特定の構造があるときに真実のテーブルにコミットすることを避けるために、いくつかの改善を提案しています。
HyperPlonk（2022）
Hyperplonkは、論文「Hyperplonk：Linear-Time Proverと高度のカスタムゲートを備えたPlonk」で提案されました。HyperplonkはPlonkの概念に基づいており、多変量多項式を採用しています。分割を使用して制約の実行を確認する代わりに、Sum-Testプロトコルに依存しています。同時に、証明の生成時間に影響を与えることなく、高次の制約もサポートします。
多変量多項式が使用されるため、高速フーリエ変換（FFT）を実行する必要はないため、生成時間が回路スケールに直線的に関連していることが証明されています。HyperPlonkはまた、小さなフィールドに新しい順列IOPを導入し、プロバー、プルーフサイズ、および検証時間のワークロードを削減する合計ベースのプロトコルを採用します。
衝突防止ハッシュ関数を使用したZKプルーフシステム
Pinocchioは2013年に提案されましたが、仮想マシンが命令を正しく実行することを証明できる回路/算術スキームを生成するためのいくつかのソリューションがあります。仮想マシンの算術スキームを開発することは、一部のプログラムに専用のサーキットを作成するよりも複雑であるか、それが重要な利点を持っています。
Tinyramのいくつかのアイデアは、後にCairo Virtual Machinesの設計で改善され、ZK-EVMと汎用ZKVMが続きました。プルーフシステムで衝突耐性ハッシュ関数を使用すると、信頼できる設定または楕円曲線操作の必要性がなくなりますが、それはより長く校正する犠牲を払っています。
Tinyram（2013）
「Snarks for C」では、Cで記述されたプログラムの実行結果が正しいことを証明するために、PCPに基づいた証明システムを開発しました。このプログラムは、簡素化されたVMであるTinyramにまとめられています。VMにはバイトレベルのアドレス指定可能なランダムメモリがあり、回路サイズはコンピューティングスケールで準線形に増加し、ループ、制御フロー、メモリアクセスなどの操作を効率的に処理できます。
で、PCPは、確率的にチェック可能な証明を意味することを意味します。検証器が証明全体をチェックする必要がある従来の証明システムとは異なり、PCPは効率的な検証を実現するために限定的なランダム性のみを必要とします。
ligero（2017）
Ligeroは、サイズO（√￣N）の証明を実装できる証明システムを導入しました。ここで、nは回路のサイズです。マトリックス形式で多項式係数を配置します。BrakedownはLigeroに基づいて構築されており、ドメインに依存しない多項式コミットメントスキームの概念を紹介しています。
スタークス（2018）
Starks（スケーラブルな透明な知識の議論）は、2018年にEli Ben-Sassonらによって提案されました。？それらは、Starkware/StarkNetおよびCairo Virtual Machinesによって使用されます。その主要な革新には、代数的中間表現（AIR）および高速リードソロモンインタラクティブオラクルプルーフ（FRI）プロトコルが含まれます。さらに、スタークスは、多くの有名なブロックチェーンプロジェクト（Polygon Miden、Risczero、Winterfell、Neptune、Zerosync、Zksyncなど）でも使用されています。
新しい開発の方向
実際のアプリケーションで異なるプルーフシステムを使用することは、さまざまな方法の利点を示し、ZKの開発を促進します。たとえば、Plonkishの算術スキームは、カスタムロジックゲートとルックアップ引数を簡単に含める方法を提供します。一方、空気中の壮大な製品のチェック（前処理をもたらすランダム化空気）を使用すると、パフォーマンスが向上し、メモリアクセスパラメーターが簡素化されます。ZK-Starkは、生成効率が向上し、ZKに優しいハッシュ機能が導入されているため、ますます人気が高まっています。
新しい多項式コミットメントスキーム（2023）
SpartanやHyperplonkなどの多変量多項式に基づいた効率的な精神の出現により、このような多項式に適用される新しいコミットメントスキームに関心が高まっています。Binius、Zeromorph、およびBasefoldはすべて、多重線形多項式を約束する新しい方法を提案しています。Biniusには、データ型を示すときに余分なオーバーヘッドがないという利点があります（他の多くのプルーフシステムは、単一ビットを表すために少なくとも32ビットのフィールド要素を使用しています）。コミットメントスキームは、フィールドに依存しない目的で設計されたBrakedownを使用します。BaseFoldは、Reed-Solomon以外にFRIを一般化し、ドメインに依存しない多項式コミットメントスキーム（PCS）を達成します。
ドメインに依存しないのは、多項式コミットメントスキームのプロパティであり、特定のドメインの特定の特性に依存しない多項式コミットメントスキームのコミットメントプロセスを指します。これは、有限ドメイン、楕円曲線、さらには整数リングなど、代数構造の多項式にコミットメントを行うことができることを意味します。
カスタマイズ可能な制約システム（2023）
CCSは、R1C、Plonkish、およびAirの算術を追加のオーバーヘッドなしでキャプチャしながら、R1CSを一般化します。Spartan IOPと組み合わせてCCSを使用すると、SuperSpartanを生成できます。これは、制約順序に比例する暗号化コストを負担する必要なく、高次元の制約をサポートします。特に、Superspartanには、線形時間証明のスナークを空気に提供します。
要約します
この記事では、1980年代半ば以降のZKテクノロジーの進捗状況をレビューします。コンピューターサイエンス、数学、ハードウェアの進歩は、ブロックチェーンの導入と相まって、新しいより効率的なZKプルーフシステムを生み出し、社会を変える可能性のある多くのアプリケーションの道を開きます。
研究者とエンジニアは、需要に基づいてZKシステムの改善を提案し、証明サイズ、メモリの使用量、透明性、量子セキュリティ抵抗、証明時間、および検証時間に焦点を当てました。ZKの主流の実装ソリューション（スナークとスタークス）には常に2つの主要なカテゴリがありましたが、2つの間の境界が徐々にぼやけており、異なる算術ソリューションと新しい算術ソリューションを組み合わせるなど、異なるプルーフシステムの利点が組み合わされています。スキーム。
新しいZKプルーフシステムが出現し続け、パフォーマンスが改善され続けることが期待できます。これらのプルーフシステムを使用したアプリケーションの場合、最新のテクノロジーの反復開発に従い、最新のアルゴリズムを継続的に再構築して適用できない場合、現在の主要な位置は一時的な位置にすぎません。
オリジナルリンク：https://blog.lambdaclass.com/our-highly-subjective-view-on-the-history-of-zero-knowledge-proofs/
