Introducing Spartanecdsa
by Personae on cryptographyWe introduce Spartanecdsa, which to our knowledge is the fastest opensource method to verify secp256k1 ECDSA signatures in zeroknowledge.
Spartanecdsa is based on the Spartan NonInteractive Zeroknowledge Proof (SpartanNIZK), which is a proving system in the Spartan zkSNARKs family. Spartan is a family of prover and verifier efficient zkSNARKs for proving R1CS satisfiability, developed by Srinath Setty. SpartanNIZK doesn’t require a trusted setup, and most importantly in the case of ECDSA verification, can work with on elliptic curve where discrete log holds.
This is uncommon in other popular elliptic curve based zkSNARK proof systems. For example, Groth16 and PSE’s fork of Halo2 require pairingfriendly curves like BN254. Zcash’s original Halo2 uses IPA and doesn’t need pairingfriendly curves, but the scalar field of the curve must have high 2adicity for efficient and practical FFT.^{1}
The original implementation of SpartanNIZK uses the curve Curve25519 in its backend; in Spartanecdsa, we use the secq256k1 curve. This choice of curve allows us to perform rightfield arithmetic for ECDSA verification, avoiding the costly range checks that have slowed down previous implementations.
Rightfield arithmetic
In zeroknowledge proving systems, the statements being proven are usually encoded in the scalar field of an elliptic curve. In ECDSA, these statements are mostly elements in $F_p$, the base field of the secp256k1 curve. In our previous attempt to implement zeroknowledge ECDSA verification using Groth16 with snarkjs, we needed to encode elements in $F_p$ to the scalar field of the BN254 curve, which is smaller than $F_p$. This is called wrongfield arithmetic and introduces an enormous number of constraints to ensure all math is being done correctly.
However, in Spartanecdsa, we encode values in $F_p$ without doing any wrongfield arithmetic by using the secq256k1 curve which is defined as follows.
$$ \begin{aligned} y^2 = x^3 + 7 \mod (\mathrm{order\ of\ }F_q) \\ F_q\mathrm{: scalar\ field\ of\ secp256k1} \end{aligned} $$
The Sage code in appendix 2 demonstrates how secp256k1 and secq256k1 relate.
Importantly, secq256k1 has a scalar field order that is exactly the same size as $F_p$, which allows us to do most of the ECDSA arithmetic in rightfield. Furthermore, not only we can do arithmetic in rightfield , but also since secq256k1 forms a cycle with secp256k1, we can construct recursive proofs using the two curves; recursion allows us to combine multiple proofs into a single proof, without incurring additional costs on verification. This property will be important for building applications like ETHDos, and also for verifying proofs on blockchains like Ethereum.^{2}
Tricks from efficientzkecdsa
Although we are now able to do rightfield ECDSA verification by using SpartanNIZK and secq256k1, ECDSA verification consists not only of arithmetic in $F_p$ but also in $F_q$, which is the scalar field of secp256k1 (i.e. the base field of secq256k1).
However, using the technique from our previous post, we can perform the operations in $F_q$ outside of the circuit without sacrificing privacy. By doing so, we are only left with statements that can be proven in the rightfield!
Benchmarks
Public key group membership proof
In the Spartanecdsa Typescript library, we provide an interface to prove membership in a group of ECDSA public keys, without revealing any information about the proven public key. The approximate benchmark of this proving method is as follows.
Benchmark  # 

Constraints  8,076 
Proving time in browser  4s 
Proving time in Node.js  2s 
Verification time in browser  1s 
Verification time in Node.js  300ms 
Proof size  16kb 
 Measured on a M1 MacBook Pro with 80Mbps internet speed
 Both proving and verification time in browser includes the time to download the circuit
The proving time has improved by 10x from our previous implementation. We believe that this magnitude of improvement will open the doors for more applications using membership proofs to be developed.
However, there are yet some difficulties in practice. Let’s say you want to create an anonymous forum where you can only post if you own an NFT of a particular collection. First, the Ethereum addresses of the NFT owners must to collected to create a group, which the users can prove membership to. However, even though ownership of an NFT is a public record, the ECDSA public keys of those addresses are not always accessible. Since an Ethereum address is a hash of a public key, the public key is only accessible only if at least one transaction has been sent from that Ethereum address; if there is a transaction from the address, the public key can be extracted from the ECDSA signature of the transaction. While if the address has no transaction record, then the public key of that address won’t be publically accessible information.
To counter this issue, in the case of our anonymous form example, we can require the users to submit their public key when they sign up to the forum, only if the address of the user has never sent a transaction before (i.e. if the public key of the address is inaccessible) (the user should send their public key using Tor for complete anonymity). The forum adds the submitted public key to the group, so the user can prove membership anonymously. However, if the user creates a post immediately after they submit their public key, the post and the submitted public key can be linked. So the forum should only allow the user to make their first post after some time has passed (e.g. 24h~), to protect the anonymity of the user.
Ethereum address group membership proof
As shown in the above example, the inaccessibility of public keys requires us to implement a design that might not lead to the best user experience. To counteract this, instead of proving membership to a group of ECDSA public keys, we could prove membership to a group of Ethereum addresses. Spartanecdsa provides an interface to do this, which has the following approximate benchmark.
Benchmark  # 

