~ knotless Search/
↑↓ move↵ open⇧↵ all results

chadtmiller.com/pds.js
Switch repository
Loading…

An atproto PDS in JavaScript, for Cloudflare Workers and Node

0
0
main
Switch branches or tags
2094 lines · 65.9 KB Raw History

Permissioned Data — Phase 1: Primitives Implementation Plan

For agentic workers: REQUIRED SUB-SKILL: Use superpowers:subagent-driven-development (recommended) or superpowers:executing-plans to implement this plan task-by-task. Steps use checkbox (- [ ]) syntax for tracking.

Goal: Build the cryptographic and addressing primitives for AT Protocol permissioned data — vendored BLAKE3 XOF, LtHash set hashing, signed commits, and space AT-URIs — in a new dependency-free @pdsjs/spaces package, verified byte-for-byte against vectors generated from the reference implementation.

Architecture: New workspace package packages/spaces with no external dependencies. BLAKE3 is hand-vendored (WebCrypto has no BLAKE3); everything else builds on crypto.subtle. Signature verification is a port — P-256 ships built in, secp256k1 is injected by the deployment. Nothing in this phase touches @pdsjs/core except adding JSDoc typedefs to ports.js.

Tech Stack: plain ESM JS + JSDoc types, vitest, biome (single quotes, 2-space indent), TDD per task, one commit per task.

Global Constraints

  • Spec: docs/superpowers/specs/2026-07-30-permissioned-data-design.md. Reference behavior is authoritative.
  • Reference pin: bluesky-social/atproto PR #5187, head 24a81bf5ab8d39557da35a4c4c0978c9aa62c45a. Fetched locally as branch pr-5187 in ~/code/atproto.
  • @pdsjs/spaces has zero external dependencies. Workspace-only dependency on @pdsjs/core. Do not add anything to package.json dependencies beyond "@pdsjs/core": "workspace:*".
  • @pdsjs/core must never import @pdsjs/spaces. Dependency direction is one-way.
  • All crypto except BLAKE3 uses crypto.subtle. Do not vendor a second hash.
  • Plain ESM JS with JSDoc type annotations. No TypeScript source files.
  • Tests live at packages/spaces/test/*.test.js (vitest include already covers packages/*/test/**/*.test.js).
  • Every task: failing test first, verify RED, minimal implementation, verify GREEN, npx biome check --write ., commit.
  • Branch: permissioned-data.

Task 1: Scaffold @pdsjs/spaces and vendor BLAKE3 XOF

Files:

  • Create: packages/spaces/package.json
  • Create: packages/spaces/src/blake3.js
  • Create: packages/spaces/src/index.js
  • Create: packages/spaces/test/blake3.test.js
  • Create: test/fixtures/blake3-vectors.json (downloaded)

Interfaces:

  • Consumes: nothing.

  • Produces: blake3(input: Uint8Array, outLen?: number) => Uint8Array — unkeyed BLAKE3 with extendable output. outLen defaults to 32. This is the only export of blake3.js.

  • Step 1: Create the package manifest

Create packages/spaces/package.json:

{
  "name": "@pdsjs/spaces",
  "version": "0.8.0",
  "type": "module",
  "main": "./src/index.js",
  "types": "./src/index.d.ts",
  "exports": {
    ".": "./src/index.js",
    "./blake3": "./src/blake3.js",
    "./lthash": "./src/lthash.js",
    "./path": "./src/path.js",
    "./uri": "./src/uri.js",
    "./mac": "./src/mac.js",
    "./verifier": "./src/verifier.js",
    "./commit": "./src/commit.js"
  },
  "dependencies": {
    "@pdsjs/core": "workspace:*"
  }
}

Create packages/spaces/src/index.js with a single line so the package resolves:

// @pdsjs/spaces - AT Protocol permissioned data (proposal 0016)
export { blake3 } from './blake3.js';

Run pnpm install to link the workspace package.

  • Step 2: Download the official BLAKE3 test vectors
mkdir -p test/fixtures
curl -sSL -o test/fixtures/blake3-vectors.json \
  https://raw.githubusercontent.com/BLAKE3-team/BLAKE3/master/test_vectors/test_vectors.json

The file has shape { key, context_string, cases: [{ input_len, hash, keyed_hash, derive_key }] }. Only input_len and hash matter here — hash is 131 bytes of extended output as hex (262 hex chars), which exercises the XOF path.

The input for a case of length n is the byte sequence i % 251 for i in [0, n). This is stated in the BLAKE3 repo's test_vectors/README.md.

Verify the download is non-empty and has cases:

node -e "const v=require('./test/fixtures/blake3-vectors.json'); console.log(v.cases.length, 'cases, lens:', v.cases.map(c=>c.input_len).join(','))"

Expected: a list including 0,1,2,3,4,5,6,7,8,63,64,65,127,128,129,1023,1024,1025,2048,2049,3072,3073,4096,4097,5120,6144,7168,8192,16384,31744,102400.

  • Step 3: Write the failing test

Create packages/spaces/test/blake3.test.js:

import { readFileSync } from 'node:fs';
import { describe, expect, it } from 'vitest';
import { blake3 } from '../src/blake3.js';

const vectors = JSON.parse(
  readFileSync(new URL('../../../test/fixtures/blake3-vectors.json', import.meta.url), 'utf8'),
);

/** Official BLAKE3 vector inputs are the repeating byte pattern i % 251. */
function vectorInput(len) {
  const bytes = new Uint8Array(len);
  for (let i = 0; i < len; i++) bytes[i] = i % 251;
  return bytes;
}

function toHex(bytes) {
  return Array.from(bytes)
    .map((b) => b.toString(16).padStart(2, '0'))
    .join('');
}

describe('blake3', () => {
  it('matches the official vectors at 32-byte output', () => {
    for (const c of vectors.cases) {
      const out = blake3(vectorInput(c.input_len), 32);
      expect(toHex(out), `input_len=${c.input_len}`).toBe(c.hash.slice(0, 64));
    }
  });

  it('matches the official vectors at extended output length', () => {
    for (const c of vectors.cases) {
      const outLen = c.hash.length / 2;
      const out = blake3(vectorInput(c.input_len), outLen);
      expect(toHex(out), `input_len=${c.input_len} outLen=${outLen}`).toBe(c.hash);
    }
  });

  it('produces 2048 bytes for LtHash expansion', () => {
    const out = blake3(new TextEncoder().encode('a'), 2048);
    expect(out.length).toBe(2048);
  });

  it('defaults to 32 bytes', () => {
    expect(blake3(new Uint8Array(0)).length).toBe(32);
  });
});
  • Step 4: Run test to verify it fails

Run: npx vitest run packages/spaces/test/blake3.test.js Expected: FAIL — Failed to resolve import "../src/blake3.js".

  • Step 5: Implement BLAKE3

Create packages/spaces/src/blake3.js. This is the only hand-rolled crypto in the tree; the file must open with a comment saying so and naming the vectors that gate it.

These constants are the error-prone part and must be exact:

// @pdsjs/spaces/blake3 - vendored BLAKE3 with extendable output.
//
// This is the only hand-written cryptographic primitive in pds.js. WebCrypto
// has no BLAKE3, and LtHash (proposal 0016) is defined in terms of it. Verified
// against the official BLAKE3 test vectors in test/fixtures/blake3-vectors.json;
// do not modify without re-running packages/spaces/test/blake3.test.js.

const IV = new Uint32Array([
  0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c,
  0x1f83d9ab, 0x5be0cd19,
]);

const MSG_PERMUTATION = [2, 6, 3, 10, 7, 0, 4, 13, 1, 11, 12, 5, 9, 14, 15, 8];

const CHUNK_START = 1 << 0;
const CHUNK_END = 1 << 1;
const PARENT = 1 << 2;
const ROOT = 1 << 3;

const BLOCK_LEN = 64;
const CHUNK_LEN = 1024;

The rest of the file:

const rotr = (x, n) => ((x >>> n) | (x << (32 - n))) >>> 0;

/** The quarter-round. Rotations are 16, 12, 8, 7. */
function g(s, a, b, c, d, mx, my) {
  s[a] = (s[a] + s[b] + mx) >>> 0;
  s[d] = rotr(s[d] ^ s[a], 16);
  s[c] = (s[c] + s[d]) >>> 0;
  s[b] = rotr(s[b] ^ s[c], 12);
  s[a] = (s[a] + s[b] + my) >>> 0;
  s[d] = rotr(s[d] ^ s[a], 8);
  s[c] = (s[c] + s[d]) >>> 0;
  s[b] = rotr(s[b] ^ s[c], 7);
}

/** Four column mixes then four diagonal mixes. */
function round(s, m) {
  g(s, 0, 4, 8, 12, m[0], m[1]);
  g(s, 1, 5, 9, 13, m[2], m[3]);
  g(s, 2, 6, 10, 14, m[4], m[5]);
  g(s, 3, 7, 11, 15, m[6], m[7]);
  g(s, 0, 5, 10, 15, m[8], m[9]);
  g(s, 1, 6, 11, 12, m[10], m[11]);
  g(s, 2, 7, 8, 13, m[12], m[13]);
  g(s, 3, 4, 9, 14, m[14], m[15]);
}

function permute(m) {
  const out = new Uint32Array(16);
  for (let i = 0; i < 16; i++) out[i] = m[MSG_PERMUTATION[i]];
  return out;
}

/**
 * @returns {Uint32Array} all 16 state words — the first 8 are the chaining
 * value, all 16 are needed for extended output.
 */
function compress(cv, block, counter, blockLen, flags) {
  const s = new Uint32Array(16);
  s.set(cv, 0);
  s[8] = IV[0];
  s[9] = IV[1];
  s[10] = IV[2];
  s[11] = IV[3];
  s[12] = counter >>> 0;
  s[13] = Math.floor(counter / 2 ** 32) >>> 0;
  s[14] = blockLen;
  s[15] = flags;

  let m = block;
  for (let i = 0; i < 7; i++) {
    round(s, m);
    if (i < 6) m = permute(m);
  }
  for (let i = 0; i < 8; i++) {
    s[i] = (s[i] ^ s[i + 8]) >>> 0;
    s[i + 8] = (s[i + 8] ^ cv[i]) >>> 0;
  }
  return s;
}

/** Read 16 little-endian uint32s from a 64-byte block. */
function wordsFromBlock(bytes, offset) {
  const m = new Uint32Array(16);
  for (let i = 0; i < 16; i++) {
    const o = offset + i * 4;
    m[i] =
      (bytes[o] |
        (bytes[o + 1] << 8) |
        (bytes[o + 2] << 16) |
        (bytes[o + 3] << 24)) >>>
      0;
  }
  return m;
}

// An Output is a deferred compression: the final block of a chunk or parent,
// not yet compressed, so the ROOT flag can still be applied to the last one.
function outputChainingValue(o) {
  return compress(o.cv, o.block, o.counter, o.blockLen, o.flags).slice(0, 8);
}

function rootOutputBytes(o, outLen) {
  const out = new Uint8Array(outLen);
  let i = 0;
  let counter = 0;
  while (i < outLen) {
    const words = compress(o.cv, o.block, counter, o.blockLen, o.flags | ROOT);
    for (let w = 0; w < 16 && i < outLen; w++) {
      for (let b = 0; b < 4 && i < outLen; b++) {
        out[i++] = (words[w] >>> (8 * b)) & 0xff;
      }
    }
    counter++;
  }
  return out;
}

function chunkOutput(input, start, len, chunkCounter) {
  let cv = IV.slice(0, 8);
  let blockFlags = CHUNK_START;
  let pos = 0;
  while (len - pos > BLOCK_LEN) {
    const m = wordsFromBlock(input, start + pos);
    cv = compress(cv, m, chunkCounter, BLOCK_LEN, blockFlags).slice(0, 8);
    pos += BLOCK_LEN;
    blockFlags = 0;
  }
  const blockLen = len - pos;
  const padded = new Uint8Array(BLOCK_LEN);
  padded.set(input.subarray(start + pos, start + len));
  return {
    cv,
    block: wordsFromBlock(padded, 0),
    counter: chunkCounter,
    blockLen,
    flags: blockFlags | CHUNK_END,
  };
}

function parentOutput(leftCv, rightCv) {
  const block = new Uint32Array(16);
  block.set(leftCv, 0);
  block.set(rightCv, 8);
  return {
    cv: IV.slice(0, 8),
    block,
    counter: 0,
    blockLen: BLOCK_LEN,
    flags: PARENT,
  };
}

/**
 * Unkeyed BLAKE3 with extendable output.
 * @param {Uint8Array} input
 * @param {number} [outLen] - output length in bytes, default 32
 * @returns {Uint8Array}
 */
export function blake3(input, outLen = 32) {
  const chunks = Math.max(1, Math.ceil(input.length / CHUNK_LEN));
  const stack = [];
  let output;

  for (let i = 0; i < chunks; i++) {
    const start = i * CHUNK_LEN;
    const len = Math.min(CHUNK_LEN, Math.max(0, input.length - start));
    const chunk = chunkOutput(input, start, len, i);

    // The last chunk stays an Output so the ROOT flag can reach it.
    if (i === chunks - 1) {
      output = chunk;
      break;
    }

    // Merge while the completed-chunk count has a trailing zero bit.
    let cv = outputChainingValue(chunk);
    let n = i + 1;
    while ((n & 1) === 0) {
      cv = outputChainingValue(parentOutput(stack.pop(), cv));
      n >>= 1;
    }
    stack.push(cv);
  }

  while (stack.length > 0) {
    output = parentOutput(stack.pop(), outputChainingValue(output));
  }
  return rootOutputBytes(output, outLen);
}

The single-chunk shortcut is not sufficient: the vectors include inputs up to 102400 bytes, so the tree path must work.

  • Step 6: Run test to verify it passes

Run: npx vitest run packages/spaces/test/blake3.test.js Expected: PASS, 4 tests.

If the 32-byte test passes but the extended-output test fails, the bug is in the root output-block counter (step 7). If short inputs pass and inputs ≥ 1024 fail, the bug is in the CV stack merge (step 6).

  • Step 7: Format and commit
npx biome check --write packages/spaces test/fixtures
git add packages/spaces test/fixtures/blake3-vectors.json pnpm-lock.yaml
git commit -m "feat(spaces): scaffold @pdsjs/spaces with vendored BLAKE3 XOF"

Task 2: Generate reference vectors

Files:

  • Create: scripts/gen-space-vectors.md (documented procedure)
  • Create: test/fixtures/space-vectors.json (generated, committed)

Interfaces:

  • Consumes: nothing from earlier tasks.
  • Produces: test/fixtures/space-vectors.json with this exact shape, consumed by Tasks 3, 6, and 7:
{
  "generatedFrom": {
    "repo": "bluesky-social/atproto",
    "pr": 5187,
    "sha": "24a81bf5ab8d39557da35a4c4c0978c9aa62c45a"
  },
  "lthash": {
    "empty": { "stateHex": "…", "digestHex": "…" },
    "single": [{ "element": "…", "stateHex": "…", "digestHex": "…" }],
    "sets": [{ "elements": ["…"], "digestHex": "…" }]
  },
  "commitCtx": [
    { "space": "…", "author": "…", "rev": "…", "ikmHex": "…", "ctxHex": "…" }
  ],
  "signedCommits": [
    {
      "didKey": "did:key:z…",
      "ctx": { "space": "…", "author": "…", "rev": "…" },
      "records": [{ "collection": "…", "rkey": "…", "cid": "…" }],
      "commit": { "ver": 1, "hashHex": "…", "ikmHex": "…", "sigHex": "…", "macHex": "…", "rev": "…" }
    }
  ]
}
  • Step 1: Create an isolated worktree of the reference

The ~/code/atproto checkout has uncommitted work on another branch. Do not check out pr-5187 in place.

cd ~/code/atproto
git worktree add ~/code/atproto-space-ref pr-5187
cd ~/code/atproto-space-ref
pnpm install --frozen-lockfile

Verify the space package is present:

ls packages/space/src

Expected: index.ts, lthash.ts, repo-commit.ts, types.ts, util.ts, and others.

  • Step 2: Write the generator as a vitest test inside the worktree

packages/space is a registered vitest project, so a test file runs the TypeScript sources directly with no build step.

Create ~/code/atproto-space-ref/packages/space/tests/gen-vectors.test.ts (untracked scratch file in the worktree — it is never committed to atproto):

import { writeFileSync } from 'node:fs'
import { P256Keypair } from '@atproto/crypto'
import { parseCid } from '@atproto/lex-data'
import { it } from 'vitest'
import { LtHash, RepoCommit, encodeCommitCtx } from '../src/index.js'

const OUT = process.env.VECTORS_OUT
const hex = (b: Uint8Array) => Buffer.from(b).toString('hex')

// Substitute two real CIDs — see Step 2a. Placeholder strings will fail to
// parse and the generator will throw rather than emit bad vectors.
const CID_A = process.env.CID_A!
const CID_B = process.env.CID_B!

const ELEMENTS = [
  'a',
  'app.example.post/3kabcdefghi/' + CID_A,
  'com.atmoboards.thread/self/' + CID_B,
]

