不完整的折叠指南：Nova、Sangria、SuperNova、HyperNova、Protostar

August 11th, 2023

特别感谢arnaucube 、 Brecht Devos、Barak、Benedikt Bünz、Binyi Chen和Ben Wan的审阅。

长话短说

整个 zk 行业正在努力的目标是 (i) 尽可能降低证明生成成本，同时 (ii) 保留尽可能小的证明，以及 (iii) 尽可能高效地进行验证。这可以通过证明者优化来实现，或者作为替代方案，可以压缩证明者证明的数据。

在过去的几年里，zk 科学界在折叠方案技术方面做了大量工作。在本文中，我们探讨了折叠方案技术，该技术可用于在验证单个证明验证整个计算链时实现更有效的 IVC（增量可验证计算）方法。我们还简要解释了折叠方案的用途，并介绍了当前技术水平的演变。

内容

递归 SNARK：特征和约束
Folding – 递归的另一种方法，以及 Nova –R1CS 的折叠应用程序
桑格利亚汽酒——PLONKish 赛道的 Nova
SuperNova——广义新星
HyperNova – 使用总和检查和可定制约束系统 (CCS) 进行折叠
ProtoStar – Nova（和 Sangria）效率保持泛化

让我们从简单的电路构建方法开始

在一种简单的方法中，人们构建了一个涵盖所有操作码和 EVM 更改的巨型电路。

免责声明：要了解操作码和电路是什么，请查看PSE 的这篇文章，要了解 ZK-EVM 中不同电路如何相互连接，请查看PSE 的另一篇文章。

这种方法的问题

证明器内存需求与 n（电路被调用的次数）成正比；
难以并行/分布式证明生成；
验证者时间也可能取决于 n；
证明时间与n成正比。

1. 递归和聚合：特征和约束

递归 SNARK 意味着在另一个 SNARK证明中验证一个SNARK 证明。递归允许 ZK-SNARK 证明者将更多知识压缩到他们的证明中，同时保持 SNARK 的简洁性。

递归 SNARKs 应用

示例 1：人们 不是生成知识证明，而是创建他们知道某个证明的证明。

结果，我们有两个电路：

内部电路（大）：证明者证明他们认识证人。在这个阶段，证明生成很快，但证明很大（证明大小为常数的情况除外）；
外电路（小）：证明者证明他们知道证明。在这个阶段，证明生成速度较慢（但这并不重要，因为在大多数情况下电路比第一个小得多），但证明很小。

感谢递归 SNARK，我们得到了快速证明生成和**简短的最终证明。**然而，如果验证器电路（外部电路）比想要证明的初始陈述小得多，则这种方法有效。

示例 2：使用证明聚合一次证明多个语句（例如，对于 ZK-Rollup，证明块中的所有交易都是有效的）。

要为所有语句生成一个整体证明，需要等到他们拥有需要证明的所有语句（在汇总示例中，在块准备好被证明之前，应该填充尽可能多的交易）。相反，由于递归 SNARK，人们可以在得到第一个语句后开始生成证明。最后，生成证据的证明。

与 ZK-Rollup 示例一样，它可以按以下方式工作：

因此，在收到所有交易后，证明者仅生成一个最终的证明证明（聚合其他证明），这比为所有交易生成整体证明要快得多。

示例 3：IVC – 增量可验证计算

IVC 允许我们用相对较少的内存进行长时间计算的证明。

函数F（例如微处理器）被迭代多次。每一步都会生成一个新的证明：它证明到目前为止的计算是正确的。

IVC的核心理念

在步骤n：

证明者计算一个新的状态s_n

证明π_n证明证明者有一个见证人***(s_n-1, w_n, π_n-1)，使得当前状态 (s_n) 相对于先前状态 (s_n-1) 是正确的。即F(s_n-1, w_n) = s_n。***并且先前状态（π_n-1）的证明相对于先前状态（s_n-1）是正确的。即，V(vp, (n-1, s_0, s_n-1), π_n-1) = true。

重要的是，在每一步结束时，只有一个最终输出——状态s_n。证人的知识**(w_0, …, w_n)嵌入到s_n中。并且在每一步中，都有一个证明π来证明直到当前步骤的每一步的计算都是正确完成的。也就是说，我们在步骤 1 处有π_1** ，在步骤 2 处有π_2 ，在步骤 3 处有π_3，...，在步骤 n 处有π_n。验证者可以通过仅验证一个证明π_n来检查当前步骤n之前的所有步骤的计算是否正确完成。

下腔静脉的应用

