Integrating Verkle Trie with Bonsai: Proposed Approach

In this guide, I'll describe the process of leveraging the flat database to limit read access to only one for SLOAD during the transition using the overlay method.

Transitioning from PMT to Verkle Trie

To facilitate the transition from Patricia Merkle Trie (PMT) to Verkle Trie, one approach that I consider most suitable and advantageous is the overlay method (https://notes.ethereum.org/@parithosh/verkle-transition).

The overlay method starts by freezing the PMT at a specific block and initializing an empty Verkle Trie. We continue processing new blocks by adding modifications to the Verkle Trie instead of the PMT. The root hash of the Verkle Trie is then used as the root hash for block validation. Additionally, for each block, a range of leaf nodes (perhaps 10K leaves per block) is transitioned from the PMT to the Verkle Trie. The exact number can be determined later to balance transition time and client loss. It should be noted that after a certain period of time, we can safely delete the PMT trie from the database, which will help reclaim storage space. Once the risk of reorg has passed.

During block processing, we need to read the account and storage state from the database. The initial idea for the transition is that when we want to read an account or a slot, we first try to read it in the Verkle tree. If we can't find it there, we try to read it in the Frozen PMT or Frozen Flat DB. This leads to a change in gas costs as we may have an additional database read (fallback mechanism).

In the proposed approach, I suggest that we have only one flat db for Verkle and PMT and we always read from this flat database. This will improve the performance of SLOAD operations by reducing unnecessary disk access. This approach is similar to what we currently do with the PMT and the flat database. We read from the flat database for SLOAD operations (a pull request is merged for this in Besu https://github.com/hyperledger/besu/pull/5319). It's important to note that with this approach, there is no fallback mechanism. All state retrievals will be done exclusively using one access to the flat database.

This means that we only freeze the PMT (trie) and continue updating the flat database. We can do this because we can rollback the flat database using our trielogs in case of reorgs.

To facilitate this, we should introduce a marker for accounts that are in Verkle but no longer in PMT. This will help identify the leaves to be transferred from PMT to Verkle. Only leaves without this marker will be transferred.

When we update a leaf, it will be also updated in the flat DB with this new marker (we could consider adding versioning for the leaves)

To enable this, we also need to maintain Keccak as the key hashing mechanism. This means that the SLOAD will always read the keys via Keccak, ensuring that the keys in the flat DB will always be hashed by Keccak.