Sangria

<!--StartFragment-->

• 原文：Sangria: a Folding Scheme for PLONK
• 作者：Nicolas Mohnblatt
• 译者：Kurt Pan

如 Nova 1 所示，可以使用折叠方案和 zkSNARK 实现增量可验证计算 (IVC)。 在本文中，我们提出了对PLONK算术化 2 变体的折叠方案。 之后，我们扩展松弛PLONK 算术化，以接受2次自定义门和具有更高门扇入扇出数的电路。 最后，概述了未来工作的路径，包括折叠更高次的门、支持查找门和为松弛PLONK算术化设计 IOP。

本文是 Sangria 技术论文的浓缩版。 请参阅完整版以获取证明和扩展讨论。 我们假设读者熟悉 IVC 和 Nova。 建议初步查看和阅读：Justin Drake 的 ZK Whiteboard Session 和这篇 Lambdaclass 博客文章。

预备知识

PLONK算术化

在 PLONK 中，计算被表示为一个矩阵$ M$，具有三列$ a、b、c$ 和$ n+s+1$ 行。$ n$ 是公共输入的数量，$s $是门的数量，额外的一行检查最终结果是否为 1（即电路是否满足）。

第$ i$ 行的值$ – a_i,b_i,c_i – $分别对应第$ i$ 个门的左输入、右输入和输出。 第$i$个门定义为：$(q_L)_i,(q_R)_i,(q_O)_i,(q_M)_i,(q_C)_i $是每个选择子向量的第$i$个值。\ $Q={q_L,q_R,q_o,q_M,q_C}$为选择子向量集合。

门使用复制约束“连接”在一起，例如$ a_3=c_1$ - 门 3 的左侧输入是门 1 的输出。$S$为复制约束集合。

电路完全由元组$ (Q,S)$ 定义。

折叠方案

Nova论文引入了折叠方案并给出了如下直观定义：

[…] 一个对于关系R的折叠方案，是一个协议：将检验两个$R $中实例的任务归约到检验单个$R$中实例的任务。

完整定义见论文中的定义6。

承诺方案

方案使用对有限域$\mathbb F$ 中的元素向量的隐藏和绑定的加法同态承诺方案。 我们将这样的方案记为为 $Com$ 。 $\bar A=Com(pp_C,a;r)$ 为对向量 $a$ 使用随机值 $r∈\mathbb F$ 和承诺参数 $ppC$的承诺。

Sangria

Nova 为 R1CS 算术化构造了一个折叠方案。 这里，我们提出了对PLONK 算术化的折叠方案。 使用与 Nova 相同的洞见：

• 折叠是通过对输入的实例-见证对进行随机线性组合来进行的。
• 交叉项被吸收到错误（或松弛）向量和缩放因子之中。
• 通过对见证和松弛向量的加法同态承诺，方案变得不再平凡。

松弛PLONK门方程

对于标量$ u∈\mathbb F$和错误（松弛）向量$ e∈\mathbb F^{n+s+1}$ ，松弛PLONK 门方程定义为 :

$$ C^′_{Q,i}(a,b,c,u,e):=u[(q_L)_ia_i+(q_R)_ib_i+(q_O)_ic_i]+(q_M)_ia_ib_i+u^2(q_C)_i+e_i\qquad(1) $$

松弛PLONK 中的复制约束与 PLONK 复制约束相同。 松弛 PLONK 的迹由元组$ (a,b,c,u,e)$ 表示。

对于 PLONK 实例-见证对$ (X,W)$，我们将松弛PLONK实例-见证对 $(U,W)$ 定义为：

$$ U:=(X,u,\overline{W_a},\overline {W_b},\overline {W_c},\bar E)\qquad\qquad\qquad(2) $$ $$ W:=(W,e,r_a,r_b,r_c,r_e)\qquad\qquad\qquad\,\,\,\,\,\,\,(3) $$

其中$\overline {W_a}=Com(pp_W,w_a;r_a)$,$\overline {W_b}=Com(pp_W,w_b;r_b)$,$Wc=Com(pp_W,w_c;r_c)$ 且 $\bar E=Com(pp_E,e;r_e)$。

重要的是，任何松弛PLONK 关系都可以通过以下方式转换为PLONK 关系：设置$ u=1, e=\vec 0$ 并提供必要的承诺。 因此，松弛PLONK 算术化是 NP 完全的。

对松弛PLONK的折叠方案

按照 Nova 的符号，折叠方案由 4 种算法$\cal  G,K,P,V $定义：

*$\cal G(1^λ)→pp$：输出大小边界 $n,s∈\mathbb N$ 和承诺参数 $pp_W$ 和 $pp_E$ ，分别用于大小为 $s $和$ n+s+1 $的向量。

• $\cal K(pp,\cal(Q,S))→(pk,vk)$: 输出 $vk←⊥$ 且 $pk←(pp,vk,\cal(Q,S))$。

验证者$\cal V $输入验证者密钥 $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^{′′}})$。 证明者 P 输入证明者密钥 pk 和两个实例及其相应的见证 $(W^′,e^′,r^′_a,r^′_b,r^′_c,r^′_e)$ and $(W^{′′},e^{′′},r^{′′}_a,r^{′′}_b,r^{′′}_c,r^{′′}_e)$。

Sangria 折叠方案按如下方式进行：

1. $\cal P$ 随机采样 $r_t$ ， 发送 $\bar T=Com(pp_E,t;r_t)$ ，其中$t$ 按如下计算：

$t:=u^{′′}(q_L∘a^′+q_R∘b^′+q_O∘c^′)+u^′(q_L∘a^{′′}+q_R∘b^{′′}+q_O∘c^{′′})+q_M∘(a^′∘b^{′′}+a^{′′}∘b^′)+2ru^′u^{′′}q_C$ 其中$o$ 指代逐元素乘法。

1. $\cal V $随机采样挑战$r$。
2. $\cal P$和 $\cal V $输出折叠实例 $(X,u,\overline W_a,\overline W_b,\overline {W_c},\bar E)$ ，其中：

$$ 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} $$ $$ \bar E←\overline {E^′}−r\bar T+r^2\overline {E^{′′}} $$

1. $\cal P$ 输出折叠见证 $(W,e,r_a,r_b,r_c,r_e)$ ，其中： $$ W←W^′+rW^{′′} $$ $$ r_a←r^′_a+r⋅r^{′′}_a $$ $$ r_b←r^′_b+r⋅r^{′′}_b $$ $$ r_c←r^′_c+r⋅r^{′′}_c $$ $$ e←e^′−r_t+r^2e^{′′} $$ $$ r_e←r^′_e−r⋅r_t+r^2⋅r^{′′}_e $$ 定理：上述构造是对承诺松弛PLONK算术化的公开抛币折叠方案，具有完美完备性、知识可靠性、零知识性。

证明直观。 完美完备性可以按照代数规则展开直到下式成立：

$C^′{Q,i}(a,b,c,u,e)=C^′{Q,i}(a^′,b^′,c^′,u^′,e^′)+r^2C^′_{Q,i}(a^{′′},b^{′′},c^{′′},u^{′′},e^{′′})$ 也可以容易看到复制约束也保持成立。

使用与 1 相同的策略来证明知识可靠性。 具体来说，我们将分叉引理应用于折叠方案（1 中的引理 1）以获得三个脚本。 然后我们证明提取器使用所有三个脚本来插值出原始的$ e^′,r^′_e $和 $e^{′′},r^{′′}_e$ 的值，以及任何两个脚本以插值出$ (W^′,r^′_a,r^′_b,r^′_c) 和 (W^{′′},r^{′′}_a,r^{′′}_b,r^{′′}_c)$。 接着证明插值结果属于满足电路的每个门等式和复制约束的迹。

最后，零知识成立，因为证明者的消息是隐藏的承诺，而验证者只发送一个公共随机值。 完整的技术说明中给出了证明。

Degree 2 Custom Gates

2次自定义门及其选择子记为：

$$ G_i(a,b,c):=(q_G)_i⋅g(a_i,b_i,c_i)\qquad\qquad\qquad(4) $$

要折叠这样的门，将 $g$ 写为单项式的和，然后将单项式按次数分开。 令 $g_C$、$g_1$ 和$ g_2$ 分别为常数、1 次和 2 次单项式的和。 可以将松弛约束方程写为：

$$ C^′_{Q,i}(a,b,c,u,e):=u[(q_L)_ia_i+(q_R)_ib_i+(q_O)_ic_i+(q_G)_i⋅g_1(a_i,b_i,c_i)]\qquad $$ $$ \quad\qquad\qquad\qquad\qquad\qquad+(q_M)_ia_ib_i+(q_G)_i⋅g_2(a_i,b_i,c_i)+u^2(q_C)_i+u^2(q_G)_i⋅g_C+e_i $$

折叠 $ (a^′,b^′,c^′,u^′,e^′)$ 和 $(a^{′′},b^{′′},c^{′′},u^{′′},e^{′′}) $ 仍然通过随机线性组合来进行 ，但是必须调整$ t $向量以吸收由以下每个2次表达式产生的交叉项： $$ (u^′+ru^{′′})[(q_L)_i(a^′_i+ra^{′′}_i)+(q_R)_i(b^′_i+rb^{′′}_i)+(q_o)_i(c^′_i+rc^{′′}_i)+(q_G)_i⋅g_1((a^′_i+ra^{′′}_i),(b^′_i+rb^{′′}_i),(c^′_i+rc^{′′}_i))] $$ $$ (q_M)_i(a^′_i+ra^{′′}_i)(b^′_i+rb^{′′}_i)\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad $$ $$ (q_G)_i⋅g^2((a^′_i+ra^{′′}_i),(b^′_i+rb^{′′}_i),(c^′i+rc^{′′}{ii}))\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad $$ $$ (u^′+ru^{′′})^2(q_C)_i\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad $$ $$ (u^′+ru^{′′})^2(q_G)_i⋅g_C\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad $$

