atproto-repo / test / mst-write.test.js

// Slice 2: prove the MST WRITE path is byte-exact, against two oracles:
//  A. rebuild the golden repo's MST from its records -> match commit.data + node bytes
//  B. atmst's own root CIDs for a 50-key, 3-height tree (build + delete)
// The atmst roots were generated by running millipds's reference on stortron with
// val(key) = cid(dag-cbor(key)); we reproduce that mapping here.

import test from 'brittle'
import { readFileSync } from 'node:fs'
import { fileURLToPath } from 'node:url'
import { dirname, join } from 'node:path'
import { readCar, loadCommit, listRecords } from '../lib/repo.js'
import { buildMst, keyHeight } from '../lib/mst.js'
import { cidForBytesSync } from '../lib/cid.js'
import * as dagCbor from '@ipld/dag-cbor'

const here = dirname(fileURLToPath(import.meta.url))
const carBytes = readFileSync(join(here, 'vectors', 'bridgetest-repo.car'))

// atmst oracle (reference roots), val(k) = cid(dag-cbor(k)):
const ATMST_KEYS = Array.from({ length: 50 }, (_, i) => `app.test.record/${String(i).padStart(4, '0')}`)
const ATMST_ROOT = 'bafyreiaxxeqrlo6flqjewuug3locbq7mmf5cmswecbic3xj6h4lyajymta'
const ATMST_ROOT_AFTER_DELETES = 'bafyreigwzj7pnllj3ggewdj4buwcaxqjhctasgcuwknjwjl7kbeiwlaot4'
const DELETE_KEYS = ['app.test.record/0000', 'app.test.record/0025', 'app.test.record/0049']
const valFor = (k) => cidForBytesSync(dagCbor.encode(k))

test('A: rebuilt golden MST matches commit.data + byte-identical node', async (t) => {
  const car = await readCar(carBytes)
  const commit = loadCommit(car)
  const records = listRecords(car).map(r => ({ key: r.key, value: r.cid }))
  const builtGolden = buildMst(records)
  t.ok(builtGolden.root.equals(commit.value.data), 'rebuilt golden MST root == commit.data')
  const goldenNode = car.blocks.get(commit.value.data.toString())
  const ourNode = builtGolden.ns.blocks.get(builtGolden.root.toString())
  t.ok(Buffer.from(ourNode.bytes).equals(Buffer.from(goldenNode.bytes)),
    'rebuilt MST node bytes are byte-identical to the golden block')
})

test('B: 50-key multi-height build matches atmst oracle (+ order independence)', (t) => {
  const built = buildMst(ATMST_KEYS.map(k => ({ key: k, value: valFor(k) })))
  const hist = {}
  for (const k of ATMST_KEYS) { const h = keyHeight(k); hist[h] = (hist[h] || 0) + 1 }
  t.comment('height histogram: ' + JSON.stringify(hist))
  t.is(built.root.toString(), ATMST_ROOT, '50-key build root matches atmst oracle')

  const shuffled = buildMst(ATMST_KEYS.slice().reverse().map(k => ({ key: k, value: valFor(k) })))
  t.is(shuffled.root.toString(), ATMST_ROOT, 'root is insertion-order independent')
})

test('D: delete path matches atmst oracle', (t) => {
  const { root, wrangler } = buildMst(ATMST_KEYS.map(k => ({ key: k, value: valFor(k) })))
  let r = root
  for (const k of DELETE_KEYS) r = wrangler.delRecord(r, k)
  t.is(r.toString(), ATMST_ROOT_AFTER_DELETES, 'root after 3 deletes matches atmst oracle')
})

test('E: key heights span >1 level (splits exercised)', (t) => {
  t.ok(new Set(ATMST_KEYS.map(keyHeight)).size >= 2, 'height histogram spans >1 level')
})