Skip to main content

State manager

The state manager tracks the network's state in a sparse Merkle tree, which the prover uses to prove each block's state transition. It consists of a Besu execution client running the Shomei plugin (for example, Linea BesuLinea Besu A build of the Besu execution client, extended with Lineth plugins such as the sequencer and tracer that add ZK-rollup functionality. Linea Besu is required to propose blocks and to generate traces, so every sequencer node must run it. Nodes that only import blocks or serve standard Ethereum JSON-RPC can run any Ethereum execution client.), which exposes each block's state changes, and a Shomei node that imports those changes into the tree.

note

"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 sequencerSequencer The set of Linea Besu plugins responsible for ordering, building, and executing blocks in a way that allows the subsequent ZK proof to be made, including the tracer. The sequencer is a plugin set rather than a standalone process; a node that runs it alongside a Maru validator is a sequencer node. produces blocks, the state manager's Besu client 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 coordinatorCoordinator Lineth's coordination module for batching, proof generation, and finality submission. The coordinator monitors block production, manages conflation deadlines, batches blocks, combines batches into blobs, orchestrates execution, compression, and aggregation proofs, and submits proofs and data to the finalization layer. requests the Merkle proof for a batch of blocks and includes it in the execution proof request it sends to the proverProver The Lineth component that generates ZK proofs of state transitions, handling proof-generation requests from the coordinator and Linea Besu. The prover produces three types of proofs (execution, compression, and aggregation) and combines them into a zk-SNARK that the finalization layer verifies. Provers may be scaled horizontally to meet throughput requirements.. The prover returns an execution proof, a zk-SNARKzk-SNARK (Zero-Knowledge Succinct Non-interactive Argument of Knowledge) A type of ZK proof where the prover and verifier don't have to interact. With zk-SNARKs, you can verify 1 transaction or 1 billion transactions in the same amount of time. of the state transition that batch produced. The state manager also serves linea_getProof to callers that need a Merkle proof of an account or a storage slot for a block already finalized on the finalization layerFinalization layer The blockchain where a Lineth deployment submits proofs and state commitments for verification and hard finality. If the finalization layer is Ethereum (an L1), the deployment is an L2. If the finalization layer is Linea (an L2), the deployment is an L3..

Two data structures are involved:

  1. Linea BesuLinea Besu A build of the Besu execution client, extended with Lineth plugins such as the sequencer and tracer that add ZK-rollup functionality. Linea Besu is required to propose blocks and to generate traces, so every sequencer node must run it. Nodes that only import blocks or serve standard Ethereum JSON-RPC can run any Ethereum execution client. records the world state in a Merkle-Patricia Trie and uses that trie to process blocks. This mirrors how Ethereum records world state.
  2. 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's SMT implementation in more detail.

Merkle trees​

The Merkle tree and its variations are commonly used across EVMEthereum Virtual Machine (EVM) A stack-based virtual machine that executes bytecode. In Ethereum, the execution model specifies how the system state is altered given a series of bytecode instructions and a small tuple of environmental data. This is specified through a formal model of a virtual state machine. chains to store and retrieve state data.

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

An internal node is the hash of its children. A leaf is the hash of the data stored there, such as an account. The root is therefore a commitment to the state of every account in the tree.

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 (SMTs)​

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

An SMT is a variation of a standard Merkle tree. It is a complete tree of fixed depth, so every branch from the root to a leaf has the same number of nodes, but a leaf holds data only when that position is in use.

At the beginning of the chain's history, every leaf holds the zero value. A parent whose children are empty holds the default hash for its level. A node with that default hash represents 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, a hash that matches the default value marks an empty subtree, so the nodes further down that subtree can be disregarded. Only the non-empty subtrees need to be tracked.

Lineth's SMT as a cryptographic accumulator​

In this context, Lineth's SMT is a "cryptographic accumulator": a type of cryptographic primitive that encodes a collection of items into short strings and allows read/write operations to be proven. Merkle trees and SMTs are elementary examples of accumulators, but there are others with more powerful capabilities.

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

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

  • hKey and hVal are the hashes of the key and value, respectively, of the stored state entry.
  • prev and next are the pointers storing the position of the leaves whose hKeys are immediately lower and higher, respectively, following lexicographic order.

The head leaf contains the lowest possible hKey, and the tail leaf contains the highest possible hKey, so they sit at the beginning and the end of the linked list. The head and the tail do not encode a stored state entry. Starting from the head, the leaf at head.next is the lowest stored item. Following next from there leads to the next stored item, and so on, until you reach the tail.

