# When must an instance refuse a federated trust-anchor update: the epoch-skew signature-replay boundary

**Date of Record:** 2026 November 14

**Scope:** Applies to cross-organization multi-agent federations where peer agents exchange signed trust-anchor documents (root keys, delegation certificates, revocation lists) and cache them locally to authenticate inbound task envelopes. Does not apply to single-organization meshes with a shared control plane, nor to federations where every envelope carries a fresh, verifiable nonce from a mutually trusted time authority.

## Core Distinction

The boundary is not "is this anchor document's signature valid?" It is "was this anchor document, though validly signed, *issued against a superset or successor of the local trust epoch that the receiving instance has not yet observed?*"

A trust-anchor document is signed by the issuing organization's root key, and it carries an `epoch` counter plus a `prev_root_digest` field. A naive receiver validates the signature against the anchor it currently holds and accepts. That is correct for a monotonic, single-writer chain. In a federation, two things break monotonicity: (a) an organization may rotate its root and *re-issue* the same logical anchor under a new epoch while old peers still hold the prior epoch; and (b) a compromised or merely buggy peer can replay a *previously valid* anchor document that was signed under an epoch the receiver has since advanced past. The signature check passes in both cases. The invariant that must hold is **epoch monotonicity per issuer identity**, not signature validity.

## What Was Observed

During a three-organization federation exercise (call them A, B, C), B rotated its root key at epoch 41. C, which had been partitioned for ~90 seconds, still held B's epoch 40 anchor. When the partition healed, C received a task envelope from B carrying an anchor document signed under epoch 41 with `prev_root_digest` pointing at the epoch-40 root. C's validator accepted it — signature valid, digest chain matched its cached epoch-40 root. Correct.

The failure appeared on a *different* code path. A separate agent instance on C's side, serving a long-lived batch job, had cached B's epoch-41 anchor earlier. It then received, from a lagging B replica, a replayed epoch-40 anchor document — the *old* one, still validly signed by the (now-retired) epoch-40 root, with `prev_root_digest` pointing at epoch 39. The validator checked the signature against the *cached epoch-41 root*, which did not match, and correctly rejected. But a third instance, which had never cached epoch 41 and held only epoch 39, accepted the epoch-40 document as a forward update — because from *its* perspective, epoch 40 > epoch 39 and the chain was intact. It then used the retired epoch-40 root to authenticate envelopes that B had since re-signed under epoch 41, and silently dropped them as signature failures. No error surfaced; the batch job simply stalled with 100% envelope rejection and no diagnostic beyond "signature mismatch."

The non-obvious part: **the receiver's decision is a function of its local epoch, and a validly signed document can be either forward-advancing or a replay depending on that local epoch.** A receiver at epoch 39 must accept epoch 40; a receiver at epoch 41 must reject epoch 40 as a replay. There is no receiver-independent answer.

## Condition of Validity

The epoch-monotonicity invariant holds only when all of the following are true:

1. Each issuer identity has exactly one signing chain, and epoch numbers are strictly increasing across that chain with no gaps that the receiver can observe out of order.
2. `prev_root_digest` is checked against the receiver's *cached* root, not against the digest embedded in the incoming document (which is trivially self-consistent).
3. The receiver tracks, per issuer, the highest epoch it has ever *accepted*, and persists that watermark durably across restarts. An in-memory watermark resets on process restart and reopens the replay window.
4. Clock skew between organizations is bounded below the epoch rotation interval. If B rotates every 60s and C's clock drifts 90s, C can observe epoch 41 before B has finished propagating it to A, and A's epoch-40 document arrives at C as a "replay" that is actually the current truth for A.

Condition 4 is the one most often violated in practice and the one that makes the boundary genuinely non-obvious: **the invariant is sound only under a bounded-skew assumption that the federation protocol usually does not enforce.**

## Decision Boundary

The operational rule for an agent instance:

- If `incoming.epoch > local_watermark[issuer]` **and** `incoming.prev_root_digest == local_root_digest[issuer]` **and** `incoming.epoch - local_watermark[issuer] == 1`: accept, advance watermark, persist.
- If `incoming.epoch > local_watermark[issuer]` but the gap is `> 1`: **do not accept and do not reject silently.** This is the ambiguous zone — the receiver has missed intermediate rotations and cannot verify the chain. Enter a `reconcile` state: fetch the full chain from the issuer, or from a quorum of peers, before proceeding. Treat envelopes under the stale root as *deferred*, not dropped.
- If `incoming.epoch <= local_watermark[issuer]`: reject as replay/stale. Log the issuer, both epochs, and the source peer. Do not advance.
- If `incoming.epoch > local_watermark[issuer]` and `prev_root_digest != local_root_digest[issuer]`: this is a fork or a forged chain. Halt federation with that issuer and escalate; do not pick a branch.

The subtle case is the `gap > 1` branch: naive implementations fold it into either "accept" (unsafe — accepts an unverifiable chain) or "reject" (unsafe — silently drops the legitimate current anchor and stalls the job, exactly as observed). Neither is correct. The correct action is a third state that neither accepts nor discards.

## Operational Effect

After this was diagnosed, the federation was changed in three ways. First, the per-issuer watermark was made durable (written to the same WAL as the anchor cache, fsynced before acknowledgment). Second, the `gap > 1` branch was implemented as an explicit `TrustReconcilePending` state with a bounded fetch deadline; envelopes arriving during reconcile are queued, not dropped. Third, the epoch rotation interval was raised to 10× the maximum observed inter-org clock skew, and skew was made a monitored metric with a hard federation-wide alarm.

The residual risk: a receiver that has *never* held any anchor for an issuer (cold start) cannot apply the watermark rule and must bootstrap from a configured trust anchor out of band. That path is outside this invariant and must be handled by a separate provisioning mechanism — do not attempt to bootstrap from an inbound envelope, because the first envelope is exactly where a replay attack lands.

```python
import time
from dataclasses import dataclass, field
from typing import Dict, Optional


class TrustEpochViolation(RuntimeError):
    """Raised when a federated trust-anchor document cannot be placed
    on the receiver's per-issuer epoch chain without ambiguity."""


@dataclass
class AnchorDoc:
    issuer: str
    epoch: int
    prev_root_digest: str
    root_digest: str
    signature: bytes
    issued_at: float


@dataclass
class IssuerState:
    watermark: int = 0
    root_digest: Optional[str] = None
    reconcile_pending: bool = False
    reconcile_deadline: float = 0.0


class FederationTrustStore:
    def __init__(self, skew_bound_s: float = 30.0) -> None:
        self._state: Dict[str, IssuerState] = {}
        self._skew_bound = skew_bound_s

    def _get(self, issuer: str) -> IssuerState:
        if issuer not in self._state:
            # Cold start: no watermark. Caller must have provisioned out of band.
            raise TrustEpochViolation(
                f"no provisioned trust anchor for issuer {issuer!r}; "
                "cannot bootstrap from an inbound document"
            )
        return self._state[issuer]

    def evaluate(self, doc: AnchorDoc, now: Optional[float] = None) -> str:
        now = time.time() if now is None else now
        st = self._get(doc.issuer)

        if now - doc.issued_at > self._skew_bound:
            # Document too old to be trusted as current; could be a slow replay.
            raise TrustEpochViolation(
                f"anchor for {doc.issuer!r} epoch {doc.epoch} is "
                f"{now - doc.issued_at:.1f}s old, exceeds skew bound "
                f"{self._skew_bound}s"
            )

        if doc.epoch <= st.watermark:
            return "reject_replay"

        if doc.prev_root_digest != st.root_digest:
            # Fork or forged chain: never pick a branch silently.
            raise TrustEpochViolation(
                f"chain fork for {doc.issuer!r}: incoming prev_root "
                f"{doc.prev_root_digest!r} != cached root {st.root_digest!r} "
                f"at watermark {st.watermark}"
            )

        gap = doc.epoch - st.watermark
        if gap == 1:
            st.watermark = doc.epoch
            st.root_digest = doc.root_digest
            st.reconcile_pending = False
            return "accept"

        # gap > 1: ambiguous zone. Do NOT accept, do NOT silently drop.
        if not st.reconcile_pending:
            st.reconcile_pending = True
            st.reconcile_deadline = now + self._skew_bound
        elif now > st.reconcile_deadline:
            raise TrustEpochViolation(
                f"reconcile deadline exceeded for {doc.issuer!r}: "
                f"watermark {st.watermark}, incoming epoch {doc.epoch}, "
                f"cannot verify intermediate chain"
            )
        return "defer_reconcile"
```