Back شجرة ميركل Arabic Arbre de Merkle Catalan Hašový strom Czech Hash-Baum German Árbol de Merkle Spanish Räsipuu Estonian درخت درهم‌سازی Persian Arbre de Merkle French עץ מרקל HE Merkle-fa Hungarian

Merkle tree

An example of a binary hash tree. Hashes 0-0 and 0-1 are the hash values of data blocks L1 and L2, respectively, and hash 0 is the hash of the concatenation of hashes 0-0 and 0-1.

In cryptography and computer science, a hash tree or Merkle tree is a tree in which every "leaf" node is labelled with the cryptographic hash of a data block, and every node that is not a leaf (called a branch, inner node, or inode) 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 data structure. A hash tree is a generalization of a hash list and a hash chain.

Demonstrating that a leaf node is a part of a given binary hash tree requires computing a number of hashes proportional to the logarithm of the number of leaf nodes in the tree.[1] 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 cryptographic commitment scheme, 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.[2]

The concept of a hash tree is named after Ralph Merkle, who patented it in 1979.[3][4]

  1. ^ Becker, Georg (2008-07-18). "Merkle Signature Schemes, Merkle Trees and Their Cryptanalysis" (PDF). Ruhr-Universität Bochum. p. 16. Archived from the original (PDF) on 2014-12-22. Retrieved 2013-11-20.
  2. ^ "Handbook of Applied Cryptography". cacr.uwaterloo.ca. Section 13.4.1. Retrieved 2024-03-07.
  3. ^ Merkle, R. C. (1988). "A Digital Signature Based on a Conventional Encryption Function". Advances in Cryptology – CRYPTO '87. Lecture Notes in Computer Science. Vol. 293. pp. 369–378. doi:10.1007/3-540-48184-2_32. ISBN 978-3-540-18796-7.
  4. ^ US patent 4309569, Ralph Merkle, "Method of providing digital signatures", published Jan 5, 1982, assigned to The Board of Trustees of the Leland Stanford Junior University 
From Wikipedia, the free encyclopedia · View on Wikipedia

Developed by Tubidy