Merkle tree

In cryptography and computer science, a hash tree (English hash tree or merkle tree ) is a data structure that forms a tree of hashes of data blocks, for example, from a file. Hash trees are an extension of hash lists and serve equally to ensure the integrity of data. If you use the Tiger hash function as a basis, as they are called Tiger trees or Tiger tree hashes.

History

Hash trees were invented in 1979 by Ralph Merkle. The original purpose was the efficient handling of many Lamport one-time signatures. Lamport signatures are valid even in the face of quantum computers safe. Unfortunately, a Lamport - keys are only used to sign a single message. When combined with hash trees, however, a Lamport key can be used for many messages, which is realized by the Merkle signature scheme.

Applications

In addition to the signatures, hash trees can be used to protect any type of data that is stored and exchanged on changes. The main application is currently in P2P networks to ensure that data blocks received from other peers, are undamaged and unaltered. There are proposals to use hash trees in the Trusted Computing. Sun Microsystems uses the ZFS. Hash trees are also used in Google Wave and the online data backup Tarsnap.

Operation

A hash tree is a tree of hash values ​​, wherein the leaves are hash values ​​of data blocks, for example a file. Nodes in the tree are hashes of their children above. Most implementations use a binary tree ( each node has at most two child nodes), however, a higher output level can just as well be used.

Normally, a cryptographic hash function such as SHA - 1, Whirlpool, or Tiger is used. If only protect against accidental damage to the hash tree, then a ( cryptographically insecure ) as CRC checksum can be used.

The root of the hash tree is referred to as a top hash root hash or master hash. Before downloading a file in a P2P network of the top hash is usually obtained from a trusted source, such as a friend or a site with a good rating. If there is the top hash, so the rest of the hash tree can also be obtained from an untrusted source, ie, by any peer of a P2P network. It can then be checked against the trusted top hash and optionally rejected.

The main difference to a hash list is that each branch of the hash tree, and can be downloaded individually tested for integrity immediately, even if the entire tree is not yet available. It is more efficient to split files for transmission into very small blocks, so that in case of damage, only small parts have to be reloaded. This, however, arise with very large files relatively large hash lists or hash trees. However, if trees are used, can be loaded quickly and checked for integrity individual branches, so downloading the file itself can begin.

Tiger Tree Hash

The Tiger Tree Hash ( TTH ) is a widely used hash tree. It uses a binary tree - usually with a block size of 1024 bytes - and the cryptographically secure Tiger hash function.

TTHs be used by the file sharing protocols Gnutella, Gnutella2, and Direct Connect, as well as file sharing applications such as Phex, BearShare, LimeWire, Shareaza and DC .