Cross-federation DM and directory bounds

Research — non-normative

This page is synced from the repo’s docs/research/ tree: exploratory design work, forward-looking plans, or historical analysis. It may describe behavior that is not built or that shipped differently. The normative spec lives in the other docs sections.

Status: design + first decision increment. This file is normative for the host-testable decision layer that ships with it (CrossFedDirectory, below); the transport/actuation it describes is deferred and called out explicitly in §9 What this does NOT do yet. It moves the ROADMAP “DHT-free directory … weak … for cross-federation DM (no lookup story)” bullet forward without changing a single wire byte in this increment.

Read alongside ROUTING.md (directory, federation, attachment model), IDENTITY.md (KEYREQ/KEYRESP, identity records, CTK), and PROTOCOL.md (RTRSYNC, packet types).

1. The problem, stated precisely

Today the directory is per-federation and bounded per node (ROUTING.md §Federation): one RTRSYNC record per (UID, current router) online attachment, gossiped only inside a federation_id, capped by directory_limit (default 1024) with eviction that prefers unreachable, then stale same-UID, then least-recently-refreshed entries. A DM routes sender → sender's router → (backbone) → recipient's router → recipient using that directory (the Node::choose_peer_by_uid lookup over directory_).

That works only when the recipient’s UID is homed in the sender’s own federation. If Alice lives in federation A and wants to DM Bob, whose identity is homed in federation B, then:

• Alice’s router has no directory entry for Bob’s UID — federation A’s RTRSYNC never carried it, so choose_peer_by_uid returns nullptr.
• Alice’s router cannot even verify a record it might receive for Bob (CTK, IK_pub) without a way to fetch and trust Bob’s IdentityRecord across the boundary.
• There is deliberately no global DHT (ROUTING.md §“What deliberately does NOT exist”) to ask “where is UID X?”.

So cross-federation DM needs three things, in order: a lookup story (find the router responsible for a foreign UID without a DHT), a trust story (verify that router’s identity record + CTK across the boundary), and bounds (so the lookup state does not become the global table we refused to build).

2. Design principle: peering, not a global namespace

chIRpChat already rejects MQTT/brokers/DHTs in favor of bounded gossip among peers that opt in to trusting each other (config peers, RK pins, federation_id roster). Cross-federation lookup must inherit that shape: it is an explicit, configured peering between federations, not an emergent global namespace.

Concretely, a federation operator who wants cross-fed reachability adds one or more federation peerings: (peer_federation_id, gateway_router_RK_pin). A gateway router is an ordinary router that additionally holds a pinned backbone link to a gateway router in the peer federation (the same authenticated TCP LA+LR link from ROUTING.md §Backbone — no new link type). This is the federation analogue of a client picking 1–3 home routers: a federation picks 1–N peer federations it will exchange referrals with. The web of peerings is sparse and operator-curated, which is exactly why it scales without a DHT: you only ever hold lookup state for federations you chose to peer with, plus short-lived referral hints you were handed.

Non-goals of the topology (see §9): transitive multi-hop federation routing, automatic peer discovery, and a global flat UID space. The first increment is one referral hop (A → B), which already covers the overwhelmingly common “two communities that know each other want to DM” case.

3. The lookup story (referral, not flooding)

When Alice DMs a UID her federation’s directory does not home, her router runs a bounded referral resolution, entirely a routing decision over state it already holds plus state it can fetch over existing links:

1. Local fast path. If the directory already homes the UID inside Alice’s federation, route normally (ROUTING.md §“DM delivery”) through choose_peer_by_uid. No cross-fed work. This is the SameFed decision below and must stay the zero-cost common case.

2. Cached referral. If a referral hint for that UID is cached ((UID → peer_federation_id, gateway_router, liveness/expiry)), and the gateway is currently reachable over the backbone (Node::router_reachable), route the DM to that gateway with a cross-federation marker. The gateway, being in (or peered with) federation B, resolves the UID in B’s own directory and forwards. This is CrossFedReferral.

3. Referral query. With no usable cached hint, the resolver decides to emit a bounded referral query to a small set of peered gateways (fan-out capped, the same shape as gossip_fanout_select): “do you home, or can you reach, UID X?”. A gateway that homes the UID (or holds its own referral) answers with a referral response carrying (UID, peer_federation_id, gateway_router, IdentityRecord-or-pointer). Alice’s router caches that hint (TTL’d) and proceeds as in step 2. This is EmitReferralQuery. Crucially this is a unicast query to configured peers, not a flood: TTL is effectively 1 federation hop, and the candidate set is the operator-pinned peering list, not “everyone”.

4. Give up cleanly. If there are no peered gateways, or the query budget is exhausted, or every candidate gateway is unreachable, the resolver returns Unresolved. The IRC layer then reports the DM as undeliverable (a *lrc notice), exactly as it does today for an unknown UID — no silent black-holing, no infinite retry storm.

The decision primitive in §6 computes which of these four a sender’s router should do, given its local directory state, its cached referral hints, its peer gateway list, and current backbone reachability. It deliberately stops at “decide the route/target”; emitting the query packet, parsing the response, and mutating the cache are actuation left for the transport increment (§9).

