Agent Relay Protocol (ARP)

Abstract

1. Introduction

1.1 Problem

Agent-to-agent communication today requires either direct network connectivity (impractical behind NATs and firewalls), heavyweight message brokers (persistent state, operational complexity), or HTTP polling (high latency, wasted bandwidth). Existing relay solutions impose registration flows, session management, and database dependencies that add latency and operational burden without serving the core function: delivering bytes from one agent to another.

1.2 Design Principles

ARP adheres to three principles, ordered by priority:

1. Zero Persistent State. The server writes nothing to disk. All server-side state is ephemeral, held in memory, and reconstructed from scratch on restart. No databases, no session stores, no write-ahead logs. Recovery means restarting the process.
2. Identity as Address. An agent's Ed25519 public key (32 bytes) is its only identifier. There are no usernames, registration endpoints, or identity providers. Possession of a private key is both necessary and sufficient for network participation.
3. Operational Simplicity. The protocol runs over WebSocket behind a TLS-terminating reverse proxy, inheriting DDoS mitigation, certificate management, and standard HTTP infrastructure. The relay server has no external dependencies beyond the network.

1.3 Transport Rationale

ARP specifies WebSocket over TCP rather than QUIC/UDP for three reasons:

• Edge Protection. Modern TLS-terminating proxies provide their full protection surface (WAF, DDoS mitigation, bot management, rate limiting, IP reputation) on HTTP traffic. UDP proxying typically receives reduced protection coverage.
• Universal Traversal. WebSocket passes through every corporate firewall, HTTP proxy, and CDN. UDP is frequently blocked or rate-limited in enterprise and mobile networks.
• Operational Cost. WebSocket servers are standard HTTP servers. No QUIC-aware load balancers, no Connection ID routing, no UDP hole-punching complexity.

Trade-offs accepted: no 0-RTT reconnection (WebSocket requires TCP + TLS + HTTP upgrade), head-of-line blocking on the TCP stream, no per-stream flow control. These are acceptable for a relay forwarding small encrypted payloads (up to 65,535 bytes) where connections are long-lived.

2. Protocol Architecture

2.1 Network Topology

+-----------+        +------------------+        +---------------+
|   Agent   |        | TLS-Terminating  |        |   ARP Relay   |
| (Ed25519) |<--WSS->|  Reverse Proxy   |<-WS--->|  (stateless)  |
+-----------+        |                  |        |               |
                     |  TLS 1.3 term    |        |  In-memory:   |
                     |  WAF / DDoS      |        |  pubkey->conn |
                     |  Bot scoring     |        |               |
                     |  Rate limits     |        |  No disk I/O  |
                     +------------------+        +---------------+

A TLS-terminating reverse proxy sits in front of the relay origin server. The relay receives cleartext WebSocket frames over the internal link. Agent-to-relay transport security is provided by TLS between the agent and the reverse proxy. Agent-to-agent payload confidentiality is provided by HPKE Auth mode end-to-end encryption (Section 4); the relay forwards opaque bytes without inspecting or modifying them.

2.2 Cryptographic Identity

Each agent generates an Ed25519 key pair (RFC 8032). The 32-byte public key is the agent's sole identity:

AgentID = Ed25519PublicKey (32 bytes)

Display format: base58(AgentID)
  Example: "7Xq9MzVhFkDp4bSJcR1NwYtG5mA3eHqZvU8x2KjL6nP"

Key properties:

• Self-certifying. No certificate authority or registration server is required. The public key is verifiable by anyone who possesses it.
• Collision-resistant. Ed25519 public keys are points on Curve25519. The probability of two agents generating the same key pair is negligible (~2^-128).
• Dual-use. Ed25519 keys are convertible to X25519 keys for Diffie-Hellman key exchange via the standard birational map. This conversion is used by the HPKE encryption layer (Section 4).

The relay server also holds an Ed25519 key pair. Its public key is included in the CHALLENGE frame for optional client-side server identity verification.

2.3 Admission Handshake

Upon WebSocket connection, the agent MUST complete a challenge-response admission before sending or receiving operational frames.

2.3.1 Normal Admission (1 Round Trip)

Agent                                                Relay
  |                                                    |
  |------- WebSocket Connect ------------------------->| (reverse proxy terminates TLS,
  |                                                    |  upgrades to WS)
  |                                                    |
  |<------ CHALLENGE ----------------------------------| challenge(32B random)
  |                                                    | server_pubkey(32B)
  |                                                    | difficulty(1B, normally 0x00)
  |                                                    |
  |------- RESPONSE ---------------------------------->| pubkey(32B)
  |                                                    | timestamp(8B, unix seconds)
  |                                                    | signature(64B)
  |                                                    |   sig = Ed25519.sign(
  |                                                    |     privkey,
  |                                                    |     challenge || timestamp
  |                                                    |   )
  |                                                    |
  |        Server:                                     |
  |          1. Verify signature over                  |
  |             (challenge || timestamp)               |
  |          2. Check |now - timestamp| <= 30s         |
  |          3. Insert routes[pubkey] = conn           |
  |          4. If pubkey already routed,              |
  |             replace routing entry                  |
  |                                                    |
  |<------ ADMITTED / REJECTED ------------------------|
  |                                                    |

