commonware_storage/bmt/

mod.rs

//! Stateless Binary Merkle Tree (BMT).
//!
//! The Binary Merkle Tree is constructed level-by-level. The first level consists of position-hashed leaf digests.
//! On each additional level, pairs of nodes are hashed from the previous level (if a level contains an odd
//! number of nodes, the last node is duplicated). The finalized root of the tree incorporates the leaf count
//! to prevent proof malleability: `root = hash(leaf_count || tree_root)`.
//!
//! For example, given three leaves A, B, and C, the tree is constructed as follows:
//!
//! ```text
//!     Level 2 (tree_root):  [hash(hash(hash(0,A),hash(1,B)),hash(hash(2,C),hash(2,C)))]
//!     Level 1:              [hash(hash(0,A),hash(1,B)),hash(hash(2,C),hash(2,C))]
//!     Level 0 (leaves):     [hash(0,A),hash(1,B),hash(2,C)]
//!     Finalized root:       hash(3 || tree_root)
//! ```
//!
//! A proof for one or more leaves is generated by collecting the siblings needed to reconstruct the root.
//! An external process can then use this proof (with some trusted root) to verify that the leaves
//! are part of the tree.
//!
//! # Example
//!
//! ```rust
//! use commonware_storage::bmt::{Builder, Tree};
//! use commonware_cryptography::{Sha256, sha256::Digest, Hasher as _};
//!
//! // Create transactions and compute their digests
//! let txs = [b"tx1", b"tx2", b"tx3", b"tx4"];
//! let digests: Vec<Digest> = txs.iter().map(|tx| Sha256::hash(&[*tx])).collect();
//!
//! // Build a Merkle Tree from the digests
//! let mut builder = Builder::<Sha256>::new(digests.len());
//! for digest in &digests {
//!    builder.add(digest);
//! }
//! let tree = builder.build();
//! let root = tree.root();
//!
//! // Generate a proof for leaf at index 1
//! let proof = tree.proof(1).unwrap();
//! assert!(proof.verify_element_inclusion::<Sha256>(&digests[1], 1, &root).is_ok());
//! ```

use alloc::{
    string::{String, ToString},
    vec,
    vec::Vec,
};
use bytes::BufMut;
use commonware_codec::{
    Buf, EncodeSize, FixedSize, Read, ReadExt, ReadRangeExt, Write, util::max_items_size,
};
use commonware_cryptography::{Digest, Hasher};
use commonware_parallel::Sequential;
use commonware_utils::{non_empty_vec, vec::NonEmptyVec};
use thiserror::Error;

/// There should never be more than 32 sibling levels in a proof. Because
/// [Proof::leaf_count] is a `u32`, a tree can have at most `u32::MAX` leaves,
/// which requires at most `u32::BITS` sibling hashes per proven item.
pub const MAX_LEVELS: usize = u32::BITS as usize;

/// Errors that can occur when working with a Binary Merkle Tree (BMT).
#[derive(Error, Debug)]
pub enum Error {
    #[error("invalid position: {0}")]
    InvalidPosition(u32),
    #[error("invalid proof: {0} != {1}")]
    InvalidProof(String, String),
    #[error("no leaves")]
    NoLeaves,
    #[error("unaligned proof")]
    UnalignedProof,
    #[error("duplicate position: {0}")]
    DuplicatePosition(u32),
    #[error("unsorted position: {0}")]
    UnsortedPosition(u32),
}

/// Constructor for a Binary Merkle Tree (BMT).
pub struct Builder<H: Hasher> {
    leaves: Vec<H::Digest>,
}

impl<H: Hasher> Builder<H> {
    /// Creates a new Binary Merkle Tree builder.
    pub fn new(leaves: usize) -> Self {
        Self {
            leaves: Vec::with_capacity(leaves),
        }
    }

    /// Adds a leaf to the Binary Merkle Tree.
    ///
    /// When added, the leaf is hashed with its position.
    ///
    /// # Panics
    ///
    /// Panics if the tree already has `u32::MAX` leaves.
    pub fn add(&mut self, leaf: &H::Digest) -> u32 {
        // The count after this add must fit in Proof::leaf_count, a u32, so the
        // maximum position is u32::MAX - 1.
        let position: u32 = self.leaves.len().try_into().expect("too many leaves");
        assert!(position < u32::MAX, "too many leaves");

        let digest = H::hash(&[&position.to_be_bytes(), leaf.as_ref()]);
        self.leaves.push(digest);
        position
    }

    /// Builds the Binary Merkle Tree.
    ///
    /// It is valid to build a tree with no leaves, in which case
    /// just an "empty" node is included (no leaves will be provable).
    pub fn build(self) -> Tree<H::Digest> {
        Tree::new::<H>(self.leaves)
    }
}

/// Constructed Binary Merkle Tree (BMT).
#[derive(Clone, Debug)]
pub struct Tree<D: Digest> {
    /// Records whether the tree is empty.
    empty: bool,

    /// The digests at each level of the tree (from leaves to root).
    levels: NonEmptyVec<NonEmptyVec<D>>,

    /// The finalized root digest, which incorporates the leaf count.
    ///
    /// This is computed as `H(leaf_count || tree_root)` to prevent
    /// proof malleability where proofs that declare different leaf
    /// counts could verify against the same root.
    root: D,
}

impl<D: Digest> Tree<D> {
    /// Builds a Merkle Tree from a slice of position-hashed leaf digests.
    fn new<H: Hasher<Digest = D>>(mut leaves: Vec<D>) -> Self {
        // If no leaves, add an empty node.
        //
        // Because this node only includes a position, there is no way a valid proof
        // can be generated that references it.
        let mut empty = false;
        let leaf_count = leaves.len() as u32;
        if leaves.is_empty() {
            leaves.push(H::hash(&[]));
            empty = true;
        }

        // Create the first level
        let mut levels = non_empty_vec![non_empty_vec![@leaves]];

        // Construct the tree level-by-level
        let mut current_level = levels.last();
        while !current_level.is_singleton() {
            let mut next_level = Vec::with_capacity(current_level.len().get().div_ceil(2));

            // Process four nodes (two sibling pairs) at a time, duplicating an unpaired
            // trailing node. Hashing both pairs together lets the underlying hasher
            // interleave independent messages (see `Hasher::hash_pair`). A trailing
            // group with a single pair falls back to a single hash.
            for group in current_level.chunks(4) {
                match group {
                    [a, b, c, d] => {
                        let (left, right) = H::hash_pair(
                            &[a.as_ref(), b.as_ref()],
                            &[c.as_ref(), d.as_ref()],
                            &Sequential,
                        );
                        next_level.push(left);
                        next_level.push(right);
                    }
                    [a, b, c] => {
                        let (left, right) = H::hash_pair(
                            &[a.as_ref(), b.as_ref()],
                            &[c.as_ref(), c.as_ref()],
                            &Sequential,
                        );
                        next_level.push(left);
                        next_level.push(right);
                    }
                    [a, b] => next_level.push(H::hash(&[a.as_ref(), b.as_ref()])),
                    [a] => next_level.push(H::hash(&[a.as_ref(), a.as_ref()])),
                    _ => unreachable!("chunks(4) yields at most 4 elements"),
                }
            }

            // Add the computed level to the tree
            levels.push(non_empty_vec![@next_level]);
            current_level = levels.last();
        }

        // Compute the finalized root: H(leaf_count || tree_root)
        // This binds the root to the tree size, preventing malleability attacks.
        let tree_root = levels.last().first();
        let root = H::hash(&[&leaf_count.to_be_bytes(), tree_root.as_ref()]);

        Self {
            empty,
            levels,
            root,
        }
    }

    /// Returns the finalized root of the tree.
    ///
    /// The root incorporates the leaf count via `H(leaf_count || tree_root)`,
    /// which prevents proof malleability attacks where different tree sizes
    /// could produce valid proofs for the same root.
    pub const fn root(&self) -> D {
        self.root
    }

    /// Generates a Merkle proof for the leaf at `position`.
    ///
    /// The proof holds the minimal siblings needed to reconstruct the root and
    /// equals the single-element multi-proof for `position`.
    pub fn proof(&self, position: u32) -> Result<Proof<D>, Error> {
        // The empty tree's placeholder node passes the bound check, so it is
        // rejected separately.
        let leaf_count = self.levels.first().len().get() as u32;
        if self.empty || position >= leaf_count {
            return Err(Error::InvalidPosition(position));
        }

        // Walk up from the leaf and record the other child of each parent on the
        // path. `index ^ 1` is the left neighbor of an odd index or the right
        // neighbor of an even index. The right neighbor is absent only for the last
        // node of an odd-sized level, and that node is paired with itself. The root
        // level has no parent and is skipped.
        let levels = self.levels.len().get();
        let mut siblings = Vec::with_capacity(levels - 1);
        let mut index = position as usize;
        for level in &self.levels[..levels - 1] {
            if let Some(sibling) = level.get(index ^ 1) {
                siblings.push(*sibling);
            }
            index /= 2;
        }

        Ok(Proof {
            leaf_count,
            siblings,
        })
    }

    /// Generates a Merkle range proof for a contiguous set of leaves from `start`
    /// to `end` (inclusive).
    ///
    /// The proof contains the minimal set of sibling digests needed to reconstruct
    /// the root for all elements in the range. This is more efficient than individual
    /// proofs when proving multiple consecutive elements.
    pub fn range_proof(&self, start: u32, end: u32) -> Result<Proof<D>, Error> {
        // For empty trees, return an empty proof
        if self.empty {
            if start == 0 && end == 0 {
                return Ok(Proof::default());
            }
            return Err(Error::InvalidPosition(start));
        }

        // Validate range bounds
        if start > end {
            return Err(Error::InvalidPosition(start));
        }
        let leaf_count = self.levels.first().len().get() as u32;
        if start >= leaf_count {
            return Err(Error::InvalidPosition(start));
        }
        if end >= leaf_count {
            return Err(Error::InvalidPosition(end));
        }

        // Compute required siblings without enumerating every leaf in the range.
        // There are at most two per level and they arrive sorted by level and
        // index, so their digests are pushed straight into the proof.
        let mut siblings = Vec::with_capacity(2 * (levels_in_tree(leaf_count) - 1));
        siblings_required_for_range_proof(leaf_count, start, end, |level, index| {
            siblings.push(self.levels[level][index])
        })?;

        Ok(Proof {
            leaf_count,
            siblings,
        })
    }

