atproto user agency toolkit for individuals and groups
1import { describe, it, expect, beforeEach, afterEach } from "vitest";
2import { mkdtempSync, rmSync } from "node:fs";
3import { tmpdir } from "node:os";
4import { join } from "node:path";
5import Database from "better-sqlite3";
6import { IpfsService } from "../ipfs.js";
7import { RepoManager } from "../repo-manager.js";
8import type { Config } from "../config.js";
9import { readCarWithRoot } from "@atproto/repo";
10import { generateMstProof, verifyMstProof, extractAllRecordPaths, extractAllCids } from "./mst-proof.js";
11
12function testConfig(dataDir: string): Config {
13 return {
14 DID: "did:plc:test123",
15 HANDLE: "test.example.com",
16 PDS_HOSTNAME: "test.example.com",
17 AUTH_TOKEN: "test-auth-token",
18 SIGNING_KEY:
19 "0000000000000000000000000000000000000000000000000000000000000001",
20 SIGNING_KEY_PUBLIC:
21 "zQ3shP2mWsZYWgvZM9GJ3EvMfRXQJwuTh6BdXLvJB9gFhT3Lr",
22 JWT_SECRET: "test-jwt-secret",
23 PASSWORD_HASH: "$2a$10$test",
24 DATA_DIR: dataDir,
25 PORT: 3000,
26 IPFS_ENABLED: true,
27 IPFS_NETWORKING: false,
28 REPLICATE_DIDS: [],
29 FIREHOSE_URL: "wss://localhost/xrpc/com.atproto.sync.subscribeRepos",
30 FIREHOSE_ENABLED: false,
31 RATE_LIMIT_ENABLED: false,
32 RATE_LIMIT_READ_PER_MIN: 300,
33 RATE_LIMIT_SYNC_PER_MIN: 30,
34 RATE_LIMIT_SESSION_PER_MIN: 10,
35 RATE_LIMIT_WRITE_PER_MIN: 200,
36 RATE_LIMIT_CHALLENGE_PER_MIN: 20,
37 RATE_LIMIT_MAX_CONNECTIONS: 100,
38 RATE_LIMIT_FIREHOSE_PER_IP: 3,
39 OAUTH_ENABLED: false, PUBLIC_URL: "http://localhost:3000",
40 };
41}
42
43describe("MST Path Proof", () => {
44 let tmpDir: string;
45 let db: InstanceType<typeof Database>;
46 let ipfsService: IpfsService;
47 let repoManager: RepoManager;
48
49 beforeEach(async () => {
50 tmpDir = mkdtempSync(join(tmpdir(), "mst-proof-test-"));
51 const config = testConfig(tmpDir);
52
53 db = new Database(join(tmpDir, "test.db"));
54 ipfsService = new IpfsService({
55 db,
56 networking: false,
57 });
58 await ipfsService.start();
59
60 repoManager = new RepoManager(db, config);
61 repoManager.init(undefined, ipfsService, ipfsService);
62 });
63
64 afterEach(async () => {
65 if (ipfsService.isRunning()) {
66 await ipfsService.stop();
67 }
68 db.close();
69 rmSync(tmpDir, { recursive: true, force: true });
70 });
71
72 /**
73 * Helper: create records, export CAR, store blocks in IPFS, return root CID.
74 */
75 async function getRepoRootCid(): Promise<string> {
76 const carBytes = await repoManager.getRepoCar();
77 const { root, blocks } = await readCarWithRoot(carBytes);
78 await ipfsService.putBlocks(blocks);
79 return root.toString();
80 }
81
82 // ============================================
83 // Existence proofs
84 // ============================================
85
86 it("generates and verifies an existence proof for a single record", async () => {
87 await repoManager.createRecord("app.bsky.feed.post", undefined, {
88 $type: "app.bsky.feed.post",
89 text: "Hello, world!",
90 createdAt: "2025-01-01T00:00:00.000Z",
91 });
92
93 const rootCid = await getRepoRootCid();
94
95 // Get the record's rkey
96 const records = await repoManager.listRecords("app.bsky.feed.post", {
97 limit: 10,
98 });
99 const rkey = records.records[0]!.uri.split("/").pop()!;
100 const recordPath = `app.bsky.feed.post/${rkey}`;
101
102 // Generate proof
103 const proof = await generateMstProof(ipfsService, rootCid, recordPath);
104
105 expect(proof.found).toBe(true);
106 expect(proof.recordCid).not.toBeNull();
107 expect(proof.commitBlock.cid).toBe(rootCid);
108 expect(proof.nodes.length).toBeGreaterThan(0);
109
110 // Verify proof
111 const verification = await verifyMstProof(proof, rootCid, recordPath);
112
113 expect(verification.valid).toBe(true);
114 expect(verification.found).toBe(true);
115 expect(verification.recordCid).toBe(proof.recordCid);
116 expect(verification.error).toBeUndefined();
117 });
118
119 it("generates and verifies proof with multiple records", async () => {
120 // Create several records to build a deeper MST
121 for (let i = 0; i < 10; i++) {
122 await repoManager.createRecord("app.bsky.feed.post", undefined, {
123 $type: "app.bsky.feed.post",
124 text: `Post number ${i}`,
125 createdAt: new Date().toISOString(),
126 });
127 }
128
129 const rootCid = await getRepoRootCid();
130
131 // Get all records and verify proofs for each
132 const records = await repoManager.listRecords("app.bsky.feed.post", {
133 limit: 100,
134 });
135
136 for (const record of records.records) {
137 const rkey = record.uri.split("/").pop()!;
138 const recordPath = `app.bsky.feed.post/${rkey}`;
139
140 const proof = await generateMstProof(
141 ipfsService,
142 rootCid,
143 recordPath,
144 );
145
146 expect(proof.found).toBe(true);
147 expect(proof.recordCid).not.toBeNull();
148
149 const verification = await verifyMstProof(
150 proof,
151 rootCid,
152 recordPath,
153 );
154 expect(verification.valid).toBe(true);
155 expect(verification.found).toBe(true);
156 }
157 });
158
159 it("generates and verifies proof for records in different collections", async () => {
160 await repoManager.createRecord("app.bsky.feed.post", undefined, {
161 $type: "app.bsky.feed.post",
162 text: "A post",
163 createdAt: new Date().toISOString(),
164 });
165
166 await repoManager.putRecord("app.bsky.actor.profile", "self", {
167 $type: "app.bsky.actor.profile",
168 displayName: "Test User",
169 });
170
171 const rootCid = await getRepoRootCid();
172
173 // Verify post
174 const posts = await repoManager.listRecords("app.bsky.feed.post", {
175 limit: 10,
176 });
177 const postRkey = posts.records[0]!.uri.split("/").pop()!;
178 const postPath = `app.bsky.feed.post/${postRkey}`;
179
180 const postProof = await generateMstProof(
181 ipfsService,
182 rootCid,
183 postPath,
184 );
185 expect(postProof.found).toBe(true);
186 const postVerification = await verifyMstProof(
187 postProof,
188 rootCid,
189 postPath,
190 );
191 expect(postVerification.valid).toBe(true);
192 expect(postVerification.found).toBe(true);
193
194 // Verify profile
195 const profilePath = "app.bsky.actor.profile/self";
196 const profileProof = await generateMstProof(
197 ipfsService,
198 rootCid,
199 profilePath,
200 );
201 expect(profileProof.found).toBe(true);
202 const profileVerification = await verifyMstProof(
203 profileProof,
204 rootCid,
205 profilePath,
206 );
207 expect(profileVerification.valid).toBe(true);
208 expect(profileVerification.found).toBe(true);
209 });
210
211 // ============================================
212 // Non-existence proofs
213 // ============================================
214
215 it("generates and verifies a non-existence proof", async () => {
216 await repoManager.createRecord("app.bsky.feed.post", undefined, {
217 $type: "app.bsky.feed.post",
218 text: "Only post",
219 createdAt: new Date().toISOString(),
220 });
221
222 const rootCid = await getRepoRootCid();
223
224 // Use a path that definitely does not exist
225 const nonExistentPath = "app.bsky.feed.post/nonexistent-rkey-12345";
226
227 const proof = await generateMstProof(
228 ipfsService,
229 rootCid,
230 nonExistentPath,
231 );
232
233 expect(proof.found).toBe(false);
234 expect(proof.recordCid).toBeNull();
235
236 const verification = await verifyMstProof(
237 proof,
238 rootCid,
239 nonExistentPath,
240 );
241
242 expect(verification.valid).toBe(true);
243 expect(verification.found).toBe(false);
244 expect(verification.recordCid).toBeNull();
245 });
246
247 it("non-existence proof for nonexistent collection", async () => {
248 await repoManager.createRecord("app.bsky.feed.post", undefined, {
249 $type: "app.bsky.feed.post",
250 text: "Post in a real collection",
251 createdAt: new Date().toISOString(),
252 });
253
254 const rootCid = await getRepoRootCid();
255
256 const nonExistentPath = "com.example.nonexistent/abc123";
257
258 const proof = await generateMstProof(
259 ipfsService,
260 rootCid,
261 nonExistentPath,
262 );
263
264 expect(proof.found).toBe(false);
265 expect(proof.recordCid).toBeNull();
266
267 const verification = await verifyMstProof(
268 proof,
269 rootCid,
270 nonExistentPath,
271 );
272 expect(verification.valid).toBe(true);
273 expect(verification.found).toBe(false);
274 });
275
276 // ============================================
277 // Proof compactness
278 // ============================================
279
280 it("proof is compact: fewer blocks than total MST", async () => {
281 // Create enough records to build a multi-level MST
282 for (let i = 0; i < 20; i++) {
283 await repoManager.createRecord("app.bsky.feed.post", undefined, {
284 $type: "app.bsky.feed.post",
285 text: `Post ${i} for compactness test`,
286 createdAt: new Date().toISOString(),
287 });
288 }
289
290 const rootCid = await getRepoRootCid();
291
292 const records = await repoManager.listRecords("app.bsky.feed.post", {
293 limit: 100,
294 });
295 const rkey = records.records[0]!.uri.split("/").pop()!;
296 const recordPath = `app.bsky.feed.post/${rkey}`;
297
298 const proof = await generateMstProof(
299 ipfsService,
300 rootCid,
301 recordPath,
302 );
303
304 // The proof should have:
305 // - 1 commit block
306 // - N MST node blocks (path from root to leaf)
307 // For a tree with 20+ entries, this should be fewer blocks than the total tree
308 const totalProofBlocks = 1 + proof.nodes.length; // commit + MST nodes
309 // 20 records => several MST nodes in total; proof should be a subset
310 expect(totalProofBlocks).toBeLessThanOrEqual(10);
311 expect(proof.found).toBe(true);
312 });
313
314 // ============================================
315 // Verification failure cases
316 // ============================================
317
318 it("verification fails with wrong commit CID", async () => {
319 await repoManager.createRecord("app.bsky.feed.post", undefined, {
320 $type: "app.bsky.feed.post",
321 text: "Wrong CID test",
322 createdAt: new Date().toISOString(),
323 });
324
325 const rootCid = await getRepoRootCid();
326
327 const records = await repoManager.listRecords("app.bsky.feed.post", {
328 limit: 10,
329 });
330 const rkey = records.records[0]!.uri.split("/").pop()!;
331 const recordPath = `app.bsky.feed.post/${rkey}`;
332
333 const proof = await generateMstProof(
334 ipfsService,
335 rootCid,
336 recordPath,
337 );
338
339 // Verify with a wrong commit CID
340 const fakeCommitCid =
341 "bafyreig6mxqmjlb7yjbhhhz6vqmtiw4kgipvhqoowdkggjlpzpd5tcm4";
342 const verification = await verifyMstProof(
343 proof,
344 fakeCommitCid,
345 recordPath,
346 );
347
348 expect(verification.valid).toBe(false);
349 expect(verification.error).toContain("Commit block CID mismatch");
350 });
351
352 it("verification fails with tampered node bytes", async () => {
353 await repoManager.createRecord("app.bsky.feed.post", undefined, {
354 $type: "app.bsky.feed.post",
355 text: "Tamper test",
356 createdAt: new Date().toISOString(),
357 });
358
359 const rootCid = await getRepoRootCid();
360
361 const records = await repoManager.listRecords("app.bsky.feed.post", {
362 limit: 10,
363 });
364 const rkey = records.records[0]!.uri.split("/").pop()!;
365 const recordPath = `app.bsky.feed.post/${rkey}`;
366
367 const proof = await generateMstProof(
368 ipfsService,
369 rootCid,
370 recordPath,
371 );
372
373 // Tamper with the first MST node
374 const tamperedProof = {
375 ...proof,
376 nodes: proof.nodes.map((node, i) => {
377 if (i === 0) {
378 // Flip a byte
379 const tampered = new Uint8Array(node.bytes);
380 tampered[tampered.length - 1] =
381 (tampered[tampered.length - 1]! ^ 0xff) & 0xff;
382 return { ...node, bytes: tampered };
383 }
384 return node;
385 }),
386 };
387
388 const verification = await verifyMstProof(
389 tamperedProof,
390 rootCid,
391 recordPath,
392 );
393
394 expect(verification.valid).toBe(false);
395 });
396
397 it("verification fails with wrong record path", async () => {
398 await repoManager.createRecord("app.bsky.feed.post", undefined, {
399 $type: "app.bsky.feed.post",
400 text: "Wrong path test",
401 createdAt: new Date().toISOString(),
402 });
403
404 const rootCid = await getRepoRootCid();
405
406 const records = await repoManager.listRecords("app.bsky.feed.post", {
407 limit: 10,
408 });
409 const rkey = records.records[0]!.uri.split("/").pop()!;
410 const recordPath = `app.bsky.feed.post/${rkey}`;
411
412 const proof = await generateMstProof(
413 ipfsService,
414 rootCid,
415 recordPath,
416 );
417
418 // Verify against a different path — the proof says found=true but
419 // the verification will walk the nodes with the wrong path
420 const wrongPath = "app.bsky.feed.post/totally-wrong-rkey";
421 const verification = await verifyMstProof(
422 proof,
423 rootCid,
424 wrongPath,
425 );
426
427 // The proof was generated for a different path, so either:
428 // - The verifier will not find the record at the wrong path (found mismatch)
429 // - Or the node chain won't be valid
430 expect(verification.valid).toBe(false);
431 });
432
433 it("verification fails with empty nodes array", async () => {
434 await repoManager.createRecord("app.bsky.feed.post", undefined, {
435 $type: "app.bsky.feed.post",
436 text: "Empty nodes test",
437 createdAt: new Date().toISOString(),
438 });
439
440 const rootCid = await getRepoRootCid();
441
442 const records = await repoManager.listRecords("app.bsky.feed.post", {
443 limit: 10,
444 });
445 const rkey = records.records[0]!.uri.split("/").pop()!;
446 const recordPath = `app.bsky.feed.post/${rkey}`;
447
448 const proof = await generateMstProof(
449 ipfsService,
450 rootCid,
451 recordPath,
452 );
453
454 const emptyProof = { ...proof, nodes: [] };
455 const verification = await verifyMstProof(
456 emptyProof,
457 rootCid,
458 recordPath,
459 );
460
461 expect(verification.valid).toBe(false);
462 expect(verification.error).toContain("no MST nodes");
463 });
464
465 // ============================================
466 // Edge cases
467 // ============================================
468
469 it("handles a repo with a single record", async () => {
470 await repoManager.putRecord("app.bsky.actor.profile", "self", {
471 $type: "app.bsky.actor.profile",
472 displayName: "Solo",
473 });
474
475 const rootCid = await getRepoRootCid();
476 const recordPath = "app.bsky.actor.profile/self";
477
478 const proof = await generateMstProof(
479 ipfsService,
480 rootCid,
481 recordPath,
482 );
483
484 expect(proof.found).toBe(true);
485 expect(proof.nodes.length).toBeGreaterThanOrEqual(1);
486
487 const verification = await verifyMstProof(proof, rootCid, recordPath);
488 expect(verification.valid).toBe(true);
489 expect(verification.found).toBe(true);
490 });
491
492 it("handles many records to create a deeper tree", async () => {
493 // Create 50 records to ensure multi-level MST
494 for (let i = 0; i < 50; i++) {
495 await repoManager.createRecord("app.bsky.feed.post", undefined, {
496 $type: "app.bsky.feed.post",
497 text: `Deep tree post ${i}`,
498 createdAt: new Date().toISOString(),
499 });
500 }
501
502 const rootCid = await getRepoRootCid();
503
504 const records = await repoManager.listRecords("app.bsky.feed.post", {
505 limit: 100,
506 });
507
508 // Test the first, middle, and last record
509 const indicesToTest = [
510 0,
511 Math.floor(records.records.length / 2),
512 records.records.length - 1,
513 ];
514
515 for (const idx of indicesToTest) {
516 const record = records.records[idx]!;
517 const rkey = record.uri.split("/").pop()!;
518 const recordPath = `app.bsky.feed.post/${rkey}`;
519
520 const proof = await generateMstProof(
521 ipfsService,
522 rootCid,
523 recordPath,
524 );
525
526 expect(proof.found).toBe(true);
527 expect(proof.recordCid).not.toBeNull();
528
529 const verification = await verifyMstProof(
530 proof,
531 rootCid,
532 recordPath,
533 );
534
535 expect(verification.valid).toBe(true);
536 expect(verification.found).toBe(true);
537 expect(verification.recordCid).toBe(proof.recordCid);
538 }
539 });
540
541 it("generate throws when commit block is missing", async () => {
542 await expect(
543 generateMstProof(
544 ipfsService,
545 "bafyreig6mxqmjlb7yjbhhhz6vqmtiw4kgipvhqoowdkggjlpzpd5tcm4",
546 "app.bsky.feed.post/abc",
547 ),
548 ).rejects.toThrow("Commit block not found");
549 });
550
551 it("proof roundtrip: generate then verify maintains consistency", async () => {
552 await repoManager.createRecord("app.bsky.feed.post", undefined, {
553 $type: "app.bsky.feed.post",
554 text: "Roundtrip test",
555 createdAt: new Date().toISOString(),
556 });
557
558 const rootCid = await getRepoRootCid();
559
560 const records = await repoManager.listRecords("app.bsky.feed.post", {
561 limit: 10,
562 });
563 const rkey = records.records[0]!.uri.split("/").pop()!;
564 const existingPath = `app.bsky.feed.post/${rkey}`;
565 const missingPath = "app.bsky.feed.post/zzz-does-not-exist";
566
567 // Existence proof roundtrip
568 const existProof = await generateMstProof(
569 ipfsService,
570 rootCid,
571 existingPath,
572 );
573 const existVerify = await verifyMstProof(
574 existProof,
575 rootCid,
576 existingPath,
577 );
578 expect(existVerify.valid).toBe(true);
579 expect(existVerify.found).toBe(true);
580
581 // Non-existence proof roundtrip
582 const missingProof = await generateMstProof(
583 ipfsService,
584 rootCid,
585 missingPath,
586 );
587 const missingVerify = await verifyMstProof(
588 missingProof,
589 rootCid,
590 missingPath,
591 );
592 expect(missingVerify.valid).toBe(true);
593 expect(missingVerify.found).toBe(false);
594 });
595
596 // ============================================
597 // extractAllRecordPaths
598 // ============================================
599
600 it("extractAllRecordPaths returns all record paths", async () => {
601 await repoManager.createRecord("app.bsky.feed.post", undefined, {
602 $type: "app.bsky.feed.post",
603 text: "Post one",
604 createdAt: new Date().toISOString(),
605 });
606 await repoManager.createRecord("app.bsky.feed.post", undefined, {
607 $type: "app.bsky.feed.post",
608 text: "Post two",
609 createdAt: new Date().toISOString(),
610 });
611 await repoManager.putRecord("app.bsky.actor.profile", "self", {
612 $type: "app.bsky.actor.profile",
613 displayName: "Test User",
614 });
615
616 const rootCid = await getRepoRootCid();
617
618 const paths = await extractAllRecordPaths(ipfsService, rootCid);
619
620 // Should find all three records
621 expect(paths.length).toBe(3);
622 expect(paths.filter((p) => p.startsWith("app.bsky.feed.post/")).length).toBe(2);
623 expect(paths).toContain("app.bsky.actor.profile/self");
624 });
625
626 it("extractAllRecordPaths returns sorted paths for a large repo", async () => {
627 for (let i = 0; i < 30; i++) {
628 await repoManager.createRecord("app.bsky.feed.post", undefined, {
629 $type: "app.bsky.feed.post",
630 text: `Post ${i}`,
631 createdAt: new Date().toISOString(),
632 });
633 }
634
635 const rootCid = await getRepoRootCid();
636 const paths = await extractAllRecordPaths(ipfsService, rootCid);
637
638 expect(paths.length).toBe(30);
639 // MST in-order walk produces sorted keys
640 const sorted = [...paths].sort();
641 expect(paths).toEqual(sorted);
642 });
643
644 it("extractAllRecordPaths returns empty for missing commit", async () => {
645 const paths = await extractAllRecordPaths(
646 ipfsService,
647 "bafyreig6mxqmjlb7yjbhhhz6vqmtiw4kgipvhqoowdkggjlpzpd5tcm4",
648 );
649 expect(paths).toEqual([]);
650 });
651
652 // ============================================
653 // extractAllCids
654 // ============================================
655
656 it("extractAllCids returns all reachable CIDs", async () => {
657 await repoManager.createRecord("app.bsky.feed.post", undefined, {
658 $type: "app.bsky.feed.post",
659 text: "CID walk test",
660 createdAt: new Date().toISOString(),
661 });
662 await repoManager.createRecord("app.bsky.feed.post", undefined, {
663 $type: "app.bsky.feed.post",
664 text: "Another post",
665 createdAt: new Date().toISOString(),
666 });
667
668 const rootCid = await getRepoRootCid();
669
670 const cids = await extractAllCids(ipfsService, rootCid);
671
672 // Should include at least: commit CID, MST root, MST nodes, record value CIDs
673 expect(cids.size).toBeGreaterThanOrEqual(4);
674 // The commit CID itself should be in the set
675 expect(cids.has(rootCid)).toBe(true);
676 });
677
678 it("extractAllCids grows with more records", async () => {
679 await repoManager.createRecord("app.bsky.feed.post", undefined, {
680 $type: "app.bsky.feed.post",
681 text: "First post",
682 createdAt: new Date().toISOString(),
683 });
684
685 const rootCid1 = await getRepoRootCid();
686 const cids1 = await extractAllCids(ipfsService, rootCid1);
687
688 // Add more records
689 for (let i = 0; i < 10; i++) {
690 await repoManager.createRecord("app.bsky.feed.post", undefined, {
691 $type: "app.bsky.feed.post",
692 text: `Additional post ${i}`,
693 createdAt: new Date().toISOString(),
694 });
695 }
696
697 const rootCid2 = await getRepoRootCid();
698 const cids2 = await extractAllCids(ipfsService, rootCid2);
699
700 // More records = more CIDs
701 expect(cids2.size).toBeGreaterThan(cids1.size);
702 });
703
704 it("extractAllCids returns only commit CID for missing data", async () => {
705 const fakeCid = "bafyreig6mxqmjlb7yjbhhhz6vqmtiw4kgipvhqoowdkggjlpzpd5tcm4";
706 const cids = await extractAllCids(ipfsService, fakeCid);
707 // Only the commit CID itself (data can't be loaded)
708 expect(cids.size).toBe(1);
709 expect(cids.has(fakeCid)).toBe(true);
710 });
711});