Merkle Trees

A Merkle tree is a tree data structure widely used in cryptography and blockchain technologies. Ralph Merkle proposed Merkle trees in 1987 in his paper, "A Digital Signature Based on a Conventional Encryption Function."

Merkle trees are used in distributed systems to verify data integrity and synchronization between data blocks from multiple nodes.

Data structure

A Merkle tree is a tree structure in which every leaf node has a hash value. The tree computes hash values out of data that has cryptographic significance. The hash function used to calculate the hash value should be deterministic. A hash function should always produce the same output for a given input, regardless of the number of times it is executed. Furthermore, the output should be distinct for distinct data values.

Every internal node (branch) has a hash value computed out of the hash values from its child nodes. This process continues recursively up to the root, producing a single hash value for the root. The root's hash value is called the data structure's fingerprint.

Merkle trees are also called hash trees. A Merkle tree with only two child nodes is called a binary hash tree. Merkle trees help to resolve Byzantine errors.