Tracking: StateCommitment abstraction

[frisitano]

Describe the feature

Overview

This issue will be used to plan the implementation of the StateCommitment implementation. The StateCommitment will be used to provide an abstraction over the types associated with the state commitment. This will allow reth to be used with different state representations configured by the user. Initial POC implemented here.

Plan

We will implement the StateCommitment via the following units of work:

• Introduce StateCommitment trait, integrate with NodeTypes and provide MPT implementation. - feat: introduce StateCommitment type #11842
• Introduce StateCommitment types within providers. - Introduce StateCommitment in StateProviders #12602
• Introduce HashedPostStateProvider and refactor methods on HashedPostState and PrefixSetLoader to be generic over the KeyHasher - Introduce HashedPostStateProvider #12607
• Introduce HashedStorageProvider - Introduce HashedStorageProvider #12894
• Introduce KeyHasherProvider - Introduce KeyHasherProvider #12895

Refactor codebase to leverage StateCommitment types for all operations:

• StateRoot - Introduce StateRootProviderExt and Integrate with StateCommitment #12896
• StorageRoot
• StateProof
• StateWitness
• KeyHasher
• ParallelStateRoot

Additional context

#11786

Tasks

Preview Give feedback

1. feat: introduce StateCommitment type #11842
   +0
2. Introduce StateCommitment in StateProviders #12602
   +0
3. Introduce HashedPostStateProvider #12607
   +0
4. Introduce HashedStorageProvider #12894
   A-db A-trie +2
5. Introduce KeyHasherProvider #12895
   S-blocked +1
6. Introduce StateRootProviderExt and Integrate with StateCommitment #12896
   S-blocked +1

[Thegaram]

This could be added to #11241. @mattsse

[Rjected]

Just added to the tracking issue @Thegaram

[github-actions]

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

[frisitano]

We have had a change of strategy at Scroll and we will no longer be using the binary Merkle Patricia trie with Poseidon key hashing. Instead, we will be migrating to native MPT, however, we would still like to land this feature in a more conservative fashion. The primary source of the invasiveness of the proposed change was the modified key hashing scheme. If we instead continue to use the standard keccak key hashing scheme the solution becomes much simpler with no need for HashedPostStateProvider, HashedStorageProvider etc. I propose that the layer at which we introduce the abstraction is the HashBuilder layer, this means we will introduce a trait that looks something like:

pub trait HashBuilderT {
    pub fn with_updates(mut self, retain_updates: bool) -> Self;
    pub fn with_proof_retainer(mut self, retainer: ProofRetainer) -> Self;
    pub fn set_updates(&mut self, retain_updates: bool);
    pub fn split(mut self) -> (Self, HashMap<Nibbles, BranchNodeCompact>);
    pub fn take_proof_nodes(&mut self) -> ProofNodes;
    pub fn updates_len(&self) -> usize;
    pub fn add_leaf(&mut self, key: Nibbles, value: &[u8]);
    pub fn add_branch(&mut self, key: Nibbles, value: B256, stored_in_database: bool);
    pub fn root(&mut self) -> B256;
}

We can then implement this trait on the different hash builder implementations as seen in the mpt and bmpt examples below:

• mtp
• bmpt

We would then make the consumers of the HashBuilder generic over the trait HashBuilderT. For example the StateRoot:

reth/crates/trie/trie/src/trie.rs

Lines 21 to 37 in 3e07d65

	/// `StateRoot` is used to compute the root node of a state trie.
	#[derive(Debug)]
	pub struct StateRoot<T, H> {
	/// The factory for trie cursors.
	pub trie_cursor_factory: T,
	/// The factory for hashed cursors.
	pub hashed_cursor_factory: H,
	/// A set of prefix sets that have changed.
	pub prefix_sets: TriePrefixSets,
	/// Previous intermediate state.
	previous_state: Option<IntermediateStateRootState>,
	/// The number of updates after which the intermediate progress should be returned.
	threshold: u64,
	#[cfg(feature = "metrics")]
	/// State root metrics.
	metrics: StateRootMetrics,
	}

We would use the generic HashBuilderT type when calculating the root:

I think this yields a far less invasive change and still fulfills the function of allowing for generic state commitment. If we have an agreement on this new approach I will back out previous changes related to key hashing and then create a PR for the proposed solution.

[emhane]

thanks a lot for the update @frisitano

@Rjected @mattsse @klkvr @rkrasiuk

[Rjected]

HashBuilder generic over the trait HashBuilderT

I don't agree with the approach to abstract the hash builder. It's abstracting over a concrete implementation detail (the hash builder), rather than providing a good abstraction and API for implementing the state root. For example, we recently reimplemented the state root computation with what we call the sparse trie. The calculation involves:

• spawning a task
• sending it state updates
• waiting on its final result

And this results in a very different internal architecture, and a very different API, than the hash builder. If we were to introduce this abstraction, it would be difficult / impossible to implement the sparse trie. So I would prefer we go a different route, and think about what a state commitment abstraction would need to look like from first principles

[frisitano]

We currently have the following abstraction in place:

reth/crates/trie/db/src/commitment.rs

Lines 10 to 22 in fd0e9dc

	/// The `StateCommitment` trait provides associated types for state commitment operations.
	pub trait StateCommitment: std::fmt::Debug + Send + Sync + Unpin + 'static {
	/// The state root type.
	type StateRoot<'a, TX: DbTx + 'a>: DatabaseStateRoot<'a, TX>;
	/// The storage root type.
	type StorageRoot<'a, TX: DbTx + 'a>: DatabaseStorageRoot<'a, TX>;
	/// The state proof type.
	type StateProof<'a, TX: DbTx + 'a>: DatabaseProof<'a, TX>;
	/// The state witness type.
	type StateWitness<'a, TX: DbTx + 'a>: DatabaseTrieWitness<'a, TX>;
	/// The key hasher type.
	type KeyHasher: KeyHasher;
	}

With a concrete implementation for ethereum mpt:

reth/crates/trie/db/src/commitment.rs

Lines 24 to 39 in fd0e9dc

	/// The state commitment type for Ethereum's Merkle Patricia Trie.
	#[derive(Debug)]
	#[non_exhaustive]
	pub struct MerklePatriciaTrie;
	impl StateCommitment for MerklePatriciaTrie {
	type StateRoot<'a, TX: DbTx + 'a> =
	StateRoot<DatabaseTrieCursorFactory<'a, TX>, DatabaseHashedCursorFactory<'a, TX>>;
	type StorageRoot<'a, TX: DbTx + 'a> =
	StorageRoot<DatabaseTrieCursorFactory<'a, TX>, DatabaseHashedCursorFactory<'a, TX>>;
	type StateProof<'a, TX: DbTx + 'a> =
	Proof<DatabaseTrieCursorFactory<'a, TX>, DatabaseHashedCursorFactory<'a, TX>>;
	type StateWitness<'a, TX: DbTx + 'a> =
	TrieWitness<DatabaseTrieCursorFactory<'a, TX>, DatabaseHashedCursorFactory<'a, TX>>;
	type KeyHasher = KeccakKeyHasher;
	}

I propose that we remove the KeyHasher trait as it will remove some complexity from the codebase. We can then look to introduce a trait for the sparse trees you describe, this would be added as a GAT in StateCommitment trait.

Let me know your thoughts. Would this introduce the correct API?