Merkle Tree — What is it and why use it?

It is one thing to invest in cryptocurrency and blockchain technology, but it is another to fully understand the details of how blockchain works. In many blockchains, including the aelf ecosystem, one piece of technology that is being incorporated into the network is the Merkle Tree. Although there are many parts to this network, the Merkle Tree is one important aspect to understand when identifying how we plan to ensure efficiency and reliability in the verification process.

The Merkle Tree is not some new amazing discovery, but it is a tested and true system which is used quite widely not just in blockchain, but any trust-less or peer-2-peer environment. In fact, this concept dates back to 1979, before blockchain was even an idea. It is named after computer scientist, Ralph Merkle.

A Merkle Tree, in simple terms, takes lots of data, compresses it down into one simple string of characters which can prove the verity of the data held within, without revealing what that data is. Similar to a compressed file (.ZIP or .RAR), which if named correctly according to a certain standard, a user can recognize the content without having to decompress and open the contained files. This string of characters (title) is called a hash. Hashing is a one-way function, which means if you put in the same data you will always get the same hash, but you cannot take that hash and extract the original data.

The ‘tree’ concept is a common idea throughout science and it refers to a structure which includes parents and children branching off each other. In this case it is an upside down tree in the sense that you start with all the leaves (Transactions/blocks) and work back to the one parent hash (Merkle Root). As seen in figure 1.1, we start with transactions which get hashed twice before they get included into the Merkle Tree. We might have transactions 1–100 hashed into block L1, 101–200 hashed into block L2, 201–300 into block L3, 301–400 into block L4. These are then hashed into the bottom branch of the tree. For example, block L1 is hashed into hash 0–0.

This diagram shows what we call a binary tree. This means that each parent can have two children branches maximum. Technically, you can increase this but binary trees are the most common. Once we have Hash 0–0 and 0–1, this gets hashed into its ‘parent’ hash (Hash 0). This is continued until we get to the top hash which is called the Merkle Root.

This process has multiple benefits including security, speed and efficiency. By using this process to condense data, it can be verified very quickly without revealing any actual data by matching up each hash with the Merkle Tree Root. Due to the complexity of the merkle tree created in correlation with the decentralized aspect of blockchain, it makes it very difficult to alter the data found within these hashes.

The speed of a network can be increased simply by using this technology. Instead of sending files over the network to be verified and then sent back, one computer only needs to send the hash (remember this is only a string of characters) which can be very quickly verified. If there is a discrepancy, then hashes of the subtrees are requested until the culpable block is found and altered as necessary. This is much faster than searching an entire file for one error. Of course, this is also a much more efficient use of resources.

Not in the traditional sense. Normally the Merkle Tree will be employed within one blockchain. Aelf will be using the Merkle Tree to control the interoperability between all the sidechains. Each side chain will create its own Tree and submit the Merkle Root to be contained within the Mainchain.

Should Sidechain A want to confirm some data that is from Sidechain B, Sidechain A will approach the Mainchain and ask to verify the data, comparing it with the Merkle Root stored there. You could almost relate the Mainchain to an archive which each Sidechain will go to for data verification.

This concept is quite unique and will improve the verification process greatly. It is an efficient process to create an environment for cross-chain interoperability. It allows for private and public chains to talk to each other and verify data without any privacy breakdown.

Before I finish I want to clarify one point. This Merkle Tree is not the same as the Sidechain ‘tree’ used by the aelf network to break down sidechains. The Merkle Tree is used to store and verify data with the mainchain and with other sidechains. A sidechain ‘tree’ may be made up of multiple sub-chains creating its own tree-like structure where each chain (branch) performs a specific use case. When one of these chains becomes too large to manage, it can be further broken down into multiple chains.

The merkle tree is just another feature of the aelf ecosystem which is not only unique, but also revolutionizing the way a Blockchain network functions. For more unique components of aelf, see here.