作者：Pierre

原文：

https://hackmd.io/KxG-BH1nQPGpdRxz6M50hw https://hackmd.io/mArMuUx5TC2LEcYecc741Q↳

译者：Kurt Pan

Part1用 Nova 做 zk/snark应用

本文对考虑将 Nova 用于 zk/snark 应用的开发者给出了详细操作方法。我们会过一遍该项目有关电路开发、wasm 编译和 react/nextjs 设置的库。更多细节和基准测试的信息见本文第二部分。

1设置准备

确保演示应用在本地正常运行

运行以下命令：

$ git clone git@github.com:dmpierre/nova-browser-ecdsa.git
$ cd nova-browser-ecdsa/
$ pnpm i && pnpm dev

试着在 http://localhost:3000/ 里去生成证明。

安装 wasm-pack

由于我们希望将 Nova 与 wasm 一起使用，因此需要安装 wasm-pack 。

https://github.com/rustwasm/wasm-pack↳

在库中，进入 nova-browser-ecdsa/apps/web/ ，尝试运行 pnpm wasm:build 。如果运行正常，则无需任何配置。否则需要安装 wasm-pack 。假设已经安装了 rust，运行 cargo install wasm-pack 。完成后，尝试再次运行 pnpm wasm:build 。

可能会弹出各种错误。它可能会说 blst 未正确编译。在这种情况下，请确保具有正确的环境变量设置，以便 rustc 可以找到 llvm 设置。请参阅此文件：https://github.com/nalinbhardwaj/Nova-Scotia/blob/main/browser-test/env.sh 。还可能最终收到cargo的报错：unable to create target: 'No available targets are compatible with triple wasm32-unknown-unknown：这也归结为要去正确设置环境变量。

之前已经有将用Halo2 证明系统写的电路移植到 wasm 的工作。（如Zordle：https://github.com/nalinbhardwaj/zordle/ ）。也有一些关于如何完成此操作的文档 （ https://zcash.github.io/halo2/user/wasm-port.html ）。这些与我们正在做的工作非常相似，所以不要犹豫，可以去看看。

2签名聚合电路

我们将使用 Nova-Scotia 把我们的 circom 电路移植到 Nova 可以输入的东西上。

https://github.com/nalinbhardwaj/Nova-Scotia/↳

首先，Nova-scotia希望在你的电路中定义 step_in 公开信号。这是因为 Nova 使用该 step_in 变量将通过电路计算的每个见证链接在一起。每个见证还将输出公开数据，这些数据将被重定向到下一个见证的后续 step_in 信号中。这意味着你应该确保输出信号遵循与 step_in 信号相同的格式。Nova-scotia没有输出信号的命名约定。这是因为电路的所有输出变量默认都是公开的。有时你会看到名为 step_out 的输出信号。

Nova基本工作原理的模型。来自这篇论文。 是由circom编译来的一个R1CS实例， 是公开输入/输出，即Nova-scotia 中的step_in/step_out， 是辅助私有输入。

https://eprint.iacr.org/2023/969.pdf

We went for a very straightforward solution regarding our aggregation circuit. We define three signals:
对于我们的聚合电路，我们寻求一个非常简单的解决方案。我们定义三个信号：

signal input step_in[7];
signal input signatures[N_SIGS][7];
signal output step_out[7];

高效的 ECDSA 签名由 5 个大整数组成的数组表示。我们附加两个由公钥组成的附加值，以便为每个经过验证过的签名添加公钥检查。因此，每个签名由 7 个值组成。 step_in 和 step_out 信号是上图中的 ，所有剩下的签名都作为作为私有辅助输入。这对于一个应用来说是没有意义的。一个好的练习可能是使用 step_in 一组公钥和消息，而 signatures 仅是签名数据。这对于签名数据应该保持私密的应用来说是有意义的。

批大小是 N_SIGS 。这基本就是折叠的大小，即每个折叠步骤我们聚合的签名数量。可以在我们运行的基准测试中了解折叠步骤的大小与 Nova 的证明和验证时间之间的关系。

https://hackmd.io/mArMuUx5TC2LEcYecc741Q#Benchmark↳

main.circom 电路最终被定义为：

component main { public [ step_in ] } = BatchEfficientECDSAPubKey(10);