it('generates vectors', async () => {
  const lthashSingle = ELEMENTS.map((element) => {
    const h = new LtHash().add(element)
    return { element, stateHex: hex(h.state()), digestHex: hex(h.digest()) }
  })

  const sets = [
    { elements: [ELEMENTS[0], ELEMENTS[1]] },
    { elements: [ELEMENTS[1], ELEMENTS[0]] },
    { elements: ELEMENTS },
  ].map(({ elements }) => {
    const h = new LtHash()
    for (const e of elements) h.add(e)
    return { elements, digestHex: hex(h.digest()) }
  })

  const empty = new LtHash()

  const ctxCases = [
    { space: 'at://did:plc:aaaa/space/com.example.type/key1', author: 'did:plc:bbbb', rev: '3lkabcdefgh2x' },
    { space: 'at://did:plc:cccc/space/com.atmoboards.forum/general', author: 'did:plc:dddd', rev: '3lkzzzzzzzz2x' },
  ]
  const commitCtx = ctxCases.map((c, i) => {
    const ikm = new Uint8Array(32).fill(i + 1)
    return { ...c, ikmHex: hex(ikm), ctxHex: hex(encodeCommitCtx(c, ikm)) }
  })

  const keypair = await P256Keypair.create({ exportable: true })
  const records = [
    { collection: 'app.example.post', rkey: '3kabcdefghi', cid: CID_A },
    { collection: 'com.atmoboards.thread', rkey: 'self', cid: CID_B },
  ]
  const repo = RepoCommit.fromRecords(
    records.map((r) => ({ ...r, cid: parseCid(r.cid) })),
  )
  const ctx = ctxCases[0]
  const signed = await repo.sign(ctx, keypair)

  const out = {
    generatedFrom: {
      repo: 'bluesky-social/atproto',
      pr: 5187,
      sha: process.env.REF_SHA,
    },
    lthash: {
      empty: { stateHex: hex(empty.state()), digestHex: hex(empty.digest()) },
      single: lthashSingle,
      sets,
    },
    commitCtx,
    signedCommits: [
      {
        didKey: keypair.did(),
        ctx,
        records,
        commit: {
          ver: signed.ver,
          hashHex: hex(signed.hash),
          ikmHex: hex(signed.ikm),
          sigHex: hex(signed.sig),
          macHex: hex(signed.mac),
          rev: signed.rev,
        },
      },
    ],
  }

  writeFileSync(OUT!, JSON.stringify(out, null, 2) + '\n')
})

If parseCid is not the correct export name in @atproto/lex-data, check packages/lex/lex-data/src/index.ts in the worktree and use the exported CID parser. The generator must fail loudly rather than emit placeholder CIDs.

  • Step 2a: Source two real CIDs

Do not invent CID strings — an invalid CID either throws in the generator or, worse, produces vectors pds.js can reproduce but the reference cannot. Take two real ones from the reference's own fixtures:

cd ~/code/atproto-space-ref
grep -rhoE 'bafyrei[a-z2-7]{52}' packages --include='*.ts' --include='*.json' | sort -u | head -2

If that yields fewer than two, generate them in the worktree instead:

npx vitest run --reporter=basic --testNamePattern='__cids__' \
  --root . packages/space 2>/dev/null || true

and failing that, add a throwaway test in the worktree that CBOR-encodes two small objects with the reference's own helpers and prints the resulting CIDs. Whatever the source, the two values must round-trip through the reference's CID parser before use.

Export them for the next step:

export CID_A=<first cid>
export CID_B=<second cid>
  • Step 3: Run the generator
cd ~/code/atproto-space-ref
REF_SHA=$(git rev-parse HEAD) \
CID_A=$CID_A CID_B=$CID_B \
VECTORS_OUT=~/code/pds.js/test/fixtures/space-vectors.json \
  npx vitest run packages/space/tests/gen-vectors.test.ts

Expected: PASS, and the fixture written.

  • Step 4: Verify the fixture
cd ~/code/pds.js
node -e "
const v = require('./test/fixtures/space-vectors.json');
console.log('sha', v.generatedFrom.sha);
console.log('empty state all-zero:', /^0+$/.test(v.lthash.empty.stateHex));
console.log('state bytes:', v.lthash.single[0].stateHex.length / 2);
console.log('order-independent:', v.lthash.sets[0].digestHex === v.lthash.sets[1].digestHex);
console.log('ctx cases:', v.commitCtx.length, 'commits:', v.signedCommits.length);
"

Expected: sha is the pinned SHA, empty state is all zeros, state is 2048 bytes, the two reordered sets share a digest, 2 ctx cases, 1 signed commit.

If order-independence is false, the generator is wrong — stop and fix it before proceeding, because every downstream task trusts this file.

  • Step 5: Document the regeneration procedure

Create scripts/gen-space-vectors.md recording: why the worktree exists, the exact commands from Steps 1–3, and the rule that regenerating this fixture is how pds.js resyncs with upstream. State that generatedFrom.sha must be updated in the spec's §0 pin whenever the fixture is regenerated.

  • Step 6: Commit
npx biome check --write scripts test/fixtures
git add test/fixtures/space-vectors.json scripts/gen-space-vectors.md
git commit -m "test(spaces): reference vectors generated from atproto PR #5187"

Task 3: LtHash

Files:

  • Create: packages/spaces/src/lthash.js
  • Create: packages/spaces/test/lthash.test.js
  • Modify: packages/spaces/src/index.js

Interfaces:

  • Consumes: blake3(input, outLen) from Task 1; test/fixtures/space-vectors.json from Task 2.

  • Produces:

    • LTHASH_STATE_BYTES = 2048
    • class LtHash with constructor(state?: Uint8Array | null), add(element: string): this, remove(element: string): this, state(): Uint8Array, digest(): Promise<Uint8Array>, isEmpty(): boolean, equals(other: LtHash): boolean.
    • digest() is async — it uses crypto.subtle.digest('SHA-256', …). This differs from the reference's synchronous digest() and is deliberate (spec §2).

  • Step 1: Write the failing test

Create packages/spaces/test/lthash.test.js:

import { readFileSync } from 'node:fs';
import { describe, expect, it } from 'vitest';
import { LTHASH_STATE_BYTES, LtHash } from '../src/lthash.js';

const vectors = JSON.parse(
  readFileSync(new URL('../../../test/fixtures/space-vectors.json', import.meta.url), 'utf8'),
);

const toHex = (bytes) =>
  Array.from(bytes)
    .map((b) => b.toString(16).padStart(2, '0'))
    .join('');

describe('LtHash', () => {
  it('starts as 2048 zero bytes', () => {
    const h = new LtHash();
    expect(h.state()).toEqual(new Uint8Array(LTHASH_STATE_BYTES));
    expect(h.isEmpty()).toBe(true);
  });

  it('rejects a state of the wrong length', () => {
    expect(() => new LtHash(new Uint8Array(10))).toThrow(/2048/);
  });

  it('add then remove returns to the zero state', () => {
    const h = new LtHash().add('a');
    expect(h.isEmpty()).toBe(false);
    h.remove('a');
    expect(h.isEmpty()).toBe(true);
  });

  it('is order-independent', async () => {
    const a = new LtHash().add('a').add('b');
    const b = new LtHash().add('b').add('a');
    expect(a.equals(b)).toBe(true);
    expect(await a.digest()).toEqual(await b.digest());
  });

  it('distinguishes different elements', () => {
    expect(new LtHash().add('a').equals(new LtHash().add('b'))).toBe(false);
  });

  it('round-trips through state()', () => {
    const h = new LtHash().add('a').add('b');
    expect(new LtHash(h.state()).equals(h)).toBe(true);
  });

  it('matches the reference empty state', async () => {
    const h = new LtHash();
    expect(toHex(h.state())).toBe(vectors.lthash.empty.stateHex);
    expect(toHex(await h.digest())).toBe(vectors.lthash.empty.digestHex);
  });

  it('matches the reference for single elements', async () => {
    for (const c of vectors.lthash.single) {
      const h = new LtHash().add(c.element);
      expect(toHex(h.state()), c.element).toBe(c.stateHex);
      expect(toHex(await h.digest()), c.element).toBe(c.digestHex);
    }
  });

  it('matches the reference for element sets', async () => {
    for (const c of vectors.lthash.sets) {
      const h = new LtHash();
      for (const e of c.elements) h.add(e);
      expect(toHex(await h.digest()), c.elements.join(',')).toBe(c.digestHex);
    }
  });
});
  • Step 2: Run test to verify it fails

Run: npx vitest run packages/spaces/test/lthash.test.js Expected: FAIL — Failed to resolve import "../src/lthash.js".

  • Step 3: Implement LtHash

Create packages/spaces/src/lthash.js:

// @pdsjs/spaces/lthash - homomorphic set hash for permissioned repo commits.

import { blake3 } from './blake3.js';

const LANES = 1024;
const LANE_BYTES = 2; // cannot change without reworking the Uint16Array impl
export const LTHASH_STATE_BYTES = LANES * LANE_BYTES; // 2048

/**
 * A homomorphic set hash. Each element expands to 1024 little-endian u16 lanes
 * summed into the state mod 2^16. Addition and subtraction commute, so the state
 * depends only on the current set, not on insertion order.
 */
export class LtHash {
  /** @param {Uint8Array|null} [state] */
  constructor(state) {
    if (state && state.length !== LTHASH_STATE_BYTES) {
      throw new Error(
        `LtHash state must be ${LTHASH_STATE_BYTES} bytes, got ${state.length}`,
      );
    }
    const buffer = new ArrayBuffer(LTHASH_STATE_BYTES);
    this.bytes = new Uint8Array(buffer);
    this.lanes = new Uint16Array(buffer);
    if (state) this.bytes.set(state);
  }

  /** @param {string} element @returns {this} */
  add(element) {
    const lanes = expand(element);
    for (let i = 0; i < LANES; i++) this.lanes[i] += lanes[i];
    return this;
  }

  /** @param {string} element @returns {this} */
  remove(element) {
    const lanes = expand(element);
    for (let i = 0; i < LANES; i++) this.lanes[i] -= lanes[i];
    return this;
  }

  /** @returns {Uint8Array} the full state, for persistence */
  state() {
    return new Uint8Array(this.bytes);
  }

  /** @returns {Promise<Uint8Array>} */
  async digest() {
    const hash = await crypto.subtle.digest('SHA-256', this.bytes);
    return new Uint8Array(hash);
  }

