ゼロ知識証明における時代を超越したイノベーションの出現の背後にある本当の理由を探る

作成者: LambdaClass

コンパイル者: mutourend; Yiping、IOSG Ventures

1. はじめに

ゼロ知識、簡潔、非対話型知識証明 (zk-SNARK) は、証明者が検証者に特定のステートメントを納得させることを可能にする強力な暗号化プリミティブです。声明以外の情報を開示することなく、正確性を保証します。 zk-SNARK は、検証可能なプライベート計算、コンピューター プログラム実行の正確性の証明、ブロックチェーン拡張への応用により、広く注目を集めています。私たちは、記事で説明したように、zk-SNARK が世界の形成に大きな影響を与えると信じています。 zk-SNARK は、さまざまな多項式コミットメント スキーム、算術スキーム、インタラクティブなオラクル証明、または確率的テスト可能な証明を使用する、さまざまなタイプの証明システムをカバーします。しかし、これらの基本的なアイデアやコンセプトは 1980 年代半ばまで遡ります。

zk-SNARK の開発は、ゼロ知識証明 (この特定の使用例では妥当性証明と呼ばれることが多い) を使用して拡張できるため、ビットコインとイーサリアムの発売以来大幅に加速しました。 zk-SNARK は、ブロックチェーンのスケーラビリティにおいて重要な役割を果たします。ベン・サッソン氏が説明するように、近年、カンブリア紀の爆発的な暗号証明が見られました。各証明システムには長所と短所があり、特定のトレードオフを念頭に置いて設計されています。ハードウェア、アルゴリズム、新しいプルーフ、ツールの進歩により、パフォーマンスが向上し続け、新しいシステムの作成につながります。これらのシステムの多くはすでに使用されており、私たちは限界を押し広げ続けます。すべてのアプリケーションに機能する普遍的な証明システムがあるのでしょうか、それともさまざまなニーズに適したいくつかのシステムがあるのでしょうか?私たちは、次のような理由により、1 つの証明システムが他の証明システムを圧倒する可能性は非常に低いと考えています。

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

2) さまざまな制限タイプ (記憶、検証期間、証明期間に関して)。

3) 堅牢性の必要性 (1 つの証明システムが壊れても、他の証明システムが存在します)。

証明システムは大幅な変更を受ける可能性がありますが、証明の迅速な検証可能性という重要な特性を依然として共有しています。イーサリアムなどのベースレイヤーの変更に伴う問題は、証明を検証し、新しい証明システムに簡単に適応できるレイヤーで解決されます。この記事では、SNARK のさまざまな特徴について簡単に説明します。

1) 暗号の仮定: 衝突耐性のあるハッシュ関数、楕円曲線上の離散対数問題、指数の知識。

2) 透過的設定と信頼できる設定。

3) 証明長: 線形と超線形。

4) バリデーター時間: 定数時間、対数、サブリニア、リニア。

5)プルーフサイズ。

6) 再帰が簡単です。

7) 算術スキーム。

8) 単変数多項式と多変数多項式。

この記事では、SNARK の起源、いくつかの基本的な構成要素、およびさまざまな証明システムの隆盛 (および衰退) について探っていきます。この記事は、証明システムの徹底的な分析を提供することを目的としたものではありません。代わりに、私たちに影響を与える人だけに焦点を当ててください。もちろん、これらの開発は、この分野の先駆者たちの素晴らしい仕事とアイデアによってのみ可能になりました。

2. 基本知識

ゼロ知識証明は新しいものではありません。定義、基礎、重要な定理、さらには重要なプロトコルが 1980 年代半ばから開発されました。最新の SNARK を構築するために使用される重要なアイデアとプロトコルの一部は、ビットコインが存在する前 (2007 年の GKR) でさえ、1990 年代に提案されました (サムチェック プロトコル)。これを使用する際の主な問題は、強力な使用例の欠如 (インターネットは 1990 年代に開発されていない) と必要なコンピューティング能力に関連しています。

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

ゼロ知識証明の分野は、Goldwasser、Micali、Rackoff による論文「対話型証明システムの知識の複雑さ」によって学術文献に登場しました。起源については、2023 年 1 月のビデオ ZKP MOOC レクチャー 1: ZKP の概要と歴史をご覧ください。この論文では、倍数性、信頼性、ゼロ知識の概念を導入し、二次残差と二次非残差の構築を提供します。

