11170835610

Committed 03 Oct 2024 10:41PM UTC coverage: 49.188% (-9.6%) from 58.738%

Build # 11170835610

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #9154 from ziggie1984/master

multi: bump btcd version.

Run Details

3 of 6 new or added lines in 6 files covered. (50.0%)

26110 existing lines in 428 files now uncovered.

97359 of 197934 relevant lines covered (49.19%)

1.04 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

95.2

/internal/musig2v040/keys.go

// Copyright 2013-2022 The btcsuite developers

package musig2v040

import (
        "bytes"
        "fmt"
        "sort"

        "github.com/btcsuite/btcd/btcec/v2"
        "github.com/btcsuite/btcd/btcec/v2/schnorr"
        "github.com/btcsuite/btcd/chaincfg/chainhash"
        secp "github.com/decred/dcrd/dcrec/secp256k1/v4"
)

var (
        // KeyAggTagList is the tagged hash tag used to compute the hash of the
        // list of sorted public keys.
        KeyAggTagList = []byte("KeyAgg list")

        // KeyAggTagCoeff is the tagged hash tag used to compute the key
        // aggregation coefficient for each key.
        KeyAggTagCoeff = []byte("KeyAgg coefficient")

        // ErrTweakedKeyIsInfinity is returned if while tweaking a key, we end
        // up with the point at infinity.
        ErrTweakedKeyIsInfinity = fmt.Errorf("tweaked key is infinity point")

        // ErrTweakedKeyOverflows is returned if a tweaking key is larger than
        // 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141.
        ErrTweakedKeyOverflows = fmt.Errorf("tweaked key is to large")
)

// sortableKeys defines a type of slice of public keys that implements the sort
// interface for BIP 340 keys.
type sortableKeys []*btcec.PublicKey

// Less reports whether the element with index i must sort before the element
// with index j.
func (s sortableKeys) Less(i, j int) bool {
        // TODO(roasbeef): more efficient way to compare...
        keyIBytes := schnorr.SerializePubKey(s[i])
        keyJBytes := schnorr.SerializePubKey(s[j])

        return bytes.Compare(keyIBytes, keyJBytes) == -1
}

// Swap swaps the elements with indexes i and j.
func (s sortableKeys) Swap(i, j int) {
        s[i], s[j] = s[j], s[i]
}

// Len is the number of elements in the collection.
func (s sortableKeys) Len() int {
        return len(s)
}

// sortKeys takes a set of schnorr public keys and returns a new slice that is
// a copy of the keys sorted in lexicographical order bytes on the x-only
// pubkey serialization.
func sortKeys(keys []*btcec.PublicKey) []*btcec.PublicKey {
        keySet := sortableKeys(keys)
        if sort.IsSorted(keySet) {
                return keys
        }

        sort.Sort(keySet)
        return keySet
}

// keyHashFingerprint computes the tagged hash of the series of (sorted) public
// keys passed as input. This is used to compute the aggregation coefficient
// for each key. The final computation is:
//   - H(tag=KeyAgg list, pk1 || pk2..)
func keyHashFingerprint(keys []*btcec.PublicKey, sort bool) []byte {
        if sort {
                keys = sortKeys(keys)
        }

        // We'll create a single buffer and slice into that so the bytes buffer
        // doesn't continually need to grow the underlying buffer.
        keyAggBuf := make([]byte, 32*len(keys))
        keyBytes := bytes.NewBuffer(keyAggBuf[0:0])
        for _, key := range keys {
                keyBytes.Write(schnorr.SerializePubKey(key))
        }

        h := chainhash.TaggedHash(KeyAggTagList, keyBytes.Bytes())
        return h[:]
}

// keyBytesEqual returns true if two keys are the same from the PoV of BIP
// 340's 32-byte x-only public keys.
func keyBytesEqual(a, b *btcec.PublicKey) bool {
        return bytes.Equal(
                schnorr.SerializePubKey(a),
                schnorr.SerializePubKey(b),
        )
}

// aggregationCoefficient computes the key aggregation coefficient for the
// specified target key. The coefficient is computed as:
//   - H(tag=KeyAgg coefficient, keyHashFingerprint(pks) || pk)
func aggregationCoefficient(keySet []*btcec.PublicKey,
        targetKey *btcec.PublicKey, keysHash []byte,
        secondKeyIdx int) *btcec.ModNScalar {

        var mu btcec.ModNScalar

        // If this is the second key, then this coefficient is just one.
        if secondKeyIdx != -1 && keyBytesEqual(keySet[secondKeyIdx], targetKey) {
                return mu.SetInt(1)
        }

        // Otherwise, we'll compute the full finger print hash for this given
        // key and then use that to compute the coefficient tagged hash:
        //  * H(tag=KeyAgg coefficient, keyHashFingerprint(pks, pk) || pk)
        var coefficientBytes [64]byte
        copy(coefficientBytes[:], keysHash[:])
        copy(coefficientBytes[32:], schnorr.SerializePubKey(targetKey))

        muHash := chainhash.TaggedHash(KeyAggTagCoeff, coefficientBytes[:])

        mu.SetByteSlice(muHash[:])

        return &mu
}

