Efficient ECDSA & the case for clientside proving
by Personae on cryptographyIn this post, we introduce our research improving private ECDSA signature verification, stemming from this ETHResearch post and implemented in this repository. We also introduce the importance of clientside proving to unlock the full potential of zeroknowledge cryptography.
There will be some math in this post! It might look scary! But the key insights of the method are simple and should teach you some fun cryptography.
Motivation
ECDSA & ring signatures
Digital signatures are a key tool in publickey cryptography, where every user $u$ has a public key $pk_u$ and private key $sk_u$. In particular, the validity of a digital signature $s$ on message $m$ generated by $sk_u$ can be verified by anyone with access to $pk_u$. As a result, digital signatures allow us to verify the authenticity and integrity of messages or documents. If all messages are attached with a signature from some trusted party, then messages cannot be changed without invalidating the attached signature.
The Elliptic Curve Digital Signature Algorithm, or ECDSA for short, is the signature algorithm used in blockchains like Ethereum and Bitcoin. In particular, each address on these chains is the hash of an ECDSA public key, which itself is a secp256k1 elliptic curve point. And we sign all transactions with our ECDSA public key, which verifies their authenticity and integrity.
Proving you know one of the private keys in a group of public keys without revealing it is a necessary primitive for many of the anonymous speech applications Personae is interested in (heyanon!, storyform, HeyAnoun). Surprisingly, this simple extension requires much heavier cryptographic machinery than a normal signature; there’s an entire field of research dedicated to this problem called ring signatures. Unfortunately these methods aren’t compatible with Ethereum/Bitcoin’s ECDSA keys out of the box, so we opt to use an even more overpowered tool in zkSNARKs.
The zkSNARK method, first implemented by 0xPARC, privately inputs a group member’s public key $pk$ and a signature $s$, and publicly inputs the entire group $G$ (usually succinctly as a Merkle root). The circuit verifies $s$ was generated from $pk$ AND that $pk$ is in the group $G$. Sounds simple enough!
Unfortunately, the math for the signature verification is very SNARKunfriendly. In particular, there’s a lot of “wrong field arithmetic” — the necessary operations happen over the base field of the secp256k1 curve which is different from the scalar field of the curves used in snarkjs. If that means nothing to you, don’t worry – it just means we have a huge blowup in constraints to make sure all of our elliptic curve math is done correctly. And if that also means nothing to you, don’t worry – it just means computing a proof is very computation and memoryintensive, requiring ~1GB of proof metadata and ~5 minutes of browser computation on a MacBook.
Clientside proving
Okay, so if our gigachad friends at 0xPARC already implemented this method, why don’t we just use that for our applications? Well, a 5 minute proving time that only works on highend laptops is far from a viable UX. And generating proofs can’t just be offloaded to the cloud – for full privacy it’s necessary these proofs are computed on the user’s device. Otherwise you’ll need to send your plaintext public key to a server to generate your proof, which grants it the power to break your anonymity if it wishes^{1}. There’s some halfserver halfclient models that have been deployed; we analyze those further in the appendix of this post.
But we claim any solution with a server obscures the true unlock of zeroknowledge cryptography. Another framing of the importance of clientside proving is that it allows people to generate authoritative claims of identity without any trusted party, a power us measly humans didn’t have until this technology started to become practical. This means the user can have full custody over their personal data instead of trusting other (potentially misaligned) institutions to manage and verify it.
But the straightforward ZK ECDSA construction is just too expensive for everyone to run on their devices, especially mobile phones. And as more of identity moves onchain with innovations in DeSoc and SBTs, private ECDSA group membership will be an increasingly important tool in maintaining anonymity and owning more of our identity. And so starting with the ideas in this post, we’ve been on a journey to keep bringing the proving cost down until all devices can easily generate a proof.
Notation
ECDSA signature verification has a bunch of moving parts. All operations are on elliptic curve points and happen modulo $n$, but you can mostly ignore those details for the sake of this post. The main fact you’ll need is that a generator in elliptic curve math is equivalent to “1” in normal math. A more indepth guide can be found here. Okay, these are each of the variables we’ll need:
Term  Definition 

$G$  generator 
$n$  order of group 
$k$  random number $\lt n$ 
$R$  $k * G$ 
$r$  xcoordinate of $R$ 
$a$  private key 
$Q_a$  public key defined as $a * G$ 
$m$  hash of message 
$s$  $k^{1} (m + ar) \mod n$ 
$s^{1}$  $k (m + ar)^{1} \mod n$ 
Here are specific circom
functions from 0xPARC’s circomecdsa
that we reference:
Function  Inputs  Description 

