You've asked for a way to hash a file into a short string $h$ so that given a partial download $c'_0 \mathbin\| c'_1 \mathbin\| c'_2 \mathbin\| \cdots \mathbin\| c'_{i-1}$ of the file that should start with $c_0 \mathbin\| c_1 \mathbin\| c_2 \mathbin\| \cdots \mathbin\| c_{i-1}$ but may have been modified in transit, you can compute some verification function $f(h, c'_0 \mathbin\| c'_1 \mathbin\| c'_2 \mathbin\| \cdots \mathbin\| c'_{i-1})$ to tell you whether this partial download is good or not.
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.
Here is a slight variation:
- The client will download, alongside each chunk $c_i$, a small set of additional hashes $a_i$ that can be used together with $h$ to verify that $c_i$ is correct.
- The adversary may tamper with the chunk $c_i$ and the additional hashes $a_i$, replacing them by $c'_i$ and $a'_i$; we assume only that the client is given a hash of the complete download, $h$, that is known to be good.
- We will define a verification function $F(h, c'_i, a'_i)$ which returns 1 if $c'_i = c_i$ and $a'_i = a_i$, that is if the data were unmodified in transit, and 0 with high probability under any forgery attempt. ($F$ is defined on chunks, not on prefixes of the file, so it doesn't actually matter which order you download them in.)
In this slight variation, the original verification function $f(h, c'_0 \mathbin\| c'_1 \mathbin\| \cdots \mathbin\| c'_{i-1})$ will be replaced by
\begin{multline}
f\bigl(h, (c'_0, a'_0) \mathbin\| (c'_1, a'_1) \mathbin\| \cdots \mathbin\| (c'_{i-1}, a'_{i-1})\bigr) \\
= F(h, c'_0, a'_0) \mathbin\& F(h, c'_1, a'_1) \mathbin\& \cdots \mathbin\& F(h, c'_{i-1}, a'_{i-1}).
\end{multline}
Transmitting the additional hashes is not likely to be an onerous burden: The number of additional hashes for each chunk is logarithmic in the length of the file, the size of the hash can be a tiny fraction of the size of a chunk (say, 32 bytes vs. a megabyte), and most likely, the client will be downloading, e.g., an HTTP header alongside the chunk $c'_i$ anyway, not to mention TCP and IP headers and ethernet frames and any other encapsulation, like tunnels and VPNs, that may happen on the network anyway.
Similarly, storing the additional hashes on the server is not likely to be an onerous burden either: Your file system almost certainly stores various metadata alongside each file anyway, including its modification times, the locations on disk where its data are stored, directory entries pointing to it, etc.
How does this work?
Hash computation. Before anyone can download the file:
- On the server, split the full file up into chunks $c_0, c_1, c_2, \dots, c_{2^\ell - 1}$.
- On the server, compute the hashes
\begin{align}
h_{0,0} &:= H(0, 0, c_0), \\
h_{0,1} &:= H(0, 1, c_1), \\
h_{0,2} &:= H(0, 2, c_2), \\
\vdots \\
h_{0,2^\ell - 1} &:= H(0, 2^\ell - 1, c_{2^\ell - 1}).
\end{align}
These are the leaves of a Merkle tree.
- On the server, compute the hashes
\begin{align}
h_{1,0} &:= H(1, 0, h_{0,0}, h_{0,1}), \\
h_{1,1} &:= H(1, 1, h_{0,2}, h_{0,3}), \\
h_{1,2} &:= H(1, 2, h_{0,4}, h_{0,5}), \\
\vdots \\
h_{1, 2^{\ell-1} - 1} &:= H(1, 2^{\ell-1} - 1, h_{0, 2^\ell - 2}, h_{0, 2^\ell - 1}).
\end{align}
These are the first level of the Merkle tree above the leaves.
- On the server, compute the hashes
\begin{align}
h_{2,0} &:= H(2, 0, h_{1,0}, h_{1,1}), \\
h_{2,1} &:= H(2, 1, h_{1,2}, h_{1,3}), \\
h_{2,2} &:= H(2, 2, h_{1,4}, h_{1,5}), \\
\vdots \\
h_{2,2^{\ell-2} - 1} &:= H(2, 2^{\ell-2} - 1, h_{1,2^{\ell-1} - 2}, h_{2,2^{\ell-1} - 1}).
\end{align}
- Repeat, combining two hashes at a time.
- At the end of this process, the server will have a hash $h := h_{\ell,0}$. This is the root of a Merkle tree, which is also a hash of the original data $c_0 \mathbin\| c_1 \mathbin\| c_2 \mathbin\| \cdots \mathbin\| c_{2^\ell - 1}$. Share the root hash $h = h_{\ell,0}$ of the Merkle tree first. For example, you might transmit it on another channel (like how a .torrent file is shared separately from the pieces), or the server might digitally sign it with a long-term key pair whose public key the client knows a priori.
Download process. When the client wants to download the $i^{\mathit{th}}$ chunk $c_i$, after getting the known-good hash $h$ of the file:
- The server sends a set $a_i$ of additional hashes alongside $c_i$, $$a_i := (h_{0,i \oplus 1}, h_{1,\lfloor i/2\rfloor \oplus 1}, h_{2,\lfloor i/2^2\rfloor \oplus 1}, \ldots, h_{\ell - 1, \lfloor i/2^{\ell - 1}\rfloor \oplus 1}).$$ These are the sibling hashes of a path down the Merkle tree—for the subtrees that do not have $c_i$ in them. Here $\oplus$ means xor; that is, we are toggling between the even- and odd-numbered hash indices.
- The client receives a putative chunk $c'_i$ and the putative hashes $a'_i := (h'_{0,i \oplus 1}, \ldots)$, which may be the correct chunk $c_i$ and the correct hashes $a_i = (h_{0,i\oplus 1},\ldots)$ or may have been modified in transit by an adversary. The client can now compute
\begin{align}
h'_{0,i} &:= H(0, i, c'_i), \\
h'_{1,\lfloor i/2\rfloor} &:= H(1, \lfloor i/2\rfloor, h'_{0,2\lfloor i/2\rfloor}, h'_{0,2\lfloor i/2\rfloor + 1}), \\
h'_{2,\lfloor i/2^2\rfloor} &:= H(2, \lfloor i/2^2\rfloor, h'_{1,2\lfloor i/2^2\rfloor}, h'_{1,2\lfloor i/2^2\rfloor + 1}), \\
\vdots \\
h'_{\ell,0} &:= H(\ell, 0, h'_{\ell - 1, 0}, h'_{\ell - 1, 1}).
\end{align}
To ensure the data were not modified in transit, the client then checks $h'_{\ell,0} \stackrel?= h_{\ell,0}$ and drops the data on the floor if it fails. In other words, we have the chunk verification function $$F(h, c'_i, a'_i) := \begin{cases} 1, & \text{if $h'_{\ell,0} = h$;} \\ 0, & \text{otherwise,} \end{cases}$$ with $h'_{\ell,0}$ computed from $c'_i$ and $a'_i = (h'_{0,i \oplus 1}, \ldots)$ as above. Note that the computation of $F$, the verification function, involves only the root hash $h$, the chunk $c'_i$ itself, and the $\ell$ hashes included in $a'_i$; verifying a chunk does not require knowing anything else about any other chunk in the file.
For example, in an eight-chunk file, when you transmit chunk $c_6$, send it alongside $h_{0,7}$, $h_{1,2}$, and $h_{2,0}$; the client, given the possibly modified $(c'_6, h'_{0,7}, h'_{1,2}, h'_{2,0})$, computes $h'_{0,6} = H(0, 6, c'_6)$, $h'_{1,3} = H(1, 3, h'_{0,6}, h'_{0,7})$, $h'_{2,1} = H(2, 1, h'_{1,2}, h'_{1,3})$, and $h'_{3,0} = H(3, 0, h'_{2,0}, h'_{2,1})$, and then verifies $h'_{3,0} \stackrel?= h_{3,0}$ before accepting the chunk $c'_6$ as genuine. The information needed to download and verify $c_6$ is illustrated in the diagram below:
- The red solid boxes are data transmitted. Note that there is no need to download any other chunk to verify $c_6$—only three hashes are needed.
- The blue dashed boxes are recomputed by the receiver.
- The red solid circle is the root of the Merkle tree, i.e. the hash $h$ of the whole file, which is sent first on some channel assumed not to be corrupted, and which the receiver uses to verify each chunk.
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}
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?
