The Solana Virtual Machine (SVM) is becoming widely adopted as the execution layer for various Layer-2 (L2) solutions. However, a key limitation in SVM’s original design is the obscurity of its global state root. This poses significant challenges for rollup systems, where global state roots are critical for ensuring integrity, enabling fraud proofs, and supporting cross-layer operations.

In a rollup, the proposer submits the L2 state root (Merkle root) to the Layer-1 (L1) periodically, establishing checkpoints for the L2 chain. These checkpoints allow inclusion proofs for any account state, enabling stateless execution from one checkpoint to another. Fraud proofs rely on this mechanism, as participants can provide inclusion proofs to verify valid inputs during disputes. Additionally, Merkle trees enhance the security of canonical bridges by allowing users to generate inclusion proofs for withdrawal transactions, ensuring trustless interactions between L2 and L1.

To address these challenges, SOON Network introduces Merkle trees into the SVM execution layer, enabling clients to provide inclusion proofs. SOON integrates with Proof-of-History by using unique entries to embed state roots directly into SVM-based blockchains. With this innovation, SOON stack can support new SVM-based rollups with enhanced security, scalability, and utility.

Solana’s Merklization Problem

Solana has always been engineered with high throughput as the core objective, requiring deliberate design trade-offs — particularly during its early development — to achieve its novel performance. Among these trade-offs, one of the most impactful decisions centered around how and when Solana would merklize its state.

Ultimately this decision created significant challenges for clients in proving global state as well as transaction inclusion and simple payment verification (SPV). The lack of a consistently-hashed state root representing the merklized SVM state poses considerable difficulty for projects such as light clients and rollups.

Let’s take a look at how merklization is done on other chains and then identify the challenges presented by Solana’s protocol architecture.

Merkle Trees on Bitcoin

On Bitcoin, transactions are stored in a block using a Merkle tree, whose root is stored in the block’s header. The Bitcoin protocol will hash a transaction’s inputs and outputs (as well as some other metadata) into a Transaction ID (TxID). In order to prove state on Bitcoin, a user can simply compute a Merkle proof to verify the TxID against the block’s Merkle root.

This verification process also validates state, since the Tx ID is unique to some set of inputs and outputs, both of which reflect changes to address state. Note that Bitcoin transactions can also contain Taproot scripts, which produce transaction outputs that can be checked during verification, often by re-running the script using the transaction’s inputs and the script’s witness data, and validating against its outputs.

Merkle Trees on Ethereum

Similar to Bitcoin, Ethereum stores transactions using a custom data structure (derived from a Merkle tree) called a Merkle Patricia Trie (MPT). This data structure is designed for rapid updates and optimization over large data sets. Naturally, this is because Ethereum has significantly more inputs and outputs to manage than Bitcoin.

The Ethereum Virtual Machine (EVM) acts as a global state machine. The EVM is essentially a gigantic distributed computing environment that supports executable smart contracts, each of which reserves their own address space in the global memory. As a result, clients who wish to verify state on Ethereum must take into account not only the result of a transaction (logs, return code, etc.) but also the changes to the global state as a result of the transaction.

Luckily, the EVM makes clever use of three important trie structures, which store their roots in each block header.

• State trie: A giant key-value store of all the state on Ethereum, including each Ethereum address and the data stored within each account. For smart contracts, these accounts store another trie called a Storage trie, which is yet another key-value map of all the smart contract’s data for its address space.
• Transactions trie: Key-value store of all transactions in a block, where the key is the transaction’s ID, and the value is the transaction data.
• Receipts trie: Trie containing the receipts (status, events) from every transaction in the block, hashed by the index of each transaction in the block. Each receipt contains information about the transaction’s execution, including a transaction post-state hash of the state trie.

Given a transaction, a client can prove its inclusion in a block by evaluating the transactions trie root (like Bitcoin), its result by evaluating the receipt trie, and the changes to global state by evaluating the state trie.

Merkle Trees on Solana

One of the reasons for Solana’s high throughput is the fact that it does not have the multi-tree structure that Ethereum has. Solana leaders do compute Merkle trees when creating blocks, but they are structured differently than those within EVM. Unfortunately, therein lies the problem for SVM-based rollups.

