Merkle Tree (ELI5): a way of packaging data such that you are able to quickly and efficiently verify huge chunks of information it stores.
Primarily found in cryptography, a Merkle tree (or hash tree) is data structured as a tree in which every leaf node is labeled with the cryptographic hash value of a data block, and every non-leaf node is labelled with the cryptographic hash of the labels of its child nodes. Hash trees allow efficient and secure verification of the contents of large data structures.
Merkle trees make extensive use of one way hashing and are established by hashing a hash’s corresponding hash together and climbing up the tree until you obtain the root hash which is or can be publicly known.
Technical Note: Demonstrating that a leaf node is a part of a given binary hash tree requires computing a number of hashes proportional to the log of the number of leaf nodes in the tree.
Merkle Tree: Example of Hashing Transactions
In the Merkle Tree above, each block-level represents a higher order of hashing stemming from a transaction (T0-T7). For each block-level above the original transaction, the subsequent hash value (H), is passed through a hash function until reaching the highest block-level represented as the combination of all the preceding hashes (H01234567).
The lowest-level hash values are referred to as leaves — containing the hashed value of the transaction (T) associated with the leaf. The resultant hashing of leaves and their subsequent hashes, levels 3 and 4, are referred to as branches (or nodes). Finally, the highest block-level, the Merkle Root, stores the summary of all of the transaction data as a singular value.
