DEOS Capability Caveat Algebra — v1.1 Specification

Status: v1.1 — drafted 2026-05-05 Spec URI: https://projectmaya.deoscomputing.io/capability/caveats/v1 Maintainer: DEOS Computing (did:web:deos.computing) Companion: /ucan/tokens/v1

This document is normative for v1.1. It defines the caveat algebra over DEOS UCAN-shaped capability tokens: how attenuations narrow across delegation chains, how actions satisfy a leaf, how revocation interacts with caveats, and how time bounds compose. v1.0 admitted integer-max + equality caveats and exact-string can matching; v1.1 extends with hierarchical can matching, set-membership over with, OR-composition within attenuations, caveat-level revocation, ratchets, and tightened chain-time validation. v1.0 tokens validate identically under v1.1.

1. Goals

A v1.1 caveat algebra must:

Match can hierarchically. A parent token granting tool/* allows a child token to attenuate to tool/call, tool/exec, etc. v1.0 only matched exact strings.
Allow set-membership on with. A token granting {"with": ["mcp://a", "mcp://b"]} SHALL satisfy any action whose resource matches one of the entries.
Allow OR-composition within an attenuation. Multiple alternatives in a single att entry, where any one alternative being satisfied satisfies the entry.
Permit caveat-level revocation. Specific allowed values can be revoked individually rather than revoking the whole token.
Define normative time-range composition. When multiple time bounds appear (nbf, exp, until, after), the resulting effective window MUST be the intersection of all bounds.
Not break v1.0 receipts — existing caveat shapes continue to validate identically.

2. Hierarchical `can` matching (UCAN1.1-4)

2.1 Syntax

A can value is a slash-delimited path, e.g. tool/call, tool/exec, payment/intent, kv/get. v1.1 introduces wildcards:

tool/* — matches any single segment after tool/. So tool/call matches; tool/call/inner does NOT match.
tool/** — matches any number of segments. So tool/call, tool/call/inner, tool/exec/sub/path all match.
The empty wildcard * matches any single top-level segment.

2.2 Matching algorithm

A child can value SATISFIES a parent can value when:

match(parent, child):
  parent_segs = split(parent, "/")
  child_segs = split(child, "/")
  for i in 0..max(parent_segs.len, child_segs.len):
    if i >= parent_segs.len:
      // parent ran out; child has more segments → only match if last
      // parent seg was "**"
      return parent_segs.last == "**"
    if i >= child_segs.len:
      return false  // child too short
    p = parent_segs[i]
    c = child_segs[i]
    if p == "**":
      return true   // ** consumes the rest
    if p == "*":
      continue      // single-segment wildcard; advance
    if p != c:
      return false
  return parent_segs.len == child_segs.len

A token attenuating from parent attenuation {can: P, ...} to child attenuation {can: C, ...} MUST have match(P, C) == true. Verifiers reject chains where any child violates this.

2.3 Action satisfaction

A receipt's action satisfies the leaf attenuation's can when:

action.type → derived_can_string (table below)
match(leaf.can, derived_can_string) == true

The action_type → can mapping:

action.type	derived can
`tool_call`	`tool/call`
`payment_intent`	`payment/intent`
`payment_settlement`	`payment/settlement`
`identity_claim`	`identity/claim`
`message_send`	`message/send`
`code_execution`	`code/execute`
`policy_evaluation`	`policy/evaluate`

A leaf attenuation {can: "tool/*"} therefore satisfies a tool_call action; {can: "*/*"} satisfies all action types; {can: "**"} satisfies all action types and any nested derived form.

2.4 Backward compatibility

A v1.0 token with can: "tool/call" (literal, no wildcards) continues to work exactly as before — match("tool/call", "tool/call") == true per the algorithm. Receivers of v1.0 tokens see no behavior change. Only NEW tokens authoring wildcards see the new behavior.

3. Set-membership on `with` (CAV1.1-6)

3.1 Syntax

The with field, originally a single string, MAY also be an array of strings:

{"with": ["mcp://weather*", "mcp://forecast*"], "can": "tool/call"}

A child attenuation MUST be a subset of the parent's set — every element of child.with MUST be a subset-string of some element in parent.with under the v1.0 with-prefix matching rule.

An action's resource satisfies the leaf when at least one element of the leaf's with array matches by the prefix-or-glob rule.

3.2 Mixed forms

A token MAY mix string and array forms across the chain:

Parent: with: "mcp://*" (string)
Child: with: ["mcp://weather*", "mcp://forecast*"] (array, each element a subset of parent)

The child is valid if every array element is a subset of the parent's single with.

3.3 Empty arrays

An empty with: [] matches NOTHING. A leaf with empty with MUST be rejected as unsatisfiable.

