What are Merkle trees and how do they work?
A binary tree that uses cryptographic hash algorithms is called a Merkle tree.
A hash tree also referred to as a Merkle tree, has labeled leaf nodes with the cryptographic hash of a data block. In addition, it has labeled non-leaf nodes with the cryptographic hash of the labels of its child nodes.
Each node generates a digest that recursively relies on all of the characteristics in its subtree, and one or more attributes are added to the leaves. In a Merkle tree structure, leaves compute their own attributes' hash, and parents calculate the digests of their children's concatenated left-to-right digests.
But who invented Merkle trees? Ralph Merkle developed Merkle trees in 1988 to create stronger digital signatures. Merkle trees efficiently verify the correctness and integrity of data while reducing the verification's memory requirements. Also, compared to other data structures, Merkle trees take up less disc space, which is one of the significant advantages of Merkle trees.
So, is Ethereum a Merkle tree? The Ethereum blockchain uses a Merkle tree called the Merkle Patricia trie, which offers a data structure that may be used to store all (key, value) bindings and is authenticated cryptographically.
Additionally, all of the Merkle tries in the Ethereum execution layer use a Merkle Patricia Trie. The state trie updates over time as there is one global state trie. All contract data is kept in storage trie. Every block has its own transactions trie that stores (key, value) pairs. Each block contains a separate Receipts trie that is never updated.
What are Verkle trees and how do they work?
Similar to Merkle trees, Verkle trees allow you to organize a considerable quantity of data and create a brief "witness" of each item of data or group of related pieces that can be confirmed by someone who has access to the tree's root.
However, Verkle trees' most important feature is their proof-size efficiency. A Verkle tree would require less than 150 bytes to produce a proof for a tree with a billion data points, compared to a typical binary Merkle tree's around 1 kilobyte. Verkle trees utilize a proving system called Polynomial Commitments, relying upon polynomial functions to describe data.
But who invented Verkle trees? In 2018, John Kuszmaul introduced Verkle trees, which are still not as well known as many other significant new cryptographic structures. A Verkle tree structure resembles Ethereum's current Merkle Patricia tree. In essence, each node has one of three properties:
- It is empty.
- It is a leaf node with a key and value.
- It is an intermediate node with a defined number of children (the "width" of the tree).
A hash of the values of a node's children is used to calculate the value of an intermediate node. However, Verkle trees are more expansive than Merkle Patricia trees, which is one of the distinct advantages of Verkle trees and the only substantial distinction between their structural components. The sole restriction is that if the width increases too much, proofs begin to take too long to produce. As a result, the proofs get shorter and shorter as the width increases.
What is the importance of Merkle and Verkle trees in blockchain?
Merkle trees are employed in Bitcoin (BTC) and other cryptocurrencies to more effectively and securely encrypt blockchain data. Verkle trees allow for smaller proof sizes, particularly important for Ethereum's upcoming scaling upgrades.
But, how do you identify a Merkle tree? Leaf nodes, non-leaf nodes and the Merkle root are the three essential parts of a Merkle tree in the context of blockchains. Transaction hashes or transaction IDs (TXIDs) reside in leaf nodes, which can be viewed on a block explorer. Then, above the leaf nodes, a layer of non-leaf nodes is hashed together in pairs. Non-leaf nodes keep the hash of the two leaf nodes they represent below them.
Related: What is blockchain technology? How does it work?
As the tree narrows as it ascends, half as many nodes per layer are formed when non-leaf node levels continue to be hashed together in pairs. Two nodes will be present in the final non-leaf node layer, which establishes the Merkle root (used to verify the leaf nodes) and is the location of the last hashing in a Merkle tree.
The Merkle root stored in the data portion of a block can be compared to the Merkle root stored in the header, allowing the miner to identify any manipulation quickly. A Merkle proof combines the value being proved and the hashing values needed to recover the Merkle root. In addition, they support simple Payment Verification (SPV), which can be used to authenticate a transaction without downloading a complete block or blockchain. This allows using a crypto wallet or light-client node to send and receive transactions.
Verkle trees enable significantly reduced proof sizes for a large amount of data compared to Merkel trees. The proof length, typically logarithmic in the state size, impacts network communication. But, what is a Verkle proof? A Verkle proof is evidence of a large amount of data stored, which could easily be verified by anyone with the tree's root.
The prover must offer a single proof demonstrating all parent-child links between all commitments along the paths from each leaf node to the root instead of presenting all "sister nodes” at every level in Verkle trees. Compared to ideal Merkle trees, proof sizes can be reduced by a factor of six–eight and by a factor of more than 20–30 compared to Ethereum's current hexary Patricia trees.
Merkle trees vs. Verkle trees
There are many differences between both types of trees, particularly in providing Merkle proofs and Verkle proofs.
The whole set of sister nodes in a Merkle tree, including Merkle Patricia trees, constitutes evidence of a value. The proof must include all nodes in the tree with any parent node in common with the node you are attempting to prove. On the other hand, in a Verkle tree, you only need to supply the path plus a tiny bit extra as proof—you don't even need to add sister nodes.
The Verkle tree's main idea is that a Merkle tree may be created by substituting vector commitments for the cryptographic hash functions. A Verkle tree serves the same purpose as a Merkle tree. However, they are significantly more effective in size in bytes, which is the primary distinction.
Due to their tree-like structure, Merkle proofs are simple to update in part while the Polynomial Commitments in Verkle trees call for a complete alteration of the entire curve, which would be challenging to calculate witnesses for.
People worldwide may send, receive and verify transactions with crypto wallets that can be run efficiently and simply on a personal computer or smartphone, which is the significant Merkle tree use case, possibly due to Merkle roots formed from Merkle trees. On the contrary, one of the crucial Verkle trees use cases includes substituting a vector commitment for the hashes in a Merkle tree, increasing the effectiveness of broader branching factors.
Purchase a licence for this article. Powered by SharpShark.