Hash functions are also used in hash tree, or Merkle tree, where the hash function dependency forms a binary tree structure. Let's construct such hash tree. The hash tree construction starts from the below and moves upward. It begins with the child nodes. Given any data x sub i's, the child nodes are the hash output of these x sub i's. For simpler description we will skip x and denote the hash outputs of x sub i's as H sub i. In other words, H1 is equal to H of x1, H2 is equal to H of x2, and so on. For the parent nodes, H12 is the hash of output of H1 concatenated with H2. And likewise, H34 is the hash output of H3 and H4 and so on. Similarly, moving up another layer, H1234 is the hash output of H12 and H34. And H5678, the hash output of H56 and H78. And lastly, the top parent node, or the Merkle root, is the hash of the two child nodes directly beneath it. So in this case, HRoot, the Merkle root, is the hash of H1234 and H5678. Due to such construction, each node in the hash tree are dependent on its child nodes. For example, the Merkle root, HRoot is dependent on all the nodes here. And H56 is dependent on H5 and H6. But it's not dependant on other nodes, let's say H3. Suppose the integrity of one of the child nodes is compromised, this can happen by a malicious attacker modifying the data, or by natural and accidental failure. For example, due to a transmission channel error. In this example, suppose x3 changes. Then that change in x3 cascades through the path leading to all of its parent nodes. Therefore, an efficient way to check if there's a change in the child nodes would be to check the root, which is dependent on all the child nodes. In addition to detection, the hash tree also provides an efficient way to localize the integrity failure. In other words, the problem is not only to see whether there is an error in the data, but also to see where the error is. After detecting the error, you can move off to the child nodes of the root. And since there's a change in the hash for H1234, but no change in H5678, you understand that the change originated from the left half of the tree. You can further move down the tree to further localize the change or the error. After checking H12 and H34, you understand that the error is in H34, and therefore, between H3 and H4. Moving down farther in the hash tree enables you to localize the error or the change to H3, and therefore, x3. In other words, you can localize the error by following the path that leads from the root to the child node as opposed to checking all H sub i's. Such hash tree helps with efficiency of the hash verification. For example, for detection, you can check the Merkle root to see if there's an error. And for the error or changed localization, the effort scales with the log with the number of data blocks. You can also scale the binary tree exponentially by increasing the depth of the tree. For example, while we used the depth of three, which supported eight data blocks in this example, adding another layer below will enable a tree structure that supports 16 child nodes, which corresponds to 16 data blocks.