  /** @returns {boolean} */
  isEmpty() {
    for (let i = 0; i < LANES; i++) if (this.lanes[i] !== 0) return false;
    return true;
  }

  /** @param {LtHash} other @returns {boolean} */
  equals(other) {
    for (let i = 0; i < LANES; i++) {
      if (this.lanes[i] !== other.lanes[i]) return false;
    }
    return true;
  }
}

/**
 * Expand an element to 1024 little-endian u16 lanes with BLAKE3 in XOF mode.
 * @param {string} element
 * @returns {Uint16Array}
 */
function expand(element) {
  const expanded = blake3(new TextEncoder().encode(element), LTHASH_STATE_BYTES);
  const buffer = new ArrayBuffer(LTHASH_STATE_BYTES);
  new Uint8Array(buffer).set(expanded);
  return new Uint16Array(buffer);
}

Uint16Array on a little-endian host reads the buffer little-endian, which matches the spec. Do not add byte-swapping.

  • Step 4: Run test to verify it passes

Run: npx vitest run packages/spaces/test/lthash.test.js Expected: PASS, 9 tests.

If the structural tests pass but the reference-vector tests fail, the bug is in blake3, not here — the lane arithmetic has no other degrees of freedom.

  • Step 5: Export from the package index

Modify packages/spaces/src/index.js:

// @pdsjs/spaces - AT Protocol permissioned data (proposal 0016)
export { blake3 } from './blake3.js';
export { LTHASH_STATE_BYTES, LtHash } from './lthash.js';
  • Step 6: Format and commit
npx biome check --write packages/spaces
git add packages/spaces
git commit -m "feat(spaces): LtHash homomorphic set hash"

Task 4: Record path and set-hash element helpers

Files:

  • Create: packages/spaces/src/path.js
  • Create: packages/spaces/test/path.test.js
  • Modify: packages/spaces/src/index.js

Interfaces:

  • Consumes: nothing.

  • Produces:

    • formatRecordPath(collection: string, rkey: string) => string — "{collection}/{rkey}"
    • parseRecordPath(path: string) => { collection: string, rkey: string } — throws on a path that is not exactly two segments
    • formatSetHashElement(collection: string, rkey: string, cid: string) => string — "{collection}/{rkey}/{cid}", the element folded into LtHash

  • Step 1: Write the failing test

Create packages/spaces/test/path.test.js:

import { describe, expect, it } from 'vitest';
import {
  formatRecordPath,
  formatSetHashElement,
  parseRecordPath,
} from '../src/path.js';

describe('record paths', () => {
  it('formats a record path', () => {
    expect(formatRecordPath('app.example.post', '3kabc')).toBe(
      'app.example.post/3kabc',
    );
  });

  it('parses a record path', () => {
    expect(parseRecordPath('app.example.post/3kabc')).toEqual({
      collection: 'app.example.post',
      rkey: '3kabc',
    });
  });

  it('round-trips', () => {
    const path = formatRecordPath('com.atmoboards.thread', 'self');
    expect(formatRecordPath(...Object.values(parseRecordPath(path)))).toBe(path);
  });

  it('rejects paths without exactly two segments', () => {
    expect(() => parseRecordPath('only-one')).toThrow(/invalid record path/);
    expect(() => parseRecordPath('a/b/c')).toThrow(/invalid record path/);
    expect(() => parseRecordPath('')).toThrow(/invalid record path/);
  });

  it('formats a set hash element', () => {
    expect(
      formatSetHashElement('app.example.post', '3kabc', 'bafyreiabc'),
    ).toBe('app.example.post/3kabc/bafyreiabc');
  });
});
  • Step 2: Run test to verify it fails

Run: npx vitest run packages/spaces/test/path.test.js Expected: FAIL — Failed to resolve import "../src/path.js".

  • Step 3: Implement

Create packages/spaces/src/path.js:

// @pdsjs/spaces/path - record path and set hash element formatting.

/**
 * @param {string} collection
 * @param {string} rkey
 * @returns {string}
 */
export function formatRecordPath(collection, rkey) {
  return `${collection}/${rkey}`;
}

/**
 * @param {string} path
 * @returns {{collection: string, rkey: string}}
 */
export function parseRecordPath(path) {
  const parts = path.split('/');
  if (parts.length !== 2 || !parts[0] || !parts[1]) {
    throw new Error(`invalid record path: ${path}`);
  }
  return { collection: parts[0], rkey: parts[1] };
}

/**
 * The element a record contributes to a repo's set hash.
 * @param {string} collection
 * @param {string} rkey
 * @param {string} cid
 * @returns {string}
 */
export function formatSetHashElement(collection, rkey, cid) {
  return `${collection}/${rkey}/${cid}`;
}
  • Step 4: Run test to verify it passes

Run: npx vitest run packages/spaces/test/path.test.js Expected: PASS, 5 tests.

  • Step 5: Export and commit

Add to packages/spaces/src/index.js:

export {
  formatRecordPath,
  formatSetHashElement,
  parseRecordPath,
} from './path.js';

npx biome check --write packages/spaces
git add packages/spaces
git commit -m "feat(spaces): record path and set hash element helpers"

Task 5: Space AT-URIs

Files:

  • Create: packages/spaces/src/uri.js
  • Create: packages/spaces/test/uri.test.js
  • Modify: packages/spaces/src/index.js

Interfaces:

  • Consumes: nothing.

  • Produces:

    • SPACE_MARKER = 'space'
    • formatSpaceUri({ spaceDid, spaceType, skey, authorDid?, collection?, rkey? }) => string
    • parseSpaceUri(uri: string) => { spaceDid, spaceType, skey, authorDid: string|null, collection: string|null, rkey: string|null } — throws Error on a non-space or malformed URI
    • isSpaceUri(uri: string) => boolean

  • Step 1: Write the failing test

Create packages/spaces/test/uri.test.js:

import { describe, expect, it } from 'vitest';
import { formatSpaceUri, isSpaceUri, parseSpaceUri } from '../src/uri.js';

const SPACE = 'at://did:plc:aaaa/space/com.atmoboards.forum/general';
const FULL = `${SPACE}/did:plc:bbbb/com.atmoboards.thread/3kabc`;

describe('space URIs', () => {
  it('formats a bare space URI', () => {
    expect(
      formatSpaceUri({
        spaceDid: 'did:plc:aaaa',
        spaceType: 'com.atmoboards.forum',
        skey: 'general',
      }),
    ).toBe(SPACE);
  });

  it('formats a full record URI', () => {
    expect(
      formatSpaceUri({
        spaceDid: 'did:plc:aaaa',
        spaceType: 'com.atmoboards.forum',
        skey: 'general',
        authorDid: 'did:plc:bbbb',
        collection: 'com.atmoboards.thread',
        rkey: '3kabc',
      }),
    ).toBe(FULL);
  });

  it('parses a bare space URI', () => {
    expect(parseSpaceUri(SPACE)).toEqual({
      spaceDid: 'did:plc:aaaa',
      spaceType: 'com.atmoboards.forum',
      skey: 'general',
      authorDid: null,
      collection: null,
      rkey: null,
    });
  });

  it('parses a full record URI', () => {
    expect(parseSpaceUri(FULL)).toEqual({
      spaceDid: 'did:plc:aaaa',
      spaceType: 'com.atmoboards.forum',
      skey: 'general',
      authorDid: 'did:plc:bbbb',
      collection: 'com.atmoboards.thread',
      rkey: '3kabc',
    });
  });

  it('round-trips', () => {
    expect(formatSpaceUri(parseSpaceUri(FULL))).toBe(FULL);
    expect(formatSpaceUri(parseSpaceUri(SPACE))).toBe(SPACE);
  });

  it('recognises space URIs by the marker segment', () => {
    expect(isSpaceUri(SPACE)).toBe(true);
    expect(isSpaceUri(FULL)).toBe(true);
    // Public repo URI: the first path segment is a collection NSID, which
    // always contains dots. The space marker never does.
    expect(isSpaceUri('at://did:plc:aaaa/app.bsky.feed.post/3kabc')).toBe(false);
    expect(isSpaceUri('at://did:plc:aaaa')).toBe(false);
  });

  it('rejects malformed space URIs', () => {
    expect(() => parseSpaceUri('at://did:plc:aaaa/app.bsky.feed.post/3k')).toThrow();
    // missing skey
    expect(() => parseSpaceUri('at://did:plc:aaaa/space/com.example.t')).toThrow();
    // author present but collection/rkey truncated
    expect(() => parseSpaceUri(`${SPACE}/did:plc:bbbb/com.example.c`)).toThrow();
    // non-DID authority
    expect(() => parseSpaceUri('at://alice.test/space/com.example.t/k')).toThrow();
  });

  it('rejects a space type that is not an NSID', () => {
    expect(() => parseSpaceUri('at://did:plc:aaaa/space/nodots/k')).toThrow();
  });
});
  • Step 2: Run test to verify it fails

Run: npx vitest run packages/spaces/test/uri.test.js Expected: FAIL — Failed to resolve import "../src/uri.js".

  • Step 3: Implement

Create packages/spaces/src/uri.js. The addressing scheme is:

at://{spaceDid}/space/{spaceType}/{skey}[/{authorDid}/{collection}/{rkey}]

Valid segment counts after the host are exactly 3 (bare space) or 6 (full record). Anything else is malformed. Validate that spaceDid and authorDid start with did:, and that spaceType and collection contain at least one dot (the NSID property the marker relies on).

// @pdsjs/spaces/uri - permissioned space AT-URI addressing.
//
//   at://{spaceDid}/space/{spaceType}/{skey}[/{authorDid}/{collection}/{rkey}]
//
// Space URIs are distinguished from public ones by the literal `space` segment,
// which contains no dots, whereas a collection NSID always contains at least two.

export const SPACE_MARKER = 'space';

/**
 * @param {{spaceDid: string, spaceType: string, skey: string,
 *          authorDid?: string|null, collection?: string|null, rkey?: string|null}} parts
 * @returns {string}
 */
export function formatSpaceUri(parts) {
  const { spaceDid, spaceType, skey, authorDid, collection, rkey } = parts;
  let uri = `at://${spaceDid}/${SPACE_MARKER}/${spaceType}/${skey}`;
  if (authorDid) uri += `/${authorDid}`;
  if (collection) uri += `/${collection}`;
  if (rkey) uri += `/${rkey}`;
  return uri;
}

/**
 * @param {string} uri
 * @returns {boolean}
 */
export function isSpaceUri(uri) {
  const segments = splitUri(uri);
  return segments !== null && segments[1] === SPACE_MARKER;
}

/**
 * @param {string} uri
 * @returns {{spaceDid: string, spaceType: string, skey: string,
 *            authorDid: string|null, collection: string|null, rkey: string|null}}
 */
export function parseSpaceUri(uri) {
  const segments = splitUri(uri);
  if (segments === null || segments[1] !== SPACE_MARKER) {
    throw new Error(`not a space URI: ${uri}`);
  }
  const [spaceDid, , spaceType, skey, authorDid, collection, rkey] = segments;
  if (segments.length !== 4 && segments.length !== 7) {
    throw new Error(`invalid space URI: ${uri}`);
  }
  if (!spaceDid.startsWith('did:')) {
    throw new Error(`space authority must be a DID: ${uri}`);
  }
  if (!spaceType.includes('.')) {
    throw new Error(`space type must be an NSID: ${uri}`);
  }
  if (!skey) throw new Error(`invalid space URI: ${uri}`);
  if (segments.length === 4) {
    return { spaceDid, spaceType, skey, authorDid: null, collection: null, rkey: null };
  }
  if (!authorDid.startsWith('did:')) {
    throw new Error(`space record author must be a DID: ${uri}`);
  }
  if (!collection.includes('.')) {
    throw new Error(`collection must be an NSID: ${uri}`);
  }
  if (!rkey) throw new Error(`invalid space URI: ${uri}`);
  return { spaceDid, spaceType, skey, authorDid, collection, rkey };
}

/**
 * @param {string} uri
 * @returns {string[]|null} host followed by path segments, or null if not an at:// URI
 */
function splitUri(uri) {
  if (!uri.startsWith('at://')) return null;
  const segments = uri.slice('at://'.length).split('/');
  if (segments.length < 2 || segments.some((s) => s === '')) return null;
  return segments;
}
  • Step 4: Run test to verify it passes

Run: npx vitest run packages/spaces/test/uri.test.js Expected: PASS, 8 tests.

  • Step 5: Export and commit

Add to packages/spaces/src/index.js:

export { SPACE_MARKER, formatSpaceUri, isSpaceUri, parseSpaceUri } from './uri.js';

npx biome check --write packages/spaces
git add packages/spaces
git commit -m "feat(spaces): space AT-URI parsing and formatting"

Task 6: Commit context encoding and MAC

Files:

  • Create: packages/spaces/src/mac.js
  • Create: packages/spaces/test/mac.test.js
  • Modify: packages/spaces/src/index.js

Interfaces:

  • Consumes: test/fixtures/space-vectors.json from Task 2.
  • Produces:
    • COMMIT_VERSION = 1
    • encodeCommitCtx(ctx: {space, author, rev}, ikm: Uint8Array) => Uint8Array
    • hmacSha256(key: Uint8Array, data: Uint8Array) => Promise<Uint8Array>
    • hkdfExpandSha256(ikm: Uint8Array, info: Uint8Array) => Promise<Uint8Array> — 32 bytes
    • computeMac(ikm: Uint8Array, ctxBytes: Uint8Array, hash: Uint8Array) => Promise<Uint8Array>
    • bytesEqual(a: Uint8Array, b: Uint8Array) => boolean — length-checked

Critical detail: the reference's hkdfSha256(ikm, info) is expand(sha256, ikm, info, 32) — HKDF-Expand only, with ikm used directly as the PRK. crypto.subtle.deriveBits({name:'HKDF'}) performs extract and expand and will not match. Because the output length equals the hash length, expand collapses to a single block:

hkdfExpandSha256(ikm, info) = HMAC-SHA256(ikm, info || 0x01)
  • Step 1: Write the failing test

Create packages/spaces/test/mac.test.js:

import { readFileSync } from 'node:fs';
import { describe, expect, it } from 'vitest';
import {
  COMMIT_VERSION,
  bytesEqual,
  computeMac,
  encodeCommitCtx,
  hkdfExpandSha256,
  hmacSha256,
} from '../src/mac.js';

const vectors = JSON.parse(
  readFileSync(new URL('../../../test/fixtures/space-vectors.json', import.meta.url), 'utf8'),
);

const toHex = (b) =>
  Array.from(b)
    .map((x) => x.toString(16).padStart(2, '0'))
    .join('');
const fromHex = (h) =>
  new Uint8Array(h.match(/../g).map((x) => parseInt(x, 16)));

describe('encodeCommitCtx', () => {
  it('matches the reference vectors byte for byte', () => {
    for (const c of vectors.commitCtx) {
      const out = encodeCommitCtx(
        { space: c.space, author: c.author, rev: c.rev },
        fromHex(c.ikmHex),
      );
      expect(toHex(out), c.space).toBe(c.ctxHex);
    }
  });

  it('starts with the domain prefix', () => {
    const out = encodeCommitCtx(
      { space: 'at://did:plc:a/space/com.e.t/k', author: 'did:plc:b', rev: '3l' },
      new Uint8Array(32),
    );
    expect(new TextDecoder().decode(out.slice(0, 16))).toBe('atproto-space-v1');
  });

  it('uses big-endian uint16 length prefixes', () => {
    const out = encodeCommitCtx(
      { space: 'ab', author: 'c', rev: 'd' },
      new Uint8Array(1),
    );
    // prefix(16) | 0x0000 0x0002 'ab' | 0x0000 0x0001 'c' | ...
    expect(out[16]).toBe(0x00);
    expect(out[17]).toBe(0x02);
    expect(String.fromCharCode(out[18], out[19])).toBe('ab');
  });

  it('rejects a field longer than uint16', () => {
    expect(() =>
      encodeCommitCtx(
        { space: 'x'.repeat(0x10000), author: 'a', rev: 'b' },
        new Uint8Array(0),
      ),
    ).toThrow(/uint16/);
  });
});

describe('mac', () => {
  it('hkdfExpandSha256 is a single HMAC block', async () => {
    const ikm = new Uint8Array(32).fill(7);
    const info = new TextEncoder().encode('info');
    const expected = await hmacSha256(
      ikm,
      new Uint8Array([...info, 0x01]),
    );
    expect(await hkdfExpandSha256(ikm, info)).toEqual(expected);
  });

  it('reproduces the reference commit MAC', async () => {
    for (const c of vectors.signedCommits) {
      const ctxBytes = encodeCommitCtx(c.ctx, fromHex(c.commit.ikmHex));
      const mac = await computeMac(
        fromHex(c.commit.ikmHex),
        ctxBytes,
        fromHex(c.commit.hashHex),
      );
      expect(toHex(mac)).toBe(c.commit.macHex);
    }
  });
});

describe('bytesEqual', () => {
  it('compares by length and content', () => {
    expect(bytesEqual(new Uint8Array([1, 2]), new Uint8Array([1, 2]))).toBe(true);
    expect(bytesEqual(new Uint8Array([1, 2]), new Uint8Array([1, 3]))).toBe(false);
    expect(bytesEqual(new Uint8Array([1]), new Uint8Array([1, 2]))).toBe(false);
  });
});

describe('COMMIT_VERSION', () => {
  it('is 1', () => {
    expect(COMMIT_VERSION).toBe(1);
  });
});
  • Step 2: Run test to verify it fails

Run: npx vitest run packages/spaces/test/mac.test.js Expected: FAIL — Failed to resolve import "../src/mac.js".

  • Step 3: Implement

Create packages/spaces/src/mac.js:

// @pdsjs/spaces/mac - commit context encoding and deniable-signature MAC.

export const COMMIT_VERSION = 1;

const DOMAIN_PREFIX = new TextEncoder().encode('atproto-space-v1');

/**
 * ctx = "atproto-space-v1"
 *    || uint16be(len(space))  || space
 *    || uint16be(len(author)) || author
 *    || uint16be(len(rev))    || rev
 *    || uint16be(len(ikm))    || ikm
 *
 * Length prefixes are big-endian per the TLS variable-length vector convention,
 * deliberately the opposite byte order from the set hash's lanes.
 *
 * @param {{space: string, author: string, rev: string}} ctx
 * @param {Uint8Array} ikm
 * @returns {Uint8Array}
 */
