Enclave-Side Spatial Joins with Sealed Data

The reason to put a spatial join inside an enclave is throughput: tens of millions of points joined in minutes, against hours for the equivalent secure-computation protocol. The reason it is hard is that an enclave has a small protected memory region, so a real join must stream through it in chunks, and every chunk of intermediate state that spills outside must be sealed — encrypted to a key the enclave alone can derive. Getting the sealing policy wrong is how a deployment ends up with plaintext intermediates on disk after all. This page implements the streaming join and its sealing, under trusted execution for spatial workloads in Secure Multi-Party Computation in Spatial Analytics.

Parameter Configuration and Calibration

  • chunk_points — how many points enter protected memory at once. Size it from the enclave’s usable protected memory minus the index, with headroom. Too large and the platform pages protected memory to disk, which is encrypted but slow and leaks access patterns; too small and the join becomes dominated by chunk-boundary handling.
  • seal_policy — measurement-bound or signer-bound. Sealing to the measurement means only this exact enclave build can unseal, which is what you want for intermediates. Sealing to the signer lets a future build unseal, which is what you want for long-lived state that must survive upgrades — and which is a much weaker guarantee.
  • grid_resolution — the join key. A spatial join inside an enclave is still a join on a grid cell, and the resolution decides both the candidate set size and the disclosure of the output. Use the same resolution the release will be published at, so no finer intermediate ever exists.
  • dp_epsilon — applied inside the enclave, before anything leaves. The enclave’s advantage over a trusted server is that noise can be added within the protected region, so even the host never observes the exact aggregate.
Intermediate Where it lives Sealed to If it leaks
Input chunk protected memory n/a host sees ciphertext only
Cell index protected memory n/a —
Partial counts spilled to disk measurement exact per-cell counts
Final aggregate released n/a noised, thresholded
Chunk size against protected-memory pressure A grouped bar chart across five chunk sizes. Working-set size grows linearly with the chunk. Time spent paging protected memory is zero until the working set approaches the enclave's usable region, then rises sharply — ninety-one percent at a two-million-point chunk, at which point throughput collapses and access patterns leak through page faults. Chunk size against protected-memory pressure 48 bytes per point; the enclave's usable region is ~90 MB 0 50 100 MB / % 0 0 10k 2 0 50k 5 0 100k 24 34 500k 96 91 2000k working set (MB) % of time paging
A join that fits is worth far more than one that is theoretically faster. Size the chunk below the paging cliff and stream.

Reference Implementation

python
from __future__ import annotations

import hashlib
import hmac
import math
import random
from dataclasses import dataclass, field
from typing import Iterable, Iterator, Mapping, Sequence


class SealingError(RuntimeError):
    """Raised when sealed state cannot be opened by this enclave build."""


@dataclass(frozen=True)
class SealPolicy:
    """Which enclave identity may unseal a blob."""

    measurement: str
    platform_secret: bytes
    bind_to_measurement: bool = True

    def key(self) -> bytes:
        material = self.platform_secret + (
            self.measurement.encode() if self.bind_to_measurement else b"signer"
        )
        return hashlib.blake2b(material, digest_size=32).digest()

    def seal(self, blob: bytes) -> bytes:
        k = self.key()
        stream = hashlib.blake2b(k, digest_size=len(blob)).digest()
        tag = hmac.new(k, blob, hashlib.sha256).digest()
        return tag + bytes(a ^ b for a, b in zip(blob, stream))

    def unseal(self, sealed: bytes) -> bytes:
        k = self.key()
        tag, body = sealed[:32], sealed[32:]
        stream = hashlib.blake2b(k, digest_size=len(body)).digest()
        blob = bytes(a ^ b for a, b in zip(body, stream))
        if not hmac.compare_digest(tag, hmac.new(k, blob, hashlib.sha256).digest()):
            raise SealingError(
                "sealed state does not open under this enclave identity — "
                "either the build changed or the blob was written by another enclave"
            )
        return blob


