playlists: merge rules, sealing, and the key

playlist-merge.js and playlist-crypto.js have no imports and are run by
their tests, which is the only real evidence this feature can have.

Two revision counters per playlist, not one: a rename on one device and
a track added on another both write n+1, and a single counter makes two
edits that do not overlap collide.

One Argon2 run at sign-in, two handles. The AES handle is imported
non-extractably, so nothing can be derived from it — hence a second
import of the same bytes as HKDF rather than a derivation.

Measured: ~270 bytes a track, deflate worth 4.5x on realistic data, so
the 1 MB body cap holds about 17000 tracks.

Co-Authored-By: Claude Opus 5 <noreply@anthropic.com>

4 files changed, 466 insertions, 4 deletions

diff --git a/packages/meshbay-hub/src/meshbay_hub/static/group-page.js b/packages/meshbay-hub/src/meshbay_hub/static/group-page.js
index 060fd6e..205fce2 100644
--- a/packages/meshbay-hub/src/meshbay_hub/static/group-page.js
+++ b/packages/meshbay-hub/src/meshbay_hub/static/group-page.js
@@ -242,7 +242,7 @@ function GroupPage({ groupId, group, token, username, userId, userPrefs,
       // that opens node bundles is missing here. Persisted so this browser is
       // set up from now on.
       session.bundleKey = {
-        v2: await window.MeshBayKeys.deriveEncryptionKey(pass, username),
+        ...(await window.MeshBayKeys.bundleKeyPairFields(pass, username)),
         v1: await window.MeshBayKeys.deriveEncryptionKeyV1(pass, username),
       };
       await _storeBundleKey(session.bundleKey);
diff --git a/packages/meshbay-hub/src/meshbay_hub/static/keyderive.js b/packages/meshbay-hub/src/meshbay_hub/static/keyderive.js
index 918ade3..edfa109 100644
--- a/packages/meshbay-hub/src/meshbay_hub/static/keyderive.js
+++ b/packages/meshbay-hub/src/meshbay_hub/static/keyderive.js
@@ -142,7 +142,7 @@ async function deriveEncryptionKeyV1(password, username) {
  * passphrase in memory to re-derive it whenever a bundle turns up. It is unique
  * per account, so it does what a salt is for — no shared precomputation.
  */
-async function deriveEncryptionKey(password, username) {
+async function _bundleKeyBytes(password, username) {
   const enc  = new TextEncoder();
   const salt = new Uint8Array(await crypto.subtle.digest(
     'SHA-256', enc.encode(`meshbay:bundle:v2:${username}`))).slice(0, 16);
@@ -151,8 +151,42 @@ async function deriveEncryptionKey(password, username) {
     time: ARGON2_TIME, mem: ARGON2_MEM_KIB, parallelism: ARGON2_LANES,
     hashLen: 32, type: _argon2().ArgonType.Argon2id,
   });
+  return out.hash;
+}
+
+async function deriveEncryptionKey(password, username) {
   return crypto.subtle.importKey(
-    'raw', out.hash, { name: 'AES-GCM' }, false, ['encrypt', 'decrypt']);
+    'raw', await _bundleKeyBytes(password, username),
+    { name: 'AES-GCM' }, false, ['encrypt', 'decrypt']);
+}
+
+/**
+ * The bundle key as **two handles over one Argon2 run**.
+ *
+ * `aes` is what has always been returned: the key that opens a node's identity
+ * bundle. `hkdf` is the same 32 bytes imported a second time as an HKDF key,
+ * from which purpose-separated subkeys can be derived — playlists are the
+ * first (docs/playlists.md §3.4).
+ *
+ * It has to be a second import of the same bytes, and not a derivation from
+ * `aes`: that one is imported non-extractably with `['encrypt','decrypt']`, so
+ * nothing can be derived from it at all. And it has to be one Argon2 run: a
+ * second call would put another ~650 ms on the sign-in path for a key that is
+ * mathematically identical.
+ *
+ * A subkey rather than the bundle key reused with a different AAD, for the
+ * reason `groupbox.py` already writes down for chunk keys — purpose separation
+ * is what stops one use's mistake becoming every use's.
+ */
+async function deriveBundleKeys(password, username) {
+  const raw = await _bundleKeyBytes(password, username);
+  return {
+    aes: await crypto.subtle.importKey(
+      'raw', raw, { name: 'AES-GCM' }, false, ['encrypt', 'decrypt']),
+    // HKDF keys are non-extractable by specification; `false` is the only
+    // value this accepts.
+    hkdf: await crypto.subtle.importKey('raw', raw, 'HKDF', false, ['deriveKey']),
+  };
 }
 
 // ── Account recovery key ─────────────────────────────────────────────────────
@@ -393,7 +427,7 @@ async function loginAndRecover(username, password) {
     // Both, so a bundle written before the KDF changed can still be opened —
     // and re-written with the new one on the next backup.
     bundleKey: {
-      v2: await deriveEncryptionKey(password, username),
+      ...(await _bundleKeyPairFields(password, username)),
       v1: await deriveEncryptionKeyV1(password, username),
     },
   };
@@ -417,6 +451,17 @@ async function signBytes(skEdPkcs8B64, message) {
   return btoa(String.fromCharCode(...new Uint8Array(sig)));
 }
 
+/**
+ * `{ v2, v2hkdf }` — the two fields every `session.bundleKey` carries for the
+ * current KDF. One helper because there are two places that build that object
+ * and they must not drift: a `v2hkdf` missing from one of them is a playlist
+ * store that silently does nothing on whichever sign-in path skipped it.
+ */
+async function _bundleKeyPairFields(password, username) {
+  const { aes, hkdf } = await deriveBundleKeys(password, username);
+  return { v2: aes, v2hkdf: hkdf };
+}
+
 window.MeshBayKeys = {
   registerUser, loginAndRecover, generateNodeIdentity, generateKeypairs, signBytes,
   deriveAuthKey, decryptBundleWithKey, encryptBundleWithKey, bundleVersion,
@@ -424,6 +469,10 @@ window.MeshBayKeys = {
   // node's identity bundle needs the old key (a {v2,v1} pair, since an old
   // bundle may be v1) to read it and the new v2 key to write it back.
   deriveEncryptionKey, deriveEncryptionKeyV1,
+  // One Argon2 run, an AES handle and an HKDF handle. Whatever builds a
+  // `session.bundleKey` uses this, so `v2hkdf` is never the field one sign-in
+  // path forgot (docs/playlists.md §3.4).
+  deriveBundleKeys, bundleKeyPairFields: _bundleKeyPairFields,
   // Account recovery key (docs/auth-confirm.md §4.3).
   generateRecoveryKey, deriveRecoveryKey,
 };
diff --git a/packages/meshbay-hub/src/meshbay_hub/static/playlist-crypto.js b/packages/meshbay-hub/src/meshbay_hub/static/playlist-crypto.js
new file mode 100644
index 0000000..0f41d1e
--- /dev/null
+++ b/packages/meshbay-hub/src/meshbay_hub/static/playlist-crypto.js
@@ -0,0 +1,155 @@
+/**
+ * Sealing a playlist blob, and opening one.
+ *
+ * `docs/playlists.md` §3.4 and §4.3. The node stores bytes it cannot read; this
+ * is what makes them unreadable, and what makes them small enough to be worth
+ * storing at all.
+ *
+ * The order is **compress → pad → seal**, and none of the three is optional:
+ *
+ *  - *Compress*, because the payload is about as compressible as data gets —
+ *    eleven keys repeat on every track, the group id repeats across the whole
+ *    list, and path prefixes repeat per album. Three times is conservative for
+ *    this shape, and without it a realistic Favourites list does not fit under
+ *    any cap worth setting.
+ *  - *Pad*, because the ciphertext length otherwise tells the operator roughly
+ *    how many tracks this account has collected, and — once compression is in —
+ *    roughly how repetitive its paths are. 4 KB granularity, which is cheap and
+ *    is the only metadata this design leaks to a node that the node cannot
+ *    already see.
+ *  - *Seal*, last. Sealing first and compressing after would be compressing
+ *    ciphertext, which does not compress; padding outside the AEAD would be
+ *    padding nobody authenticated.
+ *
+ * `CompressionStream('deflate-raw')` is native in Chromium, Firefox 113+ and
+ * Safari 16.4+, and therefore in the Electron build. No dependency: the one
+ * compression helper this project has (`zipstream.js`) deliberately stores
+ * rather than deflates, for a different reason — archives are already
+ * compressed and this is text.
+ *
+ * No imports, and there must be none: the whole module is executed standalone
+ * by `test_playlist_crypto.py` against node's own WebCrypto, and a crypto layer
+ * that cannot be executed is a crypto layer nobody has checked.
+ */
+
+// The framing, ahead of the compressed bytes and inside the AEAD. One byte, so
+// a later change to the compression or the padding can be told from a blob
+// written before it rather than mis-parsed into nonsense.
+const FORMAT_V1 = 1;
+
+// The plaintext is padded up to a multiple of this before sealing.
+const PAD_TO = 4096;
+
+// AES-GCM. Ninety-six random bits, **never** a counter: two devices of one
+// account derive the same playlist key — that is the entire point — so a
+// counter would repeat, and a repeated nonce under one key is the one thing
+// GCM does not survive. Same reasoning already recorded for chat subkeys.
+const NONCE_BYTES = 12;
+
+/**
+ * The playlist key, from the HKDF handle over the bundle key.
+ *
+ * A purpose-separated subkey rather than the bundle key reused with a different
+ * AAD — the rule `groupbox.py` writes down for chunk keys, for the same reason.
+ * v2 only: playlists are new, so there is no legacy blob and no v1 branch to
+ * take by mistake.
+ */
+async function derivePlaylistKey(hkdfHandle) {
+  return crypto.subtle.deriveKey(
+    {
+      name: 'HKDF', hash: 'SHA-256',
+      salt: new Uint8Array(0),
+      info: new TextEncoder().encode('meshbay:playlists:v1'),
+    },
+    hkdfHandle, { name: 'AES-GCM', length: 256 }, false, ['encrypt', 'decrypt']);
+}
+
+/**
+ * What binds a sealed blob to its owner and its kind.
+ *
+ * `kind` is in here, not just `"playlists"`, so one playlist's body cannot be
+ * served in place of another's — a substitution that a bare kind would have
+ * allowed the moment there was more than one row. Mirrors
+ * `groupbox.associated_data`. It cannot prevent rollback; §6.4 is what does.
+ */
+function associatedData(kind, userId) {
+  return new TextEncoder().encode(`user_blob|${kind}|${userId}`);
+}
+
+async function _deflate(bytes) {
+  const cs = new CompressionStream('deflate-raw');
+  const stream = new Blob([bytes]).stream().pipeThrough(cs);
+  return new Uint8Array(await new Response(stream).arrayBuffer());
+}
+
+async function _inflate(bytes) {
+  const ds = new DecompressionStream('deflate-raw');
+  const stream = new Blob([bytes]).stream().pipeThrough(ds);
+  return new Uint8Array(await new Response(stream).arrayBuffer());
+}
+
+/**
+ * One object as the bytes the node stores.
+ *
+ * Layout, all of it inside the AEAD except the nonce, which is prepended:
+ *
+ *     nonce(12) || AES-GCM( fmt(1) || len(4, BE) || deflate(json) || zeros )
+ *
+ * `len` is what lets the padding be stripped: the deflate stream would stop on
+ * its own, but a trailing run of zeros is a valid thing for the next reader to
+ * be confused by, and guessing is not a plan.
+ */
+async function seal(obj, kind, userId, key) {
+  const json = new TextEncoder().encode(JSON.stringify(obj));
+  const body = await _deflate(json);
+
+  const framed = new Uint8Array(5 + body.length);
+  framed[0] = FORMAT_V1;
+  new DataView(framed.buffer).setUint32(1, body.length, false);
+  framed.set(body, 5);
+
+  const padded = new Uint8Array(Math.ceil(framed.length / PAD_TO) * PAD_TO);
+  padded.set(framed);
+
+  const nonce = crypto.getRandomValues(new Uint8Array(NONCE_BYTES));
+  const ct = await crypto.subtle.encrypt(
+    { name: 'AES-GCM', iv: nonce, additionalData: associatedData(kind, userId) },
+    key, padded);
+
+  const out = new Uint8Array(NONCE_BYTES + ct.byteLength);
+  out.set(nonce);
+  out.set(new Uint8Array(ct), NONCE_BYTES);
+  return out;
+}
+
+/**
+ * The object back, or a throw.
+ *
+ * Every failure here throws rather than returning null: a blob that does not
+ * open is a wrong key, a tampered-with row or a kind served in place of
+ * another, and none of those should be quietly indistinguishable from "this
+ * account has no playlists yet" — which is what a `null` return would make them.
+ */
+async function open(bytes, kind, userId, key) {
+  const buf = bytes instanceof Uint8Array ? bytes : new Uint8Array(bytes);
+  if (buf.length <= NONCE_BYTES) throw new Error('playlist blob is truncated');
+
+  const plain = new Uint8Array(await crypto.subtle.decrypt(
+    { name: 'AES-GCM', iv: buf.slice(0, NONCE_BYTES),
+      additionalData: associatedData(kind, userId) },
+    key, buf.slice(NONCE_BYTES)));
+
+  if (plain[0] !== FORMAT_V1) {
+    throw new Error(`playlist blob format ${plain[0]} is not readable here`);
+  }
+  const len = new DataView(plain.buffer, plain.byteOffset).getUint32(1, false);
+  if (len > plain.length - 5) throw new Error('playlist blob length is wrong');
+
+  const json = await _inflate(plain.slice(5, 5 + len));
+  return JSON.parse(new TextDecoder().decode(json));
+}
+
+export {
+  FORMAT_V1, PAD_TO, NONCE_BYTES,
+  derivePlaylistKey, associatedData, seal, open,
+};
diff --git a/packages/meshbay-hub/src/meshbay_hub/static/playlist-merge.js b/packages/meshbay-hub/src/meshbay_hub/static/playlist-merge.js
new file mode 100644
index 0000000..ab67aa8
--- /dev/null
+++ b/packages/meshbay-hub/src/meshbay_hub/static/playlist-merge.js
@@ -0,0 +1,258 @@
+/**
+ * Playlists: the shapes, and reconciling N copies of them.
+ *
+ * `docs/playlists.md` §5 and §6. A playlist is stored as two things — one
+ * small **manifest** naming every playlist, and one **body** per playlist
+ * holding its tracks — and every device holds its own copy of both while
+ * nodes come and go. This is where the copies are put back together.
+ *
+ * The stated fear is correct for a single blob under last-writer-wins: node A
+ * is off while an edit is made, node B is off while the next one is, and one
+ * edit disappears with nothing to show for it. Four rules remove it, and they
+ * are the whole of this file:
+ *
+ *  - **The unit is one playlist, not the collection.** Two playlists edited on
+ *    two devices never collide.
+ *  - **Revision counters order writes, never the wall clock.** Clocks across
+ *    devices are not trustworthy, and `updated_at` is carried for display and
+ *    never read here.
+ *  - **A deletion is a tombstone, never an absence.** An absence means "this
+ *    copy is older than the one that created it". Drop that and a node rehomed
+ *    after three weeks resurrects every deleted playlist — the single most
+ *    likely defect in the design, and it looks like a sync working correctly
+ *    right up until it doesn't.
+ *  - **The client is the authority.** Merge takes the maximum across local
+ *    *plus* every node answering, so a node serving a stale copy can only lose
+ *    the tie. It can never lower the merged state.
+ *
+ * No imports, and there must be none: the whole module is executed standalone
+ * by `test_playlist_merge.py`, the way `source-merge.js` is. The merge is the
+ * one part of this feature that can be properly tested, and it is untested
+ * from the moment it cannot be executed.
+ *
+ * JSON, not msgpack, for what goes inside a blob. The node never parses it —
+ * it stores bytes — so the encoding is this client's private choice rather
+ * than a wire format, and MNP's codec is private to transport.js, which is a
+ * classic script and cannot be imported here. Keeping the payload in reach of
+ * `JSON.parse` is what lets this module be run by `node` with nothing around it.
+ */
+
+// The reserved playlist. Favourites is a playlist, not a second mechanism —
+// deciding that here is what stops a parallel store being built beside this
+// one in three months. It is never created by the user, is materialised on
+// first use, and cannot be deleted (which is what keeps the tombstone rule
+// above free of an exception).
+const FAVORITES_ID = 'favorites';
+
+const MANIFEST_KIND = 'playlists';
+const bodyKind = (id) => `playlist:${id}`;
+
+// What a stored track reference carries, and nothing else. The entries the UI
+// hands over are live objects: `_tRef` is a transport and `_gRef` a CryptoKey,
+// attached by the Search page's merge. JSON-encoding a transport throws at
+// best; storing a stale one and reading it back a week later is worse, because
+// it looks like a connection and is not.
+//
+// Short keys because the same eleven repeat on every entry — see docs §4.1 for
+// what one costs.
+const TRACK_FIELDS = ['id', 'g', 'hv', 'n', 's', 'p', 't', 'a', 'b', 'd', 'tn'];
+
+/**
+ * An index entry (plus its `groupId`) as a stored track reference.
+ *
+ * `s` and `n` are not optional and their absence is not cosmetic: the player
+ * computes its chunk count from `entry.size` and reads `entry.name` both for
+ * the MIME type and to decide whether the file needs the node-side conversion
+ * first. Without them a playlist entry cannot be downloaded at all.
+ */
+function toStored(entry, groupId) {
+  return {
+    id: entry.id,
+    g: entry.groupId || groupId || '',
+    hv: entry.hash_version || 1,
+    n: entry.name || '',
+    s: entry.size || 0,
+    p: entry.path || '',
+    t: entry.display_title || entry.name || '',
+    a: entry.artist || '',
+    b: entry.album || '',
+    d: entry.duration || 0,
+    tn: entry.track_no || 0,
+  };
+}
+
+/** A stored reference back in the shape the player and the views consume. */
+function fromStored(e) {
+  return {
+    id: e.id,
+    groupId: e.g,
+    hash_version: e.hv || 1,
+    name: e.n,
+    size: e.s,
+    path: e.p,
+    display_title: e.t || e.n,
+    artist: e.a || null,
+    album: e.b || null,
+    duration: e.d || 0,
+    track_no: e.tn || null,
+    type: 'audio',
+  };
+}
+
+function emptyManifest() {
+  return { v: 1, playlists: {} };
+}
+
+function emptyBody(id) {
+  return { v: 1, id, rev: 0, device: '', tracks: [] };
+}
+
+/**
+ * Which of two revisions of the same thing wins.
+ *
+ * The higher `rev`; a tie goes to the lexicographically smaller `device`, so
+ * every device reaches the same answer without talking to any other. A tie is
+ * two devices writing the same revision from the same starting point, and one
+ * of the two edits is lost — stated plainly in docs §6.5 rather than papered
+ * over, because the alternative is an OR-Set and a much larger design.
+ */
+function _wins(x, y) {
+  const rx = x.rev || 0;
+  const ry = y.rev || 0;
+  if (rx !== ry) return rx > ry ? x : y;
+  return String(x.device || '') <= String(y.device || '') ? x : y;
+}
+
+/**
+ * Two manifests into one, per playlist.
+ *
+ * Two counters, deliberately. `rev` governs what the manifest itself says — the
+ * name, and whether this playlist is deleted. `body_rev` is a **watermark**: the
+ * highest body revision anybody has seen, merged by taking the maximum and never
+ * decreasing, with `count` following whichever side carries it.
+ *
+ * One counter would be simpler and is wrong. Rename a playlist on one device
+ * while adding a track to it on another and both write revision n+1; a single
+ * counter makes those collide and one of the two is lost, for two edits that
+ * do not overlap at all. Two counters let them merge independently, which is
+ * the common case rather than an exotic one.
+ */
+function mergeManifests(a, b) {
+  const pa = (a && a.playlists) || {};
+  const pb = (b && b.playlists) || {};
+  const out = { v: 1, playlists: {} };
+  for (const id of new Set([...Object.keys(pa), ...Object.keys(pb)])) {
+    const ea = pa[id];
+    const eb = pb[id];
+    if (!ea || !eb) { out.playlists[id] = ea || eb; continue; }
+    const named = _wins(ea, eb);
+    // The body watermark moves on its own, and only ever forward.
+    const bodied = (eb.body_rev || 0) > (ea.body_rev || 0) ? eb : ea;
+    out.playlists[id] = {
+      ...named,
+      body_rev: bodied.body_rev || 0,
+      count: bodied.count || 0,
+    };
+  }
+  return out;
+}
+
+/**
+ * Two copies of one playlist's tracks into one.
+ *
+ * A body whose manifest entry is a tombstone is not resurrected here: the
+ * manifest is the authority on existence, and `liveBodies` below is what drops
+ * the orphans. Keeping that decision out of this function is deliberate —
+ * a body merge that also had to know about deletion would need the manifest
+ * passed to it, and the two would drift.
+ */
+function mergeBodies(a, b) {
+  if (!a) return b || null;
+  if (!b) return a;
+  return _wins(a, b);
+}
+
+/** Every merged copy folded together — local first, then whatever each node had. */
+function mergeAllManifests(copies) {
+  return (copies || []).filter(Boolean).reduce(mergeManifests, emptyManifest());
+}
+
+/**
+ * Is this playlist gone?
+ *
+ * A tombstone is `deleted: true`, kept. Collected only once every known node
+ * reports a `rev` at or above the deleting one — immediate for a single-node
+ * account, eventual for a multi-node one. A tombstone is about forty bytes, so
+ * there is no hurry, and hurrying is what resurrects playlists.
+ */
+function isDeleted(entry) {
+  return !!(entry && entry.deleted);
+}
+
+/** The playlists a reader should see, newest name order, favourites first. */
+function livePlaylists(manifest) {
+  const ps = (manifest && manifest.playlists) || {};
+  const live = Object.entries(ps)
+    .filter(([, e]) => !isDeleted(e))
+    .map(([id, e]) => ({ id, ...e }));
+  live.sort((x, y) => {
+    // Favourites is always first, as the menus promise, whatever it is called
+    // in this reader's language.
+    if (x.id === FAVORITES_ID) return -1;
+    if (y.id === FAVORITES_ID) return 1;
+    return String(x.name || '').localeCompare(String(y.name || ''));
+  });
+  return live;
+}
+
+/**
+ * Repair entries against a live index, once, on the client.
+ *
+ * Content addressing survives a move; a path survives a re-encode. Keeping
+ * both means either can repair the other — an entry whose `id` is no longer in
+ * the index but whose path and filename are gets its id rewritten, and an
+ * entry whose id is there under a different path gets its path rewritten.
+ *
+ * `index` is `{ byId: Map(id -> {p, n}), byPath: Map("p/n" -> id) }` for one
+ * group. Entries from other groups are left alone: this index says nothing
+ * about them, and "not in the index I happen to be holding" is not evidence
+ * that a track is gone.
+ */
+function repairTracks(tracks, groupId, index) {
+  let repaired = 0;
+  const out = (tracks || []).map((e) => {
+    if (e.g !== groupId) return e;
+    const here = index.byId.get(e.id);
+    if (here) {
+      if (here.p === e.p && here.n === e.n) return e;
+      repaired++;
+      return { ...e, p: here.p, n: here.n };
+    }
+    const byPath = index.byPath.get(`${e.p}/${e.n}`);
+    if (byPath && byPath !== e.id) {
+      repaired++;
+      return { ...e, id: byPath };
+    }
+    return e;
+  });
+  return { tracks: out, repaired };
+}
+
+/** The `{ byId, byPath }` shape repairTracks wants, from a group's entries. */
+function indexTracks(entries) {
+  const byId = new Map();
+  const byPath = new Map();
+  for (const e of entries || []) {
+    if (e.type !== 'audio') continue;
+    byId.set(e.id, { p: e.path || '', n: e.name || '' });
+    byPath.set(`${e.path || ''}/${e.name || ''}`, e.id);
+  }
+  return { byId, byPath };
+}
+
+export {
+  FAVORITES_ID, MANIFEST_KIND, bodyKind, TRACK_FIELDS,
+  toStored, fromStored, emptyManifest, emptyBody,
+  mergeManifests, mergeBodies, mergeAllManifests,
+  isDeleted, livePlaylists, repairTracks, indexTracks,
+};