原文标题：《 Nova：零知识证明的新篇章 》

原文来源：Huobi Research

引言

零知识证明是密码学中的一种重要技术，它允许一个人向另一个人证明一个陈述是真实的，而无需透露任何其他信息。这种技术在许多领域都有广泛的应用，包括身份验证、区块链和安全计算等。Nova 是微软开发的一种新型零知识证明系统，它使用了一种名为松弛的秩一约束系统（Relaxed Rank-1 Constraint Systems，Relaxed R 1 CS）的技术，以提高证明的效率和灵活性。最后一章节对源码进行详细解读。

Nova 的优点

Nova 的主要优点在于其使用的松弛的 R1CS 技术。R1CS 是一种用于构建零知识证明的系统，它可以用于证明一个人知道满足一组多项式等式的解，而不必透露任何关于解的信息。然而，传统的 R1CS 系统需要在证明过程中使用大量的随机性，这会导致证明的生成和验证过程非常复杂和耗时。Nova 通过使用松弛的 R1CS 来解决这个问题，它允许在证明中使用更少的随机性，从而大大提高了证明的效率。

Nova 还具有其他一些优点。例如，它支持增量计算，这意味着可以逐步计算复杂的函数，而不必一次性计算整个函数。这在处理大规模数据或进行复杂计算时非常有用。此外，Nova 还支持多项式计算，这使得它可以处理更复杂的证明任务。

Nova 的缺点

尽管 Nova 具有许多优点，但它也有一些缺点。首先，由于 Nova 使用的是松弛的 R1CS，因此它的证明可能不如传统的 R1CS 系统那么强大。这是因为松弛的 R1CS 允许在证明中使用更少的随机性，这可能会降低证明的安全性。然而，Nova 的开发者已经采取了一些措施来解决这个问题，例如使用更强大的密码学算法和更复杂的证明策略。

其次，Nova 的实现相对复杂，这可能会增加使用和维护的难度。Nova 使用了许多高级的密码学技术，如多项式计算、群操作和随机预言机等，这需要深入理解这些技术才能有效地使用和修改 Nova。

Nova 在零知识证明领域的重要地位

Nova 在零知识证明领域中占据了重要的地位。它的出现，为零知识证明的发展开辟了新的道路。Nova 采用的松弛的 R1CS 技术，使得证明的生成和验证过程更加高效，这对于大规模的零知识证明应用至关重要。此外，Nova 还支持增量计算和多项式计算，这使得它可以处理更复杂的证明任务，进一步扩大了零知识证明的应用范围。

Nova 的源码解读

https://github.com/microsoft/Nova

在 src/ 目录下，有以下几个重要的子目录：

bellperson/：这个目录可能包含了关于 Bellman-Ford 算法的代码。

gadgets/：这个目录可能包含了一些用于构建 zk-SNARK 证明的工具。

provider/：这个目录可能包含了一些提供者的代码，如 keccak.rs 可能是实现 Keccak 哈希函数的代码。

spartan/：这个目录可能包含了关于  Spartan 协议的代码。

traits/：这个目录可能包含了一些 Rust traits，用于定义一些公共的行为。

src/bellperson/mod.rs 文件的内容：

这个模块主要用于生成 R1CS（Rank-1 Constraint Systems，一种用于 zk-SNARKs 的约束系统）。

它包含了三个子模块：

r1cs：这个模块可能包含了关于 R1CS 的代码。

shape_cs：这个模块可能包含了关于形状约束系统的代码。

solver：这个模块可能包含了关于解决约束系统的代码。

在测试部分，它定义了一个函数 synthesize_alloc_bit，这个函数接受一个约束系统，然后添加一些约束来检查输入的两个比特是否确实是比特。然后，它定义了一个函数 test_alloc_bit_with，这个函数首先创建一个形状

src/bellperson/r 1 cs.rs 文件的内容：

这个文件主要定义了两个 trait：`NovaWitness` 和 `NovaShape`，它们分别提供了从实现者获取 `R 1 CSInstance` 和 `R 1 CSWitness`，以及获取 `R 1 CSShape` 和 `CommitmentKey` 的方法。

- `NovaWitness` trait 有一个方法 `r1cs_instance_and_witness`，它接受一个 `R 1 CSShape` 和一个 `CommitmentKey`，然后返回一个 `R 1 CSInstance` 和一个 `R 1 CSWitness`。这个 trait 为 `SatisfyingAssignment` 结构体实现，这意味着任何 `SatisfyingAssignment` 都可以使用这个方法来获取一个 `R 1 CSInstance` 和一个 `R 1 CSWitness`。

- `NovaShape` trait 有一个方法 `r 1 cs_shape`，它返回一个 `R 1 CSShape` 和一个 `CommitmentKey`。这个 trait 为 `ShapeCS` 结构体实现，这意味着任何 `ShapeCS` 都可以使用这个方法来获取一个 `R 1 CSShape` 和一个 `CommitmentKey`。

