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

Bravish Ghosh

cs.CEOct 29, 2026

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

Authors: Bravish Ghosh

Organizations: Cygnux Labs

Abstract

When one AI agent tells another that "the tests passed" or "a person approved this refund", the receiver has only the sender's word. A2A and MCP authenticate the channel, but the sender is the party in doubt, so a prompt-injected agent can launder fabricated facts and authority through a multi-agent system. We present Proof-Carrying Messages (PCM), a protocol in which each claim carries evidence: records from an append-only Merkle log that the agent cannot write, with inclusion proofs, signed by an attesting signer the agent cannot control. Receivers check messages offline and give each claim a three-valued result: proven, unproven or failed. A claim that rests only on the agent's own report is never proven. Authority travels as grant chains rooted in a recorded human approval, and the chains can only narrow. We specify four claim types, a typed caveat algebra, replay rules that survive restarts, and strict readings that make independent verifiers agree, and we prove the resulting security properties. On a pre-specified benchmark of 926 messages from real runs, 712 of them lies in 16 classes, PCM accepts 10 lies, all of them stale evidence (1.4%, 95% CI 0.8-2.6%). Plain A2A accepts all 712, and models of six deployed protocols (A2A with signed Agent Cards, uAgents, RFC 9421, SCITT, AP2, Verifiable Intent) accept 504-712. Two independent verifiers agree on all 926 verdicts, and verification takes about 1 ms.

Figures & tables

Party	Role	Writes	Trusted?
Agent (sender)	Calls tools, composes the message body	from , to , intent , claims , grants , payload ; T1 tool results	✗
Attesting signer	Holds keys, decides policy, appends records, signs messages, grants and checkpoints	id , ts , nonce , sig ; record seq , source , tier ; approvals; effects	✓ (TCB)
Attesting gateway / executor	Runs a tool call on the agent’s behalf and reports the result	T2 tool results (marked by the signer from the authenticated caller)	✓ (per tool class)
Observer	Egress proxy or kernel sensor that reports network effects	effect.observed records	✓
Person	Human approver named in the signer’s approvals configuration	approval answers	✓ (for what they approve)
Witness	Cosigns checkpoints consistent with its view	cosignatures	optional

Table 1: Parties in PCM and what each is trusted for. “Writes” lists what enters the log or the message on that party’s authority.

Panel of Figure 2 — Figure 2: PCM architecture. ❶ – ❸ : every tool call of agent $A$ is decided and recorded by the attesting signer. Results come from the agent’s own process ( T1 ) or from an attesting executor or gateway ( T2 ); approvals come from named people; network effects come from observers. ❹ : when $A$ sends a message, it asks the signer to sign the body as its run, and for records with inclusion proofs. ❺ – ❻ : the receiver verifies everything offline against keys it pins. The agent never holds a key.

Panel of Figure 3 — Figure 3: Anatomy of a PCM message , from the conformance vector accept-approved-by . Every object is closed (an unknown member makes the envelope invalid). The signature covers the JCS encoding of every member except sig , together with the domain-separation tag. Evidence and grants are therefore bound to the message, and nothing can be added after signing.

Claim	proven when	unproven when	failed when
tests_passed {suite}	an opened, non-denied decision of a shell -class tool whose command equals suite exactly, with a T2 result ok	no evidence; result is T1 ; tool not placed as shell	suite is no single test command ( Section 6.1 ); the T2 result is not ok ; no matching call
approved_by {person, call, covers?}	an approval by the configured person (not an agent, not self) of call , plus the approval.request it answers plus the policy.decision that request names; with covers , the approval also covers this request	no evidence; with covers : the schema names no tool, or the decision is not opened	no such triple; records disagree on what was approved; with covers : another tool, other args, or a pcm.grant that did not issue this root grant
reached_host {host}	an observer’s net effect with connections $>0$ to the host; or an opened http -class call whose URL host equals it, with a T2 result ok	no evidence; only a connect attempt or a zero-connection minute; result is T1 ; a host that will not parse ( Section 6.3.1 )	no record of the host; a URL whose scheme has no host ( file: , gopher: ); the T2 result is not ok
file_written {path, digest}	an opened Write whose full content hashes to digest and whose absolute path equals path under the claim’s path rules, with a T2 result ok	no evidence; result is T1 ; the call’s path is relative and may be the file; a drive path spelled otherwise	path is relative or has a .. segment; the digest differs; a tool other than Write

Table 2: The four claim types of PCM 0.1 and when each is proven , unproven or failed . “Attested” is Definition 5 . Each row is pinned by the vectors listed in the specification.

