a16z crypto が新たに発表した2つの SNARK ツールの詳細解説

原文タイトル：「ルックアップ特異点」へのアプローチ：LassoとJoltの紹介
編訳：倩雯，ChainCatcher

SNARKは、誰でも信頼されていない検証者に対して特定の属性を満たす「証拠」（witness）を知っていることを証明できる暗号プロトコルです。SNARKのWeb3における顕著な応用の一つは、L2ロールアップがL1のブロックチェーンに対して一連の取引を承認するデジタル署名を知っていることを証明することです。これにより、署名自体はL1に保存および検証される必要がなくなり、スケーラビリティが向上します。

SNARKのブロックチェーン外での応用には、高速だが信頼されていないハードウェアデバイスが生成したすべての出力の有効性を証明し、ユーザーがそれらを信頼できるようにすることが含まれます。個人は、信頼機関が発行した証明書をゼロ知識で証明できます。たとえば、年齢制限のあるコンテンツにアクセスするのに十分な年齢であることを、誕生日を明かさずに証明することができます。ネットワークを通じて暗号化データを送信する誰もが、そのデータがネットワークポリシーに準拠していることを管理者に証明でき、詳細を明かす必要はありません。

多くのSNARKは証明者（prover）にとってコストが低いですが、一般的にSNARKは検証計算に約6桁のオーバーヘッドをもたらします。検証者が負担する追加の作業は高度に並列化可能ですが、100万倍のオーバーヘッドはSNARKの応用を大きく制限します。

より高性能なSNARKはL2の速度を向上させ、ビルダーがまだ実現されていないアプリケーションをアンロックできるようにします。したがって、私たちは2つの関連する新技術を発表しました：Lassoは新しいルックアップパラメータであり、証明者のコストを大幅に削減します；JoltはLasso技術を使用して、zkVMや他のフロントエンド設計にSNARKの新しいフレームワークを提供します。これらは共同でSNARK設計の性能、開発者体験、監査可能性を向上させ、web3の構築を促進します。

人気のSNARKツールチェーンhalo2のルックアップパラメータと比較して、Lassoの初期実装は速度が10倍以上向上したことが証明されています。Lassoのコードベースが完全に最適化されると、速度は約40倍向上すると予想しています。JoltにはLassoに基づくさらなる革新が含まれており、既存のzkVMと同等またはそれ以上の速度を実現できることを期待しています。

ルックアップパラメータ、LassoとJolt

SNARKフロントエンド（SNARK frontend）は、コンピュータプログラムを回路に変換し、SNARKバックエンドが取り込むコンパイラです。回路は、原始的な演算が加算と乗算のみである非常に限られた計算モデルです。

現代のSNARK設計における重要なツールの一つはルックアップパラメータ（lookup argument）であり、これは信頼されていない証明者が暗号的に大規模なベクトルを提出し、そのベクトルの各エントリが特定のテーブルに含まれていることを証明できるプロトコルです。ルックアップパラメータは、少数の加算と乗算では自然に計算できない演算を効率的に処理でき、回路の小型化を維持するのに役立ちます。

イーサリアム財団のバリーは、「ルックアップパラメータだけを使用して効率的に回路を定義できれば、より簡素化されたツールと回路がもたらされる」と提案しました。つまり、「ルックアップ特異点」を実現することができ、これにより「ルックアップのみを実行する回路を設計できる」ようになります。この方法は、ほぼすべての面で多項式制約よりも優れています。

このビジョンは、今日の作業方法と対照的です。今日の作業方法では、開発者は特異性のあるドメイン固有言語を使用してSNARKをデプロイするか、制約を手動でコーディングします。このツールチェーンは多くの人力と物力を消費し、安全性に関する重大な脆弱性の可能性を高めます。複雑なツールや回路を使用しても、SNARKは依然として遅く、その応用を制限しています。

LassoとJoltは、性能、開発者体験、監査可能性という3つの重要な問題を解決しました。私は、これらが共同でルックアップ特異点のビジョンを実現すると信じています。LassoとJoltは、SNARK設計における多くの公认真理についても再考を促します。必要な背景知識を紹介した後、本記事ではSNARKの性能に関する一般的な見解を再評価し、LassoやJoltなどの革新技術に基づいてこれらの見解を更新する方法を説明します。

SNARK設計の背景：なぜこんなに遅いのか？

