Skip to main content

k256/
schnorr.rs

1//! Taproot Schnorr signatures as defined in [BIP340].
2//!
3//! # About
4//!
5//! [Schnorr signatures] are a simple group-based digital signature scheme with
6//! a number of desirable properties relating to security and composability:
7//!
8//! - Provably secure: strongly unforgeable under chosen message attack (SUF-CMA).
9//! - Non-malleable: signatures cannot be altered by an attacker and still verify.
10//! - Linear: multiple parties can collaborate to produce a valid signature
11//!   a.k.a. multisignatures.
12//!
13//! Originally described in the late 1980s by their eponymous creator Claus
14//! Schnorr, they were patent-encumbered and thus lingered in obscurity until
15//! the [relevant patents] expired in 2010.
16//!
17//! Since then, Schnorr signatures have seen something of a resurgence, with
18//! [EdDSA] and its concrete instantiation Ed25519 over the Curve25519 elliptic
19//! curve becoming the first Schnorr variant to see mainstream standardization.
20//!
21//! The Taproot upgrade to Bitcoin includes a variant of Schnorr which operates
22//! over the secp256k1 elliptic curve, and is specified in [BIP340].
23//! That is the variant which is implemented by this crate.
24//!
25//! Because Taproot Schnorr is intended for use in consensus-critical
26//! applications (e.g. Bitcoin), it is fully specified such that no two
27//! implementations should disagree on the validity of a signature.
28//!
29//! # Usage
30//!
31#![cfg_attr(all(feature = "getrandom", feature = "schnorr"), doc = "```")]
32#![cfg_attr(
33    not(all(feature = "getrandom", feature = "schnorr")),
34    doc = "```ignore"
35)]
36//! # fn main() -> Result<(), Box<dyn core::error::Error>> {
37//! // NOTE: requires the `getrandom` and `schnorr` crate features are enabled
38//! use k256::{
39//!     elliptic_curve::Generate,
40//!     schnorr::{
41//!         signature::{Signer, Verifier},
42//!         SigningKey, VerifyingKey
43//!     }
44//! };
45//!
46//! //
47//! // Signing
48//! //
49//! let signing_key = SigningKey::generate(); // serialize with `.to_bytes()`
50//! let verifying_key_bytes = signing_key.verifying_key().to_bytes(); // 32-bytes
51//!
52//! let message = b"Schnorr signatures prove knowledge of a secret in the random oracle model";
53//! let signature = signing_key.sign(message); // returns `k256::schnorr::Signature`
54//!
55//! //
56//! // Verification
57//! //
58//! let verifying_key = VerifyingKey::from_bytes(&verifying_key_bytes)?;
59//! verifying_key.verify(message, &signature)?;
60//! # Ok(())
61//! # }
62//! ```
63//!
64//! [Schnorr signatures]: https://en.wikipedia.org/wiki/Schnorr_signature
65//! [BIP340]: https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki
66//! [relevant patents]: https://patents.google.com/patent/US4995082
67//! [EdDSA]: https://en.wikipedia.org/wiki/EdDSA
68
69#![allow(non_snake_case, clippy::many_single_char_names)]
70
71mod signing;
72mod verifying;
73
74pub use self::{signing::SigningKey, verifying::VerifyingKey};
75pub use signature::{self, Error, rand_core::CryptoRng};
76
77use crate::{FieldBytes, NonZeroScalar, arithmetic::FieldElement};
78use core::fmt;
79use elliptic_curve::subtle::ConstantTimeEq;
80use sha2::{Digest, Sha256};
81use signature::Result;
82
83const AUX_TAG: &[u8] = b"BIP0340/aux";
84const NONCE_TAG: &[u8] = b"BIP0340/nonce";
85const CHALLENGE_TAG: &[u8] = b"BIP0340/challenge";
86
87/// Taproot Schnorr signature serialized as bytes.
88pub type SignatureBytes = [u8; Signature::BYTE_SIZE];
89
90/// Taproot Schnorr signature as defined in [BIP340].
91///
92/// [BIP340]: https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki
93#[derive(Copy, Clone)]
94pub struct Signature {
95    r: FieldElement,
96    s: NonZeroScalar,
97}
98
99impl Signature {
100    /// Size of a Taproot Schnorr signature in bytes.
101    pub const BYTE_SIZE: usize = 64;
102
103    /// Serialize this signature as bytes.
104    #[must_use]
105    pub fn to_bytes(&self) -> SignatureBytes {
106        let mut ret = [0; Self::BYTE_SIZE];
107        let (r_bytes, s_bytes) = ret.split_at_mut(Self::BYTE_SIZE / 2);
108        r_bytes.copy_from_slice(&self.r.to_bytes());
109        s_bytes.copy_from_slice(&self.s.to_bytes());
110        ret
111    }
112
113    /// Get the `r` component of this signature.
114    fn r(&self) -> &FieldElement {
115        &self.r
116    }
117
118    /// Get the `s` component of this signature.
119    fn s(&self) -> &NonZeroScalar {
120        &self.s
121    }
122
123    /// Split this signature into its `r` and `s` components.
124    fn split(&self) -> (&FieldElement, &NonZeroScalar) {
125        (self.r(), self.s())
126    }
127
128    /// Parse a Taproot Schnorr from a byte array.
129    ///
130    /// # Errors
131    /// Returns [`Error`] if the signature failed to parse successfully.
132    pub fn from_bytes(bytes: &SignatureBytes) -> Result<Self> {
133        let components = FieldBytes::slice_as_chunks(bytes).0;
134        let r_bytes = components[0];
135        let s_bytes = components[1];
136
137        let r = FieldElement::from_bytes(&r_bytes)
138            .into_option()
139            .ok_or_else(Error::new)?;
140
141        // one of the rules for valid signatures: !is_infinite(R);
142        if r.is_zero().into() {
143            return Err(Error::new());
144        }
145
146        let s = NonZeroScalar::try_from(s_bytes.as_slice()).map_err(|_| Error::new())?;
147
148        Ok(Self { r, s })
149    }
150
151    /// Parse a Taproot Schnorr from a byte slice.
152    ///
153    /// # Errors
154    /// Returns [`Error`] if `bytes` is not 64-bytes (i.e. [`Signature::BYTE_SIZE`]) long or if it
155    /// otherwise failed to parse successfully.
156    pub fn from_slice(bytes: &[u8]) -> Result<Self> {
157        SignatureBytes::try_from(bytes)
158            .map_err(|_| Error::new())?
159            .try_into()
160    }
161}
162
163impl Eq for Signature {}
164
165impl From<Signature> for SignatureBytes {
166    fn from(signature: Signature) -> SignatureBytes {
167        signature.to_bytes()
168    }
169}
170
171impl From<&Signature> for SignatureBytes {
172    fn from(signature: &Signature) -> SignatureBytes {
173        signature.to_bytes()
174    }
175}
176
177impl PartialEq for Signature {
178    fn eq(&self, other: &Self) -> bool {
179        (self.r == other.r) && (self.s.ct_eq(&other.s).into())
180    }
181}
182
183impl TryFrom<SignatureBytes> for Signature {
184    type Error = Error;
185
186    fn try_from(signature: SignatureBytes) -> Result<Signature> {
187        Signature::from_bytes(&signature)
188    }
189}
190
191impl TryFrom<&SignatureBytes> for Signature {
192    type Error = Error;
193
194    fn try_from(signature: &SignatureBytes) -> Result<Signature> {
195        Signature::from_bytes(signature)
196    }
197}
198
199impl TryFrom<&[u8]> for Signature {
200    type Error = Error;
201
202    fn try_from(bytes: &[u8]) -> Result<Signature> {
203        Signature::from_slice(bytes)
204    }
205}
206
207impl fmt::Debug for Signature {
208    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
209        write!(f, "{:?}", self.to_bytes())
210    }
211}
212
213impl signature::SignatureEncoding for Signature {
214    type Repr = SignatureBytes;
215
216    fn to_bytes(&self) -> Self::Repr {
217        self.into()
218    }
219}
220
221fn tagged_hash(tag: &[u8]) -> Sha256 {
222    let tag_hash = Sha256::digest(tag);
223    let mut digest = Sha256::new();
224    digest.update(tag_hash);
225    digest.update(tag_hash);
226    digest
227}
228
229// Test vectors from:
230// https://github.com/bitcoin/bips/blob/master/bip-0340/test-vectors.csv
231#[cfg(test)]
232mod tests {
233    use super::{Signature, SigningKey, VerifyingKey};
234    use hex_literal::hex;
235    use signature::hazmat::PrehashVerifier;
236
237    /// Signing test vector
238    struct SignVector {
239        /// Index of test case
240        index: u8,
241
242        /// Signing key
243        secret_key: [u8; 32],
244
245        /// Verifying key
246        public_key: [u8; 32],
247
248        /// Auxiliary randomness value
249        aux_rand: [u8; 32],
250
251        /// Message digest
252        message: [u8; 32],
253
254        /// Expected signature
255        signature: [u8; 64],
256    }
257
258    /// BIP340 signing test vectors: index 0-3
259    const BIP340_SIGN_VECTORS: &[SignVector] = &[
260        SignVector {
261            index: 0,
262            secret_key: hex!("0000000000000000000000000000000000000000000000000000000000000003"),
263            public_key: hex!("F9308A019258C31049344F85F89D5229B531C845836F99B08601F113BCE036F9"),
264            aux_rand: hex!("0000000000000000000000000000000000000000000000000000000000000000"),
265            message: hex!("0000000000000000000000000000000000000000000000000000000000000000"),
266            signature: hex!(
267                "E907831F80848D1069A5371B402410364BDF1C5F8307B0084C55F1CE2DCA8215
268                 25F66A4A85EA8B71E482A74F382D2CE5EBEEE8FDB2172F477DF4900D310536C0"
269            ),
270        },
271        SignVector {
272            index: 1,
273            secret_key: hex!("B7E151628AED2A6ABF7158809CF4F3C762E7160F38B4DA56A784D9045190CFEF"),
274            public_key: hex!("DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659"),
275            aux_rand: hex!("0000000000000000000000000000000000000000000000000000000000000001"),
276            message: hex!("243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89"),
277            signature: hex!(
278                "6896BD60EEAE296DB48A229FF71DFE071BDE413E6D43F917DC8DCF8C78DE3341
279                 8906D11AC976ABCCB20B091292BFF4EA897EFCB639EA871CFA95F6DE339E4B0A"
280            ),
281        },
282        SignVector {
283            index: 2,
284            secret_key: hex!("C90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B14E5C9"),
285            public_key: hex!("DD308AFEC5777E13121FA72B9CC1B7CC0139715309B086C960E18FD969774EB8"),
286            aux_rand: hex!("C87AA53824B4D7AE2EB035A2B5BBBCCC080E76CDC6D1692C4B0B62D798E6D906"),
287            message: hex!("7E2D58D8B3BCDF1ABADEC7829054F90DDA9805AAB56C77333024B9D0A508B75C"),
288            signature: hex!(
289                "5831AAEED7B44BB74E5EAB94BA9D4294C49BCF2A60728D8B4C200F50DD313C1B
290                 AB745879A5AD954A72C45A91C3A51D3C7ADEA98D82F8481E0E1E03674A6F3FB7"
291            ),
292        },
293        // test fails if msg is reduced modulo p or n
294        SignVector {
295            index: 3,
296            secret_key: hex!("0B432B2677937381AEF05BB02A66ECD012773062CF3FA2549E44F58ED2401710"),
297            public_key: hex!("25D1DFF95105F5253C4022F628A996AD3A0D95FBF21D468A1B33F8C160D8F517"),
298            aux_rand: hex!("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"),
299            message: hex!("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"),
300            signature: hex!(
301                "7EB0509757E246F19449885651611CB965ECC1A187DD51B64FDA1EDC9637D5EC
302                 97582B9CB13DB3933705B32BA982AF5AF25FD78881EBB32771FC5922EFC66EA3"
303            ),
304        },
305    ];
306
307    #[test]
308    fn bip340_sign_vectors() {
309        for vector in BIP340_SIGN_VECTORS {
310            let sk = SigningKey::from_bytes(&vector.secret_key.into()).unwrap();
311            assert_eq!(sk.verifying_key().to_bytes().as_slice(), &vector.public_key);
312
313            let sig = sk
314                .sign_raw(&vector.message, &vector.aux_rand)
315                .unwrap_or_else(|_| {
316                    panic!(
317                        "low-level Schnorr signing failure for index {}",
318                        vector.index
319                    )
320                });
321
322            assert_eq!(
323                vector.signature,
324                sig.to_bytes(),
325                "wrong signature for index {}",
326                vector.index
327            );
328        }
329    }
330
331    #[test]
332    #[cfg(feature = "alloc")]
333    fn bip340_ext_sign_vectors() {
334        // Test indexes 15-18 from https://github.com/bitcoin/bips/blob/master/bip-0340/test-vectors.csv
335        //
336        // These tests all use the same key and aux
337        let sk = SigningKey::from_bytes(
338            &hex!("0340034003400340034003400340034003400340034003400340034003400340").into(),
339        )
340        .unwrap();
341
342        let aux_rand = [0u8; 32];
343
344        struct Bip340ExtTest {
345            index: usize,
346            msg: alloc::vec::Vec<u8>,
347            signature: [u8; 64],
348        }
349
350        let bip340_ext_sign_vectors = [
351            Bip340ExtTest {
352                index: 15,
353                msg: vec![],
354                signature: hex!(
355                    "71535DB165ECD9FBBC046E5FFAEA61186BB6AD436732FCCC25291A55895464CF
356                    6069CE26BF03466228F19A3A62DB8A649F2D560FAC652827D1AF0574E427AB63"
357                ),
358            },
359            Bip340ExtTest {
360                index: 16,
361                msg: hex!("11").to_vec(),
362                signature: hex!(
363                    "08A20A0AFEF64124649232E0693C583AB1B9934AE63B4C3511F3AE1134C6A303EA3173BFEA6683BD101FA5AA5DBC1996FE7CACFC5A577D33EC14564CEC2BACBF"
364                ),
365            },
366            Bip340ExtTest {
367                index: 17,
368                msg: hex!("0102030405060708090A0B0C0D0E0F1011").to_vec(),
369                signature: hex!(
370                    "5130F39A4059B43BC7CAC09A19ECE52B5D8699D1A71E3C52DA9AFDB6B50AC370C4A482B77BF960F8681540E25B6771ECE1E5A37FD80E5A51897C5566A97EA5A5"
371                ),
372            },
373            Bip340ExtTest {
374                index: 18,
375                msg: vec![0x99; 100],
376                signature: hex!(
377                    "403B12B0D8555A344175EA7EC746566303321E5DBFA8BE6F091635163ECA79A8585ED3E3170807E7C03B720FC54C7B23897FCBA0E9D0B4A06894CFD249F22367"
378                ),
379            },
380        ];
381
382        for vector in bip340_ext_sign_vectors {
383            let sig = sk.sign_raw(&vector.msg, &aux_rand).unwrap_or_else(|_| {
384                panic!(
385                    "low-level Schnorr signing failure for index {}",
386                    vector.index
387                )
388            });
389
390            assert_eq!(
391                vector.signature,
392                sig.to_bytes(),
393                "wrong signature for index {}",
394                vector.index
395            );
396        }
397    }
398
399    /// Verification test vector
400    struct VerifyVector {
401        /// Index of test case
402        index: u8,
403
404        /// Verifying key
405        public_key: [u8; 32],
406
407        /// Message digest
408        message: [u8; 32],
409
410        /// Claimed signature
411        signature: [u8; 64],
412
413        /// Is signature valid
414        valid: bool,
415    }
416
417    /// BIP340 verification test vectors: index 4-14
418    const BIP340_VERIFY_VECTORS: &[VerifyVector] = &[
419        VerifyVector {
420            index: 4,
421            public_key: hex!("D69C3509BB99E412E68B0FE8544E72837DFA30746D8BE2AA65975F29D22DC7B9"),
422            message: hex!("4DF3C3F68FCC83B27E9D42C90431A72499F17875C81A599B566C9889B9696703"),
423            signature: hex!(
424                "00000000000000000000003B78CE563F89A0ED9414F5AA28AD0D96D6795F9C63
425                 76AFB1548AF603B3EB45C9F8207DEE1060CB71C04E80F593060B07D28308D7F4"
426            ),
427            valid: true,
428        },
429        // public key not on curve
430        VerifyVector {
431            index: 5,
432            public_key: hex!("EEFDEA4CDB677750A420FEE807EACF21EB9898AE79B9768766E4FAA04A2D4A34"),
433            message: hex!("243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89"),
434            signature: hex!(
435                "6CFF5C3BA86C69EA4B7376F31A9BCB4F74C1976089B2D9963DA2E5543E177769
436                 69E89B4C5564D00349106B8497785DD7D1D713A8AE82B32FA79D5F7FC407D39B"
437            ),
438            valid: false,
439        },
440        // has_even_y(R) is false
441        VerifyVector {
442            index: 6,
443            public_key: hex!("DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659"),
444            message: hex!("243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89"),
445            signature: hex!(
446                "FFF97BD5755EEEA420453A14355235D382F6472F8568A18B2F057A1460297556
447                 3CC27944640AC607CD107AE10923D9EF7A73C643E166BE5EBEAFA34B1AC553E2"
448            ),
449            valid: false,
450        },
451        // negated message
452        VerifyVector {
453            index: 7,
454            public_key: hex!("DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659"),
455            message: hex!("243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89"),
456            signature: hex!(
457                "1FA62E331EDBC21C394792D2AB1100A7B432B013DF3F6FF4F99FCB33E0E1515F
458                 28890B3EDB6E7189B630448B515CE4F8622A954CFE545735AAEA5134FCCDB2BD"
459            ),
460            valid: false,
461        },
462        // negated s value
463        VerifyVector {
464            index: 8,
465            public_key: hex!("DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659"),
466            message: hex!("243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89"),
467            signature: hex!(
468                "6CFF5C3BA86C69EA4B7376F31A9BCB4F74C1976089B2D9963DA2E5543E177769
469                 961764B3AA9B2FFCB6EF947B6887A226E8D7C93E00C5ED0C1834FF0D0C2E6DA6"
470            ),
471            valid: false,
472        },
473        // sG - eP is infinite. Test fails in single verification if has_even_y(inf) is defined as true and x(inf) as 0
474        VerifyVector {
475            index: 9,
476            public_key: hex!("DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659"),
477            message: hex!("243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89"),
478            signature: hex!(
479                "0000000000000000000000000000000000000000000000000000000000000000
480                 123DDA8328AF9C23A94C1FEECFD123BA4FB73476F0D594DCB65C6425BD186051"
481            ),
482            valid: false,
483        },
484        // sG - eP is infinite. Test fails in single verification if has_even_y(inf) is defined as true and x(inf) as 1
485        VerifyVector {
486            index: 10,
487            public_key: hex!("DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659"),
488            message: hex!("243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89"),
489            signature: hex!(
490                "0000000000000000000000000000000000000000000000000000000000000001
491                 7615FBAF5AE28864013C099742DEADB4DBA87F11AC6754F93780D5A1837CF197"
492            ),
493            valid: false,
494        },
495        // sig[0:32] is not an X coordinate on the curve
496        VerifyVector {
497            index: 11,
498            public_key: hex!("DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659"),
499            message: hex!("243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89"),
500            signature: hex!(
501                "4A298DACAE57395A15D0795DDBFD1DCB564DA82B0F269BC70A74F8220429BA1D
502                 69E89B4C5564D00349106B8497785DD7D1D713A8AE82B32FA79D5F7FC407D39B"
503            ),
504            valid: false,
505        },
506        // sig[0:32] is equal to field size
507        VerifyVector {
508            index: 12,
509            public_key: hex!("DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659"),
510            message: hex!("243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89"),
511            signature: hex!(
512                "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
513                 69E89B4C5564D00349106B8497785DD7D1D713A8AE82B32FA79D5F7FC407D39B"
514            ),
515            valid: false,
516        },
517        // sig[32:64] is equal to curve order
518        VerifyVector {
519            index: 13,
520            public_key: hex!("DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659"),
521            message: hex!("243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89"),
522            signature: hex!(
523                "6CFF5C3BA86C69EA4B7376F31A9BCB4F74C1976089B2D9963DA2E5543E177769
524                 FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141"
525            ),
526            valid: false,
527        },
528        // public key is not a valid X coordinate because it exceeds the field size
529        VerifyVector {
530            index: 14,
531            public_key: hex!("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC30"),
532            message: hex!("243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89"),
533            signature: hex!(
534                "6CFF5C3BA86C69EA4B7376F31A9BCB4F74C1976089B2D9963DA2E5543E177769
535                 69E89B4C5564D00349106B8497785DD7D1D713A8AE82B32FA79D5F7FC407D39B"
536            ),
537            valid: false,
538        },
539    ];
540
541    #[test]
542    fn bip340_verify_vectors() {
543        for vector in BIP340_VERIFY_VECTORS {
544            let valid = match (
545                VerifyingKey::from_bytes(&vector.public_key.into()),
546                Signature::try_from(vector.signature.as_slice()),
547            ) {
548                (Ok(pk), Ok(sig)) => pk.verify_prehash(&vector.message, &sig).is_ok(),
549                _ => false,
550            };
551
552            assert_eq!(
553                vector.valid, valid,
554                "incorrect validation for index {}",
555                vector.index
556            );
557        }
558    }
559
560    #[test]
561    fn try_from() {
562        // Pass an invalid signature (shorter than Self::BYTES / 2) and make sure
563        // it does not panic, but return Err
564        let invalid_signature = [111; 24];
565        assert!(Signature::try_from(&invalid_signature[..]).is_err());
566    }
567}