It might make more intuitive sense if you reverse the question. Suppose you've uploaded a file to AWS, let's say 1MB, but you don't entirely trust that they won't change the data on you. You're about to sell all your computers and go on a boat trip around the world with nothing but the clothes on your back and a single piece of paper, and when you get back next year, you want to retrieve that data from AWS and know for sure whether they corrupted it or not. (And, for some reason, you're ok with losing it entirely if they did corrupt it: this is error detection, not error-correction).

So before you upload it, you compute the SHA256 hash of the file, and you write down that 32-byte hash on your piece of paper. Then you upload the data, delete the local copy, and sell all your computers. A year from now, when you download it again and want to make sure AWS hasn't corrupted the contents, you hash the downloaded data and make sure it matches the hash you wrote down.

Next, suppose you're uploading a 1GB dataset. And you know that a year from now, you're only going to need 1MB of it (at a time). You don't really want to download 1000x the data just to do the validity check. So instead you split the dataset up into 1MB chunks, hash each one separately, concatenated the hashes (giving you a 32000 byte string), and do a second-level hash of that. You upload the 1GB dataset and the 32000 bytes of hashes, and you write down just the single 32 byte root hash. Next year, when you download that 1MB, you also download the 32000 bytes. You hash the 32000 bytes and compare it against the root hash that you wrote down, and then you hash the 1MB that you care about and compare it against the small portion of the 32000 bytes. That gives you a two-level tree shape.

But now suppose you've got a 1 TB dataset. That concatenated list of hashes is going to be 3210001000 = 32MB long, which is a drag, since you have to download the whole thing (to hash the whole thing) in order to validate any part of it. You can see where this is going: you introduce another level, you have 1M leaves of 1MB each, in groups of 1000, each of which produces a second-level hash, then you concatenate and hash all 1000 of those second-level hashes to get the root hash.

A full (binary) Merkle tree is the log2(N) version of this. You split the dataset up into blocks, hash those to get the leaves of the tree, hash the leaves to get half as many intermediate nodes, hash those, etc, until you wind up with a single root hash. Then you upload the dataset and all the nodes (leaves and intermediate notes), and you remember the root. Next year, you reconstruct the shape of the tree, and figure out which subset of the nodes you'll need to verify everything (basically the sibling node of the leaf you want to download, and the sibling node of their mutual parent, and the sibling of that node, etc, up to the top, where the last piece you need is the one child of the root node that isn't an ancestor of the leaf you're downloading). We called this the "uncle chain", and it will be log(N) long. Then you go to your backend store and fetch the leaf and those log(N) hashes, and re-perform the subset of the initial hashing that got you the root. Finally you have a reconstructed root, and you can compare that to the one you've been holding all year long.

In Tahoe-LAFS (https://tahoe-lafs.org), we had a metric we named "alacrity", which we defined as the number of bytes you have to fetch from your storage servers before you can deliver the first byte of decrypted and validated data to the user. The size of the leaves directly impacts the alacrity, as does the size of the uncle chain. In the linear approach (the 1MB example), the alacrity is the entire file: O(N) (really just "N"). The one-level 1000-way "tree" reduces that a lot, but the alacrity is still linear, the su...