{"id":15074,"date":"2017-09-14T12:02:19","date_gmt":"2017-09-14T12:02:19","guid":{"rendered":"https:\/\/www.techopedia.com\/definition\/merkle-tree\/"},"modified":"2023-09-11T15:31:48","modified_gmt":"2023-09-11T15:31:48","slug":"merkle-tree","status":"publish","type":"definition","link":"https:\/\/www.techopedia.com\/definition\/32919\/merkle-tree","title":{"rendered":"Merkle Tree (Blockchain Hash Tree)"},"content":{"rendered":"

What is a Merkle Tree?<\/span><\/h2>\n

A Merkle tree, also known as a hash tree, is a data structure used in cryptography<\/a>, blockchains<\/a>, and some cryptocurrencies<\/a> to verify the integrity<\/a> of data elements within a larger data set.<\/p>\n

Merkle trees consist of blocks of data, each of which is converted into a unique hash<\/a>. The individual hashes are then paired and hashed again, a process known as concatenation<\/a>. This process continues until only a single hash, the Merkle root, remains.<\/p>\n

The root provides a single point of reference for the entire dataset.<\/p>\n

Techopedia Explains<\/span><\/h2>\n

Tree structures are hierarchical data structures<\/a> that have a parent-child relationship between nodes.\u00a0Over time, putting a tree’s roots at the top of a diagram has become a standard way to represent tree structures in computer science<\/a>.<\/p>\n

The reason for the upside-down orientation can be attributed to historical conventions in diagramming. For example, many hierarchical representations, like organizational charts, are naturally read from top to bottom.<\/p>\n

\"What<\/p>\n

How Merkle Trees Are Created<\/span><\/h2>\n

Merkle trees are constructed using cryptographic hash functions that convert input data into fixed-size character strings called hashes. Each hash in the tree represents a specific data element or a block of data elements.<\/p>\n

As the tree is built upwards from the base (leaf level of the tree), each subsequent hash represents a combination of the parent\u2019s children hashes, until the topmost hash, the Merkle root, effectively represents the entirety of the input data.<\/p>\n

To construct a Merkle tree, the entire dataset is first divided into smaller segments called blocks. If there isn’t an even number of blocks, the last block is duplicated to achieve parity. Each block is then assigned a hash, which becomes a leaf node on the tree.<\/p>\n

To establish the tree\u2019s hierarchy, two neighboring leaf node hashes are combined (concatenated). The concatenated pair is then hashed to produce a parent node that resides above the two original leaf nodes.<\/p>\n

The process of pairing and hashing continues layer by layer, moving up the tree until only one hash remains at the top. The final hash, known as the “Merkle root” or “root hash,” summarizes the entire dataset.<\/p>\n

How Merkle Trees Are Used For Data Verification<\/span><\/h2>\n

Merkle trees allow specific data items that are part of a large dataset to be verified quickly and efficiently by inspecting a subset of the tree\u2019s hashes. Essentially, the process involves checking the path from the data block in question to the Merkle root.<\/p>\n

Here is a simplified breakdown of the verification process:<\/p>\n