Computing SquareRoot of emulated.Element

[shreyas-londhe]

Hi, I am trying to implement a hashToCurve function for emulated BN254 field. and I am not able to figure out how to compute square root of an emulated element which is needed to deriveY using the curve equation y^2 = x^3 + 3.

Here is an implmentation which is working for me using gnark-crypto

func HashToCurveG1(msg []byte) bn254.G1Affine {
	hFunc := mimc.NewMiMC()

	multiple_of_fp_lower_than_2_256 := big.NewInt(0)
	multiple_of_fp_lower_than_2_256.SetString(LAST_MULTIPLE_OF_FP_LOWER_THAN_2_256, 10)

	for i := 0; i < 256; i++ {
		hFunc.Reset()
		hFunc.Write(msg[:])
		iBytes := make([]byte, 32)
		iBytes[31] = byte(i)
		hFunc.Write(iBytes)
		hPointXBytes := hFunc.Sum(nil)
		hPointX := new(big.Int).SetBytes(hPointXBytes)

		if hPointX.Cmp(multiple_of_fp_lower_than_2_256) == 1 || hPointX.Cmp(multiple_of_fp_lower_than_2_256) == 0 {
			continue
		}

		hPointX.Mod(hPointX, fp.Modulus())

		hPointY := DeriveY(hPointX)

		var hPoint bn254.G1Affine
		hPoint.X.SetBigInt(hPointX)
		hPoint.Y.SetBigInt(hPointY)

		if hPoint.IsOnCurve() {
			return hPoint
		}
	}

	panic("No valid point was found")
}

func DeriveY(x *big.Int) *big.Int {
	y2 := new(big.Int)
	y2.Exp(x, big.NewInt(3), fp.Modulus()) // y^2 = x^3
	y2.Add(y2, big.NewInt(3))              // y^2 = x^3 + 3
	y2.Mod(y2, fp.Modulus())               // y^2 = x^3 + 3 (mod p)
	y2.Exp(                                // y = (y^2)^(p+1)/4 (mod p)
		y2,
		big.NewInt(0).Div(big.NewInt(0).Add(fp.Modulus(),
			big.NewInt(1)), big.NewInt(4)), fp.Modulus(),
	)

	y := big.NewInt(0)
	y.Add(y2, big.NewInt(2))
	y.Mod(y2, big.NewInt(2))
	if y.Cmp(big.NewInt(0)) != 0 {
		y2.Sub(fp.Modulus(), y2)
	}

	return y2
}

Similarly my deriveY function in gnark

func DeriveY(api frontend.API, x emulated.Element[emulated.BN254Fp]) emulated.Element[emulated.BN254Fp] {
	field, err := emulated.NewField[emulated.BN254Fp](api)
	utils.HandleError(err)

	// y^2 = x^3 + 3
	var y2 emulated.Element[emulated.BN254Fp]
	y2 = *field.MulMod(&x, &x)  // x^2
	y2 = *field.MulMod(&y2, &x) // x^3
	three := emulated.ValueOf[emulated.BN254Fp](3)
	y2 = *field.Add(&y2, &three) // x^3 + 3
	y2 = *field.Reduce(&y2)      // x^3 + 3 (mod p)

	// y = sqrt(y^2)

}

Any help is much appreciated, thank you!

[ivokub]

We never bothered implementing square root in emulated arithmetic. It is kind of low-hanging fruit but as we didn't have a particular need then always postponed.

If you want then you can try proposing it as a PR. It could be done similarly as Div or Inverse i.e. you compute the square root y = sqrt(y^2) in a hint and then assert that y * y == y^2 holds.

I can also try doing this today if I have time but no promises!

[shreyas-londhe]

Thanks for replying, I'll try implementing and putting up a PR

[shreyas-londhe]

Hey @ivokub I made a PR - #619
Please check it out and lmk!

[ivokub]

Sorry, was busy yesterday. I see you closed it. I recreated in #623 with tests and using new NewHint method for field.

[shreyas-londhe]

Hey thanks, I mistakenly made a PR without writing tests for it, thought it was wrong that's why I closed the PR. Thank you so much for submitting one yourself.