Nova：无信任设置的递归SNARKs

[!NOTE] 该仓库是托管在 https://github.com/microsoft/nova 的原始仓库的分支。它是一个用于实验原始软件更高级变体和解决其中问题的孵化器。

[!IMPORTANT] 该分支始终保持与原始仓库一样最新。偶尔，在孵化一段时间后，该仓库会将自己的贡献反向移植到原始仓库。请注意，在反向移植之前，本仓库中的更改尚未经过同等级别的审查。

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 库实现。当前代码支持 Pallas/Vesta（即 Pasta 曲线）和 BN254/Grumpkin 椭圆曲线循环。用户可以通过提供这些曲线（例如，secp/secq）的 Nova 特性实现来使用 Nova 与其他椭圆曲线循环（例如，请参阅 src/provider/mod.rs）。

我们还实现了一个基于 Spartan 的 SNARK，用于压缩 Nova 产生的 IVC 证明。

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

cargo test --release

运行示例

cargo run --release --example minroot

规格说明

• SuperNova

参考文献

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

Nova：从折叠方案到递归零知识论证
Abhiram Kothapalli、Srinath Setty 和 Ioanna Tzialla
CRYPTO 2022

为了效率，我们的 Nova 证明系统实现是基于椭圆曲线循环的。以下论文指定了这种实例化并提供了一个安全证明

重新审视椭圆曲线循环上的 Nova 证明系统
Wilson Nguyen、Dan Boneh 和 Srinath Setty
IACR ePrint 2023/969

致谢

请参阅贡献者列表 此处