Merkle Tree is a binary tree often used to securely and rapidly verify the data integrity of a system or to prove that a data block is a member of a data block: .
To construct a Merkle tree, you first place the inputs at the leaf nodes (nodes without any children). From the leaf nodes up, the values of each pair of child notes are hashed together and become the values of their parents. This process repeats until the root node, called the Merkle root, is reached.
A few neat properties make Merkle Tree the ideal candidate for applications like blockchain data storage, e.g., transaction histories. Because Merkle trees only store the hashes, they are tiny and can be easily stored and transmitted over the network. Data integrity can be easily verified by comparing the Merkle root. If any change is made to any leaf, the Merkle root will change. Furthermore, you only need a set of hashes to verify that a data block is a part of the tree. E.g., to prove that is part of the tree , you only need to know the hash to reach the Merkle root. This is called the Merkle path or the authentication path.