Geometry as a Blockchain Invariant: How We Run SAT Collision Detection On-Chain
Computational geometry is the last thing you'd put inside a smart contract. It's complex, it's expensive, and conventional wisdom says handle it off-chain: run the collision check in your backend, then submit a transaction only if it passes. Keep the chain lean. Keep the math elsewhere.
merca.earth does the opposite. The Separating Axis Theorem — a full convex-polygon collision algorithm — runs inside every parcel registration. On-chain. In integer arithmetic. Without floating-point.
This isn't a performance stunt. It's the only way to make the non-overlap guarantee unconditional. Here's why.
The problem with off-chain checks is a race condition, and it's not subtle.
User A draws a shape. The app queries the current state of the map: no overlap. A signs a transaction and submits it. Meanwhile, User B draws a shape that overlaps A's. B's app also queries the map: still no overlap, because A's transaction hasn't landed yet. B signs and submits.
B's transaction lands first. A's lands second. Now two parcels overlap. The protocol guarantee is broken — not by a bug, not by a malicious actor, but by the ordinary latency between a read and a write.
This isn't a theoretical edge case. It's the default behavior of any system that separates the check from the insert. The gap between "check passes" and "parcel inserted" is where invariants collapse. You can't fix it with locks, queues, or retry logic — those are mitigations, not solutions. The only real fix is atomic execution: run the check and the insert in the same transaction, with no window between them.
Sui's transaction model makes this possible — a transaction either fully succeeds or fully reverts, with no partial states. The overlap check and the insertion are a single indivisible operation. Either both happen, or neither does.
Three phases keep the on-chain SAT calls cheap.
First, a spatial index narrows all parcels down to nearby candidates — the broadphase. It queries only the cells that intersect the new parcel's bounding box, pruning the search space from every parcel on the map down to a small neighborhood. Second, bounding-box comparison discards anything whose bounding boxes don't touch — the midphase. Third, SAT runs only on the survivors — the narrowphase, typically a handful of polygons, not thousands.
Each phase eliminates 99%+ of candidates before the next. SAT's cost scales with surviving candidates, not with total map size. A map with a million parcels doesn't make registration slower — only the local neighborhood matters.
SAT itself is straightforward: for two convex shapes, if you can find any axis where their projections don't overlap, the shapes don't overlap. Check every edge normal as a candidate axis — there are at most as many as there are edges. If no axis separates them, they intersect. The algorithm is exact — no tolerance, no epsilon, no rounding. Two shapes that share only a boundary edge are not overlapping; two shapes that share any positive area are. The integer arithmetic makes that distinction precise.
But Move, the smart contract language merca.earth is written in, has no native signed integers. SAT requires them: edge normals point in any direction, projections can be negative. The protocol solves this with a custom type.
The Signed struct, from onchain/protocol/sources/math/signed.move, represents every signed value in the SAT pipeline:
// onchain/protocol/sources/math/signed.move, lines 17-22
/// A signed integer represented as magnitude + sign.
/// All cross-products and SAT projections use this type.
public struct Signed has copy, drop, store {
magnitude: u128,
negative: bool,
}
Every dot product, every projection, every signed comparison flows through this struct. The u128 magnitude gives enough headroom for coordinate multiplications without overflow — coordinates are stored at micrometer precision (1 unit = 1 micrometer), so products can reach 64-bit × 64-bit before the u128 ceiling.
With signed arithmetic in place, the SAT loop itself is direct. The has_separating_axis function, from onchain/protocol/sources/geometry/sat.move, iterates every edge of one polygon, computes the perpendicular axis for that edge, projects both polygons onto it, and checks whether the projections gap:
// onchain/protocol/sources/geometry/sat.move, lines 167-210
fun has_separating_axis(
edge_xs: &vector<u64>,
edge_ys: &vector<u64>,
xs_a: &vector<u64>,
ys_a: &vector<u64>,
xs_b: &vector<u64>,
ys_b: &vector<u64>,
): bool {
let n = vector::length(edge_xs);
let mut i = 0;
while (i < n) {
let next = if (i + 1 < n) { i + 1 } else { 0 };
let axis = perp_axis(
*vector::borrow(edge_xs, i),
*vector::borrow(edge_ys, i),
*vector::borrow(edge_xs, next),
*vector::borrow(edge_ys, next),
);
// Fail-closed: a zero axis means degenerate geometry slipped past upstream
// edge-length validation. Abort instead of silently skipping.
assert!(axis.dx != 0 || axis.dy != 0, EZeroAxis);
{
let (min_a, max_a) = project(xs_a, ys_a, &axis);
let (min_b, max_b) = project(xs_b, ys_b, &axis);
if (
!projections_overlap(
&min_a,
&max_a,
&min_b,
&max_b,
)
) {
return true
};
};
i = i + 1;
};
false
}
The function returns true the moment it finds a separating axis — short-circuiting as soon as the shapes are proven disjoint. If it exhausts all edges without finding one, the shapes overlap. sat_intersect_parts calls this twice: once with A's edges, once with B's. Both checks must fail to confirm overlap.
Geometry isn't a feature here. It's an invariant.
A digital signature proves authorship without a trusted third party. The on-chain collision check proves non-overlap the same way — without arbitration, without governance, without an oracle that could be wrong or slow. No committee resolves a boundary dispute after the fact. The protocol settled the boundary before the parcel was recorded.
This matters for what the map actually is. Every parcel on merca.earth is a claim that has been tested against every neighboring claim, in the same block it was registered. The record isn't just a list of shapes — it's a list of shapes that have been proven not to conflict. That proof is baked into the history of the chain, not stored in a database that could be rolled back or overwritten.
That's what it means for geometry to be a blockchain invariant: the check and the record are the same operation, in the same block, with no gap between them. The map is readable because every claim on it has been tested against every other claim, atomically, at the moment it was made.