BigMultModP 
a, b, p 
compute $a * b \mod p$ 
ECDSAPrivToPub 
privkey 
multiply $G$ by privkey 
Secp256k1AddUnequal 
a, b 
add secp points a and b 
Secp256k1ScalarMult 
scalar, point 
multiply point by scalar 
An ECDSA signature from public key $Q_a$ on the hashed message $m$ is the pair $(r, s)$. The verification equation^{2} checks if:
$$ R = ms^{1} * G + rs^{1} * Q_a $$
which you can follow in 0xPARC’s original implementation. To get better intuition for this signature algorithm, we recommend you check correctness – that is, verify this equation will pass for a valid signature $(r, s)$!
If you follow the original code and/or work through the above equation, you’ll see that we need a total of 2 BigMultModP
, 1 ECDSAPrivToPub
, 1 Secp256k1ScalarMult
, and 1 Secp256k1AddUnequal
inside of the circuit, for a total of 1,508,136 constraints (the 0xPARC code also inverts $s$ but you can pass $s^{1}$ in so we will ignore it). We want to remove/optimize as many of these functions as possible!
Key insights
Take computation out of the SNARK
Our first insight was that parts of the ECDSA signature verification equation could be taken out of the SNARK without sacrificing privacy. For simplicity we first rewrite the signature verification equation as
$$ s * R = m * G + r * Q_a $$
If we look carefully at the definition of $R$, we see it is just a random element on the curve. And $m$ is publicly known as we are always verifying a signature on a specific message. And so moving $R$, $r$, and $m$ outside of the SNARK shouldn’t reveal anything about our user’s public key ^{3}. We further rewrite the equation as
$$ \begin{aligned} s * R  m * G &= r * Q_a \\ r^{1}s * R  r^{1}m * G &= Q_a \\ s(r^{1} * R)  (r^{1}m * G) &= Q_a \end{aligned} $$
From this rewrite, we introduce two new terms:
Term  Definition 

$T$  $r^{1} * R$ 
$U$  $r^{1}m * G$ 
which we substitute above to get
$$ s * T + U = Q_a $$
Because $T$ and $U$ are defined using $R$, $r$, and $m$, we can compute them outside of the SNARK and pass them in as public inputs. And so with this rewrite we only need to do 1 Secp256k1ScalarMult
and 1 Secp256k1AddUnequal
inside of the circuit. Okay, 3 operations cut! Is this progress?
Unfortunately, this only cuts 100k constraints from the original 1.5mil constraint circuit, because Secp256k1ScalarMult
is by far the most expensive operation. This is implemented as ecdsa_verify_no_precompute
in this file for reference. But hope is not lost yet! This rearranged equation is key for our next insight.
Precomputing point multiples
The original 0xPARC code uses a clever optimization to speed up the ECDSAPrivToPub
subroutine, which multiples the generator point $G$ by a scalar $a$. Because $G$ is known in advance, the code stores precomputed multiples of $G$ directly in the circuit to reduce the number of operations in ECDSAPrivToPub
. The 0xPARC blog post dives into this in more detail.
As $T$ is revealed publicly in our rearranged equation, we should be able to do the same technique on $T$ to speed up the Secp256k1ScalarMult
between $s$ and $T$! However, because $T$ changes for every proof, we need to compute these multiples on the fly and pass them in as public inputs. Using the notation of the 0xPARC code, we determined a stride
of 8 was most efficient, meaning we compute $(2^{8i} * j) * T$ for all $i \in [0, 31], j \in [0,255]$. Precomputing these multiples directly in JS is very slow, so we rewrote the cache computation in Rust and compiled to WASM to majorly reduce the overhead when proving in browser.
This cache of points means we can skip a number of costly operations in normal Secp256k1ScalarMult
, bringing our total constraints to 163,239. This is a more than 9x drop from the original circuit! The full method is:
 Public inputs: $U$ and precomputed $T$ multiples
 Private inputs: $s$, $Q_a$
 Logic
 Inside zkSNARK circuit $$ s * T + U = Q_a $$
 Outside of the zkSNARK
 Compute $U$ and precomputed multiples of $T$ in WASM
