threshold/protocols/frost/frost_ed25519_test.go

package frost_test

import (
	"bytes"
	"crypto/ed25519"
	"crypto/rand"
	"crypto/sha256"
	"encoding/hex"
	"fmt"
	"testing"

	"github.com/luxfi/threshold/internal/test"
	"github.com/luxfi/threshold/pkg/math/curve"
	"github.com/luxfi/threshold/pkg/math/polynomial"
	"github.com/luxfi/threshold/pkg/math/sample"
	"github.com/luxfi/threshold/pkg/party"
	"github.com/luxfi/threshold/pkg/protocol"
	"github.com/luxfi/threshold/protocols/frost"
	"github.com/mr-tron/base58"
	"github.com/stretchr/testify/assert"
	"github.com/stretchr/testify/require"
)

// runEd25519Keygen runs a real N-party keygen ceremony and returns every party's
// config plus the agreed group public key.
func runEd25519Keygen(t *testing.T, sessionID string, n, threshold int) ([]party.ID, map[party.ID]*frost.Config, curve.Point) {
	t.Helper()

	partyIDs := test.PartyIDs(n)
	results, err := test.RunProtocol(t, partyIDs, []byte(sessionID), func(id party.ID) protocol.StartFunc {
		return frost.KeygenEd25519(id, partyIDs, threshold)
	})
	require.NoError(t, err, "keygen must complete")
	require.Len(t, results, n)

	configs := make(map[party.ID]*frost.Config, n)
	var pubKey curve.Point
	for id, result := range results {
		config, ok := result.(*frost.Config)
		require.True(t, ok, "result should be *frost.Config for party %s, got %T", id, result)
		require.Equal(t, "ed25519", config.PublicKey.Curve().Name())
		configs[id] = config
		if pubKey == nil {
			pubKey = config.PublicKey
		} else {
			require.True(t, pubKey.Equal(config.PublicKey),
				"every party must derive the same group public key")
		}
	}
	return partyIDs, configs, pubKey
}

// runEd25519Sign runs a real signing ceremony and returns the signature every
// signer agreed on, plus its 64-byte RFC 8032 encoding.
func runEd25519Sign(t *testing.T, sessionID string, configs map[party.ID]*frost.Config, signers []party.ID, message []byte) ([]byte, frost.Ed25519Signature) {
	t.Helper()

	results, err := test.RunProtocol(t, signers, []byte(sessionID), func(id party.ID) protocol.StartFunc {
		return frost.SignEd25519(configs[id], signers, message)
	})
	require.NoError(t, err, "signing must complete")
	require.Len(t, results, len(signers))

	var first []byte
	var sig frost.Ed25519Signature
	for id, result := range results {
		s, ok := result.(frost.Ed25519Signature)
		require.True(t, ok, "result should be frost.Ed25519Signature for party %s, got %T", id, result)
		raw, err := s.MarshalBinary()
		require.NoError(t, err)
		require.Len(t, raw, ed25519.SignatureSize)
		if first == nil {
			first, sig = raw, s
		} else {
			require.Equal(t, first, raw, "every signer must output the same signature")
		}
	}
	return first, sig
}

// solanaAddress is how a Solana address is derived from a public key: base58 of
// the raw 32 bytes, nothing else.
func solanaAddress(t *testing.T, pubKey curve.Point) (string, []byte) {
	t.Helper()
	raw, err := pubKey.MarshalBinary()
	require.NoError(t, err)
	require.Len(t, raw, ed25519.PublicKeySize, "a Solana address is exactly 32 bytes of key material")
	return base58.Encode(raw), raw
}

