Lookup Argument简史

1. 引言

主要参考Ingonyama团队2023年4月文章《A Brief History of Lookup Arguments》。

近年来zk-SNARKs的研究热点有：

• 让ZKP proof更succinct
• 降低Prover time和Verifier time

但，大多数SNARKs仍受限于，易于转换为多项式的算术运算。通常将“易于转换为多项式的算术运算” 称为 “SNARK-friendly”的，而其它“SNARK-unfriendly”运算则仍未解决。

直到2018年Jonathan Bootle等人在《BCG+18 Nearly linear-time zero-knowledge proofs for correct program execution》论文中，提出了lookup协议来处理某些SNARK-unfriendly运算。lookup协议用于证明如下statement：

• 已知table T = { t i } i = 0 , ⋯ , N − 1 T=\{t_i\}_{i=0,\cdots,N-1} T={ti​}i=0,⋯,N−1​具有不同值（“rows”）
• 一组lookups F = { f j } j = 0 , ⋯ , m − 1 F=\{f_j\}_{j=0,\cdots,m-1} F={fj​}j=0,⋯,m−1​（可能有重复值）
• 证明：所有lookups均包含在table内，即$F\subseteq T$。

table $T$通常是public的，而lookups通常为private witness。
可：

• 将table看成是某特定变量的所有合法值
• 而lookups为，某特定程序执行给出的该变量值。
• 则，以上statement即表示，该变量维护了整个执行过程中的合法状态。
• 除非明确指出，可假定$m<N$，且大多数情况下$m\ll N$。

本文关注各种不同的lookup argument及其变种演变思路，重点关注：

• plookup：Ariel Gabizon等人2020年论文 plookup: A simplified polynomial protocol for lookup tables
• cq：Liam Eagen等人2022年论文 cq: Cached quotients for fast lookups

2. lookup argument用途

2.1 范围检查

当检查数字$x$在 { 0 , 1 , ⋯ , N − 1 } \{0,1,\cdots,N-1\} {0,1,⋯,N−1}范围内，其中$N=2^n$。
对应的算术约束方式为：

• 定义$n$个数字$b_0,\cdots ,b_{n-1}$，检查对于每个$i$，有 b i ∈ { 0 , 1 } b_i\in\{0,1\} bi​∈{0,1}，且${\sum }_i{b}_i{2}^i=x$。一共需要$n+1$个约束。
• 若需要做$m$个数字的范围检查，则需要$O(mn)=O(m\log N)$个约束。

而若借助lookup argument，则仅需要一个lookup约束，就可检查$m$个数字在 { 0 , 1 , ⋯ , N − 1 } \{0,1,\cdots,N-1\} {0,1,⋯,N−1}范围内。后面将介绍这样一个lookup约束的开销。且当$N$不是为power of 2时，上面的算术约束方式将是笨重的，而lookup argument无需关注$N$是否为power of 2。

2.2 有限域函数

lookup argument可用于实现任意（有限域）函数，通过简单将该函数的完整输入输出值来定义table。可用于实现具有任意多个变量的函数。

如哈希计算中广泛使用的$k$-bit XOR函数。遵循2.1节的逻辑，使用算术约束方式，将需要$6k$个约束。而借助lookup argument，可直接借助table $T$来实现，其中table $T$的rows为：
$t_i=(A,B,C)$
其中：

• 对于每个$i$， A , B ∈ { 0 , 1 , ⋯ , 2 k − 1 } A,B\in\{0,1,\cdots,2^k-1\} A,B∈{0,1,⋯,2k−1}为2个$k$-bit数字的不同组合，且$C=A\oplus B$。
• 整个table $T$具有$2^{2k}$行，且每行需存储$3k$ bits。
  • 当$k=32$时（很多哈希函数的通用取值），则这样的table是完全不实用的。
  • 当$k=16$时，这样的table需要24GB存储空间，对大多数应用场景来说，也是不实用的。

2.3 更好的XOR

Halo2中的16-bit table chip for SHA-256，通过利用zero-interleaving，借助lookup argument，实现了更好的bit-wise XOR函数。
zero-interleaving，是指以二进制来表示数字：
$A={\sum }_{l=0}^{k-1}{a}_l{2}^l$
然后在任意2个原始bits之间添加一个‘0’ bit，从而有：
$A^{\prime }={\sum }_{l=0}^{k-1}{a}_l{4}^l$
对XOR的2个输入$A,B$均做zero-interleaving之后，有$A^{\prime },B^{\prime }$。计算$C^{\prime \prime }=A^{\prime }+B^{\prime }$，则$C^{\prime \prime }$的偶数位置的bit即为$C=A\oplus B$。为根据$C^{\prime \prime }$获得$C$，需将$C^{\prime \prime }$分解为奇数bit和偶数bit：
$C^{\prime \prime }={\sum }_{l=0}^{k-1}{c}_l^{even}{4}^l+2{\sum }_{l=0}^{k-1}{c}_l^{odd}{4}^l$

