How to write a circuit to verify EdDSA generated externally?

[samngmco]

I have a question about EdDSA. Is it possible to use gnark to verify a standard Ed25519 signature? It seems that if I use BN254, it does not emulate a standard curve 25519. This means that it won't be able to verify an externally signed signature. Also, if it generates a signature, it won't be possible to verify it externally (I mean using NodeJS, for example). It's not because of the Mimc hash; I debugged the code. It should be because of the curve parameters.

On the contrary, we are able to verify an ECDSA signature signed by an external source (with the use of emulated.Secp256k1Fp/Fr, etc..)

I would greatly appreciate any assistance you could provide. Thank you in advance for your support.

[gbotrel]

cc @ivokub @yelhousni

[ivokub]

Hi @samngmco - we do not have ed25519 signature verification in gnark right now. In general, ed25519 is a EdDSA signature algorithm with fixed curve (curve25519) and hash (SHA2-512 afaik), but our EdDSA signature verification right now (package std/signature/eddsa) only supports SNARK-native curves (BN254, BLS12-381 etc.). And I'm not sure that Curve25519 is SNARK friendly (such that the scalar field corresponds to Curve25519), but it is highly unlikely. So, it would be necessary to implement EdDSA using field emulation, which shouldn't be too hard.

However, the difficult problem would be the hash function - SHA2 is really SNARK-unfriendly and would blow up the circuit size significantly. And it would require some more delicate implementation to convert the non-native field elements to suitable input for the SHA2 gadget.

I do not say it is not possible - but it would be difficult to implement and the performance would be quite bad. Unfortunately, we are not planning right now to add ed25519. Contributions are welcome though!

[samngmco]

@ivokub, thanks for your feedback. My plan is to do hashing outside of the circuit. I will try to see if I can use sw_emulated[fp/fr] to emulate curve25519.

[ivokub]

Then indeed should be doable. You can have a look at std/signature/ecdsa as this already operates on non-native arithmetic and can give you a blueprint for implementing non-native EdDSA

[yacovm]

Here you have instantiations of the curve parameters for the emulated curves.

Does anyone know how to instantiate the ed25519 curve? Specifically, what should be the a,b in the short Weierstrass form?

[ivokub]

I think https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-23 gives the mappings. See Appendix E