PARENT-H ASH DAG: A C OST A NALYSIS OF C ONSTANT-T IME A PPEND FOR O N -C HAIN R EGISTRIES
arXiv:2606.09593v1 [cs.DC] 8 Jun 2026
A P REPRINT Ian C. Moore, PhD Principal, DeFiMind [email protected]
Fernando Paredes García Researcher, DeFiMind [email protected]
June 9, 2026
A BSTRACT 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. Keywords blockchain · provenance trees · append-only registry · Merkle tree · parent-hash DAG · gas cost · stochastic analysis · O(1) complexity · Ethereum
1
Introduction
Provenance trees (PTs) 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 for digital artifacts [17]. Each node in a PT carries a globally unique identifier, a parent reference binding it to its lineage, and a manifest commitment; the resulting structure is tamper-evident, publicly verifiable, and queryable by both humans and AI agents. This queryability is not incidental: a PT functions as a coordination medium in the sense of Paredes García [18], with downstream agents (verifiers, derivative-work registries, AI provenance tools) acting on the traces left by prior registrations rather than via direct message exchange. PTs are advanced in [17] together with an assertion that the underlying append operation is O(1), invariant to both registry size and tree depth, contrasted with the Θ(log N ) of Merkle-tree registries. The assertion is stated at a system level, in the context of a specific cryptographic commitment scheme for operator-gated attribution. It does not isolate the underlying data-structural pattern as a standalone primitive, does not characterize the distribution of per-insert cost, does not state the constants underlying the complexity classes, and does not establish the empirical crossover depth at which the pattern becomes cheaper than its standard alternative, the incremental Merkle tree. The present paper closes that gap. We isolate the data-structural nucleus of the PT construction, the parent-hash directed acyclic graph (PHDAG) primitive, in which each append performs a constant number of storage writes to previously-untouched slots without reference to tree geometry, and place it in direct comparison with the IMT
The Parent-Hash DAG
A P REPRINT
primitive that dominates production zero-knowledge protocols and rollup state commitments. The IMT, introduced in production settings by Tornado Cash [1] and adopted subsequently by Semaphore and the major zero-knowledge rollup state commitments, maintains a fixed-depth binary tree in which each append updates a logarithmic-length frontier. IMT serves in this paper as the comparator against which the PHDAG primitive’s properties are made legible: depth-dependent cost versus depth-invariant cost, growing variance versus near-zero variance, succinct inclusion proofs versus event-log reconstructibility. The IMT occupies a singular position in the deployed Ethereum ecosystem. It is the data structure underlying Tornado Cash’s anonymity sets [1], Semaphore’s zero-knowledge identity commitments [2], and the state commitments of the major zero-knowledge rollups: zkSync [3], Scroll [4], and Linea [5]. The pattern’s appeal in these settings is a single property: the O(log N ) Merkle inclusion proof, which permits a contract or off-chain verifier to confirm membership of a leaf without reference to the remainder of the tree. This property is essential to zero-knowledge applications, where in-circuit verification of membership must complete within a single transaction’s gas budget. The corresponding append cost, growing logarithmically in tree capacity, is accepted as the price of admission. For applications where succinct membership proofs are not the dominant query, the cost trade is less obviously favorable, and to our knowledge has not been examined. This paper makes four contributions: 1. Formal complexity analysis. We formalize the O(1) append complexity of PHDAG with explicit bounds on the number of EVM operations per transaction, and contrast it with the O(d) complexity of IMT. We further characterize the off-chain reconstruction complexity as O(|V |) (Section 3). 2. Stochastic cost model. We model per-insert gas cost as a random variable over the uniformly distributed leaf index. For IMT at depth d we derive closed-form expressions for the mean and variance of per-insert cost, obtaining E[g] = c0 + d2 (cL + cR ) and Var[g] = (cL − cR )2 d/4, where cL and cR are the per-level costs of a write level and a read level under the EVM storage-access gas schedule (Section 4). 3. Empirical validation. We deploy independent IMT and PHDAG contracts on Base Sepolia across depths 1–25 and measure per-insert gas cost for proportional workloads, totaling over 500 transactions (Section 6). 4. Crossover identification. We empirically locate the depth at which PHDAG becomes cheaper than IMT, and situate this crossover relative to production-deployed systems. The crossover falls below every surveyed production registry, placing all such systems in the regime where PHDAG is strictly cheaper and exhibits negligible per-insert variance (Section 7). The paper is structured as follows. Section 2 reviews the two primitives and establishes notation. Section 3 presents the formal complexity analysis. Section 4 develops the stochastic cost model. Section 5 describes the experimental setup. Section 6 presents the empirical results. Section 7 discusses the regime of applicability of each primitive and the implications for standardization. Section 8 surveys related work and Section 9 concludes.
2
Background and Notation
2.1
The EVM Gas Schedule
We work under the EVM gas schedule established by EIP-2929 and EIP-3529 [13, 14], which introduced the coldversus-warm access model for storage operations. Under this model, the EVM maintains a per-transaction access list of storage slots that have been touched during the transaction’s execution. The first access to a slot is cold and is billed at a higher rate; every subsequent access to the same slot within the same transaction is warm and is billed at a lower rate. The access list is reset at the start of every transaction. The schedule applies to both reads (SLOAD) and writes (SSTORE), with distinct cold and warm prices for each. The zero-versus-nonzero value-transition cases for SSTORE follow the net-metering definitions of EIP-2200 [15], and the underlying opcode and receipt semantics follow the Ethereum Yellow Paper [16]: • Cold SSTORE: ≈ 22,100 gas when writing to a storage slot not yet accessed in the current transaction. • Warm SSTORE: ≈ 5,000 gas when writing to a slot already accessed in the current transaction. • Cold SLOAD: ≈ 2,100 gas on first access in a transaction. • Warm SLOAD: ≈ 100 gas on subsequent access. Additional fixed costs include the base transaction cost (21,000 gas), calldata costs (4 gas per zero byte, 16 per non-zero byte), and event emission overhead. 2
The Parent-Hash DAG
A P REPRINT
The critical structural property of this schedule, for the purposes of this paper, is that the cost of a storage operation depends only on whether the target slot is cold or warm within the current transaction. It does not depend on the depth of the Merkle Patricia Trie representing global state, on the size of any contract’s storage, or on the total number of accounts in the network. This is the property that makes a constant-op contract truly O(1) in gas cost regardless of how large the registry becomes. We denote the aggregate fixed overhead per transaction by α, the marginal warm-SSTORE cost by β ≈ 5,000, and the marginal cold-SSTORE cost by γ ≈ 22,100. 2.2
Two Storage Tiers in the EVM
The EVM exposes two distinct on-chain storage tiers with different access, mutability, and cost characteristics. Both are persisted indefinitely by the network, but they serve different roles in contract design. Storage slots are modified via SSTORE and are part of the world state σ maintained by every full node. They are queryable by other contracts via SLOAD, mutable in principle (a contract can overwrite a previously written slot), and expensive (5,000–22,100 gas per write under the schedule of Section 2.1). Their canonical role is to carry the protocol’s current state in a form directly accessible from on-chain logic. Event logs are emitted via the LOG opcodes and are part of transaction receipts. They are not readable by smart contracts; once emitted, no opcode can modify or delete them, so they are structurally append-only at the EVM level. Each log is attested through the receipts root of the block header that contains its transaction, and is therefore verifiable from chain headers alone, independent of current world state. Event emission is substantially cheaper than storage writes (approximately 375 gas per topic plus calldata-priced data) because the EVM does not have to support contract-side reads against them. These two tiers permit a design choice the cost analysis in this paper turns on: where does the canonical history of an append-only registry live? A storage-canonical design places the history in slots (typically as a Merkle root commitment), with events serving as auxiliary notifications. A log-canonical design places the history in the event stream, with storage slots serving only as a queryable on-chain index. Both designs are durable; both are auditable; both are deployable. They differ in cost, in consumer access pattern, and in what kinds of queries each natively supports. The remainder of the paper analyzes one canonical instance of each choice. The incremental Merkle tree (Section 2.3) is a storage-canonical primitive: the Merkle root in storage is the commitment, and the event log is auxiliary. The parent-hash directed acyclic graph (Section 2.4) is a log-canonical primitive: the insertion event carries the complete metadata required for reconstruction (Proposition 2), and storage slots serve as a queryable index supporting appendtime integrity checks. The cost asymmetry between the two primitives, developed formally in Section 3 and empirically in Section 6, is a direct consequence of this architectural difference. Figure 1 renders this distinction visually. 2.3
The Incremental Merkle Tree Primitive
The IMT is a storage-canonical primitive in the sense of Section 2.2: the protocol’s canonical history is summarized in a Merkle root persisted to a storage slot, with the insertion event emitted as an auxiliary notification. Figure 1 (left panel) shows the structure visually. Conceptually, an IMT of depth d is a complete binary tree of capacity N = 2d leaves. Internal nodes are hashes of their children; unpopulated leaves hold a precomputed zero hash. The hash at the root of the tree is a cryptographic commitment to the entire current state: any change to any leaf changes the root. This single-value commitment is what makes the IMT useful. A verifier in possession of the root and a sequence of d sibling hashes (the inclusion proof [6]) can confirm membership of any leaf without reference to the rest of the tree. An append to an IMT works as follows. A new leaf is placed at the next unfilled position in leaf-index order, left-to-right. The contract must then recompute the chain of internal hashes from the new leaf up to the root. To avoid re-reading the entire tree on every append, the contract maintains a frontier: an array of length d caching the rightmost filled internal node at each level. The append walks up the frontier, updating cached nodes as it goes, and writes the new root to its storage slot. Figure 1 highlights the frontier path traversed by a single append in accent color. The pattern descends from the Merkle tree construction of Merkle [6] and the append-only Merkle log pattern of Certificate Transparency [19]. The fixed-capacity, frontier-based variant we analyze here was crystallized as a production Ethereum primitive by the MerkleTreeWithHistory contract of Tornado Cash [1], from which Semaphore [2] and 3
The Parent-Hash DAG
A P REPRINT
Figure 1: Architectural comparison of append-only primitives. Left (IMT, storage-canonical): an append updates the frontier path through a fixed-depth binary tree (here d = 3), recomputing the root in contract storage. The event log carries an auxiliary insertion notification. Cost grows with depth. Right (PHDAG, log-canonical): an append emits a node into the event log of the block containing its transaction, with parent references linking nodes across blocks. Contract storage carries only an index supporting append-time integrity checks. Cost is constant in depth and in registry size. Accent color marks elements active during the current append.
the major zero-knowledge rollups [3, 4, 5] inherit the design. We adopt an equivalent minimal reference implementation in the present work to isolate the primitive’s cost from application-specific overhead. The cost-relevant property of the IMT is its frontier-update pattern. At each level k ∈ {0, 1, . . . , d − 1} during an insert at leaf index i, the contract writes to filledSubtrees[k] iff bit k of i is zero; otherwise it reads filledSubtrees[k] and does not write. In addition to this per-level conditional write, the contract always writes to the root and nextIndex slots. This asymmetric write pattern is the source of IMT’s depth-dependent cost and cost variability. 2.4
The Parent-Hash DAG Primitive
The PHDAG is a log-canonical primitive in the sense of Section 2.2: the protocol’s canonical history is carried in the event stream, with storage slots serving as a queryable on-chain index that supports append-time integrity checks. Figure 1 (right panel) shows the structure visually. Conceptually, a PHDAG is a directed acyclic graph built incrementally: each appended node carries a globally unique identifier and a pointer to a previously-appended parent node, and the structure grows one node at a time. There is no fixed geometric shape: nodes may branch arbitrarily, depth is unbounded, and the parent reference is the only inter-node link. The structure’s integrity comes from the chain of parent references and from the content commitment (manifest hash) carried by each node, not from any global root commitment. There is no Merkle root, and accordingly no succinct membership proof of the kind IMT provides. An append to a PHDAG works as follows. The inserting party submits three values: a globally unique identifier arId, a parent reference (or the zero value if this is a root node), and a manifest commitment. The contract writes these into three mapping-backed storage slots, each keyed by arId, and emits an insertion event carrying the full metadata. Because arId is globally unique by construction, every append writes to three storage slots that have never been written to before in the contract’s lifetime: three cold SSTOREs. The storage slots are not where the registry’s canonical state lives; their purpose is to enable the contract to validate, at the next append, that a referenced parent exists. The canonical state lives in the event log, distributed across the blocks containing the registry’s inserts. Figure 1 shows two nodes appended in adjacent blocks, with the parent reference linking them across the block boundary. The pattern descends from the parent-hash content-addressed structures of git [7] and IPFS [8], both of which build DAGs in which each node references its parent(s) by content hash and the structure’s integrity is enforced by hash-chain validation rather than by a global commitment. The PHDAG primitive analyzed here adapts this pattern to the on-chain setting and was introduced as the data-structural core of the AnchorRegistry provenance registry of Moore [17], where each node carries application-specific metadata not considered in the present analysis. For our cost analysis we treat the primitive in its minimal form: three SSTOREs per append to unique keys, plus one SSTORE to the shared counter slot, plus an insertion event. The reference contract used for our empirical work implements exactly this minimal form. 4
The Parent-Hash DAG
A P REPRINT
The cost-relevant property of the PHDAG is that each append’s storage writes target previously-untouched slots, with no dependence on any geometric parameter (depth, capacity, registry size). This is the property that yields the O(1) append complexity formalized in Section 3. 2.5
Notation
Throughout, we denote: • n: the number of anchors currently registered in the registry • d: tree depth parameter for IMT, fixed at contract deployment. For PHDAG the notion of depth applies graph-theoretically to nodes (distance from root along parent references) but is not a parameter of the contract or of any cost expression in this paper. • N = 2d : IMT capacity • i: leaf index of a given insert, uniformly distributed in [0, N ) • g: total gas consumed by a single insert, treated as a random variable • α: fixed per-transaction overhead (base tx + calldata + event) • β: marginal cost per warm SSTORE (≈ 5,000 gas) • γ: marginal cost per cold SSTORE (≈ 22,100 gas) • c0 : fixed per-insert overhead for the IMT cost model (base tx, calldata, event, and the unconditional root/nextIndex writes) • cL : marginal cost of an IMT write level (left-child level: SSTORE + SLOAD + keccak256 + overhead) • cR : marginal cost of an IMT read level (right-child level: SLOAD + keccak256 + overhead) • W (i, d): number of write levels for an insert at leaf index i, equal to d − pop(i) (Lemma 3) • pop(x): the Hamming weight (popcount) of x • |V |: the number of nodes in a provenance tree V 2.6
The Ledger as Coordination Medium
A property orthogonal to the cost analysis but central to the role of append-only registries in practice is the function of the ledger as a coordination medium. Paredes García [18] develops this perspective formally as ledger-state stigmergy: autonomous agents (bots, indexers, downstream contracts, AI tools) coordinate not by exchanging messages but by reading shared ledger state and reacting to traces left by prior actions. Smart contracts in this reading are coordination artifacts embedded in the medium; each append leaves a persistent, cryptographically authenticated, globally visible trace that subsequent agents may act upon. The framework identifies three recurring patterns for such coordination: State-Flag (agents poll storage variables), Event-Signal (agents subscribe to event logs), and Threshold-Trigger (agents act when quantitative state variables cross a boundary). We adopt this vocabulary throughout: the reconstruction property of PHDAG (Section 3) is presented as a structural guarantee, and its coordination-medium consequences are developed in Section 7.
3
Formal Complexity Analysis
We begin by establishing the structural complexity of each primitive, independent of any stochastic or empirical refinement. The results of this section are statements about the number of EVM operations executed per append, from which gas-cost asymptotics follow under the fixed-per-opcode pricing of EIP-2929/3529. 3.1
PHDAG Append is O(1)
Lemma 1 (Bounded On-Chain Operations). The PHDAG append function executes a fixed, bounded number of EVM operations, independent of the registry size n and of any notion of tree depth. Proof. The append function executes exactly the following steps: 1. Input validation (length and non-empty checks on the identifier and manifest commitment): O(1). 5
The Parent-Hash DAG
A P REPRINT
2. A bounded number of lookups into the registered mapping: one SLOAD to confirm the new identifier is unused, and, for a non-root append, one further SLOAD to confirm the referenced parent exists (a root append, whose parent reference is the zero value, skips the second by short-circuit evaluation). At most two SLOADs, each with constant gas cost. 3. For the general (non-root) append, three SSTORE operations writing the identifier, parent reference, and manifest commitment to slots keyed by the unique arId. When the parent reference is the zero value (a root append, the case measured in Section 6), the write to parents[arId] stores zero to an already-zero slot and is billed at the no-op rate rather than as a zero-to-nonzero set, leaving two cold sets (2γ) plus one zero-store; a non-root append writes a nonzero parent and incurs the third set (3γ). Either way the count is a fixed constant independent of n and of depth. 4. One SSTORE updating the monotonic counter, preceded by one SLOAD of the counter slot: a single read and a single warm write at β gas. 5. Emission of one insertion event with a fixed number of topics and a bounded data payload. Each of the five steps performs a fixed number of EVM operations: step 1, a constant number of validation opcodes; step 2, at most two SLOADs; step 3, three SSTOREs (two cold sets and one zero-store for a root append, three cold sets for a non-root append); step 4, one SLOAD and one SSTORE; step 5, exactly one event emission. Thus no step contains a loop, iteration, or traversal whose count varies with n or with any property of the registry. The total opcode count is therefore the sum of these per-step constants, which is itself a constant c1 independent of n and of any depth. The insertion event in step 5 above is not auxiliary to the storage writes in steps 3 and 4; under the log-canonical design of Section 2.2, it carries the canonical metadata that the storage slots merely index. Both are necessary, and both are constant-cost. Lemma 2 (Registry-Size Invariance). The gas cost of a PHDAG append is invariant to the global registry size n. Formally, treating the per-append storage gas G(n) as a function of the registry’s pre-append cardinality n ∈ N0 , ∂G = 0. ∂n Proof. The proof proceeds in four parts: a formal model of the contract’s storage footprint, a formal model of the EVM’s per-transaction access list under EIP-2929/3529, a step-by-step execution trace of the append, and the resulting invariance. (i) Contract storage footprint. The persistent state of the deployed PHDAG contract is modeled as a key-value mapping σ : K → V, where K = V = {0, 1}256 . For a registry of size n, the occupied storage footprint O(n) ⊂ K partitions into four disjoint subsets: O(n) = Sreg (n) ∪ Spar (n) ∪ Sman (n) ∪ {kctr }, where Sreg , Spar , Sman are the slot sets for the registered, parents, and manifests mappings respectively, each of cardinality n, and kctr is the fixed slot holding the monotonic counter count. Thus |O(n)| = 3n + 1, growing linearly with n. For a mapping declared at storage position p, the address of the entry under key κ is given by the Solidity storage layout specification: k(κ, p) = keccak256(κ ∥ p). (ii) Per-transaction access list. Under the EIP-2929/3529 gas schedule (Section 2.1), each transaction maintains a transient access list At ⊂ K recording the slots touched at or before execution step t. The cost of a write to slot k at step t is: γ k∈ / At (cold) CostSSTORE (k, At ) = β k ∈ At (warm) with γ ≈ 22,100 and β ≈ 5,000 gas. The cost of a read (SLOAD) at slot k has the analogous form with constants γR ≈ 2,100 and βR ≈ 100. After any access at slot k, the list updates monotonically: At+1 = At ∪ {k}. Critically, A0 = ∅ at the start of every transaction: the access list does not persist across transactions and does not depend on O(n). (iii) Execution trace. Let the append be invoked with a fresh identifier κ∗ and parent reference κpar . By construction (Section 2.4), κ∗ has not been used in any prior append, so k(κ∗ , preg ), k(κ∗ , ppar ), k(κ∗ , pman ) ∈ / O(n) for the respective mapping positions preg , ppar , pman . The contract executes the following storage-touching steps: 6
The Parent-Hash DAG
A P REPRINT
t = 0 Duplicate check. SLOAD on k(κ∗ , preg ) to confirm the new identifier is unused. This slot is not in A0 = ∅, so the access is cold, costing γR . A1 = {k(κ∗ , preg )}. t = 1 Parent existence check. SLOAD on k(κpar , preg ). For a non-root append this slot is not in A1 , so the access is cold, costing γR ; for a root append (κpar = 0) the check is skipped by short-circuit evaluation and this SLOAD does not occur. We trace the non-root case, which is the general one. A2 = A1 ∪ {k(κpar , preg )}. t = 2 Write registered[arId]. SSTORE on k(κ∗ , preg ). This slot was warmed by the duplicate check at t = 0, but holds the zero value until now; the write is a zero-to-nonzero allocation billed at the cold SSTORE rate γ. A3 = A2 (slot already present). t = 3 Write parents[arId]. SSTORE on k(κ∗ , ppar ). Different mapping position, so the keccak256 output is distinct; not in A3 . For a root append (κpar = 0, the case measured in Section 6) this stores zero to an already-zero slot: a zero-to-zero no-op billed at the warm/no-op rate, not a cold allocation. For a non-root append the value written is nonzero, giving a cold allocation γ. We carry the non-root cost γ as the general case; the root case substitutes the smaller zero-store cost. A4 = A3 ∪ {k(κ∗ , ppar )}. t = 4 Write manifests[arId]. SSTORE on k(κ∗ , pman ). Distinct from prior slots by the same argument; not in A4 . Cold allocation: γ. A5 = A4 ∪ {k(κ∗ , pman )}. t = 5 Read counter. SLOAD on kctr (compiled from count += 1). Not in A5 , so cold: γR . A6 = A5 ∪ {kctr }. t = 6 Write counter. SSTORE on kctr . Now in A6 (warmed by the immediately preceding SLOAD). Warm: β. (iv) Invariance. The total storage gas of the append is G(n) = 3γR + |{z} 3 cold SLOADs
3γ |{z}
3 cold SSTOREs
+
β |{z}
1 warm SSTORE
for a non-root append, with the root case omitting one SLOAD (2γR in place of 3γR ) and replacing one cold set with a zero-store (two cold sets in place of three, since the zero parent reference is stored to an already-zero slot). Each term is a protocol constant; none is a function of n. The access list At at each step is a function of the transaction’s own prior steps, not of O(n), because A0 = ∅ and the only insertions into A during the append are the slots the append itself touches. The cold/warm classification of each step is therefore determined by the transaction’s internal structure and is independent of n. Consequently, ∂G = 0, ∀n ∈ N0 . ∂n The remaining per-transaction costs (base transaction, calldata, opcode execution outside storage, event emission) are functions of the transaction’s input length and opcode sequence, both fixed for a given append, and are likewise independent of n. The total cost gPHDAG is therefore a constant function of n. Theorem 1 (O(1) Gas Complexity of PHDAG Append). The gas cost gPHDAG of a PHDAG append satisfies gPHDAG ≤ C for some constant C > 0, and in particular gPHDAG = O(1) with respect to both the global registry size n and any notion of tree depth. Proof. By Lemma 1, the number of EVM operations per append is bounded by a constant c1 . By Lemma 2, the gas cost of each such operation is independent of n. Therefore the total gas cost is bounded by a constant C proportional to c1 . PHDAG has no tree-depth parameter, so depth-invariance holds vacuously. Writing out the constant explicitly: gPHDAG ≈ αPHDAG + 3γ + 3γR + β, (1) for a non-root append, where αPHDAG bundles the base transaction cost, calldata, event emission, and input validation; 3γ is the three cold SSTOREs writing to unique keys; 3γR is the three cold SLOADs of Lemma 2 (duplicate check, parent existence check, counter read); and β is the warm SSTORE to the counter. The root append benchmarked in Section 6 differs in two fixed terms (Lemma 2): it omits the parent-existence SLOAD (2γR in place of 3γR ), and its write to parents[arId] stores the zero parent reference to an already-zero slot, a zero-to-zero no-op in place of a third cold set (2γ in place of 3γ). The expression above is therefore the count of structural operations, not a closed-form gas total: the per-operation prices γ, γR , β are upper nominal figures, and the value-transition cases (a slot pre-warmed by an earlier SLOAD, a zero-to-nonzero set versus a zero-store) are priced distinctly under EIP-2200/2929/3529. We do not propagate these into a hand-derived constant; the per-append constant is read directly from the measurement in Section 6. What the expression establishes is the property that matters for Theorem 1: a fixed set of storage operations, independent of n and of depth, hence a fixed gas cost. 7
The Parent-Hash DAG
3.2
A P REPRINT
IMT Append is O(d)
By the structural write pattern described in Section 2, IMT append executes a loop of length d, with each iteration performing either an SLOAD or an SSTORE depending on the leaf index parity. The number of EVM operations per append therefore scales linearly in d. Proposition 1 (O(d) Gas Complexity of IMT Append). The gas cost gIMT of an IMT append at depth d satisfies gIMT = O(d) with respect to tree depth. The precise distribution of per-append cost within the O(d) envelope is the subject of the stochastic analysis in Section 4. 3.3
Off-Chain Reconstruction is O(|V |)
A property orthogonal to per-append cost is the complexity of reconstructing the complete registry from public blockchain data alone. For PHDAG, the registry state is fully encoded in the sequence of insertion events; no off-chain index is required for correctness. Proposition 2 (O(|V |) Trustless Reconstruction). Let V be the set of nodes registered in a deployed PHDAG contract instance up to the current block height. Given the deployment block Bstart and the contract address, the complete directed acyclic graph G = (V, E) is reconstructible from public event logs alone in time O(|V |) and space O(|V |), with no dependency on any off-chain index or trusted service. The edges in E are oriented parent→child, consistent with the ancestry-integrity convention of [17]. Proof. The proof proceeds in four parts: the event log model, an explicit reconstruction algorithm, time complexity, and space complexity. (i) Event log model. Each invocation of the PHDAG append function emits exactly one Appended event carrying the full metadata of the registered node. Model the j-th such event as the tuple Lj = ⟨κj , µj , κpar,j ⟩, where κj is the unique identifier, µj is the manifest commitment, and κpar,j is either the parent’s identifier or the sentinel ∅ if κj is a root node. A single eth_getLogs call filtered by the event signature hash T0 = keccak256(“Appended(bytes32,bytes32,bytes32)”) over the block range [Bstart , Bcurrent ] returns the chronologically ordered sequence S = [L1 , L2 , . . . , Lm ]. The contract reverts on duplicate identifiers (Section 2.4), so each event corresponds to a distinct node, and the append-only nature of the ledger guarantees no event is lost. Therefore m = |V |. (ii) Reconstruction algorithm. Initialize an empty graph G = (V, E) with V = ∅, E = ∅, and an empty hash map M (with amortized O(1) insertion). Process S in a single pass: 1: for each Lj = ⟨κj , µj , κpar,j ⟩ ∈ S do 2: V ← V ∪ {κj } 3: M[κj ] ← µj 4: if κpar,j ̸= ∅ then 5: E ← E ∪ {(κpar,j , κj )} 6: end if 7: end for The edge ordering (κpar,j , κj ) encodes the provenance direction parent→child. (iii) Time complexity. Fetching S is an O(|V |) data transfer over the JSON-RPC interface. Each iteration of the loop performs a constant number of operations: one vertex insertion (cV ), one hash-map insertion (cM , amortized constant), one conditional test, and at most one edge insertion (cE ). Letting Cloop = cV + cM + cE , T (|V |) =
|V | X
Cloop = Cloop · |V | = O(|V |).
j=1
(iv) Space complexity. The algorithm stores each identifier once in V and once as a key in M, and each non-root node contributes one edge to E. Because every node has at most one parent reference, |E| ≤ |V |. The total space is therefore S(|V |) = |V | + |V | + |E| ≤ 3|V | = O(|V |). The graph is fully recovered in linear time and space without invoking any off-chain index or trusted service. 8
The Parent-Hash DAG
A P REPRINT
This property is significant for the robustness of PHDAG-based registries: the integrity of the registry is not coupled to any off-chain service. A complete re-sync can be performed by any party with read access to the blockchain, with time complexity linear in the registry size and no other dependencies.
4
A Stochastic Model of IMT Per-Insert Cost
Theorem 1 and Proposition 1 establish the structural complexity classes of the two primitives. We now refine the IMT analysis by modeling the per-insert cost as a random variable whose distribution is determined by the binary representation of the leaf index. 4.1
The Frontier Write Distribution
Lemma 3 (Frontier Write Count). For an insert at leaf index i ∈ [0, 2d ), the number of filledSubtrees[k] slots written during the frontier update loop is W (i, d) = d − pop(i mod 2d ), where pop(·) denotes the Hamming weight. Proof. The proof proceeds in four parts: the frontier state model, the recurrence governing the loop’s index variable, the mutation condition at each level, and the resulting Hamming-weight identity. (i) Frontier state. An IMT of depth d maintains an array f = [f0 , f1 , . . . , fd−1 ] holding the rightmost filled internal node at each level. The insertion routine traverses levels k = 0, 1, . . . , d − 1 from leaf to root, conditionally updating f at each level. Let bk (i) denote the k-th bit of i in its unique base-2 expansion: i=
d−1 X
bk (i) · 2k ,
bk (i) = ⌊i/2k ⌋ mod 2.
k=0
(ii) Loop recurrence. The contract maintains a local variable xk tracking the active node index at level k, with initial value and update rule: x0 = i, xk+1 = ⌊xk /2⌋. Unrolling the recurrence to depth k yields the closed form xk = ⌊i/2k ⌋. (iii) Mutation condition. At level k the contract writes to fk iff xk corresponds to a left child of its parent in the binary tree, equivalently, iff xk is even. When xk is odd, the loop instead reads fk to combine with xk ’s sibling and ascends without writing. The write condition is therefore Writek ⇐⇒ xk ≡ 0
(mod 2) ⇐⇒ ⌊i/2k ⌋ mod 2 = 0 ⇐⇒ bk (i) = 0.
Let Ik = I(bk (i) = 0) = 1 − bk (i) be the indicator of a write at level k. (iv) Total write count. Summing the indicator over all d levels: W (i, d) =
d−1 X k=0
Ik =
d−1 X
d−1 X bk (i). 1 − bk (i) = d −
k=0
k=0
The remaining sum is the count of 1-bits in the low d bits of i, which is by definition pop(i mod 2d ). Therefore W (i, d) = d − pop(i mod 2d ).
Corollary 1 (Total Warm-SSTORE Count). The total number of warm SSTORE operations performed per IMT insert is S(i, d) = W (i, d) + 2 = d − pop(i mod 2d ) + 2, where the additive 2 accounts for the unconditional writes to root and nextIndex. 9
The Parent-Hash DAG
4.2
A P REPRINT
Distribution of Cost
Treating the leaf index i as uniformly distributed on [0, 2d ), the popcount P = pop(i) is distributed as a sum of d independent Bernoulli(1/2) random variables: P ∼ Binomial(d, 1/2). Remark 1 (On the uniform-index assumption). Real-world appends populate the IMT sequentially in leaf-index order i = 0, 1, 2, . . ., which is not uniform. We model i as uniformly distributed in [0, 2d ) because the cost of an append depends on i only through its low-order bit pattern (Lemma 3), and across any contiguous span of 2d sequential indices the popcount distribution coincides exactly with the binomial. The uniform model is therefore the correct lifetime-average distribution for the per-insert cost: it is the mean over a full epoch of 2d sequential appends, not an idealization that abstracts away the order of insertion. This lifetime-average assumption should be distinguished from the index distribution sampled by our experiments. The depth sweep (Section 5) measures only the first max(d, 2) appends at each depth, i.e. the small indices i = 1, 2, 3, . . ., which have low Hamming weight and hence an above-average write-level count W = d − pop(i). The sweep is thus a write-heavy sub-sample of the lifetime distribution, not a uniform draw from it. The two coincide only in the limit of a fully populated tree. This distinction is load-bearing for interpreting the measured mean slope and crossover (Sections 4.5 and 6.3): the model evaluated at the uniform distribution and the model evaluated at the sweep’s sampled indices are the same model, and both are reported. Non-uniform write schedules in the wild (skipping indices, adversarial ordering) are excluded by the monotonic counter in the canonical IMT implementation; an inserting party cannot choose its leaf index. Theorem 2 (Moments of Warm-SSTORE Count). Under uniform sampling of the leaf index i over the tree capacity index space Ω = {0, 1, . . . , 2d − 1}, the per-insert warm-SSTORE count S defined in Corollary 1 has moments E[S] = d2 + 2,
(2)
Var[S] = d4 .
(3)
Proof. The proof proceeds in four parts: the probability space, the decomposition of the leaf index into independent Bernoulli bits, the resulting binomial distribution of the popcount, and the application of linearity and scale-translation to compute the moments of S. (i) Probability space. Let (Ω, F, P) be a finite probability space with Ω = {0, 1, . . . , 2d − 1}, F = 2Ω , and the uniform probability measure 1 P(I = i) = d , ∀i ∈ Ω. 2 By Corollary 1, the warm-SSTORE count is the deterministic transformation S(I, d) = d − pop(I) + 2. (ii) Bit-level decomposition. Define d random variables B0 , B1 , . . . , Bd−1 as the binary digits of I: I=
d−1 X
Bk · 2 k ,
Bk = ⌊I/2k ⌋ mod 2.
k=0
For each k, exactly half of the integers in Ω have bit k set, so 2d−1 1 = , d 2 2 giving Bk ∼ Bernoulli(1/2). Moreover, the uniform measure on Ω factorizes exactly as a product of d Bernoulli(1/2) measures: for any bit pattern (b0 , . . . , bd−1 ) ∈ {0, 1}d , P(Bk = 1) =
d−1
P(B0 = b0 , . . . , Bd−1 = bd−1 ) =
Y 1 = P(Bk = bk ). 2d k=0
Therefore the bits {Bk }d−1 k=0 are i.i.d. Bernoulli(1/2). (iii) Binomial distribution of the popcount. The Hamming weight is the sum of the indicator bits: P = pop(I) =
d−1 X k=0
10
Bk .
The Parent-Hash DAG
A P REPRINT
As a sum of d i.i.d. Bernoulli(1/2) variables, P follows the binomial distribution P ∼ Binomial(d, 1/2), with first and second moments E[P ] = d · 12 = d2 ,
Var[P ] = d · 12 · 12 = d4 .
(iv) Moments of S. Applying linearity of expectation to S = d − P + 2: E[S] = d − E[P ] + 2 = d − d2 + 2 = d2 + 2. Applying the scale-translation rule Var[aX + b] = a2 Var[X] with a = −1 and b = d + 2: Var[S] = (−1)2 Var[P ] = Var[P ] = d4 . This establishes both moments. These are the moments of the write count itself. To turn them into gas, we attach a cost to each level type and propagate the distribution of W through the resulting affine cost expression; this is the content of the next theorem. Theorem 3 (Moments of Per-Insert Gas Cost). The per-insert gas cost g of an IMT append decomposes by level type. Each level of the frontier loop is either a write level (a left-child level, where filledSubtrees[k] is updated) or a read level (a right-child level, where the slot is read but not written). Writing W = W (i, d) for the write-level count of Lemma 3, the cost is g = c0 + cL · W + cR · (d − W ), where c0 is the fixed per-transaction overhead (base transaction, calldata, event emission, and the unconditional root and nextIndex writes), cL is the marginal cost of a write level, and cR is the marginal cost of a read level. Under uniform leaf-index sampling, with E[W ] = d/2 and Var[W ] = d/4 (Theorem 2, via W = d − P ), E[g] = c0 + d2 (cL + cR ), 2
Var[g] = (cL − cR ) p √ and the standard deviation is Var[g] = |cL − cR | d/2.
· d4 ,
(4) (5)
Proof. The level-type decomposition is exact: the frontier loop runs d iterations, of which exactly W are write levels and d − W are read levels (Lemma 3). Each write level executes the same opcode sequence (one SSTORE updating a slot that already holds a nonzero value, one SLOAD of the precomputed zero hash, one keccak256, and fixed loop overhead), so it has a fixed marginal cost cL ; each read level executes one SLOAD, one keccak256, and the same loop overhead, with fixed marginal cost cR . The per-transaction remainder is collected into c0 . This gives g = c0 + cL W + cR (d − W ) = c0 + cR d + (cL − cR )W , an affine function of the single random variable W . Applying linearity of expectation and the scale-translation rule Var[aX + b] = a2 Var[X] with the moments of W yields Equations 4 and 5. The constants c0 , cL , and cR are determined by the EVM gas schedule and the contract’s opcode sequence.1 Rather than fix them from first principles, we calibrate them against the empirical measurements (Section 6), where a regression of per-insert gas on (W, d − W ) recovers cL ≈ 7,950, cR ≈ 2,750, and c0 ≈ 37,800 gas with coefficient of determination R2 > 0.999, confirming both the level-type decomposition and the constancy of the per-level costs. Remark 2 (Relation to the warm-SSTORE count). The warm-SSTORE count S = W + 2 of Corollary 1 counts only the storage writes. It is not by itself a cost model, because the read levels also carry depth-linear cost (cR per level) through their SLOAD and keccak256 operations. A cost model of the form g = α + βS, which prices only the SSTOREs and treats the read levels as part of the fixed overhead, undercounts the per-depth cost and overstates the crossover depth (Section 4.5). The level-type decomposition above is the corrected model. 1
A write level combines an SSTORE to an already-nonzero slot (the frontier slot holds a nonzero hash from contract initialization onward, so the update is billed as a value-change reset rather than a zero-to-nonzero allocation), a cold SLOAD of the zero-hash table, a keccak256 over two words, and loop overhead. A read level omits the SSTORE. The cold/warm and zero/nonzero pricing of EIP-2929/3529 makes both per-level costs constants independent of depth and registry size.
11
The Parent-Hash DAG
4.3
A P REPRINT
Asymptotic Behavior
p √ The mean cost E[g] scales linearly in d with slope (cL +cR )/2. The standard deviation Var[g] scales as |cL −cR | d/2, sub-linearly in d but still growing in absolute terms. Two features of these expressions are worth drawing out. First, the variance is governed by the difference cL − cR between the two per-level costs, not by either cost alone. The randomness in per-insert cost comes entirely from which levels are writes and which are reads; if write levels and read levels cost the same (cL = cR ), the per-insert cost would be deterministic at c0 + d cL regardless of leaf index. The cost variance is thus a direct consequence of the cost asymmetry between level types. Second, the coefficient of variation
√ |cL − cR | d/2 CV(g) = c0 + d (cL + cR )/2
√ √ approaches |cL − cR |/ d (cL + cR ) in the large-d limit and therefore decreases as Θ(1/ d), even as the absolute √ standard deviation grows as Θ( d). IMT cost becomes proportionally more predictable with depth while becoming absolutely less so. 4.4
PHDAG as a Degenerate Case
The stochastic framework developed above for IMT covers PHDAG as well, but as a trivial instance. For IMT, the warm-SSTORE count S is a random variable: its value depends on the leaf-index bit pattern, with mean d/2 + 2 and variance d/4 (Theorem 2). For PHDAG, the analogous quantity is deterministic: every append performs exactly the same number of storage operations (three cold SSTOREs and one warm SSTORE, alongside the fixed two-or-three SLOADs of Lemma 2), independent of any input or registry state. As S counts warm SSTOREs by definition, the SLOADs sit outside the count S but are equally deterministic and equally independent of registry state. A random variable that takes a single value with probability 1 is called degenerate; it has the same distribution as a non-random constant. In this sense, SPHDAG = 4 almost surely, with E[SPHDAG ] = 4 and Var[SPHDAG ] = 0. PHDAG is not outside the framework; it is the framework’s trivial case, where all randomness collapses. This framing matters for what it predicts about empirical variance. The framework attributes any non-zero variance in gPHDAG to sources outside the structural cost model: calldata byte-level variation (different counts of leading-zero bytes in the random arId), and other non-structural per-transaction effects. The empirically observed σPHDAG ≈ 6 gas (Section 6), with measured costs falling on a small number of discrete levels spaced 12 gas apart, is consistent with this prediction: the residual variance is small and traceable to calldata composition rather than to any depth- or registry-size-dependent quantity. 4.5
The Crossover Depth
Equating the corrected mean IMT cost (Equation 4) with the constant PHDAG cost (Equation 1) and solving for d gives the depth at which the two primitives have equal mean cost: d∗ =
gPHDAG − c0 . (cL + cR )/2
(6)
Using the calibrated constants c0 ≈ 37,800, cL ≈ 7,950, cR ≈ 2,750 gas (Section 6) and the measured gPHDAG = 76,276 gas, 76,276 − 37,800 38,476 d∗ ≈ ≈ ≈ 7.2. (7,950 + 2,750)/2 5,350 This uniform-index crossover is the apples-to-apples comparison: the lifetime-average IMT cost (the mean over a full epoch of 2d sequential inserts, for which the popcount distribution is exactly binomial; see Remark 1) against the constant PHDAG cost. The depth sweep observes a slightly lower crossover, at d = 6, and this is fully accounted for by the sweep’s index distribution rather than by any gap in the model. The sweep populates each tree with the small leaf indices i = 1, 2, 3, . . ., whose low Hamming weight gives an above-average write-level count: at d = 5 the sampled mean is W ≈ 3.75 against the uniform expectation d/2 = 2.5, and at d = 6 it is W ≈ 4.6 against 3.0. Evaluating the fitted cost model at the sweep’s actual sampled indices reproduces the measured per-depth means to within the residual scale of Section 6.3 (for example 78,248 predicted versus 78,293 measured at d = 6) and yields the same crossover at d = 6. The uniform-index value d∗ ≈ 7.2 and the as-sampled value d = 6 are therefore the same model under two index distributions: the former is the lifetime average, the latter the write-heavy low-index slice the sweep measured. 12
The Parent-Hash DAG
A P REPRINT
The practical conclusion is insensitive to this distinction. Whether the crossover is taken as the lifetime-average 7.2 or the write-heavy as-sampled 6, it lies far below the d ≥ 20 of every production registry surveyed (Section 7), placing all such systems in the regime where PHDAG is strictly cheaper.
5
Methodology
5.1
Network and Tooling
All experiments were conducted on the Base Sepolia testnet (chain id 84532), an Ethereum L2 network operating under the same gas schedule as Ethereum mainnet. Base Sepolia provides a realistic EVM environment at testnet cost. Contracts were compiled with solc 0.8.24 and deployed and invoked via web3.py with local nonce tracking to avoid race conditions with load-balanced RPC endpoints. 5.2
Reference Implementations
We implemented two minimal reference contracts, both available in the reproducibility repository [20]. The IncrementalMerkleTree contract implements the frontier-update pattern (as defined in Section 2.3) with configurable depth at deployment. The ParentHashDAG contract implements the minimal three-SSTORE append operation with no application-specific metadata. Both contracts have been audited for correctness against unit tests and deployed multiple times across the experimental range. 5.3
Experimental Design
Uniform depth sweep. We deployed the IMT contract at each depth d ∈ {1, 2, . . . , 25} and performed 3 appends against each instance. The first insert at each depth traverses cold frontier slots and is discarded from the steady-state analysis; the remaining inserts are averaged to estimate the per-insert cost at that depth. Proportional depth sweep. To obtain better statistical power at production-relevant depths, we additionally deployed the IMT contract at each depth and performed max(d, 2) appends per depth, again discarding the first insert. At depth 25 this yields 24 post-cold-cascade inserts per depth, affording meaningful variance estimates. PHDAG run. A single PHDAG contract was deployed and 200 appends were performed to characterize the primitive’s cost distribution. Every append in this run was a root append: the parent reference was the zero value, so the parentexistence SLOAD of Lemma 2 is short-circuited and each append performs two cold SLOADs rather than three. The run therefore measures the root case of the append; a non-root append (one carrying a live parent reference) performs one additional cold SLOAD, a fixed increment of γR ≈ 2,100 gas that does not depend on registry size or depth and so leaves the constant-bound claim of Theorem 1 intact. PHDAG does not admit a depth parameter, so no sweep is required; its cost is by construction invariant to registry size and to any notion of tree depth (Theorem 1). Random leaf values throughout were generated via secrets.token_bytes(32) to avoid pathological bit patterns. The first append against the freshly deployed contract pays a one-time cold-initialization cost and is excluded from the steady-state statistics below, exactly as the first insert at each IMT depth is excluded from the sweep. 5.4
Measurement
Gas consumption per insert was obtained from the gasUsed field of the post-mining transaction receipt. Receipts were collected sequentially with local nonce tracking between transactions to preclude concurrent execution. All raw data is published alongside this manuscript in a reproducibility repository [20].
6
Results
The PHDAG primitive exhibits mean gas cost ḡPHDAG = 76,276 gas with standard deviation σPHDAG ≈ 6 gas across the steady-state portion of the 200-append root run (the 199 appends remaining after the first-insert cold-initialization outlier is excluded; see Section 5). The measured costs take only a small number of discrete values spaced 12 gas apart, tracking the number of leading-zero bytes in the random arId calldata; this 12-gas quantum is the spacing between adjacent levels, not the standard deviation, and the 199 steady-state appends span a range of just 36 gas in total. The excluded first append costs 93,379 gas, roughly 17,100 above the steady-state cluster, a one-time cold-initialization cost on the freshly deployed contract; including it raises the run mean to 76,361 gas, and it is set aside on the same basis as the IMT cold-cascade first insert. The steady-state total sits below the nominal structural expression of Equation 1 for two reasons, both structural rather than incidental. First, the benchmarked appends are root appends, so the write 13
The Parent-Hash DAG
A P REPRINT
to parents[arId] stores the zero parent reference to an already-zero slot: a zero-store in place of one of the three cold sets, removing roughly one γ from the nominal storage total (Lemma 2). Second, the rounded schedule values γ ≈ 22,100 and γR ≈ 2,100 are upper nominal figures, and the value-transition pricing of EIP-2200/2929/3529 for the specific cold/warm and zero/nonzero cases involved is somewhat lower. The measured 76,276 is therefore the root-case constant (2γR of SLOADs, two cold sets plus one zero-store, and the warm counter write), not the non-root nominal sum; a non-root append adds one cold SLOAD and turns the zero-store back into a cold set, a fixed increment that leaves the structural claim unchanged. What the formal analysis predicts, and what the measurement confirms, is that the per-append cost is a fixed constant, independent of registry size and of any notion of tree depth (Theorem 1). The exact constant is a matter of which append case is measured and of the schedule’s effective per-operation prices, not of the structure, and is recovered directly from the measurement. 6.1
Proportional Depth Sweep
Figure 2 displays the results of the proportional depth sweep. Across the full range d ∈ {1, . . . , 25}, the per-insert cost of IMT grows approximately linearly with d. The PHDAG primitive remains at 76,276 gas across all depths, consistent with the depth-invariance established by Theorem 1 and visualized as a horizontal reference line in the figure. The per-insert cost also exhibits the leaf-index dependence predicted by Lemma 3: inserts at indices 2k (longest write cascades, where many popcount bits are zero) are the most expensive, and those at 2k − 1 (all low bits one) the cheapest.
Figure 2: Per-insert gas cost of PHDAG and IMT primitives as a function of tree depth. PHDAG (blue) is depth-invariant at 76,276 gas. IMT (red) grows approximately linearly with depth, with per-insert variance (error bars) also growing in absolute terms. The crossover between primitives under the sweep’s workload falls at depth 6 (green band), slightly below the lifetime-average d∗ ≈ 7.2 (Section 4.5). Each IMT point aggregates max(d, 2) appends per depth with the first insert excluded to remove cold-cascade contamination. The empirical crossover depth, the value of d at which ḡIMT first exceeds ḡPHDAG , is located at d = 6 in the sweep (ḡIMT ≈ 71,000 at d = 5, rising to ≈ 78,000 at d = 6). As discussed in Section 4.5, this as-sampled crossover sits slightly below the lifetime-average value d∗ ≈ 7.2 because the sweep samples write-heavy low indices; both lie far below production depths. For all depths d ≥ 6 the PHDAG primitive is strictly cheaper per append under the sweep’s workload. 14
The Parent-Hash DAG
6.2
A P REPRINT
Variance Scaling
The error bars in Figure 2 encode the empirical √ per-insert standard deviation at each depth. IMT variance grows monotonically with depth, consistent with the Θ( d) scaling of Theorem 3. The absolute magnitude of the sweep’s √ per-depth standard deviation is, however, smaller than the uniform-index prediction |cL − cR | d/2: at d = 10 the uniform-index formula gives ≈ 8,200 gas, while the sweep’s sample standard deviation is ≈ 3,500 gas. This is the same sampling effect that governs the mean (Section 6.3): the sweep measures only small leaf indices, which span a narrow band of Hamming weights and therefore a narrow band of write-level counts W , under-representing the full popcount range that drives the uniform-index variance. The sweep confirms the sign and functional form of the variance scaling (monotone growth in d) but not its uniform-index magnitude, which would require sampling the full leaf-index space at each depth. PHDAG variance, by contrast, is invariant to depth at σPHDAG ≈ 6 gas across all measurements, consistent with the zero-variance prediction of Theorem 1 modulated only by the discrete 12-gas calldata quantum described above. 6.3
Agreement with the Stochastic Model
We estimate the per-level cost constants of Theorem 3 directly from the proportional depth sweep (Section 5): the 326 measured inserts across depths 1–25, less the 25 first-inserts excluded for the cold-allocation cascade, giving n = 301. For each measured insert we compute the write-level count W = d − pop(i) (Lemma 3) from its depth and leaf index, and fit the cost model g = c0 + cL W + cR (d − W ) by ordinary least squares (OLS). Because W and (d − W ) sum to d, the model is equivalently written in the cleanly identified form g = c0 + cR d + (cL − cR ) W , separating an intercept, a per-depth cost cR , and a per-write premium cL − cR ; we report all three coefficients together with their standard errors. The first insert at each depth, which pays the one-time zero-to-nonzero cold-allocation cascade as the frontier slots are populated for the first time, is handled either by exclusion or by an additive indicator term; the two treatments yield coefficients agreeing to within one gas, confirming that the cascade is separable from the steady-state per-level costs. The excl-first-insert fit (n = 301) gives c0 = 37,823 (SE 23),
cL = 7,952 (SE 1.2),
cR = 2,748 (SE 7.9),
2
with coefficient of determination R = 0.999994 and root-mean-square residual 113 gas on cost values spanning 38,635 to 253,706 gas. The per-write premium is cL − cR = 5,204 (SE 8.2). The near-exact fit, with a structurally simple three-parameter model, confirms both the level-type decomposition of Theorem 3 and the constancy of the per-level costs across the full depth range. The calibrated constants give a uniform-index mean slope of (cL + cR )/2 ≈ 5,350 gas per depth level (Equation 4). The slope measured directly from the sweep is higher, at ≈ 7,700 gas per depth level, and the difference is a sampling effect rather than a discrepancy in the model. The sweep populates each tree with small leaf indices i = 1, 2, 3, . . ., whose low Hamming weight gives an above-average write-level count W = d − pop(i); the measured inserts are therefore write-heavy relative to the uniform mean E[W ] = d/2, and the more expensive write levels (cL > cR ) are over-represented. Reweighting the per-level costs by the sweep’s empirical write fraction reproduces the measured slope; equivalently, evaluating the fitted model at the sweep’s actual W values reproduces every per-depth mean to within the residual scale above. The uniform-index slope 5,350 and the as-sampled slope 7,700 are the same model under two index distributions.
7
Discussion
7.1
Regimes of Applicability
The crossover at d ≈ 6–7 (Section 4.5) divides the design space into two regimes. The crossover is a narrow band rather than a single depth (the as-sampled 6 to the lifetime-average 7.2); the two-regime split below brackets this band, and every production registry surveyed sits far into the deep regime regardless of which edge is taken. Shallow regime (d ≲ 6). IMT is more gas-efficient per append and additionally provides succinct O(log N ) inclusion proofs, a property PHDAG does not provide without additional structure. For applications requiring membership proofs with bounded capacity, IMT is the correct primitive. At the floor of the IMT range, d = 1, an append writes at most one filledSubtrees slot plus the unconditional root and nextIndex slots: two to three SSTOREs total against PHDAG’s three cold SSTOREs plus a warm counter write, which explains the cost gap at the shallowest depths. 15
The Parent-Hash DAG
A P REPRINT
Deep regime (d ≳ 7). PHDAG is strictly cheaper per append, and additionally exhibits negligible per-insert variance. This is the regime occupied by every production append-only on-chain registry we have surveyed: Tornado Cash (d = 20), Semaphore (d = 20–32), and the major zero-knowledge rollup state commitments (d = 32–40). In this regime the choice between primitives is governed by whether the application requires succinct inclusion proofs. 7.2
The Role of Inclusion Proofs
The comparison in this paper addresses append cost only. IMT’s O(log N ) inclusion proof is a valuable property not shared by PHDAG: a Merkle inclusion proof [19] is a sequence of d sibling hashes that can be verified by a contract or off-chain verifier without reference to the remainder of the tree. ZK rollups and privacy protocols exploit this property heavily, and for these applications the depth-dependent append cost is accepted as a necessary consequence. Provenance registries, by contrast, typically require different queries: parent-chain traversal, descendant enumeration, and direct existence checks by unique identifier. The O(|V |) off-chain reconstruction guarantee of Proposition 2 supports all of these queries natively in linear time in the registry size, with no additional on-chain structure required. The architectural match between query pattern and primitive is the determining factor in primitive selection. 7.3
Variance and Operational Predictability
For production operators providing append services on behalf of end users, as is typical in operator-gated registries [17], per-insert cost predictability is an operational requirement distinct from average cost. An operator quoting a fixed fee per append must either over-charge (to cover worst-case cost) or accept margin compression on the expensive tail of the distribution. PHDAG’s near-zero variance eliminates this consideration entirely. IMT’s variance, while small in relative terms (CV decreases with depth), grows in absolute terms and at depth 25 is a non-trivial fraction of the per-insert cost. The practical implication is that IMT-based registries operating at production depth must budget for the upper tail of the per-insert distribution, not the mean. For an operator submitting 105 appends per day at depth 25, a plausible volume for a large ZK rollup or privacy protocol, the cumulative variance of the daily gas budget is non-trivial. PHDAG-based registries do not incur this budgeting uncertainty. 7.4
Trustless Reconstruction as a Robustness Property
Proposition 2 formalizes a property that, in practice, determines the indestructibility of a provenance registry. If every off-chain indexing service associated with a PHDAG-based registry were to disappear simultaneously, a complete reconstruction of the registry could be performed by any party with read access to the blockchain in time linear in the registry size. No trust in any single party is required; no off-chain infrastructure is required; no coordination among users is required. The registry survives as long as the underlying blockchain survives. This robustness derives from the log-canonical architecture of Section 2.2: event logs are attested through the receipts root of every block header, so their integrity is verifiable from chain headers alone, independent of any contract’s current storage state or any off-chain index. The insertion event in PHDAG carries the complete metadata required for reconstruction, which is the architectural property that makes the indestructibility claim rigorous rather than rhetorical. For PHDAG this property is architectural: it follows from the log-canonical design by construction (Proposition 2), independent of any implementation choice. For IMT it is at most incidental. An IMT-based registry can recover the same guarantee only by emitting sufficient payload in its insertion events, that is, by replicating in its auxiliary log the very state its storage-canonical design treats the Merkle root as carrying. The property is therefore native to one primitive and bolted on to the other, and the difference traces directly to where each places its canonical history (Section 2.2). 7.5
Implications for Standardization
The PHDAG primitive’s simplicity and depth-invariance make it a natural candidate for standardization as an Ethereum Improvement Proposal (EIP) defining a uniform interface for append-only provenance registries. A standardized PHDAG interface would enable interoperable provenance infrastructure across the ecosystem without requiring each application to reimplement storage layout, event schema, or reconstruction logic. The constant-cost guarantee of Theorem 1 and the linear-time reconstruction guarantee of Proposition 2 are both implementation-agnostic and therefore suitable for inclusion in such a standard. We leave the precise specification of the proposed EIP to future work. 16
The Parent-Hash DAG
7.6
A P REPRINT
Provenance Traces as a Coordination Medium
The preceding subsections frame the choice between PHDAG and IMT in terms of append cost, variance, and inclusion proofs. A complementary framing is available, and it is the one that most directly explains why PHDAG suffices for provenance applications despite lacking succinct membership proofs. PHDAG is a coordination medium in the sense introduced in Section 2.6: an append-only ledger whose insertion events are read by an ecosystem of autonomous agents (indexers, derivative-work registries, compliance tools, AI provenance verifiers) which then act on those traces. In the pattern catalogue of [18], this is the Event-Signal pattern at its strongest, natural for a log-canonical primitive whose insertion events are the canonical history rather than auxiliary notifications. Each PHDAG append emits a single event carrying the complete metadata required for reconstruction (Proposition 2); the event is the trace, the agents are the consumers of provenance, and the activation predicate is application-specific (a new descendant of a known artifact, a manifest matching a query, a tree whose root has been flagged). This reframes the inclusion-proof question. ZK rollups and privacy protocols require succinct membership proofs because their agents are on-chain contracts that must verify membership within a single transaction’s gas budget. Provenance registries are consumed by a different agent population: off-chain readers whose activation predicates run over the full event stream, not within an in-circuit verification. The O(log N ) inclusion proof that motivates IMT is the wrong primitive for this consumer profile; the right primitive is a complete, authenticated, linear-time reconstructible event log, which is precisely what PHDAG provides by construction. The architectural advantage is not that PHDAG could be augmented with succinct proofs; it is that the consumer population does not need them. A second consequence concerns the persistence of traces. Paredes García [18] observes that biological stigmergic media decay (pheromones evaporate), while ledger state does not; that work treats the asymmetry as a design consideration with both costs (stale traces persist, polluting the predicate space) and benefits (the medium is permanently legible). Provenance registries occupy the extreme end of this spectrum: the indestructibility of the trace is itself the value proposition. A retracted or expired anchor would undermine the core claim of an immutable provenance record. PHDAG’s design, append-only with no decay mechanism and reconstructible from public event logs in O(|V |) time, aligns with this requirement by construction. The properties that would be liabilities in a task-board contract (no expiry, no garbage collection, unbounded state growth) are exactly what a provenance medium requires.
8
Related Work
Incremental Merkle trees. The MerkleTreeWithHistory contract of Tornado Cash [1] established the canonical production IMT pattern. Semaphore [2] adapted the pattern for identity commitment sets. The major zero-knowledge rollups (zkSync [3], Scroll [4], Linea [5]) employ sparse Merkle tree variants at depths 32–40 as their state commitment mechanism. Our analysis applies to the frontier-update pattern (as defined in Section 2.3) common to these systems; sparse Merkle trees with account-keyed access patterns exhibit additional cost variation not modeled here. Parent-hash provenance. The underlying parent-reference append pattern, in which each appended element carries a pointer to a prior element and is registered in unique-keyed storage, is most fully developed as the data-structural core of the AnchorRegistry provenance registry of Moore [17]. That work embeds the pattern within a dual-layer cryptographic commitment scheme addressing operator trust, and asserts an O(1) append complexity at a high level in its implementation section. The present paper isolates the pattern from its application context, names it the parent-hash directed acyclic graph (PHDAG) primitive, formalizes its complexity with explicit constants, and places it in direct comparison with IMT within a unified stochastic cost analysis. Gas cost analysis. Prior work on EVM gas cost has focused primarily on deterministic cost modeling for optimization [9, 10] and on the economic design of gas markets [11, 12]. The stochastic treatment of per-insert cost as a random variable parameterized by usage patterns, to our knowledge, has not been presented in prior work. Ledger-state coordination. Paredes García [18] develops ledger-state stigmergy as a formal framework for indirect coordination of autonomous agents through shared ledger state, introducing a state-transition formalism and an applied pattern catalogue (State-Flag, Event-Signal, Threshold-Trigger, with a Commit-Reveal sequencing overlay). That work is medium-general and uses a task-board as its worked example; the present paper applies its vocabulary in Sections 2.6 and 7.6 to characterize PHDAG as an Event-Signal coordination medium for provenance traces. Certificate Transparency. On-chain CT-style logs [19] employ similar append-only patterns but typically operate on-chain only as a settlement layer, with the bulk of the log maintained off-chain. Our analysis applies directly to any variant that performs per-append on-chain work. 17
The Parent-Hash DAG
9
A P REPRINT
Conclusion
We have presented both a formal and a stochastic cost analysis of the two dominant append-only on-chain registry primitives: the incremental Merkle tree and the parent-hash directed acyclic graph. The formal analysis establishes that PHDAG append is O(1) in both global registry size and any notion of tree depth, with an explicit constant bound derived from the EVM gas schedule. The stochastic analysis √ yields closed-form expressions for the mean √ and variance of IMT per-insert cost, with the variance growing as Θ( d) in absolute terms and decreasing as Θ(1/ d) in relative terms. We validated both analyses empirically on Base Sepolia across tree depths 1–25. The PHDAG primitive was observed to cost 76,276 gas per append with a standard deviation of approximately 6 gas, consistent with the constant bound predicted by the formal analysis. The IMT primitive was observed to grow linearly with depth, with the crossover between primitives at d∗ ≈ 7 for a uniform leaf index and at d = 6 under the depth sweep’s workload. Every production-deployed append-only registry surveyed operates at a depth above this crossover, placing all such systems in the regime where PHDAG is strictly cheaper and where per-append cost is fully predictable. A separate structural property, O(|V |) trustless reconstruction from public event logs alone, ensures that PHDAG-based registries survive the failure of any off-chain infrastructure. Constant-cost append, depth-invariant variance, and trustless reconstruction together make PHDAG the preferred primitive for append-only registries operating at production depth, where succinct membership proofs are not the dominant query, the regime every production registry surveyed occupies, and a strong candidate for standardization as a uniform registry interface for the Ethereum ecosystem. The stochastic framing suggests several directions for future work. The depth sweep measured a write-heavy subsample of the leaf-index space; a sweep over uniformly sampled leaf indices at each depth would directly confirm the uniform-index variance magnitude predicted by Theorem 3, which the present experiments confirm only in functional form. Extension of the analysis to sparse Merkle tree variants used in zero-knowledge rollups would characterize the cost profile of those systems’ state commitment mechanisms. Finally, the standardization of the PHDAG primitive as a uniform interface for append-only provenance infrastructure, through an Ethereum Improvement Proposal, would enable interoperable provenance systems across the ecosystem.
Acknowledgments The authors thank the Base team for operating a reliable L2 testnet on which this work was conducted. The authors used AI writing assistance (Anthropic Claude) in drafting this manuscript. All theoretical contributions, experimental designs, and empirical analyses are the authors’ own. The reference implementations, raw experimental data, and analysis scripts are available at [20].
References [1] Tornado Cash Privacy Solution, tornado-core: MerkleTreeWithHistory.sol, GitHub repository, 2019–2022. Available: https://github.com/tornadocash/tornado-core [2] Semaphore Protocol, semaphore: Semaphore.sol smart contracts, GitHub repository, 2020–2026. Available: https://github.com/semaphore-protocol/semaphore [3] Matter Labs, era-contracts: zkSync Era L1 and L2 smart contracts, GitHub repository, 2022–2026. Available: https://github.com/matter-labs/era-contracts [4] Scroll, scroll-contracts: Scroll zkEVM rollup smart contracts, GitHub repository, 2023–2026. Available: https: //github.com/scroll-tech/scroll-contracts [5] Consensys, linea-monorepo: Linea zkEVM smart contracts, prover, and coordinator, GitHub repository, 2023– 2026. Available: https://github.com/Consensys/linea-monorepo [6] R. C. Merkle, A Digital Signature Based on a Conventional Encryption Function, Advances in Cryptology — CRYPTO ’87, LNCS 293, pp. 369–378, Springer, 1988. [7] 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 [8] J. Benet, IPFS — Content Addressed, Versioned, P2P File System, arXiv:1407.3561, 2014. [9] 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 DAG
A P REPRINT
[10] 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 [11] T. Roughgarden, Transaction Fee Mechanism Design for the Ethereum Blockchain: An Economic Analysis of EIP-1559, arXiv:2012.00854, 2020. [12] V. Buterin, Blockchain Resource Pricing, Ethereum Research position paper, August 2018. Available: https: //ethresear.ch/t/draft-position-paper-on-resource-pricing/2838 [13] 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 [14] 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 [15] 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 [16] G. Wood, Ethereum: A Secure Decentralised Generalised Transaction Ledger, Ethereum Project Yellow Paper, Shanghai version, 2025. Available: https://ethereum.github.io/yellowpaper/paper.pdf [17] I. C. Moore, Trustless Provenance Trees: A Game-Theoretic Framework for Operator-Gated Blockchain Registries, arXiv:2604.03434, 2026. [18] F. Paredes García, Ledger-State Stigmergy: A Formal Framework for Indirect Coordination Grounded in Distributed Ledger State, arXiv:2604.03997, 2026. [19] B. Laurie, A. Langley, and E. Kasper, Certificate Transparency, RFC 6962, IETF, June 2013. [Online]. Available: https://datatracker.ietf.org/doc/html/rfc6962 [20] 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