Johnathan Corgan
6a564e26ac
Everything the release needs except the version number, which stays at 0.5.0-dev until the tag. The changelog entry covers only the work that is new on this line. The point release's forty-six entries arrived under their own heading with the forward merge and are left alone; the twenty that remained are regrouped by topic and eight more added for changes no entry covered. Three of those eight matter to someone upgrading. Five root modules and four re-exports left the public library surface and Node::connections narrowed, none of it recorded anywhere; the entry names what to use instead and distinguishes the removed connection-phase enum from the Noise type of the same name, which is a different type that still exists. Tracing targets moved, so an existing RUST_LOG filter stops matching rather than erroring. And the handshake resend interval key no longer governs the first resend, which is now a constant, though it still governs later ones. Seven more entries cover the work that landed after the first content pass was written: the experimental native datagram API, the fipsctl probe diagnostic, per-instance transport addressing, the app-owned UDP socket seam, and the connect, disconnect and path-MTU fixes. The four bug fixes among them all reach the deployed line, so the release notes no longer claim this release carries exactly one fix for a shipped bug; it carries four. There is no security section, because after the split every security entry belongs to the point release. The release notes say so plainly rather than leaving a reader upgrading across both releases to conclude this one carries no security work. The notes are organized by audience, since the release spans OpenWrt routers, embedders, FreeBSD, and the existing platforms, and a single list serves none of them. The native datagram API is given a section of its own rather than folded into the embedding seam: it is a client-facing API rather than a way to host a node, and its one rule with no Berkeley-socket counterpart, that the v1 wire carries no half-close, needs to be somewhere a client author will read it. FreeBSD is advertised as supported on x86_64 only, stated wherever the platform appears. Android is advertised as an embedding seam and not as a supported platform: a compile-gated library surface with no artifact and no host application guide. The configuration table rename is carried through every shipped file that taught the old spelling: nine documentation files, the OpenWrt sample config and a test generator, twenty-two sites in all. Guides written this same cycle were among them, which is how the omission was found. The documentation that arrived with the native API was checked for the same omission and was already clean. The compatibility tests keep the old spelling deliberately, since they exist to test the fold. The changelog section is the fold of master's [Unreleased], not a snapshot of it. An earlier version of this commit took a copy that then drifted, so each section ended up holding a bullet the other did not and re-folding them would have picked a winner silently. Both causes were fixed on master instead — the NixOS module had never been recorded there, and the pre-release batch of fixes was new — so [Unreleased] is a strict superset and this is a copy rather than a merge. [0.5.0] carries all forty-six bullets byte for byte, [Unreleased] is empty, and [0.4.2] is untouched, checked by hashing it against master's copy. The BLE work landed after the content pass and gets one summary entry in the changelog and one section in the release notes rather than nine bullets: the ble_available gate replacing target_os = "linux", packet-boundary recovery for stream-oriented backends, peer recognition by node identity instead of a rotating link address, the L2CAP PSM moving into the backend seam and onto the advertisement, the embedder-supplied Android radio, bounded probe retry, and inbound handshakes moved off the accept loop. The two release-notes copies no longer share their link paths. Relative links resolve from one directory only, so the seven written for docs/releases/ all 404ed from the root copy. The root copy now uses paths from the repository root and the versioned copy keeps the ../ form; both sets were resolved against the tree. The same two links are broken the same way in the v0.4.0 through v0.4.2 notes, left as shipped history. The contributor tallies are re-derived against maint..HEAD rather than adjusted: twenty commits from outside the project and 171 from me, with Arjen at fifteen and fr34aky at two. An earlier count of twelve and 138 was carried from a measurement taken three days before this content was written, and the BLE branch widened the gap after it. Arjen's NixOS flake module, the UDP sin6_scope_id fix and most of the BLE rework were uncredited, as was fr34aky's L2CAP PSM seam. They want one last re-derive at tag time if anything lands before the tag. A sweep of all 99 tracked markdown files against the tree corrected fifty-three of them. Four told the reader to run a build.sh that does not exist; the only harness builder is testing/scripts/build.sh. The BLE build prerequisites were described as optional on the strength of a probe that build.rs does not perform, and bluez was named a build prerequisite when libdbus-sys asks only for libdbus-1-dev and pkg-config and bluez is the runtime daemon. Link cost is the primary sort key in next-hop ranking, not reserved for future use; Ethernet runs on macOS as well as Linux; the BLE MTU is the L2CAP CoC MTU rather than a negotiated ATT_MTU; effective Ethernet MTU is 1497; the LAN discovery subsystem is src/mdns and eight citations still named a src/discovery that never existed here. The connectivity states in three tutorials were invented, and their jq filters matched nothing including healthy peers. One command filtered on a literal fd97: address prefix, which only the first byte of fixes, so it returned empty for all but one reader in 256 and every later step using the variable failed silently. transports.tor.advertise_on_nostr was undocumented despite being validated against node.rendezvous.nostr.enabled. The transport design document gains the BLE section it never had, written from the source: the backend cascade and its compile_error tripwire, the platform gate, the PSM advertisement wire layout and the byte budget that forces a 16-bit service-data key, and the probe and admission bounds. Three source files carried the same class of staleness and are corrected with the documentation: the OpenWrt ipk usage line and Makefile error text both named a packaging/openwrt that does not exist, and chaos.sh parsed --subnet without listing it. Folded in with the content commit, having been prepared alongside it: The three GitHub Action pins that had gone stale. Every third-party action is pinned to a commit SHA, nothing reports that a pin has aged, and re-resolving all ten against their tags found dorny/test-reporter@v2, taiki-e/install-action@v2 and vmactions/freebsd-vm@v1 had moved. The three install-action@nextest references stay unpinned, since that action reads the tool to install from the ref name. check-action-pins.sh passes at 75 references and all nine workflow files parse. The lockfile refresh, which is the mutating half of the dependency sweep. Thirty-six packages move to their latest semver-compatible versions and every one is transitive; nothing declared in Cargo.toml changes version. No advisory forces any of them. It was taken before the validation battery, because a gate run against a lockfile that later moves proves nothing about what ships. The sha2 0.10 to 0.11, hkdf 0.12 to 0.13 and bech32 0.11 to 0.12 majors, three of the four deferred at v0.4.0 for change surface rather than security. All three land with no source change. sha2 and hkdf must move together, since both depend on digest 0.11, and neither changes an algorithm. That matters because the chaining-key KDF in the Noise handshake is built on Hkdf::<Sha256>, where an output change would be a wire break rather than a compile error; no known-answer vectors exist for that path, so the wire-compatibility gate is what covers it. secp256k1 0.31 is deliberately absent, since nostr's own requirement would leave two copies of the ECC library in the tree. The README support matrix, rebuilt as one feature table broken out by Linux variety. A single Linux column hid that Debian, Ubuntu, Arch and NixOS are one glibc build differing in packaging, that OpenWrt is musl and drops BLE, and that Android is not a daemon platform. Transport rows sort by how many platforms carry them. A Native API row reads its platform set from the cfg gates. The installer row becomes a package format row naming the artifact, and only the .deb is exercised per release. Four changelog and release-note gaps the BLE re-walk found: a Bluetooth LE bullet stranded inside the released 0.4.2 section, a missing Fixed entry for the scan and probe loop counting a pool-refused connection as an established link, the unnamed embedder call that installs an application-owned radio, and the fact that stopping the transport now stops scanning as well as advertising. Three release-document gaps found walking the unsurveyed commits: the UDP reuse-flag fix stated in the direction opposite to the one it was made, with the silent second-daemon bind it prevents left unsaid; the corrected native-API socket paragraph carried into both release-note copies, which still named SOCK_SEQPACKET on FreeBSD and two kernels where three are handled; and the coordinate-cache hardening, which shipped with no text anywhere despite adding four operator-visible status fields. That last entry states plainly that the checks are mitigations and not a closure, since the coordinate is still not authenticated. Also folded in, the documentation pass that followed the content commit: A stage-pipeline diagram for the probe, embedded in the fipsctl reference under the five-stage list. It draws the five stages left to right with each stage's failure reasons below it, and the bypass that skips both lookup stages when the coordinates are cached or the target is a direct peer. Its branches come from the probe state machine rather than from the report, so the path stage is drawn as the one failure that does not stop the probe. A rewrite of the README's "What FIPS does" section. It now opens with what a machine running FIPS gets, rather than with the two deployment modes, and gives the self-organizing and permissionless property its own paragraph since it holds for both modes. A regrouping of the README's feature list into the mesh, getting traffic onto it, and running a node, with a bullet added for the native datagram API, which had none despite sitting in the support matrix. The Quick start now leads with the released packages rather than a source build. It also fixes a real defect: the package enables fips.service and fips-dns.service and starts neither on a fresh install, so .fips name resolution was silently dead until the next reboot and neither page said to start the service. A rewrite of the release notes. They opened with seven subsections of upgrade caveats and reached the first feature two hundred lines in; they now open with a summary of the release and elaborate below it in the same order. Android is stated as supported through an embedded crate rather than as a standalone daemon, consistently across all three documents. The OpenWrt pair is corrected: it is 802.11s between routers with FIPS supplying encryption, authentication and routing, plus a convention of an open !FIPS SSID a client joins over WiFi, not meshing over a router's own radios. The probe's path output is described as the least-common-ancestor walk, which is the worst-case fallback route rather than the route a packet takes. Detail that did not change what a reader does was cut from the notes and kept in the changelog.
25 KiB
FIPS Mesh Operation
This document describes how the FIPS mesh operates at the link layer — how spanning tree, bloom filters, routing decisions, discovery, and error recovery work together as a coherent system. It treats spanning tree and bloom filters as black boxes (what they provide to routing) and focuses on how the pieces interact.
For spanning tree algorithms and data structures, see fips-spanning-tree.md. For bloom filter parameters and mathematics, see fips-bloom-filters.md.
Overview
FIPS mesh operation is entirely distributed. Each node makes forwarding decisions using only local information: its direct peers, their spanning tree positions, and their bloom filters. There are no routing tables pushed from above, no link-state floods, and no distance-vector exchanges.
Two complementary mechanisms provide the information each node needs:
- Spanning tree gives every node a coordinate in the network — its ancestry path from itself to the root. These coordinates enable distance calculations between any two nodes without global topology knowledge.
- Bloom filters summarize which destinations are reachable through each peer. Because they propagate along tree edges, they encode directional reachability — which subtree contains a given destination.
Together, they enable a routing decision process that is local, efficient, and self-healing.
Spanning Tree Formation and Maintenance
For routing purposes, the spanning tree provides each node with a coordinate (its ancestry path from itself to the root) plus a way to compute distance between any two nodes (hops to their lowest common ancestor). The strictly-decreasing distance invariant gives greedy forwarding its loop-freedom.
The tree forms through distributed parent selection — root is the
smallest node_addr (no election), and each node picks the peer with
the lowest effective_depth = depth + link_cost. Cost-aware parent
selection lets the tree trade hop count for link quality once MMP has
accumulated SRTT and ETX metrics. Hysteresis (20% improvement
required to switch) and hold-down (suppress non-mandatory
re-evaluation after a switch) keep the tree stable under metric
noise. Partitions self-resolve — each segment converges to its own
root and reconverges to the smallest reachable root when segments
rejoin.
Liveness is detected via FMP heartbeats; dead-peer removal triggers tree reconvergence and bloom filter recomputation for the affected subtree. The heartbeat and dead-timeout mechanism lives at the link layer; see fips-mesh-layer.md.
For the parent-selection algorithm, hold-down/hysteresis details, and the convergence walkthroughs, see fips-spanning-tree.md and spanning-tree-dynamics.md.
Bloom Filter Gossip and Propagation
For routing purposes, each node maintains a bloom filter per peer that answers "can peer P possibly reach destination D?" — either "no" (definitive) or "maybe" (probabilistic). Because filters propagate along tree edges with split-horizon exclusion, a bloom hit on a tree peer reliably indicates which subtree contains the destination, and tree-coordinate distance ranks competing matches.
FilterAnnounce updates are event-driven (peer changes, tree restructuring, local identity changes) and rate-limited to prevent storms. False positives at large scale never cause loops — the self-distance check at each hop guarantees forward progress, and mismatched bloom matches fall through to greedy tree routing.
For the filter computation, split-horizon merge rules, FPR analysis, size classes, and folding, see fips-bloom-filters.md.
Routing Decision Process
At each hop, FMP makes a local forwarding decision using the find_next_hop()
priority chain. This is the core routing algorithm.
Priority Chain
-
Local delivery — The destination node_addr matches the local node. Deliver to FSP above.
-
Direct peer — The destination is an authenticated neighbor. Forward directly. No coordinates or bloom filters needed.
-
Coordinate cache check — Multi-hop forwarding requires the destination's tree coordinates to be in the local cache. On miss,
find_next_hop()returns None immediately — bloom filters are never consulted — and the source receives a CoordsRequired error signal. -
Bloom-guided routing — One or more peers' bloom filters contain the destination. Select the best peer by composite key:
(link_cost, tree_distance, node_addr). -
Greedy tree routing — Fall-through when bloom yields no candidate. Forward to the peer that minimizes tree distance. If the tree has no next hop closer to the destination, the source receives a PathBroken error signal.
Convergence Requirements
Multi-hop routing depends on two propagation processes that must run to convergence simultaneously:
- Bloom convergence: Filters must propagate so peers advertise reachability
- Coordinate availability: Destination coordinates must be cached at every transit node on the path
Bloom convergence without coordinates trips step 3 (coord-cache miss → CoordsRequired). Coordinates without bloom convergence falls through to greedy tree routing — functional but suboptimal.
Candidate Ranking
When bloom filters identify multiple candidate peers, they are ranked by a composite key:
- link_cost — Per-link quality metric derived from ETX (Expected Transmission Count), computed from bidirectional delivery ratios in MMP metrics. In practice this is an uncommon tie-breaker: most forwarding decisions are resolved by tree distance alone, and link_cost only differentiates candidates when multiple peers offer the same tree distance to the destination.
- tree_distance — Coordinate-based distance to destination through this peer
- node_addr — Deterministic tie-breaker
A peer with a bloom filter hit but no entry in the peer ancestry table (missing TreeAnnounce) defaults to maximum distance and is effectively invisible to routing.
Routing Decision Flowchart
Loop Prevention
The routing decision enforces strict progress: a packet is only forwarded to a peer that is strictly closer (by tree distance) to the destination than the current node. This self-distance check prevents routing loops even with stale coordinates, because each transit node evaluates using its own freshly-computed coordinates.
If no peer is closer than the current node (a local minimum in the tree
distance metric), find_next_hop() returns None and the caller generates a
PathBroken error.
Coordinate Caching
The coordinate cache maps NodeAddr → TreeCoordinate and is the
critical data structure for multi-hop routing. The session layer owns
this cache (its eviction policy, TTL/refresh semantics, parent-change
flush, and timer ordering with session idle timeout); see
fips-session-layer.md for
the canonical treatment.
Discovery Protocol
Discovery resolves a destination's tree coordinates so that multi-hop routing can proceed. Requests are forwarded using bloom-guided tree routing — only to tree peers (parent + children) whose bloom filter contains the target — producing single-path forwarding through the spanning tree.
When Discovery Is Needed
- First contact with a destination (no cached coordinates)
- After receiving CoordsRequired (transit node lost coordinates)
- After receiving PathBroken (coordinates may be stale)
LookupRequest
The source creates a LookupRequest containing:
- request_id: Unique identifier for deduplication
- target: The node_addr being sought
- origin: The requester's node_addr
- origin_coords: The requester's current tree coordinates (so the response can route back)
- TTL: Bounds the forwarding radius
Bloom-Guided Tree Routing
Rather than flooding to all peers, the request is forwarded only to tree peers (parent + children) whose bloom filter contains the target. Because bloom filters propagate along tree edges with split-horizon exclusion, typically only one tree peer matches — producing a single directed path through the spanning tree toward the target's subtree. This reduces discovery traffic by roughly 90% compared to flooding.
If no tree peer's bloom filter matches the target, the request falls back to non-tree peers whose bloom filter contains the target. This recovers from dead ends caused by stale bloom filters, tree restructuring, or transit node failures. If no peer at all has a bloom match, the request is dropped at that node.
Loop prevention: The spanning tree is inherently loop-free, so tree-only
forwarding cannot loop. The request_id dedup cache (default 10s window)
provides defense-in-depth, catching edge cases during tree restructuring
where a request might arrive via both tree and fallback paths.
Retry Logic
Single-path forwarding is more fragile than flooding — if any transit node
on the path has a stale bloom filter or loses a link, the request fails.
To compensate, each discovery is a sequence of attempts with growing
per-attempt timeouts. The default sequence is [1s, 2s, 4s, 8s]
(configurable via node.lookup.attempt_timeouts_secs); the destination
is declared unreachable only after the full sequence is exhausted (15s
total at default).
When the current attempt's deadline elapses without a LookupResponse,
the originator sends another LookupRequest with a fresh request_id
and the next entry in the sequence as its deadline. Fresh request_ids
let each attempt take a different forwarding path as the bloom and tree
state evolve, which is particularly useful during cold-start convergence.
Originator Backoff (optional, off by default)
After the per-attempt sequence is exhausted, the originator can additionally
suppress further fresh lookups for the same target with exponential
post-failure backoff. This is disabled by default (backoff_base_secs: 0); the per-attempt sequence is the only retry pacing in the standard
configuration. Operators may opt in via node.lookup.backoff_base_secs
and node.lookup.backoff_max_secs if their deployment has chatty apps
generating repeated lookups for genuinely unreachable destinations. When
enabled, backoff is reset on topology changes that might make
previously unreachable targets reachable: parent switch, new peer
connection, first RTT measurement from MMP, or peer reconnection.
Bloom Filter Pre-Check
Before initiating a lookup, the originator checks whether any peer's bloom filter contains the target. If no peer advertises reachability, the lookup is skipped entirely and recorded as a failure for backoff purposes. This avoids wasting network resources when the target is not in the mesh.
Transit-Side Rate Limiting
Transit nodes enforce a per-target minimum interval (default 2s, configurable
via forward_min_interval_secs) for forwarded lookups. This is
defense-in-depth against misbehaving nodes that generate fresh request_ids
at high rate to bypass dedup. The rate limiter collapses rapid-fire lookups
for the same target regardless of request_id.
LookupResponse
When the request reaches the target (or a node that has the target as a direct peer), a LookupResponse is created containing:
- request_id: Echoed from the request
- target: The target's node_addr
- target_coords: The target's current tree coordinates
- path_mtu: Minimum MTU along the response path (transit-annotated,
initialized to
u16::MAXby the target) - proof: Signature covering
(request_id || target || target_coords)— authenticates that the response is genuine and the target holds the claimed tree position
The response routes back to the requester using reverse-path routing as
the primary mechanism: each transit node looks up the request_id in its
recent_requests table to find the peer that forwarded the original request,
and sends the response back through that peer. This ensures the response
follows the same path as the request. Greedy tree routing toward the
origin_coords is used only as a fallback if the reverse-path entry has
expired.
Response-forwarded flag: Each recent_requests entry tracks whether a
response has already been forwarded for that request_id. If a second
response arrives (e.g., from convergent request paths that reached the
target via different routes), the transit node drops it. This prevents
response routing loops where multiple responses for the same request
circulate through the network.
Proof verification: The source verifies the Schnorr proof upon receipt,
confirming that the target actually signed the response. The proof covers
(request_id || target || target_coords) — coordinates are included because
verification at the source confirms the target holds the claimed position.
The path_mtu field is excluded from the proof because it is a transit
annotation modified at each hop.
Coordinate Discovery Sequence
Discovery Outcome
On receiving a verified LookupResponse, the source caches the target's
coordinates and clears any backoff state for that target. Subsequent routing
to that destination can proceed via the normal find_next_hop() priority
chain.
If discovery times out (no response after all retry attempts), queued packets receive ICMPv6 Destination Unreachable and the target enters backoff.
Coordinate Cache Warming
SessionSetup carries plaintext source and destination coordinates, which transit nodes cache as the message travels — warming the forward path. SessionAck carries them back along the reverse path, warming return-path caches. Steady-state data packets piggyback coordinates via the FSP CP flag during the warmup window, falling back to standalone CoordsWarmup messages when piggybacking would exceed the transport MTU. See fips-session-layer.md for the canonical hybrid-warmup design (SessionSetup self-bootstrapping plus CP-flag piggyback plus standalone CoordsWarmup).
Error Recovery
When routing fails, transit nodes signal the source endpoint so it can take corrective action.
CoordsRequired
Trigger: A transit node receives a SessionDatagram but has no cached coordinates for the destination. It cannot make a forwarding decision.
Transit node action:
- Create a new SessionDatagram addressed back to the original source, carrying a CoordsRequired payload identifying the unreachable destination
- Route the error via
find_next_hop(src_addr) - If the source is also unreachable, drop silently (no cascading errors)
Source recovery:
- Immediately send a standalone CoordsWarmup (0x14) message to re-warm transit caches along the path (rate-limited: at most one per destination per configurable interval, default 2s)
- Reset CP warmup counter — subsequent data packets piggyback coordinates when possible, or trigger additional CoordsWarmup messages when piggybacking would exceed the transport MTU
- Initiate discovery (bloom-guided LookupRequest) for the destination
- When discovery completes, warmup counter resets again (covers timing gap)
The crypto session remains active throughout — only routing state is refreshed.
PathBroken
Trigger: A transit node has cached coordinates for the destination but no peer is closer to the destination than itself (a local minimum in the tree distance metric). The cached coordinates may be stale.
Transit node action: Same as CoordsRequired — generate error back to source.
Source recovery:
- Immediately send a standalone CoordsWarmup (0x14) message (rate-limited, same per-destination interval as CoordsRequired response)
- Remove stale coordinates from cache
- Initiate discovery for the destination
- Reset CP warmup counter
MtuExceeded
Trigger: A transit node receives a SessionDatagram but the total packet size exceeds the next-hop link MTU. The packet cannot be forwarded without fragmentation, which FIPS does not perform at the mesh layer.
Transit node action:
- Create a new SessionDatagram addressed back to the original source, carrying an MtuExceeded payload identifying the destination, the reporting router, and the bottleneck MTU
- Route the error via
find_next_hop(src_addr) - Drop the original oversized packet
Source recovery: FSP uses the reported bottleneck MTU to adjust its
session-layer path MTU estimate (immediate decrease). The source can then
reduce payload sizes to fit within the discovered path MTU. MtuExceeded is
the reactive complement to the proactive path_mtu field in
SessionDatagram and LookupResponse — the proactive field tracks the
minimum MTU along the forward path, while MtuExceeded signals when an
actual packet exceeds the limit.
Error Signal Rate Limiting
All three error types are rate-limited at transit nodes: maximum one error per destination per 100ms. This prevents storms during topology changes when many packets to the same destination hit the same routing failure simultaneously.
At the source side, CoordsWarmup responses to CoordsRequired/PathBroken are
independently rate-limited: at most one standalone CoordsWarmup per destination
per coords_response_interval_ms (default 2000ms, configurable). This
prevents amplification where a burst of error signals would generate a
corresponding burst of warmup messages.
Error signals (CoordsRequired, PathBroken, MtuExceeded) are handled asynchronously outside the packet receive path, allowing the RX loop to continue processing without blocking on discovery or session repair.
Error Routing Limitation
Error signals route back to the source using find_next_hop(src_addr). For
steady-state data packets (after the CP warmup window), the
transit node may lack cached coordinates for the source. If so, the error is
silently dropped.
This blind spot is partially addressed by CP warmup: transit nodes receive source coordinates during the warmup phase. But after warmup expires and transit caches for the source expire, errors may be lost. The session idle timeout (90s) limits the window — if traffic stops long enough for transit caches to fully expire, the session tears down and re-establishment re-warms the path.
Cold Start → Warm Cache → Steady State
Cold Start
A new node or a node reaching a new destination goes through the following sequence:
- DNS resolution (IPv6 adapter only): Resolve
npub.fips→ populate identity cache with NodeAddr + PublicKey - Session initiation attempt: Fails because no coordinates are cached for the destination
- Discovery: LookupRequest routes through the spanning tree via bloom-guided forwarding; LookupResponse returns the destination's coordinates
- Session establishment: SessionSetup carries coordinates, warming transit caches along the path
- Warmup: First N data packets include CP flag, reinforcing transit caches
The first packet to a new destination always triggers this sequence. The packet is queued (bounded) until the session is established.
Warm Cache
After session establishment and warmup:
- Transit nodes have cached coordinates for both endpoints
- Bloom filters have converged for the destination
- Data packets use minimal headers (no coordinates)
- Routing decisions are fast: bloom candidate selection + distance ranking
Steady State
In steady state, the mesh is mostly self-maintaining:
- TreeAnnounce gossip keeps the spanning tree current
- FilterAnnounce gossip keeps bloom filters current
- Coordinate caches are refreshed by active routing traffic
- Occasional cache misses trigger CP warmup or discovery, but these are rare when traffic is flowing
Cache Expiry and Recovery
When traffic to a destination stops:
- Session idles out (90s) — session torn down
- Coordinate caches expire (300s) — transit nodes forget coordinates
- Bloom filters remain — they have no TTL, so tree-propagated reachability information persists
When traffic resumes:
- Identity cache: usually still populated (LRU, no TTL)
- Session: new establishment required (full handshake)
- Coordinates: discovery may be needed if cache has expired
- SessionSetup re-warms transit caches on the new path
Leaf-Only Operation (under development)
Leaf-only operation is an optimization for resource-constrained nodes (sensors, battery-powered devices). The core infrastructure exists (config flag, node constructor, bloom filter support) but is not yet enabled in normal operation.
Concept
A leaf-only node connects to a single upstream peer that handles all routing on its behalf:
- No bloom filter storage or processing: The upstream peer includes the leaf's identity in its own outbound bloom filters
- No spanning tree participation: The leaf does not offer itself as a potential parent to other nodes
- Simplified routing: All traffic tunnels through the upstream peer
- Minimal resource usage: Suitable for ESP32-class devices (~500KB RAM)
Upstream Peer Responsibilities
The upstream peer:
- Includes the leaf's identity in its outbound bloom filters
- Forwards all traffic addressed to the leaf
- Handles discovery responses on behalf of the leaf
- Maintains the link session with the leaf
What the Leaf Retains
Even as a leaf-only node, it still:
- Maintains its own Noise IK link session with the upstream peer (FMP layer)
- Can establish end-to-end FSP sessions with arbitrary destinations
- Has its own identity (npub, node_addr)
The optimization is purely at the routing/mesh layer — the leaf delegates routing decisions but retains its own end-to-end encryption and identity.
Packet Type Summary
For typical sizes, forwarding category, and the byte-level layouts of each FMP and FSP message type, see ../reference/wire-formats.md. The canonical Packet Type Summary table lives there.
Privacy Considerations
Source and destination node_addrs are visible to every transit node (required for forwarding decisions and error signal routing). FIPS prioritizes low-latency greedy routing with explicit error signaling over metadata privacy.
The node_addr is SHA-256(pubkey) truncated to 128 bits — a one-way hash.
Transit nodes learn which node_addr pairs are communicating but cannot
determine the actual Nostr identities (npubs) of the endpoints. An observer
can verify "does this node_addr belong to pubkey X?" but cannot enumerate
communicating identities from traffic alone.
Onion routing was considered and rejected because it requires the sender to know the full path upfront (incompatible with self-organizing routing) and prevents per-hop error feedback (incompatible with CoordsRequired/PathBroken recovery).
Implementation Status
| Feature | Status |
|---|---|
| Spanning tree formation | Implemented |
| TreeAnnounce gossip | Implemented |
| Bloom filter computation (split-horizon) | Implemented |
| FilterAnnounce gossip | Implemented |
| find_next_hop() priority chain | Implemented |
| Coordinate cache (unified, TTL + refresh) | Implemented |
| Flush coord cache on parent change | Implemented |
| LookupRequest/LookupResponse discovery | Implemented |
| SessionSetup self-bootstrapping | Implemented |
| Hybrid coordinate warmup (CP + CoordsWarmup) | Implemented |
| CoordsRequired recovery | Implemented |
| PathBroken recovery | Implemented |
| MtuExceeded recovery | Implemented |
| LookupResponse proof verification | Implemented |
| Discovery reverse-path routing | Implemented |
| Error signal rate limiting | Implemented |
| Flap dampening (hysteresis + hold-down) | Implemented |
| Link liveness (dead timeout) | Implemented |
| Discovery request deduplication | Implemented |
| Discovery bloom-guided tree routing | Implemented |
| Discovery retry logic | Implemented |
| Discovery originator backoff | Implemented |
| Discovery transit-side rate limiting | Implemented |
| Discovery response-forwarded dedup | Implemented |
| Leaf-only operation | Under development |
| Link cost in parent selection (ETX) | Implemented |
| Link cost in candidate ranking | Implemented |
References
- fips-concepts.md — Protocol overview
- fips-architecture.md — Layer architecture and identity model
- fips-mesh-layer.md — FMP specification
- fips-spanning-tree.md — Tree algorithms and data structures
- fips-bloom-filters.md — Filter parameters and math
- ../reference/wire-formats.md — Wire format reference
- spanning-tree-dynamics.md — Convergence walkthroughs