@dataclass
class StreamingJoin:
    """Join a stream of points against a cell-indexed polygon set, in chunks.

    Only `chunk_points` points are inside protected memory at any moment; partial
    results are sealed before they leave. The invariant that matters: no plaintext
    intermediate ever exists outside the enclave, including in a crash dump.
    """

    polygons_by_cell: Mapping[str, str]
    seal: SealPolicy
    chunk_points: int = 100_000
    _counts: dict[str, int] = field(default_factory=dict)

    def _process(self, chunk: Sequence[tuple[str, float, float]]) -> None:
        for cell, _x, _y in chunk:
            polygon = self.polygons_by_cell.get(cell)
            if polygon is None:
                continue
            self._counts[polygon] = self._counts.get(polygon, 0) + 1

    def run(self, points: Iterable[tuple[str, float, float]]) -> bytes:
        """Consume the stream and return the SEALED partial counts."""
        chunk: list[tuple[str, float, float]] = []
        for point in points:
            chunk.append(point)
            if len(chunk) >= self.chunk_points:
                self._process(chunk)
                chunk.clear()
        if chunk:
            self._process(chunk)
        payload = ";".join(f"{k}={v}" for k, v in sorted(self._counts.items())).encode()
        return self.seal.seal(payload)

    def release(
        self, sealed: bytes, *, epsilon: float, min_count: int, seed: int = 0
    ) -> dict[str, float]:
        """Unseal, add noise INSIDE the enclave, threshold, and release.

        Noise is applied before the result crosses the enclave boundary, so the host
        never observes the exact aggregate — the property a merely-trusted server
        cannot offer.
        """
        payload = self.seal.unseal(sealed).decode()
        rng = random.Random(seed)
        out: dict[str, float] = {}
        for item in filter(None, payload.split(";")):
            key, raw = item.split("=")
            count = int(raw)
            if count < min_count:
                continue
            u = rng.random() - 0.5
            noise = -(1.0 / epsilon) * math.copysign(1.0, u) * math.log1p(-2 * abs(u))
            out[key] = max(0.0, count + noise)
        return out

Validation Checkpoint

python
def _validate() -> None:
    polygons = {f"cell{i}": f"zone{i % 4}" for i in range(64)}
    policy = SealPolicy(measurement="build-4.2.1", platform_secret=b"platform")

    join = StreamingJoin(polygons_by_cell=polygons, seal=policy, chunk_points=1_000)
    rng = random.Random(3)
    points = [(f"cell{rng.randrange(64)}", 0.0, 0.0) for _ in range(50_000)]
    sealed = join.run(points)

    # 1. The sealed blob must not contain the plaintext counts.
    assert b"zone0=" not in sealed

    # 2. The same enclave build can unseal and release.
    released = join.release(sealed, epsilon=1.0, min_count=5)
    assert set(released) <= {"zone0", "zone1", "zone2", "zone3"}
    for zone, value in released.items():
        assert abs(value - 12_500) < 400, (zone, value)

    # 3. A DIFFERENT build must not be able to unseal measurement-bound state.
    upgraded = SealPolicy(measurement="build-4.3.0", platform_secret=b"platform")
    other = StreamingJoin(polygons_by_cell=polygons, seal=upgraded)
    try:
        other.release(sealed, epsilon=1.0, min_count=5)
    except SealingError:
        pass
    else:
        raise AssertionError("measurement-bound sealing must exclude other builds")

    # 4. Signer-bound sealing DOES survive an upgrade — weaker, and sometimes needed.
    signer_policy = SealPolicy("build-4.2.1", b"platform", bind_to_measurement=False)
    signer_join = StreamingJoin(polygons_by_cell=polygons, seal=signer_policy,
                                chunk_points=1_000)
    signer_sealed = signer_join.run(points)
    successor = StreamingJoin(
        polygons_by_cell=polygons,
        seal=SealPolicy("build-4.3.0", b"platform", bind_to_measurement=False),
    )
    assert successor.release(signer_sealed, epsilon=1.0, min_count=5)

    # 5. Chunking must not change the result.
    big = StreamingJoin(polygons_by_cell=polygons, seal=policy, chunk_points=50_000)
    assert big.run(points) == sealed

    # 6. Small zones must be suppressed before noise, not after.
    tiny = StreamingJoin(polygons_by_cell={"cellX": "zoneRare"}, seal=policy)
    rare = tiny.run([("cellX", 0.0, 0.0)] * 3)
    assert tiny.release(rare, epsilon=1.0, min_count=5) == {}

    print("enclave-side join: all assertions passed")


