Implement BMPT ParallelStateRoot

[frisitano]

Describe the feature

Currently, we only have a StateRoot implementation for the BMPT (#36). However, in live sync mode, the engine uses a ParallelStateRoot object, which computes all storage tries in parallel. We should create a ParallelStateRoot type for the BMPT, introduce a ParallelStateRootProvider, and include it in the StateCommitment type.

Implementation

First, we should review usage of the ParallelStateRoot object within the reth codebase and implement a DatabaseParallelStateRoot trait in https://github.com/scroll-tech/reth/blob/scroll/crates/trie/db/src/state.rs. We should then introduce a ParallelStateRoot type for scroll in https://github.com/scroll-tech/reth/tree/scroll/crates/scroll/state-commitment/src/root. We should implement DatabaseParallelStateRoot on both the scroll and native ParallelStateRoot types. We should add ParallelStateRoot GAT which is bound by DatabaseParallelStateRoot in StateCommitment. We should update the concrete implementations of StateCommitment for both BMPT and MPT. We should introduce a ParallelStateRootProvider in https://github.com/scroll-tech/reth/tree/scroll/crates/storage/provider. Alternatively, it may be sufficient to add additional methods to StateRootProviderExt if we only use the ParallelStateRoot when calculating the state root for the most recent state (this should be investigated).

reth/crates/storage/storage-api/src/trie.rs

Lines 46 to 78 in b456d1f

	/// A trait that is used to compute the state root of the latest state stored in the database.
	pub trait StateRootProviderExt: Send + Sync {
	/// Returns the state root of the current state.
	fn state_root(&self) -> ProviderResult<B256>;
	/// Returns the state root of the current state and trie updates.
	fn state_root_with_updates(&self) -> ProviderResult<(B256, TrieUpdates)>;
	/// Returns the state root with trie updates associated with the given block range.
	fn incremental_state_root_with_updates(
	&self,
	range: std::ops::RangeInclusive<BlockNumber>,
	) -> ProviderResult<(B256, TrieUpdates)>;
	/// Returns the state root progress.
	fn state_root_with_progress(
	&self,
	state: Option<IntermediateStateRootState>,
	) -> ProviderResult<StateRootProgress>;
	/// Returns the state root of the current state with the provided prefix sets updated.
	fn state_root_from_prefix_sets_with_updates(
	&self,
	prefix_set: TriePrefixSets,
	) -> ProviderResult<(B256, TrieUpdates)>;
	/// Returns the state root of the [`HashedPostState`] on top of the current, the trie updates
	/// and the sorted hashed post state ([`HashedPostStateSorted`]).
	fn state_root_from_state_with_updates_and_sorted_state(
	&self,
	hashed_state: HashedPostState,
	) -> ProviderResult<(B256, TrieUpdates, HashedPostStateSorted)>;
	}

We should replace direct instantiation and invocation of ParallelStateRoot in the codebase with invocations of the provider methods.

Additional context

No response

[frisitano]

@greged93 Can you explore this issue by exploring the open questions raised in the description to see what direction we should take please?

[greged93]

I'm running into some cyclic dep issues which might limit the above design. Currently, I have added a ParallelDatabaseStateRoot trait, which is implemented on reth-trie-parallel::ParallelStateRoot and reth-scroll-state-commitment::ParallelStateRoot. Because the methods incremental_root and incremental_root_with_updates require various trait bounds, these bounds need to be reflected on the ParallelStateRoot GAT of StateCommitment (same requirement as described here). The traits are defined in reth-provider, which means reth-node-types ends up importing reth-provider, which creates the cyclic dep: reth-node-types depends on reth-provider depends on reth-node-types.

I think being able to go around this would require a rework on the ConsistentDbView, replacing the Factory generic into a Tx, but might be missing something.

[frisitano]

Can you provide references to the code where you have implemented this please so I can have some additional context.

[greged93]

here is the branch for it.

• ParallelStateCommit: similar to StateCommitment, I had it extracted here to avoid circular dependencies.
• ParallelDatabaseStateRoot: as described in the issue.
• ParallelDatabaseStateRoot implementation for MPT ParallelStateRoot.
• ParallelDatabaseStateRoot implementation for BMPT ParallelStateRoot.

[frisitano]

Right, I see the issue here. I think given that we will be deprecating the tree I would propose that we implement ParallelStateRoot for BMPT and then feature gate it's instantiation for now. This avoids having to introduce the ParallelStateCommite abstraction and the issues associated with it.

[greged93]

adding this suggestion from @frisitano here in case we want to explore an abstraction in the future:

• Introduce a ConsistentDBViewProviderFactory which we implement on ConsistentDBView.

pub trait ConsistentDBViewProviderFactory {
    type DB: Database;

    type Provider: DBProvider<Tx = <Self::DB as Database>::TX>;

    fn provider_ro(&self) -> ProviderResult<Self::Provider>;
}

• Use this trait as a bound in the various traits implementations:

pub trait ParallelDatabaseStateRoot<F: ConsistentDBViewProviderFactory> {
    /// Returns a parallel state root instance from the [`ConsistentDbView`].
    fn from_consistent_db_view(view: F) -> Result<Self, ProviderError>;
    /// Calculate the state root in parallel.
    fn incremental_root(self, input: TrieInput) -> Result<B256, ParallelStateRootError>;
    /// Calculate the state root in parallel and returns the trie updates.
    fn incremental_root_with_updates(
        self,
        input: TrieInput,
    ) -> Result<(B256, TrieUpdates), ParallelStateRootError>;
}

[frisitano]

closed by #100