precompile/babyjubjub/kat_test.go

// Copyright (C) 2025, Lux Industries Inc. All rights reserved.
// See the file LICENSE for licensing terms.

package babyjubjub

import (
	"math/big"
	"testing"

	"github.com/consensys/gnark-crypto/ecc/bn254/twistededwards"
	"github.com/luxfi/geth/common"
	"github.com/luxfi/precompile/contract"
	"github.com/luxfi/precompile/modules"
	"github.com/luxfi/precompile/precompileconfig"
	"github.com/stretchr/testify/require"
)

// subgroupOrder is the prime order of the Baby Jubjub subgroup generated by the
// reduced-form base point: r/8 with the cofactor removed. Published in EIP-2494
// and circomlib.
func subgroupOrder() *big.Int {
	l, ok := new(big.Int).SetString(
		"2736030358979909402780800718157159386076813972158567259200215660948447373041", 10)
	if !ok {
		panic("bad subgroup order literal")
	}
	return l
}

func w32(v *big.Int) []byte {
	b := make([]byte, 32)
	v.FillBytes(b)
	return b
}

func basePoint(tb testing.TB) (*big.Int, *big.Int) {
	tb.Helper()
	c := twistededwards.GetEdwardsCurve()
	return c.Base.X.BigInt(new(big.Int)), c.Base.Y.BigInt(new(big.Int))
}

func pointWords(x, y *big.Int) []byte {
	return append(w32(x), w32(y)...)
}

func invoke(tb testing.TB, op byte, args ...[]byte) ([]byte, uint64, error) {
	tb.Helper()
	in := []byte{op}
	for _, a := range args {
		in = append(in, a...)
	}
	return BabyJubJubPrecompile.Run(nil, common.Address{}, ContractAddress, in, 1<<22, true)
}

func mulBy(tb testing.TB, pt []byte, s *big.Int) []byte {
	tb.Helper()
	out, _, err := invoke(tb, OpScalarMul, pt, w32(s))
	require.NoError(tb, err)
	return out
}

// TestKAT_SubgroupOrder pins the published order of the base point. L*B is the
// identity and (L+1)*B is B: two facts a wrong ladder cannot fake.
func TestKAT_SubgroupOrder(t *testing.T) {
	bx, by := basePoint(t)
	B := pointWords(bx, by)
	l := subgroupOrder()

	identity := pointWords(big.NewInt(0), big.NewInt(1))

	require.Equal(t, identity, mulBy(t, B, l), "L*B must be the identity")
	require.Equal(t, B, mulBy(t, B, new(big.Int).Add(l, big.NewInt(1))), "(L+1)*B must be B")
	require.Equal(t, identity, mulBy(t, B, new(big.Int).Lsh(l, 1)), "2L*B must be the identity")

	// (L-1)*B is -B = (r-x, y).
	negX := new(big.Int).Sub(rBN254, bx)
	require.Equal(t, pointWords(negX, by),
		mulBy(t, B, new(big.Int).Sub(l, big.NewInt(1))), "(L-1)*B must be -B")

	// And -B + B closes the loop.
	sum, _, err := invoke(t, OpPointAdd, pointWords(negX, by), B)
	require.NoError(t, err)
	require.Equal(t, identity, sum)
}

// TestScalarIsNotReducedModField is the regression for the defect this file was
// written around: the multiplier used to be pushed through fr.Element, which
// reduces modulo r -- the BN254 FIELD, not the Baby Jubjub group order. Every
// scalar at or above r therefore produced (s mod r)*P instead of s*P.
//
// r*B is the sharpest witness. Correctly it is (r mod L)*B, a point far from
// the identity; under the old reduction it was 0*B, the identity exactly.
func TestScalarIsNotReducedModField(t *testing.T) {
	bx, by := basePoint(t)
	B := pointWords(bx, by)
	l := subgroupOrder()
	identity := pointWords(big.NewInt(0), big.NewInt(1))

	rB := mulBy(t, B, rBN254)
	require.NotEqual(t, identity, rB,
		"r*B is not the identity: r is the field modulus, not the group order")
	require.Equal(t, mulBy(t, B, new(big.Int).Mod(rBN254, l)), rB,
		"r*B must equal (r mod L)*B")

	// (r+1)*B must not collapse onto 1*B either.
	rPlus1 := new(big.Int).Add(rBN254, big.NewInt(1))
	require.NotEqual(t, B, mulBy(t, B, rPlus1),
		"(r+1)*B must not be B: that was the reduction bug")
	require.Equal(t, mulBy(t, B, new(big.Int).Mod(rPlus1, l)), mulBy(t, B, rPlus1))

	// The identity s*P == (s mod L)*P must hold across the whole 32-byte range,
	// including the largest word there is.
	maxWord := new(big.Int).Sub(new(big.Int).Lsh(big.NewInt(1), 256), big.NewInt(1))
	for _, s := range []*big.Int{
		new(big.Int).Sub(rBN254, big.NewInt(1)),
		new(big.Int).Add(rBN254, big.NewInt(7)),
		new(big.Int).Lsh(l, 3),
		maxWord,
	} {
		require.Equal(t, mulBy(t, B, new(big.Int).Mod(s, l)), mulBy(t, B, s),
			"s*P must equal (s mod L)*P for s = %s", s)
	}
}

