pith. sign in

arxiv: 2606.09593 · v1 · pith:Q2HPNCPJnew · submitted 2026-06-08 · 💻 cs.DC · cs.CR

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

Ian C. Moore , Fernando Paredes Garcia This is my paper

Pith reviewed 2026-06-27 14:51 UTC · model grok-4.3

classification 💻 cs.DC cs.CR
keywords parent-hash DAGPHDAGon-chain registrygas costconstant-time appendincremental Merkle treeprovenance treeblockchain storage
0
0 comments X

The pith

Parent-hash DAGs allow appends to on-chain registries at fixed gas cost independent of size or depth.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that a parent-hash directed acyclic graph structure lets each new entry into an on-chain provenance registry perform only a constant number of storage writes to untouched slots. This produces gas costs that stay flat regardless of how many prior entries exist or how deep the structure grows. A sympathetic reader would care because it removes the scaling penalty that forces registry operators to choose between high fees and small size. The authors contrast this with incremental Merkle trees, for which they derive a stochastic cost model showing linear growth in expected gas with depth, and they confirm the difference with measurements across depths 1 to 25 on Base Sepolia. They also show that the full registry state can be rebuilt trustlessly from public logs in time linear in the number of entries.

Core claim

PHDAG append is formalized as O(1) in gas cost because each insertion writes a fixed number of new parent hashes exclusively into previously untouched storage slots; the cost is therefore independent of registry size and tree depth. Empirical runs on Base Sepolia show PHDAG costs remain at 76,276 gas with standard deviation near 6 gas, while IMT per-insert cost grows linearly with depth. Closed-form expressions are derived for the mean and variance of IMT cost as a random variable over leaf index. The point at which IMT becomes more expensive lies below the depths of all surveyed production registries. Registry state can be reconstructed from event logs in linear time with no off-chain data.

What carries the argument

The parent-hash directed acyclic graph (PHDAG) pattern, in which each append writes a constant number of new hashes to previously untouched storage slots.

If this is right

  • On-chain registries using PHDAG can grow arbitrarily large while keeping per-append gas cost fixed.
  • The cost advantage over incremental Merkle trees appears at depths already exceeded by every production registry examined.
  • Trustless reconstruction of the entire registry from public event logs succeeds in time linear in the number of entries.
  • The stochastic model supplies explicit mean and variance formulas for the gas cost of each IMT insertion.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same constant-write pattern could be applied to other append-only structures that currently rely on Merkle trees for on-chain verification.
  • If gas invariance holds across EVM-compatible chains, operators could migrate registries without re-evaluating per-operation economics.
  • Linear-time reconstruction from logs remains feasible only if the total number of entries stays within practical query budgets for the target chain.

Load-bearing premise

The implementation can be realized so that every append performs only a constant number of storage writes exclusively to previously untouched slots, without hidden state-dependent overheads or additional writes that scale with current depth or size.

What would settle it

Deploy the PHDAG contract on an EVM chain and measure gas usage for successive appends; if measured costs rise materially with depth or total entries, the constant-time claim does not hold.

Figures

Figures reproduced from arXiv: 2606.09593 by Fernando Paredes Garcia, Ian C. Moore.

