Proof-Carrying Messages (PCM): A Protocol for AI Agents Whose Claims Carry Offline-Verifiable Evidence

Abstract

PCM is a protocol for messages between AI agents in which each claim about what happened can carry evidence that the receiver checks offline: records from a log the sending agent can't write, with Merkle inclusion proofs. When one AI agent tells another "the tests passed" or "a person approved this", the receiver today has only its word. PCM lets each such claim carry signed records from a log the sending agent can't write, and the receiver checks them offline. In a pre-registered benchmark of 926 messages, 712 of them lies, PCM accepted 10 lies, all of one kind it states as a limit (stale evidence); plain A2A accepted all 712, and a check of the sender's signature alone accepted 643.