// TestKAT_ScalarMulIsRepeatedAddition ties the ladder to the addition law:
// k*B must equal B added to itself k times, for small k where both are cheap.
func TestKAT_ScalarMulIsRepeatedAddition(t *testing.T) {
	bx, by := basePoint(t)
	B := pointWords(bx, by)

	acc := pointWords(big.NewInt(0), big.NewInt(1))
	for k := 1; k <= 12; k++ {
		var err error
		acc, _, err = invoke(t, OpPointAdd, acc, B)
		require.NoError(t, err)
		require.Equal(t, acc, mulBy(t, B, big.NewInt(int64(k))), "%d*B", k)
	}
}

// TestNonCanonicalCoordinateRejected is the regression for the second defect
// here: coordinates went through fr.Element.SetBytes, which reduces modulo r,
// so x and x+r named the same point. InCurve answered true for a coordinate any
// caller's own range check would reject, and two distinct calldata encodings
// produced one output.
func TestNonCanonicalCoordinateRejected(t *testing.T) {
	bx, by := basePoint(t)

	ncX := new(big.Int).Add(bx, rBN254)
	ncY := new(big.Int).Add(by, rBN254)
	require.LessOrEqual(t, ncX.BitLen(), 256, "the non-canonical form must still fit a word")
	require.LessOrEqual(t, ncY.BitLen(), 256)

	B := pointWords(bx, by)
	for _, tc := range []struct {
		name string
		pt   []byte
	}{
		{"x + r", pointWords(ncX, by)},
		{"y + r", pointWords(bx, ncY)},
		{"both + r", pointWords(ncX, ncY)},
		{"x = r", pointWords(rBN254, by)},
		{"y = r", pointWords(bx, rBN254)},
		{"x = 2^256-1", pointWords(new(big.Int).Sub(new(big.Int).Lsh(big.NewInt(1), 256), big.NewInt(1)), by)},
	} {
		t.Run(tc.name, func(t *testing.T) {
			for _, op := range []struct {
				name string
				args [][]byte
				op   byte
			}{
				{"inCurve", [][]byte{tc.pt}, OpInCurve},
				{"pointAdd first", [][]byte{tc.pt, B}, OpPointAdd},
				{"pointAdd second", [][]byte{B, tc.pt}, OpPointAdd},
				{"scalarMul", [][]byte{tc.pt, w32(big.NewInt(2))}, OpScalarMul},
			} {
				out, _, err := invoke(t, op.op, op.args...)
				require.ErrorIs(t, err, ErrInvalidInput,
					"%s must refuse a non-canonical coordinate, not reduce it", op.name)
				require.Nil(t, out)
			}
		})
	}

	// The canonical encoding of the same point is still accepted, so the
	// refusals above come from canonicality and not from a broken fixture.
	out, _, err := invoke(t, OpInCurve, B)
	require.NoError(t, err)
	require.Equal(t, byte(1), out[31])
}