将长计算分解为一系列小的相同步骤，从而显着降低证明者的内存需求；
生成简洁的证据来证明区块链的当前状态是正确的。也就是说，将整个区块链的有效性证明压缩为一个简洁的证明（例如，Mina 使用它向每个区块“注入”一个证明，证明区块链上从创世开始的所有先前交易都是有效的）；
F是延迟函数的一次或多次调用，与IVC一起构成可验证延迟函数（例如MinRoot）；
ZK-VM：F是 VM（例如 EVM、LLVM、WASM 等）的步骤（机器支持的任何操作码）；
zkBridge：F根据区块链共识规则等验证状态。

递归的局限性

然而，证明者需要为运行整个验证算法V (vp, x, π)的电路C构建证明。验证多项式承诺的评估证明的成本很高。

好的，递归允许我们做一些技巧，在其他证明中生成证明。这有助于减少证明生成时间和证明大小。但是如果我们可以压缩我们想要证明的陈述呢？

用于半结构化计算的 ZK-SNARK 的演变

图表来源：PSE 的“CCS & HyperNova with Srinath - Folding Schemes FTW”讲座。

2. Folding – 递归的替代方案，以及 Nova – R1CS 的折叠实例化

免责声明1：2020 年，Benedikt Bünz、 Alessandro Chiesa、William Lin、Pratyush Mishra和 Nicholas Spooner发表了论文《Proof-Carrying Data without Succinct Arguments》。它实现了与下面描述的“关于折叠的酷事”相同的特性。然而，它的成本是 3 次标量乘法，而不是 2 次（用于折叠）。

免责声明 2：尽管在 Nova 中，折叠方案是针对 R1CS 实例化的，但它可以推广到其他约束系统。例如，桑格利亚汽酒（Nicolas Mohnblatt）的 PLONKish 赛道就是这样做的。有关更多详细信息，请参阅第 3 节“Sangria – Nova for PLONKish 电路”。

想法：进行预处理以压缩 SNARK 输入。

关于折叠的酷事：

不执行任何多项式除法或乘法（例如，通过需要大量内存且计算量大的 FFT）；
适用于任何类型的椭圆曲线（例如 secp、secq、Pasta 等）；
F用R1CS指定；
没有可信设置；
与递归开销相比，折叠预计比 Groth16、PLONK、Halo 等快 5-50 倍。证明时间由两个大小为**O(C)的多次幂运算决定，其中C = | F | **;
验证器电路是常量大小（两个标量乘法）；
证明大小为**O(log C)**组元素（几 KB）。

长话短说：通过折叠，可以将两个实例“压缩”为一个，并添加它们被正确“压缩”的证据。

它满足完整性和知识健全性要求：

如果原始证人w1和w2是正确的，则新证人w也是正确的；
如果新见证人 w 对于折叠实例x是正确的，则可以提取初始实例x1和x2的原始见证人w1和w2 。

“简而言之折叠”的高级概述

最初，折叠是一种交互式协议，如上图所示，其中T是交叉项，这意味着索引为 1 和 2 的变量参与一项，而 r 是随机挑战。

可以使用 Fiat-Shamir 将协议转换为非交互式协议。然后证明者自行生成随机性，对x1、x2和T进行哈希处理，并附上随机性已正确生成的证明。

最初，Nova 是为 R1CS 设计的（请记住，存在三种常见的约束系统：R1CS、PLONK和AIR）。

对于R1CS程序A、B、C和公共输入x（其中A、B、C – 三个m*m大小的矩阵），如果z = (x, w)使得(Az) ○ ( Bz) = Cz，其中○是哈达玛积。

为了构建 R1CS 的折叠方案，我们有

R1CS实例：R1CS程序A、B、C和公共输入x；
公共输入x1和见证人z1 = (x1, w1) ;
公共输入x2和见证人z2 = (x2, w2)；
对于z1和z2，我们期望 ( Az) ○ (Bz) = Cz。

如果我们直接说（只是弃牌）：

使用具有随机性的线性组合r : x = x1 + r * x2 ;
计算z = z1 + r * z2 = (x1 + r * x2, w1 + r * w2) ;
计算**(Az) ○ (Bz)** ;
但是，我们将得到(Az) ○ (Bz) = Cz1 + r ^2 * Cz2 + E ，而不是理想的 (Az) ○ (Bz) = Cz ，其中Cz = Cz1 + r * Cz2 ，其中E包括所有一些交叉-项和E如下：

为了克服这个问题，可以使用Relaxed R1CS：

为了构建松弛R1CS的折叠方案，我们有