2) サムチェックプロトコル (1992)。

sumcheck プロトコルは、Lund、Fortnow、Karloff、Nisan によって 1992 年の対話型証明システムの代数手法の論文で提案されました。これは、簡潔な対話型証明の最も重要な構成要素の 1 つです。これは、多変量多項式の合計の要件を、ランダムに選択された点の 1 つの評価に減らすのに役立ちます。

3) ゴールドワッサー カライ ロスブルム (GKR) (2007)。

GKR プロトコル (論文「計算の委任: マグルのための対話型証明」を参照) は、証明者が回路内のゲート数に応じて線形に動作し、検証者が回路のサイズに応じて準線形に動作する対話型プロトコルです。このプロトコルでは、証明者と検証者は、深さ d dd の有限体のファンイン 2 演算回路について合意します。ここで、層 d dd は入力層に対応し、層 0 00 は出力層に対応します。プロトコルは回路の出力に関するステートメントで始まり、前の層の値に関するステートメントに要約されます。再帰を使用すると、これを回路の入力の宣言に変換でき、簡単にチェックできます。これらの削減は、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 から Ethereum ZK へのブリッジを参照してください。

3. 楕円曲線を使用した実用的な SNARK

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

1) より効率的な証明者が必要です。

2) 前処理の量を減らします。

3) 回路固有ではなく、一般的なセットアップを行ってください。

4) 信頼できる設定の使用は避けてください。

5) 多項式制約を手動で記述する代わりに、高級言語を使用して回路を記述する方法を開発します。

現在、楕円曲線を使用した実用的な SNARKs ソリューションは次のとおりです。

1) Pinocchio (2013)

2) Groth 16 (2016)

3) Bulletproofs & IPA (2016)

4) Sonic、Marlin、Plonk (2019)

5) ルックアップ (2018/2020)

6) Spartan (2019)

7) HyperPlonk (2022)

8) フォールディング スキーム (2008/2021)

3.1 ピノキオ (2013)

Pinocchio (論文「Pinocchio: Nearly Practical Verifiable Computation」を参照) は、最初の実用的で使用可能な zk-SNARK です。 SNARK は 2 次算術プログラム (QAP) に基づいています。プルーフ サイズは最初は 288 バイトです。 Pinocchio のツールチェーンは、C コードから算術回路までのコンパイラーを提供し、さらに QAP への変換を行います。このプロトコルでは、検証者が回線固有のキーを生成する必要があります。楕円曲線のペアを使用して方程式をチェックします。証明の生成と鍵設定の漸近は、計算サイズに応じて線形にスケールし、検証期間はパブリックの入出力のサイズに応じて線形にスケールします。

3.2 Groth 16 (2016)

Groth の 2016 年の論文「ペアリングベースの非対話型引数のサイズ」では、問題のパフォーマンスを向上させる新しい知識引数が導入されています。 R1CS によって説明されます。最小の証明サイズ (わずか 3 つのグループ要素) と 3 つのペアリングを含む高速検証を備えています。また、構造化参照の文字列を取得するための前処理ステップも含まれます。主な欠点は、認定されるプログラムごとに異なる信頼できるセットアップが必要であり、不便であることです。 ZCash では Groth16 が使用されていました。詳細については、ブログ「Groth 16 プルーフ システムの概要」も参照してください。

3.3 Bulletproofs と IPA (2016)

KZG PCS の弱点の 1 つは、信頼できるセットアップが必要であることです。 Bootle et al. の 2016 年の Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Logsetting 論文では、内積関係を満たす Pedersen コミットメント開始のための効率的なゼロ知識引数システムが紹介されました。内積証明システムには、対数通信と相互作用を備えた線形証明器がありますが、線形持続時間検証が行われます。また、信頼できるセットアップを必要としない多項式コミットメント スキームも開発しました。 Halo 2 と Kimchi は両方とも IPA PCS のアイデアを採用しています。

3.4 Sonic、Marlin、および Plonk (2019)

Sonic、Plonk、および Marlin は、普遍的で更新可能な構造化参照文字列を導入することで Groth16 の問題を解決します。各プログラムの信頼できる設定。 Marlin は、Aleo の中核である R1CS に基づく証明システムを提供します。