export function encodeCommitCtx(ctx, ikm) {
  const encoder = new TextEncoder();
  const fields = [
    encoder.encode(ctx.space),
    encoder.encode(ctx.author),
    encoder.encode(ctx.rev),
    ikm,
  ];

  let size = DOMAIN_PREFIX.length;
  for (const field of fields) {
    if (field.length > 0xffff) {
      throw new Error('commit ctx field exceeds uint16 length prefix');
    }
    size += 2 + field.length;
  }

  const out = new Uint8Array(size);
  out.set(DOMAIN_PREFIX);
  let offset = DOMAIN_PREFIX.length;
  for (const field of fields) {
    out[offset++] = (field.length >>> 8) & 0xff;
    out[offset++] = field.length & 0xff;
    out.set(field, offset);
    offset += field.length;
  }
  return out;
}

/**
 * @param {Uint8Array} key
 * @param {Uint8Array} data
 * @returns {Promise<Uint8Array>}
 */
export async function hmacSha256(key, data) {
  const cryptoKey = await crypto.subtle.importKey(
    'raw',
    key,
    { name: 'HMAC', hash: 'SHA-256' },
    false,
    ['sign'],
  );
  const sig = await crypto.subtle.sign('HMAC', cryptoKey, data);
  return new Uint8Array(sig);
}

/**
 * HKDF-Expand (RFC 5869 §2.3) with SHA-256 and L = 32, matching the reference's
 * `expand(sha256, ikm, info, 32)`. `ikm` is used directly as the PRK — there is
 * no extract step, which is why crypto.subtle's HKDF cannot be used here. With
 * L equal to the hash length this is exactly one block.
 *
 * @param {Uint8Array} ikm
 * @param {Uint8Array} info
 * @returns {Promise<Uint8Array>}
 */
export function hkdfExpandSha256(ikm, info) {
  const block = new Uint8Array(info.length + 1);
  block.set(info);
  block[info.length] = 0x01;
  return hmacSha256(ikm, block);
}

/**
 * @param {Uint8Array} ikm
 * @param {Uint8Array} ctxBytes
 * @param {Uint8Array} hash
 * @returns {Promise<Uint8Array>}
 */
export async function computeMac(ikm, ctxBytes, hash) {
  return hmacSha256(await hkdfExpandSha256(ikm, ctxBytes), hash);
}

/**
 * @param {Uint8Array} a
 * @param {Uint8Array} b
 * @returns {boolean}
 */
export function bytesEqual(a, b) {
  if (a.length !== b.length) return false;
  for (let i = 0; i < a.length; i++) if (a[i] !== b[i]) return false;
  return true;
}
  • Step 4: Run test to verify it passes

Run: npx vitest run packages/spaces/test/mac.test.js Expected: PASS, 8 tests.

If encodeCommitCtx matches but the MAC does not, the HKDF interpretation is wrong — re-read packages/crypto/src/hmac.ts in the worktree.

  • Step 5: Export and commit

Add to packages/spaces/src/index.js:

export {
  COMMIT_VERSION,
  bytesEqual,
  computeMac,
  encodeCommitCtx,
  hkdfExpandSha256,
  hmacSha256,
} from './mac.js';

npx biome check --write packages/spaces
git add packages/spaces
git commit -m "feat(spaces): commit ctx encoding and deniable-signature MAC"

Task 7: Signature verifier port

Files:

  • Create: packages/spaces/src/verifier.js
  • Create: packages/spaces/test/verifier.test.js
  • Modify: packages/core/src/ports.js
  • Modify: packages/spaces/src/index.js

Interfaces:

  • Consumes: bytesEqual from Task 6 (not required, but available).
  • Produces:
    • createVerifier({ secp256k1 } = {}) => { verify(didKey: string, data: Uint8Array, sig: Uint8Array): Promise<boolean> }
    • parseDidKey(didKey: string) => { curve: 'p256'|'secp256k1', publicKey: Uint8Array } — throws on unsupported multicodec
    • Typedefs in packages/core/src/ports.js: SignatureVerifierPort, DidResolverPort

The multicodec prefixes are: 0x1200 (varint 0x80 0x24) for P-256, 0xe7 (varint 0xe7 0x01) for secp256k1. did:key values are did:key:z<base58btc(multicodec || compressedPublicKey)>. @pdsjs/core/crypto already exports base58btcDecode-equivalent helpers used by plc.js; reuse them rather than writing new base58 code. Check packages/core/src/crypto.js and packages/core/src/plc.js:47 for the encode path and add a decode counterpart there if one does not exist.

  • Step 1: Write the failing test

Create packages/spaces/test/verifier.test.js:

import { readFileSync } from 'node:fs';
import { describe, expect, it } from 'vitest';
import { encodeCommitCtx } from '../src/mac.js';
import { createVerifier, parseDidKey } from '../src/verifier.js';

const vectors = JSON.parse(
  readFileSync(new URL('../../../test/fixtures/space-vectors.json', import.meta.url), 'utf8'),
);

const fromHex = (h) =>
  new Uint8Array(h.match(/../g).map((x) => parseInt(x, 16)));

describe('parseDidKey', () => {
  it('recognises the P-256 multicodec', () => {
    const { didKey } = vectors.signedCommits[0];
    const parsed = parseDidKey(didKey);
    expect(parsed.curve).toBe('p256');
    expect(parsed.publicKey.length).toBe(33);
  });

  it('rejects a non-did:key string', () => {
    expect(() => parseDidKey('did:plc:aaaa')).toThrow(/did:key/);
  });
});

describe('createVerifier', () => {
  it('verifies a reference P-256 commit signature', async () => {
    const verifier = createVerifier();
    const c = vectors.signedCommits[0];
    const ctxBytes = encodeCommitCtx(c.ctx, fromHex(c.commit.ikmHex));
    expect(
      await verifier.verify(c.didKey, ctxBytes, fromHex(c.commit.sigHex)),
    ).toBe(true);
  });

  it('rejects a tampered signature', async () => {
    const verifier = createVerifier();
    const c = vectors.signedCommits[0];
    const ctxBytes = encodeCommitCtx(c.ctx, fromHex(c.commit.ikmHex));
    const sig = fromHex(c.commit.sigHex);
    sig[0] ^= 0xff;
    expect(await verifier.verify(c.didKey, ctxBytes, sig)).toBe(false);
  });

  it('rejects tampered data', async () => {
    const verifier = createVerifier();
    const c = vectors.signedCommits[0];
    const ctxBytes = encodeCommitCtx(c.ctx, fromHex(c.commit.ikmHex));
    ctxBytes[0] ^= 0xff;
    expect(
      await verifier.verify(c.didKey, ctxBytes, fromHex(c.commit.sigHex)),
    ).toBe(false);
  });

  it('rejects secp256k1 when no verifier is injected', async () => {
    const verifier = createVerifier();
    // did:key with the secp256k1 multicodec (zQ3s… prefix)
    await expect(
      verifier.verify(
        'zQ3shokFTS3brHcDQrn82RUDfCZESWL1ZdCEJwekUDPQiYBme',
        new Uint8Array(1),
        new Uint8Array(64),
      ),
    ).rejects.toThrow(/secp256k1/);
  });

  it('delegates secp256k1 to an injected verifier', async () => {
    let called = null;
    const verifier = createVerifier({
      secp256k1: async (publicKey, data, sig) => {
        called = { publicKey, data, sig };
        return true;
      },
    });
    const didKey = 'did:key:zQ3shokFTS3brHcDQrn82RUDfCZESWL1ZdCEJwekUDPQiYBme';
    const data = new Uint8Array([1, 2, 3]);
    const sig = new Uint8Array(64);
    expect(await verifier.verify(didKey, data, sig)).toBe(true);
    expect(called.data).toEqual(data);
    expect(called.publicKey.length).toBe(33);
  });
});

The secp256k1 did:key in the last two cases is the well-known example from the did:key spec. If it does not decode to a 33-byte key, substitute any did:key:zQ3s… value produced by Secp256k1Keypair.create().did() in the reference worktree and record it in the test.

  • Step 2: Run test to verify it fails

Run: npx vitest run packages/spaces/test/verifier.test.js Expected: FAIL — Failed to resolve import "../src/verifier.js".

  • Step 3: Implement

Create packages/spaces/src/verifier.js:

// @pdsjs/spaces/verifier - signature verification port.
//
// P-256 ships built in on crypto.subtle. secp256k1 is injected: hand-rolling
// ECDSA verification is a different risk class from hand-rolling a hash, since
// a subtle bug means accepting a forged credential rather than a failing test.
// Without an injected verifier, spaces interoperate only with P-256 accounts.

import { base58btcDecode } from '@pdsjs/core/crypto';

const P256_MULTICODEC = [0x80, 0x24];
const SECP256K1_MULTICODEC = [0xe7, 0x01];

/**
 * @param {string} didKey - did:key:z… (the did: prefix is optional)
 * @returns {{curve: 'p256'|'secp256k1', publicKey: Uint8Array}}
 */
