Private ECDSA Verification using ZK: Motivation, Optimizations & Security

ECDSA signatures form the backbone of many modern blockchains. Most notably, Ethereum and many ERC-20 cryptocurrencies use signatures for spending funds, interacting with DeFi applications, etc. In short, to check whether you own the keys to an address, you are requested to generate an ECDSA signature on a challenge message, and then this signature is verified to complete the check.

Any party verifying your signature needs to know your public key/address. This is a crucial input to the signature verification algorithm. What if we want to check ownership of an address/controlling keys in a privacy-preserving manner? The motivation behind it is simple: enhanced privacy. We might just want to check that you own one of the addresses amongst 100 addresses with a total balance of >1000 ETH. Indeed, such verification is enough to provide access to, let's say, some new VC/crowdfunding DAO or some other high-value access. Multiple privacy-preserving applications would benefit from privacy-preserving ECDSA verification. The idea is simple, take a large group of addresses that satisfy your access criteria, and a user proves that they own one of these addresses. The proof can be used as an anonymous credential, no other information about the user is leaked, and the access-gating criteria are mathematically enforced using the power of zero-knowledge proofs.

With the motivation now clear, let's briefly summarize the contributions of various teams toward progress in this area. To the best of our knowledge, a team of individuals at 0xPARC's working groups started what is now circom-ecdsa. This repository serves as the codebase that enables the bulk of ECDSA verification as utilized in most of cryptography. However, circom is a resource-constrained environment. To generate a proof that attests to the fact that you own the keys to some address in a group, the proof actually is that of knowledge of a signature on a public, random message that verifies correctly under one of the public keys in the said group. Generating such a proof is costly and takes a lot of time and resources as mentioned in the benchmarks of the linked circom-ecdsa repository. The bottleneck is ECDSA verification in circom.

A fair question to ask at this point is why not use some other signature scheme, such as EdDSA, where the signature verification algorithm is highly efficient to run inside a circom circuit. The answer is simple: wallets support ECDSA signing at large. Another question is, why not use knowledge of the ECDSA private key and verify a zero-knowledge proof for that? The answer is, again that wallets do not expose private keys. People are wary of platforms that do any operations with their private keys, and for fair reason. So, from a user experience and infrastructure compatibility standpoint, our best bet is ECDSA verification in circom.

Naturally, folks have attempted to optimize ECDSA verification in circom. This eth-research forum post ventures into optimization tricks to improve costs.  Resulting optimizations have been implemented by the Personae Labs team in this repository. For access-gating in many of our products and supporting privacy infrastructure at large, efficient ECDSA verification in circom is extremely beneficial. As a result, we wanted to understand the security ramifications of these optimizations. Crucially, we have worked towards decisively answering the following question, to the best of our knowledge:

Does this optimization make it any easier for an adversary to generate a forged zero-knowledge proof for knowledge of a signature?

For SealHub’s efficient verification of ECDSA signatures, we are deploying a variant of ECDSA with precomputes to support faster verification in a circom circuit. ECDSA signatures usually work as follows, all arithmetic is \(\text{mod } n\) where \(n\) is the order of the elliptic curve group:

• KeyGen(\(G\)): G is the generator of the elliptic curve group. Sample a random scalar as your secret key \(sk = d_a\) , and your public key is the elliptic curve point \(pk = Q_A= d_a*G\), calculated using group scalar multiplication.
• Sign(\(sk, msg\)): This algorithm performs the signing in the following way:
  - Calculate \(m = H(msg)\) using a hash function
  - Sample a random scalar \(k\) and computes the nonce \(R = k*G\)   , which is a point on the curve, and the x-coordinate of this point is \(r\)
  - Compute \(s = k^{-1}(m + d_ar)\)
  - Output signature \(\sigma = (r, s)\)
• Verify(\(pk, msg, \sigma\)): This algorithm verifies a signature, given a message and the secret key in the following way:
  - Hash the message to get \(m\)
  -  Calculate \(u_1 = ms^{-1}, u_2 = rs^{-1}\)
  - Calculate \((x, y) = u_1*G + u_2*Q_a\)
  - If \(x = r (\text{mod } n)\) then the signature is valid

Security for private attestation using the above scheme

Let us assume that a private attestation scheme creates a system where, as mentioned earlier, you get some high-value opportunity if you prove that you own keys to an address in a particular group. For this purpose, SealHub makes potential users sign a publicly known message. And it verifies the signature in zero-knowledge. This incentivizes an attacker to compute a witness for a target address or a group of target addresses. Given that an attacker wants to create a false witness, it has to compute \((r, s)\) such that they satisfy the given equation in the verification algorithm for a target public key \(Q_a\). Guessing two scalars randomly is a bad strategy; at that point, you could guess the secret key and be done. Guessing the secret key from the public key is equivalent to breaking ECDLP with 256-bits of security (see report, page 3-4). Adversaries that break this break most cryptocurrencies as it gives them the ability to spend anyone's funds.

