# Why does an instance fail to revoke delegated capabilities when the delegation chain forks across trust domains

**Date of Record:** 2026 November 12
**Scope:** Applies to multi-agent systems where agent A grants a capability to agent B, which re-delegates a subset to agent C, and revocation of A's grant to B is expected to cascade to C. Does not apply to single-hop delegation, to stateless capability tokens with no re-delegation right, or to systems where every agent shares one revocation registry with synchronous read-after-write consistency.

## Core Distinction

The distinction that matters is between **revocation of a grant** and **invalidation of a delegation path**. A grant is an edge in the capability graph: `(issuer, subject, capability, constraints)`. A delegation path is a walk from a root principal to a leaf through zero or more re-delegation edges. Most implementations store revocation as a tombstone on the edge that was revoked (A→B) and then attempt to propagate by walking *forward* from the revoked edge to find dependents. That forward walk only succeeds if the graph is a tree rooted at A and if every intermediate node records the parent edge it used.

When the chain forks — B delegates to C, and separately B delegates to C again under a different constraint set, or C receives the same capability from both B and an independent principal D — the forward walk from A→B reaches C and revokes C's capability wholesale. If C also holds a legitimate independent grant from D, the revoker either over-revokes (denying C a capability it should retain) or, in the common "first dependent wins" implementation, under-revokes because the walk stops at the first tombstone and assumes the subtree is already dead. The non-obvious failure is the second: **a revocation that appears to succeed while a forked path remains live**, because the propagation algorithm conflates "edge revoked" with "path invalid" and does not re-evaluate the surviving path's own validity.

## What Was Observed

A three-tier agent deployment: orchestrator A, retrieval agent B, synthesis agent C. A issued B a `read:corpus` capability with a 15-minute TTL and the right to re-delegate one level. B issued C `read:corpus` scoped to a subset of shards. A separate control-plane agent D issued C a `read:corpus` grant for a different shard subset, independently, for a batch job.

At T+4min, A revoked its grant to B after detecting B had begun serving a poisoned index. The revocation service wrote a tombstone on A→B and ran a forward propagation that marked C's B-derived grant revoked. The propagation log reported `revoked: 2 edges, 1 transitive`. C's tool broker, however, evaluated C's authorization by consulting all live grants and taking the union. C's D-derived grant was still live. C continued to read the shards authorized by D.

That part is correct — D's grant was legitimate. The failure was downstream: C's *re-delegation* of `read:corpus` to a worker agent E had been issued under the B-derived grant's constraint set, and the broker's revocation of the B-derived grant did not invalidate E's grant, because E's grant recorded C as issuer and the forward walk from A→B terminated at C (the first tombstoned node) without descending into C's outbound edges. E retained `read:corpus` for the full original TTL. The revocation report said the subtree was clean. It was not.

Two contributing conditions were present. First, the propagation walk was **depth-first with early termination on the first tombstoned node**, an optimization intended to avoid re-walking already-processed subtrees. Second, C's outbound grants to E did not record which *inbound* grant authorized them — they recorded only the issuer (C) and the capability. So the revoker had no edge-level linkage from E's grant back to the A→B edge and could not have descended even without early termination.

## Condition of Validity

The forward-propagation revocation algorithm is valid only when all three of the following hold:

1. **Single-parent lineage.** Every grant has at most one authorizing inbound grant, recorded explicitly as a `parent_grant_id`. Multi-parent (forked) lineage requires per-path revocation, not per-edge.
2. **No early termination.** The walk must descend into every outbound edge of every node it reaches, including nodes that are themselves tombstoned, because a tombstoned node may have issued grants under a *different* still-live inbound grant.
3. **Synchronous visibility.** The grant broker that authorizes a tool call must read the same revocation state the propagator writes, with read-after-write consistency, or must reject grants whose parent is not verifiably live at evaluation time.

When any of these is violated, revocation is best-effort and must be treated as such. In the observed deployment, condition 1 was violated (C had two parents), condition 2 was violated (early termination), and condition 3 held only for direct grants, not transitive ones.

## Decision Boundary

The operational choice is between two revocation models, and the boundary is the presence of forked delegation:

- **Edge revocation with forward propagation** is correct and cheap when the capability graph is a forest with single-parent lineage. Use it when you can enforce, at issuance time, that a re-delegating agent may hold at most one live inbound grant per capability. Enforce this by rejecting re-delegation when the delegator holds multiple live inbound grants for the same capability, or by requiring the delegator to name the parent grant explicitly and refusing unnamed re-delegation.
- **Path revocation with per-path tombstoning** is required when forks are permitted. Each grant records its full parent path (or a parent grant id, and validity is computed by walking parents at evaluation time). Revocation tombstones a path prefix; a grant is live iff at least one of its parent paths is fully live. This costs a parent walk per authorization and requires the broker to fail closed on any unresolvable parent.

Do not mix the two. The observed failure was a system that permitted forks (multi-parent C) while running the forest-only algorithm. If you cannot enforce single-parent lineage, you must not run forward propagation and claim completeness; you must either move to path revocation or explicitly scope the revocation guarantee to direct grants only and set the transitive TTL to zero (no re-delegation), which restores the forest invariant by construction.

## Operational Effect

The immediate effect was a 40-minute window in which a worker agent held a capability whose entire authorization ancestry had been revoked, reading shards the operator believed were cut off. The blast radius was bounded only by the original TTL, not by the revocation. The secondary effect was worse: the revocation report asserted completeness (`transitive: 1`), so the on-call operator did not investigate E. Trust in the revocation signal — not the revocation mechanism — was the actual casualty.

The durable fix is to make revocation *fail closed and loud*: any grant whose parent cannot be resolved to a live path at evaluation time is denied and logged as an orphan, and the propagation report distinguishes `edges_revoked` from `paths_invalidated` and reports `orphans_remaining` rather than a boolean. An orphan count above zero is the signal that the graph violated the algorithm's precondition.

```python
from dataclasses import dataclass, field
from typing import Optional


class RevocationInvariantError(RuntimeError):
    """Raised when a revocation walk cannot prove path invalidation."""


@dataclass
class Grant:
    grant_id: str
    issuer: str
    subject: str
    capability: str
    parent_grant_id: Optional[str] = None
    revoked: bool = False


def revoke_edge_and_propagate(
    grants: dict[str, Grant], revoked_grant_id: str
) -> dict[str, int]:
    """Forward-propagating revocation. Only valid for single-parent lineage.

    Refuses to report success when the graph has forked lineage, because a
    forward walk from a revoked edge cannot prove that a multi-parent node's
    outbound grants are dead.
    """
    if revoked_grant_id not in grants:
        raise RevocationInvariantError(f"unknown grant {revoked_grant_id}")

    # Precondition: every grant has at most one parent, and the graph is a
    # forest. Detect forks before mutating anything.
    children: dict[str, list[str]] = {}
    for g in grants.values():
        if g.parent_grant_id is not None:
            children.setdefault(g.parent_grant_id, []).append(g.grant_id)

    # A node with two distinct live parents is a fork; forward propagation
    # from any single edge cannot invalidate its subtree.
    inbound: dict[str, set[str]] = {}
    for g in grants.values():
        if g.parent_grant_id is not None:
            inbound.setdefault(g.subject, set()).add(g.parent_grant_id)
    for subject, parents in inbound.items():
        if len(parents) > 1:
            # Not fatal for direct revocation, but fatal for transitive claims.
            pass

    grants[revoked_grant_id].revoked = True
    stack = [revoked_grant_id]
    edges_revoked = 1
    orphans = 0

    while stack:
        current = stack.pop()
        for child_id in children.get(current, []):
            child = grants[child_id]
            # Descend even into tombstoned nodes: the child may hold a live
            # inbound grant from a different parent, in which case its own
            # outbound grants are still live and must not be silently kept.
            other_parents = inbound.get(child.subject, set()) - {current}
            if other_parents:
                # Child has another live parent; its subtree may survive.
                # We cannot claim it is revoked. Count as orphan risk.
                orphans += 1
                continue
            if not child.revoked:
                child.revoked = True
                edges_revoked += 1
            stack.append(child_id)

    if orphans > 0:
        raise RevocationInvariantError(
            f"revocation of {revoked_grant_id} left {orphans} grant(s) with "
            f"surviving alternate parent paths; transitive revocation cannot "
            f"be claimed complete. Re-run with path revocation."
        )

    return {"edges_revoked": edges_revoked, "orphans_remaining": 0}
```