Blockchain Semantics Insights
Business Case | Deep Tech | Announcements | Blockchain Glossary |
What is the Blockchain data structure? What is a Merkle Tree?Jan. 9, 2018, 2:39 p.m. GMT
Merkle Tree is a data structure used by several Blockchains. Every block stores all the transaction data it has in the form of a Merkle tree. In this data structure, hashes of child nodes are combined together into the parent node’s header. This technique of combining the child nodes’ headers and adding it to the header of the parent node continues iteratively till we reach the final node, right at top, the root node. Thus, the root node will contain information about all of the nodes present in the tree.
It is theoretically possible to make a Blockchain without Merkle trees. You could simply create giant block headers that directly contain every transaction. But doing so would pose huge scalability challenges.
The most common and simple form of Merkle tree is the binary Merkle tree; it can be depicted as shown:
Image courtesy: Wikipedia
Let us discuss how this tree is generated. Suppose there are 4 transactions L1, L2, L3 and L4 in a block.
First- All the transactions of the block are individually hashed. For example, L1 is hashed to hash 0-0.
Then the combination of hash 0-0 and hash 0-1 is hashed and stored into a parent node. Same procedure is repeated for other nodes.
And lastly, combination of hash 0 and hash 1 is hashed and stored in its parent node and this is, so to say, the final node of this Merkle tree. It is called the root node or simply the Merkle root. This Merkle root along with previous block header hash, a time-stamp and a nonce is used to generate the block header.
To summarise, hash of all the transactions in a block is stored in the the Merkle tree. So when a node wants to verify if any transaction is changed, the node will only have to build the Merkle tree using all the transactions of block. This makes it very simple to validate or invalidate a transaction. Thus, Merkle tree helps maintain security in Blockchain.
To learn more about Merkle tree use of Merkle tree in block and block structure, pls visit Blockchain and Bitcoin Certification by Blockchain Semantics.