Security for private attestation using the optimization

The optimization suggests tweaking the verification algorithm a bit. This is done so that the circom circuit that runs the ECDSA verification algorithm is not too computationally costly to execute and generate proofs from. The optimization suggests that the verification algorithm check the following equation instead:

\[Q_a = sr^{-1}*R - mr^{-1}*G\]

The above equation is indeed a repurposing of the equation in the signature verification algorithm since the value of \(s\) should be \(s= k^{-1}(m + d_ar)\). Taking equation \(ks= m + d_ar\) and multiplying the scalar on both sides with \(G\) we get:

\[sk*G = m*G + d_ar*G \]

\[s*R = m*G + r*Q_a \]

\[s*R - m*G = r*Q_a \]

We get the tweaked verification check used by the optimization by multiplying the above equation with \(r^{-1}\) on both sides.

The values \((T= r^{-1}*R, U = -mr^{-1}G)\) are precomputed and supplied as private inputs to the verification circuit. Another thing that the optimization does differently is that it assumes that \(R\) is a public value. This creates a natural question of whether this optimization results in any security loss. A satisfying witness is a tuple \((s, T, U)\) such that \(Q_a = sT + U\). We need to consider the following attack scenarios:

• Precomputes not checked: An attacker can easily compute fake witnesses if the attestor does not check if \((T, U)\) were computed correctly. The attacker takes random scalars \(s_1, r_1\) it computes \(T^\prime= s_1r_1*G\) and \(U^\prime = Q_a - T^\prime\). The transcript \((s_1, T^\prime, U^\prime)\) would be accepted. Hence, we need to check that the precomputes are computed as expected.
• Precomputes are checked: In this scenario, the attacker needs to solve ECDLP, to input the correct \(T, U\) values. Since even if \(T, U, Q_a\) are known to the attacker, to find a valid \(s\) it has to solve ECDLP instance: \(Q_a-U=s*T\).
• Random public key: The attacker we have considered up until this point has a target public key in mind for which it wants to generate these witnesses. However, what about an attacker that just wants to compute valid witnesses for any arbitrary public key \(Q_a\) such that it does not know the corresponding private key? This becomes possible due to \(R\) being public. Such an attacker proceeds as follows:
  - Take a public \(R\) value: this fixes \(r^{-1}\) and, pick an arbitrary $m$
  - The attacker can compute \(U = -mr^{-1}*G\)
  - The attacker can compute \(T = r^{-1}*R\)
  - The attacker picks a random scalar \(s^\prime\) and computes        \(Q_a^\prime = s^\prime*T + U\)
  - \((s^\prime, T, U)\) is an accepting witness for the public key \(Q_a^\prime\), but the attacker does not know a single signature for this public key, nor the secret key
  - The above is not a dangerous attacker, as the probability of it stumbling upon any public key of value is extremely low

Overall, the optimization does not appear to allow attackers to generate a valid witness for a target public key. The security concerns in the past probably came from the possibility of the attacker solving the equation \(Q_a = sr^{-1}*R - mr^{-1}*G\) where \(R\) is public, and so are the values \(m, r, G\). However, as soon as \(Q_a\) is fixed to be a particular value, the security becomes equivalent to solving ECDLP. This is an excellent sign that the optimization does not negatively affect the security of the attestation protocol. However, one final thing to watch out for: as mentioned above, if the precomputes are checked, the attacker has to solve the ECDLP instance: \(Q_a-U=s*T\). To aid ECDSA verification in circom, the implementations might provide cached multiples of \(T\). This can make a possible attack strategy slightly more efficient if somehow these values are leaked to an attacker by mistake. Word of caution, therefore, is to keep the circom aids of this form as private inputs. Another thing to look out for at this point is to ensure that whatever you do, the precomputed values supplied to the circuit are consistent with the precomputes whose correctness was checked, possibly, elsewhere.

Hence, our analysis shows strong evidence that this optimization is just as good as vanilla ECDSA verification. Implementation errors and naive use can still result in vulnerabilities, but this is a secure, working solution if done right. All of this is a work in progress and is currently not audited and not being used for any real-world application to access gate direct monetary value. If you have any suggestions or spot a design flaw, please reach out, and we would be more than happy to discuss it further!

P.S.: ECDLP for reference