Explaining Ethereum state trie to deepen knowledge of Ethereum blockchain.
This article explains the Ethereum state trie. Ethereum is often called a "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 essential to understand it to deepen your knowledge about Ethereum. I constructed the contents to let you understand step by step logically. When I learned it, it was hard to understand because state trials have several types, and each state's try is closely related to the others. The article helps you to understand state trials profoundly and with ease. The article covers the below topics in order.
Merkle Patricia Trie
World State Trie
Account Storage Trie
Merkle Patricia Trie (Radix trie/Patricia trie/Prefix Tree)
Trie, also called Radix Trie, Patricia Trie, or Prefix Tree, is a data structure that is fastest at finding common prefixes, simple to implement, and requires little memory. As Ethereum uses Merkle Tree to store the hash in blocks efficiently, Trie is used as a core data structure of data storage. Ethereum uses "Modified Merkel Patricia Trie," invented with Merkle Tree, Patricia Tree(Trie), and some improvements. Modified Merkle Patricia Trie is used as the primary data structure in Ethereum, which tries receipt trie, world state trie, account storage trie, and transaction trie.
The above diagram shows the structure of Merkel Patricia Trie. It mainly comprises 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 more depth, please refer to "Modified Merkle Patricia Trie — How Ethereum saves a state."
State Trie Architecture
Before explaining each state trie, let me explain the whole architecture of the 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 the root node(top node of state trie) is stored in the block to spare storage. You can see the whole architecture in the below diagram.
As you can see, three central state tries, world state trie, transaction trie, and receipt trie are stored in the block. And account storage trie(account storage contents Trie) constructs leaf nodes in the 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 the state tree is considered a hard drive. All the information about accounts is stored in the World State trie, and you can retrieve information by querying it. The world state tree is closely related to the account storage tree because it has a "storage root" field that points to the root node in the account storage tree.
Account Storage Trie
Account Storage Trie is where data associated with an account is stored. This is only relevant for Contract Accounts, and all intelligent contract data is persisted in the account storage trie as a mapping between 32-byte integers.
, The 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 the world state trie.
Transaction trie records transactions in Ethereum. Transaction plays a core role in changing states, as Ethereum is a transaction-based "state" machine. Once the transaction is recorded in a block, it cannot be changed permanently to prove the balance of accounts(world state). As the transaction triad is constructed with the Modified Merkel Patricia triad, the only root node is stored in the block. The gray box below 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 was executed successfully. The receipt includes a hash of the transaction, block number, amount of gas used, address of the contract, etc. Here is a field transaction receipt.
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
The article explained the central state tries in Ethereum: Merkle Patricia Trie, world state trie, transaction trie, receipt trie, and account storage trie. As Ethereum is a world "state machine," it has the original mechanism to record and manage states with the trie data structure. World state trie stores account state, which represents how much money the account has. Transaction trie records transactions that 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.