The Ethereum World State
In this blog we dive deeper into how "states" work in Ethereum. We're gonna deep dive into how Merkle Patricia Tries work and how tries to store each of the states into the Google's LevelDB key-value store. We're going to further discuss on how Ethereum World State react on execution of transactions.
What is a state in blockchains?
Earlier, when we were at Bitcoin, the state referred to as a global set of Unspent Transaction Outputs (UTXOs). The main purpose to coming forward with UTXOs is to make the reader understand the changes in definition of a "state" in Bitcoin and in Ethereum.
- Firstly, the bitcoin UTXOs cannot be partially spent. If a user wants to spend 0.5 btc, then they have to deliberately self-address (send themselves) 0.5 bitcoin in return change. If that is not sent then they lose 0.5 btc to the bitcoin miner who mines their transaction.
- Secondly, bitcoin does not maintain user-account balances. With bitcoin, a user simply holds private keys to one or more UTXO at any given point of time. Alot of times, digital wallets make it seem it like the bitcoin blockchain automatically stores and organizes account balances, but NO, realistically, account balance is the sum of the spender's UTXOs that are each linked to a private key, and each private key is used separately to sign/spend on each UTXO.
- Thirdly, in a transaction, an entire UTXO is spent (in some cases partially received back changes form a new UTXO)
On the other hand Ethereum behaves way more differently, the Ethereum World State is able to manage much more than just balances. More importantly, data such as account balances are not stored directly in the block headers of Ethereum. Only the root node hashes of the transaction trie, state trie and receipts trie are stored directly in the block headers.
This is a similar illustration:
There are essentially 2 types of data on Ethereum:
- Permanent Data
- Epheremeral Data
Permanent Data
- Permanent Data can be defined as the data in a smart contract transaction. This transaction, once it is fully confirmed, is permanently recorded in the transaction trie, and it is never altered.
Ephemeral Data
- Ephemeral Data can be defined as the data in an ethereum account address, the balance of the Ethereum Account is stored in the State Trie and is altered whenever transactions against the particular account occurs.
Inference
Permanent Data is like mined transactions, and ephemeral data are like account balances, hence, they should be stored separately.
Let's have a proper overview of the Trie data structure.
Trie
Trie is a data-structure that is used for storing a sequence of characters. Ethereum uses something called "Practical algorithm to retrieve information encoded in alphanumeric", aka, Patricia trie.
The main advantage of Patricia Trie is it's tradeoffs for compact storage.
Let us now try to analyze a Basic Trie.
Here \0 means a null pointer, which indicates the end of the trie, much like a terminating identifier.
Rules for adding a word to the trie
To add a new word to the trie we basically traverse the search path for the word we are adding. If we encounter a null pointer, we create a new node. When we have finished adding our word, we create a null pointer (terminator). When we are adding a shorter word which is pre-existing in the trie, we just loop through all the characters pertaining to the existing word and then we add a null pointer \0.
Rules for deleting a word from the trie
We need to first search for a leaf (the very end of a particular branch in the trie), the branch that represents/stores the string. We then start deleting all nodes from the leaf back to the root of the trie. We stop once we hit a node with more than one child.
Rules for searching a word in the trie
We traverse through the entire trie, and search through each of the characters in the string. If we encounter a null pointer before exhausting all of the characters in the string (which we are searching for), then we can conclude that the string is not stored in the trie. On the contrary, if we reach a leaf (the end of a branch) and that path (from the leaf back to the root of the trie) represents our string. We conclude that the string is stored in the trie.
Patricia Trie
Here's an example of the previous trie, modified as a Patricia Trie:
Rules for adding a word to the Patricia Trie
Patricia Trie groups all the common characters in a single branch. Any non common characters will constitute a newer branch in the path. When we want to add a word to the Patricia trie we first traverse all of the characters and then add the null pointer \0 at the end.
I've added GG to the end of the AGNIX string -> AGNIXGG\0, the characters are now read in the following sequence.
Rules for deleting a word in the Patricia Trie
Deletion is similar as to a normal trie, except for when deleting nodes (from the leaf backwards to the root) we must check that all parent nodes must be in possesion of atleast 2 child nodes. It is okay for a single child node to have characters and a null pointer.
Additionally, when deleting from a trie, a path can not be left with a parent nodes which just connects to single child node. If this occurs (when deleting, we need to concatenate the appropriate characters to resolve this).
Here's an example of how it is done, here I want to delete SH\0 from the existing trie, hence on reorganizing the nodes, we see that AGNIX is both common to AGNIX\0 as well as AGNIXGG\0
Rules for searching for a word in the Merkle Patricia Trie
The rules remain the same for searching, as it was for a Standard Patricia Trie.
Similarities between the Trie and the Patricia Trie
| Data Structure | Runtime | Function | Description |
|---|---|---|---|
| Trie & Patricia Trie | O(mN) | Adding an element | m is the length of the string and N is the size of the available alphabet |
| Trie & Patricia Trie | O(mN) | Deleting an element | m is the length of the string and N is the size of the available alphabet |
| Trie & Patricia Trie | O(m) | Searching for an element | m is the length of the string we are searching for |
Differences between the Trie and the Patricia Trie
The main differences between mainly emerge from the storage perspective.
| Data Structure | Space Complexity | Description |
|---|---|---|
| Trie | O(MN) | M is the total length of all strings in the trie, and N is the size of the available alphabet. |
| Patrcia trie | O(nN + M) | n is the number of strings stored in the Patricia Trie, N is the size of the available alphabet and M is the total length of all strings in the trie. |
A closer at these data structures wrt Ethereum's execution architecture
There is one and only global State Trie in Ethereum
And this state trie is constantly updated. This state trie contains a key-value pair for every account which exists on the network. This key is a single 160-bit identifier.
The value in the global state trie is created by encoding the following accounts details of an Ethereum account (using the RLP Encoding Scheme) :
- nonce
- balance
- codeHash
- storageRoot
The state trie's root node is essentially a hash of the entire state trie at the given point in time, in the network. It is used to secure and uniquely identify all the cyrptographically dependent internal state trie data.
Here's an example struct :
Storage Trie
This is where all the smart contract data lives. Each Eth account has it's own storage trie. A 256-bit hash of the storage trie's root node is stored as the storageRoot (the storage trie's root node), in the global state trie of the Ethereum network.
Some definitive examples of tries in Ethereum
The main Ethereum clients use several approaches to perform READ/WRITE operations for their chain. One of the fundamental databases that Ethereum uses is the Level DB by Google (opens in a new tab).
Level DB
LevelDB is an open source Google key-value storage library which provides, amongst other things, forward and backward iterations over data, ordered mapping from string keys to string values, custom comparison functions and automatic compression.
The data is compressed on it's own using “Snappy” an open source Google compression/decompression library. Whilst Snappy does not aim for maximum compression, it aims for very high speeds.
Importance of Google's LevelDB
Leveldb is an important storage and retrieval mechanism which manages the state of the Ethereum network. As such, leveldb is a dependency for the most popular Ethereum clients (nodes) such as go-ethereum and silkwarm.
Last Remarks
There are several different ways in which blockchain data can be represented, infact, with the onset of research around Verkle Tries (opens in a new tab), Ethereum plans to push with another major update called The Verge, where all of Ethereum's data is being planned to be moved from Merkle Patricia Tries to Verkle Tries. However knowing good enough about MPTs and Patricia Trie's will definitely build a good foundational knowledge into the Execution Layer of Ethereum and other EVM compatible chains.