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

lightning/offers/
merkle.rs
