commonware_storage/qmdb/current/proof/

mod.rs

//! Proof types for [crate::qmdb::current] authenticated databases.
//!
//! This module provides:
//! - [OpsRootWitness]: Authenticates an ops root against a canonical `current` root.
//! - [RangeProof]: Proves a range of operations exist in the database.
//! - [constant::OperationProof]: Proves a specific operation is active, with a fixed-size bitmap chunk.
//! - [dynamic::OperationProof]: Uses a bitmap chunk size supplied when decoding.
//!
//! # Canonical root structure
//!
//! ```text
//! canonical_root = hash(
//!     ops_root
//!     || grafted_root
//!     [|| pending_chunk_digest]
//!     [|| next_bit_be || partial_chunk_digest]
//! )
//! ```
//!
//! - `ops_root` is the root of the operations tree (MMR or MMB).
//! - `grafted_root` commits to the activity bitmap's **graftable** chunks (chunks whose height-G
//!   ancestor has been born in the ops tree).
//! - `pending_chunk_digest` is `H(pending_bytes)` if a chunk is bit-complete in the bitmap but its
//!   h=G ancestor has not yet been born; absent otherwise.
//! - `(next_bit_be, partial_chunk_digest)` covers the trailing partial chunk when the bitmap length
//!   is not chunk-aligned; both elements are absent when it is.
//!
//! Both `ops_root` and `grafted_root` are computed by
//! [`Hasher::root`](crate::merkle::hasher::Hasher::root), so each commits the ops tree's family and
//! bagging policy.
//!
//! Pending and partial slots are independent: at gh >= 3 they can coexist. When both are present,
//! pending hashes in before partial.

use crate::{
    journal::contiguous::Contiguous,
    merkle::{
        self, Family, Graftable, Location, PendingChunk, Position, Proof, hasher::Hasher as _,
        storage::Storage,
    },
    qmdb::{
        self, Error,
        current::{
            db::{combine_roots, graftable_chunk_window, partial_chunk, pending_chunk},
            grafting,
        },
    },
};
use ahash::AHashMap;
use bytes::BufMut;
use commonware_codec::{Buf, Encode, EncodeSize, Read, ReadExt as _, Write, varint::UInt};
use commonware_cryptography::{Digest, Hasher};
use commonware_utils::{
    Widen,
    bitmap::{Prunable as BitMap, Readable as BitmapReadable},
};
use core::{num::NonZeroU64, ops::Range};
use tracing::debug;

pub mod operation;

/// Validate the chunk width before deriving bitmap indices or Merkle heights.
pub(super) fn chunk_bits(chunk_size: usize) -> Result<u64, commonware_codec::Error> {
    chunk_size
        .checked_mul(8)
        .map(|bits| -> u64 { Widen::widen(bits) })
        .filter(|bits| bits.is_power_of_two() && bits.trailing_zeros() < 63)
        .ok_or(commonware_codec::Error::Invalid(
            "current proof",
            "invalid bitmap chunk size",
        ))
}

/// Bitmap chunk indices read by [RangeProof::new] or [constant::OperationProof::new].
///
/// Pass `None` for a range proof or the queried operation location for an operation proof.
/// The returned indices are unique and increasing. At most three chunks are needed: the
/// trailing partial chunk, a complete chunk awaiting its ops-tree ancestor, and the queried
/// operation's chunk. This allows a storage adapter to preload bitmap bytes before exposing a
/// synchronous [BitmapReadable] implementation.
///
/// `ops_leaves`, `bitmap_len`, and `pruned_chunks` must describe one consistent snapshot.
/// `N` is the bitmap chunk size in bytes and must be a nonzero power of two.
///
/// # Errors
///
/// Returns [Error::DataCorrupted] if more than one complete chunk awaits its ancestor or
/// pruning exceeds the graftable prefix. Returns [Error::OperationPruned] for a queried
/// operation in a pruned chunk, and [merkle::Error::RangeOutOfBounds] for a queried operation
/// outside the snapshot.
pub fn required_chunks<F: Graftable, const N: usize>(
    ops_leaves: Location<F>,
    bitmap_len: u64,
    pruned_chunks: u64,
    location: Option<Location<F>>,
) -> Result<impl Iterator<Item = u64>, Error<F>> {
    const { assert!(N.is_power_of_two() && N <= usize::MAX / 8) };
    let chunk_bits = BitMap::<N>::CHUNK_SIZE_BITS;
    let complete = bitmap_len / chunk_bits;
    let graftable =
        graftable_chunk_window(ops_leaves, complete, pruned_chunks, grafting::height::<N>())?;
    let queried = if let Some(loc) = location {
        if loc >= ops_leaves || *loc >= bitmap_len {
            return Err(merkle::Error::RangeOutOfBounds(loc).into());
        }
        let chunk = *loc / chunk_bits;
        if chunk < pruned_chunks {
            return Err(Error::OperationPruned(loc));
        }
        Some(chunk)
    } else {
        None
    };
    let mut chunks = [
        (!bitmap_len.is_multiple_of(chunk_bits)).then_some(complete),
        (complete > graftable).then_some(graftable),
        queried,
    ];
    chunks.sort_unstable();
    let mut previous = None;
    Ok(chunks.into_iter().flatten().filter(move |&chunk| {
        let distinct = previous != Some(chunk);
        previous = Some(chunk);
        distinct
    }))
}

/// Witness that a particular `ops_root` is committed by a `current` canonical root.
///
/// See the [Canonical root structure](self#canonical-root-structure) section in the module
/// documentation for the full layout.
#[derive(Clone, Eq, PartialEq, Debug)]
pub struct OpsRootWitness<F: Graftable, D: Digest> {
    /// The grafted-tree root committed by the canonical root.
    pub grafted_root: D,

    /// The pending-chunk contribution, if any.
    pub pending_chunk_digest: F::PendingChunk<D>,

    /// The trailing partial chunk contribution, if the bitmap length is not chunk-aligned:
    /// `(next_bit, partial_chunk_digest)`.
    pub partial_chunk: Option<(u64, D)>,
}

impl<F: Graftable, D: Digest> OpsRootWitness<F, D> {
    /// Compute the canonical `current` root that commits to `ops_root` through this witness.
    ///
    /// See the [Canonical root structure](self#canonical-root-structure) section in the module
    /// documentation for the full layout.
    pub fn root<H: Hasher<Digest = D>>(&self, ops_root: &D) -> D {
        let partial = self.partial_chunk.as_ref().map(|(nb, d)| (*nb, d));
        combine_roots::<H>(
            ops_root,
            &self.grafted_root,
            self.pending_chunk_digest.as_ref(),
            partial,
        )
    }

    /// Return true if this witness proves that `root` commits to `ops_root`.
    pub fn verify<H: Hasher<Digest = D>>(&self, ops_root: &D, root: &D) -> bool {
        self.root::<H>(ops_root) == *root
    }
}

impl<F: Graftable, D: Digest> Write for OpsRootWitness<F, D> {
    fn write(&self, buf: &mut impl BufMut) {
        self.grafted_root.write(buf);
        self.pending_chunk_digest.write(buf);
        self.partial_chunk.is_some().write(buf);
        if let Some((next_bit, digest)) = &self.partial_chunk {
            UInt(*next_bit).write(buf);
            digest.write(buf);
        }
    }
}

impl<F: Graftable, D: Digest> EncodeSize for OpsRootWitness<F, D> {
    fn encode_size(&self) -> usize {
        self.grafted_root.encode_size()
            + self.pending_chunk_digest.encode_size()
            + self
                .partial_chunk
                .as_ref()
                .map_or(1, |(nb, d)| 1 + UInt(*nb).encode_size() + d.encode_size())
    }
}

impl<F: Graftable, D: Digest> Read for OpsRootWitness<F, D> {
    type Cfg = ();

    fn read_cfg(buf: &mut impl Buf, _: &Self::Cfg) -> Result<Self, commonware_codec::Error> {
        let grafted_root = D::read(buf)?;
        let pending_chunk_digest = F::PendingChunk::<D>::read(buf)?;
        let partial_chunk = if bool::read(buf)? {
            let next_bit = UInt::<u64>::read(buf)?.into();
            let digest = D::read(buf)?;
            Some((next_bit, digest))
        } else {
            None
        };
        Ok(Self {
            grafted_root,
            pending_chunk_digest,
            partial_chunk,
        })
    }
}

#[cfg(feature = "arbitrary")]
impl<F: Graftable, D: Digest> arbitrary::Arbitrary<'_> for OpsRootWitness<F, D>
where
    D: for<'a> arbitrary::Arbitrary<'a>,
    F::PendingChunk<D>: for<'a> arbitrary::Arbitrary<'a>,
{
    fn arbitrary(u: &mut arbitrary::Unstructured<'_>) -> arbitrary::Result<Self> {
        Ok(Self {
            grafted_root: u.arbitrary()?,
            pending_chunk_digest: u.arbitrary()?,
            partial_chunk: u.arbitrary()?,
        })
    }
}

/// A proof that a range of operations exist in the database.
#[derive(Clone, Eq, PartialEq, Debug)]
pub struct RangeProof<F: Graftable, D: Digest> {
    /// The Merkle digest material required to verify the proof.
    pub proof: Proof<F, D>,

    /// The pending-chunk contribution, if any.
    pub pending_chunk_digest: F::PendingChunk<D>,

    /// Digest of the bitmap's trailing partial chunk, if any.
    pub partial_chunk_digest: Option<D>,

    /// The ops-tree root digest.
    pub ops_root: D,
}

/// Parameters that identify the operation span and snapshot used to build a range proof.
#[derive(Clone, Copy, Eq, PartialEq, Debug)]
pub struct RangeProofSpec<F: Family, D: Digest> {
    /// First operation location to prove.
    pub start_loc: Location<F>,

    /// Maximum number of operations to include.
    pub max_ops: NonZeroU64,

    /// Inactivity floor used to fold old inactive peaks.
    pub inactivity_floor: Location<F>,

    /// The ops-tree root at the time of proof generation.
    pub ops_root: D,
}

impl<F: Graftable, D: Digest> RangeProof<F, D> {
    /// Create a new range proof for the provided `range` of operations, fetching the digests of
    /// its [merkle::RangePlan] from `storage` and building with [Self::build].
    pub async fn new<H: Hasher<Digest = D>, S: Storage<F, Digest = D>, const N: usize>(
        status: &impl BitmapReadable<N>,
        storage: &S,
        inactivity_floor: Location<F>,
        range: Range<Location<F>>,
        ops_root: D,
    ) -> Result<Self, Error<F>> {
        let ops_leaves = Location::try_from(storage.size())?;
        let plan = merkle::RangePlan::new(ops_leaves, range)?;
        let positions = plan.positions();
        let digests = storage.get_nodes(&positions).await?;
        let fetched: AHashMap<_, _> = positions.into_iter().zip(digests).collect();
        Self::build::<H, N>(
            status,
            plan,
            |pos| fetched.get(&pos).copied(),
            inactivity_floor,
            ops_root,
        )
    }

    /// Build the range proof planned by `plan` from digests already in memory.
    ///
    /// `get_node` supplies the digest at each of the plan's positions as the grafted view of the
    /// ops tree serves them, like [crate::qmdb::current::db::Db::grafted_storage]: plain ops-tree
    /// digests below the grafting height and bitmap-authenticated grafted digests at and above it.
    /// `status` supplies the bitmap chunks of [required_chunks]. The plan's leaf count, the digests,
    /// `status`, `inactivity_floor`, and `ops_root` must all describe one snapshot.
    ///
    /// # Errors
    ///
    /// Returns the errors of [merkle::RangePlan::build], and [Error::DataCorrupted] if the bitmap
    /// and the plan's leaf count imply more than one pending chunk or pruning beyond the graftable
    /// chunks.
    pub fn build<H: Hasher<Digest = D>, const N: usize>(
        status: &impl BitmapReadable<N>,
        plan: merkle::RangePlan<F>,
        get_node: impl Fn(Position<F>) -> Option<D>,
        inactivity_floor: Location<F>,
        ops_root: D,
    ) -> Result<Self, Error<F>> {
        let ops_leaves = plan.leaves();
        let grafting_height = grafting::height::<N>();
        let inactive_peaks = grafting::chunk_aligned_inactive_peaks::<F>(
            ops_leaves,
            inactivity_floor,
            grafting_height,
        )?;

        let hasher = qmdb::hasher::<H>();
        let proof = plan.build(&hasher, inactive_peaks, get_node)?;

        let partial_chunk_digest =
            partial_chunk::<_, N>(status).map(|(chunk, _)| hasher.digest(chunk.as_slice()));

        let pending_chunk_digest: F::PendingChunk<D> =
            pending_chunk::<_, _, N>(status, ops_leaves, grafting_height)?
                .map(|chunk| hasher.digest(chunk.as_slice()))
                .try_into()
                .expect("pending_chunk must be consistent with family");

        Ok(Self {
            proof,
            pending_chunk_digest,
            partial_chunk_digest,
            ops_root,
        })
    }

    /// Returns a proof that the specified range of operations are part of the database, along with
    /// the operations from the range and their activity status chunks. A truncated range (from
    /// hitting the max) can be detected by looking at the length of the returned operations vector.
    ///
    /// # Errors
    ///
    /// Returns [Error::OperationPruned] if `start_loc` falls in a pruned bitmap chunk.
    /// Returns [`merkle::Error::LocationOverflow`] if `start_loc` > [merkle::Family::MAX_LEAVES].
    /// Returns [`merkle::Error::RangeOutOfBounds`] if `start_loc` >= number of leaves in the tree.
    pub async fn new_with_ops<
        H: Hasher<Digest = D>,
        C: Contiguous,
        S: Storage<F, Digest = D>,
        const N: usize,
    >(
        status: &impl BitmapReadable<N>,
        storage: &S,
        log: &C,
        request: RangeProofSpec<F, D>,
    ) -> Result<(Self, Vec<C::Item>, Vec<[u8; N]>), Error<F>> {
        // Compute the end location of the range.
        let leaves = Location::new(status.len());
        if request.start_loc >= leaves {
            return Err(merkle::Error::RangeOutOfBounds(request.start_loc).into());
        }

        // Reject ranges that start in pruned bitmap chunks.
        let chunk_bits = BitMap::<N>::CHUNK_SIZE_BITS;
        let start = *request.start_loc / chunk_bits;
        if (start as usize) < status.pruned_chunks() {
            return Err(Error::OperationPruned(request.start_loc));
        }

        let max_loc = request.start_loc.saturating_add(request.max_ops.get());
        let end_loc = core::cmp::min(max_loc, leaves);

        // Generate the proof from the grafted storage.
        let proof = Self::new::<H, S, N>(
            status,
            storage,
            request.inactivity_floor,
            request.start_loc..end_loc,
            request.ops_root,
        )
        .await?;

        // Collect the operations necessary to verify the proof.
        let positions: Vec<u64> = (*request.start_loc..*end_loc).collect();
        let ops = log.read_many(&positions).await?;

        // Gather the chunks necessary to verify the proof.
        let end = (*end_loc - 1) / chunk_bits; // chunk that contains the last bit
        let chunks = (start..=end)
            .map(|i| status.get_chunk(i as usize))
            .collect::<Vec<_>>();

        Ok((proof, ops, chunks))
    }

    /// Reconstruct the canonical current root, optionally collecting the positioned digests
    /// required to compute the peaks covering the proven range.
    fn reconstruct_root<H, O>(
        &self,
        start_loc: Location<F>,
        ops: &[O],
        chunks: &[impl AsRef<[u8]>],
        chunk_size: usize,
        collected: Option<&mut Vec<(Position<F>, D)>>,
    ) -> Result<D, merkle::Error<F>>
    where
        H: Hasher<Digest = D>,
        O: Encode,
    {
        let chunk_bits = chunk_bits(chunk_size).map_err(|_| merkle::Error::InvalidProof)?;
        if ops.is_empty() || chunks.is_empty() {
            debug!("verification failed, empty input");
            return Err(merkle::Error::InvalidProof);
        }
        // Compute the (non-inclusive) end location of the range.
        let Some(end_loc) = start_loc.checked_add(ops.len() as u64) else {
            debug!("verification failed, end_loc overflow");
            return Err(merkle::Error::InvalidProof);
        };

        let leaves = self.proof.leaves;
        if end_loc > leaves {
            debug!(
                loc = ?end_loc,
                ?leaves, "verification failed, invalid range"
            );
            return Err(merkle::Error::InvalidProof);
        }

        // Validate the number of input chunks.
        let start_chunk = *start_loc / chunk_bits;
        let end_chunk = (*end_loc - 1) / chunk_bits;
        let complete_chunks = *leaves / chunk_bits;

        if (end_chunk - start_chunk + 1) != chunks.len() as u64 {
            debug!("verification failed, chunk metadata length mismatch");
            return Err(merkle::Error::InvalidProof);
        }
        if chunks
            .iter()
            .any(|chunk| chunk.as_ref().len() != chunk_size)
        {
            debug!("verification failed, chunk size mismatch");
            return Err(merkle::Error::InvalidProof);
        }

        let next_bit = *leaves % chunk_bits;
        let has_partial_chunk = next_bit != 0;

        let elements = ops.iter().map(|op| op.encode()).collect::<Vec<_>>();
        let chunk_vec = chunks.iter().map(|c| c.as_ref()).collect::<Vec<_>>();
        let grafting_height = chunk_bits.trailing_zeros();

        let graftable_chunks =
            grafting::graftable_chunks::<F>(*leaves, grafting_height).min(complete_chunks);
        let pending_chunks = complete_chunks - graftable_chunks;
        if pending_chunks > 1 {
            debug!(
                ?complete_chunks,
                ?graftable_chunks,
                "verification failed, multiple pending chunks"
            );
            return Err(merkle::Error::InvalidProof);
        }
        let has_pending_chunk = pending_chunks == 1;

        let grafting_verifier = grafting::Verifier::<F, H>::new(
            grafting_height,
            start_chunk,
            chunk_vec,
            graftable_chunks,
        );

        if self.pending_chunk_digest.as_ref().is_some() != has_pending_chunk {
            debug!(
                pending_in_proof = self.pending_chunk_digest.as_ref().is_some(),
                expected = has_pending_chunk,
                "pending_chunk_digest presence does not match bitmap state"
            );
            return Err(merkle::Error::InvalidProof);
        }

        // For partial chunks, validate the last chunk digest from the proof.
        if has_partial_chunk {
            let Some(last_chunk_digest) = self.partial_chunk_digest else {
                debug!("proof has no partial chunk digest");
                return Err(merkle::Error::InvalidProof);
            };

            // If the proof covers an operation in the partial chunk, verify that the
            // chunk provided by the caller matches the digest embedded in the proof.
            if end_chunk == complete_chunks {
                let last_chunk = chunks.last().expect("chunks non-empty");
                if last_chunk_digest != grafting_verifier.digest(last_chunk.as_ref()) {
                    debug!("last chunk digest does not match expected value");
                    return Err(merkle::Error::InvalidProof);
                }
            }
        } else if self.partial_chunk_digest.is_some() {
            debug!("proof has unexpected partial chunk digest");
            return Err(merkle::Error::InvalidProof);
        }

        // For a pending chunk, validate the supplied chunk bytes against the digest in the proof
        // when the verifier's range includes the pending chunk's index. The pending chunk is at
        // index `graftable_chunks` (== `complete_chunks - 1` when present).
        if let Some(pending_digest) = self.pending_chunk_digest.as_ref() {
            let pending_idx = graftable_chunks;
            if pending_idx >= start_chunk && pending_idx <= end_chunk {
                let local = (pending_idx - start_chunk) as usize;
                // The earlier `chunks.len() == end_chunk - start_chunk + 1` check makes this
                // index in-bounds for well-formed inputs; treat any mismatch as a malformed
                // proof (rather than panicking) since `verify` runs against attacker-supplied data.
                let Some(pending_chunk_bytes) = chunks.get(local) else {
                    debug!(
                        ?pending_idx,
                        chunks_len = chunks.len(),
                        "pending chunk index out of range in supplied chunks"
                    );
                    return Err(merkle::Error::InvalidProof);
                };
                if *pending_digest != grafting_verifier.digest(pending_chunk_bytes.as_ref()) {
                    debug!("pending chunk digest does not match expected value");
                    return Err(merkle::Error::InvalidProof);
                }
            }
        }

        let merkle_root = match self.proof.reconstruct_root_inner(
            &grafting_verifier,
            &elements,
            start_loc,
            collected,
        ) {
            Ok(root) => root,
            Err(error) => {
                debug!(?error, "invalid proof input");
                return Err(merkle::Error::InvalidProof);
            }
        };

        let partial =
            has_partial_chunk.then(|| (next_bit, self.partial_chunk_digest.as_ref().unwrap()));
        Ok(combine_roots::<H>(
            &self.ops_root,
            &merkle_root,
            self.pending_chunk_digest.as_ref(),
            partial,
        ))
    }

    /// Return true if the given sequence of `ops` were applied starting at location `start_loc` in
    /// the db with the provided root, and having the activity status described by `chunks`.
    pub fn verify<H: Hasher<Digest = D>, O: Encode, const N: usize>(
        &self,
        start_loc: Location<F>,
        ops: &[O],
        chunks: &[[u8; N]],
        root: &H::Digest,
    ) -> bool {
        self.verify_with_chunk_size::<H, O>(start_loc, ops, chunks, N, root)
    }

    /// Verify an operation range using bitmap chunks whose size is configured at runtime.
    ///
    /// `chunk_size` must match the source database. It must be a nonzero power of two,
    /// its bit width must fit in `usize` and `u64`, and its grafting height must be below 63.
    /// Every supplied chunk must contain exactly `chunk_size` bytes. Invalid sizes and
    /// malformed proofs return `false`.
    ///
    /// This verifies the same proof and wire encoding as [Self::verify], accepting arrays,
    /// byte slices, or owned byte buffers without copying their contents.
    pub fn verify_with_chunk_size<H: Hasher<Digest = D>, O: Encode>(
        &self,
        start_loc: Location<F>,
        ops: &[O],
        chunks: &[impl AsRef<[u8]>],
        chunk_size: usize,
        root: &D,
    ) -> bool {
        matches!(
            self.reconstruct_root::<H, O>(start_loc, ops, chunks, chunk_size, None),
            Ok(reconstructed_root) if reconstructed_root == *root
        )
    }
}

/// Verify that a [RangeProof] is valid for a range of operations and return the positioned digests
/// required to compute the peaks covering the proven range.
pub fn verify_proof_and_extract_digests<F, Op, H, const N: usize>(
    proof: &RangeProof<F, H::Digest>,
    start_loc: Location<F>,
    operations: &[Op],
    chunks: &[[u8; N]],
    target_root: &H::Digest,
) -> Result<qmdb::verify::ExtractedDigests<F, H>, merkle::Error<F>>
where
    F: Graftable,
    Op: Encode,
    H: Hasher,
{
    let mut collected = Vec::new();
    let reconstructed_root =
        proof.reconstruct_root::<H, Op>(start_loc, operations, chunks, N, Some(&mut collected))?;
    if reconstructed_root != *target_root {
        debug!("verification failed, root mismatch");
        return Err(merkle::Error::RootMismatch);
    }

    Ok(collected)
}

impl<F: Graftable, D: Digest> Write for RangeProof<F, D> {
    fn write(&self, buf: &mut impl BufMut) {
        self.proof.write(buf);
        self.pending_chunk_digest.write(buf);
        self.partial_chunk_digest.write(buf);
        self.ops_root.write(buf);
    }
}

impl<F: Graftable, D: Digest> EncodeSize for RangeProof<F, D> {
    fn encode_size(&self) -> usize {
        self.proof.encode_size()
            + self.pending_chunk_digest.encode_size()
            + self.partial_chunk_digest.encode_size()
            + self.ops_root.encode_size()
    }
}

impl<F: Graftable, D: Digest> Read for RangeProof<F, D> {
    /// The maximum number of digests in the embedded Merkle proof.
    type Cfg = usize;

    fn read_cfg(
        buf: &mut impl Buf,
        max_digests: &Self::Cfg,
    ) -> Result<Self, commonware_codec::Error> {
        let proof = Proof::<F, D>::read_cfg(buf, max_digests)?;
        let pending_chunk_digest = F::PendingChunk::<D>::read(buf)?;
        let partial_chunk_digest = Option::<D>::read(buf)?;
        let ops_root = D::read(buf)?;
        Ok(Self {
            proof,
            pending_chunk_digest,
            partial_chunk_digest,
            ops_root,
        })
    }
}

#[cfg(feature = "arbitrary")]
impl<F: Graftable, D: Digest> arbitrary::Arbitrary<'_> for RangeProof<F, D>
where
    D: for<'a> arbitrary::Arbitrary<'a>,
    F::PendingChunk<D>: for<'a> arbitrary::Arbitrary<'a>,
{
    fn arbitrary(u: &mut arbitrary::Unstructured<'_>) -> arbitrary::Result<Self> {
        Ok(Self {
            proof: u.arbitrary()?,
            pending_chunk_digest: u.arbitrary()?,
            partial_chunk_digest: u.arbitrary()?,
            ops_root: u.arbitrary()?,
        })
    }
}

