Merkle Patricia Trie

Published on :

21 Aug, 2024

Blog Author :

Edited by :

Reviewed by :

The Merkle Patricia Trie (MPT) is a fundamental data structure utilized within the Ethereum blockchain, integrating the characteristics of both Merkle trees and Patricia tries. Its primary role is to function as a robust data storage system for managing the vast array of transactions and receipts on the network.

In contrast to Bitcoin, the Merkle Patricia Trie is purpose-built for Ethereum, addressing the specific requirements of the network. It stands as a unique and vital component of Ethereum's infrastructure, offering efficient data management capabilities tailored to Ethereum's decentralized and smart contract focused ecosystem.

What Is Merkle Patricia Trie?

The Merkle Patricia Trie (MPT) is a pivotal database structure merging Patricia Tries and Merkle Trees, primarily used in the Ethereum blockchain.
It encompasses various node types, including empty, branch, leaf, and extension nodes, forming an organized data storage system.
Ethereum employs three distinct tree structures: the transaction tree, the receipt tree, and the state tree. Notably, empty nodes serve as backups for branch nodes, and other nodes contain keys and paths.
This structure optimizes data storage and retrieval within Ethereum's network.

Merkle Patricia Trie Explained

The Merkle Patricia Trie is an Ethereum-based database, which is a variation of the Patricia Trie. It offers a structured approach for organizing and storing data in a tree-like format. In this context, Patricia derives from Practical Algorithm To Retrieve Information Coded In Alphanumeric, while Trie relates to retrieval. While a similar database is found in Bitcoin, it doesn't align with Ethereum's requirements.

Unlike Bitcoin, which maintains an unchanging list of transactions, Ethereum's dynamic nature and the creation of new accounts demand flexibility. Hence, the MPT was purposefully designed for Ethereum. It operates using a key-value mapping structure, using keys (transaction IDs) and values (transactions). It serves to store and retrieve data efficiently, though it removes operations after a transaction occurs.

The modified MPT in Ethereum comprises various nodes traceable via hashing. The root node acts as a parent node or cryptographic representation of the entire Trie. Additionally, different tree structures, such as transactions, receipts, and state trees, serve specific functions. For example, the transaction tree determines block inclusion, the receipts tree retrieves transaction-related data, and the state tree verifies balance updates and account existence within the network.

Features (Nodes)

In the Ethereum network's MPT, essential components, or nodes, play crucial roles. Each node possesses a unique hash value that also functions as a key, connecting to branches through nibbles to distinguish items based on their fundamental values. Let us delve into these node types:

#1 - Null nodes

These nodes represent empty strings and serve as stand-ins for missing or deleted values when necessary. They not only replace such values but also act as proof of the MPT for a specific piece of data.

#2 - Branch nodes

As the name suggests, branch nodes are analogous to the branches of a tree. Each branch node consists of 17 items, with one item representing the value and the remaining 16 representing hexadecimal characters. The last item serves as the key-value pair.

#3 - Leaf nodes

A node without child nodes is classified as a leaf node (or end node). It originates from a branch node and includes two components: path and value. For instance, if AxBE is a branch node in the MPT, the subsequent leaf nodes would be AxBEF and AxBEC. Each leaf node, like AxBEF, features AxF as the path and 1000 as the value.

#4 - Extension nodes

Another node type, the extension node, serves as a shortcut to stored data. It's an optimized version of a branch node. In some instances, branch nodes have only one child node with no subsequent siblings. To streamline the Trie, these branch nodes are compressed into extension nodes, which include a prefix, path, and value related to the child node. The hash value is derived from another node in this context.

Examples

Let us look at some examples to comprehend the concept better:

Example #1

Suppose TICK operates on the Ethereum blockchain network. On a regular basis, this network records millions of transactions, accompanied by the creation of numerous accounts to facilitate these exchanges. These accounts store essential data concerning keys and account balances, which are then organized and stored in the MPT for future reference. As multiple accounts, including Account #1, #2, and #3, are established, they integrate into this database.

The initial phase commences with an empty node, serving as the foundational component of the Trie. Subsequently, all three accounts evolve into branch nodes. During this stage, it becomes necessary to provide a Merkle Patricia Trie proof to validate the account balances. This proof is generated starting from the root node and extending to Account #1, encapsulating the hashes of the empty node, branch node, and leaf node.

When an account holder transfers 20ETH to another wallet, the Merkle Patricia Trie undergoes an update. Consequently, the proof generated at a later stage will reflect these changes in its state. This process effectively captures the entire data of the TICK blockchain.

Example #2

In the rapidly evolving world of cryptocurrencies, June 2023 has brought forth exciting developments with the emergence of Kakarot zkEVM. This Ethereum Virtual Machine (EVM) implementation, crafted in Cairo, is poised to play a pivotal role in revolutionizing the Ethereum and StarkWare ecosystems.

Kakarot zkEVM outlines an ambitious three-phase roadmap. Phase one focuses on integrating EVM functionality into Starknet, simplifying app deployment. In the second phase, Kakarot and Madara merge to establish L3 zkEVM, enhancing security and decentralization through proof of validity. The final phase unites Kakarot and Madara to create type 1 zkEVM, enabling L1 consensus proofs and potentially transitioning from Pedersen Merkle Patricia Trie (MPT) to Keccak MPT.

This strategic progression not only boosts efficiency but also reduces computational and storage costs, signaling a promising future for a more secure, scalable, and cost-effective blockchain ecosystem.

Importance

MPTs are vital data structures not only in blockchains but also in computer systems. Their significance to network participants can be summarized as follows:

MPTs efficiently store both temporary and permanent data. They utilize Patricia's tries for the former and incorporate fixed data into Merkle trees.
These structures excel in facilitating frequent data edits and updates within nodes. They allow for data deletion after operations, ensuring that older data nodes are removed as new ones are updated.
MPTs offer developers the advantage of code reusability for protocol updates, serving as a universal framework for major upgrades without the need to create entirely new code from scratch.
Significantly, MPTs play a pivotal role in reducing data storage requirements and associated costs when recording and maintaining databases. Their compression techniques, particularly within the Ethereum network, efficiently address this challenge.

Frequently Asked Questions (FAQs)

1. What is the difference between Merkle patricia trie and Merkle tree?

MPT is primarily used within the Ethereum network for facilitating constant data editing, while the Merkle tree isn't designed to offer data on the current state. For instance, Merkle trees can't provide information about an account's balance.

2. What is the difference between the sparse Merkle tree and the Merkle Patricia tree?

The critical contrast between them lies in their operational approach. Sparse Merkle trees handle data that might not even exist in the database, representing an advanced version of Merkle trees. In contrast, MPT focuses solely on the provided dataset.

3. How many bytes of data can the Merkle Patricia Trie store?

In the storage structure, the address length can range from zero to 32 bytes, roughly equivalent to 48 characters.

4. Why are keys hashed in Merkle Patricia Trie?

Key hashing in MPT serves as a defense against Denial-of-Service (DoS) attacks, employing the sha3(k) algorithm to safeguard keys under adverse circumstances.