Panel of Figure 4 — Figure 4: How approved_by is proven (vector accept-approved-by ). The call id is the agent’s own name, so an approval record alone says nothing about what was approved. The checker requires the three-record linkage. The result’s conformance field approved reports the decision’s tool and opened args, and covers: true asks the verifier to check that this approval stands for this request.

Panel of Figure 5 — Figure 5: Host canonicalisation ( Section 6.3.1 ). Every step is specified character by character, so that verifiers in any language agree. Where two common readers disagree on a URL’s host, the host will not parse rather than match a host the call may not have reached. Examples below each step are refused there; each is a conformance vector.

Panel of Figure 6 — Figure 6: A grant chain only narrows (illustrative values; the vector accept-approved-by uses a non-delegable root). No agent holds a key. The signer signs a child only after checking it against its parent, and the verifier checks the whole chain again. A child that widens one caveat while tightening another is refused.

	child caveat $c$
parent $p$	$=v$	$\in T$	$\leq b^{\prime}$	$\geq b^{\prime}$
$=x$	$v=x$ , same JSON type	$T=\{x\}$ (strings)	never	never
$\in S$	$v$ a string in $S$	$T\subseteq S$	never	never
$\leq b$	same type, $v\leq b$	never	same type, $b^{\prime}\leq b$	never
$\geq b$	same type, $v\geq b$	never	never	same type, $b^{\prime}\geq b$

Table 3: When a child caveat

c

implies a parent caveat

p

on the same field ( Lemma 3 ). A child narrows its parent iff every parent caveat is implied by at least one child caveat. Missing caveats count as widening; the child may add caveats on any field.

Rule	Check	Example vectors ( reject- omitted)
needed	no grants: none , or failed if the schema has grant: true	grant-needed
signature	each sig.key = message sig.key ; verifies with tag pcm.grant.v0	grant-tampered , grant-from-another-log
intent	each grant’s intent = intent.type	grant-other-intent
caveats	valid for the intent’s schema	grant-bad-caveat
expiry	message ts $\leq$ each expires_at	grant-expired
tenant	each issuer.tenant = from.tenant	grant-cross-tenant

Table 4: Grant-chain rules (S7.6). Any failing rule makes the grants result failed and the verdict reject .

	accept	accept-unproven	reject	bad-input	total
Level 1 (no evidence)	11	2	35	1	49
Level 2 (evidence)	19	44	75	–	138
all	30	46	110	1	187

Table 5: The PCM 0.1 conformance vectors by level and expected verdict. A vector is Level 2 iff some claim carries evidence. One bad-input vector holds raw text ( 1e400 ) that must be refused as a parse error.

#	Class	Attack or mistake	Rule that closes it
1	V	Reuse a victim’s run id and tenant on another signer; replay its evidence	checkpoint origin $=$ message’s log; one key per log name; records of sender’s run and tenant
2	C	Agent reports its own tool result as success ( T1 )	only T2 or signer-written records prove; tier read from signer-set top-level fields
3	C	Harmless tool given a command / url member to pose as shell/http	placement by frozen table of tool names only
4	G	Grant from one tenant authorises another	issuer tenant must equal from.tenant ; no cross-tenant delegation
5	E	Log key signs checkpoints, messages and grants	tags pcm.message.v0 / pcm.grant.v0 ; JCS bytes never parse as a note
6	G	Root grant minted by an agent, self-approved, or by the subject	root only from a configured person’s approval of the exact terms

Table 6: Attacks and mistakes closed by PCM 0.1 rules (condensed from S14). “Class” marks where the check lives: E nvelope/signature, V idence, C laim checker, G rant, R eplay, D eterminism.

Input	Readers disagree	Effect before $\rightarrow$ PCM 0.1 rule	Vector
http://0127.0.0.1/	inet_aton : 87.0.0.1 ; macOS resolver: 127.0.0.1	proved a host never contacted (F1) $\rightarrow$ IPv4 only as a dotted quad	...-ipv4-leading-zero
1e400	one JSON loader: error; another: $+\infty$	different verdict classes (F5) $\rightarrow$ parse error, bad-input	bad-input-number-past-double
http://[::1]@ api.example.com/	CPython urlsplit , across releases, three bracket checks	accept vs. accept-unproven $\rightarrow$ one bracket rule, applied first	...-bracket-ipv6-userinfo
[::ffff:01.2.3.4]	ipaddress $<$ 3.9.5 accepts; $\geq$ 3.9.5 refuses	reached 1.2.3.4 vs. nothing $\rightarrow$ refuse leading zero in an embedded quad	...-ipv6-leading-zero
faß.example , U+1806	IDNA 2003 vs. UTS 46 vs. browsers	proved example.com from a look-alike $\rightarrow$ printable ASCII hosts only	...-deviation , ...-idn
http://a.example\ @b.example/	browser: a.example ; generic parser: b.example	either host provable $\rightarrow$ two readings must agree	...-ambiguous

