An authenticated data structure built for changing access patterns reported smaller access-weighted membership proofs and lower hash-input work than two baselines in a replay of Ethereum StateDB operations. The paper reports a 2.4-fold reduction in average hash input against MPT, and an HMT figure equal to 0.34 times UBT's level. Its access-weighted proofs were 0.18 times the MPT size and 0.55 times the UBT size. A membership proof is the extra information checked with a lookup to show that a requested element is included. These are approximate author-reported ratios, and no confidence intervals are reported. The document is an arXiv version 1 preprint dated 25 August 2026.
A layout that tracks frequency
The study asks whether authenticated data structures can remain efficient when elements are updated and access frequencies change. Its design, called HMT, combines a cold authenticated tier, a periodically rebuilt hot HuffMHT and an overflow tree for newly hot elements. In ordinary terms, frequently used elements can sit in the hot tier, the remaining elements in the cold tier and newly hot elements in the overflow tree until a migration takes place.
To track changes in demand, HMT estimates access frequency with a Count-Min Sketch and uses a bucketed least-frequently-used cache for promotion and demotion candidates. Promotion and demotion mean moving elements into or out of the hot tier. The migration policies make those changes in batches.
What the Ethereum comparison measured
The main empirical comparison replayed a go-ethereum StateDB trace in recorded order and mapped each Ethereum account to one authenticated element. The evaluation centered on two measures: hashing work per authenticated data structure update and access-weighted membership-proof size. The first is the total input presented to the hash function during an update; the second weights proof size by the access pattern. They are measures of internal update work and proof burden, not direct end-to-end readings of deployment performance.
In the policy comparison, Sliding-Window was the best policy in the plotted metrics. Ratio-Based was stable but could retain stale hot items. Dynamic-Control remained competitive in proof size at higher hashed-input cost and was treated as exploratory. The comparison is descriptive, with no inferential uncertainty estimates reported.
Controlled tests show the maintenance gap
In a stable-key benchmark, the system inserted 100,000 keys and then applied 5,000,000 Zipf-distributed get and update operations with a = 4 and b = 1. Across batches 2 through 10, batched pair swaps averaged 47.1 milliseconds, compared with 100.3 milliseconds for full rebuilds. The paper reports that comparison as a 2.13-fold reduction.
A separate continuous-insertion benchmark started empty, inserted 100,000 keys over 5,000,000 operations and compared periodic-rebuild HuffMHT with Adaptive Huffman. In the final batch, periodic-rebuild HuffMHT took about 180 milliseconds, while Adaptive Huffman took about 136 seconds.
Proof size was not the only score
Another test was a 10,000-block stress replay. Balanced MT reached 1.14 million operations per second, periodic-rebuild HuffMHT reached 667,000 and Adaptive Huffman reached 2,300. Adaptive Huffman produced the smallest weighted proofs among the three. These are descriptive stress-test values, with no uncertainty estimate reported.
Adding more tiers did not improve mean proof size in the sensitivity analysis. The paper attributes that result to extra cross-tier roots outweighing local savings from shorter proofs. In the tier-combination comparison, MT plus MT and HuffMHT plus MT recorded 368,000 and 362,000 operations per second, respectively. HuffMHT plus HuffMHT reached 29,300 operations per second, about 12.3 times lower than HuffMHT plus MT, and produced the smallest weighted proofs.
The boundaries of the result
The evidence is limited to the stated controlled workloads, deterministic Ethereum replay, tested configurations and reported metrics. The main replay did not reconstruct the full Ethereum pre-state, and each account was treated as one authenticated element. The empirical evaluation remains tied to the particular trace, workload patterns, configurations and testbed described in the report.
Hash-input bytes and access-weighted proof size are proxy metrics rather than direct readings of validation latency, bandwidth, storage or energy. The descriptive comparisons do not establish universal HMT superiority outside the tested workloads, baselines, parameters and hardware, an end-to-end Ethereum deployment, or system-level benefits from smaller weighted proofs.
Paper data and sources
Original title: Authenticated Data Structures for Dynamic Workloads
Authors: Ziheng Shangguan, Aviv Yaish, Dahlia Malkhi
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-25
DOI: Not available
Original paper · Full text