fabrizio-m/lilium

# Lilium 一个可定制的证明系统。 - [x] 泛型支持任意域和（同态）承诺方案。 - [x] 支持任意度数、电路级、用户自定义的 custom gates。 - [x] 折叠。 - [x] 提供高级 API 用于在 Rust 中构建电路并生成 witness。 - [x] 泛型且可组合的电路。 - [x] 代码量和依赖数量都很小。 - [ ] 私有递归（IVC）。 - [ ] 公开递归（PCD?）。 - [ ] 支持 lookups 和 lookup gates。 ## 引言 Lilium 是一个针对算术电路的知识证明。 如果数字电路以比特为值，以 OR 和 AND 为 gates。 那么算术电路则以域元素（如某个素数模运算下的自然数）为值，以加法和乘法为 gates。 算术电路是一组变量以及连接它们的 gates/constraints。 Lilium 允许你证明自己知道每个变量的值赋值，使得所有的 constraints 都被满足，最重要的是，无需泄露这些值。 例如这个电路： $$x - 3 = 0$$ 如果 $$x = 3$$，那么你可以证明它而无需泄露 x 的值。 这个/某个 witness 可以说是 3。 但是这个： $$x^2 + 1 = 0$$ 不存在可能的 witness，你不可能知道不存在的东西。 那这个呢？它应该有解： $$x^6 - 1 + x^5 = 0$$ 但如果你不知道它，你就无法证明它。存在性是不够的，你需要有相关知识。 ### 为什么要使用它 #### 示例 1 假设你有一个非常喜欢的数字 X，你想把它只留给自己，并且假设 X 也是一个平方数。 但某天，有人声称你的数字不是平方数，你不能无视这样的指控，你需要证明 X 是一个平方数。 最简单的方法是提供 X 和某个 w，然后任何人都可以检查 X = w^2，但所有人都会知道你的 X，这是不可接受的。 有没有可能在泄露 X 的情况下证明它是一个平方数？ #### 示例 2 给定 Fibonacci 数列： fib(0) = 0 fib(1) = 1 fib(i+2) = fib(i) + fib(i+1) 你想知道 fib(1000)，这里没有任何秘密，任何人都可以计算它，但这需要时间。如果有人能替你计算它就好了。 有人能在不需要你计算 fib() 1000 次来验证正确性的情况下，证明 fib(1000) = X 吗？ #### 示例 3 你想证明你的银行账户里至少有 $30，但你不想透露你到底有多少钱（$31）。 你能不泄露 x 的情况下证明 x >= 30 吗？ ### 如何使用它 以上 3 个例子的答案是肯定的，但怎么做呢？ 整体的方法是一样的： - 创建一个代表我们声明的电路，或者我们的声明是其特定实例的一组声明集合。 - 使用 lilium 为该电路创建一个 circuit key。 - 使用该 key 为我们的声明生成证明。 - 使用该 key 验证证明。 完整的示例可以在 [lilium/examples/](./lilium/examples/) 中找到。 #### 创建电路 电路只是一个实现了 Circuit trait 的类型，你可以针对特定的域来实现它，也可以泛型实现它。 ``` pub trait Circuit { fn circuit>( cs: &mut C, public_input: [Var; IN], ) -> ([Var; OUT], ()); } struct MyCircuit; impl Circuit for MyCircuit { ... } ``` 在这个简化版本的 trait 中，你可以看到大多数重要的内容。 电路接受一些变量作为输入，以及一些实现了 ConstraintSystem 的值，你可以使用 cs 来创建新变量，并连接和约束这些变量的 gates。 最后你输出一些构成公开输出的变量。 ### 证明与验证 一旦你有了电路，你就可以创建一个 key 并开始生成证明了。 ``` fn main() { use field_and_pcs::{Fr, FrScheme}; let circuit_key: CircuitKey = CircuitKey::new(); let inputs = []; let (instance, proof, _output) = circuit_key.prove_from_inputs(inputs); let instance: LcsInstance = instance; let proof: Proof = proof; assert!(circuit_key.verify(instance, proof)); println!("verification successful"); } ``` #### 示例 1 实现 为了证明 $x$ 是一个平方数，我们需要证明存在某个 $w$ 使得 $w^2 = x$，并且我们不能泄露它们中的任何一个。 我们的电路看起来会是这样的，稍微简化了一点： ``` fn circuit( cs: &mut C, []: [Var; 0], ) { let x = cs.free_variable(|_, _| my_number()); let w = cs.free_variable(|_, _| my_number::().sqrt().expect("not square")); let w_square = cs.square(w); cs.assert_equals(x, w_square); } ``` 我们有 2 个自由变量，一个的值设为 x，另一个设为 w。 然后我们使用一个平方 gate 来计算 $w^2$。 最后是一个强制 $w^2 = x$ 的等式 gate。 #### 示例 2 实现 这是一个我们对零知识不那么感兴趣（因为任何人都可以计算任意 x 的 fib(x)），而是对简洁性更感兴趣的场景。 简洁性允许我们用比生成证明所需更少的时间来验证某个声明的证明。 注意：该示例在实践中并不简洁，有关简洁性的详细信息，请参见（TODO: 添加链接）。 这次的电路将有 2 个公开输入，期望输入 $fib(0)$ 和 $fib(1)$ 的值，以及一个用于 $fib(1000)$ 的公开输出。 ``` fn circuit>( cs: &mut C, public_input: [Var; 2], ) -> ([Var; 1], [Var; 0]) { let [_, res] = (0..N).fold(public_input, |last_two, _| { let [a, b] = last_two; let c = cs.add(a, b.clone()); [b, c] }); ([res], []) } ``` 这个更接近于实际的代码，正如你在 [example2.rs](./lilium/examples/example2.rs) 中看到的那样。 #### 示例 3 实现 我们现在利用了电路类型，目前唯一可用的是：Uint。 电路类型支持简单实现那些原本需要许多变量和 gates 的功能。 例如，`Uint::new` 会创建大约 32 个变量和 96 个 constraints。 `Uint::new(cs,x)` 会创建一个与 x 值相同的新变量，但将其约束为适合一个 N 位数字，在这个例子中是 $[0..2^32]$ 区间。 由于值是相同的，所以它可以像 `_int` 那样被丢弃。 原始变量现在被约束为一个大于 0 的 `u32`。 但我们希望它大于 30，为此我们从原始金额中减去 30，并用另一次范围检查确认它 $>30$。 ``` fn circuit>( cs: &mut C, public_input: [Var; 1], ) -> ([Var; 0], [Var; 1]) { let [minimum] = public_input; let amount = cs.free_variable(|_, _| balance()); let _int: Uint = Uint::new(cs, amount.clone()); let amount_less_minimum = cs.sub(amount.clone(), minimum); let _int: Uint = Uint::new(cs, amount_less_minimum); ([], [amount]) } ``` 你在最后看到的不是公开输出，因为这里没有公开输出。 它是一个私有输出，它看起来很相似，但它只是证明者在生成证明后获得的信息，而验证者永远不会看到。 ## 特性 ### 自定义 gates Gate 是 [Gate](./ccs/src/gates.rs) trait 的实现： ``` pub trait Gate { fn gate(i: [V; I]) -> [V; O]; fn check(i: [V; I], o: [V; O]) -> Constraints; } ``` 通过一个 `gate` 方法将输入映射到输出，以及一个 `check` 方法在输入和输出之间创建 constraints。一个 constraint 只是在满足时计算结果为 0 的某个等式。 目前 gates 的定义与特定的域无关，它们可以具有任意的度数、输入/输出数量以及 1 个或多个 constraints。 Circuit builder API 允许使用任意数量和类型的 gates，只要设置了正确的配置，就可以为任何电路创建 `CircuitKey`。 下面是几个示例，有关更多信息，请参见 [ccs/src/gates.rs](./ccs/src/gates.rs)。 ``` pub enum Equality {} impl Gate<2, 2, 0> for Equality { fn gate(_i: [V; 2]) -> [V; 0] { [] } fn check(i: [V; 2], _o: [V; 0]) -> Constraints { let [a, b] = i; Constraints::from(a - b) } } pub enum Square {} impl Gate<2, 1, 1> for Square { fn gate(i: [V; 1]) -> [V; 1] { let [x] = i; [x.clone() * x] } fn check(i: [V; 1], o: [V; 1]) -> Constraints { let ([x], [expected]) = (i, o); let xx = x.clone() * x; Constraints::from(xx - expected) } } ``` 正如你所见，`IO` 仅仅是 `I + O`。 `Constraints` 是一个必须被强制为 0 的变量列表。 如果你像大多数 gates 一样只有单个 constraint，你可以像这里一样使用 `From` 实现。 ### 电路级 Gates 一些证明系统，比如那些基于 R1CS 和一些 plonk 实现的系统，提供一个单一的通用 gate，它执行某种形式的加法和乘法。 你的整个电路是由这个单一 gate 的许多实例构建而成的。 其他证明系统添加了实现级别的 custom gates，提供了一系列 gates 来定义你的电路。Custom gate 可以针对特定的应用进行专门化，在不同的方面优于通用 gate。 许多 plonk 的实现都属于这一类。 实现级别的 custom gates 的一个局限性在于，作为库的用户，你最多只能选择使用某个给定的 gate。添加一个新 gate 需要修改库的实现。对于库的用户来说，这些 gates 并不是那么“自定义”。 更进一步，证明系统可以公开一个接口来创建你自己的 gates 并使用它们。 到目前为止所有类型的一个小问题是，它们都是证明系统级别 gates 的例子。这意味着这些 gates，无论是固定的还是自定义的，都设定在证明系统中，然后电路再使用它们。 这并不是什么大不了的问题，但我们还能做得更好。电路级别的 custom gates 允许你直接在电路中使用任何你想要的 gate，证明系统随后只需从你的电路中推断出要使用的 gates，而无需任何额外的配置。 总的来说，这使得它更易于使用，并促进了诸如电路组合等其它功能，因为由 2 个电路组合而成的电路所使用的 gates，仅仅是它们各自使用的 gates 的并集。 对于特定的 gate 可以有多“自定义”，也存在一些差异，主要有 3 点： - 度数：虽然大多数时候你可以按需增加加法，但乘法会增加 gate 的度数，一些实现可能会将你限制在最大度数，例如，允许使用平方 gate，但不允许使用立方 gate。即使被允许，随着度数的增加，证明者的性能在某些实现中可能比其他实现受到的影响更大。 - 元数：一个 gate 可以有多少个输入和输出，它可能是固定的，也可能是灵活的。一个常见的选择是 N -> 1 gates，你可以拥有任意多个输入，但只能有 1 个输出。 - Constraints 数量：一个有用的 gate 有 1 个或多个 constraints，大多数有 1 个，而一些高级 gates 有多个 constraints。Constraint 是你希望在输入和输出之间成立的某种等式。 例如，$a + b = c$ 将是加法 gate 的 constraint。 对于大多数 N -> 1 gates，单个 constraint 就足够了，但对于 N -> M gates，你可能需要多个 constraints。 Lilium 目前实现了任意度数和元数的电路级 custom gates。Gates 可以有任意数量的 constraints，但如果你想使用折叠，目前它只接受带有单 constraint gates 的电路。 关于度数的性能是线性的，这意味着度数为 3 的 gate 所需的证明者时间是度数为 1 的 gate 的两倍（我们从 0 开始计数）。 ### 电路组合 由于电路的核心只是一个函数，你可以在另一个电路内部调用一个电路。 例如 poseidon2 置换电路： ``` pub struct TestingHash; impl Circuit for TestingHash { type PrivateInput = (); type PrivateOutput = [F; 3]; fn circuit>( cs: &mut C, public_input: [Var; 3], ) -> ([Var; 3], [Var; 3]) { ... } fn handle_output(out: [F; 3]) -> Self::PrivateOutput { out } } ``` 现在可以多次调用它来创建一个哈希链电路： ``` pub struct HashChain; impl Circuit for HashChain { type PrivateInput = (); type PrivateOutput = F; fn circuit>( cs: &mut C, public_input: [Var; 1], ) -> ([Var; 1], [Var; 1]) { let [x] = public_input; let mut state = [(); 3].map(|_| x.clone()); for _ in 0..N { //HERE let (new_state, _) = TestingHash::circuit(cs, state); state = new_state; } let [out, _, _] = state; ([out.clone()], [out]) } fn handle_output([out]: [F; 1]) -> Self::PrivateOutput { out } } ``` ### 折叠 折叠允许你将 2 个实例合并为一个，使得新实例只有在 2 个原始实例也是有效的情况下才有效。 这个过程可以重复进行，将 N 个实例折叠为 1 个，但即使折叠每次都成功，在折叠后的实例被证明之前，也无法对任何原始实例做出任何断言。 ``` let key = CircuitKey::::new(); let (instance1, witness1, _) = key.commit_witness([input1]); let (instance2, witness2, _) = key.commit_witness([input2]); let instances = (instance1, instance2); let witnesses = [witness1, witness2]; // Prover fold both instance-witness pairs, getting a new // instance-witness pair, and a folding proof. let (prover_instance, witness, fold_proof) = key.fold(instances, witnesses); // Verifier does the same, but without witnesses, receives only an instance. let verifier_instance = key.fold_instances(instances, fold_proof); // The same instance as the prover. assert_eq!(prover_instance, verifier_instance); ``` 为什么我需要折叠？主要有 3 个应用： - 你想要一个更小的电路：如果你的电路可以拆分成更小的块，你仍然需要折叠每个块，但在最后你只需要证明一个单一的小块。对于相同规模的电路，折叠的性能远远好于完整证明。 - 你的计算是无界或可变的：如果它可以被定义为由任意数量的较小步骤组成，那么你只需根据每个特定实例的需要来证明尽可能多的步骤。如果没有它，你将不得不为最坏的情况定义一个大型电路。 - 更小的验证时间：验证 Lilium 证明的复杂度是 O(log n) + pcs.open。这意味着如果你使用的承诺方案的验证时间是 O(n)，验证可能需要几秒钟的时间，这绝对不是简洁的。另一方面，无论使用何种承诺方案，折叠始终具有 O(1) 的验证时间。 ## 基准测试 基准测试可以在 `lilium/benches` 中找到，分为两套：执行时间基准测试（`exectime`）和峰值内存基准测试（`memory`）。两者都是使用 Criterion 构建的，因此通常的 Criterion CLI 选项和 HTML 报告都可以正常工作。 要运行所有的基准测试，只需运行 ``` cargo bench ``` 要仅运行执行时间基准测试，请运行 ``` cargo bench Time ``` 或 ``` cargo bench --bench exectime ``` 要仅运行内存基准测试，请运行 ``` cargo bench Memory ``` 或 ``` cargo bench --bench memory ``` 内存基准测试报告了在测量的操作本身期间分配的峰值堆内存，这是相对于设置后获取的基线而言的。Circuit key 和 SRS 被排除在外，并有它们自己的组（Setup Memory, SRS Memory）。 HTML 报告被写入 `target/criterion`，你可以使用以下命令在本地提供它 ``` python3 -m http.server 8000 --directory target/criterion ``` 然后在浏览器中打开 `http://localhost:8000/report/index.html` 你可以使用以下命令保存用于比较的基线 ``` cargo bench -- --save-baseline foo ``` 然后你可以使用以下命令与它进行比较 ``` cargo bench -- --baseline foo ``` ### 单线程 所有基准测试都基于 [HashChain](https://github.com/fabrizio-m/lilium/blob/master/lilium/src/testing/utils.rs#L87) 电路。 这是一个计算所需长度 poseidon2 链的电路。 选择这些长度是为了使 constraints 的数量刚好低于下一个 2 的幂，并且报告显示的是 constraints 的数量，而不是链的长度。如果你对链的长度感兴趣，测量的值对应于 `[11, 22, 44, 89, 178, 356, 712, 1424, 2849, 5698]`，并产生从 $2^{12}$ 到 $2^{21}$ 的 constraints 计数。 这些基准测试是在 Azure Standard FX2mds VM 中运行的。 #### 证明时间  #### 折叠时间  #### Commit 和 fold 你很少会刚好只有 2 个实例来进行折叠，最常见的情况是你有 1 个正在运行的实例，并创建一个新实例与它进行折叠。 此基准测试对一个实例进行 commit 以及对其进行折叠的时间总和，从而提供一个与证明进行对比的更现实的参考点。  ## 设计考量 本节将解释该库的内部设计考量，它超越了仅仅使用该库所需的内容，可以安全地忽略。 ### 历史 这个项目最初是 Hypernova 的一个简单实现，旨在实现论文中定义的关系和折叠方案的知识证明。 随着时间的推移，我扩大了范围，转向了更有用、更强大的库，从而偏离了 Hypernova 和 CCS。 脱离 CCS 的主要设计目标是让算术化直接成为电路的目标，不考虑与 R1CS、Plonk 或 AIR 的兼容性。 - 矩阵像在 CCS 中一样被使用，但受到了更多限制，与 one-hot 编码同构。 - 显式的 selectors 作为普通多项式存在，而不是额外的矩阵。 - 公开输入的工作方式有些不同，这是为了简化和优化。 - 我计划进行更多的更改，以更好地支持常量并添加 lookups。 我从未实现过 Hypernova 的折叠，因为 NeutronNova 出现了，我更喜欢那个方法，也就是目前实现的方法。我不认为 NeutronNova 的折叠可以与我进行 lookups 所需的稀疏多项式一起工作。为了支持这一点，我最终可能会使用这 3 种方法（Nova, Hypernova, NeutronNova）。 ### 依赖项 我拥有非常少的外部依赖，ark-ff，以及如果你使用默认提供的基于 IPA 的多项式承诺方案时的 ark-ec。 至于内部依赖，我有以下 crates： #### Ccs 实现了关于电路的所有内容： - `Circuit`。 - 从电路生成 constraints。 - 生成 witness。 - 表示电路的结构。 - 常见 gates 的实现。 你可能会注意到，我还有一些东西需要重命名为 lcs。 #### Commit 定义了表示折叠方案的 traits，用于 commit 和 open 多项式以及 batching 的实用工具。 还有一个基于 IPA 的多项式承诺的实现，在需要时作为默认的承诺方案使用。 #### Hash-to-curve 这是 IPA 承诺方案的一个依赖项，它最初作为一个单独的 crate 开始，因为我认为我需要更多功能来支持折叠。 但目前，在开始公开递归之前，不需要进一步的开发。 #### Spark Spark 稀疏多项式承诺方案的部分实现，它允许对包含大量零的大型多项式进行承诺，只需支付非零元素的成本。 它实现了一个我称之为“static spark”的变体，其中假设承诺是格式良好的，因此需要的检查更少。 这适用于向 circuit keys 中的矩阵进行承诺，但不适用于例如 lookups。 根据我未来实现 lookups 的方式，该实现可能会扩展到完整的 Spark，从而允许对不受信任的承诺进行打开证明。 #### Sponge 实现了一个通用的 sponge/duplex，兼容任何置换，一个定义置换的 trait，以及一个 poseidon2 置换的通用实现。 poseidon2 置换应该适用于任何域，但仍有少数情况尚未处理，对于大多数 256 位或更大的素数域仍然足够。 #### Sumcheck 这是目前最复杂的 crate，它实现了一个通用且高效的 sumcheck 证明者和验证者，以及它们所需的几个实用工具。 还有一个 sumfold 实现，以及专门的 zerocheck 证明者。 #### Transcript 实现了 Fiat-Shamir transcript，并定义了 `Protocol` 和 `Reduction`，它们分别是知识证明和知识规约。 因为我在了解知识规约之前就创建了它，所以它并没有严格匹配正式定义。它们的主要目标是帮助构建结构化且可组合的协议定义，同时防范许多损害可靠性的常见 bug。 现在可以预见的是，我没有太多使用 `Protocol`，即使在我使用了的少数情况下，也没有完全使用。未来我可能会摆脱它，只使用 `Reduction`，我也会让它更接近正式定义。 ## 问答 这里有一些我无法放入其他部分的话题。 只要你有一个合适的承诺方案，一切都会按预期运行。 但它不会足够安全。因为 sumcheck 的安全性取决于 challenges 的大小。 Sumcheck 必须更新为使用足够大的域扩展，以提供足够的安全性。 目前对于 1.0 的要求是： - 处理所有的 TODO。 - 记录所有 crates 中的公开接口。 - 提高证明性能，这主要相当于重新设计 spark。 - 做一些我想到的特定重构。 目前整个代码库都是单线程的。 我想思考一种干净的方法，使其在未来能够推广到硬件加速。 但如果需要，现在添加它也不是什么大工作量，尽管提出来。 大约 99% 的运行时集中在 3-4 个算法上，使它们支持多线程是很容易的。 目前代码库使用了 std，仅仅是因为到目前为止这不是一个值得关注的问题。 但它在任何地方都不是必需的，一个简单的重构应该就能让所有的 crates 支持 no-std。 ## 参考文献 TODO：添加对论文等资料的引用。

标签：Rust, 可视化界面, 密码学, 手动系统调用, 算术电路, 网络流量审计, 证明系统, 通知系统, 零知识证明