Merkle Tree

A Merkle tree creates a single, fixed-size root hash that represents the entire dataset. Any modification to a single leaf node (data block) will produce a completely different root hash, making unauthorized alterations immediately detectable. This property is the basis for tamper-evident logging.

• Changing one byte of data changes the leaf hash.
• The change cascades up the tree, altering the root.
• Verification requires only recomputing the path, not the whole dataset.

To prove a specific data block is part of the tree, you only need to provide a Merkle proof (or audit path) consisting of O(log n) sibling hashes, rather than the entire dataset. A verifier can recompute the root hash from the leaf and the proof, confirming membership without downloading all data.

• Complexity: O(log n) for both proof size and verification time.
• Use Case: Light clients in blockchains verifying a transaction without storing the full chain.

Every node in a Merkle tree is the output of a cryptographic hash function (typically SHA-256). Leaf nodes are hashes of data blocks, while non-leaf nodes are hashes of the concatenation of their child nodes' hashes.

• Formula: Parent = H(Left Child || Right Child)
• Deterministic: The same dataset always produces the same tree.
• Collision Resistance: The security relies on the pre-image and collision resistance of the underlying hash function.

Merkle trees enable efficient comparison of large, replicated datasets across distributed systems. By comparing only the root hash, systems can instantly determine if their copies are identical. If they differ, a binary search through the tree hierarchy quickly identifies the inconsistent data blocks without transferring the entire dataset.

• Dynamo-style databases use Merkle trees for anti-entropy repair.
• Git uses a Merkle DAG to track file system snapshots.

By publishing the Merkle root of an audit log into a public blockchain transaction, the log's integrity is permanently and publicly verifiable. This process, known as blockchain anchoring, provides an immutable, globally trusted timestamp that proves the data existed before a specific block time, enabling strong non-repudiation.

• The root is stored in an OP_RETURN output or a smart contract.
• Anyone can later verify the log's state against the published root.

A Sparse Merkle Tree (SMT) extends the concept to prove that a specific key has no entry in a dataset. By structuring the tree with a vast, pre-defined address space (e.g., 256-bit keys) where empty leaves have a default null hash, an SMT can generate a proof of non-inclusion, which is critical for credential revocation and access control lists.

• Default Value: Empty leaves are hashed as a constant null value.
• Proof: Shows the path to the key resolves to the default hash.