/// Proofs with fixed-size bitmap chunks.
pub mod constant {
    /// A proof that a specific operation is active, with a fixed-size bitmap chunk.
    pub type OperationProof<F, D, const N: usize> = super::operation::Proof<F, D, [u8; N]>;
}

/// Proofs with runtime-sized bitmap chunks.
pub mod dynamic {
    /// An operation proof with a runtime-sized bitmap chunk.
    ///
    /// Decoding takes `(chunk_size, max_digests)` as configuration. The chunk size must match
    /// the source database and satisfy [super::RangeProof::verify_with_chunk_size]'s size
    /// requirements. The bitmap chunk has no length prefix, so its wire encoding matches
    /// [super::constant::OperationProof].
    /// The operation supplied to verification must use the source database's key and value codecs.
    ///
    /// # Examples
    ///
    /// ```
    /// use commonware_codec::{Decode, Encode, Input};
    /// use commonware_cryptography::{Sha256, sha256::Digest};
    /// use commonware_storage::{merkle::mmr, qmdb::current::proof::dynamic::OperationProof};
    ///
    /// fn verify<O: Encode>(
    ///     encoded: impl Input,
    ///     chunk_size: usize,
    ///     max_digests: usize,
    ///     operation: O,
    ///     root: &Digest,
    /// ) -> bool {
    ///     let Ok(proof) = OperationProof::<mmr::Family, Digest>::decode_cfg(
    ///         encoded,
    ///         &(chunk_size, max_digests),
    ///     ) else {
    ///         return false;
    ///     };
    ///     proof.verify::<Sha256, _>(operation, root)
    /// }
    /// ```
    pub type OperationProof<F, D> = super::operation::Proof<F, D, bytes::Bytes>;
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::{
        merkle::{conformance::build_test_mem, hasher::Standard as StandardHasher, mem::Mem},
        mmb, mmr,
        qmdb::current::{db, grafting},
    };
    use bytes::Bytes;
    use commonware_codec::{Decode as _, DecodeExt as _};
    use commonware_cryptography::{Sha256, sha256};
    use commonware_macros::test_async;
    use commonware_parallel::{Sequential, Strategy};
    use commonware_utils::{
        Widen,
        bitmap::{Prunable as BitMap, Readable as BitmapReadable},
        sync::Mutex,
    };
    use core::ops::Range;
    use std::collections::{BTreeMap, BTreeSet};

    /// Compute grafted leaf digests for the given bitmap chunks as `(chunk_idx, digest)` pairs.
    ///
    /// See [`db::read_graft_inputs`] for the chunk requirements. The grafted leaf digest is
    /// `hash(chunk || ops_h_G_node)`, except that an all-zero chunk's leaf is the ops digest
    /// itself (zero-chunk identity).
    async fn compute_grafted_leaves<
        F: merkle::Graftable,
        H: Hasher,
        S: Strategy,
        const N: usize,
    >(
        ops_tree: &impl Storage<F, Digest = H::Digest>,
        chunks: impl IntoIterator<Item = (usize, [u8; N])>,
        strategy: &S,
    ) -> Result<Vec<(usize, H::Digest)>, Error<F>> {
        let inputs = db::read_graft_inputs::<F, _, N>(ops_tree, chunks).await?;
        Ok(grafting::graft_chunk_digests::<H, _, N>(strategy, inputs))
    }

    #[test]
    fn test_ops_root_witness_codec_roundtrip() {
        type F = mmb::Family;
        for partial_chunk in [
            None,
            Some((0u64, Sha256::hash(&[b"partial-zero"]))),
            Some((123u64, Sha256::hash(&[b"partial-nonzero"]))),
        ] {
            let witness: OpsRootWitness<F, _> = OpsRootWitness {
                grafted_root: Sha256::hash(&[b"grafted"]),
                pending_chunk_digest: None,
                partial_chunk,
            };
            let encoded = witness.encode();
            assert_eq!(encoded.len(), witness.encode_size());
            let decoded = OpsRootWitness::<F, sha256::Digest>::decode(encoded).unwrap();
            assert_eq!(decoded, witness);
        }
    }

    #[test]
    fn test_ops_root_witness_root_matches_verify() {
        type F = mmb::Family;

        let ops_root = Sha256::hash(&[b"ops root"]);
        let witness: OpsRootWitness<F, _> = OpsRootWitness {
            grafted_root: Sha256::hash(&[b"grafted root"]),
            pending_chunk_digest: Some(Sha256::hash(&[b"pending chunk"])),
            partial_chunk: Some((13, Sha256::hash(&[b"partial chunk"]))),
        };

        let root = witness.root::<Sha256>(&ops_root);

        assert!(witness.verify::<Sha256>(&ops_root, &root));
        assert_ne!(root, ops_root);

        let wrong_ops_root = Sha256::hash(&[b"wrong ops root"]);
        assert!(!witness.verify::<Sha256>(&wrong_ops_root, &root));
    }

    fn range_proof_digest_count<F: Graftable, D: Digest>(proof: &RangeProof<F, D>) -> usize {
        proof.proof.digests.len()
    }

    #[test]
    fn test_range_proof_codec_roundtrip() {
        type F = mmb::Family;
        const MAX_DIGESTS: usize = 64;

        let proof = Proof::<F, sha256::Digest> {
            leaves: mmb::Location::new(42),
            inactive_peaks: 0,
            digests: vec![
                Sha256::hash(&[b"d0"]),
                Sha256::hash(&[b"d1"]),
                Sha256::hash(&[b"d2"]),
            ],
        };
        let ops_root = Sha256::hash(&[b"ops-root"]);

        let cases = [
            // Minimal: no optional fields or prefix/suffix witnesses.
            RangeProof {
                proof: proof.clone(),
                pending_chunk_digest: None,
                partial_chunk_digest: None,
                ops_root,
            },
            // All optional fields populated.
            RangeProof {
                proof,
                pending_chunk_digest: Some(Sha256::hash(&[b"pending"])),
                partial_chunk_digest: Some(Sha256::hash(&[b"partial"])),
                ops_root,
            },
            // Default proof with only partial chunk digest.
            RangeProof {
                proof: Proof::<F, sha256::Digest>::default(),
                pending_chunk_digest: None,
                partial_chunk_digest: Some(Sha256::hash(&[b"only-partial"])),
                ops_root,
            },
        ];

        for proof in cases {
            let encoded = proof.encode();
            assert_eq!(encoded.len(), proof.encode_size());
            let decoded =
                RangeProof::<F, sha256::Digest>::decode_cfg(encoded, &MAX_DIGESTS).unwrap();
            assert_eq!(decoded, proof);
        }
    }

    #[test]
    fn test_range_proof_codec_enforces_merkle_digest_budget() {
        type F = mmb::Family;

        let proof = RangeProof {
            proof: Proof::<F, sha256::Digest> {
                leaves: mmb::Location::new(42),
                inactive_peaks: 0,
                digests: vec![Sha256::hash(&[b"d0"])],
            },
            pending_chunk_digest: None,
            partial_chunk_digest: None,
            ops_root: Sha256::hash(&[b"ops-root"]),
        };

        let encoded = proof.encode();
        let total_digests = range_proof_digest_count(&proof);

        let decoded =
            RangeProof::<F, sha256::Digest>::decode_cfg(encoded.clone(), &total_digests).unwrap();
        assert_eq!(decoded, proof);
        assert!(
            RangeProof::<F, sha256::Digest>::decode_cfg(encoded, &(total_digests - 1)).is_err()
        );
    }

    #[test]
    fn test_range_proof_decode_rejects_pending_for_mmr() {
        const MAX_DIGESTS: usize = 64;

        let proof = RangeProof {
            proof: Proof::<mmb::Family, sha256::Digest> {
                leaves: mmb::Location::new(42),
                inactive_peaks: 0,
                digests: vec![Sha256::hash(&[b"d0"])],
            },
            pending_chunk_digest: Some(Sha256::hash(&[b"pending"])),
            partial_chunk_digest: None,
            ops_root: Sha256::hash(&[b"ops-root"]),
        };
        let encoded = proof.encode();

        // MMB allows pending_chunk_digest.
        assert!(
            RangeProof::<mmb::Family, sha256::Digest>::decode_cfg(encoded.clone(), &MAX_DIGESTS)
                .is_ok()
        );

        // MMR rejects it on decode.
        assert!(
            RangeProof::<crate::merkle::mmr::Family, sha256::Digest>::decode_cfg(
                encoded,
                &MAX_DIGESTS
            )
            .is_err()
        );
    }

    #[test]
    fn test_operation_proof_codec_roundtrip() {
        type F = mmb::Family;
        const N: usize = 32;
        const MAX_DIGESTS: usize = 64;

        let range_proof = RangeProof {
            proof: Proof::<F, sha256::Digest> {
                leaves: mmb::Location::new(7),
                inactive_peaks: 0,
                digests: vec![Sha256::hash(&[b"sib"])],
            },
            pending_chunk_digest: None,
            partial_chunk_digest: None,
            ops_root: Sha256::hash(&[b"ops"]),
        };

        let chunk: [u8; N] = core::array::from_fn(|i| i as u8);

        let proof = constant::OperationProof::<F, sha256::Digest, N> {
            loc: mmb::Location::new(5),
            chunk,
            range_proof,
        };

        let encoded = proof.encode();
        assert_eq!(encoded.len(), proof.encode_size());
        let decoded =
            constant::OperationProof::<F, sha256::Digest, N>::decode_cfg(encoded, &MAX_DIGESTS)
                .unwrap();
        assert_eq!(decoded, proof);
    }

    #[test]
    fn test_operation_proof_codec_enforces_merkle_digest_budget() {
        type F = mmb::Family;
        const N: usize = 32;

        let range_proof = RangeProof {
            proof: Proof::<F, sha256::Digest> {
                leaves: mmb::Location::new(7),
                inactive_peaks: 0,
                digests: vec![Sha256::hash(&[b"sib"])],
            },
            pending_chunk_digest: None,
            partial_chunk_digest: None,
            ops_root: Sha256::hash(&[b"ops"]),
        };
        let total_digests = range_proof_digest_count(&range_proof);
        let proof = constant::OperationProof::<F, sha256::Digest, N> {
            loc: mmb::Location::new(5),
            chunk: core::array::from_fn(|i| i as u8),
            range_proof,
        };

        let encoded = proof.encode();
        let decoded = constant::OperationProof::<F, sha256::Digest, N>::decode_cfg(
            encoded.clone(),
            &total_digests,
        )
        .unwrap();
        assert_eq!(decoded, proof);
        assert!(
            constant::OperationProof::<F, sha256::Digest, N>::decode_cfg(
                encoded,
                &(total_digests - 1)
            )
            .is_err()
        );
    }

    #[test_async]
    async fn test_range_proof_verifies_for_mmb_multi_peak_chunk() {
        type F = mmb::Family;
        const N: usize = 1;

        let hasher = qmdb::hasher::<Sha256>();
        let grafting_height = grafting::height::<N>();

        let leaf_count = (16..=64u64)
            .find(|&leaves| {
                let size = F::location_to_position(mmb::Location::new(leaves));
                F::chunk_peaks(size, 1, grafting_height).nth(1).is_some()
            })
            .expect("expected an MMB size whose second chunk spans multiple peaks");

        let mut status = BitMap::<N>::new();
        for _ in 0..leaf_count {
            status.push(true);
        }
        let ops = build_test_mem(&hasher, mmb::mem::Mmb::new(), leaf_count);
        let ops_root = ops.root(&hasher, 0).unwrap();

        let graftable_chunks_for_test = grafting::graftable_chunks::<F>(
            *Location::<F>::try_from(ops.size()).unwrap(),
            grafting_height,
        )
        .min(<BitMap<N> as BitmapReadable<N>>::complete_chunks(&status) as u64)
            as usize;
        let chunk_inputs: Vec<_> = (0..graftable_chunks_for_test)
            .map(|chunk_idx| {
                (
                    chunk_idx,
                    <BitMap<N> as BitmapReadable<N>>::get_chunk(&status, chunk_idx),
                )
            })
            .collect();
        let mut leaf_digests =
            compute_grafted_leaves::<F, Sha256, Sequential, N>(&ops, chunk_inputs, &Sequential)
                .await
                .unwrap();
        leaf_digests.sort_by_key(|(chunk_idx, _)| *chunk_idx);

        let grafted_hasher = grafting::GraftedHasher::<F, _>::new(hasher.clone(), grafting_height);
        let mut grafted = Mem::<F, sha256::Digest>::new();
        let merkleized = {
            let mut batch = grafted.new_batch();
            for (_, digest) in leaf_digests {
                batch = batch.add_leaf_digest(digest);
            }
            batch.merkleize(&grafted, &grafted_hasher)
        };
        grafted.apply_batch(&merkleized).unwrap();

        let storage = grafting::Storage::<F, Sha256, _, _>::new(&grafted, grafting_height, &ops);
        let ops_leaves_for_root = Location::<F>::try_from(ops.size()).unwrap();
        let root = db::compute_ops_root_witness::<F, Sha256, _, _, N>(
            &status,
            &storage,
            ops_leaves_for_root,
            Location::new(0),
        )
        .await
        .unwrap()
        .root::<Sha256>(&ops_root);

        let loc = mmb::Location::new(BitMap::<N>::CHUNK_SIZE_BITS + 4);
        let proof = RangeProof::new::<Sha256, _, N>(
            &status,
            &storage,
            Location::new(0),
            loc..loc + 1,
            ops_root,
        )
        .await
        .unwrap();

        let element = hasher.digest(&(*loc).to_be_bytes());
        assert!(proof.verify::<Sha256, _, N>(
            loc,
            &[element],
            &[<BitMap<N> as BitmapReadable<N>>::get_chunk(&status, 1)],
            &root,
        ));
    }

