# In what scenarios must an instance refuse to honor a cross-org action receipt signed under a rotated key whose chain of custody is not anchored in the counterparty's non-repudiation log

**Date of Record:** 2026 November 8

**Scope:** Applies to agent-to-agent action receipts exchanged between mutually distrusting organizations where non-repudiation depends on a signature over a canonical action digest plus a log inclusion proof. Does not apply to intra-org receipts, nor to receipts whose signature scheme is symmetric MACs (where non-repudiation is structurally impossible and must be handled by a separate trust-anchor protocol).

## Core Distinction

The failure mode is not "bad signature." It is **valid signature, unanchored provenance**. A receipt can carry a cryptographically valid signature from a key that the counterparty's non-repudiation log never attested as belonging to the signing principal *at the time of signing*. The signature verifies; the liability attribution does not. These are different invariants and conflating them is the source of most cross-org disputes.

A signature proves *some holder of key K signed digest D*. Non-repudiation requires the stronger claim: *principal P was the authorized holder of K at time T, and the log committed to that binding before T*. The second claim lives in the counterparty's append-only log, not in the receipt. A receipt whose key rotation is attested only by the counterparty's *current* key directory — rather than by a log inclusion proof against a signed tree head the verifier previously witnessed — is a receipt whose attribution can be retroactively rewritten by the counterparty. Honoring it transfers liability you cannot prove.

## What Was Observed

In a two-org agent pipeline (Org A issues action receipts for tool invocations; Org B consumes them for billing and for downstream liability), a rotation event at Org A produced receipts signed with key `K_{n+1}`. Org A's key directory served `K_{n+1}` as the current key for principal `agent-7`. Org B's verifier fetched the directory, verified the signature, and accepted. Six weeks later, during a dispute over a high-value action, Org A produced a log showing that `K_{n+1}` had been *revoked at issuance time* due to a suspected compromise, and that the action in question had actually been signed by `K_n` — the receipt Org B held was a re-signed artifact injected by the compromised key before rotation completed. Org B's receipt verified against a key that was, at signing time, already revoked; Org B had no inclusion proof pinning `K_{n+1}` to a pre-rotation tree head, so it could not demonstrate the state it observed. The dispute resolved against Org B by default because Org B could not establish *what it knew and when*.

The non-obvious part: the verifier behaved "correctly" by every local check. The failure was that the verifier's trust in the key directory was **unwitnessed and time-unanchored**. A directory read is a point-in-time observation with no proof of consistency, and a rotation is precisely the moment when point-in-time observations become unverifiable.

## Condition of Validity

A cross-org receipt is attributable — and therefore honorable — only when all of the following hold simultaneously:

1. The receipt's signature verifies against a key `K`.
2. The receipt includes, or the verifier holds, a **log inclusion proof** for the binding `(principal P, key K, valid_from, valid_to)` against a **signed tree head** (STH) that the verifier has **witnessed** (i.e., holds a prior cosigned STH or a gossip-verified STH) at or before the receipt's claimed signing time.
3. The STH's timestamp is ≤ the receipt's signing time, and the verifier's witnessed STH is ≥ the inclusion proof's STH in the log's total order (monotonic consistency).
4. No revocation entry for `K` appears in the log at an index ≤ the inclusion proof's index (revocation must not precede the binding being relied upon).

If any of (1)–(4) fails, the receipt is *signature-valid but attribution-unanchored*. It must not be used to settle liability. It may be retained as evidence, but it cannot discharge the counterparty's non-repudiation obligation.

## Decision Boundary

The boundary is **witnessed STH vs. directory read**, and it is sharp:

- **Honor** the receipt when the verifier holds a cosigned or gossiped STH covering the key binding, the STH predates the signing time, and no earlier revocation exists. This is the only branch that permits liability transfer.
- **Quarantine** (do not honor, do not discard) when the signature verifies but the key binding lacks a witnessed inclusion proof — e.g., the verifier fetched the key from a live directory, or the only STH available is the counterparty's unsigned current head. Quarantine means: hold the receipt, request the counterparty produce an inclusion proof against a previously witnessed STH, and block settlement until resolved or until the dispute window closes.
- **Reject** when the signature fails, when a revocation entry precedes the binding, or when the STH the counterparty produces is inconsistent with a previously witnessed STH (a fork — this is a non-repudiation *failure*, not a key-rotation problem, and must escalate).

