TRIP: Trajectory-based Recognition of Identity Proof

1.1. Requirements Language

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.¶

1.2. Terminology

Breadcrumb

A single, signed attestation of spatiotemporal presence. The atomic unit of the TRIP protocol.¶

Trajectory

An ordered, append-only chain of breadcrumbs produced by a single identity key pair.¶

Epoch

A batch of consecutive breadcrumbs whose aggregate integrity is attested by a Merkle root and a signature.¶

Trajectory Identity Token (TIT)

A 16-byte identifier derived from the public key and genesis breadcrumb, used as a persistent pseudonym.¶

H3 Cell

A hexagonal cell identifier from the H3 geospatial indexing system, used as the privacy-preserving spatial coordinate in breadcrumbs.¶

Context Digest

A SHA-256 hash of ambient environmental signals (Wi-Fi BSSIDs, cell tower IDs, IMU readings) that provides corroborating evidence for a breadcrumb's claimed location without revealing the raw signals.¶

Trust Score

A numerical value reflecting the spatiotemporal diversity and longevity of a trajectory, computed according to a defined trust function.¶

2.1. Identity Model

A TRIP identity is an Ed25519 key pair. The 32-byte public key is the identity. There is no registration authority; any entity capable of generating a valid Ed25519 key pair MAY participate in the protocol. The private key MUST be stored in a secure enclave or hardware-backed keystore and MUST NOT leave the originating device.¶

A single physical entity MAY maintain multiple TRIP identities. The protocol makes no attempt to link multiple identities to a single entity; such linkage is explicitly a non-goal.¶

3.1. Data Structure

A breadcrumb is a fixed-schema record consisting of the following fields, serialized as a CBOR [RFC8949] map with integer keys:¶

The canonical CBOR encoding of fields 1 through 8 (inclusive), sorted by CBOR label in ascending integer order, constitutes the "signable payload." The signature in field 9 is an Ed25519 signature over this signable payload.¶

3.2. Breadcrumb Hash

The breadcrumb hash is the SHA-256 digest of the complete canonical CBOR encoding of the breadcrumb (fields 1 through 9 inclusive). This hash serves as the chain link: the "previous" field (label 7) of breadcrumb N+1 MUST contain the breadcrumb hash of breadcrumb N.¶

   BreadcrumbHash(B) = SHA-256(CBOR-Canonical(B[1..9]))
   B[N+1].previous   = BreadcrumbHash(B[N])
   B[0].previous     = null

3.3. Spatial Quantization

Raw geographic coordinates (latitude, longitude) MUST NOT appear in any breadcrumb or in any message transmitted by a TRIP implementation. All spatial data MUST be quantized to an H3 cell index before storage or transmission.¶

The H3 geospatial indexing system [H3] partitions the Earth's surface into a hierarchy of hexagonal cells at 16 resolution levels (0-15). The resolution determines the trade-off between location privacy and spatial precision:¶

Implementations SHOULD default to resolution 10. Implementations MUST support resolutions 7 through 12 inclusive. A verifier MAY accept breadcrumbs at resolutions outside this range but SHOULD apply reduced trust weight.¶

3.4. Context Digest Construction

The context digest provides corroborating environmental evidence for a claimed location without disclosing the raw sensor data. It is constructed as follows:¶

1. Collect available ambient signals: Wi-Fi BSSIDs, cellular tower identifiers, and inertial measurement unit (IMU) readings.¶

2. Construct a pipe-delimited string of tagged components in the following order:¶

   • "h3:" followed by the H3 cell hex string¶
   • "ts:" followed by the timestamp bucketed to 5-minute intervals (Unix minutes / 5 * 5)¶
   • "wifi:" followed by the first 16 hex characters of SHA-256(sorted comma-joined BSSIDs), if available¶
   • "cell:" followed by the first 16 hex characters of SHA-256(sorted comma-joined tower IDs), if available¶
   • "imu:" followed by the first 16 hex characters of SHA-256(IMU vector string), if available¶
