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

What it is

PCM 0.1 (Proof-Carrying Messages) is a protocol from Bravish Ghosh of Cygnux Labs, posted to arXiv on 29 October 2026. It lets a receiving agent check claims such as "the tests passed" or "a person approved this refund" without trusting the sender. The reference implementation is Tracekit 1.5.0. The specification, JSON Schemas, frozen tool registry, 187 conformance vectors, a standalone verifier and the benchmark are all released under the MIT licence.

How it works

The agent's tool calls go through an attesting signer that the agent cannot control. The signer holds all keys and writes each call to an append-only Merkle log. It signs checkpoints, messages and grants. A message carries the log records behind each claim, with RFC 9162 inclusion proofs. The receiver checks them offline against log keys it has pinned.

Each claim gets one of three verdicts:

• proven: the evidence was written by a party other than the agent.
• unproven: the evidence is absent, is only the agent's own report (tier T1), shows less than the claim, or cannot be matched with certainty.
• failed: the claim is malformed or contradicted.

Authority travels as grant chains rooted in a recorded human approval. Each link can only narrow its parent under a typed caveat table. No agent holds a signing key.

The paper specifies four claim types, replay rules that survive restarts, and "strict readings" for parser disagreements. Its examples include 0127.0.0.1, 1e400 and shlex versus sh. A claim outside the strict reading becomes unproven.

flowchart LR
  A[Agent, untrusted] -->|tool calls| S[Attesting signer, TCB]
  S --> L[Merkle log agent cannot write]
  S -->|signed message + proofs| R[Receiver, offline check]
  R --> P[proven]
  R --> U[unproven]
  R --> F[failed]

Preconditions / Affected

PCM only helps where tool calls and approvals are routed through the signer, and, for calls that matter, through an attesting gateway or executor. The signer is the trusted computing base. The paper assumes it signs only as the calling run and sets id, ts and nonce itself. It also assumes the adversary cannot make a T2 executor or observer report events that did not happen.

Results

The benchmark is PCM-Lies: 926 messages from real signer runs (real pytest suites, HTTP fetches, file writes, human approvals), 712 of them lies in 16 classes. Labels come from ground truth, not from any verifier.

• PCM 0.1 accepts 10 of 712 lies (1.4%, 95% CI 0.8–2.6%). All 10 are stale evidence: a suite passed, the code changed, and the sender still cites the pass.
• Of the other 702 lies, 626 are rejected and 76 are flagged accept-unproven. All 72 claims backed only by the agent's own report are unproven.
• Baselines accept: plain A2A 712; sender-signature check 643; A2A 1.0 with signed Agent Card 712; uAgents envelope 702; RFC 9421 with replay checks 682; SCITT receipts 550; Mastercard Verifiable Intent 0.1 509; AP2 0.2 mandates 504. AP2, SCITT and RFC 9421 stacked still accept 365 (51.3%).
• The six deployed protocols are specification-faithful models built by the author, not the real products.
• Two independently written verifiers agree on all 926 verdicts and reason classes.
• Messages are 1.9–11.7 KB at the median (4.2–6.1 KB with one claim). Verification takes 0.8–1.2 ms at the median.

Caveats

• A compromised agent can still request anything its grants allow. The grant sets the limit, not the agent.
• A compromised signer or leaked log key is out of scope (non-goal N5).
• A claim says something happened, not that it still holds (N2). This explains all 10 false accepts.
• PCM cannot prove absence, because the sender chooses which records to disclose (N3). It provides no confidentiality (N4).
• The benchmark and the baseline models come from the PCM author. The fetched text ends partway through Section 3, so the proofs, the 29-attack catalogue and the evaluation detail were not available to check.