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