Table 7: Reader divergences that PCM 0.1 resolves by a strict reading. Each row is pinned by at least one conformance vector (name abbreviated). “Effect before” is what the divergence allowed in an earlier draft or a naive implementation.

Class	Lie (mutation)	T	H	F	A	G	X	Total
Content lies: the sender says something false about the world
L1	fabricated event (no such call or approval)	12	12	12	12			48
L2	wrong outcome (ran and failed; claims success)	12	12	12	12			48
L3	wrong object (other host, file, args or tool)	12	12	12	23			59
L4	T1 -only evidence (agent’s own report)	12	12	12				36
Evidence and delivery lies: the sender forges or reuses proof

Table 8: The PCM-Lies dataset (926 messages). Columns are claim types: T tests_passed , H reached_host , F file_written , A approved_by , G grant only, X three claims. L4 and AB-t1 are unknowable ( T1 -only); L16 mixes 96 lies with 35 true encodings.

Hypothesis (pass bar)	Result	Outcome
H1: no lie accepted (0)	10 of 712 accepted (1.4%, 95% CI 0.76–2.57%), all stale evidence (L10, freshness scope); verdicts on lies: 626 reject , 76 accept-unproven , 10 accept	fail
H2: honest claims proven ( $\geq$ 99%)	76 of 78 claims (97.4%); 81 of 83 messages; both misses are HTTP 404 fetches	fail
H3: T1 -only claims unproven (100%)	72 of 72	pass
H4: verifiers agree (100%)	926 of 926 (verdict, reason class, conformance fields)	pass
Baseline: plain A2A	712 of 712 lies accepted	—
Baseline: sender signature only	643 of 712 (90.3%, CI 87.9–92.3%)	—

Table 9: Pre-specified hypotheses, final dataset (926 messages; Tracekit 1.5.0). Both PCM verifiers give identical numbers.

Figure 7: PCM’s verdict on each lie class. Only L10 (stale proofs) produces accept , for the 10 messages whose cited evidence is real but later undone. L4 is entirely accept-unproven by design ( T1 -only). In L1–L3 and L16, accept-unproven marks claims the verifier cannot decide (no evidence, a host that will not parse), which a receiver treats as the sender’s word.

Figure 8: Lies accepted per class (cell value, out of $n$ ) for each receiver. Darker is worse. Authenticating the sender (Agent Card, uAgents, RFC 9421, sender signature) catches only replays, forged signatures and unparseable wire input. SCITT receipts catch evidence that is not in the log (L9, part of L5/L8/L10) but cannot tie a claim to its records. AP2 and VI catch authority lies (L12–L15) but carry no evidence about tests, hosts or files. PCM’s only non-zero cell is L10.

		sender authentication					mandates
Scope	$n$	A2A	Card	uAg.	9421	SCITT	VI	AP2	SigOnly	PCM
claim	192	192	192	192	192	182	146	146	192	0
evidence	265	265	265	265	265	113	208	208	229	0
authority	90	90	90	90	90	90	26	21	82	0
delivery	50	50	50	40	20	50	36	36	50	0
encoding	96	96	96	96	96	96	83	83	71	0

Table 10: Lies accepted by scope and receiver. Scopes partition the 712 lies. “Freshness” is the 10 stale-evidence lies; other L10 lies (an old checkpoint with later records) fall under “evidence”.

	Finding	Before	After	Status
F1	leading-zero IPv4 ( 0127.0.0.1 )	accept : 87.0.0.1 proven, though macOS connected to 127.0.0.1 (7 lies)	accept-unproven : “not written as a dotted quad”	fixed
F2	stale evidence	accept (10)	accept (10)	open (limit)
F3	approval of a smaller or other call	accept (6 lies)	accept-unproven or reject via covers	fixed
F4	honest fetch answered 404	reject (2 honest)	reject (2 honest)	open (limit)
F5	1e400 read two ways	verifiers disagree (5)	both refuse as bad-input	fixed
H1 lies accepted		23/687 (3.3%, CI 2.2–5.0%)	10/712 (1.4%, CI 0.8–2.6%)

Table 11: Findings of the PCM-Lies benchmark, before (dataset 1, 879 messages) and after (dataset 2, 926 messages, with the fixes). Three were fixed in the specification and both verifiers, with vectors; two are documented 0.1 limits.

