File integrity checking: why use a hash tree instead of a hash list?

Question

File sharing systems sometimes use the likes of a Tiger Tree Hash to check the integrity of a file as it is downloaded.

Hash trees in general are useful to check integrity of the tree leaves without downloading the full tree, instead needing only the root and tree branch that contains the interesting leaf (plus necessary stubs in the branch).

My question is: why use a tree at all for file integrity checking when what one presumably wants is to download the full file? A plain hash list (a hash per file block + a hash of the list) would have been trivial to implement and manage, and only be marginally bigger than the tree. The list's hash still works as well as the root hash in the tree case.

In fact I only know one file sharing client that allows one to select parts of a file to be downloaded, so the whole use case looks atypical.

So, is this a case of early, marginal, mostly unused optimization? Or am I missing something?

Answer 1

Looks like the question itself needs some correction. My characterization of what happens in "file sharing" was too simplistic, and adding detail to it explains the matter.

eDonkey/eMule in the 00's did use Tiger Tree Hashes, which are a kind of Merkle trees.

But by then, looks like BitTorrent's torrent files only contained a simple list of hashes corresponding to the blocks of the torrented file. The number of blocks was fixed, but their size could be adjusted. This made for big torrent files, which stressed web servers; but minimizing torrent file size forced big file blocks in the torrent, which was also bad.

So around 2009, BEP 30 introduced a way to reduce the size of the torrent files AND to reduce the size of the hashed file blocks: the new style of torrent file contains only the root of a Merkle tree (so its size is minimal, relieving the web server), and the tree is created internally by seeders. The pieces of the tree needed for each block transmission are sent in-band, making it self-contained and verifiable with the root.

The key point is that the tree is not transmitted by itself, but generated by seeders and transmitted piecewise as needed. This piecewise transmission probably generates a lot of redundancy, but this redundancy is in the P2P protocol, so this inefficiency is much less important than the relief to the web server.

A hash list as the one I described in the question might be workable as a substitute of the tree, but would cause even greater inefficiency in the protocol, and would need storage of the whole list of hashes (linear to the size of the torrented file) even if the client is not interested in some blocks.