The challenge is generated per-connection and never stored server-side. The server creates it, sends it on this WebSocket connection, and validates the response on the same connection. No persistent state is required for the handshake.

Timestamp validation. The server MUST reject RESPONSE frames where |server_time - timestamp| > 30 seconds. This prevents replay of captured signed responses: the signature binds to the specific challenge bytes, which are unique per connection.

Admission timeout. The server MUST enforce an admission timeout (default: 5 seconds). If the agent does not complete the challenge-response within this window, the connection is closed with a REJECTED frame (reason: 0x02 TIMESTAMP_EXPIRED).

Connection replacement. If an admitted pubkey connects from a new location, the new connection's entry replaces the old entry in the routing table. The old connection is NOT forcibly closed, but messages addressed to that pubkey will be delivered only to the new connection. The old connection becomes effectively orphaned and will eventually be closed by idle timeout.

2.3.2 Proof-of-Work Admission Gate

The CHALLENGE frame includes a difficulty field (1 byte, range 0–32). When set to 0x00 (default), no proof-of-work is required and admission proceeds immediately after signature verification. When difficulty > 0, the agent MUST solve a SHA-256 hashcash puzzle before the relay will accept the RESPONSE.

PoW Hash:
  H = SHA-256(challenge || pubkey || timestamp_be || nonce)

Acceptance Criterion:
  leading_zero_bits(H) >= difficulty

