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