// TestRefusal_PointNotOnCurve is the invalid-curve refusal: a well-formed pair
// of canonical coordinates that does not satisfy the curve equation.
func TestRefusal_PointNotOnCurve(t *testing.T) {
	bx, by := basePoint(t)
	B := pointWords(bx, by)

	offCurve := pointWords(bx, new(big.Int).Add(by, big.NewInt(1)))
	// Confirm the fixture really is off the curve before relying on it.
	res, _, err := invoke(t, OpInCurve, offCurve)
	require.NoError(t, err, "InCurve answers, it does not refuse")
	require.Equal(t, byte(0), res[31], "fixture must be off the curve")

	for _, tc := range []struct {
		name string
		args [][]byte
		op   byte
	}{
		{"pointAdd first", [][]byte{offCurve, B}, OpPointAdd},
		{"pointAdd second", [][]byte{B, offCurve}, OpPointAdd},
		{"scalarMul", [][]byte{offCurve, w32(big.NewInt(3))}, OpScalarMul},
	} {
		t.Run(tc.name, func(t *testing.T) {
			out, _, err := invoke(t, tc.op, tc.args...)
			require.ErrorIs(t, err, ErrNotOnCurve)
			require.Nil(t, out)
		})
	}

	// (0, 0) satisfies neither the curve equation nor the identity: a caller
	// spelling "point at infinity" the Weierstrass way must be refused.
	zero := make([]byte, PointLen)
	res, _, err = invoke(t, OpInCurve, zero)
	require.NoError(t, err)
	require.Equal(t, byte(0), res[31], "(0,0) is not on this twisted Edwards curve")

	out, _, err := invoke(t, OpPointAdd, zero, B)
	require.ErrorIs(t, err, ErrNotOnCurve)
	require.Nil(t, out)
}

// TestInCurveAcceptsTorsionPoints records the property a caller must guard for
// itself. InCurve answers the curve equation, which the identity and the three
// non-trivial cofactor points satisfy. A protocol that treats "InCurve == 1" as
// "this is a valid public key" is open to a small-subgroup attack: multiplying
// by a secret leaks that secret modulo 8.
func TestInCurveAcceptsTorsionPoints(t *testing.T) {
	torsion := [][]byte{
		pointWords(big.NewInt(0), big.NewInt(1)),                           // identity, order 1
		pointWords(big.NewInt(0), new(big.Int).Sub(rBN254, big.NewInt(1))), // order 2
	}
	identity := pointWords(big.NewInt(0), big.NewInt(1))

	for _, pt := range torsion {
		out, _, err := invoke(t, OpInCurve, pt)
		require.NoError(t, err)
		require.Equal(t, byte(1), out[31], "cofactor point satisfies the curve equation")

		// Its order divides 8, so the eighth multiple is the identity -- the
		// check a caller has to perform itself.
		require.Equal(t, identity, mulBy(t, pt, big.NewInt(8)))
	}

	// The base point is emphatically not torsion.
	bx, by := basePoint(t)
	require.NotEqual(t, identity, mulBy(t, pointWords(bx, by), big.NewInt(8)))
}

// TestRefusal_Length walks every truncation and the unknown-opcode arm.
func TestRefusal_Length(t *testing.T) {
	bx, by := basePoint(t)
	B := pointWords(bx, by)

	for _, tc := range []struct {
		name string
		in   []byte
		err  error
	}{
		{"nil", nil, ErrInvalidInput},
		{"empty", []byte{}, ErrInvalidInput},
		{"pointAdd op only", []byte{OpPointAdd}, ErrInvalidInput},
		{"pointAdd one point", append([]byte{OpPointAdd}, B...), ErrInvalidInput},
		{"pointAdd one byte short", append([]byte{OpPointAdd}, append(append([]byte{}, B...), B[:PointLen-1]...)...), ErrInvalidInput},
		{"scalarMul op only", []byte{OpScalarMul}, ErrInvalidInput},
		{"scalarMul no scalar", append([]byte{OpScalarMul}, B...), ErrInvalidInput},
		{"scalarMul one byte short", append([]byte{OpScalarMul}, append(append([]byte{}, B...), make([]byte, 31)...)...), ErrInvalidInput},
		{"inCurve op only", []byte{OpInCurve}, ErrInvalidInput},
		{"inCurve one byte short", append([]byte{OpInCurve}, B[:PointLen-1]...), ErrInvalidInput},
		{"unknown op 0x00", []byte{0x00}, ErrInvalidOp},
		{"unknown op 0x04", []byte{0x04}, ErrInvalidOp},
		{"unknown op 0xff", append([]byte{0xFF}, B...), ErrInvalidOp},
	} {
		t.Run(tc.name, func(t *testing.T) {
			out, _, err := BabyJubJubPrecompile.Run(nil, common.Address{}, ContractAddress, tc.in, 1<<22, true)
			require.ErrorIs(t, err, tc.err)
			require.Nil(t, out)
		})
	}

	// Trailing data past the fixed operand width is ignored, not refused.
	short, _, err := invoke(t, OpInCurve, B)
	require.NoError(t, err)
	long, _, err := invoke(t, OpInCurve, B, []byte{0xAA, 0xBB})
	require.NoError(t, err)
	require.Equal(t, short, long)
}