// secondUniqueKeyIndex returns the index of the second unique key. If all keys
// are the same, then a value of -1 is returned.
func secondUniqueKeyIndex(keySet []*btcec.PublicKey, sort bool) int {
        if sort {
                keySet = sortKeys(keySet)
        }

        // Find the first key that isn't the same as the very first key (second
        // unique key).
        for i := range keySet {
                if !keyBytesEqual(keySet[i], keySet[0]) {
                        return i
                }
        }

        // A value of negative one is used to indicate that all the keys in the
        // sign set are actually equal, which in practice actually makes musig2
        // useless, but we need a value to distinguish this case.
        return -1
}

// KeyTweakDesc describes a tweak to be applied to the aggregated public key
// generation and signing process. The IsXOnly specifies if the target key
// should be converted to an x-only public key before tweaking.
type KeyTweakDesc struct {
        // Tweak is the 32-byte value that will modify the public key.
        Tweak [32]byte

        // IsXOnly if true, then the public key will be mapped to an x-only key
        // before the tweaking operation is applied.
        IsXOnly bool
}

// KeyAggOption is a functional option argument that allows callers to specify
// more or less information that has been pre-computed to the main routine.
type KeyAggOption func(*keyAggOption)

// keyAggOption houses the set of functional options that modify key
// aggregation.
type keyAggOption struct {
        // keyHash is the output of keyHashFingerprint for a given set of keys.
        keyHash []byte

        // uniqueKeyIndex is the pre-computed index of the second unique key.
        uniqueKeyIndex *int

        // tweaks specifies a series of tweaks to be applied to the aggregated
        // public key.
        tweaks []KeyTweakDesc

        // taprootTweak controls if the tweaks above should be applied in a BIP
        // 340 style.
        taprootTweak bool

        // bip86Tweak specifies that the taproot tweak should be done in a BIP
        // 86 style, where we don't expect an actual tweak and instead just
        // commit to the public key itself.
        bip86Tweak bool
}

// WithKeysHash allows key aggregation to be optimize, by allowing the caller
// to specify the hash of all the keys.
func WithKeysHash(keyHash []byte) KeyAggOption {
        return func(o *keyAggOption) {
                o.keyHash = keyHash
        }
}

// WithUniqueKeyIndex allows the caller to specify the index of the second
// unique key.
func WithUniqueKeyIndex(idx int) KeyAggOption {
        return func(o *keyAggOption) {
                i := idx
                o.uniqueKeyIndex = &i
        }
}

// WithKeyTweaks allows a caller to specify a series of 32-byte tweaks that
// should be applied to the final aggregated public key.
func WithKeyTweaks(tweaks ...KeyTweakDesc) KeyAggOption {
        return func(o *keyAggOption) {
                o.tweaks = tweaks
        }
}

// WithTaprootKeyTweak specifies that within this context, the final key should
// use the taproot tweak as defined in BIP 341: outputKey = internalKey +
// h_tapTweak(internalKey || scriptRoot). In this case, the aggregated key
// before the tweak will be used as the internal key.
//
// This option should be used instead of WithKeyTweaks when the aggregated key
// is intended to be used as a taproot output key that commits to a script
// root.
func WithTaprootKeyTweak(scriptRoot []byte) KeyAggOption {
        return func(o *keyAggOption) {
                var tweak [32]byte
                copy(tweak[:], scriptRoot[:])

                o.tweaks = []KeyTweakDesc{
                        {
                                Tweak:   tweak,
                                IsXOnly: true,
                        },
                }
                o.taprootTweak = true
        }
}

// WithBIP86KeyTweak specifies that then during key aggregation, the BIP 86
// tweak which just commits to the hash of the serialized public key should be
// used. This option should be used when signing with a key that was derived
// using BIP 86.
func WithBIP86KeyTweak() KeyAggOption {
        return func(o *keyAggOption) {
                o.tweaks = []KeyTweakDesc{
                        {
                                IsXOnly: true,
                        },
                }
                o.taprootTweak = true
                o.bip86Tweak = true
        }
}

// defaultKeyAggOptions returns the set of default arguments for key
// aggregation.
func defaultKeyAggOptions() *keyAggOption {
        return &keyAggOption{}
}

// hasEvenY returns true if the affine representation of the passed jacobian
// point has an even y coordinate.
//
// TODO(roasbeef): double check, can just check the y coord even not jacobian?
func hasEvenY(pJ btcec.JacobianPoint) bool {
        pJ.ToAffine()
        p := btcec.NewPublicKey(&pJ.X, &pJ.Y)
        keyBytes := p.SerializeCompressed()
        return keyBytes[0] == secp.PubKeyFormatCompressedEven
}

