Skip to content

core: add paged read-walk evidence without full matched-set materialization #230

Description

@heyoub

Problem

Store::query_with_read_walk_evidence accepts a limit, but the implementation first calls query_hits_with_snapshot(region), materializing the complete matching hit set, and only then applies the limit.

That makes the result bounded while the work is not bounded. A hot-path consumer cannot use this evidence surface for large regions without reintroducing O(base/matched-set) discovery, memory, and latency.

Requested neutral contract

Add a paged read-walk evidence API whose work and output are both bounded:

  • opaque cursor bound to store identity, region, frozen input frontier/ceiling, and prior page anchor;
  • explicit page limit enforced during discovery, not after materialization;
  • deterministic item order and canonical report body across restart;
  • page evidence including input frontier, returned range, next cursor, truncation state, and proof references;
  • typed failures for stale/forked cursor, store swap, frontier regression, malformed cursor, and anchor mismatch;
  • a fold/combination rule that proves a complete walk from page reports without reopening the base set.

The API should remain region- and payload-neutral.

Proof requested

  • operation-count witness at 100k+ entries showing work proportional to page size plus index seek;
  • no allocation proportional to the complete matched set;
  • restart/resume from a cursor;
  • empty page and exact-boundary page;
  • concurrent append above the frozen ceiling does not perturb the walk;
  • truncation/fork/store-swap/anchor mismatch fail closed;
  • concatenated page results and combined evidence equal the existing full read-walk result at the same ceiling.

Downstream containment

The downstream keeps bounded query_entries_after paging on agent hot paths and uses read-walk evidence only in explicit offline/proof contexts. It will switch through a narrow compatibility seam when this API ships rather than reimplementing the substrate proof format.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions