CS Paper Radar

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

Zhongming Yao, Junchang Xin, Yumeng Song, Yusen Mao, Kristian Torp, Yuemin Ding, Divesh Srivastava, Yushuai Li, Christian S. Jensen, Tianyi Li

cs.DB ·submitted 2026-08-21 17:24 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

VeriTS: Verifiable Model-Enhanced Time-Series Queries on Blockchain Systems

cs.DB ·2026-08-28 ·Zhongming Yao, Jun Pang, Chenxu Wang, Qian Ma, Peiyuan Guan +1 more
similarity 0.61
Abstract

Every blockchain transaction carries a timestamp, and the chain imposes a total order. On-chain data therefore forms per-source time-series streams. However, existing systems support only basic lookups on blocks and transactions, and cannot answer time-series queries such as time-range retrieval and windowed aggregation. Offloading queries off-chain restores expressiveness, but the off-chain query layer is untrusted, so results must be verifiable. To this end, we propose VeriTS, the first verifiable time-series query framework for blockchain systems. It supports efficient range and aggregation queries. VeriTS maintains an off-chain query layer. In this layer, each stream is kept under one tree whose nodes carry authenticated aggregates, so the query index is itself the authenticated data structure. A light client thus verifies a windowed aggregate from a logarithmic number of authenticated nodes rather than from every record. VeriTS further answers error-tolerant queries from compact model representations of a stream, and extends the completeness and soundness guarantees to such approximate answers. As VeriTS never trusts the model behind a representation, a faulty or adversarial model can only widen an answer's certified interval, never falsify it. Experiments offer evidence that on windowed aggregation, VeriTS improves verification efficiency by more than two orders of magnitude over per-record proofs. On range retrieval, proofs shrink by up to 14.5x.

0.18

Authenticated Data Structures for Dynamic Workloads

cs.CR ·2026-08-25 ·Ziheng Shangguan, Aviv Yaish, Dahlia Malkhi
publishedhot direction similarity 0.60
Abstract · 40 pages, 18 figures, 2 tables. Appendix A-G included

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.

0.49

Asynchronous Verifiable Information Dispersal with Low Space and Communication Complexity

cs.DC cs.CRcs.IT ·2026-08-25 ·Thomas Locher, Yvonne-Anne Pignolet
published similarity 0.57
Abstract · Published at SPAA 2026 (July 6-10, 2026, London, UK)

The primary goal of a distributed storage system is to ensure that clients can both write and read data in a reliable and consistent manner, even in the presence of failures. While existing asynchronous verifiable information dispersal (AVID) protocols achieve optimal space complexity for storage and communication complexity for data retrieval in a Byzantine setting, the crucial operations of data dispersal and node recovery have received less attention. We propose an efficient AVID protocol that simultaneously guarantees low complexities for dispersal, storage, retrieval, and recovery. At the core of the proposed protocol lies a novel mechanism to encode data in a two-dimensional matrix and a bespoke dispersal algorithm. The protocol maintains an optimal communication complexity for retrieval while substantially improving upon the state of the art for recovery. Additionally, we describe how the protocol can be modified in order to reduce the space complexity and the communication complexity for dispersal, at the expense of a higher communication complexity for retrieval and recovery. As the proposed protocols strike a balance across all considered metrics, they are suitable for a broad range of real-world use cases.

0.46

A Graph-Based Framework for Extending Metric Differential Privacy Mechanisms

cs.CR ·2026-09-12 ·Ruiyao Liu, Chenxi Qiu
top venue similarity 0.56
Abstract · ACM CCS 2026

Metric differential privacy (mDP) is well suited to structured secret domains, but directly constructing utility-aware mechanisms over large or fine-grained domains is often computationally prohibitive. We study extension-based mDP design, where a mechanism is first specified on a finite set of seed records and then extended to a larger target domain. To our knowledge, this is the first work to systematically formulate extension as a general design paradigm for mDP rather than a method-specific construction. We present a graph-based extension framework, identify three requirements for correctness, local mDP constraints, overlap consistency, and successor-level mDP preservation, and show that, under these conditions, the induced global mechanism is well defined and satisfies $ε$-mDP on the target domain. We further instantiate the framework with a tree-based extension algorithm for multi-resolution grids, where multi-dimensional extension is realized through one-dimensional interpolation and dimension-wise composition. Experiments on road-map datasets demonstrate that our approach achieves a strong utility-scalability trade-off while preserving exact mDP guarantees.

0.41

XIR: A Framework for Interoperability across Cross-Chain Protocols Based on a Verifiable Intermediate Representation

cs.CR cs.DC ·2026-09-17 ·Yushen Li, Linpeng Jia, Jiaying Feng, Ziliang Liao, Yi Sun
similarity 0.55
Abstract · Submitted to Blockchain: Research and Applications

