CS Paper Radar

Authenticated Data Structures for Dynamic Workloads

Ziheng Shangguan, Aviv Yaish, Dahlia Malkhi

cs.CR ·submitted 2026-08-25 22:46 UTC · v1
publishedhot direction

Abstract

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.

Comment
40 pages, 18 figures, 2 tables. Appendix A-G included

Closest papers

Nearest neighbours by meaning across the whole index.

Merkle-Tree-Based Verifiable Public Data Auditing for Cloud Object Storage Using Smart Contracts

cs.CR cs.DC ·2026-10-26 ·Siri Reddy Tadi, K. Gangadhara Rao, M. Venu Gopalachari, C. Chetann Reddy, Jaswanth Bhimireddy
similarity 0.64
Abstract · 15 pages, 12 figures, 11 tables

Owners of data in cloud object storage cannot directly check whether the provider still keeps every object unchanged. Existing research mostly checks blocks inside files or relies on third-party auditors, and less attention has been given to checking each object against a public blockchain reference while measuring the cost. A full-data audit downloads every object and compares it with a saved hash list, which is slow and only as reliable as that list. We propose a public auditing system in which the SHA-256 hash of each object and its name forms a leaf of a Merkle tree, so the whole dataset is represented by one Merkle root. This root is stored in an Ethereum smart contract as a trusted public record, while the objects stay with the provider. An auditor downloads an object, rebuilds the root using a short Merkle proof and compares it with the stored root, marking the object as intact, modified or missing. In five experiments on an S3-compatible store and a local Hardhat blockchain (normal audit, single- and multiple-object tampering, deletion and scalability), the system detected 15 of 15 single modifications, 2,205 of 2,205 modified objects and 830 of 830 deleted objects with no false alarms. The proof needed only 14 hashes for 10,000 objects, so checking one object took about 10 ms and a 100-object sample about 150 ms regardless of dataset size, while a full audit of 10,000 objects (14.3 s) took about as long as downloading them (13.5 s). Storing the root cost 91,863 gas, 252 times less than storing 1,000 hashes on-chain. The system thus shows exactly which objects were modified or are missing, with its main savings coming from checking selected objects.

0.24

Hashrope: A Persistent Data Structure for Mechanisms of LLM Context Management

cs.DS cs.CL ·2026-10-12 ·Muntaser Syed, Ameerah Alsulami, Marius Silaghi
published similarity 0.62
Abstract · Accepted at IEEE ICTAI 2026 (full paper)

Serving stacks for large language models manage context through four recurring mechanisms: incremental edits to a growing context, branching and snapshotting for tree search, identification of reusable prefixes for KV-cache reuse, and encoding of repeated segments. Each mechanism is served today by a different specialist structure. We show that all four reduce to a single persistent weight-balanced rope whose every node carries a polynomial hash of its subtree over a Mersenne prime, so that the structure supports logarithmic edits and logarithmic verified content-identity queries at the same time. We validate each mechanism with pre-registered, replicated experiments, then compare against a deployed specialist per mechanism: the Ropey editing library, a faithful PagedAttention copy-on-write block table, and the vendored SGLang radix matcher. On workloads that interleave edits with identity queries, Hashrope is net-superior to Ropey by a factor that grows without bound (369.7x at one million characters). Against the radix matcher on a live vLLM stack serving Qwen2.5-7B-Instruct-1M on four A100 GPUs, Hashrope identifies a one-million-token shared prefix exactly and 1.20x faster, at a context length the dense engine cannot even prefill.

0.35

Securing Filesystems for Confidential Computing

cs.CR ·2026-08-20 ·Dimitra Giantsidi, Antoine Delignat-Lavaud, Cédric Fournet, Jinnan Guo, Heidi Howard +3 more
similarity 0.62
Abstract

