Merge pull request #2601 from vbrekher/fix/psbt-multi-a-finalizer

### psbt/finalizer.go
@@ -562,23 +562,23 @@ func finalizeTaprootInput(p *Packet, inIndex int) error {
 				"signature not found: %w", err)
 		}
 
-		// The witness stack will contain all signatures, followed by
-		// the script itself and then the control block.
+		// Make sure that all script spend signatures reference the same
+		// target leaf. Signing multiple possible execution paths at the same
+		// time is currently not supported by this library.
 		for idx, scriptSpendSig := range pInput.TaprootScriptSpendSig {
-			// Make sure that if there are indeed multiple
-			// signatures, they all reference the same leaf hash.
 			if !bytes.Equal(scriptSpendSig.LeafHash, targetLeafHash) {
 				return fmt.Errorf("script spend signature %d "+
 					"references different target leaf "+
 					"hash than first signature; only one "+
 					"script path is supported", idx)
 			}
+		}
 
-			sig := append([]byte{}, scriptSpendSig.Signature...)
-			if scriptSpendSig.SigHash != txscript.SigHashDefault {
-				sig = append(sig, byte(scriptSpendSig.SigHash))
-			}
-			witnessStack = append(witnessStack, sig)
+		witnessStack, err = taprootScriptSpendWitnessStack(
+			leafScript.Script, pInput.TaprootScriptSpendSig,
+		)
+		if err != nil {
+			return err
 		}
 
 		// Complete the witness stack with the executed script and the