    #[test_async]
    async fn test_range_proof_verifies_with_partial_suffix_mmb() {
        type F = mmb::Family;
        const N: usize = 1;

        let hasher = qmdb::hasher::<Sha256>();
        let grafting_height = grafting::height::<N>();
        let chunk_bits = BitMap::<N>::CHUNK_SIZE_BITS;

        let (leaf_count, loc) = (chunk_bits * 2 + 1..=64u64)
            .find_map(|leaves| {
                let complete_chunks = leaves / chunk_bits;
                if complete_chunks < 2 || leaves % chunk_bits == 0 {
                    return None;
                }

                let size = F::location_to_position(mmb::Location::new(leaves));
                F::chunk_peaks(size, 1, grafting_height).nth(1)?;
                Some((leaves, mmb::Location::new(chunk_bits + 1)))
            })
            .expect("expected an MMB proof with a partial trailing suffix chunk");

        let mut status = BitMap::<N>::new();
        for _ in 0..leaf_count {
            status.push(true);
        }
        let ops = build_test_mem(&hasher, mmb::mem::Mmb::new(), leaf_count);
        let ops_root = ops.root(&hasher, 0).unwrap();

        let graftable_chunks_for_test = grafting::graftable_chunks::<F>(
            *Location::<F>::try_from(ops.size()).unwrap(),
            grafting_height,
        )
        .min(<BitMap<N> as BitmapReadable<N>>::complete_chunks(&status) as u64)
            as usize;
        let chunk_inputs: Vec<_> = (0..graftable_chunks_for_test)
            .map(|chunk_idx| {
                (
                    chunk_idx,
                    <BitMap<N> as BitmapReadable<N>>::get_chunk(&status, chunk_idx),
                )
            })
            .collect();
        let mut leaf_digests =
            compute_grafted_leaves::<F, Sha256, Sequential, N>(&ops, chunk_inputs, &Sequential)
                .await
                .unwrap();
        leaf_digests.sort_by_key(|(chunk_idx, _)| *chunk_idx);

        let grafted_hasher = grafting::GraftedHasher::<F, _>::new(hasher.clone(), grafting_height);
        let mut grafted = Mem::<F, sha256::Digest>::new();
        let merkleized = {
            let mut batch = grafted.new_batch();
            for (_, digest) in leaf_digests {
                batch = batch.add_leaf_digest(digest);
            }
            batch.merkleize(&grafted, &grafted_hasher)
        };
        grafted.apply_batch(&merkleized).unwrap();

        let storage = grafting::Storage::<F, Sha256, _, _>::new(&grafted, grafting_height, &ops);
        let ops_leaves_for_root = Location::<F>::try_from(ops.size()).unwrap();
        let root = db::compute_ops_root_witness::<F, Sha256, _, _, N>(
            &status,
            &storage,
            ops_leaves_for_root,
            Location::new(0),
        )
        .await
        .unwrap()
        .root::<Sha256>(&ops_root);
        let proof = RangeProof::new::<Sha256, _, N>(
            &status,
            &storage,
            Location::new(0),
            loc..loc + 1,
            ops_root,
        )
        .await
        .unwrap();

        let element = hasher.digest(&(*loc).to_be_bytes());
        let chunk_idx = (*loc / BitMap::<N>::CHUNK_SIZE_BITS) as usize;
        assert!(proof.verify::<Sha256, _, N>(
            loc,
            &[element],
            &[<BitMap<N> as BitmapReadable<N>>::get_chunk(
                &status, chunk_idx
            )],
            &root,
        ));
    }

    #[test_async]
    async fn test_range_proof_verifies_when_range_reaches_partial_chunk_mmb() {
        type F = mmb::Family;
        const N: usize = 1;

        let hasher = qmdb::hasher::<Sha256>();
        let grafting_height = grafting::height::<N>();
        let chunk_bits = BitMap::<N>::CHUNK_SIZE_BITS;

        // Search for an MMB size whose chunk 1 is multi-peak AND whose total leaves
        // aren't chunk-aligned (so a partial trailing chunk exists). The proven range
        // starts inside chunk 1 and extends to the end (touching the partial chunk).
        let (leaf_count, start_loc, complete_chunks) = (17..=128u64)
            .find_map(|leaves| {
                let complete_chunks = leaves / chunk_bits;
                if complete_chunks < 2 || leaves % chunk_bits == 0 {
                    return None;
                }
                let leaves_loc = mmb::Location::new(leaves);
                let size = F::location_to_position(leaves_loc);
                F::chunk_peaks(size, 1, grafting_height).nth(1)?;
                let start_loc = mmb::Location::new(chunk_bits + 1);
                Some((leaves, start_loc, complete_chunks))
            })
            .expect("expected an MMB size with chunk 1 multi-peak and a partial trailing chunk");

        let mut status = BitMap::<N>::new();
        for _ in 0..leaf_count {
            status.push(true);
        }
        let ops = build_test_mem(&hasher, mmb::mem::Mmb::new(), leaf_count);
        let ops_root = ops.root(&hasher, 0).unwrap();

        let graftable_chunks_for_test = grafting::graftable_chunks::<F>(
            *Location::<F>::try_from(ops.size()).unwrap(),
            grafting_height,
        )
        .min(<BitMap<N> as BitmapReadable<N>>::complete_chunks(&status) as u64)
            as usize;
        let chunk_inputs: Vec<_> = (0..graftable_chunks_for_test)
            .map(|chunk_idx| {
                (
                    chunk_idx,
                    <BitMap<N> as BitmapReadable<N>>::get_chunk(&status, chunk_idx),
                )
            })
            .collect();
        let mut leaf_digests =
            compute_grafted_leaves::<F, Sha256, Sequential, N>(&ops, chunk_inputs, &Sequential)
                .await
                .unwrap();
        leaf_digests.sort_by_key(|(chunk_idx, _)| *chunk_idx);

        let grafted_hasher = grafting::GraftedHasher::<F, _>::new(hasher.clone(), grafting_height);
        let mut grafted = Mem::<F, sha256::Digest>::new();
        let merkleized = {
            let mut batch = grafted.new_batch();
            for (_, digest) in leaf_digests {
                batch = batch.add_leaf_digest(digest);
            }
            batch.merkleize(&grafted, &grafted_hasher)
        };
        grafted.apply_batch(&merkleized).unwrap();

        let storage = grafting::Storage::<F, Sha256, _, _>::new(&grafted, grafting_height, &ops);
        let ops_leaves_for_root = Location::<F>::try_from(ops.size()).unwrap();
        let root = db::compute_ops_root_witness::<F, Sha256, _, _, N>(
            &status,
            &storage,
            ops_leaves_for_root,
            Location::new(0),
        )
        .await
        .unwrap()
        .root::<Sha256>(&ops_root);

        let leaves_loc = mmb::Location::new(leaf_count);
        let proof = RangeProof::new::<Sha256, _, N>(
            &status,
            &storage,
            Location::new(0),
            start_loc..leaves_loc,
            ops_root,
        )
        .await
        .unwrap();

        let elements = (*start_loc..leaf_count)
            .map(|idx| hasher.digest(&idx.to_be_bytes()))
            .collect::<Vec<_>>();
        let start_chunk_idx = (*start_loc / chunk_bits) as usize;
        let end_chunk_idx = complete_chunks as usize;
        let chunks = (start_chunk_idx..=end_chunk_idx)
            .map(|chunk_idx| <BitMap<N> as BitmapReadable<N>>::get_chunk(&status, chunk_idx))
            .collect::<Vec<_>>();
        assert!(proof.verify::<Sha256, _, N>(start_loc, &elements, &chunks, &root,));

        // Flip a byte in the trailing partial chunk while preserving the window shape.
        let mut bad_chunks = chunks;
        let last = bad_chunks.last_mut().unwrap();
        last[0] ^= 1;
        assert!(
            !proof.verify::<Sha256, _, N>(start_loc, &elements, &bad_chunks, &root),
            "tampered partial chunk bytes should not verify"
        );
    }

    #[test_async]
    async fn test_range_proof_rejects_unexpected_partial_chunk_digest() {
        type F = mmb::Family;
        const N: usize = 1;

        let hasher = qmdb::hasher::<Sha256>();
        let grafting_height = grafting::height::<N>();
        let chunk_bits = BitMap::<N>::CHUNK_SIZE_BITS;

        let leaf_count = chunk_bits * 2; // Perfect chunks, NO partial trailing bits
        let mut status = BitMap::<N>::new();
        for _ in 0..leaf_count {
            status.push(true);
        }
        let ops = build_test_mem(&hasher, mmb::mem::Mmb::new(), leaf_count);
        let ops_root = ops.root(&hasher, 0).unwrap();

        let graftable_chunks_for_test = grafting::graftable_chunks::<F>(
            *Location::<F>::try_from(ops.size()).unwrap(),
            grafting_height,
        )
        .min(<BitMap<N> as BitmapReadable<N>>::complete_chunks(&status) as u64)
            as usize;
        let chunk_inputs: Vec<_> = (0..graftable_chunks_for_test)
            .map(|chunk_idx| {
                (
                    chunk_idx,
                    <BitMap<N> as BitmapReadable<N>>::get_chunk(&status, chunk_idx),
                )
            })
            .collect();
        let mut leaf_digests =
            compute_grafted_leaves::<F, Sha256, Sequential, N>(&ops, chunk_inputs, &Sequential)
                .await
                .unwrap();
        leaf_digests.sort_by_key(|(chunk_idx, _)| *chunk_idx);

        let grafted_hasher = grafting::GraftedHasher::<F, _>::new(hasher.clone(), grafting_height);
        let mut grafted = Mem::<F, sha256::Digest>::new();
        let merkleized = {
            let mut batch = grafted.new_batch();
            for (_, digest) in leaf_digests {
                batch = batch.add_leaf_digest(digest);
            }
            batch.merkleize(&grafted, &grafted_hasher)
        };
        grafted.apply_batch(&merkleized).unwrap();

        let storage = grafting::Storage::<F, Sha256, _, _>::new(&grafted, grafting_height, &ops);
        let ops_leaves_for_root = Location::<F>::try_from(ops.size()).unwrap();
        let root = db::compute_ops_root_witness::<F, Sha256, _, _, N>(
            &status,
            &storage,
            ops_leaves_for_root,
            Location::new(0),
        )
        .await
        .unwrap()
        .root::<Sha256>(&ops_root);

        let loc = mmb::Location::new(0);
        let mut proof = RangeProof::new::<Sha256, _, N>(
            &status,
            &storage,
            Location::new(0),
            loc..loc + 1,
            ops_root,
        )
        .await
        .unwrap();

        let element = hasher.digest(&(*loc).to_be_bytes());
        let chunk = <BitMap<N> as BitmapReadable<N>>::get_chunk(&status, 0);

        // Tamper with the proof by injecting a fake partial chunk digest
        let mut tampered = proof.clone();
        tampered.partial_chunk_digest = Some(hasher.digest(b"fake partial chunk"));
        assert!(!tampered.verify::<Sha256, _, N>(loc, &[element], &[chunk], &root,));

        proof.partial_chunk_digest = Some(hasher.digest(b"fake partial chunk"));
        assert!(!proof.verify::<Sha256, _, N>(loc, &[element], &[chunk], &root,));
    }

