本部分中，对于$m\in \Z,i\in [0,2^m)$，记$\langle i\rangle_m=\mathbf v\in B_m$表示整数$i$的二进制表示，对应于一个长度为$m$的向量$\mathbf v$

HyperPlonk

Constraint systems

首先来看一下HyperPlonk的索引关系（indexed relation）

HyperPlonk的公共参数为$gp=(\mathbb F,l,n,l_w,l_q,f)$，其中$\mathbb F$为域，$l=2^\nu$为公共输入长度，$n=2^\mu$为约束数量，$l_w=2^{\nu_w},l_q=2^{\nu_q}$分别表示witness数量和每个约束的选择器数量，$f:\mathbb F^{l_q+l_w}\rarr \mathbb F$为一个阶为$d$的算术映射

HyperPlonk的索引关系定义为$\mathcal R_{PLONK}$，为一个三元组

$$ (\mathsf{i},\mathsf{x} ,\mathsf{w})=((q,\sigma);(p,[[w]]);w) $$

其中

  • $\sigma:B_{\mu+\nu_w}\rarr B_{\mu+\nu_w}$为一个置换
  • $q,p,w$：三个多项式，变量数量分别为$\mu+\nu_q,\mu+\nu,\mu+\nu_w$

$\mathcal R_{PLONK}$满足下列三个条件

  • 导线置换为可满足的：$(\sigma;([[w]],[[w]]);w)$满足置换关系
  • 门约束为可满足的：$(([[\tilde f]]);\tilde f)$满足零校验，其中多项式$\tilde f$定义如下

$$ \tilde f(\mathbf X)=f(q(\langle 0\rangle_{\nu_q},\mathbf X)),\dots,q(\langle l_q-1\rangle_{\nu_q},\mathbf X),w(\langle 0\rangle_{\nu_w},\mathbf X),\dots,w(\langle l_w-1\rangle_{\nu_w},\mathbf X) $$

  • 公共输入与witness一致：公共输入多项式$p$与多项式$w(0^{\mu+\nu_w-\nu},\mathbf X)$一致

State Machines

$\mathcal R_{PLONK}$可以用于对诸如$[2]$的状态机进行建模，这里不再展开介绍，感兴趣可以看原文

主要是懒，不想看

The PolyIOP protocol

介绍一下无需FFT运算的多变量PIOP来证明上述的索引关系

回顾一下之前的系列文章，在$\mathcal R_{PLONK}$中，零校验PIOP协议用于检查自定义的代数门，置换检查协议用于检查拷贝约束，之后通过公共输入多项式和witness多项时间的随机求值来检查其一致性

记$d=deg(f)$表示多项式$f$的阶，对应的协议如下图所示

其中$gp$中的公共参数$l_w,l_q$为常数（$l_w,l_q=O(1)$），上述协议的相关复杂度如下

  • 合理性误差为$O(\frac{2^\mu+d\mu}{|\mathbb F|})$
  • Prover Time为$O(nd\cdot \log^2d)$
  • Verifier Time为$O(\mu+l)$
  • 请求复杂度为$2\mu+4+\log l_w$，其中$2\mu+\log l_w$为请求单变量预言机的复杂度，此外还包含3次多线性预言机请求和1次对$\tilde f$的预言机请求
  • 轮复杂度为$2\mu+1+\nu_w$
  • Prover发送的域元素数量为$2\mu$
  • 证明预言机的大小为$O(n)$
  • witness大小为$n\cdot l_w$

上述协议的完备性和合理性都基于其调用的三个子协议，零知识性下一篇博客介绍（或者看原文的附录A）

HyperPlonk+

介绍一下如何将查找门集成到HyperPlonk的约束系统中，同时介绍一个用于扩展关系的PIOP协议

Constraint systems

HyperPlonk+的索引关系$\mathcal R_{PLONK+}$基于关系$\mathcal R_{PLONK}$，区别在于$\mathcal R_{PLONK+}$采用了一组非代数约束，用于确保与witness相关的函数包含于某个预处理的表中

接下来举个简单的例子：假设与关系$\mathcal R_{PLONK}$相关的电路，扇入为2，具有$n$个加法/乘法门，记第$i$个门的输入分别为$w_1(i),w_2(i)$

