Merkle Patricia Tree in Blockchain
Mostly utilized in blockchain technology, particularly in Ethereum, a Merkle Patricia Tree (MPT), also called a Modified Merkle Patricia Trie, is a cryptographically verified key-value store data structure. It combines the characteristics of Patricia trees (sometimes called Radix trees) and Merkle trees, two different types of data structures.
Components and Foundation
Merkle Tree Foundation:
A Merkle tree is a structure that resembles a tree and comprises hashes of individual data points, like transactions, at its base, known as leaves. Parent nodes are constructed by hashing together the hashes of their child nodes until a single Merkle root is produced at the very top.
This Merkle root acts as a unique digital fingerprint for each item of data in that tree. Data integrity can be quickly and effectively verified since any change, even a single bit change, within a data piece will change its hash, which will then affect the entire Merkle tree and eventually the Merkle root. Because Merkle trees are “set in stone” by the Merkle hash root, creation and editing time are irrelevant; they are ideal for static, permanent data, such as mined transactions.
You can also read Types of Security Tokens Blockchain, How it works & Benefits
Patricia Tree Integration:
A Patricia tree, also known as a Radix trie, is a condensed form of a “tree,” a computer tree that records data. For “Practical Algorithm to Retrieve Information Coded in Alphanumeric,” “Patricia” is an abbreviation. By combining nodes that are their parents’ only children, it maximizes storage and speeds up processes like data deletion, insertion, and search. In order to maximize storage and retrieval times, it pairs comparable-value nodes, so that pathways with similar prefixes share the same beginning branch.
The Modified Merkle Patricia Trie ensures dependable data verification (from Merkle Tree) and efficient data storage (from Patricia Trie) by fusing the best features of each.
Why Ethereum Uses Merkle Patricia Tries
Ethereum’s dynamic structure and the ongoing creation and modifications of accounts necessitate flexibility in contrast to Bitcoin, which largely maintains an immutable list of transactions. In order to meet these particular needs, Merkle Patricia Tries were specifically created for Ethereum.
- Data Integrity and Tamper Detection: The Merkle Patricia tree ensures blockchain data integrity. Even a single bit alteration to a transaction or data element’s hash will cascade through the Merkle tree and root. This lets you evaluate data integrity fast and efficiently without reviewing every piece of data.
- Verification of Inclusion: A key-value pair’s inclusion can be confirmed using the MPT without requiring access to the complete collection of key-value pairs. Light clients in Ethereum, which only have access to the Merkle root hash for a specific block and not the entire blockchain state, will find this very helpful. The account key and its balance value, the Merkle root hash, and more information can all be found in a full node’s Merkle proof. Without requiring the complete blockchain state, a light client can use this tiny bit of information to confirm the accuracy of data, such as an account balance. Because the Merkle root hash is part of every block head and is verified by computing work, Ethereum’s Proof of Work consensus method makes it reliable.
- Efficiency: MPTs make the Ethereum network’s data storage and retrieval as efficient as possible. Because they store fixed-length hashes rather than massive databases and proofs are compact and fast to send, they drastically save storage needs and related expenses. They are ideal for ephemeral data, such as Ethereum account statuses, which fluctuate regularly, because they are effective at both data editing and data verification.
Node Types
Internally, the Merkle Patricia Tree has four types of nodes:
- EmptyNode / Null nodes: These stand in for empty strings and act as stand-ins for values that have been removed or are missing. They may also serve as evidence of a particular data piece’s MPT. A fresh LeafNode is used in its stead when it stops at an EmptyNode.
- LeafNode: This node represents the end of a specific data path and holds the remaining path and value or the actual key-value pair. A new branch and LeafNode are added when it stops at a LeafNode, which transforms it into an ExtensionNode.
- BranchNode: This node represents the 16-character hexadecimal alphabet and functions similarly to a tree branch. It can have up to 16 children. Each branch node has 17 items, including one value that functions as a key-value pair and 16 hexadecimal characters (nibbles that lead to child nodes). It can be transformed to another ExtensionNode and a new BranchNode is generated when it stops at an ExtensionNode.
- ExtensionNode: This node functions as a branch node’s optimized version or shortcut. Paths for branch nodes with a single child and no siblings after that are compressed.
You can also read What Is A Hash Pointer In BlockChain Data structure Basics’
Function in Ethereum: The Three Tries
At its core, the Ethereum blockchain is a “state tree.” The roots of three different Merkle Patricia Trees can be found in each Ethereum block header:
- A per-blockchain data structure called State Trie (World State Trie) keeps track of the current status of every account on the network. It serves as a mapping between account states (such as balances, nonces, storageRoot, and codeHash) and addresses. Account balances and other data changes are regularly reflected in this state. This world state trie’s root node is hashed and included in the block header as “stateRoot.”
- Transactions Tree: This tree contains details about the transactions that are a part of a block. The block header contains the transaction root root hash for this tree. The transaction tree is never updated when a block is mined. Values are RLP encoding of the associated transactions, and keys are RLP encoding of unsigned integers beginning at index 0.
- Receipts Tree: This tree keeps track of the results and consequences (receipts) of every transaction that is carried out. Logs (events emitted) and gas utilised are examples of data. The block header additionally contains receiptRoot, the root hash of the receipts tree. The transaction receipt trie is never changed after a block is mined, just like the transaction trie.
Building and Updating a Trie (Example)
The root node of a newly constructed trie points to an EmptyNode.
- Adding the first transaction: The transaction data is used to generate a LeafNode, which is referenced by the root node.
- Adding the second transaction: The LeafNode at the root turns into a BranchNode with two branches pointing to two LeafNodes.
- Adding subsequent transactions: Similar processes occur; a LeafNode might turn into a BranchNode, or an ExtensionNode might be used to compress paths. Even if the root node doesn’t explicitly change, its hash will change if any of its underlying branches or nodes are updated.
The path to the LeafNode where a transaction’s value is stored is its Merkle Proof. Beginning with the root hash, verification entails decoding nodes and matching nibbles until the correct LeafNode is located.
Importance and Benefits
Integrity of data and detection of tampering.
- Immutability: Once data is recorded on the blockchain, it is very difficult or nearly impossible to change it due to the cryptographic linking of blocks through their hashes and Merkle roots.
- Storage and bandwidth efficiency: Smaller proof sizes for verification and lower storage needs.
- Decentralization support: Merkle trees’ architecture naturally accommodates a distributed system, allowing multiple nodes throughout the network to add to the blockchain without the need for a central authority.
- Stores both temporary and permanent data effectively.
- Enables regular data updates and alterations within nodes, enabling data erasure following operations.
- Reusable code for updating protocols.
- Attacks known as Denial-of-Service (DoS) are prevented via key hashing.
You can also read What Is Merkle Proof, Features, Applications And Purpose