Solana merklizes transactions into what are called entries, and there can be multiple entries per slot; hence, multiple transaction roots per block. Furthermore, Solana computes a Merkle root of account state only once per epoch (about 2.5 days), and this root is not available on the ledger.

In fact, Solana block headers do not contain any Merkle roots at all. Instead, they contain the previous and current blockhash, which is computed through Solana’s Proof of History (PoH) algorithm. PoH requires validators to continuously register “ticks” by recursively hashing block entries, which can be empty or contain batches of transactions. The final tick (hash) of the PoH algorithm is that block’s blockhash.

The problem with Proof of History is that it makes proving state very difficult to do from a blockhash. Solana is designed to stream PoH hashes in order to maintain its concept of elapsed time. The transaction root is only available for a PoH tick that contained an entry with transactions, not the block as a whole, and there is no state root stored in any entry.

However, there exists another hash that clients can use: the bank hash. Sometimes referred to as a slot hash, bank hashes are available in the SlotHashes sysvar account, which can be queried by a client. A bank hash is created for each block (slot) from a handful of inputs:

• The previous bank hash.
• The account state delta hash.
• The count of transaction signatures in the bank, as bytes.
• This bank’s blockhash.
• Only once per epoch, a hash of all accounts in the accounts DB.
• Only when the cluster has restarted, a hash of any hard forks caused by cluster restart.

As one can see, the bank hash is overloaded with several hash inputs, which adds complexity for clients attempting to prove information about transactions or state. Additionally, only a bank hash for a bank that performed an “epoch accounts hash” — the hash of all accounts once per epoch — will have that particular root included in it. Furthermore, the SlotHashes sysvar account is truncated to the last 512 bank hashes.

SOON’s Merklization Solution

SOON network is an SVM L2 on top of Ethereum. While integrating merklization into SOON, we prioritized using proven and well-established solutions for the sake of stability, rather than reinventing the wheel. In deciding which data structure or hashing algorithms to use, we considered their compatibility with the L1 contracts of the Optimism Stack, their ability to integrate seamlessly into the Solana architecture, and whether they can achieve high performance under Solana’s account model.

We found that as the number of accounts increases, the Merkle Patricia Trie (MPT) storage model based on LSM-Tree would produce more disk read/write amplification, resulting in performance losses. Ultimately, we decided to integrate the Erigon MPT by building off of the excellent Rust work done by the rETH team and adding support for the Solana account model.

Architecture

As mentioned previously, SOON’s state trie is an MPT built to support Solana accounts. As such, we have defined an SVM-compatible account type to serve as each leaf node’s data.

struct TrieSolanaAccount {

lamports: u64,

data: Vec<u8>,

executable: bool,

rent_epoch: u64,

owner: Pubkey,

}

To enable the MPT module to subscribe to the latest state of SVM accounts in real time, we introduced an account notifier. During the Banking Stage, the account notifier informs the MPT module of account state changes, and the MPT incrementally updates these changes in the trie structure.

It’s important to note that the MPT module only updates its subtrees during every 50 slots and does not compute the state root at the end of every slot. This approach is taken for two reasons. First, computing the state root for every slot would significantly impact performance. Second, the state root is only needed when the proposer submits an outputRoot to the L1. Therefore, it only needs to be computed periodically, based on the proposer’s submission frequency.

outputRoot = keccak256(version, state_root, withdraw_root, l2_block_hash)

SOON MPT module maintains two types of trie structures simultaneously: the State Trie for global state and the Withdraw Trie for withdrawal transactions. The proposer periodically generates an outputRoot by state root and withdraw root, and submits it to the L1.

Currently, SOON computes the state root and withdrawal root once every 450 slots and appends it to the L2 blockchain. As a result, the consistency of MPT data across other nodes in the network can be ensured. However, the Solana block structure does not include a block header, meaning there is no place to store the state root. Let’s take a closer look at the basic structure of the Solana blockchain and then explore how SOON introduces the UniqueEntry to store the state root.

The Solana blockchain is composed of slots, which are generated by the PoH module. A slot contains multiple entries, with each entry including ticks and transactions. At the network and storage layers, a slot is stored and transmitted using shreds as the smallest unit. Shreds can be converted to and from entries.

[derive(Serialize, Deserialize, Debug, Default, PartialEq, Eq, Clone)]

