PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Zhongming Yao, Jun Pang, Chenxu Wang, Qian Ma, Peiyuan Guan, Shiliang Zhang

arXiv:2608.28318v1cs.DB

TL;DR

Blockchain systems lack expressive and verifiable time-series queries, while off-chain query layers are untrusted. VeriTS combines authenticated interval-tree indexing with exact and bounded-error model paths, with experiments reporting major verification and proof-size improvements.

  • Problem

    Existing blockchain systems mainly support block- and transaction-level lookups, leaving time-range retrieval and windowed aggregation without a verifiable off-chain query layer.

  • Method

    VeriTS stores streams under authenticated aggregate interval trees for exact queries and authenticated model segments for approximate queries, with miners anchoring their digests on-chain.

  • Results

    Verification efficiency improves by more than two orders of magnitude over per-record proofs, and range-query proofs shrink by up to 14.5×.

  • Takeaways & Limitations

    An untrusted encoder may enlarge proof size and answer width, but accepted approximate answers remain correct within their certified intervals.

Abstract

from arXiv · show

Blockchain data is temporal. Every transaction carries a timestamp and the chain imposes a total order, so on-chain data 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 without altering blockchain storage structures. VeriTS maintains an off-chain query layer that represents each stream through an authenticated aggregate interval tree. The tree serves as the query index and as the authenticated data structure at once, so a windowed aggregate is answered by folding a logarithmic number of node aggregates. VeriTS verifies completeness through a minimum covering set and soundness through aggregate folding. It extends both guarantees to an approximate path over model segments, redefining completeness and soundness under bounded error. Miners validate a model's residual rather than replay its computation, so even an adversarial encoder can inflate proof size and answer width but never correctness. Experiments offer evidence that on windowed aggregation, VeriTS improves verification efficiency by more than two orders of magnitude over per-record proofs. Range-query proofs shrink by up to 14.5x.

I. INTRODUCTION

VeriTS addresses the lack of expressive, verifiable time-series queries on blockchains by combining an off-chain query layer with authenticated structures and an approximate model path.

  • Motivation: Blockchain transactions form ordered per-source time-series streams, but existing blockchain interfaces mainly support block- and transaction-level lookups.Applications need time-range retrieval and windowed SUM, COUNT, MIN, MAX, and AVG queries.
  • Challenges: Off-chain query layers improve expressiveness but require verification because their data and operators are outside blockchain consensus.Completeness means no in-range record is missing, while soundness means every returned record is on-chain and in-range.
  • Framework: VeriTS represents each stream over an authenticated aggregate interval tree that serves simultaneously as the query index and authenticated data structure.Windowed aggregates fold a logarithmic number of node aggregates, while miners anchor the supporting structure’s digest on-chain.
  • Approximate path: The framework extends exact verification with an encoder-independent approximate path over authenticated model segments under bounded error.An untrusted encoder can affect proof size and answer width but never correctness.
  • Results: More than two orders of magnitude higher verification efficiency and up to 14.5× smaller range-query proofs are reported relative to baselines.These figures come from the experimental study described in the introduction.

II. RELATED WORK

Prior verifiable blockchain-query systems mainly target Boolean, relational, or graph-oriented access, leaving verifiable temporal window aggregation insufficiently addressed.

  • Authenticated queries: Existing blockchain verifiable-query systems use accumulator-, Merkle-, or skip-list-based authenticated data structures for range, provenance, SQL-subset, and related queries.These systems authenticate access patterns but do not establish VeriTS’s temporal aggregation focus.
  • Data views: Graph-oriented systems support topology traversals, while relational schemes flatten transactions into tables and lack a native ordered-interval index.Neither workload model directly matches append-heavy temporal streams and windowed aggregation.
  • Research gap: Verifiable windowed aggregation over blockchain data’s temporal view remains an open gap in the reviewed work.The passage contrasts this gap with existing graph-view and coarse-grained or absent integrity mechanisms.

B. Data Model