3. Compute SHA-256 of the resulting pipe-delimited string.¶

   input  = "h3:8a2a1072b59ffff|ts:29145660|wifi:a3b2c1d4e5f67890"
   digest = SHA-256(input)

If no ambient signals are available, the context digest MUST still be computed from the h3 and ts components alone. A verifier SHOULD assign higher trust weight to breadcrumbs with richer context digests.¶

3.5. Genesis Breadcrumb

The first breadcrumb in a trajectory (index 0) is the genesis breadcrumb. Its "previous" field MUST be null (CBOR simple value 22). The genesis breadcrumb establishes the binding between an Ed25519 public key and its trajectory chain.¶

3.6. Velocity Plausibility

Before accepting a breadcrumb, a verifier SHOULD check that the implied velocity between consecutive breadcrumbs does not exceed a configurable maximum. The implied velocity is computed using the Haversine distance [HAVERSINE] between the H3 cell centers divided by the time difference.¶

The following entity speed classes are RECOMMENDED:¶

An entity class tag MAY be included in the meta field (CBOR label 8) under key "entity_class". Verifiers SHOULD reject breadcrumbs that exceed the maximum speed for the declared entity class. If no entity class is declared, verifiers SHOULD apply the "human" speed limit.¶

3.7. Location Deduplication

A conforming producer MUST NOT emit a breadcrumb whose H3 cell is identical to the H3 cell of the immediately preceding breadcrumb in the same trajectory. This constraint enforces the core principle that trajectory identity requires physical movement. Implementations SHOULD additionally enforce a minimum geographic distance (RECOMMENDED: 50 meters) between consecutive breadcrumbs.¶

5.1. Data Structure

An epoch aggregates a contiguous range of breadcrumbs into a single verifiable unit. Epochs enable efficient verification: a verifier can check the epoch Merkle root and signature without examining every individual breadcrumb.¶

5.2. Merkle Tree Construction

The Merkle tree is a binary tree constructed from the breadcrumb hashes within the epoch. Leaves are the SHA-256 hashes of individual breadcrumbs. Internal nodes are computed as SHA-256(left_child || right_child). If the number of leaves is odd, the last leaf is duplicated.¶

                     MerkleRoot
                    /          \
               H(AB)            H(CD)
              /     \          /     \
          H(B0)   H(B1)   H(B2)   H(B3)

where H(Bn) = BreadcrumbHash(breadcrumb_n) and H(AB) = SHA-256(H(B0) || H(B1)).¶

5.3. Bundling Rules

A producer SHOULD bundle an epoch when the number of unbundled breadcrumbs reaches or exceeds 100. Implementations MAY use a different threshold but MUST NOT create epochs with fewer than 10 breadcrumbs (except for the final epoch if the trajectory is being closed).¶

Epochs MUST be sequential and contiguous: epoch N+1 MUST begin at the breadcrumb immediately following the last breadcrumb of epoch N. No breadcrumb may belong to more than one epoch, and no breadcrumb may be omitted from an epoch.¶

6.1. Trust Model Overview

TRIP trust reflects the difficulty of fabricating a trajectory. A trajectory that visits many distinct spatial cells over a long duration is harder to fake than one confined to a small area or short time span. The trust model quantifies this intuition through three components: trajectory density, spatial diversity, and temporal decay.¶

6.2. Trust Score Function

The trust score T for a trajectory is computed using a Parisi percolation model [PARISI]:¶

   T = D(t) * S * k_percolation

   where:

   D(t) = exp(-(t - t_last)^2 / (2 * tau^2))
          Gaussian temporal decay function
          t       = current time
          t_last  = timestamp of most recent breadcrumb
          tau     = decay half-life (RECOMMENDED: 30 days)

   S     = unique_cells / total_breadcrumbs
           Spatial diversity ratio (0.0 to 1.0)
           unique_cells = count of distinct H3 cells visited

   k_percolation = min(breadcrumb_count / 100.0, k_max)
                   Parisi percolation factor [PARISI]
                   k_max = 7 (RECOMMENDED)

