EVM state manager

The state manager maintains the network's state in the representation the proving pipeline needs. It consists of a Besu node running the Shomei plugin, and a Shomei node that represents state as a sparse Merkle tree.

info

"State" refers to the data stored on the blockchain at any given point in time. To update state is to update the record of the contents of every account whose contents have changed.

How it works

As the sequencer produces blocks, the Besu node executes them and its Shomei plugin exposes the state changes each block made. The Shomei node imports those changes and applies them to its own tree, tracking the state of user accounts, smart contracts, and balances block by block, and deriving a new state root for each block.

The coordinator requests the Merkle proof for a batch's range of blocks and passes it to the prover with the rest of the proof request, so the resulting proof attests to the state transition that batch produced. The state manager also serves linea_getProof to callers that need an account or storage proof for a block already finalized on the finalization layer.

Two data structures are involved:

Linea Besu records the world state in a Merkle-Patricia Trie, which it uses to process blocks and maintain consensus. This mirrors how consensus and state are managed on Ethereum Mainnet.
The state manager tracks the same state in a variant of a regular Merkle tree called a sparse Merkle tree (SMT), which is more efficient to update and prove.

The rest of this page explains Lineth state management in greater detail, focusing on the SMT configuration that sets Lineth apart.

Merkle trees

The Merkle tree and its variations are commonly used across EVM chains to store and retrieve data about the state of every account on the blockchain.

A Merkle tree is comprised of "nodes" that branch off from each other. At the base is the root, or state root, from which branches stem, and leaves stem from the branches.

Each node is represented by a cryptographic hash which encodes data about its properties; for example, the contents of your account. Each hash encodes the hashes of its child nodes. Taken to its full extent, this cascading system means the root encodes data of the state of every single account on the blockchain.

Cryptographic hashes are deterministic and one-way: the same data always produces the same hash, but you can't recover the data from the hash. Anyone holding the root can check whether a piece of data belongs in the tree by rehashing it along with the sibling hashes on its path to the root, without seeing the rest of the tree.

Sparse Merkle trees

Lineth implements a sparse Merkle tree to track account state and generate and store proofs, which keeps updates and proofs cheap enough to produce for every block.

A sparse Merkle tree is a variation of a standard Merkle tree where not all leaf nodes are filled with data; instead, data is only stored in nodes where it's needed. It is a complete tree of fixed depth, meaning that all branches of the tree have the same length (the same number of leaves).

At the beginning of the chain's history, all leaf nodes are set to a default value, which is typically a hash of a specific value, such as zero. Because all leaf nodes have the same hash value, the parent nodes and higher-level nodes also have the same hash value. A node whose hash is the default value for its level is therefore considered to represent an empty subtree.

In the example above, node A's children are empty, so node A holds the default hash for its level, which marks the whole subtree beneath it as empty. Node B's hash is derived from children that do hold data, so it differs from the default.

With this construction, we do not need to keep track of every individual node's hash. Instead, we can assume hashes that reflect the default value are empty, and the subtree or node that lies further down the chain of nodes can be disregarded; we only need to pay attention to the ones that correspond to non-empty subtrees.

Cryptographic accumulator

In this context, we can consider Lineth's sparse Merkle tree as a type of "cryptographic accumulator." A cryptographic accumulator is a type of cryptographic primitive encoding a collection of items into very short strings and allowing read/write operations to be proven. Merkle trees and sparse Merkle trees are elementary examples of accumulators but there are others with more powerful capabilities.

Lineth's state manager uses an extended version of a sparse Merkle tree that enables it to prove all CRUD (create, read, update, delete) operations for a key-addressed database. As an outline, the construction uses a sparse Merkle tree to store the nodes of a sorted doubly-linked list that encodes all the non-zero items of the state.

Lineth's state manager uses the accumulator to track the network's account trie but also the storage of every contract separately.

The leaves of the tree have the following structure: prev || next || hKey || hVal.

hKey and hVal are the hashes of the key and the value of the stored state entry, respectively. prev and next are pointers storing the position of the leaves whose hKeys are immediately lower and higher, respectively, following lexicographic order. The first two leaves of the SMT are called the head and the tail, and are special in that they do not encode a stored tuple. The head is the lowest possible hKey, while the tail is the highest possible hKey. They are therefore situated at the beginning and the end of the linked list, respectively. Starting from the head, we can access the SMT leaf stored at head.next to get the lowest "actually stored" item. Further incrementing the next value will give us the second-lowest stored item and so on. Repeating the process walks us through the entire set of stored items before we end up at the tail node, marking the final step.

Leaves can also be referred to as storage slots, in that they contain data about the contents of the account in question.

Tracking empty leaves

All leaves in the tree are populated with default/zero values at initialization. Since a deterministic hashing function will ensure that these leaves are always represented by the same hash, empty leaves can be easily recognized by the accumulator.

However, in order for the state manager to update a storage slot with data about an account's contents, it must know which empty leaf to overwrite, and exactly where these empty leaves are. The index assigned to any "new" leaf—an empty leaf being updated so that it stores data—must also be deterministic. This requirement means that anyone can reconstruct the tree by looking at transaction history.

