Merkle Patricia Tries: A Deep Dive into Data Structure Security

Fundamental to blockchain technology, these structures ensure data integrity and enable efficient transaction access

In the realm of blockchain technology, Merkle Trees serve as a fundamental data structure, ensuring the integrity of blocks and fast access to transactions. Specifically, they allow for the efficient verification of individual pieces of data without the need to examine every other piece, making them indispensable for maintaining the trust and efficiency of blockchain networks. Beyond their core verification role, Merkle Trees have evolved into more sophisticated structures like Merkle Patricia Tries (MPTs).

While Merkle Trees mainly serve to check if something exists within a list, MPTs provide further functionality. They not only let users check for items but also efficiently add or remove them from a succinct proof only. Examining the origins of Merkle Trees, their evolution into MPTs or alternative data structures, and how they have revolutionized data organization and security can provide further insights into decentralized network functionality.

The beginnings of Merkle Trees

The story of Merkle Trees commences in 1979 with Ralph Merkle, a computer scientist who envisioned an efficient method for verifying the integrity of large datasets. His concept was simple yet groundbreaking: construct a tree-like structure where each leaf node represents a hash or unique identifier of a data block, and each non-leaf node represents a hash of its child nodes.

This structure allows for quick and easy checking of any piece of data within the set by simply following the branches from the top to the bottom of the tree.

The hash function and Merkle Trees

In more technical terms, Merkle Trees function like a filing cabinet where each file has a unique fingerprint known as a hash. These hashes become organized into a tree-like structure.

At the origin of this tree is a single hash called the root hash. This root hash represents the entire tree and all the data within it. A Merkle tree hash function receives a set of data and organizes it into a tree structure. The function then recursively hashes pairs of nodes until the function generates a single root hash. Critically, hash functions possess distinct properties:

• •They are short and portable (only a few bytes long), irrespective of the size of the input data.
• •The same input always yields the same output.
• •Finding two different inputs that produce the same output is computationally infeasible.
• •Given a hash, finding the original input is computationally infeasible.

These properties make hash functions perfect for ensuring data integrity. Even the slightest change in input data results in a completely different hash, making tampering or corruption easily detectable. However, while Merkle Trees excel at verifying data integrity, they remain computationally expensive to construct and extend, which means adding an element to large trees is cumbersome, especially when done repeatedly.

Enter the Merkle Patricia Trie

The Merkle Patricia Trie (MPT) emerges as a hybrid data structure combining the strengths of:

• •Trie: A tree-like structure where each node represents part of a key, the path from root to leaf representing the complete key.
• •Patricia Trie: A compressed trie eliminating nodes with only one child, optimizing storage.
• •Merkle Tree: Each node in the Patricia Trie associates with a hash, enabling efficient data integrity verification.

Given this hybrid approach, MPTs enable the efficient addition and removal of key-value pairs—a crucial function for dynamic data storage. Adding introduces new data with a unique key, potentially modifying the tree structure. Removing deletes existing data using the key as a locator, adjusting the tree accordingly. Both operations ensure data integrity through hash updates, and are possible from knowledge of a short root hash representing the entire tree and a succinct proof. This highlights MPTs' efficiency and security in handling evolving data sets. In fact, Ethereum uses MPTs to store its blockchain state and transactions, allowing light clients to check balances without storing the entire blockchain.

In other words, the key advantage of MPTs lies in their ability to efficiently update and verify changes. By using succinct proofs, it’s possible to add or remove elements without needing the entire dataset—just the root hash and the proof suffice. This proof not only verifies membership but also validates the legitimacy of additions or removals. However, while significantly smaller than the entire data set, MPT proofs can become large compared to the size of a transaction, reaching multiple kilobytes for substantial data stores. This poses less of a problem for off-chain operations, but on-chain, every byte generates additional network costs.

A Merkle proof represents a concise collection of hashes that allows verification of a specific data block's inclusion within the Merkle structure without downloading the entire dataset. This proof consists of:

• •The data block itself.
• •The hashes of its sibling nodes along the path to the root.

The verifier uses these hashes to recalculate the root hash and compare it to the original, thus verifying the data block's integrity. Notably, the hash function builds the Merkle structure, while the Merkle proof serves as a way to efficiently check if something belongs within that structure.

The data structure of Merkle Patricia Tries

Like Merkle Trees, MPTs enable efficient data integrity verification. To verify a key-value pair's inclusion, one needs only the hashes of nodes along the path from the root to the leaf containing the pair. Recalculating the root hash and comparing it to the original confirms integrity.

MPTs comprise branch nodes, extension nodes (with a key fragment and single child), leaf nodes (storing key-value pairs), and empty nodes. Each node stores a hash of its contents, creating a Merkle tree structure within the trie. To store or retrieve a key-value pair, the key converts to hexadecimal, the trie is traversed based on these digits, nodes are created or updated as needed, and hashes are calculated and stored.

In theory, MPTs reflect a radix of two (i.e., two children) and perform most efficiently in this format. However, in practical terms, they typically utilize a radix of 16 (i.e., 16 children) because this structure aligns optimally with hexadecimal encoding, where each digit in a hexadecimal string can represent a branching path.

Merkle Patricia Forestry: An innovative data structure

Cardano specifically lacks highly optimized primitives for bitwise operations–fundamental for manipulating data at the bit level. In fact, Cardano Improvement Proposal (CIP)-0123 proposes to address this challenge with a solution part of the upcoming Plomin hard fork. In the interim, this gap hinders the efficient use of radix two trees, data structures relying on bitwise operations for:

• •Node traversal: Examining specific bits in a key to navigate the tree.
• •Data manipulation: Altering bits within keys for insertion, deletion, and search operations.
• •Memory efficiency: Optimizing storage and access of data.

Without these optimized primitives, radix two tree operations become slow and resource-intensive while code complexity increases, requiring workarounds for efficient bit manipulation. For this reason, innovative data structures that leverage existing solutions have emerged to further organize and verify large amounts of data efficiently. For instance, the Merkle Patricia Forestry makes radix 16 MPTs as efficient as their radix two equivalents by leveraging a unique hashing structure of the proofs.

The Merkle Patricia Forestry structure, while based on MPTs, introduces a key innovation in proof encoding. Instead of listing all neighboring node hashes at each step, it organizes them into Sparse Merkle Trees. This drastically reduces the number of hashes required for verification, from a maximum of 15 in traditional MPTs to just 4. As a result, the proof size is comparable to that of a radix 2 trie, but the cost of verification increases marginally.

This concept saw recent demonstration through the placement of Bitcoin's complete block history into this structure. Matthias Benkort, Technical Director of Open-Source Development at the Cardano Foundation, then added a new Bitcoin block to it, all on the Cardano blockchain. This occurred using a very small amount of data and computing power, showcasing the efficiency of the Merkle Patricia Forestry. Given its improved functionality, this structure could support solutions like trustless bridges between different blockchains, managing domain names on blockchain networks, or even storing large datasets like financial market data or Github stats directly on chain.

Data structures of the future

Merkle Trees and their more advanced counterparts, like MPTs, have transformed how individuals and enterprises store, retrieve, and verify data in the digital age. Their ability to ensure data integrity and enable efficient verification makes them essential in various fields, especially blockchain technology.

As entities continue to generate and rely on ever-growing volumes of data, Merkle Trees, MPTs, and novel alternatives will undoubtedly remain crucial in safeguarding the security and trustworthiness of our digital world.