Trait SparseTrie 

pub trait SparseTrie:
    Sized
    + Debug
    + Send
    + Sync {
    // Required methods
    fn set_root(
        &mut self,
        root: TrieNode,
        masks: Option<BranchNodeMasks>,
        retain_updates: bool,
    ) -> SparseTrieResult<()>;
    fn set_updates(&mut self, retain_updates: bool);
    fn reveal_nodes(
        &mut self,
        nodes: &mut [ProofTrieNode],
    ) -> SparseTrieResult<()>;
    fn update_leaf<P: TrieNodeProvider>(
        &mut self,
        full_path: Nibbles,
        value: Vec<u8>,
        provider: P,
    ) -> SparseTrieResult<()>;
    fn remove_leaf<P: TrieNodeProvider>(
        &mut self,
        full_path: &Nibbles,
        provider: P,
    ) -> SparseTrieResult<()>;
    fn root(&mut self) -> B256;
    fn is_root_cached(&self) -> bool;
    fn update_subtrie_hashes(&mut self);
    fn get_leaf_value(&self, full_path: &Nibbles) -> Option<&Vec<u8>>;
    fn find_leaf(
        &self,
        full_path: &Nibbles,
        expected_value: Option<&Vec<u8>>,
    ) -> Result<LeafLookup, LeafLookupError>;
    fn updates_ref(&self) -> Cow<'_, SparseTrieUpdates>;
    fn take_updates(&mut self) -> SparseTrieUpdates;
    fn wipe(&mut self);
    fn clear(&mut self);
    fn shrink_nodes_to(&mut self, size: usize);
    fn shrink_values_to(&mut self, size: usize);
    fn size_hint(&self) -> usize;
    fn prune(&mut self, max_depth: usize) -> usize;
    fn update_leaves(
        &mut self,
        updates: &mut B256Map<LeafUpdate>,
        proof_required_fn: impl FnMut(B256, u8),
    ) -> SparseTrieResult<()>;

    // Provided methods
    fn with_root(
        self,
        root: TrieNode,
        masks: Option<BranchNodeMasks>,
        retain_updates: bool,
    ) -> SparseTrieResult<Self> { ... }
    fn with_updates(self, retain_updates: bool) -> Self { ... }
    fn reserve_nodes(&mut self, _additional: usize) { ... }
    fn reveal_node(
        &mut self,
        path: Nibbles,
        node: TrieNode,
        masks: Option<BranchNodeMasks>,
    ) -> SparseTrieResult<()> { ... }
}

Trait defining common operations for revealed sparse trie implementations.

This trait abstracts over different sparse trie implementations (serial vs parallel) while providing a unified interface for the core trie operations needed by the crate::RevealableSparseTrie enum.

Required Methods

fn set_root( &mut self, root: TrieNode, masks: Option<BranchNodeMasks>, retain_updates: bool, ) -> SparseTrieResult<()>

Configures the trie to have the given root node revealed.

Arguments

• root - The root node to reveal
• masks - Trie masks for root branch node
• retain_updates - Whether to track updates

Returns

Ok(()) if successful, or an error if revealing fails.

Panics

May panic if the trie is not new/cleared, and has already revealed nodes.

fn set_updates(&mut self, retain_updates: bool)

Configures the trie to retain information about updates.

If retain_updates is true, the trie will record branch node updates and deletions. This information can be used to efficiently update an external database.

Arguments

• retain_updates - Whether to track updates

fn reveal_nodes(&mut self, nodes: &mut [ProofTrieNode]) -> SparseTrieResult<()>

Reveals one or more trie nodes if they have not been revealed before.

This function decodes trie nodes and inserts them into the trie structure. It handles different node types (leaf, extension, branch) by appropriately adding them to the trie and recursively revealing their children.

Arguments

• nodes - The nodes to be revealed, each having a path and optional set of branch node masks. The nodes will be unsorted.

Returns

Ok(()) if successful, or an error if any of the nodes was not revealed.

Note

The implementation may modify the input nodes. A common thing to do is std::mem::replace each node with [TrieNode::EmptyRoot] to avoid cloning.

fn update_leaf<P: TrieNodeProvider>( &mut self, full_path: Nibbles, value: Vec<u8>, provider: P, ) -> SparseTrieResult<()>

Updates the value of a leaf node at the specified path.

If the leaf doesn’t exist, it will be created. If it does exist, its value will be updated.

Arguments

• full_path - The full path to the leaf
• value - The new value for the leaf
• provider - The trie provider for resolving missing nodes

Returns

Ok(()) if successful, or an error if the update failed.

fn remove_leaf<P: TrieNodeProvider>( &mut self, full_path: &Nibbles, provider: P, ) -> SparseTrieResult<()>

Removes a leaf node at the specified path.

This will also handle collapsing the trie structure as needed (e.g., removing branch nodes that become unnecessary).

Arguments

• full_path - The full path to the leaf to remove
• provider - The trie node provider for resolving missing nodes

Returns

Ok(()) if successful, or an error if the removal failed.

fn root(&mut self) -> B256

Calculates and returns the root hash of the trie.

This processes any dirty nodes by updating their RLP encodings and returns the root hash.

Returns

The root hash of the trie.

fn is_root_cached(&self) -> bool

Returns true if the root node is cached and does not need any recomputation.

fn update_subtrie_hashes(&mut self)

Recalculates and updates the RLP hashes of subtries deeper than a certain level. The level is defined in the implementation.

The root node is considered to be at level 0. This method is useful for optimizing hash recalculations after localized changes to the trie structure.

fn get_leaf_value(&self, full_path: &Nibbles) -> Option<&Vec<u8>>

Retrieves a reference to the leaf value at the specified path.

Arguments

• full_path - The full path to the leaf value

Returns

A reference to the leaf value stored at the given full path, if it is revealed.

Note: a value can exist in the full trie and this function still returns None because the value has not been revealed.

Hence a None indicates two possibilities:

• The value does not exists in the trie, so it cannot be revealed
• The value has not yet been revealed. In order to determine which is true, one would need an exclusion proof.

fn find_leaf( &self, full_path: &Nibbles, expected_value: Option<&Vec<u8>>, ) -> Result<LeafLookup, LeafLookupError>

Attempts to find a leaf node at the specified path.

This method traverses the trie from the root down to the given path, checking if a leaf exists at that path. It can be used to verify the existence of a leaf or to generate an exclusion proof (proof that a leaf does not exist).

Parameters

• full_path: The path to search for.
• expected_value: Optional expected value. If provided, will verify the leaf value matches.

Returns

• Ok(LeafLookup::Exists) if the leaf exists with the expected value.
• Ok(LeafLookup::NonExistent) if the leaf definitely does not exist (exclusion proof).
• Err(LeafLookupError) if the search encountered a blinded node or found a different value.

fn updates_ref(&self) -> Cow<'_, SparseTrieUpdates>

Returns a reference to the current sparse trie updates.

If no updates have been made/recorded, returns an empty update set.

fn take_updates(&mut self) -> SparseTrieUpdates

Consumes and returns the currently accumulated trie updates.

This is useful when you want to apply the updates to an external database and then start tracking a new set of updates.

Returns

The accumulated updates, or an empty set if updates weren’t being tracked.

fn wipe(&mut self)

Removes all nodes and values from the trie, resetting it to a blank state with only an empty root node. This is used when a storage root is deleted.

This should not be used when intending to reuse the trie for a fresh account/storage root; use clear for that.

Note: All previously tracked changes to the trie are also removed.

fn clear(&mut self)

This clears all data structures in the sparse trie, keeping the backing data structures allocated. A crate::SparseNode::Empty is inserted at the root.

This is useful for reusing the trie without needing to reallocate memory.

fn shrink_nodes_to(&mut self, size: usize)

Shrink the capacity of the sparse trie’s node storage to the given size. This will reduce memory usage if the current capacity is higher than the given size.

fn shrink_values_to(&mut self, size: usize)

Shrink the capacity of the sparse trie’s value storage to the given size. This will reduce memory usage if the current capacity is higher than the given size.

fn size_hint(&self) -> usize

Returns a cheap O(1) size hint for the trie representing the count of revealed (non-Hash) nodes.

This is used as a heuristic for prioritizing which storage tries to keep during pruning. Larger values indicate larger tries that are more valuable to preserve.

fn prune(&mut self, max_depth: usize) -> usize

Replaces nodes beyond max_depth with hash stubs and removes their descendants.

Depth counts nodes traversed (not nibbles), so extension nodes count as 1 depth regardless of key length. max_depth == 0 prunes all children of the root node.

Preconditions

Must be called after root() to ensure all nodes have computed hashes. Calling on a trie without computed hashes will result in no pruning.

Behavior

• Embedded nodes (RLP < 32 bytes) are preserved since they have no hash
• Returns 0 if max_depth exceeds trie depth or trie is empty

Returns

The number of nodes converted to hash stubs.

fn update_leaves( &mut self, updates: &mut B256Map<LeafUpdate>, proof_required_fn: impl FnMut(B256, u8), ) -> SparseTrieResult<()>

Applies leaf updates to the sparse trie.

When a LeafUpdate::Changed is successfully applied, it is removed from the given [B256Map]. If it could not be applied due to blinded nodes, it remains in the map and the callback is invoked with the required proof target.

Once that proof is calculated and revealed via SparseTrie::reveal_nodes, the same updates map can be reused to retry the update.

The callback receives (key, min_len) where key is the full 32-byte hashed key (right-padded with zeros from the blinded path) and min_len is the minimum depth at which proof nodes should be returned.

The callback may be invoked multiple times for the same target across retry loops. Callers should deduplicate if needed.

LeafUpdate::Touched behaves identically except it does not modify the leaf value.

Provided Methods

fn with_root( self, root: TrieNode, masks: Option<BranchNodeMasks>, retain_updates: bool, ) -> SparseTrieResult<Self>

Configures the trie to have the given root node revealed.

See Self::set_root for more details.

fn with_updates(self, retain_updates: bool) -> Self

Configures the trie to retain information about updates.

See Self::set_updates for more details.

fn reserve_nodes(&mut self, _additional: usize)

Reserves capacity for additional trie nodes.

Arguments

• additional - The number of additional trie nodes to reserve capacity for.

fn reveal_node( &mut self, path: Nibbles, node: TrieNode, masks: Option<BranchNodeMasks>, ) -> SparseTrieResult<()>

The single-node version of reveal_nodes.

Returns

Ok(()) if successful, or an error if the node was not revealed.

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl SparseTrie for ParallelSparseTrie