bug: ...

[p4u]

Today I have updated our base code to gnark-crypto@master, and suddenly a previously working circuit for ElGamal decryption, stop working...

After digging for I while, I think I have found the issue.

When performing a scalar multiplication on the Identity point (0, 1) of a Twisted Edwards curve (specifically tested on BN254/BabyJubJub), the result is (0, 0) instead of (0, 1).

The point (0, 0) is not a valid point on the twisted edwards curve equation. This issue seems to affects both the off-circuit gnark-crypto library and the in-circuit gnark standard library constraints.

Reproduction Steps (gnark-crypto)

package main

import (
	"fmt"
	"math/big"

	"github.com/consensys/gnark-crypto/ecc/bn254/twistededwards"
)

func main() {
	// 1. Initialize Identity Point (0, 1)
	p := &twistededwards.PointAffine{}
	p.X.SetZero()
	p.Y.SetOne()

	fmt.Printf("Original: X=%s Y=%s\n", p.X.String(), p.Y.String())

	// 2. Perform Scalar Multiplication by random scalar
	scalar := big.NewInt(12345)
	res := &twistededwards.PointAffine{}
	res.ScalarMultiplication(p, scalar)

	fmt.Printf("Result:   X=%s Y=%s\n", res.X.String(), res.Y.String())

	// 3. Check
	if res.X.IsZero() && res.Y.IsZero() {
		fmt.Println("FAIL: Result is (0,0) which is invalid.")
	} else if res.X.IsZero() && res.Y.IsOne() {
		fmt.Println("PASS: Result is Identity (0,1).")
	} else {
		fmt.Println("FAIL: Unexpected result.")
	}
}

Using the current master branch

go get github.com/consensys/gnark-crypto@master

Original: X=0 Y=1
Result:   X=0 Y=0
FAIL: Result is (0,0) which is invalid.

However, using the @latest release, the result is correct.

---

The in-circuit std/algebra/native/twistededwards implementation also fails when ScalarMul is called as an Identity witness, triggering an assertion failure.

package main

import (
	testing

	"github.com/consensys/gnark-crypto/ecc"
	"github.com/consensys/gnark/frontend"
	"github.com/consensys/gnark/std/algebra/native/twistededwards"
	"github.com/consensys/gnark/test"
)

type TestCircuit struct {
	PointX frontend.Variable
	PointY frontend.Variable
}

func (c *TestCircuit) Define(api frontend.API) error {
	curve, _ := twistededwards.NewEdCurve(api, ecc.BN254)
	p := twistededwards.Point{X: c.PointX, Y: c.PointY}

	// This fails with "assertIsEqual 0 == 1" inside the scalar mul logic
	_ = curve.ScalarMul(p, 12345)
	return nil
}

func TestIdentityScalarMult(t *testing.T) {
	assert := test.NewAssert(t)
	witness := TestCircuit{PointX: 0, PointY: 1} // Identity
	assert.CheckCircuit(&TestCircuit{}, test.WithValidAssignment(&witness))
}

[ivokub]

Thanks for the issue. It is definitely a regression and we try to fix it soon.

cc @yelhousni

[ivokub]

I think it probably comes from #743 - usually for affine coordinates we represent infinity point as (0,0), interesting that it used to be (0,1) before. It was probably a bug before, but we still shouldn't do regressions

For your use case, is it possible to update the arithmetic to assume (0,0) being infinity point? Or it would require breaking changes on your side? In this case imo we can decide if we want to have some kind of backwards compatibility layer or not.

[yelhousni]

No the neutral point on twisted Edwards curves is the affine point (0,1), contrary to Weierstrass curve where it is a point at infinity and we take conventionally (0,0) as a representation when this point is not on the curve. I am investigating the issue.

[yelhousni]

ok found the bug and fixed it. I will do a clean PR tomorrow with more tests, but here is the bug: In https://github.com/ConsenSys/gnark-crypto/tree/2e354b07c43bc29e6f8b4d3aeddfd825f61b8dc5/ecc/bn254/twistededwards/point.go#L282 we use MixedAdd(p,q) which implements a dedicated addition from https://eprint.iacr.org/2008/522.pdf (Sec. 3.2). This gives an incorrect result when p or q are the neutral points or equal. We should have implemented the ScalarMul with unified addition from Sec. 3.1, this bug was introduced in #743. See

• fix
  https://github.com/ConsenSys/gnark-crypto/tree/57a6d084ea34296cc3066e2906c72fa4aa962098/ecc/bn254/twistededwards/point.go#L365
• test
  https://github.com/ConsenSys/gnark-crypto/tree/57a6d084ea34296cc3066e2906c72fa4aa962098/ecc/bn254/twistededwards/point_test.go#L38