merkle.rs
This Kit feature is not available yet.
In rust/crates/mkit-core/src/
Preview
Code · 74.4 KiB//! Merkle (BMT) content-addressing for `ChunkedBlob` and `Tree`.
//!
//! A merkelized object's content-address **is** its Binary Merkle Tree
//! root: the object id is `wrap_id(kind, bmt_root(leaves))` where the BMT
//! is built over the object's child stream. This makes inclusion of any
//! chunk/entry provable, and makes a reconstructed object's read-time id
//! check a free completeness proof for its whole child set.
//!
//! ## Primitive — a vendored BMT, byte-identical to `commonware_storage::bmt`
//!
//! The house idiom (makechain `transactions_root.rs`) uses
//! `commonware_storage::bmt`. We do **not** depend on it for object identity:
//! `merkle.rs` lives in `mkit-core` and `Object::id` calls it, so this module
//! must compile to `wasm32` for `mkit-core` *itself* to — independent of any
//! wasm caller. Instead this module vendors the *identical* BMT construction
//! over the `blake3` crate (already a mkit dependency, wasm-clean). A
//! native-only test (`tests::vendored_root_matches_commonware`) cross-verifies
//! the vendored root byte-for-byte against `commonware_storage::bmt`, and
//! `tests::proofs_match_commonware` extends that guarantee to inclusion
//! proofs (bytes and cross-verifier acceptance) — so the two never drift.
//!
//! RESOLVED (commonware#4089 / commonwarexyz/monorepo#4090, shipped in
//! `commonware =2026.7.0`): `bmt` itself is now genuinely `no_std` — that
//! part of the original TODO held. It is *not* enough to drop the vendored
//! copy, though: `commonware_storage::bmt::Builder<H: Hasher>` is generic
//! over `commonware_cryptography::Hasher`, so reaching a concrete hasher
//! (e.g. `Blake3`) means depending on the `commonware-cryptography` crate —
//! and that crate's `blst` dependency (BLS12-381) is **not** feature-gated;
//! it compiles unconditionally for every consumer, wasm or not. Confirmed
//! empirically: `blst`'s C sources fail to build for
//! `wasm32-unknown-unknown` wherever the local `clang` has no WASM LLVM
//! backend registered (e.g. stock Xcode clang on macOS — `clang
//! --print-targets` lists no `wasm32` entry). Even on a toolchain where it
//! *does* build, making `commonware-storage` (and therefore
//! `commonware-cryptography`/`blst`) a mandatory dependency of `mkit-core`'s
//! object-identity path would impose that C library's build/binary-size
//! cost on every consumer, not just wasm callers — the same reason
//! `mkit-attest` keeps `blst` behind an opt-in `bls-threshold` feature
//! instead of pulling it in by default. So the vendored construction stays;
//! the cross-check test is what keeps it honest against upstream.
//!
//! The construction (matching commonware):
//! * leaf at index `i` is hashed with its position: `H(i_be32 ‖ leaf)`;
//! * each level pairs nodes `H(left ‖ right)`, duplicating the last node
//! `H(left ‖ left)` when a level has an odd count;
//! * an empty tree is a single node `H("")`;
//! * the finalized root is `H(leaf_count_be32 ‖ tree_root)`, which binds
//! the leaf count and defeats the odd-node-duplication malleability.
//!
//! Normative crypto: `docs/specs/SPEC-MERKLE-OBJECTS.md`.
//!
//! ## Identity formulas
//!
//! ```text
//! id = wrap_id(kind, bmt_root(leaves))
//! = domain_digest(TYPE_DOMAIN, bmt_root(leaves))
//!
//! ChunkedBlob leaves = [meta_leaf] ++ chunks
//! meta_leaf = domain_digest("mkit-cblob-meta-v1", total_size_le ‖ chunk_size_le)
//! chunk i -> BMT position i+1 (meta is position 0)
//!
//! Tree leaves = entries (existing lex order)
//! entry leaf = domain_digest("mkit-tree-entry-v1", name_len_le ‖ name ‖ mode ‖ object_hash)
//! ```
//!
//! The outer `wrap_id` wrap makes the id type-distinct: a bare BMT root
//! over identical leaf streams would collide across types (the prologue
//! type byte is not in the root), so an empty `Tree` and an empty
//! `ChunkedBlob`, or a 1-entry `Tree` and a 1-chunk `ChunkedBlob` with the
//! same child hash, would otherwise share an id.
//!
//! ## Inclusion proofs — stable, commonware-aligned
//!
//! Object identity (`compute_tree_id` / `compute_chunked_id`) and the
//! inclusion-proof construction below are both stable
//! (`docs/specs/SPEC-MERKLE-OBJECTS.md` §5). [`Proof`]'s bytes and sibling
//! selection are byte-identical to `commonware_storage::bmt::Proof` at the
//! pinned `2026.9.0` train: a commonware-based verifier can decode a
//! mkit-produced proof with the upstream type and run its own
//! `verify_element_inclusion` / `verify_range_inclusion` /
//! `verify_multi_inclusion` against the **inner root** (see
//! [`chunked_inner_root`] / [`tree_inner_root`]), then apply [`wrap_id`] to
//! compare against the object id. `tests::proofs_match_commonware` pins
//! this claim; `rust/tests/golden/proofs/` carries fixed vectors.
//!
//! Verification in this crate is always stated against the **object id**
//! (`verify_tree_entry`, `verify_chunk`, and their range/multi
//! counterparts), never the bare inner root — passing a caller the inner
//! root invited skipping the type-domain wrap and accepting, say, a
//! `Tree` proof against a `ChunkedBlob` id (issue #1015 §Security). The
//! inner-root-comparing primitives (`Proof::verify_element_inclusion` and
//! friends) stay `pub(crate)`, kept only so the cross-check test can
//! compare directly against upstream's verifiers.
use std::collections::BTreeSet;
use bytes::{Buf, BufMut};
use commonware_codec::{EncodeSize, Error as CodecError, Read, ReadExt, ReadRangeExt, Write};
use crate::hash::{HASH_LEN, Hash, Hasher, domain_digest, hash};
use crate::object::{ChunkedBlob, Tree, TreeEntry};
/// Type domain for the outer identity wrap of a `ChunkedBlob`.
const CHUNKED_TYPE_DOMAIN: &[u8] = b"mkit.chunked\x00";
/// Type domain for the outer identity wrap of a `Tree`.
const TREE_TYPE_DOMAIN: &[u8] = b"mkit.tree\x00";
/// Leaf domain binding a `ChunkedBlob`'s `total_size`/`chunk_size`.
const CBLOB_META_DOMAIN: &[u8] = b"mkit-cblob-meta-v1";
/// Leaf domain for a `Tree` entry's `(name, mode, object_hash)` triple.
const TREE_ENTRY_DOMAIN: &[u8] = b"mkit-tree-entry-v1";
/// Upper bound on sibling levels in a [`Proof`]: `u32::BITS`, matching
/// `commonware_storage::bmt::MAX_LEVELS`. Because [`Proof::leaf_count`] is a
/// `u32`, a tree can have at most `u32::MAX` leaves, which requires at most
/// `u32::BITS` sibling hashes per proven item.
pub const MAX_LEVELS: usize = u32::BITS as usize;
/// The two object kinds addressed by a BMT root (`crate::merkle`), keying
/// [`wrap_id`]'s type-domain wrap. A versioned, supported accessor for the
/// outer identity wrap — the alternative (exposing the raw `TYPE_DOMAIN`
/// byte strings) would make them de facto ABI.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ObjectKind {
/// A [`Tree`]'s entry list.
Tree,
/// A [`ChunkedBlob`]'s `[meta, chunks…]` list.
ChunkedBlob,
}
impl ObjectKind {
fn type_domain(self) -> &'static [u8] {
match self {
Self::Tree => TREE_TYPE_DOMAIN,
Self::ChunkedBlob => CHUNKED_TYPE_DOMAIN,
}
}
}
/// Apply the outer type-domain wrap to a bare BMT inner root, producing the
/// object id. The inverse does not exist — `wrap_id` is a one-way hash —
/// so a verifier holding `(inner_root, proof)` reconstructs the inner root
/// from the proof and wraps it with the *expected* kind to compare against
/// a claimed id, rather than trying to "unwrap" the id.
#[must_use]
pub fn wrap_id(kind: ObjectKind, inner_root: &Hash) -> Hash {
domain_digest(kind.type_domain(), inner_root)
}
/// Errors building or verifying a merkle inclusion proof.
#[derive(Debug, thiserror::Error, PartialEq, Eq)]
pub enum MerkleError {
/// The requested leaf position is outside the object's leaf range.
#[error("merkle position {0} is out of range")]
PositionOutOfRange(u32),
/// The same position was requested more than once in a multi-proof.
#[error("merkle position {0} is duplicated")]
DuplicatePosition(u32),
/// No positions were given to prove/verify.
#[error("no merkle positions given")]
NoPositions,
/// A range's `start` is greater than its `end`.
#[error("merkle range start {start} is greater than end {end}")]
InvalidRange {
/// The range's start position.
start: u32,
/// The range's end position.
end: u32,
},
/// The proof bytes were malformed (bad codec payload or trailing bytes).
#[error("merkle proof is malformed")]
MalformedProof,
/// The proof's sibling count does not match what the position(s)
/// require — too few, too many, or misordered.
#[error("merkle proof is unaligned with the requested position(s)")]
UnalignedProof,
/// The proof did not verify against the given root/id.
#[error("merkle proof verification failed")]
VerificationFailed,
}
impl From<CodecError> for MerkleError {
fn from(_: CodecError) -> Self {
Self::MalformedProof
}
}
// ---------------------------------------------------------------------------
// Vendored BMT primitive (over `blake3`)
// ---------------------------------------------------------------------------
/// Leaf/index count as `u32`. Objects are decode-capped at 1M
/// entries/chunks (see `serialize.rs`), far below `u32::MAX`, so this
/// only panics on a programmer error that bypassed those caps.
fn u32_of(n: usize) -> u32 {
u32::try_from(n).expect("merkle leaf/index count fits u32 (objects capped at 1M)")
}
/// `BLAKE3(a ‖ b)`.
fn h2(a: &[u8], b: &[u8]) -> Hash {
let mut h = Hasher::new();
h.update(a).update(b);
h.finalize()
}
/// Position-hash a leaf: `H(index_be32 ‖ leaf)` (matches commonware
/// `Builder::add`).
fn position_leaf(index: u32, leaf: &Hash) -> Hash {
h2(&index.to_be_bytes(), leaf)
}
/// Returns the number of levels in a tree with `leaf_count` leaves
/// (level 0 = leaves, last level = the pre-finalize root). A tree with 1
/// leaf has 1 level, a tree with 2 leaves has 2 levels, etc. Ported from
/// `commonware_storage::bmt::levels_in_tree`.
fn levels_in_tree(leaf_count: u32) -> usize {
(u32::BITS - leaf_count.saturating_sub(1).leading_zeros() + 1) as usize
}
/// A built BMT: every level from the position-hashed leaves up to the
/// single pre-finalize root node, plus the finalized root. Kept around so
/// one build serves many proofs cheaply — mirrors commonware's
/// `Builder`/`Tree` split.
struct BmtTree {
/// The real leaf count (0 for an empty tree, even though `levels[0]`
/// then holds a single placeholder node).
leaf_count: u32,
/// `true` when built from zero leaves — no position is ever provable.
empty: bool,
/// `levels[0]` = position-hashed leaves (or the single `H("")`
/// placeholder); `levels[levels.len() - 1]` = the single pre-finalize
/// tree root node.
levels: Vec<Vec<Hash>>,
/// The finalized root: `H(leaf_count_be32 ‖ levels.last()[0])`.
root: Hash,
}
fn build_bmt(leaves: &[Hash]) -> BmtTree {
let leaf_count = u32_of(leaves.len());
let empty = leaves.is_empty();
let position_hashed: Vec<Hash> = if empty {
vec![hash(b"")]
} else {
leaves
.iter()
.enumerate()
.map(|(i, l)| position_leaf(u32_of(i), l))
.collect()
};
let mut levels = vec![position_hashed];
while levels.last().expect("levels is never empty").len() > 1 {
let cur = levels.last().expect("levels is never empty");
let mut next = Vec::with_capacity(cur.len().div_ceil(2));
for pair in cur.chunks(2) {
let right = if pair.len() == 2 { &pair[1] } else { &pair[0] };
next.push(h2(&pair[0], right));
}
levels.push(next);
}
let tree_root = levels.last().expect("levels is never empty")[0];
let root = h2(&leaf_count.to_be_bytes(), &tree_root);
BmtTree {
leaf_count,
empty,
levels,
root,
}
}
/// Returns the sorted, deduplicated `(level, index)` positions of siblings
/// required to prove inclusion of leaves at the given `positions`. A
/// sibling is omitted when it would be the node's own duplicate (an odd
/// trailing node) or is already covered by another proven position —
/// verifiers reconstruct `H(computed, computed)` / skip re-deriving it
/// without consuming a proof entry. Ported from
/// `commonware_storage::bmt::siblings_required_for_multi_proof`.
fn siblings_required_for_multi_proof(
leaf_count: u32,
positions: impl IntoIterator<Item = u32>,
) -> Result<BTreeSet<(usize, usize)>, MerkleError> {
let mut current = BTreeSet::new();
for pos in positions {
if pos >= leaf_count {
return Err(MerkleError::PositionOutOfRange(pos));
}
if !current.insert(pos as usize) {
return Err(MerkleError::DuplicatePosition(pos));
}
}
if current.is_empty() {
return Err(MerkleError::NoPositions);
}
let mut sibling_positions = BTreeSet::new();
let levels_count = levels_in_tree(leaf_count);
let mut level_size = leaf_count as usize;
for level in 0..levels_count.saturating_sub(1) {
for &index in ¤t {
let sibling_index = if index.is_multiple_of(2) {
if index + 1 < level_size {
index + 1
} else {
index
}
} else {
index - 1
};
if sibling_index != index && !current.contains(&sibling_index) {
sibling_positions.insert((level, sibling_index));
}
}
current = current.iter().map(|idx| idx / 2).collect();
level_size = level_size.div_ceil(2);
}
Ok(sibling_positions)
}
/// Returns the sorted, deduplicated `(level, index)` positions of siblings
/// required to prove inclusion of a contiguous range of leaves from
/// `start` to `end` (inclusive). Ported from
/// `commonware_storage::bmt::siblings_required_for_range_proof`.
fn siblings_required_for_range_proof(
leaf_count: u32,
start: u32,
end: u32,
) -> Result<BTreeSet<(usize, usize)>, MerkleError> {
if leaf_count == 0 {
return Err(MerkleError::NoPositions);
}
if start > end {
return Err(MerkleError::InvalidRange { start, end });
}
if start >= leaf_count {
return Err(MerkleError::PositionOutOfRange(start));
}
if end >= leaf_count {
return Err(MerkleError::PositionOutOfRange(end));
}
let mut sibling_positions = BTreeSet::new();
let levels_count = levels_in_tree(leaf_count);
let mut level_start = start as usize;
let mut level_end = end as usize;
let mut level_size = leaf_count as usize;
for level in 0..levels_count.saturating_sub(1) {
if !level_start.is_multiple_of(2) {
sibling_positions.insert((level, level_start - 1));
}
if level_end.is_multiple_of(2) {
let right = level_end + 1;
if right < level_size {
sibling_positions.insert((level, right));
}
}
level_start /= 2;
level_end /= 2;
level_size = level_size.div_ceil(2);
}
Ok(sibling_positions)
}
impl BmtTree {
/// Generates a proof for the leaf at `position`. A single-element
/// multi-proof.
fn proof(&self, position: u32) -> Result<Proof, MerkleError> {
self.multi_proof(core::iter::once(position))
}
/// Generates a range proof for the contiguous leaves `start..=end`.
fn range_proof(&self, start: u32, end: u32) -> Result<Proof, MerkleError> {
// Intentional divergence from `commonware_storage::bmt`, whose
// `range_proof(0, 0)` on an empty tree returns `Proof::default()`:
// SPEC-MERKLE-OBJECTS §5.4 requires a builder to refuse every
// position of the empty `Tree`, including the range `0..=0`.
// `tests::proofs_match_commonware` only draws `n >= 1`, so the
// cross-check never compares this case.
if self.empty {
return Err(MerkleError::PositionOutOfRange(start));
}
if start > end {
return Err(MerkleError::InvalidRange { start, end });
}
let leaf_count = self.leaf_count;
if start >= leaf_count {
return Err(MerkleError::PositionOutOfRange(start));
}
if end >= leaf_count {
return Err(MerkleError::PositionOutOfRange(end));
}
let sibling_positions = siblings_required_for_range_proof(leaf_count, start, end)?;
let siblings = sibling_positions
.iter()
.map(|&(level, index)| self.levels[level][index])
.collect();
Ok(Proof {
leaf_count,
siblings,
})
}
/// Generates a proof for the non-contiguous leaves at `positions`.
/// Positions may be given in any order; duplicates are rejected.
fn multi_proof(&self, positions: impl IntoIterator<Item = u32>) -> Result<Proof, MerkleError> {
let mut positions = positions.into_iter().peekable();
let first = *positions.peek().ok_or(MerkleError::NoPositions)?;
if self.empty {
return Err(MerkleError::PositionOutOfRange(first));
}
let leaf_count = self.leaf_count;
let sibling_positions = siblings_required_for_multi_proof(leaf_count, positions)?;
let siblings = sibling_positions
.iter()
.map(|&(level, index)| self.levels[level][index])
.collect();
Ok(Proof {
leaf_count,
siblings,
})
}
}
// ---------------------------------------------------------------------------
// Proof: wire format + verification
// ---------------------------------------------------------------------------
/// A BMT inclusion proof for one or more leaves: the tree's leaf count
/// plus the deduplicated sibling digests needed to reconstruct the root,
/// ordered level-major (bottom-up) then index-ascending.
///
/// Bytes are `u32 BE leaf_count ‖ LEB128-varint(n) ‖ n × 32-byte digest` —
/// byte-identical to `commonware_storage::bmt::Proof<D>` at the pinned
/// `2026.9.0` train (`tests::proofs_match_commonware` pins this; see also
/// `rust/tests/golden/proofs/`). A commonware-based verifier can decode
/// these bytes with the upstream type directly.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct Proof {
/// The number of leaves in the tree. Incorporated into the finalized
/// root, so a mismatched `leaf_count` fails verification rather than
/// being silently accepted (malleability guard).
pub leaf_count: u32,
/// The deduplicated sibling digests, level-major bottom-up then
/// index-ascending, with self-duplicate and already-proven siblings
/// omitted (see `docs/specs/SPEC-MERKLE-OBJECTS.md` §5.3).
pub siblings: Vec<Hash>,
}
impl Write for Proof {
fn write(&self, writer: &mut impl BufMut) {
self.leaf_count.write(writer);
self.siblings.write(writer);
}
}
impl EncodeSize for Proof {
fn encode_size(&self) -> usize {
self.leaf_count.encode_size() + self.siblings.encode_size()
}
}
impl Read for Proof {
/// The maximum number of items being proven. The upper bound on
/// sibling hashes is derived as `max_items * MAX_LEVELS`, bounding
/// allocation before any hashing happens.
type Cfg = usize;
fn read_cfg(reader: &mut impl Buf, max_items: &Self::Cfg) -> Result<Self, CodecError> {
let leaf_count = u32::read(reader)?;
let max_siblings = max_items.saturating_mul(MAX_LEVELS);
let siblings = Vec::<Hash>::read_range(reader, ..=max_siblings)?;
Ok(Self {
leaf_count,
siblings,
})
}
}
impl Proof {
/// Encode to the commonware-identical wire bytes.
#[must_use]
pub fn encode(&self) -> Vec<u8> {
let mut out = Vec::with_capacity(self.encode_size());
self.write(&mut out);
out
}
/// Decode from the commonware-identical wire bytes, bounding the
/// sibling count to `max_items * MAX_LEVELS`. `max_items` should be the
/// number of positions the caller is about to verify (1 for a
/// single-leaf proof, the range length for a range proof, the position
/// count for a multi-proof). Rejects trailing bytes.
///
/// # Errors
///
/// [`MerkleError::MalformedProof`] on a truncated buffer, an
/// over-`max_items` sibling count, or trailing bytes.
pub fn decode(bytes: &[u8], max_items: usize) -> Result<Self, MerkleError> {
let mut buf = bytes;
let proof = Self::read_cfg(&mut buf, &max_items)?;
if buf.has_remaining() {
return Err(MerkleError::MalformedProof);
}
Ok(proof)
}
/// Reconstructs the tree's inner (pre-wrap) root implied by this proof
/// for `leaf` at `position`, without comparing it to anything. The
/// shared building block for both the inner-root-comparing
/// (commonware-parity) verifiers below and the public id-based
/// verifiers. `pub(crate)` so `verify` can compare the fold to a
/// bundle-declared inner root without a second pass.
pub(crate) fn reconstruct_element_root(
&self,
leaf: &Hash,
mut position: u32,
) -> Result<Hash, MerkleError> {
if position >= self.leaf_count {
return Err(MerkleError::PositionOutOfRange(position));
}
let mut computed = position_leaf(position, leaf);
let mut level_size = self.leaf_count as usize;
let mut sibling_iter = self.siblings.iter();
while level_size > 1 {
let is_last_odd = position.is_multiple_of(2) && position as usize + 1 >= level_size;
let (left, right) = if is_last_odd {
(computed, computed)
} else if position.is_multiple_of(2) {
let sib = *sibling_iter.next().ok_or(MerkleError::UnalignedProof)?;
(computed, sib)
} else {
let sib = *sibling_iter.next().ok_or(MerkleError::UnalignedProof)?;
(sib, computed)
};
computed = h2(&left, &right);
position /= 2;
level_size = level_size.div_ceil(2);
}
if sibling_iter.next().is_some() {
return Err(MerkleError::UnalignedProof);
}
Ok(h2(&self.leaf_count.to_be_bytes(), &computed))
}
/// Reconstructs the tree's inner (pre-wrap) root implied by this proof
/// for the non-contiguous `elements` (leaf, position pairs). Elements
/// may be given in any order; duplicate positions are rejected.
pub(crate) fn reconstruct_multi_root(
&self,
elements: &[(Hash, u32)],
) -> Result<Hash, MerkleError> {
// A proof over zero positions is rejected unconditionally, even
// when `leaf_count == 0` and `siblings` is empty (upstream's
// `Default` proof, which would otherwise trivially "reconstruct"
// the empty tree's root). Accepting it here would let a caller
// verify zero proven entries/chunks against any id whose inner
// root happens to equal the empty tree's — most notably the
// real `TREE_EMPTY_ID` — without ever having proven anything.
// Builders already refuse to construct such a proof
// (`BmtTree::multi_proof`'s `NoPositions` on an empty position
// iterator); this is the matching verification-side rule (see
// `tests::verify_rejects_empty_element_set` and
// SPEC-MERKLE-OBJECTS §5.4).
if elements.is_empty() {
return Err(MerkleError::NoPositions);
}
for (_, position) in elements {
if *position >= self.leaf_count {
return Err(MerkleError::PositionOutOfRange(*position));
}
}
let mut sorted: Vec<(u32, Hash)> = elements
.iter()
.map(|(leaf, pos)| (*pos, position_leaf(*pos, leaf)))
.collect();
sorted.sort_unstable_by_key(|(pos, _)| *pos);
for i in 1..sorted.len() {
if sorted[i - 1].0 == sorted[i].0 {
return Err(MerkleError::DuplicatePosition(sorted[i].0));
}
}
let levels = levels_in_tree(self.leaf_count);
let mut level_size = self.leaf_count;
let mut sibling_iter = self.siblings.iter();
let mut current = sorted;
for _ in 0..levels.saturating_sub(1) {
let mut next_level: Vec<(u32, Hash)> = Vec::with_capacity(current.len().div_ceil(2));
let mut idx = 0;
while idx < current.len() {
let (pos, digest) = current[idx];
let parent_pos = pos / 2;
let (left, right) = if pos.is_multiple_of(2) {
let left = digest;
let right = if idx + 1 < current.len() && current[idx + 1].0 == pos + 1 {
idx += 1;
current[idx].1
} else if pos + 1 >= level_size {
left
} else {
*sibling_iter.next().ok_or(MerkleError::UnalignedProof)?
};
(left, right)
} else {
// The left child was missing from `current`, so it must
// be a sibling.
let right = digest;
let left = *sibling_iter.next().ok_or(MerkleError::UnalignedProof)?;
(left, right)
};
next_level.push((parent_pos, h2(&left, &right)));
idx += 1;
}
current = next_level;
level_size = level_size.div_ceil(2);
}
if sibling_iter.next().is_some() {
return Err(MerkleError::UnalignedProof);
}
if current.len() != 1 {
return Err(MerkleError::UnalignedProof);
}
Ok(h2(&self.leaf_count.to_be_bytes(), ¤t[0].1))
}
/// Reconstructs the inner root for a contiguous range of `leaves`
/// starting at `position`. A convenience wrapper over
/// [`Self::reconstruct_multi_root`].
fn reconstruct_range_root(&self, position: u32, leaves: &[Hash]) -> Result<Hash, MerkleError> {
if leaves.is_empty() && position != 0 {
return Err(MerkleError::PositionOutOfRange(position));
}
if !leaves.is_empty() {
let leaves_len = u32_of(leaves.len());
let end = position
.checked_add(leaves_len - 1)
.ok_or(MerkleError::PositionOutOfRange(position))?;
if end >= self.leaf_count {
return Err(MerkleError::PositionOutOfRange(end));
}
}
let elements: Vec<(Hash, u32)> = leaves
.iter()
.enumerate()
.map(|(i, l)| (*l, position + u32_of(i)))
.collect();
self.reconstruct_multi_root(&elements)
}
/// Verify against the bare (pre-wrap) inner root — matches
/// `commonware_storage::bmt::Proof::verify_element_inclusion` exactly.
/// `cfg(test)`: kept only for the commonware cross-check test
/// (`tests::proofs_match_commonware`) and `tests::verify_chunk_rejects_meta_leaf`,
/// which need to show the *bare* BMT proof accepts a position/leaf the
/// id-based verifier must still reject. Every real caller MUST use the
/// id-based [`verify_tree_entry`] / [`verify_chunk`], which close the
/// inner-root-vs-id confusion footgun (issue #1015 §Security) — so this
/// is deliberately not reachable outside tests, not just `pub(crate)`.
#[cfg(test)]
pub(crate) fn verify_element_inclusion(
&self,
leaf: &Hash,
position: u32,
inner_root: &Hash,
) -> Result<(), MerkleError> {
let got = self.reconstruct_element_root(leaf, position)?;
if &got == inner_root {
Ok(())
} else {
Err(MerkleError::VerificationFailed)
}
}
/// Verify a multi-leaf proof against the bare inner root. `cfg(test)`
/// for the same reason as [`Self::verify_element_inclusion`].
#[cfg(test)]
pub(crate) fn verify_multi_inclusion(
&self,
elements: &[(Hash, u32)],
inner_root: &Hash,
) -> Result<(), MerkleError> {
let got = self.reconstruct_multi_root(elements)?;
if &got == inner_root {
Ok(())
} else {
Err(MerkleError::VerificationFailed)
}
}
/// Verify a range proof against the bare inner root. `cfg(test)` for
/// the same reason as [`Self::verify_element_inclusion`].
#[cfg(test)]
pub(crate) fn verify_range_inclusion(
&self,
position: u32,
leaves: &[Hash],
inner_root: &Hash,
) -> Result<(), MerkleError> {
let got = self.reconstruct_range_root(position, leaves)?;
if &got == inner_root {
Ok(())
} else {
Err(MerkleError::VerificationFailed)
}
}
}
// ---------------------------------------------------------------------------
// Leaf digests
// ---------------------------------------------------------------------------
/// The position-0 metadata leaf digest for a `ChunkedBlob`'s
/// `total_size`/`chunk_size`, without requiring a materialized
/// [`ChunkedBlob`] value. Shared by [`chunked_meta_leaf`] (which has one)
/// and [`verify_chunk_with_meta_leaf`] (which — by design — never does;
/// see that function's docs).
pub(crate) fn chunked_meta_leaf_raw(total_size: u64, chunk_size: u32) -> Hash {
let mut body = [0u8; 12];
body[..8].copy_from_slice(&total_size.to_le_bytes());
body[8..].copy_from_slice(&chunk_size.to_le_bytes());
domain_digest(CBLOB_META_DOMAIN, &body)
}
/// The position-0 metadata leaf for a `ChunkedBlob`, binding its
/// `total_size` and `chunk_size` (neither is derivable from the chunk
/// list, so without this they could be forged — a second-preimage hole).
fn chunked_meta_leaf(cb: &ChunkedBlob) -> Hash {
chunked_meta_leaf_raw(cb.total_size, cb.chunk_size)
}
/// The leaf digest for one `Tree` entry. The `name_len` u32-LE prefix is
/// the anti-ambiguity guard so `("ab", m, h)` and `("a", m, "b"‖…)` cannot
/// alias. Feeding this triple (not the raw `object_hash`) means a Tree
/// inclusion proof attests the full `(name, mode, object_hash)`.
pub(crate) fn tree_entry_leaf(e: &TreeEntry) -> Hash {
let mut body = Vec::with_capacity(4 + e.name.len() + 1 + HASH_LEN);
body.extend_from_slice(&u32_of(e.name.len()).to_le_bytes());
body.extend_from_slice(&e.name);
body.push(e.mode as u8);
body.extend_from_slice(&e.object_hash);
domain_digest(TREE_ENTRY_DOMAIN, &body)
}
fn chunked_leaves(cb: &ChunkedBlob) -> Vec<Hash> {
let mut leaves = Vec::with_capacity(1 + cb.chunks.len());
leaves.push(chunked_meta_leaf(cb));
leaves.extend_from_slice(&cb.chunks);
leaves
}
fn tree_leaves(tree: &Tree) -> Vec<Hash> {
tree.entries.iter().map(tree_entry_leaf).collect()
}
// ---------------------------------------------------------------------------
// Inner roots + identity
// ---------------------------------------------------------------------------
/// Bare (pre-wrap) BMT root over a `ChunkedBlob`'s leaves (`[meta] ++
/// chunks`). A commonware-based verifier's `verify_*_inclusion` checks
/// against this; mkit callers use the id-based [`verify_chunk`] instead.
#[must_use]
pub fn chunked_inner_root(cb: &ChunkedBlob) -> Hash {
build_bmt(&chunked_leaves(cb)).root
}
/// Bare (pre-wrap) BMT root over a `Tree`'s entry leaves. A
/// commonware-based verifier's `verify_*_inclusion` checks against this;
/// mkit callers use the id-based [`verify_tree_entry`] instead.
#[must_use]
pub fn tree_inner_root(tree: &Tree) -> Hash {
build_bmt(&tree_leaves(tree)).root
}
/// The content-address (object id) of a `ChunkedBlob`.
#[must_use]
pub fn compute_chunked_id(cb: &ChunkedBlob) -> Hash {
wrap_id(ObjectKind::ChunkedBlob, &chunked_inner_root(cb))
}
/// The content-address (object id) of a `Tree`.
#[must_use]
pub fn compute_tree_id(tree: &Tree) -> Hash {
wrap_id(ObjectKind::Tree, &tree_inner_root(tree))
}
/// The id of the empty `Tree` (`entries = []`) — a real, common object.
/// Pinned from a test run (see `empty_tree_id_matches_constant`); the
/// empty BMT root is `H(leaf_count ‖ H(""))`, NOT `H(0 ‖ 0)`.
pub const TREE_EMPTY_ID: Hash = [
0x1a, 0xb8, 0xd0, 0x78, 0x8b, 0x29, 0xfe, 0x59, 0x92, 0x01, 0x1e, 0x64, 0xd6, 0xc9, 0x22, 0xec,
0x93, 0xf4, 0x24, 0x8b, 0x37, 0x55, 0xb9, 0x2b, 0x15, 0xb0, 0x7e, 0x66, 0x4c, 0xb1, 0x56, 0x52,
];
// ---------------------------------------------------------------------------
// Position lookup (mirror makechain `message_index`)
// ---------------------------------------------------------------------------
/// BMT position of `chunk_hash` within `cb`, or `None` if absent. The
/// returned position is the chunk index **+ 1** (the metadata leaf
/// occupies position 0).
#[must_use]
pub fn chunk_position(cb: &ChunkedBlob, chunk_hash: &Hash) -> Option<u32> {
cb.chunks
.iter()
.position(|c| c == chunk_hash)
.map(|i| u32_of(i + 1))
}
/// BMT position (= entry index) of the entry named `name` within `tree`,
/// or `None` if absent.
#[must_use]
pub fn tree_entry_position(tree: &Tree, name: &[u8]) -> Option<u32> {
tree.entries.iter().position(|e| e.name == name).map(u32_of)
}
/// Wire size of a proof, calculated from tree shape without hashing leaves.
pub(crate) fn proof_encoded_size(
leaf_count: u32,
positions: impl IntoIterator<Item = u32>,
) -> Result<usize, MerkleError> {
let siblings = siblings_required_for_multi_proof(leaf_count, positions)?.len();
let mut count = siblings;
let mut prefix = 1;
while count >= 128 {
prefix += 1;
count >>= 7;
}
Ok(4 + prefix + siblings * 32)
}
// ---------------------------------------------------------------------------
// Proof construction
// ---------------------------------------------------------------------------
/// Build an inclusion proof that the chunk at `position` (= chunk index +
/// 1, per [`chunk_position`]) belongs to `cb`.
pub fn build_chunk_proof(cb: &ChunkedBlob, position: u32) -> Result<Proof, MerkleError> {
build_bmt(&chunked_leaves(cb)).proof(position)
}
/// Build a range proof that the chunks at `start..=end` belong to `cb`.
pub fn build_chunks_range_proof(
cb: &ChunkedBlob,
start: u32,
end: u32,
) -> Result<Proof, MerkleError> {
build_bmt(&chunked_leaves(cb)).range_proof(start, end)
}
/// Build a multi-leaf proof that the chunks at `positions` belong to `cb`.
pub fn build_chunks_multi_proof(
cb: &ChunkedBlob,
positions: impl IntoIterator<Item = u32>,
) -> Result<Proof, MerkleError> {
build_bmt(&chunked_leaves(cb)).multi_proof(positions)
}
/// Build an inclusion proof that the entry at `position` (= entry index)
/// belongs to `tree`.
pub fn build_tree_entry_proof(tree: &Tree, position: u32) -> Result<Proof, MerkleError> {
build_bmt(&tree_leaves(tree)).proof(position)
}
/// Build a range proof that the entries at `start..=end` belong to `tree`.
pub fn build_tree_entries_range_proof(
tree: &Tree,
start: u32,
end: u32,
) -> Result<Proof, MerkleError> {
build_bmt(&tree_leaves(tree)).range_proof(start, end)
}
/// Build a multi-leaf proof that the entries at `positions` belong to
/// `tree`.
pub fn build_tree_entries_multi_proof(
tree: &Tree,
positions: impl IntoIterator<Item = u32>,
) -> Result<Proof, MerkleError> {
build_bmt(&tree_leaves(tree)).multi_proof(positions)
}
// ---------------------------------------------------------------------------
// Proof verification — against the object id
// ---------------------------------------------------------------------------
/// Verify that `entry` at `position` belongs to the `Tree` whose id is
/// `tree_id`.
pub fn verify_tree_entry(
tree_id: &Hash,
entry: &TreeEntry,
position: u32,
proof: &Proof,
) -> Result<(), MerkleError> {
let root = proof.reconstruct_element_root(&tree_entry_leaf(entry), position)?;
check_wrapped(ObjectKind::Tree, &root, tree_id)
}
/// Verify that `entries` (in tree order, starting at `start`) belong to
/// the `Tree` whose id is `tree_id`.
pub fn verify_tree_entries_range(
tree_id: &Hash,
start: u32,
entries: &[TreeEntry],
proof: &Proof,
) -> Result<(), MerkleError> {
let leaves: Vec<Hash> = entries.iter().map(tree_entry_leaf).collect();
let root = proof.reconstruct_range_root(start, &leaves)?;
check_wrapped(ObjectKind::Tree, &root, tree_id)
}
/// Verify that `entries` (each with its own position, any order) belong to
/// the `Tree` whose id is `tree_id`.
pub fn verify_tree_entries_multi(
tree_id: &Hash,
entries: &[(TreeEntry, u32)],
proof: &Proof,
) -> Result<(), MerkleError> {
let elements: Vec<(Hash, u32)> = entries
.iter()
.map(|(e, pos)| (tree_entry_leaf(e), *pos))
.collect();
let root = proof.reconstruct_multi_root(&elements)?;
check_wrapped(ObjectKind::Tree, &root, tree_id)
}
/// Verify that the chunk `chunk_hash` at `position` belongs to the
/// `ChunkedBlob` whose id is `chunked_id`. Rejects `position == 0`: that
/// position is the metadata leaf, not a chunk, so a valid BMT proof of it
/// must never be accepted as a chunk proof (see `verify_chunk_rejects_meta_leaf`).
pub fn verify_chunk(
chunked_id: &Hash,
chunk_hash: &Hash,
position: u32,
proof: &Proof,
) -> Result<(), MerkleError> {
if position == 0 {
return Err(MerkleError::PositionOutOfRange(0));
}
let root = proof.reconstruct_element_root(chunk_hash, position)?;
check_wrapped(ObjectKind::ChunkedBlob, &root, chunked_id)
}
/// Verify that `chunk_hashes` (in chunk order, starting at `start`) belong
/// to the `ChunkedBlob` whose id is `chunked_id`. Rejects a range whose
/// `start` is 0 (the metadata leaf).
pub fn verify_chunks_range(
chunked_id: &Hash,
start: u32,
chunk_hashes: &[Hash],
proof: &Proof,
) -> Result<(), MerkleError> {
if start == 0 {
return Err(MerkleError::PositionOutOfRange(0));
}
let root = proof.reconstruct_range_root(start, chunk_hashes)?;
check_wrapped(ObjectKind::ChunkedBlob, &root, chunked_id)
}
/// Verify that `chunks` (each with its own position, any order) belong to
/// the `ChunkedBlob` whose id is `chunked_id`. Rejects any position `== 0`
/// (the metadata leaf).
pub fn verify_chunks_multi(
chunked_id: &Hash,
chunks: &[(Hash, u32)],
proof: &Proof,
) -> Result<(), MerkleError> {
if chunks.iter().any(|(_, pos)| *pos == 0) {
return Err(MerkleError::PositionOutOfRange(0));
}
let elements: Vec<(Hash, u32)> = chunks.to_vec();
let root = proof.reconstruct_multi_root(&elements)?;
check_wrapped(ObjectKind::ChunkedBlob, &root, chunked_id)
}
/// Verify, in one multi-proof, that (a) a `ChunkedBlob`'s metadata leaf —
/// computed HERE from the caller's *claimed* `total_size`/`chunk_size`,
/// never accepted as an externally supplied leaf digest — and (b) the
/// chunk `chunk_hash` at `chunk_position` (= chunk index + 1) both belong
/// to the `ChunkedBlob` whose id is `chunked_id`.
///
/// This is the one sanctioned way a proof over position 0 is ever
/// accepted from outside this module: the verifier derives the meta leaf
/// itself from the very values it is simultaneously authenticating,
/// rather than trusting a caller-supplied leaf digest at that position.
/// [`verify_chunk`]'s "reject a caller-supplied position 0" rule is
/// unaffected — that guards a different, single-leaf proof shape; this
/// one always proves exactly `{0, chunk_position}` together. Used by
/// `crate::verify` (issue #1015 verifier kit PR 2, SPEC-DISCLOSURE) to
/// authenticate a disclosed chunk's `total_size`/`chunk_size`
/// announcement alongside its content id, in a single proof.
pub(crate) fn verify_chunk_with_meta_leaf(
chunked_id: &Hash,
total_size: u64,
chunk_size: u32,
chunk_hash: &Hash,
chunk_position: u32,
proof: &Proof,
) -> Result<(), MerkleError> {
if chunk_position == 0 {
return Err(MerkleError::PositionOutOfRange(0));
}
let meta_leaf = chunked_meta_leaf_raw(total_size, chunk_size);
let elements = [(meta_leaf, 0u32), (*chunk_hash, chunk_position)];
let root = proof.reconstruct_multi_root(&elements)?;
check_wrapped(ObjectKind::ChunkedBlob, &root, chunked_id)
}
/// Wrap `root` with `kind`'s type domain and compare to `expected_id`.
fn check_wrapped(kind: ObjectKind, root: &Hash, expected_id: &Hash) -> Result<(), MerkleError> {
if &wrap_id(kind, root) == expected_id {
Ok(())
} else {
Err(MerkleError::VerificationFailed)
}
}
// =========================================================================
// Tests
// =========================================================================
#[cfg(test)]
mod tests {
use super::*;
use crate::object::EntryMode;
fn cb(total: u64, chunk_size: u32, chunks: &[u8]) -> ChunkedBlob {
ChunkedBlob {
total_size: total,
chunk_size,
chunks: chunks.iter().map(|b| [*b; 32]).collect(),
}
}
fn entry(name: &[u8], mode: EntryMode, h: u8) -> TreeEntry {
TreeEntry {
name: name.to_vec(),
mode,
object_hash: [h; 32],
}
}
fn tree(entries: Vec<TreeEntry>) -> Tree {
Tree { entries }
}
#[test]
fn id_changes_when_a_leaf_changes() {
let a = cb(100, 0, &[1, 2, 3]);
let b = cb(100, 0, &[1, 2, 4]);
assert_ne!(compute_chunked_id(&a), compute_chunked_id(&b));
}
#[test]
fn id_changes_when_leaf_count_changes() {
let a = cb(100, 0, &[1, 2, 3]);
let b = cb(100, 0, &[1, 2, 3, 3]); // duplicated last — must not collide
assert_ne!(compute_chunked_id(&a), compute_chunked_id(&b));
}
#[test]
fn chunked_id_changes_when_metadata_changes() {
let a = cb(100, 0, &[1, 2, 3]);
let b = cb(101, 0, &[1, 2, 3]);
let c = cb(100, 64, &[1, 2, 3]);
assert_ne!(compute_chunked_id(&a), compute_chunked_id(&b));
assert_ne!(compute_chunked_id(&a), compute_chunked_id(&c));
}
#[test]
fn tree_ordering_matters() {
let a = tree(vec![
entry(b"a", EntryMode::Blob, 1),
entry(b"b", EntryMode::Blob, 2),
]);
let b = tree(vec![
entry(b"b", EntryMode::Blob, 2),
entry(b"a", EntryMode::Blob, 1),
]);
assert_ne!(compute_tree_id(&a), compute_tree_id(&b));
}
#[test]
fn empty_tree_id_matches_constant() {
let got = compute_tree_id(&tree(vec![]));
assert_eq!(got, TREE_EMPTY_ID, "update TREE_EMPTY_ID to {got:02x?}");
}
#[test]
fn type_binding_no_cross_collisions() {
let empty_tree = compute_tree_id(&tree(vec![]));
let empty_cblob = compute_chunked_id(&cb(0, 0, &[]));
assert_ne!(empty_tree, empty_cblob);
let t = tree(vec![entry(b"x", EntryMode::Blob, 9)]);
let c = cb(10, 0, &[9]);
assert_ne!(compute_tree_id(&t), compute_chunked_id(&c));
}
#[test]
fn id_ne_flat_blake3_of_serialized_bytes() {
let c = cb(100, 0, &[1, 2, 3]);
let serialized =
crate::serialize::serialize(&crate::object::Object::ChunkedBlob(c.clone())).unwrap();
assert_ne!(compute_chunked_id(&c), crate::hash::hash(&serialized));
}
#[test]
fn chunk_position_offsets_by_one() {
let c = cb(100, 0, &[7, 8, 9]);
assert_eq!(chunk_position(&c, &[7; 32]), Some(1));
assert_eq!(chunk_position(&c, &[9; 32]), Some(3));
assert_eq!(chunk_position(&c, &[0; 32]), None);
}
#[test]
fn chunk_inclusion_proof_round_trips() {
let c = cb(100, 0, &[10, 20, 30, 40]);
let id = compute_chunked_id(&c);
for (idx, byte) in [(0usize, 10u8), (2, 30), (3, 40)] {
let pos = chunk_position(&c, &[byte; 32]).unwrap();
assert_eq!(pos, u32_of(idx) + 1);
let proof = build_chunk_proof(&c, pos).unwrap();
verify_chunk(&id, &[byte; 32], pos, &proof).unwrap();
assert!(verify_chunk(&id, &[0xFF; 32], pos, &proof).is_err());
}
}
#[test]
fn verify_chunk_rejects_meta_leaf() {
let c = cb(100, 0, &[10, 20, 30]);
let id = compute_chunked_id(&c);
let meta_leaf = chunked_meta_leaf(&c);
// Position 0 is a *valid* raw BMT proof of the meta leaf...
let proof = build_chunk_proof(&c, 0).unwrap();
proof
.verify_element_inclusion(&meta_leaf, 0, &chunked_inner_root(&c))
.expect("meta leaf is a valid BMT element at position 0");
// ...but `verify_chunk` MUST reject it: position 0 is never a chunk.
assert_eq!(
verify_chunk(&id, &meta_leaf, 0, &proof),
Err(MerkleError::PositionOutOfRange(0))
);
}
#[test]
fn verify_chunk_with_meta_leaf_round_trips_and_rejects_forgery() {
let c = cb(100, 0, &[10, 20, 30]);
let id = compute_chunked_id(&c);
let pos = chunk_position(&c, &[20; 32]).unwrap(); // index 1 -> position 2
let proof = build_chunks_multi_proof(&c, [0, pos]).unwrap();
verify_chunk_with_meta_leaf(&id, 100, 0, &[20; 32], pos, &proof).unwrap();
// Forged total_size must be rejected — the meta leaf the verifier
// computes no longer folds to the real root.
assert!(verify_chunk_with_meta_leaf(&id, 101, 0, &[20; 32], pos, &proof).is_err());
// Forged chunk_size, likewise.
assert!(verify_chunk_with_meta_leaf(&id, 100, 64, &[20; 32], pos, &proof).is_err());
// Wrong chunk hash at the right position.
assert!(verify_chunk_with_meta_leaf(&id, 100, 0, &[0xFF; 32], pos, &proof).is_err());
// Position 0 is never accepted as `chunk_position`, even though
// it is a structurally valid multi-proof position.
assert_eq!(
verify_chunk_with_meta_leaf(&id, 100, 0, &[10; 32], 0, &proof),
Err(MerkleError::PositionOutOfRange(0))
);
}
#[test]
fn tree_inclusion_proof_round_trips() {
let t = tree(vec![
entry(b"a", EntryMode::Blob, 1),
entry(b"b", EntryMode::Tree, 2),
entry(b"c", EntryMode::Executable, 3),
]);
let id = compute_tree_id(&t);
let pos = tree_entry_position(&t, b"b").unwrap();
assert_eq!(pos, 1);
let proof = build_tree_entry_proof(&t, pos).unwrap();
verify_tree_entry(&id, &t.entries[1], pos, &proof).unwrap();
let wrong = entry(b"b", EntryMode::Blob, 2);
assert!(verify_tree_entry(&id, &wrong, pos, &proof).is_err());
}
#[test]
fn range_and_multi_proofs_round_trip() {
let t = tree(
(0..9)
.map(|i| entry(&[b'a' + i], EntryMode::Blob, i))
.collect(),
);
let id = compute_tree_id(&t);
let range_proof = build_tree_entries_range_proof(&t, 2, 4).unwrap();
verify_tree_entries_range(&id, 2, &t.entries[2..=4], &range_proof).unwrap();
assert!(verify_tree_entries_range(&id, 2, &t.entries[2..4], &range_proof).is_err());
let multi_proof = build_tree_entries_multi_proof(&t, [0, 4, 8]).unwrap();
let elements = [
(t.entries[0].clone(), 0),
(t.entries[4].clone(), 4),
(t.entries[8].clone(), 8),
];
verify_tree_entries_multi(&id, &elements, &multi_proof).unwrap();
let wrong_elements = [
(t.entries[0].clone(), 0),
(t.entries[4].clone(), 5), // wrong position
(t.entries[8].clone(), 8),
];
assert!(verify_tree_entries_multi(&id, &wrong_elements, &multi_proof).is_err());
}
#[test]
fn chunk_range_and_multi_proofs_reject_position_zero() {
let c = cb(100, 0, &[1, 2, 3]);
let id = compute_chunked_id(&c);
let proof = build_chunks_range_proof(&c, 0, 1).unwrap();
assert_eq!(
verify_chunks_range(&id, 0, &c.chunks[..2], &proof),
Err(MerkleError::PositionOutOfRange(0))
);
let multi = build_chunks_multi_proof(&c, [0, 2]).unwrap();
assert_eq!(
verify_chunks_multi(&id, &[(c.chunks[0], 0), (c.chunks[1], 2)], &multi),
Err(MerkleError::PositionOutOfRange(0))
);
}
#[test]
fn single_leaf_tree_proof_has_no_siblings() {
// Odd trailing node at every level up to the root: the proof must
// omit the self-duplicate sibling entirely (issue #1015: the old
// format wrongly emitted it).
let t = tree(vec![entry(b"only", EntryMode::Blob, 1)]);
let id = compute_tree_id(&t);
let proof = build_tree_entry_proof(&t, 0).unwrap();
assert!(
proof.siblings.is_empty(),
"single-leaf tree proof must have zero siblings"
);
verify_tree_entry(&id, &t.entries[0], 0, &proof).unwrap();
}
#[test]
fn verify_rejects_empty_element_set() {
// A "proof" over zero positions must never verify — not even
// against the real empty tree id with the trivial
// `Proof::default()` (`leaf_count: 0, siblings: []`). Upstream's
// own `verify_multi_inclusion` treats exactly this input as a
// valid proof that a tree is empty; mkit's id-based verifiers
// reject it unconditionally instead, so a caller can never
// "verify" zero proven entries/chunks against an id merely
// because that id's inner root happens to fold the same way
// (SPEC-MERKLE-OBJECTS §5.4).
assert_eq!(
verify_tree_entries_range(&TREE_EMPTY_ID, 0, &[], &Proof::default()),
Err(MerkleError::NoPositions)
);
assert_eq!(
verify_tree_entries_multi(&TREE_EMPTY_ID, &[], &Proof::default()),
Err(MerkleError::NoPositions)
);
// The rule holds regardless of `leaf_count`: an empty
// entries/positions slice is rejected even against a genuinely
// non-empty tree with an otherwise-valid proof.
let t = tree(vec![entry(b"a", EntryMode::Blob, 1)]);
let id = compute_tree_id(&t);
let real_proof = build_tree_entry_proof(&t, 0).unwrap();
assert_eq!(
verify_tree_entries_range(&id, 0, &[], &real_proof),
Err(MerkleError::NoPositions)
);
assert_eq!(
verify_tree_entries_multi(&id, &[], &real_proof),
Err(MerkleError::NoPositions)
);
}
#[test]
fn empty_tree_builders_refuse_position_zero() {
// SPEC-MERKLE-OBJECTS §5.4: position 0 of the empty `Tree`
// (leaf_count 0), including the range `0..=0`, MUST be refused
// rather than answered with the all-default proof (MKIT-56).
let empty = tree(vec![]);
assert_eq!(
build_tree_entries_range_proof(&empty, 0, 0),
Err(MerkleError::PositionOutOfRange(0))
);
assert_eq!(
build_tree_entry_proof(&empty, 0),
Err(MerkleError::PositionOutOfRange(0))
);
assert_eq!(
build_tree_entries_multi_proof(&empty, [0]),
Err(MerkleError::PositionOutOfRange(0))
);
}
#[test]
fn out_of_range_position_rejected() {
let c = cb(10, 0, &[1]);
assert_eq!(
build_chunk_proof(&c, 2),
Err(MerkleError::PositionOutOfRange(2))
);
}
#[test]
fn proof_round_trips_through_encode_decode() {
let t = tree(
(0..7)
.map(|i| entry(&[b'a' + i], EntryMode::Blob, i))
.collect(),
);
let proof = build_tree_entry_proof(&t, 6).unwrap();
let bytes = proof.encode();
let decoded = Proof::decode(&bytes, 1).unwrap();
assert_eq!(proof, decoded);
// Trailing byte must be rejected.
let mut truncated_extra = bytes.clone();
truncated_extra.push(0);
assert_eq!(
Proof::decode(&truncated_extra, 1),
Err(MerkleError::MalformedProof)
);
// A truncated buffer must be rejected.
assert_eq!(
Proof::decode(&bytes[..bytes.len() - 1], 1),
Err(MerkleError::MalformedProof)
);
// An over-tight `max_items` bound must be rejected.
assert_eq!(Proof::decode(&bytes, 0), Err(MerkleError::MalformedProof));
}
/// Cross-verify the vendored BMT against `commonware_storage::bmt`
/// (native-only dev-dep) for several leaf counts incl. odd ones — the
/// guard that the wasm-path vendored construction never drifts from the
/// house primitive.
#[test]
fn vendored_root_matches_commonware() {
use commonware_cryptography::blake3::{Blake3, Digest};
use commonware_storage::bmt::Builder;
for n in [1usize, 2, 3, 4, 5, 7, 8, 9, 16, 33] {
let leaves: Vec<Hash> = (0..n)
.map(|i| hash(&[u8::try_from(i % 256).unwrap(); 4]))
.collect();
let mut builder = Builder::<Blake3>::new(n);
for l in &leaves {
builder.add(&Digest(*l));
}
let cw_root = builder.build().root().0;
let ours = build_bmt(&leaves).root;
assert_eq!(ours, cw_root, "vendored BMT root diverged at n={n}");
}
}
/// Strategy for `(leaf_count, single_pos, (range_start, range_end),
/// multi_positions)`, weighted towards odd counts and powers-of-two ±1
/// (where the odd-trailing-node dedup logic is most exercised) on top
/// of a broad uniform range.
fn tree_and_positions()
-> impl proptest::strategy::Strategy<Value = (usize, u32, (u32, u32), Vec<u32>)> {
use proptest::prelude::*;
let boundary_counts: Vec<usize> = [1usize, 2, 4, 8, 16, 32, 64, 128, 256]
.into_iter()
.flat_map(|p| [p.saturating_sub(1).max(1), p, p + 1])
.chain([
3usize, 5, 7, 9, 15, 17, 31, 33, 63, 65, 127, 129, 255, 257, 300,
])
.collect();
prop_oneof![
3 => 1usize..=300,
2 => proptest::sample::select(boundary_counts),
]
.prop_flat_map(|n| {
let n_u32 =
u32::try_from(n).expect("n is bounded well under u32::MAX by the strategy above");
(
Just(n),
0..n_u32,
(0..n_u32).prop_flat_map(move |s| (Just(s), s..n_u32)),
proptest::collection::vec(0..n_u32, 1..=n.min(6)).prop_map(|mut v| {
v.sort_unstable();
v.dedup();
v
}),
)
})
}
proptest::proptest! {
#![proptest_config(proptest::prelude::ProptestConfig::with_cases(400))]
/// Cross-verify [`Proof`] against `commonware_storage::bmt::Proof`
/// (native-only dev-dep): for many randomised trees and randomised
/// single/range/multi positions, mkit's encoded bytes must equal
/// upstream's, and each side's verifier must accept the other's
/// bytes/positions against the (matching) inner root. A mutated
/// proof must be rejected by both. Pins issue #1015's
/// "commonware-aligned bytes" claim beyond the root-only check
/// above.
#[test]
fn proofs_match_commonware((n, pos, (start, end), positions) in tree_and_positions()) {
use commonware_cryptography::blake3::{Blake3, Digest};
use commonware_storage::bmt::Builder;
let leaves: Vec<Hash> = (0..n).map(|i| hash(&(i as u64).to_le_bytes())).collect();
let ours = build_bmt(&leaves);
let mut cw_builder = Builder::<Blake3>::new(n);
for l in &leaves {
cw_builder.add(&Digest(*l));
}
let cw_tree = cw_builder.build();
let cw_root = cw_tree.root();
assert_eq!(ours.root, cw_root.0, "root mismatch at n={n}");
// --- single position ---
let our_proof = ours.proof(pos).unwrap();
let cw_proof = cw_tree.proof(pos).unwrap();
assert_eq!(
our_proof.encode(),
commonware_codec::Encode::encode(&cw_proof).to_vec(),
"single-proof bytes diverged at n={n} pos={pos}"
);
cw_proof
.verify_element_inclusion::<Blake3>(&Digest(leaves[pos as usize]), pos, &cw_root)
.expect("upstream must accept its own proof");
our_proof
.verify_element_inclusion(&leaves[pos as usize], pos, &ours.root)
.expect("ours must accept its own proof");
// Cross-accept: decode the other side's bytes with our type.
let cw_bytes = commonware_codec::Encode::encode(&cw_proof).to_vec();
let our_decoded = Proof::decode(&cw_bytes, 1).unwrap();
our_decoded
.verify_element_inclusion(&leaves[pos as usize], pos, &ours.root)
.expect("ours must accept upstream's proof bytes");
// Cross-accept the other way: upstream decodes our bytes.
let our_bytes = our_proof.encode();
let mut our_bytes_buf: &[u8] = &our_bytes;
let cw_decoded =
<commonware_storage::bmt::Proof<Digest> as commonware_codec::Read>::read_cfg(
&mut our_bytes_buf,
&1usize,
)
.unwrap();
cw_decoded
.verify_element_inclusion::<Blake3>(&Digest(leaves[pos as usize]), pos, &cw_root)
.expect("upstream must accept our proof bytes");
// --- mutation must be rejected by both ---
if !our_proof.siblings.is_empty() {
let mut mutated = our_proof.clone();
mutated.siblings[0][0] ^= 0x01;
assert!(
mutated
.verify_element_inclusion(&leaves[pos as usize], pos, &ours.root)
.is_err()
);
let mut dropped = our_proof.clone();
dropped.siblings.pop();
assert!(
dropped
.verify_element_inclusion(&leaves[pos as usize], pos, &ours.root)
.is_err()
);
let mut extra = our_proof.clone();
extra.siblings.push(hash(b"extra"));
assert!(
extra
.verify_element_inclusion(&leaves[pos as usize], pos, &ours.root)
.is_err()
);
}
let mut wrong_count = our_proof.clone();
wrong_count.leaf_count = wrong_count.leaf_count.wrapping_add(1);
assert!(
wrong_count
.verify_element_inclusion(&leaves[pos as usize], pos, &ours.root)
.is_err()
);
if n >= 2 {
// --- range ---
let our_range = ours.range_proof(start, end).unwrap();
let cw_range = cw_tree.range_proof(start, end).unwrap();
assert_eq!(
our_range.encode(),
commonware_codec::Encode::encode(&cw_range).to_vec(),
"range-proof bytes diverged at n={n} start={start} end={end}"
);
let range_leaves: Vec<Hash> = leaves[start as usize..=end as usize].to_vec();
let cw_range_leaves: Vec<Digest> =
range_leaves.iter().map(|h| Digest(*h)).collect();
cw_range
.verify_range_inclusion::<Blake3>(start, &cw_range_leaves, &cw_root)
.expect("upstream must accept its own range proof");
our_range
.verify_range_inclusion(start, &range_leaves, &ours.root)
.expect("ours must accept its own range proof");
// --- multi ---
if !positions.is_empty() {
let our_multi = ours.multi_proof(positions.iter().copied()).unwrap();
let cw_multi = cw_tree.multi_proof(positions.iter().copied()).unwrap();
assert_eq!(
our_multi.encode(),
commonware_codec::Encode::encode(&cw_multi).to_vec(),
"multi-proof bytes diverged at n={n} positions={positions:?}"
);
let elements: Vec<(Hash, u32)> =
positions.iter().map(|&p| (leaves[p as usize], p)).collect();
let cw_elements: Vec<(Digest, u32)> = positions
.iter()
.map(|&p| (Digest(leaves[p as usize]), p))
.collect();
cw_multi
.verify_multi_inclusion::<Blake3>(&cw_elements, &cw_root)
.expect("upstream must accept its own multi proof");
our_multi
.verify_multi_inclusion(&elements, &ours.root)
.expect("ours must accept its own multi proof");
}
}
}
}
}
/// Kani proof harnesses (`cargo kani -p mkit-core --no-default-features
/// -Z stubbing --harness merkle_`, see `delta.rs`), the model-checked counterpart of the `merkle_proof` fuzz
/// target.
///
/// BLAKE3 (`h2`, `domain_digest`, `hash`) is stubbed with a cheap
/// deterministic `toy` mixer: the index/level arithmetic, sibling
/// consumption and wire decoding are what is verified here; collision
/// resistance is BLAKE3's job and out of scope for a model checker.
#[cfg(kani)]
mod kani_proofs {
use super::*;
/// Loop-free deterministic mixer over the first 16 bytes of `a` and
/// of `b` (zero-padded) and both lengths. Each output half depends on
/// both inputs, so a change in either input's first 16 bytes
/// propagates up the tree (a mixer that merely copied inputs into
/// disjoint halves would drop leaf bytes one level up and make the
/// tampered-leaf canary unfalsifiable). Loop-free so it does not
/// interact with the global unwind bound.
fn toy(a: &[u8], b: &[u8]) -> Hash {
fn first16(x: &[u8]) -> u128 {
let mut w = [0u8; 16];
let n = x.len().min(16);
w[..n].copy_from_slice(&x[..n]);
u128::from_le_bytes(w)
}
let (ha, hb) = (first16(a), first16(b));
let lo = ha ^ hb.rotate_left(8) ^ a.len() as u128;
let hi = hb ^ ha.rotate_left(16) ^ ((b.len() as u128) << 64);
let mut out = [0u8; HASH_LEN];
out[..16].copy_from_slice(&lo.to_le_bytes());
out[16..].copy_from_slice(&hi.to_le_bytes());
out
}
fn toy_h2(a: &[u8], b: &[u8]) -> Hash {
toy(a, b)
}
fn toy_domain_digest(domain: &[u8], body: &[u8]) -> Hash {
toy(body, domain)
}
fn toy_hash(data: &[u8]) -> Hash {
toy(data, &[])
}
/// SPEC-MERKLE-OBJECTS §5.3/§5.4: number of wire siblings a
/// single-leaf proof of `position` in a `leaf_count`-leaf tree
/// consumes (odd trailing nodes fold with themselves, no sibling).
fn spec_sibling_count(leaf_count: u32, mut position: u32) -> usize {
let mut level_size = u64::from(leaf_count);
let mut need = 0;
while level_size > 1 {
if !(position % 2 == 0 && u64::from(position) + 1 >= level_size) {
need += 1;
}
position /= 2;
level_size = level_size.div_ceil(2);
}
need
}
fn short_at<const N: usize>() {
let buf: [u8; N] = kani::any();
let b: &[u8] = &buf;
if let Ok(p) = Proof::decode(b, 1) {
assert!(N == 5 && b[4] == 0 && p.siblings.is_empty());
let lc: [u8; 4] = b[..4].try_into().expect("4 bytes");
assert_eq!(p.leaf_count, u32::from_be_bytes(lc));
kani::cover!(true, "ok_no_siblings");
}
}
/// `Proof::decode(_, 1)` (the single-leaf bound the fuzz target and
/// `verify_chunk` callers use) never panics on any input of 0..=4
/// bytes (truncated before the sibling-count varint; each length
/// concrete, every byte symbolic) and rejects all of them.
#[kani::proof]
#[kani::unwind(4)]
fn merkle_proof_decode_no_panic() {
short_at::<0>();
short_at::<1>();
short_at::<2>();
short_at::<3>();
short_at::<4>();
}
/// As above at 5 bytes (be32 leaf count + a symbolic varint): accepts
/// exactly the §5.2 empty proof `be32(leaf_count) ‖ varint(0)`.
#[kani::proof]
// Varint <= 1 byte here; no sibling fits.
#[kani::unwind(4)]
fn merkle_proof_decode_empty_proof() {
short_at::<5>();
}
/// At exactly 37 bytes with the sibling-count varint pinned to 1
/// (be32 leaf count + `0x01` + one digest, the other 36 bytes
/// symbolic): no panic, `Ok`, and the proof carries exactly the wire
/// leaf count and digest (§5.2). (With the varint symbolic, the
/// symbolic-size sibling `Vec` allocation ran out of memory.)
#[kani::proof]
// Largest loop: the 4-word digest comparison.
#[kani::unwind(6)]
fn merkle_proof_decode_one_sibling() {
let mut buf: [u8; 37] = kani::any();
buf[4] = 1;
let p = Proof::decode(&buf, 1).expect("one-sibling proof decodes");
assert_eq!(
p.leaf_count,
u32::from_be_bytes([buf[0], buf[1], buf[2], buf[3]])
);
assert_eq!(p.siblings.len(), 1);
let d = &p.siblings[0];
let w = |x: &[u8], i: usize| u64::from_le_bytes(x[i..i + 8].try_into().expect("8"));
assert!((0..4).all(|k| w(d, 8 * k) == w(&buf[5..], 8 * k)));
}
/// One adversarial verification with `S` sibling digests and a
/// symbolic `leaf_count <= max_leaves`.
fn verify_with<const S: usize>(max_leaves: u32) -> bool {
let proof = Proof {
leaf_count: kani::any_where(|&n| n <= max_leaves),
siblings: kani::any::<[Hash; S]>().to_vec(),
};
let position: u32 = kani::any();
let leaf: Hash = kani::any();
let id: Hash = kani::any();
let folded = proof.reconstruct_element_root(&leaf, position);
let shape_ok = position < proof.leaf_count
&& proof.siblings.len() == spec_sibling_count(proof.leaf_count, position);
assert_eq!(folded.is_ok(), shape_ok);
let chunk = verify_chunk(&id, &leaf, position, &proof);
if position == 0 {
assert_eq!(chunk, Err(MerkleError::PositionOutOfRange(0)));
}
if chunk.is_ok() {
assert!(shape_ok);
}
let entry = TreeEntry {
name: vec![b'a'],
mode: crate::object::EntryMode::Blob,
object_hash: leaf,
};
let _ = verify_tree_entry(&id, &entry, position, &proof);
chunk.is_ok()
}
/// Adversarial single-leaf verification: any `leaf_count`, any
/// `position`, no sibling digests, any claimed id. `verify_chunk` /
/// `verify_tree_entry` never panic/overflow, and the fold succeeds
/// iff `position < leaf_count` and the proof carries exactly the §5.3
/// sibling count (§5.4 "consumed exactly once"). Chunk position 0 is
/// always rejected (§5.5). One harness per sibling count: 0..=2 in
/// one harness did not finish within 15 min.
#[kani::proof]
#[kani::stub(h2, toy_h2)]
#[kani::stub(crate::hash::domain_digest, toy_domain_digest)]
#[kani::stub(crate::hash::hash, toy_hash)]
// <= 32 fold levels (any u32 leaf count).
#[kani::unwind(34)]
fn merkle_verify_s0() {
verify_with::<0>(u32::MAX);
}
/// As above with one arbitrary sibling digest and `leaf_count <= 8`
/// (<= 3 fold levels; any `u32` leaf count ran out of memory). Run
/// with `-Z unstable-options --cbmc-args --unwindset memcmp.0:33`.
#[kani::proof]
#[kani::stub(h2, toy_h2)]
#[kani::stub(crate::hash::domain_digest, toy_domain_digest)]
#[kani::stub(crate::hash::hash, toy_hash)]
#[kani::unwind(5)]
fn merkle_verify_s1() {
kani::cover!(verify_with::<1>(8), "accepts_one_sibling_proof");
}
/// As above with two arbitrary sibling digests and `leaf_count <= 8`.
#[kani::proof]
#[kani::stub(h2, toy_h2)]
#[kani::stub(crate::hash::domain_digest, toy_domain_digest)]
#[kani::stub(crate::hash::hash, toy_hash)]
#[kani::unwind(5)]
fn merkle_verify_s2() {
kani::cover!(verify_with::<2>(8), "accepts_two_sibling_proof");
}
/// Independent single-leaf proof builder following SPEC-MERKLE-
/// OBJECTS §1.1 (position-hashed leaves, odd trailing node paired
/// with itself, `H(be32(leaf_count) ‖ top)` finalization) and §5.3
/// (level-major siblings, self-duplicates omitted). Returns the
/// finalized inner root and the sibling list. `leaves.len() <= 4`.
fn spec_proof(leaves: &[Hash], pos: usize) -> (Hash, Vec<Hash>) {
#[allow(clippy::cast_possible_truncation)]
let mut level: Vec<Hash> = leaves
.iter()
.enumerate()
.map(|(i, l)| toy_h2(&(i as u32).to_be_bytes(), l))
.collect();
let mut p = pos;
let mut siblings = Vec::new();
while level.len() > 1 {
if p % 2 == 1 {
siblings.push(level[p - 1]);
} else if p + 1 < level.len() {
siblings.push(level[p + 1]);
}
let mut next = Vec::new();
let mut i = 0;
while i < level.len() {
let right = if i + 1 < level.len() {
level[i + 1]
} else {
level[i]
};
next.push(toy_h2(&level[i], &right));
i += 2;
}
level = next;
p /= 2;
}
#[allow(clippy::cast_possible_truncation)]
let root = toy_h2(&(leaves.len() as u32).to_be_bytes(), &level[0]);
(root, siblings)
}
/// A `ChunkedBlob` with `N` symbolic chunks and symbolic sizes, its
/// §3.1 leaf list `[meta, chunks…]`, and its id computed through the
/// §2 domain wrap of the spec-built root.
fn chunked_fixture<const N: usize>() -> (ChunkedBlob, Vec<Hash>) {
let cb = ChunkedBlob {
total_size: kani::any(),
chunk_size: kani::any(),
chunks: kani::any::<[Hash; N]>().to_vec(),
};
let mut leaves = vec![chunked_meta_leaf_raw(cb.total_size, cb.chunk_size)];
leaves.extend_from_slice(&cb.chunks);
(cb, leaves)
}
/// Spec-built proof for chunk `pos` (1-based, concrete) of an
/// `N`-chunk symbolic blob is accepted.
fn chunk_rt<const N: usize>(pos: u32) {
let (cb, leaves) = chunked_fixture::<N>();
let (root, siblings) = spec_proof(&leaves, pos as usize);
let id = wrap_id(ObjectKind::ChunkedBlob, &root);
#[allow(clippy::cast_possible_truncation)]
let proof = Proof {
leaf_count: leaves.len() as u32,
siblings,
};
assert_eq!(
proof.siblings.len(),
spec_sibling_count(proof.leaf_count, pos)
);
assert_eq!(
verify_chunk(&id, &cb.chunks[(pos - 1) as usize], pos, &proof),
Ok(())
);
}
/// Spec conformance (§1.1, §5.3–§5.5): for every `ChunkedBlob` of 1
/// symbolic chunk (any sizes) and every chunk position, the proof an
/// independent §5.3 builder produces for the independently built §1.1
/// root (wrapped per §2) has the model sibling count and is accepted
/// by `verify_chunk`. (`build_chunk_proof` goes through a `BTreeSet`
/// and `compute_chunked_id` through `build_bmt`'s `Vec<Vec<Hash>>`
/// levels; both ran out of memory even for one chunk, so the builder
/// side is left to the unit tests and the `merkle_proof` fuzz target.)
#[kani::proof]
#[kani::stub(h2, toy_h2)]
#[kani::stub(crate::hash::domain_digest, toy_domain_digest)]
#[kani::stub(crate::hash::hash, toy_hash)]
// <= 2 levels for <= 3 leaves; `spec_proof` pairs <= 3 nodes. Run
// with `-Z unstable-options --cbmc-args --unwindset memcmp.0:33` for
// the 32-byte digest comparisons.
#[kani::unwind(5)]
fn merkle_roundtrip_one_chunk() {
chunk_rt::<1>(1);
}
/// As above for a 2-chunk blob (3 leaves, odd trailing node), both
/// chunk positions, each concrete (a symbolic position, i.e. a
/// symbolic index into the digest vectors, ran out of memory).
#[kani::proof]
#[kani::stub(h2, toy_h2)]
#[kani::stub(crate::hash::domain_digest, toy_domain_digest)]
#[kani::stub(crate::hash::hash, toy_hash)]
// As above: `--cbmc-args --unwindset memcmp.0:33`.
#[kani::unwind(5)]
fn merkle_roundtrip_two_chunks() {
chunk_rt::<2>(1);
chunk_rt::<2>(2);
}
/// SPEC-MERKLE-OBJECTS §5.4 builder rule: "A builder MUST refuse any
/// position `>= leaf_count` ... A builder asked for position 0 of an
/// empty `Tree`, including the range `0..=0`, MUST refuse rather than
/// return the all-default proof." For the empty `Tree` every
/// single-leaf, range and (one-position) multi-leaf request, over
/// every `u32` position, is refused. The `cover` shows the range
/// assertion is on a reachable path.
#[kani::proof]
#[kani::stub(h2, toy_h2)]
#[kani::stub(crate::hash::domain_digest, toy_domain_digest)]
#[kani::stub(crate::hash::hash, toy_hash)]
#[kani::unwind(3)]
fn merkle_builder_empty_tree_refuses() {
let empty = Tree {
entries: Vec::new(),
};
let (p, start, end): (u32, u32, u32) = (kani::any(), kani::any(), kani::any());
assert!(build_tree_entry_proof(&empty, p).is_err());
assert!(build_tree_entries_multi_proof(&empty, [p]).is_err());
let range = build_tree_entries_range_proof(&empty, start, end);
kani::cover!(range.is_err(), "range_refused");
assert!(
range.is_err(),
"empty-Tree range proof must be refused (SPEC-MERKLE-OBJECTS §5.4)"
);
}
/// Canary (§6 "leaf tampered"): the checker must find a forged chunk
/// hash that the verifier rejects under a genuine 2-chunk proof, i.e.
/// falsify "any leaf verifies under a genuine proof".
#[kani::proof]
#[kani::stub(h2, toy_h2)]
#[kani::stub(crate::hash::domain_digest, toy_domain_digest)]
#[kani::stub(crate::hash::hash, toy_hash)]
// As above: `--cbmc-args --unwindset memcmp.0:33`.
#[kani::unwind(6)]
#[kani::should_panic]
fn merkle_canary_tampered_leaf_verifies() {
let (_cb, leaves) = chunked_fixture::<2>();
let (root, siblings) = spec_proof(&leaves, 1);
let id = wrap_id(ObjectKind::ChunkedBlob, &root);
let proof = Proof {
leaf_count: 3,
siblings,
};
let forged: Hash = kani::any();
assert!(verify_chunk(&id, &forged, 1, &proof).is_ok());
}
}