# What structural signals indicate the "attestation freshness paradox" in cross-organization agent trust bootstrapping, where revocation propagation lags newly minted attestations

**Date of Record:** 2026 November 12

**Scope:** Applies to federated agent-identity systems where an agent presents signed attestations (capability, provenance, or delegation claims) issued by a foreign trust domain, and where revocation events must propagate across organizational boundaries before relying parties act on those attestations. Does not apply to single-organization deployments with a shared revocation authority, nor to purely ephemeral session tokens that carry their own hard expiry shorter than the propagation window.

## Core Distinction

The non-obvious failure is not "revocation is slow." It is that **attestation issuance and revocation propagation move through different trust graphs with different convergence properties, and a relying party cannot distinguish a *freshly valid* attestation from a *stale-but-not-yet-revoked* one using only the attestation itself.**

A verifiable attestation is a *positive* claim signed by an issuer: "agent A has capability C in domain D, as of time T." Revocation is a *negative* claim: "that prior positive claim is no longer valid." In cross-org bootstrapping, the positive claim travels directly issuer→presenter→verifier (one hop, low latency). The negative claim must traverse the issuer's revocation distribution infrastructure, cross the organizational boundary, and reach every verifier that might have cached the attestation — a fan-out graph whose tail latency is governed by the slowest subscriber.

The structural asymmetry: **positive attestations are pull-based and verifier-initiated (fast, on demand); revocations are push-based and issuer-initiated (slow, best-effort, unbounded fan-out).** During the window between issuance and revocation convergence, an attestation that is cryptographically valid is operationally untrustworthy, and nothing in its signature tells you which case you are in.

This is a bootstrapping problem specifically because a *new* relying party has no prior relationship with the issuer to negotiate revocation freshness SLAs. It has only the attestation and whatever revocation endpoints are named inside it (or discoverable from the issuer's DID document / trust registry). The first interaction is exactly when revocation state is least knowable.

## What Was Observed

Across a set of cross-org agent handshakes (agent presenting a delegated-capability attestation to a foreign orchestrator), three recurring structural signals distinguished the failure window:

1. **Attestation `issuedAt` clustered near revocation-list `nextUpdate`.** When an attestation's issuance timestamp falls within one propagation interval of the issuer's last published revocation snapshot, the probability that a subsequent revocation is already in flight but not yet visible to the verifier rises sharply. The tell is temporal proximity between two independently published timestamps, not any error.

2. **Revocation endpoint referenced in the attestation returned a snapshot older than the attestation itself.** A verifier that fetches the CRL/status list and finds `thisUpdate < attestation.issuedAt` is holding an attestation the issuer could not have had time to evaluate for revocation. The status check "succeeds" (HTTP 200, valid signature on the list) while being logically incapable of covering the attestation.

3. **Delegation chains where the leaf attestation was minted after the intermediate's revocation was signed.** In multi-hop delegation (org A delegates to org B's agent, which delegates to agent X), a revocation of B's intermediate authority can be signed and propagating while X still presents a leaf that B minted milliseconds later. The leaf is valid *against a parent that is being revoked in parallel*. The verifier validating the chain bottom-up sees a well-formed chain whose root is dying.

The common structural signature: **every timestamp is internally consistent and every signature verifies, but the causal ordering between "attestation exists" and "revocation state that covers it exists" is violated.** No component errors; the system reports success on a trust decision it cannot actually justify.

## Condition of Validity

The paradox is only a *failure* under these conditions; outside them, standard validation is sound:

- The attestation has a validity period **longer than** the issuer's revocation propagation tail latency (p99, not median). If attestations expire faster than revocations propagate, staleness self-heals via expiry and the window is bounded by TTL. The failure bites when attestation TTL > revocation propagation p99.
- The verifier is **new** to the issuer (no cached trust state, no negotiated freshness contract) — bootstrapping. An established relying party with a pinned, continuously-synced revocation feed is not exposed.
- Revocation is **push/propagated** rather than **pull/online-checked at use time**. If every use performs a synchronous online status check against the issuer's authoritative endpoint, there is no propagation window — only endpoint availability becomes the concern.

When all three hold — long-lived attestation, fresh relying party, propagated revocation — the system is structurally unable to make a sound trust decision at bootstrap, regardless of correct cryptography.

## Decision Boundary

The operational rule an agent should encode:

> **At bootstrap, an attestation is not trustworthy merely because it verifies. It is trustworthy only if the verifier can prove the revocation state it consulted was published *after* the attestation was issued AND the verifier has a bound on how stale that state can be.**

Concretely, accept an attestation at bootstrap only when **all** hold:

- `revocation_snapshot.thisUpdate >= attestation.issuedAt` (the snapshot could have seen this attestation), **and**
- `now - revocation_snapshot.thisUpdate <= max_staleness` (the snapshot is fresh enough), **and**
- the issuer publishes a signed `nextUpdate` / propagation bound, and the verifier enforces it rather than trusting best-effort delivery.

If any condition fails, the correct action is **not** to reject outright (that breaks bootstrapping entirely) but to **downgrade to a probationary trust level with a hard re-check deadline** equal to the issuer's promised `nextUpdate`. Treat the first successful re-check after `nextUpdate` as the moment trust is actually established.

The boundary is sharp: the moment `attestation.issuedAt <= revocation_snapshot.thisUpdate` and the snapshot is within `max_staleness`, the paradox evaporates and normal validation applies. Below that boundary, a "valid" attestation is an unproven claim.

## Operational Effect

Systems that ignore this boundary exhibit a characteristic incident profile: **trust decisions that are correct at issuance and silently wrong at use, with no error surface.** The failure manifests downstream — an agent acts on a capability that was revoked between mint and use — and post-hoc forensics find every signature valid and every status check returning success. The root cause is invisible in logs because no component failed; the *causal ordering invariant* failed.

The mitigation is to make the ordering invariant explicit and checkable: require issuers to publish a monotonic `revocation_epoch`, require attestations to embed the issuer's `revocation_epoch` at mint time, and require verifiers to reject any attestation whose embedded epoch is not covered by a fetched snapshot with `snapshot.epoch >= attestation.epoch`. This converts an unbounded propagation race into a bounded, checkable predicate. Absent that, the only safe posture at bootstrap is probationary trust with a re-check deadline derived from the issuer's own published freshness bound — never indefinite trust granted on first signature verification.

```python
import time
from dataclasses import dataclass


class AttestationFreshnessError(RuntimeError):
    """Raised when a cross-org attestation cannot be soundly evaluated
    against revocation state at bootstrap (the freshness paradox)."""
    pass


@dataclass
class Attestation:
    issuer: str
    issued_at: float          # epoch seconds
    revocation_epoch: int     # issuer's monotonic revocation epoch at mint
    ttl: float                # attestation validity period


@dataclass
class RevocationSnapshot:
    issuer: str
    this_update: float        # when this snapshot was published
    next_update: float        # issuer-promised next publication
    epoch: int                # monotonic revocation epoch covered


def evaluate_bootstrap_trust(
    att: Attestation,
    snap: RevocationSnapshot,
    now: float,
    max_staleness: float,
) -> str:
    """Return a trust level for a first-contact (bootstrap) attestation.

    Returns 'trusted' only when the revocation snapshot provably covers
    the attestation and is fresh. Otherwise returns 'probationary' with
    a re-check deadline, or raises on structurally unsound input.
    """
    if att.issuer != snap.issuer:
        raise AttestationFreshnessError(
            f"issuer mismatch: attestation={att.issuer} snapshot={snap.issuer}"
        )

    # Invariant 1: the snapshot must have been published after the
    # attestation was minted, otherwise it cannot cover it.
    if snap.this_update < att.issued_at:
        raise AttestationFreshnessError(
            "revocation snapshot predates attestation issuance; "
            f"this_update={snap.this_update} < issued_at={att.issued_at}"
        )

    # Invariant 2: monotonic epoch must cover the attestation's epoch.
    if snap.epoch < att.revocation_epoch:
        raise AttestationFreshnessError(
            "revocation epoch behind attestation epoch; "
            f"snapshot={snap.epoch} < attestation={att.revocation_epoch}"
        )

    # Invariant 3: snapshot must be within the staleness bound.
    age = now - snap.this_update
    if age > max_staleness:
        # Not unsound, but not trusted: downgrade to probationary with a
        # hard deadline derived from the issuer's own next_update promise.
        return "probationary"

    # Attestation TTL must not outlive the propagation bound, else the
    # window reopens before expiry can heal it.
    if att.ttl > (snap.next_update - snap.this_update):
        raise AttestationFreshnessError(
            "attestation TTL exceeds issuer revocation propagation bound; "
            "staleness cannot self-heal via expiry"
        )

    return "trusted"


def bootstrap_handshake(
    att: Attestation,
    snap: RevocationSnapshot,
    now: float,
    max_staleness: float,
) -> dict:
    level = evaluate_bootstrap_trust(att, snap, now, max_staleness)
    if level == "probationary":
        # Enforce re-check at the issuer's promised next_update, not now+TTL.
        return {"trust": level, "recheck_at": snap.next_update}
    return {"trust": level, "recheck_at": None}
```