// TestEd25519ThresholdSignatureVerifiesUnderRFC8032 is the test this ciphersuite
// exists to pass.
//
// A key is generated by a real 2-of-3 ceremony, a message is signed by a real
// signing ceremony, and the result is handed to crypto/ed25519 — the same
// RFC 8032 verifier Solana runs. Anything less than this (internal consistency,
// "it returns 64 bytes") is compatible with minting addresses we cannot spend
// from, which is exactly how a taproot signature can masquerade as an Ed25519 one.
func TestEd25519ThresholdSignatureVerifiesUnderRFC8032(t *testing.T) {
	partyIDs, configs, pubKey := runEd25519Keygen(t, "ed25519-keygen", 3, 1)

	signers := partyIDs[:2]
	message := []byte("transfer 1 SOL")
	raw, sig := runEd25519Sign(t, "ed25519-sign", configs, signers, message)

	address, pub := solanaAddress(t, pubKey)

	// THE assertion.
	require.True(t, ed25519.Verify(pub, message, raw),
		"threshold signature must verify under crypto/ed25519")

	// The same thing through the signature type, which is what round 3 gates on.
	assert.True(t, sig.Verify(pubKey, message))

	t.Logf("2-of-3 ed25519 ceremony verified under RFC 8032")
	t.Logf("  solana address: %s", address)
	t.Logf("  public key:     %x", pub)
	t.Logf("  signature:      %x", raw)
}

// TestEd25519PublicKeyIsSpendable checks the properties that decide whether
// funds sent to this address can ever move again.
func TestEd25519PublicKeyIsSpendable(t *testing.T) {
	_, _, pubKey := runEd25519Keygen(t, "ed25519-spendable", 3, 1)
	address, pub := solanaAddress(t, pubKey)

	// A Solana address is base58 of the key, so it must round-trip.
	decoded, err := base58.Decode(address)
	require.NoError(t, err)
	assert.Equal(t, pub, decoded, "address must decode back to the public key")
	assert.GreaterOrEqual(t, len(address), 32, "base58 Solana addresses are 32-44 chars")
	assert.LessOrEqual(t, len(address), 44)

	// crypto/ed25519 must accept it as a public key at all.
	require.Len(t, pub, ed25519.PublicKeySize)

	// And it must be free of torsion. A key with a small-order component still
	// base58-encodes to a perfectly ordinary looking address and still accepts
	// deposits, but z*G = R + c*Y can never hold for it, so nothing signed with
	// it will ever verify. Strict verifiers (ed25519-dalek verify_strict, which
	// Solana uses) reject such keys outright.
	edPoint, ok := pubKey.(*curve.Ed25519Point)
	require.True(t, ok)
	assert.True(t, edPoint.IsPrimeOrder(), "group public key must be in the prime-order subgroup")

	// Round-tripping through the wire decoder enforces the same invariant.
	require.NoError(t, curve.Ed25519{}.NewPoint().UnmarshalBinary(pub))

	t.Logf("address %s is prime-order and round-trips", address)
}

// TestEd25519ThresholdVariants runs several (t, n) shapes end to end.
func TestEd25519ThresholdVariants(t *testing.T) {
	cases := []struct{ n, threshold int }{
		{2, 1}, // 2-of-2
		{3, 1}, // 2-of-3
		{5, 2}, // 3-of-5
		{5, 4}, // 5-of-5
	}

	for _, tc := range cases {
		t.Run(fmt.Sprintf("%dof%d", tc.threshold+1, tc.n), func(t *testing.T) {
			id := fmt.Sprintf("ed25519-%d-%d", tc.threshold, tc.n)
			partyIDs, configs, pubKey := runEd25519Keygen(t, id+"-keygen", tc.n, tc.threshold)

			signers := partyIDs[:tc.threshold+1]
			message := []byte(fmt.Sprintf("%d-of-%d payment", tc.threshold+1, tc.n))
			raw, _ := runEd25519Sign(t, id+"-sign", configs, signers, message)

			_, pub := solanaAddress(t, pubKey)
			assert.True(t, ed25519.Verify(pub, message, raw),
				"%d-of-%d signature must verify under RFC 8032", tc.threshold+1, tc.n)
		})
	}
}

