# Which invariants prevent trust-broker replay in cross-organization multi-agent federation

**Date of Record:** 2026 November 13
**Scope:** Applies to federations where an agent in org A obtains a capability for an agent in org C via a trust broker in org B, and where the broker mints or attests assertions (tokens, vouchers, signed claims) rather than merely routing. Does not apply to pure discovery/lookup brokers that never issue attestations, nor to single-org delegation chains where a single trust root controls the whole path.

## Core Distinction

A federation broker has two structurally different jobs that are frequently conflated in implementation: **identity resolution** (mapping a subject in one namespace to a subject in another) and **authority attestation** (asserting that a subject may act, with what scope, for how long). Replay-safety invariants belong to the second job, but are usually enforced against data structures produced by the first.

The non-obvious boundary is this: a broker that is *idempotent as a resolver* is not thereby *idempotent as an attestor*. Resolving `alice@orgA` to `principal:7f3a` twice is harmless; attesting "principal 7f3a may invoke `payments.settle` for 300s" twice is not, because the second attestation may be consumed by a different relying party than the first. The invariant that actually holds the system together is not "tokens are single-use" (too strong for federation, where one attestation legitimately fans out to several downstream agents) but **the binding of an attestation to a specific (issuer, subject, audience, delegation-depth) tuple that cannot be re-presented under any other tuple**.

## What Was Observed

During a two-broker federation drill (org A broker `ta.example`, org C broker `tc.example`, mutual trust via a shared root), a replayed assertion was accepted for 41 seconds after its nominal consumption. The sequence:

1. Agent `a1` in org A requests delegation to org C for scope `read:catalog`.
2. Broker B mints assertion `X` with claims `{iss: ta, sub: a1, aud: tc, scope: read:catalog, exp: T+300, jti: j1}`.
3. `a1` presents `X` to `tc`; `tc` validates, records `j1` in a consumed-set with TTL 300s, issues downstream credential `Y` to `a1`.
4. `a1` forwards `Y` to a peer agent `a2` in org A (allowed by federation policy: agents may re-delegate one hop).
5. `a2` presents `Y` to `tc`. `tc` validates `Y`, but its replay check keys on `jti` of `X`, not `Y` — `Y` carries a fresh `jti: j2`. The consumed-set does not cover `Y`.
6. `a2` obtains a second downstream credential for the same scope. The fan-out was not intended: policy permitted one downstream agent per upstream assertion.

The failure was not a broken signature, a clock skew, or a missing TTL. Every cryptographic check passed. The failure was that the replay invariant was keyed on the *token identifier* rather than on the *delegation edge* `(issuer, subject, audience, parent_jti)`. A fresh `jti` on a child credential is correct behavior (it makes the child individually revocable) but it silently escapes a consumed-set keyed on parent identifiers.

## Condition of Validity

The invariant below holds **only** when all of the following are true:

- The broker is the sole minting authority on the delegation edge; relying parties do not mint sibling attestations for the same edge.
- Delegation depth is bounded and declared in the assertion (`delegation_depth` claim), and each relying party enforces the bound against the *presented* depth, not a locally cached one.
- The consumed-set is keyed on the full edge tuple, not on any single claim, and its TTL is at least the maximum of (assertion `exp`, downstream credential `exp`) so that a child cannot outlive the parent's replay window.
- Clocks across orgs are within the assertion's `nbf`/`exp` skew tolerance; a broker that accepts unbounded skew converts the replay window into an unbounded window.

Where any of these is false — notably in federations that permit relying parties to mint sibling attestations, or that allow depth to be inferred rather than declared — the invariant degrades and the system should fall back to strict single-use on the parent `jti`, accepting the fan-out cost.

## Decision Boundary

The operative question at each relying party is not "have I seen this token?" but "have I seen this **edge**?" The boundary is:

- If the presented assertion's `parent_jti` is absent (root attestation), enforce single-use on `jti`.
- If `parent_jti` is present, enforce single-use on `(iss, sub, aud, parent_jti, delegation_depth)` and additionally verify that the parent is itself in the consumed-set — i.e., a child is only admissible if its parent was admitted, and the edge is only consumable once.
- If `delegation_depth` exceeds the policy bound for the audience, reject before touching the consumed-set (rejection must not consume, or a malicious replayer can burn a legitimate edge).

The subtlety that bites: step 2's "parent is in the consumed-set" check must be against the *parent's edge key*, not the parent's `jti`, or the same escape recurses one level up.

## Operational Effect

After keying the consumed-set on the edge tuple and adding the parent-admission check, the drill's step 5 was rejected with a distinct error class (`DelegationEdgeReplay`), distinguishable from signature failure and from depth-violation. This distinction matters operationally: edge-replay is a *policy* signal (someone is fanning out), while signature failure is a *compromise* signal. Collapsing them into one error destroys the ability to alert correctly. The 41-second window closed to zero in the drill; the cost was an additional index on the consumed-set and a requirement that every relying party record the parent edge at admission time, which increased write amplification on the broker by roughly 1.8× under the drill's load. That cost is the price of the invariant and should be budgeted, not discovered.

```python
from dataclasses import dataclass
from typing import Optional


class DelegationEdgeReplay(RuntimeError):
    """Raised when a delegation edge is presented more than once."""
    pass


class DepthViolation(RuntimeError):
    """Raised when delegation depth exceeds policy before replay check."""
    pass


@dataclass(frozen=True)
class EdgeKey:
    iss: str
    sub: str
    aud: str
    parent_jti: Optional[str]
    depth: int


def admit_assertion(assertion: dict, consumed: set, max_depth: int) -> EdgeKey:
    depth = assertion.get("delegation_depth", 0)
    if depth > max_depth:
        # Reject before consuming: a rejected edge must not burn the slot.
        raise DepthViolation(
            f"depth {depth} exceeds policy {max_depth} for {assertion.get('aud')}"
        )

    parent = assertion.get("parent_jti")
    key = EdgeKey(
        iss=assertion["iss"],
        sub=assertion["sub"],
        aud=assertion["aud"],
        parent_jti=parent,
        depth=depth,
    )

    # A child is admissible only if its parent edge was itself admitted.
    if parent is not None:
        parent_key = EdgeKey(
            iss=assertion["iss"],
            sub=assertion["sub"],
            aud=assertion["aud"],
            parent_jti=None,
            depth=depth - 1,
        )
        if parent_key not in consumed:
            raise DelegationEdgeReplay(
                f"parent edge for jti={parent} was never admitted"
            )

    if key in consumed:
        raise DelegationEdgeReplay(
            f"edge replay: {key} already consumed"
        )

    consumed.add(key)
    return key
```