_validate()
The sealing policy is a security decision, not an operational one A two-row comparison of sealing policies. Binding sealed state to the code measurement means no other build can read it, including a legitimate upgrade — the right choice for short-lived intermediates. Binding to the signer lets any future build the same key signs read the state, which is convenient for long-lived state and a materially weaker guarantee. The sealing policy is a security decision, not an operational one the convenient option is the weaker one survives an upgrade readable by a future build use for Bind to measurement no no short-lived intermediates Bind to signer yes yes — any build it signs long-lived state
Default to measurement-bound sealing and design intermediates to be recomputable. Signer-bound sealing is a deliberate weakening, and should be documented as one.

Assertion 5 is worth keeping because chunk-boundary bugs are the characteristic defect of streaming joins, and they produce results that are nearly right — a few thousand points double-counted or dropped at boundaries, which no aggregate-level check will notice.

Incident Response and Edge Cases

  • The enclave runs out of protected memory mid-join. The platform pages, and throughput collapses while access-pattern leakage rises. Reduce chunk_points and re-measure; a join that fits is worth more than a join that is theoretically faster.
  • Sealed state cannot be opened after a deploy. Expected under measurement-bound sealing, and it is the correct behaviour. Design the pipeline so intermediates are short-lived and recomputable; if state must survive upgrades, seal to the signer and document the weaker guarantee.
  • A crash dump appears on the host. Enclave memory should not be dumpable, but the untrusted host process around it is. Audit what the host-side wrapper holds — buffers of ciphertext are fine, a convenience copy of decrypted input is not.
  • Two data owners disagree about the join resolution. The finer resolution wins the accuracy argument and loses the disclosure one. Resolve it before the enclave is built, because the resolution is part of the measured code and changing it invalidates every approval.
  • Results differ between runs. Either the noise seed is not fixed for a reproducible release, or chunking is non-deterministic. Both are fixable; the second is a correctness bug and should fail assertion 5 in CI.
Where an enclave join's time goes A stacked bar chart of enclave join stage timings at one and ten million points. The join itself dominates at both sizes, and index construction is the second cost. Differential-privacy noise and output encryption are negligible in both cases, which is worth knowing: the privacy steps are not what makes this expensive. Where an enclave join's time goes same code, two dataset sizes 0 50 100 seconds 8.8 s 1M points 114 s 10M points decrypt index build join DP noise encrypt out
The DP step is a rounding error in the runtime. Nothing about adding the noise inside the enclave is expensive — which removes the usual excuse for adding it outside.

Frequently Asked Questions

Why seal intermediates at all if the enclave is trusted?

Because intermediates leave the enclave. Protected memory is small, so a real join spills partial state to ordinary storage the host controls. Sealing is what keeps that state confidential; without it, the join's inputs are effectively on disk in the clear, one chunk at a time.

Should sealing bind to the measurement or the signer?

The measurement, for anything short-lived — it guarantees only this reviewed build can reopen the state. Bind to the signer only for state that must survive upgrades, and treat that as a deliberate weakening: any future build the same key signs can read it.

Does the enclave remove the need for a minimum-count threshold?

No. Confidentiality of the inputs says nothing about what the outputs reveal. A zone visited by three people is a disclosure whether the join ran on a laptop or in an enclave, so the suppression threshold and the noise both still apply — and both belong inside the measured code.

How large a join is realistic inside an enclave?

Tens of millions of points is routine when the work is streamed in chunks that fit protected memory, because the per-point work is native-speed. The limiting factor is rarely total data size; it is whether the index and the working set fit without paging.

Up one level: Trusted Execution for Spatial Workloads · Section: Secure Multi-Party Computation in Spatial Analytics.