VeriTS organizes transaction-derived records into ordered per-source streams and authenticates them with an aggregate interval tree supporting exact query verification.

  • Data Model: A time-series record contains a source identifier, timestamp, value, and optional attribute set, and streams order records by timestamp with on-chain-position tie breaking.Records may represent transactions or per-block metrics.
  • Data Model: Range queries return all records in a source stream within a time interval, while aggregation queries apply SUM, COUNT, MIN, MAX, or AVG to in-range values.The example sums values 10, 12, and 9 over [t1, t3] to obtain 31.
  • Authenticated structure: The authenticated aggregate interval tree adapts authenticated aggregation to append-only, time-ordered streams and anchors each stream’s root digest on-chain.Each internal node stores an aggregate for its subtree, allowing subtree certification without traversing leaves.
  • Query verification: Appending a record updates O(log n) nodes on one root-to-leaf path, and a windowed aggregate folds the O(log n) covering-node aggregates.The client checks the covering set, anchored root, and aggregate fold.

B. Range and Tag-Constrained Queries

VeriTS handles exact range, tag-constrained, sliding-window, and approximate queries through authenticated records, cached covering sets, and certified model segments.

  • B. Range and Tag-Constrained Queries: A range-query proof opens the minimum covering subtrees, includes all in-window records and boundary records, and costs O(k+log n).The client rebuilds leaf hashes and matches the reconstructed root to the anchored digest.
  • B. Range and Tag-Constrained Queries: Tag-constrained aggregation uses the range verification object because precomputed subtree aggregates do not summarize predicate-filtered subsets.The client filters authenticated in-window records locally before aggregating them.
  • B. Range and Tag-Constrained Queries: For sliding windows, the client caches verified node pairs and receives only a delta verification object for each shift.Adjacent minimum covering sets share nodes covering their overlapping interval.
  • B. Range and Tag-Constrained Queries: The approximate path answers bounded-error queries from certified model segments, whose value and arrival models resolve aggregates and window boundaries.The representation supports closed-form aggregation over contiguous position ranges and answers in proportion to overlapping segments rather than records.

B. Segment Authentication

VeriTS authenticates model segments with a segment-interval tree and certifies approximate query answers using bounded value and arrival errors. Clients verify coverage and derive intervals containing exact aggregates from authenticated parameters.

  • Segment Authentication: The segment-interval tree stores segment intervals, model parameters, error bounds, and counts, while its root and stream budget cap are anchored on-chain.The tree is an authenticated aggregate interval tree specialized to model segments.
  • Segment Authentication: Miners validate each segment against raw records before anchoring it in the segment-interval tree, with amortized O(1) cost per record.They check both error inequalities and the segment’s record count; validation occurs off the query path.
  • Verification Semantics: Model-completeness requires authenticated segments to fully cover the query interval, verified through a segment-level minimum covering set and boundary proof.This replaces record-level coverage with a boundary proof over segments.
  • Boundary Resolution: The arrival model resolves boundary membership in O(1), leaving only a bounded run of undecided positions at each window edge.With Ethereum-like spacing, µj=12 s and εtj=6 s, at most one position is undecided regardless of segment length.
  • Aggregate Error Bounds: For non-negative values, aggregate intervals can tighten their lower endpoint to S −∆v, while extrema remain bounded by the largest segment error.The client verifies an interval guaranteed to contain the exact answer rather than an unknown-accuracy point estimate.

D. Encoder Independence and Payoff

VeriTS makes its approximate path independent of encoder trust: encoder choices affect proof size and answer width, but authenticated residual checks preserve correctness. Approximation benefits retrieval more than aggregation because compression replaces returned records, whereas aggregation is already logarithmic.

  • Budget Allocation: Budget allocation is workload-sensitive: interior segments favor tight value bounds, while segments repeatedly straddling window edges favor tighter arrival bounds.A learned encoder can exploit this allocation axis because local sweeps do not observe workload frequency.
  • Encoder Independence: An arbitrary, potentially adversarial encoder can change segment count, verification-object size, and latency, but cannot make an accepted interval incorrect.Every anchored segment passes miner replay checks, and client checks use only fields authenticated by the anchored tree root.
  • Encoder Independence: The trusted computing base is unchanged whether segments come from a greedy sweep or a billion-parameter pretrained model.Encoder provenance does not enter the client’s authenticated checks.
  • Payoff: Aggregation proofs improve only from O(log n) to O(log s), whereas retrieval proofs shrink with the stream’s compression ratio by shipping segments instead of records.The approximate path therefore offers a modest aggregation gain but a compression-ratio-scale retrieval gain.
  • Payoff: A coarser error bound merges more records per segment but widens the answer interval, creating a compression-dependent trade-off.The approximate path can be counterproductive below its stream-specific break-even point.

