cs.CEOct 29, 2026
SavePCM: A Proof-Carrying Message Protocol for Verifiable Multi-Agent Communication
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.
Figure 2: PCM architecture. ❶ – ❸ : every tool call of agent 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 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.
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 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.
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.
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.
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 | ||||
| parent | ||||
| , same JSON type | (strings) | never | never | |
| a string in | never | never | ||
| same type, | never | same type, | never | |
| same type, | never | never | same type, | |
Table 3: When a child caveat implies a parent caveat 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 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 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) IPv4 only as a dotted quad | ...-ipv4-leading-zero |
| 1e400 | one JSON loader: error; another: | different verdict classes (F5) 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 one bracket rule, applied first | ...-bracket-ipv6-userinfo |
| [::ffff:01.2.3.4] | ipaddress 3.9.5 accepts; 3.9.5 refuses | reached 1.2.3.4 vs. nothing 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 printable ASCII hosts only | ...-deviation , ...-idn |
| http://a.example\ @b.example/ | browser: a.example ; generic parser: b.example | either host provable 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 ( 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 ) 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 | 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 | 1.42 | 2.25 | 0.99 | 1.16 |
| reached_host | 4.2 | 9.5 | 1.45 | 1.67 | 0.99 | 1.23 |
| file_written | 4.4 | 7.4 | 1.42 | 1.64 | 0.99 | 1.10 |
| approved_by | 6.1 | 13.0 | 1.67 | 2.51 | 1.25 | 1.82 |
| grant only | 1.9 | 4.5 | 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 proof | Person- rooted auth. | Attenuating delegation | Replay across restart | Offline | |
| A2A / MCP (+TLS) [ 1 , 2 ] | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | — |
| Signed Agent Card / uAgents | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ |
| RFC 9421 + replay (ANP, TAP) | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ | |
| SCITT receipts [ 7 , 33 ] | ✓ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ |
| AP2 / Verifiable Intent [ 3 , 25 ] | ✗ | ✗ | ✓ | ✗ | ✓ | ||
| Macaroons / Biscuit / UCAN | ✗ | ✗ | ✗ | ✗ | ✓ | ✗ | ✓ |
Table 13: What a receiver can check under each approach. ✓ : yes; : 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 |
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 |
Table 15: Receiver models used in RQ5.
More in this topic
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