PaperlayerView exact revision on arXiv

Source-linked AI summary

Authenticated Data Structures for Dynamic Workloads

Ziheng Shangguan, Aviv Yaish, Dahlia Malkhi

arXiv:2608.25206v1cs.CR

TL;DR

Authenticated data structures traditionally incur access costs that ignore skew, while adapting layouts to changing access frequencies introduces restructuring overhead. HMT combines frequency-aware Huffman-Merkle layouts with batched, adaptive tiering, and its best policy reduces hashing and access-weighted proof sizes against MPT and UBT.

  • Problem

    Dynamic authenticated data structures lack a practical approach that adapts to evolving access frequencies while explicitly accounting for restructuring cost.

  • Method

    HMT decouples authentication from layout optimization using hot and cold authenticated tiers, periodic HuffMHT rebuilds, overflow handling, and batched migration decisions.

  • Results

    Sliding-Window uses about 2.4× less average hash input than MPT and 0.34× less than UBT, with access-weighted proofs smaller by 0.18× and 0.55×, respectively.

  • Takeaways & Limitations

    Giving frequently accessed elements shorter authenticated paths while batching layout changes improves hashing and access-weighted proof metrics on real-world data.

  • Takeaways & Limitations

    Directly adapting Huffman per operation is constrained by the need to recompute hashes along affected ancestor paths before each committed root.

Abstract

from arXiv · show

We introduce the Huffman-Merkle Tree (HMT), an authenticated data structure (ADS) for dynamic workloads where items may differ in access frequencies, and access frequencies can change over time. An ADS allows proving item membership against a short commitment to a large mutable state, with applications including verifiable storage, Internet transparency services, and blockchains. Optimizing ADS performance under continuously changing access frequencies has not been fully addressed before, neither in theory nor in practice. HMT addresses dynamically changing access skew through two complementary mechanisms. The first is a Huffman-coding-based Merkle-tree layout, with a novel extension to support evolving access frequencies. The second is an elastic tiering regime that partitions items across separate trees, such as hot and cold tiers, with adaptive migration between them. The key insight in this approach is to place frequently accessed items closer to the root, while assigning less frequently accessed items to progressively larger and deeper trees. This reduces the overall frequency-weighted access cost. Our scheme is designed to scale to gigabytes of data spanning millions of items. To handle dynamism efficiently, layout updates are applied in batches, access frequencies are tracked using a count-min sketch, and the system employs a tier-promotion cache while exploring multiple tier-migration policies. We implement HMT and compare it on real-world data with Ethereum's Merkle Patricia Trie (MPT) ADS and its proposed replacement, the Unified Binary Tree (UBT). Our evaluation considers two metrics: the amount of hashing per update and access-weighted membership-proof size. The latter captures both item access cost and frequency. We find that the best HMT policy uses about 2.4x and 0.34x less average hash operations than MPT and UBT respectively, and has 0.18x and 0.55x shorter proofs.

1 Introduction

HMT addresses the challenge of authenticated data structures under skewed, changing access frequencies by combining frequency-aware layouts with dynamic tiering and batched adaptation. Evaluated on real-world data, HMT improves hashing overhead and access-weighted proof size over prominent alternatives.

  • Motivation: HMT targets dynamic workloads where access frequencies vary and change over time, a setting not previously addressed with explicit restructuring-cost accounting.Prior approaches rebuilt the entire structure when distributions changed, incurring hash-compression overhead.
  • HMT design: HMT separates frequently accessed items into a hot HuffMHT and stores cold elements in a balanced Merkle Tree.The tiered design combines short paths for hot items with flatter structure for efficient insertions of rarely accessed elements.
  • Dynamic adaptation: HMT adapts to changing frequencies through batched layout updates, Count-Min Sketch estimation, promotion caching, and multiple migration policies.Policies include lifetime-rate, sliding-window, and feedback-controlled admission mechanisms.
  • Evaluation: HMT evaluates commit-time hash input and access-weighted membership-proof length using real-world Ethereum data against MPT and UBT.The proof metric weights each item’s membership-proof length by its access frequency.
  • Results: Sliding-Window HMT uses about 2.4× fewer average hash operations than MPT and 0.34× fewer than UBT, while producing proofs 0.18× and 0.55× as large, respectively.Ratio-Based remains stable, while Dynamic-Control remains competitive in proof size at the cost of additional hash-input work in this run.

