_ 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 use crate::prelude::*;
  19
  20 /// Valid type range for signature TLV records.
  21 const SIGNATURE_TYPES: core::ops::RangeInclusive<u64> = 240..=1000;
  22
  23 tlv_stream!(SignatureTlvStream, SignatureTlvStreamRef, SIGNATURE_TYPES, {
  24         (240, signature: Signature),
  25 });
  26
  27 /// Error when signing messages.
  28 #[derive(Debug, PartialEq)]
  29 pub enum SignError<E> {
  30         /// User-defined error when signing the message.
  31         Signing(E),
  32         /// Error when verifying the produced signature using the given pubkey.
  33         Verification(secp256k1::Error),
  34 }
  35
  36 /// Signs a message digest consisting of a tagged hash of the given bytes, checking if it can be
  37 /// verified with the supplied pubkey.
  38 ///
  39 /// Panics if `bytes` is not a well-formed TLV stream containing at least one TLV record.
  40 pub(super) fn sign_message<F, E>(
  41         sign: F, tag: &str, bytes: &[u8], pubkey: PublicKey,
  42 ) -> Result<Signature, SignError<E>>
  43 where
  44         F: FnOnce(&Message) -> Result<Signature, E>
  45 {
  46         let digest = message_digest(tag, bytes);
  47         let signature = sign(&digest).map_err(|e| SignError::Signing(e))?;
  48
  49         let pubkey = pubkey.into();
  50         let secp_ctx = Secp256k1::verification_only();
  51         secp_ctx.verify_schnorr(&signature, &digest, &pubkey).map_err(|e| SignError::Verification(e))?;
  52
  53         Ok(signature)
  54 }
  55
  56 /// Verifies the signature with a pubkey over the given bytes using a tagged hash as the message
  57 /// digest.
  58 ///
  59 /// Panics if `bytes` is not a well-formed TLV stream containing at least one TLV record.
  60 pub(super) fn verify_signature(
  61         signature: &Signature, tag: &str, bytes: &[u8], pubkey: PublicKey,
  62 ) -> Result<(), secp256k1::Error> {
  63         let digest = message_digest(tag, bytes);
  64         let pubkey = pubkey.into();
  65         let secp_ctx = Secp256k1::verification_only();
  66         secp_ctx.verify_schnorr(signature, &digest, &pubkey)
  67 }
  68
  69 pub(super) fn message_digest(tag: &str, bytes: &[u8]) -> Message {
  70         let tag = sha256::Hash::hash(tag.as_bytes());
  71         let merkle_root = root_hash(bytes);
  72         Message::from_slice(&tagged_hash(tag, merkle_root)).unwrap()
  73 }
  74
  75 /// Computes a merkle root hash for the given data, which must be a well-formed TLV stream
  76 /// containing at least one TLV record.
  77 fn root_hash(data: &[u8]) -> sha256::Hash {
  78         let nonce_tag = tagged_hash_engine(sha256::Hash::from_engine({
  79                 let first_tlv_record = TlvStream::new(&data[..]).next().unwrap();
  80                 let mut engine = sha256::Hash::engine();
  81                 engine.input("LnNonce".as_bytes());
  82                 engine.input(first_tlv_record.record_bytes);
  83                 engine
  84         }));
  85         let leaf_tag = tagged_hash_engine(sha256::Hash::hash("LnLeaf".as_bytes()));
  86         let branch_tag = tagged_hash_engine(sha256::Hash::hash("LnBranch".as_bytes()));
  87
  88         let mut leaves = Vec::new();
  89         let tlv_stream = TlvStream::new(&data[..]);
  90         for record in tlv_stream.skip_signatures() {
  91                 leaves.push(tagged_hash_from_engine(leaf_tag.clone(), &record.record_bytes));
  92                 leaves.push(tagged_hash_from_engine(nonce_tag.clone(), &record.type_bytes));
  93         }
  94
  95         // Calculate the merkle root hash in place.
  96         let num_leaves = leaves.len();
  97         for level in 0.. {
  98                 let step = 2 << level;
  99                 let offset = step / 2;
 100                 if offset >= num_leaves {
 101                         break;
 102                 }
 103
 104                 let left_branches = (0..num_leaves).step_by(step);
 105                 let right_branches = (offset..num_leaves).step_by(step);
 106                 for (i, j) in left_branches.zip(right_branches) {
 107                         leaves[i] = tagged_branch_hash_from_engine(branch_tag.clone(), leaves[i], leaves[j]);
 108                 }
 109         }
 110
 111         *leaves.first().unwrap()
 112 }
 113
 114 fn tagged_hash<T: AsRef<[u8]>>(tag: sha256::Hash, msg: T) -> sha256::Hash {
 115         let engine = tagged_hash_engine(tag);
 116         tagged_hash_from_engine(engine, msg)
 117 }
 118
 119 fn tagged_hash_engine(tag: sha256::Hash) -> sha256::HashEngine {
 120         let mut engine = sha256::Hash::engine();
 121         engine.input(tag.as_ref());
 122         engine.input(tag.as_ref());
 123         engine
 124 }
 125
 126 fn tagged_hash_from_engine<T: AsRef<[u8]>>(mut engine: sha256::HashEngine, msg: T) -> sha256::Hash {
 127         engine.input(msg.as_ref());
 128         sha256::Hash::from_engine(engine)
 129 }
 130
 131 fn tagged_branch_hash_from_engine(
 132         mut engine: sha256::HashEngine, leaf1: sha256::Hash, leaf2: sha256::Hash,
 133 ) -> sha256::Hash {
 134         if leaf1 < leaf2 {
 135                 engine.input(leaf1.as_ref());
 136                 engine.input(leaf2.as_ref());
 137         } else {
 138                 engine.input(leaf2.as_ref());
 139                 engine.input(leaf1.as_ref());
 140         };
 141         sha256::Hash::from_engine(engine)
 142 }
 143
 144 /// [`Iterator`] over a sequence of bytes yielding [`TlvRecord`]s. The input is assumed to be a
 145 /// well-formed TLV stream.
 146 struct TlvStream<'a> {
 147         data: io::Cursor<&'a [u8]>,
 148 }
 149
 150 impl<'a> TlvStream<'a> {
 151         fn new(data: &'a [u8]) -> Self {
 152                 Self {
 153                         data: io::Cursor::new(data),
 154                 }
 155         }
 156
 157         fn skip_signatures(self) -> core::iter::Filter<TlvStream<'a>, fn(&TlvRecord) -> bool> {
 158                 self.filter(|record| !SIGNATURE_TYPES.contains(&record.r#type))
 159         }
 160 }
 161
 162 /// A slice into a [`TlvStream`] for a record.
 163 struct TlvRecord<'a> {
 164         r#type: u64,
 165         type_bytes: &'a [u8],
 166         // The entire TLV record.
 167         record_bytes: &'a [u8],
 168 }
 169
 170 impl<'a> Iterator for TlvStream<'a> {
 171         type Item = TlvRecord<'a>;
 172
 173         fn next(&mut self) -> Option<Self::Item> {
 174                 if self.data.position() < self.data.get_ref().len() as u64 {
 175                         let start = self.data.position();
 176
 177                         let r#type = <BigSize as Readable>::read(&mut self.data).unwrap().0;
 178                         let offset = self.data.position();
 179                         let type_bytes = &self.data.get_ref()[start as usize..offset as usize];
 180
 181                         let length = <BigSize as Readable>::read(&mut self.data).unwrap().0;
 182                         let offset = self.data.position();
 183                         let end = offset + length;
 184
 185                         let _value = &self.data.get_ref()[offset as usize..end as usize];
 186                         let record_bytes = &self.data.get_ref()[start as usize..end as usize];
 187
 188                         self.data.set_position(end);
 189
 190                         Some(TlvRecord { r#type, type_bytes, record_bytes })
 191                 } else {
 192                         None
 193                 }
 194         }
 195 }
 196
 197 /// Encoding for a pre-serialized TLV stream that excludes any signature TLV records.
 198 ///
 199 /// Panics if the wrapped bytes are not a well-formed TLV stream.
 200 pub(super) struct WithoutSignatures<'a>(pub &'a Vec<u8>);
 201
 202 impl<'a> Writeable for WithoutSignatures<'a> {
 203         #[inline]
 204         fn write<W: Writer>(&self, writer: &mut W) -> Result<(), io::Error> {
 205                 let tlv_stream = TlvStream::new(&self.0[..]);
 206                 for record in tlv_stream.skip_signatures() {
 207                         writer.write_all(record.record_bytes)?;
 208                 }
 209                 Ok(())
 210         }
 211 }
 212
 213 #[cfg(test)]
 214 mod tests {
 215         use super::{TlvStream, WithoutSignatures};
 216
 217         use bitcoin::hashes::{Hash, sha256};
 218         use bitcoin::secp256k1::{KeyPair, Secp256k1, SecretKey};
 219         use core::convert::Infallible;
 220         use crate::offers::offer::{Amount, OfferBuilder};
 221         use crate::offers::invoice_request::InvoiceRequest;
 222         use crate::offers::parse::Bech32Encode;
 223         use crate::util::ser::Writeable;
 224
 225         #[test]
 226         fn calculates_merkle_root_hash() {
 227                 // BOLT 12 test vectors
 228                 macro_rules! tlv1 { () => { "010203e8" } }
 229                 macro_rules! tlv2 { () => { "02080000010000020003" } }
 230                 macro_rules! tlv3 { () => { "03310266e4598d1d3c415f572a8488830b60f7e744ed9235eb0b1ba93283b315c0351800000000000000010000000000000002" } }
 231                 assert_eq!(
 232                         super::root_hash(&hex::decode(tlv1!()).unwrap()),
 233                         sha256::Hash::from_slice(&hex::decode("b013756c8fee86503a0b4abdab4cddeb1af5d344ca6fc2fa8b6c08938caa6f93").unwrap()).unwrap(),
 234                 );
 235                 assert_eq!(
 236                         super::root_hash(&hex::decode(concat!(tlv1!(), tlv2!())).unwrap()),
 237                         sha256::Hash::from_slice(&hex::decode("c3774abbf4815aa54ccaa026bff6581f01f3be5fe814c620a252534f434bc0d1").unwrap()).unwrap(),
 238                 );
 239                 assert_eq!(
 240                         super::root_hash(&hex::decode(concat!(tlv1!(), tlv2!(), tlv3!())).unwrap()),
 241                         sha256::Hash::from_slice(&hex::decode("ab2e79b1283b0b31e0b035258de23782df6b89a38cfa7237bde69aed1a658c5d").unwrap()).unwrap(),
 242                 );
 243         }
 244
 245         #[test]
 246         fn calculates_merkle_root_hash_from_invoice_request() {
 247                 let secp_ctx = Secp256k1::new();
 248                 let recipient_pubkey = {
 249                         let secret_key = SecretKey::from_slice(&hex::decode("4141414141414141414141414141414141414141414141414141414141414141").unwrap()).unwrap();
 250                         KeyPair::from_secret_key(&secp_ctx, &secret_key).public_key()
 251                 };
 252                 let payer_keys = {
 253                         let secret_key = SecretKey::from_slice(&hex::decode("4242424242424242424242424242424242424242424242424242424242424242").unwrap()).unwrap();
 254                         KeyPair::from_secret_key(&secp_ctx, &secret_key)
 255                 };
 256
 257                 // BOLT 12 test vectors
 258                 let invoice_request = OfferBuilder::new("A Mathematical Treatise".into(), recipient_pubkey)
 259                         .amount(Amount::Currency { iso4217_code: *b"USD", amount: 100 })
 260                         .build_unchecked()
 261                         .request_invoice(vec![0; 8], payer_keys.public_key()).unwrap()
 262                         .build_unchecked()
 263                         .sign::<_, Infallible>(|digest| Ok(secp_ctx.sign_schnorr_no_aux_rand(digest, &payer_keys)))
 264                         .unwrap();
 265                 assert_eq!(
 266                         invoice_request.to_string(),
 267                         "lnr1qqyqqqqqqqqqqqqqqcp4256ypqqkgzshgysy6ct5dpjk6ct5d93kzmpq23ex2ct5d9ek293pqthvwfzadd7jejes8q9lhc4rvjxd022zv5l44g6qah82ru5rdpnpjkppqvjx204vgdzgsqpvcp4mldl3plscny0rt707gvpdh6ndydfacz43euzqhrurageg3n7kafgsek6gz3e9w52parv8gs2hlxzk95tzeswywffxlkeyhml0hh46kndmwf4m6xma3tkq2lu04qz3slje2rfthc89vss",
 268                 );
 269                 assert_eq!(
 270                         super::root_hash(&invoice_request.bytes[..]),
 271                         sha256::Hash::from_slice(&hex::decode("608407c18ad9a94d9ea2bcdbe170b6c20c462a7833a197621c916f78cf18e624").unwrap()).unwrap(),
 272                 );
 273         }
 274
 275         #[test]
 276         fn skips_encoding_signature_tlv_records() {
 277                 let secp_ctx = Secp256k1::new();
 278                 let recipient_pubkey = {
 279                         let secret_key = SecretKey::from_slice(&[41; 32]).unwrap();
 280                         KeyPair::from_secret_key(&secp_ctx, &secret_key).public_key()
 281                 };
 282                 let payer_keys = {
 283                         let secret_key = SecretKey::from_slice(&[42; 32]).unwrap();
 284                         KeyPair::from_secret_key(&secp_ctx, &secret_key)
 285                 };
 286
 287                 let invoice_request = OfferBuilder::new("foo".into(), recipient_pubkey)
 288                         .amount_msats(100)
 289                         .build_unchecked()
 290                         .request_invoice(vec![0; 8], payer_keys.public_key()).unwrap()
 291                         .build_unchecked()
 292                         .sign::<_, Infallible>(|digest| Ok(secp_ctx.sign_schnorr_no_aux_rand(digest, &payer_keys)))
 293                         .unwrap();
 294
 295                 let mut bytes_without_signature = Vec::new();
 296                 WithoutSignatures(&invoice_request.bytes).write(&mut bytes_without_signature).unwrap();
 297
 298                 assert_ne!(bytes_without_signature, invoice_request.bytes);
 299                 assert_eq!(
 300                         TlvStream::new(&bytes_without_signature).count(),
 301                         TlvStream::new(&invoice_request.bytes).count() - 1,
 302                 );
 303         }
 304
 305         impl AsRef<[u8]> for InvoiceRequest {
 306                 fn as_ref(&self) -> &[u8] {
 307                         &self.bytes
 308                 }
 309         }
 310
 311         impl Bech32Encode for InvoiceRequest {
 312                 const BECH32_HRP: &'static str = "lnr";
 313         }
 314
 315         impl core::fmt::Display for InvoiceRequest {
 316                 fn fmt(&self, f: &mut core::fmt::Formatter) -> Result<(), core::fmt::Error> {
 317                         self.fmt_bech32_str(f)
 318                 }
 319         }
 320 }