A verifier MAY apply additional weighting factors (e.g., context digest richness, geographic spread) but MUST compute at least the base trust score defined above for interoperability.¶

6.3. Trust Thresholds

TRIP does not mandate specific trust thresholds for application-level decisions. However, the following reference thresholds are RECOMMENDED for interoperability:¶

7.1. Breadcrumb Verification

A verifier MUST perform the following checks on each breadcrumb, in order:¶

1. Decode the CBOR payload and verify that all mandatory fields (labels 1-7, 9) are present.¶
2. Verify that the identity field (label 2) is a valid 32-byte Ed25519 public key.¶
3. Reconstruct the signable payload from fields 1-8 in canonical CBOR encoding.¶
4. Verify the Ed25519 signature (label 9) against the signable payload using the identity public key.¶
5. If index > 0, verify that the "previous" field (label 7) matches the hash of the preceding breadcrumb.¶
6. If index == 0, verify that the "previous" field is null.¶
7. Verify that the timestamp is not in the future (with a tolerance of RECOMMENDED 5 minutes for clock skew).¶
8. OPTIONAL: Verify velocity plausibility relative to the preceding breadcrumb (Section 3.6).¶

7.2. Epoch Verification

A verifier MUST perform the following checks on each epoch:¶

1. Verify the Ed25519 signature over fields 1-9.¶
2. Reconstruct the Merkle tree from the constituent breadcrumb hashes and verify it matches the declared merkle_root.¶
3. Verify that start_index and end_index define a contiguous range.¶
4. Verify that count == end_index - start_index + 1.¶
5. If epoch_index > 0, verify that previous_epoch matches the hash of the preceding epoch.¶

7.3. TIT Verification

To verify a claimed TIT, a verifier MUST:¶

1. Obtain the claimant's Ed25519 public key and genesis breadcrumb.¶
2. Verify the genesis breadcrumb per Section 7.1.¶
3. Compute the TIT per Section 4 and compare with the claimed value.¶

8.1. CDDL Schema

The following CDDL [RFC8610] defines the TRIP data structures:¶

; TRIP Protocol CDDL Schema

breadcrumb = {
  1 => uint,                ; index
  2 => bstr .size 32,       ; identity (Ed25519 public key)
  3 => #6.1(number),        ; timestamp (epoch seconds)
  4 => uint,                ; cell (H3 index)
  5 => uint .le 15,         ; resolution (0-15)
  6 => bstr .size 32,       ; context digest (SHA-256)
  7 => bstr .size 32 / nil, ; previous hash or null
  ? 8 => meta-map,          ; optional metadata
  9 => bstr .size 64,       ; signature (Ed25519)
}

meta-map = {
  ? "battery"      => uint .le 100,
  ? "accuracy"     => float,
  ? "network"      => tstr,
  ? "entity_class" => entity-class,
  ? "manual"       => bool,
  * tstr => any,
}

entity-class = "human" / "vehicle" / "drone" / "anchor"

epoch = {
  1  => uint,                ; epoch_index
  2  => bstr .size 32,       ; identity
  3  => #6.1(number),        ; start_time
  4  => #6.1(number),        ; end_time
  5  => uint,                ; start_index
  6  => uint,                ; end_index
  7  => bstr .size 32,       ; merkle_root
  8  => uint,                ; count
  9  => bstr .size 32 / nil, ; previous_epoch hash or null
  10 => bstr .size 64,       ; signature
}

trajectory-identity-token = bstr .size 16

9.1. Threat Model

TRIP assumes the following threat model:¶

