1 // Copyright (c) 2013-2022 The btcsuite developers
2 3 package schnorr
4 5 import (
6 "fmt"
7 8 "github.com/btcsuite/btcd/btcec/v2"
9 "github.com/btcsuite/btcd/chaincfg/chainhash"
10 secp "github.com/decred/dcrd/dcrec/secp256k1/v4"
11 ecdsa_schnorr "github.com/decred/dcrd/dcrec/secp256k1/v4/schnorr"
12 )
13 14 const (
15 // SignatureSize is the size of an encoded Schnorr signature.
16 SignatureSize = 64
17 18 // scalarSize is the size of an encoded big endian scalar.
19 scalarSize = 32
20 )
21 22 var (
23 // rfc6979ExtraDataV0 is the extra data to feed to RFC6979 when
24 // generating the deterministic nonce for the BIP-340 scheme. This
25 // ensures the same nonce is not generated for the same message and key
26 // as for other signing algorithms such as ECDSA.
27 //
28 // It is equal to SHA-256([]byte("BIP-340")).
29 rfc6979ExtraDataV0 = [32]uint8{
30 0xa3, 0xeb, 0x4c, 0x18, 0x2f, 0xae, 0x7e, 0xf4,
31 0xe8, 0x10, 0xc6, 0xee, 0x13, 0xb0, 0xe9, 0x26,
32 0x68, 0x6d, 0x71, 0xe8, 0x7f, 0x39, 0x4f, 0x79,
33 0x9c, 0x00, 0xa5, 0x21, 0x03, 0xcb, 0x4e, 0x17,
34 }
35 )
36 37 // Signature is a type representing a Schnorr signature.
38 type Signature struct {
39 r btcec.FieldVal
40 s btcec.ModNScalar
41 }
42 43 // NewSignature instantiates a new signature given some r and s values.
44 func NewSignature(r *btcec.FieldVal, s *btcec.ModNScalar) *Signature {
45 var sig Signature
46 sig.r.Set(r).Normalize()
47 sig.s.Set(s)
48 return &sig
49 }
50 51 // Serialize returns the Schnorr signature in the more strict format.
52 //
53 // The signatures are encoded as
54 //
55 // sig[0:32] x coordinate of the point R, encoded as a big-endian uint256
56 // sig[32:64] s, encoded also as big-endian uint256
57 func (sig Signature) Serialize() []byte {
58 // Total length of returned signature is the length of r and s.
59 var b [SignatureSize]byte
60 sig.r.PutBytesUnchecked(b[0:32])
61 sig.s.PutBytesUnchecked(b[32:64])
62 return b[:]
63 }
64 65 // ParseSignature parses a signature according to the BIP-340 specification and
66 // enforces the following additional restrictions specific to secp256k1:
67 //
68 // - The r component must be in the valid range for secp256k1 field elements
69 // - The s component must be in the valid range for secp256k1 scalars
70 func ParseSignature(sig []byte) (*Signature, error) {
71 // The signature must be the correct length.
72 sigLen := len(sig)
73 if sigLen < SignatureSize {
74 str := fmt.Sprintf("malformed signature: too short: %d < %d", sigLen,
75 SignatureSize)
76 return nil, signatureError(ecdsa_schnorr.ErrSigTooShort, str)
77 }
78 if sigLen > SignatureSize {
79 str := fmt.Sprintf("malformed signature: too long: %d > %d", sigLen,
80 SignatureSize)
81 return nil, signatureError(ecdsa_schnorr.ErrSigTooLong, str)
82 }
83 84 // The signature is validly encoded at this point, however, enforce
85 // additional restrictions to ensure r is in the range [0, p-1], and s is in
86 // the range [0, n-1] since valid Schnorr signatures are required to be in
87 // that range per spec.
88 var r btcec.FieldVal
89 if overflow := r.SetByteSlice(sig[0:32]); overflow {
90 str := "invalid signature: r >= field prime"
91 return nil, signatureError(ecdsa_schnorr.ErrSigRTooBig, str)
92 }
93 var s btcec.ModNScalar
94 s.SetByteSlice(sig[32:64])
95 96 // Return the signature.
97 return NewSignature(&r, &s), nil
98 }
99 100 // IsEqual compares this Signature instance to the one passed, returning true
101 // if both Signatures are equivalent. A signature is equivalent to another, if
102 // they both have the same scalar value for R and S.
103 func (sig Signature) IsEqual(otherSig *Signature) bool {
104 return sig.r.Equals(&otherSig.r) && sig.s.Equals(&otherSig.s)
105 }
106 107 // schnorrVerify attempt to verify the signature for the provided hash and
108 // secp256k1 public key and either returns nil if successful or a specific error
109 // indicating why it failed if not successful.
110 //
111 // This differs from the exported Verify method in that it returns a specific
112 // error to support better testing while the exported method simply returns a
113 // bool indicating success or failure.
114 func schnorrVerify(sig *Signature, hash []byte, pubKeyBytes []byte) error {
115 // The algorithm for producing a BIP-340 signature is described in
116 // README.md and is reproduced here for reference:
117 //
118 // 1. Fail if m is not 32 bytes
119 // 2. P = lift_x(int(pk)).
120 // 3. r = int(sig[0:32]); fail is r >= p.
121 // 4. s = int(sig[32:64]); fail if s >= n.
122 // 5. e = int(tagged_hash("BIP0340/challenge", bytes(r) || bytes(P) || M)) mod n.
123 // 6. R = s*G - e*P
124 // 7. Fail if is_infinite(R)
125 // 8. Fail if not hash_even_y(R)
126 // 9. Fail is x(R) != r.
127 // 10. Return success iff failure did not occur before reaching this point.
128 129 // Step 1.
130 //
131 // Fail if m is not 32 bytes
132 if len(hash) != scalarSize {
133 str := fmt.Sprintf("wrong size for message (got %v, want %v)",
134 len(hash), scalarSize)
135 return signatureError(ecdsa_schnorr.ErrInvalidHashLen, str)
136 }
137 138 // Step 2.
139 //
140 // P = lift_x(int(pk))
141 //
142 // Fail if P is not a point on the curve
143 pubKey, err := ParsePubKey(pubKeyBytes)
144 if err != nil {
145 return err
146 }
147 if !pubKey.IsOnCurve() {
148 str := "pubkey point is not on curve"
149 return signatureError(ecdsa_schnorr.ErrPubKeyNotOnCurve, str)
150 }
151 152 // Step 3.
153 //
154 // Fail if r >= p
155 //
156 // Note this is already handled by the fact r is a field element.
157 158 // Step 4.
159 //
160 // Fail if s >= n
161 //
162 // Note this is already handled by the fact s is a mod n scalar.
163 164 // Step 5.
165 //
166 // e = int(tagged_hash("BIP0340/challenge", bytes(r) || bytes(P) || M)) mod n.
167 var rBytes [32]byte
168 sig.r.PutBytesUnchecked(rBytes[:])
169 pBytes := SerializePubKey(pubKey)
170 171 commitment := chainhash.TaggedHash(
172 chainhash.TagBIP0340Challenge, rBytes[:], pBytes, hash,
173 )
174 175 var e btcec.ModNScalar
176 e.SetBytes((*[32]byte)(commitment))
177 178 // Negate e here so we can use AddNonConst below to subtract the s*G
179 // point from e*P.
180 e.Negate()
181 182 // Step 6.
183 //
184 // R = s*G - e*P
185 var P, R, sG, eP btcec.JacobianPoint
186 pubKey.AsJacobian(&P)
187 btcec.ScalarBaseMultNonConst(&sig.s, &sG)
188 btcec.ScalarMultNonConst(&e, &P, &eP)
189 btcec.AddNonConst(&sG, &eP, &R)
190 191 // Step 7.
192 //
193 // Fail if R is the point at infinity
194 if (R.X.IsZero() && R.Y.IsZero()) || R.Z.IsZero() {
195 str := "calculated R point is the point at infinity"
196 return signatureError(ecdsa_schnorr.ErrSigRNotOnCurve, str)
197 }
198 199 // Step 8.
200 //
201 // Fail if R.y is odd
202 //
203 // Note that R must be in affine coordinates for this check.
204 R.ToAffine()
205 if R.Y.IsOdd() {
206 str := "calculated R y-value is odd"
207 return signatureError(ecdsa_schnorr.ErrSigRYIsOdd, str)
208 }
209 210 // Step 9.
211 //
212 // Verified if R.x == r
213 //
214 // Note that R must be in affine coordinates for this check.
215 if !sig.r.Equals(&R.X) {
216 str := "calculated R point was not given R"
217 return signatureError(ecdsa_schnorr.ErrUnequalRValues, str)
218 }
219 220 // Step 10.
221 //
222 // Return success iff failure did not occur before reaching this point.
223 return nil
224 }
225 226 // Verify returns whether or not the signature is valid for the provided hash
227 // and secp256k1 public key.
228 func (sig *Signature) Verify(hash []byte, pubKey *btcec.PublicKey) bool {
229 pubkeyBytes := SerializePubKey(pubKey)
230 return schnorrVerify(sig, hash, pubkeyBytes) == nil
231 }
232 233 // zeroArray zeroes the memory of a scalar array.
234 func zeroArray(a *[scalarSize]byte) {
235 for i := 0; i < scalarSize; i++ {
236 a[i] = 0x00
237 }
238 }
239 240 // schnorrSign generates a BIP-340 signature over the secp256k1 curve for the
241 // provided hash (which should be the result of hashing a larger message) using
242 // the given nonce and private key. The produced signature is deterministic
243 // (same message, nonce, and key yield the same signature) and canonical.
244 //
245 // WARNING: The hash MUST be 32 bytes and both the nonce and private keys must
246 // NOT be 0. Since this is an internal use function, these preconditions MUST
247 // be satisfied by the caller.
248 func schnorrSign(privKey, nonce *btcec.ModNScalar, pubKey *btcec.PublicKey, hash []byte,
249 opts *signOptions) (*Signature, error) {
250 251 // The algorithm for producing a BIP-340 signature is described in
252 // README.md and is reproduced here for reference:
253 //
254 // G = curve generator
255 // n = curve order
256 // d = private key
257 // m = message
258 // a = input randomness
259 // r, s = signature
260 //
261 // 1. d' = int(d)
262 // 2. Fail if m is not 32 bytes
263 // 3. Fail if d = 0 or d >= n
264 // 4. P = d'*G
265 // 5. Negate d if P.y is odd
266 // 6. t = bytes(d) xor tagged_hash("BIP0340/aux", t || bytes(P) || m)
267 // 7. rand = tagged_hash("BIP0340/nonce", a)
268 // 8. k' = int(rand) mod n
269 // 9. Fail if k' = 0
270 // 10. R = 'k*G
271 // 11. Negate k if R.y id odd
272 // 12. e = tagged_hash("BIP0340/challenge", bytes(R) || bytes(P) || m) mod n
273 // 13. sig = bytes(R) || bytes((k + e*d)) mod n
274 // 14. If Verify(bytes(P), m, sig) fails, abort.
275 // 15. return sig.
276 //
277 // Note that the set of functional options passed in may modify the
278 // above algorithm. Namely if CustomNonce is used, then steps 6-8 are
279 // replaced with a process that generates the nonce using rfc6979. If
280 // FastSign is passed, then we skip set 14.
281 282 // NOTE: Steps 1-9 are performed by the caller.
283 284 //
285 // Step 10.
286 //
287 // R = kG
288 var R btcec.JacobianPoint
289 k := *nonce
290 btcec.ScalarBaseMultNonConst(&k, &R)
291 292 // Step 11.
293 //
294 // Negate nonce k if R.y is odd (R.y is the y coordinate of the point R)
295 //
296 // Note that R must be in affine coordinates for this check.
297 R.ToAffine()
298 if R.Y.IsOdd() {
299 k.Negate()
300 }
301 302 // Step 12.
303 //
304 // e = tagged_hash("BIP0340/challenge", bytes(R) || bytes(P) || m) mod n
305 pBytes := SerializePubKey(pubKey)
306 commitment := chainhash.TaggedHash(
307 chainhash.TagBIP0340Challenge, R.X.Bytes()[:], pBytes, hash,
308 )
309 310 var e btcec.ModNScalar
311 if overflow := e.SetBytes((*[32]byte)(commitment)); overflow != 0 {
312 k.Zero()
313 str := "hash of (r || P || m) too big"
314 return nil, signatureError(ecdsa_schnorr.ErrSchnorrHashValue, str)
315 }
316 317 // Step 13.
318 //
319 // s = k + e*d mod n
320 s := new(btcec.ModNScalar).Mul2(&e, privKey).Add(&k)
321 k.Zero()
322 323 sig := NewSignature(&R.X, s)
324 325 // Step 14.
326 //
327 // If Verify(bytes(P), m, sig) fails, abort.
328 if !opts.fastSign {
329 if err := schnorrVerify(sig, hash, pBytes); err != nil {
330 return nil, err
331 }
332 }
333 334 // Step 15.
335 //
336 // Return (r, s)
337 return sig, nil
338 }
339 340 // SignOption is a functional option argument that allows callers to modify the
341 // way we generate BIP-340 schnorr signatures.
342 type SignOption func(*signOptions)
343 344 // signOptions houses the set of functional options that can be used to modify
345 // the method used to generate the BIP-340 signature.
346 type signOptions struct {
347 // fastSign determines if we'll skip the check at the end of the routine
348 // where we attempt to verify the produced signature.
349 fastSign bool
350 351 // authNonce allows the user to pass in their own nonce information, which
352 // is useful for schemes like mu-sig.
353 authNonce *[32]byte
354 }
355 356 // defaultSignOptions returns the default set of signing operations.
357 func defaultSignOptions() *signOptions {
358 return &signOptions{}
359 }
360 361 // FastSign forces signing to skip the extra verification step at the end.
362 // Performance sensitive applications may opt to use this option to speed up the
363 // signing operation.
364 func FastSign() SignOption {
365 return func(o *signOptions) {
366 o.fastSign = true
367 }
368 }
369 370 // CustomNonce allows users to pass in a custom set of auxData that's used as
371 // input randomness to generate the nonce used during signing. Users may want
372 // to specify this custom value when using multi-signatures schemes such as
373 // Mu-Sig2. If this option isn't set, then rfc6979 will be used to generate the
374 // nonce material.
375 func CustomNonce(auxData [32]byte) SignOption {
376 return func(o *signOptions) {
377 o.authNonce = &auxData
378 }
379 }
380 381 // Sign generates an BIP-340 signature over the secp256k1 curve for the
382 // provided hash (which should be the result of hashing a larger message) using
383 // the given private key. The produced signature is deterministic (same
384 // message and same key yield the same signature) and canonical.
385 //
386 // Note that the current signing implementation has a few remaining variable
387 // time aspects which make use of the private key and the generated nonce,
388 // which can expose the signer to constant time attacks. As a result, this
389 // function should not be used in situations where there is the possibility of
390 // someone having EM field/cache/etc access.
391 func Sign(privKey *btcec.PrivateKey, hash []byte,
392 signOpts ...SignOption) (*Signature, error) {
393 394 // First, parse the set of optional signing options.
395 opts := defaultSignOptions()
396 for _, option := range signOpts {
397 option(opts)
398 }
399 400 // The algorithm for producing a BIP-340 signature is described in
401 // README.md and is reproduced here for reference:
402 //
403 // G = curve generator
404 // n = curve order
405 // d = private key
406 // m = message
407 // a = input randomness
408 // r, s = signature
409 //
410 // 1. d' = int(d)
411 // 2. Fail if m is not 32 bytes
412 // 3. Fail if d = 0 or d >= n
413 // 4. P = d'*G
414 // 5. Negate d if P.y is odd
415 // 6. t = bytes(d) xor tagged_hash("BIP0340/aux", t || bytes(P) || m)
416 // 7. rand = tagged_hash("BIP0340/nonce", a)
417 // 8. k' = int(rand) mod n
418 // 9. Fail if k' = 0
419 // 10. R = 'k*G
420 // 11. Negate k if R.y id odd
421 // 12. e = tagged_hash("BIP0340/challenge", bytes(R) || bytes(P) || mod) mod n
422 // 13. sig = bytes(R) || bytes((k + e*d)) mod n
423 // 14. If Verify(bytes(P), m, sig) fails, abort.
424 // 15. return sig.
425 //
426 // Note that the set of functional options passed in may modify the
427 // above algorithm. Namely if CustomNonce is used, then steps 6-8 are
428 // replaced with a process that generates the nonce using rfc6979. If
429 // FastSign is passed, then we skip set 14.
430 431 // Step 1.
432 //
433 // d' = int(d)
434 var privKeyScalar btcec.ModNScalar
435 privKeyScalar.Set(&privKey.Key)
436 437 // Step 2.
438 //
439 // Fail if m is not 32 bytes
440 if len(hash) != scalarSize {
441 str := fmt.Sprintf("wrong size for message hash (got %v, want %v)",
442 len(hash), scalarSize)
443 return nil, signatureError(ecdsa_schnorr.ErrInvalidHashLen, str)
444 }
445 446 // Step 3.
447 //
448 // Fail if d = 0 or d >= n
449 if privKeyScalar.IsZero() {
450 str := "private key is zero"
451 return nil, signatureError(ecdsa_schnorr.ErrPrivateKeyIsZero, str)
452 }
453 454 // Step 4.
455 //
456 // P = 'd*G
457 pub := privKey.PubKey()
458 459 // Step 5.
460 //
461 // Negate d if P.y is odd.
462 pubKeyBytes := pub.SerializeCompressed()
463 if pubKeyBytes[0] == secp.PubKeyFormatCompressedOdd {
464 privKeyScalar.Negate()
465 }
466 467 // At this point, we check to see if a CustomNonce has been passed in,
468 // and if so, then we'll deviate from the main routine here by
469 // generating the nonce value as specified by BIP-0340.
470 if opts.authNonce != nil {
471 // Step 6.
472 //
473 // t = bytes(d) xor tagged_hash("BIP0340/aux", a)
474 privBytes := privKeyScalar.Bytes()
475 t := chainhash.TaggedHash(
476 chainhash.TagBIP0340Aux, (*opts.authNonce)[:],
477 )
478 for i := 0; i < len(t); i++ {
479 t[i] ^= privBytes[i]
480 }
481 482 // Step 7.
483 //
484 // rand = tagged_hash("BIP0340/nonce", t || bytes(P) || m)
485 //
486 // We snip off the first byte of the serialized pubkey, as we
487 // only need the x coordinate and not the market byte.
488 rand := chainhash.TaggedHash(
489 chainhash.TagBIP0340Nonce, t[:], pubKeyBytes[1:], hash,
490 )
491 492 // Step 8.
493 //
494 // k'= int(rand) mod n
495 var kPrime btcec.ModNScalar
496 kPrime.SetBytes((*[32]byte)(rand))
497 498 // Step 9.
499 //
500 // Fail if k' = 0
501 if kPrime.IsZero() {
502 str := fmt.Sprintf("generated nonce is zero")
503 return nil, signatureError(ecdsa_schnorr.ErrSchnorrHashValue, str)
504 }
505 506 sig, err := schnorrSign(&privKeyScalar, &kPrime, pub, hash, opts)
507 kPrime.Zero()
508 if err != nil {
509 return nil, err
510 }
511 512 return sig, nil
513 }
514 515 var privKeyBytes [scalarSize]byte
516 privKeyScalar.PutBytes(&privKeyBytes)
517 defer zeroArray(&privKeyBytes)
518 for iteration := uint32(0); ; iteration++ {
519 // Step 6-9.
520 //
521 // Use RFC6979 to generate a deterministic nonce k in [1, n-1]
522 // parameterized by the private key, message being signed, extra data
523 // that identifies the scheme, and an iteration count
524 k := btcec.NonceRFC6979(
525 privKeyBytes[:], hash, rfc6979ExtraDataV0[:], nil, iteration,
526 )
527 528 // Steps 10-15.
529 sig, err := schnorrSign(&privKeyScalar, k, pub, hash, opts)
530 k.Zero()
531 if err != nil {
532 // Try again with a new nonce.
533 continue
534 }
535 536 return sig, nil
537 }
538 }
539