2 Preliminaries

Authenticated data structures commit large mutable datasets with short digests and support verifiable membership proofs. This section introduces Merkle-based structures, frequency-aware Huffman layouts, and the static-to-dynamic challenge that motivates HMT.

  • Authenticated Data Structures: ADSs provide operations for reading, updating, committing, proving, and verifying key-value membership without exposing the entire dataset.The interface includes Put, Delete, Commit, Get, GetProof, and Verify.
  • Merkle Trees: Merkle trees store values at leaves, hash child commitments internally, and use the root hash as a commitment to the dataset.An inclusion proof supplies sibling hashes and orientations along the path to the root.
  • Ethereum State Structures: Balanced binary Merkle-tree proofs contain logN hash values, so their cost is independent of item access frequency.MPTs likewise incur costs that do not depend on access frequencies, while MPT witnesses contain encoded trie nodes.
  • Frequency-Based Structures: Huffman coding assigns shorter binary-tree paths to higher-probability items, minimizing expected code length for a known distribution.A HuffMHT applies this frequency-aware layout to authentication paths, making expected proof depth equal to expected Huffman code length.
  • Frequency-Based Structures: HMT’s novelty is dynamically maintaining a Huffman-shaped authenticated layout under insertions, updates, and changing access frequencies.Its design combines frequency-aware organization with authenticated-map dynamism rather than merely using a static Huffman tree.
  • Frequency-Based Structures: For Zipf distributions with a > 1, HuffMHT weighted average depth can remain bounded as N grows, whereas balanced binary MT depth grows as Θ(log N).The same skew can produce a long-tail cost for cold elements, motivating separate handling for cold and new elements.

3 Handling Dynamic Access Frequencies

HMT adapts Huffman-based authenticated layouts to changing access frequencies through batched rebuilding and incremental pair-swaps. It avoids the per-access restructuring cost of traditional adaptive Huffman while updating only affected hashes.

  • HMT extends static Huffman layouts to dynamic workloads where new items arrive and access frequencies change over time.
  • Complete rebuilding recomputes the entire tree for each update, making its cost linear in the number of elements rather than the changed subset.
  • Incremental updates realize frequency-order changes using pair-swaps and recompute hashes along the affected ancestor paths.
  • O(|S|n) hash computations is the worst-case cost of the incremental strategy for an accessed set S in a HuffMHT with n leaves.
  • Traditional adaptive Huffman is unsuitable as a direct ADS because each structural move changes ancestor hashes that must be recomputed before commitment.
  • Periodic rebuilding keeps absorbed elements in a base HuffMHT and newly inserted or unabsorbed elements in an overflow Merkle tree until the next rebuild.

4 Tiered Tree Architecture

HMT partitions items across adaptive hot and cold tiers, combining frequency-aware proofs for popular items with balanced-tree maintenance for cold and new items. A hashed tuple of tier roots preserves one global commitment and membership soundness.

  • Tier Migration: HMT migrates items deterministically at period boundaries, promoting lower-tier candidates that exceed a threshold and demoting items according to the active policy.
  • Tiered Tree Architecture: HMT places frequently accessed items in a HuffMHT hot tier and infrequent or newly inserted items in a balanced Merkle Tree cold tier.
  • Tiered Tree Architecture: The cold tier avoids HuffMHT tail depths that can reach N −1, compared with maximum depth ⌈log2 N⌉ for a balanced binary Merkle Tree.
  • Tier Count: Two tiers balance shorter local paths against the additional per-tier roots required in membership proofs; adding tiers did not further reduce proof size in the sensitivity analysis.
  • Global Commitment: The global root hashes the concatenation of all tier roots, allowing one commitment to represent the entire tiered state.
  • Membership-proof Soundness: HMT membership soundness follows when constituent tier ADSs are membership sound and the hash function is collision resistant.
  • Promotion Cache: The promotion cache tracks only bounded candidate sets, so uncached cold keys may be missed until observed again; CMS overestimation affects layout quality but not proof soundness.