To ensure consistency in the leaves' position, the state manager only ever inserts new leaves to the left of the previous leaf in the tree. If this wasn't the case, and the state manager was able to insert any node in any position, it would be impossible to reconstitute the tree in the exact same configuration, impacting the ability of L1 to verify the Merkle proof provided.

Applying the accumulator

The EVM uses a variant of a Merkle tree known as a Merkle-Patricia Trie to track:

World state, which keeps track of accounts.
Account storage state, which keeps track of the contents of each account.

Lineth adapts this structure. Linea Besu still uses the Merkle-Patricia Trie to execute blocks, but the state manager tracks both trees using the custom cryptographic accumulator described above.

The accumulator can perform the following operations:

Insertion: Add a new storage slot to the tree, triggered by storing a non-zero value in a previously zero-valued slot.
Update: Change the value of an existing storage slot in the tree, triggered by storing a new non-zero value in a previously non-zero slot.
Deletion: Remove a storage slot from the tree, triggered by storing the zero value in a previously non-zero slot.
Read zero: Prove non-membership, triggered when a storage slot has been accessed, but not updated, and its value is zero.
Read non-zero: Prove membership, triggered when a storage slot has been accessed, but not updated and its value is non-zero.

These operations are applied to two trees; world state and account storage state.

World state

The world state tree maps all accounts that exist on the blockchain—contracts and externally-owned accounts (EOAs)—and points towards the account storage state for each. While on Ethereum Mainnet, this data is stored in a standard trie, Lineth uses the accumulator to map accounts as key-value pairs. Otherwise, the implementation is similar to the EVM.

Their structure is as follows:

HKey: Hash(address)
Val: Hash(nonce, balance, storageRoot, codeHash, keccakCodeHash, CodeSize)

Every piece of data fed into the Val (value) hash function must have a finite field interpretation. The data must be formatted this way to enable the prover to access the world state when verifying proofs. Each element is formatted as follows (all elements require one field, other than keccakCodeHash):

nonce: The nonce is written in big-endian form into a byte32. For instance if the nonce is 10, then the nonce should be encoded as 0x000000000000000000000000000000000000000000000000000000000000000a.
balance: Formatted the same as the nonce; big-endian byte32.
storageRoot: The storage root should not be the Keccak of the Patricia trie root as in the EVM, but the "custom Merkle tree" root of the account storage state described in Account storage state.
codeHash: The code hash should not be the Keccak of the code, but the one obtained as described in Account storage state.
Two field elements for keccakCodeHash: One for the 128 most significant bits and one for the 128 least significant bits. The Keccak code hash corresponds exactly to the Keccak hash as specified by the EVM (the output of EXTCODEHASH). We keep the Keccak and the "custom" version for practical reasons.
codeSize: The code size should be the same value as that returned by the CODESIZE/EXTCODESIZE opcodes.

Account storage state

Also referred to as the "storage trie," the account storage state is the database the state manager accesses to retrieve data about the contents of accounts. Account storage is mainly relevant for contract accounts; for EOAs, the data about assets and transactions is stored in the world state Val, and the codeHash and its variants are empty.

Since the main function of account storage is to record contracts in such a way that they can be easily retrieved and processed, it must efficiently encode the contract. It does this using the following format:

HKey: Hash(StorageKeyMSB, StorageKeyLSB)
Val: Hash(StorageValueMSB, StorageValueLSB)

In both cases, the MSB refers to the first 16 bytes of a "word," and LSB the last 16. "Word" in this context refers to the natural unit of data used by the EVM, which is 256-bit (32 byte) chunks.

For example, if the data regarding a contract's code was encoded in a byte32, the standard data type for words on EVM-equivalent environments, it might look like this:

[a0, a1, a2, …., a15, b0, b1, …, b15]

That byte32 would be split into an MSB and LSB like this:

MSB: [0, 0, .., 0, a0, a1, a2, a3, .., a15]
LSB: [0, 0, .., 0, b0, b1, b2, b3, .., b15]

The MSB takes the first 16 bytes, and the LSB the second 16 bytes.

Generating state-root-transition witnesses

The accumulator, built using a sparse Merkle tree, is simultaneously:

A data structure on which we can perform operations.
A dataset that we can summarize using a short string at any time (i.e. the root hash).
A tool that can be used by Lineth to verify that a given operation triggered a transition from hash A to hash B.

Once the accumulator has processed a new block's state changes and updated state accordingly, the coordinator can request the proof of the resulting transition and pass it to the prover. That proof is the prover's witness for the state transition: the evidence that applying the block's operations to the previous state root produces the new one, which the prover uses without re-executing the transactions themselves.

How it works​

Merkle trees​

Sparse Merkle trees​

Cryptographic accumulator​

Tracking empty leaves​

Applying the accumulator​

World state​

Account storage state​

Generating state-root-transition witnesses​

See also​