# Verkle Trie with Bonsai for Besu

## Introduction
Bonsai introduces several enhancements to the Besu client. Unlike other clients that store nodes of the world state by hash, Bonsai stores them by location in the tree. This approach enables natural pruning by replacing old nodes at the same position in the tree with the new ones. Unlike hash-based storage, which only adds new nodes to the database and keeps growing, Bonsai's technique ensures that there is only one version of the state at any given time. Consequently, it does not support managing reorganizations (reorgs) as it only maintains a single state. Bonsai addresses this limitation by introducing "trielogs,"

## Components of Bonsai

### Tree
The tree component of Bonsai stores nodes based on their location in the tree, enabling calculation of the root hash and block validation. By naturally pruning old nodes, the tree keeps the state representation compact and reduces storage requirements.

### Flat Database
The flat database is a storage optimization in Bonsai that stores all leaf nodes in a flat format. This design allows for quick and efficient access to accounts and storages, enhancing the performance of SLOAD operations. Instead of traversing the tree structure, the flat database enables direct access to the required data in a single disk read, resulting in faster query processing.

### Trielogs
Trielogs are a key feature introduced by Bonsai to manage state rollback and rollforward. They represent the differences between two blocks' state by capturing each modification made to an account or storage. Trielogs contain the prior and next versions for each modification, allowing for state changes to be reverted or applied selectively.

### Accumulator

Bonsai introduces an object called the Bonsai accumulator, which accumulates modifications made during a block processing. It stores changes to accounts and storages, and at the end, these modifications are merged and used to update the tree and the flat database. This accumulator system allows for additional optimizations in Besu, such as preloading tree nodes during block processing. For example, if a modification is detected on an account and it needs to be read in the flat db, a background task can be triggered to pre-fetch the path of that account in the tree. This preloading can reduce the time needed to update the tree at the end.

### Snapshot

Bonsai incorporates various optimizations in Besu to support multiple copies of the state at different levels simultaneously. This enables handling scenarios where, for example, an RPC request requires the account state at block 4 and another request needs it at block 5 concurrently. This is achieved through a combination of rocksDB snapshot and in-memory diff layers. However, the details of these optimizations will be complex to describe quickly and are beyond the scope of this document.

### So what is Bonsai ?
In summary, Bonsai brings significant improvements to the Besu client. The tree component optimizes state storage by storing nodes based on their location, facilitating natural pruning and reducing storage requirements. The flat database optimization allows for fast and efficient access to accounts and storages, enhancing the performance of SLOAD operations. Finally, trielogs enable selective state rollback or rollforward by capturing the differences between two blocks. Together, these components provide a more efficient and flexible state management system for Besu.
Bonsai also introduces the Bonsai accumulator in Besu, which accumulates modifications during transactions for efficient updating of the tree and flat database. This system enables optimizations like preloading tree nodes during block processing, reducing read times. Additionally, Bonsai incorporates various state management optimizations to support multiple state copies at different levels simultaneously. These optimizations enhance the performance and flexibility of Besu.

## Integrating Verkle Trie with Bonsai: Proposed Approach

To integrate Verkle Trie with Bonsai effectively, we need to consider the necessary changes and adaptations. I will summarize my perspective on how we should integrate Verkle Trie with Bonsai.

### 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 proposed by Guillaume in his document https://notes.ethereum.org/@parithosh/verkle-transition.
("State expiry is essentially the same concept without the additional transition of n additional leaves per block.")

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. In the proposed approach, I suggest that we always read from the flat database and avoid reading from the Verkle Trie. 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 in progress for this in Besu https://github.com/hyperledger/besu/pull/5319). It's important to note that with this approach, there is no fallback to the PMT. All state retrievals will be done exclusively using the flat database.

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

Therefore, what we need is to have Bonsai as it currently exists, with the ability to freeze the PMT and transition to a Verkle Trie starting from a specific block.

The trielogs will continue to be created as they currently are, and the accumulator will also function as before. A significant part of Bonsai will remain unchanged, and we will only focus on the final part, which is updating the tree.

From that point, we will simply write to the Verkle Trie instead of the PMT.

Additionally, we need to handle the case of a reorg where we may need to revert to a block where the PMT was the only tree.

### Performance Considerations

In terms of performance, I don't believe that disk access will be the major challenge during this transition, even though accessing 10K leaves per block may incur some cost. I think the main performance challenge will be the hash calculation. Verkle Trie hashing is slower than Keccak, so optimizations will be necessary.

We will likely need to explore ways to parallelize the hash calculation for nodes at the same level. Guillaume mentioned that hashing node-by-node is not optimized with this hashing method and that it is preferable to calculate the hash of multiple elements at the same time. Therefore, parallelizing the tree can be highly beneficial. We can also continue preloading the tree paths as we currently do with the PMT. Additionally, leveraging the accumulator to calculate as many hashes as possible in the background before needing (accountHash, slotHash , etc) to update the tree could be advantageous.

### Java Library for Verkle Trie

In terms of code, I suggest that we consider developing a Java library for Verkle Trie integration instead of using Rust. Although Rust performs well, trying to align the Rust library with Besu may require significant effort and potentially lead to time loss.

Instead, we can start a Java library specifically to meet the needs of Besu. Our existing Merkle Tree implementation could serve as an excellent foundation as it aligns well with our requirements.

The Merkle Tree implementation allows us to pass a `NodeLoader` implementation, which provides the logic to fetch nodes from the database without the tree needing to know the specifics of Besu's logic. Besu can simply fetch the required data from the database and provide it to the tree. Developing a separate library also helps reduce the dev cost by not necessitating in-depth knowledge of Besu, and it prepares the groundwork for the modularization effort we want to do in Besu.

Additionally, this library could explore ways to parallelize hash calculations at each level, which would greatly enhance performance.

**Before starting the library, it's essential to clearly define the interfaces and requirements from Besu's perspective. This way, the library implementation won't require significant refactoring of Besu's logic.**

Furthermore, this library should have the capability to interact with Besu for cryptographic calculations by providing the data to be hashed. Besu can then invoke the desired cryptographic method and pass the result back to the Verkle Trie library.

This integration allows the Verkle Trie library to abstract away the specifics of cryptographic operations, ensuring that Besu can utilize its preferred cryptographic functions while providing the necessary data for hashing.

By separating the responsibilities of the Verkle Trie library and Besu, we can achieve a clean and modular integration that promotes maintainability and flexibility.