概要とLasso以前の提案

Lookup Argumentは、事前に計算されたテーブルから値を参照することで計算コストを削減する手法です。

SHA-256回路などは、R1CSにすると2^20もの回路サイズになってしまいますが、テーブルに保存することで回路サイズを小さくすることができます。

Lookup Argumentでは、あるベクトルaがテーブルTの中に存在することを証明することで、計算結果が正しいことを証明します。

Lookup Argumentの分類

Lookup Argument	特徴	証明者の計算コスト
Arya		m+2N*log(m)
plookup	Plonk-IOPに適したLookup	5 * max(m, N)
HyperPlonk	Plonkをブールハイパーキューブに適応させた	4 * max(m, N)
Caulk	計算コストが線形以下	O(m^2 + m*log(N))
Caulk+	Caulkのサブプロトコルを多項式除算チェックに置き換えた	O(m^2)
flookup		O(m*log^2(m))
nlookup	HyperNovaに適したLookup

(mはルックアップ回数、Nはテーブルサイズ)

(計算コストはフィールド計算の回数)

References

1. Arya: https://discovery.ucl.ac.uk/id/eprint/10063978/1/ZKRAM-Asiacrypt2018-Final.pdf

2. plookup: https://eprint.iacr.org/2020/315.pdf

   1. Presentation: https://www.youtube.com/watch?v=Vdlc1CmRYRY

3. HyperPlonk: https://eprint.iacr.org/2022/1355

4. Caulk: https://eprint.iacr.org/2022/621

5. Caulk+: https://eprint.iacr.org/2022/957

6. flookup: https://eprint.iacr.org/2022/1447