Presence-Privacy-Protocol

1. Terminology

2. Identity Model

2.1 Key Generation

Each user generates an Ed25519 key pair on first launch:

seed       = randombytes(32)
(pk, sk)   = crypto_sign_ed25519_seed_keypair(seed)

• pk (32 bytes): the user's public identity, used as their protocol address.
• sk (64 bytes): stored in platform-secure storage (Keychain on iOS, Keystore on Android).
• seed (32 bytes): the backup/recovery secret. Users SHOULD be prompted to back up their seed phrase (BIP-39 mnemonic or raw hex).

2.2 Key Conversion

Ed25519 keys are converted to X25519 for Diffie-Hellman key exchange:

x25519_pk  = crypto_sign_ed25519_pk_to_curve25519(ed25519_pk)
x25519_sk  = crypto_sign_ed25519_sk_to_curve25519(ed25519_sk)

This allows a single key pair to serve both signing (Ed25519) and encryption (X25519) purposes.

2.3 Key Rotation

A key rotation event is signed by the old key and contains the new public key:

KeyRotation {
  old_pubkey:  bytes32       // signing key (== author)
  new_pubkey:  bytes32       // replacement key
  timestamp:   uint64
  signature:   bytes64       // sign(new_pubkey || timestamp, old_sk)
}

Recipients who receive and verify this event update their local contact mapping. The relay MAY store key rotation events for a configurable retention period to allow offline recipients to catch up.

3. Crypto Layer

All cryptographic operations use libsodium primitives. Implementations on platforms without libsodium MUST use compatible algorithms (X25519, XChaCha20-Poly1305, Ed25519) from equivalent libraries (e.g., TweetNaCl).

3.1 Symmetric Encryption

Algorithm:   XChaCha20-Poly1305 (AEAD)
Nonce:       24 bytes, randomly generated per encryption
Key:         32 bytes
Auth tag:    16 bytes (appended to ciphertext by libsodium)

encrypt(plaintext, nonce, key) -> ciphertext || tag
decrypt(ciphertext || tag, nonce, key) -> plaintext | error

libsodium function: crypto_aead_xchacha20poly1305_ietf_encrypt/decrypt

3.2 Key Exchange

Algorithm:   X25519 Diffie-Hellman
Output:      32-byte shared secret

shared_secret = crypto_scalarmult(my_x25519_sk, their_x25519_pk)

The shared secret is passed through a KDF before use as an encryption key:

encryption_key = crypto_generichash(
    32,                        // output length
    shared_secret,             // input
    "ppp-event-key-v1"         // context/salt
)

3.3 Gift Wrap Pattern

The Gift Wrap pattern uses three layers to hide both content and sender identity from the relay. This is the REQUIRED encryption method for all events.

Layer 1 — Rumor (cleartext content):

The rumor is the actual event payload. It is NOT signed, providing sender deniability at the content layer.

Rumor {
  sender:       bytes32          // author's real Ed25519 pubkey
  kind:         uint8            // event type (see S4)
  content:      EventContent     // type-specific payload
  created_at:   uint64           // unix timestamp
}

Layer 2 — Seal (encrypted + signed by sender):

The seal encrypts the rumor with a shared secret derived from an ephemeral key and the recipient's key. It proves authorship to the recipient.

ephemeral_seal  = crypto_sign_ed25519_seed_keypair(randombytes(32))
seal_shared     = crypto_scalarmult(
                    ephemeral_seal.x25519_sk,
                    recipient.x25519_pk)
seal_key        = kdf(seal_shared, "ppp-seal-v1")
seal_nonce      = randombytes(24)
sealed_rumor    = encrypt(serialize(rumor), seal_nonce, seal_key)

Seal {
  ephemeral_pk:   bytes32        // ephemeral_seal.ed25519_pk
  nonce:          bytes24
  ciphertext:     bytes          // sealed_rumor
  sender_sig:     bytes64        // sign(sealed_rumor, sender.ed25519_sk)
}

The signature binds the sender's identity to the sealed content. The recipient verifies sender_sig using rumor.sender (available after decrypting the seal).

Layer 3 — Gift Wrap (encrypted with ephemeral key):

The wrap encrypts the seal with a SECOND ephemeral key pair. The relay sees only this outer layer.

ephemeral_wrap  = crypto_sign_ed25519_seed_keypair(randombytes(32))
wrap_shared     = crypto_scalarmult(
                    ephemeral_wrap.x25519_sk,
                    recipient.x25519_pk)
wrap_key        = kdf(wrap_shared, "ppp-wrap-v1")
wrap_nonce      = randombytes(24)
wrapped_seal    = encrypt(serialize(seal), wrap_nonce, wrap_key)

GiftWrap {
  recipient:      bytes32        // recipient's Ed25519 pubkey
  ephemeral_pk:   bytes32        // ephemeral_wrap.ed25519_pk
  nonce:          bytes24
  ciphertext:     bytes          // wrapped_seal
  created_at:     uint64         // relay-facing timestamp
  expires_at:     uint64         // event TTL
}

Decryption (recipient side):

1. wrap_shared = crypto_scalarmult(my_x25519_sk, giftwrap.ephemeral_pk)
2. wrap_key    = kdf(wrap_shared, "ppp-wrap-v1")
3. seal        = decrypt(giftwrap.ciphertext, giftwrap.nonce, wrap_key)
4. seal_shared = crypto_scalarmult(my_x25519_sk, seal.ephemeral_pk)
5. seal_key    = kdf(seal_shared, "ppp-seal-v1")
6. rumor       = decrypt(seal.ciphertext, seal.nonce, seal_key)
7. verify      = crypto_sign_verify(seal.sender_sig,
                   seal.ciphertext, rumor.sender)

What each party sees:

4. Event Format

4.1 Serialization

All protocol messages are serialized using MessagePack. Implementations for constrained devices MAY use CBOR as an alternative, provided field ordering and type mapping are preserved.

Field names are serialized as short integer keys to minimize payload size:

4.2 Event Kinds

4.3 Event Content by Kind

PRESENCE (0x01):

PresenceContent {
  event_id:     bytes16          // unique event identifier (UUID)
  message:      string           // user-visible message text
  region:       Region           // geographic area (see S4.4)
  time_window: {
    starts_at:  uint64           // unix timestamp
    ends_at:    uint64           // unix timestamp
    timezone:   string           // IANA timezone identifier
  }
  recipients:   [bytes32]        // list of recipient pubkeys
}

REVOKE (0x02):

RevokeContent {
  event_id:     bytes16          // ID of the event to revoke
}

KEY_ROTATION (0x04):

KeyRotationContent {
  new_pubkey:   bytes32          // the replacement public key
  migration_sig: bytes64         // sign(old_pk || new_pk, old_sk)
}

CARRY_GROUP_INVITE (0x06):

CarryGroupInviteContent {
  group_id:     bytes16          // carry group identifier
  group_name:   string           // human-readable name
  members:      [bytes32]        // current member pubkeys
  couriers:     [bytes32]        // designated courier pubkeys
}

4.4 Region Model

The region defines the geographic area where an event is discoverable. The protocol uses a circle as the baseline representation, with a version-extensible region_type field for future area representations.

4.4.1 Region Type 0: Circle (v0.1 baseline)

Region {
  region_type:  uint8 = 0        // 0 = circle
  latitude:     float64          // center latitude (WGS84)
  longitude:    float64          // center longitude (WGS84)
  radius_m:     uint32           // radius in meters [10 .. 50,000]
}

Wire overhead: 1 + 8 + 8 + 4 = 21 bytes.

Latitude MUST be in [-90, 90] and longitude MUST be in [-180, 180] (WGS84 decimal degrees).

Receiver-side presence check (haversine):

d = haversine(my_lat, my_lon, region.latitude, region.longitude)
is_inside = (d <= region.radius_m)

The haversine formula requires only basic trigonometry and is implementable in ~15 lines in any language, including J2ME CLDC 1.1.

4.4.2 Future Region Types (reserved)

Compatibility rule: Clients that encounter an unknown region_type MUST fall back to the bounding circle if present, or discard the event if no bounding circle is provided.

4.5 Event ID Derivation

event_id = crypto_generichash(
    32,
    serialize(giftwrap.ephemeral_pk
              || giftwrap.nonce
              || giftwrap.ciphertext)
)

This ensures uniqueness without revealing content or sender.

5. Relay Protocol

5.1 WebSocket Transport (Tier 1)

Connection endpoint: wss://<relay-host>/v1/ws

All WebSocket frames are MessagePack-encoded objects with a cmd field.

5.1.1 Authentication

On connection, the relay issues a challenge:

Relay -> Client:
{ cmd: "CHALLENGE", nonce: bytes32 }

Client -> Relay:
{ cmd: "AUTH", pubkey: bytes32, sig: bytes64 }
  where sig = crypto_sign_detached(nonce, client_ed25519_sk)

Relay -> Client:
{ cmd: "AUTH_OK" }
  or
{ cmd: "AUTH_FAIL", reason: string }

After AUTH_OK, all subsequent commands are scoped to the authenticated pubkey.

5.1.2 Commands

STORE — submit an event for delivery:

Client -> Relay:
{ cmd: "STORE", event: GiftWrap }

Relay -> Client:
{ cmd: "STORED", event_id: bytes32 }
  or
{ cmd: "STORE_FAIL", reason: string }

The relay validates: recipient pubkey is well-formed, event is not expired, event_id is not already stored. The relay does NOT need to decrypt the event.

FETCH — retrieve events for the authenticated pubkey:

Client -> Relay:
{ cmd: "FETCH", since: uint64 }

Relay -> Client:
{ cmd: "EVENTS", events: [GiftWrap] }

since is a unix timestamp; the relay returns events with created_at > since. The relay MAY paginate using a cursor field.

FETCH_CARRY — courier fetches for a carry group:

Client -> Relay:
{ cmd: "FETCH_CARRY", group_id: bytes16,
  since: uint64, sig: bytes64 }

Relay -> Client:
{ cmd: "CARRY_EVENTS", events: [GiftWrap] }

ACK — confirm receipt of events:

Client -> Relay:
{ cmd: "ACK", event_ids: [bytes32] }

Relay -> Client:
{ cmd: "ACKED", count: uint }

NOTIFY — relay pushes a notification:

Relay -> Client:
{ cmd: "NOTIFY", count: uint }

Sent when new events arrive for the authenticated pubkey. The client then issues a FETCH.

5.1.3 Connection Lifecycle

• Clients SHOULD send a WebSocket ping every 30 seconds.
• Relays SHOULD close idle connections after 5 minutes.
• On disconnect, clients SHOULD reconnect with exponential backoff (1s, 2s, 4s, ... capped at 60s).

5.2 HTTP Polling Transport (Tier 2)

Authentication via Authorization header:

Authorization: PPP-Ed25519 <pubkey_hex>:<sig_hex>
  where sig = crypto_sign_detached(
    request_body || timestamp, sk)

Clients SHOULD poll at a default interval of 30 seconds. The relay MAY include a Retry-After header.

5.3 Push Notification Bridge

Client -> Relay:
{ cmd: "REGISTER_PUSH",
  platform: "apns" | "fcm",
  token: string }

Push payloads MUST NOT contain event content — they serve only as wake signals for the client to FETCH.

5.4 SMS Notification (Tier 3)

Client -> Relay:
{ cmd: "REGISTER_SMS", phone_hash: bytes32 }

SMS content is limited to a generic notification and MUST NOT contain event content, sender identity, or location data.

5.5 Storage Backend

A single-instance relay uses SQLite (WAL mode) for event persistence. The relay stores only opaque GiftWrap envelopes — it cannot decrypt content, identify senders, or filter by location.

• STORE: Insert envelope, reject duplicates via event_id primary key.
• FETCH: Query by (recipient, created_at) with partial index excluding acknowledged events.
• ACK: Set acked_at timestamp; purge after grace period.
• Expiry purge: Background task deletes events past expires_at.

6. Sealed Sender

When a client submits a Note via authenticated STORE, the relay learns which pubkey sent it — breaking sender anonymity at the transport layer. Sealed sender eliminates this by allowing anonymous HTTP submission with a delivery token as the only identifier.

6.1 Delivery Token Derivation

shared_secret  = X25519(alice_x25519_sk, bob_x25519_pk)
               = X25519(bob_x25519_sk, alice_x25519_pk)

delivery_token = BLAKE2b(
    output_len:  12,
    key:         shared_secret,
    input:       recipient_pk
                 || "ppp-note-delivery-v1"
)

Properties:

• Symmetric: both contacts derive the same token for a given recipient.
• Domain-separated: the context string ensures tokens are distinct from room member tokens.
• 12 bytes (96 bits): sufficient anti-collision space for ~50-100 tokens per user.
• Self-authenticating: derived from a shared secret only the two contacts can compute.

6.2 Token Registration

Client -> Relay:
{ cmd: "REGISTER_DELIVERY_TOKEN",
  delivery_token: bytes12 }

Relay -> Client:
{ cmd: "DELIVERY_TOKEN_REGISTERED" }

• Maximum 100 tokens per recipient.
• Registration is idempotent.
• Rate-limited per standard per-pubkey limiter.

6.3 Anonymous Note Submission

POST /v1/note/submit
Content-Type: application/msgpack

{
  delivery_token:  bytes12,
  ephemeral_pk:    bytes32,
  nonce:           bytes24,
  ciphertext:      bytes,
  created_at:      uint64,
  expires_at:      uint64
}

Processing flow:

1. Validate field lengths.
2. Look up delivery_token → recipient_pk. Unknown token → 401.
3. Per-token rate limit: 2/sec. Exceeded → 429.
4. Validate expires_at > now.
5. Derive event_id = BLAKE2b(32, ephemeral_pk || nonce || ciphertext).
6. Store event. Duplicate → 409.
7. Notify recipient (WebSocket or push).

6.4 Graceful Fallback

Sealed sender is an optimization. Clients MUST support fallback to authenticated STORE when:

• The recipient hasn't registered the sender's delivery token yet.
• Token submission fails (unknown token, rate limit, error).
• The sender is already on an authenticated WebSocket.

Fallback degrades privacy but never blocks delivery. Clients SHOULD retry sealed submission before falling back.

6.5 Anonymity Set Considerations

The anonymity set is bounded by the number of contacts with registered tokens for the recipient. If Bob has only 3 contacts, the relay knows the sender is one of 3 people.

6.6 Sealed Sender Levels Roadmap

7. Room Protocol

Rooms are location-anchored group messaging spaces managed by an admin. Unlike point-to-point events (which use Gift Wrap encryption addressed to a single recipient), room messages are encrypted with a symmetric room key shared among members. The relay stores opaque ciphertext and routes messages by room_id — it cannot read content or identify senders.

Location representation — circles vs S2 cells: Notes and rooms use different spatial representations because they serve different purposes with different privacy properties:

• Notes use circles (S4.4) inside the encrypted payload. The relay never sees the location — only the recipient decrypts and performs a haversine proximity check. Circles are trivially implementable on all target platforms, including J2ME (~15 lines of basic trigonometry).
• Rooms use S2 cell IDs as relay-visible metadata for spatial indexing. The relay must answer “what rooms are near this location?” for discovery, which requires an indexable spatial representation. S2 cells provide hierarchical precision and map efficiently to SQLite indexes.

This means DISCOVER_ROOMS queries reveal to the relay which S2 cell the client is interested in (approximate location), while note regions remain fully confidential. This asymmetry is inherent: rooms trade some location privacy for discoverability by nearby strangers, while notes are exchanged only between known contacts.

7.1 Room Lifecycle

Creation:

Client -> Relay:
{ cmd: "CREATE_ROOM",
  room_id:            bytes16,
  s2_cell_id:         string,    // S2 fine cell for discovery
  s2_coarse_id:       string,    // S2 coarse parent cell
  gated:              bool,      // require membership token
  proximity_required: bool,      // reserved for future use
  ble_enabled:        bool,      // BLE knock/admit support
  max_members:        uint32,    // 1-100
  expires_at:         uint64 }   // must be > now

Relay -> Client:
{ cmd: "ROOM_CREATED", room_id: bytes16 }

The authenticated caller becomes the room admin. The relay indexes the room by S2 cell for geospatial discovery.

Discovery:

Client -> Relay:
{ cmd: "DISCOVER_ROOMS", s2_cell_id: string }

Relay -> Client:
{ cmd: "ROOMS", rooms: [RoomInfo] }

RoomInfo contains: room_id, s2_cell_id, gated, proximity_required, ble_enabled, member_count, created_at, expires_at. Only non-expired rooms matching the queried S2 cell are returned.

Update (admin only):