which is implemented as ecdsa_verify
here in circom.
Offchain verification
Although verifying and storing the proof on Ethereum is good practice in terms of security and convenience, our method makes onchain verification costly due to number of precomputed multiples we include. Therefore, the proofs from this model must be stored on “cheaper” storage, such as decentralized storage networks (e.g. IPFS, Arweave). From there, clients and servers can verify the proofs on their own, which is an acceptable solution for many nonfinancial privacy applications. We implement this solution in heyanoun.
The easiest way to make the method onchain friendly is to reduce the number of precomputed multiples, which decreases the input size but increases the proving time. Another method is to SNARKify the “outside of zkSNARK” checks and then link those checks to the original circuit. This requires the original circuit to privately input the precomputed multiples of $T$, but publicly output a hash $h_1$ of all of them. You then have another circuit (which can be computed serverside!) that internally computes the correct multiples of $T$ one by one and also publicly outputs a hash $h2$ of all of them. Then, your verifier or smart contract must input both of these proofs and verify that $h1 == h2$!
To keccak or not to keccak
We also include a version of the circuit called ecdsa_verify_pubkey_to_eth_addr
that converts the public key to an address using Keccak, which is a total of 315,175 constraints. This is a more than 5x drop from the old ECDSAVerify + PubkeyToAddress circuit. This circuit is important because many onchain groups are of addresses not public keys, like airdrop lists.
However, if all of the Ethereum addresses in a particular group have sent a transaction (or interacted with a smart contract) at least once, then we can use ecdsa_verify
instead (which requires meaningfully fewer constraints than ecdsa_verify_pubkey_to_eth_addr
). This is because we can extract the address’s public key from the ECDSA signature of the transaction.
Next up
In this post, we reviewed the math behind efficientzkecdsa
, which improves clientside proving of private ECDSA signature verification and thus private ECDSA group membership. The key insights require no math past high school Algebra I, yet are meaningful enough to make private group membership proving significantly smoother for our users. If you’ve made it to the end, hopefully you understand ECDSA better and are motivated to dig deeper into the beautiful world of cryptography (we mean cryptography specifically, not its bastardization in “crypto”! two very different things! sorry to be that person!).
Next post is gonna be a banger fr. In collaboration with Geometry, we’ll first present a full security proof of the efficientzkecdsa method
(HackMD sketch here, from Nico of Geometry). We’ll then present an alternate construction for onchain verification using the ideas in this post.
But the meat of the post will be comparing implementations of private group membership in new proving backends like Halo2, plonky2, Nova, and Spartan. Compared to our current backend Groth16, these new backends can more easily tradeoff proving and verification time, meaning we can have both proverfriendly and verifierfriendly versions of our circuits. The former is useful for clientside proving, and the latter for onchain verification. And some backends use commitment schemes like IPA and FRI that avoid EC pairings entirely, meaning we have more flexibility in choosing the finite fields of our circuits.
If you want to do cuttingedge ZK research focused on bringing clientside proving to millions or billions of consumer devices, please reach out to vivek@personaelabs.org and dan@personaelabs.org. We would love to support your work via research grants!
Credit roll
Thank you for making it to the end! Names within each group are sorted alphabetically by first name.
 Project leads: Dan Tehrani, Vivek Bhupatiraju
 Post writers: Vivek Bhupatiraju
 Post reviewers: Aayush Gupta, Amir Bolous, Hadrien Charlanes, Enrico Bottazzi, Lakshman Sankar, Leopold Sayous, Jason Kim, Nikita Kolmogorov, Shrey Jain
 Post inspirations: David Wong, Dankrad Feist, Vitalik Buterin, halo2 book