从而：

• 有$c_l^{even}$为$C=A\oplus B$的二进制表示，
• 同时有副产品：$c_l^{odd}$为$D=A\wedge B$的二进制表示。$\wedge$表示bit-wise AND。
• 借助4次zero-interleaving table：$A,B,C,D\to A^{\prime },B^{\prime },C^{\prime },D^{\prime }$，以及一个算术约束：
  $A^{\prime }+B^{\prime }=C^{\prime \prime }=C^{\prime }+2D^{\prime }$
  可同时证明$A,B$的bit-wise XOR和bit-wise AND结果。

当$k=32$时，以上实现仍是不切实际的大，单个table需要48GB存储空间。
但，对于$k=16$的情况，以上实现对应的lookup table仅需要384kB。
可通过slicing以SNARK-friendly的方式来降低bits数，即，引入arithmetic gate——其以2个16-bit数字$x_0,x_1$为输入，然后最终获得32-bit的数字$x=x_0\cdot 1+x_1\cdot 2^{16}$。

2.4 有限状态机

lookup table可用于实现有限状态机。状态机内包含一组状态，以及依赖于输入的状态变化。实现状态机的lookup table内，包含 (current state, input, next state) 的所有合法组合。状态机的execution trace通常表示为：
$(state(j),input(j),next\_state(j))$

可使用lookup argument来证明该状态机的合法执行，同时证明wiring约束：
$next\_state(j)=state(j+1)$

该wiring 约束是SNARK-friendly的。

3. Plookup

Plookup为早期的lookup协议之一，其为首个lookup协议的简化版。
Plookup的基于的思想为：

• 已知向量$t\in {\mathbb{F}}^N,f\in {\mathbb{F}}^m,s\in {\mathbb{F}}^{N+m}$，和双变量多项式：
  $F(\beta ,\gamma )=(1+\beta {)}^m{\prod }_{j=1}^m(\gamma +f_j){\prod }_{i=1}^{N-1}(\gamma (1+\beta )+t_i+\beta t_{i+1})$
  $G(\beta ,\gamma )={\prod }_{k=1}^{m+N-1}(\gamma (1+\beta )+s_k+\beta s_{k+1})$