R1CS实例：R1CS程序A、B、C和公共输入**(x,u,E)，其中标量c和向量E**是噪声参数；
公共输入**(x1, c1, E1)和见证者z1 = (x1, w1)**；
公共输入**(x2, c2, E2)和见证者z2 = (x2, w2)**；
对于z1和z2，我们期望**(Az) ○ (Bz) = u(Cz) + E**。

如果我们直接说（只是弃牌）：

使用随机性r的线性组合：(i) x = x1 + r * x2，(ii) u = u1 + r * u2，(iii) E = E1 + rT + r^2 * E2（其中T是交叉学期）;
计算z = z1 + r * z2 = (x1 + r * x2, w1 + r * w2) ;
计算**(Az) ○ (Bz)** ;
现在**(Az) ○ (Bz) =Cu(Cz) + E为真，这意味着 w 是宽松 R1CS 实例(x, u, E) 的有效见证人；**
然而， E的大小与总计算的大小有关：也就是说，E可能比x大得多。所以，对于验证者来说，E太大而无法处理它。

为了解决这个问题，可以使用承诺的宽松 R1CS：即使用对 E 的小承诺，comm(E)，而不是使用大的 E。它解决了问题，因为 E 取决于总计算的大小，对 E 的承诺则不然。

为了构建一个**致力于、**轻松的 R1CS 折叠方案，我们有

R1CS 实例：R1CS 程序A、B、C和公共输入**(x, u, comm(E))，其中comm(E)是使用同态承诺方案完成的对E**的承诺；
公共输入**(x1, u1, comm(E1))和见证(z1, E1, rE1)，其中rE是用于comm(E)**的随机性；
公共输入**(x2, u2, comm(E2))和见证(z2, E2, rE2)**；
我们期望z1和z2都满足**(Az) ○ (Bz) = u(Cz) + E**，并且comm(E)是使用r表示E1、E2、rE1和rE2对E的承诺。

如果我们直接说（只是弃牌）：

使用随机性r的线性组合：(i) x = x1 + r * x2，(ii) u = u1 + r * u2，(iii) comm(E) = comm(E1) + r * comm(T) + r ^2 * comm(E2)（其中我们还使用对T 的同态承诺，并具有一定的随机性rT）；
计算 (i) z = z1 + r * z2 = (x1 + r * x2, w1 + r * w2) , (ii) E = E1 + rT + r^2 * E2 ,(iii) rE = rE1 + r * rT + r^2 * rE2 ;
计算**(Az) ○ (Bz)** ;
(Az) ○ (Bz) = u(Cz) + E成立。

要详细了解 (Az) ○ (Bz) 计算，请查看幻灯片，要真正深入了解 Nova（以及完整性和知识可靠性的证明），请查看原始Nova 论文。

折叠首先在 Nova 中实现，这给 Nova 证明系统带来了巨大的优势。

不同现代验证系统的比较

折叠方案应用

使用承诺的宽松 R1CS 修改 IVC

我们将函数F扩充为F'，添加检查以确保上一步的折叠是否正确完成。

粗略地说：Nova 递归开销比采用最先进（截至 2022 年 7 月）可信设置 SNARK 的基于 SNARK 的 IVC 低 10 倍，比不带可信设置的 SNARK 小 100 倍。

然而，这是一个交互式协议。为了使其成为非交互式的，可以使用 Fiat-Shamir。

证明者自己生成一个随机挑战。随机挑战是两个折叠实例的散列和对交叉项的承诺；
证明者还生成随机挑战已正确生成的证明；
但是，验证者没有证明者用于生成随机挑战的输入。它拥有的一切——折叠的最后结果。
这就是为什么证明者还应该证明（i）它为获取随机挑战生成的输入而进行的所有折叠（例如消息折叠、噪声参数折叠、交叉项折叠等）均已正确完成，（ii）折叠实例正确链接在一起，即步骤 i 的输出是步骤 i + 1 的输入；
这是通过将初始 R1CS 程序A、B、C增强为A'、B'、C'来验证 (i) 证人对于正在折叠的实例的正确性以及 (ii) 折叠是否正确完成来完成的。该程序采用三个实例：x_i、x_1→i、x_1→i+1，并检查 (i) x_1→i+1是x_i和x_1→i的正确折叠，并且 (ii) x_i是有效实例；
事实上，它检查函数F的计算是否正确，并且还在G组中执行两次乘法（一次检查乘积r * x和一次r * com(T)）。在“正常”递归中，证明者需要 (i) 评估函数F和 (ii)运行整个 SNARK 验证电路；
在 Nova 中，运行整个验证电路被G组中的两次乘法+ 一些简单的散列代替（散列很便宜）。

这比递归 SNARK 更快（约 10 倍）并且更便宜。我们只有 20k 约束——这很便宜！

