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