FlagThis

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 protocols 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 interactions 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 workflows 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.