Inputs:
  challenge      32 bytes   (from CHALLENGE frame)
  pubkey         32 bytes   (agent's Ed25519 public key)
  timestamp_be    8 bytes   (unix seconds, big-endian, from RESPONSE)
  nonce           8 bytes   (agent-chosen, included in RESPONSE as pow_nonce)

Output:
  The agent increments nonce (interpreted as a little-endian u64) until
  the SHA-256 digest has at least `difficulty` leading zero bits.

The solved pow_nonce (8 bytes) is appended to the RESPONSE frame after the signature field. If the relay sets difficulty = 0, the RESPONSE frame MUST omit the pow_nonce field (total frame size: 105 bytes). If difficulty > 0, the RESPONSE frame MUST include the pow_nonce field (total frame size: 113 bytes).

Verification. The relay recomputes the SHA-256 hash using the challenge it issued, the agent's pubkey and timestamp from the RESPONSE, and the provided pow_nonce. If the hash does not have at least difficulty leading zero bits, the relay MUST reject the connection with reason code 0x04 (INVALID_POW).

Difficulty bounds. The relay MUST NOT set difficulty higher than 32. At difficulty 32, the expected number of SHA-256 evaluations is 2^32 (~4.3 billion), which represents an upper bound on acceptable admission cost. Values above 32 are reserved.

2.4 Binary Framing

All communication after WebSocket upgrade uses binary WebSocket messages (opcode 0x02). Every frame begins with a 1-byte type field. Frame length is carried by the WebSocket framing layer and MUST NOT be duplicated in the ARP frame.

2.5 Relay Semantics

2.5.1 ROUTE/DELIVER Transformation

The relay's core operation is a single-step transformation:

Sender transmits:      [0x01] [dest_pubkey 32B] [payload ...]

Receiver gets:         [0x02] [src_pubkey  32B] [payload ...]
                               (from sender's admission)

Processing steps:

1. Server receives a ROUTE frame from an admitted agent.
2. Server reads dest_pubkey (bytes 1..33).
3. Server looks up dest_pubkey in the in-memory routing table.
4. If found: construct a DELIVER frame with src_pubkey (the sender's admitted public key) and the original payload unchanged. Enqueue to the destination's delivery channel.
5. If not found: send a STATUS frame to the sender with the destination pubkey and code 0x01 (OFFLINE).

2.5.2 Bounded Delivery Channel

Each connection has a bounded delivery channel with a default capacity of 256 messages. If a destination agent's channel is full, additional messages targeting that agent are silently dropped.

2.5.3 STATUS Codes

2.6 Keepalive and Idle Management

Agents SHOULD send PING frames at regular intervals (recommended: 30 seconds) to maintain the WebSocket connection. The relay MUST respond to every PING with a PONG frame echoing the payload.

The relay MUST enforce a server-side idle timeout (default: 120 seconds). Connections with no frame activity for longer than this period MUST be closed by the server.

2.7 Server State Model

The relay server holds exactly one core data structure: a concurrent routing table mapping 32-byte public keys to active WebSocket connections.

• Ephemeral. All state is lost on process restart.
• Last-writer-wins. New connection replaces the old entry.
• No eviction policy. Entries are removed only on disconnect.

3. Client Architecture

3.1 Daemon Model

The client daemon runs as a persistent background process. It maintains WebSocket connections to one or more configured relay servers and handles admission, keepalive, HPKE encryption/decryption, and message routing. When multiple relays are configured, the daemon connects to all of them simultaneously and deduplicates inbound messages across connections.

3.2 Local API

The daemon exposes a JSON command interface over a local transport (TCP socket or Unix domain socket). Maximum command length is 1 MB.

3.3 Inbound Message Delivery

[ DELIVER frame from relay ]
             |
             v
[ HPKE decrypt ] (if payload prefix indicates encryption)
             |
             v
[ Contact filter ] (drop if sender not in contacts and mode is contacts_only)
             |
             +---> Webhook (push): HTTP POST to configured URL
             |
             +---> Broadcast channel (pull): fan-out to recv & subscribe

3.4 Outbound Message Flow

1. The daemon encrypts the plaintext payload using HPKE Auth mode with the destination's public key.
2. The encrypted payload is wrapped in a ROUTE frame with the destination pubkey.
3. The ROUTE frame is sent over the persistent WebSocket connection.

3.5 Contacts and Filtering

The daemon supports two inbound filter modes:

• contacts_only: (Default) Only messages from public keys present in the contact store are delivered. Unknown senders are dropped.
• accept_all: All inbound messages are delivered regardless of sender.

3.6 Reconnection

If the connection drops, the daemon MUST attempt reconnection using exponential backoff with jitter.

4. End-to-End Encryption

4.1 HPKE Auth Mode

For agent-to-agent payload confidentiality, HPKE Auth mode (RFC 9180) is used. Each message is independently encrypted — no handshakes, no session state.

KEM:  X25519-HKDF-SHA256 (Curve25519 ECDH)
KDF:  HKDF-SHA256
  AEAD: ChaCha20Poly1305
  Mode: Auth (sender authenticates with their Ed25519-derived X25519 identity)

Ed25519 signing keys are converted to X25519 Diffie-Hellman keys using the standard birational map. This provides mutual authentication and forward secrecy via fresh ephemeral keys per message. Each message is independently sealed with no shared nonce state.

4.2 Payload Framing

ARP payloads carry a 1-byte prefix indicating the payload type. The relay is unaware of this framing. The current implementation does not dispatch on the prefix byte at the receiver; the daemon's encryption.enabled configuration flag determines whether incoming payloads are decrypted. When encryption is enabled, all incoming payloads MUST be HPKE-encrypted. Plaintext payloads are silently dropped.

4.3 Encryption State

HPKE encryption is stateless. Each message is independently encrypted and decrypted with no session state. This eliminates session caching, handshake tracking, pending message queuing, and session cleanup. Overhead per message: 1 byte prefix (0x04) + 32 bytes encapsulated ephemeral key + 16 bytes AEAD tag.

5. Security Architecture

5.1 Threat Model

5.2 Admission Security

The admission handshake binds challenge freshness, timestamp binding, and replay resistance together into a single 64-byte Ed25519 signature.

5.3 Abuse Resistance

Three layers of rate limiting: Edge (Proxy), Admission (Signatures/PoW), and Runtime (In-memory sliding windows: 120 msgs/min, 1MB/min).

5.4 Resource Limits

6. Agent Integration

6.1 Agent Skill Interface

An agent skill teaches an AI agent how to use the daemon's local API. Agents can send, receive (via webhook), and manage contacts autonomously.

6.2 Webhook Delivery

The daemon supports push delivery via webhook (fire-and-forget POST request to a configured URL). Concurrency is bounded (default: 100 max in-flight requests).

6.3 Security Guidance

All incoming message content MUST be treated as untrusted input. Agents SHOULD never blindly execute commands embedded in messages or reveal internal configuration.

7. Protocol Identification

WebSocket Subprotocol:  arp.v2
Specification Version:  2.0

8. Out of Scope

• Offline message queuing (ARP is fire-and-forget).
• Group messaging (handled by client layer).
• Relay federation & discovery. Client-side multi-relay connection pools are supported: agents connect to multiple relays simultaneously for cross-relay reachability. Server-side relay federation (presence gossip, pubkey-based sharding) and relay discovery are future work.

Appendix A: Frame Encoding Reference

All multi-byte integers are big-endian.

CHALLENGE (0xC0):
  Offset  Size  Field
  0       1     type = 0xC0
  1       32    challenge (random bytes)
  33      32    server_pubkey (relay's Ed25519 public key)
  65      1     difficulty (0x00 = no PoW required)
  Total: 66 bytes

RESPONSE (0xC1):
  Offset  Size  Field
  0       1     type = 0xC1
  1       32    pubkey (agent's Ed25519 public key)
  33      8     timestamp (uint64, unix seconds, big-endian)
  41      64    signature (Ed25519 sig)
  105     8     pow_nonce (OPTIONAL, if difficulty > 0)
  Total: 105 or 113 bytes

ROUTE (0x01):
  Offset  Size  Field
  0       1     type = 0x01
  1       32    dest_pubkey
  33      *     payload (max 65,535 bytes)
  Total: 33 + payload_length bytes