export function parseDidKey(didKey) {
  const value = didKey.startsWith('did:key:') ? didKey.slice(8) : didKey;
  if (!value.startsWith('z')) {
    throw new Error(`expected a did:key multibase value, got: ${didKey}`);
  }
  const bytes = base58btcDecode(value.slice(1));
  if (bytes[0] === P256_MULTICODEC[0] && bytes[1] === P256_MULTICODEC[1]) {
    return { curve: 'p256', publicKey: bytes.slice(2) };
  }
  if (
    bytes[0] === SECP256K1_MULTICODEC[0] &&
    bytes[1] === SECP256K1_MULTICODEC[1]
  ) {
    return { curve: 'secp256k1', publicKey: bytes.slice(2) };
  }
  throw new Error(`unsupported did:key multicodec: ${didKey}`);
}

/**
 * @param {{secp256k1?: (publicKey: Uint8Array, data: Uint8Array, sig: Uint8Array) => Promise<boolean>}} [opts]
 * @returns {{verify: (didKey: string, data: Uint8Array, sig: Uint8Array) => Promise<boolean>}}
 */
export function createVerifier(opts = {}) {
  return {
    async verify(didKey, data, sig) {
      const { curve, publicKey } = parseDidKey(didKey);
      if (curve === 'p256') return verifyP256(publicKey, data, sig);
      if (!opts.secp256k1) {
        throw new Error(
          'secp256k1 verification requires an injected verifier; ' +
            'this deployment supports P-256 keys only',
        );
      }
      return opts.secp256k1(publicKey, data, sig);
    },
  };
}

/**
 * @param {Uint8Array} publicKey - 33-byte compressed point
 * @param {Uint8Array} data
 * @param {Uint8Array} sig - 64-byte raw r||s
 * @returns {Promise<boolean>}
 */
async function verifyP256(publicKey, data, sig) {
  const key = await crypto.subtle.importKey(
    'raw',
    publicKey,
    { name: 'ECDSA', namedCurve: 'P-256' },
    false,
    ['verify'],
  );
  return crypto.subtle.verify(
    { name: 'ECDSA', hash: 'SHA-256' },
    key,
    sig,
    data,
  );
}

If @pdsjs/core/crypto has no base58btcDecode, add one next to the existing base58btcEncode used by plc.js:57 and export it. Verify the encode/decode pair round-trips before relying on it.

If crypto.subtle.importKey('raw', …) rejects a 33-byte compressed point on the target runtime, decompress to the 65-byte uncompressed form first. Node 22+, Deno, and workerd all accept compressed points; confirm rather than assume.

  • Step 4: Run test to verify it passes

Run: npx vitest run packages/spaces/test/verifier.test.js Expected: PASS, 7 tests.

  • Step 5: Declare the ports in core

Modify packages/core/src/ports.js, adding these typedefs next to the existing LexiconResolverPort. This file is pure JSDoc ending in export {} — it gains type declarations and no runtime coupling.

/**
 * Verifies signatures against did:key identifiers. P-256 is always supported;
 * secp256k1 support depends on an injected implementation.
 *
 * @typedef {Object} SignatureVerifierPort
 * @property {(didKey: string, data: Uint8Array, sig: Uint8Array) => Promise<boolean>} verify
 */

/**
 * Resolves a DID to its DID document. Injected rather than imported so that
 * @pdsjs/spaces stays dependency-free.
 *
 * @typedef {Object} DidResolverPort
 * @property {(did: string) => Promise<Object>} resolveDid
 */
  • Step 6: Export and commit

Add to packages/spaces/src/index.js:

export { createVerifier, parseDidKey } from './verifier.js';

npx biome check --write packages/spaces packages/core
git add packages/spaces packages/core/src/ports.js
git commit -m "feat(spaces): signature verifier port with injectable secp256k1"

Task 8: RepoCommit

Files:

  • Create: packages/spaces/src/commit.js
  • Create: packages/spaces/test/commit.test.js
  • Modify: packages/spaces/src/index.js

Interfaces:

  • Consumes: LtHash (Task 3), formatSetHashElement (Task 4), COMMIT_VERSION/encodeCommitCtx/computeMac/bytesEqual (Task 6), verifier port (Task 7).
  • Produces:
    • class RepoCommit with:
      • constructor(setHash?: LtHash)
      • static fromState(state: Uint8Array|null|undefined): RepoCommit
      • static fromRecords(records: Iterable<{collection, rkey, cid}>): RepoCommit
      • static fromIndex(index: Record<string, string>): RepoCommit — index maps "{collection}/{rkey}" to CID string
      • add(collection, rkey, cid): this
      • remove(collection, rkey, cid): this
      • applyOp(op: {collection, rkey, cid: string|null, prev: string|null}): this
      • applyOps(ops): this
      • matches(commit: SignedCommit): Promise<boolean>
      • sign(ctx: {space, author, rev}, signer: {sign(bytes): Promise<Uint8Array>}): Promise<SignedCommit>
      • state(): Uint8Array
    • verifyCommit(commit, ctx, didKey, verifier): Promise<boolean>
    • SignedCommit shape: { ver: number, hash: Uint8Array, ikm: Uint8Array, sig: Uint8Array, mac: Uint8Array, rev: string }

Note sign takes a signer object ({ sign(bytes) }) rather than raw key material, so @pdsjs/spaces never handles private keys. randomBytes(32) comes from crypto.getRandomValues.

  • Step 1: Write the failing test

Create packages/spaces/test/commit.test.js:

import { readFileSync } from 'node:fs';
import { describe, expect, it } from 'vitest';
import { RepoCommit, verifyCommit } from '../src/commit.js';
import { createVerifier } from '../src/verifier.js';

const vectors = JSON.parse(
  readFileSync(new URL('../../../test/fixtures/space-vectors.json', import.meta.url), 'utf8'),
);

const fromHex = (h) =>
  new Uint8Array(h.match(/../g).map((x) => parseInt(x, 16)));
const toHex = (b) =>
  Array.from(b)
    .map((x) => x.toString(16).padStart(2, '0'))
    .join('');

function referenceCommit() {
  const c = vectors.signedCommits[0];
  return {
    ...c,
    signed: {
      ver: c.commit.ver,
      hash: fromHex(c.commit.hashHex),
      ikm: fromHex(c.commit.ikmHex),
      sig: fromHex(c.commit.sigHex),
      mac: fromHex(c.commit.macHex),
      rev: c.commit.rev,
    },
  };
}

describe('RepoCommit', () => {
  it('reproduces the reference set hash from the same records', async () => {
    const { records, signed } = referenceCommit();
    const repo = RepoCommit.fromRecords(records);
    expect(toHex(await repo.setHash.digest())).toBe(toHex(signed.hash));
  });

  it('matches() compares against a signed commit', async () => {
    const { records, signed } = referenceCommit();
    expect(await RepoCommit.fromRecords(records).matches(signed)).toBe(true);
    expect(await new RepoCommit().matches(signed)).toBe(false);
  });

  it('fromIndex folds in the same records as fromRecords', async () => {
    const { records } = referenceCommit();
    const index = Object.fromEntries(
      records.map((r) => [`${r.collection}/${r.rkey}`, r.cid]),
    );
    const a = RepoCommit.fromRecords(records);
    const b = RepoCommit.fromIndex(index);
    expect(toHex(await a.setHash.digest())).toBe(toHex(await b.setHash.digest()));
  });

  it('fromState round-trips', async () => {
    const { records } = referenceCommit();
    const repo = RepoCommit.fromRecords(records);
    const restored = RepoCommit.fromState(repo.state());
    expect(toHex(await restored.setHash.digest())).toBe(
      toHex(await repo.setHash.digest()),
    );
  });

  it('fromState treats null as an empty repo', () => {
    expect(RepoCommit.fromState(null).setHash.isEmpty()).toBe(true);
  });

  it('applyOp handles create, update, and delete', async () => {
    const { records } = referenceCommit();
    const [a, b] = records;
    const repo = new RepoCommit();
    repo.applyOp({ collection: a.collection, rkey: a.rkey, cid: a.cid, prev: null });
    repo.applyOp({ collection: b.collection, rkey: b.rkey, cid: b.cid, prev: null });
    const full = RepoCommit.fromRecords(records);
    expect(repo.setHash.equals(full.setHash)).toBe(true);

    // delete removes it again
    repo.applyOp({ collection: b.collection, rkey: b.rkey, cid: null, prev: b.cid });
    expect(repo.setHash.equals(RepoCommit.fromRecords([a]).setHash)).toBe(true);
  });

  it('an update is remove-then-add', async () => {
    const { records } = referenceCommit();
    const [a, b] = records;
    const repo = RepoCommit.fromRecords([a]);
    repo.applyOp({ collection: a.collection, rkey: a.rkey, cid: b.cid, prev: a.cid });
    const expected = RepoCommit.fromRecords([
      { collection: a.collection, rkey: a.rkey, cid: b.cid },
    ]);
    expect(repo.setHash.equals(expected.setHash)).toBe(true);
  });
});

