Spatial Discretization for Fine-Grain Zone Checks with STARKs

Abstract

Many location-based services rely on a point-in-polygon test ( PiP ), checking whether a point or a trajectory lies inside a geographic zone. Since geometric operations are expensive in zero-knowledge proofs, privately performing the PiP test is challenging. In this paper, we answer the research questions of how different ways of encoding zones affect accuracy and proof cost by exploiting grid-based lookup tables under a fixed STARK execution model. Beyond a Boolean grid-based baseline that marks cells as in- or outside, we explore a distance-aware encoding approach that stores how far each cell is from a zone boundary and uses interpolation to reason within a cell. % Our experiments on real-world data demonstrate that the proposed distance-aware approach achieves higher accuracy on coarse grids with only a moderate verification overhead, making zone encoding the key lever for efficient zero-knowledge spatial checks. Our experiments on real-world data demonstrate that the proposed distance-aware approach achieves higher accuracy on coarse grids (max. % 60%p 60%p accuracy gain) with only a moderate verification overhead (approximately 1.4×), making zone encoding the key lever for efficient zero-knowledge spatial checks.