VII. SECURITY ANALYSIS

VeriTS anchors both stream structures under consensus and verifies query covers against authenticated roots. Security follows because omissions create coverage gaps and tampering changes the anchored digest.

  • Security Model: Both per-stream roots enter the block header under BFT consensus with a 2f+1 quorum, preventing a single node from anchoring a forged digest.VeriTS defines verifiability against polynomial-time query-layer adversaries with negligible acceptance probability for invalid answers.
  • Security Guarantees: The exact path enforces completeness through a gap-free cover of the query interval and soundness through equality with the anchored root.A hidden record or segment opens a rejected gap, while altering a leaf, aggregate, or segment field changes a presented node.

VIII. EXPERIMENTS

Experiments evaluate VeriTS on five Ethereum and TRON streams spanning rates, events, state, and degenerate values, using range and aggregation workloads with multiple verification baselines. The setup also tests workload-aware encoder policies and exact-path query cost.

  • Datasets: Five streams from 30,000 Ethereum blocks and 200,000 TRON blocks cover rate, event, state, and degenerate quantities.ETH-Gas is a rate; ETH-Transfer and TRON-Transfer are events; TRON-Balance is state; TRON-Dust is a constant stream.
  • Query Workload: The workload uses time-range and SUM, COUNT, MIN, MAX, and AVG aggregation queries over 100–2000-record windows with 10%–50% slides.Each result averages five repetitions over 20–40 random windows.
  • Baselines: Verification compares VeriTS with window re-download and recomputation, per-record Merkle completeness proofs, and technique ablations.The evaluated optimizations include minimum-covering-set completeness, subtree-embedded aggregate folding, and delta verification objects.
  • Exact-Path Cost: Fig. 2 measures exact-path query cost on ETH-Gas, while the accompanying experiment reports object touches and wall-clock latency for aggregation.The figure compares AIT nodes for VeriTS with records touched by scan-based methods.
  • Encoder Study: The encoder study matches segment count across uniform, learned, and adversarial budget-allocation policies, fixing proof size and verification time by construction.The learned policy uses workload touch frequency, while E-Adv reverses the allocation exponent.

B. Query Performance

VeriTS answers windowed aggregates by folding a logarithmic number of authenticated interval-tree nodes, keeping touched objects nearly constant as windows grow. Its structural efficiency does not translate directly into prototype wall-clock latency, but it reduces transferred verification data and remains largely stream-independent.

  • Windowed aggregation: VeriTS touches a near-constant handful of authenticated interval-tree nodes as the window grows from 100 to 2000 records, while scan baselines touch every record.The gap reaches a factor of 130 because VeriTS folds the O(log n) node aggregates of a canonical cover.
  • Windowed aggregation: A twentyfold longer window costs VeriTS only five additional nodes because aggregation folds the canonical cover rather than visiting window records.
  • Wall-clock latency: QA and QB are several times faster than VeriTS in prototype wall-clock latency, although all three remain well under a millisecond.The latency gap reflects a vectorized scan versus interpreted tree-object folding rather than the structural query advantage.
  • Stream robustness: At a 2000-record window, verification-object size varies by only 10.9% across five streams because exact-path cost depends on canonical-cover shape, not value meaning.
  • Range retrieval: Exact-path range retrieval transfers the k returned records, giving it an unavoidable O(k) result-transfer cost.This exact series is the baseline for the approximate path.

C. Verification Performance

