]> git.bitcoin.ninja Git - rust-lightning/blob - lightning/src/offers/merkle.rs
Merge pull request #1908 from jkczyz/2022-11-refund
[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 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 /// 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 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 mut tlv_stream = TlvStream::new(&data[..]).peekable();
79         let nonce_tag = tagged_hash_engine(sha256::Hash::from_engine({
80                 let mut engine = sha256::Hash::engine();
81                 engine.input("LnNonce".as_bytes());
82                 engine.input(tlv_stream.peek().unwrap().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         for record in tlv_stream {
90                 if !SIGNATURE_TYPES.contains(&record.r#type) {
91                         leaves.push(tagged_hash_from_engine(leaf_tag.clone(), &record));
92                         leaves.push(tagged_hash_from_engine(nonce_tag.clone(), &record.type_bytes));
93                 }
94         }
95
96         // Calculate the merkle root hash in place.
97         let num_leaves = leaves.len();
98         for level in 0.. {
99                 let step = 2 << level;
100                 let offset = step / 2;
101                 if offset >= num_leaves {
102                         break;
103                 }
104
105                 let left_branches = (0..num_leaves).step_by(step);
106                 let right_branches = (offset..num_leaves).step_by(step);
107                 for (i, j) in left_branches.zip(right_branches) {
108                         leaves[i] = tagged_branch_hash_from_engine(branch_tag.clone(), leaves[i], leaves[j]);
109                 }
110         }
111
112         *leaves.first().unwrap()
113 }
114
115 fn tagged_hash<T: AsRef<[u8]>>(tag: sha256::Hash, msg: T) -> sha256::Hash {
116         let engine = tagged_hash_engine(tag);
117         tagged_hash_from_engine(engine, msg)
118 }
119
120 fn tagged_hash_engine(tag: sha256::Hash) -> sha256::HashEngine {
121         let mut engine = sha256::Hash::engine();
122         engine.input(tag.as_ref());
123         engine.input(tag.as_ref());
124         engine
125 }
126
127 fn tagged_hash_from_engine<T: AsRef<[u8]>>(mut engine: sha256::HashEngine, msg: T) -> sha256::Hash {
128         engine.input(msg.as_ref());
129         sha256::Hash::from_engine(engine)
130 }
131
132 fn tagged_branch_hash_from_engine(
133         mut engine: sha256::HashEngine, leaf1: sha256::Hash, leaf2: sha256::Hash,
134 ) -> sha256::Hash {
135         if leaf1 < leaf2 {
136                 engine.input(leaf1.as_ref());
137                 engine.input(leaf2.as_ref());
138         } else {
139                 engine.input(leaf2.as_ref());
140                 engine.input(leaf1.as_ref());
141         };
142         sha256::Hash::from_engine(engine)
143 }
144
145 /// [`Iterator`] over a sequence of bytes yielding [`TlvRecord`]s. The input is assumed to be a
146 /// well-formed TLV stream.
147 struct TlvStream<'a> {
148         data: io::Cursor<&'a [u8]>,
149 }
150
151 impl<'a> TlvStream<'a> {
152         fn new(data: &'a [u8]) -> Self {
153                 Self {
154                         data: io::Cursor::new(data),
155                 }
156         }
157 }
158
159 /// A slice into a [`TlvStream`] for a record.
160 struct TlvRecord<'a> {
161         r#type: u64,
162         type_bytes: &'a [u8],
163         // The entire TLV record.
164         record_bytes: &'a [u8],
165 }
166
167 impl AsRef<[u8]> for TlvRecord<'_> {
168         fn as_ref(&self) -> &[u8] { &self.record_bytes }
169 }
170
171 impl<'a> Iterator for TlvStream<'a> {
172         type Item = TlvRecord<'a>;
173
174         fn next(&mut self) -> Option<Self::Item> {
175                 if self.data.position() < self.data.get_ref().len() as u64 {
176                         let start = self.data.position();
177
178                         let r#type = <BigSize as Readable>::read(&mut self.data).unwrap().0;
179                         let offset = self.data.position();
180                         let type_bytes = &self.data.get_ref()[start as usize..offset as usize];
181
182                         let length = <BigSize as Readable>::read(&mut self.data).unwrap().0;
183                         let offset = self.data.position();
184                         let end = offset + length;
185
186                         let _value = &self.data.get_ref()[offset as usize..end as usize];
187                         let record_bytes = &self.data.get_ref()[start as usize..end as usize];
188
189                         self.data.set_position(end);
190
191                         Some(TlvRecord { r#type, type_bytes, record_bytes })
192                 } else {
193                         None
194                 }
195         }
196 }
197
198 #[cfg(test)]
199 mod tests {
200         use bitcoin::hashes::{Hash, sha256};
201         use bitcoin::secp256k1::{KeyPair, Secp256k1, SecretKey};
202         use core::convert::Infallible;
203         use crate::offers::offer::{Amount, OfferBuilder};
204         use crate::offers::invoice_request::InvoiceRequest;
205         use crate::offers::parse::Bech32Encode;
206
207         #[test]
208         fn calculates_merkle_root_hash() {
209                 // BOLT 12 test vectors
210                 macro_rules! tlv1 { () => { "010203e8" } }
211                 macro_rules! tlv2 { () => { "02080000010000020003" } }
212                 macro_rules! tlv3 { () => { "03310266e4598d1d3c415f572a8488830b60f7e744ed9235eb0b1ba93283b315c0351800000000000000010000000000000002" } }
213                 assert_eq!(
214                         super::root_hash(&hex::decode(tlv1!()).unwrap()),
215                         sha256::Hash::from_slice(&hex::decode("b013756c8fee86503a0b4abdab4cddeb1af5d344ca6fc2fa8b6c08938caa6f93").unwrap()).unwrap(),
216                 );
217                 assert_eq!(
218                         super::root_hash(&hex::decode(concat!(tlv1!(), tlv2!())).unwrap()),
219                         sha256::Hash::from_slice(&hex::decode("c3774abbf4815aa54ccaa026bff6581f01f3be5fe814c620a252534f434bc0d1").unwrap()).unwrap(),
220                 );
221                 assert_eq!(
222                         super::root_hash(&hex::decode(concat!(tlv1!(), tlv2!(), tlv3!())).unwrap()),
223                         sha256::Hash::from_slice(&hex::decode("ab2e79b1283b0b31e0b035258de23782df6b89a38cfa7237bde69aed1a658c5d").unwrap()).unwrap(),
224                 );
225         }
226
227         #[test]
228         fn calculates_merkle_root_hash_from_invoice_request() {
229                 let secp_ctx = Secp256k1::new();
230                 let recipient_pubkey = {
231                         let secret_key = SecretKey::from_slice(&hex::decode("4141414141414141414141414141414141414141414141414141414141414141").unwrap()).unwrap();
232                         KeyPair::from_secret_key(&secp_ctx, &secret_key).public_key()
233                 };
234                 let payer_keys = {
235                         let secret_key = SecretKey::from_slice(&hex::decode("4242424242424242424242424242424242424242424242424242424242424242").unwrap()).unwrap();
236                         KeyPair::from_secret_key(&secp_ctx, &secret_key)
237                 };
238
239                 // BOLT 12 test vectors
240                 let invoice_request = OfferBuilder::new("A Mathematical Treatise".into(), recipient_pubkey)
241                         .amount(Amount::Currency { iso4217_code: *b"USD", amount: 100 })
242                         .build_unchecked()
243                         .request_invoice(vec![0; 8], payer_keys.public_key()).unwrap()
244                         .build_unchecked()
245                         .sign::<_, Infallible>(|digest| Ok(secp_ctx.sign_schnorr_no_aux_rand(digest, &payer_keys)))
246                         .unwrap();
247                 assert_eq!(
248                         invoice_request.to_string(),
249                         "lnr1qqyqqqqqqqqqqqqqqcp4256ypqqkgzshgysy6ct5dpjk6ct5d93kzmpq23ex2ct5d9ek293pqthvwfzadd7jejes8q9lhc4rvjxd022zv5l44g6qah82ru5rdpnpjkppqvjx204vgdzgsqpvcp4mldl3plscny0rt707gvpdh6ndydfacz43euzqhrurageg3n7kafgsek6gz3e9w52parv8gs2hlxzk95tzeswywffxlkeyhml0hh46kndmwf4m6xma3tkq2lu04qz3slje2rfthc89vss",
250                 );
251                 assert_eq!(
252                         super::root_hash(&invoice_request.bytes[..]),
253                         sha256::Hash::from_slice(&hex::decode("608407c18ad9a94d9ea2bcdbe170b6c20c462a7833a197621c916f78cf18e624").unwrap()).unwrap(),
254                 );
255         }
256
257         impl AsRef<[u8]> for InvoiceRequest {
258                 fn as_ref(&self) -> &[u8] {
259                         &self.bytes
260                 }
261         }
262
263         impl Bech32Encode for InvoiceRequest {
264                 const BECH32_HRP: &'static str = "lnr";
265         }
266
267         impl core::fmt::Display for InvoiceRequest {
268                 fn fmt(&self, f: &mut core::fmt::Formatter) -> Result<(), core::fmt::Error> {
269                         self.fmt_bech32_str(f)
270                 }
271         }
272 }