Ethereum State Trie Architecture Explained

Explaining Ethereum state trie to deepen knowledge of Ethereum blockchain.

Introduction

This article explains the Ethereum state trie. Ethereum is often called “world state machine” and uses original data storage to record states(accounts) and transactions. As state trie is a core database in Ethereum, it is important to understand it to deepen your knowledge about Ethereum. I constructed contents in order to let you understand step by step logically. When I learned it, it was hard to understand deeply because state trie has several types and each state tries are closely related to each other. I hope the article helps you to understand state trie deeply with ease. The article covers below topics in order.

Merkle Patricia Trie
World State Trie
Transaction Trie
Receipt Trie
Account Storage Trie

Merkle Patricia Trie (Radix trie/Patricia trie/Prefix Tree)

Trie, it is also called Radix Trie, Patricia Trie, or Prefix Tree, is a data structure which is fastest at finding common prefixes, simple to implement, and requires small memory. As Ethereum uses Merkle Tree to efficiently store the hash in blocks, Trie is used as a core data structure of data storage. Ethereum uses “Modified Merkel Patricia Trie” which is invented with Merkle Tree, Patricia Tree(Trie), and some improvements. Modified Merkle Patricia Trie is used as the main data structure in Ethereum tries receipt trie, world state trie, account storage trie, and transaction trie.

https://ethereum.stackexchange.com/questions/268/ethereum-block-architecture

Above diagram shows the structure of Merkel Patricia Trie. It is mainly comprised of three types of nodes: extension node, branch node, and leaf node. Each node is decided by the sha3 hash value of its contents and the hash is used as a key. Go-ethereum uses levelDB, and parity uses rocksDB to store states. If you want to know more depth, please refer to “Modified Merkle Patricia Trie — How Ethereum saves a state”.

State Trie Architecture

Before starting to explain each state trie, let me explain the whole architecture of Ethereum state trie. As previously mentioned, state trie has four types: world state trie, transaction trie, transaction receipt trie, and account storage trie. Each state trie is constructed with Merkle Patricia Trie and only root node(top node of state trie) is stored in block to spare storage. You can see whole architecture in the below diagram.

As you can see, three main state tries: world state trie, transaction trie, and receipt trie are stored in the block. And, account storage trie(account storage contents trie) construct leaf node in world state trie.

World State Trie(State Trie, Global State Trie)

World state trie is a mapping between addresses and account states. It can be seen as a global state that is constantly updated by transaction executions. The Ethereum network is a decentralized computer and state trie is considered hard drive. All the information about accounts are stored in world state trie and you can retrieve information by querying it. World state trie is closely related to account storage trie because it has “storageRoot” field that points the root node in account storage trie.

Account Storage Trie

Account Storage Trie is where data associated with an account is stored. This is only relevant for Contract Account and all smart contract data is persisted in the account storage trie as a mapping between 32-bytes integers.

And, account state stores information about accounts such as how much the account has and how many transactions were sent from the account. It has four fields: nonce, balance, storageRoot, and codeHash. It is a leaf node in world state trie.

https://www.lucassaldanha.com/ethereum-yellow-paper-walkthrough-2/

Transaction Trie

Transaction trie records transactions in Ethereum. Transaction plays a core role to change states, as Ethereum is transaction-based “state” machine. Once the transaction is recorded in a block, it cannot be changed permanently as to prove the balance of accounts(world state). As Transaction Trie is constructed with Modified Merkel Patricia Trie, the only root node is stored in the block. Below gray box describes the transaction data field. If you want to know more details, please refer to Ethereum Transaction Structure Explained.

nonce: Transaction nonce is a sequence number of transactions sent from a given address.Gas Price: price you are offering to payGas Limit: Gas Limit is a limit of the amount of ETH the sender is willing to pay for the transactionRecipient: The recipient is the destination of Ethereum address.Value: The value field represents the amount of ether/wei from the sender to the recipient.Data: Data field is for contract related activities such as deployment or execution of a contract.v,r,s: This field is components of an ECDSA digital signature of the originating EOA.

Transaction Receipt Trie(Receipt Trie)

Transaction Receipt Trie records receipts(outcome) of transactions. The receipt is a result of the transaction which is executed successfully. The receipt includes a hash of transaction, block number, amount of gas used, and address of contract, etc. Here is a fields transaction receipt has.

blockHash: String, 32 Bytes - hash of the block where this transaction was in.blockNumber: Number - block number where this transaction was in.transactionHash: String, 32 Bytes - hash of the transaction.transactionIndex: Number - integer of the transactions index position in the block.from: String, 20 Bytes - address of the sender.to: String, 20 Bytes - address of the receiver. null when its a contract creation transaction.cumulativeGasUsed: Number - The total amount of gas used when this transaction was executed in the block.gasUsed: Number - The amount of gas used by this specific transaction alone.contractAddress: String - 20 Bytes - The contract address created, if the transaction was a contract creation, otherwise null.logs: Array - Array of log objects, which this transaction generated.status : String - '0x0' indicates transaction failure , '0x1' indicates transaction succeeded.cite: https://ethereum.stackexchange.com/questions/6531/structure-of-a-transaction-receipt

Conclusion

The article explained the main state tries in Ethereum: Merkle Patricia Trie, world state trie, transaction trie, receipt trie, and account storage trie. As the Ethereum is a world “state machine”, it has the original mechanism to record and manage state with the trie data structure. World state trie stores account state which represents how much money the account has. Transaction trie records transactions which can update world state trie and are immutably stored in the blockchain to prove activity history. Receipt trie represents the outcome of the transaction and can be queried externally. I do hope the article helps to deepen your knowledge about Ethereum.