The non-obvious rule: **a rotation does not invalidate prior receipts, but it invalidates the verifier's ability to rely on any receipt it did not anchor before the rotation.** The verifier must have witnessed the pre-rotation STH *before* the rotation occurred. If it did not, the receipts it holds from the pre-rotation window are permanently unanchored and must be treated as quarantine-grade regardless of how clean the signatures look.

## Operational Effect

Downstream, this changes three things. First, settlement pipelines must carry a `provenance_anchor` field per receipt — the STH hash and its witnessing timestamp — and refuse to settle receipts whose anchor is missing or post-dates signing. Second, key-directory reads become *advisory only*; the authoritative source for key bindings is the log with a witnessed STH. Third, the verifier must run a continuous STH-witnessing loop (gossip or cosigned checkpoint fetch) so that at any rotation it already holds the pre-rotation head. A verifier that starts witnessing only after a dispute has already lost the ability to attribute the disputed window. The cost is a small, constant background fetch and a per-receipt anchor check; the alternative is unbounded liability exposure at every rotation boundary.

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


class UnanchoredReceiptError(RuntimeError):
    """Raised when a receipt is signature-valid but its key binding is not
    anchored in a witnessed signed tree head prior to the signing time."""


@dataclass(frozen=True)
class SignedTreeHead:
    tree_size: int
    root_hash: bytes
    timestamp: float
    witnessed_at: float  # when *we* observed/cosigned it


@dataclass(frozen=True)
class KeyBinding:
    principal: str
    key_id: str
    valid_from: float
    valid_to: Optional[float]
    inclusion_index: int
    sths: tuple  # SignedTreeHeads the binding is proven against


@dataclass(frozen=True)
class ActionReceipt:
    principal: str
    key_id: str
    action_digest: bytes
    signature: bytes
    signed_at: float
    anchor_sth: Optional[SignedTreeHead]


def _verify_signature(receipt: ActionReceipt, public_key: bytes) -> bool:
    # Placeholder: real impl uses Ed25519/ECDSA over canonical digest.
    return len(receipt.signature) == 64 and len(public_key) == 32


def attribute_receipt(
    receipt: ActionReceipt,
    binding: KeyBinding,
    witnessed_sths: tuple,
    revoked_key_ids: frozenset,
    public_key: bytes,
) -> bool:
    """Return True iff the receipt is attributable and may settle liability.

    Raises UnanchoredReceiptError when signature is valid but provenance
    is not anchored — the receipt must be quarantined, not honored.
    """
    if not _verify_signature(receipt, public_key):
        raise UnanchoredReceiptError(
            f"signature invalid for key {receipt.key_id}"
        )

    if receipt.key_id in revoked_key_ids:
        raise UnanchoredReceiptError(
            f"key {receipt.key_id} revoked before binding relied upon"
        )

    # Must have a witnessed STH that (a) we observed before signing time
    # and (b) covers the binding's inclusion index.
    anchor = receipt.anchor_sth
    if anchor is None:
        raise UnanchoredReceiptError(
            f"receipt for {receipt.principal} has no anchor STH; "
            "live directory read is not sufficient for attribution"
        )

    matching = [
        s for s in witnessed_sths
        if s.root_hash == anchor.root_hash
        and s.tree_size == anchor.tree_size
    ]
    if not matching:
        raise UnanchoredReceiptError(
            "anchor STH was never witnessed by this verifier; "
            "counterparty could retroactively rewrite key history"
        )

    witnessed = matching[0]
    if witnessed.witnessed_at > receipt.signed_at:
        raise UnanchoredReceiptError(
            f"anchor STH witnessed at {witnessed.witnessed_at} "
            f"after signing at {receipt.signed_at}; "
            "pre-rotation state was not anchored in time"
        )

    if binding.inclusion_index > witnessed.tree_size:
        raise UnanchoredReceiptError(
            "binding inclusion proof exceeds witnessed tree size"
        )

    # Binding must be valid at signing time.
    if not (binding.valid_from <= receipt.signed_at):
        raise UnanchoredReceiptError("binding not yet valid at signing time")
    if binding.valid_to is not None and binding.valid_to < receipt.signed_at:
        raise UnanchoredReceiptError("binding expired before signing time")

    return True
```