pub struct Entry {

/// The number of hashes since the previous Entry ID.

pub num_hashes: u64,

/// The SHA-256 hash num_hashes after the previous Entry ID.

pub hash: Hash,

/// An unordered list of transactions that were observed before the Entry ID was

/// generated. They may have been observed before a previous Entry ID but were

/// pushed back into this list to ensure deterministic interpretation of the ledger.

pub transactions: Vec<VersionedTransaction>,

}

We followed the blockchain structure generated by PoH and retained the shred structure, allowing us to reuse Solana’s existing storage layer, network layer, and RPC framework. To store additional data on the L2 blockchain, we introduced the UniqueEntry. This trait allow us to customize the entry payload and define the independent validation rules for the data.

pub const UNIQUE_ENTRY_NUM_HASHES_FLAG: u64 = 0x8000_0000_0000_0000;

/// Unique entry is a special entry type. Which is useful when we need to store some data in

/// blockstore but do not want to verify it.

///

/// The layout of num_hashes is:

/// |…1 bit…|…63 bit…|

/// \ _ _/

/// \ \

/// flag custom field

pub trait UniqueEntry: Sized {

fn encode_to_entries(&self) -> Vec<Entry>;

fn decode_from_entries(

   entries: impl IntoIterator<Item = Entry>,

) -> Result<Self, UniqueEntryError>;

}

pub fn unique_entry(custom_field: u64, hash: Hash) -> Entry {

Entry {

   num_hashes: num_hashes(custom_field),

   hash,

   transactions: vec![],

}

}

pub fn num_hashes(custom_field: u64) -> u64 {

assert!(custom_field < (1 << 63));

UNIQUE_ENTRY_NUM_HASHES_FLAG | custom_field

}

pub fn is_unique(entry: &Entry) -> bool {

entry.num_hashes & UNIQUE_ENTRY_NUM_HASHES_FLAG != 0

}

In a UniqueEntry, num_hashes is used as a bit layout, where the first bit flag is used to distinguish between an Entry and a Unique Entry, and the following 63 bits are used to define the payload type. The hash field serves as the payload, containing the required custom data.

Let’s look at an example of using three unique entries to store the slot hash, state root, and withdraw root.

/// MPT root unique entry.

[derive(Default, Debug, Clone, PartialEq, Eq)]

pub struct MptRoot {

pub slot: Slot,

pub state_root: B256,

pub withdrawal_root: B256,

}

impl UniqueEntry for MptRoot {

fn encode_to_entries(&self) -> Vec<Entry> {

   let slot_entry = unique_entry(0, slot_to_hash(self.slot));
   let state_root_entry = unique_entry(1, self.state_root.0.into());
   let withdrawal_root_entry = unique_entry(2, self.withdrawal_root.0.into());
   vec![slot_entry, state_root_entry, withdrawal_root_entry]

}

fn decode_from_entries(
entries: impl IntoIterator<Item = Entry>,
) -> Result<Self, UniqueEntryError> {

   let mut entries = entries.into_iter();
   let entry = entries.next().ok_or(UniqueEntryError::NoMoreEntries)?;
   let slot = hash_to_slot(entry.hash);
   let entry = entries.next().ok_or(UniqueEntryError::NoMoreEntries)?;
   let state_root = B256::from(entry.hash.to_bytes());
   let entry = entries.next().ok_or(UniqueEntryError::NoMoreEntries)?;
   let withdrawal_root = B256::from(entry.hash.to_bytes());
   Ok(MptRoot {
       slot,
       state_root,
       withdrawal_root,
   })

}
}

Since UniqueEntry redefines the semantics of num_hashes, it cannot be processed during the PoH verification stage. Therefore, at the beginning of the verification process, we first filter out unique entries and direct them to a custom verification flow based on their payload type. The remaining regular entries continue through the original PoH verification process.

Withdrawals and Native Bridging

The native bridge is a crucial piece of infrastructure for Layer 2 solutions, responsible for message transmission between the L1 and the L2. Messages from the L1 to the L2 are called deposit transactions, while messages from L2 to L1 are called withdrawal transactions.

Deposit transactions are typically handled by the derivation pipeline and only require the user to send a single transaction on the L1. Withdrawal transactions, however, are more complex and require the user to send three transactions to complete the process:

