本部分介绍一下HyperPlonk的一些技术细节

Notation

首先看一下需要用到的符号与记法

  • $\lambda$：安全参数
  • $[n]$：表示正整数集合$\{1,\dots,n\}$
  • $[a,b)$：表示左闭右开集合$\{a,a+1,\dots,b-1\}$
  • $\langle i \rangle_m$：对于$i\in [0,2^m)$，$\langle i \rangle_m$用于将$i$表示为长度为$m$的二进制串

这里介绍两个本文的核心概念，第一个是多项式IOP（Poly. IOP），SNARK方案基于信息论证明系统构建，之后再利用密码学原语编译成SNARK，近年来的SNARK方案有不少都是基于PIOP构建的，下面介绍一下PIOP的概念

PIOP是一个关于多项式预言关系$\mathcal R=\{(\mathbf i,\mathbf x;\mathbf w )\}$的公共掷币交互式证明，关系为预言关系，包含了$\mathbb F$上的$\mu$元多项式

预言机定义了$\mu$，以及各个变量的阶，预言机可在任意点$\mathbb F^\mu$上进行查询并在这些点上对多项式进行求值

在PIOP的每一轮中，Prover发送一个多变量多项式的预言机，Verifier返回一个随机挑战

本文将多项式$f$的预言记为$[[f]]$

利用PIOP编译器，可以将上面的交互式预言机证明转换为交互式知识论证，该编译过程采用多项式承诺来代替PIOP中的预言机

在编译过后的论证中，Verifier的每个查询都会被替换为在点$z$处调用$Eval$协议，此时当所有的$Eval$协议调用均输出1时，论证中的Verifier才会接受

第二个概念是虚拟预言机（virtual oracles）与承诺，对于给定的多个多项式预言机，可以将这些多项式的函数构建成一个虚拟预言机

例如，对于给定的$k$个多项式的预言机$\{[[f_1]],\dots,[[f_k]]\}$，可以构造一个函数$g$，对应的虚拟预言机为$g(\{[[f_1]],\dots,[[f_k]]\})$

此时如果希望在点$\mathbf x$处求值，只需要对于所有的$i\in [k]$，计算$y_i=f_i(\mathbf x)$，然后输出$g(y_1,\dots,y_k)$即可

对于给定的多项式的承诺，也可以反过来以相同的方式构造这些多项式的函数的虚拟承诺

如果函数$g$为加性函数，且多项式承诺满足加法同态，则可以利用同态的性质完成特定的求职运算

比如对于两个多项式$f,g$的承诺$C_f,C_g$，如果我们希望构建对$(1-Y)\cdot f+Y\cdot g$的承诺，此时对应的求值点为$(y,\mathbf x)$，对应的求值为$(1-y)\cdot C_f+y\cdot C_g$

HyperPlonk toolbox

本节简单介绍一下各个PIOP协议的作用，原理，以及如何一步步将其规约至最底层的和校验协议

协议介绍与分析中省略了合理性误差、协议效率与相关证明，具体可以参考原文

Sumcheck Protocol

首先介绍一些多变量多项式相关的概念

  • $B_\mu=\{0,1\}^\mu \sube \mathbb F^\mu$：表示$\mu$阶的布尔超立方
  • $\mathcal F_\mu^{<d}$：表示一个多变量多项式$\mathbb F[X_1,\dots,X_\mu]$，其中每个变量的阶均小于$d$
  • $\delta ^{d,\mu}_{check}$：表示PIOP的合理性误差，其中$ckech\in \{sum,zero,prod,mset,perm,lkup\}$

这里有一点要求：每个多项式$\mathcal F_\mu^{<d}$均可以被表示为一个由参数$c=O(1)$确定的虚拟预言机，也即$f(\mathbf X)=g(h_1(\mathbf X),\dots,h_c(\mathbf X))$，其中$h_i\in f(\mathbf X)=g,i\in[c]$，$g$为包含$c$个变量的多项式，阶为$d$

然后定义一个函数$merge(f,g)$如下

$$ \begin{aligned} merge(f,g)&=h(\mathbf X_0,\dots,\mathbf X_\mu)\\ &=(1-\mathbf X_0)\cdot f(\mathbf X_1\dots,\mathbf X_\mu)+\mathbf X_0\cdot g(\mathbf X_1\dots,\mathbf X_\mu) \end{aligned} $$

此时有$h(0,\mathbf X)=f(\mathbf X),h(1,\mathbf X)=g(\mathbf X)$

接下来回顾一下和校验协议，在和校验协议中，双方校验一个包含$\mu$个变量的$d$阶多项式$f$，满足$\sum_{b\in B_\mu}f(b)=v$，经典的和校验协议可以分为两个部分

  • 对于$i=\mu,\mu-1,\dots,1$，Prover计算多项式$r_i(X)=\sum_{b\in B_{i-1}}f(b,X,\alpha_{i+1},\dots,\alpha_\mu)$，并将对应的预言机$[[r_i]]$发送给Verifier，这里$r_i$是一个阶至多为$d$的单变量多项式
  • 对于每一个$r_i$，Verifier验证是否有$v=r_i(0)+r_i(1)$，若等式成立，则选择随机数$\alpha_i\larr \mathbb F$并发送给Prover，同时令$v=r_i(\alpha_i)$

根据本文的定义，不难得出和校验协议的的合理性误差为$\delta^{d,\mu}_{sum}=d\mu/|\mathbb F|$

注意到标准的和校验协议需要在每一轮中发送一个多项式预言机，这里本文做一个小的变体，在每一轮中不发送多项式，而是向预言机发送$r_i$

这么做不仅不会改变协议的合理性错误（因为合理性错误仍然与每一轮发送的单变量多项式的阶相关），而且这样可以减少Verifier的复杂度和双方的通信开销，尤其是在多项式$r$的阶数很大时，可以显著减少通信量和Verifier开销

不过这样一个小的变体需要Verifier在三个点$\{0,1,\alpha_i\}$对多项式$r_i$求值，这样一来Prover不仅需要发送$r_i(0)$，还需要发送一个阶数更低的多项式（阶为$d-2$），如下

$$ r'_i(X)=\frac{r_i(X)-(1-X)\cdot r_i(0)-X\cdot r_i(1)}{X\cdot (1-X)} $$

此时Verifier计算下列两项

$$ \begin{aligned} r_i(1)&\larr v-r_i(0)\\ r_i(\alpha_i)&\larr r'_i(\alpha)\cdot (1-\alpha_i)\cdot \alpha_i+(1-\alpha_i)\cdot r_i(0)+\alpha_i\cdot r_i(1) \end{aligned} $$

这样一来，改进版的和校验协议每轮中只需要一次对预言机$r'_i$的请求$\alpha_i$，同时每轮的通信开销也只有一个域元素

基于上述变体，介绍一下高阶多项式的和校验协议，考虑一个多变量多项式$f(\mathbf X)=h(g_1(\mathbf X),\dots,g_c(\mathbf X))$，$h$的阶为$d$，且可以通过具有$O(d)$个门的算术电路进行求值

在和校验协议中，Prover每轮需要基于Verifier之前的随机挑战，计算一个单变量多项式$r_i(X)$，这里介绍一种方式，通过引入动态规划的思想来对协议进行优化

首先算法会输入需要进行校验的多项式$f$，以及每轮中需要用到的随机挑战$\{\alpha_1,\dots,\alpha_\mu\}$，算法输出每一轮的多项式$\{r_1,\dots,r_\mu\}$​

这样一来，和校验协议的Prover可以与协议并行运行，只需要将计算好的$r_i$作为轮消息即可，计算轮多项式的协议如下图所示

这里简单看一下，首先为所有的多项式$g_j$构建一个表$A_j:\{0,1\}^\mu\rarr \mathbb F$，该表包含了$B_\mu$中所有需要求值的点

然后协议进行这样一个递归：对于所有的$b\in B_{\mu-1},j\in [c]$，定义多项式$r^{(j,b)}(X)=(1-X)\cdot A_j[b,0]+X\cdot A_j[b,1]$，然后利用算法2（下一张图）中的方式计算$r_i(X)=\sum_{b\in B_{i-1}} r_b(X)$，将$r_i(X)$发送给Verifier，同时Verifier需要返回一个随机挑战$\alpha_i$

