Inquiry Regarding Implementation of the EdDSA Gadget in Circuit Design

[AhmedElemary57]

Greetings Community,

I am currently grappling with the integration of the EdDSA gadget into our circuit design and would greatly appreciate some expert guidance on resolving a couple of challenges I have encountered.

Firstly, I am inquiring about the most efficient method to extract a subarray representing the public key from a certificate. Specifically, I am looking to incorporate a certificate byte into the circuit as an array of frontend variables. Despite possessing the index at which the public key begins, I am struggling to efficiently retrieve the subarray required for EdDSA signature verification. Any insights or best practices on how to address this issue would be invaluable.

Secondly, assuming the successful resolution of the first challenge, I am faced with the task of converting an array of frontend variables into a format compatible with the EdDSA gadget.
Having an array of frontend variable that contains the public key I need to convert it to gnark_eddsa.PublicKey how can I do that
Given the gadget's specific requirements regarding the representation of the public key, I am uncertain about the appropriate methodology for this conversion. Although I have attempted a solution, the outcome did not meet expectations.

Below is a snippet illustrating the attempted solution for reference:

`func extractPublicKey(certificate []byte, SubjectPublicKeyStart, SubjectPublicKeyEnd int) gnark_eddsa.PublicKey {
fmt.Println(SubjectPublicKeyStart, SubjectPublicKeyEnd)

publicKeyBytes := certificate[SubjectPublicKeyStart:SubjectPublicKeyEnd]

fmt.Println("Offset --> ", publicKeyBytes)
fmt.Println("Offset Length --> ", len(publicKeyBytes))

publicKey := gnark_eddsa.PublicKey{
    A: twistededwards.Point{
        X: publicKeyBytes[SubjectPublicKeyStart : SubjectPublicKeyEnd/2],
        Y: publicKeyBytes[SubjectPublicKeyEnd/2+1 : SubjectPublicKeyEnd],
    },
}

return publicKey

}`

would be immensely grateful for any expert advice and guidance on these matters. Thank you in advance for your support and insights.

Best regards,

[ivokub]

Hi,

Regarding 1), the approach could be either to use a lookup table or a mux for retrieving the public key based on some query variable. Have a look at the selector.Mux example. This is actually how we have implemented verification key switching in recursive PLONK verifier.

2. is a bit more involved. As I understand, you wish to obtain the public key from a certificate, where the certificate is a byte array. In gnark, a frontend.Variable is any possible variable (computed or coming from the witness), where the variable lives in the field of definition (depends on the elliptic curve used, but in case of EdDSA needs to be fixed). To get from bytes to field element, you have to compute the composition \sum_i certificateBytes[i] * (2^8)^i (assuming all the endiadeness matches). But in order for this composition to be sound, you have to range check that every byte in the certificate is indeed 8 bits.

You can have a look at a hackathon project I did a few years ago: https://github.com/ritave/eIDAS-bridge/tree/main/snark (particularly here), but adapting to EdDSA public key format.

[AhmedElemary57]

Thanks for your answer.

But I have an inquiry about point 2.
Is it secure to convert an array of front-end variable even if it is of big size "1000s bytes" to one front-end variable?
for example what I want to do is to verify a certificate of size 1000-byte signature
and gnark_eddsa.Verify takes msg as one front end variable.

I can use the following code to convert my array to one front end variable.

      result := frontend.Variable(0)

	for i := 0; i < len(digits); i++ {
		result = api.Add(api.Mul(256, result), digits[i])
	}

	return result
	

But I think that there is a security issue here "I think"
An attacker could send to the circuit an other certificate that is fake to the circut that gives the same front end variable after using the compression function and the verification would pass.

Is there any other solution to that problem or how to prevent problems like this

Thanks in advance

[ivokub]

You are right - this obvious compression would indeed allow to find several inputs which "hash" to the same frontend.Variable. A solution is to use a more secure hash function - either a binary hash (a la sha2/keccak) or algebraic hash (MiMC, Poseidon etc.). But keep in mind that algebraic hashes takes as inputs also frontend.Variable so you should split your long certificates into smaller chunks (32 bytes etc depending on the scalar field).

With binary hash it is a little simpler (as it is quite similar to what is done natively without ZKs), see https://github.com/ritave/eIDAS-bridge/blob/main/snark/circuits/circuit.go#L149-L170 for the in-circuit implementation and https://github.com/ritave/eIDAS-bridge/blob/main/snark/circuits/circuit_test.go#L33-L51 for witness assignment. We use std/math/uints package which exposes uints.U8 type which is actually frontend.Variable, but we range check every variable to be exactly 8-bit long.