Suite of AT Protocol TypeScript libraries built on web standards
1import { parseCid } from "@atp/lex/data";
2import { MST } from "../mst/index.ts";
3import { BlockMap, MemoryBlockstore } from "../mod.ts";
4import fixtures from "./commit-proof-fixtures.json" with { type: "json" };
5import { assert, assertEquals } from "@std/assert";
6
7for (const fixture of fixtures) {
8 Deno.test(fixture.comment, async () => {
9 const { leafValue, keys, adds, dels } = fixture;
10 const leaf = parseCid(leafValue);
11
12 const storage = new MemoryBlockstore();
13 let mst = await MST.create(storage);
14 for (const key of keys) {
15 mst = await mst.add(key, leaf);
16 }
17
18 const rootBeforeCommit = await mst.getPointer();
19 assertEquals(rootBeforeCommit.toString(), fixture.rootBeforeCommit);
20
21 for (const key of adds) {
22 mst = await mst.add(key, leaf);
23 }
24 for (const key of dels) {
25 mst = await mst.delete(key);
26 }
27 const rootAfterCommit = await mst.getPointer();
28 assertEquals(rootAfterCommit.toString(), fixture.rootAfterCommit);
29 const proofs = await Promise.all(
30 [...adds, ...dels].map((key) => mst.getCoveringProof(key)),
31 );
32 const proof = proofs.reduce(
33 (acc, cur) => acc.addMap(cur),
34 new BlockMap(),
35 );
36 const blocksInProof = fixture.blocksInProof.map((cid) => parseCid(cid));
37 for (const cid of blocksInProof) {
38 assert(proof.has(cid));
39 }
40
41 const invertAdds = adds.map((k) => (mst: MST) => mst.delete(k));
42 const invertDels = dels.map((k) => (mst: MST) => mst.add(k, leaf));
43 const invertOrders = permutations([...invertAdds, ...invertDels]);
44
45 const proofStorage = new MemoryBlockstore(proof);
46 for (const order of invertOrders) {
47 let proofMst = MST.load(proofStorage, rootAfterCommit);
48 for (const fn of order) {
49 proofMst = await fn(proofMst);
50 }
51 const rootAfterInvert = await proofMst.getPointer();
52 assertEquals(rootAfterInvert.toString(), fixture.rootBeforeCommit);
53 }
54 });
55}
56
57function permutations<T>(arr: T[]): T[][] {
58 if (arr.length <= 1) return [arr];
59
60 return arr.reduce((perms: T[][], item: T, i: number) => {
61 const rest = [...arr.slice(0, i), ...arr.slice(i + 1)];
62 return perms.concat(permutations(rest).map((p) => [item, ...p]));
63 }, []);
64}