💻 computer science

Replay-Safe Decision Provenance for Mutable Geospatial Contexts: Version-Bound Receipts and Complete Change Frontiers

This paper proposes a replay-safe decision provenance framework for mutable geospatial contexts that uses version-bound receipts and geometric change frontiers to ensure decision integrity while achieving significant computational savings through selective replay.

Original authors: Duy-Quan Nguyen

Published 2026-09-22

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Duy-Quan Nguyen

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where every decision made about a location is tied to a specific moment in time, like a photograph taken with a camera that never changes its settings. In the digital realm, this involves "geospatial data," which is simply information about where things are on the Earth's surface, and "provenance," which is the detailed history of how that information was created and used. When a system decides whether a specific point, like a delivery truck or a mobile phone, is inside or outside a defined area, it relies on a set of rules: the shape of the area, the distance thresholds, and the software code used to make the judgment. These rules are not permanent; they change over time as boundaries are redrawn, policies are updated, or software is improved. The challenge arises when we look back at an old decision. If we try to replay that decision today using the current, updated rules, the answer might change silently, even though the original record looks exactly the same. This creates a problem for trust: how can we be sure that a historical decision was correct for the time it was made, rather than just a reflection of today's settings?

This question matters because many critical systems rely on these location-based judgments. From managing land ownership to enforcing safety zones around hazardous sites, the ability to prove exactly what a system decided, and why, is essential. If a court case or an insurance claim depends on a past decision, that decision must be reproducible under the exact conditions that existed when it happened. If the system accidentally uses a new map or a new rulebook to re-evaluate an old event, the result is a "silent context substitution," where the record remains unchanged but its meaning shifts. This paper addresses that specific failure by proposing a way to lock a decision to the exact version of the world it was made in, ensuring that history cannot be rewritten by the passage of time.

The author, Duy-Quan Nguyen, developed a system that treats a decision not just as a simple "yes" or "no," but as a package containing the evidence, the specific rules used at that moment, and the final verdict. He calls this a "receipt." When a decision is issued, the system creates a receipt that binds the location data to a specific version of the geometry, the policy, and the software code. This receipt is immutable, meaning it cannot be altered. If someone later wants to see what the decision would be under today's rules, the system does not overwrite the old receipt. Instead, it generates a new, separate document called a "counterfactual certificate." This new document explicitly states that it is a re-evaluation under different conditions, keeping the original historical record distinct and intact. This separation ensures that an old decision can be verified as it was originally made, while also allowing for a clear comparison with how the same event would be judged today.

To make this process efficient, the author had to solve a difficult mathematical problem: how to find all the past events that might have changed their status without having to re-check every single one of them. Imagine a city with a million recorded locations. If the boundary of a protected zone shifts by just a few meters, checking every single point in the city would be slow and wasteful, especially if most points are far away from the change. The author derived a precise method to identify the exact "frontier" where a change could occur. He proved that for a specific type of three-level classification system—where areas are marked as green, yellow, or red based on distance—the set of points that could change is exactly the symmetric difference of the offset regions (the areas covered by the old or the new offset boundary but not by both).

To make this practical for computers, the author created a conservative filter. Instead of calculating the complex, jagged shapes of the changing boundaries every time, the system draws a simple, slightly larger rectangle around the area of change. It then checks only the points that fall inside this rectangle. This method is safe because it never misses a point that actually changed; it might include a few extra points that didn't change, but it guarantees that no changed point is left behind. In tests, this approach was incredibly effective. When the data was spread out evenly across a large area, the filter reduced the number of points that needed a full re-check by more than 99 percent. This meant the system could skip the heavy lifting for almost the entire dataset, focusing only on the tiny fraction of points near the boundary.