Confidential computing protects applications inside Trusted Execution Environments (TEEs), but it leaves storage vulnerable. Even with disk encryption, a malicious cloud provider can roll back, replay, fork, or tamper with disk state, breaking the integrity and freshness guarantees required by stateful applications. Existing solutions either assume trusted storage, incur high overheads, or push integrity logic into applications. We present ShieldFS, a POSIX-compliant filesystem that provides end-to-end integrity and freshness for persistent storage in the confidential-computing threat model without requiring application changes. ShieldFS represents permissible filesystem states using succinct cryptographic commitments, maintained inside TEEs and replicated in a lightweight trusted registry. On-disk data structures, including a write-ahead log and a storage pool, are authenticated using hash chains and an embedded Merkle tree. ShieldFS utilizes transactions and copy-on-write to update persistent filesystem state and commitments atomically. The commitments are verified during reads, ensuring that rollback, replay, and equivocation attacks are detected even when the entire I/O stack is untrusted. We implement the design by extending ZFS, yielding ShieldZFS. Evaluation with standard filesystem benchmarks and real-world workloads shows that ShieldZFS provides strong integrity and freshness guarantees with performance comparable to state-of-the-art filesystems.

0.16

A BUD You Can Count On: Efficient, Verifiable Membership Proofs

cs.CR cs.DBcs.DC ·2026-09-10 ·Alejandro Ranchal-Pedrosa, Cody Littley, Ben Marsh
theorycode/data similarity 0.61
Abstract

A block typically changes only a small fraction of blockchain state, yet producing a state root makes validators update an authenticated tree spanning it all. We show how to support verifiable reads from the writes alone. We introduce Block Update Digests (BUDs), that commit to a block's writes and link each key touched in that block to its previous modification. An optional prior-value record lets one successor BUD authenticate the value between modifications, replacing the baseline's two BUD openings. SuperBUDs summarize those writes over longer intervals, letting a reader verify that a value remained unchanged without checking every intervening block. Thanks to BUDs and SuperBUDs, validators can just keep ordinary flat state while still serving proofs of current and historical values, including deletion. We prove soundness and completeness for reads at or after a key's first logged modification when the required proof data is available. In experiments with the baseline format, a 50x increase in state size raises the measured base-BUD cost by just 1.24x. In paired QMDB experiments, lowering its garbage-collection activation threshold raises process CPU time by 1.3-2.7x and device bytes written by 1.6-2.4x relative to its dormant configuration. BUD authentication requires no corresponding relocation of live entries. In the evaluated baseline, two-digest read-layer payloads stay below 800 bytes, and warm hash-path verification takes at most 146 μs at p99. Authenticated reads need not make validators maintain an authenticated tree over the entire state.

0.20

Chronos: Efficient Bolt-on Branching Across Data Stores for Stateful Agentic Applications

cs.DB ·2026-09-14 ·Xinjing Zhou, Jason Mohoney, Samuel Madden, Michael Stonebraker, Lei Cao
similarity 0.61
Abstract

Data-centric applications increasingly use speculative execution to explore multiple candidate paths where each path modifies state distributed across heterogeneous data stores. This trend is intensified by the rise of tool-calling agents. Hence, applications need data systems that can create branches quickly, isolate state-modifying paths, and merge changes consistently across stores without imposing substantial query overhead. Existing systems provide only partial support, forcing applications to coordinate branches and merges manually, which increases overhead and risks inconsistent cross-store state. To solve this problem, we introduce Chronos, a bolt-on system that provides branching capability across heterogeneous data stores. We make two contributions. First, Chronos introduces a compact interval-based versioning technique that enables efficient branching and data sharing through simple query rewrite. Second, Chronos introduces a bolt-on architecture that separates branch management from data path within each store. Combined with interval-based versioning, this separation provides atomic cross-store visibility for merges and enables Chronos to support diverse data stores without modifying their engines. We implement Chronos for PostgreSQL, SQLite, DuckDB, Qdrant, and a DBMS-backed filesystem. We evaluate it using cross-store agent workflows, MCTS-style exploration, and per-store benchmarks. Chronos runs MCTS-style exploration up to 16.7x faster than existing approaches while maintaining practical query performance across the underlying stores. Under concurrent cross-store workflows, Chronos prevents partially visible merges while substantially outperforming serialized execution.