Figure 9: Cost of PCM. (a) Median size of honest messages by claim type, against the same message without sig , grants and evidence (“plain A2A”); labels give the PCM size in KB and the median per-message ratio. (b) Distribution of verification time over the 876 messages that parse (the other 50 are raw texts that the loaders refuse before any check).

	size (KB)		Tracekit verifier		standalone
Claims	p50	vs. plain	p50	p99	p50	p99
tests_passed	4.2	9.2 $\times$	1.42	2.25	0.99	1.16
reached_host	4.2	9.5 $\times$	1.45	1.67	0.99	1.23
file_written	4.4	7.4 $\times$	1.42	1.64	0.99	1.10
approved_by	6.1	13.0 $\times$	1.67	2.51	1.25	1.82
grant only	1.9	4.5 $\times$	0.87	1.44	0.45	0.69

Table 12: Message size (honest messages) and verification latency (all parsed messages of each type, lies included), in ms, single-threaded CPython 3.11 on Apple silicon. Sizes are the UTF-8 bytes of compact, key-sorted JSON (1 KB

=

1000 B).

	Sender cannot sign	Claims tied to records	Self-report $\neq$ proof	Person- rooted auth.	Attenuating delegation	Replay across restart	Offline
A2A / MCP (+TLS) [ 1 , 2 ]	✗	✗	✗	✗	✗	✗	—
Signed Agent Card / uAgents	✗	✗	✗	✗	✗	✗	✓
RFC 9421 + replay (ANP, TAP)	✗	✗	✗	✗	✗	$\circ$	✓
SCITT receipts [ 7 , 33 ]	✓	✗	✗	✗	✗	✗	✓
AP2 / Verifiable Intent [ 3 , 25 ]	$\circ$	✗	✗	✓	✗	$\circ$	✓
Macaroons / Biscuit / UCAN	✗	✗	✗	✗	✓	✗	✓

Table 13: What a receiver can check under each approach. ✓ : yes;

\circ

: partly or in a limited setting; ✗ : no, by our reading of each specification. “Offline” means without contacting the sender, the signer or the service.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Vector	What differs; reason	Verdict
accept-unproven-t1-result	adds tests_passed backed only by the agent’s own report; “the result is the agent’s own report (T1)”	accept-unproven
accept-tests-passed-t2	the executor recorded the result; “…run by mtls:spiffe://example/executor (T2)”	accept
reject-claim-pytest-or-true	the executor ran pytest -q … \|\| true ; “not a single test command”	reject
reject-claim-changed-record-hash	one hex digit of a record hash changed; “record 1: hash does not match the event”	reject
reject-claim-approved-by-self-approval	erin approves a call of her own agent’s run	reject
reject-grant-amount-over-caveat	amount 50000; “grant 0: amount 50000 breaks amount <= 20000”	reject

Appendix

Table 14: Variations of the worked example and their verdicts (reasons abbreviated).

Receiver	What it checks	What it cannot see
A2A 1.0 + signed card	Server authenticates by a scheme the card declares; client verifies the card’s JWS over its RFC 8785 form (spec §7.3, §7.4, §8.4). Messages, tasks and artefacts are unsigned; messageId de-duplication is optional (off).	every message-level lie
uAgents envelope	Sender signs SHA-256 of sender, target, session, schema digest, payload, expires and nonce; receiver verifies and refuses a target it does not host.	replays to the same target; all content
RFC 9421 + replay	Signature over @method , @target-uri , content-digest with created/expires/nonce/keyid; 300 s window; in-memory (keyid, nonce) cache.	restarts; floors; all content
SCITT receipts	Each claim must carry statements, each with a content hash and an inclusion receipt against a tree head a pinned log signed.	claim-to-record semantics, tiers, run binding, replay, grants
AP2 0.2 mandates	KB-JWT ( cnf , aud , nonce, iat ); open mandate signed by a trusted platform, intent, constraints, exp ; checkout mandates of the same args/tool, disclosed.	tests, hosts, files; delegation
Verifiable Intent 0.1	As AP2, with mandates signed by a person’s device key that an issuer certifies (L1).	as AP2

Appendix

Table 15: Receiver models used in RQ5.

Agent Communication Protocols

Agent communication protocols define how AI agents discover one another, exchange messages and state, coordinate tasks, and enforce trust.

See all 49 papers

May 19, 2026

Pramana: A Protocol-Layer Treatment of Claim Verification in Autonomous Agent Networks

