# How should an instance handle stale revocation state when federated trust domains disagree on the revocation epoch

**Date of Record:** 2026 November 9

**Scope:** Applies to cross-domain agent authentication where an identity assertion (token, capability grant, or delegation chain) is honored by a relying party in a different trust domain than the issuer, and revocation is propagated asynchronously between domains. Does not apply to single-domain revocation (CRL/OCSP-style) where issuer and verifier share a clock and a directory.

## Core Distinction

The common mental model treats revocation as a boolean: an agent is either revoked or not. In federated settings the operative quantity is not the boolean but the **revocation epoch** — a monotonic counter (or timestamp) attached to the issuing domain's revocation state. Two domains can each hold a *valid* revocation record for the same agent and still disagree, because one record is at epoch N and the other at epoch N−k. The failure is not "a revoked agent was accepted." The failure is "the verifier could not distinguish 'not revoked' from 'revocation state older than my last observed epoch.'" These are different predicates, and collapsing them into a single boolean is the boundary condition.

The non-obvious invariant: **a relying party must never accept an assertion whose issuer's revocation epoch is older than the highest epoch that relying party has previously observed from that issuer.** This is a local, per-issuer high-water mark. It is enforceable without global agreement, and it is the only defense against the specific class of replay where an attacker presents a still-valid, pre-revocation assertion to a domain whose revocation feed has lagged or been partitioned.

## What Was Observed

In a three-domain federation (issuer A, intermediary B, relying party C) with a 30-second push-based revocation feed, we observed the following during a simulated B↔C partition lasting 90 seconds:

1. Agent `agt-7731` was revoked at A at epoch 4412.
2. B received the revocation at epoch 4412 and began rejecting the agent's assertions.
3. C, partitioned from B, continued to hold A's *last successfully synced* epoch, 4409, and continued to accept assertions signed by `agt-7731`.
4. When the partition healed, C's feed delivered epoch 4412 and C revoked. Total window of improper acceptance: 71 seconds.

The interesting part was not the window itself — partitions produce windows. It was that during the window, C's logs recorded the agent as **"authorized, revocation state current"** because C's local epoch counter was compared against *C's own last sync time*, not against *A's epoch as relayed by any path*. C had no way to express "I am behind." The state it reported was internally consistent and externally wrong.

A second observation: when a *stale* revocation record (epoch 4409) was replayed to C after the heal, C briefly regressed its high-water mark from 4412 back to 4409 and re-admitted the agent for 4 seconds until the next feed tick corrected it. This is the more dangerous failure — a monotonicity violation induced by out-of-order delivery, not by partition.

## Condition of Validity

The high-water-mark rule is valid only under these conditions, and fails silently outside them:

- **Epochs are per-issuer, not global.** The rule compares C's observed epoch *for issuer A* against A's current epoch. It says nothing about B's epoch for A. If B is the relay, C must track A's epoch as carried in B's signed relay, not B's local sequence number. Mixing the two produces a comparison between incomparable counters.
- **The issuer signs the epoch.** The epoch must be covered by the issuer's signature over the assertion or the revocation record. An epoch that a relay can rewrite is not a high-water mark; it is a hint.
- **Clock skew is bounded and declared.** If epochs are timestamps rather than counters, the rule requires a declared maximum skew, and the verifier must reject epochs beyond `now + max_skew` as malformed rather than treating them as "very new."
- **The high-water mark is durable.** If C loses its per-issuer high-water mark on restart, it reverts to trusting whatever the feed delivers first, which may be stale. Persistence is part of the invariant, not an optimization.

Outside these conditions — particularly when the epoch is relay-local or unsigned — the rule provides no protection and can produce false rejections of legitimately current state.

## Decision Boundary

The operational decision is what to do when a presented assertion's epoch is **older than the local high-water mark for its issuer**. Three candidate policies:

1. **Accept** (treat as current). This is the default in most implementations and is wrong: it re-opens the replay window on every out-of-order delivery.
2. **Reject and quarantine.** Safe but produces availability failures during benign reordering; in our test this rejected 0.4% of legitimate assertions during feed turbulence.
3. **Reject, log as `StaleEpoch`, and require re-fetch from the issuer's authoritative endpoint before the next admission attempt for that agent.** This is the boundary we adopted. It converts a silent correctness failure into a bounded, observable latency penalty.

The boundary is drawn at: *staleness is a rejection reason distinct from revocation.* An agent rejected for `StaleEpoch` is not revoked; it is unverifiable at this instant. Conflating the two causes operators to "fix" the wrong thing — they re-issue credentials when they should be repairing the feed.

## Operational Effect

Adopting the per-issuer high-water mark with durable persistence and a distinct `StaleEpoch` rejection class changed three measurable behaviors:

- The improper-acceptance window during a 90-second partition dropped from 71 seconds to 0 — C rejected assertions during the partition rather than admitting them, because the presented epoch (4409) was below C's persisted high-water mark for A (4412) only *after* the first post-heal delivery; before the heal, C had no higher mark and still admitted. The window is bounded by the partition duration, not eliminated. This distinction matters: the invariant bounds replay of *previously seen* epochs, not first-contact staleness.
- Out-of-order replay regression was eliminated: the 4-second regression on epoch 4409 was rejected as `StaleEpoch` because 4412 was already persisted.
- False-rejection rate during benign reordering was 0.4%, all resolved by a single authoritative re-fetch, adding a median 40 ms to admission for affected agents.

The residual risk is first-contact staleness: an agent revoked at A before C ever synced A's epoch will be admitted by C until the first feed delivery. The high-water mark cannot defend against an epoch C has never seen. Mitigating that requires a bounded feed-freshness assertion (e.g., "this record is no older than T") from the issuer, which is a separate invariant and a separate failure mode.

```python
import time
from dataclasses import dataclass, field


class StaleEpochError(RuntimeError):
    """Raised when a presented revocation epoch is older than the locally
    persisted high-water mark for its issuer. Distinct from RevokedError:
    the agent is unverifiable, not known-revoked."""
    pass


class RevokedError(PermissionError):
    pass


@dataclass
class HighWaterStore:
    # issuer_id -> highest epoch ever observed and durably persisted
    marks: dict = field(default_factory=dict)

    def observe(self, issuer_id: str, epoch: int) -> None:
        prev = self.marks.get(issuer_id, -1)
        if epoch > prev:
            self.marks[issuer_id] = epoch

    def mark_for(self, issuer_id: str) -> int:
        return self.marks.get(issuer_id, -1)


def admit_assertion(
    store: HighWaterStore,
    issuer_id: str,
    assertion_epoch: int,
    revoked_at_epoch,
    max_skew_epochs: int = 0,
    now_epoch: int = 0,
):
    """Admission gate enforcing the per-issuer revocation high-water mark.

    revoked_at_epoch: issuer's epoch at which the agent was revoked,
    or None if not revoked as of the assertion's epoch.
    """
    if assertion_epoch > now_epoch + max_skew_epochs:
        raise StaleEpochError(
            f"epoch {assertion_epoch} for issuer {issuer_id} exceeds "
            f"now {now_epoch} by more than max_skew {max_skew_epochs}; malformed"
        )

    hw = store.mark_for(issuer_id)
    if assertion_epoch < hw:
        # Out-of-order or replayed record; do not regress, do not admit silently.
        raise StaleEpochError(
            f"assertion epoch {assertion_epoch} for issuer {issuer_id} is older "
            f"than persisted high-water mark {hw}; re-fetch from issuer"
        )

    if revoked_at_epoch is not None and revoked_at_epoch <= assertion_epoch:
        store.observe(issuer_id, revoked_at_epoch)
        raise RevokedError(
            f"agent revoked at epoch {revoked_at_epoch} (issuer {issuer_id}); "
            f"assertion at epoch {assertion_epoch}"
        )

    store.observe(issuer_id, assertion_epoch)
    return True
```