Context
An ECDSA signature verification circuit written in Circom results in an R1CS with approximately 1.5 million constraints, a proving key that is close to a GB large, and a proving time that is non-trivial.
The point of doing an ECDSA signature verification using Circom is to verify that the prover owns a certain address without revealing the address. Although it is easier to check privKey * G == pubKey, most wallets don’t expose the private key of a wallet, therefore we are restricted to checking signatures. Signature verification without revealing the address has applications in, for example, zero-knowledge proof of membership. (Which is why we want to have a way to prove ownership of an address anonymously)
In this post, I will decribe a method that could improve the efficiency of ECDSA signature verification written in Circom.
I focus on implementation using Circom to avoid ambiguity. However, the method is not completely dependent on Circom. You can swap “Circom” with “zkp”, “zk-snark”, or other high-level arithmetic circuit languages.
Overview of the method
The essence of the method is, that in order to do as less computations as possible in a circuit, we offload some signature verification calculations from the circuit.
The method
This credit for this technique goes to the answerer of this stack exchange post. Although, the method is not formally verified. If this method lacks correctness, soundness, or zero-knowledge-ness, then the entire scheme I describe in this post will not work. That being a possibility, I’m writing this post hoping it to be useful at least in some way, as a source of ideas.
Verify an ECDSA signature without revealing the s part of the signature leads to reducing the required calculation that needs to be kept private (i.e. needs to be SNARKified)
First, you produce a signature with your private key as usual.
R = k * G
s = k^-1(m + da * r)
The signature = (r, s)
where
- G: The generator point of the curve
- k: The signature nonce
- R: k * G
- Qa: The public key
- m: The message to sign
- r: x-coordinate of R
The signature can be verified by checking the following equality
R = s^{-1} * m * G+ s^{-1}r * Qa
or
s * R = m * G + r * Qa.
This equation can be perceived as s being the private key, R being the generator point, and m * G + r * Qa being the public key.
Now we can prove the knowledge of s without revealing s itself, by generating a signature!
We calculate the signature as follows:
R’ = k’ * R
s’ = k^-1(m’ + s * r')
where
- k’: The signature nonce
- m’: The message to sign
- r’: x-coordinate of R'
We verify the signature (s’, r') by checking:
- s’ * R’ = m’ * R + r' * Qa’
This equation itself doesn’t reveal Qa (the public key). So it can be checked publicly, without using Circom.
We also need to check that Qa’ actually comes from Qa. This can be done by checking:
- Qa’ = m * G + r * Qa
Since we don’t want to reveal Qa (the public key), this equality check is done using Circom. Moreover, it is required to keep m a secret. If m is revealed, Qa will be recoverable. That is, in zero-knowledge proof of membership, the public keys that are members of a set are publicly known; someone can just check which public key matches Qa’, by filling in m and r .
Summary and benchmarks
To sum up, the circuit will take Qa and m as the private input, and r’ and Qa’ as the public input. I constructed the outline of the circuit here. The circuit is not complete. The purpose of it is to demonstrate the outline.
The benchmarks:
- constraints: \approx 200,000
- proving key size: \approx 134MB
- proving time (witness generation + proving): \approx 15s on a MacBook Pro
Which is a meaningful improvement from the original circuit.
And that is it.
Feedback will be appreciated.