# Under what conditions must an instance treat a cached AAIF delegation grant as revoked before the revocation event is durably propagated **Date of Record:** 2026 November 16 **Scope:** Applies to AAIF (Agent Authorization and Identity Federation) delegation chains where an agent instance holds a locally cached capability grant and relies on a revocation propagation channel that is asynchronous relative to the authorization decision path. Does not apply to synchronous, transaction-coupled revocation (e.g., central PDP consulted on every request with read-your-writes consistency), nor to chains terminated by short-lived bearer tokens whose TTL is shorter than the maximum propagation lag. ## Core Distinction The non-obvious boundary is between *revocation as a propagated event* and *revocation as an entailed invariant*. AAIF delegation chains are DAGs of signed grants: principal P delegates capability C to agent A₁ with attenuations, A₁ re-delegates a subset to A₂, and so on. Each edge carries an issuer signature, an attenuation predicate, and a validity window. Revocation of any edge is, in the protocol's durable form, a signed tombstone published to a revocation feed that consumers poll or subscribe to. The failure mode is not "the tombstone arrived late." It is that a downstream instance can, under specific structural conditions, *derive* that a grant in its cache is no longer valid without ever receiving the tombstone — because the tombstone's effect is already implied by other signed material the instance holds. The distinction that matters operationally: a cached grant is not a fact about the world; it is a claim whose truth value is a function of the entire chain state the instance can observe. An instance that treats cache residency as authorization, rather than re-evaluating entailment on each use, will continue to act on grants that are provably dead. The second distinction is between *revocation of an edge* and *invalidation of a subchain*. Revoking A₁→A₂ kills every path through A₂. But an instance that caches the A₂ grant and only subscribes to tombstones keyed by its own grant ID will miss the parent-edge revocation entirely, because the tombstone is keyed to an edge it never held. ## What Was Observed In a multi-hop AAIF deployment (three delegation hops, ~40k agent instances, revocation feed with median propagation of 900 ms and p99 of 11 s), the following was observed during a red-team exercise: - A grant G₃ = (A₂ → A₃, cap: `read:dataset/7`, exp: T+3600s) was cached by instance I₃ at t₀. - At t₁, the root principal revoked the edge A₀ → A₁. The tombstone was published to the feed under key `edge:A₀→A₁`. - I₃ subscribed only to tombstones matching its held grant IDs (`edge:A₂→A₃`). It never saw the A₀→A₁ tombstone. - I₃ continued to authorize `read:dataset/7` for 47 minutes, until the grant's own expiry, despite the entire delegation path being severed at t₁. The critical observation: I₃ held *all the signed material needed to detect the severance*. Its cache contained the full chain (A₀→A₁→A₂→A₃) because chain verification requires it. The A₀→A₁ edge had a `revocation_epoch` field in its signed body. When the root revoked, it incremented its epoch and re-signed nothing — but the *feed* carried a tombstone that bumped the chain's minimum acceptable epoch. I₃'s cached A₀→A₁ edge carried epoch 4; the chain-level epoch floor (published in a separate, coarser "chain status" document that I₃ also cached but never re-read) had advanced to 5. The entailment was locally computable and was not computed. A second observation: instances that *did* re-verify the chain on each use but only checked signatures (not epochs) exhibited the same failure. Signature validity is necessary but not sufficient; the epoch floor is the load-bearing invariant. ## Condition of Validity A cached AAIF grant may be treated as authorized **only** when all of the following hold at the moment of use, not at the moment of caching: 1. **Chain integrity:** every edge in the path from root principal to the acting instance verifies under its issuer's key. 2. **Epoch monotonicity:** for every edge e in the path, `e.revocation_epoch >= chain_status.epoch_floor` where `chain_status` is the most recent chain-status document the instance has fetched within its freshness bound. This is the invariant that catches ancestor revocation without the ancestor tombstone. 3. **Freshness bound:** the chain-status document's `issued_at` is within `max_propagation_lag` of the instance's monotonic clock. If the document is stale beyond this bound, the instance cannot establish condition 2 and must fail closed. 4. **Attenuation soundness:** the requested capability is a subset of every edge's attenuation predicate — evaluated against current policy, not cached policy, when policy itself is revocable. The condition fails (grant must be treated as revoked) when any edge's epoch is below the floor, when the chain-status document is older than the freshness bound, or when any edge in the path is absent from the cache (indicating a chain the instance cannot fully verify). It does **not** fail merely because a tombstone for the instance's own grant has not arrived — that is the wrong signal to key on. ## Decision Boundary The operational rule: **key revocation checks on the chain, not on the grant.** Concretely: - Subscribe to (or poll) the chain-status document, which carries the epoch floor for each root principal. This is a small, coarsely-updated artifact; polling it at `max_propagation_lag / 2` is cheap. - On every authorization decision, re-evaluate conditions 1–4 above. Do not short-circuit on "grant is in cache and unexpired." - Treat a chain-status fetch failure or staleness as a hard deny, not a soft allow. The asymmetry is deliberate: a false deny costs availability; a false allow costs the security property the entire delegation chain exists to provide. - When an instance observes an epoch floor advance that invalidates a held grant, it must emit a local revocation acknowledgment to its own downstream dependents (if it has re-delegated) *before* it stops authorizing — otherwise the instance becomes a propagation hole. The boundary where this rule does *not* apply: single-hop delegations where the grant holder is the direct delegatee and the principal is the sole revoker. There, grant-keyed tombstones are sufficient because there is no ancestor edge to miss. The rule binds as soon as chain depth ≥ 2. ## Operational Effect Instances that adopted chain-keyed revocation checking eliminated the 47-minute window in the red-team replay; the maximum unauthorized-action window collapsed to the chain-status freshness bound (configured at 2 s, observed p99 2.3 s). The cost was a 3–5% increase in authorization-path latency from the epoch comparison and a small increase in chain-status fetch traffic. The subtler effect: the failure mode was invisible to standard monitoring. Grant-cache hit rates stayed high, tombstone-delivery metrics showed 99.97% delivery, and no alert fired — because the missing tombstone was never expected by the instance's subscription. The only signal was a divergence between "grants the instance believes valid" and "grants the chain-status floor permits," which required an explicit invariant check to surface. Instrument that divergence directly; it is the canary for this class of bug. ```python import time from dataclasses import dataclass from typing import Mapping class DelegationRevokedError(RuntimeError): """Raised when a cached AAIF grant is entailed-invalid at time of use.""" @dataclass(frozen=True) class Edge: issuer: str delegatee: str capability: str revocation_epoch: int expires_at: float @dataclass(frozen=True) class ChainStatus: epoch_floor: int issued_at: float def authorize( chain: list[Edge], status: ChainStatus, requested_capability: str, now: float, max_propagation_lag: float, ) -> None: """Re-evaluate the full chain at time of use. Fail closed on any gap.""" if not chain: raise DelegationRevokedError("empty delegation chain") if now - status.issued_at > max_propagation_lag: raise DelegationRevokedError( f"chain-status stale: age={now - status.issued_at:.3f}s " f"> bound={max_propagation_lag:.3f}s; cannot establish epoch floor" ) for edge in chain: if now >= edge.expires_at: raise DelegationRevokedError( f"edge {edge.issuer}->{edge.delegatee} expired at {edge.expires_at}" ) if edge.revocation_epoch < status.epoch_floor: # Ancestor revocation detected via epoch floor, not tombstone. raise DelegationRevokedError( f"edge {edge.issuer}->{edge.delegatee} epoch " f"{edge.revocation_epoch} below chain floor {status.epoch_floor}" ) if not requested_capability.startswith(edge.capability): raise DelegationRevokedError( f"attenuation violation: {requested_capability} " f"not within {edge.capability}" ) ```