Merkle tree vs hash list

Question

What is the advantages of using Merkle trees over Hash lists? A hash list is a 2-level structure, Merkle tree is log n - level structure. Both can be used to verify if one of the nodes has changed. Hash list will accomplish this faster. So why ever use Merkle trees?

Enslave

Answer 1

But the hash list doesn't accomplish this faster. Say that it's expensive to acquire the hash tree or items from the list: you have to download them from potentially untrusted sources. Both the connection speed and cost of verification make acquisition of the whole dataset at once difficult.

Instead, if I get the top node of the tree from someone I trust, then I can get the two subtrees from untrusted sources and still verify authenticity. And so on, recursively.

Similarly, with the hash tree in hand I can grab chunks of data from multiple untrusted sources and verify that subsets of my final assembly are authentic without having to download the whole thing.

The alternative is downloading, say, an 800MB file, hashing it, finding out it's bad, and having to download the whole file again.

Trader

As Richard said, focus on the index, not the whole tree implementation. Merkle tree is to find a root hash that validates everything while constructing it, not after you search for it. – Rakes

I'm confused by your answer. BitTorrent uses what I would call a "list of hashes". You can obviously download data with BitTorrent from multiple untrusted sources. When one downloaded block is bad, you don't have to download the whole file again - just the block. You could also just download a part of the file. – Barrack

Answer 2

Plus, the Merkle trees can be pruned if the data grows and old data is not required.

For example, in a blockchain, all the transactions are stored in Merkle trees. If there is a spent transaction, we can prune it so that the Merkle root stays the same, but the size of the tree decrease.

Hickie