Nova：基于折叠方案的快速递归论证

Nova 是一种基于折叠方案的快速递归 SNARK（SNARK 是一种类型加密证明系统，允许证明者通过一个简短的证明向验证者证明一个数学陈述，并且递归 SNARK 能够生成关于先前证明的证明）。

[!重要] 该项目接受外部贡献，但在贡献之前请阅读 此部分。

更具体地说，Nova 实现了 增量可验证计算 (IVC)，这是一种强大的密码学原语，允许证明者在增量方式下产生关于“长时间运行”的顺序计算的正确执行证明。例如，IVC 允许以下操作：证明者接受一个证明 $\pi_i$，证明其计算的前 $i$ 步，然后更新它以产生一个证明 $\pi_{i+1}$，证明前 $i + 1$ 步的正确执行。关键的是，证明者更新证明的工作量不依赖于迄今为止执行的步骤数量，验证者验证证明的工作量也不会随着计算中的步骤数量增加而增加。包括 Nova 在内的 IVC 方案具有广泛的应用，如 Rollups、可验证延迟函数 (VDFs)、简洁区块链、可验证状态机的增量版本，以及更一般地，关于（虚拟）机器执行的证明（例如，EVM、RISC-V）。

Nova 的一个独特之处在于，它是文献中最简单的递归证明系统，但提供了最快的证明者。此外，它实现了最小的验证器电路（在此上下文中最小化的关键指标）：该电路大小恒定，其大小约为 10,000 个乘法门。Nova 是由一个称为 折叠方案 的简单原语构建的，这是一种将检查两个 NP 陈述的任务简化为检查单个 NP 陈述的密码学原语。

库的详细信息

此存储库提供了 nova-snark, 这是一个在椭圆曲线周期上实现 Nova 的 Rust 库。我们的代码支持三个曲线周期：（1）Pallas/Vesta，（2）BN254/Grumpkin，以及（3）secp/secq。

诺瓦（Nova）的核心依赖于矢量承诺方案。使用Spartan压缩IVC证明依赖于将矢量承诺解释为多线性多项式承诺，并证明已提交多项式的评估。我们的代码实现了两种承诺方案和评估论证

1. 基于IPA的评估论证的Pedersen承诺（支持所有三个曲线周期），以及
2. HyperKZG承诺和评估论证（支持具有配对的曲线，例如BN254）。

有关使用HyperKZG的更多详细信息，请参阅测试 test_ivc_nontrivial_with_compression。HyperKZG实例化需要一个通用可信设置（所谓“tau的幂”）。在src/provider/hyperkzg.rs中的setup方法中，可以加载在现有KZG可信设置中生成的群元素（该设置是为其他基于一元多项式的证明系统创建的，例如Plonk或变体），但库目前尚未这样做（请参阅此问题）。

我们还实现了一个基于Spartan的SNARK，以压缩诺瓦生成的IVC证明。有两种变体，一种不使用任何预处理，另一种使用电路的预处理以确保验证器的运行时间不依赖于步骤电路的大小。

支持的接口端

接口端是一个工具，可以将高级程序转换为中间表示（例如，电路），以便可以用于证明程序在具体输入上的执行。有三种支持的方式可以将高级程序写成可以用诺瓦证明的形式。

1. bellpepper：诺瓦的原生API接受使用bellpepper表达的电路，bellpepper是Rust工具包，用于表达电路。请参阅minroot.rs或sha256.rs以获取示例。

2. Circom：一种领域特定语言和编译器，可以将使用其语言表达的高级程序转换为电路。存在中间件将circom的输出转换为适合用诺瓦证明的形式。请参阅Nova Scotia和Circom Scotia。未来，我们将在诺瓦存储库中添加使用这些工具的示例。

3. Lurk：一种Lisp方言和通用电路，用于执行用Lurk表达的程序。通用电路可以用诺瓦证明。

未来，我们计划支持Noir，这是一种类似Rust的领域特定语言和编译器，可以将这些程序转换为IR。请参阅此GitHub问题以获取详细信息。

测试和示例

默认情况下，我们启用了底层库的asm功能（通过提升性能高达50%）。如果库无法构建或运行，可以向以下cargo命令传递--no-default-features。

运行测试（我们建议使用发布模式以显著缩短运行时间）

cargo test --release

运行示例

cargo run --release --example minroot

参考文献

以下论文，在CRYPTO 2022上发表，提供了诺瓦证明系统的详细信息和安全证明

诺瓦：基于折叠方案的递归零知识论证
Abhiram Kothapalli，Srinath Setty，和Ioanna Tzialla
CRYPTO 2022

为了效率，我们实现的诺瓦证明系统实例化在一个椭圆曲线周期上。以下论文指定了该实例化并提供了安全证明

在曲线周期上重新审视诺瓦证明系统
Wilson Nguyen，Dan Boneh，和Srinath Setty
IACR ePrint 2023/969

贡献

本项目欢迎贡献和建议。大多数贡献需要您同意《贡献者许可协议》（CLA），声明您有权并且实际上确实授予我们使用您贡献的权利。有关详细信息，请访问 https://cla.opensource.microsoft.com。

提交拉取请求时，CLA 机器人将自动判断您是否需要提供 CLA，并相应地装饰 PR（例如，状态检查，注释）。只需遵循机器人提供的说明。您只需在整个使用我们 CLA 的所有仓库中这样做一次。

本项目已采用 Microsoft 开源行为准则。有关更多信息，请参阅 行为准则常见问题解答 或通过 [email protected] 联系我们，如有任何其他问题或意见。

其他指南

此代码库实现了一种复杂的加密协议，需要具备加密、数学、安全和软件工程方面的专业知识。鉴于其固有的复杂性，引入细微错误的普遍担忧使得接受重大贡献变得极其困难。因此，外部贡献者被敦促提交增量、易于审查的拉取请求（PR），这些 PR 包含定义良好的更改。

我们更喜欢保持简单、易于理解和维护的代码。这种方法便于对代码进行正确性和安全性审计。为了实现这一目标，我们可能优先考虑代码的简单性，而不是微小的性能提升，尤其是当这种提升涉及复杂、难以维护的代码，并破坏抽象时。

如果您通过 PR 提出与性能相关的更改，我们期待包含可重现的基准测试，证明在一系列典型电路中实现了显著的加速。这种严格的基准测试确保所提出的更改在基于 Nova 构建的各种应用中显著提高了性能。每个性能提升都将经过彻底的、逐个案例的评估，以确保与维护代码库简单性的承诺保持一致。

最后，如果您打算提交重大的 PR，我们请求您先在 GitHub 上发起一个 issue，概述您的计划更改，以便在投入大量时间实现这些更改之前征求反馈。

商标

本项目可能包含项目、产品或服务的商标或徽标。Microsoft 商标的授权使用必须遵守并遵循 Microsoft 商标及品牌指南。在修改此项目的版本中使用 Microsoft 商标或徽标不得引起混淆或暗示 Microsoft 的赞助。任何第三方商标或徽标的使用均受这些第三方政策约束。

致谢

请参阅贡献者列表 此处