此外，当用 Nova 生成证明时，证明的大小与递归计算的一步成正比。

使用经过折叠方案修改的 IVC 的一些用例

VDF – 可验证的延迟函数。对于 VDF，函数F是一些延迟函数，需要进行一些重要的顺序计算。例如，计算有限域内的立方根。
并行化（例如，不同实体之间或不同 CPU 之间或一个 CPU 中不同内核之间的分布式证明）。
图灵完备的 SNARK 语言（例如 Lurk）的后端，其中函数F执行程序的一个步骤。
Rollups，其中函数F是状态转换函数——它将之前的 Merkle Root 和一些交易作为输入，执行交易，并输出更新的 Merkle Root。

核心新星挑战

证明的大小为O(|C|)，它线性取决于电路的大小。

Nova实验由微软研究团队实施。

3. 桑格利亚汽酒——PLONKish 赛道的 Nova

好的，在 Nova 中，折叠方案是针对 R1CS 实例化的，但是其他约束系统呢？Sangria（由 Geometry 的 Nicolas Mohnblatt 建议）表明 Nova 的折叠方案可以应用于任何二次约束系统，特别是 PLONKish 电路。

对 PLONKish 电路应用折叠

Verifier工作在电路深度恒定；
常数比 Nova 更糟糕（这是更灵活算术化的代价）。

对 PLONK 进行简短、高层次的回顾：

固定大小的网格；

单元格中充满了数字；

我们需要遵循一套规则。该组规则包括（i）复制约束：具有相同颜色的单元格应具有相同的值；

(ii) 门方程：每一行i应满足以下方程：

选择器和规则定义电路。一旦我们修复了选择器和规则，电路就修复了。

朴素随机线性组合应用：

保留复制约束（这可以从完美的完整性中通过代数推导出来，请查看桑格利亚汽酒技术说明以了解更多详细信息）；
但由于非线性，门方程不成立。

为了解决这个问题，我们对门方程使用（如原始 Nova 中那样）松弛

见证W = (w_a, w_b, w_c)加噪声向量e；
实例：公共输入X = (x_a, x_b, x_c)、标量u和承诺comm(w_a)、comm(w_b)、comm(w_c)、comm(e)。
松弛门方程——我们现在有一个齐次函数：

第一阶段：折叠

trace' + r * trace'' = Final_trace（与上图完全相同）；
u' + r * u'' = u。

第2阶段：将折叠结果代入松弛门方程

