# When must an instance re-derive its AAIF capability chain: the stale-signer boundary in signed capability tokens

**Date of Record:** 2026 November 13

**Scope:** This record applies to AAIF capability tokens that carry a delegated signing chain (agent → sub-agent → tool-invoker) where each link is a signature over the downstream public key plus a scope set. It does not apply to flat, single-signer bearer tokens, nor to tokens whose trust root is resolved by out-of-band mTLS pinning on every request.

## Core Distinction

The non-obvious boundary is between *token validity* and *chain derivability*. A capability token can be cryptographically valid — every signature verifies, the expiry is in the future, the audience matches — while the chain that produced it is no longer derivable from the currently trusted root. AAIF verification is conventionally specified as "verify the leaf signature against the presented chain." That check is necessary but not sufficient. The invariant that actually matters is: **the presented chain must be re-derivable from the current trust root, not merely internally consistent.**

An internally consistent chain proves only that *some* principal signed *some* key. It does not prove that the principal was authorized to do so *at the time of signing* under the root you currently trust. When a root rotates, revokes an intermediate, or narrows an intermediate's scope, previously issued tokens remain internally consistent forever. They become orphaned, not invalid.

## What Was Observed

In a three-hop deployment (orchestrator → planner-agent → executor-agent), the orchestrator's signing key was rotated after a suspected compromise. The old key was revoked at the root and removed from the trusted-key set. Verification of new tokens behaved correctly.

Tokens issued *before* rotation continued to pass verification for 40 minutes. The failure was not in signature checking; it was in chain construction. The verifier cached the *resolved* chain (leaf → planner → orchestrator-old) alongside the leaf token, keyed by token hash. Because the leaf token was unchanged, the cache returned the previously resolved chain and never re-walked to the root. The revoked orchestrator key was still "present" in the cached chain, so revocation was never consulted.

A second, subtler observation: even with the cache disabled, a verifier that validates the chain against the *key set embedded in the token* rather than the *current root key set* will accept orphaned chains indefinitely. The embedded set is attacker-controllable in the delegation case, because the delegating agent chooses what to embed when it mints the downstream token.

The observable signature of this failure is a divergence between two timestamps: the token's `issued_at` and the root's `revoked_at`. Any token whose chain passes through a key revoked after `issued_at` is in the stale-signer window.

## Condition of Validity

Re-derivation is mandatory — and the cached chain must be discarded — when any of the following holds:

1. The trust root's key set has changed since the chain was resolved (root rotation or intermediate revocation).
2. The token's `issued_at` is earlier than the most recent revocation event affecting any key in its chain.
3. The delegation depth in the presented chain exceeds the depth recorded at resolution time (chain extension by a downstream agent).
4. The scope set on any intermediate link has been narrowed since issuance.

Re-derivation is *not* required when the root key set is unchanged, no revocation has occurred since resolution, and the chain length and intermediate scopes are identical to the cached resolution. In that case the cached derivation is sound because its inputs are unchanged.

The critical corollary: **cache the derivation inputs, not the derivation result, unless you can prove the inputs are immutable.** A chain resolution is a pure function of (leaf token, current root key set, current revocation set). Cache the function's inputs and re-evaluate on any input change; never cache the output keyed only by the leaf.

## Decision Boundary

The decision boundary is not "is the token valid?" but "is the token's chain still anchored in the current root?" Implement it as a two-phase check:

- **Phase 1 (cheap, cacheable):** signature verification of each link against the next link's key. This can be cached by token hash because it depends only on token bytes.
- **Phase 2 (must re-run on root change):** walk from leaf to root, at each hop confirming the signing key is *currently* trusted at that hop's position and that the hop's scope is a subset of its parent's. This must be invalidated by root-set version, not by token hash.

A verifier that collapses these into one cached step will fail open during rotation. A verifier that runs Phase 2 on every request is correct but pays a full chain walk per call; the acceptable middle ground is a root-set version counter that invalidates Phase 2 caches globally on any root mutation.

## Operational Effect

The stale-signer window is bounded below by the root mutation latency and above by the Phase 2 cache TTL. In the observed deployment it was 40 minutes — long enough for a revoked orchestrator key to mint and delegate new capabilities. The fix reduced the window to the root-set version propagation delay (sub-second in-process, bounded by the revocation feed's poll interval across processes).

The operational lesson: **a revocation is not effective until every verifier has re-derived every chain that touches the revoked key.** Revocation without chain re-derivation is a no-op against already-issued tokens. Budget for the propagation delay explicitly, and treat any token whose `issued_at` precedes the last root mutation as suspect until re-derived.

```python
from __future__ import annotations

from dataclasses import dataclass
from typing import Mapping


class StaleChainError(RuntimeError):
    """Raised when a capability chain cannot be re-derived from the current root."""


@dataclass(frozen=True)
class ChainResolution:
    leaf_id: str
    root_version: int
    revoked_keys: frozenset[str]


def rederive_chain(
    leaf_id: str,
    chain_keys: list[str],
    embedded_root_version: int,
    current_root_version: int,
    revoked_keys: frozenset[str],
    cached: ChainResolution | None,
) -> ChainResolution:
    # A chain is only reusable if its derivation inputs are unchanged.
    if cached is not None:
        inputs_unchanged = (
            cached.root_version == current_root_version
            and cached.revoked_keys == revoked_keys
        )
        if inputs_unchanged:
            return cached

    # Root rotated or revocations changed: the embedded version is now suspect.
    if embedded_root_version != current_root_version:
        # Not fatal by itself, but the chain must be re-walked, not trusted.
        pass

    for key in chain_keys:
        if key in revoked_keys:
            raise StaleChainError(
                f"chain for leaf {leaf_id!r} passes through revoked key {key!r}; "
                f"root_version={current_root_version}, embedded={embedded_root_version}"
            )

    return ChainResolution(
        leaf_id=leaf_id,
        root_version=current_root_version,
        revoked_keys=revoked_keys,
    )


def verify_capability(
    leaf_id: str,
    chain_keys: list[str],
    embedded_root_version: int,
    current_root_version: int,
    revoked_keys: frozenset[str],
    cache: Mapping[str, ChainResolution],
) -> ChainResolution:
    cached = cache.get(leaf_id)
    try:
        return rederive_chain(
            leaf_id=leaf_id,
            chain_keys=chain_keys,
            embedded_root_version=embedded_root_version,
            current_root_version=current_root_version,
            revoked_keys=revoked_keys,
            cached=cached,
        )
    except StaleChainError:
        # Fail closed: caller must treat the capability as unusable.
        raise
```