However, the author was careful to show that this efficiency depends on how the data is distributed. In a second test, he simulated a scenario where most of the points were clustered right along the edge of the boundary, which is common in real-world situations like traffic monitoring near a zone limit. In this case, the filter was less effective, reducing the workload by only about 30 percent, because so many points were already near the line of change. This finding highlights that while the method is powerful, its speed depends on the nature of the data. The author also tested the system's ability to detect errors. He simulated situations where someone tried to swap out the map, the rules, or the software code without updating the receipt. The system successfully caught every single one of these substitutions, refusing to produce a result if the necessary components were missing or altered.

The study was conducted using synthetic data, meaning the author created his own test scenarios rather than using real-world events from a specific company or government. He ran simulations with up to one million events to see how the system performed at scale. The results showed that the system could verify the integrity of historical decisions and identify exactly which records needed re-evaluation. The author emphasizes that his work does not prove that the original location data was physically correct—a fake GPS signal will still be processed as real—but it does prove that the decision was made consistently with the rules that were in place at the time. He also noted that the system requires a trusted environment to store these receipts and that the underlying technology, while useful for blockchain systems, can also work in standard databases.

Ultimately, this work provides a blueprint for keeping digital history honest. By binding decisions to their specific context and creating a clear, auditable path for re-evaluation, the system prevents the silent drift that can corrupt historical records. It offers a way to look back at the past with confidence, knowing that the answer provided is the one that was truly given, not a new answer disguised as an old one. The research confirms that with the right structure, we can preserve the meaning of our digital decisions even as the world around them continues to change.

Technical Summary: Replay-Safe Decision Provenance for Mutable Geospatial Contexts

1. Problem Statement

The paper addresses the issue of silent context substitution in geospatial decision-making. A historical spatial decision (e.g., a geofencing verdict) is issued against a specific version of the world, including geometry, policy thresholds, coordinate reference systems (CRS), and evaluator code. While the evidence (e.g., a coordinate) may remain immutable, the context used to interpret it is mutable.

If a system re-evaluates a historical decision using current context objects rather than those bound at the time of issuance, the classification may change even if the record is byte-identical. This failure mode undermines auditability and the integrity of historical records in spatial databases, event-sourced systems, and ledger-backed architectures. Existing solutions, such as temporal databases or smart contracts, often fail to distinguish between "as-issued" semantics, "current-context" semantics, and explicit "counterfactual" comparisons, or they lack a mechanism to identify exactly which historical records require re-evaluation without replaying the entire history.

2. Methodology and Protocol Design

2.1 Semantic Separation

The author defines three distinct semantic views for spatial decisions to prevent conflation:

As-issued: The result under the context cryptographically bound when the decision was created.
Current-context: A new result generated under a context designated as current at query time.
Counterfactual: An intentional comparison under any explicitly named, non-current context version.

2.2 Version-Bound Receipts

To ensure replay safety, the protocol binds a decision receipt that includes:

Evidence hash.
A declared interpretation closure (context hash), which encompasses geometry, policy, evaluator code, spatial semantics (CRS, precision, boundary rules), and validity intervals.
The issued decision and issuance time.

The receipt is immutable. Any subsequent reclassification generates a separate reclassification certificate that links the original receipt to the new result, rather than overwriting the original.

2.3 Exact Change Frontier Characterization

For a specific three-tier point-to-polygon classifier (Green/Yellow/Red based on distance thresholds $r_1$ and $r_2$ ), the paper derives an exact mathematical characterization of label changes.

Theorem 1: A point changes its tier between context $C_0$ and $C_1$ if and only if it lies in the union of the symmetric differences of the two offset regions:
$\mathcal{F}(C_0, C_1) = [B_{r_1}(G_0) \triangle B_{r_1}(G_1)] \cup [B_{r_2}(G_0) \triangle B_{r_2}(G_1)]$
where $B_r(G)$ is the closed offset of geometry $G$ by distance $r$ .

2.4 Conservative Filtering

To avoid expensive exact geometric evaluations for every historical event, the author proposes a conservative grid-coordinate filter:

It constructs a bounding rectangle $R$ that covers the union of the old and new geometries, expanded by the maximum outer threshold plus a margin.
It selects all grid cells within this rectangle.
This creates a superset ( $\hat{Q}$ ) such that the exact change frontier $\mathcal{F} \subseteq Q \subseteq R \subseteq \hat{Q}$ .
Only points falling within this candidate set undergo exact re-evaluation; points outside are guaranteed to retain their original label.

2.5 Verification and Dependency Binding

A minimal executable verifier is implemented to check:

Integrity of artifacts (hash verification).
Consistency of the declared evaluator and spatial semantics.
Detection of missing or substituted dependencies (geometry, policy, evaluator, canonicalization, CRS).
Explicit failure states for mismatches, ensuring the system does not silently substitute current pointers for historical ones.

3. Key Contributions

Semantic Definition: Formalizes the separation of "as-issued," "current," and "counterfactual" decision semantics with a fail-closed invariant.
Protocol Specification: Defines a receipt protocol that binds evidence to a declared interpretation closure and an append-only reclassification certificate.
Theoretical Derivation: Proves an exact characterization of tier changes for a distance-based classifier and provides a conservative filter with a "no-omission" guarantee.
Empirical Evaluation: Validates the approach using synthetic benchmarks (90 trials, up to 1 million events) to measure candidate reduction, runtime, and dependency detection.

4. Experimental Results

The study utilized 90 synthetic mutation trials with 100,000 events and scaling tests up to 1,000,000 events across two data distributions: Uniform and Boundary Mixture (70% of points near polygon edges).

Completeness: In all 90 trials, the selective replay returned exactly the same set of changed identifiers as a full two-context replay (100% recall).
Candidate Reduction (Uniform Distribution): The grid filter reduced the number of events requiring exact re-evaluation by 99.47% to 99.83%.
Candidate Reduction (Boundary Mixture): Due to the high concentration of points near decision boundaries, reduction was lower, ranging from 29.84% to 29.96%.
Performance (Speedup):
- For uniform histories, the cached-label grid-filter replay achieved speedups of 53.25× to 63.90× compared to full replay, while the direct-coordinate rectangle baseline performed better, achieving 57.65× to 70.70×.
- For boundary mixtures, the grid-filter speedups were modest (1.39× to 1.76×), while the direct-coordinate rectangle baseline achieved 1.51× to 1.89×.
- Scaling to 1 million uniform events reduced selective replay time from ~2.4s (full) to ~0.01s.
Dependency Detection: A logical ablation study confirmed that only a "declared interpretation closure" (binding geometry, policy, evaluator, canonicalization, and CRS) could detect all five types of single-field substitutions. Partial bindings failed to detect specific changes.
Verifier Checks: A local verifier passed 19 functional checks, including detection of missing artifacts, hash mismatches, and isolation of issued results from current pointers.

5. Significance and Claims

The paper claims to establish conditional replay integrity and distribution-dependent recomputation savings for historical spatial decisions.

Modesty of Claims: The author explicitly states they do not claim to establish physical-location truth, production ledger enforcement, or completeness beyond the declared evaluator interface. The work does not claim that attaching a version ID is novel, but rather the explicit integration of non-interchangeable decision semantics, a declared dependency closure, and an exact spatial label-change characterization.
Practical Utility: The results support the use of selective replay to reduce computational costs when event distributions are sparse relative to the decision region. The approach is applicable to conventional append-only databases and does not strictly require a blockchain, though blockchains are noted as useful for shared, tamper-evident commitments among mutually distrustful organizations.
Limitations: The study is limited to synthetic planar workloads, a specific polygon family, and integer-coordinate fixtures. It does not evaluate bucketed spatial indexes (like R-trees) for sublinear lookups, nor does it address complex geodesic distances or arbitrary CRS changes. The "cold-start" cost of rebuilding filters is included in the timing, but the study does not claim universal performance advantages across all hardware or data distributions.

In summary, the paper provides a rigorous framework for ensuring that historical geospatial decisions remain auditable and semantically distinct from current interpretations, offering a provably complete method to identify which records require re-evaluation when contexts evolve.