1 // This file is Copyright its original authors, visible in version control
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
10 //! Tagged hashes for use in signature calculation and verification.
12 use bitcoin::hashes::{Hash, HashEngine, sha256};
14 use crate::util::ser::{BigSize, Readable};
16 use crate::prelude::*;
18 /// Valid type range for signature TLV records.
19 const SIGNATURE_TYPES: core::ops::RangeInclusive<u64> = 240..=1000;
21 /// Computes a merkle root hash for the given data, which must be a well-formed TLV stream
22 /// containing at least one TLV record.
23 fn root_hash(data: &[u8]) -> sha256::Hash {
24 let mut tlv_stream = TlvStream::new(&data[..]).peekable();
25 let nonce_tag = tagged_hash_engine(sha256::Hash::from_engine({
26 let mut engine = sha256::Hash::engine();
27 engine.input("LnNonce".as_bytes());
28 engine.input(tlv_stream.peek().unwrap().record_bytes);
31 let leaf_tag = tagged_hash_engine(sha256::Hash::hash("LnLeaf".as_bytes()));
32 let branch_tag = tagged_hash_engine(sha256::Hash::hash("LnBranch".as_bytes()));
34 let mut leaves = Vec::new();
35 for record in tlv_stream {
36 if !SIGNATURE_TYPES.contains(&record.r#type) {
37 leaves.push(tagged_hash_from_engine(leaf_tag.clone(), &record));
38 leaves.push(tagged_hash_from_engine(nonce_tag.clone(), &record.type_bytes));
42 // Calculate the merkle root hash in place.
43 let num_leaves = leaves.len();
45 let step = 2 << level;
46 let offset = step / 2;
47 if offset >= num_leaves {
51 let left_branches = (0..num_leaves).step_by(step);
52 let right_branches = (offset..num_leaves).step_by(step);
53 for (i, j) in left_branches.zip(right_branches) {
54 leaves[i] = tagged_branch_hash_from_engine(branch_tag.clone(), leaves[i], leaves[j]);
58 *leaves.first().unwrap()
61 fn tagged_hash<T: AsRef<[u8]>>(tag: sha256::Hash, msg: T) -> sha256::Hash {
62 let engine = tagged_hash_engine(tag);
63 tagged_hash_from_engine(engine, msg)
66 fn tagged_hash_engine(tag: sha256::Hash) -> sha256::HashEngine {
67 let mut engine = sha256::Hash::engine();
68 engine.input(tag.as_ref());
69 engine.input(tag.as_ref());
73 fn tagged_hash_from_engine<T: AsRef<[u8]>>(mut engine: sha256::HashEngine, msg: T) -> sha256::Hash {
74 engine.input(msg.as_ref());
75 sha256::Hash::from_engine(engine)
78 fn tagged_branch_hash_from_engine(
79 mut engine: sha256::HashEngine, leaf1: sha256::Hash, leaf2: sha256::Hash,
82 engine.input(leaf1.as_ref());
83 engine.input(leaf2.as_ref());
85 engine.input(leaf2.as_ref());
86 engine.input(leaf1.as_ref());
88 sha256::Hash::from_engine(engine)
91 /// [`Iterator`] over a sequence of bytes yielding [`TlvRecord`]s. The input is assumed to be a
92 /// well-formed TLV stream.
93 struct TlvStream<'a> {
94 data: io::Cursor<&'a [u8]>,
97 impl<'a> TlvStream<'a> {
98 fn new(data: &'a [u8]) -> Self {
100 data: io::Cursor::new(data),
105 /// A slice into a [`TlvStream`] for a record.
106 struct TlvRecord<'a> {
108 type_bytes: &'a [u8],
109 // The entire TLV record.
110 record_bytes: &'a [u8],
113 impl AsRef<[u8]> for TlvRecord<'_> {
114 fn as_ref(&self) -> &[u8] { &self.record_bytes }
117 impl<'a> Iterator for TlvStream<'a> {
118 type Item = TlvRecord<'a>;
120 fn next(&mut self) -> Option<Self::Item> {
121 if self.data.position() < self.data.get_ref().len() as u64 {
122 let start = self.data.position();
124 let r#type = <BigSize as Readable>::read(&mut self.data).unwrap().0;
125 let offset = self.data.position();
126 let type_bytes = &self.data.get_ref()[start as usize..offset as usize];
128 let length = <BigSize as Readable>::read(&mut self.data).unwrap().0;
129 let offset = self.data.position();
130 let end = offset + length;
132 let _value = &self.data.get_ref()[offset as usize..end as usize];
133 let record_bytes = &self.data.get_ref()[start as usize..end as usize];
135 self.data.set_position(end);
137 Some(TlvRecord { r#type, type_bytes, record_bytes })
146 use bitcoin::hashes::{Hash, sha256};
149 fn calculates_merkle_root_hash() {
150 // BOLT 12 test vectors
151 macro_rules! tlv1 { () => { "010203e8" } }
152 macro_rules! tlv2 { () => { "02080000010000020003" } }
153 macro_rules! tlv3 { () => { "03310266e4598d1d3c415f572a8488830b60f7e744ed9235eb0b1ba93283b315c0351800000000000000010000000000000002" } }
155 super::root_hash(&hex::decode(tlv1!()).unwrap()),
156 sha256::Hash::from_slice(&hex::decode("b013756c8fee86503a0b4abdab4cddeb1af5d344ca6fc2fa8b6c08938caa6f93").unwrap()).unwrap(),
159 super::root_hash(&hex::decode(concat!(tlv1!(), tlv2!())).unwrap()),
160 sha256::Hash::from_slice(&hex::decode("c3774abbf4815aa54ccaa026bff6581f01f3be5fe814c620a252534f434bc0d1").unwrap()).unwrap(),
163 super::root_hash(&hex::decode(concat!(tlv1!(), tlv2!(), tlv3!())).unwrap()),
164 sha256::Hash::from_slice(&hex::decode("ab2e79b1283b0b31e0b035258de23782df6b89a38cfa7237bde69aed1a658c5d").unwrap()).unwrap(),