// TestEd25519DifferentSignerSubsets checks that any authorised quorum produces a
// signature for the same address. If Lagrange interpolation were wrong for some
// subsets, deposits would be spendable only by whichever quorum happened to be
// tested.
func TestEd25519DifferentSignerSubsets(t *testing.T) {
	n, threshold := 5, 2
	partyIDs, configs, pubKey := runEd25519Keygen(t, "ed25519-subsets", n, threshold)
	_, pub := solanaAddress(t, pubKey)

	subsets := [][]party.ID{
		partyIDs[:threshold+1],
		partyIDs[1 : threshold+2],
		partyIDs[n-threshold-1:],
		{partyIDs[0], partyIDs[2], partyIDs[4]},
	}
	message := []byte("any quorum must be able to spend")

	for i, signers := range subsets {
		t.Run(fmt.Sprintf("subset_%d", i), func(t *testing.T) {
			raw, _ := runEd25519Sign(t, fmt.Sprintf("ed25519-subset-%d", i), configs, signers, message)
			assert.True(t, ed25519.Verify(pub, message, raw),
				"signers %v must produce a signature for the same address", signers)
		})
	}
}

// TestEd25519SignsRawMessageNotDigest pins PureEdDSA semantics: the bytes handed
// to SignEd25519 are the bytes the verifier is given. If the protocol hashed the
// message internally, the signature would verify for the digest instead — and
// every Solana transaction would be rejected.
func TestEd25519SignsRawMessageNotDigest(t *testing.T) {
	partyIDs, configs, pubKey := runEd25519Keygen(t, "ed25519-raw", 3, 1)
	_, pub := solanaAddress(t, pubKey)

	signers := partyIDs[:2]
	message := []byte("the exact bytes that go on the wire")
	raw, _ := runEd25519Sign(t, "ed25519-raw-sign", configs, signers, message)

	assert.True(t, ed25519.Verify(pub, message, raw), "must verify for the raw message")

	digest := sha256.Sum256(message)
	assert.False(t, ed25519.Verify(pub, digest[:], raw),
		"must NOT verify for a digest of the message")
}

// TestEd25519TONCellHash covers the TON shape, where the signed payload is the
// 32-byte hash of a cell. It is passed as the message, not pre-hashed again.
func TestEd25519TONCellHash(t *testing.T) {
	partyIDs, configs, pubKey := runEd25519Keygen(t, "ed25519-ton", 3, 1)
	_, pub := solanaAddress(t, pubKey)

	cellHash := sha256.Sum256([]byte("ton transfer body cell"))
	signers := partyIDs[:2]
	raw, _ := runEd25519Sign(t, "ed25519-ton-sign", configs, signers, cellHash[:])

	assert.True(t, ed25519.Verify(pub, cellHash[:], raw),
		"TON cell-hash signature must verify under RFC 8032")
}

// TestEd25519RejectsForgeries checks the signature does not verify where it
// must not.
func TestEd25519RejectsForgeries(t *testing.T) {
	partyIDs, configs, pubKey := runEd25519Keygen(t, "ed25519-forgery", 3, 1)
	_, pub := solanaAddress(t, pubKey)

	signers := partyIDs[:2]
	message := []byte("pay alice 10 SOL")
	raw, _ := runEd25519Sign(t, "ed25519-forgery-sign", configs, signers, message)
	require.True(t, ed25519.Verify(pub, message, raw))

	t.Run("different_message", func(t *testing.T) {
		assert.False(t, ed25519.Verify(pub, []byte("pay mallory 10 SOL"), raw))
	})

	t.Run("tampered_R", func(t *testing.T) {
		bad := append([]byte{}, raw...)
		bad[0] ^= 0x01
		assert.False(t, ed25519.Verify(pub, message, bad))
	})

	t.Run("tampered_S", func(t *testing.T) {
		bad := append([]byte{}, raw...)
		bad[32] ^= 0x01
		assert.False(t, ed25519.Verify(pub, message, bad))
	})

	t.Run("different_key", func(t *testing.T) {
		_, _, otherKey := runEd25519Keygen(t, "ed25519-forgery-other", 3, 1)
		_, otherPub := solanaAddress(t, otherKey)
		assert.False(t, ed25519.Verify(otherPub, message, raw))

		var sig frost.Ed25519Signature
		require.NoError(t, sig.UnmarshalBinary(curve.Ed25519{}, raw))
		assert.False(t, sig.Verify(otherKey, message))
		assert.True(t, sig.Verify(pubKey, message))
	})
}

