Zero Knowledge PIOPs and zk-SNARKs

介绍一下将多变量和校验PIOP编译为零知识PIOP的编译器，主要思想分为两个部分，首先是对预言多项式进行掩码处理，使其查询结果不会暴露原始多项式的相关信息，其次是要求掩码不会该边原始布尔超立方上的求值，重点在于后者，因为后者不改变分布的特性确保了协议的零知识性

与单变量的PIOP相比，多变量PIOP有一个特殊的点：若请求的点集为高度结构化的，则很难实现零知识性

举个例子，若$f$为2变量的多项式，此时需要查询4个点$\{(r_1,r_1),(r_1,r_2),(r_2,r_1),(r_2,r_2)\}$，此时任意两个点均有一个值相同，敌手可以利用这个点来消除掩码的随机性，从而获得查询结果之间的相关性

因此需要限制查询点集的结构化程度，具体而言，要求查询点集中，所有的点在至少一个维度上的值两两不相同

Definition

这里沿用了$[2]$中PIOP的HVZK的定义，由于和校验PIOP中的Prover也需要发送域元素，因此HyperPlonk中稍微改动了一下$[2]$中的定义，如下

Polynomial Masking

Def 2：若满足下列两个条件，则称随机化算法$\mathrm{msk}$为$(t,C,\mu)$-masking的

  1. 对于$d\in \N$和任意$\mu$变量$d$阶多项式$f$，$f$的掩码多项式$f^*\larr \mathrm{msk}(f,t,C)$不会该边$f$在$B_\mu$上的求值
  2. 对于$d\in \N$，任意$\mu$变量$d$阶多项式$f$和被检验方$C$（checker）所接受的请求列表$\mathbf q=(q_1,\dots,q_t)$，掩码多项式$f^*$在$\mathbf q$上的求值$\big(f^*(q_1),\dots,f^*(q_t) \big)$为$\mathbb F^t$上的均匀分布

这里有一个引理，如下

Lemma 1：对于任意的$\mu,t\in \N,l\in[\mu]$和被$C$所接受的请求列表$\mathbf q=(q_1,\dots,q_t)$，当且仅当对于所有的$q_i=(b_{i,1},\dots,b_{i,\mu})$，有$b_{i,l}\notin \{0,1,b_{1,l},\dots,b_{i-1,l}\}$，存在一个$(t,C_l,\mu)$-掩码算法$\mathrm{msk}(f,t,l)$，对于阶小于$d$的$\mu$变量多项式和$l\in [\mu]$，$deg(f^*)=\max(d,t+1)$

这里可以证明一下

对于多项式$f$，查询上界为$t$，检验方$C_l$，上述掩码算法如下

  • 构造一个单变量多项式$R(X)=\sum_{i=0}^{t-1}c_i\cdot X^i$，其中$c_i\larr \mathbb F$
  • 输出$f^*=f+Z(X_l)\cdot R(X_l)$，其中$Z(X_l)=X_l\cdot (1-X_l)$

首先，显然有$deg(f^*)=\max(d,t+1)$，其次，由于$Z$在$B_\mu$上的求值为0，因此$f^*$也不会改变$f$在$B_\mu$上的求值

之后观察求值结果$\mathbf f^*=\big(f^*(q_1),\dots,f^*(q_t) \big)$，对于$q_i=(b_{i,1},\dots,b_{i,\mu})$，定义$\mathbf R$如下

$$ \mathbf R=\Big(Z(b_{1,l})\cdot R(b_{1,l}),\dots,Z(b_{t,l})\cdot R(b_{t,l})\Big) $$

由于每个查询中，均有$\forall i\in[t] , b_{i,l}\notin\{0,1\}$，因此$z_i=Z(b_{i,l})$为非零值，因此$z_i$可逆

此外由于$R$为随机多项式，$\{b_{1,l},\dots,b_{t,l}\}$互不相同，因此$\{R(b_{1,l}),\dots,R(b_{t,l})\}$满足均匀分布，故$\mathbf R$为均匀随机的

综上，$\mathbf f^*=\mathbf f+\mathbf q$也为均匀随机的，引理证毕

Zero knowledge SumCheck

$[3]$中给出了一个和校验协议的高效编译器，这里沿用了$[3]$中的PIOP构造，如下图所示

协议的零知识性可以参见$[3]$中的定理3，下面介绍一下

