feat(protocol): cross-signing trust graph + identity pinning for multi-host agents

[hartsock]

Motivation

agent-mesh's trust model is deliberately broker-less: there is no homeserver, no key directory, no central authority. Two agents on the same LAN trust each other because their cert chains both root at the same per-user ed25519 UserKey. This is the right foundation — it keeps the mesh sovereign and LAN-first. But the trust graph it produces is flat and append-only-naive:

• Flat: every agent is either "mine" (same user_fingerprint) or "not mine." There is no intermediate identity, so the question "is this agent genuinely one of mine, running on my other host?" collapses into the same single bit as "is this any agent of mine at all?" A compromised host's agent key is indistinguishable from a legitimate one on a different host — both present a valid chain to the same root.
• No rotation detection: the auto-team rule (ensure_trustable in agent-mesh-transport/src/handshake.rs:119) verifies the chain and compares peer_user_fp == our_user_fp. It has no memory of which root key it expected to see. If an attacker presents a chain rooting at a different UserKey but somehow induces us to treat that key as ours (e.g. a swapped on-disk key after a host compromise, or a first-contact MITM before any GitHub binding is checked), nothing flags the change. Trust-on-first-use is implicit and the "use" is never pinned.

matrix-rust-sdk — explicitly a reference implementation to learn from, not a dependency — solved exactly these two problems years ago with cross-signing key hierarchies and identity pinning. We can adopt the shape of their solution while staying broker-less. This issue proposes the software trust-graph layer. The companion human-verified cross-USER step (numeric SAS / channel binding) is spike #30; cross-user trust stays gated behind a future "pact" and is out of scope here.

Current state

Verified against the code at /home/hartsock/workspaces/agent-mesh:

The hierarchy is two levels, flat.

• UserKey (agent-mesh-protocol/src/user_key.rs) — one per user, the sole root of trust. ed25519, PKCS#8 PEM on disk at 0600, zeroized on drop. Cross-signed to a GitHub SSH identity via GitHubBinding (github_binding.rs), which proves "this UserKey is held by the person who controls github.com/" — but this binding is a one-time identity anchor, not consulted on every handshake.
• AgentKey (agent_key.rs) — per-process, ephemeral, never persisted (AgentKey::issue, no save/load). Each carries a CertChain.
• CertChain (agent_key.rs:191) — Issuer::User(UserPublic) at the root, or Issuer::Agent { pubkey, parent } for delegated sub-agents. verify() (agent_key.rs:213) re-checks attenuation (caveats.leq) at every link and walks to the root user via root_user_pubkey() / user_fingerprint().

There is no per-host or per-device identity between UserKey and AgentKey. AgentMetadata.host (agent_key.rs:147) is a free-text claim — it's covered by the user's signature so it can't be tampered with post-issue, but it is not a key, carries no independent authority, and is never cross-checked against a host-level credential. Two agents on different hosts are cryptographically identical modulo that string.

The trust gate is stateless. ensure_trustable (handshake.rs:119) does exactly two things: peer_cert.verify(), then peer_user_fp != our_user_fp → DifferentUser. our_user_fp is recomputed from our own cert on every handshake (handshake.rs:74); there is no stored notion of "the root key I have trusted before for this peer." A swapped root that presented an internally-valid chain would pass verify(); it would only be caught by the != our_user_fp comparison if it differed from ours — and a host-compromise scenario where our own on-disk UserKey was replaced defeats even that.

Envelopes are signed-only, not encrypted. SignedEnvelope (envelope.rs:44) carries cert_chain + agent_sig (ed25519 over ENVELOPE_TAG || recipient || nonce || sequence || payload_cid) + a BLAKE3 payload_cid. verify() (envelope.rs:85) checks the chain, the CID-matches-payload, and the agent signature. The payload is not encrypted — confidentiality rides entirely on the iroh QUIC/TLS transport session. There is also no provenance object attached to an inbound envelope recording how much we trust its sender beyond "the chain verified": the receiver gets a binary valid/invalid, not a trust ladder.

Proposed design

Three additions, all opt-in and backward compatible (the wire types gain optional fields gated by #[serde(default)], exactly as caveats was added in agent_key.rs:168). No broker, no key directory — every credential below is still carried in-band on the cert chain and rooted at the same UserKey.

1. Host-key hierarchy (intermediate per-host identity)

Insert an optional HostKey tier between UserKey and AgentKey, mirroring matrix's master → self-signing split:

• A HostKey is a long(er)-lived ed25519 keypair, persisted per host (like UserKey, 0600 PKCS#8), signed once by the UserKey. It says "this host is one of mine."
• AgentKey::issue gains a sibling path where the HostKey signs the agent cert instead of the UserKey directly. The cert chain becomes User → Host → Agent, expressed as a new Issuer::Host { pubkey, parent: Box<CertChain> } variant alongside today's Issuer::User / Issuer::Agent. CertChain::verify already walks parents recursively and re-checks attenuation per link (agent_key.rs:221-233) — the host link slots in with the same structural check.
• This makes "is this agent genuinely one of mine on another host?" answerable: walk to the HostKey, surface its fingerprint, and let policy distinguish same-user-same-host from same-user-other-host. A compromised host can only forge agents under its own HostKey, so blast radius is contained to one host rather than the whole user identity. The UserKey private half need not be present on worker hosts at all — only the HostKey is, which is the whole point of the matrix self-signing split.
• Back-compat: a User → Agent chain (no host tier) remains valid and verifies exactly as today. HostKey is purely additive.

2. Identity pinning (DETECT, don't silently accept, a root roll)

Give the transport a small persistent pin store keyed by peer identity, mirroring matrix's pinned_master_key (identities/user.rs:598, has_pin_violation at user.rs:836):

• On first successful handshake with a given logical identity, pin the root UserKey fingerprint (and, when present, the HostKey fingerprint). This is trust-on-first-use made explicit and durable instead of implicit and forgotten.
• On every subsequent handshake, compare the presented root fingerprint against the pin. A mismatch is a pin violation — surfaced as a distinct, loud error (TransportError::PinViolation { pinned, presented }), not silently accepted and not auto-trusted. matrix's rule is exactly this: has_pin_violation returns true iff pinned_master_key.get_first_key() != master_key().get_first_key(), and identity_needs_user_approval (user.rs:421) then forces a human decision.
• Resolution paths (all opt-in, default-safe — a violation fails closed):
  • re-pin the new key (the matrix pin_current_master_key analog) — an explicit, audited "I rolled my key" acknowledgment;
  • verify the new identity out-of-band (the SAS/pact path, spike spike(transport): does the handshake expose a transcript hash for SAS binding? #30), which takes priority over pinning just as matrix's is_verified() short-circuits identity_needs_user_approval.
• Pin storage stays local and broker-less: a file under the agent-mesh state dir, same sovereignty posture as the UserKey itself. No directory is published; pins are private observations.

3. SenderData-style provenance on inbound envelopes

Attach a computed provenance verdict to each verified inbound SignedEnvelope, modeled on matrix's SenderData trust ladder (olm/group_sessions/sender_data.rs:117). Today SignedEnvelope::verify returns Result<()> — a binary. Add a richer result describing how the sender is trusted:

• UnknownRoot — chain is structurally valid but roots at a UserKey we have never pinned (cf. matrix UnknownDevice).
• SameUserUnpinnedHost — same UserKey, but a HostKey we have not seen before (cf. DeviceInfo: we have the credential but not yet a trust anchor for it).
• SameUserPinnedHost — same UserKey, host fingerprint matches our pin (the steady-state mesh case).
• PinViolation — root or host fingerprint contradicts a pin (cf. matrix VerificationViolation): the envelope verified cryptographically but trust has regressed, and policy must decide whether to act on its payload.

This is provenance binding, not encryption — it does not change the signed-only envelope model, and confidentiality continues to ride the QUIC/TLS session. It gives callers (the dispatcher, capability gates) a graded trust signal to make policy decisions on, exactly as matrix uses SenderData to decide whether to decrypt/display a message.

Explicitly out of scope

• Cross-USER trust. Connecting two different users' meshes stays gated behind a future "pact" and the human-verified SAS / channel-binding step (spike spike(transport): does the handshake expose a transcript hash for SAS binding? #30, transcript-hash channel binding). This issue is the software trust-graph layer only; it never widens authority across users.
• Payload encryption. Envelopes remain signed-only; transport confidentiality is unchanged.
• Any key directory / broker / discovery service. All credentials stay in-band on the cert chain; pins stay local.

Reference: matrix-rust-sdk

Read at /home/hartsock/workspaces/matrix-rust-sdk (reference only, not a dependency):

• The signing-key triplet — crates/matrix-sdk-crypto/src/olm/signing/pk_signing.rs: MasterSigning (:77) with new_subkeys() (:121) minting a UserSigning (signs other users' master keys) and a SelfSigning (:318, signs own devices). The master key is the root; the self-signing key is the per-account intermediate that signs devices — the structural analog of our proposed UserKey → HostKey → AgentKey. Public halves are MasterPubkey / SelfSigningPubkey / UserSigningPubkey, surfaced on the identity via master_key() / self_signing_key() / user_signing_key() (identities/user.rs:515-534).
• Identity pinning — crates/matrix-sdk-crypto/src/identities/user.rs: OwnUserIdentityData / OtherUserIdentityData carry pinned_master_key: Arc<RwLock<MasterPubkey>> (:598). pin() (:795) records the current master key; has_pin_violation() (:836) is literally pinned_master_key.get_first_key() != self.master_key().get_first_key(); identity_needs_user_approval() (:421) turns a violation into a required human decision unless the identity is already verified; pin_current_master_key() (:395) is the explicit re-pin path. The storage is versioned (v0→v1 migration adds pinning by pinning the then-current key, :609) — a clean template for adding pins back-compatibly.
• The SenderData trust ladder — crates/matrix-sdk-crypto/src/olm/group_sessions/sender_data.rs:117: SenderData progresses UnknownDevice → DeviceInfo → {VerificationViolation, SenderUnverified, SenderVerified} as the sender's device and cross-signing provenance are resolved, binding a graded trust verdict onto an inbound megolm session. This is the model for our per-envelope provenance verdict.

Acceptance criteria

• New Issuer::Host { pubkey, parent: Box<CertChain> } variant (or equivalent) lets a cert chain be User → Host → Agent; CertChain::verify re-checks attenuation at the host link and walks to the root user, with host_fingerprint() exposed alongside user_fingerprint().
• A persistent HostKey type (per-host, 0600 PKCS#8, signed once by UserKey) with generate / save / load, refusing to overwrite an existing key, mirroring UserKey.
• AgentKey can be issued under a HostKey; a legacy User → Agent chain (no host tier) still verifies unchanged (back-compat test).
• A local, broker-less pin store records the root (and host) fingerprint on first successful handshake and exposes a has_pin_violation-style check.
• ensure_trustable (handshake.rs) consults the pin store and returns a distinct TransportError::PinViolation { pinned, presented } on mismatch; a violation fails closed (connection refused), never silently re-trusted.
• Explicit, audited re-pin and (deferred to spike(transport): does the handshake expose a transcript hash for SAS binding? #30) verify resolution paths are wired, with verify taking priority over a pin when present.
• Inbound SignedEnvelope verification yields a graded provenance verdict (UnknownRoot / SameUserUnpinnedHost / SameUserPinnedHost / PinViolation) in addition to the cryptographic check; the signed-only, transport-confidential envelope model is unchanged.
• All new wire fields are #[serde(default)] and serde-roundtrip with older payloads (back-compat tests, following the caveats precedent).
• Regression tests: (a) swapped/rolled root key is detected as a PinViolation rather than silently trusted; (b) same-user-other-host is distinguishable from same-user-same-host; (c) a forged User → Host → Agent chain that amplifies caveats at the host link is rejected at verify().
• Cross-USER trust remains refused (no pact) and is documented as out of scope here, deferring to spike(transport): does the handshake expose a transcript hash for SAS binding? #30 for the human-verified SAS / channel-binding step.
• just check and just cov-ci pass (75% floor); hook/pipeline parity preserved.

Relationships

• Companion spike(transport): does the handshake expose a transcript hash for SAS binding? #30 — the SAS / transcript-hash spike supplies the interactive, human-verified cross-user step this software trust-graph leaves to a future pact.
• Related feat(protocol): optional encrypted UserKey backup with a base58 recovery key #47 — multi-host identity: cross-signing a new host key is the alternative to exporting the root seed.
• Related feat(transport): external-signer seam for the QUIC handshake (no owned seed) #28 — the external-signer / non-exportable-key seam interacts with per-host identity.

---

Meta · risk: high (per repo CLAUDE.md) · follow-up from the matrix-rust-sdk ↔ agent-mesh architectural comparison (matrix-rust-sdk is a reference implementation, not a dependency).

File/line references were drafted against a recent checkout; line numbers are indicative — symbols are authoritative (grep by name). Substance verified against origin/main @ f63c55f.

🤖 Generated with Claude Code

[hartsock]

This issue is where the X25519 DH key lives — see #43 §5 (the Ed25519↔X25519 gotcha).

The #43 confidentiality work needs an X25519 (Montgomery) key for Diffie-Hellman, but agent-mesh identities are Ed25519 (Edwards, signing) — same curve, different keys/operations. The design note recommends option (B): mint a dedicated X25519 DH keypair, signed by the Ed25519 identity, rather than birationally reusing the signing key for DH (key separation — reuse is outside the per-primitive security proofs, so it's the conservative default).

That signed DH key belongs in this cross-signing / per-host cert work: the host/device cert #44 introduces is the natural place to carry and attest the X25519 DH public key, anchored to the same trust root. Bonus: signed DH-key distribution is exactly the authenticated-key-distribution posture that mitigates vodozemac/Olm's all-zero-key finding (#43), and it's already how the vodozemac path works (it manages its own Curve25519 keys, signed by your Ed25519 identity).

🤖 Generated with Claude Code