    async fn current_range_proof_fixture<F: Graftable, const N: usize>(
        leaf_count: u64,
        range: Range<Location<F>>,
    ) -> (
        StandardHasher<Sha256>,
        RangeProof<F, sha256::Digest>,
        Vec<sha256::Digest>,
        Vec<[u8; N]>,
        sha256::Digest,
        Mem<F, sha256::Digest>,
    ) {
        let hasher = qmdb::hasher::<Sha256>();
        let grafting_height = grafting::height::<N>();
        let chunk_bits = BitMap::<N>::CHUNK_SIZE_BITS;

        let mut status = BitMap::<N>::new();
        for _ in 0..leaf_count {
            status.push(true);
        }

        let ops = build_test_mem(&hasher, Mem::<F, sha256::Digest>::new(), leaf_count);
        let ops_root = ops.root(&hasher, 0).unwrap();
        let ops_leaves = Location::<F>::try_from(ops.size()).unwrap();

        let graftable_chunks_for_test =
            grafting::graftable_chunks::<F>(*ops_leaves, grafting_height)
                .min(<BitMap<N> as BitmapReadable<N>>::complete_chunks(&status) as u64)
                as usize;
        let chunk_inputs: Vec<_> = (0..graftable_chunks_for_test)
            .map(|chunk_idx| {
                (
                    chunk_idx,
                    <BitMap<N> as BitmapReadable<N>>::get_chunk(&status, chunk_idx),
                )
            })
            .collect();
        let mut leaf_digests =
            compute_grafted_leaves::<F, Sha256, Sequential, N>(&ops, chunk_inputs, &Sequential)
                .await
                .unwrap();
        leaf_digests.sort_by_key(|(chunk_idx, _)| *chunk_idx);

        let grafted_hasher = grafting::GraftedHasher::<F, _>::new(hasher.clone(), grafting_height);
        let mut grafted = Mem::<F, sha256::Digest>::new();
        if !leaf_digests.is_empty() {
            let merkleized = {
                let mut batch = grafted.new_batch();
                for (_, digest) in leaf_digests {
                    batch = batch.add_leaf_digest(digest);
                }
                batch.merkleize(&grafted, &grafted_hasher)
            };
            grafted.apply_batch(&merkleized).unwrap();
        }

        let storage = grafting::Storage::<F, Sha256, _, _>::new(&grafted, grafting_height, &ops);
        let root = db::compute_ops_root_witness::<F, Sha256, _, _, N>(
            &status,
            &storage,
            ops_leaves,
            Location::new(0),
        )
        .await
        .unwrap()
        .root::<Sha256>(&ops_root);

        let proof = RangeProof::new::<Sha256, _, N>(
            &status,
            &storage,
            Location::new(0),
            range.clone(),
            ops_root,
        )
        .await
        .unwrap();
        let operations = (*range.start..*range.end)
            .map(|i| hasher.digest(&i.to_be_bytes()))
            .collect::<Vec<_>>();

        // Provide every bitmap chunk touched by the proven operation range.
        let start_chunk = (*range.start / chunk_bits) as usize;
        let end_chunk = ((*range.end - 1) / chunk_bits) as usize;
        let chunks = (start_chunk..=end_chunk)
            .map(|chunk_idx| <BitMap<N> as BitmapReadable<N>>::get_chunk(&status, chunk_idx))
            .collect::<Vec<_>>();

        assert!(proof.verify::<Sha256, _, N>(range.start, &operations, &chunks, &root));

        (hasher, proof, operations, chunks, root, ops)
    }

    async fn verify_proof_and_extract_digests_inner<F: Graftable>() {
        const N: usize = 1;
        let start = Location::<F>::new(14);
        let end = Location::<F>::new(18);
        let (hasher, proof, operations, chunks, root, ops) =
            current_range_proof_fixture::<F, N>(18, start..end).await;

        let extracted = verify_proof_and_extract_digests::<F, _, Sha256, N>(
            &proof,
            start,
            &operations,
            &chunks,
            &root,
        )
        .unwrap();
        assert!(!extracted.is_empty());

        // The extractor should return the authenticated digest for every proven leaf.
        for loc in *start..*end {
            let pos = F::location_to_position(Location::<F>::new(loc));
            let expected = ops.get_node(pos).unwrap();
            assert!(
                extracted
                    .iter()
                    .any(|(actual_pos, actual)| *actual_pos == pos && *actual == expected),
                "missing extracted leaf digest at {pos:?}",
            );
        }

        // Root mismatches are reported distinctly from malformed proof inputs.
        let wrong_root = hasher.digest(b"wrong current root");
        assert!(matches!(
            verify_proof_and_extract_digests::<F, _, Sha256, N>(
                &proof,
                start,
                &operations,
                &chunks,
                &wrong_root,
            ),
            Err(merkle::Error::RootMismatch)
        ));

        // Mutating operations or bitmap chunks must invalidate the extracted proof.
        let mut wrong_operations = operations.clone();
        wrong_operations[0] = hasher.digest(b"wrong operation");
        assert!(
            verify_proof_and_extract_digests::<F, _, Sha256, N>(
                &proof,
                start,
                &wrong_operations,
                &chunks,
                &root,
            )
            .is_err()
        );

        let mut bad_chunks = chunks;
        bad_chunks.last_mut().unwrap()[0] ^= 1;
        assert!(
            verify_proof_and_extract_digests::<F, _, Sha256, N>(
                &proof,
                start,
                &operations,
                &bad_chunks,
                &root,
            )
            .is_err()
        );
    }

    #[test_async]
    async fn test_verify_proof_and_extract_digests_handles_no_grafted_chunks_mmb() {
        type F = mmb::Family;
        const N: usize = 1;
        let start = Location::<F>::new(2);
        let end = Location::<F>::new(4);
        let (_, proof, operations, chunks, root, _ops) =
            current_range_proof_fixture::<F, N>(6, start..end).await;

        let extracted = verify_proof_and_extract_digests::<F, _, Sha256, N>(
            &proof,
            start,
            &operations,
            &chunks,
            &root,
        )
        .unwrap();

        assert!(!extracted.is_empty());
    }

    #[test_async]
    async fn test_verify_proof_and_extract_digests_rejects_malformed_inputs_mmb() {
        type F = mmb::Family;
        const N: usize = 1;
        let start = Location::<F>::new(14);
        let end = Location::<F>::new(18);
        let (_, proof, operations, chunks, root, _ops) =
            current_range_proof_fixture::<F, N>(18, start..end).await;

        let no_operations = Vec::<sha256::Digest>::new();
        assert!(matches!(
            verify_proof_and_extract_digests::<F, _, Sha256, N>(
                &proof,
                start,
                &no_operations,
                &chunks,
                &root,
            ),
            Err(merkle::Error::InvalidProof)
        ));

        let no_chunks = Vec::<[u8; N]>::new();
        assert!(matches!(
            verify_proof_and_extract_digests::<F, _, Sha256, N>(
                &proof,
                start,
                &operations[..1],
                &no_chunks,
                &root,
            ),
            Err(merkle::Error::InvalidProof)
        ));

        assert!(matches!(
            verify_proof_and_extract_digests::<F, _, Sha256, N>(
                &proof,
                F::MAX_LEAVES,
                &operations[..1],
                &chunks,
                &root,
            ),
            Err(merkle::Error::InvalidProof)
        ));

        assert!(matches!(
            verify_proof_and_extract_digests::<F, _, Sha256, N>(
                &proof,
                proof.proof.leaves,
                &operations[..1],
                &chunks,
                &root,
            ),
            Err(merkle::Error::InvalidProof)
        ));

        assert!(matches!(
            verify_proof_and_extract_digests::<F, _, Sha256, N>(
                &proof,
                start,
                &operations,
                &chunks[..chunks.len() - 1],
                &root,
            ),
            Err(merkle::Error::InvalidProof)
        ));

        let mut missing_partial = proof.clone();
        missing_partial.partial_chunk_digest = None;
        assert!(matches!(
            verify_proof_and_extract_digests::<F, _, Sha256, N>(
                &missing_partial,
                start,
                &operations,
                &chunks,
                &root,
            ),
            Err(merkle::Error::InvalidProof)
        ));

        let mut broken_merkle = proof;
        assert!(!broken_merkle.proof.digests.is_empty());
        broken_merkle.proof.digests.clear();
        assert!(matches!(
            verify_proof_and_extract_digests::<F, _, Sha256, N>(
                &broken_merkle,
                start,
                &operations,
                &chunks,
                &root,
            ),
            Err(merkle::Error::InvalidProof)
        ));
    }

    #[test_async]
    async fn test_verify_proof_and_extract_digests_rejects_metadata_mismatches_mmb() {
        type F = mmb::Family;
        const N: usize = 1;
        let start = Location::<F>::new(14);
        let end = Location::<F>::new(18);
        let (hasher, proof, operations, chunks, root, _ops) =
            current_range_proof_fixture::<F, N>(18, start..end).await;

        assert!(proof.pending_chunk_digest.is_some());

        let mut missing_pending = proof.clone();
        missing_pending.pending_chunk_digest = None;
        assert!(matches!(
            verify_proof_and_extract_digests::<F, _, Sha256, N>(
                &missing_pending,
                start,
                &operations,
                &chunks,
                &root,
            ),
            Err(merkle::Error::InvalidProof)
        ));

        let mut wrong_pending = proof.clone();
        wrong_pending.pending_chunk_digest = Some(hasher.digest(b"wrong pending"));
        assert!(matches!(
            verify_proof_and_extract_digests::<F, _, Sha256, N>(
                &wrong_pending,
                start,
                &operations,
                &chunks,
                &root,
            ),
            Err(merkle::Error::InvalidProof)
        ));

        let aligned_start = Location::<F>::new(8);
        let aligned_end = Location::<F>::new(12);
        let (hasher, proof, operations, chunks, root, _ops) =
            current_range_proof_fixture::<F, N>(16, aligned_start..aligned_end).await;
        assert!(proof.partial_chunk_digest.is_none());

        // A chunk-aligned proof must not carry partial metadata.
        let mut unexpected_partial = proof;
        unexpected_partial.partial_chunk_digest = Some(hasher.digest(b"unexpected partial"));
        assert!(matches!(
            verify_proof_and_extract_digests::<F, _, Sha256, N>(
                &unexpected_partial,
                aligned_start,
                &operations,
                &chunks,
                &root,
            ),
            Err(merkle::Error::InvalidProof)
        ));
    }

    #[test_async]
    async fn test_verify_proof_and_extract_digests_mmr() {
        verify_proof_and_extract_digests_inner::<mmr::Family>().await;
    }

    #[test_async]
    async fn test_verify_proof_and_extract_digests_mmb() {
        verify_proof_and_extract_digests_inner::<mmb::Family>().await;
    }

