📕Understanding Merkle-Patrica Trees pt.2
Understanding Patricia Trees
A Patricia tree (also known as a "Radix tree" or "Trie") is a specific type of data structure that is used to store a set of strings. The strings are broken down into their individual characters, and the tree is built by creating a path for each string where each character forms a node along the path. Patricia trees are especially useful for data sets where there is a significant amount of overlap in the string prefixes.
In Ethereum's Merkle Patricia tree, each account with its associated information (such as account balance, nonce, contract code if it's a contract account, and storage) forms a string that needs to be stored.
Components of a Patricia Tree
The key components of a Patricia tree are:
Node: Each node in the tree represents a character of a string. In the context of Ethereum, a node could be a part of an account address or other account information.
Edge: This is the link between nodes. An edge connects a node to its subsequent node.
Key: This is the character (or in Ethereum's case, nibble, which is half of a byte) that a node represents.
Path/Prefix: This is the sequence of characters (keys) from the root of the tree to a particular node.
Root Node: This is the starting point for the tree. All paths in the tree start from the root node.
Leaf Node: These are the end points of each path. In Ethereum, a leaf node typically contains the state of an account.
How a Patricia Tree Works
In a Patricia tree, each path from the root to a leaf node represents a string from the set of strings the tree is storing. The characters of the string form the keys of the nodes along the path.
To find a particular string in the tree, you start from the root and follow the path that corresponds to the string's characters.
Patricia Trees in Ethereum
Ethereum uses a modified version of the Patricia tree called a "Merkle Patricia tree" for its state storage. In this case, each path from the root to a leaf node represents an account address, and the leaf node contains the state of that account.
Path Traversal in a Patricia Tree
Traversal in a Patricia tree begins at the root node. Each path from the root to a leaf node in the tree corresponds to an account address. To traverse the tree and find the state of a specific account, you follow the path that corresponds to the account address you're interested in.
The keys of the nodes along a path are the individual nibbles (half-bytes) of the account address. In the case of Ethereum, addresses are 20 bytes long, which means they can be broken down into 40 nibbles.
For example, if you want to find the state of an account with the address 0xabcdef, you would start at the root and first go to the child that corresponds to the nibble 0xa. From there, you would go to the child that corresponds to 0xb, then to 0xc, and so on, until you've followed the entire sequence of nibbles 0xa, 0xb, 0xc, 0xd, 0xe, 0xf.
At the end of this path, you will have arrived at the leaf node that contains the state of the account with address 0xabcdef.
The Patricia tree in Ethereum distinguishes between two types of nodes: leaf nodes and extension nodes. Furthermore, these nodes can hold a key that has an even or odd number of nibbles. To indicate the type and key length, a two-bit prefix is used. The possible values of the prefix are:
0x00: Extension node, even number of nibbles.
0x10: Extension node, odd number of nibbles.
0x20: Leaf node, even number of nibbles.
0x30: Leaf node, odd number of nibbles.
Extension nodes serve as internal nodes that help to navigate the tree, while leaf nodes are the actual data holders.
The "even" and "odd" number of nibbles part is about how the key is stored. A "nibble" is a four-bit aggregation, or half of an octet (an octet being an 8-bit byte). Keys in Ethereum's Patricia Tree are represented as hexadecimal strings, where each hex character represents a nibble (4 bits).
Now, when we say "even" or "odd" number of nibbles, we are talking about the length of the path from the root node to a particular node. If the number of nibbles in the path is even, the node has an even prefix (0x00 for extension, 0x20 for leaf), and if the number of nibbles is odd, the node has an odd prefix (0x10 for extension, 0x30 for leaf).
These prefixes play a key role in ensuring efficient traversal and manipulation of the tree structure. For example, if you have the hash of a node and want to retrieve its data from the database, you can decode the prefix to know whether the node is an extension or a leaf node and whether the key has an even or odd number of nibbles. With this information, you can effectively decode the key and the value, and continue your traversal or data manipulation as needed.
Values Stored in a Node
Each node in a Patricia tree contains a key, which is a character that the node represents. In Ethereum, these keys are nibbles from account addresses. However, leaf nodes in Ethereum's Merkle Patricia trees store more than just keys, they also store the state of the corresponding account.
The state of an Ethereum account includes:
Nonce: This is a number that represents the number of transactions sent from the account's address. It is used to prevent replay attacks.
Balance: This is the amount of Ether (the cryptocurrency of Ethereum) that the account holds.
Storage Root: For smart contract accounts, this is the root of another Merkle Patricia tree that holds the storage contents of the smart contract. Each path in this tree corresponds to a storage key, and the associated leaf node contains the storage value for that key.
Code Hash: For smart contract accounts, this is the Keccak-256 hash of the EVM (Ethereum Virtual Machine) bytecode that makes up the smart contract code. If the account is not a smart contract, this value is the hash of an empty string.
Each of these account state components is stored in the leaf nodes of the Merkle Patricia tree in Ethereum.
As a result, if you know an account address, you can traverse the tree to find the leaf node for that address and get the account's state. Conversely, if you have the state root (which is the root of the Merkle Patricia tree), you can verify the state of any account in the Ethereum network. This forms the basis of Ethereum's global state management.
Each node in a Merkle Patricia tree is identified by a unique hash, which is the Keccak-256 hash of the RLP (Recursive Length Prefix) encoding of the node's contents. The different types of nodes in a Merkle Patricia tree have different contents:
Leaf Nodes: A leaf node in a Merkle Patricia tree is a two-item structure,
[key, value]. The key is the account address (or rather, the Patricia-transformed version of it), and the value is the RLP-encoded state of the account. The state includes the nonce, balance, storage root, and code hash, as mentioned earlier.Branch Nodes: A branch node is a 17-item structure. The first 16 items correspond to the 16 possible nibbles (0-9 and a-f). Each item is the hash of the child node that corresponds to that nibble, or empty if there is no such child. The 17th item is a value, which is the account state if this node represents a complete account address, or empty otherwise.
Extension Nodes: An extension node is a two-item structure,
[key, value], similar to a leaf node. The key is a shared part of the keys of its child nodes, and the value is the hash of its single child node.
So, in addition to the key and value pairs (for leaf and extension nodes) or hashes of child nodes (for branch nodes), each node implicitly contains its own hash, which is calculated as the Keccak-256 hash of the RLP encoding of the node's contents. This hash is not stored in the node itself, but it is used as the reference in its parent node.
In the context of the Merkle Patricia tree, a crucial aspect is that the structure of the tree is bound together using hashes. Specifically, each parent node doesn't store the full content of its children but rather a cryptographic hash of them. This is what enables the entire data structure to be linked and navigated.
Let's say you have a parent node in the tree, and it has two children. When those child nodes are created, the information within each child node is hashed using a cryptographic hash function (Keccak-256, in the case of Ethereum). This produces a unique output (hash) for each child node. These hashes are then stored in the parent node.
When navigating the tree, you'd start from the root node and move towards the leaf nodes based on the path you are traversing. As you reach each node, the hashes stored in that node are used to identify which child node to descend into next.
This scheme provides a number of significant benefits:
Efficiency: Storing only the hash rather than the full node data keeps the size of each node manageable, and allows for efficient navigation and updating of the tree.
Integrity: Because the hash of a node is a unique fingerprint of its content, any change in the node's data would result in a change in its hash. This, in turn, would change the parent's hash and eventually, all the way up to the root. Therefore, any tampering of data can be detected by checking the consistency of the hashes.
Proofs: Hash linking also enables the use of 'Merkle proofs'. A Merkle proof allows you to prove that a specific leaf node is a part of the tree without needing the entire tree. This is done by providing a path of hashes from the root to that leaf.
So, to summarize, each node's link to its child nodes via storing their hashes is a critical feature that allows for the traversal, integrity verification, and proof of inclusion in a Merkle Patricia tree.
Storage and lookup
The actual Patricia Tree is indeed stored in a database. The choice of storage does not necessarily have to be in a single monolithic block; rather, due to the hashed link nature of the tree, the nodes can be stored in separate locations, be it in memory or on disk, or even distributed across a network.
This architecture is known as a distributed hash table (DHT), and Ethereum employs this structure in its underlying database (using a key-value store known as LevelDB).
The primary advantage of this setup is that it allows for efficient lookup, insertion, and deletion operations. When you want to fetch or modify a specific node, you can use its hash as the key to quickly locate it in the database. This is a far more efficient process than having to search through an entire block of data or an unordered database.
Furthermore, this setup also promotes scalability and fault tolerance. In a distributed network setting, even if one location fails or goes offline, the data isn't lost, as it's not stored in one single place. Moreover, since data is spread out and linked via hashes, the system can handle more data by simply adding more storage nodes to the network.
Lastly, this structure supports privacy and security. Since each node is identified and accessed via its hash, it's not straightforward to infer the actual data unless you know the hash. Also, the hash provides a built-in checksum, making it easy to detect if the node data has been tampered with.
In summary, the fact that the Patricia tree's nodes, linked via hashes, can be stored separately, brings significant benefits in terms of efficiency, scalability, fault tolerance, and security.
The Merklization of Patricia Trie: Enhancing Integrity and Verification
The process of merklization, or transforming the Patricia Trie into a Merkle-Patricia Trie, is a vital step in maintaining the integrity and efficiency of Ethereum's state. This transformation involves the integration of cryptographic hashes, particularly through the addition of these hashes in each node of the Trie.
Understanding the Process of Merklization
The concept of merklization entails replacing the traditional pointers in a Patricia Trie (that point to child nodes) with cryptographic hashes. These hashes are generated from the contents of the respective child nodes.
To start, the leaf nodes (those without any child nodes) are processed first. The content of these nodes is passed through a cryptographic hash function to create a unique hash. This hash effectively becomes the identifier of the node. The same process is repeated for every leaf node in the trie.
Next, we consider the parent nodes of these leaf nodes. For each of these nodes, we concatenate the hashes of their children and pass this concatenated string through the same cryptographic hash function. The resulting hash serves as the identifier of the parent node. This process is repeated for every node in the trie, progressing upwards level by level, until we reach the root node.
The root node follows the same pattern. It concatenates the hashes of its direct children nodes and hashes the resulting string to produce a unique root hash. This root hash, also known as the Merkle root, is significant because it represents the entire data set. If even a tiny part of the data set changes, the root hash will also change, indicating a modification in the data.
Significance and Advantages of Merklization
1. Immutable Data Structure
The principal advantage of merklization lies in its enhancement of data security. By associating every node with the hash of its content, merklization turns the Patricia Trie into an immutable data structure. Any change in the data, no matter how small, alters the hash of the node containing the data. This change propagates up to the root of the trie, changing the root hash. Consequently, the merklized Patricia Trie offers a robust method for detecting data changes.
2. Facilitation of Merkle Proofs
The merklized Patricia Trie enables efficient data verification through the use of Merkle Proofs. In a nutshell, a Merkle Proof is a chain of hashes proving the inclusion of a specific piece of data in the data set. A user can check the existence of a particular piece of data without accessing the entire dataset, only needing the relevant hashes from the root to the leaf node containing the data. This aspect is particularly beneficial for lightweight Ethereum clients that do not store the full state.
3. Pruning and Storage Efficiency
Merklization allows for efficient pruning of the Patricia Trie. Because the nodes are connected via hashes, it becomes possible to remove nodes (especially older versions of the state) without disrupting the overall structure of the trie. Nodes that are not referenced anywhere in the trie (i.e., their hashes are not present in any parent nodes) can be safely removed. This aspect helps to optimize the storage requirements of Ethereum clients.
In summary, the merklization of the Patricia Trie is a crucial aspect of Ethereum’s state handling, providing both a high level of data integrity and an efficient means of data verification.
By now, we've covered the majority of fundamental concepts related to the Merkle-Patricia Trees.
Remember, understanding Merkle-Patricia Trees can be challenging due to their complex structure and properties, but they are a fundamental component of Ethereum's architecture and are instrumental in maintaining the integrity and security of the Ethereum state. It's okay if you don't grasp every detail right away - keep learning and revisiting the concept, and it will gradually become clearer.
Last updated
