IOSG: ゼロ知識証明における継続的なイノベーションの原動力は何ですか?

著者: LambdaClass

翻訳: mutourend; Yiping、IOSG Ventures

1. はじめに

ゼロ知識、簡潔、非対話型知識証明 (zk-SNARKs) ) は、証明者がステートメント以外の情報を明らかにすることなく、ステートメントの正しさを検証者に納得させることができる強力な暗号化プリミティブです。 zk-SNARK は、検証可能なプライベート計算、コンピューター プログラムの実行の正しさの証明、およびブロックチェーンの拡張における応用により、広く注目を集めています。私たちは、記事で説明したように、zk-SNARK が世界の形成に大きな影響を与えると信じています。 zk-SNARK は、さまざまな多項式コミットメント スキーム、算術スキーム、インタラクティブなオラクル証明、または確率的テスト可能な証明を使用する、さまざまなタイプの証明システムをカバーします。しかし、これらの基本的なアイデアやコンセプトは 1980 年代半ばまで遡ります。 zk-SNARK の開発は、ゼロ知識証明 (この特定の使用例では妥当性証明と呼ばれることが多い) を使用して拡張できるため、ビットコインとイーサリアムの発売以来大幅に加速しました。 zk-SNARK は、ブロックチェーンのスケーラビリティにおいて重要な役割を果たします。ベン・サッソン氏が述べているように、近年、カンブリア紀の爆発的な暗号証明が見られます。各証明システムには長所と短所があり、特定のトレードオフを念頭に置いて設計されています。ハードウェア、アルゴリズム、新しいプルーフ、ツールの進歩により、パフォーマンスが向上し続け、新しいシステムの作成につながります。これらのシステムの多くはすでに使用されており、私たちは限界を押し広げ続けます。すべてのアプリケーションに機能する普遍的な証明システムがあるのでしょうか、それともさまざまなニーズに適したいくつかのシステムがあるのでしょうか?私たちは、次のような理由により、1 つの証明システムが他の証明システムを圧倒する可能性は非常に低いと考えています。

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

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

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

証明システムは大幅な変更を受ける可能性がありますが、高速検証可能性という 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 つです。これは、多変量多項式評価を合計する要件を、ランダムに選択された点の単一の評価に減らすのに役立ちます。

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

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

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

Kate、Zaverucha、Goldberg は 2010 年に、多項式とその応用に対する定数サイズのコミットメントで双線形ペアリング群を使用した多項式コミットメント スキームを導入しました。コミットメントは単一のグループ要素で構成され、コミッターは多項式の正しい評価に対するコミットメントを効果的に開きます。さらに、バッチ技術のおかげで、複数の評価を開くことができます。 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)Lookups (2018/2020)

6)Spartan (2019)

7) HyperPlonk (2022)

8) 折り畳みスキーム (2008/2021)

3.1 Pinocchio (2013)

Pinocchio (論文「Pinocchio: ほぼ実用的」を参照) 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 では、C プログラムの実行の正しさを証明するために PCP ベースの SNARK が開発され、TinyRAM (簡易命令セット コンピューター) にコンパイルされます。 。このコンピュータは、バイトレベルでアドレス指定可能なランダム アクセス メモリを備えたハーバード アーキテクチャを使用しています。非決定性を利用して、回路のサイズは計算のサイズに準線形的に関係するため、任意のデータ関連のループ、制御フロー、およびメモリ アクセスを効率的に処理できます。

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 (ルート n) (n は回路サイズ) である証明システムを導入します。多項式係数を行列形式に配置し、線形コードを使用します。

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

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

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

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

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

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

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

6. 結論

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

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

以上がIOSG: ゼロ知識証明における継続的なイノベーションの原動力は何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。