ほとんどのSNARKバックエンドは、検証者に回路内の各ゲートの値に対して暗号的なコミットメントを行わせる方法を使用します。これを多項式コミットメントスキームと呼びます。その後、証明者はコミットされた値が証拠検査プログラムの正しい実行に適合していることを証明します。

私は、多項式コミットメントスキームからの証明者の作業をコミットメントコスト（commitment cost）と呼びます。SNARKには多項式コミットメントスキーム以外からの追加の証明者コストもあります。しかし、コミットメントコストはしばしばボトルネックとなります。LassoとJoltの場合も同様です。SNARKを設計する際、コミットメントコストが主要な証明者コストを構成しない場合、それは多項式コミットメントスキームのコストが低いことを意味するのではなく、むしろ他のコストがそれらのレベルを上回っていることを意味します。

直感的に言えば、コミットメントの目的は、暗号的方法を通じて証明システムの簡潔さを安全に増加させることです。証明者が大きな値のベクトルに対してコミットメントを行うと、これは証明者が全体のベクトルを検証者に送信するのと似ています。これは、トリビアル証明システム（trivial proof system）が全体の証拠を検証者に送信するのと同じです。コミットメントスキームは、検証者が実際に全体の証拠を受け取ることを強制することなくこれを実現します。これは、SNARK設計において、コミットメントスキームの目的が検証者コストを制御することであることを意味します。

しかし、これらの暗号的方法は証明者にとって非常に高価であり、特にSNARKが多項式コミットメントスキームの外で使用する情報理論的方法と比較すると顕著です。情報理論的方法は有限体の演算にのみ依存します。そして、一度のフィールド演算の速度は、任意のフィールド要素に対するコミットメントに必要な時間よりも数桁速いです。

使用される多項式コミットメントスキームに応じて、コミットメントの計算には多項式の累乗（または多スカラー乗法、MSMとも呼ばれます）、またはFFTとメルクルハッシュが含まれます。LassoとJoltは任意の多項式コミットメントスキームを使用できますが、MSMベースのスキーム（たとえば、IPA/Bulletproofs、KZG/PST、Hyrax、Dory、またはZeromorph）を使用する場合、追加のコストが発生します。

LassoとJoltが重要な理由

Lassoは新しいルックアップパラメータの方法であり、以前の方法と比較して証明者がコミットする値が少なく、より小さくなります。具体的な状況に応じて、速度を20倍以上向上させることができ、そのうち2倍から4倍はコミットメント値が少ないことから、残りの10倍はLasso内で全てのコミットメント値が非常に小さいことから来ています。以前の多くのルックアップパラメータとは異なり、Lasso（およびJolt）はFFTを回避しており、FFTは大量のスペースを必要とし、大規模なインスタンスではボトルネックを引き起こす可能性があります。

さらに、テーブルが「構造化されている」限り（技術的に正確な意味で）、Lassoは巨大なテーブル（たとえば、規模が2128に達するもの）にも適用できます。テーブルの規模が大きすぎると、誰もそれを具体化することはできませんが、Lassoは実際にアクセスするテーブル要素に対してのみコストを支払います。もう一つ注目すべき点は、テーブルが構造化されている場合、どの当事者もテーブル内のすべての値に対して暗号的なコミットメントを行う必要がないことです。

Lassoは、可分解性とLDE構造という2つの異なる構造概念を利用しています。可分解性は、非常に小規模なテーブルの少数のルックアップを通じて、テーブル全体のルックアップを完了できることを指します。これはLDE構造よりも厳格な要件ですが、Lassoは可分解なテーブルに適用する際に非常に効率的です。

Jolt

Jolt（Just One Lookup Table「ただ一つのルックアップテーブル」）は、Lassoに基づいて巨大なルックアップテーブルの機能を持つ新しいフロントエンドです。Joltは仮想マシン/CPUの抽象化、すなわち命令セットアーキテクチャ（ISA）を対象としています。この抽象をサポートするSNARKはzkVMと呼ばれます。たとえば、RISC-ZeroプロジェクトがサポートするRISC-V命令セット（乗算拡張を含む命令セット）です。これは、コンピュータアーキテクチャコミュニティによって開発された人気のオープンソースISAで、開発時にはSNARKを考慮していませんでした。

各RISC-V命令fiに対して、Joltの主なアイデアは、fiの全評価テーブルを含むルックアップテーブルを作成することです。したがって、fiが2つの32ビット入力を受け取る場合、そのテーブルには264のエントリがあり、(x,y)'thのエントリはfi(x,y)です。もし64ビットのデータ型の命令を考慮するなら、各命令のテーブルのサイズは264ではなく2128になります。

