Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Merkle tree
open-in-new
<p>In <a href="/facts/Cryptography/e94PEVau">cryptography</a> and <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, a hash tree or Merkle tree is a <a href="/facts/Tree_(data_structure)/RcXz9noF">tree</a> in which every "leaf" <a href="/facts/Tree_(data_structure)/RcXz9noF">node</a> is labelled with the <a href="/facts/Cryptographic_hash_function/cuxkgbST">cryptographic hash</a> of a data block, and every node that is not a leaf (called a <i>branch</i>, <i>inner node</i>, or <i>inode</i>) is labelled with the cryptographic hash of the labels of its child nodes. A hash tree allows efficient and secure verification of the contents of a large <a href="/facts/Data_structure/yNsNvL1I">data structure</a>. A hash tree is a generalization of a <a href="/facts/Hash_list/f7p7fe86">hash list</a> and a <a href="/facts/Hash_chain/B0HUMdkM">hash chain</a>. </p><p>Demonstrating that a leaf node is a part of a given binary hash tree requires computing a number of hashes proportional to the <a href="/facts/Logarithm/QeXaV97q">logarithm</a> of the number of leaf nodes in the tree. Conversely, in a hash list, the number is proportional to the number of leaf nodes itself. A Merkle tree is therefore an efficient example of a <a href="/facts/Cryptographic_commitment/DMqRCguM">cryptographic commitment scheme</a>, in which the root of the tree is seen as a commitment and leaf nodes may be revealed and proven to be part of the original commitment. </p><p>The concept of a hash tree is named after <a href="/facts/Ralph_Merkle/ua5bsN0I">Ralph Merkle</a>, who patented it in 1979. </p>