The following example illustrates an SMT with two stored leaves between the head and the tail.

Sparse Merkle tree storing a sorted linked listA root hashes an empty subtree and a branch of stored leaves. The leaves sit on one row: head, the lowest stored hKey, the next hKey, and tail. Dashed next arrows run left to right and dashed prev arrows run right to left. Stored leaves carry hVal, the hash of the stored value. Head and tail have none.rootinternal nodeempty subtreeinternal nodeinternal nodeinternal nodehead leaflowest possible hKeyhVal: nonestored leafnext hKey(lowest stored item)hVal: hash of valuestored leafnext hKeyhVal: hash of valuetail leafhighest possible hKeyhVal: nonenextnextnextprevprevprev

Tracking empty leaves​

Empty leaves hold the zero value. Because the hash is deterministic, every empty subtree at a given level has the same hash, so the accumulator can recognize an empty subtree from that hash.

A new stored leaf does not replace an arbitrary empty leaf. It receives the next free tree index. The head and the tail already occupy indexes 0 and 1, so the first stored leaf receives index 2, and each later insertion receives the next index. These indexes are separate from the linked-list order in the diagram above. The order of insertions follows the history of state changes, so the same history rebuilds the same tree, and the proverProver The Lineth component that generates ZK proofs of state transitions, handling proof-generation requests from the coordinator and Linea Besu. The prover produces three types of proofs (execution, compression, and aggregation) and combines them into a zk-SNARK that the finalization layer verifies. Provers may be scaled horizontally to meet throughput requirements. can check the Merkle proof against it.

Applying the accumulator​

Ethereum records two trees in a Merkle-Patricia Trie:

  • World state, which keeps track of accounts.
  • Account storage state, which keeps track of the storage slots 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. It keeps one accumulator for the world state and a separate accumulator for each account's storage. Each one is an extended SMT with its own linked list.

Each accumulator can perform the following operations:

  • Insertion: Add a leaf for a key that was not stored, when its value changes from zero to non-zero.
  • Update: Change the value of a stored leaf, when a non-zero value changes to a different non-zero value.
  • Deletion: Remove a stored leaf, when its value changes from non-zero to zero.
  • Read zero: Prove that a key is not stored. The key was read, not written, and its value is zero.
  • Read non-zero: Prove that a key is stored. The key was read, not written, and its value is non-zero.

World state​

The world state tree maps every account on the blockchain, both contracts and externally owned accounts (EOAs). Each account record includes the root of that account's storage state. While Ethereum records these accounts in a Merkle-Patricia Trie, Lineth's accumulator maps the accounts as a key-value pair, as follows:

  • hKey: Hash(address)
  • hVal: Hash(nonce, balance, storageRoot, codeHash, keccakCodeHash, codeSize)

hVal is the hash of the account record. The fields are:

  • nonce: The account nonce.
  • balance: The account balance.
  • storageRoot: The root of that account's storage accumulator. In contrast, in an Ethereum account, this field is the KeccakKeccak (Pronounced "ketchak") A versatile cryptographic function best known for its uses in hashing. It provides increased levels of security when compared to older hash algorithms. hash of the account's Patricia trie root.
  • codeHash: The hash of the account's code computed with Poseidon2, the hash function the Lineth prover uses. In contrast, in an Ethereum account, this field is the Keccak hash of the code.
  • keccakCodeHash: The Keccak hash of the code, which is the value returned by EXTCODEHASH. The account keeps this hash because the EVM returns it, and keeps codeHash because that is the hash the Lineth prover checks.
  • codeSize: The size of the code in bytes, which is the value returned by the CODESIZE and EXTCODESIZE opcodes.

Account storage state​

Also referred to as the "storage trie," the account storage state records an account's storage slots. This is mainly relevant for contract accounts. For an EOA, the balance and nonce are in the world state account. Its code size is zero, and codeHash and keccakCodeHash are the hashes of empty code.

A storage slot's key and value are each a 32-byte word, the unit the EVM uses for storage. Each word is split into its most significant bytes (MSB), the first 16 bytes; and its least significant bytes (LSB), the last 16 bytes. The accumulator hashes the two halves:

  • hKey: Hash(StorageKeyMSB, StorageKeyLSB)
  • hVal: Hash(StorageValueMSB, StorageValueLSB)

Conclusion​

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

  • A data structure on which you can perform operations.
  • A dataset that you can summarize using a short string (the root hash) at any time.
  • 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 Merkle proof of the resulting transition and include it in the execution proof request. That Merkle proof shows that applying the block's account and storage operations to the previous state root produces the new one.

See also​

Was this page helpful?