Capability Systems: Canonical Domain Analysis

Status: Phase B.2-B.3 of the Paper 3 deep-dive reconciliation. First-pass application of the methodology to capability-and-authorization-systems-as-a-domain. Companion to type_systems_domain_analysis/. Source: Paper 3 §2 (Zanzibar / UCAN / Macaroons / Biscuit), classical access-control literature, capability theory (Dennis-Van Horn, Levy 1984), methodology.md. Position in topology: Surface domain with strong substrate-dependence on identity and execution. Prediction (R11): ~25-40% filter, functional-integration core triad. Distinct from type systems in that the domain has a strong temporal/contextual character (authorization is request-bound, not data-bound).

Step 1 — Information Gathering

1.1 Primary literature

• Dennis & Van Horn 1966 — original capability paper, "Programming Semantics for Multiprogrammed Computations"
• Levy 1984 — Capability-Based Computer Systems
• Miller 2006 — Robust Composition: Towards a Unified Approach to Access Control and Concurrency Control (object-capability foundations)
• Pardo et al. 2018 — Zanzibar (Google's authorization)
• Birgisson et al. 2014 — Macaroons (contextual caveats)
• UCAN spec 2022 — decentralized capability tokens
• Paquin 2021 — Biscuit (Macaroons + Datalog)
• CHERI / Watson et al. 2015 — hardware capability architecture
• Saltzer & Schroeder 1975 — "The Protection of Information in Computer Systems" (RBAC/ABAC ancestors)
• NIST SP 800-162 — ABAC formalization
• Plan 9 — file-based capability semantics

1.2 Prior analytical work

• Paper 3 §2 (the artifact under test)
• entity_domain_analysis/analysis-entity-system-substrate.md (E+I+T+M+X+P substrate)
• This document's companion: type_systems_domain_analysis/analysis-type-systems.md

1.3 Implementation landscape

• Object-capability languages: E, Pony, Newspeak
• Capability OSes: KeyKOS, EROS, Genode
• Capability tokens: UCAN, Macaroons, Biscuit, AT Protocol session tokens
• Centralized authz: AWS IAM, Azure RBAC, Zanzibar, OpenFGA
• Hardware: CHERI, Mill CPU capabilities
• Identity-bound: SPIFFE/SPIRE workload identity
• Crypto-attested: SAML, OIDC, JWT (token-shaped but not always capability-shaped)

Step 2 — Landscape Analysis

2.1 Attractor positions

Six attractors, one more than type systems' five. Authorization is a more fragmented design space because each cluster optimizes for a different deployment topology (trusted centralizer vs decentralized agents vs hardware enforcement).

2.2 Entity system positioning

The entity system fits the DID-based decentralized cluster (UCAN-adjacent) with strong substrate-integration: capability tokens are entities, capability checks are dispatch, capability identifiers are content-addressed.

Step 3/3b — Primitive Extraction and Partial Levels

3.1 First-pass primitive candidates (developed without consulting Paper 3)

What does an authorization system structurally do? It evaluates "should this request proceed?" Decomposed:

1. Subject (Sb) — identifying the principal making the request (who)
2. Action (Ac) — what is being requested (verb + how to dispatch it)
3. Object (Ob) — what is being acted upon (target resource/data)
4. Context (Cx) — environmental conditions (time, location, peer, network attributes)
5. Authority (Au) — what makes the authorization legitimate (root vs delegated, the source of permission)
6. Attenuation (At) — how authority can be narrowed in delegation (monotonic shrinkage)
7. Revocation (Rv) — how authority can be removed once granted (negative move)

7 candidates. Iterate.

3.2 Iteration 1 — collapse / split candidates

• Split Action into Mechanism + Verb? Paper 3 does this, calling them Handler and Operation. Argument for split: "GET on /foo via the HTTP handler" vs "GET on /foo via the file handler" can have different authorization. Argument against split: Action = mechanism+verb is the typical bundling. Provisional decision: keep collapsed as Action. Most authorization systems treat them as one (e.g., Zanzibar's "relation" combines them). Paper 3's split is one of the entity system's distinctive moves — it's a design choice of the entity system, not a structural irreducibility of authorization-as-domain.

  Re-checking via irreducibility: can you have Mechanism without Verb? Yes (any handler is dispatched without specifying verb). Can you have Verb without Mechanism? Yes (operation name without binding to mechanism). They are independent. Reverse: split into Mechanism (Mc) and Verb (Vb). This brings count to 8.

• Collapse Subject and Authority? Tempting: the holder of a capability IS authorized. But Subject is the requesting principal, Authority is the source-of-permission; they can differ (Authority = root, Subject = delegated user). Keep separate.

• Collapse Attenuation and Revocation? Both are negative moves on capabilities. But Attenuation is forward-narrowing at delegation time, while Revocation is backward-cancellation after grant. Different temporal modes, different mechanisms. Keep separate.

• Context as one primitive vs split into Time + Location + Peer? Paper 3 splits Time and Peer into separate primitives. Argument for split: time has structural temporal semantics (expiry, not-before, ordering), while location/peer has structural spatial semantics. Argument for keep: both are environmental attributes evaluated at request time. Provisional: keep as Context with partial levels for Time, Location, and other environmental attributes. Splitting risks proliferating one primitive per request-attribute.

  Re-checking: in the cluster taxonomy, Time appears as its own first-class concern (Macaroons time caveats, JWT expiry, UCAN nbf/exp) — every token-based system has it. Location/peer appears as first-class only in distributed systems. Asymmetric.

  Resolution: keep Context as a primitive with Time as its dominant partial-level axis. Note that distributed authorization may benefit from splitting Peer out (matching Paper 3's choice); leave that as a domain-specific refinement.

3.3 Stable primitive set (provisional)

After iteration:

8 primitives: {Sb, Mc, Vb, Ob, Cx, Au, At, Rv}

Comparison to Paper 3's 7 dimensions:

• Paper 3 Subject ↔ methodology Sb ✓
• Paper 3 Handler ↔ methodology Mc ✓
• Paper 3 Operation ↔ methodology Vb ✓
• Paper 3 Resource ↔ methodology Ob ✓
• Paper 3 Peer ↔ methodology Cx (partial-level: spatial axis)
• Paper 3 Time ↔ methodology Cx (partial-level: temporal axis)
• Paper 3 Delegation ↔ methodology Au + At (a load-bearing pair, not a single primitive)
• No Paper 3 equivalent for methodology Rv (Revocation)

Methodology arrives at 8 primitives. Paper 3 has 7. The differences:

• Methodology splits Context into NOT-quite-Peer-and-Time (treats both as partial-levels of Cx); Paper 3 splits them outright. (Methodology may be wrong here — see Step 4 below.)
• Methodology collapses Delegation into Au+At (treats as a pair, not a primitive); Paper 3 bundles them.
• Methodology adds Revocation; Paper 3 mentions only via Time (expiry).

3.4 Domain-type declaration (R11)

Surface domain. Authorization sits on top of an identity substrate + an execution substrate + a content substrate. R11 predicts ~25-40% filter, functional-integration core triad.

3.5 Partial levels (compressed)

Subject (Sb):

Phase transition Sb3→Sb4: identity becomes intrinsic and unforgeable across topology. (Maps to entity primitive I's phase transition.)

Mechanism (Mc):

Verb (Vb):

Object (Ob):

Context (Cx):

Authority (Au):

Attenuation (At):

Revocation (Rv):

3.6 Stability check

Re-test under partial-level decomposition:

• Mc and Vb: do they collapse? Mc3 (open dispatch per handler) + Vb3 (open verb set per mechanism) — these are different axes. A handler can have multiple verbs; a verb can apply across handlers. Keep separate.
• Cx: does it split into Cx-time and Cx-spatial as separate primitives? At Cx4 they're already separate axes within one primitive. The argument for splitting is practical: every token-based system has time; not every system has spatial scoping. This is the same kind of argument Paper 3 makes for splitting Time and Peer. Defer the split for now; mark as a known refinement candidate.

8 primitives stable: {Sb, Mc, Vb, Ob, Cx, Au, At, Rv}.

Step 4 — Dependencies

Sb → (none, but pairs heavily with Au)
Mc → (none, but pairs with Ob)
Vb → Mc                  (verbs are dispatched via mechanisms)
Ob → (none, but pairs with Mc for path-bound mechanisms)
Cx → (none, environmental)
Au → Sb                  (authority is held by a subject; even root has a subject)
At → Au                  (attenuation operates on authority chains)
Rv → Au                  (revocation invalidates authority)

DAG:

Sb → Au → At
        ↘
         Rv

Mc → Vb
Ob
Cx

Hubs: Au (Authority) is hub for At and Rv. Sb is upstream of Au. Mc is upstream of Vb.

4.1 Conditional partial-level dependencies

• At2 (predicate attenuation) requires Cx2+ (predicates are evaluated against context)
• Au3 (identity-bound roots) requires Sb3+ (cryptographic identity for unforgeable root claim)
• Rv4 (content-addressed revocation) requires substrate-Identity + substrate-Tree (depends on lower substrate)

These conditional dependencies tighten the lattice at fine resolution.

Step 5-6 — Pairs and Load Classification

C(8,2) = 28 pairs.

Heavy pairs:

7 heavy pairs.

Medium pairs:

6 medium pairs.

Light/negligible pairs: remaining 15.

Heavy-pair ratio: 7/28 = 25%. Within R11 surface-domain expected range.

Step 7 — Coherent Sub-lattice (estimated)

2^8 = 256 total subsets. Apply dependencies:

• Any subset with At, Rv, but no Au: invalid
• Any subset with Au but no Sb: marginal/invalid
• Any subset with Vb but no Mc: invalid

Estimated coherent subset count: 70-100 / 256 → filter ~27-39%. Within R11 surface range.

(Precise count is script-able and deferred.)

Step 8 — Build-up Sequence

Natural build-up of an authorization system from scratch:

1. {} → no authorization (open system)
2. {Sb} → identify requesters (audit, not yet authorization)
3. {Sb, Au} → root authority + identified subjects (single-root authorization)
4. {Sb, Au, Ob} → authority scoped to objects (DAC begins)
5. {Sb, Au, Ob, Mc} → mechanism scoping (per-handler grants)
6. {Sb, Au, Ob, Mc, Vb} → verb scoping (CRUD-level discrimination)
7. {Sb, Au, Ob, Mc, Vb, At} → delegation (subjects can re-grant subsets)
8. {Sb, Au, Ob, Mc, Vb, At, Cx} → contextual conditions (time, location, etc.)
9. {Sb, Au, Ob, Mc, Vb, At, Cx, Rv} → revocation (capabilities can be undone)

This is one natural walk; others exist. Notably, the entity system reaches step 9 plus the strongest partial levels (Sb4 content-addressed subject, Au3 identity-bound roots, At3 composing caveats, Cx3-4, Rv2+).

Step 9 — Load-Bearing Compositions

9.1 Candidate triangles

9.2 Functional-integration core triad (R11 prediction)

Candidate: {Sb, Au, Ob} — the minimal triad to express "subject S, holding authority A, may act on object O." This is the structural minimum of any authorization system. Matches DAC's foundational position.

Alternative candidate: {Sb, Au, At} — the delegation triangle, which is what makes capabilities distinct from access-control-lists. The cap-systems literature centers here.

Both are reasonable triads. The choice between them depends on whether the analysis emphasizes static access (Sb+Au+Ob) or delegation (Sb+Au+At). Most modern systems require both, so the quad {Sb, Au, Ob, At} might be the load-bearing structure. Quads are higher-arity load-bearing compositions per Step 9.

9.3 Entity system's distinctive activation

Entity system activates all 8 primitives at strong partial levels:

• Sb4 (content-addressed identity via peer)
• Mc3 (open dispatch per handler)
• Vb3 (extensible operation vocabulary)
• Ob5 (set-theoretic resource scope)
• Cx3 (time + peer)
• Au3 (identity-bound roots — each peer is its own root)
• At3 (composing caveats via grant entries + token-level constraints)
• Rv2-3 (revocation via expiry + push-revoke through subscription extension)

This is the highest activation among the surveyed cluster. UCAN reaches Sb4, Au3, At2-3 but only Cx1-2 and Rv0-1. Zanzibar reaches Ob3, Mc1-2, Au1 but Sb2 only. Macaroons reach At3, Cx1-2 but Sb1-2, Au1, Ob1.

Step 10 — Emergent Properties

Step 11 — Cross-Domain Patterns

11.1 Map to entity primitives

Authority + Attenuation activates the IXP cryptographic-capability triangle that Paper 3 names. This matches.

All 6 entity primitives are needed: E (typed authority tokens), I (cryptographic identity for Sb/Au), T (object scope, handler scope), M (temporal context, revocation), X (authority verification, dispatch), P (peer scope). Consistent with Paper 3's finding that capability dimensions require the full primitive set.

11.2 Cross-domain pattern: Authority vs Identity

The Authority primitive is the cap-domain analog of the substrate-Identity primitive. Both are about unforgeable claim: substrate-Identity makes content claim unforgeable (hash); cap-Authority makes permission claim unforgeable (cryptographic signature). The methodology surfaces this analogy.

Step 12 — Literature Alignment

• Dennis & Van Horn 1966: capability = unforgeable reference. Maps to Sb+Au+At in modern decomposition.
• Miller 2006: object-capability principles. Maps to Sb1 (bearer) + Au0-1 (no ambient authority, capability is authority).
• Zanzibar: relation-based, centralizes Au at Google's identity layer; covers Sb2-3, Ob3, Mc1, Au1, At0-1. Score per methodology: ~Sb3, Mc1, Vb2, Ob3, Cx1, Au1, At1, Rv2.
• UCAN: covers Sb4, Au3, At2-3, Cx1-2. Score: ~Sb4, Mc1, Vb2, Ob3-4, Cx2, Au3, At3, Rv1.
• Macaroons: covers Sb1, Au1, At3, Cx1-2. Score: ~Sb1-2, Mc1, Vb2 (via caveats), Ob1, Cx2, Au1, At3, Rv1.
• CHERI: hardware capabilities. Sb (process), Au0 (memory-bound capability is authority), At (sub-capabilities), Rv (capability invalidation). Hardware-bound.
• Biscuit: Macaroons + Datalog. Adds Vb3-level expressivity through Datalog predicates.

The methodology's 8 primitives + partial levels cleanly stratify the comparison systems. Paper 3's 7×4 table is consistent but coarser (binary yes/no per dimension vs partial-level positioning).

Reconciliation with Paper 3

Agreement points

1. All entity primitives needed: both analyses agree capability systems require the full set {E, I, T, M, X, P}.
2. IXP cryptographic triangle distinctive: methodology identifies Sb+Au+At as activating IXP at the substrate; Paper 3 names IXP directly. Same finding.
3. Entity system covers the most of any surveyed system: methodology scores entity at highest partial levels across all 8 primitives; Paper 3 says entity covers all 7 dimensions where others cover subsets.
4. Handler + Operation split as distinctive: both agree this is the entity system's contribution (relative to systems that bundle them as "permission scope").
5. Phase-transition pairs require Full I: both agree.

Divergence points

1. Primitive count: methodology finds 8 primitives (Sb, Mc, Vb, Ob, Cx, Au, At, Rv); Paper 3 finds 7 dimensions (Subject, Handler, Operation, Resource, Peer, Time, Delegation).

2. Context vs Peer+Time: methodology bundles Peer and Time into Context (Cx) with partial levels for each axis; Paper 3 splits them outright. The split is defensible — every token-based system has Time as first-class; Peer-as-first-class is distinctive of decentralized systems. Methodology may need to split Cx at the substrate-aware refinement level.

3. Delegation as primitive vs as pair: Paper 3 treats Delegation as one of 7 dimensions; methodology treats it as the {Au, At} pair-relationship (and identifies its triangle with Sb: {Sb, Au, At}). Methodology's view is more structural — delegation is the interaction of authority and attenuation, not a primitive itself.

4. Revocation as primitive: methodology adds Rv as primitive #8; Paper 3 mentions revocation only as a sub-aspect of Time (expiry). This is a methodology addition — Paper 3 missed revocation as an independent design axis. The Macaroons/UCAN literature confirms it's a distinct primitive: token expiry is necessary but not sufficient for capability lifecycle management; explicit revocation (CRL, push-revoke) is a different mechanism.

5. Authority as primitive: methodology has Authority (Au) as primitive #6; Paper 3 has no equivalent. Paper 3 implicitly bundles Authority into Subject (the holder of a capability has authority). Methodology argues these are distinct — Subject is the requester at request time, Authority is the source of permission. They can differ (delegated subject ≠ root authority). Methodology's split is justified by capability theory (Au is the foundational object-capability concept) and by the entity system's actual mechanics (cert-chain framework distinguishes peer-keypair from controller-quorum).

Verdict

Significant revision needed: the methodology finds 8 primitives where Paper 3 has 7 dimensions, with two non-trivial additions (Authority, Revocation) and one merge (Peer+Time → Context). Paper 3's framing is consistent with the methodology in spirit (all 7 dimensions map to methodology primitives or pairs) but misses Revocation as a primitive and bundles Authority into Subject.

These are not cosmetic differences. Revocation is a well-known design space in capability systems (the "revocation problem" has its own literature). Authority is the foundational concept of object-capability theory. Paper 3's omission of both reflects its pre-methodology origins — the analysis was empirical-survey-driven, not theory-driven, and these primitives are theory-visible but not always survey-prominent.

Recommendation for Paper 3:

1. Add Revocation as a 7th... wait, 8th... wait, this is where it gets architecturally messy. Paper 3 currently structures around "7 dimensions" with explicit grant-field mapping. Adding Revocation as an 8th breaks the structure.

2. Alternative: keep Paper 3's 7-dimension framing for backward consistency but add a "Methodology Refinement" subsection noting:

   • Authority should be split from Subject (matches the cert-chain framework added in Paper 10's recent identity rewrite)
   • Revocation should be a primitive, currently treated only through Time-expiry
   • Peer + Time may bundle into Context as partial levels of one Cx primitive
   • The reconciliation lives in methodology/capability_systems_domain_analysis/

3. More ambitious: restructure Paper 3 §2 around 8 primitives (or 9 if Peer and Time stay split). This is a larger edit and risks losing the "4-dim grant is principled subset of 7 dimensions" narrative.

The choice depends on whether Paper 3 prioritizes historical continuity (option 2) or theoretical correctness (option 3).

TODO

• Script the coherent-subset count
• Position table scoring 10+ capability systems on the 8 primitives × partial levels
• Decide Cx-split question (single primitive vs Peer+Time split)
• Reconcile Paper 10's recent identity rewrite (which introduced cert-chain framework distinguishing peer-keypair from controller authority) with this analysis's Au primitive