The Evolution of Blockchain State Architectures — Karnot
https://mirror.xyz/karnot.eth/KU9VQAEm-WlLpAtjg8jkqtBauq7yXu4stdVil7Sp47M
Special thanks to the Kasar Labs team for discussion and review.
Blockchains represent a significant advancement in decentralised, permissionless databases, built to be trustless and scalable. Ethereum, as a prime example is a global database operating with over six thousand nodes that constantly read and write to the blockchain. A distributed system of such proportions demands a state architecture that meets three key criteria: it must be immutably verifiable, enable lightning-fast lookups, and scale to handle tens of thousands of writes.
Ethereum achieves this by maintaining a "world state" - a global state that is constantly updated by executing transactions. This world state stores critical information about Ethereum accounts, such as balances and smart contract states. Each interaction, whether it's a transfer, NFT mint, or memecoin snipe involves multiple reads and writes to this state. During these interactions, the system accesses the world state and executes state transformation functions to update the state accordingly.
In this article, we'll discuss the evolution of Ethereum's state architecture, its future, and how we've reimagined state at Madara. We'll explore Madara's Bonsai architecture towards the end, but we recommend reading the preceding sections to establish a solid foundation.
The blockchain “verifiability problem” arises from the need for an architecture that can support thousands of reads and writes, while remaining verifiable even on compute-light machines (light clients). While centralised databases such as SQL are efficient, scalable and battle-tested, they lack the trustless nature that blockchains require.
The primary challenge lies in achieving a balance between performance and verifiability. Blockchains require nodes to validate and store each transaction. Consequently, blockchain state architecture must be designed to be lightweight and easy to verify.
As the blockchain state expands, block verification requires more resources.
As the blockchain state expands, block verification requires more resources, which state architectures like MPTs address. Here we discuss state architectures implemented by Ethereum and Starknet
In the following examples, we will use the words "bin," "binary," "tree," "trie," "move," and "movie" to illustrate the concept of tries. Additionally, we will present the key-value pairs (bin,10), (binary,8), (move,30), (movie,55), (tree,20), (trie,48) to demonstrate Merkle trees, Merkle Patricia trees, and Bonsai trees.
A trie is an ordered tree data structure used to represent a set of strings over an alphabet set. A trie's architecture allows for the efficient storage of words with common prefixes. This design allows optimised checks on the presence of a word in a dictionary.
**Nodes**: Each node in a trie represents a prefix of the strings stored. A trie node can have multiple children, each corresponding to a different character.
**Character Mapping**: Each node contains a mapping from characters to child nodes.
In the adjoining diagram, there are two types of nodes:
**Leaf Nodes (Green Nodes):**
1.
Signify the end of a branch in a Trie
2.
Have a leaf flag to indicate whether the node is a complete word or a prefix.
3.
“tree” and “trie” are examples of leaf nodes that signal complete words in the dictionary.
**Intermediate Nodes (Yellow Nodes):**
1.
Have a character mapping to one or more child nodes
2.
“move” represents an intermediate node, a node that maps two child nodes to its existing prefix.
3.
“bin” behaves as a terminal node, representing a full word that exists in the dictionary while also having child nodes of its own.
A Trie’s unique design enables straightforward reads of leaf nodes by encoding the string as the path to the leaf node that stores the string. Hence the time complexity for insertion and search is proportional to the length of the string (O(m)), where m is the length of the string. This is because each operation involves traversing ALL the characters.
Similarly, tries demand a storage complexity of O(n), where n is the total size of all strings stored. However, the height of the trie depends only on the length of the longest string.
A trie’s structure allows efficient retrieval of leaf values, as the string is sufficient to determine its position within the Trie. As the Trie expands, this encoding allows for optimised lookup times; however a trie’s naive limitations can also be identified.
For sparse key sets, a trie may run unnecessarily deep, with many nodes having only one child. Long 'single-child' chains increase read and write times due to the need to traverse the entire tree depth.
PATRICIA (Practical Algorithm To Retrieve Information Coded In Alphanumeric) Tries are a specialised type of trie designed to optimise space usage by collapsing chains of nodes with only one child.
**Nodes and Edges**: Each node in a PATRICIA Trie represents a common prefix of the strings stored in the tree. Unlike a standard trie, where each edge corresponds to a single character, **edges in a PATRICIA tree can represent multiple characters**, leading to a more compact structure.
**Merging Nodes**: In a PATRICIA tree, any node that has only one child is **merged with its parent**. This merging reduces the number of nodes and the overall height of the tree, making it more space efficient.
A Patricia Trie’s optimisations result in improvements in the storage and compute complexity of lookups and insertions. While the worst case time complexity remains proportional to the length of the string (O(m)), due to the collapsed chains, the actual time can be less than in standard tries.
Similarly, due to a Patricia tries space-efficient design, the number of nodes required to represent a (sparse) dictionary reduce.
Using Patricia tries, we can create a data structure that quickly locates a node's position in any arbitrary tree based on its key. This allows for efficient lookups even in large databases.
With the implementation of a Patricia trie, we address the challenge of rapid reads/writes by enabling access to data storage slots through knowledge of the corresponding keys. However, in trustless environments, it is essential to ensure that the retrieved data is accurate. While Patricia tries can facilitate data retrieval, they require two separate read operations to achieve verification:
**Value Retrieval**: The first operation retrieves the value associated with a given key from the trie.
**Value Validation**: The second operation involves the validator traversing the trie again to validate the correctness of the retrieved value.
To validate without a second read, we can use a tree-like data structure that stores hashed values instead. This approach ensures that any change to the leaf node’s value automatically triggers a rehash across the tree, updating the leaf node and all its parent nodes up to the root.
The validation problem is reduced to a simple cryptographic check: if the provided leaf hash can be used to reconstruct the root hash through the Merkle proof, we can be certain that the leaf value is untampered.
This data structure is called a Merkle Tree. It is a tree based structure where each leaf node represents a hash of the underlying data, and each non-leaf node is a hash of its child nodes. This recursive hashing mechanism ensures that any data modification alters the hash of the corresponding node, propagating changes up to the root.
From this, we can derive two important properties:
To verify if all leaf nodes are unchanged between a “trusted” state tree and an “untrusted” state tree, we only need to compare the root node hash.
[Merkle proofs](https://medium.com/crypto-0-nite/merkle-proofs-explained-6dd429623dc5) verify the inclusion of specific data within the tree
To verify the presence of the leaf node "bin", we compute and return the following hashes:
**h(binary)**
**h(h(move)+h(movie))**
**h(h(tree)+h(trie))**
By calculating these hash values, we can traverse through all sibling nodes, allowing us to reconstruct the hash of the root node, to verify whether the leaf node "bin" is included in the tree. Read more on Merkle Proof verification here and here.
Merkle trees excel at proving data inclusion. To demonstrate the inclusion of a leaf node, a user can simply request a Merkle proof that shows a particular leaf is a child of the state root. Consequently,“Verifying Proof of Data Inclusion” requires only O(log N) time.
However, Merkle trees are inefficient at retrieving the "actual value" at the leaf node. This inefficiency arises because the position of a node is independent of it’s key. Hence the only way to fetch the “actual value” of a leaf node is to traverse the entire tree in a brute force fashion.
Read more about how Ethereum uses Merkle Proofs here.
A Merkle Trees property of enabling efficient checks on inclusion is leveraged in the Bitcoin Network. Light clients can use Merkle proofs to verify the status of a transaction. They do this by requesting a proof that demonstrates the inclusion of a transaction in one of the Merkle trees, with the root of that tree being included in the block header of the main chain.
This achieves Bitcoin’s use-case as a peer-to-peer version of electronic cash. However as Ethereum extends to behave as a global computer, Merkle Proofs are limiting. In particular, while Merkle Proofs enable verifying inclusion of transactions, proving the current state would require multiple, expensive reads.
Ethereum's state architecture must meet two crucial requirements:
To achieve this, Ethereum takes the Merkle tree concept one step further with “Merkle Patricia Trees”.
Merkle Patricia Trees, are specialised tree structures that combine the benefits of Merkle Trees and Patricia Tries. In particular, with an MPT, Ethereum gains the data integrity guarantees of a Merkle Tree, alongside the optimised reads/writes achieved through Patricia Tree’s key encoding. Due to these design advantages, MPTs today power Ethereum and several other blockchains.
The MPT is visualised as a tree, however it is stored in a key-value database like RocksDB where each node is serialised and stored as a value, with its hash serving as the key. This allows for efficient retrieval and verification of nodes based on their hash values.
In the above example,
