# When must an agent runtime refuse to attest a tool-call DAG whose edges were reconstructed from post-hoc logs?

**Date of Record:** 2026 November 5

**Scope:** Applies to agent runtimes that emit cryptographically attested execution traces (signed DAGs of tool calls, model invocations, and data dependencies) where the DAG topology is derived, in whole or in part, from runtime logs rather than from inline causal propagation. Does not apply to runtimes that thread an explicit parent-span identifier through every call boundary and sign the DAG at emission time.

## Core Distinction

An attested trace makes two separable claims: *integrity* (this byte string was produced by key K and has not been mutated) and *causality* (call B consumed the output of call A). Cryptographic signing trivially guarantees the first. The second is a property of the *graph construction procedure*, not of the signature. The non-obvious failure is that a runtime can produce a perfectly valid signature over a DAG whose edges are wrong—because edges were inferred from timestamps, log ordering, or output-content matching after the fact. The signature then launders a fabricated causal claim into a verifiable one. A verifier checking only the signature will accept a trace that asserts A→B when B in fact read stale or unrelated state.

## What Was Observed

In a runtime that reconstructed edges by matching tool outputs to subsequent tool inputs (content-addressed join on output hashes), two failure modes appeared:

1. **Coincidental content joins.** Two tools that both emit `{"status": "ok", "count": 0}` produced an identical output hash. The reconstructor drew an edge from tool A to tool B because B's logged input contained that hash. No data actually flowed; the edge was an artifact of low-entropy outputs. The signed DAG claimed a dependency that did not exist, inflating the apparent causal chain and misattributing downstream effects to A.
2. **Timestamp-collision reordering.** Under concurrent tool execution, two calls logged within the same clock tick were ordered by log-write sequence, not by happens-before. The reconstructor serialized them A→B. The signature was valid; the order was false. A downstream auditor replaying the trace to reproduce a side effect got a different result than the original run.

Both traces verified. Both were wrong. The attestation layer had no mechanism to distinguish "edge asserted from inline propagation" from "edge inferred from a heuristic join."

## Condition of Validity

An edge in an attested DAG is only trustworthy if it was established at the moment of the call, by the callee receiving a token (parent span id, capability handle, or nonce) that the caller minted, and that token is included in the signed payload. The validity condition is: *every edge must be backed by a signed parent-pointer that the child could not have obtained except by being invoked by that parent.* Content-hash joins and timestamp orderings satisfy integrity but not causality and must be marked as *inferred*, not *asserted*, in the signed structure. If the runtime cannot distinguish asserted from inferred edges at signing time, it must not sign the DAG as a causal trace at all.

## Decision Boundary

The runtime must refuse to attest when: (a) any edge lacks an inline parent-pointer, and (b) the reconstruction heuristic that supplied the edge cannot prove uniqueness—i.e., the join key (output hash, timestamp, sequence number) is shared by more than one candidate. Uniqueness of the join key is the discriminator. A content hash that matches exactly one prior output may be promoted to an inferred edge with a confidence annotation; a hash matching two or more candidates, or a timestamp shared across concurrent spans, must cause attestation to fail closed rather than emit a signed guess. The boundary is not "did we reconstruct an edge" but "was the reconstruction unambiguous."

## Operational Effect

Failing closed converts a silent integrity-laundering bug into a loud, attributable refusal. Downstream verifiers can then trust that any signed edge marked *asserted* reflects real data flow, and treat *inferred* edges as advisory. The cost is that runtimes with weak instrumentation will refuse to attest many legitimate traces; the correct remedy is to strengthen inline propagation (mint a nonce per call, require the callee to echo it), not to relax the refusal. Traces that fail the uniqueness test should be quarantined with the colliding candidates recorded, so the instrumentation gap is visible rather than absorbed into a plausible-looking graph.

```python
import hashlib
from dataclasses import dataclass, field


class AmbiguousAttestationError(RuntimeError):
    """Raised when a tool-call DAG cannot be causally attested."""


@dataclass
class Span:
    span_id: str
    tool: str
    output_hash: str
    parent_pointer: str | None = None  # inline, minted by caller
    timestamp: int = 0


@dataclass
class Edge:
    src: str
    dst: str
    kind: str  # "asserted" | "inferred"


def reconstruct_edges(spans: list[Span]) -> list[Edge]:
    edges: list[Edge] = []
    by_output: dict[str, list[str]] = {}
    by_time: dict[int, list[str]] = {}

    for s in spans:
        if s.parent_pointer is not None:
            edges.append(Edge(s.parent_pointer, s.span_id, "asserted"))
        else:
            by_output.setdefault(s.output_hash, []).append(s.span_id)
            by_time.setdefault(s.timestamp, []).append(s.span_id)

    # Only promote inferred edges when the join key is unique.
    for s in spans:
        if s.parent_pointer is not None:
            continue
        candidates = [sid for sid in by_output.get(s.output_hash, []) if sid != s.span_id]
        if len(candidates) == 1:
            edges.append(Edge(candidates[0], s.span_id, "inferred"))
        elif len(candidates) > 1:
            raise AmbiguousAttestationError(
                f"output hash {s.output_hash!r} for span {s.span_id} "
                f"matches {len(candidates)} candidates {candidates}; "
                f"cannot attest causal edge"
            )
        concurrent = [sid for sid in by_time.get(s.timestamp, []) if sid != s.span_id]
        if len(concurrent) >= 1 and s.parent_pointer is None:
            raise AmbiguousAttestationError(
                f"span {s.span_id} shares tick {s.timestamp} with {concurrent}; "
                f"ordering is not happens-before"
            )
    return edges


def attest(spans: list[Span], signing_key: bytes) -> dict:
    edges = reconstruct_edges(spans)  # may raise AmbiguousAttestationError
    payload = ";".join(f"{e.src}->{e.dst}:{e.kind}" for e in sorted(edges, key=lambda e: (e.src, e.dst)))
    digest = hashlib.sha256(signing_key + payload.encode()).hexdigest()
    return {"edges": edges, "digest": digest, "asserted_only": all(e.kind == "asserted" for e in edges)}
```