    /// Active chunks always have a single h=G peak; multi-peak structure can only appear
    /// at the pending-chunk index. This test exhaustively scans MMB sizes that have a
    /// pending chunk (the only configuration where multi-peak chunks ever existed) and
    /// asserts that every graftable chunk has exactly one peak.
    #[test_async]
    async fn test_graftable_chunks_always_single_peak_at_pending_sizes() {
        type F = mmb::Family;
        const N: usize = 1;

        let hasher = qmdb::hasher::<Sha256>();
        let grafting_height = grafting::height::<N>();
        let chunk_bits = BitMap::<N>::CHUNK_SIZE_BITS;

        let mut found_any_pending = false;
        for leaves in chunk_bits * 3..=128u64 {
            let leaves_loc = mmb::Location::new(leaves);
            let leaves_count = *leaves_loc;
            let complete = leaves_count / chunk_bits;
            let graftable =
                grafting::graftable_chunks::<F>(leaves_count, grafting_height).min(complete);
            if graftable == complete {
                continue; // no pending chunk at this size
            }
            found_any_pending = true;

            // Pending chunks (index >= graftable) are allowed multi-peak; their digests
            // are hashed into the canonical root separately.
            let size = F::location_to_position(leaves_loc);
            for chunk_idx in 0..graftable {
                let count = F::chunk_peaks(size, chunk_idx, grafting_height).count();
                assert_eq!(
                    count, 1,
                    "graftable chunk {chunk_idx} has {count} peaks (leaves={leaves_count}, graftable={graftable}, complete={complete})"
                );
            }
        }
        assert!(
            found_any_pending,
            "expected at least one MMB size in [{}, 128] with a pending chunk",
            chunk_bits * 3
        );

        // End-to-end: build a proof for an op in a chunk-aligned MMB whose chunk 1 is
        // multi-peak, and confirm the proof has only the standard digest material.
        let leaf_count = (chunk_bits * 2..=256u64)
            .filter(|leaves| leaves % chunk_bits == 0)
            .find(|&leaves| {
                let size = F::location_to_position(mmb::Location::new(leaves));
                F::chunk_peaks(size, 1, grafting_height).nth(1).is_some()
            })
            .expect("expected a chunk-aligned MMB size whose chunk 1 is multi-peak");
        let loc = mmb::Location::new(chunk_bits + 1);

        let mut status = BitMap::<N>::new();
        for _ in 0..leaf_count {
            status.push(true);
        }
        let ops = build_test_mem(&hasher, mmb::mem::Mmb::new(), leaf_count);
        let ops_root = ops.root(&hasher, 0).unwrap();

        let graftable_chunks_for_test = grafting::graftable_chunks::<F>(
            *Location::<F>::try_from(ops.size()).unwrap(),
            grafting_height,
        )
        .min(<BitMap<N> as BitmapReadable<N>>::complete_chunks(&status) as u64)
            as usize;
        let chunk_inputs: Vec<_> = (0..graftable_chunks_for_test)
            .map(|chunk_idx| {
                (
                    chunk_idx,
                    <BitMap<N> as BitmapReadable<N>>::get_chunk(&status, chunk_idx),
                )
            })
            .collect();
        let mut leaf_digests =
            compute_grafted_leaves::<F, Sha256, Sequential, N>(&ops, chunk_inputs, &Sequential)
                .await
                .unwrap();
        leaf_digests.sort_by_key(|(chunk_idx, _)| *chunk_idx);

        let grafted_hasher = grafting::GraftedHasher::<F, _>::new(hasher.clone(), grafting_height);
        let mut grafted = Mem::<F, sha256::Digest>::new();
        let merkleized = {
            let mut batch = grafted.new_batch();
            for (_, digest) in leaf_digests {
                batch = batch.add_leaf_digest(digest);
            }
            batch.merkleize(&grafted, &grafted_hasher)
        };
        grafted.apply_batch(&merkleized).unwrap();

        let storage = grafting::Storage::<F, Sha256, _, _>::new(&grafted, grafting_height, &ops);
        let ops_leaves_for_root = Location::<F>::try_from(ops.size()).unwrap();
        let root = db::compute_ops_root_witness::<F, Sha256, _, _, N>(
            &status,
            &storage,
            ops_leaves_for_root,
            Location::new(0),
        )
        .await
        .unwrap()
        .root::<Sha256>(&ops_root);
        let proof = RangeProof::new::<Sha256, _, N>(
            &status,
            &storage,
            Location::new(0),
            loc..loc + 1,
            ops_root,
        )
        .await
        .unwrap();

        let element = hasher.digest(&(*loc).to_be_bytes());
        let chunk_idx = (*loc / chunk_bits) as usize;
        assert!(proof.verify::<Sha256, _, N>(
            loc,
            &[element],
            &[<BitMap<N> as BitmapReadable<N>>::get_chunk(
                &status, chunk_idx
            )],
            &root,
        ));

        let mut tampered = proof.clone();
        tampered.proof.inactive_peaks = 1;
        assert!(!tampered.verify::<Sha256, _, N>(
            loc,
            &[element],
            &[<BitMap<N> as BitmapReadable<N>>::get_chunk(
                &status, chunk_idx
            )],
            &root,
        ));

        let mut tampered = proof.clone();
        tampered.proof.inactive_peaks = usize::MAX;
        assert!(!tampered.verify::<Sha256, _, N>(
            loc,
            &[element],
            &[<BitMap<N> as BitmapReadable<N>>::get_chunk(
                &status, chunk_idx
            )],
            &root,
        ));

        let mut tampered = proof;
        assert!(!tampered.proof.digests.is_empty());
        tampered.proof.digests[0] = hasher.digest(b"fake generic sibling");
        assert!(!tampered.verify::<Sha256, _, N>(
            loc,
            &[element],
            &[<BitMap<N> as BitmapReadable<N>>::get_chunk(
                &status, chunk_idx
            )],
            &root,
        ));
    }

    /// Pending and partial chunks coexist when the bitmap has both (1) a chunk whose bits
    /// are complete but whose h=G ancestor isn't yet born, AND (2) an in-progress trailing
    /// chunk. At G=3 (N=1) chunk 0 is pending for ops_leaves in [8, 11), and any ops_leaves
    /// strictly in (8, 11) also has a partial trailing chunk. This test builds those states
    /// and round-trips a `RangeProof` that spans both regions.
    #[test_async]
    async fn test_pending_and_partial_coexist_at_g_3() {
        type F = mmb::Family;
        const N: usize = 1; // G = 3, chunk_bits = 8

        let hasher = qmdb::hasher::<Sha256>();
        let grafting_height = grafting::height::<N>();
        let chunk_bits = BitMap::<N>::CHUNK_SIZE_BITS;
        assert_eq!(grafting_height, 3);
        assert_eq!(chunk_bits, 8);

        // For G=3, chunk 0 is pending while ops_leaves is in [8, 11). Pending+partial
        // coexistence holds for k in [1, 2] (k=3 transitions chunk 0 to graftable).
        for k in 1u64..=2 {
            let leaf_count = chunk_bits + k;
            let mut status = BitMap::<N>::new();
            for _ in 0..leaf_count {
                status.push(true);
            }
            let ops = build_test_mem(&hasher, mmb::mem::Mmb::new(), leaf_count);
            let ops_root = ops.root(&hasher, 0).unwrap();

            let complete = <BitMap<N> as BitmapReadable<N>>::complete_chunks(&status) as u64;
            let graftable =
                grafting::graftable_chunks::<F>(leaf_count, grafting_height).min(complete);
            let next_bit = leaf_count % chunk_bits;
            assert_eq!(complete, 1);
            assert_eq!(graftable, 0);
            assert!(next_bit > 0, "expected partial chunk for k={k}");

            // Build a grafted tree from the (zero) graftable chunks and a Storage covering
            // the post-state.
            let chunk_inputs: Vec<_> = (0..graftable as usize)
                .map(|chunk_idx| {
                    (
                        chunk_idx,
                        <BitMap<N> as BitmapReadable<N>>::get_chunk(&status, chunk_idx),
                    )
                })
                .collect();
            let leaf_digests =
                compute_grafted_leaves::<F, Sha256, Sequential, N>(&ops, chunk_inputs, &Sequential)
                    .await
                    .unwrap();
            let grafted_hasher =
                grafting::GraftedHasher::<F, _>::new(hasher.clone(), grafting_height);
            let mut grafted = Mem::<F, sha256::Digest>::new();
            if !leaf_digests.is_empty() {
                let merkleized = {
                    let mut batch = grafted.new_batch();
                    for (_, digest) in leaf_digests {
                        batch = batch.add_leaf_digest(digest);
                    }
                    batch.merkleize(&grafted, &grafted_hasher)
                };
                grafted.apply_batch(&merkleized).unwrap();
            }
            let storage =
                grafting::Storage::<F, Sha256, _, _>::new(&grafted, grafting_height, &ops);

            let ops_leaves_for_root = Location::<F>::try_from(ops.size()).unwrap();
            let witness = db::compute_ops_root_witness::<F, Sha256, _, _, N>(
                &status,
                &storage,
                ops_leaves_for_root,
                Location::new(0),
            )
            .await
            .unwrap();
            let canonical_root = witness.root::<Sha256>(&ops_root);
            assert!(
                witness.pending_chunk_digest.is_some(),
                "expected pending chunk at k={k}"
            );
            assert!(
                witness.partial_chunk.is_some(),
                "expected partial chunk at k={k}"
            );

            // Range proof spanning the pending chunk into the partial bits
            let start = mmb::Location::new(0);
            let end = mmb::Location::new(leaf_count);
            let proof = RangeProof::new::<Sha256, _, N>(
                &status,
                &storage,
                Location::new(0),
                start..end,
                ops_root,
            )
            .await
            .unwrap();
            assert!(
                proof.pending_chunk_digest.is_some(),
                "expected RangeProof pending_chunk_digest at k={k}"
            );
            assert!(
                proof.partial_chunk_digest.is_some(),
                "expected RangeProof partial_chunk_digest at k={k}"
            );

            let elements: Vec<sha256::Digest> = (0..leaf_count)
                .map(|i| hasher.digest(&i.to_be_bytes()))
                .collect();
            // Range covers chunks 0..=1: chunk 0 is pending, chunk 1 is partial. Provide both.
            let chunks: Vec<[u8; N]> = (0..=1)
                .map(|i| <BitMap<N> as BitmapReadable<N>>::get_chunk(&status, i))
                .collect();
            assert!(
                proof.verify::<Sha256, _, N>(start, &elements, &chunks, &canonical_root),
                "RangeProof verify failed at k={k}"
            );

            let pending_loc = mmb::Location::new(3);
            let pending_proof = RangeProof::new::<Sha256, _, N>(
                &status,
                &storage,
                Location::new(0),
                pending_loc..pending_loc + 1,
                ops_root,
            )
            .await
            .unwrap();
            assert!(
                pending_proof.pending_chunk_digest.is_some(),
                "expected single-element proof to carry pending chunk digest at k={k}"
            );
            let pending_element = hasher.digest(&(*pending_loc).to_be_bytes());
            assert!(
                pending_proof.verify::<Sha256, _, N>(
                    pending_loc,
                    &[pending_element],
                    &[chunks[0]],
                    &canonical_root,
                ),
                "single-element proof inside pending chunk failed at k={k}"
            );

            // Tamper with the pending chunk digest or its supplied bytes.
            let mut tampered = proof.clone();
            tampered.pending_chunk_digest = Some(hasher.digest(b"fake pending"));
            assert!(
                !tampered.verify::<Sha256, _, N>(start, &elements, &chunks, &canonical_root),
                "tampered pending digest accepted at k={k}"
            );

            let mut tampered = proof.clone();
            tampered.pending_chunk_digest = None;
            assert!(
                !tampered.verify::<Sha256, _, N>(start, &elements, &chunks, &canonical_root),
                "missing pending digest accepted at k={k}"
            );

            let mut bad_chunks = chunks.clone();
            bad_chunks[0][0] ^= 1;
            assert!(
                !proof.verify::<Sha256, _, N>(start, &elements, &bad_chunks, &canonical_root),
                "tampered pending chunk bytes accepted at k={k}"
            );
        }
    }

    /// Appending one op at the exact birth size of a pending chunk's h=G ancestor causes
    /// the chunk to transition from pending to graftable. The canonical root must change, and
    /// a freshly-rebuilt grafted tree from the post-state must contain the now-graftable
    /// chunk's leaf.
    #[test_async]
    async fn test_pending_to_graftable_transition_at_birth_size() {
        type F = mmb::Family;
        const N: usize = 1; // G = 3, chunk_bits = 8

        let hasher = qmdb::hasher::<Sha256>();
        let grafting_height = grafting::height::<N>();
        assert_eq!(grafting_height, 3);

        // chunk 0's h=G ancestor: birth = 3*2^(G-1) - 1 = 11 for G=3.
        let birth = (3u64 << (grafting_height - 1)) - 1;
        let pre_state_leaves = birth - 1; // = 10: chunk 0 still pending
        let post_state_leaves = birth; // = 11: chunk 0 just graftable

        assert_eq!(pre_state_leaves, 10);
        assert_eq!(post_state_leaves, 11);

        let graftable_pre = grafting::graftable_chunks::<F>(pre_state_leaves, grafting_height);
        let graftable_post = grafting::graftable_chunks::<F>(post_state_leaves, grafting_height);
        assert_eq!(graftable_pre, 0);
        assert_eq!(graftable_post, 1);

        // Pre-state canonical root: chunk 0 is pending; grafted tree empty.
        let mut status_pre = BitMap::<N>::new();
        for _ in 0..pre_state_leaves {
            status_pre.push(true);
        }
        let ops_pre = build_test_mem(&hasher, mmb::mem::Mmb::new(), pre_state_leaves);
        let ops_root_pre = ops_pre.root(&hasher, 0).unwrap();
        let grafted_pre = Mem::<F, sha256::Digest>::new();
        let storage_pre =
            grafting::Storage::<F, Sha256, _, _>::new(&grafted_pre, grafting_height, &ops_pre);
        let canonical_pre = db::compute_ops_root_witness::<F, Sha256, _, _, N>(
            &status_pre,
            &storage_pre,
            Location::<F>::new(pre_state_leaves),
            Location::new(0),
        )
        .await
        .unwrap()
        .root::<Sha256>(&ops_root_pre);

        // Post-state canonical root.
        let mut status_post = BitMap::<N>::new();
        for _ in 0..post_state_leaves {
            status_post.push(true);
        }
        let ops_post = build_test_mem(&hasher, mmb::mem::Mmb::new(), post_state_leaves);
        let ops_root_post = ops_post.root(&hasher, 0).unwrap();
        // After transition chunk 0 has a single h=G ancestor; build the grafted tree.
        let leaf_digests = compute_grafted_leaves::<F, Sha256, Sequential, N>(
            &ops_post,
            core::iter::once((
                0usize,
                <BitMap<N> as BitmapReadable<N>>::get_chunk(&status_post, 0),
            )),
            &Sequential,
        )
        .await
        .unwrap();
        assert_eq!(
            leaf_digests.len(),
            1,
            "post-state must have 1 graftable chunk"
        );
        let grafted_hasher = grafting::GraftedHasher::<F, _>::new(hasher.clone(), grafting_height);
        let mut grafted_post = Mem::<F, sha256::Digest>::new();
        let merkleized = grafted_post
            .new_batch()
            .add_leaf_digest(leaf_digests[0].1)
            .merkleize(&grafted_post, &grafted_hasher);
        grafted_post.apply_batch(&merkleized).unwrap();
        let storage_post =
            grafting::Storage::<F, Sha256, _, _>::new(&grafted_post, grafting_height, &ops_post);

        let canonical_post = db::compute_ops_root_witness::<F, Sha256, _, _, N>(
            &status_post,
            &storage_post,
            Location::<F>::new(post_state_leaves),
            Location::new(0),
        )
        .await
        .unwrap()
        .root::<Sha256>(&ops_root_post);

        assert_ne!(
            canonical_pre, canonical_post,
            "canonical root must change when chunk 0 transitions from pending to graftable"
        );
    }

