# 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 fifteen
routes and no curiosity.

Types are normative as written in `@argala/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. argala 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
```

The ID portion must match `[A-Za-z0-9_-]{1,64}`. 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.

  A verifier MUST canonicalise the record **as it was sealed**, including any
  member it does not recognise, and MUST NOT re-canonicalise the record after
  discarding unknown members. Dropping them first yields different bytes from
  the ones the writer signed, so every record from a writer that knows one
  more field than the reader fails signature verification — a fleet-wide,
  one-way partition that presents as forgery rather than as version skew. The
  unknown member is covered by the signature and then ignored: a verifier
  applies only the members it understands.

  argala does not use Ed25519, although it would otherwise be the better
  scheme. WebCrypto support arrived late and unevenly, and a signature scheme
  absent from a member's device is worse than a larger one that works
  consistently.

- **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 values are unpadded and match `[A-Za-z0-9_-]`.

## Records and the envelope

```ts
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 the authorship.

A receiver accepts a record only if all of the following conditions hold:

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 **of `r` as it was sealed** (see
   Cryptography — not of `r` after unknown members were dropped), `r.by`
   equals that device's member, and the device was not already revoked when
   `r.at` says the record was written.

A record that fails any of these checks is skipped, and the reason is reported.
It is never applied on a "best effort" basis.

**`at` must be monotonic per device AND must exceed 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 handles the obvious case: two writes to one record within a
single millisecond. The third is easier to miss and more damaging — 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. argala gives you
per-record merge; where you put the record boundaries decides what "conflict"
means in your app.

## Limits

These values are normative and come from `LIMITS` in `@argala/core`. A relay
MAY enforce stricter limits, but never looser ones, because a conforming client
must not be rejected for respecting these limits.

| 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 total 140 MB, and the resulting 413 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, selfSig?, 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.

`selfSig` is the device's own signature, under its signing key, over
`selfAttestationBytes(fingerprint)` — the bytes
`skm-device-self-v1\n<fingerprint>`. It binds the WRAPPING key the relay
publishes for a device to the SIGNING key that device's records verify under,
so a relay cannot publish an honest signing key beside a wrapping key it holds
the private half of. The relay stores and republishes it verbatim and cannot
check it; a device that verifies it has proven nothing about who the device
belongs to, only that both published keys came from one holder. It is optional
on the wire because devices registered before it existed do not have one, and
a device without one is simply never auto-approved.

The **device fingerprint** is
`SHA-256("skm-device-v1\n<memberId>\n<thumbprint(pubJwk)>\n<thumbprint(sigJwk)>")`,
base64url, where each thumbprint is RFC 7638 over the JWK's required members
only (`crv`, `kty`, `x`, `y` for EC). The device ID is deliberately NOT in the
digest: it is a free-form string a relay chooses, and including it would turn
a preimage search into a cheap grind over one field.

The **pairing code** a human compares is 12 characters of Crockford base32
(lowercase, no `i`, `l`, `o` or `u`) over
`PBKDF2-SHA256(fingerprint, "skm-pair-v1", 310000)` taken to 64 bits. The
stretch raises the cost of every guess, allowing the code to use 12 characters
instead of 40.

The code is deliberately **one-sided** — derived from the joining device
alone, not from both parties the way a Signal safety number is. A symmetric
construction would let a relay controlling both screens search two candidate
sets at once and look for a collision between them; that is a birthday attack,
and resisting it would cost twice the characters.

Both derivations are client-side. They are specified here because two
implementations must agree on them exactly, or the ceremony has a human
comparing two different strings and concluding something is wrong.

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.

### Capabilities

A relay MAY refuse an operation a member is not permitted to perform, with
`403 {error: 'not-permitted', need: <capability>}`. Two capabilities are
defined, and both name an operation the relay MEDIATES:

| capability | gates                                                        |
| ---------- | ------------------------------------------------------------ |
| `write`    | `POST push`, `POST blobs/:id`, `DELETE blobs/:id`            |
| `rotate`   | `POST keys` where `epoch > latest` — minting a new key epoch |

Where the permissions come from is outside this protocol: they are the host
app's, arriving through the same seam as membership. A relay that has no
opinion MUST behave as though every member holds both, so that a deployment
which has not configured any keeps working.

**A capability is not a confidentiality boundary.** A member holding a graph
key can decrypt every record in it; refusing their writes does not and cannot
change that. To stop somebody reading, remove them and rotate. Nor is this a
defence against a hostile relay, which decides the answer it then enforces.

A client MUST NOT treat `403 not-permitted` as a transport failure. It is not
retryable, and it must not abort a sync: a device that is permitted to read
and not to write has to keep pulling, so the correct handling is to hold the
queued writes, report the refusal, and continue with the pull.

### 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}
GET  /graphs/:gid/log?after=&limit=            -> {entries: LogEntry[], cursor, more, head, oldest}
```

```ts
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 encounters 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.

### The append-only log

```ts
LogEntry = { seq, recordId, rev };
```

One line per accepted write, in the order the relay assigned. Nothing here is
a field the relay did not already have: `seq` it assigned, `recordId` and
`rev` it was handed on the push. It is not filtered and MUST NOT be — a client
that asked to see a subset cannot verify a chain over everything.

**Why it exists.** `graph_records` is keyed by record ID, so an update moves
the row to a new sequence number and the version it replaced ceases to exist in
that table. A client that joined last week and one that joined today therefore
pull different sequences of rows, and no chain computed over those rows could
ever agree. The log does not move, so a chain over the log does.

A relay MUST append inside the same transaction as the record upsert, MUST NOT
log a write it refused (a last-write-wins loser is not a write), and MUST NOT
rewrite an entry. `head` is the highest seq in the log; `oldest` is the lowest,
so a client whose cursor predates the log knows that the span cannot be checked
rather than concluding that the relay omitted it.

**The chain**, over entries in seq order, is what clients compare:

```
h₀ = base64url(SHA-256("skm-log-v1\ngenesis\n" + storageKey))
hₖ = base64url(SHA-256("skm-log-v1\n" + hₖ₋₁ + "\n" + seq + "\n" + recordId + "\n" + rev))
```

Genesis is bound to the storage key so one graph's log cannot pass as
another's. Sequence numbers are NOT contiguous — a push allocates its whole
range up front and a refused op spends one — so a chain over "every entry
present, in order" is the definition, not "every seq from 1".

A client SHOULD verify two things after a pull, and only for an unfiltered
subscription, and only up to the sequence number it was actually served:

1. every entry names a record it holds at that `rev` or newer, unless it
   refused that record deliberately;
2. its chain head at a checkpoint boundary equals what other devices signed
   for the same boundary.

Failing (1) means the relay contradicted its own account of a push it
accepted. Failing (2) means it is not serving one graph to everybody.

### Checkpoints

A device publishes its chain head as an ordinary record — sealed, signed,
pushed, and verified against the roster like anything else — of reserved kind
`skm.checkpoint`:

```ts
data = { v: 1, d: deviceId, seq, head };
```

`d` is not decoration. The record ID below is derived from the graph key, so
every member can compute every other device's slot and write into it. A
receiver MUST believe a checkpoint only when its ID is the one derived for
`d`, and when the record's proven author (`by`, checked against the signature
and the roster) owns device `d`. Without both checks a member could put a
false history in an honest device's mouth, or inflate how many devices appear
to corroborate one.

`seq` MUST be a multiple of 64, so that two devices crossing the log at
different moments hold a head at the same point rather than two nearby ones.
The head at boundary B is the chain after folding every entry with `seq ≤ B`,
which is defined whether or not an entry sits exactly on B.

The record ID MUST NOT be derived from anything the relay can link to a
device. argala uses `HMAC(HKDF(epoch-1 key, "skm-ckpt-v1"), deviceId)`, for the
same reason personal record IDs are derived: IDs are visible, and naming this
one after its author would hand back the authorship that keeping signatures
inside the ciphertext exists to hide.

Kinds beginning `argala.` are reserved for the engine and MUST be validated
against the protocol's own schemas, never against an application's registry.

### 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 `@argala/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 advances `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, selfSig, revokedAt}]}
GET    /graphs/:gid/keygaps   -> {latestEpoch, gaps: [{deviceId, memberId, pubJwk, sigJwk, selfSig, epochs}]}
POST   /graphs/:gid/keys      {epoch, wraps: [{deviceId, wrapped}], excluding?} -> {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.

It also **includes devices of members who have since left the graph**, for the
same reason one level up. A roster built from current membership alone answers
a different question depending on when it is asked, so offboarding somebody
would make every record they ever wrote unattributable — kept by devices that
had already synced, dropped by every device that synced afterwards. A relay
MUST therefore serve the devices of every member who has pushed to the graph,
not only those who are in it now. This grants a departed member nothing: they
cannot push, and the completeness check for a new epoch still covers current
members only, so the next key is not wrapped to them.

`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. It carries `sigJwk` and
`selfSig` alongside `pubJwk` because the granting device has to fingerprint
the whole triple before it decides to wrap; handing it only the wrapping key
would mean approving one thing and encrypting to another.

`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 with a warning —
  unless it says so. `excluding` names devices the caller is stranding **on
  purpose**, so that a device nobody has approved does not deadlock rotation
  against the completeness rule. A device may not be both wrapped to and
  excluded, and may not be excluded if it is not eligible in the first place
  (`400 invalid-exclusion`). The relay reports the exclusions on the
  `graph.rotate` event: a field that could strand a device silently would be
  worse than no field.
- **`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.

Minting an epoch (`epoch > latest`) additionally requires the `rotate`
capability, and a caller without it is refused `403 not-permitted {need}`.
Filling a gap (`epoch <= latest`) does not: the grant hands over a key its
caller already holds, and a member who could not add a second device would
have an unusable seat rather than a restricted one.

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 the creating device will vouch for → `POST keys {epoch: 1,
wraps, excluding}`. On a fleet of one that is the creating device itself,
which pins its own keys: trust on first use, and there is no in-band fix
for it.

**Link a device.** New device generates both keypairs and a `selfSig` over its
own fingerprint, `PUT /devices/:id`, then polls `GET keys` and enters the
`waiting` state. Any device holding the keyring reads `GET keygaps` and, for each
gap, fingerprints the published key triple and decides whether it will wrap to
it at all: automatically if that device has already written a record this one
opened and verified and its `selfSig` checks out, otherwise only after a human
compares pairing codes. It then wraps each missing epoch and `POST keys`,
naming in `excluding` any device it refused. **No private key ever moves.**
This is the ceremony that makes a recovery bundle a recovery mechanism rather
than an onboarding step, and the approval step is what stops the relay from
adding a device of its own and waiting to be granted.

**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 every active device the rotating
device will vouch for → `POST keys {epoch: latest+1, excluding}`. A removed
member retains what they already synced but can read nothing written
afterward. Rotation runs the same approval gate as a grant for the same reason:
responding to a stolen laptop is the worst possible moment to hand a key to a
device nobody recognises.

**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 sequence numbers, epoch numbers, blob sizes
and policies, the device roster with public keys and self-attestations, which
devices a rotation deliberately excluded, 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. The log adds no new field
the relay can read, but it does make the relay RETAIN the shape of a record's
edit history rather than overwrite it. This is a meaningful change in
retention and is documented as such in SECURITY.md.

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