根据需要，我们将 step_in 定义为公开变量。现在可以使用以下命令编译它：

$ circom --prime secq256k1 --r1cs --wasm ./main.circom

注意，与 circom 使用的默认素数相比，我们使用了不同的素数。这让我们能够获得一些相当不错的性能提升。可以在第二部分阅读有关我们这样做的原因和方式的信息。永远注意你用来编译电路的素数。

3使用 Nova-Scotia

Nova Scotia 库充当了 circom 编译文件和 Nova 之间的中间件。在我们的例子中，它将帮助我们将多个见证实例折叠到一起，每个实例都验证批量ECDSA 签名。在这里用 nova 定义了该聚合。

https://github.com/dmpierre/nova-browser-ecdsa/blob/main/nova-ecdsa/src/main.rs↳

首先，我们使用 load_r1cs 加载之前编译的 R1CS 文件。然后，我们读取要聚合的所有签名并计算见证。它们存储在一个 .json 中，其结构使用 struct EffSig 定义。

https://github.com/dmpierre/nova-browser-ecdsa/blob/2308b6eb72de35e599fe1d562a9ff18a8a76225f/nova-ecdsa/src/main.rs#L14

然后，我们定义起始公开输入，即  - 见上文。由于我们的 step_in 需要一个签名和公钥，因此使用相关值初始化 start_public_input 。然后设置所有辅助/私有输入。我们有 iteration_count 个折叠步骤，其中每个包含 per_iteration_count个签名。

https://github.com/dmpierre/nova-browser-ecdsa/blob/2308b6eb72de35e599fe1d562a9ff18a8a76225f/nova-ecdsa/src/main.rs#L41

现在，我们可以使用 create_public_params 函数从 R1CS 里来初始化公开参数。这将生成证明和验证 SNARK 所需的相关数据。现在可以运行 create_recursive_circuit 了。这将生成一个 recursive_snark ，证明聚合在一起的所有签名的有效性。这个 recursive_snark 有一个 verifier() 方法，我们随后调用该方法来验证证明的有效性。我们使用初始公开输入以及此递归 SNARK 所包含的折叠步骤数作为 verify 方法的输入。

4写我们的wasm

将 Nova SNARK 移植到浏览器几乎就是复制粘贴我们上面所做的事情。我们建了一个名为 nova-ecdsa-browser 的文件夹。在 wasm.rs 中，我们定义了三个不同的函数 generate_params 、 generate_proof 和 verify_compressed_proof 。其中每一个都对应于一个上述的步骤。一个细微的区别是我们还在浏览器中生成Spartan压缩证明。

由于我们希望在浏览器内进行调试，因此最有用的事情之一就是在每个函数的开头调用 init_panic_hook() 。这将使控制台记录相关错误消息而不是 error: unreachable 成为可能。此后我们删除了这些行，但请记住，这可能是调试代码的有用方法。

准备就绪后，我们可以运行以下命令：

$ wasm-pack build --target web --out-dir ../packages/nova-ecdsa-browser-pkg

这将生成一个可供 Web 应用使用的Typescript包。由于我们是在一个大库的上下文中工作，因此我们将其输出到 packages 工作区中的单独文件夹中。

5集成到web应用中

现在，我们切换到 apps/web 并通过将以下行添加到 package.json 来安装 Nova 签名聚合包：

{
    ...
    "nova-ecdsa-browser": "workspace:*",
    ...
}

为了在 Nova 工作时不阻塞浏览器的主线程，我们将使用 Web Worker。我们为每个相关步骤定义一个worker：生成公开参数、计算证明并验证它。每部分代码都存储在 workers/ 文件夹中。最终，我们还在 hooks/ 文件夹中编写了相关的react hooks。当用户请求时，这些hooks将负责用相关数据调用workers。

https://hackmd.io/KxG-BH1nQPGpdRxz6M50hw?view↳

一个可能错误的小贴士

1.SharedArrayBuffer transfer requires self.crossOriginIsolated

当得到下面异常时：

workerHelpers.js:98 Uncaught (in promise) DOMException: Failed to execute 'postMessage' on 'Worker': SharedArrayBuffer transfer requires self.crossOriginIsolated.

next.config.js中, 确保加入:

async headers() {
return [
  {
    source: '/(.*?)',
    headers: [
      {
        key: 'Cross-Origin-Embedder-Policy',
        value: 'require-corp',
      },
      {
        key: 'Cross-Origin-Opener-Policy',
        value: 'same-origin',
      },
      {
        key: 'Access-Control-Allow-Origin',
        value: '*',
      }
    ],
  },
]
}

Part2用Nova聚合secp256k1上的ECDSA签名

Nova 是一个递归证明系统, 基于折叠方案构建。它是使用椭圆曲线的一个2-cycle来实现的, 这带来了效率上的增益。当一条曲线的基域 是另一条曲线的标量域 ，并反之亦然时，就会出现 2-cycle。证明者将在 上工作，验证者的工作则将在 上进行。Halo2 的文档是一个很好的入门读物。

https://zcash.github.io/halo2/background/curves.html#cycles-of-curves↳

以太坊使用 secp256k1 曲线。恰好 secp256k1 和 secq256k1 之间存在cycle（secp/secq）。secp256k1 的基域是 secq256k1 的标量域, 反之亦然。

可以在此处看到 的基域有及其阶（的）等于 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141。

因此, secq 的基域将有 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 ，且有  0xfffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f

https://neuromancer.sk/std/secg/secp256k1

这对于我们这个签名聚合项目来说非常有趣。我们可以让 Nova 在一个曲线cycle上工作，其中证明 secp256k1 签名的成本可以被减少到大约 3k 约束 - 使用 Personae 设计的高效 ECDSA 格式。与折叠相结合，这将有助于签名聚合达到足以引人注目的性能水平。

https://personaelabs.org/posts/efficient-ecdsa-1/↳

6在 Nova 中实现 secp/secq

Nova 是用 Rust 实现的。它非常灵活，允许用户根据他们的想要达到的特定用例选择任何曲线cycle。由于我们想要聚合 secp256k1 ECDSA 签名，因此我们必须将 secp/secq 集成到其中。Nova 代码库需要曲线来实现 Group trait。这并不太难。之前已经对初始代码库之外的曲线（即来自 halo2curves 库的曲线）完成了该工作。

https://github.com/microsoft/Nova/blob/bd56514f3a5364553a31979aa1c1c480aa9e20cd/src/traits/mod.rs#L18

https://github.com/microsoft/Nova/pull/181

https://github.com/privacy-scaling-explorations/halo2curves↳

由于 secp 已经通过 halo2curves 实现，所以我们首先实现 secq：实现 secq 时需要对换 secp 的基域和标量域。这也没什么神奇的！因此，我们向 halo2curves 库提了一个 PR 并已经得到合并。此后发布了一个新的 halo2 crate，因此现在已经可以在 cargo install 后使用此cycle了。

https://github.com/dmpierre/halo2curves/blob/c0d422b4c943507bdc886786527a0d46c4ebc00a/src/secq256k1/mod.rs

https://github.com/privacy-scaling-explorations/halo2curves/pull/65↳

7写签名聚合电路