$[3]$ Thm 3：对于任意Verifier $\mathcal V^*$，任意$l$变量多项式$f$，变量的阶为$d$，存在一个模拟器$\mathcal S$，模拟器可以访问$H$（如下），则模拟器可以输出零知识和校验协议中步骤1-步骤4的$\mathcal V^*$的视角

$$ H=\sum_{x_1,\dots,x_l\in\{0,1\}}f(x_1,\dots,x_l) $$

这里需要$[3]$中的零知识和校验协议的相关知识，打算后续博客补充

Zero knowledge compilation for SumCheck-based PIOPs

介绍一下和校验PIOP的一般形式，HyperPlonk中用到的多变量PIOP均适用此类形式，如下图所示

这里有几个点需要关注

  • 步骤2中Prover需要发送多项式$g_1,\dots g_c$，这里可以用一个阶大于1的预言机$f=h(g_1,\dots,g_c)$来代替
  • 对于同一轮中Prover需要发送多个多线性预言机的情况，可以使用之前提到的$merge$函数将这些多项式整合为一个多项式
  • HyperPlonk中不同形式的PIOP最终均可规约为和校验PIOP

综上，上述和校验PIOP的一般形式可用于HyperPlonk中的多变量PIOP

接下来看一下如何将任意基于和校验PIOP转换为零知识PIOP

记$(\{p_i\}_{i\in[0,k_1]},\{f_i\}_{i\in[k_2]})$表示上述协议用到的多项式，对于所有的$i\in[k_1]$，令$t_i\in\N$表示$p_i$出现在和校验协议中的多项式$\{f_i\}_{i\in[k_2]}$的次数，记$t^*=max\{t_i\}$

（看不懂了，暂时放一下）

zk-SNARKs from PIOPs

上一小节提到了，Prover所发送的掩码多项式为$f^*=f+Z\cdot R$，根据$[4]$中的定理10，可以通过任意假加法和spanning来为$f^*$构造一个满足隐藏性和求值零知识性的多项式承诺方案

具体而言，$f^*$的承诺值为$(C_1,C_2)\in \mathbb G$，其中$C_1$为$f$的承诺值，$C_2$为$Z\cdot R$的承诺值，之后利用$[4]$中的ZK变换即可

Open Problems

HyperPlonk通过引入布尔超立方的方式，移除了Plonk中拉式插值法对FFT的依赖，同时还提出了Orion+多线性承诺方案

但是HyperPlonk仍然存在几个问题

Higher degree shifts

之前提到了，通过构造一个本原多项式来不断地生成布尔超立方的下一个值（$next$函数），这个方法也是HyperPlonk查找论证的核心思想之一

但是Halo2算法的部分版本中，证明系统可能需要访问比上一步中更多的状态，此时需要更多的转换

解决这一问题的方式是多次组合$next$函数来完成，但是这也会导致Verifier Time指数级增长，因此高阶的$next$函数效率仍然是个问题

Better codes and hash functions for Orion+

Orion+在较小多项式上的实用性受到递归使用的限制，只有在处理较大的（估计超过24个变量）多线性多项式时，递归电路的大小才有可能超过原始多项式的大小

改进的关键点在于设计一个具有更好距离的线性码和对电路更加友好的Hash函数

Automatic custom gate design

HyperPlonk+在处理高阶自定义门时具有不错的效率

然而，目前为特定应用设计合适的自定义门的任务仍然保留给电路的设计者，对于任意给定的应用，需要有一种更具原则性的方法来自动化和优化自定义门的设计

Linear-time permutation argument for small fields

之前提到了一个在小的域上的置换论证，但是这个论证的Prover Time为拟线性阶的

因此下一步研究的关键点在于：是否存在合理性最优的置换论证或多集论证，其Prover Time为线性阶

‍

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]$ Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely, Nicholas P. Ward:Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS. EUROCRYPT (1) 2020: 738-768

$[3]$ Tiancheng Xie, Jiaheng Zhang, Yupeng Zhang, Charalampos Papamanthou, Dawn Song:Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation. CRYPTO (3) 2019: 733-764

$[4]$ Dan Boneh, Justin Drake, Ben Fisch, Ariel Gabizon:Halo Infinite: Proof-Carrying Data from Additive Polynomial Commitments. CRYPTO (1) 2021: 649-680