4. OR-composition within attenuations (CAV1.1-5)

4.1 Syntax

A single att entry MAY be a wrapping array OR-composing multiple alternatives:

{"att": [
  [
    {"with": "mcp://a*", "can": "tool/call"},
    {"with": "mcp://b*", "can": "tool/call"}
  ],
  {"with": "kv://state*", "can": "kv/*"}
]}

The outer att array still ANDs across entries (a chain valid for ALL of them).

The INNER array (the OR-composition) is satisfied when any one of its alternatives is satisfied.

4.2 Validation

A child token's attenuation entry can be EITHER:

Single map → must narrow some single map alternative in the parent's matching entry, OR
Array → must narrow at least one alternative in the parent's matching entry, where EACH array element narrows at least one parent alternative.

The OR-composition is symmetric only when narrowing: the child can drop alternatives but cannot add them.

4.3 Action satisfaction with OR

For an action to satisfy a leaf's OR-composed att entry, the action MUST satisfy at least one alternative.

5. Caveat-level revocation (CAV1.1-1)

5.1 The use case

A capability granted via with: ["mcp://a", "mcp://b", "mcp://c"] may need to have ONLY mcp://b revoked without invalidating the rest. v1.0 revocation operates at the token level (revoke the whole token); v1.1 adds caveat-level granularity.

5.2 Format

A caveat-revocation entry has the same shape as a token revocation but with an additional caveat_path field:

{
  "v": 1,
  "schema": "deos_caveat_revocation_v1",
  "issuer_did": "<the substrate>",
  "token_iss": "<the token's iss>",
  "token_nnc": "<the token's nnc>",
  "caveat_path": "att[2].with[1]",
  "revoked_value": "mcp://b",
  "revoked_at_ns": <unix ns>,
  "reason": "<text>",
  "signatures": [{"kid": "<substrate kid>", ...}]
}

caveat_path follows the JSON Pointer-like syntax — array indices in brackets, fields after dots.

5.3 Verifier behavior

When validating a chain, the verifier:

Looks up token-level revocations as in v1.0.
ALSO looks up caveat-level revocations for each token.
For each caveat-level revocation matching the token, REMOVES the revoked value from the relevant collection (e.g. drops mcp://b from a with array) before checking action satisfaction.
If the modified collection becomes empty, the leaf MUST be rejected per §3.3.

5.4 New endpoint

POST /attestation/v1/caveat-revoke

Body:

{
  "token_iss": "<DID>",
  "token_nnc": "<string>",
  "caveat_path": "att[2].with[1]",
  "revoked_value": "<value at that path>",
  "reason": "<text>"
}

Auth: admin token (mirrors v1.0 /revoke). Audited via admin-events.jsonl.

6. Tightened time-range composition (UCAN1.1-2 carve-out)

6.1 Effective time window

When a chain has tokens with various nbf, exp, until, after time bounds, the effective time window for the action is the intersection of all bounds:

effective_nbf = max( token.nbf for token in chain ) ∪ caveat.after
effective_exp = min( token.exp for token in chain ) ∪ caveat.until

If effective_nbf > effective_exp, the chain is unsatisfiable and MUST be rejected at chain-validation time, not at action-satisfaction time.

6.2 v1.0 fix

v1.0 enforced these bounds at action-satisfaction time only. v1.1 enforces at chain-validation time additionally. v1.0 receipts still validate (the v1.0 check was a strict subset; nothing that passed v1.0 fails v1.1).

7. Worked examples

7.1 Hierarchical can

Parent token: att: [{"with": "mcp://*", "can": "tool/*"}] Child token: att: [{"with": "mcp://weather*", "can": "tool/call"}]

Validation:

match("tool/*", "tool/call") → true (single-segment wildcard)
with narrows from mcp://* to mcp://weather* (v1.0 rule)
ACCEPT.

7.2 OR-composition

Parent: att: [[{"with":"mcp://a","can":"tool/call"}, {"with":"mcp://b","can":"tool/call"}]] Child: att: [{"with":"mcp://a","can":"tool/call"}]

Validation:

Child has one alternative; it must narrow at least one parent alternative.
The child's mcp://a, tool/call exactly matches the parent's first alternative.
ACCEPT.

Action: tool_call against mcp://a/forecast → satisfies child's leaf → ACCEPT.

7.3 Caveat-level revocation

Token: att: [{"with":["mcp://a","mcp://b","mcp://c"],"can":"tool/*"}] Caveat-revocation: caveat_path: "att[0].with[1]", revoked_value: "mcp://b"

After revocation, the effective leaf is with: ["mcp://a","mcp://c"].

Action against mcp://b/foo → the leaf no longer permits mcp://b → REJECT. Action against mcp://a/foo → still permitted → ACCEPT.

8. Implementation status

v1.1 deliverable is this spec. Implementations target v1.2:

Item	Lands in
Hierarchical `can` matching (``, `*`)	v1.2
Set-membership `with` array	v1.2
OR-composition within att	v1.2
Caveat-level revocation	v1.2
Tightened time-range composition	v1.2
Multi-sig caveats	v1.3
Ratchet caveats (`seq`)	v1.2

9. Security considerations

This section satisfies the RFC 3552 requirement.

9.1 Wildcard escalation

A token granting can: "**" is functionally equivalent to no can restriction. Verifiers MUST reject such tokens at admission unless an explicit --allow-unbounded-can flag is set on the substrate's Registration Policy (off by default).

A parent token granting tool/* allows attenuation to tool/<anything>, including future actions not yet defined. This is by design — the wildcard expresses "any operation under this namespace." Operators issuing high-authority root tokens SHOULD prefer narrower wildcards over **.

9.2 OR-composition and revocation

A token using OR-composition [{A}, {B}] is satisfied by either A or B. Revoking only A leaves B still effective. To fully revoke the token, the operator MUST revoke at the token level, not the caveat level.

Verifiers MUST handle this correctly: if a caveat-level revocation removes one alternative, the others remain. If all alternatives of an OR-composition are caveat-revoked, the entry is unsatisfiable and the leaf is rejected.

9.3 Caveat path injection

The caveat_path field in a revocation could be malformed or path-inject. Verifiers MUST validate the path against the token's actual structure and reject revocations whose paths don't resolve.

9.4 Time-range composition under clock skew

Bounds at chain-validation time are checked against the receipt's claimed issued_at_ns. A misbehaving substrate could publish a receipt with a falsified timestamp to bypass an exp boundary. Mitigations: OTS anchoring bounds the timestamp from above (per /anchor/bitcoin/v1 §3.4); UCAN tokens are short-lived (typical exp is hours, not days).

10. Ratchets — `seq` caveat

A caveat-level ratchet lets an issuer cap the number of times a token can be exercised. Useful for one-shot delegations, bounded N-time delegations, and per-session ordering.

10.1 Syntax

A token's attenuation MAY include seq: N (non-negative integer):

{
  "iss": "did:deos:user-x",
  "aud": "did:deos:agent-y",
  "att": [
    {"with": "mcp://x", "can": "tool/call", "seq": 0}
  ],
  "exp": 1234567890,
  "nnc": "single-use-nonce"
}

The seq: 0 says "this attenuation is valid only when the substrate's per-(iss, nnc) counter equals 0 at /append time." After successful use, the substrate increments the counter; the same token re-submitted attempts to satisfy seq: 0 against a counter of 1 and is rejected.

10.2 Substrate enforcement (normative)

The substrate maintains a per-(iss, nnc) counter persisted to <data-dir>/seq-counters.json (key = BLAKE3-truncated of iss\0nnc). On /append:

For every chain token's every attenuation with seq set, look up the substrate's counter for (iss, nnc).
If att.seq != counter, reject with HTTP 400.
After all ratchets validate AND the receipt is durably appended to the MMR, increment each touched counter by 1 and persist.

Crash-safety: bump happens AFTER MMR append. A crash between sign and bump leaves the counter at the pre-receipt value; re-submission is content-addressed-idempotent (returns duplicate: true) without bumping again.

10.3 Use-once tokens via `seq`

A common pattern is a single-use UCAN. The issuer mints a token with seq: 0 and a unique nnc. After the substrate accepts it once, the counter advances to 1; any replay attempt fails. To grant a multi-use version, the issuer mints a NEW token with seq omitted (no ratchet) or seq: 0 and a fresh nonce.

10.4 Limitations

The ratchet is per-token, not per-attenuation. Multiple attenuations on a single token sharing (iss, nnc) advance their counter together.
The counter is substrate-state, not part of the receipt body. Verifiers cannot independently re-derive it; trust the substrate to enforce.
Cross-substrate replay is NOT prevented by this primitive: a token used at substrate A can be replayed at substrate B unless distinct nnc values are used per substrate.

11. Threshold caveats — `threshold` [v1.3]

Status: design specified; implementation deferred to v1.3.

A threshold caveat requires N-of-M independent attestations before an attenuation is satisfied. Useful for high-stakes capabilities (e.g. "may transfer >$1M") where one signer is insufficient.

11.1 Wire shape (proposed)

{
  "with": "payment://account-x",
  "can": "transfer",
  "threshold": {
    "count": 2,
    "attestations": [
      "did:deos:officer-1#sig-1",
      "did:deos:officer-2#sig-1",
      "did:deos:officer-3#sig-1"
    ]
  }
}

Means at least 2 of {officer-1, officer-2, officer-3} must have submitted a signed attestation referencing this token's (iss, nnc) before the attenuation is satisfied.

11.2 Attestation submission

A new endpoint POST /attestation/v1/threshold-attestation accepts:

{
  "schema": "deos_threshold_attestation_v1",
  "token_iss": "did:deos:user-x",
  "token_nnc": "...",
  "att_index": 0,
  "attester_kid": "did:deos:officer-1#sig-1",
  "attested_at_ns": 1730000000000000000,
  "signature": { "alg": "ed25519", "kid": "...", "sig": "..." }
}

Substrate validates signature, persists to <data-dir>/threshold-attestations.jsonl, and indexes by (token_iss, token_nnc, att_index).

11.3 Why deferred

Substantial endpoint + storage work (~300 LOC); demand has been soft. Pair with multi-sig caveats (§12) in v1.3 to avoid two parallel paths.

12. Multi-sig caveats — `multi_sig` on token `s` [v1.3]

Status: design specified; implementation deferred to v1.3.

Today a UCAN token has one signature in s. Multi-sig caveats let a token require N-of-M signers from a declared list.

12.1 Wire shape (proposed)

The token's s field becomes an ARRAY:

{
  "iss": "did:deos:org-finance",
  "aud": "did:deos:agent-y",
  "att": [{...}],
  "exp": ...,
  "nnc": "...",
  "multi_sig": {
    "required": 2,
    "signers": [
      "did:deos:officer-1#sig-1",
      "did:deos:officer-2#sig-1",
      "did:deos:officer-3#sig-1"
    ]
  },
  "s": [
    {"alg": "ed25519", "kid": "did:deos:officer-1#sig-1", "sig": "..."},
    {"alg": "ed25519", "kid": "did:deos:officer-2#sig-1", "sig": "..."}
  ]
}

Verifier checks ≥ required signatures verify, all kids are in declared signers list, each sig is over "deos-ucan-v1:" || canonical(token minus s).

12.2 Why deferred

Touches the canonical-signing path; needs careful spec to avoid breaking v1 single-sig tokens. v1.1 verifiers reject s arrays with unknown sub-fields cleanly; v1.3 ships with a feature-detection bit so v1.3 verifiers can tell whether a substrate supports multi-sig.

13. References

/ucan/tokens/v1 — UCAN token format
/revocation/v1 — extended in §5
UCAN v1.0 specification (https://github.com/ucan-wg/spec)
RFC 3552 — security considerations format

14. Maintainer

DEOS Computing — design questions and conformance reports to github.com/DEOS-Computing.

License: CC BY 4.0 (text), Apache-2.0 (reference code).

DEOS Capability Caveat Algebra — v1.1 Specification

1. Goals

2. Hierarchical can matching (UCAN1.1-4)

2.1 Syntax

2.2 Matching algorithm

2.3 Action satisfaction

2.4 Backward compatibility

3. Set-membership on with (CAV1.1-6)

3.1 Syntax

3.2 Mixed forms

3.3 Empty arrays

4. OR-composition within attenuations (CAV1.1-5)

4.1 Syntax

4.2 Validation

4.3 Action satisfaction with OR

5. Caveat-level revocation (CAV1.1-1)

5.1 The use case

5.2 Format

5.3 Verifier behavior

5.4 New endpoint

6. Tightened time-range composition (UCAN1.1-2 carve-out)

6.1 Effective time window

6.2 v1.0 fix

7. Worked examples

7.1 Hierarchical can

7.2 OR-composition

7.3 Caveat-level revocation

8. Implementation status

9. Security considerations

9.1 Wildcard escalation

9.2 OR-composition and revocation

9.3 Caveat path injection

9.4 Time-range composition under clock skew

10. Ratchets — seq caveat

10.1 Syntax

10.2 Substrate enforcement (normative)

10.3 Use-once tokens via seq

10.4 Limitations

11. Threshold caveats — threshold [v1.3]

11.1 Wire shape (proposed)

11.2 Attestation submission

11.3 Why deferred

12. Multi-sig caveats — multi_sig on token s [v1.3]

12.1 Wire shape (proposed)

12.2 Why deferred

13. References

14. Maintainer

2. Hierarchical `can` matching (UCAN1.1-4)

3. Set-membership on `with` (CAV1.1-6)

10. Ratchets — `seq` caveat

10.3 Use-once tokens via `seq`

11. Threshold caveats — `threshold` [v1.3]

12. Multi-sig caveats — `multi_sig` on token `s` [v1.3]