I’m Vivek, a researcher at 0xPARC and Personae Labs. One of my main projects is heyanon.xyz, whose core cryptographic primitive is a ECDSAVerify inside of a SNARK. Currently this takes a few minutes to compute in specific browsers, so we’re very interested in any methods that can speed up this process!
This is a great find! My intuition is also telling me that this scheme is secure, as the only part of the original ECDSA signature computation trace that’s revealed publicly is R, which is just k * G and unrelated to the original user’s private key. I will attempt to write a full security analysis for this over the next few days so we can be even more confident that this can be deployed, dm me on Twitter (twitter.com/viv_boop) if you or anyone else is interested in collaborating on this!
One thing is we need to have a private, random, and unique m generated for the initial signature, and I’m wondering how that must be implemented so it is secure when deployed. I know for ECDSA, k must also be random and the deterministic version is generated based on some HMAC involving the original message m and the user’s private key d_a (details here). So perhaps we need to follow a similar technique for m for full security?
And looking through the code, one observation is that computing r^-1 * m * G inside the circuit can be made a bit more efficient without sacrificing any security. If you just pass in r^{-1} * m as an input into the circuit, you can use the original PrivToPub code from circom-ecdsa that stores precomputed multiples of G instead of passing in precomputed multiples of r^-1 * G and multiplying by m. This should decrease the input size a bunch and hopefully save constraints!