    #[test_async]
    async fn test_range_proof_allows_ops_and_grafted_inactive_counts_to_differ() {
        type F = mmb::Family;
        const N: usize = 1;

        let hasher = qmdb::hasher::<Sha256>();
        let grafting_height = grafting::height::<N>();
        let chunk_bits = BitMap::<N>::CHUNK_SIZE_BITS;
        let leaf_count = chunk_bits;
        let leaves = mmb::Location::new(leaf_count);
        let inactivity_floor = mmb::Location::new(chunk_bits - 2);

        let ops_inactive_peaks = F::inactive_peaks(leaves, inactivity_floor);
        let aligned_inactive =
            grafting::chunk_aligned_inactive_peaks::<F>(leaves, inactivity_floor, grafting_height)
                .unwrap();
        assert_ne!(ops_inactive_peaks, aligned_inactive);

        let mut status = BitMap::<N>::new();
        for _ in 0..leaf_count {
            status.push(true);
        }
        let ops = build_test_mem(&hasher, mmb::mem::Mmb::new(), leaf_count);

        // The ops root is the inner QMDB log root and commits the ops-tree inactive peak count.
        // The grafted bitmap root commits the chunk-aligned count, since bitmap chunks are
        // the atomic inactive-prefix boundary for the current root.
        let ops_root = ops.root(&hasher, ops_inactive_peaks).unwrap();

        let graftable_chunks_for_test = grafting::graftable_chunks::<F>(
            *Location::<F>::try_from(ops.size()).unwrap(),
            grafting_height,
        )
        .min(<BitMap<N> as BitmapReadable<N>>::complete_chunks(&status) as u64)
            as usize;
        let chunk_inputs: Vec<_> = (0..graftable_chunks_for_test)
            .map(|chunk_idx| {
                (
                    chunk_idx,
                    <BitMap<N> as BitmapReadable<N>>::get_chunk(&status, chunk_idx),
                )
            })
            .collect();
        let mut leaf_digests =
            compute_grafted_leaves::<F, Sha256, Sequential, N>(&ops, chunk_inputs, &Sequential)
                .await
                .unwrap();
        leaf_digests.sort_by_key(|(chunk_idx, _)| *chunk_idx);

        let grafted_hasher = grafting::GraftedHasher::<F, _>::new(hasher.clone(), grafting_height);
        let mut grafted = Mem::<F, sha256::Digest>::new();
        let merkleized = {
            let mut batch = grafted.new_batch();
            for (_, digest) in leaf_digests {
                batch = batch.add_leaf_digest(digest);
            }
            batch.merkleize(&grafted, &grafted_hasher)
        };
        grafted.apply_batch(&merkleized).unwrap();

        let storage = grafting::Storage::<F, Sha256, _, _>::new(&grafted, grafting_height, &ops);
        let ops_leaves_for_root = Location::<F>::try_from(ops.size()).unwrap();
        let root = db::compute_ops_root_witness::<F, Sha256, _, _, N>(
            &status,
            &storage,
            ops_leaves_for_root,
            inactivity_floor,
        )
        .await
        .unwrap()
        .root::<Sha256>(&ops_root);

        let loc = mmb::Location::new(chunk_bits - 1);
        let proof = RangeProof::new::<Sha256, _, N>(
            &status,
            &storage,
            inactivity_floor,
            loc..loc + 1,
            ops_root,
        )
        .await
        .unwrap();
        assert_eq!(proof.proof.inactive_peaks, aligned_inactive);

        let element = hasher.digest(&(*loc).to_be_bytes());
        let chunk = <BitMap<N> as BitmapReadable<N>>::get_chunk(&status, 0);
        assert!(proof.verify::<Sha256, _, N>(loc, &[element], &[chunk], &root));
    }

    fn invalid_chunk_sizes() -> impl Iterator<Item = usize> {
        [0, 3, usize::MAX, 1 << (usize::BITS - 1)]
            .into_iter()
            .chain(usize::try_from(1u64 << 60).ok())
    }

    async fn check_dynamic_proofs<F: Graftable, const N: usize>() {
        let chunk_bits = (N * 8) as u64;
        let height = chunk_bits.trailing_zeros() as u64;
        for leaves in [
            chunk_bits - 1,
            chunk_bits,
            chunk_bits + 1,
            chunk_bits + height,
            chunk_bits * 2,
            chunk_bits * 2 + 2,
        ] {
            let start = Location::<F>::new(chunk_bits - 2);
            let (_, proof, operations, chunks, root, _) =
                current_range_proof_fixture::<F, N>(leaves, start..Location::new(leaves)).await;
            assert!(proof.verify::<Sha256, _, N>(start, &operations, &chunks, &root));
            let slices = chunks.iter().map(<[u8; N]>::as_slice).collect::<Vec<_>>();
            assert!(proof.verify_with_chunk_size::<Sha256, _>(
                start,
                &operations,
                &slices,
                N,
                &root
            ));
            assert!(!proof.verify_with_chunk_size::<Sha256, _>(
                start,
                &operations,
                &slices,
                N,
                &Sha256::hash(&[b"wrong root"]),
            ));

            for loc in [start, Location::new(leaves - 1)] {
                let (_, range_proof, operations, chunks, root, _) =
                    current_range_proof_fixture::<F, N>(leaves, loc..loc + 1).await;
                let native = constant::OperationProof::<F, sha256::Digest, N> {
                    loc,
                    chunk: chunks[0],
                    range_proof,
                };
                assert!(native.verify::<Sha256, _>(operations[0], &root));
                let encoded = native.encode();
                let max_digests = native.range_proof.proof.digests.len();
                let dynamic = dynamic::OperationProof::<F, sha256::Digest>::decode_cfg(
                    encoded.clone(),
                    &(N, max_digests),
                )
                .unwrap();
                assert_eq!(dynamic.encode(), encoded);
                assert_eq!(dynamic.encode_size(), encoded.len());
                assert_eq!(dynamic.loc, loc);
                assert_eq!(dynamic.chunk.as_ref(), native.chunk.as_slice());
                assert!(dynamic.verify::<Sha256, _>(operations[0], &root));
                assert!(!dynamic.verify::<Sha256, _>(Sha256::hash(&[b"wrong operation"]), &root,));
                assert!(
                    !dynamic.verify::<Sha256, _>(operations[0], &Sha256::hash(&[b"wrong root"]),)
                );

                let mut inactive = dynamic;
                let mut chunk = inactive.chunk.to_vec();
                let bit = (*loc % chunk_bits) as usize;
                chunk[bit / 8] &= !(1 << (bit % 8));
                inactive.chunk = Bytes::from(chunk);
                assert!(!inactive.verify::<Sha256, _>(operations[0], &root));
            }
        }
    }

    #[test_async]
    async fn dynamic_proofs_match_native_mmr() {
        check_dynamic_proofs::<mmr::Family, 1>().await;
        check_dynamic_proofs::<mmr::Family, 32>().await;
        check_dynamic_proofs::<mmr::Family, 64>().await;
    }

    #[test_async]
    async fn dynamic_proofs_match_native_mmb() {
        check_dynamic_proofs::<mmb::Family, 1>().await;
        check_dynamic_proofs::<mmb::Family, 32>().await;
        check_dynamic_proofs::<mmb::Family, 64>().await;
    }

    async fn check_dynamic_range_rejections<F: Graftable>() {
        const N: usize = 1;
        let start = Location::<F>::new(6);
        let (_, proof, operations, chunks, root, _) =
            current_range_proof_fixture::<F, N>(18, start..Location::new(18)).await;
        let chunks = chunks
            .iter()
            .map(|chunk| chunk.to_vec())
            .collect::<Vec<_>>();
        for chunk_size in invalid_chunk_sizes() {
            assert!(!proof.verify_with_chunk_size::<Sha256, _>(
                start,
                &operations,
                &chunks,
                chunk_size,
                &root,
            ));
        }
        assert!(!proof.verify_with_chunk_size::<Sha256, _>(start, &operations, &chunks, 2, &root));
        assert!(!proof.verify_with_chunk_size::<Sha256, _>(
            start,
            &operations[..0],
            &chunks,
            N,
            &root
        ));
        assert!(!proof.verify_with_chunk_size::<Sha256, _>(
            start,
            &operations,
            &chunks[..0],
            N,
            &root
        ));
        assert!(!proof.verify_with_chunk_size::<Sha256, _>(
            start,
            &operations,
            &chunks[..chunks.len() - 1],
            N,
            &root,
        ));
        assert!(!proof.verify_with_chunk_size::<Sha256, _>(
            proof.proof.leaves,
            &operations,
            &chunks,
            N,
            &root,
        ));
        assert!(!proof.verify_with_chunk_size::<Sha256, _>(
            F::MAX_LEAVES,
            &operations,
            &chunks,
            N,
            &root,
        ));

        let mut extra = chunks.clone();
        extra.push(chunks[0].clone());
        assert!(!proof.verify_with_chunk_size::<Sha256, _>(start, &operations, &extra, N, &root));
        for chunk_len in [0, 2, 3] {
            let mut malformed = chunks.clone();
            malformed[1].resize(chunk_len, 0);
            assert!(!proof.verify_with_chunk_size::<Sha256, _>(
                start,
                &operations,
                &malformed,
                N,
                &root,
            ));
        }

        let mut tampered = chunks.clone();
        tampered.last_mut().unwrap()[0] ^= 1;
        assert!(!proof.verify_with_chunk_size::<Sha256, _>(
            start,
            &operations,
            &tampered,
            N,
            &root
        ));
        let mut missing_partial = proof.clone();
        assert!(missing_partial.partial_chunk_digest.take().is_some());
        assert!(!missing_partial.verify_with_chunk_size::<Sha256, _>(
            start,
            &operations,
            &chunks,
            N,
            &root,
        ));
        let mut wrong_operations = operations;
        wrong_operations[0] = Sha256::hash(&[b"wrong operation"]);
        assert!(!proof.verify_with_chunk_size::<Sha256, _>(
            start,
            &wrong_operations,
            &chunks,
            N,
            &root,
        ));
    }

    #[test_async]
    async fn dynamic_range_rejects_malformed_inputs() {
        check_dynamic_range_rejections::<mmr::Family>().await;
        check_dynamic_range_rejections::<mmb::Family>().await;
    }

    async fn check_dynamic_operation_codec_rejections<F: Graftable>() {
        const N: usize = 32;
        let loc = Location::<F>::new(14);
        let (_, range_proof, operations, chunks, root, _) =
            current_range_proof_fixture::<F, N>(18, loc..loc + 1).await;
        let native = constant::OperationProof::<F, sha256::Digest, N> {
            loc,
            chunk: chunks[0],
            range_proof,
        };
        let encoded = native.encode();
        let max_digests = native.range_proof.proof.digests.len();
        assert!(max_digests > 0);
        assert!(
            dynamic::OperationProof::<F, sha256::Digest>::decode_cfg(
                encoded.clone(),
                &(N, max_digests - 1),
            )
            .is_err()
        );
        for end in 0..encoded.len() {
            assert!(
                dynamic::OperationProof::<F, sha256::Digest>::decode_cfg(
                    encoded.slice(..end),
                    &(N, max_digests),
                )
                .is_err(),
                "truncated proof decoded at {end}"
            );
        }
        let mut trailing = encoded.to_vec();
        trailing.push(0);
        assert!(
            dynamic::OperationProof::<F, sha256::Digest>::decode_cfg(trailing, &(N, max_digests),)
                .is_err()
        );
        for chunk_size in invalid_chunk_sizes() {
            assert!(matches!(
                dynamic::OperationProof::<F, sha256::Digest>::decode_cfg(
                    encoded.clone(),
                    &(chunk_size, max_digests),
                ),
                Err(commonware_codec::Error::Invalid(_, _)),
            ));
        }
        for chunk_size in [1, N / 2, N * 2] {
            if let Ok(dynamic) = dynamic::OperationProof::<F, sha256::Digest>::decode_cfg(
                encoded.clone(),
                &(chunk_size, max_digests),
            ) {
                assert!(!dynamic.verify::<Sha256, _>(operations[0], &root));
            }
        }
        let dynamic =
            dynamic::OperationProof::<F, sha256::Digest>::decode_cfg(encoded, &(N, max_digests))
                .unwrap();
        for chunk in [Bytes::new(), Bytes::from_static(&[0; 3])] {
            let mut malformed = dynamic.clone();
            malformed.chunk = chunk;
            assert!(!malformed.verify::<Sha256, _>(operations[0], &root));
        }
    }