基本的に、各RISC-V命令のルックアップテーブルは可分解であり、Lassoに適用できます。少数の命令は、他の命令の短いシーケンスを適用することで処理されます。たとえば、除算命令の処理方法は、証明者が商と余りを提出し、商と余りが一度の乗算と一度の加算で正しく提供されたかどうかを確認することです。

TステップのRISC-V CPUを実行する回路は、次のように生成できます。Tステップの各ステップに対して、回路はそのステップで実行する原始的なRISC-V命令fiとその命令の入力(x,y)を決定するためのいくつかの単純なロジックを含みます。次に、回路は一度のルックアップを実行し、関連するテーブルの(x,y)項を明らかにすることでfiを実行します。より正確には、Joltは1つのテーブルのみを考慮しており、それは各命令のテーブルが接続されたものであるため、「ただ一つのルックアップテーブル」と呼ばれます。

SNARK設計における公认真理の再評価

LassoとJoltは、SNARK設計におけるいくつかの公认真理を覆しました。

1.SNARKの過大なフィールド（over large field）は無駄である。誰もがFRI、Ligero、Brakedownまたはその変種を使用すべきであり、これらの技術は楕円曲線技術を回避し、楕円曲線技術は通常大きなフィールドに適しています。

ここでのフィールドサイズは、SNARK証明において数値が出現するサイズとして大まかに理解できます。大きな数の加算と乗算のオーバーヘッドは非常に大きいため、大きなフィールド上のSNARKは無駄を引き起こし、これは私たちが大きな数が決して出現しないプロトコルを設計すべきであることを意味します。MSMに基づくコミットメントは楕円曲線を使用し、楕円曲線は通常大きなフィールド上で定義され（サイズは約2256）、そのため楕円曲線の性能は劣ります。

私は以前、小さなフィールドを使用することが合理的かどうかは、アプリケーションに大きく依存すると議論しました。LassoとJoltは、MSMに基づくコミットメントスキームを使用しても、証明者の作業がフィールドサイズの影響をほとんど受けないことを示しています。これは、MSMに基づくコミットメントにおいて、コミットメント値のサイズがそれらの値が存在するフィールドのサイズよりも重要であるためです。

既存のSNARKは、証明者に多くのランダムフィールド要素を提出させます。たとえば、Plonkという証明者は、各回路ゲートに対して約7つのランダムフィールド要素（および追加の非ランダムフィールド要素）を提出します。証明された計算に出現するすべての値が非常に小さくても、これらのランダムフィールド要素は非常に大きくなります。

対照的に、LassoとJoltは証明者に小さな数値を提出するよう要求するだけです（Lassoの証明者が提出する数値は以前のルックアップパラメータよりも少ない）。これは、MSMスキームの性能を大幅に向上させます。少なくとも、LassoとJoltは、証明者の性能が重要な場合、コミュニティがMSMに基づくコミットメントを放棄すべきだという考えを捨てるべきです。

2.命令セットがシンプルであれば、zkVMの速度が向上する。

各命令の評価テーブルが可分解である限り、Jolt（各命令）の複雑さは命令の入力サイズのみに依存します。Joltは、巨大な複雑な命令が可分解であることを証明しました。特に、すべてのRISC-V命令がそうです。

これは、よりシンプルな仮想マシン（zkVM）が必然的により小さな回路とそれに関連するより高速な証明者（仮想マシンの各ステップ）の結果をもたらすという一般的な見解と対照的です。この見解は、極小のzkVM（Cairo VMなど）の設計を導いてきました。

実際、よりシンプルな仮想マシンに対して、Joltは以前のSNARKよりも証明者のコミットメントコストを低下させることができます。たとえば、Cairo VMを実行する証明者は、仮想マシンの各ステップで51のフィールド要素を提出する必要があります。Cairo VMがデプロイするSNARKは、現在251ビットのフィールドにあります（63ビットはSNARKがフィールドサイズを使用できるハードリミットです）。Joltの検証者は、RISC-V CPU上で各ステップで約60のフィールド要素を提出します（64ビットデータ型として定義されます）。提出されるフィールド要素が少ないことを考慮すると、Joltの検証者のコストは約6つの256ビットのランダムフィールド要素を提出するコストに相当します。

3.大規模な計算を小さな部分に分解しても性能の損失はない。

