💻 computer science

Parent-Hash DAG: A Cost Analysis of Constant-Time Append for On-Chain Registries

This paper introduces and formally analyzes the Parent-Hash DAG (PHDAG) as a constant-time, gas-efficient alternative to incremental Merkle trees for on-chain registries, demonstrating through theoretical modeling and empirical benchmarks that PHDAG maintains depth-invariant costs while Merkle tree costs grow linearly, making PHDAG superior for all practical production depths.

Original authors: Ian C. Moore, Fernando Paredes Garcia

Published 2026-06-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ian C. Moore, Fernando Paredes Garcia

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are running a digital library where people come to register new books. Every time someone adds a book, the library has to update its master list. The question this paper asks is: What is the most efficient way to update this list as the library grows from a few books to millions?

The authors compare two different ways of organizing this library: the Incremental Merkle Tree (IMT) and the Parent-Hash DAG (PHDAG).

Here is the breakdown of their findings using simple analogies.

1. The Two Approaches

The Incremental Merkle Tree (IMT): The "Tower of Blocks"

Think of the IMT as a giant, perfectly symmetrical tower of blocks.

How it works: Every time you add a new book (a leaf), you have to climb up the tower, update the block directly above it, then the one above that, all the way to the very top (the root).
The Cost: The taller the tower gets, the longer the climb. If the library has 1,000 books, you climb a short way. If it has 1 million books, you climb much higher.
The Problem: The cost (in "gas," which is like the energy fee to perform the update) goes up as the library grows. It's like paying more for a taxi ride the further you go. Also, the cost varies: sometimes you have to climb a lot of stairs, sometimes fewer, depending on exactly where you place the new book.

The Parent-Hash DAG (PHDAG): The "Chain of Letters"

Think of the PHDAG as a chain of letters passed between friends.

How it works: When you add a new book, you simply write down its details and write a note saying, "This book follows that specific previous book." You drop this note into a public mailbox (the blockchain event log). You don't need to climb a tower or update a central root. You just write your note and link it to the past.
The Cost: It doesn't matter if the library has 10 books or 10 million. You always write the same amount of text and drop it in the same mailbox.
The Benefit: The cost is constant. It never changes, no matter how big the library gets. It's like paying a flat fee to send a postcard, regardless of how many postcards have been sent before.

2. The Big Discovery: When Does the Switch Happen?

The authors did the math and ran real-world tests on a test network (Base Sepolia) to see exactly when the "Chain of Letters" (PHDAG) becomes cheaper than the "Tower of Blocks" (IMT).

The Tipping Point: They found that the "Tower" is only cheaper when the library is tiny (less than about 7 levels deep).
The Reality: Almost every real-world system that uses these registries (like privacy tools or identity systems) is much, much deeper than 7 levels. They are usually 20 to 40 levels deep.
The Result: In the real world, the "Chain of Letters" (PHDAG) is always cheaper and always predictable.

3. Why Does This Matter? (The "Variance" Problem)

Imagine you are a delivery service charging a fixed fee to update the library.

With the Tower (IMT): Sometimes the update is cheap, sometimes it's expensive. You have to guess the price. If you guess wrong, you might lose money on expensive updates. The cost "jitters" up and down.
With the Chain (PHDAG): The price is always exactly the same. There is no guessing. The authors found the cost fluctuates by only about 6 units of gas (a tiny amount), which is practically zero. This makes it incredibly reliable for businesses.

4. The "Reconstruction" Superpower

There is one other major difference.

The Tower (IMT): To prove a book exists, you need a specific "proof" (a receipt showing the path up the tower). If the central index breaks, you might lose the ability to verify the whole tower easily.
The Chain (PHDAG): The entire history is written in the public mailbox (event logs). Even if the computer running the library crashes, anyone can walk through the mailbox, read the letters in order, and rebuild the entire library from scratch. It is "indestructible" because the history is scattered across the public record, not locked in one storage slot.

5. The Bottom Line

The paper concludes that for any large-scale, real-world system that needs to record a history of events (like proving who owns what digital art or tracking supply chains):

Stop using the Tower (IMT) for this specific job. It gets too expensive and unpredictable as it grows.
Start using the Chain (PHDAG). It is cheaper, the price never changes, and the data is safer because it can be rebuilt from public records at any time.

The authors suggest that the blockchain community should adopt this "Chain of Letters" method as a standard rule for all future provenance registries, because it is the most efficient and robust way to handle large amounts of data.

Technical Summary: A Cost Analysis of Constant-Time Append for On-Chain Registries

Problem Statement

Provenance trees (PTs) are append-only directed acyclic graphs (DAGs) used as the data substrate for operator-gated provenance infrastructure. While previous work asserted that the underlying append operation for PTs is $O(1)$ in gas cost—independent of registry size and tree depth—this claim lacked formal isolation as a standalone primitive, explicit constant bounds, or empirical benchmarking against the industry standard: the Incremental Merkle Tree (IMT).

