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?
2 Answers
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.
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.
Related