feat(trie): create "updatable" trie representation

[rkrasiuk]

Description

Subtrie, sparse trie, multiproof - these are the terms commonly used to describe parts of the trie that have been touched and/or updated following the state transition. Currently, the closest representation for desired feature is the MultiProof struct. However, we do not have a good way to reveal or update the paths inside this struct.

Tasks

Beta Give feedback

1. feat: new reth-trie-sparse crate #11707
   A-trie C-enhancement +2
2. feat(trie): sparse trie #11741
   A-trie C-enhancement +2
3. trie: sparse trie node removal #11743
   A-trie C-enhancement +2
   
4. fix(trie): reveal sparse #11804
   A-trie C-bug +2
   
5. trie: inconsistent SparseTrie::update_rlp_node_level behavior #11805
   A-trie C-debt +2
   
6. perf(trie): parallelize node hash computation in update_rlp_node_level #11806
   A-trie C-perf +2
   
7. Benchmark SparseTrie::update_rlp_node_level #12012
   A-trie C-benchmark +2
   
8. perf(trie): cache prefix set lookups in sparse trie #12088
   A-trie C-perf +2
9. perf(trie): reduce allocations in sparse trie rlp node calculation #12092
   A-trie C-perf +2
10. perf(trie): collect only changed sparse nodes at a depth #12093
    A-trie C-perf +2
11. fix(trie): sparse trie walk should be done in a sorted manner #12087
    A-trie C-bug +2

Requirements

Requirements for the implementation:

• Can be constructed from state proofs
• Must be able to operate only on revealed paths of the main trie
• Must be able to retain TrieUpdates equivalent to StateRoot struct

Considerations

Hash-Based Subtrie

The "updatable" trie can be represented similarly to the state field of the ExecutionWitness.

struct Subtrie {
  root: B256,
  nodes: HashMap<B256, TrieNode>,
}

The update function for the subtrie could be implemented using the following algorithm:

1. Starting from the root node, remove all nodes matching the updated key from self.nodes by their hash (including the previous leaf at key if present) and retain the in-memory as a stack ([root, ..., parent, leaf?])
2. Insert the leaf node with the updated value
3. Pop the ancestor from the stack, update with descendant's node hash and reinsert back to self.nodes one by one

Path-Based Subtrie

This implementation can have inner representation similar to the MultiProof.

struct Subtrie {
  nodes: HashMap<Nibbles, TrieNode>
}

Note

We avoid BTreeMap at all costs due to performance implications as the collection grows large.

Then the update function could be implemented using the following algorithm:

1. Update leaf at key and retain the node hash in memory
2. Search for first ancestor by popping bytes from the key (path)
3. Update all ancestors by traversing the subtrie up to the root node

Relevant Links

struct MultiProof

reth/crates/trie/common/src/proofs.rs

Lines 15 to 24 in f2082e0

	/// The state multiproof of target accounts and multiproofs of their storage tries.
	/// Multiproof is effectively a state subtrie that only contains the nodes
	/// in the paths of target accounts.
	#[derive(Clone, Default, Debug)]
	pub struct MultiProof {
	/// State trie multiproof for requested accounts.
	pub account_subtree: BTreeMap<Nibbles, Bytes>,
	/// Storage trie multiproofs.
	pub storages: HashMap<B256, StorageMultiProof>,
	}

[github-actions]

This issue is stale because it has been open for 21 days with no activity.