Merkle tree

In a basic binary Merkle tree, each leaf represents a data item and stores its cryptographic hash. Each parent stores a hash computed from its children's hashes; this process continues until a single root hash is produced. A system can publish or otherwise authenticate that root as a commitment to the dataset. A change to an item ordinarily changes the hashes along its path and therefore changes the root. Secure use depends on a suitable hash function and unambiguous encoding of leaves and internal nodes; protocol details such as domain separation help prevent structural ambiguities.

To demonstrate that a particular item belongs to the committed dataset, a prover supplies the item and the sibling hashes needed to recompute the root from its leaf upward. The verifier checks the result against a trusted root. For a balanced binary tree containing N leaves, an inclusion proof uses a number of sibling hashes that grows logarithmically with N, rather than requiring the verifier to download every item. The root alone does not establish that a record is present; the proof and the trustworthiness of the root are essential.

Certificate Transparency uses Merkle trees to organize logged certificates and support public auditing. A signed tree head identifies a particular log state. An inclusion proof can show that a certificate is in that state, while a consistency proof can show that a later tree extends an earlier one without changing its existing entries. These proofs help monitors and other observers detect certain forms of omission or inconsistent log history. Cryptographic proofs do not by themselves ensure a log is honest or that every observer sees the same view; monitoring and comparison between observers are also important.

Merkle trees are useful when large collections must be checked efficiently, including authenticated storage, distributed systems, software or data distribution, and transparency logs. Variants may support updates, non-binary branching, or sparse key spaces. A tree does not encrypt its contents, guarantee that the committed data is true, or provide authentication unless the root is obtained through a trusted or verifiable channel. Implementations must also specify how data is encoded and hashed, since incompatible conventions can produce different roots or weaken verification.