门(trace') + r * t + r^2 * 门(trace'') = 门(final_trace)

然而，t相当大（如何在上面的等式中看到几行）因此有点难以操作，因此我们使用定义e的技巧来使其更容易（并且只需摆脱t）：

e' - r * t + r^2 * e'' = e。

协议

Prover 计算交叉项t并提交给t；
Prover发送**comm(t)**给验证者；
验证者发送一些随机性；
证明者和验证者都进行线性组合：证明者和验证者输出折叠实例：X' + r * X'' = X u' + r * u'' = u com(w_a) = com(w_a') + r * com(w_a'') com(w_b) = com(w_b') + r * com(w_b'') com(w_c) = com(w_c') + + r * com(w_c'') com(e') - r * com(t) + r^2 * com(e'') = com(e)

证明者输出折叠见证：W' + r * W'' = We e' - r * t + r^2 * e'' = e r_a' + r * r_a'' = = r_a r_b' + r * r_b'' = r_b r_c' + r * r_c'' = r_c r_e' + r * r_t + r^2 * r_e'' = r_e

对于验证者来说，为了能够处理承诺，它应该使用加法同态承诺方案。

有关 Relaxed PLONK 折叠方案的详细说明，请查看Geometry 或Sangria Technical Note中 Nicolas Mohnblatt 的这篇注释。

桑格利亚汽酒表演

验证者对承诺进行四次添加（椭圆曲线点添加）；
事实上，我们可以通过提交额外的列来处理更宽的电路（这意味着每个门有超过两根线进入和超过一根线出来）。验证者需要对每个跟踪列执行一个额外的加点；
我们还可以处理更高级别的定制大门。每一个额外的学位都需要证明者的消息中包含一个额外的承诺，而验证者将为每个学位执行一个额外的加分。它还将改变我们处理噪声项的方式。d 级门将通过u至u^d的幂来放松。新噪声的折叠方程将是

Nova 电路中的 12k 约束（总共 20k 约束中）是最昂贵的点添加。所以问题是：更宽的电路和定制门的好处是否会超过额外加点的成本（验证者将强加的）？

4. SuperNova——广义Nova

好的，在 Nova 中，一个函数F可以一次又一次地应用。但是如果每一步都有不同的功能怎么办？这就是 SuperNova 让我们能够做到的！

此外，虽然 Nova 证明的大小为O(|C|)，即与电路的大小线性相关，但在 SuperNova 中，证明程序步骤的成本仅与表示所请求指令的电路大小成正比。

SuperNova 是 Nova 对半结构化电路的推广。

SuperNova 的酷炫之处

每个步骤适用于任何可能的函数**{F_1、F_2、F_3 等…}**；
证明生成不必遵循顺序路径（可以使用二叉树优化）。

SuperNova 下引入了非均匀 IVC（IVC 的泛化）。

我们有

k + 1 个非确定性函数F_1、F_2、…、F_k 的集合，这些函数是编码不同指令的电路，以及一个特殊函数φ，可帮助选择要执行的指令之一（φ是选择器电路）；
初始输入s_0。

目标是

证明s_n是应用电路C_j n 次的输出，其中在步骤i处，j = φ(w_i-1, s_i-1)。

要深入了解 SuperNova，请查看原始论文。

将 SuperNova 与具有通用电路的递归 ZK-SNARK 和具有修剪电路的 ZK-SNARK 进行比较：

在修剪电路中，不使用通用电路，而是选择一个已执行的电路，因此，只需为执行的内容付费（而不是为整个电路执行付费）；
所谓开销，我们指的是见证人大小、公共 IO（交互式 Oracle）大小、约束数量、NP 检查器时间（NP 检查器查看见证人和约束系统并检查其是否可满足）、证明时间等的额外增长。
在上表中，递归开销是指在使用递归的情况下，某些原语效率不是很高。例如，必须使用 Merkle 树或基于多集的哈希函数的内存。两者都会导致每个内存操作至少有数百个约束。而对于非递归 SNARK，我们可以使用例如访问内存成本低得多的排列。然而，对于递归 SNARK，如果每条指令执行至少 10k 个门，则可以减轻这种递归开销。

Jules 的SuperNova 实验实施。

5. HyperNova – 使用总和检查和可定制约束系统（CCS）进行折叠

我们将在下一章（HyperNova）的解释中使用和检查协议。为了保持同一页面，让我们简要描述一下总和检查是什么。

和检查协议的简要说明

非正式直觉：我们可以将求和协议视为一种工具，它将多个点的多项式评估转变为一个点的评估。

形式直觉：

有关详细解释，请参阅 Justin Thaler 所著的《Proofs, Arguments, and Zero-Knowledge》一书，第 4.1 节“The Sum-Check Protocol”。

验证者可以通过预言机访问字段F上的k 变量多项式g；
验证者的目标是计算k 个变量**[b_1, …, b_k]上多项式g**评估的总和；
天真地，验证者只需向预言机询问b的每个值的多项式g评估，然后将结果相加即可。需要2^k次预言机评估和2^k次字段添加；

使用和校验协议，验证者将大部分工作委托给证明者，而验证者本身只检查 k 个证明者消息，然后在最后进行 1 g 多项式评估（oracle 查询）；
在阶段 0，证明者发送验证者声明的答案c_1。总和检查协议必须检查

在下一轮中，证明者向验证者发送一个单变量多项式。例如，在第一轮中，证明者向验证者发送多项式s_1(x_1)，该多项式等于

为了指定多项式，证明者发送 3-4 个系数（3-4 个字段元素）；

验证者想要检查是否确实 (i) s_1(x_1) = H_1(x_1) ，(ii) 它与真实答案c_1（在 0 阶段发送）一致。因此，验证者在随机点r_1处检查(i) c_1 = s_1(0) + s_1(1)、(ii) s_1 = H_1。**s_1(r_1)**可以直接从证明者的第一条消息计算，但不能从H_1 **(r_1)**计算；
验证者需要检查

为了计算它，证明者和验证者可以递归地应用和校验协议并通过该协议逐轮进行。在每一轮中， g 的另一个变量绑定到随机选择的元素r_1。他们一轮又一轮地这样做，直到在第k轮中 g 的最终变量绑定到随机元素r_k；

在第 k 轮中，证明者发送声称等于H_k = g(r_1, …, r_k) 的单变量多项式s_k(x_k)；
验证者检查s_k-1(r_k-1) = s_k(0) + s_k(1)；
然后，验证者需要检查的最终语句是s_k(r_k) = g(r_1, …, r_k)。此检查需要验证者执行一次 oracle 查询（可以自行执行）。

CCS

CCS是一个约束系统，它在没有开销的情况下概括了 Plonkish、R1CS 和 AIR。

最初为 R1CS 描述的 SNARK 很容易扩展到 CCS（因此是 PLONKish）：

斯巴达 (R1CS) → 超级斯巴达 (CCS)
马林鱼 (R1CS) → 超级马林鱼 (CCS)

然而，最初为 PLONKish（Plonk、HyperPlonk 等）描述的 SNARK 无法在没有开销的情况下处理 CCS（甚至 R1CS）。高层原因是CCS和R1CS都具有线性组合，而PLONKish证明系统受到有限且特定类型的线性约束的限制。

CCS说明

为了指定电路，CCS 有t 个矩阵M_1, M_2, …, M_t；
为了允许自定义约束，它有q个多重集S_1, S_2, …, S_q；
公共输入：x；
证人W使得Z = (W, x, 1)。

如果 Hadamard 乘积之和为零，则电路满足，即

可以说 R1CS 是 CCS 的一种特例，其中

电路说明：M_1=A，M_2=B，M_3=-C；
S_1 = {1, 2}, S_2 = {3};
公共输入：x；
证人 W 使得Z = (W, x, 1)；
Az ○ Bz = Cz。

承诺CCS (CCCS)

要将两个 CCS 合二为一，我们将使用 CCCS（承诺 CCS），其中 C = comm(w)也在实例中。

然而，如果我们尝试进行 Nova 式松弛，交叉项的数量将与约束的程度成正比。这效率不高。

因此，我们可以将其中一个 CCCS 线性化以获得 LCCCS，而不是折叠两个 CCCS。然后折叠 CCCS x LCCCS → LCCCS（结果也将是线性化的 CCCS）。

线性 CCCS 意味着约束是线性的，因此多重集的大小为 1。这足以构建 IVC，但不是 NP 完全的。

线性化承诺 CCS (LCCCS)

CCS 包括

t 个矩阵M_1, M_2, …, M_t；
q多重集S_1, S_2, …, S_q；
公共输入：x；
承诺C = comm(W)；
标量u ;
随机挑战r ;
压缩矩阵所有行的标量**(v_1, v_2, …, v_t) ：**

见证向量W使得Z = (W, x, u)。

高级 CCS 折叠图

步骤 1：CCCS x LCCCS → LCCCS 折叠：使用一次和校验协议调用，通过相同的随机挑战将 CCCS 简化为 LCCCS

这是一个交互协议；
两个折叠实例应具有相同的结构：相同的矩阵 M和多重集 S；
验证器以 LCCCS ( C', u', x', r', v_1', …, v_t') 和 CCCS (C'', x'')开始，进行线性组合，并输出两个 LCCCS，(C', u', x', r, σ_1', …, σ_t')和**(C', u', x', r, θ_1', …, θ_t')具有相同的随机挑战 r；**
验证器输入和输出W'、 W''。

步骤 2： 对于 LCCCS x LCCCS → LCCCS 折叠 – 所有检查都是线性约束

验证者向证明者发送随机挑战γ （随机挑战对于所有i都是相同的）；
证明者采用W', W''，进行线性组合W' + γ * W'' = W并输出W；
验证者采用**(C', u', x', r, v_1', …, v_t')** , (C'', u'', x'', r, v_1'', ..., v_t'')并使得线性组合C' + γ * C'' = C u ' + γ * u'' = u x' + γ * x'' = x v_i' + γ * v_i'' = v_i并输出(C, u, x , r, v_1, …, v_t)。

**[ (C, u, x, r, v_1, …, v_t), W ]**的正确性通过线性保持：

超新星

HyperNova是一种证明者高效且递归的 ZK-SNARK，用于证明增量计算，其中每个步骤都用提交的 CCS 表示。

HyperNova 使用 SuperSpartan 的早期版本为可定制约束构建新的折叠方案。关键思想是设计一个多项式，对有关高度约束的声明以及一些先前的声明进行编码。当总和检查应用于该多项式时，所得到的权利要求采用适合折叠的形式，而不需要任何交叉项。

HyperNova 可以通过两种方式构建：(i) 直接方法：直接构建在 CCS 的非交互式多重折叠方案上，(ii) 另一种方法将多重折叠方案与 Nova 结合使用作为黑匣子。

有关 HyperNova 协议的详细描述，请查看原始论文。

超新星成本

证明者成本：1 MSM 提交见证+1 总和检查；
验证者成本（递归电路）：1 个标量乘法 + 对数个哈希值

HyperNova由arnaucube和asn实验性实现。

nlookup：Nova 的查找参数

假设有一个大小为n的表T。考虑CCS 实例中的m 个变量v_1, …, v_m ，我们希望强制这些值包含在T中。

查找：将T存储为 Merkle 树，电路将其作为公共输入获取承诺。然后，为了证明T中存在某个值，证明者可以向电路提供 Merkle 包含证明作为非确定性建议，并且电路验证 Merkle 包含证明。它需要电路内部进行O(m * log(n)) 次哈希计算。
p Lookup：约束数量为O(max(m, n))，如果n ≈ m则有效，但不适用于递归，其中特定递归步骤可能执行m << n查找操作；
nlookup：对于大小为n个条目的表的m次查找，nlookup 需要**O(m * log(n))乘法和电路内的O(log(n))哈希运算（具有小常数），并且证明者执行O( n)**有限域运算。特别是，证明者不承诺任何额外的多项式。这是使用 Nova 和 HyperNova 高效表达有限状态机的完美工具。有关 nlookup 的详细描述，请查看HyperNova 论文的第 7 节。

6. ProtoStar – Nova（和 Sangria）保效率泛化

ProtoStar IVC 结合了高效折叠方案的通用方法和用于表达关系的简单特殊声音协议*，允许递归电路支持（i）高阶门，（ii）任意大的查找表，（iii）任意多个操作码在只有 3 个组操作的 VM 中。

免责声明：堆积和折叠是指底层类似的技术。由于不同作者大致在同一时间探讨相似现象的不同论文，出现了定义差异。

ProtoStar 的目标大致上与 HyperNova 的目标类似：与 Nova（及其泛化 - Sangria）一样，证明者复杂性和递归电路大小都与门的程度成正比，ProtoStar和 HyperNova 的目标是将其最小化（理想情况下，使其成为常数）。然而，与 HyperNova 不同的是，在 ProtoStar 中，(i) 支持查找的开销几乎可以忽略不计，(ii) 不需要和检查协议。

图表来源：ProtoStar论文。

编译器仅需要向量承诺，因此不需要可信设置、配对或 FFT。
每个累积/IVC 步骤中的证明者在支持的电路数量上是对数的，并且与查找中的表大小无关（与Nova 的 d * log(n) 相比）。
查找效率更高，因为使用对数导数参数而不是乘积参数。因此，可以在许多地方放置零系数。递归电路由3组标量乘法和d个字段元素的散列主导，其中d是最高门的度数；
无需额外的 MSM 成本即可实现高阶门。无需使用多个门，而是可以将它们与随机元素 b（验证者挑战）的幂相加，最终只有一个 d+1 级的门。d+1 次的门可以处理，因为它只是一个多项式（更多细节请查看“通用 ProtoStar 折叠方法”（下一节）的第四步）。然而，我们仍然需要 d 个交叉项，但是我们可以使用字段元素作为一维向量的简单承诺方案，而不是使用承诺。这些交叉项的处理成本要低得多；
在验证器电路尺寸方面，ProtoStar 比 HyperNova 做得更好：如果发生非本地现场操作，在没有查找支持的情况下，必要的非本地现场操作模拟可能会相当昂贵。Protostar 具有廉价的查找支持（ProtoStar 中的 O(d) 与 HyperNova 中的 O(d*log(N)），因此非本地字段运算电路可以更高效。但是，如果使用 SNARK 友好的哈希函数，则差异微不足道。
ProtoStar 中的技术可以推广到 PCD（Proof-Carrying Data），即不仅可以证明计算链，还可以在不牺牲效率的情况下证明计算的整个树/ DAG（有向无环图）。
它支持高效的电路分支。也就是说，电路始终与整组操作码成比例。也就是说，创建具有多个分支的电路，这些分支（i）由选择器打开和关闭，以及（ii）以“关闭”分支的方式组织，在证明过程中不会花费任何成本；
它可以与Wilson最近提出的 IVC 编译器一起使用，以进一步提高效率。

ProtoStar 折叠通用配方

**1.为关系R建立多轮特殊声音协议* Π。**

*关于特殊声音协议的旁注

与IVC相比，特殊声音协议更容易构造，因为它**（i）** 不需要简洁，（ii）可以交互，（iii）可以表示复杂的关系（例如，查找关系）。

k-special-sound协议可以从k轮通信中提取有效的见证。

考虑 1-special-sound 协议的示例：

资料来源： PSE与 Binyi Chen 举办的“深入研究 Protostar 论文和协议”研讨会

**2. 使用关系R的压缩验证器将协议Π转换为另一个交互协议CV[Π] 。**

3.使用 Fiat-Shamir将此协议转换为非交互式参数NARK(CV[Π]) 。

4. 构建 NARK(CV[Π]) 验证者检查的折叠方案。

我们有两张支票，一张证明支票和一张折叠支票，我们很乐意将它们折叠成一张支票；
证明者的实例 x 包括承诺 C、随机挑战 r 和 u = 1。折叠的实例 x 包括承诺 C、随机挑战 r、松弛 u 和噪声向量 E；
证明者和折叠的见证人 w 包括证明者消息 m；
累积校验是验证者计算的齐次方程，而证明者的NARK校验有0到d不同度数的元素，其中d是每次校验的最大度数。
目标是将两项检查合并为一个方程式。我们可以使用多项式插值来做到这一点：

然而，在这种方法下，许多组操作取决于每个检查 d 的最大度。我们希望他们独立。

压缩验证检查：使用随机线性组合将多个验证检查 L 压缩为一个约束。然而，这种检查的程度最终要大得多，d+L。此外，支票中的条款不再是同质的。所以，折叠不能再应用了。
为了解决同质性问题，验证者可以用另一个变量替换所有系数，而不是使用一些不同程度的系数，这样检查程度将为 d+1 并且检查将是同质的。证明者最后将发送一个具有不同幂次的初始系数的数组。然而，在这种技术下，验证者需要检查所有这些初始系数。因此，O(l^1/2) 额外的组操作被添加到证明者工作中，并且 O(l^1/2) deg-2 正确性检查被添加到验证者工作中，其中 l 是初始验证者检查的数量。

遵循ProtoStar累积/折叠方案，Group操作的数量与验证者检查的程度无关。

有关 ProtoStar 的详细描述，请查看原始论文。

其他令人兴奋的、使用折叠的相关内容未在本文中介绍，以供进一步探索：

Origami – 一种用于 Halo2 查找参数的显式折叠方案，作者：Yan Zhu和aardvark；
ParaNova – oskarth并行化 Nova ；
MoonMoon – 通过使用 Lev Soukhanov的 RSA 组中的 Pedersen 承诺，向 Nova 添加排列参数并在整数系数上使用 Nova ；
ProtoGalaxy – 高效的 ProtoStar 式的多个实例折叠：Liam Eagen 和Ariel Gabizon的论文以及arnaucube的概念验证实现；
David Wong的一篇 Nova 攻击解释文章《当年的零知识攻击可能刚刚发生，或者 Nova 是如何被攻破的》。

结论以及下一步是什么？

因此，HyperNova 和 ProtoStar 可能不是最终游戏。现有 zk 协议的折叠实现仍处于早期阶段，并且正在进行中。要跟踪折叠实现的进展情况，请检查 lurk lab 的github 存储库，该存储库汇总了所有折叠新闻，包括新鲜出炉的实现。Folding 和所有这些很棒的 Nova 都是由微软研究院的 Srinath Setty 推出的，请关注他的 Twitter，了解接下来会发生什么。Zeroknowledge.fm （查看其 zkStudyClub）和EF 的PSE小组（查看其 YouTube并关注其即将推出的研究活动）正在进行有关折叠及其实现的大量教育工作。不和谐服务器）。

资料来源：

“递归 zkSNARKs：探索新领域”文章，作者：0xPARC
“ZKP MOOC 讲座 10：递归 SNARKs”讲座和幻灯片，作者：Dan Boneh
“Nova：折叠方案中的递归零知识论证”论文，作者：Abhiram Kothapalli、Srinath Setty、Ioanna Tzialla
“模块十四：Nova 速成课程”与 Justin Drake 的ZK 白板课程，作者： zeroknowledge.fm
Twitter 帖子总结了 IVC 和折叠方案的关键见解，作者：@0xevvm
“Nova：来自折叠方案的递归零知识论证”讲座，由 Protocol Labs 与 Srinath Setty 共同主持
Srinath Setty 的“超新星”讲座，作者： zeroknowledge.fm
“SuperNova：证明无需通用电路的通用机器执行”论文，作者：Abhiram Kothapalli、Srinath Setty
PSE 小组与 Srinath Setty 进行的“CCS 和 HyperNova - 折叠方案 FTW”讲座
“HyperNova：可定制约束系统的递归参数”论文，作者：Abhiram Kothapalli、Srinath Setty
Benedikt Bünz 介绍 ProtoStar 的Twitter帖子
“Protostar: Generic Efficient Accumulation/Folding for Special-sound Protocols”论文，作者：Benedikt Bünz、Binyi Chen
levochka.eth 总结 ProtoStar 的Twitter帖子
Zeroknowledge.fm 播客，第 280 集：Benedikt Bünz和 Binyi Chen 的 ProtoStar。
PSE 与 Binyi Chen 举办的“深入研究 Protostar 论文和协议”研讨会。