Merkle Tree

Merkle Tree

A Merkle tree is a data structure that is used in computer science applications. The root is combined with other information (the software version, the previous block's hash, the timestamp, the difficulty target, and the nonce) and then run through a hash function to produce the block's unique hash: 000000000000000000bfc767ef8bf28c42cbd4bdbafd9aa1b5c3c33c2b089594 in the case of block #482819. In bitcoin's blockchain, a block of transactions is run through an algorithm to generate a hash, which is a string of numbers and letters that can be used to verify that a given set of data is the same as the original set of transactions, but not to obtain the original set of transactions. The Merkle root of a given block is stored in the header: for example, the Merkle root of block #482819 is e045b18e7a3d708d686717b4f44db2099aabcad9bebf968de5f7271b458f71c8. The Merkle tree allows you to verify that everything is accounted for with three hashes: given HAB, HC, HEFGH, and the root HABCDEFGH, HD (the only missing hash) has to be present in the data.

What Is a Merkle Tree?

A Merkle tree is a data structure that is used in computer science applications. In bitcoin and other cryptocurrencies, Merkle trees serve to encode blockchain data more efficiently and securely.

They are also referred to as "binary hash trees."

Breaking Down Merkle Tree

In bitcoin's blockchain, a block of transactions is run through an algorithm to generate a hash, which is a string of numbers and letters that can be used to verify that a given set of data is the same as the original set of transactions, but not to obtain the original set of transactions. Bitcoin's software does not run the entire block of transaction data — representing 10 minutes' worth of transactions on average — through the hash function at one time, however. Rather, each transaction is hashed, then each pair of transactions is concatenated and hashed together, and so on until there is one hash for the entire block. (If there is an odd number of transactions, one transaction is doubled and its hash is concatenated with itself.)

Visualized, this structure resembles a tree. In the diagram below, "T" designates a transaction, "H" a hash. Note that the image is highly simplified; an average block contains over 500 transactions, not eight.

Merkle Tree

Image by Julie Bang © Investopedia 2020

The hashes on the bottom row are referred to as "leaves," the intermediate hashes as "branches," and the hash at the top as the "root." The Merkle root of a given block is stored in the header: for example, the Merkle root of block #482819 is e045b18e7a3d708d686717b4f44db2099aabcad9bebf968de5f7271b458f71c8. The root is combined with other information (the software version, the previous block's hash, the timestamp, the difficulty target, and the nonce) and then run through a hash function to produce the block's unique hash: 000000000000000000bfc767ef8bf28c42cbd4bdbafd9aa1b5c3c33c2b089594 in the case of block #482819. This hash is not actually included in the relevant block, but the next one; it is distinct from the Merkle root.

The Merkle tree is useful because it allows users to verify a specific transaction without downloading the whole blockchain (over 350 gigabytes at the end of June 2021). For example, say that you wanted to verify that transaction TD is included in the block in the diagram above. If you have the root hash (HABCDEFGH), the process is like a game of sudoku: you query the network about HD, and it returns HC, HAB, and HEFGH. The Merkle tree allows you to verify that everything is accounted for with three hashes: given HAB, HC, HEFGH, and the root HABCDEFGH, HD (the only missing hash) has to be present in the data.

Merkle Tree 2

Image by Julie Bang © Investopedia 2020

Merkle trees are named after Ralph Merkle, who proposed them in a 1987 paper titled "A Digital Signature Based on a Conventional Encryption Function." Merkle also invented cryptographic hashing.

Related terms:

Bitcoin

Bitcoin is a digital or virtual currency created in 2009 that uses peer-to-peer technology to facilitate instant payments. read more

Blockchain : What You Need to Know

A guide to help you understand what blockchain is and how it can be used by industries. You've probably encountered a definition like this: “blockchain is a distributed, decentralized, public ledger." But blockchain is easier to understand than it sounds. read more

Encryption

Encryption is a means of securing digital data using an algorithm and a key. read more

Hash

A hash is a function that converts an input of letters and numbers into an encrypted output of a fixed length. read more

Merkle Root (Cryptocurrency)

A Merkle root contains information about every single transaction hash that ever was on a particular block in a blockchain. read more

Nonce

In blockchain technology, nonce means a number added to a hashed, or encrypted block, that, when rehashed, meets the difficulty level restrictions. Blockchain miners aim to solve the nonce. read more

Target Hash

A target hash sets the difficulty for cryptocurrency mining using a proof-of-work (PoW) blockchain system. read more