Partial Merkle Tree

A PMT provides a cryptographic proof that a specific piece of data (e.g., a transaction) is included in a block. It does this by supplying a minimal set of hash values (the Merkle path) from the leaf to the root, allowing a verifier to recompute the known Merkle root without possessing the entire tree.

• Core Function: Proves inclusion, not exclusion.
• Verification: Requires only O(log n) hashes, where n is the number of leaves.

The primary advantage of a PMT is its drastic reduction in data transfer requirements. Instead of downloading an entire block (which can be megabytes in size), a light client or Simplified Payment Verification (SPV) node only needs the block header and a small PMT to verify transaction inclusion.

• Example: Verifying one transaction in a 4000-tx block requires ~12 hashes (for a tree depth of 12) versus the entire block data.

The proof itself is a Merkle path or authentication path. It consists of the sibling hashes needed at each level of the tree to reconstruct the root.

• Components: The target leaf's hash, the sibling hashes at each level, and the position (left/right) of each hash.
• Process: The verifier hashes the leaf with its provided sibling, then hashes that result with the next sibling, recursively climbing to the root.

PMTs are the enabling technology for Simplified Payment Verification (SPV), as defined in the Bitcoin whitepaper. Light clients use PMTs to verify that payments to them were confirmed, relying on the full nodes' proof-of-work but not storing the chain.

• Trust Model: Trusts that the Merkle root in the valid, mined block header is correct.
• Privacy Consideration: Requesting a PMT for a specific transaction can reveal user interest to the serving full node.

A Full Merkle Tree contains every node hash and is used by full nodes to calculate the root for a new block. A Partial Merkle Tree is a subset derived from it for verification purposes.

• Full Tree: Constructed by block producers. Size: ~2n hashes.
• Partial Tree: Extracted by full nodes for queriers. Size: ~log₂(n) hashes.
• Relationship: The PMT is a verifiable slice of the full tree's data structure.

Bitcoin implements PMTs via the merkleblock message (P2P command) and the CMerkleBlock structure. It includes a bitmask to indicate which nodes in the traversal are part of the proof, along with the vector of hashes.

• Protocol Message: A full node sends a merkleblock in response to a getdata request for a transaction filtered by a Bloom filter.
• Structure: Contains the block header, the number of transactions, the hashes, and the traversal flag bits.

A Partial Merkle Tree is constructed by hashing data into leaf nodes and building a binary tree of hashes up to a single Merkle root. To prove a specific piece of data (e.g., a transaction) is included, one provides a Merkle proof—the minimal set of sibling hashes needed to recompute the root from the target leaf. This allows verification with O(log n) data instead of the full tree.

Light clients and Simplified Payment Verification (SPV) wallets rely on PMTs. They do not store the full blockchain. Instead, they download block headers containing the Merkle root. To verify a transaction, a full node provides a compact Merkle proof. The client hashes the transaction with the proof; if it matches the root in the validated block header, the transaction's inclusion is cryptographically proven.

• Bitcoin: Uses PMTs in its merkleblock message format. SPV clients request this message to filter and verify transactions relevant to their wallets.
• Ethereum: Employs Merkle Patricia Tries for state and transaction verification. Light clients use Les protocol to request proofs for account balances or transaction receipts via PMT-like structures.

PMTs drastically reduce the data required for verification. For a blockchain with thousands of transactions per block, a proof requires only a few hundred bytes (logarithmic scale) versus megabytes for the full block. This is critical for mobile wallets, IoT devices, and scaling solutions that need trust-minimized access to chain data without running a full node.

Historically, SPV clients used Bloom filters to privately request relevant transactions from full nodes, which then returned PMT proofs. This was privacy-leaking and inefficient. Modern protocols like BIP 157/158 (Neutrino) use client-side filtering: nodes serve compact filters, and clients download entire blocks, using PMTs internally to verify only their transactions, improving privacy and efficiency.

PMTs are fundamental to interoperability and scaling:

• Cross-Chain Bridges: Relays use Merkle proofs to verify events (e.g., token locks) on a source chain for execution on a destination chain.
• Optimistic Rollups: Fraud proofs often involve providing a Merkle proof to demonstrate incorrect state transition within a rollup block.
• Light Client Bridges: Chains like Cosmos IBC use light clients that verify headers and proofs from other chains.

In modular blockchain architectures like Ethereum with danksharding, Partial Merkle Trees (or their extension, Kate commitments) are crucial for data availability sampling. Light nodes randomly sample small pieces of erasure-coded data and verify their inclusion via proofs. By collecting enough samples, they can probabilistically guarantee the entire data block is available, preventing data withholding attacks without downloading all data.

In Optimistic Rollups, a Partial Merkle Tree is used to generate concise fraud proofs. When a sequencer posts an invalid state transition, a verifier can challenge it by submitting a proof containing only the relevant state leaves (e.g., account balances) and their Merkle paths. The Layer 1 contract verifies this small proof against the published state root, enabling secure scaling with minimal on-chain data.

Ethereum originally used Bloom filters in logs to help light clients find transactions of interest, but verification still relied on Merkle Patricia proofs. A client would query for logs matching a filter and then verify the returned log's inclusion in a block using a Partial Merkle Tree proof. This combined approach allowed for efficient querying and cryptographically secure verification of event data.

