PCM: A Proof-Carrying Message Protocol for Verifiable Multi-Agent Communication
PCM: A Proof-Carrying Message Protocol for Verifiable Multi-Agent Communication
Quick read
Based on the paper's full text (AI-generated); refer to the original
The paper proposes the PCM (Proof-Carrying Messages) protocol, which attaches to each claim in messages between agents cryptographic evidence that the sender cannot tamper with; on a benchmark of 926 real messages, it accepted only 1.4% of lies, whereas ordinary A2A accepted all 712. Tool calls are recorded by proof signers that agents cannot control into an append-only Merkle log; the receiver verifies offline and gives a three-valued conclusion of proven, unproven, or failed, and a claim based solely on an agent's self-report is never judged proven; permissions are passed along an authorization chain rooted in human approval records that can only narrow, and agents do not hold signing keys. The benchmark PCM-Lies contains 712 lies in 16 categories; the specification models of six deployed protocols (A2A 1.0, AP2, SCITT, etc.) accepted 504–712 of them, and all 10 that PCM accepted were expired evidence (the event did occur but was subsequently revoked); validators from two independent implementations reached consistent conclusions on all 926 messages, with about 1 millisecond per verification.
- In multi-agent systems, the receiver can only take the sender's word for claims such as "the test passed" or "someone approved the refund"; A2A, MCP, and the like only authenticate the channel, while the sender is precisely the suspect party, and a prompt-injected agent can use multi-hop propagation to forge facts and permissions.
- Proposes Proof-Carrying Messages (PCM): an agent's tool calls are recorded by an attesting signer it cannot control into an append-only Merkle log, and messages carry log records with inclusion proofs; the receiver verifies offline and returns one of three values: proven/unproven/failed; permissions are passed along a human-approved grant chain and can only narrow.
- On 926 real runtime messages (including 712 lies across 16 categories), PCM accepts 10 lies (1.4%), all of them stale evidence; plain A2A accepts all 712, and six deployed protocol models accept 504–712; two independent verifiers agree on all 926 judgments, with verification taking about 1 ms.
- PCM cannot make a compromised agent honest; the signer is the trusted computing base; a claim only states that something once happened, not that it still holds, so stale evidence cannot be ruled out; it also cannot prove absence, does not provide confidentiality, and 0.1 has no revocation mechanism.
The paper designs for multi-agent communication a protocol that attaches verifiable evidence to each claim; the benchmark shows that models of deployed protocols accepted more than 70% of lies, whereas PCM accepted only 1.4%.