Lookup PIOP
本节介绍一下多变量查找关系，该关系基于多集检查，也是HyperPlonk+的核心，核心思想与Plonkup的单变量查找类似，但是Plonkup的多变量扩展需要更多的多项式子域，因此扩展是非平凡的
为了将该关系扩展至多线性的情况，需要建立一个有效的函数$g$来生成布尔超立方，此外该函数$g$还必须得是线性的，因为线性函数可以防止多项式的阶数不会指数爆炸
首先介绍一下Lookup关系：该关系为一个三元组$(\mathbf i;\mathbf x;\mathbf w)=(\mathbf t;[[f]];(f,addr))$，其中$\mathbf t$为长度为$2^\mu-1$的域元素向量，多项式$f$的阶至多为$d$，$addr:B_\mu\rarr[1,2^\mu)$用于将$\mathbf x$映射到表中的地址，也即$f(\mathbf x)=\mathbf t_{addr(\mathbf x)}$
在正式介绍lookup协议之前，先介绍一下如何构建一个生成整个布尔超立方的二次函数
对于$\mu \in \N$，和子集$S\sube [\mu-1]$，固选择一个本原多项式$p_\mu\in \mathbb F_2[X]$，如下
$$ p_\mu=X^\mu+\sum_{s\in S} X^s+1 $$
根据$p_\mu$的定义，$X$是$\mathbb F^\mu_2[X]\backslash\{0\}$的生成元，因此可以定义一个生成元函数$g_\mu:B_\mu\rarr B_\mu$，如下
$$ g_\mu(\mathbf b_1,\dots,\mathbf b_\mu)=(\mathbf b_\mu,\mathbf b_1',\dots,\mathbf b'_{\mu-1}) $$
其中若$i\in S$，则$\mathbf b'_i= \mathbf b_i\oplus b_\mu$，否则$\mathbf b'_i= \mathbf b_i$
注意到多项式$f$的系数为$\mathbf b$，$g_\mu(\mathbf b)$为$X\cdot f(X)$的系数向量，因此可以得到下列引理
Lemma 1：对于所有的$\mathbf x\in B_\mu\backslash \{0^\mu\}$，有$\{g_\mu^{(i)}(\mathbf x\}_{i\in [2^\mu-1]}=B_\mu\backslash\{0^\mu\}$，其中$g_\mu^{(i)}(\cdot)$表示$g_\mu$的$i$次迭代
这个引理不难理解，因为$X$是生成元，对于生成元函数$g_\mu$和$\mathbf x\in B_\mu\backslash \{0^\mu\}$，$g_\mu$的$i$次迭代的值还是在$B_\mu\backslash \{0^\mu\}$内
由于用生成器$g$直接合成多项式$f$会导致得到的多项式的阶变得非常大，而且此类方式中Prover需要发送一个复合的预言机$f(g(\cdot))$，会进一步影响PIOP的效率
本文通过将生成元线性化来解决这个问题，对于多变量多项式$f$，定义$f_{\Delta_\mu}$如下
$$ f_{\Delta_\mu}(\mathbf X_1,\dots,\mathbf X_\mu)=\mathbf X_\mu\cdot f(1,\mathbf X'_1,\dots,\mathbf X'_\mu)+(1-\mathbf X_\mu)\cdot f(0,\mathbf X_1,\dots,\mathbf X_\mu) $$
其中若$i\in S$，则$\mathbf X_i'=1-\mathbf X_i$，否则$\mathbf X_i'=\mathbf X_i$
上面的$g_\mu$对应于Part I中的$next()$，$f_\Delta$对应于Part I中的多项式$f'$
这样一来，只需要计算两次$f$就可以计算得到$f_\Delta$
这里可以看一下为什么对于$\mathbf x\in B_\mu$，均有$f_{\Delta_\mu}=f(g_\mu)$
首先对于$\mathbf x=0^\mu$的情况，根据定义，不难得到$f_{\Delta_\mu}(0^\mu)=f(0^\mu),g_\mu(0^\mu)=0^\mu$，因此$f_{\Delta_\mu}(0^\mu)=f(g_\mu(0^\mu))$
然后看一下对于$\mathbf x\in B_\mu/\{0\}$的情况，根据上面定义的，若$i$在集合$S$内，则$\mathbf x'_i=\mathbf x_i\oplus \mathbf x_\mu$，这里可以考虑$\mathbf x_\mu$的情况
- 当$\mathbf x_\mu=1$时，$\mathbf x'_i=\mathbf x_i\oplus \mathbf x_\mu=1-\mathbf x_i$
- 当$\mathbf x_\mu=0$时，$\mathbf x'_i=\mathbf x_i\oplus \mathbf x_\mu=\mathbf x_i$
因此我们可以得到
$$ \begin{aligned} f(\mathbf x_\mu,\mathbf x'_1,\dots,\mathbf x'_{\mu-1})&=\mathbf x_\mu\cdot f(1,\mathbf x_1^*,\dots,\mathbf x'_{\mu-1})+(1-\mathbf x_\mu)\cdot f(0,\mathbf x_1,\dots,\mathbf x_{\mu-1})\\ &=f_{\Delta_\mu}(\mathbf x_1,\dots,\mathbf x_\mu) \end{aligned} $$
综上，对于$\mathbf x\in B_\mu$，均有$f_{\Delta_\mu}=f(g_\mu)$
基于上述内容，介绍一下Lookup的PIOP，Lookup的PIOP需要调用一个2集合的多集检查协议
先介绍一个新的记法，用于将向量嵌入（embed）到布尔超立方中，同时不改变向量与生成元函数的相对位置
对于向量$\mathbf t\in \mathbb F^{2^\mu-1}$，记一个多线性多项式$t\larr emb(\mathbf t)\in \mathcal F_\mu^{(\leq 1)}$，对于$\forall i\in [2^{\mu}-1]$，满足
- $t(0^\mu)=0$
- $t(g_\mu^{(i)}(1,0^{\mu-1}))=\mathbf t_i$
对于下标向量$\mathbf t$和$t\larr emb(\mathbf t)$，构造预言机$[[t]]$
这里不难理解，由上面的Lemma 1可以得到，$t$将向量$\mathbf t$嵌入到了$B_\mu\backslash \{0^\mu\}$中
前面提到了Lookup的关系为$(\mathbf t;[[f]];(f,addr))$，满足$f(B_\mu)\sube t(B_\mu)\backslash \{0\}$，这里定义一个辅助向量$\mathbf a=(a_1,\dots,a_{2^\mu-1})$，其中$a_i\in \N$表示$\mathbf t_i$出现在$f(B_\mu)$中的次数
由于$\sum a_i=2^\mu$，我们可以定义一个向量$\mathbf h\in \mathbb F^{2^{\mu+1}-1}$，如下
$$ \mathbf h=\big(\underbrace{\mathbf t_1,\dots,\mathbf t_1}_{1+a_1},\mathbf t_2,\dots,\mathbf t_{i-1},\underbrace{\mathbf t_i\dots,\mathbf t_i}_{1+a_i},\mathbf t_{i+1},\dots,\mathbf t_{2^\mu-2},\underbrace{\mathbf t_{2^\mu-1}\dots,\mathbf t_{2^\mu-1}}_{1+a_{2^\mu-1}}\big) $$
然后看一下Lookup协议如何实现
- Prover首先向Verifier发送$\mathbf h$的预言机$[[h]]$，其中$h\larr emb(\mathbf h)$
- 定义两个多项式$g_1=merge(f,t),g_2=merge(f,t_{\Delta_\mu})$，之后对$\big( ([[g_1]],[[g_2]],[[h]],[[h_{\Delta_{\mu+1}}]]);(f,t,h) \big)$运行多集检查协议
- Verifier请求$h(0^{\mu+1})$，并检查相应是否为0
这里看一下协议如何执行的
首先看一下协议的完备性，不失一般性假设$n=2^\mu$，对于查找关系的三元组$(\mathbf t;[[f]];(f,addr))$，定义上述向量$\mathbf h$，这里回顾一下Plookup$[3]$中的一个点：若式1成立，则式2中的两个集合等价
$$ \begin{align} \big\{ [\mathbf f_i,\mathbf f_i] \big\}_{i\in [n]}\cup\big\{ [\mathbf t_i,\mathbf t_{(i\mod(n-1)+1)}] \big\}_{i\in [n-1]}&=\big\{ [\mathbf h_i,\mathbf h_{(i\mod(2n-1)+1)}] \big\}_{i\in [2n-1]} \tag{1}\\ \big\{[f(\mathbf x),f(\mathbf x)]\big\}_{\mathbf x\in B_\mu}\cup \big\{[t(\mathbf x),t_{\Delta_\mu}(\mathbf x)]\big\}_{\mathbf x\in B_\mu\backslash\{0\}}&=\big\{[h(\mathbf x),h_{\Delta_{\mu+1}}(\mathbf x)]\big\}_{\mathbf x\in B_{\mu+1}\backslash\{0\}} \tag{2}\\ \end{align} $$
之后在式2两侧同时加上$[0,0]=[t(0^\mu),t_{\Delta_\mu}(0^\mu)]=[h(\mathbf x),h_{\Delta_{\mu+1}}(\mathbf x)]$，则可以得到
$$ \big\{[f(\mathbf x),f(\mathbf x)]\big\}_{\mathbf x\in B_\mu}\cup \big\{[t(\mathbf x),t_{\Delta_\mu}(\mathbf x)]\big\}_{\mathbf x\in B_\mu}=\big\{[h(\mathbf x),h_{\Delta_{\mu+1}}(\mathbf x)]\big\}_{\mathbf x\in B_{\mu+1}}\tag 3 $$
此时调用多集检查可以通过验证，因此协议的完备性成立
之后看一下知识合理性，记$\mathbf f\in \mathbb F^n$表示$f$在$B_\mu$上的求值，若$(\mathbf t;[[f]])$不满足查表关系，则根据Plonkup中的结论，对于任意的$\mathbf h$，上述式1不成立，则式3也不成立
Batch Opening
本节介绍一下如何通过批处理的方式来证明多个多元多项式求值的正确性
本质上讲，批处理可以将对不同多项式的多次oracle查询简化为对多变量oracle的单次查询
和多项式承诺与Plonk的批处理一样，HyperPlonk也利用了批处理来对揭示求值，Prover只需要计算一个多线性多项式承诺的证明
这里有两个点需要注意
- 在批处理多个多项式时，不要求这些多项式都是相等的，也可以是一个多项式在多个点求值，此时可以视为对同一个多项式进行批处理
- 可以不失一般性假设所有的多项式的变量数量均为$\mu$，如果有多项式$f'$的变量数量不足$\mu$，比如$\mu-1$，此时可以定义$f(Y,X)=Y\cdot f'+(1-Y)\cdot f'$，此时多项式的变量数量为$\mu$
接下来看一下批处理的构造，假设$k$个多项式$\{f_1,\dots,f_k\}$均为多线性多项式（这里可以扩展至多变量多项式），并且不失一般性假设$k=2^l$
批处理需要处理一个集合$Z=\{\mathbf z_i\}_{i\in [k]}\sube \mathbb F^\mu$，且对于所有的$i\in [k]$，均有$f_i(\mathbf z_i)-y_i=0$
不难看出本质上批处理可以用零校验协议来完成，但是由于集合$Z$的表示方式不为布尔超立方，因此不能直接使用前面提到的零校验协议
为了用零校验协议进行处理，这里用到的方式是利用多线性扩展，将每个零约束条件转变为和校验，这样就可以处理布尔超立方了
具体而言，由于$f_i$为多线性的，因此根据多线性扩展的定义，等式$f_i(\mathbf z_i)-y_i=0$可以等价$c_i=0$，其中$c_i$定义如下
$$ c_i=\Big( \sum_{\mathbf b\in B_\mu} f_i(\mathbf b)\cdot eq(\mathbf b,\mathbf z_i) \Big)-y_i $$
不难看出，当且仅当对于所有的$i\in [k]$，多项式$\sum_{i\in [k]}eq(\mathbf Z,\langle i\rangle)\cdot c_i$为零多项式时，有$c_i=0$成立，根据SZ引理，对于随机向量$\mathbf t\larr \mathbb F^l$，有下列等式成立
$$ \sum_{i\in [k]}eq(\mathbf t,\langle i\rangle )\cdot c_i=\sum_{i\in[k]}eq(\mathbf t,\langle i\rangle)\cdot \Big[ \Big(\sum_{\mathbf b\in B_\mu} f_i(\mathbf b)\cdot eq(\mathbf b,\mathbf z_i) \Big) -y_i\Big]=0 \tag 4 $$
接下来需要对式4进行算术运算，使其成为代数公式
对于所有的$(i,\mathbf b)\in [k]\times B_\mu$，记$g_{i,\mathbf b}=eq(\mathbf t,\langle i\rangle)\cdot f_i(\mathbf b)$，对应的多线性扩展记为$\tilde g$，同时记$\tilde{eq}$表示$eq(\mathbf b,\mathbf z_i)$的多线性扩展
令$s=\sum_{i\in[k]}eq(\mathbf t,\langle i \rangle)\cdot y_i$，此时上述式4可以改写为
$$ \sum_{i\in[k],\mathbf b\in B_\mu}\tilde g(\langle i \rangle,\mathbf b)\cdot \tilde{eq}(\langle i \rangle,\mathbf b)=s \tag 5 $$
式5相当于在集合$B_{l+\mu}$上对阶为2的多项式$g^*=\tilde g(\mathbf Y,\mathbf X)\cdot \tilde {eq}(\mathbf Y,\mathbf X)$的和校验协议（注意到$g^*=\tilde g\cdot \tilde{eq}$的阶为2，因此上述和校验协议中无需发送任何单变量预言机）
综上，我们可以得到算法4，如下
这里可以分析一下效率：
- Prover需要对包含$\mu+\log k$个变量的阶为2的多项式执行和校验协议，且$\tilde g,\tilde {eq}$均可在$O(k\cdot 2^\mu)$内构建，因此Prover Time为$O(k\cdot 2^\mu)$
- Verifier在和校验中计算和$s$的开销为$O(k)$，对$eq(\mathbf a_2,\mathbf z_i)$求值的开销为$O(\mu)$，因此总的Verifier Time为$O(k\mu)$
下面介绍一种批处理的优化，可以在特殊情况下具有更高的效率
More Efficient Batching Scheme in a Special Setting
由于部分情况下只需要在多个点对单个多线性多项式进行揭示，因此可以针对性的进行优化
对于只有一个多项式$f$的情况，为了简单起见，假设$\forall i\in[k],y_i=0$，此时可以将式4改写为下列形式
$$ \sum_{i\in[k]}eq(\mathbf t,\langle i\rangle)\cdot \Big(\sum_{\mathbf b\in {B_\mu}} f(\mathbf b)\cdot eq(\mathbf b,\mathbf z_i) \Big)=\sum_{\mathbf b\in {B_\mu}} \Big( \sum_{i\in[k]}eq(t,\langle i\rangle)\cdot eq(\mathbf b,\mathbf z_i) \Big) \tag 6 $$
这里记$d_i=eq(\mathbf t,\langle i\rangle)$，上述等式为集合$B_\mu$上关于多项式$f\cdot \tilde{eq}^*$的和校验协议，其中
$$ \tilde{eq}^*(\mathbf X)=\sum_{i\in[k]}d_i\cdot eq(\mathbf X,\mathbf z_i) $$
此时可以将批处理论证规约至多项式$f$的承诺揭示
如之前介绍的，在和校验协议中，Prover每一轮都需要在$x_i=\{0,1,2\}$上对一个阶为2的多项式$r_i(\mathbf X)$进行求值
$$ r_i(X)=\sum_{\mathbf b\in B_{i-1}}f(\mathbf b,X,\alpha)\cdot \tilde {eq}^*(\mathbf b,X,\alpha) \tag 7 $$
其中$\alpha=(\alpha_{i+1},\dots,\alpha_\mu)$为Verifier每轮的挑战
这里$f(\mathbf b,X,\alpha)$可以通过上一篇博客算法1中计算的表格$f(B_{i-1},\{0,1,2\},\alpha)$得到，由于表格的大小为$O(2^\mu)$，利用表格计算$r_i(x_i)$的开销为$O(k)$，协议共执行$\mu$轮，因此总的开销为$O(2^\mu+k\mu)$
由于$\mathbf z_i$为布尔超立方，根据$\tilde {eq}^*$的定义，有
$$ \begin{aligned} \tilde {eq}^*(\mathbf b,X,\alpha)&=\sum_{j\in[k]}d_i\cdot eq((\mathbf b,X,\alpha),\mathbf z_j)\\ &=\sum_{j\in[k]}d_j\cdot eq(\mathbf b,\mathbf z_j[1..i-1])\cdot eq(X,\mathbf z_j[i])\cdot eq(\alpha,\mathbf Z_j[i+1..]) \end{aligned} $$
上述式子中，至多存在$k$个$\mathbf b$，使得$\tilde {eq}^*(\mathbf b,X,\alpha)$求值非零，因此对于第$l$个向量$c_l=\mathbf z_l[1..i-1](1\leq l\leq k)$，有
$$ \tilde {eq}^*(\mathbf c_l,X,\alpha)=\sum_{j\in[k]}d_j\cdot eq(\mathbf z_l[1..i-1],\mathbf z_j[1..i-1])\cdot eq(X,\mathbf z_j[i])\cdot eq(\alpha,z_j[i+1..]) $$
这里注意到最后一项$eq(\alpha,z_j[i+1..])$的值可以动态计算，第二项$eq(X,\mathbf z_j)$可以在常量时间内计算，而第一项$eq(\mathbf z_l[1..i-1],\mathbf z_j[1..i-1])$只有在两者相等时结果才为1，因此使得$\tilde {eq}^*(\mathbf c_l,X,\alpha)$非零的$k$个值可以在$O(k)$内计算，因此$r_i(x_i)$也可以在$O(k)$内计算
References
$[1]$ Binyi Chen, Benedikt Bünz, Dan Boneh, Zhenfei Zhang:HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates. IACR Cryptol. ePrint Arch. 2022: 1355 (2022)
$[2]$ Multiset checks in PLONK and Plookup - HackMD
$[3]$ Ariel Gabizon, Zachary J. Williamson:plookup: A simplified polynomial protocol for lookup tables. IACR Cryptol. ePrint Arch. 2020: 315 (2020)