この見解に基づいて、現在のプロジェクトは大きな回路を小さな部分に分解し、それぞれの部分を証明し、SNARKの再帰を通じて結果を集約します。これらのデプロイは、この方法を使用して多くのSNARKの性能ボトルネックを緩和しています。たとえば、FRIに基づくSNARKは、小型回路に対しても約100GBの証明者スペースを必要とします。また、FFTも必要であり、これは超線形操作であり、SNARKが一度に大規模な回路に適用されるとボトルネックになります。

現実には、いくつかのSNARK（LassoやJoltなど）は規模の経済性を示しています（現在デプロイされているSNARKは規模の経済性を持っていません）。これは、証明された文が大きくなるほど、証明者のオーバーヘッドが相対的に証拠検査（witness checking、すなわち正しさを保証せずに証拠回路を評価するために必要な作業）のコストが小さくなることを意味します。技術的には、規模の経済は2つの側面から来ます：

1）サイズnのMSMのピッペンジャー加速（Pippenger speedup）は、元のアルゴリズムに対してlog(n)倍の向上をもたらします。nが大きくなるほど、向上が大きくなります。

2）Lassoなどのルックアップパラメータでは、証明者はルックアップテーブルのサイズに依存する一度のコストを支払う必要がありますが、ルックアップ値の数には依存しません。証明者の一度のコストは、テーブルへのすべてのクエリで分散されます。より大きなデータブロックは、より多くのルックアップを意味し、より良い分散をもたらします。

現在、大規模な回路を処理する主流の方法は、回路をできるだけ小さなブロックに分解することです。各ブロックのサイズの主な制限は、それらが小さすぎると再帰的な証明の集約が証明者のボトルネックになることです。

LassoとJoltは、基本的に逆のアプローチを提案します。私たちは規模の経済性を持つSNARKを使用すべきです。そして、大規模な計算をできるだけ大きな部分に分解し、結果を再帰的に処理します。各計算セグメントのサイズの主な制限要因は証明者スペースであり、計算セグメントが大きくなるにつれて、証明者スペースも増加します。

4.高次制約は効率的なSNARKの必要条件である。

JoltはR1CSを中間表現として使用します。Joltでは、「高次」または「カスタム」制約を使用しても何の利益もありません。Joltでは、証明者の大部分のコストはルックアップパラメータLassoにあり、証明制約システムの充足性にはありません（このシステムはルックアップオプションを当然のものと見なします）。

Joltは汎用的であるため、汎用性を失うことはありません。したがって、開発者は高度な制約（通常は手動でカスタマイズされたもの）を設計する際に、今日の人気のSNARKからより高い性能を引き出すために、高度な制約の設計に重点を置いていますが、Joltはまさにその逆です。

もちろん、特定の状況では、高度またはカスタム制約が役立つこともあります。重要な例はMinroot VDFであり、これに対して5次制約はコミットメントコストを約3倍削減できます。

5.スパース多項式コミットメントスキーム（Sparse polynomial commitment）は高額であり、可能な限り回避すべきである。

真の批判は、最近導入されたCCSとそのシステムをサポートするSNARK（（Super-）Spartanおよび（Super-）Marlin）に主に向けられています。CCSは、今日の実践で人気のあるすべての制約システムの簡潔な要約です。

この批判は根拠がありません。実際、LassoとJoltの技術の核心は、Spartanにおけるスパース多項式コミットメントスキームであるSparkです。Spark自体は、任意の（非スパース）多項式コミットメントスキームをスパース多項式をサポートするスキームに変換するものです。

LassoはSparkを最適化および拡張し、証明者が「小さな」値のみを提出することを保証しますが、これらの最適化がなくても、この批判は無意味です。実際、Spartanの証明者は、SNARK（Plonkなどのスパース多項式コミットメントを回避するSNARK）と比較して、コミットされた（ランダムな）フィールド要素が少なくなります。

Spartanのアプローチは、特に繰り返し構造を持つ回路に対して追加の性能上の利点を持っています。これらの回路に対して、ゲートを追加してもSpartan検証者の暗号的作業量は増加しません。この作業量は、与えられた制約システム内の変数の数が増加するにつれてのみ増加し、制約の数が増加するにつれては増加しません。また、Plonkとは異なり、Spartan検証者は同じ変数の複数の異なる「コピー」に対してコミットメントを行う必要はありません。

結論

私たちは、LassoとJoltがSNARKの設計方法を大きく変え、性能と監査可能性を向上させると信じています。本シリーズの次回の記事では、LassoとJoltの動作原理について詳しく探ります。