### psbt/taproot_multi_a.go
@@ -0,0 +1,179 @@
+package psbt
+
+import (
+	"fmt"
+
+	"github.com/btcsuite/btcd/txscript/v2"
+	"github.com/btcsuite/btcd/wire/v2"
+)
+
+type taprootScriptToken struct {
+	opcode byte
+	data   []byte
+}
+
+// taprootScriptSpendWitnessStack returns the witness elements required before
+// the tapscript and control block for a script-path spend. multi_a scripts are
+// matched by pubkey instead of relying on PSBT signature slice ordering.
+func taprootScriptSpendWitnessStack(script []byte,
+	scriptSpendSigs []*TaprootScriptSpendSig) (wire.TxWitness, error) {
+
+	keys, threshold, isMultiA, err := parseTaprootMultiA(script)
+	if err != nil {
+		return nil, err
+	}
+
+	// Preserve the existing ordering behavior for script types the finalizer
+	// already handled. CHECKSIGADD scripts are parsed as multi_a below so an
+	// unsupported CHECKSIGADD construction cannot silently produce a witness.
+	if !isMultiA {
+		witnessStack := make(wire.TxWitness, 0, len(scriptSpendSigs))
+		for _, scriptSpendSig := range scriptSpendSigs {
+			witnessStack = append(
+				witnessStack, taprootScriptSpendSigBytes(scriptSpendSig),
+			)
+		}
+
+		return witnessStack, nil
+	}
+
+	keySet := make(map[string]struct{}, len(keys))
+	for _, key := range keys {
+		keySet[string(key)] = struct{}{}
+	}
+
+	sigByKey := make(map[string][]byte, len(scriptSpendSigs))
+	for idx, scriptSpendSig := range scriptSpendSigs {
+		key := string(scriptSpendSig.XOnlyPubKey)
+		if _, ok := keySet[key]; !ok {
+			return nil, fmt.Errorf("taproot script spend signature %d "+
+				"does not match a multi_a key: %w", idx,
+				ErrInvalidPsbtFormat)
+		}
+		if _, ok := sigByKey[key]; ok {
+			return nil, fmt.Errorf("duplicate taproot script spend "+
+				"signature for multi_a key: %w", ErrInvalidPsbtFormat)
+		}
+
+		sigByKey[key] = taprootScriptSpendSigBytes(scriptSpendSig)
+	}
+
+	available := 0
+	for _, key := range keys {
+		if _, ok := sigByKey[string(key)]; ok {
+			available++
+		}
+	}
+	if available < threshold {
+		return nil, ErrNotFinalizable
+	}
+
+	// NUMEQUAL requires exactly threshold successful signature checks. If
+	// the PSBT contains more signatures, select a deterministic subset in
+	// script order and leave the other witness positions empty.
+	selected := make([][]byte, len(keys))
+	remaining := threshold
+	for idx, key := range keys {
+		if remaining == 0 {
+			break
+		}
+
+		if sig, ok := sigByKey[string(key)]; ok {
+			selected[idx] = sig
+			remaining--
+		}
+	}
+
+	// CHECKSIG and CHECKSIGADD consume witness elements from the top of the
+	// stack, so multi_a signatures are supplied in reverse script-key order.
+	witnessStack := make(wire.TxWitness, 0, len(keys))
+	for idx := len(selected) - 1; idx >= 0; idx-- {
+		witnessStack = append(witnessStack, selected[idx])
+	}
+
+	return witnessStack, nil
+}
+
+// taprootScriptSpendSigBytes returns a script-spend signature with its
+// non-default sighash byte appended.
+func taprootScriptSpendSigBytes(scriptSpendSig *TaprootScriptSpendSig) []byte {
+	sig := append([]byte{}, scriptSpendSig.Signature...)
+	if scriptSpendSig.SigHash != txscript.SigHashDefault {
+		sig = append(sig, byte(scriptSpendSig.SigHash))
+	}
+
+	return sig
+}
+
+// parseTaprootMultiA recognizes the standard multi_a tapscript template:
+//
+//	<key> CHECKSIG [<key> CHECKSIGADD ...] <threshold> NUMEQUAL
+func parseTaprootMultiA(script []byte) ([][]byte, int, bool, error) {
+	tokenizer := txscript.MakeScriptTokenizer(0, script)
+	tokens := make([]taprootScriptToken, 0, 8)
+	hasCheckSigAdd := false
+	for tokenizer.Next() {
+		token := taprootScriptToken{
+			opcode: tokenizer.Opcode(),
+			data:   tokenizer.Data(),
+		}
+		if token.opcode == txscript.OP_CHECKSIGADD {
+			hasCheckSigAdd = true
+		}
+		tokens = append(tokens, token)
+	}
+	if tokenizer.Err() != nil {
+		return nil, 0, false, ErrUnsupportedScriptType
+	}
+
+	if len(tokens) < 4 || len(tokens[0].data) != 32 ||
+		tokens[1].opcode != txscript.OP_CHECKSIG {
+
+		if hasCheckSigAdd {
+			return nil, 0, false, ErrUnsupportedScriptType
+		}
+		return nil, 0, false, nil
+	}
+
+	keys := make([][]byte, 0, len(tokens)/2)
+	keys = append(keys, tokens[0].data)
+
+	idx := 2
+	for idx+1 < len(tokens) && len(tokens[idx].data) == 32 &&
+		tokens[idx+1].opcode == txscript.OP_CHECKSIGADD {
+
+		keys = append(keys, tokens[idx].data)
+		idx += 2
+	}
+
+	if idx+2 != len(tokens) || tokens[idx+1].opcode != txscript.OP_NUMEQUAL {
+		if hasCheckSigAdd {
+			return nil, 0, false, ErrUnsupportedScriptType
+		}
+		return nil, 0, false, nil
+	}
+
+	threshold, ok := taprootMultiAThreshold(tokens[idx])
+	if !ok || threshold < 1 || threshold > len(keys) {
+		return nil, 0, false, ErrUnsupportedScriptType
+	}
+
+	return keys, threshold, true, nil
+}
+
+// taprootMultiAThreshold decodes the threshold token used by multi_a.
+func taprootMultiAThreshold(token taprootScriptToken) (int, bool) {
+	if txscript.IsSmallInt(token.opcode) {
+		return txscript.AsSmallInt(token.opcode), true
+	}
+	if token.data == nil {
+		return 0, false
+	}
+
+	num, err := txscript.MakeScriptNum(token.data, true, 4)
+	if err != nil {
+		return 0, false
+	}
+
+	return int(num.Int32()), true
+}

