DEFINITION of '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.

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. (See also, How Bitcoin Works.)

The Merkle tree is useful because it allows users to verify a specific transaction without downloading the whole blockchain (over 130 gigabytes at the end of August 2017). 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 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
  1. Merkle Root (Cryptocurrency)

    A Merkle root contains information about every single transaction ...
  2. Proof of Work

    Proof of work describes the process that allows the bitcoin network ...
  3. Nonce

    Nonce is a number added to a hashed block, that, when rehashed, ...
  4. Block Time (Cryptocurrency)

    Block time is the average time for a new block to be generated ...
  5. Application-Specific Integrated ...

    An application-specific integrated circuit (ASIC) is a piece ...
  6. Block Reward

    Bitcoin block rewards are the new bitcoins that are awarded by ...
Related Articles
  1. Tech

    How Bitcoin Works

    Miners, hashes, keys, cold storage, blocks - it's confusing. We can help you understand how bitcoin works.
  2. Trading

    Bitcoin Cash: The New King of Cryptocurrency?

    Investors are wondering if the popularity of Bitcoin Cash poses a serious threat to the Bitcoin throne.
  3. Tech

    Bitcoin Cash Set To Undergo Hard Fork

    The cryptocurrency will undergo a hard fork to enable a stable hash rate amid extreme price volatility.
  4. Tech

    Blockchain Could Make You—Not Equifax—the Owner of Your Data

    All hype aside, blockchain technology is really good at one thing: taking out the middlemen. Leaky data brokers' days may be numbered.
  5. Tech

    How Do You Mine Litecoin?

    This guide will give you a sense of the concepts in litecoin mining, an introduction to the vocabulary and suggestions for further research.
  6. Tech

    Bitcoin Cash Broke $1000: Where Will It Go Next?

    The surge in Bitcoin Cash’s mining profitability and high trade volume propelled its price to near $1,000 over the weekend.
  7. Investing

    Using Decision Trees in Finance

    Decision trees are a major tool that can be used in corporate finance and economic forecasting. Discover how binomial trees plays an integral role in pricing of interest rates.
  8. Investing

    Amazon to Sell Real Christmas Trees

    The online retail giant plans to sell and ship fresh, full-size Christmas trees this year
  9. Tech

    How Do You Mine Ethereum?

    Mining for ethereum is a profitable, essential, and oftentimes confusing process. Here's the basics of how to do it.
  10. Tech

    How Does Blockchain Work?

    Blockchain technology supports the cryptocurrency space and many other promising applications.
RELATED FAQS
  1. Is Bitcoin legal in the US?

    Learn about the legality of Bitcoin as a form of payment in the United States, as well as how it is produced and concerns ... Read Answer >>
  2. Why do Bitcoins have value?

    Performing with transactional anonymity, Bitcoin has value as a private digital currency, investment tool and social networking ... Read Answer >>
Trading Center