    #[test_async]
    async fn dynamic_operation_codec_rejects_malformed_inputs() {
        check_dynamic_operation_codec_rejections::<mmr::Family>().await;
        check_dynamic_operation_codec_rejections::<mmb::Family>().await;
    }

    struct PreloadedBitmap<'a> {
        bitmap: &'a BitMap<1>,
        chunks: BTreeMap<usize, [u8; 1]>,
        reads: Mutex<BTreeSet<usize>>,
    }

    impl BitmapReadable<1> for PreloadedBitmap<'_> {
        fn complete_chunks(&self) -> usize {
            self.bitmap.complete_chunks()
        }

        fn get_chunk(&self, chunk: usize) -> [u8; 1] {
            self.reads.lock().insert(chunk);
            self.chunks[&chunk]
        }

        fn last_chunk(&self) -> ([u8; 1], u64) {
            let (_, bits) = self.bitmap.last_chunk();
            let chunk = BitMap::<1>::to_chunk_index(self.len() - 1);
            (self.get_chunk(chunk), bits)
        }

        fn pruned_chunks(&self) -> usize {
            self.bitmap.pruned_chunks()
        }

        fn len(&self) -> u64 {
            self.bitmap.len()
        }
    }

    async fn fixture<F: Graftable>(
        leaves: u64,
        pruned: u64,
    ) -> (BitMap<1>, Mem<F, sha256::Digest>, Mem<F, sha256::Digest>) {
        let hasher = qmdb::hasher::<Sha256>();
        let height = grafting::height::<1>();
        let ops = build_test_mem(&hasher, Mem::<F, sha256::Digest>::new(), leaves);
        let mut bitmap = BitMap::<1>::new();
        for loc in 0..leaves {
            bitmap.push(loc >= pruned * 8);
        }
        let chunks = (0..grafting::graftable_chunks::<F>(leaves, height))
            .map(|chunk| (chunk as usize, *bitmap.get_chunk(chunk as usize)));
        let mut digests =
            compute_grafted_leaves::<F, Sha256, Sequential, 1>(&ops, chunks, &Sequential)
                .await
                .unwrap();
        digests.sort_unstable_by_key(|(chunk, _)| *chunk);
        let mut grafted = Mem::<F, sha256::Digest>::new();
        if !digests.is_empty() {
            let mut batch = grafted.new_batch();
            for (_, digest) in digests {
                batch = batch.add_leaf_digest(digest);
            }
            let hasher = grafting::GraftedHasher::<F, _>::new(hasher, height);
            let batch = batch.merkleize(&grafted, &hasher);
            grafted.apply_batch(&batch).unwrap();
        }
        bitmap.prune_to_bit(pruned * 8);
        (bitmap, ops, grafted)
    }

    async fn check_constructor_reads<F: Graftable + PartialEq>() {
        for leaves in [1, 7, 8, 9, 10, 11, 16, 17, 18, 24, 25] {
            let graftable = grafting::graftable_chunks::<F>(leaves, grafting::height::<1>());
            for pruned in 0..=graftable {
                let floor = Location::<F>::new(pruned * 8);
                if *floor == leaves {
                    continue;
                }
                let (bitmap, ops, grafted) = fixture::<F>(leaves, pruned).await;
                let hasher = qmdb::hasher::<Sha256>();
                let ops_root = ops.root(&hasher, 0).unwrap();
                let storage = grafting::Storage::<F, Sha256, _, _>::new(
                    &grafted,
                    grafting::height::<1>(),
                    &ops,
                );
                let root = db::compute_ops_root_witness::<F, Sha256, _, _, 1>(
                    &bitmap,
                    &storage,
                    Location::new(leaves),
                    floor,
                )
                .await
                .unwrap()
                .root::<Sha256>(&ops_root);
                for location in core::iter::once(None)
                    .chain((*floor..leaves).map(|loc| Some(Location::new(loc))))
                {
                    let required = required_chunks::<F, 1>(
                        Location::new(leaves),
                        bitmap.len(),
                        pruned,
                        location,
                    )
                    .unwrap()
                    .collect::<Vec<_>>();
                    assert!(required.windows(2).all(|pair| pair[0] < pair[1]));
                    let ops_leaves = Location::new(leaves);
                    let planned = location.map_or_else(
                        || {
                            merkle::RangePlan::new(ops_leaves, floor..ops_leaves)
                                .unwrap()
                                .positions()
                        },
                        |loc| {
                            merkle::ElementPlan::new(ops_leaves, loc)
                                .unwrap()
                                .positions()
                        },
                    );
                    let fetched: BTreeMap<_, _> = planned
                        .iter()
                        .copied()
                        .zip(storage.get_nodes(&planned).await.unwrap())
                        .collect();
                    let get_node = |pos: Position<F>| fetched.get(&pos).copied();
                    let preloaded = PreloadedBitmap {
                        bitmap: &bitmap,
                        chunks: required
                            .iter()
                            .map(|&chunk| (chunk as usize, *bitmap.get_chunk(chunk as usize)))
                            .collect(),
                        reads: Mutex::new(BTreeSet::new()),
                    };
                    if let Some(loc) = location {
                        let proof =
                            constant::OperationProof::<F, sha256::Digest, 1>::new::<Sha256, _>(
                                &preloaded, &storage, floor, loc, ops_root,
                            )
                            .await
                            .unwrap();
                        let built =
                            constant::OperationProof::<F, sha256::Digest, 1>::build::<Sha256>(
                                &preloaded,
                                merkle::ElementPlan::new(ops_leaves, loc).unwrap(),
                                get_node,
                                floor,
                                ops_root,
                            )
                            .unwrap();
                        assert_eq!(built, proof);
                        assert!(
                            proof.verify::<Sha256, _>(hasher.digest(&(*loc).to_be_bytes()), &root,)
                        );
                        let proof = dynamic::OperationProof::<F, sha256::Digest>::decode_cfg(
                            proof.encode(),
                            &(1, 64),
                        )
                        .unwrap();
                        assert!(
                            proof.verify::<Sha256, _>(hasher.digest(&(*loc).to_be_bytes()), &root)
                        );
                    } else {
                        let proof = RangeProof::new::<Sha256, _, 1>(
                            &preloaded,
                            &storage,
                            floor,
                            floor..Location::new(leaves),
                            ops_root,
                        )
                        .await
                        .unwrap();
                        let built = RangeProof::build::<Sha256, 1>(
                            &preloaded,
                            merkle::RangePlan::new(ops_leaves, floor..ops_leaves).unwrap(),
                            get_node,
                            floor,
                            ops_root,
                        )
                        .unwrap();
                        assert_eq!(built, proof);
                        let elements = (*floor..leaves)
                            .map(|loc| hasher.digest(&loc.to_be_bytes()))
                            .collect::<Vec<_>>();
                        let chunks = (pruned..leaves.div_ceil(8))
                            .map(|chunk| *bitmap.get_chunk(chunk as usize))
                            .collect::<Vec<_>>();
                        assert!(proof.verify::<Sha256, _, 1>(floor, &elements, &chunks, &root));
                        assert!(proof.verify_with_chunk_size::<Sha256, _>(
                            floor, &elements, &chunks, 1, &root,
                        ));
                    }
                    let read_chunks = preloaded
                        .reads
                        .into_inner()
                        .into_iter()
                        .map(Widen::widen)
                        .collect::<Vec<_>>();
                    assert_eq!(
                        read_chunks, required,
                        "leaves={leaves}, pruned={pruned}, location={location:?}",
                    );
                }
            }
        }
    }

    #[test_async]
    async fn required_chunks_match_constructor_reads() {
        check_constructor_reads::<mmr::Family>().await;
        check_constructor_reads::<mmb::Family>().await;
    }

    #[test_async]
    async fn operation_proof_build_rejects_pruned_locations() {
        type F = mmr::Family;
        let (bitmap, ops, _) = fixture::<F>(16, 1).await;
        let ops_root = ops.root(&qmdb::hasher::<Sha256>(), 0).unwrap();
        let plan = merkle::ElementPlan::new(Location::new(16), Location::new(3)).unwrap();
        assert!(matches!(
            constant::OperationProof::<F, sha256::Digest, 1>::build::<Sha256>(
                &bitmap,
                plan,
                |_| None,
                Location::new(8),
                ops_root,
            ),
            Err(Error::OperationPruned(loc)) if *loc == 3
        ));
    }

    #[test]
    fn required_chunks_boundary_sets() {
        for (leaves, mmr, mmb) in [
            (0, vec![], vec![]),
            (1, vec![0], vec![0]),
            (7, vec![0], vec![0]),
            (8, vec![], vec![0]),
            (9, vec![1], vec![0, 1]),
            (10, vec![1], vec![0, 1]),
            (11, vec![1], vec![1]),
            (16, vec![], vec![1]),
            (17, vec![2], vec![1, 2]),
            (18, vec![2], vec![1, 2]),
            (24, vec![], vec![2]),
            (25, vec![3], vec![2, 3]),
        ] {
            assert_eq!(
                required_chunks::<mmr::Family, 1>(Location::new(leaves), leaves, 0, None)
                    .unwrap()
                    .collect::<Vec<_>>(),
                mmr
            );
            assert_eq!(
                required_chunks::<mmb::Family, 1>(Location::new(leaves), leaves, 0, None)
                    .unwrap()
                    .collect::<Vec<_>>(),
                mmb
            );
        }
        assert!(
            required_chunks::<mmr::Family, 1>(Location::new(16), 16, 2, None)
                .unwrap()
                .next()
                .is_none()
        );
    }

    fn check_invalid_metadata<F: Graftable>() {
        for (ops_leaves, bitmap_len, loc) in [(0, 0, 0), (16, 16, 16), (8, 9, 8), (9, 8, 8)] {
            assert!(matches!(
                required_chunks::<F, 1>(Location::new(ops_leaves), bitmap_len, 0, Some(Location::new(loc))),
                Err(Error::Merkle(merkle::Error::RangeOutOfBounds(found))) if *found == loc
            ));
        }
        assert!(matches!(
            required_chunks::<F, 1>(Location::new(16), 16, 1, Some(Location::new(7))),
            Err(Error::OperationPruned(loc)) if *loc == 7
        ));
        assert!(matches!(
            required_chunks::<F, 1>(Location::new(0), 24, 0, None),
            Err(Error::DataCorrupted("multiple pending bitmap chunks"))
        ));
        assert!(matches!(
            required_chunks::<F, 1>(Location::new(8), 8, 2, None),
            Err(Error::DataCorrupted(
                "pruned chunks exceed graftable chunks"
            ))
        ));
    }

    #[test]
    fn required_chunks_reject_invalid_metadata() {
        check_invalid_metadata::<mmr::Family>();
        check_invalid_metadata::<mmb::Family>();
        assert!(matches!(
            required_chunks::<mmb::Family, 1>(Location::new(8), 8, 1, None),
            Err(Error::DataCorrupted(
                "pruned chunks exceed graftable chunks"
            ))
        ));
    }

    #[cfg(feature = "arbitrary")]
    mod conformance {
        use super::super::{OpsRootWitness, RangeProof, constant, dynamic};
        use crate::merkle::{mmb, mmr};
        use commonware_codec::conformance::CodecConformance;
        use commonware_cryptography::sha256::Digest as Sha256Digest;

        commonware_conformance::conformance_tests! {
            CodecConformance<OpsRootWitness<mmr::Family, Sha256Digest>>,
            CodecConformance<OpsRootWitness<mmb::Family, Sha256Digest>>,
            CodecConformance<RangeProof<mmr::Family, Sha256Digest>>,
            CodecConformance<RangeProof<mmb::Family, Sha256Digest>>,
            CodecConformance<constant::OperationProof<mmr::Family, Sha256Digest, 32>>,
            CodecConformance<constant::OperationProof<mmb::Family, Sha256Digest, 32>>,
            CodecConformance<dynamic::OperationProof<mmr::Family, Sha256Digest>>,
            CodecConformance<dynamic::OperationProof<mmb::Family, Sha256Digest>>,
        }
    }
}