Merkle Tree: Here’s Why Optimistic Rollups Will Be Safe
Optimistic Rollups appeared in the Jakarta update. They are not on the mainnet yet, but on the testnet, the developers are already actively working with them. Meanwhile, we want to talk about the technology without which we wouldn't have rollups: Merkle’s tree and proofs.
The announcement of Merkle’s proofs went unnoticed: they were given one line in the Jakarta update description and one page in the documentation about the proof format. So we’ll tell you everything in order.
What Is Merkle’s Tree
The basis of the Merkle tree is the hashing of data. Hashing is the transformation of information using a special algorithm, which results in a unique string of a certain length. The result (hash or checksum) will be the same if the same information is hashed repeatedly. If a single bit of information in the file changes, the hash will also change.
Hashing is used to verify the authenticity of received data. For example, files on torrent trackers often come with a checksum of the original. When a user downloads it to their computer, they can calculate the checksum of their copy and compare it with the original. If they are the same, the file has been downloaded without errors.
When downloading a large number of files, it would be inefficient to count and compare the checksums of each fragment. It is easier to collect the data in one place, for example in an archive, and hash it. By comparing hashes of these two archives you can understand if all the files were downloaded correctly. But if the hashes do not match, you will have to decompress the archive and still hash the fragments separately and compare the results with the hashes of the original files in order to find the broken fragment.
The most efficient way to prove that all fragments correspond to the original is to recursively hash them in pairs. First hash the individual fragments, then the sum of hashes of neighboring pairs, and repeat it until the hash of the whole set is obtained. This structure is called a hash tree or Merkle tree. If one fragment is corrupted, then it is possible to quickly identify it by comparing hashes in each subsequent branch.
Merkle’s tree consists of three elements:
- Leaves: the original data fragments (DATA A, DATA B…);
- Branches or tree nodes (not to be confused with blockchain nodes): hashes of previous pairs of leaves or branches (ABC, BDE);
- Root: hash of the whole tree (DFA).
Nodes in the blockchain protocol store all blocks and their hashes in a Merkle tree. The root corresponds to the current state of the entire blockchain, i.e. all users’ balances are hashed in it. In Tezos, it is called Context Hash, and bakers include it in the header of each block.
With Context reconciliation, nodes can quickly confirm or deny that the baker used correct data about past transactions in the blockchain when creating the block.
But this is a simplified explanation. In reality, Tezos structure is more complex and includes a large number of branches to optimize search and data handling.
Why Merkle Tree Is So Important for Optimistic Rollups
A Merkle tree can be used to quickly prove that a piece of data is included in a given data set without revealing all the other pieces. This is known as the Merkle Proof.
For example, to prove that a transaction was actually included in block C, a node provides a description of the path from transaction C to the root of the tree for verification. It does not need to disclose the contents of other elements (Blinded Nodes or hidden nodes), just provide the corresponding hashes. If everything is correct, when the path is repeated, the one who checks it gets the same root.
The Tarides team calculates that such a Merkle proof for 100 transactions would fit in 46KB, while the “real” proof with all transactions and user balances would take 3.4GB.
Merkle’s proof is necessary for rollups to work because it allows an L1 node to verify the validity of transactions in an L2 chain in seconds, even if the L1 node does not have a full L2 chain. Or conversely, prove that the transaction in the L2 chain is wrong, and the rollup operator is trying to fool everyone.
This is how Merkle’s tree will make rollups safe and honest for users.
Subscribe and never miss updates from the world of Tezos: