Return to Revisions

1. Split the full file up into chunks $c_0, c_1, c_2, \dots, c_{2^\ell - 1}$.
2. 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.
3. 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.
4. 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}
5. Repeat, combining two hashes at a time.
6. At the end of this process, you will have a hash $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}$. Transmit the root hash $h_{\ell,0}$ of the Merkle tree first.
7. Suppose want to transmit the $i^{\mathit{th}}$ chunk $c_i$.
   1. Write the number $i$ out in binary: $i = i_0 + 2 i_1 + 4 i_2 + \cdots + 2^{\ell - 1} i_{\ell - 1}$.
   2. Transmit $h_{0,1 - i_0}$, $h_{1,1 - i_1}$, $h_{2,1 - i_2}$, $\ldots$, $h_{\ell - 1, 1 - i_{\ell - 1}}$ alongside the chunk $c_i$. This is a path down the Merkle tree.
   3. The receiver can now recompute $h_{0,i_0} = H(0, c_i)$ directly, and then $h_{1,i_1} = H(1, h_{0, \lfloor i/2^{\ell - 1}\rfloor}, h_{1, \lfloor i/2^{\ell + 1}\rfloor + 1})$, and so on, and verify that the result turns out to be $h_{\ell,0}$.

Note that the overhead you must transmit alongside each chunk is $\ell$ hashes, so the total number of bits transmitted is at most $2^\ell (|c| + |H| \ell)$, where $|c|$ is the maximum size of a chunk (say, a megabyte) and $|H|$ is the size of a hash (typically 256). Handling all the fenceposts in non-power-of-two lengths, or extending to radix $r > 2$ with a total cost of $2^\ell (|c| + (r - 1) |H| \ell)$ bits, is left as an exercise for the reader.

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}$, so that the receiver can recompute $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 then compare $h_{3,0}$ to $H(3, 0, h_{2,0}, h_{2,1})$ to make sure it's correct. In the diagram below, the red solid boxes are data transmitted, and the blue dashed boxes are recomputed by the receiver; the red solid circle, of course, is the root of the Merkle tree, which is sent first, and which the receiver uses to verify each chunk.