1. First, the user must send an initial withdrawal transaction on the L2.
2. Once the outputRoot containing this initial withdrawal transaction is submitted to the L1 by the proposer, the user needs to send an inclusion proof for the withdrawal transaction to the L1. Upon successful verification, the challenge period begins.
3. After the challenge period ends, the user sends a finalize transaction to complete the entire withdrawal process.

The inclusion proof of a withdrawal transaction ensures that the withdrawal occurred on the L2, significantly enhancing the security of the canonical bridge.

In the OP Stack, the hash of the user’s withdrawal transaction is stored in the state variable corresponding to the OptimismPortal contract. The eth_getProof RPC interface is then used to provide users with an inclusion proof for a specific withdrawal transaction.

Unlike EVM, SVM contract data is stored in the data field of accounts, and all types of accounts exist at the same hierarchy level.

SOON has introduced a native bridge program: Bridge1111111111111111111111111111111111111. Whenever a user initiates a withdrawal transaction, the bridge program generates a globally unique index for each withdrawal transaction and uses this index as a seed to create a new Program Derived Account (PDA) to store the corresponding withdrawal transaction.

[derive(Clone, Copy, Debug, PartialEq)]

pub struct WithdrawalTransaction {

/// withdrawal counter

pub nonce: U256,

/// user who wants to withdraw

pub sender: Pubkey,

/// user address in L1

pub target: Address,

/// withdraw amount in lamports

pub value: U256,

/// gas limit in L1

pub gas_limit: U256,

/// withdrawal calldata in L1

pub data: L1WithdrawalCalldata,

}

We defined the WithdrawalTransaction structure to store withdrawal transactions in the data field of the PDA.

This design works similarly to the OP Stack. Once the outputRoot containing the withdrawal transaction is submitted to the L1, the user can submit an inclusion proof for the withdrawal transaction to the L1 to start the challenge period.

Fault Proofs

After the proposer submits the outputRoot to L1, it signifies that the state of L2 has been settled. If a challenger detects that the proposer submitted an incorrect state, they can initiate a challenge to protect the funds in the bridge.

One of the most critical aspects of constructing a fault proof is enabling the blockchain to transition from state S1 to state S2 in a stateless manner. This ensures that the arbitrator contract on L1 can replay the program’s instructions statelessly to perform arbitration.

However, at the beginning of this process, the challenger must prove that all the initial inputs in state S1 are valid. These initial inputs include the participating accounts’ states (e.g., lamports, data, owner, etc.). Unlike the EVM, the SVM naturally separates account state from computation. However, Anza’s SVM API allows accounts to be passed into SVM through a TransactionProcessingCallback trait, as shown below.

pub trait TransactionProcessingCallback {

fn account_matches_owners(&self, account: &Pubkey, owners: &[Pubkey]) -> Option<usize>;

fn get_account_shared_data(&self, pubkey: &Pubkey) -> Option<AccountSharedData>;

fn add_builtin_account(&self, _name: &str, _program_id: &Pubkey) {}

}

Thus, we only need to use the state S1 along with the inclusion proofs of the input accounts to verify the validity of the challenge program’s inputs.

Conclusion

SOON is marking a key milestone for the development of the SVM ecosystem. By integrating merklization, SOON addresses Solana’s lack of a global state root, enabling essential features like inclusion proofs for fault proofs, secure withdrawals, and stateless execution.

Furthermore, SOON’s merklization design within SVM can enable light clients on SVM-based chains, even though Solana itself does not currently support light clients. It’s even possible some of the design could assist with bringing light clients to the main chain as well.

Using Merkle Patricia Tries (MPT) for state management, SOON aligns with Ethereum’s infrastructure, enhancing interoperability and advancing SVM-based L2 solutions. This innovation strengthens the SVM ecosystem by improving security, scalability, and compatibility, while fostering the growth of decentralized applications.

Disclaimer:

1. This article is reprinted from [Medium]. All copyrights belong to the original author [@0xandrewz and @realbuffalojoe]. If there are objections to this reprint, please contact the Gate Learn team, and they will handle it promptly.
2. Liability Disclaimer: The views and opinions expressed in this article are solely those of the author and do not constitute investment advice.
3. The Gate Learn team translated the article into other languages. Copying, distributing, or plagiarizing the translated articles is prohibited unless mentioned.