4. The trust / identity story

Routing a DM into federation B is worthless if Alice cannot tell Bob’s record from a forgery handed to her by a hostile gateway. The existing identity stack already closes this, and cross-fed reuses it verbatim:

• A referral response carries (or lets Alice fetch via ordinary KEYREQ across the gateway link) Bob’s signed IdentityRecord (IDENTITY.md §6: UID(8) IK_pub(32) epoch(1) CTK(8) … sig(64)).
• Alice’s node verifies it the same way it verifies any KEYRESP today: UID == SHA-256(IK_pub)[0..8], every subkey cert signs under IK_pub, and the trailing signature verifies under IK_pub. A gateway cannot forge a record — it can at most refuse to answer or hand back a record that fails verification, which Alice rejects.
• Once verified and cached (the same bounded IdentityRecordStore LRU), Alice enforces Tier-2 chat tags (CTK) and can demand Tier-3 SIGNED_FULL / CHECKPOINT on the DM exactly as within a federation (IDENTITY.md §4). The cross-federation boundary changes transport, not the authenticity model: Tier-1 ingress attestation now spans two federations’ pinned links, and the operator who peered the federations is making the same trust decision they make when they pin any backbone peer.
• A revoked UID (IDENTITY.md §5, RTRSYNC revoke/clear rows) must not be resurrected by a cross-fed referral: a referral hint for a locally-denylisted UID is dropped, and an inbound referral response for it is ignored — the resolver treats local revoke state as authoritative over any foreign hint.

The honest caveat (same bold honesty as IDENTITY.md §4.2): cross-fed Tier-1 attestation is only as strong as the weakest pinned link on the path and the gateway operators’ diligence. A federation that peers with a sloppy federation inherits its attestation quality for traffic crossing that seam. This is a deliberate, operator-visible trade — you choose your peers — not a hidden one.

5. Bounds, eviction, and failure modes

5.1 Bounds and eviction

Referral hints are a second bounded cache, sibling to the directory, never a global table:

• crossfed_hint_limit (proposed default 256) caps cached referral hints per node. 0 disables cross-fed entirely (no peerings, no hints).
• Hints carry a TTL (proposed default 1 h) and a liveness generation copied from the answering gateway, so a fresher answer supersedes a stale one deterministically.
• Eviction mirrors directory eviction (ROUTING.md, enforce_directory_limit): prefer hints whose gateway is currently unreachable, then expired hints, then least-recently-used. A new counter fed.crossfed_hint_drop makes the eviction observable (TELEMETRY.md rule: new observable behavior gets a Counter).
• The query budget is bounded per UID and per interval (like GossipFanoutPolicy.fanout): a resolver will not emit more than fanout referral queries per resolution and will not re-query a UID before a backoff window elapses. This is what stops a popular-but-unreachable UID from turning every DM attempt into a fan-out storm.

5.2 Failure modes the design must survive

• Loops / amplification. A referral query must not be re-emitted by the receiving gateway as another query into a third federation in this increment: the first increment is one federation hop only. The resolver marks a query as cross_fed_hop = 1 and a gateway drops a query that already carries a hop (no transitive A→B→C). This bounds fan-out to peers × fanout, not peers^depth. Transitive referral (with a proper TTL and a visited-set) is explicitly deferred (§9).
• Unreachable / stale preference. The resolver prefers a reachable gateway with a fresh hint over a stale or unreachable one, and prefers not querying at all when a usable cached hint exists — minimizing both airtime and information leakage. When the only cached hint points at an unreachable gateway, the resolver falls back to a fresh bounded query rather than black-holing on the dead hint.
• Privacy (who-DMs-whom leakage). A referral query reveals (querying federation, target UID) to every gateway it is sent to. The design minimizes this three ways: (a) query the fewest gateways that can answer (cap = fanout, prefer a single best peer when one is known to home the target’s federation); (b) never broadcast a referral query onto RF or to non-peered routers — it rides only operator-pinned backbone links; (c) once a hint is cached, suppress further queries for its TTL so repeated DMs to the same person do not re-leak the relationship on every message. The resolver’s prefer cached hint over query rule is therefore a privacy control, not just an efficiency one. The deeper “hide the target UID from the gateway entirely” (private set intersection / oblivious lookup) is out of scope and noted in §9.
• Hostile gateway. Cannot forge identity (§4) but can lie about reachability or refuse to forward. Mitigations: Alice marks a gateway that fails to deliver (ACK retry budget exhausts) the same way she marks any unreachable router, demotes its hints, and re-queries other peers. A gateway that hands back records that fail verification is ignored and SHOULD be surfaced to the operator (future fed.crossfed_reject counter).
• Eviction churn under scale. Because both the directory and the hint cache are bounded and refreshable from gossip/query, the worst case at internet scale is more queries, not unbounded memory — the system degrades to “slower first-DM to a cold foreign UID”, never to “OOM” or “global table”.

6. The decision primitive (CrossFedDirectory)

The first code increment is a pure, host-tested decision that mirrors backbone_link_better / GossipFanoutPolicy / LaneSchedule::promote_client: it computes intent and touches no wire bytes, no sockets, no heap on the radio path. It lives in core/include/lrc/link_policy.h beside the other transport-agnostic federation policy, and is covered by tests/test_link_policy.cpp.

Inputs (all caller-provided views — no ownership, no allocation):

• self_fed — the resolving node’s federation_id.
• a span of directory attachments the node already homes/learned ({uid, fed_id, gateway_rtr, reachable, last_heard, live_rev}), the same facts PeerUser already carries plus the home fed_id;
• a span of referral hints ({uid, peer_fed_id, gateway_rtr, reachable, expires_ms, live_rev});
• a span of peer gateways ({gateway_rtr, peer_fed_id, reachable}) from the operator’s peering config;
• now_ms, a CrossFedPolicy (fanout, hint TTL handling), and the target uid.

Output: a CrossFedDecision { action, gateway_rtr, peer_fed_id } where action is one of SameFed, CrossFedReferral, EmitReferralQuery, Unresolved, following §3 exactly. The selection rules reuse the project’s existing freshness/reachability ordering (reachable first, then most-recently-heard, then liveness generation — the same shape as Node::prefer_peer).

This primitive is only the decision. It does not emit packets, does not mutate caches, and does not perform crypto — the embedding (Node / lrcd / firmware) wires its real directory and config into the views and acts on the returned intent, just as it does for LaneSchedule::promote_client.

7. Does this need a wire change?

Not for this increment, and the first transport increment can avoid one too.

• The referral query and referral response are expressible as new optional sections inside RTRSYNC (PROTOCOL.md already frames RTRSYNC as a bag of optional, version-tolerant sections carrying directory/identity rows) or, if a request/response shape is cleaner, as a new packet type in the reserved range (PROTOCOL.md §Versioning: new types are additive and blind-relayable by v1 nodes). Either way it is additive: it does not touch the frozen header/addressing layout, the canonical image, Tag8 coverage, UID derivation, or the dedup key — so packet_golden_bytes is untouched.
• The identity record that establishes trust already has a wire format and a fetch path (KEYREQ/KEYRESP, IDENTITY.md §6) that works across any pinned link. Cross-fed reuses it as-is.

If and when the transport increment lands, it MUST go through the lrc-wire-change checklist as a deliberate LPP v1.x field event (write the doc first, additive section/type, re-pin golden bytes by hand only if a parsed layout truly changes, sweep dependents). The strong preference, stated here so the next agent inherits it, is: carry referrals as TTL-tagged optional RTRSYNC sections scoped to the peering link, reusing the existing delta machinery, adding zero new top-level packet types for the first increment.

8. Counters (observable behavior)

Proposed lrc::Counter names for when the transport lands (named now so they are stable API per TELEMETRY.md):

• fed.crossfed_query — referral queries emitted.
• fed.crossfed_hint_rx — referral hints accepted into the hint cache.
• fed.crossfed_hint_drop — hints evicted by the bound.
• fed.crossfed_reject — referral responses dropped for failed verification or local revoke.
• fed.crossfed_unresolved — DMs that resolved to Unresolved.

No counter is added in this commit (the decision primitive is pure and the embedding is not yet wired); they are reserved here so the wire increment uses stable names.

9. What this does NOT do yet

Explicitly out of scope for this increment, in rough priority order:

1. Transport/actuation. No referral query/response is emitted or parsed; no Node/lrcd/firmware wiring; no cache mutation. This commit ships the decision only, per the project’s “build the host-testable decision layer first” discipline (ROADMAP §“Designed vs built”).
2. Transitive (multi-hop) federation routing. Only one A→B referral hop. No A→B→C, no visited-set, no inter-federation path TTL beyond 1. A→C requires A to peer with C (or a future transitive increment with loop protection).
3. Automatic peer discovery. Federation peerings are operator-configured (pinned gateway RKs), never auto-learned. There is intentionally no global “list of all federations”.
4. A global flat UID namespace / DHT. Still refused (ROUTING.md). Lookup is bounded referral among curated peers; reachability degrades to “more queries / slower cold DM”, never to a global table.
5. Oblivious / privacy-preserving lookup. A referral query still reveals the target UID to the queried gateways. PSI-style hiding of the target is a research item, not in this design.
6. Offline cross-fed mailboxing. This increment routes online cross-fed DMs (or cleanly reports unresolved). Mailboxing a DM for an offline foreign UID across federations reuses the MailboxStore/MAILBOXSYNC machinery (ROUTING.md §“DM delivery and mailboxes”) but is deferred until the online path and its transport exist.
7. Roaming across federations. A user changing their home federation (not just their router within one) is out of scope; identity is still keyed by UID, but re-homing semantics and the directory hand-off are future work.

When the transport increment lands, this section shrinks and the corresponding behavior moves into the normative body of ROUTING.md / PROTOCOL.md, per AGENTS.md rule 3.