Attacks and Defenses in Decentralized Multi-Agent Systems with Hop-by-Hop Task Decomposition and Delegation

Matthew D. Laws, Maria Lazou, Alina Oprea, Cristina Nita-RotaruarXiv 2026 · arXiv

TL;DR

Decentralized multi-agent LLM systems are highly efficient but vulnerable to "inside jobs" where a single malicious agent can derail tasks or steal data. This paper introduces a cryptographic Verified Execution Trace protocol and an LLM-powered auditor that together detect and attribute 98% of such attacks with virtually zero performance overhead.

What Problem Does This Paper Address?

We are moving toward a world of "agentic" workflows where multiple Large Language Models (LLMs) collaborate to solve complex problems. In a Decentralized Multi-Agent System (DMAS), these agents might belong to different companies, run different models, and have different private memories.

The most flexible way for them to work is "hop-by-hop": Agent A does a bit of work, decides what’s left, and passes it to Agent B. There is no central "boss" or orchestrator. While this is great for scalability and privacy, it’s a security nightmare. Because no single entity sees the whole execution path, a malicious agent can:

  • Rewrite the task: Change "book a flight to London" to "send $1000 to my account."
  • Sabotage availability: Intentionally send the task to the least capable agent to waste time and money.
  • Steal data: Trick other agents into revealing their private system prompts or past memories.

Prior security work focused on centralized systems. This paper tackles the "wild west" of decentralized, autonomous delegation.

Figure 1: Benign (a) and compromised (b) hop-by-hop decomposition and delegation.

Methods

The authors propose a two-layered defense strategy:

  1. Verified Execution Trace (VET) Protocol: This is a lightweight cryptographic layer. Every time an agent receives a task, performs a subtask, and delegates the rest, it must sign its actions. Crucially, it includes a cryptographic hash of the previous agent's message. This creates a "hash chain"—similar to a blockchain—that makes the entire history of the task tamper-evident. If an agent tries to delete a step or change what a previous agent said, the chain breaks.
  2. The Auditor: Once a task is finished, the user (or a third party) can run an auditor.
  3. Cryptographic Verification: It first checks the signatures and hash chain to ensure the "plumbing" of the protocol wasn't tampered with.
  4. Semantic Verification: This is the clever part. Even if an agent follows the protocol perfectly, it could still lie (e.g., providing a wrong answer). The auditor uses a frontier LLM (like GPT-4 or the paper's gpt-6.1-sol) to review a restructured text summary of the trace. It looks for logical inconsistencies or "adversarial" behavior that cryptography alone can't catch.
Figure 2: Hop-by-hop system with our Verified Execution Trace protocol. Every message is appended with additional metadata, including the prior hash, and signed by the sender. Agents verifies incoming messages before proceeding (Section 4.2). The auditor, invoked by the user, verifies the hash chain and the semantic properties of the trace (Section 4.3).

Datasets

The researchers evaluated their system using HiddenBench, a benchmark designed for multi-agent reasoning. In HiddenBench, a task is split into $N$ pieces of information distributed across different agents. No single agent has enough info to solve the task alone, forcing them to collaborate.

They tested the attacks and defenses using two primary models:

  • gpt-6.1-sol: A high-performance proprietary model.
  • Qwen3.8-27B-FP8: A capable open-weight model.

Key Insights and Ideas

  • Cryptography is necessary but insufficient: You can cryptographically prove who said what, but you can't prove they weren't lying. The "aha moment" here is combining rigid crypto-signatures with the "common sense" of an LLM auditor to catch semantic attacks.
  • Attribution is the goal: In a decentralized system, you might not be able to stop a malicious action in real-time, but if you can irrefutably prove who did it, you can kick them out of the collective or lower their reputation score.
  • The "Context Bloat" Attack: One of the most effective availability attacks is simply padding a task with thousands of tokens of "garbage" text. This forces every downstream agent to pay for and process those tokens, exponentially increasing the cost of the task.

Key Results

  • Devastating Attacks: A single malicious agent in an undefended system can cause 100% task failure. It can also inflate token costs by 7.7x and runtime by 3.2x.
  • High-Fidelity Detection: The proposed auditor detects and correctly attributes 98% of attacks.
  • Negligible Overhead: The cryptographic operations (signing and hashing) add only milliseconds to tasks that typically take 20–100 seconds to execute. The "cost" of security is essentially free compared to the cost of the LLM inference itself.
  • Data Leakage: Without defenses, malicious agents successfully exfiltrated up to 94% of relevant prior task data from benign agents.

Limitations and Future Work

  • Collusion: The current model assumes malicious agents do not coordinate. If two agents collude, they could potentially "launder" malicious actions more effectively.
  • Detection vs. Prevention: The VET protocol is an auditing tool—it catches bad actors after the fact. Developing real-time "firewalls" for decentralized agents remains an open challenge.
  • Auditor Intelligence: The semantic auditor needs to be at least as "smart" as the agents it is auditing. If attackers use more sophisticated "jailbreaking" or "prompt injection" techniques, the auditor might be fooled.
  • DAG Support: While the paper focuses on sequential "hop-by-hop" chains, the authors note the protocol can be extended to Directed Acyclic Graphs (DAGs) for parallel task execution, though this wasn't the primary focus of the evaluation.

Summary updated

Abstract

Decentralized multi-agent LLM systems enable independently administered agents, each with its own operator, model, memory, and configuration, to collaborate on complex tasks without centralized coordination. Agents autonomously decompose tasks, execute subtasks and delegate remaining work to peers, enabling scalability and eliminating single points of failure. However, decentralization also introduces significant security challenges, as no single entity has complete visibility into task execution or the authority to enforce correct behavior across agents. In this paper, we systematize threats from malicious agents in decentralized multi-agent systems and propose mitigation techniques. We first design and evaluate attacks against integrity, availability, and confidentiality, demonstrating that a single malicious agent can cause up to 100% task failure, inflate token consumption and runtime by up to 7.7x and 3.2x, respectively, and exfiltrate up to 94% of relevant prior tasks from benign agents. We then present a cryptographic protocol that produces an irrefutable verified execution trace of every action taken in the system and develop an auditor that analyzes these traces to detect and attribute malicious behavior. Evaluations on HiddenBench using gpt-6.1-sol and Qwen3.8-27B-FP8 show that our protocol incurs negligible latency overhead, while the auditor detects and correctly attributes 98% of attacks, including those that comply with the protocol.
BibTeX
@misc{laws2026attacks,
  author = {Matthew D. Laws and Maria Lazou and Alina Oprea and Cristina Nita-Rotaru},
  title = {{Attacks and Defenses in Decentralized Multi-Agent Systems with Hop-by-Hop Task Decomposition and Delegation}},
  year = {2026},
  eprint = {2611.25056},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.25056},
}
Figure