Optimizations
Implementation · how the circuit was optimized — profile where the constraints concentrate, then reduce exactly those.
A static circuit already avoids the general-purpose overhead a zkVM carries (Design choices), but that head start was not enough on its own. The first version of the circuit was still large and slow, and its cost grew steeply with every added signature. Reaching production speed required profiling exactly where the constraints went, then rewriting the two components that dominated — cutting the circuit 4.3× smaller and making batching scale far more gently. This page follows that work in order: the profile, the two reductions, and the result.
The problem
The first version of the circuit (bucket size N = 16) contained ~6.32M constraints, and a single proof took ~10 minutes; each additional signature added a further ~350K constraints. Profiling the R1CS count component by component shows where that cost concentrated:
| Component | Used in | Constraints | Share |
|---|---|---|---|
| SHA-512 | signature verification (per-slot hash) | 3,620,210 | 57.3 % |
| EC operations | signature verification (MSM, 32 points) | 2,388,452 | 37.8 % |
| SHA-256 | input binding (witness hash) | 190,615 | 3.0 % |
| Fiat-Shamir challenges | batching | 139,814 | 2.2 % |
| Prefix binding | domain separation | 3,921 | 0.1 % |
Two components account for almost the entire circuit: SHA (signature verification plus input binding) at ~60 % combined — ~581 constraints per hashed byte — and elliptic-curve operations at ~38 %. These are the two the optimization targets.
Reducing SHA-512
SHA-512 is unavoidable in Ed25519: every signature check computes h = SHA-512(R ‖ A ‖ msg) — one full hash per slot, per update. Its circuit cost is concentrated in the bitwise operations of the compression function, which is where the reduction is applied:
- Re-structured gnark's SHA implementation to save bitwise operations: range checks are enforced once in bulk rather than per operation, with algebraic rewrites of the inner operations.
- Hash exactly the signed bytes, keeping the surrounding proto-encoding out of the circuit entirely.
The constraint cost per hashed byte falls from ~581 to ~137 (4.24×), taking the circuit's SHA-512 total from 3.62M down to ~854K constraints.
Reducing the elliptic-curve cost
Ed25519 verification reduces to a curve-equation check: each signature asserts [Sᵢ]G = Rᵢ + [hᵢ]Aᵢ — one equation per signature, N per update. The circuit applies batch verification: each equation is scaled by a random per-slot Fiat-Shamir challenge zᵢ and summed into a single combined equation:
(Σ zᵢSᵢ)·G = Σ zᵢ·Rᵢ + Σ (zᵢhᵢ)·Aᵢ
Because the zᵢ are random, invalid signatures cannot cancel within the sum: a single bad signature breaks the combined equation except with negligible probability. The left side is one scalar multiplication; the batch reduces to a single large multi-scalar multiplication (MSM) over the 2N points {Rᵢ, Aᵢ}. Inside a gnark circuit this MSM is the bottleneck — computed directly it costs ~72.6K constraints per point, growing linearly with the batch.
The reduction implements Liam Eagen's technique (ePrint 2022/596):
- Rather than computing the MSM in the circuit, the circuit verifies an MSM result.
- That result is computed off-circuit and supplied through a gnark hint; hint outputs are unconstrained, so the computation itself costs nothing in the circuit.
- The technique then verifies the supplied result by evaluating a prover-supplied witness at a random challenge point — a dishonest hint fails this check with overwhelming probability.
Verifying the result rather than computing it is dramatically cheaper: the EC cost falls from 2,388,452 to 302,646 constraints (~7.9×), and it becomes near-constant in batch size — ~7K constraints per additional signature, against ~145K for in-circuit MSM.
The result
The same profile at N = 16, with both reductions applied, totals 1,469,587 constraints:
| Component | Constraints | Share | vs first version |
|---|---|---|---|
| SHA-512 | 853,501 | 58.1 % | reduced 76 % |
| ECIP verify (EC ops) | 302,646 | 20.6 % | reduced 87 % |
| SHA-256 | 190,615 | 13.0 % | unchanged |
| Fiat-Shamir challenges | 139,814 | 9.5 % | unchanged |
| Prefix binding | 3,921 | 0.3 % | unchanged |
The circuit shrank from ~6.32M to ~1.47M constraints — 4.3× fewer (−77 %). Batching now scales far more gently: each additional signature costs ~65K constraints instead of ~350K (a 5.4× per-slot improvement), with elliptic-curve verification a near-fixed cost rather than a linear one.
Measured end-to-end: Benchmark.