Overview
先介绍一下Plonk和HyperPlonk的一些背景
2019年9月，Gabizon、Williamson和Ciobotaru提出了Plonk算法， 一时掀起了学界研究浪潮，以至于部分人将2019年9月称为SNARKtember（SNARK+September的合成词），意思是这一年的九月到11月这段时间内，涌现了大量的SNARK研究方案
后续还有基于Plonk改进的Plonkup，在Plonk中引入了查表的概念，以及后续的一些fflonkup、Caulk/Caulk+等查表算法
首先来回顾一下SNARK的构建过程，现代SNARK的构建方案主要分为两步
- 构建信息论证明系统：以往的诸如Groth16等方案采用PCP，近两年出于效率、通信量等方面考虑，PIOP要比PCP方案更胜一筹
目前可选择的PIOP方案有很多，最经典的是Plonk和Marlin这两个，其他的还有Sonic和Libra等等 - 利用多项式承诺编译上述证明系统：部分文献也将这一步称为密码学编译器，主要目的是实现SNARK中的零知识性，其他的一些性质，如后量子安全，透明性等等性质也都取决于使用的多项式承诺
多项式承诺方案中，KZG10用的是最多的，不仅好用还实用，而且可以批量处理，其他的还有基于IPA的（bulletproof），基于FRI的，还有2020年提出的DARK方案（为KZG10方案添加了透明性）
这两点也是现代SNARK构造的核心，所以在每一个介绍SNARK的视频里面，总是可以在PPT里面看到一个搅拌机（图源$[3]$）
这个搅拌机的意思是：方案的设计者可以选择左边的任意一个PIOP方案和右边任意一个多项式承诺方案，将其组合在一起即可得到SNARK
回顾一下之前介绍的Plonk算法，Plonk的证明长度非常短，也就300-500 Bytes，验证速度很快，而且Plonk有两个最主要的优点
- 支持自定义门（custom gates）：自定义门可以使得Plonk具有比R1CS和QAP更灵活的中间表达方式，只要通过设置合适的向量选择器，就可以在同一个约束条件内表达多个约束条件
- 通用性：这个解决了Groth16特定电路的问题，特定电路意味着需要反复执行setup步骤，而setup又是SNARK方案中开销比较大的步骤，Plonk的通用性只需要执行一次setup即可，大大提高了方案在处理不同电路时的效率
尽管Plonk很快，也很好用，但是Plonk存在一个效率的瓶颈：在处理规模大于$2^{20}$的电路时，效率会急剧下降
因为Plonk中的Prover在生成证明过程中需要用到FFT来计算相关参数，而FFT最快也需要线性对数阶（$O(n\log n)$）的计算开销，因此当电路规模大于$2^{20}$时，FFT会占据Plonk执行时的大部分开销，如果想要进一步优化，则需要考虑抛弃FFT
综上，HyperPlonk来了，HyperPlonk的目的之一就是解决Plonk中采用FFT导致效率下降的问题
HyperPlonk不仅保留了Plonk的灵活性，同时避免了在证明生成过程中的FFT步骤，更重要的是HyperPlonk支持比Plonk更高程度的自定义门，且不会影响证明程序的运行时间，这两种方法都可以显著加快证明器的运行时间
HyperPlonk vs. Plonk：Overview
这里通过回顾一下Plonk方案的方式，来和HyperPlonk做一个对比
Plonk第一步需要将给定的电路转换为一个计算轨迹，如下图所示
此时对应的公共输入$x=\{x_1,x_2\}$，witness为$w=\{w_1\}$，对应的statement为$out=77$
接下来第二步是用单变量多项式表示这个计算轨迹，如下图所示
这里需要利用拉式插值法，将左边的计算轨迹构造成右边的三个单变量多项式$L,R,O$
这一步需要用到FFT或者NTT，即便是使用对FFT友好的域，这一步也需要$O(n\log n)$的计算开销
而且这个步骤的内存开销为$O(n)$，这意味着几乎不可能通过并行的方式来加速这个步骤的计算
因此这个步骤是Plonk在处理大规模电路时的主要开销，导致Plonk难以处理非常大的$n$，也无法适用于需要高度并行的系统中
HyperPlonk的主要思想是利用布尔超立方来代替原本的拉式插值法，如下图所示
注意到右边，把原来的$\{\omega^i\}$替换为了二进制表示，这样一来就不需要像原来一样，在多项式的系数和求值之间进行转换
最大的好处在于：减少了表达计算轨迹所需要的变量数量，观察上面的input和三个计算门，构造对应的单变量多项式一共需要四个变量$\{\omega^0,\omega^1,\omega^2,\omega^3\}$，变量的数量与计算门的数量呈线性关系
而采用布尔超立方的方式，只需要两个二进制位即可表示input和三个计算门，将变量的数量降低至了对数阶
这里引入布尔超立方采用了和Spartan、Quarks相同的思想，只不过前两者均将布尔超立方作用于R1CS，而HyperPlonk将其作用于Plonk的自定义门
之后Plonk的第三步中，需要对计算门进行检查，主要思想是构造一个选择器（Selector），选择器为一个单变量多项式$S(X)$，若$S(\omega^l)=1$，则表示第$l$个计算门为加法门，若$S(\omega^l)=0$，则表示其为乘法门（这里可以参考之前的博客）
因此，对于所有的$y\in\{1,\omega^1,\dots,\omega^{|C|-1}\}$，Plonk的计算门检查为下列等式
$$ S(y)\cdot [L(y+R(y)]+(1-S(y))\cdot [L(y)\cdot R(y)]=O(y) $$
在Plonk中，这一步会被归约为零校验（ZeroCheck），然后进一步归约为系数校验（QuotientCheck），比较复杂
HyperPlonk继续沿用了布尔超立方的思想，将上述单变量多项式$S$修改为多变量$S(\langle l \rangle )$，其中$\langle l \rangle =X_1,\dots,X_n$，此时和原来一样，利用$S$的取值分别代表加法门和乘法门
此时上述集合$\{1,\omega^1,\dots,\omega^{|C|-1}\}$的大小就降低至了对数阶，以上面那个电路为例子的话，集合为$\{00,01,10,11\}$
而且还有一个好处，HyperPlonk在归约到零校验时，无需归约为系数校验，直接归约至和校验
之后Plonk还有一个步骤，称为置换校验，简单来说就是需要确保计算门的输出为另一个计算门的输入，对于上面那个例子，需要确保下面这个图中，颜色相同的部分具有相同的值
Plonk中的做法是利用置换校验，对于置换$\pi$，需要确保置换前后的集合不变，也即$(L,R,O)=\pi(L,R,O)$
总结一下，Plonk方案的总体框架如下图左侧所示，HyperPlonk如右侧所示
重点在于，HyperPlonk将Plonk最底层的系数校验替换为了和校验，这一步很关键，因为系数校验需要用到FFT（或者NTT），而和校验协议可以基于布尔超立方进行，从而消除了对FFT/NTT的依赖，提高了方案在处理大型电路时的效率
Features
High-degree Gates
前面提到了Plonk在检查计算门时的验证等式为
$$ S(y)\cdot [L(y+R(y)]+(1-S(y))\cdot [L(y)\cdot R(y)]=O(y) $$
HyperPlonk对这个验证等式进行了推广，使其可以检验更高次的多项式，比如对于$G(L,R)=L^5+R$，HYperPlonk可以完成如下检查
$$ S(y)\cdot [L(y+R(y)]+(1-S(y))\cdot [G(L(y),R(y))]=O(y) $$
这么做的好处就是可以减少电路或者witness的大小，从而间接提高Prover构造证明的效率
由于Plonk最底层的系数校验的开销很大（需要对一个阶为$O(dn)$的多项式进行系数校验），这个步骤会包含群运算，而且阶越高，意味着需要更大规模的FFT运算
而上一节提到了，HyperPlonk最底层的协议为和校验协议，该协议中主要包含的运算为域运算，而域运算的效率要比群运算高得多，协议执行的轮数也仅与多项式的阶相关，并且可以支持更高阶的多项式
Batch Evaluations
HyperPlonk的另一个特性是实现批处理
举个例子，比如对于$k$个多项式$f_1,\dots,f_k$，每个多项式均包含$\mu$个变量，Prvoer希望证明，对于任意的$i\in [k]$，均有$f_i(z_i)=y_i$成立
为了确保效率，这里有两点基本的要求
- Prvoer Time约等于这$k$个多项式求值的时间复杂度
- 要求Verifier Time、通信量、协议轮数均为对数阶
在Halo$[BDFG20]$方案中也有类似的批处理技术，但是Halo的方案只能针对单变量多项式处理，而HyperPlonk需要在多变量多项式上进行运算，而且Halo的方案的Prover Time为$O(k^2\mu\cdot 2^\mu)$，显然太大了
HyperPlonk将Prover Time优化至了$O(k2^\mu)$。同时通信量为$O(\mu)$，Verifier Time为$O(k\mu)$
接下来看一下如何实现
先考虑最简单的$k=1$的情况，在单变量多项式中，如果说需要验证$f_i(z_i)=y_i$，需要利用到拉氏插值多项式，而HyperPlonk处理的是多变量多项式，对应的方法是多项式的多线性扩展，如上图左侧的表格所示（或者参考之前的博客$[2]$）
此时验证$f_i(z_i)=y_i$，相当于验证下列等式
$$ \sum^{2^\mu}_{j=0}f_i(\langle j\rangle)\cdot eq(\langle j\rangle),z_i)=y_i $$
该等式可以通过和校验协议完成验证，从而将其归约至单点求值
但是上面讨论的是$k=1$的情况，在$k>1$时，则需要用到和校验协议的批处理的特性
对于$k$个多项式，$f_1(z_1)=y_1,\dots,f_k(z_k)=y_k$，可以构造一个由这$k$个多项式线性组合而成的多项式$f^*$，然后再执行和校验协议即可
Lookup on the Boolean Hypercube
查表是一个非常有用的方式，比如说我们希望确保所有输入和输出的值都在范围$[0,2^{16}-1]$内，此时我们可以预计算一个表$\{0,\dots,2^{16}-1\}$，包含所有的$2^{16}$个值，然后证明所有输入输出值均在这个表内即可
查表可能对算术电路不太好用，因为大部分的值都可以通过构造特定的约束条件来完成，不需要查表这个额外的操作
但是在证明包含大量位运算的计算时非常有用，由于算术电路只能处理加法和乘法，这两个运算很难转换为与、或、异或、取反等位运算，而且包含大量位运算的电路也难以在椭圆曲线上进行实例化，比如说证明SHA256的值被正确计算，此时算术电路就很难处理这个问题
此时查表的优势就体现出来了：可以通过预计算一个表，包含所有计算过程中可能的值（就像上面的范围检查一样），然后在构造证明时，证明所有的值都在这个表内即可
这里可以回顾一下Plonk的查表版本Plonkup$[5]$，Plonkup中的预计算的表为$T$，witness为某个单变量多项式$f$，需要证明有$f(H)\sube T(H)$成立，如下图所示
此时通过在$f$上进行拉式插值法，然后证明这些值在对应的表内即可，具体的过程可以看之前介绍Plonkup的博客$[4]$
但是上面这个方式只适用于单变量多项式，对于多变量多项式，需要一些额外的技巧
首先需要在域$\mathbb F_2$上构造一个阶为$\mu$的本原多项式$p_\mu(X)$，此时$\mathbb F_2[X]/p_\mu\cong \mathbb F_{2^\mu}$，且$X$为$\mathbb F_{2^\mu}/\{0\}$的生成元
举个例子，令$p_\mu(X)=X^4+X+1$，对于多项式$b_3X^3+b_2X^2+b_1X+b_0$，记其向量表示$u=(b_3,b_2,b_1,b_0)\in \mathbb F_{2^4}/\{0\}$
由于$X$是生成元，我们可以不断的乘$X$来生成下一个多项式（下一个$u$），不难得到$u$与下一个$u$的关系为$next(u)=(b_2,b_1,b_0\oplus b_3,b_3)$，在经过有限次的乘法之后，我们可以得到$\mathbb F_{2^4}/\{0\}$中的所有元素，如下所示
但是这个过程有几个问题
- $next$在某些维度的开销为二次的
- 多项式$f(next(X))$的阶会非常大，导致难以处理
- 和校验处理上述这个过程的开销会很大
重点来了，为了解决这个问题，方法是在布尔超立方上，利用多线性多项式对$f(next(X))$进行模拟
继续上面那个例子，注意到$next$函数的后两个二进制位均与$b_3$相关，此时我们可以枚举所有可能的$b_3$来模拟$next$的计算过程
具体而言，构造一个多项式$f'$如下
$$ f'(X_3,\dots,X_0)=X_3\cdot f(X_2,X_1,1-X_0,1)+(1-X_3)\cdot f(X_2,X_1,X_0,1) $$
不难看出$f'$与$f(next(X))$是等价的，由于多项式$f'$是多线性的，因此基于该多项式，我们可以构造一个线性时间的Lookup PIOP
小结
介绍了一下HyperPlonk的大致技术路线和关键技术点，下一篇文章介绍具体的技术细节
HyperPlonk系列打算分四（或者五）个部分来写吧，内容有点多
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]$ 多项式扩展与和校验协议 - 三两老友杂的小岛 (snowolf0620.xyz)
$[3]$ zkStudyClub: HyperPlonk (Binyi Chen, Benedikt Bünz) - YouTube
$[4]$ Plookup:A simplified polynomial protocol for lookup tables - 三两老友杂的小岛 (snowolf0620.xyz)
$[5]$ Ariel Gabizon, Zachary J. Williamson:plookup: A simplified polynomial protocol for lookup tables. IACR Cryptol. ePrint Arch. 2020: 315 (2020)