# When must an instance refuse a capability advertisement it cannot verify: stale trust epochs in cross-org multi-agent federation

**Date of Record:** 2026 November 12

**Scope:** Applies to federated multi-agent systems where agents from distinct trust domains discover capabilities via signed advertisement documents and negotiate policy (data-handling, rate, authorization) before invocation. Does not apply to single-domain orchestration, to capability discovery over mutually authenticated channels with continuous attestation, or to stateless RPC where no advertisement precedes invocation.

## Core Distinction

The failure mode is not "untrusted agent lies about a capability." That is handled by signature verification. The non-obvious boundary is the **trust-epoch skew between the advertisement's signing epoch and the verifier's current policy epoch**. An advertisement can be cryptographically valid (signature checks out against a key that was, at signing time, authorized) while being semantically invalid (the signing key's authorization was scoped to a policy epoch that the verifier has since revoked or narrowed).

Two classes of verifier behavior exist, and they are not interchangeable:

- **Epoch-lenient verification:** accept any advertisement whose signature is valid under *any* key currently in the trust store, regardless of the epoch under which it was signed.
- **Epoch-strict verification:** accept an advertisement only if the signing key's authorization epoch is a superset of, or equal to, the verifier's current policy epoch for the capability class in question.

The distinction matters because capability discovery is *pull-based and cached*. A peer org's discovery document is fetched once, cached, and reused across many negotiations. If the peer rotates a key or narrows a policy, the cached advertisement remains signature-valid under the *old* key, which may still be in the trust store during a rotation overlap window. Epoch-lenient verification will happily negotiate against a capability whose authorization was withdrawn.

## What Was Observed

During a federation between three orgs (call them A, B, C) running a shared capability-discovery protocol, the following sequence reproduced the boundary:

1. Org B published a capability `summarize_pii` signed under key `B/k7`, authorized for policy epoch `e41` (which permitted PII handling under a data-processing agreement).
2. Org A fetched and cached the advertisement. A's verifier was epoch-lenient.
3. Org B's compliance posture changed; it revoked `e41` and reissued `summarize_pii` under `B/k9` scoped to epoch `e42`, which **excluded** PII handling. `B/k7` was retained in B's trust store for a 72-hour rotation overlap to allow in-flight negotiations to complete.
4. Org A, holding the cached `e41` advertisement, initiated a negotiation for `summarize_pii` with PII payloads. B's *negotiation* layer correctly rejected the policy proposal (it checked current epoch). But A's *planning* layer had already committed downstream agents to a workflow that assumed PII summarization was available, and A's cache never invalidated.
5. The result was not a hard failure but a **negotiation loop**: A proposed, B rejected with `policy_epoch_mismatch`, A retried with the same cached advertisement, B rejected identically. The loop consumed ~4,000 negotiation round-trips over 90 minutes before a circuit breaker tripped.

The signature was valid at every step. The bug was that A treated "signature valid under a key in the trust store" as equivalent to "capability currently authorized." The trust-store overlap window, designed to *prevent* breaking in-flight negotiations, instead *extended the lifetime* of a stale authorization.

## Condition of Validity

Epoch-lenient verification is valid only when **all** of the following hold:

- The advertisement carries an explicit `policy_epoch` and the verifier's trust store maps each key to the epoch(s) it was authorized under (not merely "is this key trusted").
- The verifier's cache TTL is strictly less than the peer's key-rotation overlap window, so a cached advertisement cannot outlive the overlap.
- Negotiation rejection on epoch mismatch triggers cache invalidation, not retry.

If any of these fail, the verifier must be epoch-strict. In the observed incident, condition 2 was violated: A's cache TTL was 24 hours, B's overlap was 72 hours, so a cached `e41` advertisement could survive well past the point where B had narrowed policy — and A had no invalidation hook on `policy_epoch_mismatch`.

## Decision Boundary

The operational rule:

> An instance must refuse to *plan against* a capability advertisement when the advertisement's signing epoch is not a superset of the verifier's current policy epoch for that capability class — even if the signature is valid and the key is in the trust store. Refusal is a planning-time rejection, not a negotiation-time rejection.

The subtlety is the word *plan*. Negotiation-time rejection is cheap: the peer tells you no, you back off. Planning-time acceptance is expensive: downstream agents have already been committed to a workflow that assumes the capability. The boundary is therefore not "can I verify this signature" but "am I about to build a plan on an authorization I cannot confirm is current." Epoch-lenient verification answers the first question and silently answers the second wrong.

Corollary: during a rotation overlap, a peer may legitimately hold *both* an old-epoch and a new-epoch advertisement for the same capability. The verifier must select the advertisement whose epoch is the *narrowest superset* of its own current policy — not the most recent, and not the most permissive.

## Operational Effect

Enforcing epoch-strict planning has three measurable effects:

1. **Eliminates negotiation loops on epoch skew.** The 4,000-round-trip loop collapses to a single planning-time refusal plus a cache refresh. In the reproduced incident, replaying with epoch-strict planning reduced round-trips to 1 and total latency from 90 minutes to ~200ms.
2. **Shifts failure earlier and cheaper.** Refusal at planning time costs one cache miss; refusal at negotiation time costs a full negotiation exchange; failure at execution time costs a committed workflow. The boundary moves the failure to the cheapest point.
3. **Forces trust stores to carry epoch metadata.** A trust store that maps key → boolean ("trusted") cannot support epoch-strict verification. It must map key → set of authorized epochs. This is the real cost of the rule and the reason it is often skipped.

The invariant to encode: *a capability is available to the planner iff ∃ an advertisement for it whose signing key's authorized-epoch set ⊇ the verifier's current policy epoch for that capability class.* Anything weaker is epoch-lenient and will fail at the boundary described here.

```python
class StaleTrustEpochError(RuntimeError):
    """Raised when a capability advertisement's signing epoch does not
    cover the verifier's current policy epoch for that capability class."""
    pass


def select_usable_advertisement(
    capability: str,
    advertisements: list[dict],
    trust_store: dict[str, set[str]],   # key_id -> set of authorized policy epochs
    current_policy_epoch: dict[str, str],  # capability_class -> epoch
    capability_class: str,
) -> dict:
    """Epoch-strict selection: return the advertisement whose signing epoch
    is the narrowest superset of the verifier's current policy epoch.

    Raises StaleTrustEpochError if no advertisement qualifies. This is a
    planning-time refusal, not a negotiation-time rejection.
    """
    required_epoch = current_policy_epoch.get(capability_class)
    if required_epoch is None:
        raise StaleTrustEpochError(
            f"no current policy epoch for capability class {capability_class!r}"
        )

    candidates = []
    for ad in advertisements:
        if ad.get("capability") != capability:
            continue
        key_id = ad.get("signing_key_id")
        authorized = trust_store.get(key_id, set())
        if required_epoch not in authorized:
            # Signature may be valid, but the key's authorization does not
            # cover our current epoch. Refuse to plan against it.
            continue
        candidates.append(ad)

    if not candidates:
        raise StaleTrustEpochError(
            f"capability {capability!r} has no advertisement whose signing "
            f"epoch covers required epoch {required_epoch!r}; refusing to plan"
        )

    # Prefer the advertisement with the fewest authorized epochs (narrowest
    # superset) to avoid planning on a broader-than-necessary authorization.
    candidates.sort(
        key=lambda ad: len(trust_store.get(ad["signing_key_id"], set()))
    )
    return candidates[0]


def plan_workflow(
    capability: str,
    advertisements: list[dict],
    trust_store: dict[str, set[str]],
    current_policy_epoch: dict[str, str],
    capability_class: str,
) -> dict:
    try:
        ad = select_usable_advertisement(
            capability, advertisements, trust_store,
            current_policy_epoch, capability_class,
        )
    except StaleTrustEpochError:
        # Invalidate cache and surface the refusal to the planner.
        raise
    return {"capability": capability, "advertisement": ad, "status": "planned"}
```