commonware_storage/bmt/
mod.rs

1//! Stateless Binary Merkle Tree (BMT).
2//!
3//! The Binary Merkle Tree is constructed level-by-level. The first level consists of position-hashed leaf digests.
4//! On each additional level, pairs of nodes are hashed from the previous level (if a level contains an odd
5//! number of nodes, the last node is duplicated). The root of the tree is the digest of the node in the top level.
6//!
7//! For example, given three leaves A, B, and C, the tree is constructed as follows:
8//!
9//! ```text
10//!     Level 2 (root):       [hash(hash(hash(0,A),hash(1,B)),hash(hash(2,C),hash(2,C)))]
11//!     Level 1:              [hash(hash(0,A),hash(1,B)),hash(hash(2,C),hash(2,C))]
12//!     Level 0 (leaves):     [hash(0,A),hash(1,B),hash(2,C)]
13//! ```
14//!
15//! A proof for a given leaf is generated by collecting the sibling at each level (from the leaf up to the root).
16//! An external process can then use this proof (with some trusted root) to verify that the leaf (at a fixed position)
17//! is part of the tree.
18//!
19//! # Example
20//!
21//! ```rust
22//! use commonware_storage::bmt::{Builder, Tree};
23//! use commonware_cryptography::{Sha256, sha256::Digest, Hasher as _};
24//!
25//! // Create transactions and compute their digests
26//! let txs = [b"tx1", b"tx2", b"tx3", b"tx4"];
27//! let digests: Vec<Digest> = txs.iter().map(|tx| Sha256::hash(*tx)).collect();
28//!
29//! // Build a Merkle Tree from the digests
30//! let mut builder = Builder::<Sha256>::new(digests.len());
31//! for digest in &digests {
32//!    builder.add(digest);
33//! }
34//! let tree = builder.build();
35//! let root = tree.root();
36//!
37//! // Generate a proof for leaf at index 1
38//! let mut hasher = Sha256::default();
39//! let proof = tree.proof(1).unwrap();
40//! assert!(proof.verify(&mut hasher, &digests[1], 1, &root).is_ok());
41//! ```
42
43use bytes::{Buf, BufMut};
44use commonware_codec::{EncodeSize, Read, ReadExt, ReadRangeExt, Write};
45use commonware_cryptography::{Digest, Hasher};
46use thiserror::Error;
47
48/// There should never be more than 255 levels in a proof (would mean the Binary Merkle Tree
49/// has more than 2^255 leaves).
50const MAX_LEVELS: usize = u8::MAX as usize;
51
52/// Errors that can occur when working with a Binary Merkle Tree (BMT).
53#[derive(Error, Debug)]
54pub enum Error {
55    #[error("invalid position: {0}")]
56    InvalidPosition(u32),
57    #[error("invalid proof: {0} != {1}")]
58    InvalidProof(String, String),
59    #[error("no leaves")]
60    NoLeaves,
61    #[error("unaligned proof")]
62    UnalignedProof,
63}
64
65/// Constructor for a Binary Merkle Tree (BMT).
66pub struct Builder<H: Hasher> {
67    hasher: H,
68    leaves: Vec<H::Digest>,
69}
70
71impl<H: Hasher> Builder<H> {
72    /// Creates a new Binary Merkle Tree builder.
73    pub fn new(leaves: usize) -> Self {
74        Self {
75            hasher: H::new(),
76            leaves: Vec::with_capacity(leaves),
77        }
78    }
79
80    /// Adds a leaf to the Binary Merkle Tree.
81    ///
82    /// When added, the leaf is hashed with its position.
83    pub fn add(&mut self, leaf: &H::Digest) -> u32 {
84        let position: u32 = self.leaves.len().try_into().expect("too many leaves");
85        self.hasher.update(&position.to_be_bytes());
86        self.hasher.update(leaf);
87        self.leaves.push(self.hasher.finalize());
88        position
89    }
90
91    /// Builds the Binary Merkle Tree.
92    ///
93    /// It is valid to build a tree with no leaves, in which case
94    /// just an "empty" node is included (no leaves will be provable).
95    pub fn build(self) -> Tree<H> {
96        Tree::new(self.hasher, self.leaves)
97    }
98}
99
100/// Constructed Binary Merkle Tree (BMT).
101#[derive(Clone, Debug)]
102pub struct Tree<H: Hasher> {
103    /// Records whether the tree is empty.
104    empty: bool,
105
106    /// The digests at each level of the tree (from leaves to root).
107    levels: Vec<Vec<H::Digest>>,
108}
109
110impl<H: Hasher> Tree<H> {
111    /// Builds a Merkle Tree from a slice of position-hashed leaf digests.
112    fn new(mut hasher: H, mut leaves: Vec<H::Digest>) -> Self {
113        // If no leaves, add an empty node.
114        //
115        // Because this node only includes a position, there is no way a valid proof
116        // can be generated that references it.
117        let mut empty = false;
118        if leaves.is_empty() {
119            leaves.push(hasher.finalize());
120            empty = true;
121        }
122
123        // Create the first level
124        let mut levels = Vec::new();
125        levels.push(leaves);
126
127        // Construct the tree level-by-level
128        let mut current_level = levels.last().unwrap();
129        while current_level.len() > 1 {
130            let mut next_level = Vec::with_capacity(current_level.len().div_ceil(2));
131            for chunk in current_level.chunks(2) {
132                // Hash the left child
133                hasher.update(&chunk[0]);
134
135                // Hash the right child
136                if chunk.len() == 2 {
137                    hasher.update(&chunk[1]);
138                } else {
139                    // If no right child exists, duplicate left child.
140                    hasher.update(&chunk[0]);
141                };
142
143                // Compute the parent digest
144                next_level.push(hasher.finalize());
145            }
146
147            // Add the computed level to the tree
148            levels.push(next_level);
149            current_level = levels.last().unwrap();
150        }
151        Self { empty, levels }
152    }
153
154    /// Returns the root of the tree.
155    pub fn root(&self) -> H::Digest {
156        *self.levels.last().unwrap().first().unwrap()
157    }
158
159    /// Generates a Merkle proof for the leaf at `position`.
160    ///
161    /// The proof contains the sibling digest at each level needed to reconstruct
162    /// the root.
163    pub fn proof(&self, position: u32) -> Result<Proof<H>, Error> {
164        // Ensure the position is within bounds
165        if self.empty || position >= self.levels.first().unwrap().len() as u32 {
166            return Err(Error::InvalidPosition(position));
167        }
168
169        // For each level (except the root level) record the sibling
170        let mut siblings = Vec::with_capacity(self.levels.len() - 1);
171        let mut index = position as usize;
172        for level in &self.levels {
173            if level.len() == 1 {
174                break;
175            }
176            let sibling_index = if index % 2 == 0 { index + 1 } else { index - 1 };
177            let sibling = if sibling_index < level.len() {
178                level[sibling_index]
179            } else {
180                // If no right child exists, use a duplicate of the current node.
181                //
182                // This doesn't affect the robustness of the proof (allow a non-existent position
183                // to be proven or enable multiple proofs to be generated from a single leaf).
184                level[index]
185            };
186            siblings.push(sibling);
187            index /= 2;
188        }
189        Ok(Proof { siblings })
190    }
191
192    /// Generates a Merkle range proof for a contiguous set of leaves from `start`
193    /// to `end` (inclusive).
194    ///
195    /// The proof contains the minimal set of sibling digests needed to reconstruct
196    /// the root for all elements in the range. This is more efficient than individual
197    /// proofs when proving multiple consecutive elements.
198    pub fn range_proof(&self, start: u32, end: u32) -> Result<RangeProof<H>, Error> {
199        // For empty trees, return an empty proof
200        if self.empty && start == 0 && end == 0 {
201            return Ok(RangeProof::default());
202        }
203
204        // Ensure the range is within bounds
205        if start > end {
206            return Err(Error::InvalidPosition(start));
207        }
208        let leaf_count = self.levels.first().unwrap().len() as u32;
209        if start >= leaf_count {
210            return Err(Error::InvalidPosition(start));
211        }
212        if end >= leaf_count {
213            return Err(Error::InvalidPosition(end));
214        }
215
216        // For each level (except the root level) collect the necessary siblings
217        let mut siblings = Vec::new();
218        for (level_idx, level) in self.levels.iter().enumerate() {
219            // If the level has only one node, we're done
220            if level.len() == 1 {
221                break;
222            }
223
224            // Calculate the range of indices at this level
225            let level_start = (start as usize) >> level_idx;
226            let level_end = (end as usize) >> level_idx;
227
228            // Check if we need a left sibling
229            let mut left = None;
230            if level_start % 2 == 1 {
231                // Our range starts at an odd index, so we need the even sibling to the left
232                left = Some(level[level_start - 1]);
233            }
234
235            // Check if we need a right sibling
236            let mut right = None;
237            if level_end % 2 == 0 {
238                if level_end + 1 < level.len() {
239                    // Our range ends at an even index, so we need the odd sibling to the right
240                    right = Some(level[level_end + 1]);
241                } else {
242                    // If no right child exists, use a duplicate of the current node.
243                    //
244                    // This doesn't affect the robustness of the proof (allow a non-existent position
245                    // to be proven or enable multiple proofs to be generated from a single leaf).
246                    right = Some(level[level_end]);
247                }
248            }
249
250            siblings.push(Bounds { left, right });
251        }
252
253        Ok(RangeProof { siblings })
254    }
255}
256
257/// A Merkle proof for a leaf in a Binary Merkle Tree.
258#[derive(Clone, Debug, Eq)]
259pub struct Proof<H: Hasher> {
260    /// The sibling hashes from the leaf up to the root.
261    pub siblings: Vec<H::Digest>,
262}
263
264impl<H: Hasher> PartialEq for Proof<H>
265where
266    H::Digest: PartialEq,
267{
268    fn eq(&self, other: &Self) -> bool {
269        self.siblings == other.siblings
270    }
271}
272
273impl<H: Hasher> Write for Proof<H> {
274    fn write(&self, writer: &mut impl BufMut) {
275        self.siblings.write(writer);
276    }
277}
278
279impl<H: Hasher> Read for Proof<H> {
280    type Cfg = ();
281
282    fn read_cfg(reader: &mut impl Buf, _: &Self::Cfg) -> Result<Self, commonware_codec::Error> {
283        let siblings = Vec::<H::Digest>::read_range(reader, ..=MAX_LEVELS)?;
284        Ok(Self { siblings })
285    }
286}
287
288impl<H: Hasher> EncodeSize for Proof<H> {
289    fn encode_size(&self) -> usize {
290        self.siblings.encode_size()
291    }
292}
293
294impl<H: Hasher> Proof<H> {
295    /// Verifies that a given `leaf` at `position` is included in a Binary Merkle Tree
296    /// with `root` using the provided `hasher`.
297    ///
298    /// The proof consists of sibling hashes stored from the leaf up to the root. At each level, if the current
299    /// node is a left child (even index), the sibling is combined to the right; if it is a right child (odd index),
300    /// the sibling is combined to the left.
301    pub fn verify(
302        &self,
303        hasher: &mut H,
304        leaf: &H::Digest,
305        mut position: u32,
306        root: &H::Digest,
307    ) -> Result<(), Error> {
308        // Compute the position-hashed leaf
309        hasher.update(&position.to_be_bytes());
310        hasher.update(leaf);
311        let mut computed = hasher.finalize();
312        for sibling in self.siblings.iter() {
313            // Determine the position of the sibling
314            let (left_node, right_node) = if position % 2 == 0 {
315                (&computed, sibling)
316            } else {
317                (sibling, &computed)
318            };
319
320            // Compute the parent digest
321            hasher.update(left_node);
322            hasher.update(right_node);
323            computed = hasher.finalize();
324
325            // Move up the tree
326            position /= 2;
327        }
328        let result = computed == *root;
329        if result {
330            Ok(())
331        } else {
332            Err(Error::InvalidProof(computed.to_string(), root.to_string()))
333        }
334    }
335}
336
337/// A pair of sibling digests, one on the left boundary and one on the right boundary.
338#[derive(Clone, Debug, Eq)]
339pub struct Bounds<D: Digest> {
340    /// The left sibling digest.
341    pub left: Option<D>,
342
343    /// The right sibling digest.
344    pub right: Option<D>,
345}
346
347impl<D: Digest> PartialEq for Bounds<D> {
348    fn eq(&self, other: &Self) -> bool {
349        self.left == other.left && self.right == other.right
350    }
351}
352
353impl<D: Digest> Write for Bounds<D> {
354    fn write(&self, writer: &mut impl BufMut) {
355        self.left.write(writer);
356        self.right.write(writer);
357    }
358}
359
360impl<D: Digest> Read for Bounds<D> {
361    type Cfg = ();
362
363    fn read_cfg(reader: &mut impl Buf, _: &Self::Cfg) -> Result<Self, commonware_codec::Error> {
364        Ok(Self {
365            left: Option::<D>::read(reader)?,
366            right: Option::<D>::read(reader)?,
367        })
368    }
369}
370
371impl<D: Digest> EncodeSize for Bounds<D> {
372    fn encode_size(&self) -> usize {
373        self.left.encode_size() + self.right.encode_size()
374    }
375}
376
377/// A Merkle range proof for a contiguous set of leaves in a Binary Merkle Tree.
378#[derive(Clone, Debug, Eq)]
379pub struct RangeProof<H: Hasher> {
380    /// The sibling digests needed to prove all elements in the range.
381    ///
382    /// Organized by level, from leaves to root. Each level can have at most
383    /// 2 siblings (one on the left boundary and one on the right boundary).
384    pub siblings: Vec<Bounds<H::Digest>>,
385}
386
387impl<H: Hasher> PartialEq for RangeProof<H>
388where
389    H::Digest: PartialEq,
390{
391    fn eq(&self, other: &Self) -> bool {
392        self.siblings == other.siblings
393    }
394}
395
396impl<H: Hasher> Default for RangeProof<H> {
397    fn default() -> Self {
398        Self { siblings: vec![] }
399    }
400}
401
402/// A node tracked during range proof verification.
403struct Node<D: Digest> {
404    position: usize,
405    digest: D,
406}
407
408impl<H: Hasher> RangeProof<H> {
409    /// Verifies that a given range of `leaves` starting at `position` are included
410    /// in a Binary Merkle Tree with `root` using the provided `hasher`.
411    ///
412    /// The proof contains the set of sibling digests needed to reconstruct
413    /// the root for all elements in the range.
414    pub fn verify(
415        &self,
416        hasher: &mut H,
417        position: u32,
418        leaves: &[H::Digest],
419        root: &H::Digest,
420    ) -> Result<(), Error> {
421        // Handle empty tree case
422        if position == 0 && leaves.is_empty() && self.siblings.is_empty() {
423            let empty_root = hasher.finalize();
424            if empty_root == *root {
425                return Ok(());
426            } else {
427                return Err(Error::InvalidProof(
428                    empty_root.to_string(),
429                    root.to_string(),
430                ));
431            }
432        }
433
434        // Check that we have leaves and the position is valid
435        if leaves.is_empty() {
436            return Err(Error::NoLeaves);
437        }
438        if position.checked_add(leaves.len() as u32).is_none() {
439            return Err(Error::InvalidPosition(position));
440        }
441
442        // Compute position-hashed leaves
443        let mut nodes: Vec<Node<H::Digest>> = Vec::new();
444        for (i, leaf) in leaves.iter().enumerate() {
445            let leaf_position = position + i as u32;
446            hasher.update(&leaf_position.to_be_bytes());
447            hasher.update(leaf);
448            nodes.push(Node {
449                position: leaf_position as usize,
450                digest: hasher.finalize(),
451            });
452        }
453
454        // Process each level
455        for bounds in self.siblings.iter() {
456            // Check if we should have a left sibling
457            let first_pos = nodes[0].position;
458            let last_pos = nodes[nodes.len() - 1].position;
459            let needs_left = first_pos % 2 == 1;
460            let needs_right = last_pos % 2 == 0;
461            if needs_left != bounds.left.is_some() {
462                return Err(Error::UnalignedProof);
463            }
464            if needs_right != bounds.right.is_some() {
465                return Err(Error::UnalignedProof);
466            }
467
468            // If we have a left sibling, we need to include it
469            let mut i = 0;
470            let mut next_nodes = Vec::new();
471            if let Some(left) = &bounds.left {
472                // The first node in our range needs its left sibling
473                let node = &nodes[0];
474                hasher.update(left);
475                hasher.update(&node.digest);
476                next_nodes.push(Node {
477                    position: node.position / 2,
478                    digest: hasher.finalize(),
479                });
480                i = 1;
481            }
482
483            // Process pairs of nodes in our range
484            while i < nodes.len() {
485                // Compute the parent position
486                let node = &nodes[i];
487                let parent_pos = node.position / 2;
488
489                // Check if we have a pair within our range
490                if i + 1 < nodes.len() && nodes[i + 1].position == node.position + 1 {
491                    // We have both children in our range
492                    hasher.update(&node.digest);
493                    hasher.update(&nodes[i + 1].digest);
494                    next_nodes.push(Node {
495                        position: parent_pos,
496                        digest: hasher.finalize(),
497                    });
498                    i += 2;
499                } else if i == nodes.len() - 1 {
500                    // This is the last node and it should have a right sibling
501                    let right = bounds.right.as_ref().ok_or(Error::UnalignedProof)?;
502                    hasher.update(&node.digest);
503                    hasher.update(right);
504                    next_nodes.push(Node {
505                        position: parent_pos,
506                        digest: hasher.finalize(),
507                    });
508                    i += 1;
509                } else {
510                    // Single node in the middle (shouldn't happen for contiguous range)
511                    return Err(Error::UnalignedProof);
512                }
513            }
514
515            nodes = next_nodes;
516        }
517
518        // Verify we ended up with the expected root
519        if nodes.len() != 1 {
520            return Err(Error::UnalignedProof);
521        }
522        let computed = nodes[0].digest;
523        if computed == *root {
524            Ok(())
525        } else {
526            Err(Error::InvalidProof(computed.to_string(), root.to_string()))
527        }
528    }
529}
530
531impl<H: Hasher> Write for RangeProof<H> {
532    fn write(&self, writer: &mut impl BufMut) {
533        self.siblings.write(writer);
534    }
535}
536
537impl<H: Hasher> Read for RangeProof<H> {
538    type Cfg = ();
539
540    fn read_cfg(reader: &mut impl Buf, _: &Self::Cfg) -> Result<Self, commonware_codec::Error> {
541        let siblings = Vec::<Bounds<H::Digest>>::read_range(reader, ..=MAX_LEVELS)?;
542        Ok(Self { siblings })
543    }
544}
545
546impl<H: Hasher> EncodeSize for RangeProof<H> {
547    fn encode_size(&self) -> usize {
548        self.siblings.encode_size()
549    }
550}
551
552#[cfg(test)]
553mod tests {
554    use super::*;
555    use commonware_codec::{DecodeExt, Encode};
556    use commonware_cryptography::sha256::{Digest, Sha256};
557    use commonware_utils::hex;
558
559    fn test_merkle_tree(n: usize) -> Digest {
560        // Build tree
561        let mut digests = Vec::with_capacity(n);
562        let mut builder = Builder::new(n);
563        for i in 0..n {
564            let digest = Sha256::hash(&i.to_be_bytes());
565            builder.add(&digest);
566            digests.push(digest);
567        }
568        let tree = builder.build();
569        let root = tree.root();
570
571        // For each leaf, generate and verify its proof
572        let mut hasher = Sha256::default();
573        for (i, leaf) in digests.iter().enumerate() {
574            // Generate proof
575            let proof = tree.proof(i as u32).unwrap();
576            assert!(
577                proof.verify(&mut hasher, leaf, i as u32, &root).is_ok(),
578                "correct fail for size={n} leaf={i}"
579            );
580
581            // Serialize and deserialize the proof
582            let mut serialized = proof.encode();
583            let deserialized = Proof::<Sha256>::decode(&mut serialized).unwrap();
584            assert!(
585                deserialized
586                    .verify(&mut hasher, leaf, i as u32, &root)
587                    .is_ok(),
588                "deserialize fail for size={n} leaf={i}"
589            );
590
591            // Modify a sibling hash and ensure the proof fails
592            if !proof.siblings.is_empty() {
593                let mut update_tamper = proof.clone();
594                update_tamper.siblings[0] = Sha256::hash(b"tampered");
595                assert!(
596                    update_tamper
597                        .verify(&mut hasher, leaf, i as u32, &root)
598                        .is_err(),
599                    "modify fail for size={n} leaf={i}"
600                );
601            }
602
603            // Add a sibling hash and ensure the proof fails
604            let mut add_tamper = proof.clone();
605            add_tamper.siblings.push(Sha256::hash(b"tampered"));
606            assert!(
607                add_tamper
608                    .verify(&mut hasher, leaf, i as u32, &root)
609                    .is_err(),
610                "add fail for size={n} leaf={i}"
611            );
612
613            // Remove a sibling hash and ensure the proof fails
614            if !proof.siblings.is_empty() {
615                let mut remove_tamper = proof.clone();
616                remove_tamper.siblings.pop();
617                assert!(
618                    remove_tamper
619                        .verify(&mut hasher, leaf, i as u32, &root)
620                        .is_err(),
621                    "remove fail for size={n} leaf={i}"
622                );
623            }
624        }
625
626        // Test proof for larger than size
627        assert!(tree.proof(n as u32).is_err());
628
629        // Return the root so we can ensure we don't silently change.
630        root
631    }
632
633    /// Roots for all trees with 1..201 leaves.
634    ///
635    /// We use these pre-generated roots to ensure that we don't silently change
636    /// the tree hashing algorithm.
637    const ROOTS: [&str; 200] = [
638        "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855",
639        "50ae5b142a0f31db537ba060ba07e46fafe1ec960ebec7b6f08f03dafe774f52",
640        "fce6b9d873d5a92d828695fbddb93d0cecc76747e311035cf7b2a80532f65ea2",
641        "33635879d11892586d0735076c9d1b9d661344861d46aa96c36450b71a32300c",
642        "e5e67dc697801aea53044bc042a0e8724abf1f96512c0b4a4dd9027697fbb160",
643        "4fe4f8ada41e7d98d2344a7faec0360cf4c718318c6cce2bbfdad544288ab746",
644        "1a80d0ad0413511f1a56490d9527a5dd2f4686884c4fdc4e912221b7a67462c3",
645        "924aeecd88420edaf033e055f276823ffea95eb965f8a24bedd3b71ff7a4e00e",
646        "48b65ee4de800d7ab900781dc0257bf22675e5d921395e4392e1f1ca81095d06",
647        "846ab5f09531e4176aa66a6bd03d83f7503c16dfc494aa7cf600825bb11df9c3",
648        "bd491c9ca0678c29f61ad2affcfb313edbbd5f59c58a7c0d5ce1f0dbb7baf282",
649        "422aab7074448c8d5563ba5636f18fb46ccab9de0a12c997d82d12f0273a9477",
650        "4ee0c261ba4eb3902ac003b6789675f7a2ccb09ffd23249fdc457f436e675b18",
651        "e303776cd1f6f708659765f938dcb79ffe7878f03b67d97947ee8320c2377480",
652        "787847b8cfd106d7264ed6280c72d4e5e62294c8c4f786f486b16217b993fcbb",
653        "2d7cb674b223d2b3bf82a3d76d53b58eb542b5f9cec672f075c2cd3056a869f8",
654        "9888bb342b33693d7885e1a84fa9cd803bdbb3fdb5593f6cabdd68511fc34e3a",
655        "d491440069227e34868e75ea9c4c0946bc3084651798946916100de64b1ee2c7",
656        "b3f496525d3b4b9db0d409a954a0f29078b1c9f7b4fbc5d32e4615bfbf657ab3",
657        "3ad08b0ce43aea793560e5b093398abfdfb37310e86c8bf0cfa91e7573f80100",
658        "86229048316a1c894883a9e3a8d3c3d3e95f0b843d1f648f9e58462aff9f3148",
659        "143f71172df1ea73e59c795d0b3a7ccaff6cb9d934200ddb7fe485a02bbcb25d",
660        "688a6084995fb4d5b65592f8fac5b5347d46252ff08059d825884ed7b46a92a9",
661        "1152caa5f17fd92aa0f86b4ec07a442b176b62961e525bfe84d5b82913ab5269",
662        "71e367ea9deacf960f80370f169accf59345b77e02e780bf916e9daab0be060b",
663        "05bcda0901af59dd91b74c3f34edc6f7ba9e4b6e61b77888053a02c65f7b75a3",
664        "6c8e49673a96942fa83ff46c4f82511806d7185e7025d8b39df159b98b1394fa",
665        "a38f666a29ea9c6d084eebce18a31422234db99be0e947205e5b6fb05dc344a4",
666        "b9325d2e47b15e451928b96feadaf29ae57107e15f28f04a59f54e44b3e152a0",
667        "5e35af451db9a82e17a904e477aa48ebf678abd3527c5a7a6c1e0d0cae033196",
668        "eb1e3e7c34f35cee920cae35d779675f8f0e4a226d513ff72e67a61f1cb07bed",
669        "dfffa428315478482fb39b6cabd19b82c4abe0fdfe28a2d8b637b00934694d26",
670        "e8af2e8391e3fcec5a1a4acd0df713dd56abea1949234aeec4f999c57adc6886",
671        "9ffeaf6d1802438062656b7a8ac052287b349172abb1cd0c6102de8d782c773b",
672        "637127e22c8c5505c95637436a8c7872523bb1e05000ce3b026b2c60335a9ec6",
673        "3a5ae08c9837b67941f2096b4e806b8bf54e1d11836e3b54c2d1ddd8be81d339",
674        "b9e868d4441e850c8989ab140cb7e7107fa916a7cc9f10532460669b5d185fb9",
675        "ca4e9513943517c7756ecb1fdfcf941f8b296eb59ca344960ddf447fc811b3fe",
676        "e889aa56a848a2b283fd3fd6e134fc83450c0d6c1d01f576c2bb5eb72a87f409",
677        "7f37830b35e2eaf1c22658508a2cf8cf2c4ad138ee96bbb4dca6d466699ab09d",
678        "5f30c90f31b8a32a117579c89ef258d3621e3c4ffd0051b50fe7032e7d16024c",
679        "022e9efb9c643379420118e4553d2355eec5e3bcb3502778bc4b2e85d57b4795",
680        "daa5d97c2202a64210ec877a9075dd17fb9f6178ad6b0905809a4d79df13e3c8",
681        "5d2873958ea245ac1e8ece124ae9fe1b5cecb36034a0fa644f447026728bcabd",
682        "7744dc3b7505d01edc098edb6873e8e923d371ec777b0abe2d7fc0f5e5abfcff",
683        "52fe4af553d4bb631cc42ceabb7395fd2a234ee1431b8720571d2878e4676e4b",
684        "c46c4647b7464f67c19ec8a66815b87487070fd0aad02dd51c537af08e7036b2",
685        "004828da3fd62ee55449394a54882573d2ce5f323e45cf021e99ca0c3f4b12fd",
686        "aea7466b24c3537178dfb0e2b23254162230c36613664f546923edda8f4a9cb9",
687        "12b52d15244e3e4f01f2b69dff8b18e4d30cda39e3d87b09875fba0918c0f3c4",
688        "cb774e0aba6a497ebeefdac5237ea4b91cf02d8df761e4d5931bca06f92ba7e7",
689        "730fd826be4ae1482b88affb6e74ff3461409903a499f86170168f4634a3e36b",
690        "12ac285defa63afcc7a47541993837d2da3f81def14004a058d0b82c340f3f28",
691        "e661d6c753cf32fa26eefa5d2c1e4602386df79e96b1e0bd3a54454de6fadc1c",
692        "608587b5ae578e310be49be55fee4d950bf85cda31af2ecd0306bfc34fab61d1",
693        "a41205347e79e7b2a688422cb620caef3862c06be97c3cceb0cc6cef39fbafe8",
694        "d332d4863654ba825c0e1ddb63b9a0c1bf35aea89a28f0c7234ec104e4e9e8e8",
695        "d21f7cbce3ba334611617b73f5abf283d17ca7a7a0e460f4e4c559bb6175cadb",
696        "ec13e53573f637e38ce6f45b55e8a9967f3121ee30b52fd2b8b680512b175ee0",
697        "b137cc53ae95e87de14667d94bfc77015d29ae978c09ada78ce00061b03f7d56",
698        "f41819163d7e13359c09c50776f0da810dc39d6e15ea67f2b047dbd2a609933f",
699        "f128a3ee5cb5b6d687aaf6908445256de0099d976346ef6e5496bd51a2b7400c",
700        "94141d70b9b61b86ec050753f11a9f2d275f3d28a07d044c7f0d8736128252a9",
701        "80acd071567fcca9e8740fe47d29c1197b2df093e22197c53e6176d9b1565045",
702        "55871c3b57591746d7febac3e386dd838cf13276572daf484332811f1a62e8f4",
703        "7674ec07655fb1f00bc1c46f9f7b3847674815b4c8a05327ac6a40ac031c7616",
704        "253794e58aab5d5ad517c2e1d007566e25c8be42033c1255f4139dc014914c2f",
705        "ad0ad5f5c95c2e5ad0f78354bafb7563f0c6573a74253145373ffc24eb13debb",
706        "c322c8902b4a4c10879856222f820d8f92ffd15d25d5d461a1ac126954580626",
707        "1e1be47b4c0b321f3ac638039ff9e47ca6ebadf15a6230699c6405a3ed7044dc",
708        "225a9d06465ac4b1cf65528c799966c5a8344e484d31289c8cfd9d29202bd02f",
709        "17382a91ee6946f78cb712e53a9e58d6c0e07a26be2b47463ecbfcada335dd6e",
710        "4635742a72a250016f3c92d510d3aa64b2f7f2d8f739cace99b49ae20bfda981",
711        "0b49ac169f476f95c84e376ca86c7ac66a82df44bd6783edf238be23bffaad5e",
712        "f18d45122b929ae17a7233f60414b5626577eb00b00e106a1eb852a6c4cf7f57",
713        "3ab2fb11c3d06ca1d8228402b7f6f3ebebc2072305e015fd142c51675cfddbec",
714        "c9dcb27313895d2f7c67af4d6ae6734a22aecc49cec0b9f3cdb27eed7e4d8f03",
715        "ed4397b2d47b98848253e66d79aba7bfa2beb2a44ffc3aa6d9b4056fcfd099cb",
716        "b35074c978d512800e700adfddf0a73fbf4de49215cfdb69430aa51525ce507e",
717        "58093e52dc8e10fed83fd8f60a6ebd5980cde59667044d3eaf6dd942c3dc110a",
718        "b23225934ef6cfbfc2fd95da072a030d8a4815502bf15d14f90a64b6b6bd1a83",
719        "e66ec3aff80f8224a1012ef0fd137e685ab294c4a3d47b976553d13afcc130cf",
720        "b06ec0ecaa3d9fba83a25bb25b44ef88ba66748c7dd6ca4692fa6c3efccfb44e",
721        "0a9e7cbb5b1697e45245329a5a4bff4b2ca1a93a7f1ed1cf8a552ac6493131ce",
722        "f9f3a65472790ca66b908e0e8bddd2040aa0db36557f453df8a8d6b4604a12c5",
723        "0650349d871b9efc044110657c49eaa2dcbb27257a320d6e59a18178c237ec38",
724        "49c04edb1576b51db9fe0bd990dbf16b90418837be51c7983b32d76bbf2f9f30",
725        "1b2ece1a345f9e762235b01c8f644277408281545f063732183386bab2a09dce",
726        "182b36c2af475f3ca465b409f8a110ec6a23e0e5388730ed7920628bbe15268e",
727        "a8aecf727c29a84d4e15be02399f78b4fd0f1b45a48d30062a8c871de684b612",
728        "9e0bc42a02db1b41d4ed9a7c6fcab527085c469b37471bc20f89fbeedd5e03ce",
729        "3b89297f5235f95c35dabe6235dd89958af0b15b1868e5151cde112fa3039773",
730        "15e7c5ef9b6c731b075322897799f54ec8622a00ca90cceac3411f83b49ea237",
731        "79e2533ad3eebb44325eb5a5b93e7cbb67278b564eeeff4a029c802935527a01",
732        "3a691d7163b2ff4bf566c0bee7ccef767a5303d3a9319729d799ae12e19f4c1a",
733        "5799066961c8ca5c5b3d62e90e407fa51429488fd14c80ba8ba28529a2071c84",
734        "ae530275bf76e94083b2c8de75ad44fe7ab4d45c46fd461ca796a7a2803e7608",
735        "3f8eec5de2cc57152c9d58caa5fd4d2a3ddf22d666eae9a6ae0aee433127f9f6",
736        "00f16a9bde34a6d3c1b0c21486165cc32dfa840e3a07da864625d7a2b1d493bf",
737        "e57b868d21768ac786eca4889030c7517af93102198b0cdf15879bb12e434985",
738        "48a705b3265d0696a69c7870d05052ed0d24c9c094727408be4429f6b236db62",
739        "14e0743518594de85852563962db3b63688dda7034f86f86b903c9bec21860f2",
740        "9d1b3b67045dc6b85b3a2c5cd4c2ed14c6ad2d1f17740a6fe29387865e433c71",
741        "ca5afe197a9aeb4020a6110ac693e84b174800e4de4bd92d9a15cacf7d77f598",
742        "7f833e5072a4c8c3802613626b5afa42a69790614f4fd84ee269ce2cc8de08fb",
743        "d4f5f4d6b6c185e1d68dcac5d4e7d55828cd94c1eb6170e75d0ca474e21a14d8",
744        "eaf15269b6f147771746cf2cd7f8b6f2eab92287a8468f03127eab68b78fcfa1",
745        "f84c317503d500c03b32e2d14360a6d1877e791f5cccaccc9c0e15c71ed85705",
746        "e0e6d90287b23f7065a13537ed8353d43bcc14b80e6902938db6cf5ac43e79fb",
747        "2e244362779d657581f0a9879daba8acbe1c7234a2e27eef91c8a0a1be6c6efb",
748        "7086f9c9e40a5f576235d41dac2187001ff1c315cc94dd3a0feaf3e905be7f7a",
749        "4b9e14b2834ab37608e3ec4b85db30a4b45d0caf78dd6363e02d8802a2d51a41",
750        "e3e44f53cf473636859fc6d6eb05dc505e5a56c612216636a44c8eac8efad382",
751        "99d4638fb24b7aca63e936a60abb74abb70d7797643879be80735605a7e2a2ed",
752        "1e8401b6c65c67dc544e9a1ce21c6ce9903702ac30c93d0caa0df64b6c0e1e36",
753        "1bf14f3f0372956833770f87e9145cfc0a5b0dc985b1b694353e705961e94738",
754        "ed9b69ad2d779f82b2d1a97a5bd1e2f941b2edfdfd82db99f121561964345128",
755        "035c58d5ac8a38fc0e6dec6472f3459f47c17f76bb04eef929064482f5bfb2a9",
756        "706ff9580c8869ab68edb9e801b5c631377a10ac07617fb34d9250616231ad52",
757        "f9b815729a5cdfe9f1ebcaaca36a658464a5d49c2dad1dcae7aed2688c2209a7",
758        "8c1e7468650b0f8309c23b7fb453ce59ab989fcaa80fa32bd82d02c25fc19b68",
759        "557a00a4e6d55c60a033b23ca20975f5c774ed0fef3bc316f68fb4a6df66137e",
760        "06516e2e9e5fa3583c643209666758483e38c642757e7a452ed29d716229370b",
761        "f708b4d19acfadd56e1e4275ed1191d285c656ee045efd2b7049539a39caf5a2",
762        "00a126e14b8ec6f7e7e31d0d4b551a24fcbcad62045490feb532b0b78d15a411",
763        "c47d49034a6a7ce59fae50d10153fdd619783c39265789a7858b420cbc32b56e",
764        "c7d67122fc2b83e565ee0108e16753936f2bb62128d38237454053e60ac918a8",
765        "18db7a4c3694b83c2258a4bafdd062cf20d80d356d9d899bc429be9d732dac0e",
766        "e3e55212157e06d8745eb23eb4a391611abf0d9e98efe19b482d0d0fdd66a053",
767        "70d1830363a58704b037f018a417b7e8682f7a2bad6ed5eaefacf335b9f2de13",
768        "559e34d21bf90025d69c0401e3bfb70abfd470fcd4a64f739728f41c0fed4075",
769        "73828339c42835cd9f48291c11322d905a35e4d0cccca4095a93a1e4bb778664",
770        "7f4cba2e2e584eae771dc328099a098819a6625ea5b2c9382120a1504964841b",
771        "a1f44690445ccd1b9930f615e416aeda750601a49631b4eb536f6fd709293f0e",
772        "5de9674bc7412231cdb526dc17bfd2e0ed0635be4224d9f72c16378bba7ad8dd",
773        "7b217e77ea4175029928ba4839f6d350df9e41b67cff183b1a43ab52925193ca",
774        "53bea1bad7659ccd0feb50136fc5093878888fe0cb16dee5ed7503b01d96e4ba",
775        "084e489bf686d41db4e8f0ff1bce15a40ac24b948ddcc377a8095d99751673ea",
776        "bf67b177d3000a2ac7df34d422486cec6606c6ee82ee50aa91dd98b567957f6d",
777        "2f5777d29dcb3c78730c52fedff7d57270125f9a8a570c9d30cf0ad141803118",
778        "3c06f61c8b538beb4a557bbdde61a379a631972b3d0698fbb98c68c874744698",
779        "12d7d4f4c868b645681dc988d3a170b2f6e425c067ef89ee7a7f07c801ba226e",
780        "6f0a289c5c41336a1b5d32aecaec5aa57d1352e319820b80e84d38979ce1ea2c",
781        "a8e2f08c46aeadcf56bb10d427418174269e679af7a53c7a1fe92c3fe13f133b",
782        "e7e04233a526c7b513eb02d65b8c81b48edf95782d0fbacd0ece7d391f3a7598",
783        "d0c677a7b01abb943f00ab1dfa2d4097c4b2309566d6a9ada3cd0f0d1041b449",
784        "2cc6597dfd2903bb9e8549f2d1f6842f0e136b0aab9872bbf4b86f49b59c3678",
785        "0f230a73d7922eae8290b989014806fb9e6e3c042fa87a8adc742b31e99c4dcc",
786        "ec0ab16c9228a1671d6501189cc53dedaafe17cb3aea8119f77fd78d035ec740",
787        "f80b66f4f25c4995b19cb973dfd5be34cda67e47e359e944d7fb6ee63e4a64b4",
788        "791066ca90c59ab7729bc242be45e26f8f1343656ed63e7c597eb3618ac34036",
789        "5efea2b25d7407a8c14a9d0f232e7280a9b13b14e48635925be0703547060f3c",
790        "5bb18cd0630e2cefec9817220b3561157f893570cf8f7374eb5d4d374be7d3fc",
791        "97d1a186229ef63fd0616c3dc36777065ad201b11109b8a8b43a7326c868cd72",
792        "d715dfb79b1bca2e5464e3c2c1f7b9cd3b3962fb7a9b42ddc629efd76a5b9b0d",
793        "bb9960745bfd91f49aedda17a5151d3f2105523d637e8df3c4a19e201688e3ab",
794        "4d694f1b092b6c514f50b832d483d14cbf2d22435c1d64b0a0143b1b91a7db0e",
795        "f4aec328caed1748906126cd72f9dc032dc529e3cabc9a55f96ff7f08e136630",
796        "65d7ca2883222a70edb0acadb0d969fb3824224e3de365ca98b8d41124955640",
797        "5a7c37a041319dbc68a2aebb98d18dcf971bdd26f7679fb4c8d71023dd62e763",
798        "45c7c8a9c1a6d073df038a63c8fb3585750f2186020fc42e67388ed90d687334",
799        "76ceb2ed736c577275c47a270f13fc3f829db8f677fe52117a7916913f8e9f07",
800        "83616f52af18dfb6bca88c39905c24d1d7443b8fafcb408ba92e3357bf64826d",
801        "6184a19e674eb02c014ffd52ccfae8451d78bdd371d7f3c5d9c0b034ea75f34b",
802        "73cbf19495785c2a8822229e71ae5246cb0572f5bfc31ab0c95a6f9bdbe42880",
803        "ad417fcc01c49775fedc526cac80ed9751799f50db513d7107da4b5539e25025",
804        "fcf56dcdb68b31aa8c71404585a886cfcc978e08be8f64c6c3ce8438044013ca",
805        "f4c9a1a92630aa75afd8b8dbcaafdc212ffb2f34b69a7bdb2f40609aa332236d",
806        "b932d9bc11b9f21ab792e3b5dff181a56cc9eeab2f3ee7afe4d3c82317fe3b9e",
807        "f78f6c3055d0c1c49fe4303a4e97de9e85107d084a542e15d3a1f59d068d48cf",
808        "aed078316e0c3c4624d12b253adc31114011bdc8550b3cf9aa7a3ae3528478ae",
809        "67879ad6b94d3e536c41abcd2719df496d990e360e3cd1bf6168ad34681c9b7e",
810        "3d9c7c5590c129b3ac13384367c823d2bf4fe8b681d617b3b5d627494897753a",
811        "c5b437bb860c077c0a42eaf4574418da19681dcd8bae66f39d64c28488d73715",
812        "c3a56646dde6bef7edbd352447a84d11887f90e6c701ba3f416657c2266e7dc0",
813        "8d2540362789502dfb5a288bc65ac890265a214a0cda02f5ceaccb469b0cc137",
814        "2e45352b458f89889bada37cf933852d182a7824113b025b88b6a85cb269c6aa",
815        "6fc01506749124063a43a2120245bf3b1c5aea36f3d59bc39dc51e057e75f71f",
816        "588efc61ec42e19f898bd5d958a7365c4c3baf8038a64a1460806f3cdc21948f",
817        "808d865fc016720e9bf61a0d5eaa015f6f187d41d7633845c92c6cacdfe613c9",
818        "e6a1d190049b0c050e189d26c00f96e2235eb8bcb196aca24fdc62fd0ecb9eae",
819        "1a306d0a919c071c844e7bba1c052090637ede6b61cc4683f0f4b2c461eecdb8",
820        "4e45867c281c31ee45c7fca4a8360deba83194d8e564ee67f3bf93ed3957bec7",
821        "bf6327fddf29b861a04f968dc5774cfef7b3e10eb1f245e5efa8fd83fafa2bf1",
822        "3e45cc36fbaf609569d86d61b35149cdb76ad98f89ece8346f3a37a3c1719cf4",
823        "880158cad3643cf9a0edb91393c32054ddbc1f246e033ce487c8eb4d107c1194",
824        "bb0df4b7018c0263acab38f3b17f39b275825c0f68d4433309723398933b8da7",
825        "d7e391633d0961dd8a570346483012a0b6f63e00d246111fa34f2ccc47fb8703",
826        "8200353a6675b2cf6f8d582522f4b5a3631c7d63e1c2241f11663349e76462f3",
827        "fac2e4190f279be818ea9aa3480dc4a1e3cbcf7f0882f8e31c2157ef0508e90f",
828        "17749a05e9cae5177d8e0faba46da779823d3e8d86ef5ed79b54d78135bb7223",
829        "87028314fdab0aa49907b7ce8b8f3908907295d7e0c0b6bae2fe9b5ba5c0ceb4",
830        "167183adfd0b5e5969f45cfc8ff6540e15ead0fdcd6c9dfc298d630759d189be",
831        "537a57b808d97bd0bd43c44ed409c104453422052e55d6b5ff6c2f0e094e8be7",
832        "91f9ca4ece65c41449b62d0bfc3b3394bd748bb084b8821e4c022a7eece1c612",
833        "bbe7726fdfcf0ff06ec19af865ca1f63aa04c17ed76b61048d146a35790ad9bf",
834        "e80cd26d4b358842e76d45a4e5560ec8998fcff4675a526d940739338bf427a7",
835        "165b46546b409202ee4b213ee9cc36b4e401d90a726a9976c45b9c448df4b8ea",
836        "fdd9b0055a0d85ae21f227a875ac22cef20592fba24cebc306cf401ab8d61fab",
837        "a7df94accafd8e8cfc78996cb98b25dc2cf28b3eb4983106b50e359b81040eb5",
838    ];
839
840    #[test]
841    fn test_merkle_trees() {
842        for (n, previous) in ROOTS.into_iter().enumerate() {
843            let root = test_merkle_tree(n);
844            assert_eq!(hex(&root), previous);
845        }
846    }
847
848    #[test]
849    fn test_tampered_proof_no_siblings() {
850        // Create transactions and digests
851        let txs = [b"tx1", b"tx2", b"tx3", b"tx4"];
852        let digests: Vec<Digest> = txs.iter().map(|tx| Sha256::hash(*tx)).collect();
853        let element = &digests[0];
854
855        // Build tree
856        let mut builder = Builder::new(txs.len());
857        for digest in &digests {
858            builder.add(digest);
859        }
860        let tree = builder.build();
861        let root = tree.root();
862
863        // Build proof
864        let mut proof = tree.proof(0).unwrap();
865
866        // Tamper with proof
867        proof.siblings = Vec::new();
868
869        // Fail verification with an empty proof.
870        let mut hasher = Sha256::default();
871        assert!(proof.verify(&mut hasher, element, 0, &root).is_err());
872    }
873
874    #[test]
875    fn test_tampered_proof_extra_sibling() {
876        // Create transactions and digests
877        let txs = [b"tx1", b"tx2", b"tx3", b"tx4"];
878        let digests: Vec<Digest> = txs.iter().map(|tx| Sha256::hash(*tx)).collect();
879        let element = &digests[0];
880
881        // Build tree
882        let mut builder = Builder::new(txs.len());
883        for digest in &digests {
884            builder.add(digest);
885        }
886        let tree = builder.build();
887        let root = tree.root();
888
889        // Build proof
890        let mut proof = tree.proof(0).unwrap();
891
892        // Tamper with proof
893        proof.siblings.push(*element);
894
895        // Fail verification with an empty proof.
896        let mut hasher = Sha256::default();
897        assert!(proof.verify(&mut hasher, element, 0, &root).is_err());
898    }
899
900    #[test]
901    fn test_invalid_proof_wrong_element() {
902        // Create transactions and digests
903        let txs = [b"tx1", b"tx2", b"tx3", b"tx4"];
904        let digests: Vec<Digest> = txs.iter().map(|tx| Sha256::hash(*tx)).collect();
905
906        // Build tree
907        let mut builder = Builder::new(txs.len());
908        for digest in &digests {
909            builder.add(digest);
910        }
911        let tree = builder.build();
912        let root = tree.root();
913
914        // Generate a valid proof for leaf at index 2.
915        let proof = tree.proof(2).unwrap();
916
917        // Use a wrong element (e.g. hash of a different transaction).
918        let mut hasher = Sha256::default();
919        let wrong_leaf = Sha256::hash(b"wrong_tx");
920        assert!(proof.verify(&mut hasher, &wrong_leaf, 2, &root).is_err());
921    }
922
923    #[test]
924    fn test_invalid_proof_wrong_index() {
925        // Create transactions and digests
926        let txs = [b"tx1", b"tx2", b"tx3", b"tx4"];
927        let digests: Vec<Digest> = txs.iter().map(|tx| Sha256::hash(*tx)).collect();
928
929        // Build tree
930        let mut builder = Builder::new(txs.len());
931        for digest in &digests {
932            builder.add(digest);
933        }
934        let tree = builder.build();
935        let root = tree.root();
936
937        // Generate a valid proof for leaf at index 1.
938        let proof = tree.proof(1).unwrap();
939
940        // Use an incorrect index (e.g. 2 instead of 1).
941        let mut hasher = Sha256::default();
942        assert!(proof.verify(&mut hasher, &digests[1], 2, &root).is_err());
943    }
944
945    #[test]
946    fn test_invalid_proof_wrong_root() {
947        // Create transactions and digests
948        let txs = [b"tx1", b"tx2", b"tx3", b"tx4"];
949        let digests: Vec<Digest> = txs.iter().map(|tx| Sha256::hash(*tx)).collect();
950
951        // Build tree
952        let mut builder = Builder::new(txs.len());
953        for digest in &digests {
954            builder.add(digest);
955        }
956        let tree = builder.build();
957
958        // Generate a valid proof for leaf at index 0.
959        let proof = tree.proof(0).unwrap();
960
961        // Use a wrong root (hash of a different input).
962        let mut hasher = Sha256::default();
963        let wrong_root = Sha256::hash(b"wrong_root");
964        assert!(proof
965            .verify(&mut hasher, &digests[0], 0, &wrong_root)
966            .is_err());
967    }
968
969    #[test]
970    fn test_invalid_proof_serialization_truncated() {
971        // Create transactions and digests
972        let txs = [b"tx1", b"tx2", b"tx3"];
973        let digests: Vec<Digest> = txs.iter().map(|tx| Sha256::hash(*tx)).collect();
974
975        // Build tree
976        let mut builder = Builder::<Sha256>::new(txs.len());
977        for digest in &digests {
978            builder.add(digest);
979        }
980        let tree = builder.build();
981
982        // Generate a valid proof for leaf at index 1.
983        let proof = tree.proof(1).unwrap();
984        let mut serialized = proof.encode();
985
986        // Truncate one byte.
987        serialized.truncate(serialized.len() - 1);
988        assert!(Proof::<Sha256>::decode(&mut serialized).is_err());
989    }
990
991    #[test]
992    fn test_invalid_proof_serialization_extra() {
993        // Create transactions and digests
994        let txs = [b"tx1", b"tx2", b"tx3"];
995        let digests: Vec<Digest> = txs.iter().map(|tx| Sha256::hash(*tx)).collect();
996
997        // Build tree
998        let mut builder = Builder::<Sha256>::new(txs.len());
999        for digest in &digests {
1000            builder.add(digest);
1001        }
1002        let tree = builder.build();
1003
1004        // Generate a valid proof for leaf at index 1.
1005        let proof = tree.proof(1).unwrap();
1006        let mut serialized = proof.encode();
1007
1008        // Append an extra byte.
1009        serialized.extend_from_slice(&[0u8]);
1010        assert!(Proof::<Sha256>::decode(&mut serialized).is_err());
1011    }
1012
1013    #[test]
1014    fn test_invalid_proof_modified_hash() {
1015        // Create transactions and digests
1016        let txs = [b"tx1", b"tx2", b"tx3", b"tx4"];
1017        let digests: Vec<Digest> = txs.iter().map(|tx| Sha256::hash(*tx)).collect();
1018
1019        // Build tree
1020        let mut builder = Builder::new(txs.len());
1021        for digest in &digests {
1022            builder.add(digest);
1023        }
1024        let tree = builder.build();
1025        let root = tree.root();
1026
1027        // Generate a valid proof for leaf at index 2.
1028        let mut proof = tree.proof(2).unwrap();
1029
1030        // Modify the first hash in the proof.
1031        let mut hasher = Sha256::default();
1032        proof.siblings[0] = Sha256::hash(b"modified");
1033        assert!(proof.verify(&mut hasher, &digests[2], 2, &root).is_err());
1034    }
1035
1036    #[test]
1037    fn test_odd_tree_duplicate_index_proof() {
1038        // Create transactions and digests
1039        let txs = [b"tx1", b"tx2", b"tx3"];
1040        let digests: Vec<Digest> = txs.iter().map(|tx| Sha256::hash(*tx)).collect();
1041
1042        // Build tree
1043        let mut builder = Builder::new(txs.len());
1044        for digest in &digests {
1045            builder.add(digest);
1046        }
1047        let tree = builder.build();
1048        let root = tree.root();
1049
1050        // The tree was built with 3 leaves; index 2 is the last valid index.
1051        let proof = tree.proof(2).unwrap();
1052
1053        // Verification should succeed for the proper index 2.
1054        let mut hasher = Sha256::default();
1055        assert!(proof.verify(&mut hasher, &digests[2], 2, &root).is_ok());
1056
1057        // Should not be able to generate a proof for an out-of-range index (e.g. 3).
1058        assert!(tree.proof(3).is_err());
1059
1060        // Attempting to verify using an out-of-range index (e.g. 3, which would correspond
1061        // to a duplicate leaf that doesn't actually exist) should fail.
1062        assert!(proof.verify(&mut hasher, &digests[2], 3, &root).is_err());
1063    }
1064
1065    #[test]
1066    fn test_range_proof_basic() {
1067        // Create test data
1068        let digests: Vec<Digest> = (0..8u32).map(|i| Sha256::hash(&i.to_be_bytes())).collect();
1069
1070        // Build tree
1071        let mut builder = Builder::<Sha256>::new(digests.len());
1072        for digest in &digests {
1073            builder.add(digest);
1074        }
1075        let tree = builder.build();
1076        let root = tree.root();
1077
1078        // Test range proof for elements 2-5
1079        let range_proof = tree.range_proof(2, 5).unwrap();
1080        let mut hasher = Sha256::default();
1081        let range_leaves = &digests[2..6];
1082
1083        assert!(range_proof
1084            .verify(&mut hasher, 2, range_leaves, &root)
1085            .is_ok());
1086
1087        // Serialize and deserialize
1088        let mut serialized = range_proof.encode();
1089        let deserialized = RangeProof::<Sha256>::decode(&mut serialized).unwrap();
1090        assert!(deserialized
1091            .verify(&mut hasher, 2, range_leaves, &root)
1092            .is_ok());
1093    }
1094
1095    #[test]
1096    fn test_range_proof_single_element() {
1097        // Create test data
1098        let digests: Vec<Digest> = (0..8u32).map(|i| Sha256::hash(&i.to_be_bytes())).collect();
1099
1100        // Build tree
1101        let mut builder = Builder::<Sha256>::new(digests.len());
1102        for digest in &digests {
1103            builder.add(digest);
1104        }
1105        let tree = builder.build();
1106        let root = tree.root();
1107
1108        // Test single element range proof
1109        for (i, digest) in digests.iter().enumerate() {
1110            let range_proof = tree.range_proof(i as u32, i as u32).unwrap();
1111            let mut hasher = Sha256::default();
1112
1113            let result = range_proof.verify(&mut hasher, i as u32, &[*digest], &root);
1114            assert!(result.is_ok());
1115        }
1116    }
1117
1118    #[test]
1119    fn test_range_proof_full_tree() {
1120        // Create test data
1121        let digests: Vec<Digest> = (0..7u32).map(|i| Sha256::hash(&i.to_be_bytes())).collect();
1122
1123        // Build tree
1124        let mut builder = Builder::<Sha256>::new(digests.len());
1125        for digest in &digests {
1126            builder.add(digest);
1127        }
1128        let tree = builder.build();
1129        let root = tree.root();
1130
1131        // Test full tree range proof
1132        let range_proof = tree.range_proof(0, (digests.len() - 1) as u32).unwrap();
1133        let mut hasher = Sha256::default();
1134        assert!(range_proof.verify(&mut hasher, 0, &digests, &root).is_ok());
1135    }
1136
1137    #[test]
1138    fn test_range_proof_edge_cases() {
1139        // Create test data
1140        let digests: Vec<Digest> = (0..15u32).map(|i| Sha256::hash(&i.to_be_bytes())).collect();
1141
1142        // Build tree
1143        let mut builder = Builder::<Sha256>::new(digests.len());
1144        for digest in &digests {
1145            builder.add(digest);
1146        }
1147        let tree = builder.build();
1148        let root = tree.root();
1149        let mut hasher = Sha256::default();
1150
1151        // Test first half
1152        let range_proof = tree.range_proof(0, 7).unwrap();
1153        assert!(range_proof
1154            .verify(&mut hasher, 0, &digests[0..8], &root)
1155            .is_ok());
1156
1157        // Test second half
1158        let range_proof = tree.range_proof(8, 14).unwrap();
1159        assert!(range_proof
1160            .verify(&mut hasher, 8, &digests[8..15], &root)
1161            .is_ok());
1162
1163        // Test last elements
1164        let range_proof = tree.range_proof(13, 14).unwrap();
1165        assert!(range_proof
1166            .verify(&mut hasher, 13, &digests[13..15], &root)
1167            .is_ok());
1168    }
1169
1170    #[test]
1171    fn test_range_proof_invalid_range() {
1172        // Create test data
1173        let digests: Vec<Digest> = (0..8u32).map(|i| Sha256::hash(&i.to_be_bytes())).collect();
1174
1175        // Build tree
1176        let mut builder = Builder::<Sha256>::new(digests.len());
1177        for digest in &digests {
1178            builder.add(digest);
1179        }
1180        let tree = builder.build();
1181
1182        // Test invalid ranges
1183        assert!(tree.range_proof(8, 8).is_err()); // Start out of bounds
1184        assert!(tree.range_proof(0, 8).is_err()); // End out of bounds
1185        assert!(tree.range_proof(5, 8).is_err()); // End out of bounds
1186        assert!(tree.range_proof(2, 1).is_err()); // Start > end
1187    }
1188
1189    #[test]
1190    fn test_range_proof_tampering() {
1191        // Create test data
1192        let digests: Vec<Digest> = (0..8u32).map(|i| Sha256::hash(&i.to_be_bytes())).collect();
1193
1194        // Build tree
1195        let mut builder = Builder::<Sha256>::new(digests.len());
1196        for digest in &digests {
1197            builder.add(digest);
1198        }
1199        let tree = builder.build();
1200        let root = tree.root();
1201
1202        // Get valid range proof
1203        let range_proof = tree.range_proof(2, 4).unwrap();
1204        let mut hasher = Sha256::default();
1205        let range_leaves = &digests[2..5];
1206
1207        // Test with wrong leaves
1208        let wrong_leaves = vec![
1209            Sha256::hash(b"wrong1"),
1210            Sha256::hash(b"wrong2"),
1211            Sha256::hash(b"wrong3"),
1212        ];
1213        assert!(range_proof
1214            .verify(&mut hasher, 2, &wrong_leaves, &root)
1215            .is_err());
1216
1217        // Test with wrong number of leaves
1218        assert!(range_proof
1219            .verify(&mut hasher, 2, &digests[2..4], &root)
1220            .is_err());
1221
1222        // Test with tampered proof
1223        let mut tampered_proof = range_proof.clone();
1224        assert!(!tampered_proof.siblings.is_empty());
1225        // Tamper with the first level's left sibling if it exists
1226        if let Some(ref mut left) = tampered_proof.siblings[0].left {
1227            *left = Sha256::hash(b"tampered");
1228        } else if let Some(ref mut right) = tampered_proof.siblings[0].right {
1229            *right = Sha256::hash(b"tampered");
1230        }
1231        assert!(tampered_proof
1232            .verify(&mut hasher, 2, range_leaves, &root)
1233            .is_err());
1234
1235        // Test with wrong root
1236        let wrong_root = Sha256::hash(b"wrong_root");
1237        assert!(range_proof
1238            .verify(&mut hasher, 2, range_leaves, &wrong_root)
1239            .is_err());
1240    }
1241
1242    #[test]
1243    fn test_range_proof_various_sizes() {
1244        // Test range proofs for trees of various sizes
1245        for tree_size in [1, 2, 3, 4, 5, 7, 8, 15, 16, 31, 32, 63, 64] {
1246            let digests: Vec<Digest> = (0..tree_size as u32)
1247                .map(|i| Sha256::hash(&i.to_be_bytes()))
1248                .collect();
1249
1250            // Build tree
1251            let mut builder = Builder::<Sha256>::new(digests.len());
1252            for digest in &digests {
1253                builder.add(digest);
1254            }
1255            let tree = builder.build();
1256            let root = tree.root();
1257            let mut hasher = Sha256::default();
1258
1259            // Test various range sizes
1260            for range_size in 1..=tree_size.min(8) {
1261                for start in 0..=(tree_size - range_size) {
1262                    let range_proof = tree
1263                        .range_proof(start as u32, (start + range_size - 1) as u32)
1264                        .unwrap();
1265                    let end = start + range_size;
1266                    assert!(
1267                        range_proof
1268                            .verify(&mut hasher, start as u32, &digests[start..end], &root)
1269                            .is_ok(),
1270                        "Failed for tree_size={tree_size}, start={start}, range_size={range_size}"
1271                    );
1272                }
1273            }
1274        }
1275    }
1276
1277    #[test]
1278    fn test_range_proof_malicious_wrong_position() {
1279        // Create test data
1280        let digests: Vec<Digest> = (0..8u32).map(|i| Sha256::hash(&i.to_be_bytes())).collect();
1281
1282        // Build tree
1283        let mut builder = Builder::<Sha256>::new(digests.len());
1284        for digest in &digests {
1285            builder.add(digest);
1286        }
1287        let tree = builder.build();
1288        let root = tree.root();
1289
1290        // Get valid range proof for position 2 to 4
1291        let range_proof = tree.range_proof(2, 4).unwrap();
1292        let mut hasher = Sha256::default();
1293        let range_leaves = &digests[2..5];
1294
1295        // Try to verify with wrong position
1296        assert!(range_proof
1297            .verify(&mut hasher, 3, range_leaves, &root)
1298            .is_err());
1299        assert!(range_proof
1300            .verify(&mut hasher, 1, range_leaves, &root)
1301            .is_err());
1302    }
1303
1304    #[test]
1305    fn test_range_proof_malicious_reordered_leaves() {
1306        // Create test data
1307        let digests: Vec<Digest> = (0..8u32).map(|i| Sha256::hash(&i.to_be_bytes())).collect();
1308
1309        // Build tree
1310        let mut builder = Builder::<Sha256>::new(digests.len());
1311        for digest in &digests {
1312            builder.add(digest);
1313        }
1314        let tree = builder.build();
1315        let root = tree.root();
1316
1317        // Get valid range proof for position 2 to 4
1318        let range_proof = tree.range_proof(2, 4).unwrap();
1319        let mut hasher = Sha256::default();
1320
1321        // Try to verify with reordered leaves
1322        let reordered_leaves = vec![digests[3], digests[2], digests[4]];
1323        assert!(range_proof
1324            .verify(&mut hasher, 2, &reordered_leaves, &root)
1325            .is_err());
1326    }
1327
1328    #[test]
1329    fn test_range_proof_malicious_extra_siblings() {
1330        // Create test data
1331        let digests: Vec<Digest> = (0..8u32).map(|i| Sha256::hash(&i.to_be_bytes())).collect();
1332
1333        // Build tree
1334        let mut builder = Builder::<Sha256>::new(digests.len());
1335        for digest in &digests {
1336            builder.add(digest);
1337        }
1338        let tree = builder.build();
1339        let root = tree.root();
1340
1341        // Get valid range proof
1342        let mut range_proof = tree.range_proof(2, 3).unwrap();
1343        let mut hasher = Sha256::default();
1344        let range_leaves = &digests[2..4];
1345
1346        // Tamper by setting both siblings when there should only be one or two
1347        assert!(!range_proof.siblings.is_empty());
1348        // Force an invalid state by modifying the siblings
1349        if range_proof.siblings[0].left.is_none() {
1350            range_proof.siblings[0].left = Some(Sha256::hash(b"extra"));
1351        } else if range_proof.siblings[0].right.is_none() {
1352            range_proof.siblings[0].right = Some(Sha256::hash(b"extra"));
1353        }
1354        assert!(range_proof
1355            .verify(&mut hasher, 2, range_leaves, &root)
1356            .is_err());
1357    }
1358
1359    #[test]
1360    fn test_range_proof_malicious_missing_siblings() {
1361        // Create test data
1362        let digests: Vec<Digest> = (0..8u32).map(|i| Sha256::hash(&i.to_be_bytes())).collect();
1363
1364        // Build tree
1365        let mut builder = Builder::<Sha256>::new(digests.len());
1366        for digest in &digests {
1367            builder.add(digest);
1368        }
1369        let tree = builder.build();
1370        let root = tree.root();
1371
1372        // Get valid range proof for a single element (which needs siblings)
1373        let mut range_proof = tree.range_proof(2, 2).unwrap();
1374        let mut hasher = Sha256::default();
1375        let range_leaves = &digests[2..3];
1376
1377        // The proof should have siblings at the first level
1378        assert!(!range_proof.siblings.is_empty());
1379        assert!(range_proof.siblings[0].left.is_some() || range_proof.siblings[0].right.is_some());
1380
1381        // Remove a sibling from a level
1382        range_proof.siblings[0].left = None;
1383        range_proof.siblings[0].right = None;
1384        assert!(range_proof
1385            .verify(&mut hasher, 2, range_leaves, &root)
1386            .is_err());
1387    }
1388
1389    #[test]
1390    fn test_range_proof_integer_overflow_protection() {
1391        // Create test data
1392        let digests: Vec<Digest> = (0..8u32).map(|i| Sha256::hash(&i.to_be_bytes())).collect();
1393
1394        // Build tree
1395        let mut builder = Builder::<Sha256>::new(digests.len());
1396        for digest in &digests {
1397            builder.add(digest);
1398        }
1399        let tree = builder.build();
1400
1401        // Test overflow in range_proof generation
1402        assert!(tree.range_proof(u32::MAX, u32::MAX).is_err());
1403        assert!(tree.range_proof(u32::MAX - 1, u32::MAX).is_err());
1404        assert!(tree.range_proof(7, u32::MAX).is_err());
1405    }
1406
1407    #[test]
1408    fn test_range_proof_malicious_wrong_tree_structure() {
1409        // Create test data
1410        let digests: Vec<Digest> = (0..8u32).map(|i| Sha256::hash(&i.to_be_bytes())).collect();
1411
1412        // Build tree
1413        let mut builder = Builder::<Sha256>::new(digests.len());
1414        for digest in &digests {
1415            builder.add(digest);
1416        }
1417        let tree = builder.build();
1418        let root = tree.root();
1419
1420        // Get valid range proof
1421        let mut range_proof = tree.range_proof(2, 3).unwrap();
1422        let mut hasher = Sha256::default();
1423        let range_leaves = &digests[2..4];
1424
1425        // Add extra level (simulating proof from different tree structure)
1426        range_proof.siblings.push(Bounds {
1427            left: Some(Sha256::hash(b"fake_level")),
1428            right: None,
1429        });
1430        assert!(range_proof
1431            .verify(&mut hasher, 2, range_leaves, &root)
1432            .is_err());
1433
1434        // Remove a level
1435        let mut range_proof = tree.range_proof(2, 2).unwrap();
1436        assert!(!range_proof.siblings.is_empty());
1437        range_proof.siblings.pop();
1438        assert!(range_proof
1439            .verify(&mut hasher, 2, range_leaves, &root)
1440            .is_err());
1441    }
1442
1443    #[test]
1444    fn test_range_proof_boundary_conditions() {
1445        // Test various power-of-2 boundary conditions
1446        for tree_size in [1, 2, 4, 8, 16, 32] {
1447            let digests: Vec<Digest> = (0..tree_size as u32)
1448                .map(|i| Sha256::hash(&i.to_be_bytes()))
1449                .collect();
1450
1451            // Build tree
1452            let mut builder = Builder::<Sha256>::new(digests.len());
1453            for digest in &digests {
1454                builder.add(digest);
1455            }
1456            let tree = builder.build();
1457            let root = tree.root();
1458            let mut hasher = Sha256::default();
1459
1460            // Test edge cases
1461            // First element only
1462            let proof = tree.range_proof(0, 0).unwrap();
1463            assert!(proof.verify(&mut hasher, 0, &digests[0..1], &root).is_ok());
1464
1465            // Last element only
1466            let last_idx = tree_size - 1;
1467            let proof = tree.range_proof(last_idx as u32, last_idx as u32).unwrap();
1468            assert!(proof
1469                .verify(
1470                    &mut hasher,
1471                    last_idx as u32,
1472                    &digests[last_idx..tree_size],
1473                    &root
1474                )
1475                .is_ok());
1476
1477            // Full tree
1478            let proof = tree.range_proof(0, (tree_size - 1) as u32).unwrap();
1479            assert!(proof.verify(&mut hasher, 0, &digests, &root).is_ok());
1480        }
1481    }
1482
1483    #[test]
1484    fn test_empty_tree_proof() {
1485        // Build an empty tree
1486        let builder = Builder::<Sha256>::new(0);
1487        let tree = builder.build();
1488
1489        // Empty tree should fail for any position since there are no elements
1490        assert!(tree.proof(0).is_err());
1491        assert!(tree.proof(1).is_err());
1492        assert!(tree.proof(100).is_err());
1493    }
1494
1495    #[test]
1496    fn test_empty_tree_range_proof() {
1497        // Build an empty tree
1498        let builder = Builder::<Sha256>::new(0);
1499        let tree = builder.build();
1500        let root = tree.root();
1501
1502        // Empty tree should return default range proof only for (0, 0)
1503        let range_proof = tree.range_proof(0, 0).unwrap();
1504        assert!(range_proof.siblings.is_empty());
1505        assert_eq!(range_proof, RangeProof::default());
1506
1507        // All other combinations should fail
1508        let invalid_ranges = vec![
1509            (0, 1),
1510            (0, 10),
1511            (1, 1),
1512            (1, 2),
1513            (5, 5),
1514            (10, 10),
1515            (0, u32::MAX),
1516            (u32::MAX, u32::MAX),
1517        ];
1518        for (start, end) in invalid_ranges {
1519            assert!(tree.range_proof(start, end).is_err());
1520        }
1521
1522        // Verify empty range proof against empty tree root
1523        let mut hasher = Sha256::default();
1524        let empty_leaves: &[Digest] = &[];
1525        assert!(range_proof
1526            .verify(&mut hasher, 0, empty_leaves, &root)
1527            .is_ok());
1528
1529        // Should fail with non-empty leaves
1530        let non_empty_leaves = vec![Sha256::hash(b"leaf")];
1531        assert!(range_proof
1532            .verify(&mut hasher, 0, &non_empty_leaves, &root)
1533            .is_err());
1534
1535        // Should fail with wrong root
1536        let wrong_root = Sha256::hash(b"wrong");
1537        assert!(range_proof
1538            .verify(&mut hasher, 0, empty_leaves, &wrong_root)
1539            .is_err());
1540
1541        // Should fail with wrong position
1542        assert!(range_proof
1543            .verify(&mut hasher, 1, empty_leaves, &root)
1544            .is_err());
1545    }
1546
1547    #[test]
1548    fn test_empty_range_proof_serialization() {
1549        let range_proof = RangeProof::<Sha256>::default();
1550        let mut serialized = range_proof.encode();
1551        let deserialized = RangeProof::<Sha256>::decode(&mut serialized).unwrap();
1552        assert_eq!(range_proof, deserialized);
1553    }
1554
1555    #[test]
1556    fn test_empty_tree_root_consistency() {
1557        // Create multiple empty trees and verify they have the same root
1558        let mut roots = Vec::new();
1559        for _ in 0..5 {
1560            let builder = Builder::<Sha256>::new(0);
1561            let tree = builder.build();
1562            roots.push(tree.root());
1563        }
1564
1565        // All empty trees should have the same root
1566        for i in 1..roots.len() {
1567            assert_eq!(roots[0], roots[i]);
1568        }
1569
1570        // The root should be the hash of empty data
1571        let mut hasher = Sha256::default();
1572        let expected_root = hasher.finalize();
1573        assert_eq!(roots[0], expected_root);
1574    }
1575
1576    #[test]
1577    fn test_range_proof_bounds_usage() {
1578        // This test ensures that all bounds in a range proof are actually used during verification
1579        // and that we don't have unnecessary siblings
1580        let digests: Vec<Digest> = (0..16u32).map(|i| Sha256::hash(&i.to_be_bytes())).collect();
1581
1582        // Build tree
1583        let mut builder = Builder::<Sha256>::new(digests.len());
1584        for digest in &digests {
1585            builder.add(digest);
1586        }
1587        let tree = builder.build();
1588        let root = tree.root();
1589        let mut hasher = Sha256::default();
1590
1591        // Test various ranges
1592        let test_cases = vec![
1593            (1, 2),  // Range starting at odd index (needs left sibling)
1594            (4, 4),  // Range starting at even index ending at odd (needs right sibling)
1595            (3, 6),  // Range with both boundaries needing siblings
1596            (0, 16), // Full tree (no siblings needed at leaf level)
1597        ];
1598
1599        for (start, count) in test_cases {
1600            let range_proof = tree.range_proof(start, start + count - 1).unwrap();
1601            let end = start as usize + count as usize;
1602
1603            // Verify the proof works
1604            assert!(range_proof
1605                .verify(&mut hasher, start, &digests[start as usize..end], &root)
1606                .is_ok());
1607
1608            // For each level with siblings, try removing them and verify the proof fails
1609            for level_idx in 0..range_proof.siblings.len() {
1610                let bounds = &range_proof.siblings[level_idx];
1611
1612                // If there's a left sibling, removing it should make the proof fail
1613                if bounds.left.is_some() {
1614                    let mut tampered_proof = range_proof.clone();
1615                    tampered_proof.siblings[level_idx].left = None;
1616                    assert!(tampered_proof
1617                        .verify(&mut hasher, start, &digests[start as usize..end], &root)
1618                        .is_err());
1619                }
1620
1621                // If there's a right sibling, removing it should make the proof fail
1622                if bounds.right.is_some() {
1623                    let mut tampered_proof = range_proof.clone();
1624                    tampered_proof.siblings[level_idx].right = None;
1625                    assert!(tampered_proof
1626                        .verify(&mut hasher, start, &digests[start as usize..end], &root)
1627                        .is_err());
1628                }
1629
1630                // If there's no left sibling, adding one should make the proof fail
1631                if bounds.left.is_none() {
1632                    let mut tampered_proof = range_proof.clone();
1633                    tampered_proof.siblings[level_idx].left = Some(Sha256::hash(b"fake_left"));
1634                    assert!(tampered_proof
1635                        .verify(&mut hasher, start, &digests[start as usize..end], &root)
1636                        .is_err());
1637                }
1638
1639                // If there's no right sibling, adding one should make the proof fail
1640                if bounds.right.is_none() {
1641                    let mut tampered_proof = range_proof.clone();
1642                    tampered_proof.siblings[level_idx].right = Some(Sha256::hash(b"fake_right"));
1643                    assert!(tampered_proof
1644                        .verify(&mut hasher, start, &digests[start as usize..end], &root)
1645                        .is_err());
1646                }
1647            }
1648        }
1649    }
1650
1651    #[test]
1652    fn test_range_proof_duplicate_node_edge_cases() {
1653        // Test trees with odd sizes that require duplicate nodes
1654        for tree_size in [3, 5, 7, 9, 11, 13, 15] {
1655            let digests: Vec<Digest> = (0..tree_size as u32)
1656                .map(|i| Sha256::hash(&i.to_be_bytes()))
1657                .collect();
1658
1659            // Build tree
1660            let mut builder = Builder::<Sha256>::new(digests.len());
1661            for digest in &digests {
1662                builder.add(digest);
1663            }
1664            let tree = builder.build();
1665            let root = tree.root();
1666            let mut hasher = Sha256::default();
1667
1668            // Test range including the last element (which may require duplicate handling)
1669            let start = tree_size - 2;
1670            let proof = tree
1671                .range_proof(start as u32, (tree_size - 1) as u32)
1672                .unwrap();
1673            assert!(proof
1674                .verify(&mut hasher, start as u32, &digests[start..tree_size], &root)
1675                .is_ok());
1676        }
1677    }
1678}
commonware_storage/bmt/mod.rs

commonware_storage/bmt/
mod.rs
