Protocol

Everything a second implementation would need. The protocol is deliberately small: HTTP with JSON bodies, one binary endpoint for blobs, no streaming requirement, no server-side state machine. A relay is a database with fourteen routes and no curiosity.

Types are normative as written in @skm/core (protocol.ts, keys.ts); this file explains what they mean and why they are shaped that way.

Vocabulary

Term	Meaning
member	An identity in the host app. skm never defines one.
device	One machine holding keys. A member has many; each has its own wrapping and signing keypairs.
graph	A namespace of records under one keyring.
record	{id, kind, deleted?, data, at, by}, encrypted as one unit.
epoch	A generation of a graph’s key. Rotation mints the next one.
rev	A record’s revision — the device’s monotonic timestamp. LWW compares these.
seq	The relay’s per-graph write counter. Pull cursors are seqs.

Graph ids

u                  the caller's personal graph
g:<groupId>        a shared graph; membership answered by the Directory
d:<memberId>       the pairwise graph between the caller and that member

[A-Za-z0-9_-]{1,64} for the id part. A relay maps these to storage keys, which clients never send and never see:

u          -> u:<callerId>
g:<id>     -> g:<id>
d:<other>  -> d:<a>:<b>   where [a, b] = sort([callerId, other])

The pairwise form is order-independent on purpose: Sam addresses the graph as d:alex and Alex addresses the same graph as d:sam, and both must land on one row. Everything that binds or signs uses the storage key, so both ends compute the same string with nothing coordinating them.

Cryptography

• Records and blobs: AES-256-GCM. Nonce is 96 random bits, fresh per encryption.

• AAD: <storageKey>/<recordId> for records, <storageKey>/blob/<blobId> for blobs. This is the whole anti-swap defense: ciphertext lifted from one slot and replayed into another fails to open, because the slot’s name is authenticated data. A relay that shuffles rows produces errors, not wrong answers.

• Key wrapping: ephemeral ECDH P-256 → HKDF-SHA256 (info: "skm-wrap-v1") → AES-256-GCM over the 32-byte graph key. The wrap carries its ephemeral public key (epk, a JWK, base64url).

• Signatures: ECDSA P-256 with SHA-256, over "skm-record-v1\n" + storageKey + "\n" + canonicalJson(record). Canonical means object keys sorted recursively — JSON.stringify preserves insertion order, which is a property of how an object was built rather than of what it contains, and two devices that build one record differently would otherwise disagree about its bytes.

  Not Ed25519, which would be the better scheme: WebCrypto support for it arrived late and unevenly, and a signature scheme absent on a member’s device is worse than a larger one that always works.

• Code-derived keys: PBKDF2-SHA256, 310,000 iterations, 128-bit salt. Used for invite keyrings and recovery bundles.

• Derived tags: HKDF(key, label) → HMAC-SHA256(input), truncated to 132 bits, for unlinkable personal record ids.

All base64url, unpadded, [A-Za-z0-9_-].

Records and the envelope

interface GraphRecord {
  id: string; // [A-Za-z0-9_-]{1,64}
  kind: string; // the app's schema name
  deleted?: true; // tombstone: an empty husk that keeps syncing
  data: Record<string, unknown>;
  at: number; // the revision; monotonic per device
  by: string; // author's member id
}

interface RecordEnvelope {
  // what is actually sealed
  v: 1;
  r: GraphRecord;
  d?: string; // the DEVICE that signed
  s?: string; // base64url ECDSA signature
}

The signature lives inside the ciphertext rather than beside it on the wire. The relay cannot verify it (no plaintext, no roster trust) and does not need it, so putting it outside would leak an author to the one party that should not learn one.

A receiver accepts a record only if all of this holds:

1. the ciphertext opens under the AAD naming its slot;
2. the envelope parses, and r.id matches the slot it arrived in;
3. the app’s schema for r.kind accepts r.data (tombstones excepted);
4. unless the app opted out, d names a device in the graph’s roster, s verifies over the signing bytes, r.by equals that device’s member, and the device was not already revoked when r.at says the record was written.

A record failing any of these is skipped, and the reason is reported. It is never applied “best effort”.

at must be monotonic per device AND must clear the revision it replaces. The relay drops a push whose rev is <= the one it holds, so a device that stamps a losing revision keeps content the relay never accepted — a silent divergence with no error anywhere, made permanent by the fact that the pull cursor has already passed the relay’s copy. Stamp max(now, last + 1, priorRev + 1), where priorRev is the at of the record being overwritten, or 0 for a new one.

The second term is the obvious case: two writes to one record inside a single millisecond. The third is the one that is easy to miss and worse — editing a record another device wrote from a clock a few milliseconds ahead produces a LOWER revision unless the local copy is read first.

Granularity is the app’s decision, and it is the important one. A chat message is one record because nobody co-edits a sentence already sent. A document should be a header record plus one record per block, so LWW merges at paragraph granularity instead of clobbering an afternoon. skm gives you per-record merge; where you put the record boundaries decides what “conflict” means in your app.

Limits

Normative, from LIMITS in @skm/core. A relay MAY be configured stricter; it may never be looser, because a client that respects these must not be rejected for it.

Limit	Value	Why
maxRecordBytes	512 KiB	plaintext record; larger content is a blob
maxCiphertextChars	700,000	one sealed record on the wire
maxOpsPerPush	200	records per push
maxPushBytes	8 MiB	and a byte budget: 200 maximal records is 140MB, and the 413 that follows is not retryable, so the queue would stop draining and stay stopped
maxPullLimit	500	records per pull page
maxBlobBytes	25 MiB	one blob
maxRevSkewMs	5 min	how far ahead of the relay a revision may be stamped

Routes

All paths are relative to wherever the relay is mounted. Every route requires authentication; the token must name both the member and the device. Every route except device registration additionally requires that the named device is registered to the named member and not revoked.

Devices

PUT    /devices/:deviceId    {pubJwk, sigJwk, label?}  -> {ok, deviceId, fresh}
GET    /devices                                        -> {devices: [...]}
POST   /devices/:deviceId/revoke                       -> {ok, rotationOwedFor}

PUT is set-once, and takes both keys at once: a device that could add a signing key later could sign yesterday’s history with today’s key. A device id already bound to different keys is refused with 409 device-key-conflict — rebinding is exactly how an attacker would redirect the next grant. The honest response to a 409 is a new device id, never a rebind.

Revoke drops the device’s wraps, marks it revoked, and sets rotation_required on every graph it held keys for. It does not, and cannot, reach into a device that already synced.

Records

POST /graphs/:gid/push    {ops: GraphOpIn[]}   -> {accepted, cursor, now, epoch, rejected?}
GET  /graphs/:gid/pull?after=&limit=&kinds=&shards=
                                               -> {ops: GraphOpOut[], cursor, more, epoch}

GraphOpIn  = {recordId, rev, e?, n, c, k?, sh?}   // e = epoch, n = nonce, c = ciphertext
GraphOpOut = GraphOpIn & {seq}

Push semantics, per op:

1. If rev is more than maxRevSkewMs ahead of the relay’s clock, reject it with rev-too-far-ahead and continue. A device with a broken clock would otherwise pin a record nothing could ever supersede.
2. If a row exists with rev >= op.rev, skip it silently. Losing is normal; it is how devices converge.
3. If a quota would be exceeded, reject that op with a reason and continue.
4. Otherwise upsert, assigning the next seq from a per-graph counter.

A push is not all-or-nothing: rejected names each refused record and why, so a client is told precisely what did not land instead of inferring it from a count. now is the relay’s clock — the reference a device with a wrong clock uses to correct itself, since retrying from the same wrong clock cannot work.

epoch on both answers is the graph’s current key generation (0 = no key yet). It is how a device learns that somebody rotated: without it, a device only finds out by meeting a record it cannot open, and until then it keeps sealing under the key the rotation was performed to take away. A client SHOULD treat an epoch above the one it holds as a signal to fetch keys before its next write. It is optional on the wire so a client can talk to an older relay, and a client MUST only ever move its idea of the epoch upward.

The sequence comes from a counter, never from MAX(seq) + 1: a number reused after a delete would make a puller skip a record.

Pull returns ops with seq > after, ascending, at most limit. more says another page waits. Clients persist cursor per subscription, because a filtered and an unfiltered view of one graph are at different places in the same sequence.

A client that meets an op sealed under an epoch it lacks must stop before that op without advancing its cursor, ask for keys, and resume later. Skipping it loses the record forever.

Partial sync

k (kind) and sh (shard) on a pushed op are stored and readable by the relay forever. That is the entire point of them and the entire cost. A client sends them only when the app has decided partial sync is worth the leak; the default in @skm/client is to send neither.

shard is an app-chosen label — a channel, a month, a project — which SHOULD be an opaque derived tag rather than a name, and MUST NOT change over a record’s life: the relay filters on it, so a record that moves shards would vanish from one subscription without appearing in the other.

A filtered pull that exhausts its matches fast-forwards cursor to the graph’s high-water mark rather than leaving it where it was, so the next pull does not rescan the same range forever. Anything written after that mark necessarily has a higher seq, so nothing can be skipped by it.

Keys

