Public Key Validation in the Circuit

[BlakeMScurr]

Hi there!

I'm building a circuit to prove membership in some list of addresses for PSE's e2e-zk-ecdsa project, and I think I need public key validation inside the circuit. This is because we want to prove membership in arbitrary address sets, including ones where some addresses may have no transactions or signed messages which means the public key can't be recovered. This means we can't do public key validation on the set outside the circuit as you reccomend, so it has to be done in the circuit.

I don't think circom-ecdsa has public key validation yet, so I was planning on implementing it and I hoped you guys could validate my approach.
According to Johnson et al, you just need to make sure that:

1. $\mathcal{Q} \neq \mathcal{O}$ (where $\mathcal{Q}$ is the public key, and $\mathcal{O}$ is the point at infinity).
2. The coordinates of $\mathcal{Q}$ are in the field
3. $\mathcal{Q}$ is on the curve
4. $n\mathcal{Q} = \mathcal{O}$

I think Secp256k1PointOnCurve solves 2 and 3, and Secp256k1ScalarMult partially solves 4, but I'm not sure how to represent $\mathcal{O}$. My guess is that you represent it as (0,0) but I can't quite tell.

I was also considering writing an ecrecover circuit, but I realised that passing a public key as input to ECDSAVerifyNoPubkeyCheck basically does the same thing from the verifier's point of view, at least for set membership.

I'd be curious if you pick any holes in this. Thanks!

[yi-sun]

Regarding 4: We do not provide a way to represent the point at infinity — (0, 0) represents the origin, which is not on the curve. To check (4), you can check that (n - 1) * Q = -Q using the explicit formula for negating a point.

[BlakeMScurr]

Thank you that makes a lot of sense!
So if you don't represent the point at infinity, does Secp256k1PointOnCurve also confirm that $\mathcal{O} \neq \mathcal{Q}$?

[yi-sun]

Correct — if a point can be represented as an input to Secp256k1PointOnCurve, then it is not equal to O.

…

On Fri, Nov 25 2022 at 4:31 PM, BlakeMScurr < ***@***.*** > wrote: Thank you that makes a lot of sense! So if you don't represent the point at infinity, does Secp256k1PointOnCurve also confirm that $\mathcal{O} \neq \mathcal{Q}$ ? — Reply to this email directly, view it on GitHub ( #16 (comment) ) , or unsubscribe ( https://github.com/notifications/unsubscribe-auth/ABHQFNAETXDLEOJ4NTWIS7DWKE44RANCNFSM6AAAAAASK3H6YQ ). You are receiving this because you commented. Message ID: <0xPARC/circom-ecdsa/issues/16/1327916095 @ github. com>

[BlakeMScurr]

Hi, one more question! The explicit formula for $-\mathcal{Q}$ that you mention above is $(-x, y)$ right?

I just wanted to clarify that $-x$ refers to modular additive inverse, so I should calculate $-\mathcal{Q} = \mathcal{O} - \mathcal{Q}$ using the BigSub template.

I was a little confused because I thought $-x$ might mean multiplication inverse, so I should use the BigModInv template.

[yi-sun]

Yes, modular additive inverse. But this would be (x, -y), which you can compute using BigSub.

…

On Thu, Dec 1 2022 at 9:09 PM, BlakeMScurr < ***@***.*** > wrote: Hi, one more question! The explicit formula for $-\mathcal{Q}$ that you mention above is $(-x, y)$ right? I just wanted to clarify that $-x$ refers to modular additive inverse, so I should calculate $-\mathcal{Q} = \mathcal{O} - \mathcal{Q}$ using the BigSub template. I was a little confused because I thought $-x$ might mean multiplication inverse, so I should use the BigModInv template. — Reply to this email directly, view it on GitHub ( #16 (comment) ) , or unsubscribe ( https://github.com/notifications/unsubscribe-auth/ABHQFNFN2P5INKHDKBEWUXTWLFK7JANCNFSM6AAAAAASK3H6YQ ). You are receiving this because you commented. Message ID: <0xPARC/circom-ecdsa/issues/16/1334674818 @ github. com>

[BlakeMScurr]

Thanks for you help! It seems to work now.

By the way, I had an interesting bug where I couldn't use (n - 1) * Q = -Q because the double and add circuit implicitly calculates nQ and errors (by trying to add a point to its inverse and failing a range check deep in the circuit). The left hand side of this multiplexer ends up being nQ on the last round because n-1 is even.

I just used (n - 2) * Q = 2(-Q) instead. This adds an extra doubler but is OK for our purposes.

I also made a PR for this, in case you're interested in having the functionality here.