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

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}

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

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:

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.