Sangria借鉴了Nova的思想，为Plonk的变体构建了一个折叠方案

此外Sangria还提出了松弛的Plonk，可适用于阶为2的自定义门和更高门数的电路

Preliminaries

回顾一下Plonk的计算，其可以被表示为一个$n+s-1$行，3列的矩阵$M$，其中$n$表示公共输入的数量，$s$表示电路中门的数量

Plonk中的公共输入记为$X=(x_a,x_b,x_c)$，对应的witness为$W=(w_a,w_b,w_c)$，Plonk的约束条件记为$(\mathcal Q,\mathcal S)$，$\mathcal Q$表示自定义门约束，$\mathcal S$表示拷贝约束

此外，本文还需要一个满足隐藏性、绑定性和加法同态的承诺方案，记为$\mathrm{Com}$，对于向量$\mathbf a$和随机性$r$，其承诺记为$\bar A=\mathrm{Com}(pp_C,\mathbf a;r)$

Sangria:A folding scheme for the PLONK arithmetization

主要思路和Nova差不多，包含下列三个步骤

  • 通过一个随机性，构造instance-witness对的随机线性组合来完成折叠
  • 交叉项通过错误向量$e$和比例系数来吸收
  • 对松弛向量和witness作用加法同态承诺

Relaxed Plonk Gate

对于标量$u\in \mathbb F$和错误向量$\mathbf e\in \mathbb F^{n+s-1}$，本文定义松弛的Plonk门约束等式如下（松弛Plonk中的拷贝约束与原版Plonk一致）

$$ C'_{\mathcal Q,i}(\mathbf a,\mathbf b,\mathbf c,u,\mathbf e)=u[(\mathbf q_L)_i\mathbf a_i+(\mathbf q_R)_i\mathbf b_i+(\mathbf q_O)_i\mathbf c_i]+(\mathbf q_M)_i\mathbf a_i\mathbf b_i+u^2(\mathbf q_C)_i+\mathbf e_i $$

这里将上述松弛Plonk记为五元组$(\mathbf a,\mathbf b,\mathbf c,u,\mathbf e)$

对于Plonk的instance-witness对$(X,W)$，对应的松弛的Plonk的instance-witness对记为$(U,W)$，如下

$$ \begin{aligned} U&=(X,u,\overline {W_a},\overline {W_b},\overline {W_c},\overline E)\\ W&=(W,\mathbf e,r_a,r_b,r_c,r_e) \end{aligned} $$

其中$\overline {W_a}=\mathrm{Com}(pp_W,\mathbf w_a;r_a)$，$\overline {W_b},\overline {W_c},\overline {E}$同理

这里和Nova一样，松弛的Plonk可以和原版的Plonk互相转换，令$u=1,\mathbf e=\vec 0$就是原版的Plonk

Folding Scheme for Relaxed Plonk

这里和Nova一样，折叠方案包含四个算法$\mathcal G,\mathcal K,\mathcal P,\mathcal V$

  • $\mathcal G$：输出公共参数$pp$，包含大小参数$n,s$和两个用于承诺的参数$pp_W,pp_E$
  • $\mathcal K$：输出$pk=(pp,vk,(\mathcal Q,\mathcal S)),vk=\bot$

方案中Verifier可以知道验证密钥$vk$和两个松弛Plonk的实例，记为$(X',u',\overline {W_a'},\overline {W_b'},\overline {W_c'},\overline {E'}),(X'',u'',\overline {W_a''},\overline {W_b''},\overline {W_c''},\overline {E''})$，Prover可以知道$pk$和这两个实例对应的witness，记为$(W',\mathbf e',r_a',r_b',r_c',r_e'),(W,\mathbf e'',r_a'',r_b'',r_c'',r_e'')$

折叠的过程和Nova类似，首先Prover选择随机值$r_t$，计算$\overline T=\mathrm{Com}(pp_E,\mathbf t;r_t)$，其中$\mathbf t$如下

