A Path-based approach of Nimbus-Eth1 for Kaustinen

Context

Most clients in today's Ethereum L1 eceosystem uses a hash-based storage, which adds new nodes to the database, resulting in a significant growth in the size of the database.

A path-based db will essentially enforce that there is only ONE version of the world state at any given time. Thereby, avoiding reorgs.

Approach

Initial

The database would stories verkle nodes based on the location of the same in the trie. Which basically means, the path associated to it, something we call as stem in the verkle world very frequently.

Advantage

This would enable the database to perform natural pruning by replacing old verkle nodes with the new ones. Thereby, preventing the database to subsequently keep growing.

Although, we're currently doubtful about whether to maintain one world state in the database or not.

Using a FlatDB approach

The flat database approach, stores all the leaf node of the verkle trie in a flat format, thereby, enabling efficient efficient access to accounts/storage/codehash from the unified verkle trie.

Instead of the traversing recursively the trie structure, the flat db direct makes 1 disk read to get direct access to the data. Thereby, reducing cost and enhancing the performance of opcodes like SLOAD in the EVM.

Managing State

Using the flat database, the state can be efficiently managed as well. This can be done by using the state diffs, which represent the differences between 2 blocks' state capturing each modification that were made any segment to the unified verkle trie, be it account, storage or code hash.

KVT Params

So far the plan is to use the basic KVT implementation that is being used in Aristo, the idea is to store in the following way:

    key: Path to Leaf Node
    value: Serialized Verkle Leaf Node

Managing Concurrency

The FlatDB along with an in-memory diff layer will be used to support multiple copies of the same state. This would enable Nimbus-Eth1 to handle multiple scenarios where a RPC call the account state at both block n and block n+1.

This can be achieved by managing the Aristo KVT and the in-memory state diff belonging to nim-eth-verkle.

Further Benefits of FlatDB during MPT->VKT migration

Transition

One of the most talked about approach of transitioning from MPT to VKT is by using the overlay method.

1. We initiate the overlay method by freezing the Merkle Patricia Trie at a given block and we initialize an empty Verkle Trie.

2. We then continue processing the subsequent blocks by the adding only the modifications to the Verkle Trie.

3. We then compute the rootHash and this rootHash is later used to prepare the ExecutionWitness.

   Note that the Execution Witness consists of the following:

   ​​​​    ExecutionWitness:
   ​​​​        StateDiff:
   ​​​​        VerkleProof: