Return to Answer

You haven't specified what security properties you want, but let's say it's random oracle indifferentiability of the hash function given an underlying short-input hash function $H$ like SHAKE128-256, which serves for preimage resistance, second-preimage resistance (and therefore forgery detection), and collision resistance. (This also works if you randomize $H$ and use $H_r$ instead, like KMAC128, which obviates any need for collision resistance even in signature applications.)

You haven't specified what security properties you want, but let's say it's random oracle indifferentiability of the hash function given an underlying short-input hash function $H$ like SHAKE128-256, which serves for preimage resistance, second-preimage resistance, and collision resistance (and therefore forgery detection). This also works if you randomize $H$ and use $H_r$ instead, like KMAC128, which obviates the need for collision resistance.

Handling all the fenceposts in non-power-of-two lengths, or extending to radix $r > 2$ with a total transmission cost of $|c| n + |H| (r - 1) n \log_r n$ bits, is left as an exercise for the reader.

Exercises for the reader.

• Handle all the fenceposts in non-power-of-two lengths.
• Extend to radix $r > 2$ with total transmission cost of $|c| n + |H| (r - 1) n \log_r n$ bits.
• Generalize to unbalanced Merkle trees, e.g. backwards SHA-256 if you want to download only in start-to-end order. What costs does this restriction on order save?

What does this cost? Let $|c|$ be the maximum chunk size, say 64 KB or 1 MB, and $|H|$ the hash size, typically 256 bits.

• The overhead you must store is a total of $2^{\ell + 1}$ hashes (one for each chunk, and an additional one for each node in the tree) costing $|H| 2^{\ell + 1}$ bits of storage.
• The overhead you must transmit alongside each chunk is $\ell$ hashes, if you don't optimize it away, so the total number of bits transmitted is at most $2^\ell (|c| + |H| \ell)$.

Here are some example data volumes to get some perspective for how much this costs:

\begin{equation} \begin{array}{rrrrrr} \text{file size} & \text{$|c|$} & \text{$|H|$} & \text{hash storage} & \text{total tx} & \text{tx overhead} \\ 1\,\text{MB} & 1\,\text{KB} & 32\,\text{B} & 64\,\text{KB} & 1.31\,\text{MB} & 31.25\% \\ 1\,\text{MB} & 64\,\text{KB} & 32\,\text{B} & 1\,\text{KB} & 1.002\,\text{MB} & 0.20\% \\ 1\,\text{GB} & 64\,\text{KB} & 32\,\text{B} & 1024\,\text{KB} & 1.007\,\text{GB} & 0.68\% \\ 1\,\text{GB} & 256\,\text{KB} & 32\,\text{B} & 256\,\text{KB} & 1.001\,\text{GB} & 0.15\% \\ 1\,\text{GB} & 1\,\text{MB} & 32\,\text{B} & 64\,\text{KB} & 1.0003\,\text{GB} & 0.031\% \end{array} \end{equation}

Handling all the fenceposts in non-power-of-two lengths, or extending to radix $r > 2$ with a total transmission cost of $2^\ell \bigl(|c| + \frac{r - 1}{\log_2 r} |H| \ell\bigr)$ bits, is left as an exercise for the reader.

What does this cost? Let $|c|$ be the maximum chunk size, say 64 KB or 1 MB, $|H|$ be the hash size, typically 256 bits, and $n = 2^\ell$ be the total number of chunks.

• The overhead you must store is a total of $2n$ hashes (one for each chunk, and an additional one for each node in the tree) costing $2 |H| n$ bits of storage.
• The overhead you must transmit alongside each chunk is $\ell = \log_2 n$ hashes, if the server does nothing to avoid resending hashes the client already has, so the total number of additional bits transmitted for hashes alongside the $n$ chunks is at most $|H| n \log_2 n$.

Thus, the total number of bits stored is $|c| n + 2 |H| n$ and the total number of bits transmitted is $|c| n + |H| n \log_2 n$.

Here are some example data volumes to get some perspective for how much this costs:

\begin{equation} \begin{array}{rrrrrr} \text{file size} & \text{$|c|$} & \text{$|H|$} & \text{hash storage} & \text{hash tx} & \text{tx overhead} \\ 1\,\text{MB} & 1\,\text{KB} & 32\,\text{B} & 64\,\text{KB} & 320\,\text{KB} & 31.25\% \\ 1\,\text{MB} & 64\,\text{KB} & 32\,\text{B} & 1\,\text{KB} & 2\,\text{KB} & 0.20\% \\ 1\,\text{GB} & 64\,\text{KB} & 32\,\text{B} & 1024\,\text{KB} & 7168\,\text{KB} & 0.68\% \\ 1\,\text{GB} & 256\,\text{KB} & 32\,\text{B} & 256\,\text{KB} & 1536\,\text{KB} & 0.15\% \\ 1\,\text{GB} & 1\,\text{MB} & 32\,\text{B} & 64\,\text{KB} & 320\,\text{KB} & 0.031\% \end{array} \end{equation}

Handling all the fenceposts in non-power-of-two lengths, or extending to radix $r > 2$ with a total transmission cost of $|c| n + |H| (r - 1) n \log_r n$ bits, is left as an exercise for the reader.