How Hash Trees Work
A hash tree is a tree of hashes in which the leaves are hashes of data blocks in, for instance, a file or set of files. Nodes further up in the tree are the hashes of their respective children. For example, in the picture hash 0 is the result of hashing the result of concatenating hash 0-0 and hash 0-1. That is, hash 0 = hash( hash 0-0 || hash 0-1 ) where || denotes concatenation.
Most hash tree implementations are binary (two child nodes under each node) but they can just as well use many more child nodes under each node.
Usually, a cryptographic hash function such as SHA-1, Whirlpool, or Tiger is used for the hashing. If the hash tree only needs to protect against unintentional damage, much less secure checksums such as CRCs can be used.
In the top of a hash tree there is a top hash (or root hash or master hash). Before downloading a file on a p2p network, in most cases the top hash is acquired from a trusted source, for instance a friend or a web site that is known to have good recommendations of files to download. When the top hash is available, the hash tree can be received from any non-trusted source, like any peer in the p2p network. Then, the received hash tree is checked against the trusted top hash, and if the hash tree is damaged or fake, another hash tree from another source will be tried until the program finds one that matches the top hash.
The main difference from a hash list is that one branch of the hash tree can be downloaded at a time and the integrity of each branch can be checked immediately, even though the whole tree is not available yet. For example, in the picture the integrity of data block 2 can be verified immediately if the tree already contains hash 0-0 and hash 1 by hashing the data block and iteratively combining the result with hash 0-0 and then hash 1 and finally comparing the result with the top hash. Similarly, the integrity of data block 3 can be verified if the tree already has hash 1-1 and hash 0. This can be an advantage since it is efficient to split files up in very small data blocks so that only small blocks have to be redownloaded if they get damaged. If the hashed file is very big, such a hash tree or hash list becomes fairly big. But if it is a tree, one small branch can be downloaded quickly, the integrity of the branch can be checked, and then the downloading of data blocks can start.
There are several additional tricks, benefits and details regarding hash trees. See the references and external links below for more in-depth information.
Read more about this topic: Hash Tree
Famous quotes containing the words trees and/or work:
“It was a tangled and perplexing thicket, through which we stumbled and threaded our way, and when we had finished a mile of it, our starting-point seemed far away. We were glad that we had not got to walk to Bangor along the banks of this river, which would be a journey of more than a hundred miles. Think of the denseness of the forest, the fallen trees and rocks, the windings of the river, the streams emptying in, and the frequent swamps to be crossed. It made you shudder.”
—Henry David Thoreau (1817–1862)
“If the heart beguiles itself in its choice [of a wife], and imagination will give excellencies which are not the portion of flesh and blood:Mwhen the dream is over, and we awake in the morning, it matters little whether ‘tis Rachael or Leah,—be the object what it will, as it must be on the earthly side ... of perfection,—it will fall short of the work of fancy, whose existence is in the clouds.”
—Laurence Sterne (1713–1768)