One proof for any leaf: OR-aggregation Merkle inclusion proofs

A classical Merkle inclusion proof grows with the tree: log₂(n) sibling hashes, recomputed hop by hop, per leaf proven. Our peer-reviewed construction aggregates inclusion proofs with OR logic inside a zero-knowledge proof — and the result is a proof whose size does not depend on the number of leaves at all, verifiable against any single valid leaf hash. Here is what that changes, in engineering terms.

The baseline: proofs that grow

Merkle trees are the workhorse commitment of every chain: commit to n items with one 32-byte root, prove membership of any item with the sibling path. The proof is log₂(n) hashes — 20 siblings for a million leaves — and the verifier recomputes the path. Fine for one leaf. Now prove a thousand leaves: the classical aggregation is AND logic — concatenate paths, deduplicate shared prefixes, and the verifier still processes every leaf hash and a proof that grows with both k and n. At exchange-reserve scale, airdrop scale, or rollup-state scale, the verifier's bill is the product bottleneck — and when the verifier is a contract, the bill is gas.

OR instead of AND

The paper flips the aggregation logic. Instead of proving “leaf₁ is included AND leaf₂ is included AND …,” the prover produces a zero-knowledge proof of the statement “I know a valid inclusion path for a leaf among the committed set” — OR logic across the set — and aggregation happens inside the proof system rather than by concatenating paths. Two properties fall out, and they are the paper's headline results. Size: the aggregated proof's size is independent of the number of leaves in the tree. Verification: the verifier checks the proof against any single valid leaf hash — it does not touch the leaf set. The tree can be a million leaves or a billion; the artifact the verifier handles is the same.

The formal construction, security argument, and comparative analysis are in the paper — the journal version is peer-reviewed and the arXiv preprint is open. The paper's comparison of aggregation approaches (its Table 1) compresses to this:

Approach	Proof size	Verification data	Universality
AND aggregation	Compact	All leaf hashes	Universal
Embedded-path proofs (per-leaf)	Compact	Single leaf hash	Leaf-specific
OR aggregation (the paper)	Compact	Single leaf hash	Universal

OR aggregation is the only row that gets both: one proof, any leaf, verified against a single hash. Concrete proving-cost numbers are deliberately absent — the paper defines the construction and leaves implementation benchmarking to future work, and this post claims nothing the paper does not.

What “universal” buys

Universality here is operational, not rhetorical: one verification procedure serves any leaf and any position — the verifier's job does not change shape as the committed set changes. For contract engineering that is the difference between deploying one fixed verifier and regenerating verification logic as trees grow. For systems that continuously append — state commitments, artifact logs — it means the verification side of the protocol is frozen while the data side scales.

The bill: the prover pays

Nothing is free. The construction replaces cheap hash recomputation with ZK proving, so prover compute rises by orders of magnitude while verifier cost collapses to a constant. That trade is correct in exactly one situation — when verification is the scarce, priced resource — and that situation happens to be the on-chain default: gas is expensive, prover time off-chain is a commodity. It is the same asymmetry that makes ZK light clients economical (we wrote up the NEAR→Ethereum client in those terms), and the two lines of work compose: light clients prove consensus; aggregated inclusion proofs make the state under that consensus cheap to check.

Where this lands in practice

Four targets, in rising order of ambition. Proof-of-reserves: an exchange commits to its liability set; auditors and users verify against a constant-size artifact instead of a per-user path. Airdrop and allowlist claims: claim verification stops scaling with the recipient set. Batch state proofs: rollups and bridges proving many slots per block amortize into one aggregated proof. Artifact archives: systems that produce heavy per-block artifacts and archive them off-chain keep disputes cheap because inclusion never gets more expensive — the accumulator design questions that raises are a post of their own.

Limits

Three, stated plainly. Proving cost is real: below some batch size, classical paths are simply cheaper end to end — the crossover is workload-specific and should be measured, not assumed. The construction's concrete performance depends on the proof system it is instantiated with, and toolchains reprice yearly. And OR semantics prove membership within the committed set — applications that need to bind a proof to one specific named leaf layer that binding on top. None of these are objections; they are the boundary of the tool, and knowing the boundary is what lets you ship it.