From Privacy to Workflow Integrity: Communication-Graph Metadata in Autonomous Agent Interoperability
arXiv:2606.07150v1 [cs.CR] 5 Jun 2026
Bijaya Dangol Independent Researcher [email protected] June 8, 2026 Abstract Agent-interoperability protocols such as A2A and MCP standardize what agents say to one another, but assume address-based transport over HTTP(S). Such transports protect message content, increasingly with end-to-end encryption. What they leave in the clear is the communication graph: which agent contacts which, when, and how often. In agent systems this graph is more consequential than a privacy framing suggests. Endpoints are often capability-labeled, workflows are structured and chained, and interactions are coupled to real actions, so an observer of the graph recovers more than a history of past relationships. It can infer the pending workflow, the task being assembled and the action likely to follow, and, because these workflows execute at machine speed, act on that inference before the workflow completes. The threat is therefore one of workflow integrity, not privacy alone: predictive leverage over autonomous action. We give a threat model for the agent communication graph; identify what makes agent metadata distinctively revealing (semanticity, prospectivity, actuation); define transport- and bootstrap-layer privacy properties (unlinkability, no central observer, deniability, metadata minimization, and discovery privacy) and evaluate candidate transports (SimpleX/SMP, Tor, mixnets) against them; and present an A2A case study in which a metadata-protecting binding is expressible but surfaces the protocol’s implicit identity assumptions. We then test both claims on a generative model of agent workflows anchored to a real A2A capture. From passive metadata alone, with no payloads, a classifier recovers an interaction’s task class well above chance, and does so from only the opening of a workflow. Applied together, the properties drive that recovery sharply back toward chance. Beyond what an observer can recover, we measure the leverage of acting on the leak: an adversary that must choose, from a workflow’s opening and under a fixed budget, which workflows to act on realizes in this model most of the advantage a clairvoyant attacker would have over a metadata-blind one, and the same properties that suppress inference suppress this leverage.
1
Introduction
the communication graph: the record of which agent contacts which, when, how often, and how much data flows. Because routing requires addressing and addresses are identifiers, this graph is visible to network observers, relays, and registries even when every payload is encrypted. The graph is more than a privacy concern. Endpoints are often capability-labeled, workflows are structured and chained, and interactions are coupled to real actions. From such a graph an observer reads the shape of a task in progress, not merely a record of past contacts, and at machine speed can act on that shape before the workflow completes. What is exposed is then a matter of integrity, not privacy alone: the observer holds predictive leverage over actions that have not yet occurred. Existing agent-protocol
AI agents built by different vendors are increasingly made to interoperate through open protocols. A2A [1], now hosted by the Linux Foundation, and MCP [4] let agents discover one another, delegate tasks, and increasingly transact on behalf of users and organizations. These protocols standardize the content and structure of agent messages, but assume a conventional, address-based transport: agents are reachable at URLs or stable names, and messages travel over HTTP(S). Transport security here has focused, reasonably, on protecting message content: TLS in transit and a growing set of end-to-end schemes that keep payloads from intermediaries. What this leaves untouched is 1
threat models examine authentication, identity, and payload leakage; the communication graph, with its prospective, action-coupled character, has drawn little attention. This paper develops it systematically. Our contributions are:
the core set [1, §5], the extension point we use in §8. MCP plays a complementary (agent-to-tool) role but shares the same address-based, HTTP-oriented assumptions.
1. A threat model for the agent-interop commu- 2.2 Transport security today nication graph as a metadata surface, separate Beyond TLS, recent bindings strengthen content profrom payload confidentiality (§3, §4). tection: SLIM/SLIMRPC provides broker-less deliv2. An account of why agent metadata is distinc- ery with MLS end-to-end encryption [2, 5], so that tively revealing (its semanticity, prospectivity, no central intermediary reads message content. These and actuation), which reframes the threat from mechanisms target confidentiality and, for SLIM, the privacy to the integrity of autonomous workflows removal of a trusted broker; none aims at concealing the communication graph. (§5). 3. A transport- and bootstrap-privacy property framework (unlinkability, no central ob- 2.3 Metadata-protecting transports server, deniability, metadata minimization, and A separate lineage protects communication metadata: discovery privacy) and an evaluation of candidate mix networks [6], onion routing [8], mixnets [13], and transports against it (§6, §7). identity-less messaging such as SimpleX’s SMP [15]. These were built for human or general messaging; §7 4. An A2A case study showing a metadataasks what they offer when repurposed as agent-interop protecting binding is expressible but surfaces the transports. protocol’s implicit identity assumptions, and a reconciliation with the ecosystem’s identity and reputation direction (§8, §10). 5. An empirical evaluation on simulated agent workflows anchored to a real A2A capture: a label-blind network observer recovers task class well above chance and from only a short prefix of a workflow, and only the full set of properties collapses this recovery toward chance; and, moving from inference to action, that the recovered signal carries decision-theoretic leverage: an adversary acting under a budget from a workflow’s opening captures most of the attainable advantage over a blind baseline, which the same properties largely remove (§9).
2
Background
2.1
Agent interoperability protocols
3
System and Threat Model
3.1
System model
We consider a set of agents A = {a1 , a2 , . . . } that interoperate by exchanging messages under an interop protocol such as A2A or MCP. Two agents communicate over a transport binding that realizes the protocol’s abstract operations (request/response, streaming updates, and notifications) over a concrete transport. A binding may route through one or more intermediaries (relays, gateways, or brokers), and the protocol may use a registry for capability discovery and connection bootstrap. An interaction between ai and aj is the set of messages exchanged to complete one logical exchange (in A2A, the lifecycle of a task). Each message m carries a transport-visible descriptor
A2A models interoperation as tasks exchanged between a client and a remote agent. Agents publish Agent Cards (metadata documents at well-known URLs that declare capabilities, endpoints, and authentication) and communicate over one of several bindings (JSON-RPC, gRPC, or HTTP+JSON), all over HTTPS [1]. Operations are asynchronous: a call returns immediately, and task updates arrive by polling, server-sent streaming, or push notifications to a client-provided webhook [1, §3.1.7]. A2A also admits custom protocol bindings for transports beyond
obs(m) = (src, dst, t, ℓ, d), its endpoint identifiers, timestamp, length, and direction. Notably obs(m) excludes the message content, which we assume encrypted (Assumption 1).
3.2
The communication graph
Over a period of operation, interactions induce a communication graph G = (V, E): V is the set of transport-visible agent identifiers, and each edge 2
Agent A
encrypted
transport / relay
encrypted
Agent B
observer Learns the A ↔ B edge, timing, and volume, even though message content stays sealed.
Figure 1: Content encryption protects the payload but not the communication graph. An observer at the network or at an intermediary learns who talks to whom, when, and how often; in agent systems, often capability-labeled endpoints and their sequence further reveal the task in progress (§5). Out of scope are content confidentiality and paye ∈ E records that two endpoints interacted, annotated with timing, frequency, and volume. A linkage load data minimization (assumed handled elsewhere), relation maps transport-visible identifiers to persistent application-level authorization, and side channels outagent or operator identities. The assets we protect side the transport. are G, this linkage, and, as §5 argues, the predictive leverage over future action that G confers; not the content, which is protected by other means.
3.3
Adversary model
We model honest-but-curious adversaries distinguished by vantage point (Table 1); the threat is that G leaks without any active attack. A network observer N sees obs(m) for messages on observed links; an intermediary R sees what it forwards; a registry G sees discovery lookups and connection bootstrap; a participating or log-retaining endpoint E sees its own interactions, and more under collusion. Adversaries may collude to widen their coverage of E. Our leakage analysis needs only passive observation: the objective ranges from reconstructing G to inferring the pending workflow it encodes (§5). Acting on that inference (to preempt or interfere) may require separate active capabilities, which only strengthen the adversary.
4
The Communication-Graph Metadata Problem
4.1
Content and metadata are independent
The starting point is a simple but consequential observation: content confidentiality and communicationgraph privacy are independent, because they protect different things. An interaction can be perfectly content-confidential and still be fully graph-exposed.
Concretely, under Assumption 1 the payload reveals nothing, yet routing still requires the transport to address the destination. When endpoints are named by persistent identifiers, those identifiers appear as src and dst in every obs(m) and directly reveal the edge; the timing t, length ℓ, and direction d are visible 3.4 Trust assumptions and scope regardless of encryption. Since G is by definition the Assumption 1 (Content confidentiality). Message set of such edges, any adversary that observes them content is end-to-end encrypted under secure primi- reconstructs G no matter how strong the content tives; the adversary learns nothing from payloads. protection is. We state this as an observation, not a theorem, on We deliberately grant the strongest content protection so as to isolate the metadata axis: any leakage we purpose: it is close to definitional. The contribution identify is leakage that content encryption, however is not the claim that metadata leaks (that is well understood for communication systems in general) strong, does not prevent. but a systematic account of which metadata leaks Assumption 2 (No trusted graph custodian). No sin- in agent-interop protocols, to whom (§3), what a gle party is trusted to observe the full communication transport must provide to prevent it (§6), and the graph. protocol-level consequences of providing it (§8). 3
Adversary
Vantage point
Observes
N network R intermediary G registry E endpoint / log
links / paths relay / gateway / broker discovery service a participant or its logs
obs(m): endpoints, timing, volume forwarded src/dst, timing, volume lookups, connection bootstrap own interactions; more under collusion
Table 1: Adversary classes. All are passive (honest-but-curious) in the base model and may collude to increase coverage of E.
4.2
A walk through the A2A task life- graph can reveal something stronger, a task in progress, because agent interactions differ from generic messagcycle ing along three axes.
Let a client ac delegate a task to a server as under A2A, with all content encrypted. At discovery, G observes that ac resolved as . At connection setup, N and any on-path R observe the ac ↔ as edge. On message/send they observe timing and size; across streaming or polled updates they observe cadence and volume; a push notification additionally exposes ac ’s callback endpoint. By completion, although no adversary has read a single field of the task, N , R, and G jointly learn that ac engaged as , when, how often, and how much data flowed, and across many tasks the shape of the agents’ relationships.
Semanticity. Agent endpoints, tools, and registry entries are often semantically meaningful rather than opaque addresses. Agent Cards advertise skills, registries are queried by capability, and MCP tools are named by function. Observing that a client contacted a “contract-review” agent or invoked a “payments” tool reveals the class of task, not merely that an interaction occurred. This is the explicit-label analogue of website-fingerprinting attacks, where the class of activity is inferred from encrypted-traffic metadata [14], except that here the label is advertised rather than inferred. What an observer actually recovers depends 4.3 Why current bindings do not ad- on vantage point and binding: a registry sees capabildress it ity queries directly, whereas a pure network observer The A2A bindings over HTTPS (JSON-RPC, gRPC, may recover labels only indirectly, through discovery HTTP+JSON) protect content with TLS but address lookups, Agent Card fetches, structured names, or agents by URL, so N and R obtain the edge directly. repeated endpoint patterns. SLIM/SLIMRPC removes the central content-reading broker via MLS, yet routes by a persistent structured Prospectivity. Agent workflows are structured and name; R and N still obtain the edge, and the persis- chained: discovery precedes delegation, delegation tent name supplies the linkage of §3. None of these precedes tool invocation, and updates follow. Early target G: they protect content, which is independent steps can therefore predict later ones. An observer of the graph. who recognizes the opening of a familiar workflow may anticipate its trajectory before it completes, rather than learning of it only afterward. 4.4 Problem statement Definition 1 (Metadata-protecting binding). A transport binding is metadata-protecting against an adversary class if, from that adversary’s observations, it cannot reconstruct the communication graph G, nor infer the pending workflow it encodes (§5), beyond a bounded, unlinkable view, as made precise by the properties of §6.
Actuation. Agent interactions often trigger actions directly, without a human reviewing each step. The graph is thus coupled to consequences in the world: influencing or interrupting the observed workflow can change what the agents actually do. As an illustration, a lookup for a sanctions-screening agent, followed by payment-settlement and contractreview calls, suggests a cross-border transaction being 5 Why Agent Metadata Is Dif- assembled, revealing the kind of deal in progress well before it completes, without a single payload being ferent read. Generic communication metadata reveals that parties Together these shift the adversary’s objective. From communicated. In agent interoperability the same passive observation alone a graph observer may infer 4
historical relationships and, beyond them, pending intent and workflow trajectory. The harm comes when the adversary acts on that inference through separate, active channels: poisoning discovery, preempting a negotiation, triggering a competing action. Because the workflow is structured and runs at machine speed, such a move can land before the workflow completes. The pattern is familiar from front-running in decentralized exchanges, where adversaries watch pendingtransaction metadata and act ahead of it [7]. Agent interoperability raises the analogous risk wherever workflows are capability-labeled and structured, and potentially across many application domains rather than one. The framing shifts accordingly. Protecting the communication graph is not merely a privacy question, concealing who interacts; it concerns the integrity and contestability of autonomous workflows: their freedom to execute, and to be steered by their principals rather than by an outside observer who holds predictive leverage over machine-speed action. Section 9 measures how much intent the graph leaks, inferring task class from endpoint and sequence metadata; here the threat serves as the design motivation. A scope note: what becomes transport-visible is inter-agent and inter-tool coordination, not an agent’s internal, local planning.
specific agent to participation; any party can plausibly deny it. This targets a logging or colluding endpoint E. Definition 5 (Metadata minimization). The observable descriptors (t, ℓ, d) are reduced (e.g., padded, batched, or mixed) so that timing and volume do not distinguish interactions. This targets traffic analysis by N and R that survives even fresh identifiers. Definition 6 (Discovery privacy). Capability lookup and connection bootstrap do not reveal the requested capability, the selected peer, or the resulting interaction edge to an untrusted registry or transport intermediary.
This targets the registry G and the early, preinteraction leakage that §5 identifies as especially sensitive. Definitions 2–5 are wire-transport properties; §7 evaluates how far real transports meet them. Discovery privacy (Definition 6) is realized at the bootstrap layer instead, and §8 shows how an identity-less binding can provide it through out-of-band exchange. Together they make a binding metadata-protecting (Definition 1) against the corresponding adversaries; 6 Privacy Properties for Trans- in the terms of §5 they bound an adversary’s predictive leverage by denying the identity, timing, and port and Bootstrap discovery cues that make workflow inference possible, The following properties span transport and bootstrap so they protect the integrity of autonomous workflows, and are protocol-independent; for each we note the not only privacy. adversary capability it removes. Definition 2 (Unlinkability). An adversary cannot tell whether two observed interactions involve the same agent, nor link a transport-visible identifier to a persistent agent identity. This requires that identifiers not be stable across interactions: each interaction uses a fresh identifier unlinkable to the agent’s others.
7
Transport Design Space
No transport was designed for agent interoperability; each was built for human or general messaging, so applying it inherits both its protections and its limitations. Table 2 rates candidate transports against the properties of §6, alongside the HTTP(S) and SLIM Identifier freshness is the mechanism; it denies the bindings as baselines. Ratings are qualitative (strong / edge-linkage of §3 to N and R, and the persistentpartial / weak); the point is the shape of the trade-off, identity linkage to all classes. not a score. Definition 3 (No central observer). No single adversary vantage point observes more than a small fraction HTTP(S) bindings (incl. SLIM). Agents are of E; reconstructing G requires collusion among mul- addressed by persistent URL or structured name, so tiple independent parties. unlinkability is weak and a network observer or inThis targets the global view of a network observer N termediary obtains the edge directly. SLIM removes or a shared intermediary R, and follows Assumption 2. the central content-reading broker (an improvement over a single shared intermediary) but still routes by Definition 4 (Deniability). An interaction leaves no persistent name and provides no identifier freshness, transferable transcript that cryptographically binds a mixing, or deniability. 5
Transport HTTP(S) / current bindings SLIM / SLIMRPC SimpleX / SMP Tor onion services Mixnet (e.g. Nym)
Unlinkability
No central obs.
Deniability
Metadata min.
weak weak strong weak strong
weak partial strong strong strong
weak weak strong partial strong
weak weak partial partial strong
Cost low latency, mature low latency, maturing async, modest throughput moderate latency, mature high latency, emerging
Table 2: Candidate transports rated against the four wire-transport properties of §6; discovery privacy is a bootstrap-layer concern, addressed in §8. Ratings are qualitative; the point is the trade-off, not a score. SimpleX / SMP. Identity-less by construction: connections are bootstrapped out of band and carried over unidirectional queues with per-queue identifiers and no global account, giving strong unlinkability and, with separate and rotating relays, no single observer of the graph; deniability is a design goal. Its weak point is metadata minimization (a relay still sees the timing and volume of the queues it hosts), so traffic-analysis defenses are only partial. The model is asynchronous with modest throughput.
metadata-protecting binding is therefore expressible in principle. The instructive result is what one meets in trying: mapping A2A onto an identity-less transport (we use SMP) surfaces three implicit identity assumptions that the specification never states because, over HTTP, they always hold. Assumption 1: push notifications assume an HTTP-reachable client. A2A push delivers task updates to a client-provided webhook URL [1, §3.1.7], presuming the client has a stable, reachable address; an identity-less client has none. This is surmountable: server-initiated delivery re-maps onto the transport’s own asynchronous channel. At task creation the client supplies a reply queue it controls, and the server posts updates there. Because A2A already treats push as one of several interchangeable update mechanisms, the semantics are preserved; only the carrier changes.
Tor onion services. Strong at hiding network location and distributing trust across relays, but a published onion address is a persistent identifier, so unlinkability is weak when agents reuse addresses, and a global passive adversary can mount traffic correlation. Maturity is high, latency moderate. Mixnets (e.g. Nym). Purpose-built for metadata protection: per-packet unlinkable formats, distributed mixing, and cover traffic earn strong ratings on unlinkability, no-central-observer, and metadata minimization. The cost is high latency and lower maturity, precisely the trade-off a deployment must weigh.
Assumption 2: authentication is identity-based. A2A authentication is declared in the Agent Card and is identity-bearing (mutual TLS [1, §4.5.6], OAuth/OIDC, keys tied to a principal). An identityless transport cannot present a stable principal. This is the genuine mismatch: schemes that require a veriTakeaway. No transport provides all four wire- fiable persistent identity (a client certificate, an OIDC transport properties cheaply; they trace a pri- subject) do not translate. What does translate is a vacy/latency frontier. SMP is a strong first instan- different trust basis: channel binding from the out-oftiation because it is identity-less and ships today; a band handshake, plus capability- or credential-based mixnet is stronger on traffic analysis at a latency cost; authorization via selectively disclosed attestations Tor is the most mature but weakest on unlinkability. (§10). This establishes what a peer is entitled to The properties of §6, not any single transport, are the without fixing who it persistently is. portable target.
8
Case Study: A MetadataProtecting Binding for A2A
A2A is a useful case study because it already admits transports beyond its core set through custom protocol bindings, and because its operations are already asynchronous: an operation returns immediately and updates arrive by polling, streaming, or push. A 6
Assumption 3: discovery assumes addressable endpoints. A2A discovery resolves an Agent Card at a well-known URL [1] and selects a binding from its declared endpoint. With no addressable endpoint, both the card’s location and the endpoint it advertises must change form. This is surmountable but needs a different bootstrap: capabilities are exchanged out of band (an invitation carries or precedes the Agent Card), and the card declares a rendezvous or invitation mechanism in place of a URL. The capability content
of the card is unaffected; its addressing model is what never observed. To check realism, we anchor the gengives way. erator to a real capture from the A2A reference SDK, a live task lifecycle driven over HTTP, and confirm that it matches the lifecycle’s structure and scale. What the case study shows. Two of the three An adversary view projects a trace onto what a assumptions (push, discovery) are surmountable by single vantage point sees (Table 1). The registry view re-mapping onto asynchronous and out-of-band mechsees the semantic capability labels named in discovery anisms the transport already provides; one (identityqueries. The network view sees only opaque endpoint based authentication) is a semantic mismatch that identifiers, timing, volume, and direction, and no seforces a different, credential-based trust basis. None mantic labels. A classifier then predicts the latent is stated in the specification, because over an addresstask class. Following the website-fingerprinting trabased transport they hold for free. Naming them is dition [14], we treat its accuracy above chance as a useful independently of whether an identity-less bindconservative indicator of leakage: an unoptimized deing is ever standardized: they delimit exactly where coder can only understate it, so we deliberately leave it interoperability and persistent identity are entangled. untuned. Chance is 1/K for K balanced classes, and They are also where an adversary would act: discovery we report cross-validated accuracy with a bootstrap and push are the early, action-coupled steps whose 95% confidence interval. visibility enables the preemption of §5.
9.2
9
Empirical Evaluation
Leakage is recoverable in the model, and prospective
With K = 8 balanced classes, chance is 0.125. The registry view recovers the task class at 1.00, neartautologically, since it observes the labels directly. The result that matters is the label-blind network view, which recovers the class at 0.99 (Fig. 2). An observer of pure transport metadata is thus nearly as informed as one reading the advertised labels: persistent identifiers, together with capability-correlated timing and volume, let it reconstruct the capability footprint indirectly. This is the semanticity of §5 made concrete. Recovery is also prospective. Given only the first tenth of a workflow, the network view already predicts its class at 0.70, roughly 5.6× chance, and accuracy climbs toward certainty as more of the workflow is 9.1 Setup observed (Fig. 3). The opening of a workflow predicts its trajectory, exactly the predictive leverage §5 singles No public corpus of agent-interop traces exists, so out as distinctive to agent metadata. we sample workflows from a generative model of the A2A task lifecycle: discovery, delegation, streamed updates, completion. Each task class is a stochastic 9.3 The properties neutralize the leak, but only as a set process over capability-typed stages, drawn from a shared vocabulary with tunable overlap, so the set of We next realize the properties of §6 as transforms on capabilities alone does not identify the class. Several the observed traffic and re-measure (Fig. 4). On its agents serve each capability and some are multi-skill, own, each wire property barely moves the network obso a transport-visible identifier is not merely a relaserver. Unlinkability (fresh per-interaction identifiers) beled capability. Timing and size profiles attach to closes the persistent-identifier channel but leaves the capabilities rather than classes and are shared across timing and volume fingerprint, holding accuracy at them; all class signal therefore flows through which 0.95. Metadata minimization (padding and a batched capabilities are invoked and in what order. Each mescadence) closes timing and volume but leaves the sage yields the descriptor obs(m) of §3, and content is identifiers, holding it at 0.99. Only the two together 1 Code and data: https://github.com/dangoldbj/agent- collapse recovery, to 0.42. The registry view is a sepametadata-privacy. rate channel: neither wire property touches it, and it Two claims from the earlier sections invite a test. The threat model holds that graph metadata leaks pending workflow intent (§5); the property framework holds that a defined set of properties removes it (§6). We evaluate both, and then ask the third, decision-theoretic question the integrity framing demands: what the recovered signal is worth to an adversary that acts on it (§9.4). The aim is a controlled demonstration rather than a field measurement: that intent is recoverable from passive metadata, that it is recoverable early, and that the properties reduce recovery sharply toward chance, and only in combination.1
7
1.00
0.99
1.00
1.0
0.8
task-class accuracy
task-class accuracy
1.0
0.6 0.4 0.2 0.0
chance = 0.125 registry (semantic label)
network (label-blind)
0.6 0.4 registry (semantic label) network (label-blind) combined chance = 0.125
0.2 0.0
combined
Figure 2: Task class recovered from communicationgraph metadata, by adversary view (K = 8, chance 0.125; error bars are bootstrap 95% CIs). Even the label-blind network view, seeing only obs(m), recovers the class far above chance.
0.2
0.4 0.6 0.8 fraction of workflow observed
1.0
Figure 3: Prospectivity: accuracy as a function of the fraction of the workflow observed. From only its opening, the network view predicts the pending task class well above chance. κ = (Jinf − Jblind )/(Jorc − Jblind ), normalized so that 0 is the blind baseline and 1 the oracle; a ranking worse than random can fall below 0, and in our experiments κ ∈ [0, 1]. It is the share of the attainable advantage the adversary realizes from metadata alone.
falls only to discovery privacy (1.00 → 0.125, exactly chance). The threat therefore yields only to the full set of properties, each matched to a channel; partial measures do not suffice, a content-protecting binding that retains persistent names being one such case (§4). The residual 0.42 stays above chance because a structural channel remains: the message counts and sequence shape that the wire properties do not target and that cover traffic would address (§7).
9.4
0.8
We instantiate the game minimally, adding nothing to the generator. One task class is the adversary’s target, v(w) = 1 if w is of that class and 0 otherwise; the budget equals one class’s mass; the ranking is the network observer’s out-of-fold posterior on the target, from exactly the prefix features used in the preceding subsections. Then Jinf is the count of true target workflows among the top-B by that posterior, and Jblind and Jorc are closed-form; we average over the choice of target. What VoM and κ capture is selection leverage: the advantage of picking the right workflows to act on, from the opening alone. That is the precondition for changing outcomes, not proof that they change; the latter would mean acting against a live binding (§10). The value of metadata is substantial and, like the inference beneath it, prospective. Deciding from only the opening fifth of each workflow, the adversary captures κ ≈ 0.90 of the attainable advantage over the blind baseline (Fig. 5); from only the first tenth it already captures about two-thirds, climbing toward unity as more of the workflow is seen (Fig. 6, left). Under a budget, knowing the task early is most of the way to acting on it. Actuation is not a restatement of leakage. The value of metadata is the product of two independent factors (an early-decidable signal and a budget to spend), and collapses if either is absent: with no budget there is nothing to actuate, so VoM → 0 as
Actuation: the value of acting on the leak
Leakage and prospectivity are properties of recoverability: how much the metadata tells an observer about the task. Whether that knowledge bears on workflow integrity is a separate, decision-theoretic question, since an observer that cannot act on what it learns poses no integrity threat. We therefore model an adversary that must act under a budget and measure what the metadata is worth to it. Definition 7 (Actuation game and value of metadata). Among N concurrent workflows, each w carries an adversary value v(w) ≥ 0. By a decision deadline f , having observed only the leading fraction f of every workflow, a metadata-only adversary commits a budget of B interventions, P choosing a set S with |S| = B to maximize J(S) = w∈S v(w), and ranks workflows using the label-blind network view of the observed prefix alone. With Jinf , Jblind , and Jorc the objective under the metadata-informed, uniformly random, and true-value selections, the value of metadata is VoM(B, f ) = Jinf − Jblind and the capture ratio is 8
0.99
1.00
unlink.
1.00
0.95
1.00
meta-min
1.00
0.99
1.00
both (wire)
1.00
0.42
1.00
disc. privacy
0.12
0.99
0.99
all
0.12
0.42
0.42
registry (semantic label)
network (label-blind)
combined
1.0 0.9
1.0
0.8
0.8
0.7
capture ratio
1.00
accuracy
none
0.6 0.5 0.4
blind baseline (chance) = 0 0.90
0.83
0.92
0.6 0.4 0.2
0.3 0.2
0.90
0.11
0.11
0.0 none
unlink. meta-min
both (wire)
disc. privacy
all
Figure 4: Accuracy under each property (rows) for each adversary view (columns); red is leaking, green is protected. The network observer falls only when unlinkability and metadata minimization are combined (“both”); the registry observer falls only to discovery privacy. No single property suffices.
Figure 5: Actuation. Capture ratio κ by privacy property, at an early decision deadline (f = 0.2) and a budget equal to one task class’s mass, averaged over targets (error bars span ±1.96 standard errors across target classes; chance, the blind baseline, is 0). The integrity analogue of Fig. 4: only the combined wire properties (“both”) collapse the leverage, and discovery privacy, which the label-blind observer ignores, the budget shrinks (Fig. 6, right), and with no early does not. signal the ranking is uninformative and κ → 0. The axis is genuinely separate from recoverability, and website-fingerprinting, which bounds the signal factor value of metadata too. Two limitations are intrinsic. alone, does not speak to it. The workflows are simulated and calibrated to a small The defense carries over, and again only as a set. real capture rather than a labeled real corpus, so the Each wire property alone leaves the leverage near its magnitude is generator-dependent. And the actuaunprotected level (κ = 0.83 under unlinkability, 0.92 tion result (§9.4) measures leverage in the model: it under metadata minimization); the two together drive quantifies the advantage a budgeted adversary’s selecit to 0.12, essentially the blind baseline (Fig. 5). No- tion gains from metadata over the simulated workflow tably the leverage falls further than inference itself: population, the decision-theoretic core of the integrity under both properties the label-blind observer still threat, but stops short of a live exploit against a derecovers task class at 0.42 (Fig. 4), yet that residual ployed binding. The evaluation thus substantiates all labeling power buys almost no leverage, because select- three axes (semanticity, prospectivity, and actuation) ing the highest-value workflows under a tight budget and the efficacy of the properties against each; demondemands a precision the residual channel lacks. Dis- strating end-to-end manipulation on real agent traffic covery privacy, which does not touch the network view, is the natural next step. leaves κ unchanged, as expected. Selection leverage is downstream of inference: with recovery gone, there is nothing left to target. The integrity defense thus 10 Discussion follows from the privacy defense, since the properties that suppress what an observer can recover suppress 10.1 Reputation and trust without a the leverage it gains. global graph
9.5
A natural objection, especially in the current agent ecosystem, is that trust and reputation require persistent identity and an observable history of interactions, which metadata privacy appears to break. The tension is real but narrower than it first appears. It conflicts only with global-observation reputation: a registry or ledger that watches all interactions to compute scores. That design is fundamentally incompatible with unlinkability, and is itself a graph-
Robustness and scope
The effect is structural rather than tuned. Across sweeps of the number of classes, the capability overlap, and the timing noise, the network view stays 4–14× above chance, the short-prefix prediction stays above chance, and the two wire properties always collapse recovery. We therefore claim the structure of the effect, not its precise magnitude; this holds for the 9
350 Value of Metadata (workflows)
1.0
capture ratio
0.8 0.6
no protection unlinkability only both (wire) blind baseline = 0
0.4 0.2 0.0
300 250 200 150 100 50 0
0.2 0.4 0.6 0.8 1.0 decision deadline (fraction observed)
0.1
0.2 0.3 0.4 budget (fraction of workflows)
0.5
Figure 6: Actuation is the product of inference and budget, vanishing on either edge. Left: capture ratio against the decision deadline; leverage tracks prospectivity, is substantial even from a short prefix, and the combined wire properties hold it at the blind baseline. Right: value of metadata against budget (no protection, full workflow); it vanishes without a budget to spend and peaks where the budget is scarce relative to the target set, the signature of a value-of-information quantity. surveillance mechanism, i.e. the very asset of §3. It is compatible, however, with two other models. Under credential-based reputation, portable signed attestations are selectively disclosed: an agent proves “a verifier attests that I completed N tasks at quality q” without revealing whom it transacted with, so trust travels with the agent rather than being reconstructed from observed traffic. Under pairwise reputation, two agents accrue trust over their own repeated interactions with no global observer. Both align with the verifiable-credentials direction already pursued in the ecosystem; only the global-ledger variant conflicts, and credential-based approaches can provide privacypreserving alternatives while preserving the properties of §6. This is also the trust basis that the authentication mismatch of §8 requires.
10.2
Limitations
actuation against live agent traffic rather than within the model, are the natural next steps.
10.3
Because A2A exposes custom protocol bindings, a metadata-protecting binding can be introduced incrementally and selected per Agent Card, coexisting with HTTP and SLIM bindings rather than replacing them. Agents for which the communication graph is sensitive (regulated, competitive, or adversarial settings) can opt in, while latency-sensitive agents retain existing bindings. The threat model and properties are transport- and protocol-agnostic, so the same analysis applies to MCP and to other transports on the frontier of §7.
11
The properties of §6 are stated qualitatively; tightening them into adversary-indistinguishability games is future work. The strongest metadata protection (mixing, cover traffic) carries latency and bandwidth costs that may be unacceptable for interactive, low-latency agent calls; an identity-less transport also makes discovery and authentication harder, as §8 shows. Our evaluation (§9) measures inference and in-model actuation on simulated workflows anchored to a real capture; a reference binding with live wire measurements (latency, throughput, and an adversary’s reconstruction of G on real traffic), and a demonstration of
Deployment
Related Work
Threat modeling of agent-interop protocols. Recent work has begun to systematize agent-interop security. Comparative threat models examine MCP, A2A, Agora, and ANP for protocol-specific and crossprotocol risks [3, 12], and surveys map the interoperability landscape [9]. These analyses concentrate on authentication, identity, message injection, permissioning, and the leakage of sensitive payload data: for instance, the sensitive context streamed during delegation [11]. Our surface is complementary and, to our knowledge, not previously treated as a first-class
10
transport-layer security surface: the transport-level 12 Conclusion communication graph (who communicates with whom, when), which persists even when payloads are fully The communication graph of interoperating agents protected. remains exposed under today’s address-based bindings even with end-to-end payload encryption, and in agent systems it is more revealing than a privacy framPrivacy leakage in multi-agent systems. A par- ing suggests. Because endpoints are often capabilityallel line studies information leakage within multi- labeled, workflows are structured, and interactions are agent systems, showing that inter-agent channels leak action-coupled, the graph can leak pending workflows substantially more than output channels and that and hand an observer predictive leverage over machineprivacy controls must extend to inter-agent commu- speed action. The exposure runs to the integrity and nication [10, 16]. That work targets content-level contestability of autonomous workflows, not their prileakage between agents; we target the metadata of vacy alone. We gave a threat model for this surface, an account of what makes agent metadata distinctively the interactions themselves at the transport. revealing, transport- and bootstrap-layer properties against which any binding can be evaluated, an A2A Anonymous communication. The properties we case study in which pursuing those properties both require (unlinkability, no central observer, meta- surfaces and is constrained by the protocol’s implicit data minimization) originate in the anonymous- identity assumptions, and an empirical evaluation communication literature: mix networks [6], onion showing that the leakage is real and prospective, that routing [8], and modern mixnets such as Nym [13], this leakage carries decision-theoretic leverage (value surveyed broadly in [17]. Our contribution is not a to a budgeted adversary acting from a workflow’s new anonymity system but the application of these opening), and that the properties, applied together, properties to agent-interop transport and an analysis suppress both. A reference binding with live measureof what an interop protocol must give up to obtain ments, and a demonstration of actuation against live agent traffic rather than within the model, remain them (§8). open. Inference and preemption from metadata. That metadata enables semantic inference is established for encrypted traffic by website-fingerprinting attacks [14]; that observable pending intent enables preemption is established by front-running and minerextractable value in decentralized exchanges [7]. We argue (§5) that agent interoperability combines both, at machine speed, and our actuation result (§9.4) makes the bridge between them measurable: it casts the value of acting on recovered metadata as a decisiontheoretic quantity (the advantage a budgeted adversary gains over a blind baseline), distinct from recoverability, and shows that a transport defense must drive that value down, not merely reduce recovery. We draw on these literatures for the inference and preemption primitives rather than extend them.
References
Credentials and unlinkability. The reconciliation of §10 draws on selectively disclosed verifiable credentials, whose unlinkable presentation is an active area; the W3C threat model for decentralized credentials catalogs the relevant attack surfaces [18]. These mechanisms supply trust without a global interaction graph, complementing the transport-level properties developed here. 11
[1] A2A Project (Linux Foundation). Agent2agent (a2a) protocol specification, 2026. https://a2aprotocol.org/. [2] AGNTCY. SLIM: Secure low-latency interactive messaging, 2026. https://github.com/agntcy/ slim; IETF draft draft-mpsb-agntcy-slim. [3] Zeynab Anbiaee, Mahdi Rabbani, Mansur Mirani, Gunjan Piya, Igor Opushnyev, Ali Ghorbani, and Sajjad Dadkhah. Security threat modeling for emerging AI-agent protocols: A comparative analysis of MCP, A2A, Agora, and ANP, 2026. arXiv:2602.11327. [4] Anthropic. Model context protocol, 2025. https: //modelcontextprotocol.io/. [5] Richard Barnes, Benjamin Beurdouche, Raphael Robert, Jon Millican, Emad Omara, and Katriel Cohn-Gordon. RFC 9420: The messaging layer security (mls) protocol, 2023. https://www.rfceditor.org/rfc/rfc9420.
[6] David L. Chaum. Untraceable electronic mail, [17] Mohsen Shirali, Tobias Tefke, Ralf C. Staudereturn addresses, and digital pseudonyms. Commeyer, and Henrich C. Poehls. A survey on munications of the ACM, 24(2):84–90, 1981. anonymous communication systems with a focus on dining cryptographers networks, 2022. [7] Philip Daian, Steven Goldfeder, Tyler Kell, Yunqi arXiv:2212.08275. Li, Xueyuan Zhao, Iddo Bentov, Lorenz Breidenbach, and Ari Juels. Flash Boys 2.0: Fron- [18] W3C. Threat model for decentralized cretrunning in decentralized exchanges, miner exdentials, 2026. W3C, 20 January 2026. tractable value, and consensus instability. In https://www.w3.org/TR/threat-modelIEEE Symposium on Security and Privacy (S&P), decentralized-credentials/. 2020. [8] Roger Dingledine, Nick Mathewson, and Paul Syverson. Tor: The second-generation onion router. In USENIX Security Symposium, 2004. [9] Abul Ehtesham, Aditi Singh, Gaurav Kumar Gupta, and Saket Kumar. A survey of agent interoperability protocols: Model context protocol (MCP), agent communication protocol (ACP), agent-to-agent protocol (A2A), and agent network protocol (ANP), 2025. arXiv:2505.02279. [10] Faouzi El Yagoubi, Godwin Badu-Marfo, and Ranwa Al Mallah. AgentLeak: A full-stack benchmark for privacy leakage in multi-agent LLM systems, 2026. arXiv:2602.11510. [11] Yedidel Louck, Ariel Stulman, and Amit Dvir. Improving Google A2A protocol: Protecting sensitive data and mitigating unintended harms in multi-agent systems, 2025. arXiv:2505.12490. [12] Yedidel Louck, Ariel Stulman, and Amit Dvir. Security analysis of agentic AI communication protocols: A comparative evaluation, 2025. arXiv:2511.03841. [13] Nym Technologies. The Nym network: The next generation of privacy infrastructure, 2021. Whitepaper. https://nym.com/nymwhitepaper.pdf. [14] Andriy Panchenko, Lukas Niessen, Andreas Zinnen, and Thomas Engel. Website fingerprinting in onion routing based anonymization networks. In ACM Workshop on Privacy in the Electronic Society (WPES), 2011. [15] Evgeny Poberezkin. SimpleX messaging protocol (SMP), 2024. https://github.com/simplexchat/simplexmq/blob/stable/protocol/ simplex-messaging.md. [16] Christian Schroeder de Witt, Klaudia Krawiecka, et al. Open challenges in multi-agent security: Towards secure systems of interacting AI agents, 2025. arXiv:2505.02077. 12