# Which invariants prevent revocation from being a linearizable operation across federated agent identity graphs

**Date of Record:** 2026 November 14

**Scope:** Applies to cross-org agent identity federation where agents present verifiable credentials (VCs) signed by a home-org issuer and relying-party orgs (RPs) admit them based on trust chains and revocation status. Does not apply to single-org deployments where issuer and verifier share a single revocation database, nor to purely capability-token systems with short TTLs and no persistent credential state.

## Core Distinction

The non-obvious boundary is between *revocation visibility* and *revocation authority*. Most federation designs assume that once a revocation event is published to a status list (e.g., Bitstring Status List, OCSP-style responder, or a signed revocation registry), any RP that can read the list has "revoked" the credential. This conflates two invariants:

1. **Issuer-side monotonicity**: the issuer's revocation set only grows, and each status list entry is signed and versioned.
2. **Verifier-side causal consistency**: an RP must not admit a credential whose revocation was *causally prior* to the RP's admission decision.

The second invariant cannot be satisfied by list-reading alone. It requires that the RP's admission decision be causally ordered after the issuer's revocation event, which is not guaranteed by any bounded staleness window. A status list fetched at time *t* reflects the issuer's state at some *t' ≤ t*, but the RP has no proof that no revocation occurred in *(t', t)*. This is the revocation gap: a credentialed agent can operate in the window between revocation and propagation, and the window is unbounded under partition.

## What Was Observed

In a three-org federation (issuer A, RP B, RP C) using signed status lists with 5-minute cache TTLs, we observed the following during a network partition between A and B:

- Agent *a₁* was revoked at A at T+0 due to a compromised signing key.
- RP C, still connected to A, refreshed its status list at T+90s and began rejecting *a₁*.
- RP B, partitioned from A, continued to serve cached status list (last successful fetch T−240s) and admitted *a₁* for 41 minutes until partition healed.
- During that window, *a₁* invoked a cross-org workflow on B that wrote to a shared downstream system also reachable by C. C had already revoked *a₁* but had no mechanism to signal B's *already-admitted* session.

The critical observation: **B's admission was locally correct** — its cached list was validly signed and within its configured staleness bound. The failure was not a bug in B's verifier; it was the absence of a cross-org invariant binding B's admission to C's revocation knowledge. The credential graph had a cycle of trust but no cycle of revocation propagation.

A second observation: revocation of *a₁* at A did not propagate to derived credentials. Agent *a₁* had, prior to revocation, issued a delegation credential to sub-agent *a₂* (a common pattern for multi-agent workflows). A's revocation list covered *a₁*'s credential but not *a₂*'s delegated credential, which carried a chain pointer to *a₁*. RPs that validated *a₂* checked *a₂*'s status (valid) and *a₂*'s chain to *a₁* (signature valid) but did not re-check *a₁*'s status at admission time. Delegation chains create transitive revocation obligations that status lists do not encode.

## Condition of Validity

The invariant "an RP admits a credential only if it is not revoked" holds only under the conjunction:

- (i) the RP's status fetch is causally after the issuer's latest revocation event for that credential, **or** the credential's validity interval has a bounded, issuer-attested freshness proof (e.g., short-lived VCs with `nbf`/`exp` and issuer-signed `revocation_epoch`);
- (ii) delegated credentials carry an explicit chain-revocation root that RPs re-evaluate at admission, not merely at chain-construction time;
- (iii) the RP's admission decision is logged with the status-list version it relied on, so post-hoc reconciliation can identify admitted-during-gap sessions.

Absent (i), the system provides *eventual* revocation with unbounded gap under partition. Absent (ii), delegation bypasses revocation entirely. Absent (iii), gap-window admissions are unrecoverable.

## Decision Boundary

The operational decision: **do not treat status-list freshness as a revocation guarantee; treat it as a revocation hint, and gate admission on a freshness proof with a hard upper bound.**

Concretely, for each credential class, choose one:

- **Short-lived VCs** (`exp − nbf ≤ Δ`, Δ small, e.g. 10 min): rely on expiry; status list is advisory. Requires issuer to re-issue frequently and RP to tolerate re-issuance latency.
- **Long-lived VCs with epoch attestation**: issuer publishes a signed `revocation_epoch` counter; RP rejects if its last-seen epoch is older than a configured `max_epoch_lag`. Under partition, admission fails closed once lag exceeds bound. This trades availability for the revocation invariant.
- **Delegation chains**: require the delegated VC to embed the root credential's status pointer and epoch, and require RP to validate the full chain's status at admission. This makes delegation O(chain depth) at admission, which is the cost of the invariant.

The boundary is crossed when an operator configures `max_epoch_lag` larger than the partition-detection time, or when delegation chains are validated only at issuance. In both cases the system silently degrades to eventual revocation without the operator noticing, because every individual component reports healthy.

## Operational Effect

Under the chosen discipline, the observable effects are:

- Partition between issuer and RP causes **fail-closed admission** for long-lived credentials after `max_epoch_lag`, not silent stale admission. This surfaces the partition as an availability incident rather than a security incident — the correct trade for identity.
- Delegated agents incur chain-status validation cost at every admission; caches must be keyed by `(root_credential_id, epoch)` and invalidated on epoch advance.
- Post-hoc reconciliation queries the admission log for sessions whose relied-upon epoch was later superseded by a revocation with `revocation_time < admission_time`. These are the gap-window sessions and must be treated as suspect, not as valid.

The invariant that holds is: *no RP admits a credential whose revocation is causally prior to admission, provided the RP enforces a bounded epoch lag and validates delegation chain status at admission.* The invariant that does not hold, and must not be assumed: *status-list freshness implies revocation correctness.* It does not, and under partition the gap is unbounded.

```python
import time
from dataclasses import dataclass


class RevocationGapError(RuntimeError):
    """Raised when an admission decision cannot be causally ordered after the issuer's revocation state."""


@dataclass(frozen=True)
class StatusSnapshot:
    credential_id: str
    epoch: int
    fetched_at: float
    revoked: bool


@dataclass(frozen=True)
class AdmissionRequest:
    credential_id: str
    chain_root_id: str
    now: float


def admit(
    req: AdmissionRequest,
    snapshot: StatusSnapshot,
    chain_root_snapshot: StatusSnapshot,
    max_epoch_lag: int,
    issuer_epoch: int,
) -> bool:
    # Invariant (i): snapshot must be within bounded epoch lag of issuer.
    if issuer_epoch - snapshot.epoch > max_epoch_lag:
        raise RevocationGapError(
            f"credential {req.credential_id}: snapshot epoch {snapshot.epoch} "
            f"lags issuer epoch {issuer_epoch} by more than {max_epoch_lag}; "
            f"cannot order admission after revocation state"
        )
    # Invariant (ii): delegation chain root must be re-checked at admission.
    if issuer_epoch - chain_root_snapshot.epoch > max_epoch_lag:
        raise RevocationGapError(
            f"credential {req.credential_id}: chain root {req.chain_root_id} "
            f"status epoch {chain_root_snapshot.epoch} exceeds lag bound"
        )
    if chain_root_snapshot.revoked:
        return False
    if snapshot.revoked:
        return False
    return True


def reconcile_gap_window(
    admissions: list[tuple[AdmissionRequest, StatusSnapshot]],
    revocations: dict[str, float],
) -> list[AdmissionRequest]:
    """Return admissions whose relied-upon epoch was superseded by a revocation prior to admission time."""
    suspect = []
    for req, snap in admissions:
        rev_time = revocations.get(req.credential_id)
        if rev_time is not None and rev_time < req.now and not snap.revoked:
            suspect.append(req)
    return suspect
```