The Merkle Tree And Verkle Tree In Blockchain
通过 LCX Team · November 11, 2022
The Ethereum Merge has been executed successfully, and as Vitalik once mentioned, “Ethereum is just 40% complete—and there’s plenty more coming after the merge.” During the Ethereum Community Conference in France on July 22, Vitalik stated that Merge is only the beginning. The Ethereum network will undergo many more upgrades after the merge: the surge, the verge, the purge, and the splurge. Blockchain structures are complex but very intriguing. The Merkle Tree is an integral part of many blockchain networks, including Ethereum. Understanding how blockchain ensures efficiency and reliability in the verification process is essential to understand the Merkle Tree and verkle trees.
What is a Merkle tree?
Merkle tree is also known as a Hash tree, a data structure composed of hashes of different content blocks. It is a tree in which each leaf node is identified with a cryptographic hash of the data block and each non-leaf node with a cryptographic hash of its child node labels. It is responsible for verifying the content and encrypting the blockchain data effectively.
Ralph Merkle invented Merkle trees to construct more reliable digital signatures. Compared with other data structures, Merkle trees take up less disc space, making them more efficient.
Working of Merkle trees
In the blockchain, there are thousands of blocks in which an infinite number of transactions are taking place at the same time. Merkle tree helps in encrypting the data safely in the blockchain. It forms the pair of the transactions occurring, then calculates the hash for each pair separately. And the steps are repeated, and now the pairs are formed, and the hash is calculated for the parent node. The process of hashing pairs of nodes takes place repeatedly until there is only one hash left, which is the root of the tree; this hash is called Merkle Root.
The three essential parts of the Merkle tree in blockchain are – Leaf nodes, Merkle roots, and Non-leaf nodes.
- Leaf nodes – is the hash of transactional data occurring on the block of the blockchain. The hash value calculated for each transaction is collected in the leaf nodes.
- Non-leaf nodes – store the hash values of their previous hashes. It is also called intermediate nodes. This process continues till it reaches Merkle root.
- Merkle roots – the root of the Merkle tree is called Merkle Root. It is the last hashing location in the Merkle tree. The information in this last block and the root hash of all transactions are stored in the block’s header.
The bottom-up approach is used for constructing the Merkle tree. Due to this approach, the hash values are calculated from a lower to a higher point.
Use-cases of Merkle Tree:
-Consensus Protocols
-Cryptocurrencies
-Public-Key Directories
-Encrypted Web Applications
-Secure File Systems
-Proof-of-reserves
What is the Verkle tree?
Verkle tree helps in giving structure to the considerate quantity of data. It is done by creating a witness that will provide proof of each data item on the blockchain, but this can only be achieved by having access to the root’s tree.
John Kuszmaul invented verkle trees. The most significant feature of Verkle trees is proof size efficiency. When constructing the proof for the tree, which may contain more than a billion data points, the verkle tree needs less than 150 bytes.
Working of Verkle trees
The verkle trees enable decreased data sizes for huge amounts of data. The nodes of Verkle trees have the following features: either empty, the intermediate node has a specified number of children, or a leaf node has a key and value. The Verkle tree’s structure comprises two nodes – The extension node and the Inner node.
The extension node can represent multiple values simultaneously, and the inner node can also have multiple values that can be some other extension node. The value of an intermediate node is calculated by using a hash of the values of its children. While forming the verkle trees, the major limitation is that if the width is huge, then the proofs will take a long time to be produced. And eventually, it will result in a decrease in the length of the proofs.
Conclusion
Both the Merkle tree and the Verkle tree are playing a major role in the blockchain industry. They both have the same function and usage and are responsible for maintaining the integrity, synchronization, and encryption of blockchain data. They both are going to be more implemented in the coming years.