$$ \begin{aligned} \mathbf t=&u''(\mathbf q_L\circ \mathbf a'+\mathbf q_R\circ \mathbf b'+\mathbf q_O\circ \mathbf c')+u''(\mathbf q_L\circ \mathbf a''+\mathbf q_R\circ \mathbf b''+\mathbf q_O\circ \mathbf c'')\\ &+\mathbf q_M\circ (\mathbf a'\circ \mathbf b''+\mathbf a''\circ \mathbf b')\\ &+2u'u''\mathbf q_C \end{aligned} $$

之后Verifier选择随机数$r$发送给Prover，双方输出折叠后的实例$U=(X,u,\overline {W_a},\overline {W_b},\overline {W_c},\overline E)$如下

$$ \begin{aligned} X&=X'+rX''\\ u&=u'+ru''\\ \overline{W_a}&=\overline{W_a'}+r\overline{W_a''}\\ \overline{W_b}&=\overline{W_b'}+r\overline{W_b''}\\ \overline{W_c}&=\overline{W_c'}+r\overline{W_c''}\\ \overline{E}&=\overline{E'}-r\overline T+r^2\overline{E''} \end{aligned} $$

Prover输出对应的witness $(W,\mathbf e,r_a,r_b,r_c,r_e)$如下

$$ \begin{aligned} W&=W'+rW'\\ r_a&=r_a'+r\cdot r_a''\\ r_b&=r_b'+r\cdot r_b''\\ r_c&=r_c'+r\cdot r_c''\\ \mathbf e&=\mathbf e'-r\mathbf t+r^2\mathbf e''\\ r_e&=r_e'-r\cdot r_t+r^2\cdot r_e'' \end{aligned} $$

方案满足完美完备性和知识合理性，证明过程和Nova中的类似，这里不再展开

Degree 2 Custom Gates

阶为2的自定义门及其选择器向量可以表示为下列形式

$$ G_i(\mathbf a,\mathbf b,\mathbf c)=(\mathbf q_G)_i\cdot g(\mathbf a_i,\mathbf b_i,\mathbf c_i) $$

如果我们需要对此类自定义门进行折叠，则可以将$g$展开，写为多个单项式的和，这里记$g_C,g_1,g_2$分别表示常数多项式、阶为1和阶为2的多项式，此时之前的松弛约束等式（式1）可以改写为下列形式

$$ \begin{aligned} C'_{\mathcal Q,i}(\mathbf a,\mathbf b,\mathbf c,u,\mathbf e)=&u[(\mathbf q_L)_i\mathbf a_i+(\mathbf q_R)_i\mathbf b_i+(\mathbf q_O)_i\mathbf c_i+(\mathbf q_G)_i\cdot g_1(\mathbf a_i,\mathbf b_i,\mathbf c_i)]\\ &+(\mathbf q_M)_i\mathbf a_i\mathbf b_i+(\mathbf q_G)_i\cdot g_2(\mathbf a_i,\mathbf b_i,\mathbf c_i)+u^2(\mathbf q_C)_i+u^2\cdot (\mathbf q_G)_i\cdot g_C+\mathbf e_i \end{aligned} $$

此时和松弛的Plonk一样，通过随机性来完成折叠，不过向量$\mathbf t$需要吸收下列这些交叉项

$$ \begin{aligned} &(u'+ru'')\cdot [(\mathbf q_L)_i (\mathbf a_i'+r\mathbf a_i'')+(\mathbf q_R)_i (\mathbf b_i'+r\mathbf b_i''+(\mathbf q_O)_i (\mathbf c_i'+r\mathbf c_i''+(\mathbf q_G)_i\cdot g_1((\mathbf a_i'+r\mathbf a_i''), (\mathbf b_i'+r\mathbf b_i''), (\mathbf c_i'+r\mathbf c_i''))]\\ & (\mathbf q_M)_i\cdot (\mathbf a_i'+r\mathbf a_i'')\cdot (\mathbf b_i'+r\mathbf b_i'')\\ & (\mathbf q_G)_i\cdot g_2[ (\mathbf a_i'+r\mathbf a_i''), (\mathbf b_i'+r\mathbf b_i''), (\mathbf c_i'+r\mathbf c_i'')]\\ &(u'+ru'')^2(\mathbf q_C)_i\\ &(u'+ru'')^2\cdot (\mathbf q_G)_i\cdot g_C \end{aligned} $$

Future Works

Succinct IVC using a zkSNARK for Sangria

Nova的研究结果表明，折叠方案可用于IVC，但是这样得到的IVC不具备简洁性和零知识性，为了实现这两个性质，因此必须松弛算术化，设计一个zkSNARK

未来的研究方向之一是将Sangria的执行轨迹转换为Plonkish的执行轨迹，并为松弛向量在矩阵中添加一个额外的witness列，或者通过修改以前的IOP，添加相关的$u,\mathbf e$来实现交叉项的消除

Lower Recursion Overhead

目前折叠方案中，Verifier基于witness列中的一个承诺来完成验证，如果将witness矩阵展开成一个列向量，则Verifier验证时就可以只采用一个承诺即可（Nova就这么做的）

但是这么做会导致$pp_W$的长度变长三倍，还需要考虑Plonk IOP中队witness列的承诺问题，未来研究需要解决

Higher Degree Custom Gates

和上面介绍的差不多，高阶自定义门可以基于随机线性组合的折叠策略实现

这里记约束中出现的最高阶为$d$，大致思路如下

  1. 将未松弛的约束等式$C_{\mathcal Q,i}$表示为多个单项式的和
  2. 利用松弛因子$u$的幂，将$C_{\mathcal Q,i}$表示为齐次的$d$阶多项式
  3. 加入误差向量$\mathbf e$，用于吸收交叉项（此时误差项中包含$r$的$1\sim d-1$的幂），可以用$d-1$个向量$\mathbf t_1,\dots,\mathbf t_{d-1}$来表示误差向量$\mathbf e$

$$ \mathbf e=\mathbf e'-\sum^{d-1}_{k=1}r^k\cdot \mathbf t_k $$

  1. 按照之前的方式进行折叠，Prvoer计算并发送每个向量$\mathbf t_i$的承诺，双方计算上述误差向量

下图是一个阶为3的例子

Lookup Gates

Plonkish支持查表，因此对于查表得折叠也是一个研究方向

References

$[1]$ Sangria: a Folding Scheme for PLONK - Geometry Research

$[2]$ technical_notes/sangria_folding_plonk.pdf at main · geometryresearch/technical_notes · GitHub

‍