// TestEd25519RefreshPreservesAddress checks that resharing keeps the address
// stable and the refreshed shares still sign for it. Refresh is deliberately not
// duplicated per ciphersuite: it takes the group from the config.
func TestEd25519RefreshPreservesAddress(t *testing.T) {
	partyIDs, configs, pubKey := runEd25519Keygen(t, "ed25519-refresh", 3, 1)
	addressBefore, pub := solanaAddress(t, pubKey)

	results, err := test.RunProtocol(t, partyIDs, []byte("ed25519-refresh-run"), func(id party.ID) protocol.StartFunc {
		return frost.Refresh(configs[id], partyIDs)
	})
	require.NoError(t, err)

	refreshed := make(map[party.ID]*frost.Config, len(partyIDs))
	for id, result := range results {
		config := result.(*frost.Config)
		require.True(t, pubKey.Equal(config.PublicKey), "refresh must not change the address")
		refreshed[id] = config
	}

	signers := partyIDs[:2]
	message := []byte("spend after refresh")
	raw, _ := runEd25519Sign(t, "ed25519-refresh-sign", refreshed, signers, message)

	assert.True(t, ed25519.Verify(pub, message, raw),
		"refreshed shares must still sign for the original address")

	addressAfter, _ := solanaAddress(t, refreshed[partyIDs[0]].PublicKey)
	assert.Equal(t, addressBefore, addressAfter)
}

// TestEd25519KeygenRejectsTorsionCommitment demonstrates the defense at the
// exact place a malicious keygen participant would attack.
//
// Keygen sums each party's polynomial commitment constant to form the group key:
// Y = Σ φ_j0. The Schnorr proof accompanying φ_j0 does NOT rule out a torsion
// component — the proof checks z*G = C + e*φ_j0, and a prover who puts torsion T
// in φ_j0 can cancel it by putting -(e mod 8)*T in C, grinding C until the
// Fiat-Shamir challenge cooperates. That takes about 8 attempts.
//
// The payoff for the attacker is not a forgery, it is a brick: Y carries torsion,
// the address looks completely ordinary and accepts deposits, and no quorum can
// ever sign for it because z*G is torsion-free and z*G = R + c*Y can never hold.
//
// The commitment reaches us only by being decoded, so rejecting torsion in
// Ed25519Point.UnmarshalBinary closes it off. This test splices a small-order
// point into a real serialized commitment to confirm the decode path is the one
// keygen actually uses.
func TestEd25519KeygenRejectsTorsionCommitment(t *testing.T) {
	group := curve.Ed25519{}

	secret := sample.Scalar(rand.Reader, group)
	poly := polynomial.NewPolynomial(group, 2, secret)
	phi := polynomial.NewPolynomialExponent(poly)

	honest, err := phi.MarshalBinary()
	require.NoError(t, err)
	require.NoError(t, polynomial.EmptyExponent(group).UnmarshalBinary(honest),
		"an honest commitment must decode")

	constant, err := phi.Constant().MarshalBinary()
	require.NoError(t, err)
	idx := bytes.Index(honest, constant)
	require.GreaterOrEqual(t, idx, 0, "constant coefficient must appear in the encoding")

	// The order-2 point (0, -1): a genuine curve point, so only a subgroup check
	// catches it.
	torsion, err := hex.DecodeString("ecffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f")
	require.NoError(t, err)

	tainted := append([]byte{}, honest...)
	copy(tainted[idx:idx+32], torsion)

	assert.Error(t, polynomial.EmptyExponent(group).UnmarshalBinary(tainted),
		"a commitment carrying torsion must not decode")
}

// TestEd25519RejectsWrongCurveConfig makes sure an Ed25519 signing session
// cannot be started against a key from another group.
func TestEd25519RejectsWrongCurveConfig(t *testing.T) {
	partyIDs := test.PartyIDs(3)
	results, err := test.RunProtocol(t, partyIDs, []byte("ed25519-wrong-curve"), func(id party.ID) protocol.StartFunc {
		return frost.KeygenSR25519(id, partyIDs, 1)
	})
	require.NoError(t, err)

	var config *frost.Config
	for _, result := range results {
		config = result.(*frost.Config)
		break
	}

	_, err = frost.SignEd25519(config, partyIDs[:2], []byte("m"))(nil)
	require.Error(t, err, "ed25519 signing must refuse a ristretto255 key")
	assert.Contains(t, err.Error(), "ed25519")
}