1use crate::{q_hash, NQuin};
10
11pub const MAX_DELEGATION_NODES: usize = 256;
13
14const NO_REVOCATION: u64 = u64::MAX;
15
16#[inline]
18pub fn delegates_predicate() -> u64 {
19 q_hash("q42:delegatesTo")
20}
21
22fn reaches(edges: &[NQuin], root_authority: u64, agent: u64, revoked: u64) -> bool {
25 if agent == revoked || root_authority == revoked {
26 return false;
27 }
28 if agent == root_authority {
29 return true;
30 }
31 let p = delegates_predicate();
32 let mut frontier = [0u64; MAX_DELEGATION_NODES];
33 let mut visited = [0u64; MAX_DELEGATION_NODES];
34 let mut fl = 1usize;
35 let mut vl = 0usize;
36 frontier[0] = root_authority;
37 while fl > 0 {
38 fl -= 1;
39 let cur = frontier[fl];
40 if visited[..vl].contains(&cur) {
41 continue;
42 }
43 if vl < MAX_DELEGATION_NODES {
44 visited[vl] = cur;
45 vl += 1;
46 } else {
47 break;
48 }
49 for e in edges {
50 if e.predicate == p && e.subject == cur && e.subject != revoked && e.object != revoked {
51 let nxt = e.object;
52 if nxt == agent {
53 return true;
54 }
55 if fl < MAX_DELEGATION_NODES && !visited[..vl].contains(&nxt) {
56 frontier[fl] = nxt;
57 fl += 1;
58 }
59 }
60 }
61 }
62 false
63}
64
65#[inline]
68pub fn has_delegated_authority(edges: &[NQuin], root_authority: u64, agent: u64) -> bool {
69 reaches(edges, root_authority, agent, NO_REVOCATION)
70}
71
72#[inline]
75pub fn authority_after_revocation(
76 edges: &[NQuin],
77 root_authority: u64,
78 revoked: u64,
79 agent: u64,
80) -> bool {
81 reaches(edges, root_authority, agent, revoked)
82}
83
84pub fn revoked_descendants(
87 edges: &[NQuin],
88 root_authority: u64,
89 revoked: u64,
90 candidates: &[u64],
91 out: &mut [u64],
92) -> usize {
93 let mut n = 0usize;
94 for &c in candidates {
95 if has_delegated_authority(edges, root_authority, c)
96 && !authority_after_revocation(edges, root_authority, revoked, c)
97 {
98 if n >= out.len() {
99 break;
100 }
101 out[n] = c;
102 n += 1;
103 }
104 }
105 n
106}
107
108pub fn attenuates(parent: &[u64], child: &[u64]) -> bool {
114 child.iter().all(|c| parent.contains(c))
115}
116
117#[inline]
121pub fn is_revoked(crl: &[u64], node: u64) -> bool {
122 crl.contains(&node)
123}
124
125pub fn authority_after_crl(edges: &[NQuin], root_authority: u64, crl: &[u64], agent: u64) -> bool {
128 if is_revoked(crl, agent) || is_revoked(crl, root_authority) {
129 return false;
130 }
131 if agent == root_authority {
132 return true;
133 }
134 let p = delegates_predicate();
135 let mut frontier = [0u64; MAX_DELEGATION_NODES];
136 let mut visited = [0u64; MAX_DELEGATION_NODES];
137 let mut fl = 1usize;
138 let mut vl = 0usize;
139 frontier[0] = root_authority;
140 while fl > 0 {
141 fl -= 1;
142 let cur = frontier[fl];
143 if visited[..vl].contains(&cur) {
144 continue;
145 }
146 if vl < MAX_DELEGATION_NODES {
147 visited[vl] = cur;
148 vl += 1;
149 } else {
150 break;
151 }
152 for e in edges {
153 if e.predicate == p
154 && e.subject == cur
155 && !is_revoked(crl, e.subject)
156 && !is_revoked(crl, e.object)
157 {
158 let nxt = e.object;
159 if nxt == agent {
160 return true;
161 }
162 if fl < MAX_DELEGATION_NODES && !visited[..vl].contains(&nxt) {
163 frontier[fl] = nxt;
164 fl += 1;
165 }
166 }
167 }
168 }
169 false
170}
171
172pub fn delegation_in_force(from: u32, until: u32, now: u32) -> bool {
177 (from == 0 || now >= from) && (until == 0 || now <= until)
178}
179
180pub fn delegation_in_region(scope_region: u64, location: u64) -> bool {
183 scope_region == 0 || scope_region == location
184}
185
186#[inline]
190pub fn testamentary_delegates_predicate() -> u64 {
191 q_hash("q42:testamentarySuccessor")
192}
193
194pub fn authority_with_succession(
204 edges: &[NQuin],
205 root_authority: u64,
206 agent: u64,
207 deceased_nodes: &[u64],
208 probate_admitted: bool,
209) -> bool {
210 if agent == root_authority {
211 return true;
212 }
213 let p_del = delegates_predicate();
214 let p_test = testamentary_delegates_predicate();
215
216 let mut frontier = [0u64; MAX_DELEGATION_NODES];
217 let mut visited = [0u64; MAX_DELEGATION_NODES];
218 let mut fl = 1usize;
219 let mut vl = 0usize;
220 frontier[0] = root_authority;
221
222 while fl > 0 {
223 fl -= 1;
224 let cur = frontier[fl];
225 if visited[..vl].contains(&cur) {
226 continue;
227 }
228 if vl < MAX_DELEGATION_NODES {
229 visited[vl] = cur;
230 vl += 1;
231 } else {
232 break;
233 }
234
235 let cur_deceased = deceased_nodes.contains(&cur);
236
237 for e in edges {
238 let is_ordinary = e.predicate == p_del && e.subject == cur;
239 let is_testamentary = e.predicate == p_test && e.subject == cur;
240
241 if !is_ordinary && !is_testamentary {
242 continue;
243 }
244
245 if is_ordinary && cur_deceased && (e.metadata & 0x01) == 0 {
247 continue;
248 }
249
250 if is_testamentary && (!cur_deceased || !probate_admitted) {
252 continue;
253 }
254
255 let nxt = e.object;
256 if nxt == agent {
257 return true;
258 }
259 if fl < MAX_DELEGATION_NODES && !visited[..vl].contains(&nxt) {
260 frontier[fl] = nxt;
261 fl += 1;
262 }
263 }
264 }
265 false
266}
267
268#[cfg(test)]
269mod tests {
270 use super::*;
271
272 fn edge(delegator: u64, delegatee: u64) -> NQuin {
273 let mut q = NQuin {
274 subject: delegator,
275 predicate: delegates_predicate(),
276 object: delegatee,
277 context: 0,
278 metadata: 0,
279 parity: 0,
280 };
281 q.parity = q.subject ^ q.predicate ^ q.object ^ q.context;
282 q
283 }
284
285 #[test]
286 fn authority_flows_along_the_chain() {
287 let root = q_hash("did:state");
289 let agency = q_hash("did:agency");
290 let officer = q_hash("did:officer");
291 let ngo = q_hash("did:ngo");
292 let edges = [edge(root, agency), edge(agency, officer), edge(root, ngo)];
293 assert!(
294 has_delegated_authority(&edges, root, officer),
295 "transitive delegation"
296 );
297 assert!(has_delegated_authority(&edges, root, ngo));
298 assert!(!has_delegated_authority(
300 &edges,
301 root,
302 q_hash("did:stranger")
303 ));
304 }
305
306 #[test]
307 fn revocation_cascades_to_descendants() {
308 let root = q_hash("did:state");
309 let agency = q_hash("did:agency");
310 let officer = q_hash("did:officer");
311 let ngo = q_hash("did:ngo");
312 let edges = [edge(root, agency), edge(agency, officer), edge(root, ngo)];
313 assert!(!authority_after_revocation(&edges, root, agency, officer));
315 assert!(authority_after_revocation(&edges, root, agency, ngo));
316 let mut out = [0u64; 8];
317 let n = revoked_descendants(&edges, root, agency, &[agency, officer, ngo], &mut out);
318 assert!(out[..n].contains(&officer));
320 assert!(out[..n].contains(&agency));
321 assert!(!out[..n].contains(&ngo));
322 }
323
324 #[test]
325 fn attenuation_never_broadens_authority() {
326 let (read, write, admin) = (q_hash("cap:read"), q_hash("cap:write"), q_hash("cap:admin"));
327 assert!(attenuates(&[read, write, admin], &[read, write]));
328 assert!(
329 !attenuates(&[read], &[read, admin]),
330 "cannot grant a capability the delegator lacks"
331 );
332 assert!(attenuates(&[read], &[]));
333 }
334
335 #[test]
336 fn crl_excises_every_revoked_node() {
337 let root = q_hash("did:state");
338 let agency = q_hash("did:agency");
339 let officer = q_hash("did:officer");
340 let ngo = q_hash("did:ngo");
341 let edges = [edge(root, agency), edge(agency, officer), edge(root, ngo)];
342 assert!(authority_after_crl(&edges, root, &[], officer));
344 assert!(!authority_after_crl(&edges, root, &[agency], officer));
346 assert!(authority_after_crl(&edges, root, &[agency], ngo));
347 assert!(!authority_after_crl(&edges, root, &[agency, ngo], ngo));
349 }
350
351 #[test]
352 fn spatial_and_temporal_bounds() {
353 assert!(delegation_in_force(100, 200, 150));
355 assert!(!delegation_in_force(100, 200, 50), "before start");
356 assert!(!delegation_in_force(100, 200, 250), "after end");
357 assert!(delegation_in_force(0, 0, 999), "open-ended");
358 let region = q_hash("region:au");
360 assert!(delegation_in_region(region, region));
361 assert!(!delegation_in_region(region, q_hash("region:us")));
362 assert!(
363 delegation_in_region(0, q_hash("region:anywhere")),
364 "global scope"
365 );
366 }
367
368 #[test]
369 fn test_authority_with_succession() {
370 let root = q_hash("did:community");
371 let decedent = q_hash("did:elder_a");
372 let proxy_living = q_hash("did:living_assistant");
373 let testamentary_heir = q_hash("did:grandchild");
374
375 let edge_normal = edge(decedent, proxy_living);
376 let mut edge_surviving = edge(decedent, proxy_living);
377 edge_surviving.metadata = 0x01; let mut edge_testamentary = NQuin {
380 subject: decedent,
381 predicate: testamentary_delegates_predicate(),
382 object: testamentary_heir,
383 context: 0,
384 metadata: 0,
385 parity: 0,
386 };
387 edge_testamentary.parity = edge_testamentary.subject
388 ^ edge_testamentary.predicate
389 ^ edge_testamentary.object
390 ^ edge_testamentary.context;
391
392 let edges = [edge(root, decedent), edge_normal, edge_testamentary];
393
394 assert!(authority_with_succession(
396 &edges,
397 root,
398 proxy_living,
399 &[],
400 false
401 ));
402 assert!(!authority_with_succession(
403 &edges,
404 root,
405 testamentary_heir,
406 &[],
407 false
408 ));
409
410 assert!(!authority_with_succession(
413 &edges,
414 root,
415 proxy_living,
416 &[decedent],
417 false
418 ));
419 assert!(!authority_with_succession(
420 &edges,
421 root,
422 testamentary_heir,
423 &[decedent],
424 false
425 ));
426
427 assert!(!authority_with_succession(
430 &edges,
431 root,
432 proxy_living,
433 &[decedent],
434 true
435 ));
436 assert!(authority_with_succession(
437 &edges,
438 root,
439 testamentary_heir,
440 &[decedent],
441 true
442 ));
443
444 let surviving_edges = [edge(root, decedent), edge_surviving, edge_testamentary];
446 assert!(authority_with_succession(
447 &surviving_edges,
448 root,
449 proxy_living,
450 &[decedent],
451 true
452 ));
453 }
454}