之后Prover对所有的$b\in B_{i-1}$，令$A_j[b]=r^{(j,b)}(\alpha_i)$

这里有一个点：算法的第4~5行需要通过插值法计算，每个多项式插值需要$d$步，$c$个多项式就是$c\cdot d$步，之后还需要在包含$O(d)$个门的电路中对$d$个输入进行求值，开销为$O(d^2)$

假设$c\approx d$，则计算$r^{(b)}$的开销为$O(d^2)$，算法1的总体开销为$O(2^\mu\cdot d^2)$，有点慢，这里可以针对特定的低深度电路（比如$h=\prod_c r_c(\mathbf X)$），将算法的开销优化至$O(2^\mu\cdot d\log ^2d)$

优化的核心思想为：如果使用快速多项式乘法，则可以以符号化的方式对$h$进行求值，而非在$d$个点进行求值，这样会更快

然后先介绍一下算法2，该算法用于计算$h(X)=\prod^d_{j=1}r_j(X)$，算法2可以扩展更复杂、深度更小的电路，算法2流程如下图所示（这里不失一般性假设$d$为2的幂）

和校验协议还有一个特点，可以进行批处理，比如两个和校验的实例$(s,[[f]]),(s',[[g]])$，可以让Verifier引入一个随机性$\alpha$，构造一个随机的线性组合$(s+\alpha\cdot s',[[f]]+\alpha\cdot [[g]])$来完成批处理（3个或以上类似）

ZeroCheck PIOP

Zerocheck协议用于验证一个多元多项式在布尔超立方上的任意点均为零

首先给出零校验的定义，定义为一个二元组$(\mathbf x,\mathbf w)=([[f]],f)$，其中$f$的阶小于$d$，且满足对于所有的$\mathbf x\in B_\mu$，均有$f(\mathbf x)=0$

这里HyperPlonk利用了Spartan协议来讲Zerocheck协议规约至和校验协议，具体如下

  • 首先Verifier向Prover发送一个随机向量$r\larr \mathbb F^\mu$
  • 然后对$f$进行多项式扩展，得到$\hat f(\mathbf X)=f(\mathbf X)\cdot eq(\mathbf X,r)$
  • 对$((0,[[\hat f]]);\hat f)$执行和校验协议，当且仅当和校验协议通过时，Zerocheck协议通过

注意到Zerocheck基于和校验协议，因此Zerocheck也具备和校验协议的批处理性质，也是通过引入随机性来进行批处理

ProductCheck PIOP

乘积检验协议ProductCheck用于检查有理多项式在布尔超立方上的求值为某个声明的值$s$

此类PIOP利用了Quark协议中的思想，并基于Zerocheck协议构建

先看一下Prodcheck的定义：给定二元组$(\mathbf x,\mathbf w)=((s,[[f_1]],[[f_2]]);f_1,f_2)$，其中$f_1,f_2$均为阶小于$d$的多项式，对于由$f_1,f_2$定义的有理函数$f'=f_1/f_2$，满足下列两个条件

  • $\forall b\in B_\mu,f(b)\neq 0$
  • $\prod_{x\in B_\mu} f'(\mathbf x)=s$

若$f_2$为常函数（$f_2=c$），则直接将二元组记为$(\mathbf x,\mathbf w)=(s,[[f]];f)$

Quark协议中构造了一个包含$\mu+1$个变量的Zerocheck协议来实现Productcheck，对于给定的二元组$(\mathbf x,\mathbf w)$，协议执行如下

  • Prover发送一个预言机$\tilde v\in \mathcal F^{\leq 1}_{\mu+1}$，对于所有的$\mathbf x\in B_\mu$，满足

$$ \begin{aligned} \tilde v(0,\mathbf x)&=f'(\mathbf x)\\ \tilde v(1,\mathbf x)&=\tilde v(\mathbf x,0)\cdot \tilde v(\mathbf x,1) \end{aligned} $$

  • 定义$\hat h= merge(\hat f,\hat g)\in \mathcal F^{\leq \max(2,d+1)}_{\mu+1}$如下

