PCM: A Proof-Carrying Message Protocol for Verifiable Multi-Agent Communication

What it claims

PCM 0.1 is a message protocol in which the trusted party is an attesting signer, not the sending agent. Plain channel authentication fails here: TLS, mTLS, a signed A2A Agent Card or an RFC 9421 signature all prove who sent a message, and the sender is the party in doubt. The summary gives PCM's 1.4% false-accept rate. The comparison is what it omits: specification-faithful models of six deployed agent protocols accept 70.8% to 100% of the same 712 lies. Stacking AP2, SCITT and RFC 9421 together still accepts 51.3%.

How it works

• The signer owns everything that counts as evidence. It holds every key, sets policy, and appends each tool call to a Merkle log the agent cannot write. No agent ever holds a signing key.
• Records come in two tiers. A T1 record is a result the agent's own process reported. A T2 record comes from an attesting gateway or executor that ran the call itself. Observers (an egress proxy or kernel sensor) record network effects, and optional witnesses cosign checkpoints.
• Messages carry their proofs. Each message includes the backing records with RFC 9162 inclusion proofs under a signed checkpoint. Tool arguments are HMAC-committed and opened selectively. Only JCS (RFC 8785) bytes are hashed and signed, using Ed25519 and SHA-256.
• T1 never yields "proven". No combination of the agent's own reports can make a claim proven.
• Approvals are bound to what was decided, not to a name. An approval of a call the agent named refund-81-approved says nothing about the call, so binding requires a three-record linkage and an explicit "covers" check.
• Authority can only narrow. A grant chain is rooted in a recorded human approval of exact terms. Each later link must narrow its parent under a typed implication table. The signer checks each delegation and the receiver re-checks the whole chain.
• Verifiers are made to agree. Wherever parsers disagree, PCM adopts one strict reading, and anything outside it becomes unproven. The paper's examples: 0127.0.0.1 under inet_aton versus the macOS resolver, a.example\@b.example URL hosts, shlex versus sh tokenisation, and 1e400 in JSON. The rules are pinned by 187 conformance vectors.

flowchart LR
  A[Agent, untrusted] -->|tool calls, body| S[Attesting signer]
  G[Gateway / executor T2] --> L[Append-only Merkle log]
  O[Observer] --> L
  S --> L
  S -->|signed msg + inclusion proofs| R[Receiver, offline check]
  R -->|T2 records match| P[proven]
  R -->|absent, T1 only, ambiguous| U[unproven]
  R -->|malformed, contradicted| F[failed]

Evidence

The PCM-Lies benchmark has 926 messages from real signer runs, covering real pytest suites, HTTP fetches, file writes and human approvals. It contains 712 lies in 16 classes, labelled from ground truth rather than by a verifier. Of the 712 lies, PCM rejects 626, flags 76 as accept-unproven and accepts 10. All 72 claims backed only by agent self-report come out unproven. Two separately written verifiers agree on the verdict and reason class for all 926 messages.

Median message size is 1.9 to 11.7 KB, or 4.2 to 6.1 KB with one claim. Median verification time is 0.8 to 1.2 ms. The paper also gives security proofs (origin, evidence soundness, T1 non-elevation, attenuation, at-most-once acceptance across restarts) and a catalogue of 29 attacks and assumptions.

How to use it

The released artefacts are the specification, JSON Schemas, a frozen tool registry, the 187 vectors, a standalone verifier, the reference implementation (Tracekit 1.5.0) and the benchmark, all under the MIT licence. Adopting PCM means deploying an attesting signer that all agent tool calls go through. Receivers must pin the log keys they trust in a trust document and keep replay state. The fetched text gives no install commands.

Limits

• The signer is the trusted computing base. PCM does not protect against a compromised signer or a leaked log key.
• Compromised agents still act within their grants. A prompt-injected agent can request anything its grants allow.
• Claims are existential. A claim says something happened, not that it still holds, which explains all 10 accepted lies: a passing test run cited after later code changes made the suite fail.
• Absence cannot be proven, because the sender chooses which records to disclose.
• There is no confidentiality, which is left to TLS.
• Some results are outside the excerpt. A signer-bug variant is evaluated separately, and its results are not in the fetched text, which ends at Section 3.5.
• The evidence comes from one source. The benchmark and the baseline models were built by the author, Bravish Ghosh of Cygnux Labs (arXiv, October 2026).