Lookup argument总览

1. 引言

详情参看Ingonyama团队Tomer 2023年论文《A Brief History of Lookup Arguments》。

Bootle等人2018年论文《Nearly linear-time zero-knowledge proofs for correct program execution》中首次提出了lookup协议，用于证明如下statement：

此处假设 m < N m<N m<N，且大多数情况下 m ≪ N m\ll N m≪N。

可将lookup协议用于：

• 1）range checks：如检查某数字 x x x的取值范围为 { 0 , ⋯   , N − 1 } \{0,\cdots,N-1\} {0,⋯,N−1}，其中 N = 2 n N=2^n N=2n。
• 2）有限域函数：用于实现任意的有限域内函数运算。
• 3）更好的XOR运算
• 4）有限状态机

当前的Lookup argument方案主要有：

• 1）Plookup
• 2）cq
• 3）Caulk
• 4）Caulk+
• 5）Flookup
• 6）Baloo