$$ \begin{aligned} \hat f(\mathbf X)&=\tilde v(1,\mathbf X)-\tilde v(\mathbf X,0)\cdot \tilde v(\mathbf X,1)\\ \hat g(\mathbf X)&=f_2(\mathbf X)\cdot \tilde v(0,\mathbf X)-f_1(\mathbf X) \end{aligned} $$

然后基于$([[\hat h]],\hat h)$执行Zerocheck协议

  • Verifier在点$(1,\dots,1,0)$处请求$[[\tilde v]]$，并检查结果是否为$s$

MultisetCheck PIOP

MultisetCheck协议用于检查两个多变量集合是否相等

Gabizon在其博客中提出了此类检查的单变量版本$[2]$

里面的主要思想和Plonk系列博客中介绍的随机洗牌检查差不多

先看一下多集检查的定义：对于$k\geq 1$，多集检查为下列二元组上的关系

$$ (\mathbf x,\mathbf w)=\big( ([[f_1]],\dots,[[f_k]],[[g_1]],\dots,[[g_k]]) ;(f_1,\dots,f_k,g_1,\dots,g_k) \big) $$

其中$f_i,g_i\in \mathcal F^{\leq d}_{\mu}$，满足下列关系

$$ \big\{ f_{\mathbf x}=[f_1(\mathbf x),\dots,f_k(\mathbf x)] \big\}_{\mathbf x\in B_\mu}=\big\{ g_{\mathbf x}=[g_1(\mathbf x),\dots,g_k(\mathbf x)] \big\}_{\mathbf x\in B_\mu} $$

多集检查协议可以通过上面的乘积检查协议构建，这里以$k=1$举例，给定$(([[f]],[[g]]);(f,g))$，协议流程如下

  • Verifier向Prover发送一个随机挑战$r\larr \mathbb F$
  • 双方计算$f'=r+f,g'=r+g$，并对$((1,[[f']],[[g']]);f',g')$运行乘积检查协议

Permutation PIOP

Permutation协议用于检查两个多变量多项式$f,g$在布尔超立方上的求值结果互为置换，置换检查是HyperPlonk协议的核心协议

首先看一下置换检查的定义：置换检查对应于一个三元组$(\mathbf i;\mathbf x;\mathbf w)=(\sigma;([[f]],[[g]]);(f,g))$，其中置换$\sigma :B_\mu\rarr B_\mu$为某个预定义的置换，满足$\forall \mathbf x\in B_\mu ,g(\mathbf x)=f(\sigma(\mathbf x))$

还是上面那位Gabizon，给出了置换论证的单变量版本，本文将其扩展到多变量的PolyIOP

本文的多变量置换检查协议基于上面的多集检查协议，置换检查协议中首先需要由索引器（indexer）生成两个预言机$[[s_{id}]],[[s_\sigma]]$，其中$s_{id}\in \mathcal F_{\mu}^{(\leq 1)}$用于将每个$\mathbf x\in B_\mu$映射到$[\mathbf x]=\sum^\mu_{i=1}\mathbf x_i\cdot 2^{i-1}$，$s_\sigma\in \mathcal F_{\mu}^{(\leq 1)}$将每个$\mathbf x\in B_\mu$映射到$[\sigma(\mathbf x)]$

之后置换检查在下列实例上运行多集检查协议

$$ \big( ([[s_{id}]],[[f]],[[s_\sigma]],[[g]]);(s_{id},f,s_\sigma,g) \big) $$

Another permutation PIOP for small fields

这里介绍一个针对于较小的域的置换检查，与上面那个置换检查不同，小的域上的置换检查直接基于和校验协议构建，不需要这么多中间的协议归约，且可以将此类置换检查协议用于多项式大小的域

但是此类PIOP协议中需要将置换分解为$\mu$个多线性多项式，因此Prover Time是拟线性的，而非线性的

