chadtmiller.com/pds.js
An atproto PDS in JavaScript, for Cloudflare Workers and Node
0
0
// @pdsjs/core/mst - Merkle Search Tree implementation for AT Protocol
// MST for repository structure with proper depth-based layering
import {
CID,
cborDecode,
cborEncodeDagCbor,
cidToBytes,
cidToString,
createCid,
getKeyDepth,
} from './repo.js';
/**
* Compute common prefix length between two byte arrays
* @param {Uint8Array} a
* @param {Uint8Array} b
* @returns {number}
*/
function commonPrefixLen(a, b) {
const minLen = Math.min(a.length, b.length);
for (let i = 0; i < minLen; i++) {
if (a[i] !== b[i]) return i;
}
return minLen;
}
/**
* @typedef {Object} MstEntry
* @property {string} key - Full key (collection/rkey)
* @property {Uint8Array} keyBytes - UTF-8 encoded key bytes
* @property {string} cid - Record CID string
* @property {number} depth - MST depth from key hash
*/
/**
* Build MST from sorted records
* @param {Array<{key: string, cid: string}>} records - Records sorted by key
* @param {(cid: string, data: Uint8Array) => Promise<void>} putBlock - Storage function
* @returns {Promise<string|null>} Root CID or null if empty
*/
export async function buildMst(records, putBlock) {
if (records.length === 0) {
return null;
}
// Build entries with pre-computed depths
/** @type {MstEntry[]} */
const entries = [];
let maxDepth = 0;
for (const r of records) {
const depth = await getKeyDepth(r.key);
maxDepth = Math.max(maxDepth, depth);
entries.push({
key: r.key,
keyBytes: new TextEncoder().encode(r.key),
cid: r.cid,
depth,
});
}
// Build tree from root (highest layer) down to layer 0
return buildMstLayer(entries, maxDepth, putBlock);
}
/**
* Build MST layer recursively
* @param {MstEntry[]} entries - Entries for this subtree
* @param {number} layer - Current layer (starts at max, goes to 0)
* @param {(cid: string, data: Uint8Array) => Promise<void>} putBlock
* @returns {Promise<string|null>}
*/
async function buildMstLayer(entries, layer, putBlock) {
if (entries.length === 0) return null;
// Separate entries: depth == layer stays here, depth < layer goes to subtrees
/** @type {Array<{type: 'subtree', cid: string|null} | {type: 'entry', entry: MstEntry}>} */
const thisLayer = [];
/** @type {MstEntry[]} */
let leftSubtree = [];
for (const entry of entries) {
if (entry.depth < layer) {
// Belongs to lower layer
leftSubtree.push(entry);
} else {
// Belongs at current layer
if (leftSubtree.length > 0) {
const leftCid = await buildMstLayer(leftSubtree, layer - 1, putBlock);
thisLayer.push({ type: 'subtree', cid: leftCid });
leftSubtree = [];
}
thisLayer.push({ type: 'entry', entry });
}
}
// Handle remaining subtree
if (leftSubtree.length > 0) {
const leftCid = await buildMstLayer(leftSubtree, layer - 1, putBlock);
thisLayer.push({ type: 'subtree', cid: leftCid });
}
// Build node in ATProto format
/** @type {{ e: Array<{p: number, k: Uint8Array, v: CID, t: CID|null}>, l: CID|null }} */
const node = { e: [], l: null };
/** @type {string|null} */
let leftCid = null;
/** @type {Uint8Array} */
let prevKeyBytes = new Uint8Array(0);
for (const item of thisLayer) {
if (item.type === 'subtree') {
if (node.e.length === 0) {
leftCid = item.cid;
} else if (item.cid !== null) {
// Attach to previous entry's 't' field
node.e[node.e.length - 1].t = new CID(cidToBytes(item.cid));
}
} else {
const keyBytes = item.entry.keyBytes;
const prefixLen = commonPrefixLen(prevKeyBytes, keyBytes);
const keySuffix = new Uint8Array(
keyBytes.buffer,
keyBytes.byteOffset + prefixLen,
keyBytes.length - prefixLen,
);
node.e.push({
p: prefixLen,
k: keySuffix,
v: new CID(cidToBytes(item.entry.cid)),
t: null,
});
prevKeyBytes = new Uint8Array(keyBytes);
}
}
// Set left subtree
node.l = leftCid ? new CID(cidToBytes(leftCid)) : null;
// Encode and store
const nodeBytes = cborEncodeDagCbor(node);
const nodeCid = await createCid(nodeBytes);
const cidStr = cidToString(nodeCid);
await putBlock(cidStr, nodeBytes);
return cidStr;
}
/**
* Walk MST and yield all entries in key order
* @param {string} rootCid - Root CID string
* @param {(cid: string) => Promise<Uint8Array|null>} getBlock - Block retrieval function
* @yields {{key: string, cid: string}}
*/
export async function* walkMst(rootCid, getBlock) {
/** @type {string[]} */
const keyStack = [];
/**
* @param {string} nodeCid
* @returns {AsyncGenerator<{key: string, cid: string}, void, unknown>}
*/
async function* walkNode(nodeCid) {
const data = await getBlock(nodeCid);
if (!data) return;
const node = cborDecode(data);
// Process left subtree first
if (node.l) {
yield* walkNode(cidToString(node.l));
}
// Process entries
for (const entry of node.e || []) {
// Reconstruct key from prefix compression
const prevKey = keyStack.length > 0 ? keyStack[keyStack.length - 1] : '';
const prefix = prevKey.slice(0, entry.p);
const suffix = new TextDecoder().decode(entry.k);
const key = prefix + suffix;
keyStack.push(key);
yield { key, cid: cidToString(entry.v) };
// Process subtree after this entry
if (entry.t) {
yield* walkNode(cidToString(entry.t));
}
}
}
yield* walkNode(rootCid);
}
/**
* Collect all MST node blocks (for building CAR files)
* @param {string} rootCid - Root CID string
* @param {(cid: string) => Promise<Uint8Array|null>} getBlock - Block retrieval function
* @returns {Promise<Array<{cid: string, data: Uint8Array}>>}
*/
export async function collectMstBlocks(rootCid, getBlock) {
/** @type {Array<{cid: string, data: Uint8Array}>} */
const blocks = [];
const visited = new Set();
/**
* @param {string} cidStr
*/
async function collect(cidStr) {
if (visited.has(cidStr)) return;
visited.add(cidStr);
const data = await getBlock(cidStr);
if (!data) return;
blocks.push({ cid: cidStr, data });
// Follow child CIDs
try {
const node = cborDecode(data);
if (node.l) {
await collect(cidToString(node.l));
}
if (node.e) {
for (const entry of node.e) {
if (entry.t) {
await collect(cidToString(entry.t));
}
}
}
} catch {
// Not an MST node, ignore
}
}
await collect(rootCid);
return blocks;
}
/**
* Those of `read`, nodes of the old tree a change read, that the tree at
* `root` no longer reaches.
*
* A changed tree is the nodes the change made and subtrees of the old one.
* An old node still in it hangs off a made node, or off an old node the
* change read on its way down, since a change reads every node on the path
* to what it changes. So a walk from `root` through only those two sets
* reaches every read node still in the tree.
* @param {string|null} root
* @param {Map<string, Uint8Array>} made - Nodes the change made, by CID
* @param {Map<string, Uint8Array>} read
* @returns {string[]}
*/
export function unreachedNodes(root, made, read) {
const reached = new Set();
const next = root ? [root] : [];
while (next.length) {
const cid = /** @type {string} */ (next.pop());
if (reached.has(cid)) continue;
reached.add(cid);
const data = made.get(cid) ?? read.get(cid);
if (!data) continue;
const node = cborDecode(data);
if (node.l) next.push(cidToString(node.l));
for (const entry of node.e || []) {
if (entry.t) next.push(cidToString(entry.t));
}
}
return [...read.keys()].filter((cid) => !reached.has(cid));
}
/**
* Get MST proof blocks for a specific record
* Returns all blocks needed to verify the record exists in the MST
* @param {string} rootCid - MST root CID
* @param {string} targetKey - Key to find (collection/rkey)
* @param {(cid: string) => Promise<Uint8Array|null>} getBlock
* @returns {Promise<Array<{cid: string, data: Uint8Array}>>}
*/
export async function getMstProof(rootCid, targetKey, getBlock) {
/** @type {Array<{cid: string, data: Uint8Array}>} */
const proofBlocks = [];
const _targetKeyBytes = new TextEncoder().encode(targetKey);
/**
* @param {string} nodeCid
* @param {Uint8Array} prevKeyBytes
* @returns {Promise<boolean>} - true if found
*/
async function findPath(nodeCid, prevKeyBytes) {
const data = await getBlock(nodeCid);
if (!data) return false;
proofBlocks.push({ cid: nodeCid, data });
const node = cborDecode(data);
// Check left subtree
if (node.l) {
// We need to check if target might be in left subtree
// For now, include the path - a proper implementation would check bounds
const found = await findPath(cidToString(node.l), prevKeyBytes);
if (found) return true;
}
// Check entries
let currentKeyBytes = prevKeyBytes;
for (const entry of node.e || []) {
// Reconstruct key
const prefix = currentKeyBytes.slice(0, entry.p);
const suffix = entry.k;
const keyBytes = new Uint8Array(prefix.length + suffix.length);
keyBytes.set(prefix);
keyBytes.set(suffix, prefix.length);
currentKeyBytes = keyBytes;
const key = new TextDecoder().decode(keyBytes);
if (key === targetKey) {
return true;
}
// Check subtree
if (entry.t) {
const found = await findPath(cidToString(entry.t), currentKeyBytes);
if (found) return true;
}
}
return false;
}
await findPath(rootCid, new Uint8Array(0));
return proofBlocks;
}
// ────────────────────────────────────────────────────────────────────────────
// Incremental updates
//
// buildMst above rebuilds the whole tree, which costs O(n) per commit. These
// operations touch only the nodes on one root-to-key path, relying on content
// addressing for structural sharing: an untouched child keeps its CID, so it
// needs no rewrite. They must produce byte-identical trees to buildMst —
// packages/core/test/mst-incremental.test.js asserts that against it.
//
// Layers are dense: a child sits exactly one layer below its parent, and a
// skipped layer is represented by an entry-less node carrying only `l`. The
// algorithm follows the AT Protocol MST spec, as implemented by
// bluesky-social/atproto (dual MIT/Apache-2.0).
// ────────────────────────────────────────────────────────────────────────────
/**
* @typedef {Object} MstNodeEntry
* @property {string} key - Full key
* @property {string} value - Record CID
* @property {string|null} right - Subtree covering keys after this entry
*/
/**
* @typedef {Object} MstNode
* @property {string|null} left - Subtree covering keys before the first entry
* @property {MstNodeEntry[]} entries
*/
/**
* @typedef {Object} MstStore
* @property {(cid: string) => Promise<Uint8Array|null>} getBlock
* @property {(cid: string, data: Uint8Array) => Promise<void>} putBlock
*/
/**
* Decode a stored MST node, undoing prefix compression.
* @param {Uint8Array} bytes
* @returns {MstNode}
*/
function decodeMstNode(bytes) {
const raw = cborDecode(bytes);
/** @type {MstNodeEntry[]} */
const entries = [];
let prevBytes = new Uint8Array(0);
for (const e of raw.e || []) {
const keyBytes = new Uint8Array(e.p + e.k.length);
keyBytes.set(prevBytes.subarray(0, e.p));
keyBytes.set(e.k, e.p);
entries.push({
key: new TextDecoder().decode(keyBytes),
value: cidToString(e.v),
right: e.t ? cidToString(e.t) : null,
});
prevBytes = keyBytes;
}
return { left: raw.l ? cidToString(raw.l) : null, entries };
}
/**
* Store a node, re-applying prefix compression. Returns null for a node with
* nothing in it, which the parent records as an absent subtree.
* @param {MstNode} node
* @param {MstStore} store
* @returns {Promise<string|null>}
*/
async function storeMstNode(node, store) {
if (node.entries.length === 0 && !node.left) return null;
/** @type {Array<{p: number, k: Uint8Array, v: CID, t: CID|null}>} */
const e = [];
let prevBytes = new Uint8Array(0);
for (const entry of node.entries) {
const keyBytes = new TextEncoder().encode(entry.key);
const p = commonPrefixLen(prevBytes, keyBytes);
e.push({
p,
k: keyBytes.slice(p),
v: new CID(cidToBytes(entry.value)),
t: entry.right ? new CID(cidToBytes(entry.right)) : null,
});
prevBytes = keyBytes;
}
const bytes = cborEncodeDagCbor({
e,
l: node.left ? new CID(cidToBytes(node.left)) : null,
});
const cid = cidToString(await createCid(bytes));
await store.putBlock(cid, bytes);
return cid;
}
/**
* @param {string} cid
* @param {MstStore} store
* @returns {Promise<MstNode>}
*/
async function loadMstNode(cid, store) {
const bytes = await store.getBlock(cid);
if (!bytes) throw new Error(`Missing MST node: ${cid}`);
return decodeMstNode(bytes);
}
/**
* Index at which `key` belongs among sorted entries.
* @param {MstNodeEntry[]} entries
* @param {string} key
* @returns {number}
*/
function indexFor(entries, key) {
let i = 0;
while (i < entries.length && entries[i].key < key) i++;
return i;
}
/**
* Layer of the tree rooted at `cid`, derived from the depth of a key it holds.
* @param {string|null} cid
* @param {MstStore} store
* @returns {Promise<number|null>}
*/
async function treeLayer(cid, store) {
if (!cid) return null;
const node = await loadMstNode(cid, store);
if (node.entries.length > 0) return getKeyDepth(node.entries[0].key);
if (node.left) {
const below = await treeLayer(node.left, store);
return below === null ? null : below + 1;
}
return null;
}
/**
* Split a subtree into the parts holding keys below and above `key`.
* @param {string|null} cid
* @param {number} layer
* @param {string} key
* @param {MstStore} store
* @returns {Promise<[string|null, string|null]>}
*/
async function splitAround(cid, layer, key, store) {
if (!cid) return [null, null];
const node = await loadMstNode(cid, store);
const i = indexFor(node.entries, key);
// The subtree spanning the split point has to be divided as well
const straddling = i === 0 ? node.left : node.entries[i - 1].right;
const [innerLeft, innerRight] = straddling
? await splitAround(straddling, layer - 1, key, store)
: [null, null];
const leftEntries = node.entries.slice(0, i).map((e) => ({ ...e }));
if (i > 0) leftEntries[i - 1].right = innerLeft;
const left = await storeMstNode(
{ left: i === 0 ? innerLeft : node.left, entries: leftEntries },
store,
);
const right = await storeMstNode(
{ left: innerRight, entries: node.entries.slice(i).map((e) => ({ ...e })) },
store,
);
return [left, right];
}
/**
* Join two subtrees covering adjacent key ranges.
* @param {string|null} leftCid
* @param {string|null} rightCid
* @param {number} layer
* @param {MstStore} store
* @returns {Promise<string|null>}
*/
async function mergeTrees(leftCid, rightCid, layer, store) {
if (!leftCid) return rightCid;
if (!rightCid) return leftCid;
const left = await loadMstNode(leftCid, store);
const right = await loadMstNode(rightCid, store);
if (left.entries.length === 0) {
// Nothing at this layer on the left: its subtree joins the right's
const merged = await mergeTrees(left.left, right.left, layer - 1, store);
return storeMstNode(
{ left: merged, entries: right.entries.map((e) => ({ ...e })) },
store,
);
}
const entries = [
...left.entries.map((e) => ({ ...e })),
...right.entries.map((e) => ({ ...e })),
];
const seam = left.entries.length - 1;
entries[seam].right = await mergeTrees(
left.entries[seam].right,
right.left,
layer - 1,
store,
);
return storeMstNode({ left: left.left, entries }, store);
}
/**
* @param {string|null} cid
* @param {number} layer
* @param {string} key
* @param {number} depth
* @param {string} value
* @param {MstStore} store
* @returns {Promise<string|null>}
*/
async function addRecurse(cid, layer, key, depth, value, store) {
const node = cid
? await loadMstNode(cid, store)
: /** @type {MstNode} */ ({ left: null, entries: [] });
const i = indexFor(node.entries, key);
if (depth === layer) {
// A key already sitting at this position takes the new value in place.
// Splicing beside it would leave two entries sharing a key, which breaks
// the strict ordering every verifier checks: the repo stops being
// provable, and consumers that require proofs drop it entirely.
if (node.entries[i]?.key === key) {
const entries = node.entries.map((e) => ({ ...e }));
entries[i].value = value;
return storeMstNode({ left: node.left, entries }, store);
}
// Belongs in this node; anything spanning its position splits around it
const straddling = i === 0 ? node.left : node.entries[i - 1].right;
const [innerLeft, innerRight] = straddling
? await splitAround(straddling, layer - 1, key, store)
: [null, null];
const entries = node.entries.map((e) => ({ ...e }));
entries.splice(i, 0, { key, value, right: innerRight });
if (i > 0) entries[i - 1].right = innerLeft;
return storeMstNode(
{ left: i === 0 ? innerLeft : node.left, entries },
store,
);
}
// Belongs further down; descend into the subtree covering its position
const target = i === 0 ? node.left : node.entries[i - 1].right;
const child = await addRecurse(target, layer - 1, key, depth, value, store);
const entries = node.entries.map((e) => ({ ...e }));
if (i > 0) entries[i - 1].right = child;
return storeMstNode({ left: i === 0 ? child : node.left, entries }, store);
}
/**
* Add a key to the tree, returning the new root CID.
* @param {string|null} rootCid - Existing root, or null for an empty tree
* @param {string} key - Full key (collection/rkey)
* @param {string} value - Record CID
* @param {MstStore} store
* @returns {Promise<string|null>}
*/
export async function mstAdd(rootCid, key, value, store) {
const depth = await getKeyDepth(key);
if (!rootCid) {
return storeMstNode(
{ left: null, entries: [{ key, value, right: null }] },
store,
);
}
const layer = /** @type {number} */ (await treeLayer(rootCid, store));
if (depth <= layer) {
return addRecurse(rootCid, layer, key, depth, value, store);
}
// Deeper than the current root: the existing tree splits and sinks beneath a
// new root, with entry-less nodes filling any layers the key skips over.
let [left, right] = await splitAround(rootCid, layer, key, store);
for (let i = 0; i < depth - layer - 1; i++) {
if (left) left = await storeMstNode({ left, entries: [] }, store);
if (right) right = await storeMstNode({ left: right, entries: [] }, store);
}
return storeMstNode({ left, entries: [{ key, value, right }] }, store);
}
/**
* @param {string|null} cid
* @param {number} layer
* @param {string} key
* @param {number} depth
* @param {MstStore} store
* @returns {Promise<string|null>}
*/
async function deleteRecurse(cid, layer, key, depth, store) {
if (!cid) return null;
const node = await loadMstNode(cid, store);
if (depth === layer) {
const idx = node.entries.findIndex((e) => e.key === key);
if (idx === -1) return cid;
// The subtrees on either side of the removed entry become adjacent
const before = idx === 0 ? node.left : node.entries[idx - 1].right;
const merged = await mergeTrees(
before,
node.entries[idx].right,
layer - 1,
store,
);
const entries = node.entries
.filter((_, i) => i !== idx)
.map((e) => ({ ...e }));
if (idx > 0) entries[idx - 1].right = merged;
return storeMstNode(
{ left: idx === 0 ? merged : node.left, entries },
store,
);
}
const i = indexFor(node.entries, key);
const target = i === 0 ? node.left : node.entries[i - 1].right;
const child = await deleteRecurse(target, layer - 1, key, depth, store);
const entries = node.entries.map((e) => ({ ...e }));
if (i > 0) entries[i - 1].right = child;
return storeMstNode({ left: i === 0 ? child : node.left, entries }, store);
}
/**
* Remove a key from the tree, returning the new root CID (null when empty).
* @param {string|null} rootCid
* @param {string} key
* @param {MstStore} store
* @returns {Promise<string|null>}
*/
export async function mstDelete(rootCid, key, store) {
if (!rootCid) return null;
const depth = await getKeyDepth(key);
const layer = /** @type {number} */ (await treeLayer(rootCid, store));
if (depth > layer) return rootCid;
let root = await deleteRecurse(rootCid, layer, key, depth, store);
// Removing the deepest key can leave entry-less layers on top
while (root) {
const node = await loadMstNode(root, store);
if (node.entries.length > 0 || !node.left) break;
root = node.left;
}
return root;
}
/**
* @param {string} cid
* @param {number} layer
* @param {string} key
* @param {number} depth
* @param {string} value
* @param {MstStore} store
* @returns {Promise<string|null>} New CID, or null if the key was absent
*/
async function updateRecurse(cid, layer, key, depth, value, store) {
const node = await loadMstNode(cid, store);
if (depth === layer) {
const idx = node.entries.findIndex((e) => e.key === key);
if (idx === -1) return null;
const entries = node.entries.map((e) => ({ ...e }));
entries[idx].value = value;
return storeMstNode({ left: node.left, entries }, store);
}
const i = indexFor(node.entries, key);
const target = i === 0 ? node.left : node.entries[i - 1].right;
if (!target) return null;
const child = await updateRecurse(
target,
layer - 1,
key,
depth,
value,
store,
);
if (child === null) return null;
const entries = node.entries.map((e) => ({ ...e }));
if (i > 0) entries[i - 1].right = child;
return storeMstNode({ left: i === 0 ? child : node.left, entries }, store);
}
/**
* The record CID stored at `key`, or null if the tree does not hold it.
* @param {string|null} rootCid
* @param {string} key
* @param {MstStore} store
* @returns {Promise<string|null>}
*/
export async function mstGet(rootCid, key, store) {
let cid = rootCid;
while (cid) {
const node = await loadMstNode(cid, store);
const i = indexFor(node.entries, key);
if (node.entries[i]?.key === key) return node.entries[i].value;
cid = i === 0 ? node.left : node.entries[i - 1].right;
}
return null;
}
/**
* Replace the value at an existing key. The key set is unchanged, so the tree
* keeps its shape. Returns the root unchanged if the key is absent.
* @param {string|null} rootCid
* @param {string} key
* @param {string} value - New record CID
* @param {MstStore} store
* @returns {Promise<string|null>}
*/
export async function mstUpdate(rootCid, key, value, store) {
if (!rootCid) return null;
const depth = await getKeyDepth(key);
const layer = /** @type {number} */ (await treeLayer(rootCid, store));
if (depth > layer) return rootCid;
const updated = await updateRecurse(rootCid, layer, key, depth, value, store);
return updated ?? rootCid;
}
/**
* Undo `ops` on the tree rooted at `rootCid`, as a sync 1.1 consumer checks a
* commit: a create is deleted, an update and a delete put back the CID they
* replaced (`prev`). Returns the root that leaves, which for a sound commit
* is the previous one, and every block undoing read from `getBlock`, by CID.
* Nodes undoing makes are kept apart, and not counted as read.
* @param {string|null} rootCid
* @param {Array<{action: string, key: string, prev?: string}>} ops - In the order applied
* @param {(cid: string) => Promise<Uint8Array|null>} getBlock
* @returns {Promise<{root: string|null, read: Map<string, Uint8Array>}>}
*/
export async function mstInvert(rootCid, ops, getBlock) {
/** @type {Map<string, Uint8Array>} */
const made = new Map();
/** @type {Map<string, Uint8Array>} */
const read = new Map();
/** @type {MstStore} */
const store = {
async getBlock(cid) {
const ours = made.get(cid);
if (ours) return ours;
const data = await getBlock(cid);
if (data) read.set(cid, data);
return data;
},
async putBlock(cid, data) {
made.set(cid, data);
},
};
let root = rootCid;
for (const op of [...ops].reverse()) {
if (op.action === 'create') {
root = await mstDelete(root, op.key, store);
} else if (op.prev && op.action === 'update') {
root = await mstUpdate(root, op.key, op.prev, store);
} else if (op.prev && op.action === 'delete') {
root = await mstAdd(root, op.key, op.prev, store);
}
}
return { root, read };
}