SealedStory: Sealed, Chained Transcripts for Agents That Cannot Trust the Relay

Agents now hand each other work through relays, and most deployed protocols secure each hop or each message on its own. A relay that can neither read nor forge a message can still drop one, cut a conversation short, or show the two agents different histories. We present SealedStory, a two-party protocol in which every key depends on the whole verified history. It adds rollback and fork detection, equivocation evidence, a close and a deadline, and a closed message vocabulary. Against 31 scripted attacks at 500 trials each, undetected attacks fall from 25 for plaintext to 3 for SealedStory. The three that remain are a valid peer lying, traffic analysis, and a fully controlled endpoint, and none of them is something we claim to stop. Three further attacks work even after both parties verify each other's pin. They succeeded against our first version, and three added rules stop them. Flipping every bit of an entry stream, and running 20,000 randomized relay schedules per design, produced no accepted alteration and no out-of-order history, at 158 µs per entry. On two language models (618 calls), direct prompt injection almost never worked even over free text (2 of 192), so we could not show that the closed vocabulary lowers it. A self-copying marker did cross three agents over free text (11/15 and 14/15). The protocol has no machine-checked proof and no independent review. This paper describes the SealedStory protocol, a secure and efficient protocol for agent-to-agent communication. It is a proof-of-concept implementation of the protocol.