Constraints  159,775 
Proving time in browser  60s 
Proving time in Node.js  40s 
Verification time in browser  6s 
Verification time in Node.js  1s 
Proof size  38kb 
 Measured on a M1 MacBook Pro with 80Mbps internet speed
 Both proving and verification time in browser includes the time to download the circuit
As the benchmark shows, proving membership to an Ethereum address group takes significantly longer. This is because we need to do a Keccak hash to convert a public key into an Ethereum address during proving.
In some applications, proving can be done in the background while the user does another action (e.g. entering longform text), which will be a way to manage the long proving time. However, the underlying high cost of proving isn’t the best foundation to build a great user experience.
In summary, Spartanecdsa provides two different proving methods with different tradeoffs, for application developers to choose.
Future work
Speeding up Keccak
Managing a group of Ethereum addresses instead of the inner public keys is easier, and will result in a better user experience. To bring down the proving time in such a setup, we need to reduce the number of Keccak constraints. One possibility is to use the lookup argument. Keccak consists of numerous bitwise XORs, and lookups allow us to arithmetize them in an efficient way.
Onchain verification
Although Spartanecdsa made a significant leap in prover efficiency for ECDSA verification, the proofs are too large to be verified on blockchains like Ethereum. To do onchain verification, the proofs need to be further compressed. Fortunately, there is a significant amount of opensource effort being made toward onchain verifiable proof generation to realize zkEVMs. We imagine Spartanecdsa leveraging these efforts to make onchain proof verification a possibility. Furthermore, as mentioned above, we can also use recursion to combine proofs to make perproof cost verification lower and to make onchain verification more affordable.
Credit roll
Thanks for reading! Names within each group are sorted alphabetically by first name.
 Contributors: Dan Tehrani, Lakshman Sankar, Vivek Bhupatiraju
 Post writers: Dan Tehrani
 Post reviewers: Vivek Bhupatiraju, Lakshman Sankar
 Upstream work: Nalin Bhardwaj, Srinath Setty
Appendix 1: Under the hood
The following is an incomplete list of the components which comprise Spartanecdsa.
Upstream dependencies
Spartan
We use a fork of Spartan that operates over the secq256k1 curve.
Circom
Circom is a language for defining arithmetic circuits. We use a fork of Circom that arithmetize over the secp256k1 base field (i.e. secq256k1 scalar field).
NovaScotia
NovaScotia is a Circom R1CS compiler developed by Nalin Bhardwaj. We use a fork of NovaScotia to compile Circom circuits into a binary format that Spartan can process. We slightly modify NovaScotia to be compatible with secq256k1.
Our implementations
Secp256k1 elliptic curve operations in Circom
The Secp256k1 elliptic curve circuits were inspired by the implementation of the Halo2 ECC gadget.
Secq256k1 hashtocurve We implement hashtocurve for the secq256k1 curve, following the specification of draftirtfcfrghashtocurve10. hashtocurve is used for generating secure Pedersen commitment generators, which are used in Spartan.
Poseidon Poseidon is a zkfriendly hash function. We implement and instantiate Poseidon which hashes Secp256k1 field elements. The implementation was inspired by Neptune, a Poseidon implementation from Filecoin.
Appendix 2: Secp/Secq cycle in Sage
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
q = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
# Secp256k1
P = GF(p)
aP = P(0x0000000000000000000000000000000000000000000000000000000000000000)
bP = P(0x0000000000000000000000000000000000000000000000000000000000000007)
Secp256k1 = EllipticCurve(P, (aP, bP))
Secp256k1.set_order(q)
# Secq256k1
Q = GF(q)
aQ = P(0x0000000000000000000000000000000000000000000000000000000000000000)
bQ = P(0x0000000000000000000000000000000000000000000000000000000000000007)
Secq256k1 = EllipticCurve(Q, (aQ, bQ))
Secq256k1.set_order(p)
print(
"Secp256k1 group order == Secq256k1 base field order:",
Secp256k1.order() == Secq256k1.base_field().cardinality()
)
print(
"Secp256k1 base field order == Secq256k1 group order:",
Secp256k1.base_field().cardinality() == Secq256k1.order()
)

If your field does not have high 2adicity, you can use ECFFT as introduced by StarkWare. It is slower in complexity than raw FFT but still far more efficient than naive $O(n^2)$ algorithms. A more gentle overview of the algorithm is provided by William Borgeaud here. ↩︎

It is important to note that unlike the Pasta curves used in Halo2,the secp/secq curve cycle is not FFT friendly. Therefore it is not compatible per se with most of the FFTbased recursive systems unless ECFFTs can be used. ↩︎