この記事の由来は a 16 z、原著者：Justin Thaler、Odaily翻訳者のJessicaによって編集されました。
8 月 10 日、16 z 暗号は新しい SNARK ベースのツール Lasso と Jolt を発表しました。これらは合わせて、広く導入されているツールチェーンのパフォーマンスを一桁以上向上させることができる SNARK 設計への新しいアプローチを表しており、より優れた、より便利なツールを提供します。開発者のエクスペリエンス、そして監査を容易にします。
SNARK (Succinct Non-Interactive Argument of Knowledge) は、特定の特性を満たす「証人」を知っていることを信頼できない検証者に誰でも証明できる暗号プロトコルです。
Web 3 の顕著な使用例は、L2 が一連のトランザクションを承認するデジタル署名を知っていることを L1 に証明することです。これにより、署名自体を L1 ネットワークで保存および検証する必要がなくなり、スケーラビリティが向上します。
ブロックチェーン外部のアプリケーションには、信頼できないハードウェア デバイスによって生成されたすべての出力の正当性を迅速に証明し、ユーザーがそれらを信頼できるようにすることが含まれます。個人は、生年月日を明らかにすることなく、年齢制限のあるコンテンツにアクセスできる年齢であることを証明する認証情報を信頼できる機関が発行したことをゼロ知識の方法で証明できます。暗号化されたデータをネットワーク上で送信する人は誰でも、詳細を明らかにすることなく、データがネットワーク ポリシーに準拠していることを管理者に証明できます。
多くの SNARK は検証者にとって依然として魅力的なコストですが、SNARK は通常、依然として証明者の計算に約 6 桁のオーバーヘッドをもたらします。証明者が負担する追加の作業は高度に並列化されていますが、数百万回ものオーバーヘッドにより SNARK の適用範囲が大幅に制限されます。
より多くのパフォーマンス上の利点を持つ SNARK は L2 を高速化し、ビルダーがまだ想定されていないアプリケーションのロックを解除できるようにすることもできます。それが、証明者のコストを大幅に増加させる可能性のある新しいルックアップ パラメータである Lasso、いわゆる zkVM などに新しいフレームワークを提供するために Lasso を使用する Jolt という 2 つの新しい関連テクノロジを導入する理由です。 。これらを組み合わせることで、SNARK デザインのパフォーマンス、開発者エクスペリエンス、および監査可能性が向上し、結果的に Web 3 でのビルドが向上します。
副題
パラメータ、なげなわ、ジョルトの検索
SNARK フロントエンドは、コンピューター プログラムを SNARK バックエンドが取り込める回路に変換するコンパイラーです。(注: 回路は非常に限定された計算モデルであり、使用できる「原始演算」は加算と乗算のみです。)
最新の SNARK 設計における重要なツールは、ルックアップ パラメータと呼ばれるプロトコルです。これにより、信頼できない証明者が大きなベクトルを暗号的に送信し、そのベクトルの各エントリが所定のテーブル中央に含まれていることを証明できます。ルックアップ パラメーターは、小さな加算や乗算では自然には計算されない演算を効率的に処理することで、回路を小さく保つのに役立ちます。
しかし、イーサリアム財団のバリー・ホワイトハット氏が昨年述べたように、「ルックアップパラメータのみを使用して回路を効率的に定義できれば、より単純なツールと回路が実現するだろう」。私たちが設計した回路はルックアップのみを実行します。時間が経つにつれて、ルックアップ パラメータは「ほぼすべてのものについて多項式制約よりも効率的になるでしょう」。
このビジョンは、開発者がプログラムを多項式制約にコンパイルする特別なドメイン固有言語を使用してプログラムを作成するか、制約を直接ハンドコーディングすることによって SNARK を展開する今日の仕組みとはまったく対照的です。このツールチェーンは多大な作業が必要であり、安全上重要なバグが侵入するための多くの表面積を提供します。複雑なツールや回路を使用しても、SNARK のパフォーマンスは依然として遅いため、その適用性は制限されます。
Lasso と Jolt は、パフォーマンス、開発者エクスペリエンス、監査可能性という 3 つの主要な懸念事項すべてに対処します。一緒に、特異点を見つけるというビジョンが実現します。また、Lasso と Jolt は、SNARK のデザインで広く受け入れられている知恵の多くを再考するよう強いています。
副題
SNARK デザインの背景: なぜこんなに遅いのか?
ほとんどの SNARK バックエンドでは、証明者が多項式コミットメント スキームを使用して回路内の各ゲートの値を暗号的にコミットします。次に、証明者は、提出された値が証人チェッカーの正しい実行に実際に対応していることを証明します。
私がしなければならない多項式コミットメント スキームによる証明者の作業は、コミットメント コストと呼ばれます。SNARK には、多項式コミットメント スキームによる追加の証明コストがかかります。しかし多くの場合、コミットメントコストがボトルネックになります。ラッソとジョルトも同様です。コミットメント コストが主要な証明者コストではない SNARK が設計されている場合、それは多項式コミットメント スキームが安価であることを意味するわけではありません。むしろ、他のコストが必要以上に高くなっているということです。
直感的には、コミットメントの目的は、暗号的に安全に証明システムの単純性を高めることです。証明者が値の大きなベクトルを送信すると、通常の証明システムが証人全体を検証者に送信するのと同じように、証明者がベクトル全体を検証者に送信しているのとほぼ同じになります。コミットメント スキームは、バリデーターが実際に証人全体を受信することを強制することなくこれを実現できます。つまり、SNARK 設計におけるコミットメント スキームの目的は、バリデーターのコストを制御することです。
しかし、これらの暗号化手法は、特に SNARK が多項式コミットメント スキームの外で使用する情報理論的手法と比較すると、証明者にとって非常に高価です。情報理論的手法は有限体の演算のみに依存します。また、フィールド操作は、任意のフィールド要素を送信するのに必要な時間よりも桁違いに高速です。
副題
なげなわとジョルトが重要な理由
Lasso は、証明者が以前の作品よりも少ない、より小さな値を約束する新しい検索パラメータです。これにより 20 倍以上の高速化が可能になる可能性がありますここで、2 倍から 4 倍の高速化は、送信される値が少ないことによるものであり、さらに 10 倍の高速化は、なげなわで送信されるすべての値が小さいという事実によるものです。以前の多くのルックアップ パラメーターとは異なり、Lasso (および Jolt) はスペースを大量に消費し、大規模なインスタンスのボトルネックになる可能性がある FFT も回避します。
さらに、Lasso は、テーブルが (正確な技術的な意味で) 「構造化」されている限り、巨大なテーブルでも機能します。これらのテーブルは大きすぎて誰も明示的に実装できませんが、Lasso は実際にアクセスするテーブル要素に対してのみ料金を支払います。特に、以前の検索パラメータと比較して、テーブルが構造化されている場合、どちらの当事者もテーブル内のすべての値を暗号化された形式でコミットする必要はありません。
Lasso は、分解可能性と LDE 構造という 2 つの異なる構造概念を活用します。(LDE は、Low Degree Extended Polynomial と呼ばれる技術概念の頭字語です。)副題
Jolt
Jolt (Just One Lookup Table) は、巨大なルックアップ テーブルを使用する Lasso の機能によって解放される新しいフロントエンドです。Jolt は、命令セット アーキテクチャ (ISA) とも呼ばれる仮想マシン/CPU 抽象化をターゲットとしています。。この抽象化をサポートする SNARK は zkVM と呼ばれます。たとえば、RISC-Zero プロジェクトも対象としている RISC-V 命令セット (乗算拡張を含む) を考えてみましょう。これは、SNARK を考慮せずにコンピューター アーキテクチャ コミュニティによって開発された人気のオープンソース ISA です。
副題
SNARK デザインにおける常識を再考する
Lasso と Jolt は、SNARK デザインで受け入れられている常識の一部を覆します。
#1. 大きなSNARKはもったいない。一般に大規模なスケールに適用できる楕円曲線テクニックを避けるため、誰もが FRI、Ligero、Brakedown、またはそのバリアントを使用する必要があります。
ここでのフィールド サイズは、SNARK 証明に表示される数値のサイズにほぼ対応します。非常に大きな数の加算と乗算はコストがかかるため、大きなフィールドでの SNARK は無駄であるという考えは、決して大きな数を持たないプロトコルを設計するよう努めるべきであることを意味します。 MSM ベースのコミットメントでは楕円曲線が使用されます。楕円曲線は通常、大きなフィールド (サイズ約 2 256) にわたって定義されるため、これらの約束はパフォーマンスが低いという評判があります。
小さなフィールドを (オプションであっても) 使用することが意味があるかどうかは、主にアプリケーションに依存します。ラッソーとジョルトはさらに進化します。彼らは、MSM ベースのコミットメント スキームを使用しても、証明者の作業はフィールド サイズにほぼ依存しないことを示しています。これは、MSM ベースのコミットメントの場合、コミットされた値のサイズが、それらの値が存在するフィールドのサイズよりも重要であるためです。
既存の SNARK では、証明者は多くのランダムなフィールド要素にコミットする必要があります。たとえば、Plonk と呼ばれる一般的な SNARK バックエンドの証明者は、回路ゲートごとに約 7 つのランダム フィールド要素 (およびその他の非ランダム フィールド要素) をコミットします。これらのランダム フィールド要素は、証明された計算で表示されるすべての値が小さい場合でも大きくなる可能性があります。
対照的に、Lasso と Jolt では、証明者は小さな値を送信するだけで済みます (Lasso の証明者は、前のルックアップ パラメーターよりも少ない値も送信します)。これにより、MSM ベースのスキームのパフォーマンスが大幅に向上します。少なくとも、Lasso と Jolt は、証明者のパフォーマンスが重要な場合にはコミュニティが MSM ベースのコミットメントを放棄すべきであるという概念を解体する必要があります。
#2 命令セットがシンプルになると、zkVM が高速化されます。
Jolt の (命令ごとの) 複雑さは、各命令の評価テーブルが分解可能である限り、命令の入力サイズにのみ依存します。 Jolt は、驚くほど複雑な命令、特にすべての RISC-V が分解可能であることを実証しました。
これは、より単純な仮想マシン (zkVM) は必然的により小さな回路と、それに関連するより高速な証明器 (VM の各ステップ) につながるという一般に信じられている考えに反しています。これは、特に SNARK に適したように設計された Cairo VM などの特に単純な zkVM の背後にある主要な動機です。
実際、より単純な仮想マシンの場合、Jolt は証明者にとって以前の SNARK よりも低いコミットメント コストを実現します。たとえば、Cairo VM の実行の場合、SNARK 証明者は VM の各ステップで 51 個のフィールド要素を送信します。 Cairo によって展開された SNARK は現在 251 ビット フィールドで動作します (63 ビットは SNARK が使用できるフィールド サイズの厳密な下限です)。 Jolt の証明者は、RISC-V CPU のステップごとに最大 60 個のフィールド要素 (64 ビットを超えるデータ型を定義) を処理します。送信されるフィールド要素が小さいという事実を考慮すると、Jolt 証明者のコストは、6 つのランダムな 256 ビット フィールド要素を送信するコストとほぼ同等になります。
#3 大規模な計算を小さなチャンクに分割してもパフォーマンスが低下することはありません。
この見解に基づいて、今日のプロジェクトは大規模な回路を小さなブロックに分解し、各ブロックを個別に証明し、SNARK を通じて結果を再帰的に集計します。これらの展開では、このアプローチを使用して、一般的な SNARK のパフォーマンスのボトルネックを軽減します。たとえば、FRI ベースの SNARK は、小規模な回線であっても 100 GB 近くのプルーフ スペースを必要とします。また、SNARK が大規模回路に「同時に」適用される場合、ボトルネックになる可能性がある超線形演算である FFT も必要です。
実際には、一部の SNARK (Lasso や Jolt など) は (現在展開されている SNARK に見られる規模の不経済ではなく) 規模の経済を示しています。これは、証明されるステートメントが大きくなるほど、直接証人チェック (つまり、正しさを保証せずに証人回路を評価するために必要な作業) に比べて証明者のオーバーヘッドが小さくなることを意味します。技術レベルでは、規模の経済は 2 つの場所から生まれます。
サイズ n の MSM のピッペンジャーの高速化: log( n ) は、単純なアルゴリズムよりも改善されています。 n が大きいほど改善も大きくなります。
Lasso などのルックアップ パラメーターでは、証明者はルックアップ テーブルのサイズに応じて「1 回限り」のコストを支払いますが、ルックアップされる値の数とは関係ありません。 1 回限りの証明者のコストは、テーブルへのすべてのルックアップにわたって償却されます。ブロックが大きいほど検索数が多くなり、償却が向上します。
現在、大規模な回路を処理する一般的な方法は、物事を可能な限り小さな部分に分割することです。各部分のサイズに関する主な制約は、再帰的集計証明が証明者にとってボトルネックになるほど小さくしてはいけないということです。
Lasso と Jolt は、本質的に反対のアプローチを提案しています。スケールメリットのあるSNARKを利用すべきだ。次に、大規模な計算をできるだけ大きな部分に分割し、結果を再帰的に調べます。各フラグメントのサイズに関する主な制限は証明空間であり、フラグメントが大きくなるにつれて増加します。
#4 効率的な SNARK には高さの制約が必要です。
Jolt は中間表現として R1 CS を使用します。 Jolt で高さまたはカスタム コンストレイントを使用するメリットはありません。 Jolt における証明者のコストのほとんどは、検索を当然とする結果として得られる制約システムの充足可能性を証明するのではなく、パラメーター Lasso を検索することにかかっています。
Jolt は汎用性があるため、多用途性を失うことはありません。そのため、今日の人気の SNARK からパフォーマンスの向上を絞り出すために、開発者が設計の高さの制約 (多くの場合手動で指定) に重点を置くことに対抗します。
もちろん、一部のコンテキストでは高さまたはカスタム制約の恩恵を受ける場合もあります。重要な例は Minroot VDF で、その 5 次制約によりコミットメント コストを約 3 分の 1 に削減できます。
#5 スパース多項式コミットメント スキームはコストがかかるため、可能な限り避けるべきです。
これは、最近導入された CCS と呼ばれる拘束システムと、それをサポートする SNARK (スパルタンとマーリン) に対する主な批判です。CCS は、今日実際に普及しているすべての拘束システムを明確に一般化したものです。
この批判には根拠がありません。実際、Lasso と Jolt の技術的中核は、Spartan - Spark の疎多項式コミットメント スキームです。 Spark 自体は、任意の (非スパース) 多項式コミットメント スキームをスパース多項式をサポートするスキームに汎用的に変換するものです。
Lasso は、証明者が「小さな」値のみにコミットするように Spark を最適化および拡張しますが、これらの最適化がなくても批判は正当化されません。実際、Spartan の証明者は、SNARK (疎多項式コミットメントを回避する Plonk など) よりも少ない (ランダムな) フィールド要素を約束します。
Spartan のアプローチには、特に繰り返し構造を持つ回路において、さらなるパフォーマンス上の利点があります。これらの回路では、追加ゲートは Spartan 証明者の暗号化作業に追加されません。この作業は、制約の数ではなく、特定の制約システム内の変数の数に応じてのみ増加します。 Plonk とは異なり、Spartan 証明者は同じ変数の複数の異なる「コピー」を送信する必要はありません。
私たちは、Lasso と Jolt によって SNARK の設計方法が劇的に変わり、パフォーマンスと監査可能性が向上すると楽観的に考えています。これは、証明者のコミットメントコストを最小限に抑える驚異的な機能を備えた重要なツールです。