The IMT, dominant in zero-knowledge protocols (e.g., Tornado Cash, Semaphore) and rollup state commitments, offers succinct $O(\log N)$ inclusion proofs but incurs an append cost that grows logarithmically with tree depth ( $\Theta(\log N)$ ). For applications where succinct membership proofs are not the primary query (such as provenance registries), the cost trade-off of the IMT is less favorable, yet the crossover point where an alternative becomes cheaper has not been rigorously established.

Methodology

The paper isolates the Parent-Hash Directed Acyclic Graph (PHDAG) as a distinct primitive and compares it against the Incremental Merkle Tree (IMT) through three lenses:

Formal Complexity Analysis: The authors formalize the PHDAG append operation, proving it executes a bounded number of EVM operations independent of registry size ( $n$ ) or depth. They contrast this with the IMT's frontier-update loop, which scales linearly with depth ( $d$ ).
Stochastic Cost Modeling: Recognizing that IMT append costs vary based on the leaf index's binary representation (Hamming weight), the authors model the per-insert gas cost as a random variable. They derive closed-form expressions for the mean and variance of IMT costs under a uniform distribution of leaf indices, distinguishing between "write levels" (updating the frontier) and "read levels" (traversing without writing).
Empirical Validation: Independent contracts for both primitives were deployed on the Base Sepolia testnet. Experiments covered tree depths from 1 to 25.
- IMT: Tested via a "proportional depth sweep" performing $\max(d, 2)$ appends per depth to capture variance.
- PHDAG: Tested via a 200-append run characterizing cost distribution and variance.
- Metrics: Gas consumption was measured from transaction receipts, excluding initial cold-storage initialization costs to focus on steady-state performance.

Key Contributions

1. Formal Complexity of PHDAG

The paper establishes that PHDAG append is strictly $O(1)$ in gas cost.

Mechanism: Each append writes to three previously untouched storage slots (cold SSTOREs) keyed by a unique identifier, plus a warm write to a counter.
Invariance: The cost is invariant to the global registry size $n$ and any notion of tree depth. The access list for a transaction is reset at the start of every transaction; since PHDAG writes to new slots every time, the cost depends only on the fixed number of operations, not the state of the contract.
Reconstruction: The paper proves that the complete registry can be reconstructed from public event logs in $O(|V|)$ time with no off-chain dependency, as the event stream carries the canonical history.

2. Stochastic Model for IMT

The authors derive that IMT per-insert cost is a random variable $g$ dependent on the leaf index $i$ :

Mean: $E[g] = c_0 + \frac{d}{2}(c_L + c_R)$ , where $c_L$ and $c_R$ are the marginal costs of write and read levels, respectively.
Variance: $Var[g] = (c_L - c_R)^2 \frac{d}{4}$ .
Implication: While the relative variance (coefficient of variation) decreases as depth increases, the absolute standard deviation grows as $\Theta(\sqrt{d})$ , introducing operational unpredictability for high-depth registries.

3. Empirical Crossover and Validation

PHDAG Performance: Measured at a constant 76,276 gas per append (standard deviation $\approx 6$ gas), confirming depth invariance.
IMT Performance: Costs grew linearly with depth.
Crossover Point: The depth at which PHDAG becomes cheaper than IMT was identified at $d \approx 6$ to $7.2$.
- At $d=6$ , the measured IMT cost ( $\approx 78,000$ gas) exceeded the PHDAG cost.
- The lifetime-average crossover (uniform index distribution) is calculated at $d^* \approx 7.2$ .

Results

The empirical data validates the theoretical models:

PHDAG exhibits negligible variance and constant cost across all tested depths.
IMT exhibits linear cost growth and increasing absolute variance with depth.
Production Context: Every production registry surveyed (Tornado Cash, Semaphore, zkSync, Scroll, Linea) operates at depths $d \ge 20$ . Consequently, all such systems currently operate in the regime where PHDAG is strictly cheaper and offers predictable costs, provided the application does not require succinct inclusion proofs.

Significance and Claims

The paper claims that the PHDAG primitive is the superior choice for append-only provenance registries where:

Succinct membership proofs are not required: Provenance queries typically involve parent-chain traversal or existence checks by unique ID, which are supported by $O(|V|)$ log-based reconstruction rather than $O(\log N)$ Merkle proofs.
Cost predictability is critical: For operators managing high-volume append services, the near-zero variance of PHDAG eliminates the need to budget for worst-case gas tails, a significant operational advantage over IMT at production depths.
Robustness is paramount: The log-canonical design of PHDAG ensures that the registry's history is indestructible and reconstructible from public event logs alone, independent of any off-chain indexing service or current contract storage state.

The authors conclude that PHDAG is a strong candidate for standardization as a uniform interface for Ethereum provenance infrastructure, offering a constant-cost, depth-invariant alternative to the depth-dependent IMT for non-ZK applications.