Struct MerkleTree 

pub struct MerkleTree { /* private fields */ }

In-memory Merkle tree over the responder’s claimed keys.

Leaves are BLAKE3(DOMAIN_LEAF || key || BLAKE3(bytes)), sorted by key. Internal nodes are BLAKE3(DOMAIN_NODE || left || right). When a level has an odd number of nodes, the last node is paired with itself — i.e. node_hash(x, x) — so the level above has ceil(n/2) nodes. This is a standard self-pair construction (NOT node promotion) and deterministically maps any non-empty key set to a single root.

Rebuilt by the responder whenever its key set changes meaningfully (debounced in the integration layer; not this module’s concern).

Implementations

impl MerkleTree

pub fn build(entries: Vec<(XorName, [u8; 32])>) -> Result<Self, CommitmentError>

Build a Merkle tree over (key, bytes_hash) pairs.

entries does not need to be sorted; this method sorts internally so the produced root is deterministic per key set. Duplicate keys are an error: the responder must deduplicate before calling.

Errors

Returns an error if entries is empty (no commitment to make), if entries.len() > MAX_COMMITMENT_KEY_COUNT, or if it contains duplicate keys.

pub fn root(&self) -> [u8; 32]

The Merkle root of this tree.

unwrap-free: build guarantees at least one level with at least one entry, so last().first() is always Some.

pub fn key_count(&self) -> u32

The number of leaves (== claimed keys).

pub fn path_for(&self, key: &XorName) -> Option<Vec<[u8; 32]>>

Inclusion path for key from its leaf up to (but not including) the root.

Returns None if key is not in this tree.

pub fn sorted_keys(&self) -> Vec<XorName>

The keys this tree commits to, in sorted order.

sorted_keys()[i] is the key at leaf index i. Used by the responder’s audit-answer path to recover the leaf_index field for a challenged key in O(log n) via binary search.

pub fn key_at(&self, idx: usize) -> Option<XorName>

The key at sorted leaf index idx, if in range.

Used by the subtree-proof builder to enumerate the keys of a contiguous leaf range without cloning the whole key list.

pub fn key_index(&self, key: &XorName) -> Option<usize>

The sorted leaf index of key, if committed. O(log n) binary search over the (key-sorted) leaves — no separate key list needed, so callers don’t have to keep a duplicate sorted_keys Vec alongside the tree.

pub fn contains_key(&self, key: &XorName) -> bool

Whether key is committed. Allocation-free membership check via the same binary search as Self::key_index.

pub fn node_at(&self, level: usize, index: u64) -> Option<[u8; 32]>

The node hash at (level, index), where level counts up from the leaves (level == 0 is the leaf level, the last level is the root).

Returns None if out of range. Used by the subtree-proof builder to read sibling cut-hashes along the path from the root to the selected subtree; honours the same left-packed self-pair construction as the rest of the tree (a caller asking for an out-of-range sibling on an odd-length level should substitute the node itself).

pub fn levels_count(&self) -> usize

The number of levels in the tree (1 for a single-leaf tree; the last index is the root level). depth == levels_count() - 1.