Cross-chain protocols enable applications to exchange messages across blockchains. Under point-to-point configurations, communication depends on a direct connection between the source and destination blockchains, limiting blockchain reachability and requiring additional configurations to connect more blockchains. To quantify this problem, this paper analyzes approximately 25 million mainnet cross-chain transaction events collected from six protocols (Axelar, CCIP, Hyperlane, LayerZero, Relay, and Wormhole) between January and October 2025. The resulting graph covers 286 active blockchains and 11,935 directly connected ordered blockchain pairs. These connections provide a direct reachability of 14.64%, while full direct connectivity would require 81,510 point-to-point configurations. We present XIR, a framework for interoperability across cross-chain protocols based on a verifiable intermediate representation. This representation binds an application message to an ordered record of authenticated cross-chain protocol deliveries, preserving message identity and verification history across protocol boundaries. XIR Gateways and XIR Adapters use this representation to compose existing connections into same-protocol and cross-protocol multi-hop paths. We implement an XIR prototype integrating Hyperlane and LayerZero and evaluate it in local and public-testnet environments. Theoretical analysis and evaluation show that, with correctly configured cross-chain protocol connections, XIR avoids 67,018 additional point-to-point configurations, equivalent to 84.88% of the total required by a point-to-point configuration baseline serving the same reachable pairs, and increases reachability from 14.64% to 96.86% of all ordered blockchain pairs.

0.16

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.54
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

Authenticated Approximate Nearest Neighbor Search in Outsourced Vector Databases

cs.DB cs.CR ·2026-11-12 ·Yuanhang Zhou, Xinyi Zhang, Cheng Xu, Jianliang Xu
similarity 0.54
Abstract

Approximate Nearest Neighbor (ANN) search has become a fundamental query primitive in modern vector databases for managing large-scale embedding data. To support growing vector collections, organizations increasingly outsource database management and query processing to third-party clouds. However, untrusted service providers may return suboptimal or fabricated results, posing a serious threat to ANN search integrity. Existing authenticated ANN approaches face substantial scalability challenges. They typically require transmitting high-dimensional vectors for distance verification and rely on topology-agnostic authentication structures, resulting in excessive communication and verification overhead. In this paper, we propose VIDA, a novel and efficient scheme for authenticated graph-based ANN search. VIDA replaces raw vector transmission with compact vector commitments and employs an aggregated Inner Product Argument to efficiently verify multiple distance computations. Furthermore, we introduce MeST, a topology-aware authenticated data structure that aligns authentication paths with graph traversal, significantly reducing structural proof overhead. Additionally, we design a quantization-aware authentication strategy that exploits distance bounds for pruning, reducing the number of exact distances requiring cryptographic authentication. Extensive experiments demonstrate that the proposed schemes substantially improve the efficiency of authenticated ANN search, achieving up to a $6.6\times$ speedup in end-to-end latency and reducing data transfer time by up to 99.2% compared with state-of-the-art methods.

0.08

VerfGraph: Efficient Zero-Knowledge Verifiable Graph Query Evaluation System

cs.CR ·2026-11-03 ·Tianyi Ma, Yuncong Zhang, Yuanzhuo Yu, Boshi Yuan, Shi-Feng Sun
benchmark similarity 0.54
Abstract · 13 pages, 3 figures, 7 tables

Graph databases are often used to manage relationship-rich data, whose graph structure and attributes may be sensitive. In many applications, a database owner or a service provider evaluates queries over a private graph for a client. Because the graph cannot be fully disclosed and independently re-executing the query may be impractical, the client cannot directly verify the returned result. This creates a need for verifiable graph query evaluation that preserves data confidentiality. We present VerfGraph, a zero-knowledge system for verifiable graph query evaluation, which enables a client to verify that the query result was correctly computed over a committed graph data, without revealing private graph records or intermediate query values beyond the public inputs and what is implied by the query result. Building on the expansion-centric model introduced by the state-of-the-art zero-knowledge verifiable graph query evaluation system ZKGraph (ICDE'26), VerfGraph achieves more efficient and expressive zero-knowledge verifiable graph query evaluation by advancing design in two key ways. First, we propose novel operator-proof methods for core expansion and shortest-path operations that reduce costly sorting and comparison checks and eliminate edge canonicalization for bidirectional expansion. Furthermore, we introduce correctness proofs for count and weighted shortest-path operators, broadening the class of graph queries that can be verified. We evaluate VerfGraph using the LDBC Social Network Benchmark. Compared with ZKGraph on complex IC queries, VerfGraph achieves $33.9\times$-$59.7\times$ speedups in proof generation and reduces peak prover memory by factors of $4.5\times$-$6.6\times$, while maintaining millisecond-level verification and producing sub-MB proofs.

0.27