World State Trie

World State Trie, also known as Global State Trie, is one of the most critical data structures in Ethereum. It serves as a snapshot of the current state of the entire network. The trie stores a mapping between account addresses (both EOAs and smart contracts) and their respective account states. These account states carry details such as balance, nonce, contract code, and the storage trie’s hash.

Put simply, the World State Trie is a representation of the current state of all assets and relevant information on the Ethereum network. Each block contains a reference to the current global state, enabling network nodes to verify information and validate transactions.

Transaction Trie

A Transaction Trie is a data structure that stores all the transactions contained within a specific block. Every block has its own distinct Transaction Trie, which serves to store details related to transactions and their sequence within the block.

Transactions are grouped into blocks before being added to the Transaction Trie. This means each block holds a set of transactions, and together they make up a series of blocks known as blockchain. The Transaction Trie is linked to the World State Trie and other tries through block hashes, ensuring data integrity and immutability.

Receipts

Receipts are a data structure in which details regarding the execution of every transaction within a specific block are recorded. Each transaction that takes place in the block produces a receipt with particulars about its execution, including event logs, execution status (successful or not), and other relevant information.

Account Storage Trie

Account Storage Trie is a data structure that stores the data associated with every account on Ethereum. Each account (be it an EOA or a smart contract) has its own distinct storage trie.

This trie is tasked with storing the key values tied to a particular account. Details such as balance, nonce, contract code, and other relevant data are stored within this structure.

It's worth noting that, while the World State Trie's database is immutable and represents the network's global state, the Account Storage Trie's database changes with each block. This shift happens because transaction executions within each block can shift values stored in accounts, reflecting account state changes after each block.

How Transactions Modify State Tries

When a transaction is created and sent on the Ethereum network, it undergoes a complex validation and execution process, affecting the State Tries mentioned earlier.

1. Validation: Initially, the transaction is checked for its validity. This includes checking cryptographic signatures to ensure the transaction originates from the legitimate account holder and that there's enough balance to complete the action.

2. Execution: Following validation, the transaction is executed by miners or validators. Execution entails updating the data in both the Account Storage Trie and the World State Trie. If the transaction involves establishing a new smart contract, that contract’s code is recorded in the Account Storage Trie.

3. Receipts and Transaction Trie Update: Throughout the execution, transaction details are recorded into Receipts, which supply information about the operation executed, event logs, and other relevant data. The transaction is also appended to the block's Transaction Trie, ensuring its proper sequencing.

4. World State Trie Update: Once all transactions in a block have been executed, the World State Trie is updated to represent the network's new global state, considering all the alterations derived from the transactions carried out.

By the end of this process, the block is added to the blockchain, and changes in the State Tries become part of the Ethereum network's immutable record. With this system in place, Ethereum ensures a secure and dependable log of every activity conducted on its platform, allowing for the development of decentralized applications and smart contracts within a transparent, reliable environment.

Fundamental to Ethereum's inner workings is the Modified Merkle Patricia Trie, a data structure that plays a pivotal role in efficiently storing and accessing information on the Ethereum blockchain.

What is a Trie?

A trie is a tree-like data structure that allows for the efficient storage and retrieval of key-value pairs. The name "trie" originates from "retrieval," as it excels in swiftly locating common prefixes in keys. Each node in a trie has multiple branches, and the path taken from the root to a particular leaf node represents the key associated with that node.

The Evolution: Modified Merkle Patricia Trie

In Ethereum, the standard trie has been optimized to meet the distinct requirements of its blockchain. This led to the creation of the "Modified Merkle Patricia Trie" (MPT), which became the foundation for data storage in Ethereum. Several tries in Ethereum, such as the World State Trie, Account State Trie, Receipt Trie, and Transaction Trie, are MPT implementations.

Each of these tries stands as a separate MPT with its own unique prefix, ensuring streamlined organization and access to data related to particular elements of Ethereum’s blockchain.

Anatomy of a Modified Merkle Patricia Trie Tree

To get a clear picture of the MPT's mechanics, we need to closely inspect its structure. Each trie node has a key and its matching value. The key is the node's hash, while the value is the content held within the node. Ethereum’s state, constituted by key-value pairs, is represented as paths within the MPT.

Nibbles serve as the distinguishing unit for key values in the MPT. Each trie node can branch out to as many as 16 offshoots, ensuring a concise representation and efficient memory usage.

There are three types of nodes within the MPT:

1. Branch Nodes: A branch node consists of a 17-element array, which includes one node value and 16 branches. This node type is the primary mechanism for branching and navigating through the trie.

2. Leaf Nodes: A leaf node represents a key-value pair. The value is the MPT node's content, while the key is the node's hash. Leaf nodes store specific key-value data.

3. Extension Nodes: These nodes function as optimized nodes within the MPT. They come into play when a branch node has only one child node. Instead of duplicating the path for every branch, the MPT compresses it into an extension node, housing both the path and the child's hash.

Distinguishing Leaf Nodes from Extension Nodes

Within the MPT, it's vital to tell apart leaf nodes from extension nodes. To achieve this, a prefix is attached to each node's path. This prefix is denoted by a byte and is determined by the number of nibbles in the path.

• For leaf nodes with a path that contains an even number of nibbles, a 0x20 prefix is added.

• If the path has an odd number of nibbles, a 0x3 prefix is added for leaf nodes.

• For extension nodes with a path that contains an even number of nibbles, a 0x00 prefix is added.

• If the path has an odd number of nibbles, a 0x1 prefix is added for extension nodes.

This prefixing mechanism ensures that leaf and extension nodes are efficiently differentiated, making path representation consistent and reliable.

Updating Tries

Trie updates follow certain rules:

• When an EmptyNode is found, it’s replaced with a new LeafNode containing the remaining path of the key.

• When a LeafNode is found, it’s converted into an ExtensionNode, and a new BranchNode is created with two branches, pointing to the ExtensionNode and a new LeafNode.

• When an ExtensionNode is found, it’s converted into a different ExtensionNode with a shorter path, and a new BranchNode is generated, pointing to the new ExtensionNode.

When a trie is generated, the root node points to an EmptyNode.

Adding the First Transaction

When the key-value pair from the first transaction is added, a LeafNode containing the transaction data is generated. At the same time, the root node is updated to point to this LeafNode.

Adding the Second Transaction

When the second transaction is added, the LeafNode at the root will be changed into a BranchNode featuring two branches that point towards the two LeafNodes. The LeafNode on the right contains the remaining nibbles (nibbles being single hexadecimal characters) - 1, as well as the value for the second transaction.

And now the root node is pointing to the new BranchNode.

Adding the Third Transaction

When the third transaction is added, the LeafNode on the left side will transform into a BranchNode, like in the process of adding the second transaction. While the root node itself hasn't changed, the root hash has been modified, as its 0 branch is now pointing to a different node with distinct hashes.

Adding the Fourth Transaction

Adding the last transaction follows a process similar to adding the third transaction.  At this point, we can check whether the root hash matches the transactionRoot included in the block.

Obtaining the Merkle Proof for a Transaction

The Merkle proof for a specific transaction is essentially the path to the LeafNode that stores the transaction value. By checking the proof, you can navigate the trie starting from the root hash, decode the nodes, check the nibbles, and continue this process until you find the node matching the remaining nibbles. If it's found, the associated key value is correct; if not, the Merkle proof is invalid.