5 Dynamic Customization

HMT adapts tier placement to changing access frequencies through periodic migration policies, frequency estimates, and feedback-controlled thresholds and capacities. Its policies trade responsiveness to workload shifts against stability and migration overhead.

  • Migration framework: HMT applies tier migration at batch boundaries using candidate scoring, evaluation cadence, and fixed or feedback-controlled admission parameters.Tiers are numbered from coldest to hottest, and each adjacent boundary defines a promotion edge.
  • Migration policies: Absolute-Threshold promotes candidates when their cumulative Count-Min Sketch estimate exceeds a configured edge threshold.When the hotter tier is full, HMT compares the candidate with the least-frequent admitted element.
  • Policy trade-offs: Lifetime-based policies can retain stale hot keys and delay newly hot keys, making them undesirable when workloads change rapidly.Sliding-Window addresses this issue by using expiring recent-access statistics.
  • Migration policies: Ratio-Based ranks candidates by lifetime access rate, equivalently testing whether cumulative frequency exceeds elapsed periods multiplied by the threshold.The normalization makes thresholds grow with run length but retains lifetime-count effects.
  • Migration policies: Sliding-Window uses recent period histograms and removes expired accesses, so stale hot items lose influence after workload changes.Demotion is delayed through a per-edge wheel rather than occurring immediately when the window-local rate falls below threshold.
  • Adaptive control: Dynamic-Control adjusts promotion thresholds and hot-tier capacities with feedback loops operating at different cadences.Thresholds react to short-term admission pressure, while capacities change only after pressure persists across multiple control windows.
  • Adaptive control: Capacity control expands congested hot tiers or shrinks under-utilized tiers only after threshold adjustment is exhausted, while deterministic boundary updates support replica agreement.Controller thresholds are bounded using the access rate of the destination tier’s least-frequent admitted element.

6 Evaluation

The evaluation combines controlled restructuring benchmarks with a deterministic replay of one million Ethereum blocks, comparing HMT variants against MPT and UBT. Sliding-Window performs best across the reported hashed-input and access-weighted proof-size figures.

  • Evaluation setup: The evaluation uses microbenchmarks for layout maintenance and deterministic Ethereum state-access replay at account granularity.All compared authenticated data structures process the same operation trace in the same order.
  • 6.1 Continuous Updates: 47.1 ms versus 100.3 ms: batched pair swaps reduce average restructuring time by 2.13× compared with full rebuilds over batches 2–10.The stable-key benchmark applies 5,000,000 Zipf-distributed operations to 100,000 initially inserted keys.
  • Compared structures: The comparison includes MPT, UBT, Ratio-Based HMT, Sliding-Window HMT, and Dynamic-Control HMT configurations.HMT uses HuffMHT and Merkle Tree tiers with promotion policies that differ in their access statistics and controls.
  • Metrics: The metrics are hashed input bytes during commit and access-frequency-weighted average membership-proof length.Hashed input bytes measure data supplied to hash functions across authenticated nodes.
  • 6.2.2 Evaluation Results: Sliding-Window is lowest-cost for most blocks in hashed input bytes, while MPT remains the largest byte-level workload and UBT the second most expensive.Ratio-Based and Dynamic-Control remain close to one another in the hashed-input comparison.
  • 6.2.2 Evaluation Results: HMT proofs are substantially shorter than MPT and roughly half the size of UBT proofs in the access-weighted comparison.Sliding-Window is lowest or tied for lowest over most of the replay.
  • Policy trade-offs: Sliding-Window is best in both figures; Dynamic-Control remains competitive in proof size but incurs more hashed input than static HMT policies in this run.Ratio-Based is simpler and more stable but can retain older hot accounts after workload shifts.

7 Additional Related Literature