Plonk は、新しい算術スキーム (後に Plonkish と呼ばれる) を導入し、コピー制約の総積チェックを使用しました。 Plonkish では、特定の操作に特化したドア、いわゆるカスタム ドアの導入も可能です。いくつかのプロジェクトには、Aztec、ZK-Sync、Polygon ZKEVM、Mina's Kimchi、Plonky2、Halo 2、Scroll などのカスタム バージョンの Plonk が含まれています。 Plonk について知りたかったすべてのブログを参照してください。

3.5 ルックアップ (2018/2020)

Gabizon と Williamson は 2020 年に plookup を導入し、グランド プロダクト チェックを使用して、事前計算された値に特定の値が含まれていることを証明しました。値テーブル。ルックアップ引数は Arya で以前に提案されていましたが、その構築にはルックアップの多重度を決定する必要があり、あまり効率的ではありませんでした。 PlonkUp の論文では、plookup 引数を Plonk に導入する方法を示しています。これらのルックアップ引数の問題は、ルックアップの数に関係なく、証明者にテーブル全体の料金の支払いを強制することです。これは、大きなテーブルのコストがかなりかかることを意味し、証明者のコストを使用するルックアップの数まで削減するために多大な努力が払われました。

Haböck は、対数導関数を使用して製品小切手を逆数の合計に変換する LogUp を導入しました。 LogUp は、テーブル全体を複数の STARK モジュールに分割する必要がある Polygon plonky2 ZKEVM (限界を超えて: ZK-EVM の境界を押し上げる) のパフォーマンスにとって重要です。モジュールは適切にリンクされている必要があり、この操作を実行するにはテーブル全体のルックアップが必要です。 LogUp-GKR の導入により、GKR プロトコルを利用して LogUp のパフォーマンスが向上します。 Caulk は最初の検索引数で、その証明者時間はテーブル サイズと準線形の関係にあり、前処理時間は O ( N log ⁡ N )、ストレージは O ( N ) です (N はテーブル サイズ)。 Baloo、flookup、cq、colk など、他のいくつかのソリューションが続きました。 Lasso は、特定の構造を持つテーブルのコミットを回避するために、いくつかの改善を提案しました。さらに、Lasso の証明者は、検索操作によってアクセスされたテーブル エントリに対してのみ料金を支払います。 Jolt は Lasso を利用して、ルックアップを通じて仮想マシンの実行を証明します。

3.6 Spartan (2019)

Spartan は、多変数多項式のプロパティと sumcheck プロトコルを利用して、R1CS を使用して記述された回路に IOP を提供します。適切な多項式コミットメント スキームを使用して、線形期間証明器を備えた透明な SNARK を生成します。

3.7 HyperPlonk (2022)

HyperPlonk は、多変数多項式を使用する Plonk のアイデアに基づいて構築されています。制約の適用をチェックするために商に依存せず、代わりに sumcheck プロトコルに依存します。また、証明者の実行時間を損なうことなく、高度な制約もサポートします。多変数多項式に依存しているため、FFT を実行する必要がなく、証明者の実行時間は回路サイズに線形に比例します。 HyperPlonk は、小規模ドメインに適した新しい順列 IOP とサムチェックベースのバッチ オープニング プロトコルを導入し、証明者のワークロード、証明サイズ、検証者の時間を削減します。

3.8 フォールディング スキーム (2008/2021)

Nova では、増分検証可能計算 (IVC) を実装する新しい方法であるフォールディング スキームのアイデアを導入しています。 IVC の概念は、長さ k kk の 2 つの証明を長さ k kk の 1 つの証明に結合する方法を示した Valiant に遡ります。アイデアは、再帰的証明を使用して、ステップ i ii からステップ i 1 i 1i 1 までの実行が正しいことを証明し、ステップ i − 1 i-1i−1 からステップ i ii への遷移証明が正しいことを検証できるということです。これにより、長時間実行される計算が証明されます。

Nova は均一な計算を適切に処理できます。その後、Supernova が導入され、さまざまな種類の回路を処理できるように拡張されました。 Nova は R1CS の緩和バージョンを使用し、フレンドリーな楕円曲線で動作します。フレンドリーなカーブ サイクル (パスタ カーブなど) を使用して IVC を実装することは、Mina の主要な基本モジュールである Pickles でも​​、簡潔な状態を実現するために使用されます。ただし、フォールディングの考え方は再帰的 SNARK 検証とは異なります。アキュムレータの考え方は、証明のバッチ処理の概念とより深く関連しています。 Halo では、再帰的な証明の組み合わせの代替として累積の概念が導入されています。 Protostar は、Plonk 用の不均一 IVC ソリューションを提供し、高度なゲートとベクトル ルックアップをサポートします。

