vielle.dev
1import * as CAR from "@atcute/car";
2import { CarReader } from "@atcute/car/v4";
3import * as CBOR from "@atcute/cbor";
4import * as CID from "@atcute/cid";
5import { Client } from "@atcute/client";
6import { type FoundPublicKey, getPublicKeyFromDidController, verifySig } from "@atcute/crypto";
7import { type DidDocument, getAtprotoVerificationMaterial } from "@atcute/identity";
8import { Did } from "@atcute/lexicons";
9import { toSha256 } from "@atcute/uint8array";
10
11import { type AddressedAtUri, parseAddressedAtUri } from "./types/at-uri";
12
13export interface VerifyError {
14 message: string;
15 detail?: unknown;
16}
17
18export interface VerifyResult {
19 errors: VerifyError[];
20}
21
22export interface VerifyOptions {
23 rpc: Client;
24 uri: string;
25 cid: string;
26 record: unknown;
27 didDoc: DidDocument;
28}
29
30export const verifyRecord = async (opts: VerifyOptions): Promise<VerifyResult> => {
31 const errors: VerifyError[] = [];
32
33 // verify cid can be parsed
34 try {
35 CID.fromString(opts.cid);
36 } catch (e) {
37 errors.push({ message: `provided cid is invalid`, detail: e });
38 }
39
40 // verify record content matches cid
41 let cbor: Uint8Array;
42 {
43 cbor = CBOR.encode(opts.record);
44
45 const cid = await CID.create(CID.CODEC_DCBOR, cbor);
46 const cidString = CID.toString(cid);
47
48 if (cidString !== opts.cid) {
49 errors.push({ message: `record content does not match cid` });
50 }
51 }
52
53 // verify at-uri is valid
54 let uri: AddressedAtUri;
55 try {
56 uri = parseAddressedAtUri(opts.uri);
57
58 if (uri.repo !== opts.didDoc.id) {
59 errors.push({ message: `repo in at-uri does not match did document` });
60 }
61 } catch (err) {
62 errors.push({ message: `provided at-uri is invalid`, detail: err });
63 return { errors };
64 }
65
66 // grab public key from did document
67 let publicKey: FoundPublicKey;
68 try {
69 const controller = getAtprotoVerificationMaterial(opts.didDoc);
70 if (!controller) {
71 errors.push({
72 message: `did document does not contain verification material`,
73 });
74 return { errors };
75 }
76
77 publicKey = getPublicKeyFromDidController(controller);
78 } catch (err) {
79 errors.push({
80 message: `failed to get public key from did document`,
81 detail: err,
82 });
83 return { errors };
84 }
85
86 // grab the raw record blocks from the pds
87 let car: Uint8Array;
88 const { ok, data } = await opts.rpc.get("com.atproto.sync.getRecord", {
89 params: {
90 did: opts.didDoc.id as Did,
91 collection: uri.collection,
92 rkey: uri.rkey,
93 },
94 as: "bytes",
95 });
96 if (!ok) {
97 errors.push({ message: `failed to fetch car from pds`, detail: data.error });
98 return { errors };
99 } else {
100 car = data;
101 }
102
103 // read the car
104 let blockmap: CAR.BlockMap;
105 let commit: CAR.Commit;
106
107 try {
108 const reader = CarReader.fromUint8Array(car);
109 if (reader.header.data.roots.length !== 1) {
110 errors.push({ message: `car must have exactly one root` });
111 return { errors };
112 }
113
114 blockmap = new Map();
115 for (const entry of reader) {
116 const cidString = CID.toString(entry.cid);
117
118 // Verify that `bytes` matches its associated CID
119 const expectedCid = CID.toString(await CID.create(entry.cid.codec as 85 | 113, entry.bytes));
120 if (cidString !== expectedCid) {
121 errors.push({
122 message: `cid does not match bytes`,
123 detail: { cid: cidString, expectedCid },
124 });
125 }
126
127 blockmap.set(cidString, entry);
128 }
129
130 if (blockmap.size === 0) {
131 errors.push({ message: `car must have at least one block` });
132 return { errors };
133 }
134
135 commit = CAR.readBlock(blockmap, reader.header.data.roots[0], CAR.isCommit);
136 } catch (err) {
137 errors.push({ message: `failed to read car`, detail: err });
138 return { errors };
139 }
140
141 // verify did in commit matches the did in the at-uri
142 if (commit.did !== opts.didDoc.id) {
143 errors.push({ message: `did in commit does not match did document` });
144 }
145
146 // verify signature contained in commit is valid
147 {
148 const { sig, ...unsigned } = commit;
149
150 const data = CBOR.encode(unsigned);
151 const valid = await verifySig(
152 publicKey,
153 CBOR.fromBytes(sig) as Uint8Array<ArrayBuffer>,
154 data as Uint8Array<ArrayBuffer>,
155 );
156
157 if (!valid) {
158 errors.push({ message: `signature verification failed` });
159 }
160 }
161
162 // verify the commit is a valid commit
163 try {
164 const result = await dfs(blockmap, commit.data.$link, opts.cid);
165 if (!result.found) {
166 errors.push({ message: `could not find record in car` });
167 }
168 } catch (err) {
169 errors.push({ message: `failed to iterate over car`, detail: err });
170 }
171
172 return { errors };
173};
174
175interface DfsResult {
176 found: boolean;
177 min?: string;
178 max?: string;
179 depth?: number;
180}
181
182const encoder = new TextEncoder();
183const decoder = new TextDecoder();
184
185const dfs = async (
186 blockmap: CAR.BlockMap,
187 from: string | undefined,
188 target: string,
189 visited = new Set<string>(),
190): Promise<DfsResult> => {
191 // If there's no starting point, return empty state
192 if (from == null) {
193 return { found: false };
194 }
195
196 // Check for cycles
197 {
198 if (visited.has(from)) {
199 throw new Error(`cycle detected; cid=${from}`);
200 }
201
202 visited.add(from);
203 }
204
205 // Get the block data
206 let node: CAR.MstNode;
207 {
208 const entry = blockmap.get(from);
209 if (!entry) {
210 return { found: false };
211 }
212
213 const decoded = CBOR.decode(entry.bytes);
214 if (!CAR.isMstNode(decoded)) {
215 throw new Error(`invalid mst node; cid=${from}`);
216 }
217
218 node = decoded;
219 }
220
221 // Recursively process the left child
222 const left = await dfs(blockmap, node.l?.$link, target, visited);
223
224 let key = "";
225 let found = left.found;
226 let depth: number | undefined;
227 let firstKey: string | undefined;
228 let lastKey: string | undefined;
229
230 // Process all entries in this node
231 for (const entry of node.e) {
232 if (entry.v.$link === target) {
233 found = true;
234 }
235
236 // Construct the key by truncating and appending
237 key = key.substring(0, entry.p) + decoder.decode(CBOR.fromBytes(entry.k));
238
239 // Calculate depth based on leading zeros in the hash
240 const keyDigest = await toSha256(encoder.encode(key) as Uint8Array<ArrayBuffer>);
241 let zeroCount = 0;
242
243 outerLoop: for (const byte of keyDigest) {
244 for (let bit = 7; bit >= 0; bit--) {
245 if (((byte >> bit) & 1) !== 0) {
246 break outerLoop;
247 }
248 zeroCount++;
249 }
250 }
251
252 const thisDepth = Math.floor(zeroCount / 2);
253
254 // Ensure consistent depth
255 if (depth === undefined) {
256 depth = thisDepth;
257 } else if (depth !== thisDepth) {
258 throw new Error(`node has entries with different depths; cid=${from}`);
259 }
260
261 // Track first and last keys
262 if (lastKey === undefined) {
263 firstKey = key;
264 lastKey = key;
265 }
266
267 // Check key ordering
268 if (lastKey > key) {
269 throw new Error(`entries are out of order; cid=${from}`);
270 }
271
272 // Process right child
273 const right = await dfs(blockmap, entry.t?.$link, target, visited);
274
275 // Check ordering with right subtree
276 if (right.min && right.min < lastKey) {
277 throw new Error(`entries are out of order; cid=${from}`);
278 }
279
280 found ||= right.found;
281
282 // Check depth ordering
283 if (left.depth !== undefined && left.depth >= thisDepth) {
284 throw new Error(`depths are out of order; cid=${from}`);
285 }
286
287 if (right.depth !== undefined && right.depth >= thisDepth) {
288 throw new Error(`depths are out of order; cid=${from}`);
289 }
290
291 // Update last key based on right subtree
292 lastKey = right.max ?? key;
293 }
294
295 // Check ordering with left subtree
296 if (left.max && firstKey && left.max > firstKey) {
297 throw new Error(`entries are out of order; cid=${from}`);
298 }
299
300 return {
301 found,
302 min: firstKey,
303 max: lastKey,
304 depth,
305 };
306};