Skip to main content

qualia_core_db/modalities/
delegation.rs

1//! Delegation & credential-chain logic (§21, legal_logic.md) — the trust fabric.
2//!
3//! Legal power and identity flow through chains of authorization. This module governs how
4//! authority propagates along a delegation DAG and how **revocation of an upstream node
5//! cascades** to defeat every downstream dependent (ZCAP-LD / capability chains; Open Badges
6//! `EndorsementCredential`). Authority delegation edges are `(delegator, q42:delegatesTo,
7//! delegatee)`. Bounded BFS, zero-heap.
8
9use crate::{q_hash, NQuin};
10
11/// Bound on distinct nodes in one delegation query.
12pub const MAX_DELEGATION_NODES: usize = 256;
13
14const NO_REVOCATION: u64 = u64::MAX;
15
16/// The delegation-edge predicate `(delegator, q42:delegatesTo, delegatee)`.
17#[inline]
18pub fn delegates_predicate() -> u64 {
19    q_hash("q42:delegatesTo")
20}
21
22/// Internal: is `agent` reachable from `root_authority` along delegation edges, with `revoked`
23/// excised (revocation cuts the chain there and below)? Bounded, zero-heap.
24fn 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/// Does `agent` hold authority delegated (transitively) from `root_authority`?
66/// `Auth(α,p) ∧ Deleg*(α,…,β) → Auth(β,p)`.
67#[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/// **Revocation cascade**: after `revoked` is revoked, does `agent` still hold authority from
73/// `root_authority`? An agent whose only chain ran through `revoked` is now **defeated**.
74#[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
84/// Collect, into `out`, the `candidates` **defeated** by revoking `revoked` — held authority
85/// before, lost it after. Returns the count. Zero-heap.
86pub 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
108// ─── Attenuation: a delegatee receives ≤ the delegator's authority ────────────────
109
110/// **Attenuation** (ZCAP-LD / Macaroons): a sub-delegation's capability set `child` is valid only
111/// if a SUBSET of the delegator's `parent` set — a delegatee never gains MORE authority than the
112/// delegator holds. (Empty child trivially attenuates.)
113pub fn attenuates(parent: &[u64], child: &[u64]) -> bool {
114    child.iter().all(|c| parent.contains(c))
115}
116
117// ─── CRL: cascading revocation against a cryptographic revocation list ────────────
118
119/// Is `node` on the cryptographic revocation list `crl`?
120#[inline]
121pub fn is_revoked(crl: &[u64], node: u64) -> bool {
122    crl.contains(&node)
123}
124
125/// Does `agent` still hold authority from `root_authority` after excising EVERY node on the
126/// revocation list `crl` (a real-time CRL check across the whole chain)? Zero-heap (bounded BFS).
127pub 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
172// ─── Spatial & temporal bounds on delegated authority ─────────────────────────────
173
174/// Is a delegation temporally in-force at `now`? `[from, until]` Unix-epoch bounds, where
175/// `from == 0` means "no start bound" and `until == 0` means "open-ended".
176pub fn delegation_in_force(from: u32, until: u32, now: u32) -> bool {
177    (from == 0 || now >= from) && (until == 0 || now <= until)
178}
179
180/// Is a delegation valid in `location`? Its `scope_region` (`0` = unbounded / global) must equal
181/// `location`. Spatial bounding of delegated authority.
182pub fn delegation_in_region(scope_region: u64, location: u64) -> bool {
183    scope_region == 0 || scope_region == location
184}
185
186// ─── Testamentary Succession & Posthumous Delegation ──────────────────────────────
187
188/// Predicate for testamentary delegation edges: `(decedent, q42:testamentarySuccessor, successor)`.
189#[inline]
190pub fn testamentary_delegates_predicate() -> u64 {
191    q_hash("q42:testamentarySuccessor")
192}
193
194/// Evaluates whether `agent` holds authority from `root_authority` taking decedent status
195/// and testamentary succession into account.
196///
197/// Rules:
198/// 1. If an intermediary is in `deceased_nodes`, ordinary delegation edges from that intermediary
199///    lapse unless `metadata & 0x01 != 0` (survivesDeath flag).
200/// 2. If `probate_admitted` is true, testamentary successor edges (`q42:testamentarySuccessor`)
201///    from deceased nodes are activated.
202/// 3. Zero-heap bounded BFS traversal.
203pub 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            // Ordinary edges from deceased node lapse unless survives_death flag (metadata & 1 != 0) is set
246            if is_ordinary && cur_deceased && (e.metadata & 0x01) == 0 {
247                continue;
248            }
249
250            // Testamentary edges activate only when the delegator is deceased and probate is admitted
251            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        // root → agency → officer ; root → ngo
288        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        // An agent with no chain from root holds nothing.
299        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        // Revoke the agency: the officer (downstream) is defeated; the NGO (independent) is not.
314        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        // Both the agency itself and the officer lose authority; the NGO keeps it.
319        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        // Empty CRL → behaves like full authority.
343        assert!(authority_after_crl(&edges, root, &[], officer));
344        // Revoke the agency via the CRL: officer defeated, ngo (independent) survives.
345        assert!(!authority_after_crl(&edges, root, &[agency], officer));
346        assert!(authority_after_crl(&edges, root, &[agency], ngo));
347        // A multi-entry CRL revoking both branches.
348        assert!(!authority_after_crl(&edges, root, &[agency, ngo], ngo));
349    }
350
351    #[test]
352    fn spatial_and_temporal_bounds() {
353        // Temporal: in force only within [100, 200].
354        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        // Spatial: scoped to a region (0 = global).
359        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; // survivesDeath flag
378
379        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        // While elder is alive: normal assistant has authority; testamentary heir does NOT yet
395        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        // When elder is deceased but probate not yet admitted:
411        // Normal assistant loses authority; testamentary heir has not activated
412        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        // When elder is deceased and probate is admitted:
428        // Normal assistant still lacks authority; testamentary heir is active!
429        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        // If normal edge had survivesDeath flag, it also survives death
445        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}