Technical Summary: Notarized Agents: Receiver-Attested Confidential Receipts for AI Agent Actions

Problem Statement

Current AI agent observability is structurally compromised because the entity producing the activity log is the same entity whose activity is being logged. In the dominant model (e.g., Langfuse, LangSmith), traces are collected from within the agent's process or the operator's infrastructure. This creates a single point of failure: if an agent is compromised (via prompt injection, context poisoning, or buggy code) or if the operator has misaligned incentives, the traces can be omitted, altered, or fabricated. The agent cannot be a reliable narrator of its own actions, and the owner has no independent way to detect tampering.

Existing solutions fail to meet a threat model where the adversary controls both the agent and its operator. A robust record of agent action must be:

1. Unforgeable by the agent or operator.
2. Independently verifiable by the owner using public infrastructure.
3. Confidential from public infrastructure operators.
4. Attributable to a structurally separate party present at the event.
5. Retrievable even if the agent is unavailable.

No surveyed system delivers all five properties.

Methodology: The Sello Protocol

The paper proposes "Notarized Agents," an architectural inversion inspired by historical notarization and modern systems like Apple's Find My network. Instead of the agent reporting its actions, the services the agent calls act as independent witnesses.

The authors instantiate this class of protocols as Sello, which combines four defining properties:

• P1: Receiver-side signing: The service receiving the agent's call signs the receipt using its own private key, not the agent's or operator's.
• P2: HPKE encryption to an owner-bound key: The receipt is encrypted to the agent owner's public key. Crucially, this public key is cryptographically bound to the agent's authorization token via a JWS claim, preventing substitution attacks.
• P3: Publication to a witness-cosigned Merkle log: Receipts are appended to a public transparency log (e.g., Sigstore Rekor) with witness cosigning to ensure tamper-evidence.
• P4: Owner-side discovery: The owner queries the log using a token-derived reference, decrypts receipts locally, and verifies signatures against a service identity registry.

Protocol Flow

1. Token Binding: The agent presents a JWS authorization token containing a claim with the owner's HPKE public key (owner_hpke_pk).
2. Action & Receipt Generation: Upon receiving a call, the service verifies the token, performs the action, and constructs a receipt body (containing action hashes, status, and timestamps).
3. Encryption & Signing: The service encrypts the body to the owner_hpke_pk using HPKE (X25519/KEM, ChaCha20-Poly1305). It then signs the encrypted envelope using COSE_Sign1 (Ed25519).
4. Logging: The signed envelope is submitted to a transparency log. The log returns a Merkle inclusion proof.
5. Verification: The owner queries the log using SHA-256(token-bytes). They verify the Merkle proof, resolve the service's public key via a registry, verify the COSE signature, and decrypt the payload.

Security Mechanisms

• Revocation: The protocol ties revocation decisions to the transparency log's integrated time rather than the service's self-asserted timestamp. This prevents a compromised service from backdating receipts to evade revocation.
• Replay Protection: An owner-side deduplication rule based on a tuple of (kid, token_ref, timestamp, action hashes) detects replayed events.
• Confidentiality: Receipt contents are hidden from log operators and network observers via HPKE; only the metadata (service ID, token ref) is visible.

Key Contributions

The paper makes four specific contributions:

1. Architectural Inversion: Identifying receiver-side signing as the structural fix for agent observability and defining the four cryptographic properties (P1–P4) that distinguish notarized protocols.
2. Sello Specification: A concrete protocol using standard primitives (COSE_Sign1, HPKE, Ed25519, Merkle logs) and a novel JWS token profile that binds the owner's encryption key to the authorization token.
3. Time-Binding Novelty: Proposing the use of the transparency log's integrated time for key revocation decisions, separating it from the receipt body's timestamp to mitigate backdating attacks.
4. Comparative Analysis: A property-by-property comparison showing that no existing system (Signet, AgentROA, Agent Passport System, etc.) combines all four properties.

Results and Evaluation

The authors provide microbenchmarks of the cryptographic operations using a reference implementation on an Apple M2.

• Overhead: A Sello-aware service adds approximately 0.45 ms of median CPU work per agent call (HPKE seal + signing + log append).
• Verification: An owner reconstructing activity performs approximately 0.28 ms of median CPU work per receipt (proof verification, signature check, decryption).
• Payload Size: A complete Sello envelope is approximately 467 bytes (independent of action size, as inputs/outputs are hashed).
• Scalability: A service handling 1,000 calls/second would spend ~0.45 seconds of CPU per second on receipts. An owner can reconstruct a day of activity (100,000 receipts) in ~32 seconds of CPU time using batch verification.

The paper notes that network latency for log submission is excluded from these measurements and depends on the specific log operator.

Limitations and Claims

The paper is explicit about what Sello does not solve:

• Suppression Attack: If the agent simply does not call services, no receipts are generated. The owner cannot distinguish between "no action" and "suppressed action."
• Service Collusion: If a service colludes with the operator to emit false receipts, Sello cannot detect this from a single receipt.
• Adoption Incentive: Services currently have no reason to emit receipts. The paper posits that adoption requires regulatory mandates (e.g., EU AI Act), settlement coupling, or market trust premiums.
• Set Completeness: Sello provides per-receipt verifiability but not cryptographic set-completeness. A log operator could theoretically omit matching receipts without detection unless specific completeness mechanisms (like authenticated query results or full log audits) are deployed.

Significance

The paper argues that the significance of Sello lies not in new cryptographic primitives, but in the architectural composition of existing ones to invert the trust boundary. By shifting the source of truth from the agent to the independent services it touches, Sello provides a tamper-evident, confidential, and owner-verifiable trail that survives agent compromise.

The authors conclude that while the adoption-incentive problem remains unsolved, the protocol provides the necessary precondition for rigorous AI auditing. The core thesis is that "the agent is not the right narrator of its own actions; the services it touches are."