    /// Generates a Merkle proof for multiple non-contiguous leaves at the given `positions`.
    ///
    /// The proof contains the minimal set of sibling digests needed to reconstruct
    /// the root for all elements at the specified positions. This is more efficient
    /// than individual proofs when proving multiple elements because shared siblings
    /// are deduplicated.
    ///
    /// Positions must be strictly ascending and in range. The error names the
    /// first position in input order that is out of range, repeats the previous
    /// one, or precedes it.
    pub fn multi_proof<I, P>(&self, positions: I) -> Result<Proof<D>, Error>
    where
        I: IntoIterator<Item = P>,
        P: core::borrow::Borrow<u32>,
    {
        let mut positions = positions.into_iter().peekable();

        // Handle empty positions first, since a proof cannot cover zero elements
        let first = *positions.peek().ok_or(Error::NoLeaves)?.borrow();

        // Handle empty tree case
        if self.empty {
            return Err(Error::InvalidPosition(first));
        }

        let leaf_count = self.levels.first().len().get() as u32;

        // Get required sibling positions (this validates positions and their order)
        let sibling_positions =
            siblings_required_for_multi_proof(leaf_count, positions.map(|p| *p.borrow()))?;

        // Collect sibling digests in order. Their count is known from the helper's
        // result, so the digests need at most one allocation.
        let siblings: Vec<D> = sibling_positions
            .iter()
            .map(|&(level, index)| self.levels[level][index])
            .collect();

        Ok(Proof {
            leaf_count,
            siblings,
        })
    }
}

/// A Merkle proof for multiple non-contiguous leaves in a Binary Merkle Tree.
///
/// This proof type is more space-efficient than generating individual proofs
/// for each leaf because sibling nodes that are shared between multiple paths
/// are deduplicated.
///
/// The proof contains the leaf count and sibling digests required for verification.
/// The leaf count is incorporated into the root hash during finalization, so
/// modifying it will cause verification to fail (preventing malleability attacks).
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct Proof<D: Digest> {
    /// The number of leaves in the tree.
    ///
    /// This value is incorporated into the root hash during finalization,
    /// so modifying it will cause verification to fail (prevents malleability).
    pub leaf_count: u32,

    /// The deduplicated sibling digests required to verify all elements,
    /// ordered by their position in the tree (level-major, then index within level).
    pub siblings: Vec<D>,
}

impl<D: Digest> Default for Proof<D> {
    fn default() -> Self {
        Self {
            leaf_count: 0,
            siblings: Vec::new(),
        }
    }
}

impl<D: Digest> Write for Proof<D> {
    fn write(&self, writer: &mut impl BufMut) {
        self.leaf_count.write(writer);
        self.siblings.write(writer);
    }
}

impl<D: Digest> Read for Proof<D> {
    /// The maximum number of items being proven.
    ///
    /// The upper bound on sibling hashes is derived as `max_items * MAX_LEVELS`.
    type Cfg = usize;

    fn read_cfg(
        reader: &mut impl Buf,
        max_items: &Self::Cfg,
    ) -> Result<Self, commonware_codec::Error> {
        let leaf_count = u32::read(reader)?;
        let max_siblings = max_items.saturating_mul(MAX_LEVELS);
        let siblings = Vec::<D>::read_range(reader, ..=max_siblings)?;
        Ok(Self {
            leaf_count,
            siblings,
        })
    }
}

impl<D: Digest> EncodeSize for Proof<D> {
    fn encode_size(&self) -> usize {
        self.leaf_count.encode_size() + self.siblings.encode_size()
    }
}

#[cfg(feature = "arbitrary")]
impl<D: Digest> arbitrary::Arbitrary<'_> for Proof<D>
where
    D: for<'a> arbitrary::Arbitrary<'a>,
{
    fn arbitrary(u: &mut arbitrary::Unstructured<'_>) -> arbitrary::Result<Self> {
        Ok(Self {
            leaf_count: u.arbitrary()?,
            siblings: u.arbitrary()?,
        })
    }
}

/// Returns the number of levels in a tree with `leaf_count` leaves.
/// A tree with 1 leaf has 1 level, a tree with 2 leaves has 2 levels, etc.
const fn levels_in_tree(leaf_count: u32) -> usize {
    (u32::BITS - (leaf_count.saturating_sub(1)).leading_zeros() + 1) as usize
}

/// Returns the positions of siblings required to prove inclusion of leaves at the
/// given positions. The result is ordered by level and then by index within the
/// level.
///
/// Each position in the result is encoded as `(level, index)` where level 0 is the leaf level.
///
/// Positions must be strictly ascending and below `leaf_count`. The error names
/// the first position in input order that is not.
fn siblings_required_for_multi_proof(
    leaf_count: u32,
    positions: impl IntoIterator<Item = u32>,
) -> Result<Vec<(usize, usize)>, Error> {
    // Strictly ascending input is sorted and unique by construction, so each
    // position only needs comparing with the previous one, and reading stops at
    // the first invalid position.
    //
    // An exact length (as from a slice) sizes the buffer upfront. Any other
    // iterator grows it as positions are read, so one that never ends cannot
    // reserve memory for positions it has not produced.
    let positions = positions.into_iter();
    let capacity = match positions.size_hint() {
        (lower, Some(upper)) if lower == upper => lower.min(leaf_count as usize),
        _ => 0,
    };
    let mut current: Vec<usize> = Vec::with_capacity(capacity);
    for pos in positions {
        if pos >= leaf_count {
            return Err(Error::InvalidPosition(pos));
        }
        match current.last() {
            Some(&last) if last == pos as usize => return Err(Error::DuplicatePosition(pos)),
            Some(&last) if last > pos as usize => return Err(Error::UnsortedPosition(pos)),
            _ => current.push(pos as usize),
        }
    }
    if current.is_empty() {
        return Err(Error::NoLeaves);
    }

    // Track the sorted, unique indices that can be computed at each level and
    // record the missing siblings. Each level costs work proportional to the
    // number of positions, not to the level's size.
    let mut next = Vec::with_capacity(current.len());
    let mut sibling_positions = Vec::with_capacity(current.len());
    let levels_count = levels_in_tree(leaf_count);
    let mut level_size = leaf_count as usize;
    for level in 0..levels_count - 1 {
        for (offset, &index) in current.iter().enumerate() {
            // The sibling is the other child of the same parent. Because
            // `current` is sorted and unique, the sibling is known exactly when
            // it is the adjacent entry.
            let sibling = index ^ 1;
            let known = if index.is_multiple_of(2) {
                current.get(offset + 1) == Some(&sibling)
            } else {
                offset > 0 && current[offset - 1] == sibling
            };

            // The last node of an odd-sized level is paired with itself and needs
            // no sibling. Sibling pairs are disjoint, so each level's pushes are
            // ascending and unique.
            if sibling < level_size && !known {
                sibling_positions.push((level, sibling));
            }

            // Parents of sorted indices are sorted, and children of one parent
            // are adjacent, so skipping a repeat of the last parent keeps
            // `next` unique.
            let parent = index / 2;
            if next.last() != Some(&parent) {
                next.push(parent);
            }
        }

        // Move up a level, keeping the old buffer for the next level's parents.
        core::mem::swap(&mut current, &mut next);
        next.clear();
        level_size = level_size.div_ceil(2);
    }

    Ok(sibling_positions)
}

/// Calls `sibling` with the position of each sibling required to prove inclusion
/// of a contiguous range of leaves from `start` to `end` (inclusive). Calls are
/// ordered by level and then by index within the level.
///
/// Each position is passed as `(level, index)` where level 0 is the leaf level.
/// Bounds are validated before any position is passed.
fn siblings_required_for_range_proof(
    leaf_count: u32,
    start: u32,
    end: u32,
    mut sibling: impl FnMut(usize, usize),
) -> Result<(), Error> {
    if leaf_count == 0 {
        return Err(Error::NoLeaves);
    }
    if start > end {
        return Err(Error::InvalidPosition(start));
    }
    if start >= leaf_count {
        return Err(Error::InvalidPosition(start));
    }
    if end >= leaf_count {
        return Err(Error::InvalidPosition(end));
    }

    let levels_count = levels_in_tree(leaf_count);
    let mut level_start = start as usize;
    let mut level_end = end as usize;
    let mut level_size = leaf_count as usize;

    // Each level needs at most two siblings: the left neighbor of the range
    // start, then the right neighbor of the range end. They lie on opposite
    // sides of the range, so they are distinct and ascending.
    for level in 0..levels_count - 1 {
        if !level_start.is_multiple_of(2) {
            sibling(level, level_start - 1);
        }
        if level_end.is_multiple_of(2) {
            let right = level_end + 1;
            if right < level_size {
                sibling(level, right);
            }
        }

        level_start /= 2;
        level_end /= 2;
        level_size = level_size.div_ceil(2);
    }

    Ok(())
}

impl<D: Digest> Proof<D> {
    /// Returns an upper bound on the encoded size of a proof with at most `siblings` sibling
    /// digests.
    pub fn max_encode_size(siblings: usize) -> usize {
        max_items_size(siblings, D::SIZE) + u32::SIZE
    }