更高的扇入和扇出

只要门方程的次数小于等于 2，当前方案就可以支持更高扇入扇出数量的电路。每个额外的门输入或输出都需要一个额外的见证列承诺。

未来工作

本文为标准 PLONK 算术化构造了折叠方案，并介绍了一些自定义的功能。 最后简要指出即将到来的未来工作的方向。

使用对Sangria的zkSNARK的简洁 IVC

Nova 表明一个折叠方案直接蕴含 IVC。 然而，这些 IVC 证明既不简洁也不是零知识的。 为了实现这两个性质，必须为新的松弛算术化设计一个 zKSNARK。 一个可能的方向是将 Sangria 迹转换为 PLONKish 迹，并为松弛向量添加一个额外的见证列。 另一个方向是直接修改 IOP 以管理新引入的$ u$ 和 $e$ 值。

降低递归开销

在当前构造中，折叠验证者每个见证列使用1个承诺。 该方案还可以通过将见证矩阵 W 拍平为单个列向量，从而允许验证者使用单个见证承诺（和在Nova中一样）。 这样做需要参考串 $pp_W $相对具有“扇入 2，扇出 1”门的电路来说要长三倍。 考虑到标准 PLONK IOP 使用对每个见证列的承诺，它还可能在完整的 IVC 方案中引入额外的检查和承诺打开。

更高次自定义门

“随机线性组合”折叠策略可以实现更高次的自定义门。 设d为约束方程的最高次数，整体策略如下：

1. 将非松弛约束方程$ C_{Q,i}$ 表示为单项式之和。
2. 使用松弛因子 $u$ 的幂使 $C_{Q,i}$ 成为齐次 $d$次多项式。
3. 加入错误项$e$吸收交叉项。 交叉项现在具有$r$ 的从 $1 $到 $d−1$ 次幂。 将它们分别收集到向量 $t_1,t2,…,t{d−1}$ 使得

$$ e=e^′−∑^{d-1}_{k=1}r^kt_k+r^de^{′′}\qquad\qquad(5) $$

1. 按照标准结构中的描述进行折叠，进行以下修改：

   • 证明者计算并发送每个 $t_k$ 向量的承诺。
   • 按照上面等式中的定义计算 $e $并在承诺空间中应用相应的操作。

开销。 该策略为验证者和证明者都引入了额外的工作。 为了计算$ d−1$个交叉项向量及其承诺，证明者将执行 $\cal O(d∗(n+s)) $次域运算和 $\cal O(d∗(n+s))$ 次点加。 类似地，在承诺空间中验证者计算 $\cal O(d)$ 次点加。 注意验证者的工作依然是安全参数和电路规模方面的常数。 然而确实需要在实现 IVC的折叠和拆分累积 3 方法之间去进行更仔细的比较。

3次。使用上述策略对3次门使用随机线性组合策略的一个提案如下：

$$ u^2[(q_L)_ia_i+(q_R)_ib_i+(q_O)_ic_i]+u(q_M)_ia_ib_i+(q_3)_ia_ib_ic_i+u^3(q_C)_i+e_i\qquad\qquad(6) $$ 其中错误项被适当调整过以吸收交叉项（有关交叉项的显式表示，请参阅完整版）。

查找门

PLONKish 算术化与 R1CS 的区别部分在于它们集成了查找论证的能力。 我们对通过为支持查找的算术化开发折叠策略来保持这种灵活性很感兴趣。

致谢

感谢 Nat Bunner 和 Lev Soukhanov 对高次门折叠策略的改进。 我们还要感谢 Andrija Novakovic、Lai Ying Tong、Kobi Gurkan 和 Koh Wei Jie 提供的有益投入和贡献。

1. Kothapalli, Abhiram, Srinath Setty, and Ioanna Tzialla. Nova: Recursive zero-knowledge arguments from folding schemes. Annual International Cryptology Conference. Springer, Cham, 2022. [URL] ↩ ↩2 ↩3
2. Gabizon, Ariel, Zachary J. Williamson, and Oana Ciobotaru. Plonk: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge. Cryptology ePrint Archive, Paper 2019/953, 2019. [URL] ↩
3. Benedikt Bunz, Alessandro Chiesa, William Lin, Pratyush Mishra, and Nicholas Spooner. Proof-carrying data without succinct arguments. Cryptology ePrint Archive, Paper 2020/1618, 2020. [URL] ↩

本文首发于：https://cryptography.land/2023/03/07/sangria