_ Git - rust-lightning/blob - lightning/src/offers/merkle.rs

   1 // This file is Copyright its original authors, visible in version control
   2 // history.
   3 //
   4 // This file is licensed under the Apache License, Version 2.0 <LICENSE-APACHE
   5 // or http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   6 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your option.
   7 // You may not use this file except in accordance with one or both of these
   8 // licenses.
   9
  10 //! Tagged hashes for use in signature calculation and verification.
  11
  12 use bitcoin::hashes::{Hash, HashEngine, sha256};
  13 use bitcoin::secp256k1::{Message, PublicKey, Secp256k1, self};
  14 use bitcoin::secp256k1::schnorr::Signature;
  15 use core::convert::AsRef;
  16 use crate::io;
  17 use crate::util::ser::{BigSize, Readable, Writeable, Writer};
  18
  19 use crate::prelude::*;
  20
  21 /// Valid type range for signature TLV records.
  22 const SIGNATURE_TYPES: core::ops::RangeInclusive<u64> = 240..=1000;
  23
  24 tlv_stream!(SignatureTlvStream, SignatureTlvStreamRef, SIGNATURE_TYPES, {
  25         (240, signature: Signature),
  26 });
  27
  28 /// A hash for use in a specific context by tweaking with a context-dependent tag as per [BIP 340]
  29 /// and computed over the merkle root of a TLV stream to sign as defined in [BOLT 12].
  30 ///
  31 /// [BIP 340]: https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki
  32 /// [BOLT 12]: https://github.com/rustyrussell/lightning-rfc/blob/guilt/offers/12-offer-encoding.md#signature-calculation
  33 #[derive(Debug, PartialEq)]
  34 pub struct TaggedHash(Message);
  35
  36 impl TaggedHash {
  37         /// Creates a tagged hash with the given parameters.
  38         ///
  39         /// Panics if `tlv_stream` is not a well-formed TLV stream containing at least one TLV record.
  40         pub(super) fn new(tag: &str, tlv_stream: &[u8]) -> Self {
  41                 Self(message_digest(tag, tlv_stream))
  42         }
  43
  44         /// Returns the digest to sign.
  45         pub fn as_digest(&self) -> &Message {
  46                 &self.0
  47         }
  48 }
  49
  50 impl AsRef<TaggedHash> for TaggedHash {
  51         fn as_ref(&self) -> &TaggedHash {
  52                 self
  53         }
  54 }
  55
  56 /// Error when signing messages.
  57 #[derive(Debug, PartialEq)]
  58 pub enum SignError<E> {
  59         /// User-defined error when signing the message.
  60         Signing(E),
  61         /// Error when verifying the produced signature using the given pubkey.
  62         Verification(secp256k1::Error),
  63 }
  64
  65 /// Signs a [`TaggedHash`] computed over the merkle root of `message`'s TLV stream, checking if it
  66 /// can be verified with the supplied `pubkey`.
  67 ///
  68 /// Since `message` is any type that implements [`AsRef<TaggedHash>`], `sign` may be a closure that
  69 /// takes a message such as [`Bolt12Invoice`] or [`InvoiceRequest`]. This allows further message
  70 /// verification before signing its [`TaggedHash`].
  71 ///
  72 /// [`Bolt12Invoice`]: crate::offers::invoice::Bolt12Invoice
  73 /// [`InvoiceRequest`]: crate::offers::invoice_request::InvoiceRequest
  74 pub(super) fn sign_message<F, E, T>(
  75         sign: F, message: &T, pubkey: PublicKey,
  76 ) -> Result<Signature, SignError<E>>
  77 where
  78         F: FnOnce(&T) -> Result<Signature, E>,
  79         T: AsRef<TaggedHash>,
  80 {
  81         let signature = sign(message).map_err(|e| SignError::Signing(e))?;
  82
  83         let digest = message.as_ref().as_digest();
  84         let pubkey = pubkey.into();
  85         let secp_ctx = Secp256k1::verification_only();
  86         secp_ctx.verify_schnorr(&signature, digest, &pubkey).map_err(|e| SignError::Verification(e))?;
  87
  88         Ok(signature)
  89 }
  90
  91 /// Verifies the signature with a pubkey over the given message using a tagged hash as the message
  92 /// digest.
  93 pub(super) fn verify_signature(
  94         signature: &Signature, message: TaggedHash, pubkey: PublicKey,
  95 ) -> Result<(), secp256k1::Error> {
  96         let digest = message.as_digest();
  97         let pubkey = pubkey.into();
  98         let secp_ctx = Secp256k1::verification_only();
  99         secp_ctx.verify_schnorr(signature, digest, &pubkey)
 100 }
 101
 102 pub(super) fn message_digest(tag: &str, bytes: &[u8]) -> Message {
 103         let tag = sha256::Hash::hash(tag.as_bytes());
 104         let merkle_root = root_hash(bytes);
 105         Message::from_slice(&tagged_hash(tag, merkle_root)).unwrap()
 106 }
 107
 108 /// Computes a merkle root hash for the given data, which must be a well-formed TLV stream
 109 /// containing at least one TLV record.
 110 fn root_hash(data: &[u8]) -> sha256::Hash {
 111         let nonce_tag = tagged_hash_engine(sha256::Hash::from_engine({
 112                 let first_tlv_record = TlvStream::new(&data[..]).next().unwrap();
 113                 let mut engine = sha256::Hash::engine();
 114                 engine.input("LnNonce".as_bytes());
 115                 engine.input(first_tlv_record.record_bytes);
 116                 engine
 117         }));
 118         let leaf_tag = tagged_hash_engine(sha256::Hash::hash("LnLeaf".as_bytes()));
 119         let branch_tag = tagged_hash_engine(sha256::Hash::hash("LnBranch".as_bytes()));
 120
 121         let mut leaves = Vec::new();
 122         let tlv_stream = TlvStream::new(&data[..]);
 123         for record in tlv_stream.skip_signatures() {
 124                 leaves.push(tagged_hash_from_engine(leaf_tag.clone(), &record.record_bytes));
 125                 leaves.push(tagged_hash_from_engine(nonce_tag.clone(), &record.type_bytes));
 126         }
 127
 128         // Calculate the merkle root hash in place.
 129         let num_leaves = leaves.len();
 130         for level in 0.. {
 131                 let step = 2 << level;
 132                 let offset = step / 2;
 133                 if offset >= num_leaves {
 134                         break;
 135                 }
 136
 137                 let left_branches = (0..num_leaves).step_by(step);
 138                 let right_branches = (offset..num_leaves).step_by(step);
 139                 for (i, j) in left_branches.zip(right_branches) {
 140                         leaves[i] = tagged_branch_hash_from_engine(branch_tag.clone(), leaves[i], leaves[j]);
 141                 }
 142         }
 143
 144         *leaves.first().unwrap()
 145 }
 146
 147 fn tagged_hash<T: AsRef<[u8]>>(tag: sha256::Hash, msg: T) -> sha256::Hash {
 148         let engine = tagged_hash_engine(tag);
 149         tagged_hash_from_engine(engine, msg)
 150 }
 151
 152 fn tagged_hash_engine(tag: sha256::Hash) -> sha256::HashEngine {
 153         let mut engine = sha256::Hash::engine();
 154         engine.input(tag.as_ref());
 155         engine.input(tag.as_ref());
 156         engine
 157 }
 158
 159 fn tagged_hash_from_engine<T: AsRef<[u8]>>(mut engine: sha256::HashEngine, msg: T) -> sha256::Hash {
 160         engine.input(msg.as_ref());
 161         sha256::Hash::from_engine(engine)
 162 }
 163
 164 fn tagged_branch_hash_from_engine(
 165         mut engine: sha256::HashEngine, leaf1: sha256::Hash, leaf2: sha256::Hash,
 166 ) -> sha256::Hash {
 167         if leaf1 < leaf2 {
 168                 engine.input(leaf1.as_ref());
 169                 engine.input(leaf2.as_ref());
 170         } else {
 171                 engine.input(leaf2.as_ref());
 172                 engine.input(leaf1.as_ref());
 173         };
 174         sha256::Hash::from_engine(engine)
 175 }
 176
 177 /// [`Iterator`] over a sequence of bytes yielding [`TlvRecord`]s. The input is assumed to be a
 178 /// well-formed TLV stream.
 179 #[derive(Clone)]
 180 pub(super) struct TlvStream<'a> {
 181         data: io::Cursor<&'a [u8]>,
 182 }
 183
 184 impl<'a> TlvStream<'a> {
 185         pub fn new(data: &'a [u8]) -> Self {
 186                 Self {
 187                         data: io::Cursor::new(data),
 188                 }
 189         }
 190
 191         pub fn range<T>(self, types: T) -> impl core::iter::Iterator<Item = TlvRecord<'a>>
 192         where
 193                 T: core::ops::RangeBounds<u64> + Clone,
 194         {
 195                 let take_range = types.clone();
 196                 self.skip_while(move |record| !types.contains(&record.r#type))
 197                         .take_while(move |record| take_range.contains(&record.r#type))
 198         }
 199
 200         fn skip_signatures(self) -> core::iter::Filter<TlvStream<'a>, fn(&TlvRecord) -> bool> {
 201                 self.filter(|record| !SIGNATURE_TYPES.contains(&record.r#type))
 202         }
 203 }
 204
 205 /// A slice into a [`TlvStream`] for a record.
 206 pub(super) struct TlvRecord<'a> {
 207         pub(super) r#type: u64,
 208         type_bytes: &'a [u8],
 209         // The entire TLV record.
 210         pub(super) record_bytes: &'a [u8],
 211 }
 212
 213 impl<'a> Iterator for TlvStream<'a> {
 214         type Item = TlvRecord<'a>;
 215
 216         fn next(&mut self) -> Option<Self::Item> {
 217                 if self.data.position() < self.data.get_ref().len() as u64 {
 218                         let start = self.data.position();
 219
 220                         let r#type = <BigSize as Readable>::read(&mut self.data).unwrap().0;
 221                         let offset = self.data.position();
 222                         let type_bytes = &self.data.get_ref()[start as usize..offset as usize];
 223
 224                         let length = <BigSize as Readable>::read(&mut self.data).unwrap().0;
 225                         let offset = self.data.position();
 226                         let end = offset + length;
 227
 228                         let _value = &self.data.get_ref()[offset as usize..end as usize];
 229                         let record_bytes = &self.data.get_ref()[start as usize..end as usize];
 230
 231                         self.data.set_position(end);
 232
 233                         Some(TlvRecord { r#type, type_bytes, record_bytes })
 234                 } else {
 235                         None
 236                 }
 237         }
 238 }
 239
 240 /// Encoding for a pre-serialized TLV stream that excludes any signature TLV records.
 241 ///
 242 /// Panics if the wrapped bytes are not a well-formed TLV stream.
 243 pub(super) struct WithoutSignatures<'a>(pub &'a [u8]);
 244
 245 impl<'a> Writeable for WithoutSignatures<'a> {
 246         #[inline]
 247         fn write<W: Writer>(&self, writer: &mut W) -> Result<(), io::Error> {
 248                 let tlv_stream = TlvStream::new(self.0);
 249                 for record in tlv_stream.skip_signatures() {
 250                         writer.write_all(record.record_bytes)?;
 251                 }
 252                 Ok(())
 253         }
 254 }
 255
 256 #[cfg(test)]
 257 mod tests {
 258         use super::{SIGNATURE_TYPES, TlvStream, WithoutSignatures};
 259
 260         use bitcoin::hashes::{Hash, sha256};
 261         use bitcoin::secp256k1::{KeyPair, Secp256k1, SecretKey};
 262         use bitcoin::secp256k1::schnorr::Signature;
 263         use core::convert::Infallible;
 264         use crate::offers::offer::{Amount, OfferBuilder};
 265         use crate::offers::invoice_request::InvoiceRequest;
 266         use crate::offers::parse::Bech32Encode;
 267         use crate::util::ser::Writeable;
 268
 269         #[test]
 270         fn calculates_merkle_root_hash() {
 271                 // BOLT 12 test vectors
 272                 macro_rules! tlv1 { () => { "010203e8" } }
 273                 macro_rules! tlv2 { () => { "02080000010000020003" } }
 274                 macro_rules! tlv3 { () => { "03310266e4598d1d3c415f572a8488830b60f7e744ed9235eb0b1ba93283b315c0351800000000000000010000000000000002" } }
 275                 assert_eq!(
 276                         super::root_hash(&hex::decode(tlv1!()).unwrap()),
 277                         sha256::Hash::from_slice(&hex::decode("b013756c8fee86503a0b4abdab4cddeb1af5d344ca6fc2fa8b6c08938caa6f93").unwrap()).unwrap(),
 278                 );
 279                 assert_eq!(
 280                         super::root_hash(&hex::decode(concat!(tlv1!(), tlv2!())).unwrap()),
 281                         sha256::Hash::from_slice(&hex::decode("c3774abbf4815aa54ccaa026bff6581f01f3be5fe814c620a252534f434bc0d1").unwrap()).unwrap(),
 282                 );
 283                 assert_eq!(
 284                         super::root_hash(&hex::decode(concat!(tlv1!(), tlv2!(), tlv3!())).unwrap()),
 285                         sha256::Hash::from_slice(&hex::decode("ab2e79b1283b0b31e0b035258de23782df6b89a38cfa7237bde69aed1a658c5d").unwrap()).unwrap(),
 286                 );
 287         }
 288
 289         #[test]
 290         fn calculates_merkle_root_hash_from_invoice_request() {
 291                 let secp_ctx = Secp256k1::new();
 292                 let recipient_pubkey = {
 293                         let secret_key = SecretKey::from_slice(&hex::decode("4141414141414141414141414141414141414141414141414141414141414141").unwrap()).unwrap();
 294                         KeyPair::from_secret_key(&secp_ctx, &secret_key).public_key()
 295                 };
 296                 let payer_keys = {
 297                         let secret_key = SecretKey::from_slice(&hex::decode("4242424242424242424242424242424242424242424242424242424242424242").unwrap()).unwrap();
 298                         KeyPair::from_secret_key(&secp_ctx, &secret_key)
 299                 };
 300
 301                 // BOLT 12 test vectors
 302                 let invoice_request = OfferBuilder::new("A Mathematical Treatise".into(), recipient_pubkey)
 303                         .amount(Amount::Currency { iso4217_code: *b"USD", amount: 100 })
 304                         .build_unchecked()
 305                         .request_invoice(vec![0; 8], payer_keys.public_key()).unwrap()
 306                         .build_unchecked()
 307                         .sign::<_, Infallible>(
 308                                 |message| Ok(secp_ctx.sign_schnorr_no_aux_rand(message.as_ref().as_digest(), &payer_keys))
 309                         )
 310                         .unwrap();
 311                 assert_eq!(
 312                         invoice_request.to_string(),
 313                         "lnr1qqyqqqqqqqqqqqqqqcp4256ypqqkgzshgysy6ct5dpjk6ct5d93kzmpq23ex2ct5d9ek293pqthvwfzadd7jejes8q9lhc4rvjxd022zv5l44g6qah82ru5rdpnpjkppqvjx204vgdzgsqpvcp4mldl3plscny0rt707gvpdh6ndydfacz43euzqhrurageg3n7kafgsek6gz3e9w52parv8gs2hlxzk95tzeswywffxlkeyhml0hh46kndmwf4m6xma3tkq2lu04qz3slje2rfthc89vss",
 314                 );
 315                 assert_eq!(
 316                         super::root_hash(&invoice_request.bytes[..]),
 317                         sha256::Hash::from_slice(&hex::decode("608407c18ad9a94d9ea2bcdbe170b6c20c462a7833a197621c916f78cf18e624").unwrap()).unwrap(),
 318                 );
 319                 assert_eq!(
 320                         invoice_request.signature(),
 321                         Signature::from_slice(&hex::decode("b8f83ea3288cfd6ea510cdb481472575141e8d8744157f98562d162cc1c472526fdb24befefbdebab4dbb726bbd1b7d8aec057f8fa805187e5950d2bbe0e5642").unwrap()).unwrap(),
 322                 );
 323         }
 324
 325         #[test]
 326         fn skips_encoding_signature_tlv_records() {
 327                 let secp_ctx = Secp256k1::new();
 328                 let recipient_pubkey = {
 329                         let secret_key = SecretKey::from_slice(&[41; 32]).unwrap();
 330                         KeyPair::from_secret_key(&secp_ctx, &secret_key).public_key()
 331                 };
 332                 let payer_keys = {
 333                         let secret_key = SecretKey::from_slice(&[42; 32]).unwrap();
 334                         KeyPair::from_secret_key(&secp_ctx, &secret_key)
 335                 };
 336
 337                 let invoice_request = OfferBuilder::new("foo".into(), recipient_pubkey)
 338                         .amount_msats(100)
 339                         .build_unchecked()
 340                         .request_invoice(vec![0; 8], payer_keys.public_key()).unwrap()
 341                         .build_unchecked()
 342                         .sign::<_, Infallible>(
 343                                 |message| Ok(secp_ctx.sign_schnorr_no_aux_rand(message.as_ref().as_digest(), &payer_keys))
 344                         )
 345                         .unwrap();
 346
 347                 let mut bytes_without_signature = Vec::new();
 348                 WithoutSignatures(&invoice_request.bytes).write(&mut bytes_without_signature).unwrap();
 349
 350                 assert_ne!(bytes_without_signature, invoice_request.bytes);
 351                 assert_eq!(
 352                         TlvStream::new(&bytes_without_signature).count(),
 353                         TlvStream::new(&invoice_request.bytes).count() - 1,
 354                 );
 355         }
 356
 357         #[test]
 358         fn iterates_over_tlv_stream_range() {
 359                 let secp_ctx = Secp256k1::new();
 360                 let recipient_pubkey = {
 361                         let secret_key = SecretKey::from_slice(&[41; 32]).unwrap();
 362                         KeyPair::from_secret_key(&secp_ctx, &secret_key).public_key()
 363                 };
 364                 let payer_keys = {
 365                         let secret_key = SecretKey::from_slice(&[42; 32]).unwrap();
 366                         KeyPair::from_secret_key(&secp_ctx, &secret_key)
 367                 };
 368
 369                 let invoice_request = OfferBuilder::new("foo".into(), recipient_pubkey)
 370                         .amount_msats(100)
 371                         .build_unchecked()
 372                         .request_invoice(vec![0; 8], payer_keys.public_key()).unwrap()
 373                         .build_unchecked()
 374                         .sign::<_, Infallible>(
 375                                 |message| Ok(secp_ctx.sign_schnorr_no_aux_rand(message.as_ref().as_digest(), &payer_keys))
 376                         )
 377                         .unwrap();
 378
 379                 let tlv_stream = TlvStream::new(&invoice_request.bytes).range(0..1)
 380                         .chain(TlvStream::new(&invoice_request.bytes).range(1..80))
 381                         .chain(TlvStream::new(&invoice_request.bytes).range(80..160))
 382                         .chain(TlvStream::new(&invoice_request.bytes).range(160..240))
 383                         .chain(TlvStream::new(&invoice_request.bytes).range(SIGNATURE_TYPES))
 384                         .map(|r| r.record_bytes.to_vec())
 385                         .flatten()
 386                         .collect::<Vec<u8>>();
 387
 388                 assert_eq!(tlv_stream, invoice_request.bytes);
 389         }
 390
 391         impl AsRef<[u8]> for InvoiceRequest {
 392                 fn as_ref(&self) -> &[u8] {
 393                         &self.bytes
 394                 }
 395         }
 396
 397         impl Bech32Encode for InvoiceRequest {
 398                 const BECH32_HRP: &'static str = "lnr";
 399         }
 400
 401         impl core::fmt::Display for InvoiceRequest {
 402                 fn fmt(&self, f: &mut core::fmt::Formatter) -> Result<(), core::fmt::Error> {
 403                         self.fmt_bech32_str(f)
 404                 }
 405         }
 406 }