_ 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};
  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 /// Verifies the signature with a pubkey over the given bytes using a tagged hash as the message
  28 /// digest.
  29 ///
  30 /// Panics if `bytes` is not a well-formed TLV stream containing at least one TLV record.
  31 pub(super) fn verify_signature(
  32         signature: &Signature, tag: &str, bytes: &[u8], pubkey: PublicKey,
  33 ) -> Result<(), secp256k1::Error> {
  34         let tag = sha256::Hash::hash(tag.as_bytes());
  35         let merkle_root = root_hash(bytes);
  36         let digest = Message::from_slice(&tagged_hash(tag, merkle_root)).unwrap();
  37         let pubkey = pubkey.into();
  38         let secp_ctx = Secp256k1::verification_only();
  39         secp_ctx.verify_schnorr(signature, &digest, &pubkey)
  40 }
  41
  42 /// Computes a merkle root hash for the given data, which must be a well-formed TLV stream
  43 /// containing at least one TLV record.
  44 fn root_hash(data: &[u8]) -> sha256::Hash {
  45         let mut tlv_stream = TlvStream::new(&data[..]).peekable();
  46         let nonce_tag = tagged_hash_engine(sha256::Hash::from_engine({
  47                 let mut engine = sha256::Hash::engine();
  48                 engine.input("LnNonce".as_bytes());
  49                 engine.input(tlv_stream.peek().unwrap().record_bytes);
  50                 engine
  51         }));
  52         let leaf_tag = tagged_hash_engine(sha256::Hash::hash("LnLeaf".as_bytes()));
  53         let branch_tag = tagged_hash_engine(sha256::Hash::hash("LnBranch".as_bytes()));
  54
  55         let mut leaves = Vec::new();
  56         for record in tlv_stream {
  57                 if !SIGNATURE_TYPES.contains(&record.r#type) {
  58                         leaves.push(tagged_hash_from_engine(leaf_tag.clone(), &record));
  59                         leaves.push(tagged_hash_from_engine(nonce_tag.clone(), &record.type_bytes));
  60                 }
  61         }
  62
  63         // Calculate the merkle root hash in place.
  64         let num_leaves = leaves.len();
  65         for level in 0.. {
  66                 let step = 2 << level;
  67                 let offset = step / 2;
  68                 if offset >= num_leaves {
  69                         break;
  70                 }
  71
  72                 let left_branches = (0..num_leaves).step_by(step);
  73                 let right_branches = (offset..num_leaves).step_by(step);
  74                 for (i, j) in left_branches.zip(right_branches) {
  75                         leaves[i] = tagged_branch_hash_from_engine(branch_tag.clone(), leaves[i], leaves[j]);
  76                 }
  77         }
  78
  79         *leaves.first().unwrap()
  80 }
  81
  82 fn tagged_hash<T: AsRef<[u8]>>(tag: sha256::Hash, msg: T) -> sha256::Hash {
  83         let engine = tagged_hash_engine(tag);
  84         tagged_hash_from_engine(engine, msg)
  85 }
  86
  87 fn tagged_hash_engine(tag: sha256::Hash) -> sha256::HashEngine {
  88         let mut engine = sha256::Hash::engine();
  89         engine.input(tag.as_ref());
  90         engine.input(tag.as_ref());
  91         engine
  92 }
  93
  94 fn tagged_hash_from_engine<T: AsRef<[u8]>>(mut engine: sha256::HashEngine, msg: T) -> sha256::Hash {
  95         engine.input(msg.as_ref());
  96         sha256::Hash::from_engine(engine)
  97 }
  98
  99 fn tagged_branch_hash_from_engine(
 100         mut engine: sha256::HashEngine, leaf1: sha256::Hash, leaf2: sha256::Hash,
 101 ) -> sha256::Hash {
 102         if leaf1 < leaf2 {
 103                 engine.input(leaf1.as_ref());
 104                 engine.input(leaf2.as_ref());
 105         } else {
 106                 engine.input(leaf2.as_ref());
 107                 engine.input(leaf1.as_ref());
 108         };
 109         sha256::Hash::from_engine(engine)
 110 }
 111
 112 /// [`Iterator`] over a sequence of bytes yielding [`TlvRecord`]s. The input is assumed to be a
 113 /// well-formed TLV stream.
 114 struct TlvStream<'a> {
 115         data: io::Cursor<&'a [u8]>,
 116 }
 117
 118 impl<'a> TlvStream<'a> {
 119         fn new(data: &'a [u8]) -> Self {
 120                 Self {
 121                         data: io::Cursor::new(data),
 122                 }
 123         }
 124 }
 125
 126 /// A slice into a [`TlvStream`] for a record.
 127 struct TlvRecord<'a> {
 128         r#type: u64,
 129         type_bytes: &'a [u8],
 130         // The entire TLV record.
 131         record_bytes: &'a [u8],
 132 }
 133
 134 impl AsRef<[u8]> for TlvRecord<'_> {
 135         fn as_ref(&self) -> &[u8] { &self.record_bytes }
 136 }
 137
 138 impl<'a> Iterator for TlvStream<'a> {
 139         type Item = TlvRecord<'a>;
 140
 141         fn next(&mut self) -> Option<Self::Item> {
 142                 if self.data.position() < self.data.get_ref().len() as u64 {
 143                         let start = self.data.position();
 144
 145                         let r#type = <BigSize as Readable>::read(&mut self.data).unwrap().0;
 146                         let offset = self.data.position();
 147                         let type_bytes = &self.data.get_ref()[start as usize..offset as usize];
 148
 149                         let length = <BigSize as Readable>::read(&mut self.data).unwrap().0;
 150                         let offset = self.data.position();
 151                         let end = offset + length;
 152
 153                         let _value = &self.data.get_ref()[offset as usize..end as usize];
 154                         let record_bytes = &self.data.get_ref()[start as usize..end as usize];
 155
 156                         self.data.set_position(end);
 157
 158                         Some(TlvRecord { r#type, type_bytes, record_bytes })
 159                 } else {
 160                         None
 161                 }
 162         }
 163 }
 164
 165 #[cfg(test)]
 166 mod tests {
 167         use bitcoin::hashes::{Hash, sha256};
 168
 169         #[test]
 170         fn calculates_merkle_root_hash() {
 171                 // BOLT 12 test vectors
 172                 macro_rules! tlv1 { () => { "010203e8" } }
 173                 macro_rules! tlv2 { () => { "02080000010000020003" } }
 174                 macro_rules! tlv3 { () => { "03310266e4598d1d3c415f572a8488830b60f7e744ed9235eb0b1ba93283b315c0351800000000000000010000000000000002" } }
 175                 assert_eq!(
 176                         super::root_hash(&hex::decode(tlv1!()).unwrap()),
 177                         sha256::Hash::from_slice(&hex::decode("b013756c8fee86503a0b4abdab4cddeb1af5d344ca6fc2fa8b6c08938caa6f93").unwrap()).unwrap(),
 178                 );
 179                 assert_eq!(
 180                         super::root_hash(&hex::decode(concat!(tlv1!(), tlv2!())).unwrap()),
 181                         sha256::Hash::from_slice(&hex::decode("c3774abbf4815aa54ccaa026bff6581f01f3be5fe814c620a252534f434bc0d1").unwrap()).unwrap(),
 182                 );
 183                 assert_eq!(
 184                         super::root_hash(&hex::decode(concat!(tlv1!(), tlv2!(), tlv3!())).unwrap()),
 185                         sha256::Hash::from_slice(&hex::decode("ab2e79b1283b0b31e0b035258de23782df6b89a38cfa7237bde69aed1a658c5d").unwrap()).unwrap(),
 186                 );
 187         }
 188 }