如前所述，在 secp/secq cycle中，证明者的工作将在 secq 的域上进行。事实上，Nova 中的折叠需要中的群操作。在我们的例子中， 是由 secp256k1 的点定义的群。虽然  是 secp 的基域，但  的阶将定义 secp 的标量域。在 secp 与 secq 的cycle上下文中，回想 secp 的标量域（其中   ）是 secq 的基域 (  ）。当在  (secq 的基域)中表达约束时，即可有效地在  中表达群操作：。因此，我们必须在 secq 的基域上编写签名聚合电路。

已经存在一个 circom 的fork可以做到这一点。它实现了 secq prime 并可以在其上编译电路：只需加上标志 --prime secq256k1 即可。

https://github.com/DanTehrani/circom-secq↳

https://github.com/iden3/circom/commit/0fd517296523d295301e05906509779bee9ad6ad

为了证明签名，我们利用了此处实现的高效 ECDSA 格式并添加了公钥检查。总体而言，这实现起来是相当快的。 N_SIGS 参数定义了每个折叠步骤要聚合的签名数量。我们在应用中固定每个步骤 10 个签名，从而形成了具有 30390 个非线性约束的电路。

https://github.com/personaelabs/spartan-ecdsa/blob/main/packages/circuits/eff_ecdsa_membership/eff_ecdsa.circom↳

https://github.com/dmpierre/nova-browser-ecdsa/blob/main/nova-ecdsa/src/data/circuits/batch_efficient_ecdsa_pubkey.circom↳

Nova scotia是一个可以帮助我们轻松用起来Nova的库。

https://hackmd.io/mArMuUx5TC2LEcYecc741Q↳

问题是，使用 Nova 时编写电路的方式略有不同。你现在正在折叠：多个满足的R1CS 实例（或者读见证，如果这更好理解的话）将被打包在一起。Nova 要求这些打包实例有一个链接，将每个实例与下一个实例相关联。这是因为我们是在增量可验证计算的世界中运作，在这个世界中，一个东西首先得到证明，然后增量逐步地与另一个东西相关联。将每个实例与下一个实例联系起来的是公开信号：SNARK 计算中涉及的每个步骤的输入和输出。

nova scotia唯一要求你做的就是定义公开的 step_in 信号。由于电路的所有输出都是公开的，因此你可以自由选择喜欢的输出的名称。不过注意，由于步骤  的输出将是步骤  的输入，请确保你的输出信号匹配 step_in 所期望的信号。

所有其他非公开输入信号都称为辅助输入。nova scotia没有它们的命名约定。辅助输入包含你可能不希望验证者访问的私有数据。在我们的例子中，如果要聚合某些敏感应用的签名，可以定义 step_in 输入以包含公钥和消息，辅助输入是签名数据本身。

请注意，由于 Nova 的递归开销（利用递归性必须付出的开销），必须在大小为 20k R1CS 约束以上的电路中使用它才是有益处的。这种递归开销源自证明者除了证明电路的有效执行之外还必须做的额外工作。注意Nova 最有趣的事情之一就是这种递归开销是恒定的：无论电路大小如何，为递归付出的代价将保持不变！

8基准测试

我们使用 Nova 对 ECDSA 签名聚合进行了基准测试。该基准测试使用 circom 的 wasm 见证生成代码。这里的想法是去评估 Nova 在处理不同折叠步骤的数量和每个步骤的大小时聚合签名的速度能有多快。

使用 circom 的 wasm 见证生成器在 secp/secq 上用 Nova 聚合 ECDSA 签名，不生成压缩的Spartan证明。在 M2 Pro 上运行的基准测试。

我们可以非常清楚地看到证明者和验证者时间之间的权衡。更短的折叠步骤会导致验证者时间更快，但证明时间更长。相反，更长的折叠步骤会导致证明时间更短，但验证者成本更高。它还让我们很好的了解了可以期望浏览器内聚合的速度。当前部署的应用似乎根据运行该应用机器类型的不同在每秒 2 到 6 个签名之间波动。

我试图让 c++ 见证生成器与 secq 一起工作。虽然它编译得很好，但在尝试计算见证时我无法解决 Illegal Instruction: core dumped 错误。我不太确定这里发生了什么，我愿意接受建议！

9注意事项

如果你正在考虑向 Nova 添加曲线cycle并使用 circom 在其上编写自己的电路，则需要考虑以下几点：

1. 你需要在 circom 中实现自己的素数。secq fork 以及这个 PR 就是一个很好的例子来说明如何做到这一点。

https://github.com/DanTehrani/circom-secq↳

https://github.com/iden3/circom/pull/179/commits/9276273a5121eed7d4e3dcad9f3f1b3465d03ebe

2. 你可以使用该库为你的 wasm 生成器生成正确的参数。

   https://github.com/iden3/ffwasm#usage

3. 我不知道为什么，但使用 ffiasm 生成 intel 汇编并不会得到与 circom 生成的签名相同的签名，最终会出现 too many arguments to function ‘void Fr_str2element(PFrElement, const char*)’ 错误。我必须使用 diff 手动调整 cpp 文件。见这里。

https://github.com/iden3/circom/pull/179/commits/023bafee74f7e714ac25ec23fca5be1181b8814b

4. 我没能让 circom 的 c++ 见证生成器工作。尽管 make 运行良好，但在见证计算时我仍然会收到 Illegal insruction: core dumped 错误。我认为这是一个非常容易实现的目标，实现后就可以获得更好的基准测试性能。
5. circomlib 是一个有用电路的工具包，在编写时考虑了特定的素数大小。请记住，如果你添加的素数不适合它，则很多电路则将需要部分或完全的重写。