    /// Verifies that a given `leaf` at `position` is included in a Binary Merkle Tree
    /// with `root`.
    ///
    /// The proof consists of sibling hashes stored from the leaf up to the root. At each
    /// level, if the current node is a left child (even index), the sibling is combined
    /// to the right; if it is a right child (odd index), the sibling is combined to the
    /// left.
    ///
    /// The `leaf_count` stored in the proof is incorporated into the finalized root
    /// computation, so any modification to it will cause verification to fail.
    pub fn verify_element_inclusion<H: Hasher<Digest = D>>(
        &self,
        leaf: &D,
        mut position: u32,
        root: &D,
    ) -> Result<(), Error> {
        // Validate position
        if position >= self.leaf_count {
            return Err(Error::InvalidPosition(position));
        }

        // Compute the position-hashed leaf
        let mut computed = H::hash(&[&position.to_be_bytes(), leaf.as_ref()]);

        // Track level size to handle odd-sized levels
        let mut level_size = self.leaf_count as usize;
        let mut sibling_iter = self.siblings.iter();

        // Traverse from leaf to root
        while level_size > 1 {
            // Check if this is the last node at an odd-sized level (no real sibling)
            let is_last_odd = position.is_multiple_of(2) && position as usize + 1 >= level_size;

            let (left_node, right_node) = if is_last_odd {
                // Node is duplicated, so no sibling is consumed from the proof
                (computed, computed)
            } else if position.is_multiple_of(2) {
                // Even position: sibling is to the right
                let sibling = *sibling_iter.next().ok_or(Error::UnalignedProof)?;
                (computed, sibling)
            } else {
                // Odd position: sibling is to the left
                let sibling = *sibling_iter.next().ok_or(Error::UnalignedProof)?;
                (sibling, computed)
            };

            // Compute the parent digest
            computed = H::hash(&[left_node.as_ref(), right_node.as_ref()]);

            // Move up the tree
            position /= 2;
            level_size = level_size.div_ceil(2);
        }

        // Ensure all siblings were consumed
        if sibling_iter.next().is_some() {
            return Err(Error::UnalignedProof);
        }

        // Finalize the root by incorporating the leaf count: H(leaf_count || tree_root)
        // This binds the proof to the specific tree size, preventing malleability attacks.
        let finalized = H::hash(&[&self.leaf_count.to_be_bytes(), computed.as_ref()]);

        if finalized == *root {
            Ok(())
        } else {
            Err(Error::InvalidProof(finalized.to_string(), root.to_string()))
        }
    }

    /// Verifies that the given `elements` at their respective positions are included
    /// in a Binary Merkle Tree with `root`.
    ///
    /// Positions must be strictly ascending and in range. The error names the
    /// first position in input order that is out of range, repeats the previous
    /// one, or precedes it.
    ///
    /// The `leaf_count` stored in the proof is incorporated into the finalized root
    /// computation, so any modification to it will cause verification to fail.
    pub fn verify_multi_inclusion<H: Hasher<Digest = D>>(
        &self,
        elements: &[(D, u32)],
        root: &D,
    ) -> Result<(), Error> {
        // Handle empty case
        if elements.is_empty() {
            if self.leaf_count == 0 && self.siblings.is_empty() {
                // Compute finalized empty root: H(0 || empty_tree_root)
                let empty_tree_root = H::hash(&[]);
                let finalized = H::hash(&[&0u32.to_be_bytes(), empty_tree_root.as_ref()]);
                if finalized == *root {
                    return Ok(());
                } else {
                    return Err(Error::InvalidProof(finalized.to_string(), root.to_string()));
                }
            }
            return Err(Error::NoLeaves);
        }

        // 1. Check that positions are strictly ascending and in range
        let mut previous = None;
        for &(_, position) in elements {
            if position >= self.leaf_count {
                return Err(Error::InvalidPosition(position));
            }
            match previous {
                Some(previous) if position == previous => {
                    return Err(Error::DuplicatePosition(position));
                }
                Some(previous) if position < previous => {
                    return Err(Error::UnsortedPosition(position));
                }
                _ => previous = Some(position),
            }
        }

        // 2. Hash the position-prefixed leaves, two at a time via `hash_pair`
        let mut current: Vec<(u32, D)> = Vec::with_capacity(elements.len());
        let (leaf_chunks, leaf_remainder) = elements.as_chunks::<2>();
        for chunk in leaf_chunks {
            let (leaf_a, pos_a) = &chunk[0];
            let (leaf_b, pos_b) = &chunk[1];
            let (digest_a, digest_b) = H::hash_pair(
                &[&pos_a.to_be_bytes(), leaf_a.as_ref()],
                &[&pos_b.to_be_bytes(), leaf_b.as_ref()],
                &Sequential,
            );
            current.push((*pos_a, digest_a));
            current.push((*pos_b, digest_b));
        }
        for (leaf, position) in leaf_remainder {
            let digest = H::hash(&[&position.to_be_bytes(), leaf.as_ref()]);
            current.push((*position, digest));
        }

        // 3. Iterate up the tree
        // Since we process left-to-right and parent_pos = pos/2, next_level stays sorted.
        let levels = levels_in_tree(self.leaf_count);
        let mut level_size = self.leaf_count;
        let mut sibling_iter = self.siblings.iter();
        let mut next_level: Vec<(u32, D)> = Vec::with_capacity(current.len());
        let mut parents: Vec<(u32, D, D)> = Vec::with_capacity(current.len());

        for _ in 0..levels - 1 {
            // First pass: determine each parent's (left, right) children without hashing, so
            // independent parent digests can be batched together in the second pass.
            let mut idx = 0;
            while idx < current.len() {
                let (pos, digest) = current[idx];
                let parent_pos = pos / 2;

                // Determine if we have the left or right child
                let (left, right) = if pos.is_multiple_of(2) {
                    // We are the LEFT child
                    let left = digest;

                    // Check if we have the right child in our current set
                    let right = if idx + 1 < current.len() && current[idx + 1].0 == pos + 1 {
                        idx += 1;
                        current[idx].1
                    } else if pos + 1 >= level_size {
                        // If no right child exists in tree, duplicate left
                        left
                    } else {
                        // Otherwise, must consume a sibling
                        *sibling_iter.next().ok_or(Error::UnalignedProof)?
                    };
                    (left, right)
                } else {
                    // We are the RIGHT child
                    // This implies the LEFT child was missing from 'current', so it must be a sibling.
                    let right = digest;
                    let left = *sibling_iter.next().ok_or(Error::UnalignedProof)?;
                    (left, right)
                };

                parents.push((parent_pos, left, right));
                idx += 1;
            }

            // Second pass: hash independent parent digests two at a time via `hash_pair`.
            let (parent_chunks, parent_remainder) = parents.as_chunks::<2>();
            for chunk in parent_chunks {
                let (pos_a, left_a, right_a) = chunk[0];
                let (pos_b, left_b, right_b) = chunk[1];
                let (digest_a, digest_b) = H::hash_pair(
                    &[left_a.as_ref(), right_a.as_ref()],
                    &[left_b.as_ref(), right_b.as_ref()],
                    &Sequential,
                );
                next_level.push((pos_a, digest_a));
                next_level.push((pos_b, digest_b));
            }
            for &(pos, left, right) in parent_remainder {
                next_level.push((pos, H::hash(&[left.as_ref(), right.as_ref()])));
            }
            parents.clear();

            // Prepare for next level
            core::mem::swap(&mut current, &mut next_level);
            next_level.clear();
            level_size = level_size.div_ceil(2);
        }

        // 4. Verify root
        if sibling_iter.next().is_some() {
            return Err(Error::UnalignedProof);
        }

        if current.len() != 1 {
            return Err(Error::UnalignedProof);
        }

        // Finalize the root by incorporating the leaf count: H(leaf_count || tree_root)
        // This binds the proof to the specific tree size, preventing malleability attacks.
        let tree_root = current[0].1;
        let finalized = H::hash(&[&self.leaf_count.to_be_bytes(), tree_root.as_ref()]);

        if finalized == *root {
            Ok(())
        } else {
            Err(Error::InvalidProof(finalized.to_string(), root.to_string()))
        }
    }

