search

scroll-tech / reth

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

Stack based BMPT Implementation #24

Open frisitano opened 1 month ago

frisitano commented 1 month ago

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

https://github.com/scroll-tech/reth/blob/4b1567a55f9986b2c4fe6d9e47e2ea0a93f10f31/crates/trie/trie/src/trie.rs#L21-L37 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

https://github.com/scroll-tech/reth/blob/4b1567a55f9986b2c4fe6d9e47e2ea0a93f10f31/crates/trie/trie/src/trie.rs#L285-L299 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:

frisitano commented 4 weeks ago

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: https://github.com/paradigmxyz/reth/issues/12163

frisitano commented 4 weeks ago

Relevant: https://github.com/paradigmxyz/reth/issues/12129