Figure 1
Figure 1. Figure 1: Architectural comparison of append-only primitives. [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Per-insert gas cost of PHDAG and IMT primitives as a function of tree depth. PHDAG (blue) is depth-invariant [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗
read the original 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 with explicit constants, or benchmarked against the standard alternative, the incremental Merkle tree (IMT). We formalize PHDAG append as O(1) in gas cost, independent of registry size and tree depth, and develop a stochastic cost model for IMT in which per-insert cost is a random variable over the leaf index, deriving closed-form expressions for its mean and variance. We validate both analyses empirically on Base Sepolia across tree depths 1 to 25. PHDAG is observed to be depth-invariant at 76,276 gas (standard deviation about 6 gas), while IMT cost grows linearly with depth. The crossover below which IMT is cheaper falls far beneath the depths of every production registry surveyed. We further establish trustless registry reconstruction from public event logs in linear time with no off-chain dependency.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper claims to introduce the Parent-Hash DAG (PHDAG) as a data structure for provenance trees on blockchain, where appends are performed with a constant number of storage writes to untouched slots, leading to O(1) gas cost independent of size and depth. It develops a stochastic model for the incremental Merkle tree (IMT) with closed-form mean and variance, validates both with empirical measurements on Base Sepolia showing constant cost for PHDAG at 76,276 gas and linear growth for IMT, and claims linear-time trustless reconstruction from event logs.

Significance. If the results hold, the work is significant as it provides a constant-cost alternative to IMT for on-chain append-only registries, with the empirical invariance and closed-form expressions for the comparator being notable strengths. This could enable more scalable provenance infrastructure on public blockchains. The reproducible nature of the empirical runs on a public testnet adds to the reliability of the findings.

minor comments (2)
  1. The standard deviation is given as 'about 6 gas'; providing the exact value and the number of trials would improve precision.
  2. Ensure that the closed-form expressions for the IMT mean and variance are presented clearly with all variables defined.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of the PHDAG paper, the accurate summary of its contributions, and the recommendation for minor revision. No major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's central claim formalizes PHDAG append cost as O(1) directly from its defining pattern of a fixed number of writes to untouched storage slots, then derives a closed-form stochastic model for the IMT comparator and validates both via external gas metering on Base Sepolia. No equations reduce a prediction to a fitted parameter by construction, no load-bearing self-citations appear, and the uniqueness of the O(1) bound is not imported from prior author work. The analysis is self-contained against the stated external benchmarks and empirical runs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The O(1) claim rests on the domain assumption that storage writes to untouched slots incur only fixed gas and that the PHDAG contract can be written to guarantee this property; the IMT model rests on the standard assumption that leaf-index distribution is uniform for the stochastic analysis. No free parameters or invented entities are introduced in the abstract.

axioms (2)
  • domain assumption Storage writes to previously untouched slots on the target EVM chain incur a fixed, depth-independent gas cost.
    Invoked to establish the constant-time bound for PHDAG appends.
  • domain assumption Leaf indices in an incremental Merkle tree are filled uniformly at random for the purpose of cost modeling.
    Required for the closed-form mean and variance expressions of the IMT cost random variable.

pith-pipeline@v0.9.1-grok · 5753 in / 1623 out tokens · 27992 ms · 2026-06-27T14:51:28.443454+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 6 canonical work pages · 3 internal anchors

  1. [1]

    Avail- able:https://github.com/tornadocash/tornado-core

    Tornado Cash Privacy Solution,tornado-core: MerkleTreeWithHistory.sol, GitHub repository, 2019–2022. Avail- able:https://github.com/tornadocash/tornado-core

    2019

  2. [2]

    Available: https://github.com/semaphore-protocol/semaphore

    Semaphore Protocol,semaphore: Semaphore.sol smart contracts, GitHub repository, 2020–2026. Available: https://github.com/semaphore-protocol/semaphore

    2020

  3. [3]

    Available: https://github.com/matter-labs/era-contracts

    Matter Labs,era-contracts: zkSync Era L1 and L2 smart contracts, GitHub repository, 2022–2026. Available: https://github.com/matter-labs/era-contracts

    2022

  4. [4]

    Available: https: //github.com/scroll-tech/scroll-contracts

    Scroll,scroll-contracts: Scroll zkEVM rollup smart contracts, GitHub repository, 2023–2026. Available: https: //github.com/scroll-tech/scroll-contracts

    2023

  5. [5]

    Consensys,linea-monorepo: Linea zkEVM smart contracts, prover, and coordinator, GitHub repository, 2023–

    2023

  6. [6]

    Available:https://github.com/Consensys/linea-monorepo

  7. [7]

    R. C. Merkle,A Digital Signature Based on a Conventional Encryption Function, Advances in Cryptology — CRYPTO ’87, LNCS 293, pp. 369–378, Springer, 1988

    1988

  8. [8]

    Chacon and B

    S. Chacon and B. Straub,Pro Git, 2nd Edition: Chapter 10 — Git Internals, Apress, 2014. Available: https: //git-scm.com/book/en/v2/Git-Internals-Git-Objects

    2014

  9. [9]

    IPFS - Content Addressed, Versioned, P2P File System

    J. Benet,IPFS — Content Addressed, Versioned, P2P File System, arXiv:1407.3561, 2014

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  10. [10]

    Albert, P

    E. Albert, P. Gordillo, A. Rubio, and I. Sergey,GASTAP: A Gas Analyzer for Smart Contracts, CoRR, vol. abs/1811.10403, 2018. 18 The Parent-Hash DAGA PREPRINT

    work page arXiv 2018

  11. [11]

    Grech, M

    N. Grech, M. Kong, A. Jurisevic, L. Brent, B. Scholz, and Y . Smaragdakis,MadMax: Surviving Out-of-Gas Conditions in Ethereum Smart Contracts, Proceedings of the ACM on Programming Languages, vol. 2, no. OOPSLA, Article 116, November 2018. doi:10.1145/3276486

    work page doi:10.1145/3276486 2018

  12. [12]

    Roughgarden,Transaction Fee Mechanism Design for the Ethereum Blockchain: An Economic Analysis of EIP-1559, arXiv:2012.00854, 2020

    T. Roughgarden,Transaction Fee Mechanism Design for the Ethereum Blockchain: An Economic Analysis of EIP-1559, arXiv:2012.00854, 2020

    work page arXiv 2012

  13. [13]

    Buterin,Blockchain Resource Pricing, Ethereum Research position paper, August 2018

    V . Buterin,Blockchain Resource Pricing, Ethereum Research position paper, August 2018. Available: https: //ethresear.ch/t/draft-position-paper-on-resource-pricing/2838

    2018

  14. [14]

    Buterin and M

    V . Buterin and M. Swende,EIP-2929: Gas Cost Increases for State Access Opcodes, Ethereum Improvement Proposals, no. 2929, September 2020. Available:https://eips.ethereum.org/EIPS/eip-2929

    2020

  15. [15]

    Buterin, M

    V . Buterin, M. Swende, and A. Beregszaszi,EIP-3529: Reduction in Refunds, Ethereum Improvement Proposals, no. 3529, April 2021. Available:https://eips.ethereum.org/EIPS/eip-3529

    2021

  16. [16]

    Tang,EIP-2200: Structured Definitions for Net Gas Metering, Ethereum Improvement Proposals, no

    W. Tang,EIP-2200: Structured Definitions for Net Gas Metering, Ethereum Improvement Proposals, no. 2200, July 2019. Available:https://eips.ethereum.org/EIPS/eip-2200

    2019

  17. [17]

    Wood,Ethereum: A Secure Decentralised Generalised Transaction Ledger, Ethereum Project Yellow Paper, Shanghai version, 2025

    G. Wood,Ethereum: A Secure Decentralised Generalised Transaction Ledger, Ethereum Project Yellow Paper, Shanghai version, 2025. Available:https://ethereum.github.io/yellowpaper/paper.pdf

    2025

  18. [18]

    I. C. Moore,Trustless Provenance Trees: A Game-Theoretic Framework for Operator-Gated Blockchain Registries, arXiv:2604.03434, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  19. [19]

    Ledger-State Stigmergy: A Formal Framework for Indirect Coordination Grounded in Distributed Ledger State

    F. Paredes García,Ledger-State Stigmergy: A Formal Framework for Indirect Coordination Grounded in Dis- tributed Ledger State, arXiv:2604.03997, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  20. [20]

    Laurie, A

    B. Laurie, A. Langley, and E. Kasper,Certificate Transparency, RFC 6962, IETF, June 2013. [Online]. Available: https://datatracker.ietf.org/doc/html/rfc6962

    2013

  21. [21]

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

    I. C. Moore and F. Paredes García,ar-phdag: Reference implementations, raw data, and analysis scripts for “The Parent-Hash DAG: A Cost Analysis of Constant-Time Append for On-Chain Registries”, GitHub repository, 2026. Available:https://github.com/AnchorRegistry/ar-phdag 19

    2026