Feat: Subgroup membership testing on Bandersnatch

[yelhousni]

Description

This PR implements a method for subgroup membership testing on Bandersnatch twisted Edwards elliptic curve. It is based on the paper https://eprint.iacr.org/2022/037.pdf. A slight difference with the paper is that we implement the method directly using twisted Edwards coordinates.

This method can be generalized for all the companion twisted Edwards curves gnark-crypto supports but we need optimized higher residue symbols. As far as I can tell this cannot be as efficient as the binary-GCD-based Legendre symbol. For example Jubjub, we need an octic residue symbol.

Bandersnatch

Bandersnatch (B/Fr: -5x^2+y^2=1+dx^2y^2) has a cofactor 4. Given a point Q purported to be on the prime subgroup of B, we need to compute two Tate pairings and check they both are equal to 1. The final exponentiation to (r-1)/2 is replaced by a Legendre symbol (optimized through Pornin's binary GCD (#704). The Miller functions are just f1=x-x1 and f2=x-x2 where (x1,0) and (x2,0) are of order 2 on the birationally equivalent Weiestrass curve B'.

Given (x_e, x_e) a point on B, (x, y) is a point on B', where:

      x = ((1+y_e)/(1-y_e) + A/3 ) / B
      A = 2(a+d)/(a-d), B = 4/(a-d)

To avoid inverses we use the fact that ((a/b) / r)_2 = (a * b / r)_2.
So f1 and f2 are simplified as:

      f1 = (1 + y) * (B * (1-y)) and
      f2 = (t0 + t1 * y) * (3B * (1-y))

where:

      t0 = 3+A-3B * P'2.X
      t1 = 3-A+3B * P'2.X

Type of change

• New feature (non-breaking change which adds functionality)

How has this been tested?

Added TestIsInSubGroup.

How has this been benchmarked?

The new method is 17x faster than the naive multiplication by order (on my M1).

Checklist:

• I have performed a self-review of my code
• I have commented my code, particularly in hard-to-understand areas
• I have made corresponding changes to the documentation
• I have added tests that prove my fix is effective or that my feature works
• I did not modify files generated from templates
• golangci-lint does not output errors locally
• New and existing unit tests pass locally with my changes
• Any dependent changes have been merged and published in downstream modules

[Copilot]

Pull Request Overview

This PR adds subgroup membership checks for twisted Edwards curves (Bandersnatch and Jubjub) and hooks them into generated code, along with corresponding tests and benchmarks.

• Introduces IsInSubGroup method implementations in the edwards generator template and in the concrete bandersnatch and twistededwards packages.
• Extends CurveParams with constants (x1, x2, t0, t1, b) needed for the subgroup tests.
• Adds TestIsInSubGroup and BenchmarkIsInSubGroup in both the generator’s test template and the curve-specific test files.

Reviewed Changes

Copilot reviewed 9 out of 9 changed files in this pull request and generated 2 comments.

Show a summary per file

File	Description
internal/generator/edwards/template/tests/point.go.tmpl	Added subgroup test and benchmark blocks under wrong conditional
internal/generator/edwards/template/point.go.tmpl	Added IsInSubGroup template implementation
internal/generator/edwards/template/curve.go.tmpl	Added x1, x2, t0, t1, b to CurveParams
ecc/bls12-381/twistededwards/point_test.go	Added TestIsInSubGroup and BenchmarkIsInSubGroup
ecc/bls12-381/twistededwards/point.go	Added concrete IsInSubGroup (Jubjub)
ecc/bls12-381/twistededwards/curve.go	Added constants to CurveParams
ecc/bls12-381/bandersnatch/point_test.go	Added TestIsInSubGroup and BenchmarkIsInSubGroup
ecc/bls12-381/bandersnatch/point.go	Added concrete IsInSubGroup (Bandersnatch)
ecc/bls12-381/bandersnatch/curve.go	Added constants to CurveParams

Comments suppressed due to low confidence (2)

ecc/bls12-381/bandersnatch/point_test.go:736

• This test only verifies points in the subgroup (multiples of the base); consider adding negative cases (e.g., non-subgroup points) to ensure IsInSubGroup() correctly returns false.

func TestIsInSubGroup(t *testing.T) {

ecc/bls12-381/twistededwards/point.go:208

• [nitpick] The temporary variables tmp, res, and one are quite generic in the complex Miller-function implementation. Consider using more descriptive names (e.g., l0v1, numPart, denPart) to improve readability and maintainability.

	var (