//! A lightweight batch layer over a merkleized structure. //! //! # Overview //! //! [`UnmerkleizedBatch`] accumulates mutations (appends and overwrites) against a parent //! [`MerkleizedBatch`]. Calling [`UnmerkleizedBatch::merkleize`] computes dirty Merkle nodes and //! produces a new [`MerkleizedBatch`]. Batches can be stacked to arbitrary depth //! via `Arc`-backed parent pointers, so multiple forks can coexist on the same parent. //! //! # Lifecycle //! //! ```text //! Mem //! | //! MerkleizedBatch::from_mem() (root batch, no data) //! | //! new_batch() //! | //! v //! UnmerkleizedBatch (accumulate mutations) //! | //! merkleize(&mem, hasher) //! | //! v //! Arc (immutable, merkleized nodes) //! | //! mem.apply_batch(&batch) //! | //! v //! Mem (committed) //! ``` //! //! # Parent chain and memory //! //! Each [`MerkleizedBatch`] stores its own local data (appended nodes and overwrites) //! plus `Arc` refs to each retained ancestor's data, collected during //! [`UnmerkleizedBatch::merkleize`]. These ancestor batches' data are used by //! [`Mem::apply_batch`] to replay uncommitted ancestors without requiring the //! ancestor batches to still be alive. //! //! [`MerkleizedBatch::get_node`] reads from the retained ancestor data. A `Weak` parent //! pointer supports collecting ancestor data for new descendants. Dropping a committed //! ancestor ends that walk, with its data available in the committed [`Mem`]. Each retained //! record carries the size and peaks before and after its changes, so [`Mem::apply_batch`] //! can find the structure's state in the chain and replay only the records that follow it. //! //! During [`UnmerkleizedBatch::merkleize`], the parent is held as a strong `Arc` //! (keeping it alive for the walk), and the `Weak` chain is walked to collect //! ancestor data. After merkleize, the parent is downgraded to `Weak`. //! //! In a pipelining pattern (build next batch from prev, apply prev, repeat), each batch //! holds at most one ancestor batch (its immediate parent's data, as an `Arc` ref). //! When that batch is applied and dropped, the ancestor data is freed. Memory per //! batch is O(batch size), never growing with chain depth. //! //! [`MerkleizedBatch::get_node`] resolves positions stored in the batch chain only. //! For positions in the committed structure, callers fall through to [`Mem::get_node`] //! (or an adapter that layers a batch over a `Mem`). //! //! # Batch invalidation //! //! Unapplied ancestor batches must stay alive while merkleizing descendants. Once merkleized, //! a batch retains the data needed for node reads and application even after its ancestors are //! dropped. Applying a sibling fork to the base invalidates the chain. Applying a descendant //! can invalidate a batch's proofs by overwriting nodes those proofs read from the base. //! [`Mem::apply_batch`] returns an error unless the structure is at a state the chain reached //! before the batch: the base of its oldest retained ancestor or the tip of one of them. //! //! Pruning the base after a batch has been merkleized does not invalidate it: prune and apply //! commute (see [`Mem::apply_batch`]). An unmerkleized batch still reads sibling digests from the //! base while merkleizing, so it must be merkleized before the base is pruned past any leaf it //! updates. //! //! # Parallel appends //! //! With `std`, `UnmerkleizedBatch::add_many` splits its leaves into contiguous ranges, up to one //! per worker. Each range owns the positions from its first leaf to the next range's first leaf, //! or to the end of the batch, which hold its leaves and the internal nodes they create. A worker //! appends its leaves in order and hashes each node they create whose leaves all lie in the range. //! It leaves the others, which also cover earlier leaves, for [`UnmerkleizedBatch::merkleize`]. //! An MMR range has at most one such node per height, covering its first leaf and earlier ones. //! An MMB range can have a second that covers only earlier leaves, since an MMB delays creating a //! node of height `h` until `2^(h-1) - 1` leaves after its last leaf. If a leaf is updated after //! `add_many` hashed its ancestors, `merkleize` hashes them again. //! //! # Example (MMR) //! //! ```ignore //! let hasher = StandardHasher::::new(ForwardFold); //! let mut mmr = Mmr::new(); //! //! // Fork two independent speculative chains from the same base. //! let a1 = mmr.new_batch() //! .add(&hasher, b"a1") //! .merkleize(&mmr, &hasher); //! let b1 = mmr.new_batch() //! .add(&hasher, b"b1") //! .merkleize(&mmr, &hasher); //! //! // Commit A1. //! mmr.apply_batch(&a1).unwrap(); //! ``` use crate::merkle::{ Error, Family, Location, Position, Readable, hasher::Hasher, mem::Mem, proof::Proof, }; use ahash::RandomState; use alloc::{ sync::{Arc, Weak}, vec::Vec, }; #[cfg(feature = "std")] use commonware_codec::Write; use commonware_cryptography::Digest; use commonware_parallel::{Sequential, Strategy}; use commonware_utils::bitmap::BitMap; use core::{iter::Peekable, num::NonZeroUsize, ops::Range}; /// Overwritten node digests keyed by position. pub(crate) type Overwrites = hashbrown::HashMap, D, RandomState>; /// Push a node position into the list for its height, growing the outer Vec as needed. fn push_node(levels: &mut Vec>>, height: u32, pos: Position) { let h = height as usize; if levels.len() <= h { levels.resize_with(h + 1, Vec::new); } levels[h].push(pos); } /// Return every internal node that needs hashing, once each, grouped by height. /// /// `unhashed` lists new internal nodes that still need hashing, ascending within each height. /// `updated_leaves` lists each updated leaf once. Their ancestors need hashing too, unless /// `unhashed` already lists them. fn plan_hashes( size: Position, parent_size: Position, mut updated_leaves: Vec>, mut unhashed: Vec>>, ) -> Vec>> { if updated_leaves.is_empty() { return unhashed; } updated_leaves.sort_unstable(); debug_assert!(updated_leaves.is_sorted_by(|a, b| a < b)); debug_assert!( unhashed .iter() .all(|nodes| nodes.is_sorted_by(|a, b| a < b)) ); // Only new nodes can be unhashed, so skip the search for the parent's nodes. let is_unhashed = |pos: Position, height: u32| { pos >= parent_size && unhashed .get(height as usize) .is_some_and(|nodes| nodes.binary_search(&pos).is_ok()) }; let mut dirty = Vec::new(); let mut leaves = updated_leaves.into_iter().peekable(); let mut first_leaf = Location::new(0); for (pos, height) in F::peaks(size) { let Some(&next) = leaves.peek() else { break; }; let end = first_leaf + (1u64 << height); if next < end { mark_dirty_subtree( &mut dirty, &is_unhashed, pos, height, first_leaf, &mut leaves, ); } first_leaf = end; } assert!(leaves.peek().is_none(), "updated leaf outside the batch"); if unhashed.is_empty() { return dirty; } if unhashed.len() < dirty.len() { unhashed.resize_with(dirty.len(), Vec::new); } for (nodes, dirty) in unhashed.iter_mut().zip(dirty) { nodes.extend(dirty); } unhashed } /// Push the updated leaves' ancestors within this subtree onto `dirty`, once each, skipping those /// `is_unhashed` reports. Advance `leaves` past those leaves. /// /// `leaves` must be sorted and distinct, with its next leaf inside the subtree. fn mark_dirty_subtree( dirty: &mut Vec>>, is_unhashed: &impl Fn(Position, u32) -> bool, pos: Position, height: u32, first_leaf: Location, leaves: &mut Peekable>>, ) { if height == 0 { leaves.next(); return; } if !is_unhashed(pos, height) { push_node(dirty, height, pos); } let (left, right) = F::children(pos, height); let mid = first_leaf + (1u64 << (height - 1)); if leaves.peek().is_some_and(|loc| *loc < mid) { mark_dirty_subtree(dirty, is_unhashed, left, height - 1, first_leaf, leaves); } let end = first_leaf + (1u64 << height); if leaves.peek().is_some_and(|loc| *loc < end) { mark_dirty_subtree(dirty, is_unhashed, right, height - 1, mid, leaves); } } /// Hash the leaves `items`, from leaf `first` on, and each internal node in `nodes` (the batch's /// slice at the range's positions) whose leaves all lie in the range. Return the other internal /// nodes as `(height, position)` pairs in position order. #[cfg(feature = "std")] fn build_range( hasher: &impl Hasher, first: Location, items: &[Item], nodes: &mut [D], ) -> Vec<(u32, Position)> { let first_pos = F::location_to_position(first); let index = |pos: Position| (*pos - *first_pos) as usize; let child_digests = |nodes: &[D], pos: Position, height: u32| { let (left, right) = F::children(pos, height); (nodes[index(left)], nodes[index(right)]) }; // Append the leaves one at a time, visiting the nodes each one creates in position order. A // left child waits for its sibling so the two hash as a pair. A parent is created after its // right child, so both children are hashed by then. let mut unhashed = Vec::new(); // Left children waiting for their sibling, by height. let mut waiting: [Option>; 64] = [None; 64]; let mut buf = Vec::new(); let mut pos = first_pos; for (loc, item) in (*first..).zip(items) { buf.clear(); item.write(&mut buf); nodes[index(pos)] = hasher.leaf_digest(pos, &buf); for height in F::parent_heights(Location::new(loc)) { pos += 1; // The count is now `loc + 1`, `birth_offset` past this node's leftmost leaf. let leftmost = loc + 1 - F::birth_offset(height); if leftmost < *first { unhashed.push((height, pos)); continue; } let h = height as usize; let is_left_child = (leftmost >> height).is_multiple_of(2); if is_left_child { // At each height, the right sibling takes the slot before the next left child. debug_assert!(waiting[h].is_none()); waiting[h] = Some(pos); continue; } let (rl, rr) = child_digests(nodes, pos, height); match waiting[h].take() { Some(left) => { let (ll, lr) = child_digests(nodes, left, height); let (left_digest, right_digest) = hasher.node_digest_pair([(left, &ll, &lr), (pos, &rl, &rr)]); nodes[index(left)] = left_digest; nodes[index(pos)] = right_digest; } None => nodes[index(pos)] = hasher.node_digest(pos, &rl, &rr), } } pos += 1; } // Hash alone the left children whose sibling is created after this range. for (height, left) in (0u32..).zip(waiting) { if let Some(left) = left { let (ll, lr) = child_digests(nodes, left, height); nodes[index(left)] = hasher.node_digest(left, &ll, &lr); } } unhashed } /// A speculative batch whose root digest has not yet been computed, /// in contrast to [`MerkleizedBatch`]. pub struct UnmerkleizedBatch { parent: Arc>, appended: Vec, /// Nodes this batch overwrites, by position. Every key is below the parent's size, and nodes at /// or above it are in `appended`. Until [`Self::merkleize`] hashes internal nodes, the map /// holds only overwritten parent leaves. overwrites: Overwrites, /// New internal nodes not yet hashed, grouped by height and ascending within each. unhashed_nodes: Vec>>, /// The first leaf `add_many` added to this batch. Only new leaves from here on can have /// ancestors this batch has already hashed. add_many_start: Option>, /// Bit `i` is set if leaf `add_many_start + i` was updated. updated_new_leaves: BitMap, } impl UnmerkleizedBatch { /// Create a new batch from `parent`. pub fn new(parent: Arc>) -> Self { Self { parent, appended: Vec::new(), overwrites: Overwrites::default(), unhashed_nodes: Vec::new(), add_many_start: None, updated_new_leaves: BitMap::new(), } } /// Return a reference to the batch's strategy. pub fn strategy(&self) -> &S { &self.parent.strategy } /// Retain the live parent chain up to the first dropped weak link. /// /// Nodes beyond that link are read from committed state. #[cfg(feature = "std")] pub(crate) fn retain_ancestors(&self) -> Vec>> { let mut ancestors = Vec::new(); let mut current = Some(Arc::clone(&self.parent)); while let Some(batch) = current { current = batch.parent.as_ref().and_then(Weak::upgrade); ancestors.push(batch); } ancestors } /// The total number of nodes visible through this batch. pub(crate) fn size(&self) -> Position { Position::new(*self.parent.size() + self.appended.len() as u64) } /// The number of leaves visible through this batch. pub fn leaves(&self) -> Location { Location::try_from(self.size()).expect("invalid size") } /// Resolve a node: own data -> parent chain -> `base` fallback. fn get_node(&self, base: &Mem, pos: Position) -> Option { if pos >= self.size() { return None; } // Overwrites only hold positions below the parent's size (see `store_node`). let parent_size = self.parent.size(); if pos >= parent_size { let index = (*pos - *parent_size) as usize; return self.appended.get(index).copied(); } if let Some(d) = self.overwrites.get(&pos) { return Some(*d); } if let Some(d) = self.parent.get_node(pos) { return Some(d); } base.get_node(pos) } /// Store a digest at the given position. /// /// Positions at or above the parent's size belong to nodes this batch appended and go to /// `appended`, indexed from the parent's size. Positions below it go to `overwrites`. fn store_node(&mut self, pos: Position, digest: D) { let parent_size = self.parent.size(); if pos >= parent_size { let index = (*pos - *parent_size) as usize; self.appended[index] = digest; } else { self.overwrites.insert(pos, digest); } } /// Store an updated leaf digest. If `add_many` may have hashed the leaf's ancestors, record it /// so `merkleize` rehashes them. fn store_leaf(&mut self, loc: Location, pos: Position, digest: D) { self.store_node(pos, digest); if let Some(start) = self.add_many_start && loc >= start { let bit = *loc - *start; self.updated_new_leaves.extend_to(bit + 1); self.updated_new_leaves.set(bit, true); } } /// Return every internal node this batch must hash, once each, grouped by height. fn hash_plan(&mut self) -> Vec>> { let mut updated_leaves: Vec<_> = self .overwrites .keys() .map(|&pos| { Location::try_from(pos).expect("only leaves are overwritten before merkleize") }) .collect(); if let Some(start) = self.add_many_start { updated_leaves.extend(self.updated_new_leaves.ones_iter().map(|bit| start + bit)); } plan_hashes( self.size(), self.parent.size(), updated_leaves, core::mem::take(&mut self.unhashed_nodes), ) } /// Add a pre-computed leaf digest. pub fn add_leaf_digest(mut self, digest: D) -> Self { self.append_leaf_digest(digest, self.leaves(), self.size()); self } /// Append a leaf digest and any parent placeholders. /// /// `leaves` is the leaf index this digest occupies and `size` is the starting node count. /// Returns the new size. fn append_leaf_digest( &mut self, digest: D, leaves: Location, mut size: Position, ) -> Position { self.appended.push(digest); size += 1; for height in F::parent_heights(leaves) { self.appended.push(D::EMPTY); push_node(&mut self.unhashed_nodes, height, size); size += 1; } size } /// Add a run of pre-computed leaf digests, in order. #[cfg(feature = "std")] pub fn add_leaf_digests(mut self, digests: impl IntoIterator) -> Self { // Each leaf also appends its parent placeholders, so reserve for the full node count. let digests = digests.into_iter(); let n = digests.size_hint().0 as u64; let leaves = self.leaves(); let mut size = self.size(); let end = leaves.checked_add(n).expect("leaf count overflow"); let additional = (*Position::try_from(end).expect("size overflow") - *size) as usize; self.appended.reserve(additional); // Maintain leaf position and location incrementally to avoid recomputation on every iteration. for (i, digest) in (0u64..).zip(digests) { size = self.append_leaf_digest(digest, leaves + i, size); } self } /// Hash `element` and add it as a leaf. pub fn add(self, hasher: &impl Hasher, element: &[u8]) -> Self { let digest = hasher.leaf_digest(self.size(), element); self.add_leaf_digest(digest) } /// Add `items` as leaves in order, encoding and hashing them across the strategy. /// /// Matches calling [`add`](Self::add) on each item's encoding, which for `Bytes` includes a /// length prefix, provided [`merkleize`](Self::merkleize) uses the same `hasher`. Otherwise the /// root is unspecified. /// /// # Panics /// /// Panics if the leaf count would exceed [`Family::MAX_LEAVES`]. #[cfg(feature = "std")] pub fn add_many( mut self, hasher: &impl Hasher, items: &[Item], ) -> Self { if items.is_empty() { return self; } let first = self.leaves(); self.add_many_start.get_or_insert(first); let end = first .checked_add(items.len() as u64) .expect("leaf count overflow"); let new_len = (*F::location_to_position(end) - *self.parent.size()) as usize; let old_len = self.appended.len(); let strategy = &self.parent.strategy; let appended = &mut self.appended; let unhashed_nodes = &mut self.unhashed_nodes; strategy.run_batches(items.len(), NonZeroUsize::MIN, 1, |batches| { appended.resize(new_len, D::EMPTY); let nodes = &mut appended[old_len..]; let unhashed = batches.map_collect_vec( |ranges| { // Each range takes its nodes off the front of `rest`, so the ranges must // cover `items` in order. let mut jobs = Vec::with_capacity(ranges.len()); let mut rest = nodes; let mut covered = 0; for range in ranges { assert_eq!(range.start, covered, "ranges must cover the items in order"); covered = range.end; let range_first = first + range.start as u64; let node_count = *F::location_to_position(first + range.end as u64) - *F::location_to_position(range_first); let range_nodes = rest .split_off_mut(..node_count as usize) .expect("range ends within the batch"); jobs.push((range_first, &items[range], range_nodes)); } assert!(rest.is_empty(), "ranges must cover the items in order"); jobs }, |(range_first, range_items, range_nodes)| { build_range(hasher, range_first, range_items, range_nodes) }, ); for (height, pos) in unhashed.into_iter().flatten() { push_node(unhashed_nodes, height, pos); } }); self } /// Validate that `loc` refers to an in-bounds, non-pruned leaf and return its position. /// /// # Errors /// /// Returns [`Error::LeafOutOfBounds`] if `loc` is beyond the current leaf count, or /// [`Error::ElementPruned`] if the leaf has been pruned. fn validate_loc(&self, loc: Location) -> Result, Error> { if loc >= self.leaves() { return Err(Error::LeafOutOfBounds(loc)); } if loc < self.parent.pruning_boundary() { return Err(Error::ElementPruned(Position::try_from(loc)?)); } Position::try_from(loc) } /// Update the leaf at `loc` to `element`. /// /// # Errors /// /// Returns [`Error::LeafOutOfBounds`] if `loc` is not an existing leaf. /// Returns [`Error::ElementPruned`] if the leaf has been pruned. pub fn update_leaf( mut self, hasher: &impl Hasher, loc: Location, element: &[u8], ) -> Result> { let pos = self.validate_loc(loc)?; let digest = hasher.leaf_digest(pos, element); self.store_leaf(loc, pos, digest); Ok(self) } /// Overwrite the digest of an existing leaf. #[cfg(any(feature = "std", test))] pub fn update_leaf_digest(mut self, loc: Location, digest: D) -> Result> { let pos = self.validate_loc(loc)?; self.store_leaf(loc, pos, digest); Ok(self) } /// Batch update multiple leaf digests. #[cfg(any(feature = "std", test))] pub fn update_leaf_batched(mut self, updates: &[(Location, D)]) -> Result> { // Validate all first so a later failure can't leave a partially-applied batch. for (loc, _) in updates { self.validate_loc(*loc)?; } for (loc, digest) in updates { let pos = Position::try_from(*loc).expect("validated above"); self.store_leaf(*loc, pos, *digest); } Ok(self) } /// Consume this batch and produce an immutable [`MerkleizedBatch`] with computed dirty nodes. /// `base` provides committed node data as fallback during hash computation. /// /// # Panics /// /// Panics if a node it reads is in neither the batch chain nor `base`. That happens when `base` /// has been pruned past a leaf this batch updates, or when an unapplied ancestor was dropped /// before the parent was merkleized and appended a node this batch reads, such as a peak of /// its tip. A batch merkleized after an unapplied ancestor was dropped does not retain that /// ancestor's records, so [`Mem::apply_batch`] rejects it unless the structure already holds /// them. The [module docs](crate::merkle::batch) describe these cases under "Batch /// invalidation". pub fn merkleize( mut self, base: &Mem, hasher: &impl Hasher, ) -> Arc> { let levels = self.hash_plan(); // Dirty nodes below the parent's size land in `overwrites`, so size it once instead of // rehashing as it grows. let parent_size = self.parent.size(); let overwritten: usize = levels .iter() .map(|level| level.iter().filter(|pos| **pos < parent_size).count()) .sum(); self.overwrites.reserve(overwritten); for (height, positions) in levels.iter().enumerate() { if positions.is_empty() { continue; } self.merkleize_level(base, hasher, positions, height as u32); } // Record the peaks of the state this batch represents. A batch without changes shares // its parent's. let tip_peaks: Arc<[D]> = if self.appended.is_empty() && self.overwrites.is_empty() { Arc::clone(&self.parent.data.tip_peaks) } else { F::peaks(self.size()) .map(|(pos, _)| { self.get_node(base, pos) .expect("peak must be in the batch chain or base") }) .collect() }; // Collect ancestor data by walking the parent chain (strong Arc + Weak walk). let ancestors = collect_ancestor_batches(&self.parent); Arc::new(MerkleizedBatch { parent: Some(Arc::downgrade(&self.parent)), data: Arc::new(BatchData { parent_size: self.parent.size(), appended: self.appended, overwrites: self.overwrites, parent_peaks: Arc::clone(&self.parent.data.tip_peaks), tip_peaks, }), base_size: self.parent.base_size, pruning_boundary: self.parent.pruning_boundary(), ancestors, strategy: self.parent.strategy.clone(), }) } /// Fetch the child digests of the node at `pos`. fn child_digests(&self, base: &Mem, pos: Position, height: u32) -> (D, D) { let (left, right) = F::children(pos, height); let left = self.get_node(base, left).expect("left child missing"); let right = self.get_node(base, right).expect("right child missing"); (left, right) } /// Compute the digests of `positions` two at a time so the hasher can make progress on both /// concurrently, appending `(position, digest)` results to `output`. fn zip_nodes( &self, base: &Mem, hasher: &impl Hasher, positions: &[Position], height: u32, output: &mut Vec<(Position, D)>, ) { let (pairs, remainder) = positions.as_chunks::<2>(); for pair in pairs { let (left, right) = (pair[0], pair[1]); let (ll, lr) = self.child_digests(base, left, height); let (rl, rr) = self.child_digests(base, right, height); let (left_digest, right_digest) = hasher.node_digest_pair([(left, &ll, &lr), (right, &rl, &rr)]); output.push((left, left_digest)); output.push((right, right_digest)); } if let [pos] = remainder { let (left, right) = self.child_digests(base, *pos, height); output.push((*pos, hasher.node_digest(*pos, &left, &right))); } } /// Compute digests for one height's dirty nodes via the configured strategy. /// /// The strategy splits the positions into batches of adjacent pairs, so every pair reaches /// [`Hasher::node_digest_pair`] together and only the last batch can end in a lone node. fn merkleize_level( &mut self, base: &Mem, hasher: &impl Hasher, positions: &[Position], height: u32, ) { let pairs = positions.len().div_ceil(2); let computed: Vec, D)>> = self.parent .strategy .run_batches(pairs, NonZeroUsize::MIN, 2, |batches| { batches.map_collect_vec( |ranges| ranges, |range| { let positions = &positions[2 * range.start..positions.len().min(2 * range.end)]; let mut computed = Vec::with_capacity(positions.len()); self.zip_nodes(base, hasher, positions, height, &mut computed); computed }, ) }); for nodes in computed { for (pos, digest) in nodes { self.store_node(pos, digest); } } } } /// A batch's changes and the states before and after them, shared with descendants. #[derive(Debug)] pub(super) struct BatchData { /// Number of nodes before this batch's changes. pub(super) parent_size: Position, /// Nodes this batch appends after `parent_size`. pub(super) appended: Vec, /// Nodes this batch overwrites, by position. Every key is below `parent_size`, and nodes at or /// above it are in `appended`. pub(super) overwrites: Overwrites, /// Peak digests of the state before this batch's changes. pub(super) parent_peaks: Arc<[D]>, /// Peak digests of the state after this batch's changes. pub(super) tip_peaks: Arc<[D]>, } impl BatchData { /// Number of nodes after this batch's changes. pub(super) fn size(&self) -> Position { Position::new(*self.parent_size + self.appended.len() as u64) } fn is_empty(&self) -> bool { self.appended.is_empty() && self.overwrites.is_empty() } } /// Collect the records of `parent` and the ancestors still reachable through its `Weak` chain, /// in root-to-tip order. Skips empty records (e.g. root batches from `from_mem`). fn collect_ancestor_batches( parent: &Arc>, ) -> Vec>> { let mut ancestors = Vec::new(); // Parent is alive (strong Arc held by UnmerkleizedBatch). if !parent.data.is_empty() { ancestors.push(Arc::clone(&parent.data)); } // Walk Weak chain for grandparents+. let mut current = parent.parent.as_ref().and_then(Weak::upgrade); while let Some(batch) = current { if !batch.data.is_empty() { ancestors.push(Arc::clone(&batch.data)); } current = batch.parent.as_ref().and_then(Weak::upgrade); } ancestors.reverse(); ancestors } /// A speculative batch whose dirty Merkle nodes have been computed, in contrast to /// [`UnmerkleizedBatch`]. #[derive(Debug)] pub struct MerkleizedBatch { /// The parent batch in the chain, if any. parent: Option>, /// This batch's own changes and the states before and after them. pub(super) data: Arc>, /// Number of committed nodes when the batch chain was forked. Inherited unchanged /// by all descendants. pub(crate) base_size: Position, /// Pruning boundary of the [`Mem`] when the batch chain was forked. Inherited /// unchanged by all descendants, like `base_size`. pruning_boundary: Location, /// Records of the non-empty ancestors still alive at merkleize, in root-to-tip order. Each /// record holds only that ancestor's own changes. pub(super) ancestors: Vec>>, pub(crate) strategy: S, } impl MerkleizedBatch { /// Create a root batch representing the committed state of `mem`, with the default /// [`Sequential`] strategy. pub fn from_mem(mem: &Mem) -> Arc { Self::from_mem_with_strategy(mem, Sequential) } } impl MerkleizedBatch { /// Create a root batch representing the committed state of `mem`, using `strategy` /// for merkleization. pub fn from_mem_with_strategy(mem: &Mem, strategy: S) -> Arc { let peaks: Arc<[D]> = mem.peaks().collect(); Arc::new(Self { parent: None, data: Arc::new(BatchData { parent_size: mem.size(), appended: Vec::new(), overwrites: Overwrites::default(), parent_peaks: Arc::clone(&peaks), tip_peaks: peaks, }), base_size: mem.size(), pruning_boundary: mem.pruning_boundary(), ancestors: Vec::new(), strategy, }) } /// The total number of nodes visible through this batch. pub fn size(&self) -> Position { self.data.size() } /// Number of ancestor records this batch retains. #[cfg(feature = "std")] pub(crate) const fn ancestor_count(&self) -> usize { self.ancestors.len() } /// Resolve a node from this batch and its retained ancestor data, newest first. /// /// Returns `None` for positions that exist only in the committed [`Mem`]. Read those /// positions with [`Mem::get_node`] or a reader that combines the batch and base. pub fn get_node(&self, pos: Position) -> Option { if pos >= self.size() { return None; } // A record's overwrites only hold positions below its parent's size. for data in core::iter::once(&self.data).chain(self.ancestors.iter().rev()) { if pos >= data.parent_size { let i = (*pos - *data.parent_size) as usize; return data.appended.get(i).copied(); } if let Some(d) = data.overwrites.get(&pos) { return Some(*d); } } None } /// Iterate the nodes this batch appended or overwrote relative to its parent batch. #[cfg(feature = "std")] pub(crate) fn local_nodes(&self) -> impl Iterator, D)> + '_ { self.data .overwrites .iter() .map(|(&pos, &digest)| (pos, digest)) .chain( self.data .appended .iter() .enumerate() .map(|(index, &digest)| { (Position::new(*self.data.parent_size + index as u64), digest) }), ) } /// Compute the root digest after this batch's mutations using `inactive_peaks` and the bagging /// carried by `hasher`. pub fn root( &self, hasher: &impl Hasher, inactive_peaks: usize, ) -> Result> { hasher.root(self.leaves(), inactive_peaks, self.data.tip_peaks.iter()) } /// Inclusion proof for the element at `loc` using `inactive_peaks` and the bagging carried by /// `hasher`. pub fn proof( &self, base: &Mem, hasher: &impl Hasher, loc: Location, inactive_peaks: usize, ) -> Result, Error> { if !loc.is_valid_index() { return Err(Error::LocationOverflow(loc)); } self.range_proof(base, hasher, loc..loc + 1, inactive_peaks) .map_err(|e| match e { Error::RangeOutOfBounds(_) => Error::LeafOutOfBounds(loc), _ => e, }) } /// Inclusion proof for all elements in `range` using `inactive_peaks` and the bagging carried /// by `hasher`. pub fn range_proof( &self, base: &Mem, hasher: &impl Hasher, range: Range>, inactive_peaks: usize, ) -> Result, Error> { crate::merkle::RangePlan::new(self.leaves(), range)?.build(hasher, inactive_peaks, |pos| { Self::get_node(self, pos).or_else(|| base.get_node(pos)) }) } /// Items before this location have been pruned. pub const fn pruning_boundary(&self) -> Location { self.pruning_boundary } /// The number of leaves visible through this batch. pub fn leaves(&self) -> Location { Location::try_from(self.size()).expect("invalid size") } /// Create a child batch on top of this merkleized batch. /// /// The child must be merkleized before unapplied ancestor batches are dropped. Applying a /// sibling fork to the base invalidates it. pub fn new_batch(self: &Arc) -> UnmerkleizedBatch { UnmerkleizedBatch::new(Arc::clone(self)) } /// Number of nodes in the committed Mem when the batch chain was forked. pub const fn base_size(&self) -> Position { self.base_size } /// The appended nodes of this batch and its retained ancestors that `mem` has not applied, /// in root-to-tip order. /// /// # Errors /// /// Returns the errors of [`Mem::validate_batch`], and [`Error::DataCorrupted`] if any of /// those records overwrites a node. #[cfg(feature = "std")] pub(crate) fn unapplied<'a>( &'a self, mem: &Mem, ) -> Result + use<'a, F, D, S>, Error> { let start = mem.validate_batch(self)?; let records = || { self.ancestors[start..] .iter() .chain(core::iter::once(&self.data)) }; if records().any(|data| !data.overwrites.is_empty()) { return Err(Error::DataCorrupted("batch overwrites nodes")); } Ok(records().map(|data| data.appended.as_slice())) } /// Return a reference to the batch's strategy. pub const fn strategy(&self) -> &S { &self.strategy } } impl Readable for MerkleizedBatch { type Family = F; type Digest = D; fn size(&self) -> Position { Self::size(self) } fn get_node(&self, pos: Position) -> Option { Self::get_node(self, pos) } } #[cfg(test)] mod tests { use super::*; #[cfg(feature = "std")] use crate::merkle::Graftable; use crate::merkle::{Bagging::ForwardFold, hasher::Standard, mem::Mem, path}; use alloc::collections::BTreeSet; use commonware_cryptography::{Sha256, sha256}; use commonware_parallel::mocks::explore; #[cfg(feature = "std")] use commonware_parallel::mocks::{self, Explorer}; #[cfg(feature = "std")] use commonware_utils::NZUsize; use core::sync::atomic::{AtomicUsize, Ordering}; type D = sha256::Digest; type H = Standard; fn mem_root(mem: &Mem, hasher: &H) -> D { mem.root(hasher, 0).unwrap() } fn batch_root( batch: &MerkleizedBatch, hasher: &H, ) -> D { batch.root(hasher, 0).unwrap() } fn build_reference(hasher: &H, n: u64) -> Mem { let mut mem = Mem::new(); let batch = { let mut batch = mem.new_batch(); for i in 0u64..n { let element = hasher.digest(&i.to_be_bytes()); batch = batch.add(hasher, &element); } batch.merkleize(&mem, hasher) }; mem.apply_batch(&batch).unwrap(); mem } fn consistency_with_reference() { let hasher: H = Standard::new(ForwardFold); for &n in &[1u64, 2, 10, 100, 199] { let reference = build_reference::(&hasher, n); let base = Mem::::new(); let mut batch = base.new_batch(); for i in 0..n { let element = hasher.digest(&i.to_be_bytes()); batch = batch.add(&hasher, &element); } let merkleized = batch.merkleize(&base, &hasher); let mut result = Mem::::new(); result.apply_batch(&merkleized).unwrap(); assert_eq!( mem_root(&result, &hasher), mem_root(&reference, &hasher), "root mismatch for n={n}" ); } } fn lifecycle() { let hasher: H = Standard::new(ForwardFold); let base = build_reference::(&hasher, 50); let base_root = mem_root(&base, &hasher); let mut batch = base.new_batch(); for i in 50u64..60 { let element = hasher.digest(&i.to_be_bytes()); batch = batch.add(&hasher, &element); } let merkleized = batch.merkleize(&base, &hasher); assert_ne!(batch_root(&merkleized, &hasher), base_root); assert_eq!(mem_root(&base, &hasher), base_root); // Apply and verify proof from the resulting Mem. let mut applied = base; applied.apply_batch(&merkleized).unwrap(); let loc = Location::::new(55); let element = hasher.digest(&55u64.to_be_bytes()); let proof = applied.proof(&hasher, loc, 0).unwrap(); assert!(proof.verify_element_inclusion( &hasher, loc, &element, &batch_root(&merkleized, &hasher) )); } fn apply_batch() { let hasher: H = Standard::new(ForwardFold); let mut base = build_reference::(&hasher, 50); let mut batch = base.new_batch(); for i in 50u64..75 { let element = hasher.digest(&i.to_be_bytes()); batch = batch.add(&hasher, &element); } let merkleized = batch.merkleize(&base, &hasher); let new_root = batch_root(&merkleized, &hasher); base.apply_batch(&merkleized).unwrap(); assert_eq!(mem_root(&base, &hasher), new_root); let reference = build_reference::(&hasher, 75); assert_eq!(mem_root(&base, &hasher), mem_root(&reference, &hasher)); } fn multiple_forks() { let hasher: H = Standard::new(ForwardFold); let base = build_reference::(&hasher, 50); let base_root = mem_root(&base, &hasher); let mut ba = base.new_batch(); for i in 50u64..60 { let element = hasher.digest(&i.to_be_bytes()); ba = ba.add(&hasher, &element); } let ma = ba.merkleize(&base, &hasher); let mut bb = base.new_batch(); for i in 100u64..105 { let element = hasher.digest(&i.to_be_bytes()); bb = bb.add(&hasher, &element); } let mb = bb.merkleize(&base, &hasher); assert_ne!(batch_root(&ma, &hasher), batch_root(&mb, &hasher)); assert_ne!(batch_root(&ma, &hasher), base_root); assert_eq!(mem_root(&base, &hasher), base_root); } fn fork_of_fork_reads() { let hasher: H = Standard::new(ForwardFold); let base = build_reference::(&hasher, 50); let mut ba = base.new_batch(); for i in 50u64..60 { let element = hasher.digest(&i.to_be_bytes()); ba = ba.add(&hasher, &element); } let ma = ba.merkleize(&base, &hasher); let mut bb = ma.new_batch(); for i in 60u64..70 { let element = hasher.digest(&i.to_be_bytes()); bb = bb.add(&hasher, &element); } let mb = bb.merkleize(&base, &hasher); let reference = build_reference::(&hasher, 70); assert_eq!(batch_root(&mb, &hasher), mem_root(&reference, &hasher)); // Apply both batches and verify proofs from the resulting Mem. let mut applied = base; applied.apply_batch(&ma).unwrap(); applied.apply_batch(&mb).unwrap(); for i in [0u64, 25, 55, 65, 69] { let loc = Location::::new(i); let element = hasher.digest(&i.to_be_bytes()); let proof = applied.proof(&hasher, loc, 0).unwrap(); assert!(proof.verify_element_inclusion( &hasher, loc, &element, &batch_root(&mb, &hasher) )); } } fn update_leaf_digest_roundtrip() { let hasher: H = Standard::new(ForwardFold); let base = build_reference::(&hasher, 100); let base_root = mem_root(&base, &hasher); let updated = Sha256::fill(0xFF); let m = base .new_batch() .update_leaf_digest(Location::new(5), updated) .unwrap() .merkleize(&base, &hasher); assert_ne!(batch_root(&m, &hasher), base_root); let pos5 = Position::::try_from(Location::new(5)).unwrap(); let original = base.get_node(pos5).unwrap(); let m2 = base .new_batch() .update_leaf_digest(Location::new(5), original) .unwrap() .merkleize(&base, &hasher); assert_eq!(batch_root(&m2, &hasher), base_root); } fn update_and_add() { let hasher: H = Standard::new(ForwardFold); let base = build_reference::(&hasher, 50); let base_root = mem_root(&base, &hasher); let updated = Sha256::fill(0xAA); let mut batch = base .new_batch() .update_leaf_digest(Location::new(10), updated) .unwrap(); for i in 50u64..55 { let element = hasher.digest(&i.to_be_bytes()); batch = batch.add(&hasher, &element); } let m = batch.merkleize(&base, &hasher); assert_ne!(batch_root(&m, &hasher), base_root); let pos10 = Position::::try_from(Location::new(10)).unwrap(); assert_eq!(m.get_node(pos10), Some(updated)); } fn update_leaf_batched_roundtrip() { let hasher: H = Standard::new(ForwardFold); let base = build_reference::(&hasher, 100); let base_root = mem_root(&base, &hasher); let updated = Sha256::fill(0xBB); let locs = [0u64, 10, 50, 99]; let updates: Vec<(Location, D)> = locs.iter().map(|&i| (Location::new(i), updated)).collect(); let m = base .new_batch() .update_leaf_batched(&updates) .unwrap() .merkleize(&base, &hasher); assert_ne!(batch_root(&m, &hasher), base_root); let restore: Vec<(Location, D)> = locs .iter() .map(|&l| { let pos = Position::::try_from(Location::new(l)).unwrap(); (Location::new(l), base.get_node(pos).unwrap()) }) .collect(); let m2 = base .new_batch() .update_leaf_batched(&restore) .unwrap() .merkleize(&base, &hasher); assert_eq!(batch_root(&m2, &hasher), base_root); } fn proof_verification() { let hasher: H = Standard::new(ForwardFold); let base = build_reference::(&hasher, 50); let mut batch = base.new_batch(); for i in 50u64..60 { let element = hasher.digest(&i.to_be_bytes()); batch = batch.add(&hasher, &element); } let m = batch.merkleize(&base, &hasher); // Apply and verify proofs from the resulting Mem. let mut applied = base; applied.apply_batch(&m).unwrap(); let loc = Location::::new(55); let element = hasher.digest(&55u64.to_be_bytes()); let proof = applied.proof(&hasher, loc, 0).unwrap(); assert!(proof.verify_element_inclusion(&hasher, loc, &element, &batch_root(&m, &hasher))); let range = Location::::new(50)..Location::new(55); let rp = applied.range_proof(&hasher, range.clone(), 0).unwrap(); let elements: Vec = (50u64..55) .map(|i| hasher.digest(&i.to_be_bytes())) .collect(); assert!(rp.verify_range_inclusion( &hasher, range.start, &elements, &batch_root(&m, &hasher) )); } /// A proof requested directly from a speculative [`MerkleizedBatch`], before it is applied to /// `base`, must succeed even when the Merkle path needs nodes that only exist in `base`. The /// batch chain alone does not contain nodes committed before the fork. fn speculative_proof_uses_base_fallback() { let hasher: H = Standard::new(ForwardFold); let base = build_reference::(&hasher, 50); let mut batch = base.new_batch(); for i in 50u64..55 { let element = hasher.digest(&i.to_be_bytes()); batch = batch.add(&hasher, &element); } let m = batch.merkleize(&base, &hasher); let expected_root = batch_root(&m, &hasher); // A newly appended leaf: the path needs the committed peaks. let loc = Location::::new(52); let element = hasher.digest(&52u64.to_be_bytes()); let proof = m.proof(&base, &hasher, loc, 0).unwrap(); assert!(proof.verify_element_inclusion(&hasher, loc, &element, &expected_root)); // A committed leaf: the path needs committed siblings as well as committed peaks. let loc = Location::::new(49); let element = hasher.digest(&49u64.to_be_bytes()); let proof = m.proof(&base, &hasher, loc, 0).unwrap(); assert!(proof.verify_element_inclusion(&hasher, loc, &element, &expected_root)); // A range of new leaves and a range spanning the fork boundary. for range in [ Location::::new(50)..Location::::new(55), Location::::new(45)..Location::::new(55), ] { let elements: Vec = (*range.start..*range.end) .map(|i| hasher.digest(&i.to_be_bytes())) .collect(); let rp = m.range_proof(&base, &hasher, range.clone(), 0).unwrap(); assert!(rp.verify_range_inclusion(&hasher, range.start, &elements, &expected_root)); } } fn empty_batch() { let hasher: H = Standard::new(ForwardFold); let mut base = build_reference::(&hasher, 50); let base_root = mem_root(&base, &hasher); let m = base.new_batch().merkleize(&base, &hasher); assert_eq!(batch_root(&m, &hasher), base_root); let child = m.new_batch().merkleize(&base, &hasher); base.apply_batch(&child).unwrap(); assert_eq!(mem_root(&base, &hasher), base_root); } fn batch_roundtrip() { let hasher: H = Standard::new(ForwardFold); let base = build_reference::(&hasher, 50); let mut batch = base.new_batch(); for i in 50u64..55 { let element = hasher.digest(&i.to_be_bytes()); batch = batch.add(&hasher, &element); } let merkleized = batch.merkleize(&base, &hasher); let mut batch_again = merkleized.new_batch(); for i in 55u64..60 { let element = hasher.digest(&i.to_be_bytes()); batch_again = batch_again.add(&hasher, &element); } let reference = build_reference::(&hasher, 60); assert_eq!( batch_root(&batch_again.merkleize(&base, &hasher), &hasher), mem_root(&reference, &hasher) ); } fn sequential_apply_batch() { let hasher: H = Standard::new(ForwardFold); let mut base = build_reference::(&hasher, 50); let mut b1 = base.new_batch(); for i in 50u64..60 { let element = hasher.digest(&i.to_be_bytes()); b1 = b1.add(&hasher, &element); } let m1 = b1.merkleize(&base, &hasher); base.apply_batch(&m1).unwrap(); let mut b2 = base.new_batch(); for i in 60u64..70 { let element = hasher.digest(&i.to_be_bytes()); b2 = b2.add(&hasher, &element); } let m2 = b2.merkleize(&base, &hasher); base.apply_batch(&m2).unwrap(); let reference = build_reference::(&hasher, 70); assert_eq!(mem_root(&base, &hasher), mem_root(&reference, &hasher)); } fn batch_on_pruned_base() { let hasher: H = Standard::new(ForwardFold); let mut base = build_reference::(&hasher, 100); base.prune(Location::new(27)).unwrap(); let mut batch = base.new_batch(); for i in 100u64..110 { let element = hasher.digest(&i.to_be_bytes()); batch = batch.add(&hasher, &element); } let m = batch.merkleize(&base, &hasher); let expected_root = batch_root(&m, &hasher); // Apply and verify proofs from the resulting Mem. let mut applied = base; applied.apply_batch(&m).unwrap(); let loc = Location::::new(80); let element = hasher.digest(&80u64.to_be_bytes()); let proof = applied.proof(&hasher, loc, 0).unwrap(); assert!(proof.verify_element_inclusion(&hasher, loc, &element, &expected_root)); assert!(matches!( applied.proof(&hasher, Location::new(0), 0), Err(Error::ElementPruned(_)) )); } fn three_deep_stacking() { let hasher: H = Standard::new(ForwardFold); let mut base = build_reference::(&hasher, 100); let da = Sha256::fill(0xDD); let db = Sha256::fill(0xEE); let ma = base .new_batch() .update_leaf_digest(Location::new(5), da) .unwrap() .merkleize(&base, &hasher); let mb = ma .new_batch() .update_leaf_digest(Location::new(10), db) .unwrap() .merkleize(&base, &hasher); let mut bc = mb.new_batch(); for i in 300u64..310 { let element = hasher.digest(&i.to_be_bytes()); bc = bc.add(&hasher, &element); } let mc = bc.merkleize(&base, &hasher); let c_root = batch_root(&mc, &hasher); base.apply_batch(&mc).unwrap(); assert_eq!(mem_root(&base, &hasher), c_root); } fn overwrite_collision() { let hasher: H = Standard::new(ForwardFold); let mut base = build_reference::(&hasher, 100); let dx = Sha256::fill(0xAA); let dy = Sha256::fill(0xBB); let ma = base .new_batch() .update_leaf_digest(Location::new(5), dx) .unwrap() .merkleize(&base, &hasher); let mb = ma .new_batch() .update_leaf_digest(Location::new(5), dy) .unwrap() .merkleize(&base, &hasher); let b_root = batch_root(&mb, &hasher); base.apply_batch(&mb).unwrap(); assert_eq!(mem_root(&base, &hasher), b_root); let pos5 = Position::::try_from(Location::new(5)).unwrap(); assert_eq!(base.get_node(pos5), Some(dy)); } fn update_appended_leaf() { let hasher: H = Standard::new(ForwardFold); let base = build_reference::(&hasher, 50); let mut batch = base.new_batch(); for i in 50u64..60 { let element = hasher.digest(&i.to_be_bytes()); batch = batch.add(&hasher, &element); } let updated = Sha256::fill(0xEE); let m = batch .update_leaf_digest(Location::new(52), updated) .unwrap() .merkleize(&base, &hasher); let pos52 = Position::::try_from(Location::new(52)).unwrap(); assert_eq!(m.get_node(pos52), Some(updated)); let mut reference = build_reference::(&hasher, 60); let batch = reference .new_batch() .update_leaf_digest(Location::new(52), updated) .unwrap() .merkleize(&reference, &hasher); reference.apply_batch(&batch).unwrap(); assert_eq!(batch_root(&m, &hasher), mem_root(&reference, &hasher)); } fn update_leaf_element() { let hasher: H = Standard::new(ForwardFold); let base = build_reference::(&hasher, 50); let base_root = mem_root(&base, &hasher); let element = b"updated-element"; let m = base .new_batch() .update_leaf(&hasher, Location::new(5), element) .unwrap() .merkleize(&base, &hasher); assert_ne!(batch_root(&m, &hasher), base_root); let mut base = base; let batch = base .new_batch() .update_leaf(&hasher, Location::new(5), element) .unwrap() .merkleize(&base, &hasher); base.apply_batch(&batch).unwrap(); assert_eq!(batch_root(&m, &hasher), mem_root(&base, &hasher)); } fn update_out_of_bounds() { let hasher: H = Standard::new(ForwardFold); let base = build_reference::(&hasher, 50); let r1 = base .new_batch() .update_leaf_digest(Location::new(50), Sha256::fill(0xFF)); assert!(matches!(r1, Err(Error::LeafOutOfBounds(_)))); let updates = [(Location::::new(50), Sha256::fill(0xFF))]; let r2 = base.new_batch().update_leaf_batched(&updates); assert!(matches!(r2, Err(Error::LeafOutOfBounds(_)))); } /// A strategy that splits work into up to `parallelism` batches, run on one thread. #[cfg(feature = "std")] fn split_strategy(parallelism: usize) -> Explorer { Explorer::parallel(&mocks::inline(NZUsize!(parallelism))) } /// `add_many` up to `MAX_LEAVES` matches `add`, including the leaf that creates the family's /// tallest node. #[cfg(feature = "std")] fn add_many_at_limit() { let hasher: H = Standard::new(ForwardFold); let tallest = (1..63) .take_while(|&h| F::birth_offset(h) <= *F::MAX_LEAVES) .last() .unwrap(); // Add the leaf that creates the tallest node, then fill up to `MAX_LEAVES` from 7 and // from 300 leaves short. Each batch splits into up to three ranges. for (first, count) in [ (F::birth_offset(tallest) - 1, 1u64), (*F::MAX_LEAVES - 7, 7), (*F::MAX_LEAVES - 300, 300), ] { let first = Location::new(first); // Distinct pins, so reading the wrong one changes the root. let pinned = F::nodes_to_pin(first) .enumerate() .map(|(i, _)| Sha256::fill(i as u8)) .collect(); let base = Mem::::from_components(Vec::new(), first, pinned).unwrap(); let items: Vec = (0..count).collect(); let batch = MerkleizedBatch::from_mem_with_strategy(&base, split_strategy(3)) .new_batch() .add_many(&hasher, &items) .merkleize(&base, &hasher); let mut expected = base.new_batch(); for item in &items { expected = expected.add(&hasher, &item.to_be_bytes()); } let expected = expected.merkleize(&base, &hasher); assert_eq!(batch.data.appended, expected.data.appended, "first={first}"); assert_eq!( batch.root(&hasher, 0).unwrap(), expected.root(&hasher, 0).unwrap(), "first={first}" ); } } /// Repeated `add_many` calls on real worker threads, interleaved with `add` and `update_leaf` /// on a pruned base, match the same operations one leaf at a time in a child of a merkleized /// parent batch. #[cfg(feature = "std")] fn add_many_mixed_operations() { let hasher: H = Standard::new(ForwardFold); for parallelism in [1, 2, 3, 8] { let strategy = Explorer::parallel(&mocks::pooled(NZUsize!(parallelism), NZUsize!(parallelism))); let mut base = build_reference::(&hasher, 63); base.prune_all(); let parent = base .new_batch() .add(&hasher, b"parent") .merkleize(&base, &hasher); let mut actual = MerkleizedBatch::from_mem_with_strategy(&base, strategy) .new_batch() .add(&hasher, b"parent"); let mut expected = parent.new_batch(); for count in [0, 1, 2, 63, 64, 127, 128, 129, 256, 511, 1000] { actual = actual.add(&hasher, b"prefix"); expected = expected.add(&hasher, b"prefix"); let items: Vec = (0..count).collect(); actual = actual.add_many(&hasher, &items); for item in &items { expected = expected.add(&hasher, &item.to_be_bytes()); } // Leaf 63 is new in `actual` but a parent leaf in `expected`. for loc in [63, *actual.leaves() / 2 + 32, *actual.leaves() - 1] { let loc = Location::new(loc); actual = actual.update_leaf(&hasher, loc, b"update").unwrap(); expected = expected.update_leaf(&hasher, loc, b"update").unwrap(); } } let actual = actual.merkleize(&base, &hasher); let expected = expected.merkleize(&base, &hasher); assert_eq!( actual.root(&hasher, 0).unwrap(), expected.root(&hasher, 0).unwrap(), "workers={parallelism}" ); for pos in *parent.size()..*actual.size() { let pos = Position::new(pos); assert_eq!( actual.get_node(pos), expected.get_node(pos), "workers={parallelism} pos={pos}" ); } } } /// `add_many` split across workers matches adding the same items one at a time, on top of /// committed leaves and an unapplied parent batch. #[cfg(feature = "std")] fn add_many_matches_add() { let hasher: H = Standard::new(ForwardFold); for parallelism in [2, 3, 8] { let strategy = split_strategy(parallelism); // Includes sizes one and two short of a power of two. for committed in [0u64, 1, 2, 3, 6, 7, 14, 30, 62, 63, 100] { let base = build_reference::(&hasher, committed); for (parent_count, count) in [ (0, 1), (0, 127), (0, 128), (0, 129), (0, 300), (0, 1000), // Eight workers split this parent into one-leaf ranges. (5, 200), (130, 777), ] { let items: Vec = (0..(parent_count + count) as u64).collect(); let (parent_items, child_items) = items.split_at(parent_count); let parent = MerkleizedBatch::from_mem_with_strategy(&base, strategy.clone()) .new_batch() .add_many(&hasher, parent_items) .merkleize(&base, &hasher); let child = parent .new_batch() .add_many(&hasher, child_items) .merkleize(&base, &hasher); let mut expected_parent = base.new_batch(); for item in parent_items { expected_parent = expected_parent.add(&hasher, &item.to_be_bytes()); } let expected_parent = expected_parent.merkleize(&base, &hasher); let mut expected_child = expected_parent.new_batch(); for item in child_items { expected_child = expected_child.add(&hasher, &item.to_be_bytes()); } let expected_child = expected_child.merkleize(&base, &hasher); let case = format!("workers={parallelism} leaves={committed}+{parent_count}+{count}"); assert_eq!( parent.data.appended, expected_parent.data.appended, "{case}" ); assert_eq!(child.data.appended, expected_child.data.appended, "{case}"); assert_eq!( child.root(&hasher, 0).unwrap(), expected_child.root(&hasher, 0).unwrap(), "{case}" ); } } } } /// Updates to committed and new leaves, then an append, after `add_many` match the same /// operations after `add`. #[cfg(feature = "std")] fn add_many_then_mutate() { let hasher: H = Standard::new(ForwardFold); let base = build_reference::(&hasher, 30); let items: Vec = (0..600).collect(); let mut batch = MerkleizedBatch::from_mem_with_strategy(&base, split_strategy(4)) .new_batch() .add_many(&hasher, &items); let mut expected = base.new_batch(); for item in &items { expected = expected.add(&hasher, &item.to_be_bytes()); } for loc in [3, 47, 629] { batch = batch .update_leaf(&hasher, Location::new(loc), b"updated") .unwrap(); expected = expected .update_leaf(&hasher, Location::new(loc), b"updated") .unwrap(); } let batch = batch.add(&hasher, b"extra").merkleize(&base, &hasher); let expected = expected.add(&hasher, b"extra").merkleize(&base, &hasher); assert_eq!(batch.data.appended, expected.data.appended); assert_eq!(batch.data.overwrites, expected.data.overwrites); assert_eq!( batch.root(&hasher, 0).unwrap(), expected.root(&hasher, 0).unwrap() ); } /// `add_many` on one range hashes every new node whose leaves all lie in the range. #[cfg(feature = "std")] fn add_many_hashes_nodes_in_range() { let hasher: H = Standard::new(ForwardFold); let items: Vec = (0..64).collect(); for committed in 0..70 { let base = build_reference::(&hasher, committed); let batch = MerkleizedBatch::from_mem_with_strategy(&base, split_strategy(1)) .new_batch() .add_many(&hasher, &items); for (pos, digest) in (*base.size()..).zip(&batch.appended) { let pos = Position::::new(pos); if Location::try_from(pos).is_ok() { continue; } let leftmost = *F::leftmost_leaf(pos, F::pos_to_height(pos)); assert_eq!( *digest == D::EMPTY, leftmost < committed, "committed={committed} pos={pos}" ); } } } /// `add_many` past `MAX_LEAVES` panics. #[cfg(feature = "std")] fn add_many_past_limit() { let hasher: H = Standard::new(ForwardFold); let first = Location::new(*F::MAX_LEAVES - 1); let pinned = F::nodes_to_pin(first).map(|_| D::EMPTY).collect(); let base = Mem::::from_components(Vec::new(), first, pinned).unwrap(); let _ = base.new_batch().add_many(&hasher, &[0u64, 1]); } /// Updates are recorded once per leaf, and only from the first leaf `add_many` added, since /// earlier leaves have no ancestors that `add_many` hashed. #[cfg(feature = "std")] fn add_many_records_updates_once() { let hasher: H = Standard::new(ForwardFold); let base = build_reference::(&hasher, 31); // Without `add_many`, no update is recorded. let mut batch = base .new_batch() .add_leaf_digests((0..64u8).map(Sha256::fill)); let updates: Vec = (31..95).collect(); for &loc in &updates { batch = batch .update_leaf_digest(Location::new(loc), Sha256::fill(0xAA)) .unwrap(); } assert!(batch.updated_new_leaves.is_empty()); assert_plan_is_exact(batch, &updates); let items: Vec = (0..100).collect(); let mut batch = MerkleizedBatch::from_mem_with_strategy(&base, split_strategy(3)) .new_batch() .add(&hasher, b"before") // Starts at leaf 32, so its first leaf has ancestors `add_many` hashes. .add_many(&hasher, &items) .add(&hasher, b"after"); let updates = [31, 32, 80, 131, 132, 80]; for &loc in &updates { batch = batch .update_leaf_digest(Location::new(loc), Sha256::fill(0xAA)) .unwrap(); } assert_plan_is_exact(batch, &updates); // Alternating updates to two leaves record each once. let mut batch = MerkleizedBatch::from_mem_with_strategy(&base, split_strategy(2)) .new_batch() .add(&hasher, b"before") .add_many(&hasher, &items[..2]); for i in 0..1000u16 { let loc = Location::new(32 + u64::from(i % 2)); batch = batch .update_leaf_digest(loc, Sha256::fill(i as u8)) .unwrap(); } assert_eq!(batch.updated_new_leaves.len(), 2); assert_eq!(batch.updated_new_leaves.count_ones(), 2); assert_plan_is_exact(batch, &[32, 33]); } /// Compare roots with a tree built only by appending. /// The reference does not walk the ancestors of overwritten leaves. fn updates_match_append_only_rebuild() { let hasher: H = Standard::new(ForwardFold); for initial_len in 1..=9 { let initial: Vec<_> = (0..initial_len).map(|i| Sha256::fill(i as u8)).collect(); let mut base = Mem::::new(); let mut batch = base.new_batch(); for &digest in &initial { batch = batch.add_leaf_digest(digest); } let batch = batch.merkleize(&base, &hasher); base.apply_batch(&batch).unwrap(); for mask in 0..1usize << initial_len { let mut expected = initial.clone(); let mut batch = base.new_batch(); for i in (0..initial_len).rev() { if mask & (1 << i) == 0 { continue; } let loc = Location::new(i as u64); let digest = Sha256::fill(32 + i as u8); batch = batch .update_leaf(&hasher, loc, b"temporary") .unwrap() .update_leaf_digest(loc, Sha256::fill(254)) .unwrap() .update_leaf_batched(&[(loc, Sha256::fill(255)), (loc, digest)]) .unwrap(); expected[i] = digest; if i % 2 == 0 { let appended = Sha256::fill(expected.len() as u8); batch = batch.add_leaf_digest(appended); expected.push(appended); } } // Update an appended leaf, then append again so the peak forest can change. batch = batch.add_leaf_digest(Sha256::fill(254)); batch = batch .update_leaf_digest(Location::new(expected.len() as u64), Sha256::fill(253)) .unwrap(); expected.push(Sha256::fill(253)); batch = batch.add_leaf_digest(Sha256::fill(252)); expected.push(Sha256::fill(252)); // Only overwritten leaves from the parent batch are recorded, once each. assert_eq!(batch.overwrites.len(), mask.count_ones() as usize); let batch = batch.merkleize(&base, &hasher); let empty = Mem::::new(); let mut reference = empty.new_batch(); for digest in expected { reference = reference.add_leaf_digest(digest); } let reference = reference.merkleize(&empty, &hasher); assert_eq!( batch_root(&batch, &hasher), batch_root(&reference, &hasher), "initial_len={initial_len} mask={mask}" ); } } } /// Check that the plan contains exactly the required internal nodes, with no duplicates. fn hash_plan_is_exact() { let hasher: H = Standard::new(ForwardFold); let mut base = Mem::::new(); let mut batch = base.new_batch(); for i in 0..37u8 { batch = batch.add_leaf_digest(Sha256::fill(i)); } base.apply_batch(&batch.merkleize(&base, &hasher)).unwrap(); let all: Vec = (0..37).collect(); let cases: [(&[u64], u8); 5] = [ (&[0, 1, 2], 0), (&[36, 5, 5, 20, 0], 0), (&[3, 36], 1), (&[7, 36], 5), // In MMB, the second append merges two peaks from the parent batch. (&all, 3), ]; for (updates, appends) in cases { let mut batch = base.new_batch(); for &loc in updates { batch = batch .update_leaf_digest(Location::new(loc), Sha256::fill(0xAA)) .unwrap(); } for i in 0..appends { batch = batch.add_leaf_digest(Sha256::fill(0xBB + i)); } assert_plan_is_exact(batch, updates); } } /// Check that after `add_many`, the plan holds the nodes it left unhashed and the ancestors of /// leaves updated before or after it, once each. #[cfg(feature = "std")] fn add_many_hash_plan_is_exact() { let hasher: H = Standard::new(ForwardFold); let base = build_reference::(&hasher, 37); let items: Vec = (0..300).collect(); let cases: [&[u64]; 5] = [ &[], &[40], // A parent leaf, a new leaf updated twice, and the last leaf. &[36, 37, 337, 37], &[0, 100, 101, 200, 336], // Leaves under nodes left for `merkleize` and under nodes `add_many` hashed. &[5, 50, 150, 237, 238, 250, 300], ]; for parallelism in [1, 2, 3, 8] { for updates in cases { // Update a parent leaf first, so `add_many` runs on a batch with overwrites. let mut batch = MerkleizedBatch::from_mem_with_strategy(&base, split_strategy(parallelism)) .new_batch() .update_leaf_digest(Location::new(20), Sha256::fill(0xBB)) .unwrap() .add_many(&hasher, &items[..200]) .add(&hasher, b"between") .add_many(&hasher, &items[200..]); for &loc in updates { batch = batch .update_leaf_digest(Location::new(loc), Sha256::fill(0xAA)) .unwrap(); } let updates: Vec = updates.iter().copied().chain([20]).collect(); assert_plan_is_exact(batch, &updates); } } } /// Check that the plan holds every new internal node not yet hashed and every ancestor of the /// `updates` leaves, once each. fn assert_plan_is_exact( mut batch: UnmerkleizedBatch, updates: &[u64], ) { // New internal nodes hold placeholders until they are hashed. let mut expected = BTreeSet::new(); for (pos, digest) in (*batch.parent.size()..).zip(&batch.appended) { let pos = Position::::new(pos); if Location::try_from(pos).is_err() && *digest == D::EMPTY { expected.insert((F::pos_to_height(pos), pos)); } } for &loc in updates { let loc = Location::new(loc); let mut first_leaf = Location::new(0); for (peak, height) in F::peaks(batch.size()) { let end = first_leaf + (1u64 << height); if loc < end { for (parent, _, h) in path::Iterator::new(peak, height, first_leaf, loc) { expected.insert((h, parent)); } break; } first_leaf = end; } } let levels = batch.hash_plan(); let actual: Vec<_> = levels .iter() .enumerate() .flat_map(|(h, positions)| positions.iter().map(move |&pos| (h as u32, pos))) .collect(); assert_eq!(actual.len(), expected.len(), "updates={updates:?}"); assert_eq!( actual.into_iter().collect::>(), expected, "updates={updates:?}" ); } /// Counts the paired and lone node hashes a merkleization performs. #[derive(Clone)] struct CountingHasher<'a> { inner: H, pairs: &'a AtomicUsize, singles: &'a AtomicUsize, } impl Hasher for CountingHasher<'_> { type Digest = D; fn hash(&self, parts: &[&[u8]]) -> D { >::hash(&self.inner, parts) } fn root_bagging(&self) -> crate::merkle::Bagging { >::root_bagging(&self.inner) } fn node_digest(&self, pos: Position, left: &D, right: &D) -> D { self.singles.fetch_add(1, Ordering::Relaxed); >::node_digest(&self.inner, pos, left, right) } fn node_digest_pair(&self, nodes: [(Position, &D, &D); 2]) -> (D, D) { self.pairs.fetch_add(1, Ordering::Relaxed); >::node_digest_pair(&self.inner, nodes) } } /// Merkleizes `n` appends on `strategy` and returns the root with the number of paired and /// lone node hashes it took. fn merkleize_counting(n: u64, strategy: impl Strategy) -> (D, usize, usize) { let (pairs, singles) = (AtomicUsize::new(0), AtomicUsize::new(0)); let hasher = CountingHasher { inner: Standard::new(ForwardFold), pairs: &pairs, singles: &singles, }; let base = Mem::::new(); let mut batch = base.new_batch_with_strategy(strategy); for i in 0..n { let element = Hasher::::digest(&hasher, &i.to_be_bytes()); batch = batch.add(&hasher, &element); } let root = batch.merkleize(&base, &hasher).root(&hasher, 0).unwrap(); ( root, pairs.load(Ordering::Relaxed), singles.load(Ordering::Relaxed), ) } /// A split level hashes the same node pairs as a serial one. Batches hold whole adjacent /// pairs, so splitting changes neither the root nor the counts of paired and lone node hashes. fn level_batches_keep_pairs() { for n in [1u64, 2, 3, 10, 100, 199] { let serial = merkleize_counting::(n, commonware_parallel::Sequential); explore(|strategy| { let result = merkleize_counting::(n, strategy.clone()); assert_eq!( result, serial, "merkleizing {n} leaves must match the serial root and hash counts" ); }); } } /// `get_node` returns each node from the nearest batch in the chain that wrote it. Each batch /// locates its appended nodes from its own parent size. Nodes that exist only in the committed /// base read as `None`. fn get_node_resolves_from_writing_batch() { // Use distinct digests to identify which batch supplies each node above a committed base. let hasher: H = Standard::new(ForwardFold); let base = build_reference::(&hasher, 10); let (x, y, z, w) = ( Sha256::fill(0xA1), Sha256::fill(0xB2), Sha256::fill(0xC3), Sha256::fill(0xD4), ); let leaf_0 = Position::::try_from(Location::new(0)).unwrap(); let leaf_5 = Position::::try_from(Location::new(5)).unwrap(); let leaf_9 = Position::::try_from(Location::new(9)).unwrap(); let leaf_10 = Position::::try_from(Location::new(10)).unwrap(); let leaf_11 = Position::::try_from(Location::new(11)).unwrap(); // A appends leaf 10 at its parent's size. let a = base .new_batch() .add_leaf_digest(x) .merkleize(&base, &hasher); assert_eq!(leaf_10, a.data.parent_size); assert_eq!(a.get_node(leaf_10), Some(x)); // B overwrites leaf 0 and its ancestors up to the first peak. let b = a .new_batch() .update_leaf_digest(Location::new(0), y) .unwrap() .merkleize(&base, &hasher); let (peak, _) = F::peaks(b.size()).next().unwrap(); let peak_digest = b.data.tip_peaks[0]; // Each descendant of B reads leaf 0 and the peak as B wrote them and leaf 10 as A wrote it. // Base-only leaf 5 and the position at the batch's size read as `None`. let check_ancestor_nodes = |batch: &MerkleizedBatch| { assert_eq!(batch.get_node(leaf_0), Some(y)); assert_eq!(batch.get_node(peak), Some(peak_digest)); assert_eq!(batch.get_node(leaf_10), Some(x)); assert_eq!(batch.get_node(leaf_5), None); assert_eq!(batch.get_node(batch.size()), None); }; // An empty batch holds no nodes of its own, so every read uses retained ancestor records. let empty = b.new_batch().merkleize(&base, &hasher); check_ancestor_nodes(&empty); // C returns its own leaf 9 and leaf 11 and reads older nodes from retained records. let c = empty .new_batch() .update_leaf_digest(Location::new(9), z) .unwrap() .add_leaf_digest(w) .merkleize(&base, &hasher); assert_eq!(leaf_11, c.data.parent_size); assert_eq!(c.get_node(leaf_9), Some(z)); assert_eq!(c.get_node(leaf_11), Some(w)); check_ancestor_nodes(&c); // Overwrite leaf 0 again, then give the last batch no nodes of its own. let d = c .new_batch() .update_leaf_digest(Location::new(0), w) .unwrap() .merkleize(&base, &hasher); let e = d.new_batch().merkleize(&base, &hasher); // Drop every ancestor handle. The empty tip must retain the latest values from the chain. drop((a, b, empty, c, d)); assert_eq!(e.get_node(leaf_0), Some(w)); assert_eq!(e.get_node(leaf_9), Some(z)); assert_eq!(e.get_node(leaf_10), Some(x)); assert_eq!(e.get_node(leaf_11), Some(w)); assert_eq!(e.get_node(leaf_5), None); assert_eq!(e.get_node(e.size()), None); } #[cfg(feature = "std")] #[test] fn mmr_add_many_matches_add() { add_many_matches_add::(); } #[cfg(feature = "std")] #[test] fn mmr_add_many_then_mutate() { add_many_then_mutate::(); } #[cfg(feature = "std")] #[test] fn mmr_add_many_records_updates_once() { add_many_records_updates_once::(); } #[cfg(feature = "std")] #[test] fn mmr_add_many_hashes_nodes_in_range() { add_many_hashes_nodes_in_range::(); } #[cfg(feature = "std")] #[test] #[should_panic(expected = "leaf count overflow")] fn mmr_add_many_past_limit() { add_many_past_limit::(); } #[cfg(feature = "std")] #[test] fn mmr_add_many_at_limit() { add_many_at_limit::(); } #[cfg(feature = "std")] #[test] fn mmr_add_many_mixed_operations() { add_many_mixed_operations::(); } #[test] fn mmr_consistency() { consistency_with_reference::(); } #[test] fn mmr_level_batches_keep_pairs() { level_batches_keep_pairs::(); } #[test] fn mmr_lifecycle() { lifecycle::(); } #[test] fn mmr_apply_batch() { apply_batch::(); } #[test] fn mmr_multiple_forks() { multiple_forks::(); } #[test] fn mmr_fork_of_fork_reads() { fork_of_fork_reads::(); } #[test] fn mmr_update_leaf_digest() { update_leaf_digest_roundtrip::(); } #[test] fn mmr_update_and_add() { update_and_add::(); } #[test] fn mmr_update_leaf_batched() { update_leaf_batched_roundtrip::(); } #[test] fn mmr_proof_verification() { proof_verification::(); } #[test] fn mmr_speculative_proof_uses_base_fallback() { speculative_proof_uses_base_fallback::(); } #[test] fn mmr_empty_batch() { empty_batch::(); } #[test] fn mmr_batch_roundtrip() { batch_roundtrip::(); } #[test] fn mmr_sequential_apply_batch() { sequential_apply_batch::(); } #[test] fn mmr_batch_on_pruned_base() { batch_on_pruned_base::(); } #[test] fn mmr_three_deep_stacking() { three_deep_stacking::(); } #[test] fn mmr_overwrite_collision() { overwrite_collision::(); } #[test] fn mmr_update_appended_leaf() { update_appended_leaf::(); } #[test] fn mmr_update_leaf_element() { update_leaf_element::(); } #[test] fn mmr_update_out_of_bounds() { update_out_of_bounds::(); } #[test] fn mmr_updates_match_append_only_rebuild() { updates_match_append_only_rebuild::(); } #[test] fn mmr_hash_plan_is_exact() { hash_plan_is_exact::(); } #[test] fn mmr_get_node_resolves_from_writing_batch() { get_node_resolves_from_writing_batch::(); } #[cfg(feature = "std")] #[test] fn mmr_add_many_hash_plan_is_exact() { add_many_hash_plan_is_exact::(); } #[cfg(feature = "std")] #[test] fn mmb_add_many_matches_add() { add_many_matches_add::(); } #[cfg(feature = "std")] #[test] fn mmb_add_many_then_mutate() { add_many_then_mutate::(); } #[cfg(feature = "std")] #[test] fn mmb_add_many_records_updates_once() { add_many_records_updates_once::(); } #[cfg(feature = "std")] #[test] fn mmb_add_many_hashes_nodes_in_range() { add_many_hashes_nodes_in_range::(); } #[cfg(feature = "std")] #[test] #[should_panic(expected = "leaf count overflow")] fn mmb_add_many_past_limit() { add_many_past_limit::(); } #[cfg(feature = "std")] #[test] fn mmb_add_many_at_limit() { add_many_at_limit::(); } #[cfg(feature = "std")] #[test] fn mmb_add_many_mixed_operations() { add_many_mixed_operations::(); } #[test] fn mmb_consistency() { consistency_with_reference::(); } #[test] fn mmb_level_batches_keep_pairs() { level_batches_keep_pairs::(); } #[test] fn mmb_lifecycle() { lifecycle::(); } #[test] fn mmb_apply_batch() { apply_batch::(); } #[test] fn mmb_multiple_forks() { multiple_forks::(); } /// A structure rebuilt from the pinned nodes at `n - 1` plus the final element generates a /// verifiable proof for that element against the root at `n`. fn tip_proof_from_pins() { let hasher: H = Standard::new(ForwardFold); for &n in &[1u64, 2, 3, 8, 100, 199] { let reference = build_reference::(&hasher, n); let boundary = Location::new(n - 1); let pin_map = reference.nodes_to_pin(boundary); let pinned_nodes: Vec = F::nodes_to_pin(boundary).map(|pos| pin_map[&pos]).collect(); let element = hasher.digest(&(n - 1).to_be_bytes()); let peaks = F::peaks(F::location_to_position(Location::new(n))).count(); for inactive_peaks in 0..=peaks.min(2) { let root = reference.root(&hasher, inactive_peaks).unwrap(); let mut rebuilt = Mem::::init(crate::merkle::mem::Config { nodes: Vec::new(), pruning_boundary: boundary, pinned_nodes: pinned_nodes.clone(), }) .unwrap(); let batch = rebuilt .new_batch() .add(&hasher, &element) .merkleize(&rebuilt, &hasher); rebuilt.apply_batch(&batch).unwrap(); assert_eq!(rebuilt.root(&hasher, inactive_peaks).unwrap(), root); let proof = rebuilt.proof(&hasher, boundary, inactive_peaks).unwrap(); assert!(proof.verify_range_inclusion(&hasher, boundary, &[element], &root)); } } } #[test] fn mmr_tip_proof_from_pins() { tip_proof_from_pins::(); } #[test] fn mmb_tip_proof_from_pins() { tip_proof_from_pins::(); } #[test] fn mmb_fork_of_fork_reads() { fork_of_fork_reads::(); } #[test] fn mmb_update_leaf_digest() { update_leaf_digest_roundtrip::(); } #[test] fn mmb_update_and_add() { update_and_add::(); } #[test] fn mmb_update_leaf_batched() { update_leaf_batched_roundtrip::(); } #[test] fn mmb_proof_verification() { proof_verification::(); } #[test] fn mmb_speculative_proof_uses_base_fallback() { speculative_proof_uses_base_fallback::(); } #[test] fn mmb_empty_batch() { empty_batch::(); } #[test] fn mmb_batch_roundtrip() { batch_roundtrip::(); } #[test] fn mmb_sequential_apply_batch() { sequential_apply_batch::(); } #[test] fn mmb_batch_on_pruned_base() { batch_on_pruned_base::(); } #[test] fn mmb_three_deep_stacking() { three_deep_stacking::(); } #[test] fn mmb_overwrite_collision() { overwrite_collision::(); } #[test] fn mmb_update_appended_leaf() { update_appended_leaf::(); } #[test] fn mmb_update_leaf_element() { update_leaf_element::(); } #[test] fn mmb_update_out_of_bounds() { update_out_of_bounds::(); } #[test] fn mmb_updates_match_append_only_rebuild() { updates_match_append_only_rebuild::(); } #[test] fn mmb_hash_plan_is_exact() { hash_plan_is_exact::(); } #[test] fn mmb_get_node_resolves_from_writing_batch() { get_node_resolves_from_writing_batch::(); } #[cfg(feature = "std")] #[test] fn mmb_add_many_hash_plan_is_exact() { add_many_hash_plan_is_exact::(); } }