search

paradigmxyz / reth

Modular, contributor-friendly and blazing-fast implementation of the Ethereum protocol, in Rust
https://reth.rs/
Apache License 2.0
4.03k stars 1.24k forks source link

feat(trie): create "updatable" trie representation #11167

Open rkrasiuk opened 2 months ago

rkrasiuk commented 2 months ago

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
- [ ] https://github.com/paradigmxyz/reth/pull/11707
- [ ] https://github.com/paradigmxyz/reth/pull/11741
- [ ] https://github.com/paradigmxyz/reth/issues/11743
- [ ] https://github.com/paradigmxyz/reth/issues/11804
- [ ] https://github.com/paradigmxyz/reth/issues/11805
- [ ] https://github.com/paradigmxyz/reth/issues/11806
- [ ] https://github.com/paradigmxyz/reth/issues/12012
- [ ] https://github.com/paradigmxyz/reth/pull/12088
- [ ] https://github.com/paradigmxyz/reth/pull/12092
- [ ] https://github.com/paradigmxyz/reth/pull/12093
- [ ] https://github.com/paradigmxyz/reth/pull/12087

Requirements

Requirements for the implementation:

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

https://github.com/paradigmxyz/reth/blob/f2082e04112bfaa9f2c4a6da0ec3f05d9fba84e1/crates/trie/common/src/proofs.rs#L15-L24

github-actions[bot] commented 1 month ago

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