这里的小域上的置换检查和后面的批量检查的思想类似：对于给定的置换$\sigma$，利用多线性扩展，将在给定点$b'\in B_\mu$处检查等式$f(b')=g(\sigma(b'))$规约至和校验，然后利对所有的$b'$执行zero-check检查，来证明$b'\in B_\mu$（根据前面介绍的zero-check，这一步也可以规约至和校验）

总结一下，上述过程包含两个和校验，因此总的变量数量为$2\mu$，阶为$\mu+1$，但是直接执行这个和校验协议需要的时间开销为$2^\mu$的平方阶，下面介绍一种方式来减少开销

首先介绍原始置换$\sigma$的多线性版本的置换$\tilde \sigma:\mathbb F^\mu\rarr \mathbb F^\mu$，如下

$$ \tilde \sigma=(\sigma_1(\mathbf X),\dots,\sigma_\mu(\mathbf X)) $$

其中$\sigma_i$为$\sigma$中第$i$个二进制位的多线性扩展，注意到由于$\sigma_i(\mathbf x)\in \{0,1\}$，因此可以将置换关系改写为多项式等式的zero-check关系，如下

$$ \forall \mathbf x\in B_\mu,f(\tilde \sigma(\mathbf x))-g(\mathbf x)=0 $$

然后再对$f(\tilde \sigma(\mathbf x))-g(\mathbf x)$进行多线性扩展，则上述关系变为下列关系

$$ \forall \mathbf x\in B_\mu,\sum_{\mathbf y\in B_\mu}\big(f(\mathbf y)\cdot eq(\tilde \sigma(\mathbf x,\mathbf y)-g(\mathbf y)\cdot eq(\mathbf x,\mathbf y)\big)=0 $$

最后再将这个zero-check规约至和校验协议，对于一个长度为$\mu$的随机挑战向量$\mathbf t$，有

$$ \sum_{\mathbf x\in B_\mu} eq(\mathbf t,\mathbf x)\cdot \sum_{\mathbf y\in B_\mu}\big(f(\mathbf y)\cdot eq(\tilde \sigma(\mathbf x),\mathbf y)-g(\mathbf y)\cdot eq(\mathbf x,\mathbf y)\big)=0 $$

但是这个和校验协议有$2\mu$个变量，运行时间会爆炸，为了降低运行时间，可以利用置换的逆置换，也即$\sigma^{-1}(\sigma(\mathbf x))=\mathbf x$，这里对应的多线性版本逆置换记为$\tilde \sigma^{-1}$

基于这个逆置换，可以将上述的和校验协议改写为

$$ \sum_{\mathbf x\in B_\mu} eq(\mathbf t,\mathbf x)\cdot \sum_{\mathbf y\in B_\mu}\big(f(\mathbf y)\cdot eq(\mathbf x,\tilde \sigma^{-1}(\mathbf y))-g(\mathbf y)\cdot eq(\mathbf x,\mathbf y)\big)=0 \tag a $$

此时若有$\mathbf x=\sigma^{-1}(\mathbf y)$，则求和结果为$f(\mathbf y)$，若$\mathbf x=\mathbf y$，则有$f(\sigma(\mathbf x))=-g(\mathbf x)$，否则为0，由于所有的求和均在布尔超立方上完成，且$\sigma$为$B_\mu$的一个置换，因此式a等价于$\sum_{\mathbf x\in B_\mu}eq(\mathbf t,\mathbf x)\cdot (f(\sigma(\mathbf x)-g(\mathbf x ))$

此时Prover可以将$\tilde \sigma^{-1}$作为前$\mu$轮的置换来高效执行式1中的和校验协议，后$\mu$轮协议中的$\mathbf x$会被替换为Verifier的随机挑战$\alpha_1,\dots,\alpha_\mu$，此时可以将$\tilde \sigma^{-1}$视为一系列的多线性函数

总结一下，上面那堆废话可以总结为下列的算法3

小结

本部分先介绍HyperPlonk底层的和校验、零校验、多集检查和置换检查协议

下一篇介绍HyperPlonk+的核心协议：Lookup PIOP，以及相关的批处理方式

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)