Related work spans authenticated dictionaries, blockchain state commitments, frequency-aware trees, and dynamic-data-structure evaluation. HMT differs by adapting authenticated layout to observed hot keys while retaining hash-based commitments.

  • Blockchain state commitments: Blockchain ADS designs target compact proofs and performant reads and updates, motivating alternatives to Ethereum’s large-proof MPT.Verkle and vector-commitment proposals change the commitment primitive rather than only the tree layout.
  • HMT’s position: HMT adapts data-structure layout to observed hot keys while preserving a hash-based state commitment, unlike commitment-primitive or storage-oriented alternatives.Its distinction is layout optimization rather than primarily changing the backing store, I/O path, or commitment primitive.
  • Frequency-aware trees: Huffman-shaped authenticated trees place frequently accessed elements nearer the root, but standard Huffman optimality assumes a static independent access distribution.Dynamic blockchain workloads can change over time and exhibit more intricate access patterns.
  • Authenticated dictionaries: Authenticated dictionaries and hash tables provide the basic mutable-map commitment and query-proof abstraction, with known lookup/update trade-offs.Prior frequency-aware authenticated dictionaries and skewness-aware oblivious maps support the broader premise of access-aware layouts.
  • Dynamic evaluation: Online data-structure evaluation considers requests arriving without a reliable forecast of future workload and may use competitive ratios against an offline optimum.This frames dynamic adaptation as a workload-uncertainty problem rather than a static-layout optimization alone.

8 Conclusion

HMT decouples authentication from layout optimization by tiering cold and hot elements and batching layout changes. Real-world experiments report lower hash input and shorter access-weighted proofs, with Sliding-Window performing best.

  • Conclusion: HMT keeps cold elements in a conventional authenticated tier, moves frequently accessed elements into a periodically rebuilt HuffMHT, and uses an overflow tree for newly promoted items.The design gives hot elements shorter authenticated paths while avoiding reshaping after every access.
  • Conclusion: 2.4× less average hash input than MPT and 0.34× less than UBT: Sliding-Window is the best-performing evaluated policy.Its access-weighted proofs are also 0.18× those of MPT and 0.55× those of UBT.
  • Conclusion: The reported microbenchmarks support batched pair swaps for stable key sets and periodic rebuilds under dynamic insertions.These strategies reduce the need to update tree layout after every operation.
  • Proof procedures: Merkle inclusion proofs authenticate a leaf by providing sibling hashes along its path to the root.Verification reconstructs the commitment from the claimed key, value, and proof path.
  • Proof procedures: HMT verification identifies the item’s tier, verifies its tier proof against that tier root, and checks the combined tier-root commitment.The authenticated state is organized across tier-specific ADS roots.
  • Migration mechanisms: The bucketed LFU Promotion Cache tracks CMS-estimated frequency ranges and evicts the least-frequent candidate when its capacity is exceeded.Tier movement removes a key from its current metadata bucket before inserting it into the destination tier.
  • Migration mechanisms: Sliding-Window migration updates an aggregate recent-access histogram, rechecks delayed demotions, schedules newly cold keys, and promotes newly active qualifying keys.This policy uses window-local activity rather than cumulative lifetime counts.

B Proofs