• 则有：
  F ≡ G ⇔ { { f j } ⊆ { t i } , 且 s = ( f , t ) sorted by  t F\equiv G \Leftrightarrow \left\{\begin{matrix} \{f_j\}\subseteq \{t_i\}, & 且 \\ s=(f,t) \text{ sorted by } t & \\ \end{matrix}\right. F≡G⇔{{fj​}⊆{ti​},s=(f,t) sorted by t​且​
  其中：
  • $s=(f,t)\text{ sorted by }t$，表示$s$中值的出现顺序，与$t$中的出现顺序一样，因为有 { f j } ⊆ { t i } \{f_j\}\subseteq \{t_i\} {fj​}⊆{ti​}。

若有$s=(f,t)\text{ sorted by }t$，且， { f j } ⊆ { t i } \{f_j\}\subseteq \{t_i\} {fj​}⊆{ti​}，则对于每个$i=1,\cdots ,N-1$，都有不同的 k ∈ { 1 , ⋯ , m + N − 1 } k\in\{1,\cdots,m+N-1\} k∈{1,⋯,m+N−1}，使得：
$$(\gamma (1+\beta )+t_i+\beta t_{i+1})=(\gamma (1+\beta )+s_k+\beta s_{k+1})\text{\hspace{1em}(3.4)}$$
而对于其它$s_k=s_{k+1}$的索引值$k$，存在 j ∈ { 1 , ⋯ , m } j\in\{1,\cdots,m\} j∈{1,⋯,m}，使得$f_j=s_k$，且：
$$(1+\beta )(\gamma +f_j)=(\gamma (1+\beta )+s_k+\beta s_{k+1})\text{\hspace{1em}(3.5)}$$

将$\beta$看成是系数，则可将$F,G$看成是$\mathbb{F}[\gamma ]$多项式，从而具有唯一分解因子。通过识别以上3.4和3.5方程式中的因子，可发现其因子为关于变量$\beta$的多项式。

3.1 Plookup定义

Plookup使用如下定义：

• 1）取$m=N-1$，若不满足$N=m+1$，则需重复最后一个元素来填充相应的table，直到其满足$N=m+1$。
• 2） H = { g , ⋯ , g N = 1 } H=\{g,\cdots,g^N=1\} H={g,⋯,gN=1}为$\mathbb{F}$中order为$N$的multiplicative subgroup。
• 3）对于向量$p={\mathbb{F}}^N$，定义多项式$p(x)\in \mathbb{F}[X{]}_{<N}$，使得向量值为该多项式的evaluation值，即满足$p_i=p(g^i)$。
• 4）令$L_i(x)\in \mathbb{F}[X{]}_{<N}$为基于$H$的第$i$个Lagrange都像是，满足$L_i(g^j)={\delta }_{ij}$（为Kronecker delta）。
• 5）$s\in {\mathbb{F}}^{2N-1}$为$(f,t)$ sorted by $t$。

3.2 Plookup协议

最终的Plookup协议为：

• 1）Prover计算并对2个多项式$h_1,h_2\in \mathbb{F}[x{]}_{<N}$进行承诺，使得对于每个$i=1,\cdots ,N$，有：
  $h_1(g^i)=s_i$
  $h_2(g^i)=s_{N+i-1}$
• 2）Verifier给Prover发送随机值$\beta ,\gamma$。
• 3）Prover计算并对多项式$Z\in \mathbb{F}[x{]}_{<N}$多项式进行承诺，$Z$聚合了$F(\beta ,\gamma )/G(\beta ,\gamma )$，有：
  $Z(g)=1$
  对于$i=2,\cdots ,N-1$，有 $$Z(g^i)=\frac{(1+\beta {)}^{i-1}{\prod }_{l=1}^{i-1}(\gamma +f_l)(\gamma (1+\beta )+t_l+\beta t_{l+1})}{{\prod }_{l=1}^{i-1}(\gamma (1+\beta )+s_l+\beta s_{l+1})(\gamma (1+\beta )+s_{N+l}+\beta s_{N+l+1})}\text{\hspace{1em}(3.9)}$$
  $Z(g^N)=1$
• 4）Verifier对所有$x\in H$，检查如下identities：
  $$L_1(x)(Z(x)-1)=0\text{\hspace{1em}(3.11)}$$
  $$L_N(x)(Z(x)-1)=0\text{\hspace{1em}(3.12)}$$
  $$L_N(x)(h_1(x)-h_2(gx))=0\text{\hspace{1em}(3.13)}$$
  $$(x-g^N)Z(x)(1+\beta )(\gamma +f(x))(\gamma (1+\beta )+t(x)+\beta t(gx))=(x-g^N)Z(gx)(\gamma (1+\beta )+h_1(x)+\beta h_1(gx))(\gamma (1+\beta )+h_2(x)+\beta h_2(gx))\text{\hspace{1em}(3.14)}$$

注意，所构建的$Z(x)$多项式，在3.9方程式的基础上，分子分母乘以了相同的乘数项。即意味着，添加了第$N$项后，$F,G$的等价性，暗含了所有项可消减，最终获得1。3.11和3.12方程式检查了$Z(g)=Z(g^N)=1$，而3.14方程式，检查了每个evaluation值确实添加了正确的乘数项——其两边增加的$(x-g^N)$乘数项，可确保不包含$Z(g^N)$和$Z(g^{N+1})=Z(g)$之间的关系。

3.3 Plookup开销

Plookup协议不依赖于任何特殊的承诺方案。通常：

• 其Prover runtime为$O(N\log N)$个域运算（以根据evaluations值构建多项式），和$O(N)$个group运算（以构建多项式$Z$）。
• 当使用KZG承诺方案时，其proof size为5个group元素和9个域元素，而Verifier runtime为2个pairing函数。

3.4 Plookup泛化与优化

Plookup协议可泛化为多个witness多项式$f_1,\cdots ,f_w\in \mathbb{F}[x{]}_{<m}$和多个tables $t_1,\cdots ,t_w\in \mathbb{F}[x{]}_{<N}$。Verifier选择随机值$\alpha$，然后这些多项式可聚合为：
$t={\sum }_{l=1}^w{\alpha }^l{t}_l$
$f={\sum }_{l=1}^w{\alpha }^l{f}_l$

然后像之前那样处理$f,t$。

若table为一组连续的整数，即有$t_{l+1}=t_l$，则可将Plookup协议中的3.9方式简化为：
$Z(g^i)=\frac{{\prod }_{l=1}^{i-1}(\gamma +f_l)(\gamma +t_l)}{{\prod }_{l=1}^{i-1}(\gamma +s_l)(\gamma +s_{N+l})}$

对应的Verifier checks也需做相应调整。

Plookup协议另一个泛化是plonkup协议，见Luke Pearson等人2022年论文 Plonkup: Reconciling plonk with plookup，plonkup协议集成了plonk和plookup，支持引入通用plonk gates的高效lookup table。

4. cq协议

plookup协议的主要问题在于：

• 对于$m\ll N$的常见场景，plookup协议开销大。

自plookup协议问世以来，迭代了多个lookup协议，每个新的lookup协议，相比于之前协议，对$N$的依赖性都有所减弱，这些新lookup协议背后的核心思想为：

• 将大部分table计算，移到，预计算中。

截止2023年4月，最好的lookup协议为cq，见Liam Eagen等人2022年论文 cq: Cached quotients for fast lookups。

4.1 Logarithmic Derivative对数导数

cq协议基于如下 Logarithmic Derivative trick：

• 2个多项式$p(x)={\prod }_{a\in A}(x+a)$和$q(x)={\prod }_{b\in B}(x+b)$相等，当且仅当如下有理函数相等：
  $\frac{p^{\prime }(x)}{p(x)}={\sum }_{a\in A}\frac{1}{x+a}$
  $\frac{q^{\prime }(x)}{q(x)}={\sum }_{b\in B}\frac{1}{x+b}$

即由$p(x)=q(x)$，推导出有$p^{\prime }(x)/p(x)=q^{\prime }(x)/q(x)$是trivial的，而反之，由$p^{\prime }(x)/p(x)=q^{\prime }(x)/q(x)$，有：
$(\frac{p(x)}{q(x)}{)}^{\prime }=\frac{p^{\prime }(x)q(x)-q^{\prime }(x)p(x)}{p^2(x)}=0$

即意味着，有$p(x)/q(x)=c$，其中$c$为常数值。但是，由于$p(x),q(x)$的leading系数均为1，则有$c=1$且$p(x)=q(x)$。从而，lookups $f$包含在table $t$中，当且仅当：
$$\sum _{i=1}^N\frac{m_i}{x+t_i}=\sum _{j=1}^m\frac{1}{x+f_j}\text{\hspace{1em}(4.4)}$$
其中：

• $m_i$为lookup $f_j$中$t_i$值出现的次数。注意，每个$t_i$是唯一的，而$f_j$值支持重复，且对于许多$t_i$可以有$m_i$值为0。

cq协议的核心思想为，测试4.4方程式，在某随机点$x=\beta$的有理函数identity。

4.2 将cq协议identity调整为Sumcheck

可定义多项式$A(x),B(x)$，使得其evaluations值为：
$$A_i=\frac{m_i}{\beta +t_i},i=1,\cdots ,N\text{\hspace{1em}(4.5)}$$
$B_j=\frac{1}{\beta +f_j},j=1,\cdots ,m$

来做4.4方程式的cq协议 identity检查。

此处有：

• $A_i=A(g^i)$，其中$g$为order为$N$的multiplicative subgroup $V\subset \mathbb{F}$的generator。
• $B_j=B(w^j)$，其中$w$为order为$m$的multiplicative subgroup $H\subset \mathbb{F}$的generator。

基于随机点$\beta$，为满足方程式4.4中的关系，$A_i,B_j$需满足${\sum }_i{A}_i={\sum }_j{B}_j$，且基于multiplicative groups的这些多项式evaluations值，遵循：
${\sum }_{i=1}^N{A}_i=N\cdot A(0)$
${\sum }_{i=j}^m{B}_j=m\cdot B(0)$

然后，Prover必须证明：
$$N\cdot A(0)=m\cdot B(0)\text{\hspace{1em}(4.9)}$$

这对应的单变量sumcheck问题。

4.3 cq协议的quotient多项式

多项式：
$p(x)=A(x)(T(x)+\beta )-m(x)$
$q(x)=B(x)(F(x)+\beta )-1$
其中：

• $T(x),m(x),F(x)$多项式的evaluation值分别为$t_i,m_i,f_j$。
• 对于$V$，$p(x)$的evaluation值必须为0。
• 对于$H$，$q(x)$的evaluation值必须为0。

从而可定义quotient多项式$Q_A(x),Q_B(x)$为：
$$Q_A(x)=\frac{A(x)(T(x)+\beta )-m(x)}{Z_V(x)}\text{\hspace{1em}(4.12)}$$
$$Q_B(x)=\frac{B(x)(F(x)+\beta )-1}{Z_H(x)}\text{\hspace{1em}(4.13)}$$
其中：

• $Z_V(x),Z_H(x)$分别为$V,H$的vanishing多项式。

Prover需证明2件事：

• 1）其知道多项式$A,B,Q_A,Q_B,F,m$。
• 2）这些多项式满足上面4.9、4.12、4.13方程式关系。

若使用KZG承诺方案，则其只需要使用pairing来检查这些方程式关系。不过，接下来将进一步将这些statements切分。

4.4 cq协议中，证明其知道多项式$A$及其sum

当使用KZG承诺值$[\varphi (x){]}_1$来证明其知道多项式$\varphi (x)$时，Prover会对其在$z$点进行evaluate以定义新的多项式：
$P_{\varphi }=\frac{\varphi (x)-\varphi (z)}{x-z}$
并发送承诺值$[P_{\varphi }{]}_1$。Verifier会检查pairing方程式：
$e([\varphi (x){]}_1-[\varphi (z){]}_1,[1{]}_2)=e([P_{\varphi }{]}_1,[x-z{]}_2)$

将其重写为：
$e([\varphi (x){]}_1-[\varphi (z){]}_1+z\cdot [P_{\varphi }{]}_1,[1{]}_2)=e([P_{\varphi }{]}_1,[x{]}_2)$

使得该pairing函数的第二个参数总为$[1{]}_2$或$[x{]}_2$。

为证明其知道多项式$A$，对$A$在$x=0$点进行evaluate，有：
$P_A(x)=\frac{A(x)-A(0)}{x}$
并承诺$[P_A{]}_1$，然后使用：
$e([A(x){]}_1-[A(0){]}_1,[1{]}_2)=e([P_A(x){]}_1,[x{]}_2)$
来证明。

4.5 cq协议中，$B$多项式的low degree testing

为证明知道多项式$B$：

• 首先证明多项式$B$的degree确实$<m$。

注意，无需证明$A(x)$的degree，因其degree为SRS所支持的最大degree。

在KZG承诺方案中，为证明多项式$B$的degree确实$<m$，可定义：
$P_B(x)=\frac{B(x)-B(0)}{x}$
然后承诺$[P_B(x)\cdot x^{N-m+1}{]}_1$，最后测试：
$e([P_B(x){]}_1,[x^{N-m+1}{]}_2)=e([P_B(x)\cdot x^{N-m+1}{]}_1,[1{]}_2)$

注意，若$B(x)$中有degree $\ge m$的项，则将包括在承诺值$[P_B(x)\cdot x^{N-m+1}{]}_1$中，而SRS不支持对degree $\ge N$的项进行承诺。

4.6 cq协议中，使用Cached Quotients来证明4.12）方程式关系

可通过如下testing：
$e([A(x){]}_1,[T(x){]}_2)=e([Q_A(x){]}_1,[Z_V(x){]}_2)\cdot e([m(x){]}_1-\beta [A(x){]}_1,[1{]}_2)$

来检查4.12）方程式关系。

其中：

• $[T{]}_2,[Z_V{]}_2,[1{]}_2,[x{]}_2$均独立于lookups，可预计算。
• Prover需计算：$[A(x){]}_1,[Q_A(x){]}_1,[m(x){]}_1,A(0),[\frac{A(x)-A(0)}{x}{]}_1$。
  • 这些计算复杂度为$O(m)$，因其仅需要计算lookups。若$t_i$不存在于lookups中，则有$m_i=0,A_i=0$。
  • 只有$[Q_A(x){]}_1$的计算为$O(N)$。对应的解决方案为：
    • 预计算cached quotients：
      $$Q_i(x)=\frac{L_i(x)(T(x)-t_i)}{Z_V(x)}=\frac{T(x)-t_i}{k^i(x-g^i)}\text{\hspace{1em}(4.22)}$$
      其中：
      • $L_i(x)$为Lagrange多项式
      • $L_i(x)=\frac{Z_V(x)}{k^i(x-g^i)}$
      • $k^i=Z_V^{\prime }(g^i)=(x^N-1{)}^{\prime }{|}_{x=g^i}=N\cdot g_i^{N-1}=\frac{N}{g^i}$
      • 使用NTT，$Q_i(x)$的计算量为$O(N\log N)$。
      • 使用$Q_i(x)$，$[Q_A{]}_1$的计算量为$O(m)$，有：
        $[Q_A(x){]}_1={\sum }_{A_i\ne 0}{A}_i\cdot [Q_i(x){]}_1$
        其中$A_i$为4.5）方程式中多项式$A(x)$的evaluation值。

4.7 cq协议中，证明4.9）4.13）方程式关系

引入另一随机值$x=\gamma$：

• 首先对多项式：
  $P_F(x)=\frac{F(x)-F(\gamma )}{x-\gamma }$
  $P_{B,\gamma }(x)=\frac{P_B(x)-P_B(\gamma )}{x-\gamma }$
  承诺来证明知道 $F(\gamma ),P_B(\gamma )$。
  可通过验证：
  $$e([F(x){]}_1-[F(\gamma ){]}_1+\gamma [P_F(x){]}_1,[1{]}_2)=e([P_F(x){]}_1,[x{]}_2)\text{\hspace{1em}(4.28)}$$
  $$e([P_B(x){]}_1-[P_B(\gamma ){]}_1+\gamma [P_{B,\gamma }(x){]}_1,[1{]}_2)=e([P_{B,\gamma }(x){]}_1,[x{]}_2)\text{\hspace{1em}(4.29)}$$
  来证明$B(x),F(x)$确实evaluate到$B(\gamma ),F(\gamma )$，从而可使用这些evaluations值来证明所需的关系。
• 定义：
  $$Q_{b,\gamma }=\frac{(B(\gamma )-B(0)+A(0)\cdot N/m)(F(\gamma )+\beta )-1}{Z_H(\gamma )}\text{\hspace{1em}(4.30)}$$
  $P_{Q_B}(x)=\frac{Q_B(x)-Q_{b,\gamma }}{x-\gamma }$
  然后发送承诺值$[Q_{b,\gamma }{]}_1,[P_{Q_B}(x){]}_1$，可通过如下pairing等式来验证：
  $$e([Q_B(x){]}_1-[Q_{b,\gamma }{]}_1+\gamma [P_{Q_B}(x){]}_1,[1{]}_2)=e([P_{Q_B}(x){]}_1,[x{]}_2)\text{\hspace{1em}(4.32)}$$
  注意，该构建可同时证明如下statements：
  $Q_B(\gamma )=\frac{(B(\gamma ))(F(\gamma )+\beta )-1}{Z_H(x)}$
  $B(0)\cdot m=A(0)\cdot N$
  这样整个证明结束。

4.8 cq协议的proof batching

最后的3个proofs结构相似，cq协议可将其batch为单个协议——通过引入新的随机变量$\eta$，并定义：
$c(x)=P_B(x)+\eta F(x)+{\eta }^2{Q}_B(x)$
$v=P_B(\gamma )+\eta F(\gamma )+{\eta }^2{Q}_{b,\gamma }$
$P_{\gamma }(x)=P_{B,\gamma }(x)+\eta P_F(x)+{\eta }^2{P}_{Q_B}(x)$

然后，将4.28）、4.29）、4.32）聚合为单个check：
$e([c(x){]}_1-[v{]}_1+\gamma [P_{\gamma }(x){]}_1,[1{]}_2)=e([P_{\gamma }(x){]}_1,[x{]}_2)$

4.9 cq完整协议

4.9.1 Setup阶段

Prover和Verifier均有公开输入$t_i$，$i=1,\cdots ,N$。如下流程由某可信方执行：

• 1）选择随机值$x\in \mathbb{F}$，输出$\{[x^i{]}_1{\}}_{i=0}^{N-1}$和$\{[x^i{]}_2{\}}_{i=0}^N$。数字$x$必须删除。
• 2）计算并输出$[Z_V(x){]}_2$。
• 3）计算$T(x)={\sum }_i{t}_i{L}_i(x)$。计算并输出$[T(x){]}_2$。
• 4）对于每个$i=1,\cdots ,N$，计算并输出：
  • 根据4.22）方程式，计算并输出$[Q_i(x){]}_1$
  • $[L_i(x){]}_1$
  • $[\frac{L_i(x)-L_i(0)}{x}{]}_1$

setup阶段的输出，组成SRS，会同时发送给Prover和Verifier。

4.9.2 Proving阶段

Prover获得private witness值$f_j$，$j=1,\cdots ,m$，而Verifier获得的为这些输入的承诺值$[F(x){]}_1$。这些输入需源自同一可信方，以对待证明的问题达成共识。

cq协议证明阶段流程为：

注意，Verifier根据4.30）方程式计算$Q_{b,\gamma }$，其需要的$B(\gamma ),B(0)$并不是由Prover发送。但Prover发送了$P_B(\gamma )=(B(\gamma )-B(0))/\gamma$，因此，Verifier可计算：
$Q_{b,\gamma }=\frac{(P_B(\gamma )\cdot \gamma +A(0)\cdot N/m)(F(\gamma )+\beta )-1}{Z_H(\gamma )}$

4.10 cq协议，进一步batching和聚合

可使用Fiat-Shamir transformation来将以上协议转换为非交互式的。此时，proof内容为：
${\pi }_{cq}=\{[m{]}_1,[A{]}_1,[Q_A{]}_1,[Q_B{]}_1,[P_A{]}_1,[P_B{]}_1,[P_B{x}^{N-m+1}{]}_1,[P_{\gamma }{]}_1,P_B(\gamma ),F(\gamma ),A(0)\}$
其中：

• 前8个为group元素
• 最后3个为field元素

相应的pairing等式有：
$e([P_B(x){]}_1,[x^{N-m+1}{]}_2)=e([P_B(x)\cdot x^{N-m+1}{]}_1,[1{]}_2)$
$e([A(x){]}_1,[T(x){]}_2)=e([Q_A(x){]}_1,[Z_V(x){]}_2)\cdot e([m(x){]}_1-\beta [A(x){]}_1,[1{]}_2)$
$e([A(x){]}_1-[A(0){]}_1,[1{]}_2)=e([P_A(x){]}_1,[x{]}_2)$
$e([c(x){]}_1-[v{]}_1+\gamma [P_{\gamma }(x){]}_1,[1{]}_2)=e([P_{\gamma }(x){]}_1,[x{]}_2)$

引入新的随机值$\mu \in \mathbb{F}$，很容易将以上最后2个pairing等式batch为：
$e([c(x){]}_1-[v{]}_1+\gamma [P_{\gamma }(x){]}_1+\mu ([A(x){]}_1-[A(0){]}_1),[1{]}_2)=e([P_{\gamma }(x){]}_1+\mu [P_A(x){]}_1,[x{]}_2)$
再引入$\rho \in \mathbb{F}$，将其与第一个pairing等式batch，有：
$e([P_{\gamma }(x){]}_1+\mu [P_A(x){]}_1,[x{]}_2)\cdot e(\rho [P_B(x){]}_1,[x^{N-m+1}{]}_2)=e([c(x){]}_1-[v{]}_1+\gamma [P_{\gamma }(x){]}_1+\mu ([A(x){]}_1-[A(0){]}_1)+\rho [P_B(x)\cdot x^{N-m+1}{]}_1,[1{]}_2)$

再引入$\sigma \in \mathbb{F}$，将其与第二个pairing等式batch为单个pairing等式。定义：
$L_a=[P_{\gamma }(x){]}_1+\mu [P_A(x){]}_1$
$L_b=\rho [P_B(x){]}_1$
$L_c=\sigma [A(x){]}_1$
$L_d=-\sigma [Q_A(x){]}_1$
$R=[c(x){]}_1-[v{]}_1+\gamma [P_{\gamma }(x){]}_1+\mu ([A(x){]}_1-[A(0){]}_1)+\rho [P_B(x)\cdot x^{N-m+1}{]}_1+\sigma ([m(x){]}_1-\beta [A(x){]}_1)$

最终batch的单个pairing等式为：
$e(L_a,[x{]}_2)\cdot e(L_b,[x^{N-m+1}{]}_2)\cdot e(L_c,[T(x){]}_2)\cdot e(L_d,[Z_V(x){]}_2)=e(R,[1{]}_2)$

由于以上每个pairing函数中的第二个参数均只依赖于setup，具有相同setup的不同proofs，通过引入新的随机参数$\chi \in \mathbb{F}$，来聚合为单个proof：
$e({\sum }_k{\chi }^k{L}_{a,k},[x{]}_2)\cdot e({\sum }_k{\chi }^k{L}_{b,k},[x^{N-m+1}{]}_2)\cdot e({\sum }_k{\chi }^k{L}_{c,k},[T(x){]}_2)\cdot e({\sum }_k{\chi }^k{L}_{d,k},[Z_V(x){]}_2)=e({\sum }_k{\chi }^k{R}_k,[1{]}_2)$

4.11 cq协议开销

不同于plookup协议，cq协议高度依赖KZG承诺方案。

cq协议的开销为：

• cq协议将plookup协议$O(N\log N)$复杂度移到了setup阶段，使得这些计算对同一table只需做一次。
• cq协议证明阶段计算完全依赖于$m$，而可假设$m\ll N$。【也就是说，若$m\ll N$条件不成立，则没理由使用cq协议，plookup协议的性能会更佳。】
• cq协议Prover工作量为$O(m\log m)$。
• cq协议proof size和Verifier工作量均为常量。

5. lookup协议演进

本节将简要介绍由plookup到cq的改进点，并回顾二者之间的其它lookup协议。注意这些lookup协议都明确依赖KZG承诺方案。

5.1 Caulk

Arantxa Zapico等人2022年论文《 Caulk: Lookup arguments in sublinear time》提出了Caulk协议。
Caulk协议背后的核心思想为：

• （以$O(N\log N)$）预计算table encoding，使得该table searchable in $O(\log N)$
• lookups也做类似的encoding，使得对其的查找复杂度为$O(m\log N)$，证明该encoding的额外复杂度为$O(m^2)$。

Caulk协议：

• 将table预计算为vanishing多项式：
  $Z_T(x)={\prod }_{i=1}^N(x-t_i)$
• 将lookups类似计算为：
  $f(x)={\prod }_{j=1}^m(x-f_j)$
• Prover发送$Z_T,f$的承诺值。
• 将证明：对于$S\subseteq T$，有$f=Z_S$
  转换为证明：$Z_{T\setminus S}(x)=Z_T(x)/Z_S(x)$为一个多项式。
• 对于每个$i=1,\cdots N$，caulk会预计算多项式：
  $g_i(x)=Z_{T\setminus t_i}(x)$
  事实上，这些就是cq协议中的cached quotients。
• 若$S\subseteq T$，则有某些数字$c_j\in \mathbb{F}$，使得$Z_{T\setminus S}(x)$可分解表示为：
  $Z_{T\setminus S}(x)={\sum }_{j=1}^m{c}_j{g}_i(j)(x)$
  Prover仅需要计算$Z_{T\setminus S}(x)$多项式的承诺值，而Verifier仅需使用pairing检查：
  $e([f],[Z_{T\setminus S}])=e([Z_T],[1])$

5.2 Caulk+ 协议

Jim Posen等人2022年论文《Caulk+: Table-independent lookup arguments》中提出了Caulk+协议：

• Caulk协议中的主要缺点为：其将table看成是通用集合，而不是将其编码为某group。
• Caulk+ 协议：通过预计算table，改进了Caulk协议中的缺点。
  • Caulk+ 将table看成是某multiplicative group，其初始值为group generator powers。
  • 从而消除了计算中对$N$的依赖，prover time仅为$O(m^2)$。

5.3 Flookup 协议

Ariel Gabizon等人2022年论文《flookup: Fractional decompositionbased lookups in quasi-linear time independent of table size》提出了flookup协议：

• 将预处理开销增加到了$O(N{\log }^{2}N)$
• 将Prover runtime降低到了$O(m{\log }^{2}m)$
• 同时牺牲了承诺方案的同态属性，从而不支持将多个lookups和tables进行合并。

5.4 Baloo 协议

Arantxa Zapico等人2022年论文《Baloo: Nearly optimal lookup arguments》中提出了Baloo协议，其为Caulk+ 协议的优化版：

• 将lookups替换为a linear variant。
• 然后使用单变量sumcheck来证明其所承诺的多项式。
• 其预处理开销与Caulk+相同，为$O(N\log N)$。
• 其Prover开销与flookup相同，为$O(m{\log }^{2}m)$。
• 由于Baloo协议中的constants更大，Baloo协议的实际开销要略高于flookup。但其保留了承诺方案的同态属性，从而支持将多个lookups和tables进行合并。

lookup系列博客

• PLOOKUP
• PLOOKUP代码解析
• Efficient polynomial commitment schemes for multiple points and polynomials学习笔记
• PLONK + PLOOKUP
• PlonKup: Reconciling PlonK with plookup
• PLONK: permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge 学习笔记
• Plonk代码解析
• RapidUp: Multi-Domain Permutation Protocol for Lookup Tables学习笔记
• Lookup argument总览
• Halo2 学习笔记——设计之Proving system之Lookup argument（1）
• logUp-Multivariate lookups based on logarithmic derivatives
• cq：fast lookup argument
• Lookup Argument性能优化——Caulk
• 2023年 ZK Hack以及ZK Summit 亮点记
• Research Day 2023：Succinct ZKP最新进展
• Lasso、Jolt 以及 Lookup Singularity——Part 1
• Lasso、Jolt 以及 Lookup Singularity——Part 2
• 深入了解Lasso+Jolt
• Lookup Singularity
• Halo2、Caulk+、Baloo、Cq Lookup argument细览