A Merkle Mountain Range is a variant optimized for append-only data structures. It allows for efficient generation of inclusion proofs for any leaf while supporting easy pruning of old proofs. MMRs are used in protocols like FlyClient for efficient blockchain bridging and in Bitcoin's transaction index to provide compact proofs of inclusion across a chain of block headers, enhancing proof efficiency over standard Merkle trees.

The core security guarantee of a Partial Merkle Tree is data integrity. By providing a Merkle proof (or inclusion proof) consisting of sibling hashes along a path to the root, any verifier can cryptographically confirm that a specific leaf node (e.g., a transaction) is part of the committed dataset. This proof is non-repudiable; if the root hash is trusted, the proof's validity is mathematically certain.

The security of a partial verification rests entirely on the authenticity of the Merkle root. In blockchain contexts, this root is typically embedded in a block header and secured by Proof-of-Work or Proof-of-Stake. The critical assumption is that the majority of the network's consensus power is honest, making the published root a trustworthy commitment. A malicious actor controlling the root could construct valid proofs for non-existent data.

Partial Merkle Trees enable the light client security model (e.g., Simplified Payment Verification - SPV). A light client assumes:

• The consensus mechanism securing the block headers is robust.
• It has a honest-majority connection to the network to receive valid block headers.
• The provided Merkle proofs originate from a full node that honestly constructed them from the actual block data. This model trades full validation for efficiency, relying on these external trust assumptions.

The party constructing the proof must be trusted to provide a valid proof structure. Potential attacks include:

• Proof Forgery: Impossible if the root is fixed, as any change to the proof data invalidates the hash chain.
• Data Withholding: A malicious prover can simply not reveal the proof for a transaction, creating a false negative. The verifier cannot prove the data doesn't exist, only that it wasn't proven.
• Malleability: Care must be taken that the data hashed into leaves is canonically encoded to prevent multiple valid representations.

The system assumes the underlying cryptographic hash function (e.g., SHA-256, Keccak) is secure against:

• Pre-image resistance: Cannot find an input given an output hash.
• Second pre-image resistance: Cannot find a different input with the same hash as a known input.
• Collision resistance: Cannot find any two different inputs with the same hash. A break in these properties would allow an attacker to create fraudulent Merkle proofs.

The primary security trade-off is completeness. A Partial Merkle Proof verifies inclusion but not exclusion. It proves a specific element is in the tree, but a light client does not verify the entire set of transactions in a block. It therefore cannot independently detect invalid transactions outside its proof or ensure the total block data size is correct, relying on the full node network for those guarantees.

A Merkle Tree is a hierarchical data structure where every leaf node is a hash of a data block, and every non-leaf node is the hash of its child nodes. It enables efficient and secure verification of large datasets.

• Core Function: Provides a single root hash that cryptographically commits to the entire dataset.
• Verification: To prove a specific data block is included, one only needs the Merkle path (or proof), not the entire tree.
• Use Case: Fundamental to blockchain headers, where the Merkle root of transactions is included in a block.

A Merkle Proof is the minimal set of hash values needed to verify that a specific leaf node belongs to a Merkle Tree with a known root hash.

• Components: Includes the target leaf's hash and the sibling hashes along the path to the root.
• Efficiency: Allows a light client to verify transaction inclusion without downloading the entire blockchain.
• Relation to PMT: A Partial Merkle Tree is essentially a compact way to deliver multiple Merkle proofs for a filtered set of data.

A Bloom Filter is a probabilistic, space-efficient data structure used to test whether an element is a member of a set. It can yield false positives but never false negatives.

• Blockchain Use: Light clients use Bloom filters to tell full nodes which transactions (e.g., to their addresses) they are interested in.
• Synergy with PMT: The full node uses the client's Bloom filter to construct a Partial Merkle Tree containing only the matching transactions and their proofs, minimizing data transfer.

Simplified Payment Verification (SPV) is a method that allows a client to verify that a transaction is included in a block without running a full node or storing the entire blockchain.

• How it Works: The SPV client downloads only block headers and requests Merkle proofs for its relevant transactions.
• Dependency: Relies on structures like the Partial Merkle Tree to receive compact, verifiable proof bundles from full nodes.
• Goal: Enables lightweight, trust-minimized wallets on resource-constrained devices.

A Vector Commitment is a cryptographic primitive that allows one to commit to an ordered sequence of values with a single short commitment. Later, one can open the commitment at any specific position with a succinct proof.

• Comparison to Merkle Trees: A Merkle Tree is a specific, widely-used type of vector commitment.
• Advanced Schemes: Newer constructions like Kate-Zaverucha-Goldberg (KZG) commitments offer constant-sized proofs, which can be more efficient than the logarithmic-sized Merkle proofs for certain applications like stateless clients.

A Binary Trie (or Merkle Patricia Trie) is a modified, deterministic Merkle tree that provides efficient proof and update for key-value maps, not just lists.

• Key Feature: Combines a Patricia trie's memory efficiency with Merkle tree's cryptographic verifiability.
• Ethereum's Use: The state, storage, and transaction receipts in Ethereum are stored in variations of a Merkle Patricia Trie.
• Contrast with PMT: While a PMT is for filtering a list, a Merkle Patricia Trie is for proving the existence and state of a specific key in a dynamic database.