4. 衝突耐性のあるハッシュ関数を使用した SNARK

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

1) TinyRAM (2013)

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

2) STARKs (2018)

STARKs は 2018 年に Ben Sasson らによって提案されました。その実装は O(log2n) の証明サイズを持ち、高速な証明者と検証者を備え、信頼できるセットアップを必要とせず、ポスト量子安全であると考えられています。これは、Starkware/Starknet によって Cairo 仮想マシンで初めて使用されました。その主要コンポーネントには、

代数中間表現 (AIR)

および FRI プロトコル (Fast Reed-Solomon Interactive Oracle Proof of Proximity) が含まれます。

STARK は、他のプロジェクト (Polygon Miden、Risc0、Winterfell、Neptune)、またはそれらの一部の改良版 (ZK-Sync の Boojum、Plonky2、Starky) によっても使用されます。

3) Ligero (2017)

Ligero は、証明サイズが O(root n) (n は回路サイズ) である証明システムを導入します。多項式係数を行列形式に配置し、線形コードを使用します。

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

5. ZKP のいくつかの新しい開発

本番環境でさまざまな証明システムを使用すると、それぞれの方法の利点がわかり、新しい開発につながります。たとえば、Plonkish 算術演算は、カスタム ゲートとルックアップ引数を組み込む簡単な方法を提供します。FRI は、Plonky よりも優れた PCS としての優れたパフォーマンスを示します。同様に、AIR でグランド プロダクト チェックを使用すると (前処理引数を使用してランダム化された AIR が生成されます)、パフォーマンスが向上し、メモリ アクセス引数が簡素化されます。ハッシュ関数に基づく約束は、ハードウェアのハッシュ関数の速度、または SNARK に適した新しいハッシュ関数の導入に基づいて普及しています。

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

多変量多項式 (Spartan や HyperPlonk など) に基づく効率的な SNARK の出現により、そのような多項式に適した新しいコミットメント スキームへの関心が高まっています。 Binius、Zeromorph、および Basefold はすべて、多線形多項式専用の新しい形式を提案しています。 Binius には、データ型を表すためのオーバーヘッドがゼロという利点があり (多くの証明システムでは、単一ビットを表すために少なくとも 32 ビットのフィールド要素が使用されます)、バイナリ ドメインで動作します。 Binius の約束は Brakedown に基づいており、ドメインに依存しないように設計されています。 Basefold は FRI をリードソロモンを超えるコードに一般化し、ドメインに依存しない PCS を実現します。

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

CCS は、R1CS、Plonkish、AIR の演算をオーバーヘッドなしでキャプチャしながら、R1CS を一般化します。 CCS と Spartan IOP を組み合わせると、SuperSpartan が実現します。SuperSpartan は、制約の程度に応じて拡張される暗号コストを証明者に負担させることなく、高度な制約をサポートします。特に、SuperSpartan は線形時間証明器を使用して AIR の SNARK を生成します。

6. 結論

この記事では、1980 年代半ばの SNARK の導入以来の SNARK の進歩について説明します。コンピューターサイエンス、数学、ハードウェアの進歩とブロックチェーンの導入により、より効率的な新しいSNARKが誕生し、私たちの社会を変える可能性のある多くのアプリケーションへの扉が開かれました。研究者とエンジニアは、プルーフ サイズ、メモリ使用量、透明性設定、ポスト量子セキュリティ、証明者時間、検証者時間に焦点を当て、ニーズに基づいて SNARK の改善と調整を提案しました。

当初は 2 つの主要なライン (SNARK と STARK) がありましたが、異なる証明システムの利点を組み合わせようとして、2 つの間の境界が薄れ始めています。たとえば、さまざまな算術スキームを新しい多項式コミットメント スキームと組み合わせます。新しい証明システムが今後も登場し、パフォーマンスが向上することが予想されますが、一部のコア インフラストラクチャを変更せずにツールを簡単に使用できない限り、適応に時間がかかる一部のシステムがこれらの開発に追いつくことは困難になります。 。

以上がゼロ知識証明における時代を超越したイノベーションの出現の背後にある本当の理由を探るの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。