Week 2 of Alchemy University’s Ethereum Bootcamp focuses on blockchain storage. Students were previously introduced to the idea of blockchains as a network of nodes that agree upon a common state of data. Building on this foundation, week 2 begins by highlighting how Bitcoin manages user state. Blockchain data storage may be a difficult concept for complete beginners without exposure to the computer science concept of data structures. Some familiarity with data structures makes it easier to understand the next topic: tree data structures. The concept of trees is then applied to a data structure implemented in blockchains, the Merkle tree. Blockchain storage is not an easy concept to grasp at first glance, but it is fundamental information blockchain developers should know. Knowing how data is stored on a blockchain is foundational towards querying the blockchain and creating efficient smart contracts.
Keeping Track of Blockchain User State
Networks such as Bitcoin and Ethereum have specific models for keeping track of the state of their users. Bitcoin uses the UTXO model while Ethereum and EVM (Ethereum Virtual Machine) chains use the account model. Keeping track of user state is not a simple task because of the decentralized nature of these networks. The networks must achieve consensus and this makes it tricky to deal with user state.
Transactions
User balances begin with the transaction. There are three main components to a transaction: the amount, the payer, and the payee. The payer is the person sending the money. The payee is the person receiving the money. The amount is the amount being sent. There is a fourth component, payer authorization, which is the digital signature. The digital signature verifies the payer and allows the transaction to occur. The purpose of the transaction is to change user state. Changing state is an important dynamic in blockchains, and the tracking of changes to user state is an important concept to understand.
Account based model
One way to track user change is to use the Account based model. An account based model tracks a user’s overall account state, and this is the method Ethereum uses. It does not track what constitutes the actual balance of the account. An example account would look like this: Acct # 1 -> Name: John Doe -> Balance $500.25. A transaction in an account based model is straightforward. Provided the payer has a valid balance, the amount is subtracted from the payer and added to the payee.
UTXO based model
Bitcoin uses the UTXO (Unpent Transaction Outputs) model to keep track of balances. The UTXO model is a stark difference to the straightforward methodology of the account based model. When a payer sends a payee 1 bitcoin, the payee is credited with a UTXO worth 1 bitcoin. Technically, the outcome of this transaction is not that the payee now owns 1 bitcoin. Rather, the payee has a UTXO that allows for the use of 1 bitcoin.
The concept of a UTXO can be hard to understand as it is not as intuitive an account based model. Some key ideas can help conceptualize the idea. It is important to understand that a UTXO is non fungible. When a UTXO is “consumed”, new UTXO are created to represent the change. A UTXO can only be spent once. In the Bitcoin network, each UTXO has an associated script. Scripts are hard programmed and contain conditions required to unlock UTXO for further spending
Account vs UTXO
There are design tradeoffs when choosing how to manage user state. While the account model is straightforward in representing a user balance, the UTXO is more elaborate and abstract. It’s far more intuitive and easier to understand the account based model. On the other hand, the UTXO model offers superior privacy if used with a new address each transaction. Creating a new address in an account based model is not as simple as in a UTXO model. Bitcoin uses a model in which a set of private keys can create a near infinite amount of public keys. On the other hand, creating a new address in the Ethereum network would require a new set of private keys for each new address.
Tree Data Structures
Understanding the fundamental ideas behind a transaction and user balances leads to the concept of data structures. Before diving into data structures used in blockchain, it is important to be familiar with tree data structures. Data structures in general are specialized formats to handle information. In computer science, a node is a basic unit of a data structure, and there are many tree-like data structures.
Simple Tree
Looking at a zoomed in diagram, the top node would be referred to as the parent node, while the two nodes beneath it would be the parent’s children.
Binary Tree
A tree is considered binary when each parent has at most two children. Rules like these are what distinguish different types of trees.
Tree
A tree can be a parent with any number of children. Trees don’t have to have rules that categorize them as binary. While a binary tree enforces the idea a parent must have two children, a tree without any qualifiers doesn’t come with any rules.
Tree vs Linked List
Without some understanding of data structures, it is not as simple to learn data structures related to blockchains. Understanding the linked list data structure helps give context to the data structures used in blockchain technology. Linked lists are also considered tree data structures. What is unique about linked lists is that they are a long chain with a single parent-child relationship. A blockchain is a linked list. It is a continuous chain that has a parent element which is linked to its child element. The child of the parent becomes the parent of its child, and the chain continues to grow. Expanding on this idea brings us to blockchain data storage.
Blockchain Data Storage
Merkle Trees
Blockchains utilize the Merkle Tree. It is a tree data structure that implements hashes. A Merkle tree is a collection of hashes reduced to a single hash.
In the image above, each letter represents a hash. The combined letters represent a concatenated hash. Over a series of steps, the leaf hashes (nodes without children of their own) are combined to create a unique hash. The benefit in this method comes when trying to verify the root hash with a single piece of data.
In a peer-to-peer blockchain system, nodes must validate that they share the same data in blocks. As blocks become increasingly complex with data, a binary Merkle tree is an extremely efficient method to share data.
Merkle Trees in Bitcoin
The Merkle tree design is excellent for data verification. The Bitcoin network uses Merkle trees to store every transaction. All of the transactions in a block are arranged into a Merkle tree. When the block is verified, the hashes in the Merkle tree that represent all the transactions compose the blockchain. Actual transaction data is stored off chain, while the Merkle tree representing transactions makes up the blockchain. This makes data storage on the blockchain extremely efficient. Rather than storing thousands of transactions, a single hash that represents these transactions is stored instead.
Merkle Proofs
The benefit of using the Merkle tree design is the concept of Merkle Proofs. Rather than relying on the Merkle root, individual transactions can be traced back to Merkle branches or leaves. Merkle Proofs are used to prove that a transaction is part of a Merkle root.
The image above highlights the benefit of the Merkle Tree. As established, the Merkle tree allows for storage of large amount of data by using hashes. In the example above, C would represent a transaction. In order to prove this transaction is a part of the Merkle root, it wouldn’t be necessary to start will all the individual transactions. Instead, only the sibling D, branch H(A-B), and branch H(E-H) would be necessary to trace back to the Merkle root. While this may be highly technical information, understanding the blockchain to the level of detail is necessary to becoming an elite smart contract developer.
Patricia Merkle Tries
Because of the differences in transaction management, Ethereum does not completely follow Bitcoin’s use of Merkle Trees. Ethereum keeps track of a larger amount of state data as opposed to Bitcoins model of UTXOs. Ethereum combines the Merkle tree with another data structure which a variant of is a radix trie. The Patricia trie (or tree) combined with a Merkle tree is referred to is a Patricia Merkle Tree.
The trie in radix trie comes from the word retrieval. A radix trie is a tree like data structure that is used to retrieve a string value by traversing down a branch of nodes
A Patricia Trie is a variant of a radix tree that uses key value pairs. It is an acronym that stands for “Practical Algorithm To Retrieve Information Coded In Alphanumeric”. Ethereum uses Patricia Merkle Trees because of it’s nature of having both permanent and ephemeral data. Data relating to transactions are permanent while account based data is always changing.
The Merkle tree is perfect for permanent data while Patricia Tries are perfect for the abundant supply of ephemeral data on the Ethereum blockchain. Patricia Merkle Tries excel at handling Ethereum account state which requires frequent updates.
Ethereum’s use of Patricia Merkle Trees
Ethereum block header
The block header is the hash result of all the data elements contained in a block. It contains a lot of important information which helps identify various aspects of the block. Among other things, the block header contains the state root, transaction root, and receipts root.
State Trie
The state trie acts as a mapping between addresses and account states. It is constantly updated by transaction executions. All the information about accounts are stored in the world state trie. Because all of this information would be too much to store in each block, a root hash is committed instead. Querying this information simply requires an address. The information returned would include data such as the balance associated with the address.
Transactions Trie
The transactions trie records all the transactions in Ethereum. Each transaction includes specific information such as gas price and value. One a block is mined, the transaction trie is never updated.
Transaction receipt trie
Just like the transactions trie, the transaction receipt trie is never updated after a block is mined. The transaction receipt trie records the outcome of each transaction. The information that can be retrieved includes the gas prices of the transactions.
It is important to understand that the raw data of the blockchain is stored elsewhere in places such as archive nodes. The block header contains root hashes of various tries of data. This is an efficient method for data storage. Understanding the concepts of data storage isn’t absolutely necessary to compose a smart contract. However, this deep level of understanding the Ethereum blockchain is foundational for efficient smart contract creation.
Conclusion
Spending time understanding the low level concepts of blockchains allows developers to make more efficient decisions while interacting with the blockchain and creating smart contracts. A developer that understands Ethereum uses an account based as opposed to a UTXO model gives that developer better insight as to how data is stored on the blockchain. Understanding data storage to the level of knowing that Ethereum uses both Merkle trees and Patricia tries is beneficial to a smart contract developer. This knowledge offers clearer ideas of how to query a blockchain. It also leads to smart contract optimization through understanding how to store a minimal amount of data on the blockchain. Smart contracts have become foundational in blockchain development, and understanding blockchain storage is fundamental to the optimization of smart contracts.