Question: Hashed Key Trie Traversal

[frisitano]

Hashed Key Trie Traversal

As part of our ambitions at Scroll to leverage reth as a rollup node we are attempting to implement concrete types for our StateCommitment abstraction #11830. With this effort, we would like to reuse existing reth infrastructure such as HashedCursorFactory. This component is sensitive to ordering which is provided by the key of the account (hashed address) or storage slot (hashed slot index). In Ethereum's trie, the key is converted into nibbles and traversed from the most significant nibble to the least significant nibble. In scroll the key is traversed one bit at a time from the least significant bit to the most significant bit. Due to the difference in the trie traversal method, this impacts the order in which nodes should be provided to the HashBuilder.

A solution to this would be to modify the way that hashed keys are produced. We already have an abstraction to allow for key hashing in #11842. The idea would be to introduce a transformation step after hashing keys in the KeyHasher. This step would reverse the endianness of the keys from big-endian to little-endian and also reverse the bits in each byte. After this transformation, the ordering of the keys will conform with their position in the trie as required by the components of reth. From my initial inspection, the implications of changing the hashed key representation should not impact anything else other than the trie-related components of reth. However, I would ask collaborators/maintainers if they are aware of any issues with this approach and if this is reasonable.

Additional context

No response

[github-actions]

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

[frisitano]

I've implemented this pattern in scroll-tech#36 and have StateRoot components working with scrolls binary Merkle-Patricia trie.