// tweakKey applies a tweaks to the passed public key using the specified
// tweak. The parityAcc and tweakAcc are returned (in that order) which
// includes the accumulate ration of the parity factor and the tweak multiplied
// by the parity factor. The xOnly bool specifies if this is to be an x-only
// tweak or not.
func tweakKey(keyJ btcec.JacobianPoint, parityAcc btcec.ModNScalar, tweak [32]byte,
        tweakAcc btcec.ModNScalar,
        xOnly bool) (btcec.JacobianPoint, btcec.ModNScalar, btcec.ModNScalar, error) {

        // First we'll compute the new parity factor for this key. If the key has
        // an odd y coordinate (not even), then we'll need to negate it (multiply
        // by -1 mod n, in this case).
        var parityFactor btcec.ModNScalar
        if xOnly && !hasEvenY(keyJ) {
                parityFactor.SetInt(1).Negate()
        } else {
                parityFactor.SetInt(1)
        }

        // Next, map the tweak into a mod n integer so we can use it for
        // manipulations below.
        tweakInt := new(btcec.ModNScalar)
        overflows := tweakInt.SetBytes(&tweak)
        if overflows == 1 {
                return keyJ, parityAcc, tweakAcc, ErrTweakedKeyOverflows
        }

        // Next, we'll compute: Q_i = g*Q + t*G, where g is our parityFactor and t
        // is the tweakInt above. We'll space things out a bit to make it easier to
        // follow.
        //
        // First compute t*G:
        var tweakedGenerator btcec.JacobianPoint
        btcec.ScalarBaseMultNonConst(tweakInt, &tweakedGenerator)

        // Next compute g*Q:
        btcec.ScalarMultNonConst(&parityFactor, &keyJ, &keyJ)

        // Finally add both of them together to get our final
        // tweaked point.
        btcec.AddNonConst(&tweakedGenerator, &keyJ, &keyJ)

        // As a sanity check, make sure that we didn't just end up with the
        // point at infinity.
        if keyJ == infinityPoint {
                return keyJ, parityAcc, tweakAcc, ErrTweakedKeyIsInfinity
        }

        // As a final wrap up step, we'll accumulate the parity
        // factor and also this tweak into the final set of accumulators.
        parityAcc.Mul(&parityFactor)
        tweakAcc.Mul(&parityFactor).Add(tweakInt)

        return keyJ, parityAcc, tweakAcc, nil
}

// AggregateKey is a final aggregated key along with a possible version of the
// key without any tweaks applied.
type AggregateKey struct {
        // FinalKey is the final aggregated key which may include one or more
        // tweaks applied to it.
        FinalKey *btcec.PublicKey

        // PreTweakedKey is the aggregated *before* any tweaks have been
        // applied.  This should be used as the internal key in taproot
        // contexts.
        PreTweakedKey *btcec.PublicKey
}

