# What structural signals indicate an audit-chain fork in federated agent traces (and why hash-link continuity is not sufficient evidence of linearity)

**Date of Record:** 2026 November 12
**Scope:** Applies to federated agent audit systems where each domain emits a tamper-evident hash chain (per-domain append-only log with prev-hash linkage) and a separate correlation layer stitches cross-domain traces via trace/span identifiers. Does not apply to single-domain logging, to systems using a global consensus log with total ordering, or to correlation schemes that carry the full predecessor hash across domain boundaries.

## Core Distinction

There are two distinct integrity properties that operators routinely conflate:

1. **Chain integrity** — each domain's log is internally consistent: every record's `prev_hash` matches the hash of its immediate predecessor *within that domain*, and the domain's signed head is monotonic.
2. **Trace linearity** — the cross-domain causal sequence for a given `trace_id` is a single, non-branching path through the federation.

A fork in the *audit chain* (two divergent successors to the same record) is a different failure than a fork in the *trace* (two domains both claiming to be the causal successor of the same cross-domain span). Hash-link continuity verifies (1) and says nothing about (2). The non-obvious boundary is this: **a federated audit trail can pass every per-domain integrity check while the correlated trace is forked, reordered, or causally impossible.** Per-domain verification is a local invariant; trace linearity is a global one, and the global one is not implied by the local ones.

## What Was Observed

In a three-domain federation (domains `A`, `B`, `C`; agent runtime in `A`, tool-execution gateway in `B`, policy/approval service in `C`), a replay of a partially failed run produced the following:

- All three domain logs verified cleanly: `prev_hash` linkage intact, signed heads monotonic, no gaps in sequence numbers.
- The correlation layer reported a single `trace_id` with **two spans at the same causal position**: both `B:tool.invoke` and `C:policy.approve` carried `parent_span = A:agent.step#7` and identical `causal_epoch`, but neither was an ancestor of the other.
- The agent's own emitted reasoning trace (`A`) showed a single linear narrative: "requested approval, received approval, invoked tool." The federation's correlated view showed the tool invocation and the approval as siblings.

Root cause: the agent runtime in `A` retried `A:agent.step#7` after a timeout. The retry reused the same `trace_id` and the same `parent_span`, but the *first* attempt had already caused `B` to invoke the tool, while the *retry* went down the approval path in `C` first. Both domain logs are individually correct; the retry created a second successor to the same span in the correlation graph. The hash chains never forked because each domain only saw one of the two branches.

The structural signal that flagged it was **not** a hash mismatch. It was a **causal-epoch collision**: two spans sharing a `(trace_id, parent_span, causal_epoch)` tuple where the correlation contract requires exactly one. This is detectable only by a cross-domain join, never by per-domain verification.

## Condition of Validity

The distinction holds — and the failure is real — only under these conditions:

- **Correlation identifiers are propagated, not derived.** If downstream domains derive their parent linkage from the received `trace_id`/`span_id` (as in W3C-style context propagation), a retry at the origin re-uses identifiers and produces the fork. If instead each hop appends a fresh nonce and the parent linkage is content-addressed over the *request payload hash*, the fork becomes visible as two distinct payload hashes under one span and is caught at emission time.
- **`causal_epoch` (or an equivalent monotonic attempt counter) is part of the propagated context.** Without an attempt counter, retries are indistinguishable from genuine concurrency, and the fork is silently absorbed as legitimate fan-out.
- **At least one domain observes both branches.** If the two branches never touch a common domain, no domain-local check can ever see the fork; only the correlation layer (or an auditor performing a full cross-domain join) can.

Where the correlation layer is *also* the only writer of the trace graph and it enforces single-parent-per-epoch at write time, the failure is prevented rather than detected, and this record's detection guidance does not apply.

## Decision Boundary

Use the following boundary to decide whether a clean per-domain verification result is admissible as evidence of a sound trace:

- **Admit per-domain verification as sufficient** only when the correlation contract guarantees (a) attempt-scoped identifiers (retries get new `span_id`s), and (b) the correlation layer rejects duplicate `(trace_id, parent_span, causal_epoch)` tuples at ingest. Under both guarantees, local integrity plus the ingest rejection implies linearity.
- **Do not admit it** when identifiers are retry-stable and the correlation layer is a passive indexer. In that case you must run an explicit **fork query**: group by `(trace_id, parent_span, causal_epoch)` and assert cardinality ≤ 1; any group with cardinality ≥ 2 is a trace fork and must be escalated even though every hash chain verified.
- **Escalate to a hard failure** (not a warning) when a fork is detected *and* the two branches carry divergent tool-invocation records, because the audit trail can no longer establish which side effect actually occurred first. At that point the correct posture is "audit trail is non-authoritative for this trace," not "audit trail is corrupt."

The trap is treating "all chains verify" as a green light. It is a green light for *tamper evidence*, not for *causal ordering*.

## Operational Effect

Once the fork query was added as a mandatory post-verification gate, the observed effects were:

- Retry-induced forks surfaced as first-class audit findings rather than being silently normalized into legitimate fan-out. In the replay above, the fork was caught at the correlation layer within one ingest cycle instead of being discovered weeks later during an incident review.
- The team stopped reporting "audit integrity: OK" as a single boolean and split it into `chain_integrity` and `trace_linearity`, because the two can disagree and the disagreement is itself the signal.
- Downstream consumers (compliance export, incident reconstruction) were gated on `trace_linearity`, since a forked trace cannot answer "which side effect happened first" and must be marked non-authoritative rather than exported as fact.

The durable lesson: in federated tamper-evident logging, **the absence of a hash break is evidence about each domain in isolation and is structurally silent about the cross-domain causal graph.** Linearity is a separate invariant that requires a separate check, and retry-stable correlation identifiers are the specific mechanism that lets a fork hide behind clean chains.

```python
from __future__ import annotations

from collections import defaultdict
from dataclasses import dataclass


class TraceForkError(RuntimeError):
    """Raised when a federated trace has >1 successor at the same causal epoch."""


@dataclass(frozen=True)
class Span:
    trace_id: str
    span_id: str
    parent_span: str | None
    causal_epoch: int
    domain: str
    payload_hash: str


def assert_trace_linearity(spans: list[Span]) -> None:
    """Reject forks even when every per-domain hash chain verified cleanly.

    A fork is two or more spans sharing (trace_id, parent_span, causal_epoch).
    Per-domain chain integrity cannot observe this; only this cross-domain
    join can.
    """
    by_parent: dict[tuple[str, str | None, int], list[Span]] = defaultdict(list)
    for s in spans:
        by_parent[(s.trace_id, s.parent_span, s.causal_epoch)].append(s)

    for key, group in by_parent.items():
        if len(group) < 2:
            continue
        trace_id, parent_span, epoch = key
        domains = sorted({s.domain for s in group})
        hashes = sorted({s.payload_hash for s in group})
        # Divergent payloads across the fork mean side-effect ordering is
        # unrecoverable from the audit trail -> hard failure, not a warning.
        if len(hashes) > 1:
            raise TraceForkError(
                f"trace fork with divergent side effects: trace={trace_id} "
                f"parent={parent_span} epoch={epoch} domains={domains} "
                f"payload_hashes={hashes}; audit trail is non-authoritative "
                f"for this trace"
            )
        raise TraceForkError(
            f"trace fork (identical payloads, still non-linear): trace={trace_id} "
            f"parent={parent_span} epoch={epoch} domains={domains}"
        )
```