← Lab /AI/ML

Proof-carrying messages let receivers verify claims, rejecting 98.6% of false ones

AI/ML2026-10-29T00:50:34Z Method · Prototype · arXiv Threat model

The claim

PCM can verify multi-agent claims and limit false acceptance to 1.4% of messages

Bravish Ghosh · arXiv Paper PDF

Published as: “PCM: A Proof-Carrying Message Protocol for Verifiable Multi-Agent Communication”

So what

PCM enables multi-agent LLM pipelines to automatically reject the vast majority of fabricated claims, reducing the chance of unauthorized actions such as fraudulent refunds.

The five-minute version

PCM accepts only 10 of 712 false claims (1.4%, 95% CI 0.8-2.6%) and all of those are stale evidence that the protocol cannot catch. In a benchmark of 926 real-world messages, two independent verifiers agree on every verdict and verification takes about 1 ms. Compared with plain A2A and six modeled deployed protocols, which accept 70.8-100% of the same lies, PCM dramatically reduces the risk of agents acting on fabricated facts. The evidence is strong: the evaluation uses a publicly released benchmark (PCM-Lies) derived from real signer runs and the results are reproducible.

What they found 1

PCM rejects 702 of 712 false claims and flags the remaining 10 as stale evidence
“PCM accepts 10 of 712 lies (1.4%; 95% CI 0.8-2.6%), and all 10 are of one kind, stale evidence: a suite passed, the code changed and the suite failed, and the sender cites the pass.”

What undercuts it the paper’s own results

All 10 false accepts are stale evidence, which PCM’s current evidence model cannot detect.
PCM does not make a compromised agent honest: a prompt-injected agent can still ask for anything its grants allow, and the grant, not the agent, sets the limit.

Stated limits 4

PCM does not make a compromised agent honest: a prompt-injected agent can still ask for anything its grants allow, and the grant, not the agent, sets the limit.
Every PCM 0.1 claim type is existential: “a call ran and succeeded”. The sender chooses which records to disclose, so evidence can show that something happened, but never that nothing happened since.
A compromised signer, or a caller who can make it sign as another identity, can mint anything (Section 9.6).
PCM moves trust from the agent to the signer, but does not remove it.

What’s new here 4

Each claim carries cryptographic evidence from an append-only Merkle log that the sender cannot forge.
A three-valued semantics (proven, unproven, failed) separates doubt from falsity for individual claims.
Authority is expressed as person-rooted grant chains that can only narrow, never widen, the original approval.
Strict-reading rules guarantee deterministic verdicts across different verifier implementations.

Threat model stated by the source

Adversarysender agent fully controlled by an attacker (e.g., prompt-injected LLM)

Capabilitycompose arbitrary message bodies, fabricate T1 tool results, choose identifiers, write files, replay, reorder, drop or redirect network traffic, and send messages to any receiver

Assumesthe attesting signer is honest and its keys are not compromised; attesting gateways/executors record T2 results correctly

Artifacts & methods 5

PCM protocol (specification)system
PCM-Lies benchmarkdataset
Tracekit reference implementation (v1.5.0)system
append-only Merkle log with inclusion proofs (RFC 9162)
three-valued claim checkerprimitive

Topics

Merkle transparency logsproof-carrying messagesthree-valued claim semanticsgrant chain attenuationoffline verificationreplay protectionLLM agent security

← Previous Self-evolution makes personal agents far more vulnerable to indirect prompt injection