The proof analysis establishes frequency-weighted depth advantages for Huffman layouts and bounds authenticated maintenance costs under adaptive updates. Real-trace results show periodic rebuilding preserves much of the proof-size benefit while avoiding per-operation reshaping overhead.

  • Analytical proof bounds: Under a truncated Zipf distribution with a > 1, Huffman-tree depth has a bound independent of the number of elements N.The proposition fixes constants a > 1 and b ≥ 0 and defines the truncated Zipf distribution used in the analysis.
  • Analytical proof bounds: A balanced q-ary Merkle tree with N leaves has proof depth Θ(log N), with constants depending on fixed q but not N.This provides the balanced-tree baseline for comparing frequency-weighted Huffman depth.
  • Analytical proof bounds: If an MPT baseline has access-weighted proof depth Ω(log N), the Huffman numerator bound yields a corresponding asymptotic ratio advantage.The comparison assumes the stated MPT depth condition over the considered key-space family.
  • Dynamic maintenance: Adaptive Huffman maintenance requires O(|D|) hash computations, where affected paths satisfy |D| ≤ O(min{(s + 1)h, n}).Here D contains affected nodes and their ancestor paths, s is the number of local structural moves, h is tree height, and n is the number of leaves.
  • Dynamic maintenance: Adaptive Huffman updates have worst-case authenticated maintenance cost O(n), tight up to constants when a leaf-to-root path spans height h = n − 1.The worst case follows because an update or insertion can dirty the full path to the root.
  • Real-trace evaluation: 1.14M operations per second for balanced MT and 667K for periodic-rebuild HuffMHT contrast with 2.3K for Adaptive Huffman in the 10,000-block replay.Adaptive Huffman produced the smallest weighted proofs, but per-operation reshaping dominated replay cost; periodic rebuilding avoided that overhead.

D Tier-Count Sensitivity

Increasing the number of HMT tiers does not improve mean access-weighted proof size. Cross-tier authentication overhead outweighs the local proof savings from further splitting hot elements.

  • Tier-count sensitivity: Increasing tier number does not improve mean proof size in the one-million-block Ethereum replay.The evaluation extends corresponding two-tier policies while keeping cache capacities and the 500-block rebuild cadence unchanged.
  • Tier-count sensitivity: Additional tiers shorten tier-local proofs for the hottest elements, but each proof must also include every tier root needed to reconstruct the global root.The added cross-tier proof component outweighs marginal local-proof savings from further splitting the hot set.

E Evaluation of Additional Policies

The additional-policy evaluation uses two-tier HMT configurations with periodic rebuilding, fixed cache capacities, and 500-block batches. It compares throughput across tier combinations under the Absolute-Threshold configuration.

  • Evaluation setup: Two additional fixed policies, Absolute-Threshold and Periodic-Evaluation, are evaluated on one-million-block Ethereum data using the two-tier HMT design.Both use a balanced MT cold tier, a periodic-rebuild HuffMHT hot tier, fixed cache capacities, and 500-block batches.
  • Throughput comparison: Figure 15 reports throughput for tier combinations under Absolute-Threshold, with labels specifying the hot-tier and cold-tier structures.For example, HuffMHT+MT denotes a HuffMHT hot tier and an MT cold tier.

F Underlying ADSs Choice

The tier-combination results expose a throughput–proof-size trade-off. HuffMHT+MT retains throughput comparable to MT+MT while reducing weighted proofs relative to an all-balanced design.

  • Throughput: 368K and 362K operations per second are reported for MT+MT and HuffMHT+MT, respectively, showing comparable throughput.The combinations are written as hot tier+cold tier.
  • Throughput: 29.3K operations per second for HuffMHT+HuffMHT is about 12.3× lower than HuffMHT+MT.Making both tiers Huffman-shaped substantially reduces throughput in this comparison.
  • Proof size: MT+MT has the largest weighted proofs, while HuffMHT+HuffMHT has the smallest and HuffMHT+MT remains close to it.The proof-size comparison is access-weighted and is shown for the one-million-block Ethereum evaluation.
  • Trade-off: The tier-combination evaluation therefore identifies HuffMHT+MT as a compromise between throughput and proof size.This conclusion follows from its comparable throughput with MT+MT and lower weighted proofs than MT+MT.

G Weighted Average Proof Size By Read/Write

The proof-size metric weights keys by total read and write accesses, with separate read-only and write-only refinements evaluated against the aggregate metric. Both refinements preserve the same performance ordering, with MPT producing the largest proofs.

  • The aggregate proof-size metric weights each key by its total number of read and write accesses.
  • Separate refinements count either reads or writes, enabling access-type-specific proof-size evaluation.
  • Both read-only and write-only metrics show the same performance ordering as the aggregate metric.
  • MPT has the largest proofs across the evaluated metrics.Its proofs rise from roughly 2 kilobytes at replay start to above 3 kilobytes later in the replay.
Loading 2608.25206v1…