• Private key security: The Ed25519 private key is assumed to be held in a secure enclave. If the private key is compromised, the attacker can produce valid breadcrumbs. Key compromise is outside the scope of TRIP; key management and revocation are higher-layer concerns.¶
• GPS spoofing: An attacker with a software-defined radio can spoof GPS signals in a localized area. The context digest (Section 3.4) mitigates this by incorporating Wi-Fi BSSID and cellular tower data that are independent of GPS. Spoofing all signal sources simultaneously at diverse locations is significantly harder.¶
• Virtual environment: An attacker running the TRIP client in an emulator can feed arbitrary location data. The velocity plausibility check (Section 3.6) and the requirement for sustained diversity over time make this attack progressively more expensive.¶
• Colocation attack: Two colluding devices can generate breadcrumbs at the same locations, but each device produces an independent trajectory under its own key. Cross-trajectory correlation is a verifier-side heuristic and is outside the scope of this specification.¶

9.2. Cryptographic Agility

This specification mandates Ed25519 for signatures and SHA-256 for hashing. Future versions of TRIP MAY introduce algorithm negotiation. Implementations SHOULD be designed to allow algorithm substitution without protocol-level changes.¶

9.3. Replay Protection

The monotonically increasing index and the chaining via the "previous" hash field provide replay protection within a single trajectory. A replayed breadcrumb will fail the chain integrity check. Cross-trajectory replay (using breadcrumbs from identity A in a trajectory of identity B) will fail signature verification.¶

9.4. Denial of Service

An attacker can generate large numbers of breadcrumbs to consume verifier resources. Verifiers SHOULD rate-limit breadcrumb submission per identity and MAY require a minimum trust score before accepting further breadcrumbs for resource-intensive operations.¶

10.1. Location Privacy

TRIP's primary privacy mechanism is H3 quantization. By design, a breadcrumb reveals only that the producer was within a hexagonal cell of known area--not the precise GPS coordinates. At the default resolution 10, each cell covers approximately 15,000 square meters (0.015 km2), providing meaningful location privacy in urban environments.¶

Implementations MUST NOT store raw GPS coordinates after H3 quantization. Implementations SHOULD provide users with the ability to choose their preferred resolution level, understanding that lower resolutions (larger cells) provide more privacy at the cost of reduced trust accumulation rate.¶

10.2. Trajectory Correlation

A trajectory is intrinsically linkable: all breadcrumbs share the same identity key. This is by design, as trust accumulation requires identity continuity. However, a user who desires unlinkability across contexts MAY maintain separate TRIP identities (key pairs) for separate contexts.¶

Verifiers SHOULD disclose their data retention policies. Breadcrumbs presented for verification need not be stored by the verifier after trust computation.¶

10.3. Context Digest Privacy

The context digest is a one-way hash. Wi-Fi BSSIDs, cell tower IDs, and IMU readings cannot be recovered from the digest. However, an attacker who knows the Wi-Fi environment at a specific location and time could reconstruct the digest and confirm the producer's presence. This is a known acceptable trade-off: the digest provides corroboration, not concealment.¶

B.1. Why H3 Over Other Geospatial Systems

The H3 system was selected over alternatives (S2, Geohash, Plus Codes) for several reasons: uniform cell area at each resolution level (hexagons tile more evenly than rectangles), hierarchical parent-child relationships enabling multi-resolution disclosure, efficient neighbor computation for velocity checking, and open-source availability with well-maintained libraries across platforms.¶

B.2. Why CBOR Over JSON

CBOR provides deterministic encoding essential for reproducible signature computation, compact binary representation suitable for constrained devices and bandwidth-limited networks, and native byte string support for cryptographic material. JSON remains useful for debugging and human-readable interchange but lacks deterministic encoding rules.¶

B.3. Why Trajectory Over Biometrics

Biometric systems capture immutable characteristics (fingerprints, iris, face). Once compromised, the credential cannot be rotated. Biometric databases are high-value targets. Deepfake technology increasingly undermines facial recognition. In contrast, a trajectory is: continuously renewable (new movement generates new evidence), inherently distributed (no central biometric database), resistant to digital fabrication (requires physical presence in the real world), and privacy- preserving by design (quantized spatial cells, not raw coordinates).¶