ルックアップ引数について 1 つの記事で学ぶ

特邀专栏作者

2022-12-22 09:44

この記事は約2848文字で、全文を読むには約5分かかります

この記事では、OlaVM が高いパフォーマンスを達成できるようにするツールの 1 つである Lookup 引数に焦点を当てます。

TL;DR

前回の記事「Hello, OlaVM!」でも述べたように、OlaVM のビジョンは高パフォーマンスの ZKVM を構築することです。この記事では、OlaVM が高パフォーマンスを実現できるツールの 1 つである Lookup 引数に焦点を当てます。 Lookup 引数は、回路のサイズを縮小して ZK の効率を向上させる上で重要な役割を果たします。ZKVM の回路設計で広く使用されています。この記事を通じて、次のことを学ぶことができます。

1. ルックアップ引数は ZKVM でどのような役割を果たしますか?

2. Plookup プロトコルの原理。

3. Halo 2 の Lookup 引数プロトコルの原則。

最初のレベルのタイトル

The roles in ZKVM

いわゆる ZKVM は、実際には ZK を使用して VM のすべての実行プロセスを制約します。VM の実行プロセスは一般に、命令の実行、メモリアクセス、組み込み関数の実行などに分類できます。これらの操作に対する制約をトレースに実装するのは少し現実的ではないように思えます。まず、異なる操作タイプの制約は異なるトレース幅に対応します。制約の 1 つに対応するトレース幅が特に大きい場合、残りの制約が発生します。トレース幅に対応させるための無駄、トレース内に異なる演算タイプが多すぎる場合、より多くのセレクターが導入され、多項式の数が増えるだけでなく、制約の次数も増加します。グループの順序制限、トレース行このグループの順序を超えることはできないため、特定のタイプの操作が占めるトレース行の数は最小限に抑える必要があります。

したがって、簡単にするために次のものが必要です。

a. さまざまな操作タイプを複数のサブトレースに分割し、データの一貫性を確保するためにメイントレースとサブトレースの間に Lookup 引数が必要であることを個別に証明します。

b. 一部の ZK に適さない計算では、ビット演算などのトレースのサイズを縮小するためにルックアップ引数テクノロジを使用できます。

副題

Lookup between trace tables

画像の説明

図 1. トレース間のルックアップ

副題

Lookup for ZK-unfriendly operations

前述したように、各サブトレースの証明は独立しているため、できるだけ小さいトレースを取得すると証明者の効率が向上します。ビット単位を例に挙げると、ビット単位の演算には AND、XOR、NOT の 3 つの演算が含まれます。回路を介してビット単位の演算に対する制約を単純に実装したい場合は、各演算を複数のバイナリリムに分割する必要があります。これらの演算が 3 つの 2 ビット幅である場合、32 個のリムに分割されます。次に、以下を制限する必要があります。

合計 3 + 32 * 3 = 99 個のトレースセルが占有され、制約の数は 3 sumcheck + 32 bitwise = 35 になります。

画像の説明

図 2. 算術演算におけるルックアップ

最初のレベルのタイトル

副題

最初のレベルのタイトル

副題

最初のレベルのタイトル

Extend - 1 : Vector Lookup

Extend - 2 : Multi-tables

Links between Plookup and Lookup

Plookup プロトコルと Halo 2 ルックアッププロトコルは両方とも f⊂t を証明できますが、2 つのプロトコルの考え方は異なり、違いは次のとおりです。

Plookup は、f と t を使用して新しいシーケンス s を構築する必要があります。f と t の要素は s に少なくとも 1 回出現し、その後、s と t の要素の非ゼロ距離セットを比較することによって s⊂t が等しいことを証明する必要があります。、そして最後に f⊂s⊂t→f⊂t となります。

Halo 2 の lookup は、新しいシーケンスを構築せずに f⊂t を直接証明します。これは plookup よりも簡潔です。

最初のレベルのタイトル