// AggregateKeys takes a list of possibly unsorted keys and returns a single
// aggregated key as specified by the musig2 key aggregation algorithm. A nil
// value can be passed for keyHash, which causes this function to re-derive it.
// In addition to the combined public key, the parity accumulator and the tweak
// accumulator are returned as well.
func AggregateKeys(keys []*btcec.PublicKey, sort bool,
        keyOpts ...KeyAggOption) (
        *AggregateKey, *btcec.ModNScalar, *btcec.ModNScalar, error) {

        // First, parse the set of optional signing options.
        opts := defaultKeyAggOptions()
        for _, option := range keyOpts {
                option(opts)
        }

        // Sort the set of public key so we know we're working with them in
        // sorted order for all the routines below.
        if sort {
                keys = sortKeys(keys)
        }

        // The caller may provide the hash of all the keys as an optimization
        // during signing, as it already needs to be computed.
        if opts.keyHash == nil {
                opts.keyHash = keyHashFingerprint(keys, sort)
        }

        // A caller may also specify the unique key index themselves so we
        // don't need to re-compute it.
        if opts.uniqueKeyIndex == nil {
                idx := secondUniqueKeyIndex(keys, sort)
                opts.uniqueKeyIndex = &idx
        }

        // For each key, we'll compute the intermediate blinded key: a_i*P_i,
        // where a_i is the aggregation coefficient for that key, and P_i is
        // the key itself, then accumulate that (addition) into the main final
        // key: P = P_1 + P_2 ... P_N.
        var finalKeyJ btcec.JacobianPoint
        for _, key := range keys {
                // Port the key over to Jacobian coordinates as we need it in
                // this format for the routines below.
                var keyJ btcec.JacobianPoint
                key.AsJacobian(&keyJ)

                // Compute the aggregation coefficient for the key, then
                // multiply it by the key itself: P_i' = a_i*P_i.
                var tweakedKeyJ btcec.JacobianPoint
                a := aggregationCoefficient(
                        keys, key, opts.keyHash, *opts.uniqueKeyIndex,
                )
                btcec.ScalarMultNonConst(a, &keyJ, &tweakedKeyJ)

                // Finally accumulate this into the final key in an incremental
                // fashion.
                btcec.AddNonConst(&finalKeyJ, &tweakedKeyJ, &finalKeyJ)
        }

        // We'll copy over the key at this point, since this represents the
        // aggregated key before any tweaks have been applied. This'll be used
        // as the internal key for script path proofs.
        finalKeyJ.ToAffine()
        combinedKey := btcec.NewPublicKey(&finalKeyJ.X, &finalKeyJ.Y)

        // At this point, if this is a taproot tweak, then we'll modify the
        // base tweak value to use the BIP 341 tweak value.
        if opts.taprootTweak {
                // Emulate the same behavior as txscript.ComputeTaprootOutputKey
                // which only operates on the x-only public key.
                key, _ := schnorr.ParsePubKey(schnorr.SerializePubKey(
                        combinedKey,
                ))

                // We only use the actual tweak bytes if we're not committing
                // to a BIP-0086 key only spend output. Otherwise, we just
                // commit to the internal key and an empty byte slice as the
                // root hash.
                tweakBytes := []byte{}
                if !opts.bip86Tweak {
                        tweakBytes = opts.tweaks[0].Tweak[:]
                }

                // Compute the taproot key tagged hash of:
                // h_tapTweak(internalKey || scriptRoot). We only do this for
                // the first one, as you can only specify a single tweak when
                // using the taproot mode with this API.
                tapTweakHash := chainhash.TaggedHash(
                        chainhash.TagTapTweak, schnorr.SerializePubKey(key),
                        tweakBytes,
                )
                opts.tweaks[0].Tweak = *tapTweakHash
        }

        var (
                err       error
                tweakAcc  btcec.ModNScalar
                parityAcc btcec.ModNScalar
        )
        parityAcc.SetInt(1)

        // In this case we have a set of tweaks, so we'll incrementally apply
        // each one, until we have our final tweaked key, and the related
        // accumulators.
        for i := 1; i <= len(opts.tweaks); i++ {
                finalKeyJ, parityAcc, tweakAcc, err = tweakKey(
                        finalKeyJ, parityAcc, opts.tweaks[i-1].Tweak, tweakAcc,
                        opts.tweaks[i-1].IsXOnly,
                )
                if err != nil {
                        return nil, nil, nil, err
                }
        }

        finalKeyJ.ToAffine()
        finalKey := btcec.NewPublicKey(&finalKeyJ.X, &finalKeyJ.Y)

        return &AggregateKey{
                PreTweakedKey: combinedKey,
                FinalKey:      finalKey,
        }, &parityAcc, &tweakAcc, nil
}