GET    /graphs/:gid/keys      -> {latestEpoch, rotationRequired, wraps: [{epoch, wrapped}]}
GET    /graphs/:gid/devices   -> {devices: [{deviceId, memberId, pubJwk, sigJwk, revokedAt}]}
GET    /graphs/:gid/keygaps   -> {latestEpoch, gaps: [{deviceId, memberId, pubJwk, epochs}]}
POST   /graphs/:gid/keys      {epoch, wraps: [{deviceId, wrapped}]} -> {ok, latestEpoch}
DELETE /graphs/:gid/keys/:epoch  -> {ok, discarded}

GET keys returns wraps for the calling device only.

GET devices is the roster: what a new epoch must cover, and what signatures verify against. It includes revoked devices, marked with revokedAt — a signature made before a revocation is still a true statement about who wrote that record, and dropping the key would make every record a retired laptop ever wrote unverifiable. Wrapping filters to revokedAt === null; verification does not.

keygaps is the work list: devices holding no wrap for some epoch, with the public keys to wrap to — pulled from the roster, never supplied by the asking device, so a forged request cannot redirect a key.

POST keys has two modes:

• epoch > latest — init or rotation. Must be exactly latest + 1 (409 epoch-gap otherwise) and must cover every eligible device in one request (400 incomplete-rotation with the missing ids otherwise). A rotation that strands somebody is refused, not accepted-and-regretted.
• epoch <= latest — a grant to devices that lack that epoch. Existing wraps are never overwritten, so a key holder cannot replace another device’s copy with one it cannot open.

Every wrap must address an active device belonging to a current member; otherwise 400 not-a-member-device. A key holder could always hand the key over out of band — what the relay refuses is to be the thing that stores it for an outsider.

DELETE keys/:epoch discards the calling device’s own wrap. A wrap a device cannot open is worse than no wrap: the relay believes the key was delivered, so keygaps reports nothing and nobody re-grants it. That happens by accident, and on purpose — the relay cannot verify that a wrap decrypts, because it cannot decrypt — so a device that fails to unwrap discards the wrap and reappears in the gap list, where somebody holding the key fills it properly.

Blobs

POST   /graphs/:gid/blobs/:blobId?policy=<p>&ttl=<ms>   body: raw ciphertext
       headers: content-type: application/octet-stream, x-blob-nonce: <b64>
GET    /graphs/:gid/blobs/:blobId    -> raw ciphertext, x-blob-nonce header
POST   /graphs/:gid/blobs/:blobId/ack -> {ok, forgotten}
DELETE /graphs/:gid/blobs/:blobId    -> {ok}

Policies: retain (default), transport (deleted once every current member has acked), ephemeral (deleted after ttl, max 30 days). Uploading counts as one receipt. A sweeper re-checks transport blobs against the current member set, because that set shrinks and a blob waiting on a departed member would otherwise wait forever.

A blob id is immutable: re-uploading one that exists is a retry, answered with duplicate: true, never an edit. Overwriting would let one member swap the bytes under a record another member already read.

Ceremonies

Bootstrap a graph. GET devices → generate a 256-bit key → wrap to every active device → POST keys {epoch: 1, wraps}.

Link a device. New device generates both keypairs, PUT /devices/:id, then polls GET keys and rests in waiting. Any device holding the keyring reads GET keygaps, wraps each missing epoch to the published pubkey, and POST keys. No private key ever moves. This is the ceremony that makes a recovery bundle a recovery mechanism rather than an onboarding step.

Invite a member with the keys. Mint keySecret and a salt; seal the keyring under PBKDF2(keySecret, salt); store the sealed blob with the invite. The invite string is <doorCode>.<keySecret> — only the door code is ever sent to the server. The invitee splits it, derives the key, opens the keyring.

Rotate. GET devices → new key → wrap to all active → POST keys {epoch: latest+1}. Whoever left keeps what they already synced; they can read nothing after.

Recover. The bundle is {v: 1, salt, sealed}, sealed under a passphrase, carrying graph keyrings only — never a device keypair. A restored machine is a NEW device: it registers its own keys and adopts the graph keys. Copying the old keypair across would mean two machines signing as one device, which makes revocation meaningless.

What the relay sees

It cannot avoid seeing: which member syncs which graph and when, record ids, ciphertext sizes, revisions and seqs, epoch numbers, blob sizes and policies, the device roster with public keys, and — where an app opted in — record kinds and shard labels.

It never sees: record contents, blob contents, graph keys, any private key, record authorship, or which records a member reads.

Metadata is a real channel. SECURITY.md is where skm is honest about it, including a leak it fixed and one it cannot fix retroactively.