owned this note
owned this note
Published
Linked with GitHub
# Aggregating secp256k1 ECDSA with Nova
## Introduction
Nova is a recursive proof system, built from a folding scheme. It has been implemented using a a 2-cycle of elliptic curves, which brings to the table efficiency gains. A 2-cycle occurs when the base field ($F_p$) of a curve is the scalar field ($F_q$) of another and vice-versa. While the prover will work over $F_q$, the verifier's work will take place over $F_p$. A good primer reading on this is Halo2's [documentation](https://zcash.github.io/halo2/background/curves.html#cycles-of-curves).
Ethereum leverages the `secp256k1` curve. It happens that there exists a cycle (secp/secq) between `secp256k1` and `secq256k1`. The base field of `secp256k1` is the scalar field of `secq256k1` and vice-versa. You can see [here](https://neuromancer.sk/std/secg/secp256k1) that secp's base field has $p=\mathrm{0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f}$ with its order (the $q$ of $F_q$) equal to $\mathrm{0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141}$. Hence, secq's base field will have $p=\mathrm{0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141}$ and $q=\mathrm{0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f}$.
This is quite interesting for our signature aggregation project. We can get Nova to work on a cycle of curve where the cost of proving `secp256k1` signatures gets cut to approximately 3k constraints - using the efficient ECDSA format [devised by Personae](https://personaelabs.org/posts/efficient-ecdsa-1/). Combined with folding, this will help signature aggregation reach compelling performance levels.
## Implementing secp/secq in Nova
Nova is implemented in Rust. It is quite flexible as it allows users to choose whatever curve cycle following the specific usecase they are targetting. Since we want to aggregate `secp256k1` ECDSA signatures, we had to integrate secp/secq into it. The Nova codebase requires curves to implement the `Group` [trait](https://github.com/microsoft/Nova/blob/bd56514f3a5364553a31979aa1c1c480aa9e20cd/src/traits/mod.rs#L18). This isn't too difficult. It has been done [before](https://github.com/microsoft/Nova/pull/181) for curves outside of the initial codebase, namely from the [`halo2curves`](https://github.com/privacy-scaling-explorations/halo2curves) repo.
Since secp is already implemented with `halo2curves`, we first worked to implement [secq](https://github.com/dmpierre/halo2curves/blob/c0d422b4c943507bdc886786527a0d46c4ebc00a/src/secq256k1/mod.rs): it required to switch secp's base field and scalar field when implementing secq. Nothing fancy! Hence, we made a [PR](https://github.com/privacy-scaling-explorations/halo2curves/pull/65) to the halo2curves repo and got it merged. A new `halo2` crate has been released since, so you can now use this cycle after having `cargo install`ed it.
## Writing a signature aggregation circuit
As described earlier, on the secp/secq cycle the prover's work will occur over secq's base field. Indeed, folding in Nova requires group operations in $G_1$. In our case, $G_1$ is the group defined by the set of points of secp256k1. While $F_1$ is the base field of secp, the order of $G_1$ will define the scalar field of secp. In the context of secp's cycle with secq, recall that the scalar field of secp (where $q=|G_1|$) is the base field of secq ($F_2$). Well, it happens that expressing group operations in $G_1$ can be done efficiently when expressed as constraints in $F_2$: secq's base field. Hence, we will have to write our signature aggregation circuit over secq's base field.
There already exists a [fork](https://github.com/DanTehrani/circom-secq) of circom that does this. It [implements](https://github.com/iden3/circom/commit/0fd517296523d295301e05906509779bee9ad6ad) the secq prime and makes it possible to compile circuits over it: simply provide the flag `--prime secq256k1`.
For proving signatures, we leveraged the efficient ECDSA format, implemented [here](https://github.com/personaelabs/spartan-ecdsa/blob/main/packages/circuits/eff_ecdsa_membership/eff_ecdsa.circom) and added a public key check. This is overall rather quick to [implement](https://github.com/dmpierre/nova-browser-ecdsa/blob/main/nova-ecdsa/src/data/circuits/batch_efficient_ecdsa_pubkey.circom). The `N_SIGS` parameters defines how many signatures we want to aggregate per folding step. We settled on 10 signatures per step in our app, resulting in a circuit with 30390 non-linear constraints.
[Nova scotia]() is a library to help us onboard onto Nova without too much hassle.
The thing is that the way you will write circuits slightly differs when using Nova. You are now *folding*: multiple statisfied R1CS instances (or read witnesses if that's easier) will be packed together. Nova requires from those packed instances to have a link, relating each of the instance to the following one. This is because we operate in the Incrementally Verifiable Computation world, where things are first proved and then linked to another incrementally. What will relate each instance to the next one are public signals: the *inputs* and *outputs* of each of the *steps* involved in the computation of our SNARK.
The only thing that nova scotia requires from you is to define a public `step_in` signal. Since all the outputs to a circuit are public, you are free to choose whatever name you like for your outputs. Still, beware that since the outputs of step $t$ will be the inputs of step $t+1$, ensure that your output signal matches what `step_in` expects.
All other non-public input signals are dubbed *auxiliary inputs*. There is no naming convention for them in nova scotia. Auxiliary inputs consists of private data that you might not want the verifier to access. In our case, if one were to aggregate signatures for some sensitive application, he could define `step_in` inputs to consist of public keys and messages with auxiliary inputs being the signature data itself.
Be aware that due to Nova's recursive overhead (a cost that you have to pay to leverage recursivity), using it starts to be beneficial at circuits of size 20k R1CS constraints. This recursion overhead stems from the additional work the prover will have to do on top of proving the valid execution of your circuit. Note that one of the most interesting thing with Nova is that this recursion overhead is constant: whatever the circuit size, the price to pay for recursivity will remain the same!
## Benchmark
We ran a benchmark exercise on ECDSA signature aggregation using Nova. This benchmark is using circom's wasm witness generation code. The idea here is to evaluate how fast Nova can get at aggregating signatures while playing on the number of folding steps and the size of each of those.
---
Folding steps | Sigs per step | Prover time (s) | Verifier time (ms) | Sigs / second
|---|---|---|---|---|
30 | 10 | 16,71 | 263 | 18
15 | 20 | 12,34 | 376 | 24
6 | 50 | 9,64 | 696 | 31
3 | 100 | 8,44 | 1000 | 36
*Aggregating ECDSA signatures with Nova on secp/secq, using circom's wasm witness generator and without generating a compressed spartan proof. Benchmark running on an M2 Pro.*
---
We can see the tradeoff between prover and verifier time quite clearly. Smaller folding steps result in faster verifier time but higher proving times. Conversely, fat folding steps end up with a smaller proving time but higher verifier costs. It also gives a good idea of how fast we can expect in-browser aggregation to be. The current deployed app seems to oscillate betweeen 2 to 6 signatures per second following what kind of machine is running the app.
I tried to get the cpp witness generator to work with secq. While it compiled fine, I could not get around an `Illegal Instruction: core dumped` error when trying to compute witnesses. I'm not too sure of what is going on here and I'm opened to suggestions!
## Caveats
If you are considering to add a curve cycle to Nova and write your own circuits on top of it with circom, here are a few things to consider:
1. You will need to implement your own prime within circom. A good example on how to do this are both the [secq fork](https://github.com/DanTehrani/circom-secq) and [this PR](https://github.com/iden3/circom/pull/179/commits/9276273a5121eed7d4e3dcad9f3f1b3465d03ebe)
2. You can generate the correct parameters for your wasm generator using [this](https://github.com/iden3/ffwasm#usage) library.
3. I'm not sure why, but generating intel assembly using `ffiasm` would not give the same signature as the ones that are distributed with circom, ending up in errors as `too many arguments to function ‘void Fr_str2element(PFrElement, const char*)’`. I had to manually tweak the cpp file using `diff`. See [this](https://github.com/iden3/circom/pull/179/commits/023bafee74f7e714ac25ec23fca5be1181b8814b).
4. I did not manage to get circom's cpp witness generator to work. Although `make` runs fine, I would still get an `Illegal insruction: core dumped` error at witness calculation time. I think this is a very low hanging fruit to get much better benchmarks.
5. `circomlib`, a toolkit of useful circuits, is written with a particular prime size in mind. Keep in mind that if the prime you are adding does not fit it, several circuits will need parital or complete rework.