How come Merkle tree is more efficient when tree branches are not stored in blockchain?

Question

Suppose we have 8 transactions in a block X as follows and we know every node's hash value of the whole Merkle tree (that is, including intermediary nodes such as 45). Then if someone claims transaction t exists in X and it's located at 6. To verify this, we only need to look up hash values at 7, 45, 0123 and hash up to the top and compare with Merkle root 01234567.

I assume (based on this) Merkle tree is faster than hashing the concatenation of TXID0 ~ TXID7 directly is because hash algorithm runs faster on small files (even run it ~log(N) times) than on a large file (i.e., concatenation of N TXIDs, N is 8 here) at one time.

But reading this post, it seems that only Merkle root and N TXIDs are stored in a block and we have to recreate tree structure every time we verify a transaction, which would actually run hash functions ~N times instead of ~log(N) times (if I was correct mathematically).

---

My questions are:

1. Does hash ~N times still faster than hash one time on N concatenated hash values?
2. Why is Merkle tree not stored? Is it due to storage consideration?

Answer 1

The speed of the hash is roughly linear in the number of bytes processed: SHA2 processes block of 64 bytes at a time, and the time taken is equal to the number of blocks processed. Computing a hashtree processes more blocks due to the intermediate levels but almost all the processing can be done in parallel unlike the linear hash which must be done sequentially.

A node only verifies a block once. For that purpose it doesn't matter much if the hash is a tree or linear though if the parallelism is exploited computing a tree hash is faster.

[And Bitcoin Core uses vector instructions to processes tree hashes in parallel for a several times speedup. It doesn't currently bother using multiple cores for that, though it could.]

A lite client, however, does not validate a whole block, it normally doesn't even fetch a whole block. Instead, it wants to know if a transaction is in a block. Here, the hash structure matters a lot. If a linear hash were used the only way to prove that a transaction is in a block to a lite client would be to send it the whole block. With a tree hash one need only send it log2(n) values and the transaction itself.

The tree isn't stored in current Bitcoin implementations because there is no operation that would really benefit from it being stored in the implementations. Proving a lite client was paid is a relatively infrequent operation and recomputing the hash tree is inexpensive. An implementation could start storing it if it had a reason to do so. TXIDs aren't stored either as they can just be computed from the transactions themselves.