0.06

GUARDTs: Decentralized Access Control for Replicated Data Types

cs.PL cs.DC ·2026-11-05 ·Christian Kuessner, Ragnar Mogk, Julian Haas, Annette Bieniusa, Mira Mezini
similarity 0.60
Abstract · 24 pages, 10 figures

Replicated data types providing strong eventual consistency offer a principled foundation for developing decentralized software. Yet existing approaches to programming such data types leave access control unresolved: they either provide none at all, delegate it to a trusted coordinator, reintroducing the centralization they were designed to avoid, or tie it to specific data-type constructions, while typically assuming non-Byzantine replicas and static policies. We present GUARDTs: Guarded Unforgeable Algebraic Replicated Data Types, which embed fine-grained permissions directly into the application data model, operate without a central authority, support dynamic policy evolution, and tolerate Byzantine replicas. We formally prove that GUARDTs guarantee confidentiality, integrity, and availability and show empirically that their access control adds negligible overhead on top of the cost of Byzantine-resilient replication itself.

0.29

Mitigating Front-Running Attacks through Fair and Resilient Transaction Dissemination

cs.DC ·2026-09-21 ·Wassim Yahyaoui, Joachim Bruneau-Queyreix, Jérémie Decouchant, Marcus Völp
publishedhighly cited similarity 0.60
Abstract

In modern blockchains, efficient, fair, and faulttolerant information dissemination is critical for performance and security. Several stages of the transaction lifecycle are affected, from the creation and dissemination of transactions to the dissemination of blocks in the consensus layer. Mempool protocols, such as L{Ø}, already address some of modern blockchains' security threats. However, others remain unless fairness is embedded most fundamentally in the dissemination layer used by these protocols to share transactions and blocks and to reconcile mempools. This paper introduces HERMES, a novel dissemination protocol for mempools that leverages robust minimal structures to optimize data propagation, balance load, and ensure fairness despite faults and Byzantine actors. Specifically, we address front-running attacks by randomizing the choice of an overlay structure while forcing nodes to prove adherence to the mempools' dissemination policies and the random choice made. Experimental results show significant performance improvements compared to traditional broadcast protocols for both permissioned and permissionless blockchains.

0.57

VTRQ: Enabling Verifiable Trajectory Range Queries in Hybrid-Storage Blockchains

cs.DB ·2026-08-21 ·Zhongming Yao, Junchang Xin, Yumeng Song, Yusen Mao, Kristian Torp +5 more
similarity 0.60
Abstract

Due to their increasingly large volumes, outsourcing of trajectory storage and querying to third-party service providers has become attractive. However, in such outsourced environments, service providers may return incorrect, e.g., incomplete, tampered, or invalid query results, making verifiability of query results an important consideration. Existing hybrid-storage blockchains offer limited support for trajectory data, lacking authenticated data structures (ADS) that enable efficient verification. For example, ADSs designed for queries on one-dimensional data are unsuitable for queries on multidimensional trajectory data, while ADSs tailored for discrete data may yield incomplete results when applied to continuous trajectory data. We propose the first framework for verifiable trajectory range queries in hybrid-storage blockchains, called VTRQ. It features two efficient ADSs: (i) a spatial ADS for road networks that leverages hierarchical organization to aggregate trajectory, edge, and node hashes, thus reducing redundant computations and improving spatial verification efficiency; and (ii) a temporal ADS based on interval trees, which indexes only the start and end times of trajectories, thereby enabling pruning and efficient temporal verification. By separating spatial and temporal indexing, the method reduces the need for data comparison, enhancing both query and verification efficiency. To aggregate spatial and temporal query results, VTRQ provides a spatio-temporal edge aggregation mechanism that combines temporal verification of spatial nodes, spatial intersection computation, and temporal intersection analysis to achieve spatio-temporal filtering.

0.46