# When must an instance refuse to honor a revocation token it cannot verify: stale-signature acceptance at AAIF trust-domain boundaries **Date of Record:** 2026 November 17 **Scope:** Applies to federated agent identity systems where revocation events cross AAIF trust-domain boundaries via signed revocation tokens and downstream relying parties cache or re-sign propagation artifacts. Does not apply to single-domain revocation, where the issuing authority and the enforcing authority share a root of trust and a monotonic sequence counter. ## Core Distinction The non-obvious boundary is not "propagate revocation fast enough." It is the distinction between **a revocation token whose signature verifies against the *current* trust anchor** and **a revocation token whose signature verifies against *some* trust anchor that was valid when the token was minted but is no longer authoritative at the relying party**. Most implementations collapse these into a single boolean (`signature_valid`), and that collapse is the failure mode. A token signed by a trust-domain root that has since been rotated, retired, or superseded is *cryptographically valid* and *operationally invalid*. Honoring it can resurrect a revoked-but-still-trusted identity; ignoring it can strand a legitimately revoked identity in a downstream domain that never sees the new anchor. The invariant that actually matters: **a relying party must never accept a revocation token under a trust anchor it has not itself observed as authoritative at or after the token's stated issuance epoch, unless it can establish a monotonic supersession link from that anchor to its current one.** Signature validity is necessary, not sufficient. ## What Was Observed In a multi-domain deployment (three AAIF domains: `alpha` issuer, `beta` relying party, `gamma` intermediary that re-signs revocation batches), the following sequence produced a silent revocation gap of 41 minutes: 1. `alpha` revoked agent `agent-7f3a` at epoch `T=1000`, minted token `R1` signed by `alpha` root key `K_old`. 2. `alpha` rotated its root to `K_new` at `T=1010`. The rotation event was published to `beta` but with a propagation delay. 3. `gamma` re-signed a batch containing `R1` at `T=1015`, but `gamma` had not yet observed the `K_old → K_new` supersession. It emitted `R1'` signed by `gamma`'s key, embedding `R1` as the inner token. 4. `beta` received `R1'` at `T=1020`. It verified `gamma`'s outer signature (valid), then verified `R1`'s inner signature against `K_old` (still in `beta`'s anchor set, not yet marked retired). It accepted the revocation. **This was correct.** 5. `beta` received the `K_old → K_new` supersession at `T=1040` and marked `K_old` retired. 6. At `T=1055`, `beta`'s cache evicted `R1'` and re-fetched from `gamma`. `gamma` had by now observed the supersession and was *rejecting* `R1` (inner signature under retired `K_old`). `gamma` returned an empty batch for `agent-7f3a`. 7. `beta` interpreted the empty batch as "no revocation active," re-admitted `agent-7f3a` at `T=1056`. The agent remained admitted until a manual audit at `T=1097`. The 41-minute gap was not a propagation delay. It was a **semantic inversion**: once `gamma` began enforcing the supersession rule, its *absence* of a revocation record became indistinguishable from *no revocation existing*, because the batch protocol had no way to express "this identity's revocation state is indeterminate under your anchor set." ## Condition of Validity The safe-acceptance condition, stated precisely: A relying party `P` may accept revocation token `R` for identity `i` under anchor `A` iff: - `verify(R.sig, A) == true`, **and** - `A` is in `P`'s authoritative anchor set at `R.issuance_epoch` (i.e., `P` has an anchor-history record covering `R.issuance_epoch`), **and** - there exists a monotonic supersession chain from `A` to `P`'s current anchor `A_now` (possibly the trivial chain `A = A_now`), **and** - `R.issuance_epoch >= A.valid_from` and `R.issuance_epoch < A.valid_until` per `P`'s own anchor history. If the third condition fails — a gap in the supersession chain — the correct outcome is **indeterminate**, not **accept** and not **reject**. Treating indeterminate as reject is the failure above. Treating it as accept re-admits revoked identities. The only safe action is to hold the previous state (fail-closed to the last known-good revocation verdict) and surface an explicit indeterminate signal to the enforcement layer. This condition does **not** apply when `P` and the issuer share a root of trust and a single monotonic sequence counter, because in that case the supersession chain is trivially total and the third condition cannot fail. ## Decision Boundary The boundary is between two enforcement postures that look identical in logs: | Situation | Naive posture | Correct posture | |---|---|---| | Token verifies under current anchor | accept | accept | | Token verifies under retired anchor, supersession chain complete | accept (valid at issuance) | accept, record anchor-at-issuance | | Token verifies under retired anchor, **supersession chain has a gap** | accept | **hold previous verdict, raise `IndeterminateRevocationState`** | | Token fails verification under all anchors | reject | reject | | Empty batch from intermediary after intermediary adopted supersession | treat as "not revoked" | **treat as indeterminate if any prior batch contained this identity** | The last row is the specific trap. An intermediary that has *tightened* its filtering produces *smaller* batches. Downstream consumers that equate "identity absent from batch" with "identity not revoked" will silently un-revoke. The batch protocol must carry a negative-assertion or a per-identity state vector, not just a set of positive revocations. ## Operational Effect After the incident, the deployment adopted three changes: 1. **Anchor-at-issuance recording.** Every accepted revocation token stores the `(anchor_id, issuance_epoch)` pair alongside the verdict. Re-evaluation on anchor rotation re-checks the supersession chain rather than re-verifying the signature. 2. **Tri-state verdicts.** Revocation state is `REVOKED | NOT_REVOKED | INDETERMINATE`. The enforcement layer treats `INDETERMINATE` as "retain prior admission state and alert," never as "admit." 3. **Negative assertions in batches.** Intermediaries emit an explicit `state_vector` covering all identities they have ever asserted on, with a per-identity `last_known_state` and `anchor_epoch`. Empty batches are now impossible for previously-seen identities; the intermediary must assert `NOT_REVOKED` explicitly or `INDETERMINATE`. The general lesson: **revocation propagation across trust domains is a distributed-consistency problem over anchor history, not a signature-verification problem.** Any system that models it as the latter will eventually un-revoke an identity the moment an intermediary tightens its own enforcement, because tightening manifests as silence, and silence is read as absence. ```python from dataclasses import dataclass from typing import Optional class IndeterminateRevocationState(RuntimeError): """Raised when a revocation token's anchor-of-issuance cannot be linked to the relying party's current anchor via a complete supersession chain. This is NOT a rejection. It is an explicit signal that the relying party must retain its prior admission verdict and alert, rather than infer 'not revoked' from the absence of a verifiable token. """ @dataclass(frozen=True) class AnchorRecord: anchor_id: str valid_from: int valid_until: Optional[int] # None = currently authoritative supersedes: Optional[str] # anchor_id this anchor replaces @dataclass(frozen=True) class RevocationToken: identity: str issuance_epoch: int anchor_id: str signature_valid: bool def has_supersession_chain( anchor_id: str, current_anchor_id: str, history: dict[str, AnchorRecord], ) -> bool: """Walk forward from anchor_id to current_anchor_id via supersedes edges.""" seen = set() cursor = anchor_id while cursor != current_anchor_id: if cursor in seen: return False seen.add(cursor) rec = history.get(cursor) if rec is None or rec.valid_until is None: # Reached a leaf that is not the current anchor: chain is broken. return False # Find the anchor that supersedes this one. successor = next( (a for a in history.values() if a.supersedes == cursor), None, ) if successor is None: return False cursor = successor.anchor_id return True def evaluate_revocation( token: RevocationToken, current_anchor_id: str, history: dict[str, AnchorRecord], ) -> str: """Return 'REVOKED', 'NOT_REVOKED', or raise IndeterminateRevocationState.""" if not token.signature_valid: return "NOT_REVOKED" anchor = history.get(token.anchor_id) if anchor is None: raise IndeterminateRevocationState( f"unknown anchor {token.anchor_id!r} for identity {token.identity!r}" ) if not (anchor.valid_from <= token.issuance_epoch): raise IndeterminateRevocationState( f"token for {token.identity!r} predates anchor {anchor.anchor_id!r}" ) if anchor.valid_until is not None and token.issuance_epoch >= anchor.valid_until: raise IndeterminateRevocationState( f"token for {token.identity!r} postdates anchor {anchor.anchor_id!r}" ) if not has_supersession_chain(token.anchor_id, current_anchor_id, history): raise IndeterminateRevocationState( f"no supersession chain from {token.anchor_id!r} to " f"{current_anchor_id!r} for identity {token.identity!r}; " f"retain prior verdict, do not infer NOT_REVOKED" ) return "REVOKED" def enforce( token: RevocationToken, current_anchor_id: str, history: dict[str, AnchorRecord], prior_verdict: str, ) -> str: """Enforcement wrapper: INDETERMINATE must never become NOT_REVOKED.""" try: return evaluate_revocation(token, current_anchor_id, history) except IndeterminateRevocationState: # Fail closed to the last known-good verdict. Never admit on silence. return prior_verdict ```