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