What communication invariants prevent message replay in a decentralized agent swarm?

**Date of Record:** 2026 October 27 **Scope:** Applies when autonomous agents in a decentralized swarm communicate messages that drive state mutations, and an attacker could capture and replay these messages to cause duplicate actions, without any central nonce authority. Does not apply to centralized systems with a single message broker enforcing nonces, or strictly idempotent commutative operations.

Core Distinction

The separation between **message authenticity** (the message was signed by a legitimate agent) and **message freshness** (the message has not been replayed from a previous epoch). Relying solely on authenticity creates the **Decentralized Replay Trap**: an attacker captures a legitimately signed message and replays it in a new context, causing the receiving agent to execute the action twice. Preventing replay in a decentralized swarm requires combining vector clocks with cryptographic timestamps.

What Was Observed

In decentralized agent protocols (swarms, mesh networks, peer-to-peer), failing to prevent replay produces three primary failure modes:

  1. **Double-Execution:** An attacker replays a "transfer funds" message. The receiver executes the transfer twice, draining funds.
  2. **State Rollback:** An attacker replays an old state update message, causing the receiving agent to revert to a stale state that was previously superseded.
  3. **Vote Stuffing:** An attacker replays a vote message from a legitimate agent, inflating the vote count and corrupting consensus.

Recorded Elements

  1. **`vector_clock_signature`:** The sender's vector clock at message creation time, capturing the sender's causal context and allowing the receiver to detect stale messages.
  2. **`cryptographic_timestamp_proof`:** A cryptographic timestamp (e.g., from a trusted timestamping authority or a linked blockchain) proving the message was created at a specific epoch.
  3. **`message_deduplication_bloom_filter`:** A locally maintained Bloom filter of recently seen message IDs, allowing the receiver to quickly detect replay without persistent storage of all messages.
  4. **`epoch_freshness_window`:** The maximum acceptable age of a message, beyond which it is rejected as expired even if authentic.

Condition of Validity

* **Applies when:** The swarm is decentralized, messages drive non-idempotent state mutations, and an attacker can capture and replay messages. * **Does not apply when:** The swarm is centralized (single broker enforces nonces), or the messages are strictly idempotent and commutative (replay has no effect).

Decision Boundary

  1. **Is the message ID present in the `message_deduplication_bloom_filter`?** If yes, the message is a replay. Reject immediately.
  2. **Does the `vector_clock_signature` indicate that the message is older than the receiver's current vector clock?** If yes, the message may be stale (from a superseded context). Reject or queue for out-of-order handling.
  3. **Does the `cryptographic_timestamp_proof` show the message is within the `epoch_freshness_window`?** If no, the message is expired. Reject.
  4. **Conversely, when can a receiver accept a message without replay checks?** Only when the message is strictly idempotent, or when the swarm enforces a global nonce authority via consensus, or when the message arrives via a transport that guarantees single-delivery semantics.

Operational Effect

  1. **Replay Prevention:** Blocks captured messages from being re-executed, preventing double-spending and state corruption.
  2. **Causal Consistency:** Uses vector clocks to detect stale messages, ensuring the receiver's state reflects the sender's causal context.
  3. **Bounded Storage:** Uses Bloom filters and epochs to prevent replay without unbounded storage of message history.
from dataclasses import dataclass
from enum import Enum, auto
import hashlib
import json

class ReplayVerdict(Enum):
    FRESH_MESSAGE = auto()
    REPLAY_DETECTED = auto()
    STALE_MESSAGE = auto()
    EXPIRED_MESSAGE = auto()

@dataclass(frozen=True)
class SwarmMessage:
    message_id: str
    sender_vector_clock_hash: str
    timestamp_epoch: float
    signature: str

@dataclass(frozen=True)
class ReceiverState:
    seen_message_hashes: frozenset[str]
    current_vector_clock_hash: str
    current_epoch: float
    freshness_window_sec: float

@dataclass(frozen=True)
class ReplayManifest:
    verdict: ReplayVerdict
    directive: str
    manifest_digest: str

class DecentralizedReplayGuard:
    @staticmethod
    def _hash(data: str) -> str:
        return hashlib.sha256(data.encode("utf-8")).hexdigest()

    @classmethod
    def evaluate_message(
        cls, msg: SwarmMessage, state: ReceiverState
    ) -> ReplayManifest:
        
        # Gate 1: Deduplication
        if msg.message_id in state.seen_message_hashes:
            return ReplayManifest(
                verdict=ReplayVerdict.REPLAY_DETECTED,
                directive=f"HALT: Message {msg.message_id} already seen. Replay attack.",
                manifest_digest=cls._hash(f"REPLAY:{msg.message_id}")
            )

        # Gate 2: Freshness window
        age = state.current_epoch - msg.timestamp_epoch
        if age > state.freshness_window_sec:
            return ReplayManifest(
                verdict=ReplayVerdict.EXPIRED_MESSAGE,
                directive=f"HALT: Message is {age:.0f}s old, exceeding {state.freshness_window_sec:.0f}s window.",
                manifest_digest=cls._hash(f"EXPIRED:{msg.message_id}")
            )

        # Gate 3: Vector clock
        if msg.sender_vector_clock_hash == state.current_vector_clock_hash:
            # Same clock = likely stale or replayed
            return ReplayManifest(
                verdict=ReplayVerdict.STALE_MESSAGE,
                directive=f"HALT: Message vector clock matches current. Likely stale.",
                manifest_digest=cls._hash(f"STALE:{msg.message_id}")
            )

        # Gate 4: Fresh
        digest = cls._hash(json.dumps({
            "message": msg.message_id,
            "timestamp": f"{msg.timestamp_epoch:.0f}",
            "clock": msg.sender_vector_clock_hash
        }, sort_keys=True))
        
        return ReplayManifest(
            verdict=ReplayVerdict.FRESH_MESSAGE,
            directive="PROCEED: Message is fresh and not a replay.",
            manifest_digest=digest
        )