Lookup Arguments

ZKVMの役割

zkVMはゼロ知識証明を用いて仮想マシンの実行プロセス（命令実行、メモリアクセス、組み込み関数の実行）を制約します。ただし、これらを1つのトレースにまとめて制約するのは以下の点で非効率です

1.トレース幅の無駄：異なる制約を必要とする列数が異なり、一部の行が広くなると全体の幅が過剰になる

2.多様な操作タイプの問題：1つのトレース内に操作タイプが多すぎると選択子や多項式が増え、制約の次数が高くなる

3.グループ次数の制限：トレース行数がグループの次数に制限されるため特定の操作タイプに割り当てる行数を抑える必要がある

これらを解決するために以下のアプローチを採用する

異なる操作タイプを複数のサブトレースに分割し、主要トレースとサブトレース間のデータ整合性を「Lookup Argument」で保証する。

ビット操作のようなZKに不向きな計算では、「Lookup Argument」を使ってトレースサイズを削減する。

トレース間のLookup

VMの実行プロセス全体は「メイントレース」と呼ばれる完全なトレースを形成しますが、これはVMのすべての状態を含むものの、ZK検証に便利な補助状態は含みません。補助情報をメイントレースに含めると複雑化し制約が難しくなるため、補助情報は通常サブトレースに分離され、それぞれ別々に制約をかけます。メイントレースは主にプログラムの正しい実行やコンテキスト制約の確認に使用されます。

https://scrapbox.io/files/6746ba451caa9ee58ff1f7cc.png

サブトレースを作成することで、VMが実行する異なる操作を分割し、Lookup Argument技術を用いてサブトレース内のデータがメイントレースから派生していることを保証します。特に、ビット演算や範囲チェックなどのZKに不向きな操作に対しては、特定の操作タイプに応じたトレースを生成し、対応する制約で妥当性を証明します。

ZKに不向きな操作におけるLookupの活用

ZKに不向きな操作（例：ビット演算や範囲チェック）もLookup Argumentを活用して効率化を図ることができる。

1.ビット演算の最適化:

典型的には入力ビット同士の組み合わせを使うため非線形な計算となり、ビット演算をポリノミアル制約で表現する際に複雑で高次の制約が必要になる。またビット分解のためにトレースセルや追加制約が必要になる

AND、XOR、NOTなどのビット演算を直接制約で実装すると、32ビット操作の場合、99個のトレースセルと35の制約が必要

固定された真理値表を用いることで、32ビット操作を4つの8ビット単位に分割し、Lookupを用いて真理値表を参照することで、トレースセルを15個、制約を4つに削減可能。

2.範囲チェックの最適化:

32ビット操作を2つの16ビット単位に分割しトレースセルを削減する

範囲チェックのサム制約にカスタマイズしたADD-MUL制約を再利用可能。

3.共通制約の再利用:

カスタマイズされたASS-MULゲートを用いることで、ADD、MUL、ADD-MUL、EQ、RANGECHECKなど複数の計算タイプで同じ制約を再利用し、全体の効率を向上させる

https://scrapbox.io/files/6746badd500cb363cb817b63.png

これらの方法により、ビット演算や範囲チェックなどの証明プロセスが大幅に効率化されます。

参考