// Slice 3b: the MST-inversion proof. A #commit's `blocks` CAR must be a MINIMAL,
// self-contained covering proof of the old→new transition (not the whole tree).
//
// We prove relay-validity the way a cold relay would, using ONLY the emitted CAR:
// - inversion: replay ops backward from the new data root → must reach prevData
// (a missing block throws — the CAR is then insufficient);
// - inclusion: a created/updated record resolves at its path in the new tree;
// - exclusion: a deleted record is provably absent in the new tree;
// - minimality: far fewer MST nodes than the full tree (else a real repo is tooBig).
// The prior record CIDs travel in each op's `prev`, so no old-tree state is needed.
import test from 'brittle'
import { mkdtempSync, rmSync } from 'node:fs'
import { join } from 'node:path'
import { tmpdir } from 'node:os'
import { RepoStore } from '../lib/repo-store.js'
import { RepoManager } from '../lib/repo-manager.js'
import { commitFrame, decodeCommitFrame } from '../lib/firehose.js'
import { readCar, loadCommit } from 'atproto-repo/lib/repo.js'
import {
buildMst, reachableBlocks, nodeStoreFromBlocks, OverlayNodeStore,
NodeWrangler, findRpathProof
} from 'atproto-repo/lib/mst.js'
import { cidForBytesSync } from 'atproto-repo/lib/cid.js'
const DID = 'did:plc:yu4kgcktm7qtrwo5ofyiaf4c'
const PRIV = new Uint8Array(32).fill(7)
const iso = '2026-07-02T00:00:00.000Z'
async function newMgr (t) {
const dir = mkdtempSync(join(tmpdir(), 'fhproof-'))
const store = await new RepoStore(dir).ready()
t.teardown(async () => { try { await store.close() } catch {} rmSync(dir, { recursive: true, force: true }) })
let micros = 1_700_000_000_000_000n
const mgr = new RepoManager(store, { did: DID, privateKey: PRIV, clock: () => (micros += 1_000_000n) })
await mgr.init()
return { store, mgr }
}
// Seed a repo with n posts so the MST has real height (subtrees), like a live repo.
async function seed (mgr, n) {
for (let i = 0; i < n; i++) {
await mgr.applyWrite({
action: 'create', collection: 'app.bsky.feed.post', rkey: `3seed${i.toString().padStart(3, '0')}`,
record: { $type: 'app.bsky.feed.post', text: `seed ${i}`, createdAt: iso }
})
}
}
// ---- the cold-relay verifier: everything below uses ONLY the emitted CAR ----
function nsFromCar (car) { return nodeStoreFromBlocks(car.blocks) }
// Replay ops backward from the new data root using only CAR blocks. Returns the
// reconstructed root CID; throws (missing node) if the CAR is insufficient.
function invertFromCar (car, body) {
const overlay = new OverlayNodeStore(nsFromCar(car))
const w = new NodeWrangler(overlay)
let root = loadCommit(car).value.data
for (let i = body.ops.length - 1; i >= 0; i--) {
const op = body.ops[i]
if (op.action === 'create') root = w.delRecord(root, op.path)
else root = w.putRecord(root, op.path, op.prev) // prev decoded as a CID
}
return root
}
// how many of the CAR's blocks are MST nodes (exclude commit + record blocks)
function mstNodeCount (car, body) {
let recordCids = 0
for (const op of body.ops) if (op.cid) recordCids++
return car.blocks.size - 1 /* commit */ - recordCids
}
function fullTreeNodeCount (records) {
const mstRecs = records.map(r => ({ key: r.key, value: cidForBytesSync(r.bytes) }))
const { root, ns } = buildMst(mstRecs)
return reachableBlocks(ns, root).size
}
// 1. CREATE into a real (multi-node) tree: inversion + inclusion + minimality
test('create: CAR inverts to prevData, includes the record, ships << full tree', async (t) => {
const result = await (async () => {
const { store, mgr } = await newMgr(t)
await seed(mgr, 40)
const w = await mgr.applyWrite({ action: 'create', collection: 'app.bsky.feed.post', rkey: '3newpost01', record: { $type: 'app.bsky.feed.post', text: 'hi', createdAt: iso } })
const { body } = decodeCommitFrame(await commitFrame(w, { seq: 100, time: iso }))
const car = await readCar(body.blocks)
const inverted = invertFromCar(car, body) // uses CAR only
if (!inverted.equals(body.prevData)) return false // inversion valid
const { value } = findRpathProof(nsFromCar(car), body.commitDataRoot ?? loadCommit(car).value.data, 'app.bsky.feed.post/3newpost01')
if (value === null || !value.equals(w.ops[0].cid)) return false // inclusion proof
const full = fullTreeNodeCount(await store.records())
const shipped = mstNodeCount(car, body)
t.comment(`create: shipped ${shipped} MST nodes vs full tree ${full}`)
return shipped < full // minimal, not whole-tree
})()
t.ok(result, 'create: CAR inverts to prevData, includes the record, ships << full tree')
})
// 2. DELETE from a real tree: inversion + exclusion proof + minimality
test('delete: CAR inverts to prevData, proves record absent, ships << full tree', async (t) => {
const result = await (async () => {
const { store, mgr } = await newMgr(t)
await seed(mgr, 40)
await mgr.applyWrite({ action: 'create', collection: 'app.bsky.feed.post', rkey: '3victim01', record: { $type: 'app.bsky.feed.post', text: 'bye', createdAt: iso } })
const w = await mgr.applyWrite({ action: 'delete', collection: 'app.bsky.feed.post', rkey: '3victim01' })
const { body } = decodeCommitFrame(await commitFrame(w, { seq: 101, time: iso }))
const car = await readCar(body.blocks)
const inverted = invertFromCar(car, body)
if (!inverted.equals(body.prevData)) return false // inversion valid
const { value } = findRpathProof(nsFromCar(car), loadCommit(car).value.data, 'app.bsky.feed.post/3victim01')
if (value !== null) return false // exclusion proof
const prevOk = body.ops[0].action === 'delete' && body.ops[0].cid === null && body.ops[0].prev != null
const full = fullTreeNodeCount(await store.records())
const shipped = mstNodeCount(car, body)
t.comment(`delete: shipped ${shipped} MST nodes vs full tree ${full}`)
return prevOk && shipped < full
})()
t.ok(result, 'delete: CAR inverts to prevData, proves record absent, ships << full tree')
})
// 3. UPDATE in a real tree: inversion restores the prior value; inclusion of the new one
test('update: CAR inverts to prevData (prior value restored) + includes new value', async (t) => {
const result = await (async () => {
const { mgr } = await newMgr(t)
await seed(mgr, 40)
await mgr.applyWrite({ action: 'create', collection: 'app.bsky.feed.post', rkey: '3edit01', record: { $type: 'app.bsky.feed.post', text: 'v1', createdAt: iso } })
const w = await mgr.applyWrite({ action: 'update', collection: 'app.bsky.feed.post', rkey: '3edit01', record: { $type: 'app.bsky.feed.post', text: 'v2', createdAt: iso } })
const { body } = decodeCommitFrame(await commitFrame(w, { seq: 102, time: iso }))
const car = await readCar(body.blocks)
const inverted = invertFromCar(car, body)
if (!inverted.equals(body.prevData)) return false
const prevOk = body.ops[0].action === 'update' && body.ops[0].prev != null && !body.ops[0].prev.equals(body.ops[0].cid)
const { value } = findRpathProof(nsFromCar(car), loadCommit(car).value.data, 'app.bsky.feed.post/3edit01')
return prevOk && value !== null && value.equals(w.ops[0].cid)
})()
t.ok(result, 'update: CAR inverts to prevData (prior value restored) + includes new value')
})
// 4. Regression: the emitted set must be SUFFICIENT — invertFromCar throws on a
// missing node. Corrupt the CAR (drop one MST node) and confirm inversion fails.
test('negative control: dropping a proof node breaks inversion (proof is load-bearing)', async (t) => {
const result = await (async () => {
const { mgr } = await newMgr(t)
await seed(mgr, 40)
const w = await mgr.applyWrite({ action: 'create', collection: 'app.bsky.feed.post', rkey: '3ctrl01', record: { $type: 'app.bsky.feed.post', text: 'x', createdAt: iso } })
const { body } = decodeCommitFrame(await commitFrame(w, { seq: 103, time: iso }))
const car = await readCar(body.blocks)
// drop one MST node (not the commit, not the record)
const commitCid = loadCommit(car).cid.toString()
const recordCid = w.ops[0].cid.toString()
let dropped = null
for (const k of car.blocks.keys()) { if (k !== commitCid && k !== recordCid) { dropped = k; break } }
car.blocks.delete(dropped)
try { invertFromCar(car, body); return false } // should have thrown
catch { return true }
})()
t.ok(result, 'negative control: dropping a proof node breaks inversion (proof is load-bearing)')
})