Client -> Relay:
{ cmd: "UPDATE_ROOM",
  room_id: bytes16,
  gated: bool | null,
  proximity_required: bool | null }

Relay -> Client:
{ cmd: "ROOM_UPDATED", room_id: bytes16 }

Expiry: Rooms expire at expires_at. Expired rooms reject FETCH and STORE. A background task purges expired rooms, cascading to messages, tokens, and knocks.

7.2 Member Tokens

Members prove group membership via 12-byte tokens derived from a symmetric room key:

member_token = BLAKE2b(
    key:        room_key,            // 32 bytes
    input:      member_signing_pk
                || room_id
                || "ppp-room-member-v1",
    output_len: 12
)

Where member_signing_pk is a per-room Ed25519 key derived from the member's long-term secret:

seed = BLAKE2b(
    key:   ed25519_sk[0..32],
    input: room_id || "ppp-room-sign-v1",
    output_len: 32
)
(pk, sk) = Ed25519_from_seed(seed)

This provides unlinkability: the per-room signing key cannot be linked to the member's long-term identity by the relay.

Registration (admin only):

Client -> Relay:
{ cmd: "REGISTER_TOKEN",
  room_id:         bytes16,
  member_token:    bytes12,
  admin_signature: bytes64 }

Relay -> Client:
{ cmd: "TOKEN_REGISTERED" }

The relay verifies: (1) caller is admin, (2) signature is valid for member_token || room_id under admin pubkey, (3) token count < max_members. Registration is idempotent.

Revocation (admin only):

Client -> Relay:
{ cmd: "REVOKE_TOKENS", room_id: bytes16 }

Relay -> Client:
{ cmd: "TOKENS_REVOKED", count: uint32 }

Key Rotation with Grace Period (admin only):

Client -> Relay:
{ cmd: "ROTATE_ROOM_KEY",
  room_id:       bytes16,
  grace_seconds: uint32 }    // clamped to [0, 600]

Relay -> Client:
{ cmd: "KEY_ROTATED",
  room_id:       bytes16,
  revoked_count: uint32,
  grace_until:   uint64 }

All existing tokens are marked with grace_until. During the grace period tokens remain valid; after, they are rejected. The relay broadcasts a KEY_ROTATION notification to all room subscribers.

7.3 Room Messages

Authenticated submission (WebSocket):

Client -> Relay:
{ cmd: "STORE_ROOM",
  room_id:    bytes16,
  nonce:      bytes24,
  ciphertext: bytes }

Relay -> Client:
{ cmd: "ROOM_STORED",
  room_id:         bytes16,
  sequence_number: int64 }

Sealed submission (anonymous HTTP POST):

POST /v1/room/submit
Content-Type: application/msgpack

{
  room_id:      bytes16,
  member_token: bytes12,
  nonce:        bytes24,
  ciphertext:   bytes
}

Processing: validate lengths, verify token for room_id (respecting grace period), per-token rate limit (2/sec), verify room not expired, store with auto-increment sequence number, notify subscribers.

Fetch:

Client -> Relay:
{ cmd: "FETCH_ROOM",
  room_id:  bytes16,
  since_id: int64 }

Relay -> Client:
{ cmd: "ROOM_MESSAGES",
  room_id:  bytes16,
  messages: [RoomMessage] }

RoomMessage: id (sequence number), nonce, ciphertext, stored_at. Returns up to 100 messages with id > since_id.

7.4 BLE Knock/Admit

For BLE-enabled rooms, prospective members request admission without prior knowledge of the room key:

Knock:

Client -> Relay:
{ cmd: "KNOCK",
  room_id:               bytes16,
  knocker_eph_x25519_pk: bytes32 }

Relay -> Client:
{ cmd: "KNOCK_OK", request_id: bytes16 }

The knock has a 120-second TTL. The admin is notified via WebSocket or push fallback.

Admit (admin only):

Client -> Relay:
{ cmd: "ADMIT", request_id: bytes16 }

Relay -> Client:
{ cmd: "ADMIT_OK" }

After admission, the admin encrypts the room key for the knocker using the ephemeral X25519 key:

grant = ble_grant_encrypt(
    admin_x25519_sk,
    knocker_eph_x25519_pk,
    room_id,
    room_key
)
// Wire: nonce (24B) || ciphertext (room_id
//        || room_key + 16B auth tag)

