Merkle And Verkle Trees In Blockchain

Have you ever wondered what these two terms mean? We’re going to talk about 2 quite popular data structures. Both of them are tree-like, but it doesn’t mean they are similar! Let’s see what they look like and how much each type differs from one another. 

Here and further we will often mention the terms Merkles and Verkles for Merkle trees and Verkle trees as it follows to lighten the text. Let’s go! 

The definition of a Merkle tree

It’s usually named a hash tree. It has many leaves (nodes) called with a crypto hash of a data block. Every branch is tagged with the hash owned by its children nodes. 

To simplify, try to imagine a real tree — for instance, an apple tree — with branches, leaves and strong roots. The lowest nodes are little green leaves attached to roots (upper hashes) by branches, the medium nodes. This kind of data arrangement was invented and patented by Ralph Merkle in 1979. He’s a computer scientist who has also developed public-key cryptography.

Along with security, Merkles deliver wholeness and incontrovertibility for blockchains which are usually built on such trees, consensus algorithms and, of course, cryptography. Let’s get acquainted with this type of structure: 

Merkles effectively confirm if the info is correct whilst shrinking the memory demands of verification. If compared to other various structures, trees need less space on the disc. It’s considered as the core feature of Merkles.   

Cool fact — Vitalik Buterin’s blockchain also utilizes it! Its name is Merkle Patricia trie. It’s confirmed via cryptography and supplies a structure employed to store key and value bindings.  

Merkle tree use cases

Besides blockchain technology, Merkles are often used in popular software apps like Git and Amazon DynamoDB. 

The Merkle trait of identifying state changes is useful when validating the accuracy of data, as computing the inverse of a hash is computationally infeasible. The Merkle tree's properties are suitable for applications where a malicious user must be stopped from changing data.

Git 

Git registers any change in a file as an entirely new file. It stores the content of the file with a filename of SHA1(fileContents). Let's say this SHA1(fileContents) = x. If x already exists in the Git file system, it doesn't go ahead and create it. This avoids unnecessary recreations when metadata about a file is changed.

When a file is modified in Git, it generates a new file, as well as all its changed parents. The root subsequently changes. It's like a branch of a Persistent data structure. If you want to go back a commit, you utilize the root of the previous commit, which still leads to the old file. 

Thus, Git takes snapshots of every point of change in the project. Perfect for a version control system.

Amazon DynamoDB

It is also useful to discover the points at which the data has changed, using a Merkle Tree. Amazon DynamoDB utilizes Merkles to reduce entropy (anti-entropy technique) when a new node is added to the Dynamo DB cluster.

When copying a range assigned to a node, we have to allow concurrent updates to keep the service available. But when the migration is in progress, concurrent updates lead to stale data in the destination node.

So we copy the data range multiple times. When there is no change in the two nodes, we declare the destination node as consistent. If we want this to happen as fast as possible, we try to minimize the number of copy iterations. 

The definition of a Verkle tree 

This tree gives you a chance to arrange plenty of data and make a short “witness” of each bit of information that could be proven by somebody with full access to the root. 

Verkles appeared much later than Merkles. They have been created in 2018 by John Kuszmaul, who’s a student in MIT’s PRIMES high school research program. Verkle trees aren’t studied that well yet. However, we know that every single node owns 1 of traits: 

1. The node is empty.
2. It appears as a leaf node with a key and value.
3. It’s an intermediary node which has a specified quantity of “children”.

Another significant characteristic of Verkles is their proof-size effectiveness. This kind of structure needs no more than one hundred fifty bytes to generate a proof for a tree with a bln data points. We might compare it to Merkles — they require one kB. To specify data, Verkles have a special proof scheme called “Polynomial Commitments”. 

Here’s how a Verkle tree looks like:

Also, let’s mention that Verkle trees are more extensible than Merkle ones. This is the huge plus of Verkles and the sole significant distinction between 2 kinds of trees’ elements. 

What’s the difference?

We can outline a few additional unique features of our trees. These properties are especially noticeable in delivering the proofs for both of them:

1. In a Merkle tree, the proof has to carry all the nodes with any parent node in common with the node you are trying to prove. In a Verkle, you solely provide the route — also, there’s no need to include sister nodes.
2. Verkles seem to be more productive in size, which, as mentioned before, is the important difference between two structures.  
3. Thanks to the tree appearance, Merkle proofs are simple to edit in part whilst the Verkle’s Polynomial Commitments require a total modification. 
4. With Merkle, users all around the world are able to send, get and confirm transactions with cryptocurrency wallets that could operate on a PC or mobile phone. With Verkle you can substitute a vector commitment for the hashes in a Merkle tree, growing the efficiency of wider branching factors.

Conclusion

We have discussed two types of data structures to show that both of them have their own advantages and might be utilized in different cases. Why are these trees so essential for blockchain? Merkle trees are used in Bitcoin to encrypt the data in a more secure and effective way. Verkle trees give an opportunity to apply lesser proof sizes. It’s especially crucial for Ethereum 2.0, which is switching to the Verkle trees in its Verge update, mentioned by Vitalik Buterin during the presentation in July.  

If this article was interesting, and what’s more important, useful for you, make sure to stay tuned with SimpleSwap Blog to learn more about cryptocurrencies and blockchain with us!