Appendix: half client & half server models
There’s an alternate construction pursued by other folks in the space that leads to more efficient proofs, but sacrifices full anonymity and requires a trusted server with an baby jub jub EdDSA public key $pk_s$. What in the world is a “baby jub jub EdDSA public key” and why do these constructions use it? We will break down each of these mystery words one by one. Disclaimer: we are not professional number theorists, just some people who like math and want to share what we’ve learned recently! Please reach out if there’s any mistakes below!
Elliptic curve interlude
Baby jub jub is an elliptic curve defined in this EIP by Barry WhiteHat, Marta Bellés, and Jordi Baylina. It is a twisted Edwards curve, which means we can use the Edwardscurve Digital Signature Algorithm (EdDSA) instead of ECDSA. But the reason we use this random ass curve is because it has the same base field as the scalar field of BN254, which is the curve used in snarkjs Groth16.
The base field can be thought of “where the elliptic curve math happens”, and the scalar field “where the circuit math happens”. More precisely, let’s define an elliptic curve $E_p$ where addition and multiplication is all done modulo a prime $p$, or in the finite field $\mathbb{F}_p$. The number of points on the curve in $\mathbb{F}_p$ will be a different value $q$, which is related to $p$ by Hasse’s wonderful theorem on elliptic curves (wonderful is not in the original name, we added that). Roughly, the witness variables are encoded into these elliptic curve points, and because these points form a group all of the circuit math is done modulo $q$ or the finite field $\mathbb{F}_q$.
Going back to baby jub jub, as its base field (where its elliptic curve math happens, like signature verification) is the same as BN254’s scalar field (where the snarkjs circuit math happens), we can add and multiply curve points in the circuit without bigint math or range checks! Don’t worry if this doesn’t fully make sense, we’re just trying to give you intuition for why EdDSA on this specific curve is fast in snarkjs. It’ll be more important to understand this for future ECDSA research posts.
Proving setup
Users send their public key $pk_u$ and a signature $s_u$ to a trusted server, which verifies $s_u$ manually and then gives you $C_u$. This is a signature from the server’s EdDSA public key $pk_s$ of $pk_u$ (and usually a nullifier $n$, but we’ll ignore that for now). This $C_u$ can be thought of a certification from the trusted server, and can be used to efficiently “prove” you know the private key for $pk_u$. Prove is in quotation marks because this isn’t a real proof of knowledge in the cryptographic sense, you’re just trusting a third party.
On the clientside, we use a circuit that privately inputs your $pk_u$ and the server’s certification $C_u$, and then publicly inputs the server’s public key $pk_s$ and the members of the group $G$. The circuit logic checks $C_u$ is indeed a signature of $pk_u$ by $pk_s$ AND that $pk_u$ is in $G$.
Praise & criticism
This is really clever for a few reasons! First, the nullifier $n$: we mostly ignored it above (because it’s a rich topic on its own!) but including $n$ essentially gives each user an unlinkable private ID. This is necessary for any 1signalper member application like voting or airdrops, but unfortunately cannot be easily generated for ECDSA keys. Second, after the user signs up, each subsequent proof of private group membership is quick due to baby jub jub EdDSA verification being SNARKfriendly (which the above explanation hopefully gave you intuition for!). And finally, this “certification” technique isn’t just restricted to making groups of Ethereum public keys. If you’re okay trusting third parties, you can also create groups by logging in with web2 platforms like Twitter and GitHub and having the server verify your login and giving you the relevant certification.
What does this construction give up in exchange for these benefits? As covered in the main post, our view is that the biggest concession is requiring a server at all. Only when proving is done clientside can we start to use ZK to move identity and computation away from other institutions and into our own hands. But does that meaningfully change a user’s privacy? After all, doesn’t each postsignup proof keep your identity private? No, because the trusted server knows the set of addresses and accounts it has given a certification to. This means if people use their certification to anonymously speak or vote, they don’t speak with the full anonymity of their group – they speak under the anonymity set of addresses that have signed up on the server. The server can keep this signup set private (meaning they can doxx when the group is small) or public (meaning the first signups have a small anonymity set). This works for lowerstakes applications, but a dealbreaker for any highprofile or sensitive groups.
In addition, we’re trusting the server to correctly assign certifications to users, but these can be maliciously forged in the current model. In the case of Ethereum groups, the trusted server can maliciously sign a public key $pk_m$ and give the corresponding $C_m$ to anyone who wants to “prove” ownership of $pk_m$. This can be avoided if the server does the verification of the signature and computation of $C_m$ inside a zkSNARK to prove it was actually given a valid signature from $pk_m$. But for nonEthereum groups there isn’t an easy way to SNARKify the validity, meaning it’s fair game for the server or hacker to forge.
Looking to the future
How necessary are the other benefits in the longterm? For the nullifier: although there is currently no way to generate a nullifier from our ECDSA keys, a collaboration between Personae and Geometry has solved this problem and has implementations ready to be deployed in wallets soon! For the faster “subsequent” proofs, this is no longer an issue if ECDSA signature verification is fast enough to be done on clientside devices. These proofs also add a UX hurdle of getting and storing a certification for every address you want to prove properties about.
Due to these concerns, we don’t see this approach being the longterm solution. Pure clientside proving is technically the most secure and aesthetically the cleanest, so we will continue to pursue solutions in that realm. But we deeply appreciate this creativity behind this method and its impact on the space!

You can technically use even fancier cryptography like MPC or FHE to avoid sending a plaintext publickey, but these methods are still in development. ↩︎

The actual verification only checks that $r$ is equal to the x coordinate of the RHS. This leads to $(r, s)$ also being a valid signature. However, if the verifier is given $R$ then checking the full equation is equivalent. ↩︎

In deterministic ECDSA, $k$ isn’t fully random and is roughly derived from a hash of the user’s private key. Revealing $R$ generated deterministically is still secure in our method, which we analyze here. ↩︎