这个文件还定义了一个函数 `add_constraint`，它接受一个约束系统和三个线性组合，然后在约束系统中添加一个新的约束。这个函数被 `NovaShape` 的实现者在生成 `R 1 CSShape` 时使用。

总的来说，这个文件的主要作用是提供了一种方式，使得可以从一个满足特定条件的系统（如 `SatisfyingAssignment` 或 `ShapeCS`）中生成 R 1 CS 的实例、证人、形状和承诺密钥。

src/bellperson/shape_cs.rs

这个文件定义了一个名为 `ShapeCS` 的结构体，它实现了 `ConstraintSystem` trait。`ShapeCS` 是用于创建 R 1 CS 形状的约束系统。

`ShapeCS` 结构体包含以下几个字段：

- `named_objects`: 这是一个映射，用于存储与路径关联的对象。

- `current_namespace`: 这是一个字符串向量，用于存储当前的命名空间。

- `constraints`: 这是一个向量，用于存储所有添加到 `ShapeCS` 的约束。

- `inputs`: 这是一个字符串向量，用于存储所有的输入。

- `aux`: 这是一个字符串向量，用于存储所有的辅助输入。

`ShapeCS` 结构体实现了 `ConstraintSystem` trait，这意味着它提供了以下几个方法：

- `alloc`: 这个方法用于分配一个新的变量。

- `alloc_input`: 这个方法用于分配一个新的输入变量。

- `enforce`: 这个方法用于添加一个新的约束。

- `push_namespace`: 这个方法用于推入一个新的命名空间。

- `pop_namespace`: 这个方法用于弹出当前的命名空间。

- `get_root`: 这个方法用于获取根约束系统。

这个文件还定义了一些辅助函数，如 `proc_lc` 和 `compute_path`，它们分别用于处理线性组合和计算路径。

总的来说，这个文件的主要作用是提供了一种方式，使得可以从一个满足特定条件的系统（如 `ShapeCS`）中生成 R 1 CS 的形状。

src/bellperson/solver.rs

这个文件定义了一个名为 `SatisfyingAssignment` 的结构体，它实现了 `ConstraintSystem` trait。`SatisfyingAssignment` 是用于创建 R 1 CS 实例和证人的约束系统。

`SatisfyingAssignment` 结构体包含以下几个字段：

- `a_aux_density`, `b_input_density`, `b_aux_density`: 这些是 `DensityTracker` 类型的字段，用于跟踪查询的密度。

- `a`, `b`, `c`: 这些是向量，用于存储 A、B、C 多项式的评估结果。

- `input_assignment`, `aux_assignment`: 这些是向量，用于存储变量的赋值。

`SatisfyingAssignment` 结构体实现了 `ConstraintSystem` trait，这意味着它提供了以下几个方法：

- `new`: 这个方法用于创建一个新的 `SatisfyingAssignment` 实例。

- `alloc`: 这个方法用于分配一个新的辅助变量。

- `alloc_input`: 这个方法用于分配一个新的输入变量。

- `enforce`: 这个方法用于添加一个新的约束。

- `push_namespace`, `pop_namespace`: 这些方法用于操作命名空间，但在这个上下文中并没有实际的操作。

- `get_root`: 这个方法用于获取根约束系统。

- `is_extensible`, `extend`: 这些方法用于扩展约束系统。

总的来说，这个文件的主要作用是提供了一种方式，使得可以从一个满足特定条件的系统（如 `SatisfyingAssignment`）中生成 R 1 CS 的实例和证人。

"src/circuit.rs"，它定义了 Nova 协议中的增强电路（Augmented Circuit）。这个电路包括一个步骤电路（ Step Circuit）和 Nova 的非交互折叠方案中的验证器电路。

文件中定义了以下几个主要的结构体和方法：

- `NovaAugmentedCircuitParams`：这个结构体包含了电路的参数，包括 limb 宽度、limb 数量和一个布尔值表示这是否是主电路。

- `NovaAugmentedCircuitInputs`：这个结构体包含了电路的输入，包括参数、i、z 0、zi、U、u 和 T。

- `NovaAugmentedCircuit`：这个结构体是 Nova 增强电路的主要定义，它包含了电路的参数、只读常量、输入和步骤电路。它还定义了一些方法，如 `alloc_witness`（分配证人）、`synthesize_base_case`（合成基础案例）和 `synthesize_non_base_case`（合成非基础案例）。

- `synthesize` 方法：这是 Nova 增强电路的主要合成方法，它首先分配所有的证人，然后根据是否是基础案例来合成电路，并最后输出计算的哈希值和 u.X[ 1 ]。

这个文件还包含了一些测试代码，用于测试递归电路的功能。

总的来说，这个文件的主要作用是定义了 Nova 协议中的增强电路，这个电路是 Nova 协议的核心部分，它包括了一个步骤电路和一个验证器电路，并提供了一种方式来合成这个电路。

"src/constants.rs"，它定义了一些常量，这些常量在整个项目中被广泛使用。以下是这些常量的含义：

- `NUM_CHALLENGE_BITS`: 这个常量定义了挑战的位数，值为 128 。挑战通常是由证&