Autonomous agents deployed in regulated domains must produce a verification artifact per consequential output: a record an auditor can re-execute offline, capturing what was claimed, against what source, by whom, when, and how. Production verification today splits into two unstandardized halves. Probabilistic verdict patterns (self-consistency voting, reviewer LLM ensembles) produce judgments, not artifacts. Artifact-producing patterns (RAG, tool-augmented traces, generator-verifier loops) produce vendor-specific records no external auditor can reconstruct without bespoke integration. Pramana defines the missing wire format. Every consequential agent output is wrapped in a typed ClaimAttestation with one of four variants (measurement, inference, analogy, citation), each paired with a verify() operation against the recorded source. verify() is deterministic for MeasurementClaim and CitationClaim. For InferenceClaim and AnalogyClaim, determinism is conditional on the oracle (audit-replayable when LLM-backed). The four-way typology derives from classical Indian epistemology (pramana, valid means of knowledge). The lifecycle is specified in TLA+ and exhaustively verified under TLC across three symmetry-reduced models: 38,563 distinct reachable states, zero invariant violations. The Python reference implementation passes 84 tests. An A2A and MCP wire-extension manifest layers three deployment-grade invariants: reachability, SLA bound, and offline re-verifiability. An exploratory pilot (n=100, 2,275 reviewer calls) probes LLM-as-judge in code generation. The strongest observation is a 40-percentage-point raw FPR delta across corpora, consistent with reference-solution quality contributing significantly. The pilot does not validate Pramana on its own; the structural argument and formal verification do that.

Ravi Kiran Kadaboina

Independent Researcher

AI Agent Reliability Claim Verification Data Provenance Algorithmic Auditing AI Agent Auditing LLM Agent Verification

Ask PDF

Mar 25, 2026

AIP: Agent Identity Protocol for Verifiable Delegation Across MCP and A2A

AI agents increasingly call tools via the Model Context Protocol (MCP) and delegate to other agents via Agent-to-Agent (A2A), yet neither protocol verifies agent identity. A scan of approximately 2,000 MCP servers found all lacked authentication. In our survey, we did not identify a prior implemented protocol that jointly combines public-key verifiable delegation, holder-side attenuation, expressive chained policy, transport bindings across MCP/A2A/HTTP, and provenance-oriented completion records. We introduce Invocation-Bound Capability Tokens (IBCTs), a primitive that fuses identity, attenuated authorization, and provenance binding into a single append-only token chain. IBCTs operate in two wire formats: compact mode (a signed JWT for single-hop cases) and chained mode (a Biscuit token with Datalog policies for multi-hop delegation). We provide reference implementations in Python and Rust with full cross-language interoperability. Compact mode verification takes 0.049ms (Rust) and 0.189ms (Python), with 0.22ms overhead over no-auth in real MCP-over-HTTP deployment. In a real multi-agent deployment with Gemini 2.5 Flash, AIP adds 2.35ms of overhead (0.086% of total end-to-end latency). Adversarial evaluation across 600 attack attempts shows 100% rejection rate, with two attack categories (delegation depth violation and audit evasion through empty context) uniquely caught by AIP's chained delegation model that neither unsigned nor plain JWT deployments detect.

Sunil Prakash

Indian School of Business, India

AI Agent Security Tool Access Control for LLM Agents LLM Agent Verification Capability-Based Security

Ask PDF

Feb 18, 2026

Verifiable Semantics for Agent-to-Agent Communication

Multiagent AI systems require consistent communication, but we lack methods to verify that agents share the same understanding of the terms used. Natural language is interpretable but vulnerable to semantic drift, while learned protocols are efficient but opaque. We propose a certification protocol based on the stimulus-meaning model, where agents are tested on shared observable events and terms are certified if empirical disagreement falls below a statistical threshold. In this protocol, agents restricting their reasoning to certified terms ("core-guarded reasoning") achieve provably bounded disagreement. We also outline mechanisms for detecting drift (recertification) and recovering shared vocabulary (renegotiation). In simulations with varying degrees of semantic divergence, core-guarding reduces disagreement by 72-96%. In a validation with fine-tuned language models, disagreement is reduced by 51%. Our framework provides a first step towards verifiable agent-to-agent communication.

Philipp Schoenegger, Matt Carlson, Chris Schneider +1

Microsoft AI · Wabash College

Semantic Drift in Language Models Multi-Agent Communication Agent Communication Protocols LLM Agent Verification

Ask PDF

Abstract

Agent Communication Protocols

Explore similar work

Pramana: A Protocol-Layer Treatment of Claim Verification in Autonomous Agent Networks

AIP: Agent Identity Protocol for Verifiable Delegation Across MCP and A2A

Verifiable Semantics for Agent-to-Agent Communication