Efficient ECDSA & the case for client-side proving

by Personae on Nov 30, 2022 cryptography

In 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 client-side proving to unlock the full potential of zero-knowledge 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 public-key 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 SNARK-unfriendly. 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 blow-up 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 memory-intensive, requiring ~1GB of proof metadata and ~5 minutes of browser computation on a MacBook.

Client-side 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 high-end 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¹. There’s some half-server half-client 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 zero-knowledge cryptography. Another framing of the importance of client-side 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 on-chain 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 in-depth 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$	x-coordinate 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 circom-ecdsa 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² 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 ³. 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.

Off-chain verification

Although verifying and storing the proof on Ethereum is good practice in terms of security and convenience, our method makes on-chain 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 non-financial privacy applications. We implement this solution in heyanoun.

The easiest way to make the method on-chain friendly is to reduce the number of precomputed multiples, which decreases the input size but increases the proving time. Another method is to SNARK-ify 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 server-side!) 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 on-chain 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 efficient-zk-ecdsa, which improves client-side 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 efficient-zk-ecdsa method (HackMD sketch here, from Nico of Geometry). We’ll then present an alternate construction for on-chain 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 prover-friendly and verifier-friendly versions of our circuits. The former is useful for client-side proving, and the latter for on-chain 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 cutting-edge ZK research focused on bringing client-side 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 Edwards-curve 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 client-side, 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 1-signal-per 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 SNARK-friendly (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 client-side 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 post-signup 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 sign-up set private (meaning they can doxx when the group is small) or public (meaning the first sign-ups have a small anonymity set). This works for lower-stakes applications, but a dealbreaker for any high-profile 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 non-Ethereum 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 long-term? 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 client-side 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 long-term solution. Pure client-side 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!