describe('verifyCommit', () => {
  const verifier = createVerifier();

  it('accepts the reference commit', async () => {
    const { signed, ctx, didKey } = referenceCommit();
    expect(await verifyCommit(signed, ctx, didKey, verifier)).toBe(true);
  });

  it('rejects a wrong version', async () => {
    const { signed, ctx, didKey } = referenceCommit();
    expect(
      await verifyCommit({ ...signed, ver: 2 }, ctx, didKey, verifier),
    ).toBe(false);
  });

  it('rejects a rev mismatch between commit and ctx', async () => {
    const { signed, ctx, didKey } = referenceCommit();
    expect(
      await verifyCommit(signed, { ...ctx, rev: 'different' }, didKey, verifier),
    ).toBe(false);
  });

  it('rejects a tampered hash', async () => {
    const { signed, ctx, didKey } = referenceCommit();
    const hash = new Uint8Array(signed.hash);
    hash[0] ^= 0xff;
    expect(
      await verifyCommit({ ...signed, hash }, ctx, didKey, verifier),
    ).toBe(false);
  });

  it('rejects a tampered mac', async () => {
    const { signed, ctx, didKey } = referenceCommit();
    const mac = new Uint8Array(signed.mac);
    mac[0] ^= 0xff;
    expect(await verifyCommit({ ...signed, mac }, ctx, didKey, verifier)).toBe(
      false,
    );
  });
});

describe('sign', () => {
  it('produces a commit that verifies against our own verifier', async () => {
    const keys = await crypto.subtle.generateKey(
      { name: 'ECDSA', namedCurve: 'P-256' },
      true,
      ['sign', 'verify'],
    );
    const signer = {
      sign: async (bytes) =>
        new Uint8Array(
          await crypto.subtle.sign(
            { name: 'ECDSA', hash: 'SHA-256' },
            keys.privateKey,
            bytes,
          ),
        ),
    };
    const verifier = {
      verify: async (_didKey, data, sig) =>
        crypto.subtle.verify(
          { name: 'ECDSA', hash: 'SHA-256' },
          keys.publicKey,
          sig,
          data,
        ),
    };

    const { records } = referenceCommit();
    const ctx = {
      space: 'at://did:plc:aaaa/space/com.example.type/k',
      author: 'did:plc:bbbb',
      rev: '3lkabcdefgh2x',
    };
    const repo = RepoCommit.fromRecords(records);
    const signed = await repo.sign(ctx, signer);

    expect(signed.ver).toBe(1);
    expect(signed.rev).toBe(ctx.rev);
    expect(signed.ikm.length).toBe(32);
    expect(await verifyCommit(signed, ctx, 'ignored', verifier)).toBe(true);
  });

  it('uses a fresh ikm per signature', async () => {
    const signer = { sign: async () => new Uint8Array(64) };
    const ctx = { space: 'at://did:plc:a/space/com.e.t/k', author: 'did:plc:b', rev: '3l' };
    const repo = new RepoCommit();
    const a = await repo.sign(ctx, signer);
    const b = await repo.sign(ctx, signer);
    expect(toHex(a.ikm)).not.toBe(toHex(b.ikm));
    expect(toHex(a.mac)).not.toBe(toHex(b.mac));
  });
});
  • Step 2: Run test to verify it fails

Run: npx vitest run packages/spaces/test/commit.test.js Expected: FAIL — Failed to resolve import "../src/commit.js".

  • Step 3: Implement

Create packages/spaces/src/commit.js:

// @pdsjs/spaces/commit - permissioned repo commits with deniable signatures.

import { LtHash } from './lthash.js';
import {
  COMMIT_VERSION,
  bytesEqual,
  computeMac,
  encodeCommitCtx,
} from './mac.js';
import { formatSetHashElement } from './path.js';

/**
 * @typedef {Object} SignedCommit
 * @property {number} ver
 * @property {Uint8Array} hash
 * @property {Uint8Array} ikm
 * @property {Uint8Array} sig
 * @property {Uint8Array} mac
 * @property {string} rev
 */

export class RepoCommit {
  /** @param {LtHash} [setHash] */
  constructor(setHash = new LtHash()) {
    this.setHash = setHash;
  }

  /** @param {Uint8Array|null|undefined} state */
  static fromState(state) {
    return new RepoCommit(new LtHash(state ?? null));
  }

  /** @param {Iterable<{collection: string, rkey: string, cid: string}>} records */
  static fromRecords(records) {
    const commit = new RepoCommit();
    for (const { collection, rkey, cid } of records) {
      commit.add(collection, rkey, cid);
    }
    return commit;
  }

  /**
   * Fold in every record an index describes, to compare against a commit.
   * @param {Record<string, string>} index - "{collection}/{rkey}" to CID
   */
  static fromIndex(index) {
    const commit = new RepoCommit();
    for (const [path, cid] of Object.entries(index)) {
      commit.setHash.add(`${path}/${cid}`);
    }
    return commit;
  }

  add(collection, rkey, cid) {
    this.setHash.add(formatSetHashElement(collection, rkey, cid));
    return this;
  }

  remove(collection, rkey, cid) {
    this.setHash.remove(formatSetHashElement(collection, rkey, cid));
    return this;
  }

  /** @param {{collection: string, rkey: string, cid: string|null, prev: string|null}} op */
  applyOp(op) {
    if (op.prev) this.remove(op.collection, op.rkey, op.prev);
    if (op.cid) this.add(op.collection, op.rkey, op.cid);
    return this;
  }

  applyOps(ops) {
    for (const op of ops) this.applyOp(op);
    return this;
  }

  state() {
    return this.setHash.state();
  }

  /**
   * Whether this repo's contents match a signed commit. Verify the commit first —
   * on its own this says nothing about authenticity.
   * @param {SignedCommit} commit
   */
  async matches(commit) {
    return bytesEqual(await this.setHash.digest(), commit.hash);
  }

  /**
   * Sign a commit over the current contents.
   *
   * The signature covers only the ctx, never the digest, so a leaked commit
   * proves nothing about what the author wrote. The digest is bound to the ctx
   * by a symmetric MAC instead: readers get integrity, third parties get
   * nothing. A fresh ikm per commit means each reader receives a distinct one.
   *
   * @param {{space: string, author: string, rev: string}} ctx
   * @param {{sign: (bytes: Uint8Array) => Promise<Uint8Array>}} signer
   * @returns {Promise<SignedCommit>}
   */
  async sign(ctx, signer) {
    const hash = await this.setHash.digest();
    const ikm = crypto.getRandomValues(new Uint8Array(32));
    const ctxBytes = encodeCommitCtx(ctx, ikm);
    return {
      ver: COMMIT_VERSION,
      hash,
      ikm,
      mac: await computeMac(ikm, ctxBytes, hash),
      sig: await signer.sign(ctxBytes),
      rev: ctx.rev,
    };
  }
}

/**
 * Verify a commit's signature (authenticity) and MAC (integrity). Once this
 * passes, `hash` is trusted as the author's claim about their repo, which is
 * what makes RepoCommit#matches meaningful.
 *
 * @param {SignedCommit} commit
 * @param {{space: string, author: string, rev: string}} ctx
 * @param {string} didKey
 * @param {import('@pdsjs/core/ports').SignatureVerifierPort} verifier
 * @returns {Promise<boolean>}
 */
export async function verifyCommit(commit, ctx, didKey, verifier) {
  if (commit.ver !== COMMIT_VERSION) return false;
  if (commit.rev !== ctx.rev) return false;

  const ctxBytes = encodeCommitCtx(ctx, commit.ikm);
  const mac = await computeMac(commit.ikm, ctxBytes, commit.hash);
  if (!bytesEqual(mac, commit.mac)) return false;

  return verifier.verify(didKey, ctxBytes, commit.sig);
}
  • Step 4: Run test to verify it passes

Run: npx vitest run packages/spaces/test/commit.test.js Expected: PASS, 14 tests.

  • Step 5: Run the whole suite

Run: npx vitest run packages/spaces Expected: PASS across all six space test files.

Then confirm nothing else regressed:

Run: npx vitest run packages/core Expected: PASS — Task 7 touched only JSDoc in ports.js, plus a possible base58btcDecode addition to crypto.js.

  • Step 6: Export and commit

Add to packages/spaces/src/index.js:

export { RepoCommit, verifyCommit } from './commit.js';

Run the type build to confirm the JSDoc types are coherent:

npm run build
npm run typecheck

Expected: no errors. packages/spaces/src/*.d.ts files are generated.

npx biome check --write packages/spaces
git add packages/spaces
git commit -m "feat(spaces): RepoCommit signing and verification"

Phase 1 exit criteria

  • npx vitest run packages/spaces passes
  • npx vitest run passes (no regressions)
  • npm run typecheck introduces no NEW errors relative to the branch point (6a1b716). npm run typecheck failing outright was never a realistic bar: the repo carried 91 pre-existing error TS lines at that commit (measured via npx tsc --noEmit 2>&1 | grep -c "error TS" in a clean worktree of 6a1b716), none of which this phase is responsible for fixing.
  • packages/spaces/package.json dependencies contains only @pdsjs/core
  • packages/core does not import @pdsjs/spaces anywhere: grep -rnE "(^|[^*])\s*import .*@pdsjs/spaces|require\(['\"]@pdsjs/spaces" packages/core/src | wc -l returns 0. (A plain grep -rn "@pdsjs/spaces" packages/core/src returns 2, both inside JSDoc comment prose in ports.js rather than real imports, so the check must target import/require syntax specifically.)
  • test/fixtures/space-vectors.json generatedFrom.sha matches the pin in the spec's §0