# Why does an instance of cross-org agent federation fail to bootstrap trust when both parties hold valid verifiable credentials

**Date of Record:** 2026 November 11

**Scope:** Applies to federated agent-to-agent trust establishment where each organization issues W3C Verifiable Credentials (VCs) under its own DID, and policy is exchanged as signed JSON (e.g., a policy VC or signed policy document). Does not apply to single-issuer PKI with a shared trust root, nor to symmetric pre-shared-key federation.

## Core Distinction

A **credential that verifies** is not the same as a **credential that authorizes this peer to speak for its org in this context**. Verification answers "did the holder's key sign this, and is the issuer's DID document resolvable?" Bootstrapping answers "am I willing to treat this issuer as an authority for *this* class of claims, *right now*, for *this* counterparty?" The failure mode lives in the gap: both sides can complete cryptographic verification of each other's credentials and policy documents, report `verified: true`, and still have no trust anchor, because neither side has admitted the other's issuer DID into its authority set. The handshake deadlocks at `verified: true, trusted: false` on both sides.

## What Was Observed

Two orgs, A and B, each run an agent gateway that (1) presents a VC binding its agent DID to its org DID, (2) presents a signed policy document declaring which counterparty org DIDs it will accept, and (3) requires the peer to do the same. In the failing case:

- A resolves B's DID document, validates B's VC signature, and confirms the policy signature. Result: `verified: true`.
- B does the same for A. Result: `verified: true`.
- A's policy admits org DIDs in `{A, C}`. B's org DID is not in it. B's policy admits `{B, D}`. A is not in it.
- Each side, correctly, refuses to *grant* the peer authority. Neither emits a rejection that names the cause; both emit a generic `peer_not_trusted` and wait for the peer to "prove" itself.
- No retry, renegotiation, or policy re-fetch changes the outcome. The system is in a stable, symmetric refusal.

The non-obvious part: the gateways reported `verified: true` in health/telemetry, so operators saw "credentials valid" and "federation healthy at the crypto layer," while the actual trust graph had zero edges. Monitoring on verification success was green; federation was 0% functional.

## Condition of Validity

The deadlock is guaranteed (not merely possible) whenever **both** of the following hold:

1. **Mutual admission is required before either side grants.** Each gateway's policy check for "grant peer authority" requires the peer's org DID to already be in a local allow-list that is populated only by an explicit operator action or by a prior successful federation.
2. **The allow-list is not derivable from the peer's presented material.** The peer's policy document declares *whom it will accept*; it does not declare *that it is acceptable to me*. There is no field in either VC or policy that, when verified, causes the other side's allow-list to gain an entry.

When the first condition is *not* met (one side auto-admits on valid VC + matching policy), bootstrap succeeds one-directionally and the other side can then admit. When the second condition is *not* met (an out-of-band trust root, shared registry, or transitive authority exists), the allow-list is populated by other means and the deadlock does not occur. The failure is specific to **symmetric, self-contained, allow-list-gated** federation with no external trust root.

## Decision Boundary

Distinguish two states that telemetry conflates:

- **`verified`** — signatures check out, issuers resolve, policy documents are well-formed and signed. This is a *cryptographic* predicate. It is cheap, local, and symmetric.
- **`admitted`** — the local authority set contains the peer's org DID for the relevant claim class. This is a *policy* predicate. It is asymmetric and requires an explicit grant.

The operational rule: **never treat `verified` as a proxy for `admitted`, and never let a bootstrap loop terminate on `verified`.** A federation attempt that ends with `verified: true, admitted: false` on both sides is a *hard* failure requiring an out-of-band grant, not a transient one. Conversely, a single-sided `admitted: true` is a recoverable state: the admitted side can emit a signed "I admit you" assertion that the other side, having verified it, uses to populate its own allow-list. This asymmetry is the only self-healing path and must be designed in; it does not emerge on its own.

## Operational Effect

Systems that miss this boundary exhibit: green crypto-layer health checks with zero successful federations; identical generic errors on both sides that point operators at the wrong layer; retry storms that never converge because no amount of re-verification changes an allow-list; and, after a human adds one side's DID manually, a sudden "spontaneous" recovery that misleads postmortems into blaming the crypto layer. The fix is to make `admitted` a first-class, observable state distinct from `verified`, to emit a typed error naming the missing admission, and to provide an explicit one-directional admission-assertion path so a single operator action (or a single pre-seeded trust root) unblocks both sides.

```python
class FederationBootstrapError(RuntimeError):
    """Raised when mutual admission cannot be established despite valid credentials."""


def establish_federation(local_policy, peer_material, peer_policy):
    # Step 1: cryptographic verification (symmetric, cheap, local).
    if not verify_vc(peer_material.vc):
        raise FederationBootstrapError("peer VC failed signature/issuer verification")
    if not verify_signed_policy(peer_policy):
        raise FederationBootstrapError("peer policy failed signature verification")

    peer_org = peer_material.vc.credential_subject["org_did"]

    # Step 2: policy admission (asymmetric, requires explicit grant).
    if peer_org not in local_policy.admitted_org_dids:
        # Verified but not admitted: this is the deadlock boundary.
        # Do NOT retry. Require an out-of-band grant or an inbound
        # admission-assertion from the peer before proceeding.
        raise FederationBootstrapError(
            f"peer org {peer_org} verified but not admitted; "
            f"mutual allow-list gating will deadlock. "
            f"verified=True admitted=False"
        )

    # Step 3: only now may we grant authority and emit our own
    # admission-assertion so the peer can populate its allow-list.
    return grant_authority(peer_org)
```