The knocker decrypts to obtain room_id and room_key, then derives their member token.

7.5 Room Notifications

8. Courier & BLE

8.1 Carry Group Lifecycle

Creation: A user generates a random group_id and distributes CARRY_GROUP_INVITE events (Gift Wrapped) to members.

Joining: A recipient sends CARRY_GROUP_ACCEPT back to the inviter with their pubkey consent.

Registration with relay:

Client -> Relay:
{ cmd: "REGISTER_CARRY_GROUP",
  group_id: bytes16,
  members:  [bytes32],
  couriers: [bytes32],
  sig:      bytes64 }

Leaving: A member sends a signed leave message. The relay MUST stop including departed members' events in subsequent FETCH_CARRY responses.

8.2 Courier Fetch Phase

When a courier has internet connectivity:

1. Authenticate with the relay.
2. Issue FETCH_CARRY for each carry group.
3. Store received events locally with metadata:

CarriedEvent {
  event:      GiftWrap
  fetched_at: uint64
  hop_count:  uint8       // starts at 0
  max_hops:   uint8       // default: 3
  delivered:  bool        // until recipient ACKs
  recipient:  bytes32     // for local lookup
}

8.3 BLE Delivery Protocol

8.3.1 GATT Service Definition

Service UUID:     0xPPP1 (short) or 128-bit TBD

Characteristics:
  HANDSHAKE_NONCE  (read):   bytes32, random per-session
  AUTH_RESPONSE    (write):  bytes32 (pk) || bytes64 (sig)
  EVENT_STREAM     (notify): chunked event data
  EVENT_ACK        (write):  bytes32 (event_id)

8.3.2 Handshake Sequence

Courier                           Recipient
  |                                    |
  |<-- BLE scan, discover service -----|
  |                                    |
  |--- read HANDSHAKE_NONCE ---------->|
  |                                    |
  |<-- write AUTH_RESPONSE ------------|
  |    pubkey || sign(nonce, sk)       |
  |                                    |
  |  verify sig, check carry group     |
  |                                    |
  |--- EVENT_STREAM notifications ---->|
  |    (chunked GiftWrap events)       |
  |                                    |
  |<-- EVENT_ACK per event_id ---------|
  |                                    |

8.3.3 Event Chunking

BLE MTU is negotiable (20-512 bytes). Events larger than (MTU - 3) are chunked:

Chunk {
  sequence:  uint16     // chunk index (0-based)
  total:     uint16     // total chunk count
  data:      bytes      // chunk payload
}

8.3.4 Rate Limiting

• Maximum 1 AUTH_RESPONSE per connection per 10 seconds.
• Maximum 10 unique pubkey attempts per hour.
• Failed attempts are logged locally (not transmitted).

8.4 Multi-Hop Rules

1. Both couriers perform the handshake (each acts as courier and recipient).
2. Events exchanged only if receiving courier's carry group includes the recipient pubkey.
3. hop_count incremented on transfer.
4. Events where hop_count >= max_hops are NOT relayed further.
5. Deduplication by event_id — duplicates silently dropped.

9. Contact Discovery

9.1 Hash Construction

normalized = lowercase(strip_whitespace(identifier))
  // phone: E.164 format
  // email: lowercase, remove dots in local part

hash = crypto_generichash(
    32,
    normalized,
    relay_pepper       // relay-provided, rotated
)

The relay pepper prevents offline rainbow table attacks. It is fetched from the relay on each discovery cycle.

9.2 Discovery Flow

1. Client -> Relay:
   { cmd: "DISCOVERY_PUBLISH",
     hashes: [bytes32],
     pubkey: bytes32 }

2. Client -> Relay:
   { cmd: "DISCOVERY_QUERY",
     hashes: [bytes32] }

3. Relay -> Client:
   { cmd: "DISCOVERY_MATCHES",
     matches: [{ hash: bytes32,
                 pubkey: bytes32 }] }

9.3 Privacy Properties

• The relay sees hashes, not raw identifiers.
• Pepper rotation invalidates old hashes, requiring republication.
• Rate limiting bounds enumeration attempts.
• Query padding with dummy hashes mitigates address book size leakage.

9.4 Rainbow Table & Brute-Force Analysis

Phone numbers have low entropy (~10 billion values per country code). This makes fast hashes vulnerable even with a pepper:

9.5 Hardening Roadmap

1. Slow hashing (near-term): Replace BLAKE2b with Argon2id. Raises brute-force cost from seconds to hours/days.
2. Server-side HMAC (medium-term): Relay applies HMAC with secret key. Prevents client-side brute-force but requires trusting relay with plaintext during query.
3. Private Set Intersection (long-term): OPRF-based PSI allows matching without either party learning the other's full set.

10. Out-of-Band Verification

Contact discovery finds candidates; verification confirms them. The protocol defines the payload format and crypto handshake but does NOT prescribe which channel to use.

10.1 Verification Levels

10.2 Verification Payloads

VerificationInvite (sent by initiator via OOB channel):

VerificationInvite {
  protocol:     "ppp-verify-v1"
  sender_pk:    bytes32
  invite_token: bytes16          // random, single-use
  relay_url:    string
  sender_sig:   bytes64          // sign(invite_token, sk)
  timestamp:    uint64
}

VerificationAccept (sent by responder):

VerificationAccept {
  protocol:       "ppp-verify-v1"
  responder_pk:   bytes32
  invite_token:   bytes16        // echoed from invite
  responder_sig:  bytes64        // sign(sender_pk
                                 //   || invite_token, sk)
}

The responder_sig signs both sender_pk AND invite_token, preventing forwarding attacks.

10.3 OOB URL Format

Invite:
https://<domain>/v?p=<b64(sender_pk)>
  &t=<b64(invite_token)>
  &r=<b64(relay_url)>
  &s=<b64(sender_sig)>
  &ts=<timestamp>

Accept:
https://<domain>/va?p=<b64(responder_pk)>
  &t=<b64(invite_token)>
  &s=<b64(responder_sig)>

10.4 Verification Flow

Alice (initiator)                Bob (responder)
  |                                   |
  |  1. Generate invite_token         |
  |     Sign with alice_sk            |
  |                                   |
  |-- 2. Send invite via OOB -------->|
  |                                   |
  |              3. Verify sender_sig  |
  |              4. Sign acceptance    |
  |                                   |
  |<- 6. Send accept via OOB ---------|
  |                                   |
  |  7. Verify responder_sig          |
  |     against invite_token          |
  |                                   |
  |  8. Both pin keys at level 1      |
  |                                   |
  |== 9. PPP communication begins ====|

10.5 Key Pinning

PinnedContact {
  contact_id:         string     // local only
  pubkey:             bytes32
  verification_level: uint8      // 0, 1, or 2
  verified_at:        uint64
  verified_via:       string     // channel name
  relay_url:          string
}

This record is stored locally and is NEVER transmitted to the relay.

10.6 Key Change Detection

10.7 Channel Trust Ranking

10.8 Invite Expiry & Anti-Spam

• Invites SHOULD expire after 48 hours.
• Used tokens MUST be rejected on re-use.
• Clients SHOULD limit outgoing invites (e.g., max 20/hour).

10.9 In-Person Verification

For level 2, both parties scan QR codes or compare a verification fingerprint:

fingerprint = base64(
  BLAKE2b(sort(alice_pk, bob_pk), 16))

Displayed as: aBc1 dEf2 gHi3 jKl4

Equivalent to Signal's safety number comparison.

11. Transport Tiers

11.1 Client Capability Advertisement

Client -> Relay:
{ cmd: "CAPABILITIES",
  transports: ["ws", "http", "ble"],
  push_platform: "apns" | "fcm" | null,
  push_token: string | null }

11.2 Tier Summary

11.3 Multi-Transport Delivery

A single event may be delivered via multiple transports simultaneously. The recipient deduplicates by event_id regardless of delivery path. The first successful ACK is authoritative.

12. Metadata Protection

12.1 Payload Padding

padded_length = next_bucket(plaintext_length)
padding       = randombytes(
  padded_length - plaintext_length - 2)
padded_input  = plaintext || 0x01 || padding || 0x00
                             ^^^^              ^^^^
                         delimiter          terminator

12.2 Blinded Mailbox Identifiers (Level 2 — Deferred)

Instead of fetching by long-term pubkey, clients use rotating mailbox identifiers:

epoch      = floor(unix_time / 86400)   // daily
mailbox_seed = X25519(user_sk, relay_pk)
mailbox_id = BLAKE2b(32,
  mailbox_seed || epoch)

The relay cannot link Monday's mailbox_id to Tuesday's without knowing the user's private key.

12.3 Batched Delivery

The relay SHOULD support configurable batch windows (default: 30s) to break timing correlation between event storage and notification.

• Relays SHOULD inject dummy notifications to maintain minimum batch size.
• Clients MAY request immediate delivery for latency-sensitive use.

12.4 Techniques Evaluated But Deferred

13. Threat Model

13.1 Adversaries

13.2 What Is NOT Protected

• Relay delivery graph (recipient side): The relay knows which pubkeys receive events. Sealed sender hides the submitter but the relay still resolves delivery tokens to recipients.
• Courier recipient set: Couriers know which pubkeys are in their carry group (by design).
• Traffic analysis: Message timing patterns may leak usage patterns. Partially mitigated by padding and batching.
• Key compromise: No forward secrecy (no Double Ratchet). Past events are readable if the private key is compromised.
• Device compromise: Locally stored keys and decrypted events are accessible.

13.3 Trust Assumptions

• Users trust their device's secure storage (Keychain, Keystore).
• Users trust the relay for availability but NOT confidentiality.
• Carry group members trust their courier for liveness but NOT content access.
• OOB verification trusts the chosen channel to deliver to the intended recipient.

14. Wire Format Summary

14.1 Outer Envelope (GiftWrap)

Field          Type      Description
─────────────  ────────  ──────────────────────────────
recipient      bytes32   Recipient pubkey or mailbox ID
ephemeral_pk   bytes32   Ephemeral wrap public key
nonce          bytes24   XChaCha20 nonce
ciphertext     bytes     Encrypted Seal
created_at     uint64    Unix timestamp
expires_at     uint64    Event expiry

Overhead: 32 + 32 + 24 + 8 + 8 = 104 bytes + ciphertext

14.2 Seal

Field          Type      Description
─────────────  ────────  ──────────────────────────────
ephemeral_pk   bytes32   Ephemeral seal public key
nonce          bytes24   XChaCha20 nonce
ciphertext     bytes     Encrypted Rumor
sender_sig     bytes64   Sender signature over ciphertext

Overhead: 32 + 24 + 64 = 120 bytes + ciphertext

14.3 Rumor

Field          Type      Description
─────────────  ────────  ──────────────────────────────
sender         bytes32   Sender Ed25519 public key
kind           uint8     Event kind (S4.2)
content        varies    Kind-specific payload (S4.3)
created_at     uint64    Sender-asserted timestamp

14.4 Region

Field          Type      Description
─────────────  ────────  ──────────────────────────────
region_type    uint8     0 = circle (v0.1 baseline)
latitude       float64   Center latitude (WGS84)
longitude      float64   Center longitude (WGS84)
radius_m       uint32    Radius in meters

Overhead: 1 + 8 + 8 + 4 = 21 bytes

14.5 Total Overhead Estimate

For a typical PRESENCE event with 140-byte message and circle region:

Rumor:    32 + 1 + ~200 (16 id + 140 msg
          + 21 region + 24 time) + 8     = ~241 B
Seal:     32 + 24 + (241 + 16 tag) + 64 = ~377 B
GiftWrap: 32 + 32 + 24 + (377 + 16) + 16 = ~497 B

Under 500 bytes per event — well within BLE MTU negotiation range and efficient for constrained networks.

15. Test Vectors

Reference implementations MUST pass these vectors to confirm cross-platform interoperability.

Planned vectors:

1. Key generation from a known seed.
2. Gift Wrap encryption of a known rumor, verifiable by a known recipient key.
3. Event ID derivation from a known GiftWrap.
4. CHALLENGE-AUTH handshake with known nonce and key pair.
5. BLE handshake with known nonce and key pair.
6. Haversine distance check: known lat/lon pair → known distance → inside/outside result for a circle region.
7. OOB verification: invite generation, accept signature verification, forwarding attack rejection.

Vectors are published as JSON in the test-vectors/ directory with deterministic seeds and nonces for reproducibility.

16. Traceability

These requirements derive from the NowHere app spec and brainstorming sessions on cross-platform protocol design.

A. Sync & Reliability

B. Security Requirements