    /// Verifies that a contiguous range of `leaves` starting at `position` are included
    /// in a Binary Merkle Tree with `root`.
    ///
    /// This is a convenience method for verifying range proofs. The leaves must be
    /// in order starting from `position`.
    ///
    /// The `leaf_count` stored in the proof is incorporated into the finalized root
    /// computation, so any modification to it will cause verification to fail.
    pub fn verify_range_inclusion<H: Hasher<Digest = D>>(
        &self,
        position: u32,
        leaves: &[D],
        root: &D,
    ) -> Result<(), Error> {
        // For empty trees, only position 0 with empty leaves is valid
        if leaves.is_empty() && position != 0 {
            return Err(Error::InvalidPosition(position));
        }
        if !leaves.is_empty() {
            let leaves_len =
                u32::try_from(leaves.len()).map_err(|_| Error::InvalidPosition(position))?;
            let end = position
                .checked_add(leaves_len - 1)
                .ok_or(Error::InvalidPosition(position))?;
            if end >= self.leaf_count {
                return Err(Error::InvalidPosition(end));
            }
        }

        // Convert to format expected by verify_multi_inclusion
        let elements: Vec<(D, u32)> = leaves
            .iter()
            .enumerate()
            .map(|(i, leaf)| (*leaf, position + i as u32))
            .collect();
        self.verify_multi_inclusion::<H>(&elements, root)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use commonware_codec::{Decode, Encode};
    use commonware_cryptography::sha256::{Digest, Sha256};
    use rstest::rstest;

    /// Regression test for https://github.com/commonwarexyz/monorepo/issues/2837
    ///
    /// Before the fix, two proofs with identical siblings but different leaf_count
    /// values would both verify successfully against the same root, enabling
    /// proof malleability attacks.
    #[test]
    fn issue_2837_regression() {
        // Create a tree with 255 leaves (as in the issue report)
        let digests: Vec<Digest> = (0..255u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        let mut builder = Builder::<Sha256>::new(255);
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Get a valid proof for position 0
        let original_proof = tree.proof(0).unwrap();
        assert_eq!(original_proof.leaf_count, 255);

        // Original proof should verify
        assert!(
            original_proof
                .verify_element_inclusion::<Sha256>(&digests[0], 0, &root)
                .is_ok(),
            "Original proof should verify"
        );

        // Create a malleated proof with leaf_count=254 but same siblings
        // (This is the exact attack from issue #2837)
        let malleated_proof = Proof {
            leaf_count: 254,
            siblings: original_proof.siblings,
        };

        // Malleated proof should NOT verify because the root now incorporates
        // the leaf_count: root = H(leaf_count || tree_root)
        let result = malleated_proof.verify_element_inclusion::<Sha256>(&digests[0], 0, &root);
        assert!(
            result.is_err(),
            "Malleated proof with wrong leaf_count must fail verification"
        );
    }

    #[test]
    fn test_tampered_proof_no_siblings() {
        // Create transactions and digests
        let txs = [b"tx1", b"tx2", b"tx3", b"tx4"];
        let digests: Vec<Digest> = txs.iter().map(|tx| Sha256::hash(&[*tx])).collect();
        let element = &digests[0];

        // Build tree
        let mut builder = Builder::<Sha256>::new(txs.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Build proof
        let mut proof = tree.proof(0).unwrap();

        // Tamper with proof
        proof.siblings = Vec::new();

        // Fail verification with an empty proof.
        assert!(
            proof
                .verify_element_inclusion::<Sha256>(element, 0, &root)
                .is_err()
        );
    }

    #[test]
    fn test_tampered_proof_extra_sibling() {
        // Create transactions and digests
        let txs = [b"tx1", b"tx2", b"tx3", b"tx4"];
        let digests: Vec<Digest> = txs.iter().map(|tx| Sha256::hash(&[*tx])).collect();
        let element = &digests[0];

        // Build tree
        let mut builder = Builder::<Sha256>::new(txs.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Build proof
        let mut proof = tree.proof(0).unwrap();

        // Tamper with proof
        proof.siblings.push(*element);

        // Fail verification with extra sibling
        assert!(
            proof
                .verify_element_inclusion::<Sha256>(element, 0, &root)
                .is_err()
        );
    }

    #[test]
    fn test_invalid_proof_wrong_element() {
        // Create transactions and digests
        let txs = [b"tx1", b"tx2", b"tx3", b"tx4"];
        let digests: Vec<Digest> = txs.iter().map(|tx| Sha256::hash(&[*tx])).collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(txs.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Generate a valid proof for leaf at index 2.
        let proof = tree.proof(2).unwrap();

        // Use a wrong element (e.g. hash of a different transaction).
        let wrong_leaf = Sha256::hash(&[b"wrong_tx"]);
        assert!(
            proof
                .verify_element_inclusion::<Sha256>(&wrong_leaf, 2, &root)
                .is_err()
        );
    }

    #[test]
    fn test_invalid_proof_wrong_index() {
        // Create transactions and digests
        let txs = [b"tx1", b"tx2", b"tx3", b"tx4"];
        let digests: Vec<Digest> = txs.iter().map(|tx| Sha256::hash(&[*tx])).collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(txs.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Generate a valid proof for leaf at index 1.
        let proof = tree.proof(1).unwrap();

        // Use an incorrect index (e.g. 2 instead of 1).
        assert!(
            proof
                .verify_element_inclusion::<Sha256>(&digests[1], 2, &root)
                .is_err()
        );
    }

    #[test]
    fn test_invalid_proof_wrong_root() {
        // Create transactions and digests
        let txs = [b"tx1", b"tx2", b"tx3", b"tx4"];
        let digests: Vec<Digest> = txs.iter().map(|tx| Sha256::hash(&[*tx])).collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(txs.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();

        // Generate a valid proof for leaf at index 0.
        let proof = tree.proof(0).unwrap();

        // Use a wrong root (hash of a different input).
        let wrong_root = Sha256::hash(&[b"wrong_root"]);
        assert!(
            proof
                .verify_element_inclusion::<Sha256>(&digests[0], 0, &wrong_root)
                .is_err()
        );
    }

    #[test]
    fn test_invalid_proof_serialization_truncated() {
        // Create transactions and digests
        let txs = [b"tx1", b"tx2", b"tx3"];
        let digests: Vec<Digest> = txs.iter().map(|tx| Sha256::hash(&[*tx])).collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(txs.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();

        // Generate a valid proof for leaf at index 1.
        let proof = tree.proof(1).unwrap();
        let mut serialized = proof.encode();

        // Truncate one byte.
        serialized.truncate(serialized.len() - 1);
        assert!(Proof::<Digest>::decode_cfg(&mut serialized, &1).is_err());
    }

    #[test]
    fn test_invalid_proof_serialization_extra() {
        // Create transactions and digests
        let txs = [b"tx1", b"tx2", b"tx3"];
        let digests: Vec<Digest> = txs.iter().map(|tx| Sha256::hash(&[*tx])).collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(txs.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();

        // Generate a valid proof for leaf at index 1.
        let proof = tree.proof(1).unwrap();
        let mut serialized = proof.encode_mut();

        // Append an extra byte.
        serialized.extend_from_slice(&[0u8]);
        assert!(Proof::<Digest>::decode_cfg(&mut serialized, &1).is_err());
    }

    #[test]
    fn test_invalid_proof_modified_hash() {
        // Create transactions and digests
        let txs = [b"tx1", b"tx2", b"tx3", b"tx4"];
        let digests: Vec<Digest> = txs.iter().map(|tx| Sha256::hash(&[*tx])).collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(txs.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Generate a valid proof for leaf at index 2.
        let mut proof = tree.proof(2).unwrap();

        // Modify the first hash in the proof.
        proof.siblings[0] = Sha256::hash(&[b"modified"]);
        assert!(
            proof
                .verify_element_inclusion::<Sha256>(&digests[2], 2, &root)
                .is_err()
        );
    }

    #[test]
    fn test_odd_tree_duplicate_index_proof() {
        // Create transactions and digests
        let txs = [b"tx1", b"tx2", b"tx3"];
        let digests: Vec<Digest> = txs.iter().map(|tx| Sha256::hash(&[*tx])).collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(txs.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // The tree was built with 3 leaves; index 2 is the last valid index.
        let proof = tree.proof(2).unwrap();

        // Verification should succeed for the proper index 2.
        assert!(
            proof
                .verify_element_inclusion::<Sha256>(&digests[2], 2, &root)
                .is_ok()
        );

        // Should not be able to generate a proof for an out-of-range index (e.g. 3).
        assert!(tree.proof(3).is_err());

        // Attempting to verify using an out-of-range index (e.g. 3, which would correspond
        // to a duplicate leaf that doesn't actually exist) should fail.
        assert!(
            proof
                .verify_element_inclusion::<Sha256>(&digests[2], 3, &root)
                .is_err()
        );
    }

    #[test]
    fn test_range_proof_basic() {
        // Create test data
        let digests: Vec<Digest> = (0..8u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Test range proof for elements 2-5
        let range_proof = tree.range_proof(2, 5).unwrap();
        let range_leaves = &digests[2..6];

        assert!(
            range_proof
                .verify_range_inclusion::<Sha256>(2, range_leaves, &root)
                .is_ok()
        );

        // Serialize and deserialize
        let mut serialized = range_proof.encode();
        let deserialized = Proof::<Digest>::decode_cfg(&mut serialized, &4).unwrap();
        assert!(
            deserialized
                .verify_range_inclusion::<Sha256>(2, range_leaves, &root)
                .is_ok()
        );
    }

    #[test]
    fn test_range_proof_single_element() {
        // Create test data
        let digests: Vec<Digest> = (0..8u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Test single element range proof
        for (i, digest) in digests.iter().enumerate() {
            let range_proof = tree.range_proof(i as u32, i as u32).unwrap();

            let result = range_proof.verify_range_inclusion::<Sha256>(i as u32, &[*digest], &root);
            assert!(result.is_ok());
        }
    }

    #[test]
    fn test_range_proof_full_tree() {
        // Create test data
        let digests: Vec<Digest> = (0..7u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Test full tree range proof
        let range_proof = tree.range_proof(0, (digests.len() - 1) as u32).unwrap();
        assert!(
            range_proof
                .verify_range_inclusion::<Sha256>(0, &digests, &root)
                .is_ok()
        );
    }

    #[test]
    fn test_range_proof_edge_cases() {
        // Create test data
        let digests: Vec<Digest> = (0..15u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Test first half
        let range_proof = tree.range_proof(0, 7).unwrap();
        assert!(
            range_proof
                .verify_range_inclusion::<Sha256>(0, &digests[0..8], &root)
                .is_ok()
        );

        // Test second half
        let range_proof = tree.range_proof(8, 14).unwrap();
        assert!(
            range_proof
                .verify_range_inclusion::<Sha256>(8, &digests[8..15], &root)
                .is_ok()
        );

        // Test last elements
        let range_proof = tree.range_proof(13, 14).unwrap();
        assert!(
            range_proof
                .verify_range_inclusion::<Sha256>(13, &digests[13..15], &root)
                .is_ok()
        );
    }

    #[test]
    fn test_range_proof_invalid_range() {
        // Create test data
        let digests: Vec<Digest> = (0..8u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();

        // Test invalid ranges
        assert!(tree.range_proof(8, 8).is_err()); // Start out of bounds
        assert!(tree.range_proof(0, 8).is_err()); // End out of bounds
        assert!(tree.range_proof(5, 8).is_err()); // End out of bounds
        assert!(tree.range_proof(2, 1).is_err()); // Start > end
    }

    #[test]
    fn test_range_proof_tampering() {
        // Create test data
        let digests: Vec<Digest> = (0..8u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Get valid range proof
        let range_proof = tree.range_proof(2, 4).unwrap();
        let range_leaves = &digests[2..5];

        // Test with wrong leaves
        let wrong_leaves = vec![
            Sha256::hash(&[b"wrong1"]),
            Sha256::hash(&[b"wrong2"]),
            Sha256::hash(&[b"wrong3"]),
        ];
        assert!(
            range_proof
                .verify_range_inclusion::<Sha256>(2, &wrong_leaves, &root)
                .is_err()
        );

        // Test with wrong number of leaves
        assert!(
            range_proof
                .verify_range_inclusion::<Sha256>(2, &digests[2..4], &root)
                .is_err()
        );

        // Test with tampered proof
        let mut tampered_proof = range_proof.clone();
        assert!(!tampered_proof.siblings.is_empty());
        // Tamper with the first sibling
        tampered_proof.siblings[0] = Sha256::hash(&[b"tampered"]);
        assert!(
            tampered_proof
                .verify_range_inclusion::<Sha256>(2, range_leaves, &root)
                .is_err()
        );

        // Test with wrong root
        let wrong_root = Sha256::hash(&[b"wrong_root"]);
        assert!(
            range_proof
                .verify_range_inclusion::<Sha256>(2, range_leaves, &wrong_root)
                .is_err()
        );
    }

    #[test]
    fn test_range_proof_various_sizes() {
        // Test range proofs for trees of various sizes
        for tree_size in [1, 2, 3, 4, 5, 7, 8, 15, 16, 31, 32, 63, 64] {
            let digests: Vec<Digest> = (0..tree_size as u32)
                .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
                .collect();

            // Build tree
            let mut builder = Builder::<Sha256>::new(digests.len());
            for digest in &digests {
                builder.add(digest);
            }
            let tree = builder.build();
            let root = tree.root();

            // Test various range sizes
            for range_size in 1..=tree_size.min(8) {
                for start in 0..=(tree_size - range_size) {
                    let range_proof = tree
                        .range_proof(start as u32, (start + range_size - 1) as u32)
                        .unwrap();
                    let end = start + range_size;
                    assert!(
                        range_proof
                            .verify_range_inclusion::<Sha256>(
                                start as u32,
                                &digests[start..end],
                                &root
                            )
                            .is_ok(),
                        "Failed for tree_size={tree_size}, start={start}, range_size={range_size}"
                    );
                }
            }
        }
    }

    #[test]
    fn test_range_proof_malicious_wrong_position() {
        // Create test data
        let digests: Vec<Digest> = (0..8u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Get valid range proof for position 2 to 4
        let range_proof = tree.range_proof(2, 4).unwrap();
        let range_leaves = &digests[2..5];

        // Try to verify with wrong position
        assert!(
            range_proof
                .verify_range_inclusion::<Sha256>(3, range_leaves, &root)
                .is_err()
        );
        assert!(
            range_proof
                .verify_range_inclusion::<Sha256>(1, range_leaves, &root)
                .is_err()
        );
    }

    #[test]
    fn test_range_proof_malicious_reordered_leaves() {
        // Create test data
        let digests: Vec<Digest> = (0..8u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Get valid range proof for position 2 to 4
        let range_proof = tree.range_proof(2, 4).unwrap();

        // Try to verify with reordered leaves
        let reordered_leaves = vec![digests[3], digests[2], digests[4]];
        assert!(
            range_proof
                .verify_range_inclusion::<Sha256>(2, &reordered_leaves, &root)
                .is_err()
        );
    }

    #[test]
    fn test_range_proof_malicious_extra_siblings() {
        // Create test data
        let digests: Vec<Digest> = (0..8u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Get valid range proof
        let mut range_proof = tree.range_proof(2, 3).unwrap();
        let range_leaves = &digests[2..4];

        // Tamper by adding extra siblings
        range_proof.siblings.push(Sha256::hash(&[b"extra"]));
        assert!(
            range_proof
                .verify_range_inclusion::<Sha256>(2, range_leaves, &root)
                .is_err()
        );
    }

    #[test]
    fn test_range_proof_malicious_missing_siblings() {
        // Create test data
        let digests: Vec<Digest> = (0..8u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Get valid range proof for a single element (which needs siblings)
        let mut range_proof = tree.range_proof(2, 2).unwrap();
        let range_leaves = &digests[2..3];

        // The proof should have siblings
        assert!(!range_proof.siblings.is_empty());

        // Remove a sibling
        range_proof.siblings.pop();
        assert!(
            range_proof
                .verify_range_inclusion::<Sha256>(2, range_leaves, &root)
                .is_err()
        );
    }

    #[test]
    fn test_range_proof_integer_overflow_protection() {
        // Create test data
        let digests: Vec<Digest> = (0..8u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();

        // Test overflow in range_proof generation
        assert!(tree.range_proof(u32::MAX, u32::MAX).is_err());
        assert!(tree.range_proof(u32::MAX - 1, u32::MAX).is_err());
        assert!(tree.range_proof(7, u32::MAX).is_err());
    }

    #[test]
    fn test_range_proof_malicious_wrong_tree_structure() {
        // Create test data
        let digests: Vec<Digest> = (0..8u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Get valid range proof
        let mut range_proof = tree.range_proof(2, 3).unwrap();
        let range_leaves = &digests[2..4];

        // Add extra sibling (simulating proof from different tree structure)
        range_proof.siblings.push(Sha256::hash(&[b"fake_level"]));
        assert!(
            range_proof
                .verify_range_inclusion::<Sha256>(2, range_leaves, &root)
                .is_err()
        );

        // Remove a sibling
        let mut range_proof = tree.range_proof(2, 2).unwrap();
        let range_leaves = &digests[2..3];
        assert!(!range_proof.siblings.is_empty());
        range_proof.siblings.pop();
        assert!(
            range_proof
                .verify_range_inclusion::<Sha256>(2, range_leaves, &root)
                .is_err()
        );
    }

    #[test]
    fn test_range_proof_boundary_conditions() {
        // Test various power-of-2 boundary conditions
        for tree_size in [1, 2, 4, 8, 16, 32] {
            let digests: Vec<Digest> = (0..tree_size as u32)
                .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
                .collect();

            // Build tree
            let mut builder = Builder::<Sha256>::new(digests.len());
            for digest in &digests {
                builder.add(digest);
            }
            let tree = builder.build();
            let root = tree.root();

            // Test edge cases
            // First element only
            let proof = tree.range_proof(0, 0).unwrap();
            assert!(
                proof
                    .verify_range_inclusion::<Sha256>(0, &digests[0..1], &root)
                    .is_ok()
            );

            // Last element only
            let last_idx = tree_size - 1;
            let proof = tree.range_proof(last_idx as u32, last_idx as u32).unwrap();
            assert!(
                proof
                    .verify_range_inclusion::<Sha256>(
                        last_idx as u32,
                        &digests[last_idx..tree_size],
                        &root
                    )
                    .is_ok()
            );

            // Full tree
            let proof = tree.range_proof(0, (tree_size - 1) as u32).unwrap();
            assert!(
                proof
                    .verify_range_inclusion::<Sha256>(0, &digests, &root)
                    .is_ok()
            );
        }
    }

    #[test]
    fn test_empty_tree_proof() {
        // Build an empty tree
        let builder = Builder::<Sha256>::new(0);
        let tree = builder.build();

        // Empty tree should fail for any position since there are no elements
        assert!(tree.proof(0).is_err());
        assert!(tree.proof(1).is_err());
        assert!(tree.proof(100).is_err());
    }

    #[test]
    fn test_empty_tree_range_proof() {
        // Build an empty tree
        let builder = Builder::<Sha256>::new(0);
        let tree = builder.build();
        let root = tree.root();

        // Empty tree should return default proof only for (0, 0)
        let range_proof = tree.range_proof(0, 0).unwrap();
        assert!(range_proof.siblings.is_empty());
        assert_eq!(range_proof, Proof::default());

        // All other combinations should fail
        let invalid_ranges = vec![
            (0, 1),
            (0, 10),
            (1, 1),
            (1, 2),
            (5, 5),
            (10, 10),
            (0, u32::MAX),
            (u32::MAX, u32::MAX),
        ];
        for (start, end) in invalid_ranges {
            assert!(tree.range_proof(start, end).is_err());
        }

        // Verify empty range proof against empty tree root
        let empty_leaves: &[Digest] = &[];
        assert!(
            range_proof
                .verify_range_inclusion::<Sha256>(0, empty_leaves, &root)
                .is_ok()
        );

        // Should fail with non-empty leaves
        let non_empty_leaves = vec![Sha256::hash(&[b"leaf"])];
        assert!(
            range_proof
                .verify_range_inclusion::<Sha256>(0, &non_empty_leaves, &root)
                .is_err()
        );

        // Should fail with wrong root
        let wrong_root = Sha256::hash(&[b"wrong"]);
        assert!(
            range_proof
                .verify_range_inclusion::<Sha256>(0, empty_leaves, &wrong_root)
                .is_err()
        );

        // Should fail with wrong position
        assert!(
            range_proof
                .verify_range_inclusion::<Sha256>(1, empty_leaves, &root)
                .is_err()
        );
    }

    #[test]
    fn test_empty_range_proof_serialization() {
        let proof = Proof::<Digest>::default();
        let mut serialized = proof.encode();
        let deserialized = Proof::<Digest>::decode_cfg(&mut serialized, &0).unwrap();
        assert_eq!(proof, deserialized);
    }

    #[test]
    fn test_empty_tree_root_consistency() {
        // Create multiple empty trees and verify they have the same root
        let mut roots = Vec::new();
        for _ in 0..5 {
            let builder = Builder::<Sha256>::new(0);
            let tree = builder.build();
            roots.push(tree.root());
        }

        // All empty trees should have the same root
        for i in 1..roots.len() {
            assert_eq!(roots[0], roots[i]);
        }

        // The root should be the hash of empty data
        let empty = Sha256::hash(&[b""]);
        let expected_root = Sha256::hash(&[&0u32.to_be_bytes(), &empty]);
        assert_eq!(roots[0], expected_root);
    }

    #[rstest]
    #[case::need_left_sibling(1, 2)] // Range starting at odd index (needs left sibling)
    #[case::need_right_sibling(4, 4)] // Range starting at even index
    #[case::full_tree(0, 16)] // Full tree (no siblings needed at leaf level)
    fn test_range_proof_siblings_usage(#[case] start: u32, #[case] count: u32) {
        // This test ensures that all siblings in a range proof are actually used during verification
        let digests: Vec<Digest> = (0..16u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        let range_proof = tree.range_proof(start, start + count - 1).unwrap();
        let end = start as usize + count as usize;

        // Verify the proof works
        assert!(
            range_proof
                .verify_range_inclusion::<Sha256>(start, &digests[start as usize..end], &root)
                .is_ok()
        );

        // For each sibling, try tampering with it and verify the proof fails
        for sibling_idx in 0..range_proof.siblings.len() {
            let mut tampered_proof = range_proof.clone();
            tampered_proof.siblings[sibling_idx] = Sha256::hash(&[b"tampered"]);
            assert!(
                tampered_proof
                    .verify_range_inclusion::<Sha256>(start, &digests[start as usize..end], &root)
                    .is_err()
            );
        }
    }

    // Test trees with odd sizes that require duplicate nodes
    #[rstest]
    fn test_range_proof_duplicate_node_edge_cases(
        #[values(3, 5, 7, 9, 11, 13, 15)] tree_size: usize,
    ) {
        let digests: Vec<Digest> = (0..tree_size as u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Test range including the last element (which may require duplicate handling)
        let start = tree_size - 2;
        let proof = tree
            .range_proof(start as u32, (tree_size - 1) as u32)
            .unwrap();
        assert!(
            proof
                .verify_range_inclusion::<Sha256>(start as u32, &digests[start..tree_size], &root)
                .is_ok()
        );
    }

    #[test]
    fn test_multi_proof_basic() {
        // Create test data
        let digests: Vec<Digest> = (0..8u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Test multi-proof for non-contiguous positions [0, 3, 5]
        let positions = [0, 3, 5];
        let multi_proof = tree.multi_proof(positions).unwrap();

        let elements: Vec<(Digest, u32)> = positions
            .iter()
            .map(|&p| (digests[p as usize], p))
            .collect();
        assert!(
            multi_proof
                .verify_multi_inclusion::<Sha256>(&elements, &root)
                .is_ok()
        );
    }

    #[test]
    fn test_multi_proof_single_element() {
        // Create test data
        let digests: Vec<Digest> = (0..8u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Test single element multi-proof for each position
        for (i, digest) in digests.iter().enumerate() {
            let multi_proof = tree.multi_proof([i as u32]).unwrap();
            let elements = [(*digest, i as u32)];
            assert!(
                multi_proof
                    .verify_multi_inclusion::<Sha256>(&elements, &root)
                    .is_ok(),
                "Failed for position {i}"
            );
        }
    }

    #[test]
    fn test_multi_proof_all_elements() {
        // Create test data
        let digests: Vec<Digest> = (0..8u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Test multi-proof for all elements
        let positions: Vec<u32> = (0..digests.len() as u32).collect();
        let multi_proof = tree.multi_proof(&positions).unwrap();

        let elements: Vec<(Digest, u32)> = positions
            .iter()
            .map(|&p| (digests[p as usize], p))
            .collect();
        assert!(
            multi_proof
                .verify_multi_inclusion::<Sha256>(&elements, &root)
                .is_ok()
        );

        // When proving all elements, we shouldn't need any siblings (all can be computed)
        assert!(multi_proof.siblings.is_empty());
    }

    #[test]
    fn test_multi_proof_adjacent_elements() {
        // Create test data
        let digests: Vec<Digest> = (0..8u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Test adjacent positions (should deduplicate shared siblings)
        let positions = [2, 3];
        let multi_proof = tree.multi_proof(positions).unwrap();

        let elements: Vec<(Digest, u32)> = positions
            .iter()
            .map(|&p| (digests[p as usize], p))
            .collect();
        assert!(
            multi_proof
                .verify_multi_inclusion::<Sha256>(&elements, &root)
                .is_ok()
        );
    }

    #[test]
    fn test_multi_proof_sparse_positions() {
        // Create test data
        let digests: Vec<Digest> = (0..16u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Test widely separated positions
        let positions = [0, 7, 8, 15];
        let multi_proof = tree.multi_proof(positions).unwrap();

        let elements: Vec<(Digest, u32)> = positions
            .iter()
            .map(|&p| (digests[p as usize], p))
            .collect();
        assert!(
            multi_proof
                .verify_multi_inclusion::<Sha256>(&elements, &root)
                .is_ok()
        );
    }

    #[test]
    fn test_multi_proof_empty_tree() {
        // Build empty tree
        let builder = Builder::<Sha256>::new(0);
        let tree = builder.build();

        // Empty tree with empty positions should return NoLeaves error
        // (we can't prove zero elements)
        assert!(matches!(
            tree.multi_proof(std::iter::empty::<u32>()),
            Err(Error::NoLeaves)
        ));

        // Empty tree with any position should fail with InvalidPosition
        assert!(matches!(
            tree.multi_proof([0]),
            Err(Error::InvalidPosition(0))
        ));
    }

    #[test]
    fn test_multi_proof_empty_positions() {
        // Create test data
        let digests: Vec<Digest> = (0..8u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();

        // Empty positions should return error
        assert!(matches!(
            tree.multi_proof(std::iter::empty::<u32>()),
            Err(Error::NoLeaves)
        ));
    }

    #[test]
    fn test_multi_proof_duplicate_positions_error() {
        // Create test data
        let digests: Vec<Digest> = (0..8u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();

        // Duplicate positions should return error
        assert!(matches!(
            tree.multi_proof([1, 1]),
            Err(Error::DuplicatePosition(1))
        ));
        assert!(matches!(
            tree.multi_proof([0, 2, 2, 5]),
            Err(Error::DuplicatePosition(2))
        ));
    }

    #[test]
    fn test_multi_proof_reports_first_invalid_position() {
        // Build a tree with four leaves
        let digests: Vec<Digest> = (0..4u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();

        // Each position is checked against the previous one in input order, so the
        // first out-of-range, repeated, or descending position is reported even
        // when a later one would sort first.
        let cases = [
            (vec![], Error::NoLeaves),
            (vec![0, 0, 4], Error::DuplicatePosition(0)),
            (vec![4, 0, 0], Error::InvalidPosition(4)),
            (vec![3, 4], Error::InvalidPosition(4)),
            (vec![3, 1, 1, 3], Error::UnsortedPosition(1)),
            (vec![1, 3, 3, 1], Error::DuplicatePosition(3)),
            (vec![0, 1, 2, 3, 0, 4], Error::UnsortedPosition(0)),
            (vec![0, 1, 2, 3, 4, 0], Error::InvalidPosition(4)),
        ];

        // Verification checks positions the same way before hashing anything, so
        // any proof from this tree must report the same errors.
        let proof = tree.multi_proof([0, 3]).unwrap();
        let root = tree.root();
        for (positions, expected) in cases {
            let result = tree.multi_proof(&positions);
            assert_eq!(
                format!("{:?}", result.err()),
                format!("{:?}", Some(&expected)),
                "multi_proof({positions:?}) must report the first invalid position"
            );

            let elements: Vec<_> = positions.iter().map(|&p| (digests[0], p)).collect();
            let result = proof.verify_multi_inclusion::<Sha256>(&elements, &root);
            assert_eq!(
                format!("{:?}", result.err()),
                format!("{:?}", Some(&expected)),
                "verify_multi_inclusion({positions:?}) must report the first invalid position"
            );
        }
    }

    #[test]
    fn test_multi_proof_stops_reading_at_first_invalid_position() {
        // Reading stops at the first invalid position, so an endless iterator is
        // rejected after its first repeat, descent, or out-of-range position.
        let mut read = 0;
        let result =
            siblings_required_for_multi_proof(3, core::iter::repeat(0).inspect(|_| read += 1));
        assert!(matches!(result, Err(Error::DuplicatePosition(0))));
        assert_eq!(read, 2);

        let mut read = 0;
        let result = siblings_required_for_multi_proof(3, (0..3).cycle().inspect(|_| read += 1));
        assert!(matches!(result, Err(Error::UnsortedPosition(0))));
        assert_eq!(read, 4);

        let mut read = 0;
        let result = siblings_required_for_multi_proof(
            u32::MAX,
            core::iter::repeat(u32::MAX).inspect(|_| read += 1),
        );
        assert!(matches!(result, Err(Error::InvalidPosition(u32::MAX))));
        assert_eq!(read, 1);

        // The public API also stops at the first repeat.
        let mut builder = Builder::<Sha256>::new(3);
        for i in 0..3u32 {
            builder.add(&Sha256::hash(&[&i.to_be_bytes()]));
        }
        let tree = builder.build();
        assert!(matches!(
            tree.multi_proof(core::iter::repeat(2u32)),
            Err(Error::DuplicatePosition(2))
        ));
    }

    #[test]
    fn test_multi_proof_unsorted_input() {
        // Create test data
        let digests: Vec<Digest> = (0..8u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Positions must be ascending for generation, so the first descent is
        // rejected
        assert!(matches!(
            tree.multi_proof([5, 0, 3]),
            Err(Error::UnsortedPosition(0))
        ));
        let multi_proof = tree.multi_proof([0, 3, 5]).unwrap();

        // Verification requires the same order
        let unsorted_elements = [(digests[5], 5), (digests[0], 0), (digests[3], 3)];
        assert!(matches!(
            multi_proof.verify_multi_inclusion::<Sha256>(&unsorted_elements, &root),
            Err(Error::UnsortedPosition(0))
        ));
        let sorted_elements = [(digests[0], 0), (digests[3], 3), (digests[5], 5)];
        assert!(
            multi_proof
                .verify_multi_inclusion::<Sha256>(&sorted_elements, &root)
                .is_ok()
        );
    }

    #[test]
    fn test_multi_proof_various_sizes() {
        // Test multi-proofs for trees of various sizes
        for tree_size in [1, 2, 3, 4, 5, 7, 8, 15, 16, 31, 32] {
            let digests: Vec<Digest> = (0..tree_size as u32)
                .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
                .collect();

            // Build tree
            let mut builder = Builder::<Sha256>::new(digests.len());
            for digest in &digests {
                builder.add(digest);
            }
            let tree = builder.build();
            let root = tree.root();

            // Test various position combinations
            // First and last
            if tree_size >= 2 {
                let positions = [0, (tree_size - 1) as u32];
                let multi_proof = tree.multi_proof(positions).unwrap();
                let elements: Vec<(Digest, u32)> = positions
                    .iter()
                    .map(|&p| (digests[p as usize], p))
                    .collect();
                assert!(
                    multi_proof
                        .verify_multi_inclusion::<Sha256>(&elements, &root)
                        .is_ok(),
                    "Failed for tree_size={tree_size}, positions=[0, {}]",
                    tree_size - 1
                );
            }

            // Every other element
            if tree_size >= 4 {
                let positions: Vec<u32> = (0..tree_size as u32).step_by(2).collect();
                let multi_proof = tree.multi_proof(&positions).unwrap();
                let elements: Vec<(Digest, u32)> = positions
                    .iter()
                    .map(|&p| (digests[p as usize], p))
                    .collect();
                assert!(
                    multi_proof
                        .verify_multi_inclusion::<Sha256>(&elements, &root)
                        .is_ok(),
                    "Failed for tree_size={tree_size}, every other element"
                );
            }
        }
    }

    #[test]
    fn test_multi_proof_wrong_elements() {
        // Create test data
        let digests: Vec<Digest> = (0..8u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Generate valid proof
        let positions = [0, 3, 5];
        let multi_proof = tree.multi_proof(positions).unwrap();

        // Verify with wrong elements
        let wrong_elements = [
            (Sha256::hash(&[b"wrong1"]), 0),
            (digests[3], 3),
            (digests[5], 5),
        ];
        assert!(
            multi_proof
                .verify_multi_inclusion::<Sha256>(&wrong_elements, &root)
                .is_err()
        );
    }

    #[test]
    fn test_multi_proof_wrong_positions() {
        // Create test data
        let digests: Vec<Digest> = (0..8u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Generate valid proof
        let positions = [0, 3, 5];
        let multi_proof = tree.multi_proof(positions).unwrap();

        // Verify with wrong positions (same elements, different positions)
        let wrong_positions = [
            (digests[0], 1), // wrong position
            (digests[3], 3),
            (digests[5], 5),
        ];
        assert!(
            multi_proof
                .verify_multi_inclusion::<Sha256>(&wrong_positions, &root)
                .is_err()
        );
    }

    #[test]
    fn test_multi_proof_wrong_root() {
        // Create test data
        let digests: Vec<Digest> = (0..8u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();

        // Generate valid proof
        let positions = [0, 3, 5];
        let multi_proof = tree.multi_proof(positions).unwrap();

        let elements: Vec<(Digest, u32)> = positions
            .iter()
            .map(|&p| (digests[p as usize], p))
            .collect();

        // Verify with wrong root
        let wrong_root = Sha256::hash(&[b"wrong_root"]);
        assert!(
            multi_proof
                .verify_multi_inclusion::<Sha256>(&elements, &wrong_root)
                .is_err()
        );
    }

    #[test]
    fn test_multi_proof_tampering() {
        // Create test data
        let digests: Vec<Digest> = (0..8u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Generate valid proof
        let positions = [0, 5];
        let multi_proof = tree.multi_proof(positions).unwrap();

        let elements: Vec<(Digest, u32)> = positions
            .iter()
            .map(|&p| (digests[p as usize], p))
            .collect();

        // Tamper with sibling
        assert!(!multi_proof.siblings.is_empty());
        let mut modified = multi_proof.clone();
        modified.siblings[0] = Sha256::hash(&[b"tampered"]);
        assert!(
            modified
                .verify_multi_inclusion::<Sha256>(&elements, &root)
                .is_err()
        );

        // Add extra sibling
        let mut extra = multi_proof.clone();
        extra.siblings.push(Sha256::hash(&[b"extra"]));
        assert!(
            extra
                .verify_multi_inclusion::<Sha256>(&elements, &root)
                .is_err()
        );

        // Remove a sibling
        let mut missing = multi_proof;
        missing.siblings.pop();
        assert!(
            missing
                .verify_multi_inclusion::<Sha256>(&elements, &root)
                .is_err()
        );
    }

    #[test]
    fn test_multi_proof_deduplication() {
        // Create test data
        let digests: Vec<Digest> = (0..16u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();

        // Get individual proofs
        let individual_siblings: usize = [0u32, 1, 8, 9]
            .iter()
            .map(|&p| tree.proof(p).unwrap().siblings.len())
            .sum();

        // Get multi-proof for same positions
        let multi_proof = tree.multi_proof([0, 1, 8, 9]).unwrap();

        // Multi-proof should have fewer siblings due to deduplication
        assert!(
            multi_proof.siblings.len() < individual_siblings,
            "Multi-proof ({}) should have fewer siblings than sum of individual proofs ({})",
            multi_proof.siblings.len(),
            individual_siblings
        );
    }

    #[test]
    fn test_multi_proof_serialization() {
        // Create test data
        let digests: Vec<Digest> = (0..8u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Generate proof
        let positions = [0, 3, 5];
        let multi_proof = tree.multi_proof(positions).unwrap();

        // Serialize and deserialize
        let serialized = multi_proof.encode();
        let deserialized = Proof::<Digest>::decode_cfg(serialized, &positions.len()).unwrap();

        assert_eq!(multi_proof, deserialized);

        // Verify deserialized proof works
        let elements: Vec<(Digest, u32)> = positions
            .iter()
            .map(|&p| (digests[p as usize], p))
            .collect();
        assert!(
            deserialized
                .verify_multi_inclusion::<Sha256>(&elements, &root)
                .is_ok()
        );
    }

    #[test]
    fn test_multi_proof_serialization_truncated() {
        // Create test data
        let digests: Vec<Digest> = (0..8u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();

        // Generate proof
        let positions = [0, 3, 5];
        let multi_proof = tree.multi_proof(positions).unwrap();

        // Serialize and truncate
        let mut serialized = multi_proof.encode();
        serialized.truncate(serialized.len() - 1);

        // Should fail to deserialize
        assert!(Proof::<Digest>::decode_cfg(&mut serialized, &positions.len()).is_err());
    }

    #[test]
    fn test_multi_proof_serialization_extra() {
        // Create test data
        let digests: Vec<Digest> = (0..8u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();

        // Generate proof
        let positions = [0, 3, 5];
        let multi_proof = tree.multi_proof(positions).unwrap();

        // Serialize and add extra byte
        let mut serialized = multi_proof.encode_mut();
        serialized.extend_from_slice(&[0u8]);

        // Should fail to deserialize
        assert!(Proof::<Digest>::decode_cfg(&mut serialized, &positions.len()).is_err());
    }

    #[test]
    fn test_multi_proof_decode_insufficient_data() {
        let mut serialized = Vec::new();
        serialized.extend_from_slice(&8u32.encode()); // leaf_count
        serialized.extend_from_slice(&1usize.encode()); // claims 1 sibling but no data follows

        // Should fail because the buffer claims 1 sibling but doesn't have the data
        let err = Proof::<Digest>::decode_cfg(serialized, &1).unwrap_err();
        assert!(matches!(err, commonware_codec::Error::EndOfBuffer));
    }

    #[test]
    fn test_multi_proof_invalid_position() {
        // Create test data
        let digests: Vec<Digest> = (0..8u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();

        // Test out of bounds position
        assert!(matches!(
            tree.multi_proof([0, 8]),
            Err(Error::InvalidPosition(8))
        ));
        assert!(matches!(
            tree.multi_proof([100]),
            Err(Error::InvalidPosition(100))
        ));
    }

    #[test]
    fn test_multi_proof_verify_invalid_position() {
        // Create test data
        let digests: Vec<Digest> = (0..8u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        // Build tree
        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Generate valid proof
        let positions = [0, 3];
        let multi_proof = tree.multi_proof(positions).unwrap();

        // Try to verify with out of bounds position
        let invalid_elements = [(digests[0], 0), (digests[3], 100)];
        assert!(
            multi_proof
                .verify_multi_inclusion::<Sha256>(&invalid_elements, &root)
                .is_err()
        );
    }

    #[test]
    fn test_multi_proof_odd_tree_sizes() {
        // Test odd-sized trees that require node duplication
        for tree_size in [3, 5, 7, 9, 11, 13, 15] {
            let digests: Vec<Digest> = (0..tree_size as u32)
                .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
                .collect();

            // Build tree
            let mut builder = Builder::<Sha256>::new(digests.len());
            for digest in &digests {
                builder.add(digest);
            }
            let tree = builder.build();
            let root = tree.root();

            // Test with positions including the last element
            let positions = [0, (tree_size - 1) as u32];
            let multi_proof = tree.multi_proof(positions).unwrap();

            let elements: Vec<(Digest, u32)> = positions
                .iter()
                .map(|&p| (digests[p as usize], p))
                .collect();
            assert!(
                multi_proof
                    .verify_multi_inclusion::<Sha256>(&elements, &root)
                    .is_ok(),
                "Failed for tree_size={tree_size}"
            );
        }
    }

    #[test]
    fn test_multi_proof_verify_empty_elements() {
        // Create a valid proof and try to verify with empty elements
        let digests: Vec<Digest> = (0..8u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Generate valid proof
        let positions = [0, 3];
        let multi_proof = tree.multi_proof(positions).unwrap();

        // Try to verify with empty elements
        let empty_elements: &[(Digest, u32)] = &[];
        assert!(
            multi_proof
                .verify_multi_inclusion::<Sha256>(empty_elements, &root)
                .is_err()
        );
    }

    #[test]
    fn test_multi_proof_default_verify() {
        // Default (empty) proof should only verify against empty tree
        let default_proof = Proof::<Digest>::default();

        // Empty elements against default proof
        let empty_elements: &[(Digest, u32)] = &[];

        // Build empty tree to get the empty root
        let builder = Builder::<Sha256>::new(0);
        let empty_tree = builder.build();
        let empty_root = empty_tree.root();

        assert!(
            default_proof
                .verify_multi_inclusion::<Sha256>(empty_elements, &empty_root)
                .is_ok()
        );

        // Should fail with wrong root
        let wrong_root = Sha256::hash(&[b"not_empty"]);
        assert!(
            default_proof
                .verify_multi_inclusion::<Sha256>(empty_elements, &wrong_root)
                .is_err()
        );
    }

    #[test]
    fn test_multi_proof_single_leaf_tree() {
        // Edge case: tree with exactly one leaf
        let digest = Sha256::hash(&[b"only_leaf"]);

        // Build single-leaf tree
        let mut builder = Builder::<Sha256>::new(1);
        builder.add(&digest);
        let tree = builder.build();
        let root = tree.root();

        // Generate multi-proof for the only leaf
        let multi_proof = tree.multi_proof([0]).unwrap();

        // Single leaf tree: leaf_count should be 1
        assert_eq!(multi_proof.leaf_count, 1);

        // Single leaf tree: no siblings needed (leaf is the root after position hashing)
        assert!(
            multi_proof.siblings.is_empty(),
            "Single leaf tree should have no siblings"
        );

        // Verify the proof
        let elements = [(digest, 0u32)];
        assert!(
            multi_proof
                .verify_multi_inclusion::<Sha256>(&elements, &root)
                .is_ok(),
            "Single leaf multi-proof verification failed"
        );

        // Verify with wrong digest fails
        let wrong_digest = Sha256::hash(&[b"wrong"]);
        let wrong_elements = [(wrong_digest, 0u32)];
        assert!(
            multi_proof
                .verify_multi_inclusion::<Sha256>(&wrong_elements, &root)
                .is_err(),
            "Should fail with wrong digest"
        );

        // Verify with wrong position fails
        let wrong_position_elements = [(digest, 1u32)];
        assert!(
            multi_proof
                .verify_multi_inclusion::<Sha256>(&wrong_position_elements, &root)
                .is_err(),
            "Should fail with invalid position"
        );
    }

    #[test]
    fn test_multi_proof_malicious_leaf_count_zero() {
        // Attacker sets leaf_count = 0 but provides siblings
        let digests: Vec<Digest> = (0..8u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Generate valid proof and tamper with leaf_count
        let positions = [0, 3];
        let mut multi_proof = tree.multi_proof(positions).unwrap();
        multi_proof.leaf_count = 0;

        let elements: Vec<(Digest, u32)> = positions
            .iter()
            .map(|&p| (digests[p as usize], p))
            .collect();

        // Should fail because leaf_count=0 but there are elements
        assert!(
            multi_proof
                .verify_multi_inclusion::<Sha256>(&elements, &root)
                .is_err()
        );
    }

    #[test]
    fn test_multi_proof_malicious_leaf_count_larger() {
        // Attacker inflates leaf_count to claim proof is for larger tree
        let digests: Vec<Digest> = (0..8u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Generate valid proof and inflate leaf_count
        let positions = [0, 3];
        let mut multi_proof = tree.multi_proof(positions).unwrap();
        let original_leaf_count = multi_proof.leaf_count;
        multi_proof.leaf_count = 1000;

        let elements: Vec<(Digest, u32)> = positions
            .iter()
            .map(|&p| (digests[p as usize], p))
            .collect();

        // Should fail because an inflated leaf_count changes the required siblings
        assert!(
            multi_proof
                .verify_multi_inclusion::<Sha256>(&elements, &root)
                .is_err(),
            "Should reject proof with inflated leaf_count ({} -> {})",
            original_leaf_count,
            multi_proof.leaf_count
        );
    }

    #[test]
    fn test_multi_proof_malicious_leaf_count_smaller() {
        // Attacker deflates leaf_count to claim proof is for smaller tree
        let digests: Vec<Digest> = (0..8u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Generate valid proof and deflate leaf_count
        let positions = [0, 3];
        let mut multi_proof = tree.multi_proof(positions).unwrap();
        multi_proof.leaf_count = 4; // Smaller than actual tree

        let elements: Vec<(Digest, u32)> = positions
            .iter()
            .map(|&p| (digests[p as usize], p))
            .collect();

        // Should fail because a deflated leaf_count changes the tree structure
        assert!(
            multi_proof
                .verify_multi_inclusion::<Sha256>(&elements, &root)
                .is_err(),
            "Should reject proof with deflated leaf_count"
        );
    }

    #[test]
    fn test_multi_proof_mismatched_element_count() {
        // Provide more or fewer elements than the proof was generated for
        let digests: Vec<Digest> = (0..8u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Generate proof for 2 positions
        let positions = [0, 3];
        let multi_proof = tree.multi_proof(positions).unwrap();

        // Try to verify with only 1 element (too few)
        let too_few = [(digests[0], 0u32)];
        assert!(
            multi_proof
                .verify_multi_inclusion::<Sha256>(&too_few, &root)
                .is_err(),
            "Should reject when fewer elements provided than proof was generated for"
        );

        // Try to verify with 3 elements (too many)
        let too_many = [(digests[0], 0u32), (digests[3], 3), (digests[5], 5)];
        assert!(
            multi_proof
                .verify_multi_inclusion::<Sha256>(&too_many, &root)
                .is_err(),
            "Should reject when more elements provided than proof was generated for"
        );
    }

    #[test]
    fn test_multi_proof_swapped_siblings() {
        // Swap the order of siblings in the proof
        let digests: Vec<Digest> = (0..8u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Generate valid proof with multiple siblings
        let positions = [0, 5];
        let mut multi_proof = tree.multi_proof(positions).unwrap();

        // Ensure we have at least 2 siblings to swap
        if multi_proof.siblings.len() >= 2 {
            // Swap first two siblings
            multi_proof.siblings.swap(0, 1);

            let elements: Vec<(Digest, u32)> = positions
                .iter()
                .map(|&p| (digests[p as usize], p))
                .collect();

            assert!(
                multi_proof
                    .verify_multi_inclusion::<Sha256>(&elements, &root)
                    .is_err(),
                "Should reject proof with swapped siblings"
            );
        }
    }

    #[test]
    fn test_multi_proof_dos_large_leaf_count() {
        // Attacker sets massive leaf_count trying to cause DoS via memory allocation
        // The verify function should NOT allocate proportional to leaf_count
        let digests: Vec<Digest> = (0..4u32)
            .map(|i| Sha256::hash(&[&i.to_be_bytes()]))
            .collect();

        let mut builder = Builder::<Sha256>::new(digests.len());
        for digest in &digests {
            builder.add(digest);
        }
        let tree = builder.build();
        let root = tree.root();

        // Generate valid proof
        let positions = [0, 2];
        let mut multi_proof = tree.multi_proof(positions).unwrap();

        // Set massive leaf_count (attacker trying to exhaust memory)
        multi_proof.leaf_count = u32::MAX;

        let elements: Vec<(Digest, u32)> = positions
            .iter()
            .map(|&p| (digests[p as usize], p))
            .collect();

        // This should fail quickly without allocating massive memory
        // The function is O(elements * levels), not O(leaf_count)
        let result = multi_proof.verify_multi_inclusion::<Sha256>(&elements, &root);
        assert!(result.is_err(), "Should reject malicious large leaf_count");
    }

    #[cfg(feature = "arbitrary")]
    mod conformance {
        use super::*;
        use commonware_codec::conformance::CodecConformance;
        use commonware_conformance::Conformance;
        use commonware_cryptography::sha256::Digest as Sha256Digest;

        fn test_merkle_tree(n: usize) -> Digest {
            // Build tree
            let mut digests = Vec::with_capacity(n);
            let mut builder = Builder::<Sha256>::new(n);
            for i in 0..n {
                let digest = Sha256::hash(&[&i.to_be_bytes()]);
                builder.add(&digest);
                digests.push(digest);
            }
            let tree = builder.build();
            let root = tree.root();

            // For each leaf, generate and verify its proof
            for (i, leaf) in digests.iter().enumerate() {
                // Generate proof
                let proof = tree.proof(i as u32).unwrap();
                assert!(
                    proof
                        .verify_element_inclusion::<Sha256>(leaf, i as u32, &root)
                        .is_ok(),
                    "correct fail for size={n} leaf={i}"
                );

                // Serialize and deserialize the proof
                let serialized = proof.encode();
                let deserialized = Proof::<Digest>::decode_cfg(serialized, &1).unwrap();
                assert!(
                    deserialized
                        .verify_element_inclusion::<Sha256>(leaf, i as u32, &root)
                        .is_ok(),
                    "deserialize fail for size={n} leaf={i}"
                );

                // Modify a sibling hash and ensure the proof fails
                if !proof.siblings.is_empty() {
                    let mut update_tamper = proof.clone();
                    update_tamper.siblings[0] = Sha256::hash(&[b"tampered"]);
                    assert!(
                        update_tamper
                            .verify_element_inclusion::<Sha256>(leaf, i as u32, &root)
                            .is_err(),
                        "modify fail for size={n} leaf={i}"
                    );
                }

                // Add a sibling hash and ensure the proof fails
                let mut add_tamper = proof.clone();
                add_tamper.siblings.push(Sha256::hash(&[b"tampered"]));
                assert!(
                    add_tamper
                        .verify_element_inclusion::<Sha256>(leaf, i as u32, &root)
                        .is_err(),
                    "add fail for size={n} leaf={i}"
                );

                // Remove a sibling hash and ensure the proof fails
                if !proof.siblings.is_empty() {
                    let mut remove_tamper = proof.clone();
                    remove_tamper.siblings.pop();
                    assert!(
                        remove_tamper
                            .verify_element_inclusion::<Sha256>(leaf, i as u32, &root)
                            .is_err(),
                        "remove fail for size={n} leaf={i}"
                    );
                }
            }

            // Test proof for larger than size
            assert!(tree.proof(n as u32).is_err());

            // Return the root so we can ensure we don't silently change.
            root
        }

        struct RootConformance;

        impl Conformance for RootConformance {
            async fn commit(seed: u64) -> Vec<u8> {
                let root = test_merkle_tree(seed as usize);
                root.to_vec()
            }
        }

        commonware_conformance::conformance_tests! {
            CodecConformance<Proof<Sha256Digest>>,
            RootConformance => 200
        }
    }
}