Why does each block store a Merkle root?

Question

I understand how a Merkle root is calculated and stored in the block. But how do miners verify a transaction using the Merkle root?

Here are 18 conditions that verify a transaction. None of them uses Merkle root.

Answer 1

Merkle roots do not verify transactions, they verify a set of transactions. Transaction ID's are hashes of the transaction, and the Merkle tree is constructed from these hashes. It means that if a single detail in any of the transactions changes, so does the Merkle root. It also means that if the exact same transactions are listed in a different order, the Merkle root will also change.

So the Merkle root is cryptographic proof of which transactions are in the block, and which order they are in. It provides a convenient piece of information to be included in the block header which is then hashed and included in the next block header. Without the Merkle root in the block header, we would have no cryptographic proof of which transactions are included in a block, nor proof that their contents haven't been tampered with.

Using a Merkle tree is preferable over a hash chain or a hash of concatenated transactions because it allows for a much quicker and simpler test of whether a particular transaction is included in the set. For more details, see the section on Merkle trees in the Developer's Guide.

Answer 2

Merkle roots are stored in Bitcoin block headers so as to enable efficient membership proofs for transactions in a block, which are necessary for Simple Verified Payment verification (SPV) nodes that only store block headers and not block contents.

It is misleading to say that "Without the Merkle root in the block header, we would have no cryptographic proof of which transactions are included in a block, nor proof that their contents haven't been tampered with."

We can always just hash-chain transactions together and store a hash-chain root in the block header, for example. (Or, we can just concatenate all TXIDs together and store that hash in the header.)

However, that would not be as efficient: membership proofs with respect to a hash chain are O(n) when there are n transactions in the chain, versus O(\log{n}) proofs w.r.t. a Merkle tree.

Much later edit: I suppose no one actually answered your question: "But how do miners verify a transaction using the Merkle root?".

As I understand your question, the answer is they don't use the Merkle tree. Miners, just like full nodes on the P2P network, receive new transactions from other full nodes and verify them by checking their digital signature and that they spend valid coins (pretty much as described in your link). Merkle trees are not involved at this point. Later on, the miner takes all the verified transactions and creates a Merkle tree on top of them. As more transactions come to the miner, the miner verifies them and adds them to the Merkle tree.

Why are things added to the Merkle tree by the miner? Again, as I describe above, the only reason we have Merkle trees is so SPV nodes can efficiently verify that miners verified the transactions in the block.

There is one scenario one might describe as "miners verify a transaction using the Merkle root" though I wouldn't use that phrasing: When a miner hears about a new block, it will want to verify its validity (recall that miners don't want to extend an invalid chain). As part of the verification, the miner needs to make sure that the Merkle tree was correctly computed over the TXIDs. However, this does not imply transactions were verified: the miner still has to verify transactions individually as described in your link. One consequence of this verification is SPV security for free: When an SPV node sees a Merkle membership proof for a transaction, they can assume it's valid (because SPV nodes assume miners verify blocks).

Answer 3

Merkle Trees are useful for checking set membership in a distributed system. First, a brief algorithmic description:

Scenario: Alice, the verifier, is in possession of a digest of a set S (i.e. but not its elements), an element x. She wants to know if x belongs to S. If the answer is yes, she would like to see a proof. Since Alice does not have S, she asks Bob, the prover. Bob presumably has all the elements of S.

Simple Solution: Bob checks whether x is in S and if so returns the entire set S to Alice as a proof. Alice, can verify that x is truly in S by recomputing the digest of S and match it against the one she has.

Merkle Solution: Bob checks x is in S and if so returns log n hashes of the internal nodes that the are siblings of the nodes on the path from x to the root in the Merkle tree of S. Alice can, using the these hashes, can reconstruct the Merkle root and compare it against the hash that is in her possession.

Note that

• In the bitcoin original paper, these trees are mentioned as a way to reclaim disk space: Continuing with the example above, Bob realizes that certain elements from S became inactive (e.g. fully spent transactions in a block), ones that Alice will never ask for membership. Bob can safely delete them, as long as he stores the relevant portion of the Merkle tree that concern the active/unspent transactions. In bitcoin, this does not affect the block descriptor as the Merkle Root would be part of every Merkle Path and hence it is intact. Thus, deleting obsolete transactions does not alter the integrity of the blockchain. On the other hand, naïvely, storing a hash of all the transactions from the block will "freeze" the block from any future deletions.

• In both solutions, it is cryptographically intractable for Bob to make up a proof, if he is not in possession of the elements of S because digests are one-way functions.

• Alice, could be a client, who might not want to store the entire set for space considerations.

• In the first solution, the entire set S needs to be transmitted, though Alice needs to perform just one hash.

• However, the Merkle solution is exponentially superior when it comes to communication as only log n hashes are transmitted from the prover to the verifier, but Alice needs to perform log n hash computations. Computing hash digests is fast, hence Merkle Trees have found applications here.

Answer 4

Merkle root is not used to verify the integrity of transactions in block, but not to verify the transaction itself.

If any Transaction is changed the merkle root changes its value. So to verify the integrity of a group of transactions we use Merkle root.

This might help What Is A Merkle Tree