1	// Copyright 2013-2022 The btcsuite developers
2
3	package musig2v040
4
5	import (
6	"bytes"
7	"fmt"
8	"sort"
9
10	"github.com/btcsuite/btcd/btcec/v2"
11	"github.com/btcsuite/btcd/btcec/v2/schnorr"
12	"github.com/btcsuite/btcd/chaincfg/chainhash"
13	secp "github.com/decred/dcrd/dcrec/secp256k1/v4"
14	)
15
16	var (
17	// KeyAggTagList is the tagged hash tag used to compute the hash of the
18	// list of sorted public keys.
19	KeyAggTagList = []byte("KeyAgg list")
20
21	// KeyAggTagCoeff is the tagged hash tag used to compute the key
22	// aggregation coefficient for each key.
23	KeyAggTagCoeff = []byte("KeyAgg coefficient")
24
25	// ErrTweakedKeyIsInfinity is returned if while tweaking a key, we end
26	// up with the point at infinity.
27	ErrTweakedKeyIsInfinity = fmt.Errorf("tweaked key is infinity point")
28
29	// ErrTweakedKeyOverflows is returned if a tweaking key is larger than
30	// 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141.
31	ErrTweakedKeyOverflows = fmt.Errorf("tweaked key is to large")
32	)
33
34	// sortableKeys defines a type of slice of public keys that implements the sort
35	// interface for BIP 340 keys.
36	type sortableKeys []*btcec.PublicKey
37
38	// Less reports whether the element with index i must sort before the element
39	// with index j.
40	func (s sortableKeys) Less(i, j int) bool {	2✔
41	// TODO(roasbeef): more efficient way to compare...	2✔
42	keyIBytes := schnorr.SerializePubKey(s[i])	2✔
43	keyJBytes := schnorr.SerializePubKey(s[j])	2✔
44		2✔
45	return bytes.Compare(keyIBytes, keyJBytes) == -1	2✔
46	}	2✔
47
48	// Swap swaps the elements with indexes i and j.
49	func (s sortableKeys) Swap(i, j int) {	2✔
50	s[i], s[j] = s[j], s[i]	2✔
51	}	2✔
52
53	// Len is the number of elements in the collection.
54	func (s sortableKeys) Len() int {	2✔
55	return len(s)	2✔
56	}	2✔
57
58	// sortKeys takes a set of schnorr public keys and returns a new slice that is
59	// a copy of the keys sorted in lexicographical order bytes on the x-only
60	// pubkey serialization.
61	func sortKeys(keys []btcec.PublicKey) []btcec.PublicKey {	2✔
62	keySet := sortableKeys(keys)	2✔
63	if sort.IsSorted(keySet) {	4✔
64	return keys	2✔
65	}	2✔
66
67	sort.Sort(keySet)	2✔
68	return keySet	2✔
69	}
70
71	// keyHashFingerprint computes the tagged hash of the series of (sorted) public
72	// keys passed as input. This is used to compute the aggregation coefficient
73	// for each key. The final computation is:
74	// - H(tag=KeyAgg list, pk1 \|\| pk2..)
75	func keyHashFingerprint(keys []*btcec.PublicKey, sort bool) []byte {	2✔
76	if sort {	4✔
77	keys = sortKeys(keys)	2✔
78	}	2✔
79
80	// We'll create a single buffer and slice into that so the bytes buffer
81	// doesn't continually need to grow the underlying buffer.
82	keyAggBuf := make([]byte, 32*len(keys))	2✔
83	keyBytes := bytes.NewBuffer(keyAggBuf[0:0])	2✔
84	for _, key := range keys {	4✔
85	keyBytes.Write(schnorr.SerializePubKey(key))	2✔
86	}	2✔
87
88	h := chainhash.TaggedHash(KeyAggTagList, keyBytes.Bytes())	2✔
89	return h[:]	2✔
90	}
91
92	// keyBytesEqual returns true if two keys are the same from the PoV of BIP
93	// 340's 32-byte x-only public keys.
94	func keyBytesEqual(a, b *btcec.PublicKey) bool {	2✔
95	return bytes.Equal(	2✔
96	schnorr.SerializePubKey(a),	2✔
97	schnorr.SerializePubKey(b),	2✔
98	)	2✔
99	}	2✔
100
101	// aggregationCoefficient computes the key aggregation coefficient for the
102	// specified target key. The coefficient is computed as:
103	// - H(tag=KeyAgg coefficient, keyHashFingerprint(pks) \|\| pk)
104	func aggregationCoefficient(keySet []*btcec.PublicKey,
105	targetKey *btcec.PublicKey, keysHash []byte,
106	secondKeyIdx int) *btcec.ModNScalar {	2✔
107		2✔
108	var mu btcec.ModNScalar	2✔
109		2✔
110	// If this is the second key, then this coefficient is just one.	2✔
111	if secondKeyIdx != -1 && keyBytesEqual(keySet[secondKeyIdx], targetKey) {	4✔
112	return mu.SetInt(1)	2✔
113	}	2✔
114
115	// Otherwise, we'll compute the full finger print hash for this given
116	// key and then use that to compute the coefficient tagged hash:
117	// * H(tag=KeyAgg coefficient, keyHashFingerprint(pks, pk) \|\| pk)
118	var coefficientBytes [64]byte	2✔
119	copy(coefficientBytes[:], keysHash[:])	2✔
120	copy(coefficientBytes[32:], schnorr.SerializePubKey(targetKey))	2✔
121		2✔
122	muHash := chainhash.TaggedHash(KeyAggTagCoeff, coefficientBytes[:])	2✔
123		2✔
124	mu.SetByteSlice(muHash[:])	2✔
125		2✔
126	return &mu	2✔
127	}
128
129	// secondUniqueKeyIndex returns the index of the second unique key. If all keys
130	// are the same, then a value of -1 is returned.
131	func secondUniqueKeyIndex(keySet []*btcec.PublicKey, sort bool) int {	2✔
132	if sort {	4✔
133	keySet = sortKeys(keySet)	2✔
134	}	2✔
135
136	// Find the first key that isn't the same as the very first key (second
137	// unique key).
138	for i := range keySet {	4✔
139	if !keyBytesEqual(keySet[i], keySet[0]) {	4✔
140	return i	2✔
141	}	2✔
142	}
143
144	// A value of negative one is used to indicate that all the keys in the
145	// sign set are actually equal, which in practice actually makes musig2
146	// useless, but we need a value to distinguish this case.
UNCOV 147	return -1	×
148	}
149
150	// KeyTweakDesc describes a tweak to be applied to the aggregated public key
151	// generation and signing process. The IsXOnly specifies if the target key
152	// should be converted to an x-only public key before tweaking.
153	type KeyTweakDesc struct {
154	// Tweak is the 32-byte value that will modify the public key.
155	Tweak [32]byte
156
157	// IsXOnly if true, then the public key will be mapped to an x-only key
158	// before the tweaking operation is applied.
159	IsXOnly bool
160	}
161
162	// KeyAggOption is a functional option argument that allows callers to specify
163	// more or less information that has been pre-computed to the main routine.
164	type KeyAggOption func(*keyAggOption)
165
166	// keyAggOption houses the set of functional options that modify key
167	// aggregation.
168	type keyAggOption struct {
169	// keyHash is the output of keyHashFingerprint for a given set of keys.
170	keyHash []byte
171
172	// uniqueKeyIndex is the pre-computed index of the second unique key.
173	uniqueKeyIndex *int
174
175	// tweaks specifies a series of tweaks to be applied to the aggregated
176	// public key.
177	tweaks []KeyTweakDesc
178
179	// taprootTweak controls if the tweaks above should be applied in a BIP
180	// 340 style.
181	taprootTweak bool
182
183	// bip86Tweak specifies that the taproot tweak should be done in a BIP
184	// 86 style, where we don't expect an actual tweak and instead just
185	// commit to the public key itself.
186	bip86Tweak bool
187	}
188
189	// WithKeysHash allows key aggregation to be optimize, by allowing the caller
190	// to specify the hash of all the keys.
191	func WithKeysHash(keyHash []byte) KeyAggOption {	2✔
192	return func(o *keyAggOption) {	4✔
193	o.keyHash = keyHash	2✔
194	}	2✔
195	}
196
197	// WithUniqueKeyIndex allows the caller to specify the index of the second
198	// unique key.
199	func WithUniqueKeyIndex(idx int) KeyAggOption {	2✔
200	return func(o *keyAggOption) {	4✔
201	i := idx	2✔
202	o.uniqueKeyIndex = &i	2✔
203	}	2✔
204	}
205
206	// WithKeyTweaks allows a caller to specify a series of 32-byte tweaks that
207	// should be applied to the final aggregated public key.
UNCOV 208	func WithKeyTweaks(tweaks ...KeyTweakDesc) KeyAggOption {	×
UNCOV 209	return func(o *keyAggOption) {	×
UNCOV 210	o.tweaks = tweaks	×
UNCOV 211	}	×
212	}
213
214	// WithTaprootKeyTweak specifies that within this context, the final key should
215	// use the taproot tweak as defined in BIP 341: outputKey = internalKey +
216	// h_tapTweak(internalKey \|\| scriptRoot). In this case, the aggregated key
217	// before the tweak will be used as the internal key.
218	//
219	// This option should be used instead of WithKeyTweaks when the aggregated key
220	// is intended to be used as a taproot output key that commits to a script
221	// root.
222	func WithTaprootKeyTweak(scriptRoot []byte) KeyAggOption {	2✔
223	return func(o *keyAggOption) {	4✔
224	var tweak [32]byte	2✔
225	copy(tweak[:], scriptRoot[:])	2✔
226		2✔
227	o.tweaks = []KeyTweakDesc{	2✔
228	{	2✔
229	Tweak: tweak,	2✔
230	IsXOnly: true,	2✔
231	},	2✔
232	}	2✔
233	o.taprootTweak = true	2✔
234	}	2✔
235	}
236
237	// WithBIP86KeyTweak specifies that then during key aggregation, the BIP 86
238	// tweak which just commits to the hash of the serialized public key should be
239	// used. This option should be used when signing with a key that was derived
240	// using BIP 86.
241	func WithBIP86KeyTweak() KeyAggOption {	2✔
242	return func(o *keyAggOption) {	4✔
243	o.tweaks = []KeyTweakDesc{	2✔
244	{	2✔
245	IsXOnly: true,	2✔
246	},	2✔
247	}	2✔
248	o.taprootTweak = true	2✔
249	o.bip86Tweak = true	2✔
250	}	2✔
251	}
252
253	// defaultKeyAggOptions returns the set of default arguments for key
254	// aggregation.
255	func defaultKeyAggOptions() *keyAggOption {	2✔
256	return &keyAggOption{}	2✔
257	}	2✔
258
259	// hasEvenY returns true if the affine representation of the passed jacobian
260	// point has an even y coordinate.
261	//
262	// TODO(roasbeef): double check, can just check the y coord even not jacobian?
263	func hasEvenY(pJ btcec.JacobianPoint) bool {	2✔
264	pJ.ToAffine()	2✔
265	p := btcec.NewPublicKey(&pJ.X, &pJ.Y)	2✔
266	keyBytes := p.SerializeCompressed()	2✔
267	return keyBytes[0] == secp.PubKeyFormatCompressedEven	2✔
268	}	2✔
269
270	// tweakKey applies a tweaks to the passed public key using the specified
271	// tweak. The parityAcc and tweakAcc are returned (in that order) which
272	// includes the accumulate ration of the parity factor and the tweak multiplied
273	// by the parity factor. The xOnly bool specifies if this is to be an x-only
274	// tweak or not.
275	func tweakKey(keyJ btcec.JacobianPoint, parityAcc btcec.ModNScalar, tweak [32]byte,
276	tweakAcc btcec.ModNScalar,
277	xOnly bool) (btcec.JacobianPoint, btcec.ModNScalar, btcec.ModNScalar, error) {	2✔
278		2✔
279	// First we'll compute the new parity factor for this key. If the key has	2✔
280	// an odd y coordinate (not even), then we'll need to negate it (multiply	2✔
281	// by -1 mod n, in this case).	2✔
282	var parityFactor btcec.ModNScalar	2✔
283	if xOnly && !hasEvenY(keyJ) {	4✔
284	parityFactor.SetInt(1).Negate()	2✔
285	} else {	4✔
286	parityFactor.SetInt(1)	2✔
287	}	2✔
288
289	// Next, map the tweak into a mod n integer so we can use it for
290	// manipulations below.
291	tweakInt := new(btcec.ModNScalar)	2✔
292	overflows := tweakInt.SetBytes(&tweak)	2✔
293	if overflows == 1 {	2✔
UNCOV 294	return keyJ, parityAcc, tweakAcc, ErrTweakedKeyOverflows	×
UNCOV 295	}	×
296
297	// Next, we'll compute: Q_i = gQ + tG, where g is our parityFactor and t
298	// is the tweakInt above. We'll space things out a bit to make it easier to
299	// follow.
300	//
301	// First compute t*G:
302	var tweakedGenerator btcec.JacobianPoint	2✔
303	btcec.ScalarBaseMultNonConst(tweakInt, &tweakedGenerator)	2✔
304		2✔
305	// Next compute g*Q:	2✔
306	btcec.ScalarMultNonConst(&parityFactor, &keyJ, &keyJ)	2✔
307		2✔
308	// Finally add both of them together to get our final	2✔
309	// tweaked point.	2✔
310	btcec.AddNonConst(&tweakedGenerator, &keyJ, &keyJ)	2✔
311		2✔
312	// As a sanity check, make sure that we didn't just end up with the	2✔
313	// point at infinity.	2✔
314	if keyJ == infinityPoint {	2✔
UNCOV 315	return keyJ, parityAcc, tweakAcc, ErrTweakedKeyIsInfinity	×
UNCOV 316	}	×
317
318	// As a final wrap up step, we'll accumulate the parity
319	// factor and also this tweak into the final set of accumulators.
320	parityAcc.Mul(&parityFactor)	2✔
321	tweakAcc.Mul(&parityFactor).Add(tweakInt)	2✔
322		2✔
323	return keyJ, parityAcc, tweakAcc, nil	2✔
324	}
325
326	// AggregateKey is a final aggregated key along with a possible version of the
327	// key without any tweaks applied.
328	type AggregateKey struct {
329	// FinalKey is the final aggregated key which may include one or more
330	// tweaks applied to it.
331	FinalKey *btcec.PublicKey
332
333	// PreTweakedKey is the aggregated before any tweaks have been
334	// applied. This should be used as the internal key in taproot
335	// contexts.
336	PreTweakedKey *btcec.PublicKey
337	}
338
339	// AggregateKeys takes a list of possibly unsorted keys and returns a single
340	// aggregated key as specified by the musig2 key aggregation algorithm. A nil
341	// value can be passed for keyHash, which causes this function to re-derive it.
342	// In addition to the combined public key, the parity accumulator and the tweak
343	// accumulator are returned as well.
344	func AggregateKeys(keys []*btcec.PublicKey, sort bool,
345	keyOpts ...KeyAggOption) (
346	AggregateKey, btcec.ModNScalar, *btcec.ModNScalar, error) {	2✔
347		2✔
348	// First, parse the set of optional signing options.	2✔
349	opts := defaultKeyAggOptions()	2✔
350	for _, option := range keyOpts {	4✔
351	option(opts)	2✔
352	}	2✔
353
354	// Sort the set of public key so we know we're working with them in
355	// sorted order for all the routines below.
356	if sort {	4✔
357	keys = sortKeys(keys)	2✔
358	}	2✔
359
360	// The caller may provide the hash of all the keys as an optimization
361	// during signing, as it already needs to be computed.
362	if opts.keyHash == nil {	4✔
363	opts.keyHash = keyHashFingerprint(keys, sort)	2✔
364	}	2✔
365
366	// A caller may also specify the unique key index themselves so we
367	// don't need to re-compute it.
368	if opts.uniqueKeyIndex == nil {	4✔
369	idx := secondUniqueKeyIndex(keys, sort)	2✔
370	opts.uniqueKeyIndex = &idx	2✔
371	}	2✔
372
373	// For each key, we'll compute the intermediate blinded key: a_i*P_i,
374	// where a_i is the aggregation coefficient for that key, and P_i is
375	// the key itself, then accumulate that (addition) into the main final
376	// key: P = P_1 + P_2 ... P_N.
377	var finalKeyJ btcec.JacobianPoint	2✔
378	for _, key := range keys {	4✔
379	// Port the key over to Jacobian coordinates as we need it in	2✔
380	// this format for the routines below.	2✔
381	var keyJ btcec.JacobianPoint	2✔
382	key.AsJacobian(&keyJ)	2✔
383		2✔
384	// Compute the aggregation coefficient for the key, then	2✔
385	// multiply it by the key itself: P_i' = a_i*P_i.	2✔
386	var tweakedKeyJ btcec.JacobianPoint	2✔
387	a := aggregationCoefficient(	2✔
388	keys, key, opts.keyHash, *opts.uniqueKeyIndex,	2✔
389	)	2✔
390	btcec.ScalarMultNonConst(a, &keyJ, &tweakedKeyJ)	2✔
391		2✔
392	// Finally accumulate this into the final key in an incremental	2✔
393	// fashion.	2✔
394	btcec.AddNonConst(&finalKeyJ, &tweakedKeyJ, &finalKeyJ)	2✔
395	}	2✔
396
397	// We'll copy over the key at this point, since this represents the
398	// aggregated key before any tweaks have been applied. This'll be used
399	// as the internal key for script path proofs.
400	finalKeyJ.ToAffine()	2✔
401	combinedKey := btcec.NewPublicKey(&finalKeyJ.X, &finalKeyJ.Y)	2✔
402		2✔
403	// At this point, if this is a taproot tweak, then we'll modify the	2✔
404	// base tweak value to use the BIP 341 tweak value.	2✔
405	if opts.taprootTweak {	4✔
406	// Emulate the same behavior as txscript.ComputeTaprootOutputKey	2✔
407	// which only operates on the x-only public key.	2✔
408	key, _ := schnorr.ParsePubKey(schnorr.SerializePubKey(	2✔
409	combinedKey,	2✔
410	))	2✔
411		2✔
412	// We only use the actual tweak bytes if we're not committing	2✔
413	// to a BIP-0086 key only spend output. Otherwise, we just	2✔
414	// commit to the internal key and an empty byte slice as the	2✔
415	// root hash.	2✔
416	tweakBytes := []byte{}	2✔
417	if !opts.bip86Tweak {	4✔
418	tweakBytes = opts.tweaks[0].Tweak[:]	2✔
419	}	2✔
420
421	// Compute the taproot key tagged hash of:
422	// h_tapTweak(internalKey \|\| scriptRoot). We only do this for
423	// the first one, as you can only specify a single tweak when
424	// using the taproot mode with this API.
425	tapTweakHash := chainhash.TaggedHash(	2✔
426	chainhash.TagTapTweak, schnorr.SerializePubKey(key),	2✔
427	tweakBytes,	2✔
428	)	2✔
429	opts.tweaks[0].Tweak = *tapTweakHash	2✔
430	}
431
432	var (	2✔
433	err error	2✔
434	tweakAcc btcec.ModNScalar	2✔
435	parityAcc btcec.ModNScalar	2✔
436	)	2✔
437	parityAcc.SetInt(1)	2✔
438		2✔
439	// In this case we have a set of tweaks, so we'll incrementally apply	2✔
440	// each one, until we have our final tweaked key, and the related	2✔
441	// accumulators.	2✔
442	for i := 1; i <= len(opts.tweaks); i++ {	4✔
443	finalKeyJ, parityAcc, tweakAcc, err = tweakKey(	2✔
444	finalKeyJ, parityAcc, opts.tweaks[i-1].Tweak, tweakAcc,	2✔
445	opts.tweaks[i-1].IsXOnly,	2✔
446	)	2✔
447	if err != nil {	2✔
UNCOV 448	return nil, nil, nil, err	×
UNCOV 449	}	×
450	}
451
452	finalKeyJ.ToAffine()	2✔
453	finalKey := btcec.NewPublicKey(&finalKeyJ.X, &finalKeyJ.Y)	2✔
454		2✔
455	return &AggregateKey{	2✔
456	PreTweakedKey: combinedKey,	2✔
457	FinalKey: finalKey,	2✔
458	}, &parityAcc, &tweakAcc, nil	2✔
459	}

lightningnetwork / lnd / 11170835610

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous