Struct ParallelSparseTrie 

pub struct ParallelSparseTrie { /* private fields */ }

A revealed sparse trie with subtries that can be updated in parallel.

Structure

The trie is divided into two tiers for efficient parallel processing:

• Upper subtrie: Contains nodes with paths shorter than UPPER_TRIE_MAX_DEPTH
• Lower subtries: An array of NUM_LOWER_SUBTRIES subtries, each handling nodes with paths of at least UPPER_TRIE_MAX_DEPTH nibbles

Node placement is determined by path depth:

• Paths with < UPPER_TRIE_MAX_DEPTH nibbles go to the upper subtrie
• Paths with >= UPPER_TRIE_MAX_DEPTH nibbles go to lower subtries, indexed by their first UPPER_TRIE_MAX_DEPTH nibbles.

Each lower subtrie tracks its root via the path field, which represents the shortest path in that subtrie. This path will have at least UPPER_TRIE_MAX_DEPTH nibbles, but may be longer when an extension node in the upper trie “reaches into” the lower subtrie. For example, if the upper trie has an extension from 0x1 to 0x12345, then the lower subtrie for prefix 0x12 will have its root at path 0x12345 rather than at 0x12.

Node Revealing

The trie uses lazy loading to efficiently handle large state tries. Nodes can be:

• Blind nodes: Stored as hashes ([SparseNode::Hash]), representing unloaded trie parts
• Revealed nodes: Fully loaded nodes (Branch, Extension, Leaf) with complete structure

Note: An empty trie contains an EmptyRoot node at the root path, rather than no nodes at all. A trie with no nodes is blinded, its root may be EmptyRoot or some other node type.

Revealing is generally done using pre-loaded node data provided to via reveal_nodes. In certain cases, such as edge-cases when updating/removing leaves, nodes are revealed on-demand.

Leaf Operations

Update: When updating a leaf, the new value is stored in the appropriate subtrie’s values map. If the leaf is new, the trie structure is updated by walking to the leaf from the root, creating necessary intermediate branch nodes.

Removal: Leaf removal may require parent node modifications. The algorithm walks up the trie, removing nodes that become empty and converting single-child branches to extensions.

During leaf operations the overall structure of the trie may change, causing nodes to be moved from the upper to lower trie or vice-versa.

The prefix_set is modified during both leaf updates and removals to track changed leaf paths.

Root Hash Calculation

Root hash computation follows a bottom-up approach:

1. Update hashes for all modified lower subtries (can be done in parallel)
2. Update hashes for the upper subtrie (which may reference lower subtrie hashes)
3. Calculate the final root hash from the upper subtrie’s root node

The prefix_set tracks which paths have been modified, enabling incremental updates instead of recalculating the entire trie.

Invariants

• Each leaf entry in the subtries and upper_trie collection must have a corresponding entry in values collection. If the root node is a leaf, it must also have an entry in values.
• All keys in values collection are full leaf paths.

Implementations

impl ParallelSparseTrie

pub fn from_root( root: TrieNode, masks: TrieMasks, retain_updates: bool, ) -> SparseTrieResult<Self>

Creates a new revealed sparse trie from the given root node.

This function initializes the internal structures and then reveals the root. It is a convenient method to create a trie when you already have the root node available.

Arguments

• root - The root node of the trie
• masks - Trie masks for root branch node
• retain_updates - Whether to track updates

Returns

Self if successful, or an error if revealing fails.

Trait Implementations

impl Clone for ParallelSparseTrie

fn clone(&self) -> ParallelSparseTrie

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for ParallelSparseTrie

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for ParallelSparseTrie

fn default() -> Self

Returns the “default value” for a type.

impl PartialEq for ParallelSparseTrie

fn eq(&self, other: &ParallelSparseTrie) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl SparseTrieInterface for ParallelSparseTrie

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

Configures the trie to have the given root node revealed.

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

Configures the trie to retain information about updates.

fn reveal_nodes( &mut self, nodes: Vec<RevealedSparseNode>, ) -> SparseTrieResult<()>

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

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.

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

Removes a leaf node at the specified path.

fn root(&mut self) -> B256

Calculates and returns the root hash of the trie.

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.

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

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

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

Returns a reference to the current sparse trie updates.

fn take_updates(&mut self) -> SparseTrieUpdates

Consumes and returns the currently accumulated trie updates.

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.

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.

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.

fn reserve_nodes(&mut self, _additional: usize)

Reserves capacity for additional trie nodes.

fn reveal_node( &mut self, path: Nibbles, node: TrieNode, masks: TrieMasks, ) -> Result<(), SparseTrieError>

The single-node version of reveal_nodes.

impl Eq for ParallelSparseTrie

impl StructuralPartialEq for ParallelSparseTrie

Layout

Note: Most layout information is completely unstable and may even differ between compilations. The only exception is types with certain repr(...) attributes. Please see the Rust Reference's “Type Layout” chapter for details on type layout guarantees.

Size: 4376 bytes