对于查找关系，首先需要加强一下约束条件：对于需要进行范围检查的门，其构成一个门的子集，在该子集中的门，要求两条输入线的和在范围$[0,\dots,B)$内

这个约束很容易实现，只需要构造一个预处理表$\mathrm{table}=\{0,\dots,B\}$，然后构造选择器向量$q_{lk}\in \mathbb F^n$，使得对于$\forall i\in[n]$，若第$i$个门需要范围检查，则$q_{lk}(i)=1$，否则为0

此时对应的查找关系为：对于$\forall i\in[n]$，检查$q_{lk}(i)\cdot (w_i(i)+w_2(i))$是否在表$\mathrm{table}$内

这里可以推广一下，将（选择器和witness上的）任意代数函数都可以在表中进行检查，这里构造一个代数函数$f_{lk}$如下，此时约束条件为

$$ f_{lk}(q_{lk}(\langle0 \rangle,\langle i \rangle),\dots,q_{lk}(\langle l_{lk}-1 \rangle,\langle i \rangle),w(\langle0 \rangle,\langle i \rangle),\dots,w(\langle l_w-1 \rangle,\langle i \rangle))\in\mathrm{table} $$

其中$l_{lk}$表示选择器的数量，$l_w$表示witness导线的数量

这里需要注意：$f_{lk}=q_{lk}(i)\cdot (w_i(i)+w_2(i))$是上述约束条件的一个特例

接下来看一下HyperPlonk+索引关系的定义

对于$\mathcal R_{PLONK}$中的公共参数$gp_1=(\mathbb F,l,n,l_w,l_q,f)$，令附加公共参数$gp_2=(l_{lk},f_{lk})$，其中$l_{lk}=2^{\nu_{lk}}$表示查找选择器向量的数量，$f_{lk}:\mathbb F^{l_{lk}+l_w}\rarr \mathbb F$为代数映射，$\mathcal R_{PLONK+}$定义为三元组

$$ (\mathsf{i},\mathsf{x} ,\mathsf{w})=((\mathsf i_1,\mathsf i_2);(p,[[w]]);w) $$

其中$\mathsf i_2=(\mathrm{table}\in \mathbb F^{n-1})$，$q_{lk}$的变量数量为$\mu+\nu_k$

$\mathcal R_{PLONK+}$满足下列两个条件

  • $(\mathsf{i}_1,\mathsf{x} ,\mathsf{w})\in \mathcal R_{PLONK}$
  • 存在$addr:B_\mu\rarr [1,2^\mu)$，满足$(\mathrm{table};[[g]];(g,addr))\in \mathcal R_{LOOKUP}$，其中$g$定义如下

$$ g(\mathbf X)=f_{lk}(q_{lk}(\langle 0 \rangle_{\nu_{lk}},\mathbf X),\dots,q_{lk}(\langle l_{lk}-1 \rangle_{\nu_{lk}},\mathbf X),w(\langle0_{\nu_{w}} \rangle,\mathbf X),\dots,w(\langle l_w-1 \rangle_{\nu_{w}},\mathbf X)) \tag 1 $$

The PolyIOP protocol

上述关系对应的PIOP协议如下图所示

若$l_w,l_q,l_{lk}$为常数，记$d'=\max\big(def(f),def(f_{lk})\big)$，上述协议的相关复杂度如下

  • 合理性误差为$O(\frac{2^\mu+d’\mu}{|\mathbb F|})$
  • Prover Time为$O(nd'\cdot \log^2d')$次域运算
  • Verifier Time为$O(\mu+l)$次域运算
  • 请求复杂度为$3\mu+7+\log l_w$，其中$3\mu+\log l_w$为请求单变量预言机的复杂度，此外还包含5次多线性预言机请求，1次对$\tilde f$的预言机请求和1次对$g$（式1）的请求
  • 轮复杂度为$3\mu+3+\nu_w$
  • Prover发送的域元素数量为$3\mu$
  • 证明预言机的大小为$O(n)$
  • witness大小为$n\cdot l_w$

上述协议的完备性和合理性都基于其调用的三个子协议，零知识性下一篇博客介绍（或者看原文的附录A）

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]$ A. Gabizon and Z. J. Williamson. Proposal: The turbo-plonk program syntax for specifying snark programs. https://docs.zkproof.org/pages/standards/accepted-workshop3/proposal-turbo_plonk.pdf, 2020

‍