Optimizing ECDSA Signature Verification: Exploring Zero-Knowledge Proofs in the Sei Giga Blockchain

Following Sei Protocol’s recent Giga announcement outlining the path to achieving 5 gigagas per second on the EVM, we identified several key areas for optimization. One bottleneck in the existing Sei Giga protocol prototype that jumped out was the issue of signature recovery and verification. We wondered, given the requirement to keep ECDSA for compatibility with Ethereum wallets, could we use ZK to solve this bottleneck? Could we have a block producer recover the public key, verify blocks and submit a proof so the executor only needs to verify a proof rather than N signatures? Let's start by defining an ECDSA signature, using the NIST [Che+23] notation, in the context of the Sei Blockchain.
Signature Content
Curve: secp256k1 over Fp,p=2256−232−977.
Generator: G of prime order n.
Private key: d{1,,n−1}.
Public key: Q=dG.
Inputs: Message m, hash z=Hash(m)modn, private key d.
Output: Signature ( r,s,v ).
Signing
- z=Hash(m)modn.
- Choose random k{1,,n−1}.
- R=kG=xR,yR.
- r=xRmodn (if r=0, retry).
- s=k−1(z+rd)modn (if s=0, retry).
v{27,28} typically in Ethereum picks the sign of yR. Signature is (r,s,v).
Recovery
Given (r,s,v) and z.
- Construct R=r,yR using v to choose the sign.
- Q=r−1(sR−zG) mod n.
- Check correctness by verifying (r,s) as above.
Verification
Inputs: m,Q,(r,s,v).
Goal: Check validity of (r,s,v) for message m.
- z=Hash(m) mod n.
- Check r,s{1,,n−1}.
- w=s−1modn.
- u1=(zw)modn, u2=(rw) mod n.
- X=u1G+u2Q=xX,yX.
Valid if xX mod n=r.
If that makes no sense to you, it might be worth running over this very nice introduction to ECDSA [Cor15], but it's not essential to understand it to read the rest of this article. So what does any of this even mean for the Sei network? What was causing an issue? In the Sei blockchain, like a lot of blockchains, we recover the public key from the signature to use for verification rather than sending it along with the signature.
Why do that? Traditionally reducing the data overhead has been seen as a sensible thing to do, and given an ECDSA sig is 65 bytes and the public key in its compressed form is another 33 bytes, the worst case is a 33 byte saving for all transactions. The downside of this tradeoff is that we have to recover the public key for each transaction in order to verify it. Which brings us back to our original question: Can we do all of this quicker in ZK then have an executor validate a single proof rather than multiple signatures?
Attempting to do this sort of thing in ZK isn't entirely novel [Sun+21, 0Da22, Per22b, Har24, mat19] and lots of folks have been interested in this before, but we don't need a unique approach here, just something that works.
There are several approaches to verifying a signature in ZK. We could write custom circuits like lots of other projects have (or merely reuse their work), or we could write some code for a zkVM like SP1 [suc24]. Writing custom circuits is very complex, which we’ll dive into more in a bit. The zkVM approach felt like an easy starting point given the lack of development time needed.. A zkVM allows you to write or compile ordinary programs (e.g., Rust or C code) that run inside a specialized execution environment, which automatically generates a proof that the program was executed correctly. This can significantly reduce development complexity, as you don't need to build every cryptographic detail as custom constraints.
However, the downside is that zkVMs can impose higher overhead for low-level operations like elliptic curve arithmetic on non-native fields, and the general-purpose nature of a zkVM may result in slower proof generation compared to highly specialized, hand-tuned circuits. In a matter of hours we had a working prototype written in rust that was able to verify a signature and generate a proof (of just the verification not the recovery to) in a few seconds. This performance is great and speaks volumes about how useful zkVMs are going to be in the future but is insufficient for us. That means if there's a path forward then it has to be with custom circuits... Before we get to that let's run over ZK quickly.
What do we even mean by ZK? Zero-Knowledge proofs (ZK proofs) allow one party (the prover) to show another party (the verifier) that a certain statement is true, without revealing how it's true or disclosing sensitive details underlying that statement. Formally, let RXW be a binary relation, where X is the space of statements (e.g., "this ECDSA signature is valid") and W is the space of witnesses (e.g., the secret data needed to prove correctness). A statement xX is in the language LR if there exists a witness wW such that (x,w)R. A ZK proof is a protocol between a prover P (who knows w ) and a verifier V, with the following core properties:
- Completeness: If (x,w)R, then an honest prover can convince the verifier that xLR.
- Soundness: If (x,w)R, no cheating prover can falsely convince the verifier that xLR.
- Zero-Knowledge: The verifier learns nothing beyond the fact that x LR; in particular, they gain no additional information about the secret witness w.
In practical terms, this is typically done by constructing and verifying algebraic constraints (e.g., on group elements or polynomials) that prove knowledge of w without revealing it.
There are multiple ZK proving systems, each with its own merits and trade-offs. SNARKs (Succinct Non-interactive ARguments of Knowledge), such as Groth16 or Plonk, typically have very small proof sizes and fast verification times but may require a trusted setup and can be relatively expensive to generate proofs for large circuits. STARKs (Scalable Transparent ARguments of Knowledge) remove the need for a trusted setup and are generally considered more transparent, but their proof sizes can be larger, and verifying them can sometimes be slower, though advances like FRI-based constructions are closing this gap. Bulletproofs are another alternative that do not require a trusted setup, and are typically good for range proofs; however, Bulletproofs can be slower to verify when scaled up to large computations.
Choosing the right ZK system for verifying ECDSA in a high-throughput environment depends on balancing these concerns, proof generation speed, proof size, and trusted setup requirements. In contrast to the zkVM approach, building a custom circuit means expressing the ECDSA verification steps as handcrafted algebraic constraints. This can yield significant performance gains if done carefully, because the circuit is optimized exactly for the operations that matter: point multiplication and addition, modular inversion, and final checks. It also provides tighter control over the size of the proof and the proof generation time.
The downside is that writing and debugging large, specialized circuits is non-trivial; it requires deep familiarity with both elliptic curve arithmetic and the internal workings of your ZK backend (e.g., R1CS vs. PLONK vs. another format). When verifying ECDSA inside a ZK circuit, you need to replicate each mathematical step in an arithmetic-friendly manner. On secp256k1, this involves:
- Field Arithmetic: Performing modular additions, multiplications, and inversions in Fp with p=2256−232−977. Many popular proof systems have a different base field, forcing you to represent each 256-bit operation with custom big-integer gates or decomposition-based constraints.
- Point Operations: Implementing the standard elliptic curve point addition formulas for x1,y1+x2,y2 in a way that is friendly to the ZK constraint system. Point multiplication kG (for random k ) or u1G+u2Q also expands into multiple lower-level operations.
In the context of ECDSA, this entails implementing the core verification relation,
r=?xX mod n for X=zs−1G+rs−1Q
directly inside the ZK circuit. By enforcing these arithmetic constraints over Fp, the proof confirms that (r,s) is a valid signature on z (i.e. the hash of m ) relative to the public key Q, all without revealing the private key d or the ephemeral nonce k. All of these sub-steps can easily produce thousands of individual constraints per signature, which may push proof generation times higher. Batching signatures can make matters worse unless you carefully share repeated steps across multiple instances. The challenge, therefore, is to balance completeness of the ECDSA logic against the computational cost in the circuit, ensuring that you still gain an overall efficiency improvement once the proof is verified on chain.
As we've mentioned before some projects [Per22b] have existing implementations that have been worked on for a long time and have a number of optimisations that should make them relatively performant. By using "efficient ECDSA" [Per22a] Spartan is able to cut over 10,000 constraints from a standard implementation, getting the verification of a single signature down from around 1 s in our benchmarks to 200 ms for the verification of the proof. This is a 5 x improvement on the initial benchmarks but still somewhat insufficient.
While working on the ZK research stream, Engineering continued looking for pure technical solutions to the existing verification bottleneck. Could we fix this through basic code improvements? As it turns out, yes we could. As a result the ZK work has taken a backseat for the time being, despite the promising initial results. The engineering answer is a less complex solution and requires fewer assumptions and simpler security arguments so it's obviously the right answer for now. Is that the end of the road for ZK? Maybe not, if verification becomes a bottleneck again then we'll be back. If the Sei Blockchain moves to a PQC signature scheme then the performance characteristics of the chain today will chain dramatically so it feels feasible that ZK could be back.
Join the Sei Research Initiative
We invite developers, researchers, and community members to join us in this mission. This is an open invitation for open source collaboration to build a more scalable blockchain infrastructure. Check out Sei Protocol’s documentation, and explore Sei Foundation grant opportunities (Sei Creator Fund, Japan Ecosystem Fund). Get in touch - collaborate[at]seiresearch[dot]io
References
[Cor15] Andrea Corbellini. Elliptic Curve Cryptography: a gentle introduction. 2015. URL: https://andrea.corbellini.name/2015/05/17/ elliptic-curve-cryptography-a-gentle-introduction/
[mat19] mathcrypto. Question for cryptographers: SNARK friendly signature protocol. 2019. URL: https://ethresear.ch/t/question-for-cryptographers-snark-friendly-signature-protocol/ 4645/8
[Sun+21] Li Sun et al. zk-ECDSA: zkSNARKs for ECDSA (Part 1). 2021. URL: https://0xparc.org/blog/zk-ecdsa-1.
[0Da22] 0DanielTehrani. Efficient ECDSA signature verification using Circom. 2022. URL: https://ethresear.ch/t/efficient-ecdsa-signature-verification-using-circom/13629/1.
[Per22a] Personae. Efficient ECDSA the case for client-side proving. 2022. URL: https://personaelabs.org/posts/efficient-ecdsa-1/.
[Per22b] Personae. spartan-ecdsa. 2022. URL:https://github.com/personaelabs/ spartan-ecdsa.
[Che+23] Lily Chen et al. "Digital signature standard (DSS)". In: (2023).
[Har24] HarryR. ethsnarks. 2024. URL: https://github . com / HarryR/ ethsnarks.
[suc24] Succinct Labs. SP1. 2024. URL: https://github.com/succinctlabs/ sp1.
Sei Research Initiative (2025). Available at: https://sei.io