Hashing to TwistedEdwards curve?

[Scratch-net]

Is there any simple way to hash into TwistedEdwards BN254 in & outside the circuit? I only found hashing to G1/G2 but I guess it won't work for TwistedEdwards, at least not out of the box.

[ivokub]

We don't currently have hash to G1 for twisted Edwards curve. But I guess we could make it work based on the existing hash to curve for ecc/ packages as it is generic implementation.

But we don't currently have the corresponding in-circuit version, there is Hash to G2 proposal in #1040 though. I think the direct approach would be to have hash to curve for G1 similar to what we have in native, but this is quite expensive as works with SHA2. And I'm not sure it would be safe with MiMC etc. The current native hash to G1 imo is based on RFC9380.

cc @yelhousni, @Tabaie?

[Scratch-net]

Ok, let's put it another way.
Suppose I want to perform a simple OPRF protocol based on whatever working prime order curve available.
We would need:

1. Hashing secret data to a curve point A
2. Scalar multiplication of A to a random blinding factor r => request point B
3. Inverse computation for un-masking after server preforms its part

(optionally, but nice to have) Ability to verify server's NIZKPoK (sigma protocol) that it indeed used his private scalar s to perform s*B
It will require:
Hashing to a point
Hashing to a scalar (Mimc)
Scalar multiplication
Point addition

Is there a set of existing curves that would allow to do that in&out of circuit?

[ivokub]

For this use case it seems a 2-chain of curves would be good for good performance. The options either are twisted Edwards or native 2-chains we have (BLS12-377 -> BW6-761). But unfortunately we don't have hash to curve for none of them.

@yelhousni recommended Elligator 2, but we don't have implementations out nor in-circuit.

Otherwise, for out-circuit we do have implemented RFC9380 hash to curve though: https://pkg.go.dev/github.com/consensys/[email protected]/ecc/bls12-377#HashToG1. But don't have in-circuit implementation. If you would be interested in implementing it, then it would be great.

[ivokub]

It seems Elligator 2 is better to implement in-circuit, it doesn't seem to need hashing which is really expensive, but I'm not fully sure.

[Scratch-net]

Another small question @ivokub if I may, how do I calculate scalar modInverse modulo babyjub order in circuit? It's the crucial part of "deblind" or unmasking step in OPRF
I cannot use api.Inv or fr.element

Outside circuit I just do

        curve := tbn254.GetEdwardsCurve()
        r, _:= rand.Int(rand.Reader, &curve.Order)
        ...
	invR := r.ModInverse(r, &curve.Order) 
	deblinded := &tbn254.PointAffine{}
	deblinded.ScalarMultiplication(blinded, invR)

which works

[ivokub]

Yup, for scalar operations you cannot use frontend.API as it works on the base field. But if you have only a single scalar inverse you need to compute, then you can use non-native arithmetic. See https://pkg.go.dev/github.com/consensys/[email protected]/std/math/emulated#Field.Inverse

We don't imo have the scalar field emulated parameters implemented for babyjubjub, but should be straightforward. You need to implement the interface emulated.FieldParams, I recommend setting BitsPerLimbs to 64 and the number of limbs as much necessary (I'd think four).

[Scratch-net]

will try that, thanks!

[ivokub]

Also see https://github.com/Consensys/gnark/blob/v0.11.0/std/algebra/native/sw_bls12377/pairing2.go#L503-L518 on how we convert the emulated.Element back to frontend.Element