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.
2. 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.
3. 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}
4. Repeat, combining two hashes at a time.
5. 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.**
6. Suppose want to transmit the $i^{\mathit{th}}$ chunk $c_i$.
   1. **Transmit $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}$ alongside the chunk $c_i$.**  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.
   2. **The _receiver_ receives a putative chunk $c'_i$ and the putative hashes $h'_{0,i \oplus 1}$, $h'_{1,\lfloor i/2\rfloor \oplus 1}$, $h'_{2,\lfloor i/2^2\rfloor \oplus 1}$, $\dots$, $h'_{\ell - 1, \lfloor i/2^{\ell - 1}\rfloor \oplus 1}$, which may be the corresponding $h$ values or may have been modified in transit by an adversary.**  The receiver 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 receiver then _checks_ $h'_{\ell,0} \stackrel?= h_{\ell,0}$ and drops the data on the floor if it fails.**

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 \bigl(|c| + \frac{r - 1}{\log_2 r} |H| \ell\bigr)$ 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.  The information needed to download and verify $c_4$ 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_4$—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, which is sent first, and which the receiver uses to verify the chunk.

[![Merkle tree with fanout 2, height 3, and total length 8][1]][1]


  [1]: https://i.sstatic.net/4A7wu.png