What is Verkle Tree and how is it different from Merkel Tree?
The value and validity of blockchain depends on the immutability and secure transfer of data in a network of information. What distinguishes blockchain from many other data networks is the possibility of converting information into cryptographic codes that classify and secure data in the form of a linear, connected and immutable chain of blocks; But with the increasing adoption of blockchain and the need for greater scalability, cryptographic engineers are also constantly looking for the best solutions for data compression; so that data safety is not affected. Verkle Tree is one of these solutions.
Data in the blockchain is converted into strings of bits with a fixed size and length by hash functions so that they can be easily identified and transferred. These strings, called “hashes”, can guarantee the important features of the blockchain, namely immutability, data integrity, privacy and information transparency. Different blockchains use different data structures to classify and organize these hash codes, some of which are more efficient. Verkle tree is one of the data structures that can play a prominent role in Ethereum updates and increasing the scalability of this network by improving the accuracy and speed of data processing.
Read more: What is Merkle Tree?
Considering the importance and role of Verkle tree in the promotion of the Ethereum network, in this article we try to analyze this structure and how it works. Also, considering the similarities between Verkle tree and Merkel tree, we first point out the importance of these two information structures and then highlight their important differences. Note that these data structures have many technical and complex details. In this article, by simplifying the specialized concepts, we have limited ourselves to a brief introduction to simply introduce you to the essential nature and role. Verkle tree Let’s get to know more.
Verkle tree (Verkle) What is?
A vercle tree is a data structure that helps summarize and organize large amounts of data. This structure creates a brief “Witness” of each data or group of data so that anyone who has access to the root of the tree can validate and confirm the data.
In simpler terms, you can feed a large amount of information to a Verkle tree and end up with only a short proof. In this case, anyone who has access to the root of the tree can validate and verify each part of the data separately.
In 2018, John Kuszmaul introduced the concept of Verkle tree. This cryptographic data structure, which is still not as well known as its other counterparts, has a function similar to the Merkle Patricia tree currently used in the Ethereum blockchain. To better understand the Verkle tree, it is better to take a brief look at the Merkel tree and the Patricia Merkel tree.
Merkle Tree
The Merkle Tree includes a large amount of information in an economical and small space and helps in faster and more efficient encryption and validation. This structure, which is used in various blockchains, including Bitcoin, receives the separate data of various transactions and converts them into hash codes under encryption and hashing algorithms.
Read more: What is the hash and hashing function?
Each pair of hashes is put back under the hash function to create a new hash. Thus, the number of nodes in each new layer is reduced by half and the Merkel tree structure becomes narrower. To better imagine what is happening, just consider an upside down tree similar to the image below.
In the simplified image above, from a Merkel tree structure, nodes 0-0, 0-1, 1-0 and 1-1 are known as leaf nodes, which are the hash values of L1, L2, L3 and L4 transactions, respectively. The hash codes of these nodes are placed in a binary and pair structure under the hash function to be converted into new hash values.
The new hash values are stored in nodes 0 and 1, which are known as non-leaf nodes or parent nodes. Also, since these nodes are in the middle of the data structure, they are also called intermediate nodes. It should be noted that nodes 0-1 and 1-1 are child nodes for node 1 and nodes 0-0 and 0-1 are child nodes for node 0. Note that the data structures are much broader than the simplified illustration above.
How long does the hashing process last?
The hashing process continues until we finally reach two non-leaf nodes that create the final hash or “Top Hash”. The final hash is the root of the Merkel tree and is recorded in the header of the block. This hash is the block ID and can be used to validate leaf nodes. In other words, the Merkel root is a guarantee for the correctness of the data of the entire block.
Read more: What is a block in the Bitcoin blockchain and what is inside it?
Ethereum uses the idea of the Merkel tree structure of Bitcoin; But in this network, instead of one Merkel tree, we are faced with three Merkel trees, which are used for three components of transactions and transaction receipts and network status. This data structure, known as the Patricia Merkel tree, stores data and updates the network state to help with authentication and shield against malicious actions and data manipulation. Now, Ethereum with Introduction A new structure called work tree tries to increase the efficiency of data processing.
What are the characteristics of the Verkle tree?
In the Verkel tree, we are facing a structure similar to Patricia Merkel. In other words, each node in this structure has three main characteristics:
- it is empty.
- It is ninety pages with one key and one value. For better explanation, you can key Address An account and amount inventory Consider it.
- An intermediate node with a certain number of child nodes that define the width of the tree. In simpler terms, it specifies how many nodes fit in each layer of the tree.
The most important feature of Verkle tree is reducing the size of proof data. It is interesting to know that the Merkel tree requires one kilobyte of space to create a proof of a tree with one billion data points; While the same space for the Verkle tree is limited to 150 bytes. In fact, Verkle tree uses a proof system called “Polynomial Commitments” that depends on polynomial functions to describe the data.
To summarize, a “polynomial operation” is a proof system that, through certain cryptographic properties, allows only a small “witness” to prove large amounts of data. This operation is used to process and transfer data faster. Of course, creating this small proof requires more complex cryptographic operations compared to the Merkel tree.
What are the reasons for the importance of Merkel tree and Workel tree?
Data structures such as Merkel Tree, Patricia Merkel Tree, and Verkle Tree are used in Bitcoin and Ethereum blockchains and other digital currency networks to store and encrypt data more effectively and safely without requiring a lot of storage space. In addition, privacy and separate data storage along with transparency and verifiability are some of the other achievements of these structures for blockchain networks. Thus, in addition to reducing the volume of data, their safety and immutability are also provided by these structures.
Also, structures such as Merkel tree support Lite nodes and Simple Payment Verification (SPV). In other words, this feature allows the user to validate transactions without having to download the blockchain or even a complete block. Thus, it is possible to use a digital wallet or a light client node to send and receive transactions.
Meanwhile, the importance of Verkle trees is related to their ability to reduce the size of the proof, which can ultimately reduce the need for bandwidth. In networks like Ethereum, which are a platform for smart contracts and require continuous state change, this helps with greater scalability and more efficient consensus and faster updates.
It should be mentioned that the proof size in Verkle trees is six to eight times smaller compared to Merkel trees and twenty to thirty times smaller compared to Patricia Merkel trees in the Ethereum network, which can play a very effective role in faster and more scalable data transferability in blockchains like Ethereum.
What is the difference between the Verkle tree and the Merkel tree?
As you have probably noticed by now, Merkle and Verkle data structures, despite the similarity in structure, also have differences in terms of features and performance. One of the important differences between these two structures is related to Merkel’s proof and Werkel’s proof.
“Witness” and proof in Merkel tree include a set of “Sister Nodes”. Sister nodes are nodes that are placed in the same layer of the node hierarchy. In this case, all nodes of the tree must be included in the proof. In other words, the node being checked must have at least one node in common with its parent; But in Verkle tree, it is possible to validate the data without the need of sister nodes.
In general, a Merkel tree has a simpler structure that facilitates evaluation and updating in smaller chunks. Thus, people around the world using their digital wallets and electronic devices such as smartphones or computers can access Merkel’s root and check and process the data.
On the other hand, Verkle’s proof, despite its better performance, requires more complex codes and polynomial operations. This can make the process of calculating all the evidence in the Verkle tree at once a bit more difficult. However, this complexity of the structure will improve data transfer operations and continuous network updates, especially when running a large number of smart contracts and decentralized applications at the same time.
TotalTheclassification
In this article, we got acquainted with the Verkle tree data structure and the important role it plays in blockchains such as Ethereum. Also, we reviewed similar structures such as Merkel tree and Patricia Merkel tree and highlighted some differences of these information models. Next, we briefly explained how the Verkle tree works and pointed out its strong impact on Ethereum updates and increasing the scalability of this network.
In summary, we can say that the most prominent feature of Verkle tree is the reduction of proof size, which plays an important role in improving network throughput. In fact, the Merkel tree is instrumental in the formation of the concept of blockchain and Bitcoin, and is used for secure data encryption and validation. Verkle tree can also be considered as a powerful catalyst to increase the scalability and speed of data processing in the Ethereum blockchain.