VeriTS substantially reduces verification-object size and client verification time relative to record-oriented baselines, while sliding-window savings depend on canonical-cover alignment. Its security evaluation rejected all tested forgeries through complementary authenticated checks.

  • Client verification time: VeriTS achieves a 1031-fold client-time advantage over B-Leaf at the longest window while remaining submillisecond.B-Leaf rehashes every leaf and folds the aggregate linearly in k; VeriTS rehashes only O(log n) cover nodes.
  • Sliding windows: On ETH-Gas, the delta verification object is 1.90× smaller than B-Ind at a 10% slide.Previously authenticated node metadata can be cached, but smaller slides do not necessarily increase savings because canonical-cover alignment changes the decomposition.
  • Tamper detection: All 900 tested forgeries were rejected across exact and approximate paths.The attacks included altered aggregates, forged hashes, omitted coverage, modified records, shifted models, and manipulated error declarations.
  • Tamper detection: Internally consistent verification objects are caught by the covering-set test, root check, and client re-derivation.These checks respectively address coverage, authentication, and recomputation of quantities outside individual nodes.

4) Scalability and construction cost:

VeriTS scales favorably for fixed-window verification and supports approximate range answers whose proof savings depend on stream compressibility. Model certification is much cheaper than encoder construction, while aggregation gains remain modest.

  • Scalability and construction cost: A 16.8-fold longer TRON-Dust stream increases fixed-window VO size by 17% and client time by 26%.With a 1,000-record window, only tree depth changes, adding one sibling and one client-fold hash per doubling of n.
  • Scalability and construction cost: Miner-side model certification costs microseconds per record, 18 to 462 times less than the encoder that produced the segments.Certification replays closed forms at each position rather than replaying the search that fitted them.
  • Range retrieval: Approximate range proofs are larger than exact proofs on event streams, similar on the rate stream, and 4.05× smaller on the state stream.The trade depends on whether segment model fields cost less than transferring the k exact records.
  • Range retrieval: Stream quantity determines approximate-path outcomes: event amounts form two-record segments, running totals support thirteen-record segments, and constants can use one segment indefinitely.TRON-Transfer and TRON-Balance contain identical transfer data but receive opposite compression outcomes because one is event-like and the other is a running total.
  • The break-even point: The measured TRON-Dust range-proof saving is 14.5×, below the 24.0× prediction because Merkle siblings do not shrink with compression.
  • Aggregation: Approximate-path aggregation VO size changes by well under a factor of two on every stream, making retrieval rather than aggregation the main benefit of model segments.Compression removes only log2(n/s) levels from an already-logarithmic proof.
  • Boundary resolution: Across 1,000 queries, the verified interval contained the exact answer for every tested stream, budget, and window.The undecided boundary count stayed in single digits over most arrival-budget settings and reached about eleven only at the loosest budget.

5) The five aggregates:

VeriTS’s verified intervals behave differently across SUM, MIN, MAX, AVG, and COUNT as window size, skew, and budget allocation change. Across encoder policies, the returned intervals remained exact-answer covering while learned allocation benefits depended on the value budget’s role.

  • Aggregate behavior: SUM’s interval widens from 170 to 1,830 budget units as the window grows from 100 to 2,000 records.MIN and MAX stay within 2.0 to 2.2, AVG narrows from 2.0 to 0.93, and COUNT stays between 2.5 and 3.0 records.
  • Aggregate behavior: At 2,000 records, the SUM interval is 1,961 times the AVG interval because SUM pays the value term once per covered record.The boundary term is paid twice regardless of window length, while AVG divides a growing SUM interval by a growing count.
  • Verification under encoders: Across 108,000 interval checks, every returned interval contained the exact answer under every encoder, stream, skew, and aggregate.The client checks authenticated fields whose bounds miners validated against the chain.
  • Verification under encoders: Learned narrows interval width to 0.23 and 0.31 of Uniform-ε on ETH-Gas and TRON-Balance, while E-Adv widens it by up to 25.6×, 18.9×, and 10.5× on three streams.The reported E-Adv increases are for TRON-Dust, ETH-Gas, and TRON-Balance; Learned’s reductions are for ETH-Gas and TRON-Balance.
  • Encoder effects: Learned’s benefit tracks the share of interval width attributable to the value budget rather than stream compressibility.Halving εv yields widths of 0.42 and 0.62 where the value term dominates, but 0.99 and 1.00 where it does not; on TRON-Dust, halving εt yields 0.58.
  • Encoder effects: E-Adv’s damage grows with skew, whereas Learned’s benefit appears only at substantial skew and is not pointwise at moderate skew.Concentrated workloads create both the opportunity to tighten the busy region and the exposure from tightening elsewhere.
Loading 2608.28318v1…