Skip to content
Crypto.world

Research

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

Append-only registries on Ethereum have to pay gas for every insertion, and the dominant design — the incremental Merkle tree — becomes more expensive as the tree grows deeper, with per-insert cost…

Parent-Hash DAG: A Cost Analysis of Constant-Time Append for On-Chain Registries
arXiv
2606.09593
Published
2026-06-08
Authors
Ian C. Moore, Fernando Paredes Garcia

AI summary

Overview

Research area: Distributed systems and blockchain engineering — specifically the gas economics of append-only on-chain registries (cs.DC), with ties to data-structure design and zero-knowledge infrastructure.

Technical level: Intermediate. The paper assumes familiarity with Ethereum's EVM storage model (SSTORE/SLOAD, cold versus warm access, EIP-2929/3529) and with Merkle trees, but the argument itself is a cost comparison built from a small number of clearly stated primitives.

Scope: The paper isolates the parent-hash directed acyclic graph (PHDAG) as a standalone append-only primitive, bounds its append cost formally and empirically against the incremental Merkle tree (IMT), and identifies the depth regime in which each is cheaper.

What This Paper Is About

Append-only registries on Ethereum have to pay gas for every insertion, and the dominant design — the incremental Merkle tree — becomes more expensive as the tree grows deeper, with per-insert cost varying from one insertion to the next. The authors argue that a simpler structure, the parent-hash DAG, performs a fixed number of storage writes to previously untouched slots on every append and therefore costs the same regardless of registry size or depth. The paper's goal is to turn a previously informal, system-level claim of O(1) append into a formally bounded and empirically measured result, with the IMT measured side by side as the standard alternative.

Key Contributions

  1. A formal complexity analysis of PHDAG append. The authors prove that an append executes a fixed, bounded number of EVM operations (at most two SLOADs, three SSTOREs for a non-root append, one counter SLOAD plus one warm SSTORE, and one event emission), with no loop whose count depends on registry size n. They establish that the partial derivative of append gas with respect to n is zero, and give the explicit structural cost expression g_PHDAG ≈ α_PHDAG + 3γ + 3γ_R + β. They also prove that IMT append is O(d) in depth and that trustless reconstruction of a PHDAG registry from public event logs takes O(|V|) time and space.

  2. A stochastic cost model for IMT inserts. Treating the leaf index i as uniformly distributed on [0, 2^d), the authors prove that the number of frontier write levels is W(i,d) = d − pop(i mod 2^d), so the total warm-SSTORE count is S(i,d) = d − pop(i mod 2^d) + 2 (the +2 for the unconditional root and nextIndex writes). Because the popcount follows Binomial(d, 1/2), they derive closed forms for the mean, E[g] = c₀ + (d/2)(c_L + c_R), and the variance, Var[g] = (c_L − c_R)² d / 4, where c_L is the cost of a write level and c_R the cost of a read level.

  3. Empirical validation on a public testnet. Independent IMT and PHDAG contracts were deployed on Base Sepolia and measured across tree depths 1 to 25, totaling over 500 transactions, with per-insert gas recorded for proportional workloads.

  4. Crossover identification relative to production systems. The paper locates the depth below which the IMT is cheaper and shows that this crossover falls far beneath the depths of every production registry the authors surveyed, placing all of those systems in the regime where PHDAG is strictly cheaper.

Main Findings

  • PHDAG append is depth-invariant at 76,276 gas. Across depths 1 to 25 the measured cost held at 76,276 gas with a standard deviation of about 6 gas — essentially flat, confirming the O(1) claim empirically. The benchmarked case is a root append, which omits the parent-existence SLOAD and writes a zero parent reference to an already-zero slot.

  • IMT cost grows linearly with depth. Measured IMT per-insert gas increases with tree depth, matching the O(d) bound in Proposition 1, in contrast to the flat PHDAG line.

  • IMT per-insert cost is a random variable. The number of storage writes per insert depends on the low-order bits of the leaf index, so cost varies from insert to insert; the variance term (c_L − c_R)² d / 4 grows with depth, whereas PHDAG's measured variance is near zero.

  • The crossover sits below every surveyed production registry. The depth at which IMT becomes more expensive than PHDAG is far beneath the depths actually deployed in production, meaning all surveyed production systems operate where PHDAG is strictly cheaper. (The truncated text does not state the numeric crossover depth; it reports only that it falls below every production registry surveyed.)

  • Cost asymmetry is architectural, not incidental. The authors attribute the gap to where the canonical history lives: the IMT is storage-canonical (a Merkle root in a storage slot, events auxiliary), while the PHDAG is log-canonical (the event stream carries the canonical metadata; storage slots act only as a queryable index for append-time integrity checks).

  • Registries are reconstructible without trust or off-chain dependencies. Because each append emits one event carrying identifier, manifest commitment, and parent reference, a single filtered log query over the deployment block range plus a one-pass loop recovers the full graph in O(|V|) time and O(|V|) space, with |E| ≤ |V|.

  • The storage tier ordering matters. Event logs are much cheaper than storage writes (approximately 375 gas per topic plus calldata-priced data, because contracts cannot read them), and the paper's cost model rests on the EIP-2929/3529 rule that storage cost depends only on cold versus warm status within the transaction — not on the size of global state.

