Reproduce “Parent-Hash DAG: A Cost Analysis of Constant-Time Append for On-Chain Registries” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Ian C. Moore, Fernando Paredes Garcia
This research analyzes the gas cost of on-chain append operations for Parent-Hash Directed Acyclic Graphs (PHDAG) and Incremental Merkle Trees (IMT) in blockchain registries. It formally demonstrates PHDAG's constant-time O(1) append complexity (averaging 76,276 gas) and O(|V|) off-chain reconstruction, while showing IMT's append cost scales linearly O(d) with depth (from 38,000 to over 250,000 gas for depths 1 to 25), identifying an empirical cost crossover at depth d=6.
Key insights
- PHDAG provides a constant-time O(1) append operation with minimal variance, making it highly predictable and cost-effective for deep registries where on-chain succinct membership proofs are not the dominant query.
- IMT append costs increase linearly O(d) with tree depth and exhibit increasing variance, making it more expensive for appends in deep trees but essential for applications requiring O(log N) on-chain membership proofs.
- An empirical crossover depth of d=6 was identified, indicating that PHDAG becomes more gas-efficient than IMT for appends at relatively shallow depths, a regime that encompasses many existing production-deployed systems (d 20).
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.