Stack based BMPT Implementation

[frisitano]

Stack-Based BMPT State Root Calculation

Our ambition is to provide an implementation of scrolls BMPT within reth. We intend to leverage as much pre-existing architecture from scrolls default MPT implementation as possible to minimize the scope of this change. Leveraging the pre-existing reth types will result in a less efficient state size however the simplicity and practicality of this approach outweigh the cons.

HashBuilder

The algorithm that is used to build the state root and associated TrieUpdates is located within the HashBuilder object in alloy-trie.

We need to implement an analogous object with an analogous interface that implements an algorithm that builds a BMPT as defined in the scroll zk_trie spec here. We can name this object BmptHashBuilder or something similar to represent that the object builds a binary Merkle Patricia trie.

StateRoot

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

Lines 21 to 37 in 4b1567a

	/// `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 can leverage the pre-existing StateRoot object which is responsible for iterating over nodes and providing them to the HashBuilder for state root calculation. In the first instance, we should create a code copy of the objects but in the future, we can consider introducing abstractions by the introduction of a generic over StateCommitmentHashBuilder trait defined below on the upstream StateRoot object.

StorageRoot

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

Lines 285 to 299 in 4b1567a

	/// `StorageRoot` is used to compute the root node of an account storage trie.
	#[derive(Debug)]
	pub struct StorageRoot<T, H> {
	/// A reference to the database transaction.
	pub trie_cursor_factory: T,
	/// The factory for hashed cursors.
	pub hashed_cursor_factory: H,
	/// The hashed address of an account.
	pub hashed_address: B256,
	/// The set of storage slot prefixes that have changed.
	pub prefix_set: PrefixSet,
	/// Storage root metrics.
	#[cfg(feature = "metrics")]
	metrics: TrieRootMetrics,
	}

We will take a similar approach as described above with the StateRoot and then in the future look to introduce the StateCommitmentHashBuilder abstraction.

StateCommitmentHashBuilder

The logic for constructing state commitments is encapsulated within a single object. Currently in reth it is in the HashBuilder referenced above. With the introduction of scroll's version of the BmptHashBuilder we should consider introducing a trait for this object such as the following:

pub trait StateCommitmentHashBuilder: Default {
    fn add_branch(&mut self, key: Nibbles, value: B256, children_are_in_trie: bool);
    fn add_leaf(&mut self, key: Nibbles, value: &[u8]);
    fn root(&self) -> B256;
    fn updates_len(&self) -> usize;
    fn split(self) -> (Self, StorageTrieUpdates);
}

This will allow us to make parent objects generic over this trait:

• StateRoot
• StorageRoot
• TrieWitness
• Proof

[frisitano]

Reth uses the ordering of hashed keys to perform ordered lookups of trie branches and leaves from the database. These hashed keys are the output of the keccak256 hash function and are big-endian. This works for the native Ethereum MPT as the tree is traversed from the most significant bit to the least significant bit in nibble increments. In scroll the tree is traversed starting from the LSB to the MSB and as such the ordering of leaves does not match the ordering of the big-endian representation of the hashed keys. This impacts trie branch/leaves lookup and the stack-based algorithms that process this data.

One solution to this issue would be to transform the keys after hashing with Poseidon. We would need to reverse the endianness from big-endian to little-endian and also reverse the bits within the bytes. I would like to ask the Reth maintainers to understand if there could be any implications for this change, but my initial review suggests it should be fine as hashed keys/storage slots are internal constructs and are not publicly exposed.

Opened issue here: paradigmxyz#12163

[frisitano]

Relevant: paradigmxyz#12129