bitcoin/taproot/
merkle_branch.rs

1// SPDX-License-Identifier: CC0-1.0
2
3//! Contains `TaprootMerkleBranch` and its associated types.
4
5use hashes::Hash;
6
7use super::{
8    TapNodeHash, TaprootBuilderError, TaprootError, TAPROOT_CONTROL_MAX_NODE_COUNT,
9    TAPROOT_CONTROL_NODE_SIZE,
10};
11use crate::prelude::*;
12
13/// The merkle proof for inclusion of a tree in a taptree hash.
14#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
15#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
16#[cfg_attr(feature = "serde", serde(crate = "actual_serde"))]
17#[cfg_attr(feature = "serde", serde(into = "Vec<TapNodeHash>"))]
18#[cfg_attr(feature = "serde", serde(try_from = "Vec<TapNodeHash>"))]
19pub struct TaprootMerkleBranch(Vec<TapNodeHash>);
20
21impl TaprootMerkleBranch {
22    /// Returns a reference to the slice of hashes.
23    #[deprecated(since = "0.32.0", note = "Use `as_slice` instead")]
24    #[inline]
25    pub fn as_inner(&self) -> &[TapNodeHash] { &self.0 }
26
27    /// Returns a reference to the slice of hashes.
28    #[inline]
29    pub fn as_slice(&self) -> &[TapNodeHash] { &self.0 }
30
31    /// Returns the number of nodes in this merkle proof.
32    #[inline]
33    pub fn len(&self) -> usize { self.0.len() }
34
35    /// Checks if this merkle proof is empty.
36    #[inline]
37    pub fn is_empty(&self) -> bool { self.0.is_empty() }
38
39    /// Decodes bytes from control block.
40    ///
41    /// This reads the branch as encoded in the control block: the concatenated 32B byte chunks -
42    /// one for each hash.
43    ///
44    /// # Errors
45    ///
46    /// The function returns an error if the number of bytes is not an integer multiple of 32 or
47    /// if the number of hashes exceeds 128.
48    pub fn decode(sl: &[u8]) -> Result<Self, TaprootError> {
49        if sl.len() % TAPROOT_CONTROL_NODE_SIZE != 0 {
50            Err(TaprootError::InvalidMerkleBranchSize(sl.len()))
51        } else if sl.len() > TAPROOT_CONTROL_NODE_SIZE * TAPROOT_CONTROL_MAX_NODE_COUNT {
52            Err(TaprootError::InvalidMerkleTreeDepth(sl.len() / TAPROOT_CONTROL_NODE_SIZE))
53        } else {
54            let inner = sl
55                .chunks_exact(TAPROOT_CONTROL_NODE_SIZE)
56                .map(|chunk| {
57                    TapNodeHash::from_slice(chunk)
58                        .expect("chunks_exact always returns the correct size")
59                })
60                .collect();
61
62            Ok(TaprootMerkleBranch(inner))
63        }
64    }
65
66    /// Creates a merkle proof from list of hashes.
67    ///
68    /// # Errors
69    /// If inner proof length is more than [`TAPROOT_CONTROL_MAX_NODE_COUNT`] (128).
70    #[inline]
71    fn from_collection<T: AsRef<[TapNodeHash]> + Into<Vec<TapNodeHash>>>(
72        collection: T,
73    ) -> Result<Self, TaprootError> {
74        if collection.as_ref().len() > TAPROOT_CONTROL_MAX_NODE_COUNT {
75            Err(TaprootError::InvalidMerkleTreeDepth(collection.as_ref().len()))
76        } else {
77            Ok(TaprootMerkleBranch(collection.into()))
78        }
79    }
80
81    /// Serializes to a writer.
82    ///
83    /// # Returns
84    ///
85    /// The number of bytes written to the writer.
86    pub fn encode<Write: io::Write + ?Sized>(&self, writer: &mut Write) -> io::Result<usize> {
87        for hash in self {
88            writer.write_all(hash.as_ref())?;
89        }
90        Ok(self.len() * TapNodeHash::LEN)
91    }
92
93    /// Serializes `self` as bytes.
94    pub fn serialize(&self) -> Vec<u8> {
95        self.iter().flat_map(|e| e.as_byte_array()).copied().collect::<Vec<u8>>()
96    }
97
98    /// Appends elements to proof.
99    pub(super) fn push(&mut self, h: TapNodeHash) -> Result<(), TaprootBuilderError> {
100        if self.len() >= TAPROOT_CONTROL_MAX_NODE_COUNT {
101            Err(TaprootBuilderError::InvalidMerkleTreeDepth(self.0.len()))
102        } else {
103            self.0.push(h);
104            Ok(())
105        }
106    }
107
108    /// Returns the inner list of hashes.
109    #[deprecated(since = "0.32.0", note = "Use `into_vec` instead")]
110    #[inline]
111    pub fn into_inner(self) -> Vec<TapNodeHash> { self.0 }
112
113    /// Returns the list of hashes stored in a `Vec`.
114    #[inline]
115    pub fn into_vec(self) -> Vec<TapNodeHash> { self.0 }
116}
117
118macro_rules! impl_try_from {
119    ($from:ty) => {
120        impl TryFrom<$from> for TaprootMerkleBranch {
121            type Error = TaprootError;
122
123            /// Creates a merkle proof from list of hashes.
124            ///
125            /// # Errors
126            /// If inner proof length is more than [`TAPROOT_CONTROL_MAX_NODE_COUNT`] (128).
127            #[inline]
128            fn try_from(v: $from) -> Result<Self, Self::Error> {
129                TaprootMerkleBranch::from_collection(v)
130            }
131        }
132    };
133}
134impl_try_from!(&[TapNodeHash]);
135impl_try_from!(Vec<TapNodeHash>);
136impl_try_from!(Box<[TapNodeHash]>);
137
138macro_rules! impl_try_from_array {
139    ($($len:expr),* $(,)?) => {
140        $(
141            impl From<[TapNodeHash; $len]> for TaprootMerkleBranch {
142                #[inline]
143                fn from(a: [TapNodeHash; $len]) -> Self {
144                    Self(a.to_vec())
145                }
146            }
147        )*
148    }
149}
150// Implement for all values [0, 128] inclusive.
151//
152// The reason zero is included is that `TaprootMerkleBranch` doesn't contain the hash of the node
153// that's being proven - it's not needed because the script is already right before control block.
154impl_try_from_array!(
155    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
156    26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49,
157    50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73,
158    74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97,
159    98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116,
160    117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128
161);
162
163impl From<TaprootMerkleBranch> for Vec<TapNodeHash> {
164    #[inline]
165    fn from(branch: TaprootMerkleBranch) -> Self { branch.0 }
166}
167
168impl IntoIterator for TaprootMerkleBranch {
169    type IntoIter = IntoIter;
170    type Item = TapNodeHash;
171
172    #[inline]
173    fn into_iter(self) -> Self::IntoIter { IntoIter(self.0.into_iter()) }
174}
175
176impl<'a> IntoIterator for &'a TaprootMerkleBranch {
177    type IntoIter = core::slice::Iter<'a, TapNodeHash>;
178    type Item = &'a TapNodeHash;
179
180    #[inline]
181    fn into_iter(self) -> Self::IntoIter { self.0.iter() }
182}
183
184impl<'a> IntoIterator for &'a mut TaprootMerkleBranch {
185    type IntoIter = core::slice::IterMut<'a, TapNodeHash>;
186    type Item = &'a mut TapNodeHash;
187
188    #[inline]
189    fn into_iter(self) -> Self::IntoIter { self.0.iter_mut() }
190}
191
192impl core::ops::Deref for TaprootMerkleBranch {
193    type Target = [TapNodeHash];
194
195    #[inline]
196    fn deref(&self) -> &Self::Target { &self.0 }
197}
198
199impl core::ops::DerefMut for TaprootMerkleBranch {
200    #[inline]
201    fn deref_mut(&mut self) -> &mut Self::Target { &mut self.0 }
202}
203
204impl AsRef<[TapNodeHash]> for TaprootMerkleBranch {
205    #[inline]
206    fn as_ref(&self) -> &[TapNodeHash] { &self.0 }
207}
208
209impl AsMut<[TapNodeHash]> for TaprootMerkleBranch {
210    #[inline]
211    fn as_mut(&mut self) -> &mut [TapNodeHash] { &mut self.0 }
212}
213
214impl Borrow<[TapNodeHash]> for TaprootMerkleBranch {
215    #[inline]
216    fn borrow(&self) -> &[TapNodeHash] { &self.0 }
217}
218
219impl BorrowMut<[TapNodeHash]> for TaprootMerkleBranch {
220    #[inline]
221    fn borrow_mut(&mut self) -> &mut [TapNodeHash] { &mut self.0 }
222}
223
224/// Iterator over node hashes within Taproot merkle branch.
225///
226/// This is created by `into_iter` method on `TaprootMerkleBranch` (via `IntoIterator` trait).
227#[derive(Clone, Debug)]
228pub struct IntoIter(alloc::vec::IntoIter<TapNodeHash>);
229
230impl IntoIter {
231    /// Returns the remaining items of this iterator as a slice.
232    #[inline]
233    pub fn as_slice(&self) -> &[TapNodeHash] { self.0.as_slice() }
234
235    /// Returns the remaining items of this iterator as a mutable slice.
236    #[inline]
237    pub fn as_mut_slice(&mut self) -> &mut [TapNodeHash] { self.0.as_mut_slice() }
238}
239
240impl Iterator for IntoIter {
241    type Item = TapNodeHash;
242
243    #[inline]
244    fn next(&mut self) -> Option<Self::Item> { self.0.next() }
245
246    #[inline]
247    fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
248
249    #[inline]
250    fn nth(&mut self, n: usize) -> Option<Self::Item> { self.0.nth(n) }
251
252    #[inline]
253    fn last(self) -> Option<Self::Item> { self.0.last() }
254
255    #[inline]
256    fn count(self) -> usize { self.0.count() }
257}
258
259impl DoubleEndedIterator for IntoIter {
260    #[inline]
261    fn next_back(&mut self) -> Option<Self::Item> { self.0.next_back() }
262
263    #[inline]
264    fn nth_back(&mut self, n: usize) -> Option<Self::Item> { self.0.nth_back(n) }
265}
266
267impl ExactSizeIterator for IntoIter {}
268
269impl core::iter::FusedIterator for IntoIter {}
bitcoin/taproot/merkle_branch.rs

bitcoin/taproot/
merkle_branch.rs