### psbt/taproot_multi_a_test.go
@@ -0,0 +1,178 @@
+package psbt
+
+import (
+	"bytes"
+	"testing"
+
+	"github.com/btcsuite/btcd/txscript/v2"
+	"github.com/btcsuite/btcd/wire/v2"
+	"github.com/stretchr/testify/require"
+)
+
+func TestTaprootMultiAFinalizerOrdersSignatures(t *testing.T) {
+	keyA := bytes.Repeat([]byte{0x02}, 32)
+	keyB := bytes.Repeat([]byte{0x03}, 32)
+	sigA := bytes.Repeat([]byte{0xaa}, 64)
+	sigB := bytes.Repeat([]byte{0xbb}, 64)
+
+	script, err := txscript.NewScriptBuilder().
+		AddData(keyA).AddOp(txscript.OP_CHECKSIG).
+		AddData(keyB).AddOp(txscript.OP_CHECKSIGADD).
+		AddInt64(2).AddOp(txscript.OP_NUMEQUAL).Script()
+	require.NoError(t, err)
+
+	testCases := []struct {
+		name string
+		sigs []*TaprootScriptSpendSig
+	}{
+		{
+			name: "script order",
+			sigs: []*TaprootScriptSpendSig{
+				{XOnlyPubKey: keyA, Signature: sigA},
+				{XOnlyPubKey: keyB, Signature: sigB},
+			},
+		},
+		{
+			name: "reverse script order",
+			sigs: []*TaprootScriptSpendSig{
+				{XOnlyPubKey: keyB, Signature: sigB},
+				{XOnlyPubKey: keyA, Signature: sigA},
+			},
+		},
+	}
+
+	for _, testCase := range testCases {
+		t.Run(testCase.name, func(t *testing.T) {
+			packet := taprootMultiATestPacket(
+				t, script, testCase.sigs,
+			)
+
+			require.NoError(t, MaybeFinalizeAll(packet))
+			finalTx, err := Extract(packet)
+			require.NoError(t, err)
+			require.Equal(t, wire.TxWitness{
+				sigB,
+				sigA,
+				script,
+				make([]byte, 33),
+			}, finalTx.TxIn[0].Witness)
+		})
+	}
+}
+
+func TestTaprootMultiAFinalizerAddsPlaceholders(t *testing.T) {
+	keyA := bytes.Repeat([]byte{0x02}, 32)
+	keyB := bytes.Repeat([]byte{0x03}, 32)
+	keyC := bytes.Repeat([]byte{0x04}, 32)
+	sigA := bytes.Repeat([]byte{0xaa}, 64)
+	sigC := bytes.Repeat([]byte{0xcc}, 64)
+
+	script, err := txscript.NewScriptBuilder().
+		AddData(keyA).AddOp(txscript.OP_CHECKSIG).
+		AddData(keyB).AddOp(txscript.OP_CHECKSIGADD).
+		AddData(keyC).AddOp(txscript.OP_CHECKSIGADD).
+		AddInt64(2).AddOp(txscript.OP_NUMEQUAL).Script()
+	require.NoError(t, err)
+
+	packet := taprootMultiATestPacket(t, script, []*TaprootScriptSpendSig{
+		{XOnlyPubKey: keyA, Signature: sigA},
+		{XOnlyPubKey: keyC, Signature: sigC},
+	})
+
+	require.NoError(t, MaybeFinalizeAll(packet))
+	finalTx, err := Extract(packet)
+	require.NoError(t, err)
+	require.Equal(t, wire.TxWitness{
+		sigC,
+		[]byte{},
+		sigA,
+		script,
+		make([]byte, 33),
+	}, finalTx.TxIn[0].Witness)
+}
+
+func TestTaprootMultiAFinalizerIgnoresExcessSignatures(t *testing.T) {
+	keyA := bytes.Repeat([]byte{0x02}, 32)
+	keyB := bytes.Repeat([]byte{0x03}, 32)
+	keyC := bytes.Repeat([]byte{0x04}, 32)
+	sigA := bytes.Repeat([]byte{0xaa}, 64)
+	sigB := bytes.Repeat([]byte{0xbb}, 64)
+	sigC := bytes.Repeat([]byte{0xcc}, 64)
+
+	script, err := txscript.NewScriptBuilder().
+		AddData(keyA).AddOp(txscript.OP_CHECKSIG).
+		AddData(keyB).AddOp(txscript.OP_CHECKSIGADD).
+		AddData(keyC).AddOp(txscript.OP_CHECKSIGADD).
+		AddInt64(2).AddOp(txscript.OP_NUMEQUAL).Script()
+	require.NoError(t, err)
+
+	packet := taprootMultiATestPacket(t, script, []*TaprootScriptSpendSig{
+		{XOnlyPubKey: keyA, Signature: sigA},
+		{XOnlyPubKey: keyB, Signature: sigB},
+		{XOnlyPubKey: keyC, Signature: sigC},
+	})
+
+	require.NoError(t, MaybeFinalizeAll(packet))
+	finalTx, err := Extract(packet)
+	require.NoError(t, err)
+	require.Equal(t, wire.TxWitness{
+		[]byte{},
+		sigB,
+		sigA,
+		script,
+		make([]byte, 33),
+	}, finalTx.TxIn[0].Witness)
+}
+
+func TestTaprootMultiAFinalizerRejectsInsufficientSignatures(t *testing.T) {
+	keyA := bytes.Repeat([]byte{0x02}, 32)
+	keyB := bytes.Repeat([]byte{0x03}, 32)
+	keyC := bytes.Repeat([]byte{0x04}, 32)
+	sigA := bytes.Repeat([]byte{0xaa}, 64)
+
+	script, err := txscript.NewScriptBuilder().
+		AddData(keyA).AddOp(txscript.OP_CHECKSIG).
+		AddData(keyB).AddOp(txscript.OP_CHECKSIGADD).
+		AddData(keyC).AddOp(txscript.OP_CHECKSIGADD).
+		AddInt64(2).AddOp(txscript.OP_NUMEQUAL).Script()
+	require.NoError(t, err)
+
+	packet := taprootMultiATestPacket(t, script, []*TaprootScriptSpendSig{
+		{XOnlyPubKey: keyA, Signature: sigA},
+	})
+
+	_, err = MaybeFinalize(packet, 0)
+	require.ErrorIs(t, err, ErrNotFinalizable)
+}
+
+func taprootMultiATestPacket(t *testing.T, script []byte,
+	sigs []*TaprootScriptSpendSig) *Packet {
+
+	t.Helper()
+
+	tx := wire.NewMsgTx(2)
+	tx.AddTxIn(wire.NewTxIn(&wire.OutPoint{}, nil, nil))
+	tx.AddTxOut(wire.NewTxOut(0, nil))
+
+	packet, err := NewFromUnsignedTx(tx)
+	require.NoError(t, err)
+
+	pkScript := append(
+		[]byte{txscript.OP_1, txscript.OP_DATA_32}, make([]byte, 32)...,
+	)
+	packet.Inputs[0].WitnessUtxo = wire.NewTxOut(1, pkScript)
+
+	leafHash := txscript.NewBaseTapLeaf(script).TapHash()
+	for _, sig := range sigs {
+		sig.LeafHash = append([]byte{}, leafHash[:]...)
+	}
+
+	packet.Inputs[0].TaprootLeafScript = []*TaprootTapLeafScript{{
+		ControlBlock: make([]byte, 33),
+		Script:       script,
+		LeafVersion:  txscript.BaseLeafVersion,
+	}}
+	packet.Inputs[0].TaprootScriptSpendSig = sigs
+
+	return packet
+}