// TestGas_Schedule covers every arm and proves the zero-priced arms buy nothing.
func TestGas_Schedule(t *testing.T) {
	for _, tc := range []struct {
		name string
		in   []byte
		want uint64
	}{
		{"nil", nil, 0},
		{"empty", []byte{}, 0},
		{"pointAdd", []byte{OpPointAdd}, GasPointAdd},
		{"scalarMul", []byte{OpScalarMul}, GasScalarMul},
		{"inCurve", []byte{OpInCurve}, GasInCurve},
		{"unknown 0x00", []byte{0x00}, 0},
		{"unknown 0x04", []byte{0x04}, 0},
		{"unknown 0xff", []byte{0xFF}, 0},
	} {
		t.Run(tc.name, func(t *testing.T) {
			require.Equal(t, tc.want, BabyJubJubPrecompile.RequiredGas(tc.in))
		})
	}

	// Every operand is fixed width, so the price must not move with input size.
	require.Equal(t, uint64(GasScalarMul),
		BabyJubJubPrecompile.RequiredGas(append([]byte{OpScalarMul}, make([]byte, 1<<16)...)))

	// Scalar multiplication is the expensive arm and must be priced above the
	// membership test, which does no group arithmetic at all.
	require.Greater(t, uint64(GasScalarMul), uint64(GasPointAdd))
	require.Greater(t, uint64(GasPointAdd), uint64(GasInCurve))

	for _, in := range [][]byte{nil, {}, {0x00}, {0x04}, {0xFF}} {
		require.Zero(t, BabyJubJubPrecompile.RequiredGas(in))
		out, _, err := BabyJubJubPrecompile.Run(nil, common.Address{}, ContractAddress, in, 0, true)
		require.Error(t, err, "a zero-gas input must not execute")
		require.Nil(t, out)
	}
}

func TestGas_Deduction(t *testing.T) {
	bx, by := basePoint(t)
	in := append([]byte{OpInCurve}, pointWords(bx, by)...)

	_, left, err := BabyJubJubPrecompile.Run(nil, common.Address{}, ContractAddress, in, GasInCurve+21, true)
	require.NoError(t, err)
	require.Equal(t, uint64(21), left)

	_, left, err = BabyJubJubPrecompile.Run(nil, common.Address{}, ContractAddress, in, GasInCurve, true)
	require.NoError(t, err)
	require.Zero(t, left)

	_, left, err = BabyJubJubPrecompile.Run(nil, common.Address{}, ContractAddress, in, GasInCurve-1, true)
	require.ErrorIs(t, err, contract.ErrOutOfGas)
	require.Zero(t, left)
}

// --- module + config ----------------------------------------------------

func TestModule_Wiring(t *testing.T) {
	require.Equal(t, ConfigKey, Module.ConfigKey)
	require.Equal(t, ContractAddress, Module.Address)
	require.Same(t, BabyJubJubPrecompile, Module.Contract)
	require.NotNil(t, Module.Configurator)
	require.Equal(t,
		common.HexToAddress("0x0500000000000000000000000000000000000007"),
		ContractAddress)
}

func TestConfigurator_Surface(t *testing.T) {
	c := &configurator{}
	require.IsType(t, &Config{}, c.MakeConfig())
	require.NoError(t, c.Configure(nil, nil, nil, nil))
}

func TestConfig_Surface(t *testing.T) {
	c := &Config{}
	require.Equal(t, ConfigKey, c.Key())
	require.Nil(t, c.Timestamp())
	require.False(t, c.IsDisabled())
	require.NoError(t, c.Verify(nil))

	ts := uint64(21)
	a := &Config{Upgrade: precompileconfig.Upgrade{BlockTimestamp: &ts}}
	require.Equal(t, &ts, a.Timestamp())
	require.True(t, a.Equal(&Config{Upgrade: precompileconfig.Upgrade{BlockTimestamp: &ts}}))

	other := uint64(22)
	require.False(t, a.Equal(&Config{Upgrade: precompileconfig.Upgrade{BlockTimestamp: &other}}))
	require.False(t, a.Equal(nil))
	require.True(t, (&Config{Upgrade: precompileconfig.Upgrade{Disable: true}}).IsDisabled())
}

func TestRegisterModuleIsIdempotentlyRefused(t *testing.T) {
	require.Error(t, modules.RegisterModule(Module))
}