Methodology in Plain English

The authors take two existing data structures and put them on the same footing. First, they strip the parent-hash DAG down to its minimal form — three storage writes to unique keys per append, one write to a shared counter, and one event — so that application-specific features do not contaminate the measurement. Second, they use the Tornado Cash-style frontier-based incremental Merkle tree as the comparison point, reimplemented in a minimal reference form.

They then reason about cost at the level of individual EVM operations, using the published gas prices for cold and warm storage reads and writes. Counting operations in the append function shows that the DAG path has no loop over registry size, whereas the Merkle path loops once per tree level; that difference alone produces the O(1) versus O(d) split. To go beyond worst-case bounds for the Merkle tree, they model the leaf index as a random variable and derive how many storage writes happen at each level from the binary digits of that index — this is what produces the mean and variance formulas rather than a single number.

Finally, they check the theory against reality: they deploy both contracts on Base Sepolia, run workloads at each depth from 1 to 25, and record the gas of each insert (over 500 transactions in total). The flatness of the DAG measurements and the slope of the Merkle measurements are the empirical test of the two complexity claims, and the point where the two lines cross is what defines the practical regime boundary.

Why This Matters

Impact on research. The paper converts a claim that was previously stated at the level of a whole system into an isolated, formally bounded primitive with named constants and a derived cost distribution. That makes the PHDAG comparable to other on-chain data structures on equal terms, and it introduces a stochastic treatment of IMT insert cost — mean and variance as functions of depth — that the existing literature, which generally reports an O(log N) headline, does not provide.

Real-world applications:

  • Provenance and attribution registries for digital artifacts, where the query pattern is "walk the lineage of this item" rather than "prove membership succinctly," and where registry size grows without bound.
  • AI agent and model provenance tracking, where downstream tools read the ledger as a coordination medium — the paper explicitly frames the trace-based coordination vocabulary of State-Flag, Event-Signal, and Threshold-Trigger as the consumer pattern.
  • Content-addressed artifact registries in the style of git or IPFS but anchored on-chain, where each entry references its parent by hash and integrity comes from hash-chain validation rather than a global root.
  • Audit and compliance logs that must be reconstructible from public chain data alone, without depending on a trusted indexer or an off-chain service that could disappear.

Industry relevance. The IMT is the deployed standard behind Tornado Cash, Semaphore, zkSync, Scroll, and Linea, and its O(log N) append cost is generally accepted as the price of succinct membership proofs. This paper argues that for registries where succinct membership proofs are not the dominant query, that price is being paid for a property the application does not use — and quantifies the difference. That is a direct argument for standardizing a second primitive alongside the IMT rather than defaulting to it.

Future Directions

  • Characterizing the non-uniform arrival regime. The stochastic model assumes uniformly distributed leaf indices, but real registries fill sequentially (i = 0, 1, 2, …). The authors flag this as a modeling caveat and gesture at the behavior over contiguous spans; a full treatment of adversarial or bursty insertion patterns remains open.

  • Extending the comparison to other append-only primitives. The paper positions IMT as one comparator among possible alternatives; the same formal-and-empirical treatment could be applied to sparse Merkle trees, other accumulator schemes, or hybrid storage-canonical/log-canonical designs.

  • Quantifying the cost of what PHDAG gives up. PHDAG has no Merkle root and therefore no succinct membership proof. The paper does not price the workarounds (for example, proving ancestry by replaying the parent chain), which is the natural next question for applications that need both cheap appends and some form of proof.

  • Standardization and cross-chain validation. The authors frame the regime analysis as an input to standardization. Replicating the depth sweep on other EVM chains — with different gas schedules or calldata pricing than the EIP-2929/3529 baseline measured on Base Sepolia — would test how portable the crossover result is.

Target Audience

Protocol designers and smart-contract engineers choosing a data structure for an on-chain registry will get the most direct value, particularly those building provenance, audit, or content-addressed systems where membership proofs are not the primary query. Researchers working on the economics of on-chain data structures will find the stochastic IMT cost model and the explicit constant-bounding useful as a template. It is also relevant to teams maintaining zero-knowledge infrastructure who want a clear statement of what the IMT's O(log N) append cost buys them and when it does not apply. Readers without EVM storage-model background will need to absorb the cold/warm gas schedule and the frontier-update pattern before the results land.

Authors’ abstract

Provenance trees are append-only directed acyclic graphs of artifact registrations anchored on a public blockchain, recently introduced as the data substrate of operator-gated provenance infrastructure. Their defining data-structural pattern is a parent-hash directed acyclic graph (PHDAG), in which each append performs a constant number of storage writes to previously-untouched slots. This pattern has not previously been isolated as a standalone primitive, formally bounded…

The full abstract on arXiv
Read the original paper