Files
fips/docs/design/fips-prior-work.md
Johnathan Corgan 51d34ac574 docs: correct documentation and comments that misstate the code
Corrections to the user, reference and design documentation and to
source comments where they disagree with the code. No behaviour or wire
change; the tests added here pin the behaviour the corrected text now
states.

Correct the OpenWrt tutorial on restricting port forwards.

The OpenWrt gateway tutorial said the FIPS mesh firewall is the layer
that limits which peers reach a port forward, pointed at the mesh
firewall how-to, and told readers to add a fips-firewall drop-in for
the listen port. None of that applies: the OpenWrt package ships
neither the mesh firewall baseline nor fips-firewall.service, and on
Linux the baseline hooks the input chain only and never sees a
forward to a LAN host. A reader following the text would leave the
forward open to every mesh peer that can reach the AP.

The tutorial now says that the package's fips zone accepts port
forwards from every mesh peer by default, and shows the fw4 rules
that restrict one: an accept for the allowed peer followed by a
REJECT for the rest, matching the target's port, with the note that
an accept alone restricts nothing because other peers fall through
to the packaged accept. The summary bullet and the troubleshooting
row point at fw4 instead of the mesh firewall, and Linux readers are
sent to the forward-hook recipe in deploy-gateway.md.

Describe conntrack-less pinning and BLE evictions correctly.

The gateway troubleshooting guide said that with no readable conntrack
source a mapping is reclaimed on its TTL and grace period alone. It
left out what the pool does on top of that: no mapping counts as
having carried traffic, so a re-query does not extend a name (only a
used mapping is refreshed, and the answer TTL is capped at the time
left since creation), and at the ceiling a new name can replace any
mapping. The guide now quotes the daemon's whole warning, states both
effects, and says when mappings count traffic again: those created
after conntrack reads have succeeded for three ticks in a row.

The doc comment on the BLE pool's eviction counter said it counts a
non-static peer being displaced. There is no static-peer notion in
the pool; it records the eviction of an unverified link past its
verify grace by a newcomer, which is the only kind the pool makes.

Bring the IPv6 adapter docs and comments in line with the code.

Several statements about the IPv6 adapter disagreed with the code:

- FIPS_IPV6_OVERHEAD was described as 77 bytes on top of the 106-byte
  FIPS_OVERHEAD; 77 is the total (106 + 4 + 7 - 40).
- The effective-MTU table called a 1472-byte transport the standard
  deployment; the UDP default is 1280.
- All ICMPv6 errors were said to be rate-limited by a per-source token
  bucket. Only Packet Too Big is limited, by a per-source minimum
  interval of 100 ms; Destination Unreachable is not limited.
- The TUN writer was said to clamp MSS on inbound SYN-ACKs only, and
  clamped SYN-ACKs were listed as one of its packet sources. The clamp
  acts on any SYN-flagged segment, in both the reader and the writer.
  The design docs, the MTU how-to, the writer's doc comments and its
  trace message now say so.
- The design doc said the reader needs no "is this for me?" check. It
  has one: a packet to the node's own address is written back to the
  TUN, which macOS utun needs.
- The app-owned TUN docs (design doc and the enable_app_owned_tun
  rustdoc) said FIPS neither filters off-mesh destinations nor answers
  them with ICMPv6 there, and that the embedder clamps only outbound
  SYNs. On that path an off-mesh destination is looked up and answered
  with Destination Unreachable on app_inbound_rx (an oversize packet
  with Packet Too Big), and no MSS is clamped in either direction.
- The transport_mtu fallback comment said "UDP first, then Ethernet";
  it takes a configured UDP instance's MTU, else 1280.

A new test pins the app-owned behaviour the rustdoc now states: an
off-mesh unicast destination is answered with Destination Unreachable
from the node's own address on app_inbound_rx, and a multicast
destination gets no answer.

State what the debug inject command and the outbound path do.

The debug_commands documentation (the config field's doc comment, the
configuration reference and the Inject parameters doc) said inject
writes only into one of the calling client's own flows, and so grants
the client nothing it does not already have. inject looks the flow up
by id in the node-wide flow table, so it can write into any flow on
the node, including one another client opened or a listener accepted;
the comment on the command itself and the native API reference already
said so. All three now say the same, and the claim that it grants
nothing new is gone.

The handle_native_outbound doc said an error is reported to the client
rather than as an ICMPv6 message. Nothing is reported: an oversize
datagram is counted in drop_oversize and dropped, a send or
session-initiation failure is logged at debug, and a datagram past the
pending-queue bounds is dropped. The doc now lists those.

Stop claiming a withdrawn advert is deleted with NIP-09.

The Nostr events reference, the discovery design doc and the generic
port-advertisement doc said the node withdraws its advert with a
NIP-09 kind 5 deletion when advertising is turned off or the responder
retires. The node never sends one. The delete plan is produced only
when advertising is off and an advert event id is recorded, but an id
is recorded only after a successful publish, which needs advertising
on, and the advertise flag is fixed when the advert machine is built.
A transient missing advert and shutdown both deliberately skip the
delete, because on relays that apply deletions strictly it can also
remove the replacement the next start publishes.

The docs now say that no deletion is sent, and that an advert the node
stops publishing stays on relays until its NIP-40 expiration,
advert_ttl_secs after publication, unless a newer advert replaces it.
The generic description keeps deletion as something a responder may
do, and says FIPS does not. The doc comments on the publish plan's
delete variant, plan_publish and clear_event_id now say that the
delete path is never reached by a running node, and why.

Correct the traversal signaling description.

The Nostr events reference and the design docs disagreed with the
signaling code in four places:

- inReplyTo was described as the offer's event id. The responder sets
  it to the offer's nonce, the initiator matches answers by nonce, and
  the validator refuses any other value as a session mismatch. An
  implementation written from the docs would have every answer dropped.
- The answer's PunchHint was said to tell both sides when to probe.
  Only the responder probes on it; the initiator does not read the
  hint and starts probing from its own punch_* settings when the
  answer arrives. Fixed in the reference, the port-advertisement doc
  and the discovery design doc.
- All three event kinds were said to be signed with the node's
  identity key. The kind 21059 wrap is signed by a one-time key; only
  the seal inside it is signed with the identity key.
- The FIPS advert example did not say that FIPS emits only the d,
  protocol, version and expiration tags and carries its signaling
  relays and STUN servers in the content as signalRelays and
  stunServers, present only with a udp:nat endpoint.

Two tests pin the behaviour the docs now state: an answer whose
inReplyTo is the offer's event id is refused as a session mismatch,
and a signal's wrap is signed by a key other than the sender's while
unwrapping recovers the sender's identity from the seal.

Label the second msg2 DH as a repeat of es, not se.

The IK msg2 code, the noise module doc, the wire-formats reference, the
mesh-layer design doc and the msg2 diagram all called the second DH in
msg2 `se`. Both sides actually pair the responder's static key with the
initiator's ephemeral key, which is msg1's `es` pairing, so the step
mixes the msg1 `es` value a second time and nothing computes Noise IK's
`se`.

Relabel it as `es` again everywhere, say in the code that it is not
Noise's `se`, that it is the FMP v1 wire format and cannot change
without breaking v1 peers, and that it leaves FMP v1 open to key
compromise impersonation (FRC-1201 Section 9.3). Rename the two local
bindings to `es2`. No behaviour or wire change.

Correct the path MTU notification doc and the fips-mtu design doc.

The PathMtuNotification doc said it is sent by a node that learns a path
MTU from transit router feedback or ICMP Packet Too Big. It is sent by
the session destination, echoing the forward-path minimum it saw in the
envelope's path_mtu; a received MtuExceeded only updates local state.

fips-mtu.md said TCP reports a per-connection MTU from TCP_MAXSEG. TCP
reports the configured mtu and checks sends against it. It also said the
TCP clamp mirror is tighter-only and never loosened. Entries are
released on PathBroken (at most once a second per destination), peer
removal and session timeout, discovery-learned entries expire with the
coordinate cache TTL, and a link seed from a different transport
replaces the stored value. Describe that lifecycle, and add a short
section on the defences against forged signals: the 256-byte floors,
the admission gate, corroboration against what this node has sent, and
the rate-limited release.

Correct transport comments and docs on TCP MTU, mDNS, BLE, Ethernet, Tor and UDP.

Several transport comments and docs described behaviour the code does
not have:

- TCP: the config doc, configuration reference and transport-layer doc
  said the per-connection MTU comes from TCP_MAXSEG. TCP reports the
  configured mtu to FMP and checks sends against it.
- mDNS: the module and supervisor comments said identity is proven by a
  Noise XX handshake. FMP here is Noise IK. Drop the note in the Nostr
  discovery doc that pointed at those comments.
- BLE: the pubkey-exchange prefix doc said it is distinguished from FMP
  packets of version 1 or more. FMP is version 0, so the framer cannot
  tell them apart, as the caution below it already says.
- Ethernet: the config doc said the runtime requires Linux. It is built
  for Linux (AF_PACKET) and macOS (BPF).
- Tor: the config and transport docs, and the onion-service how-to,
  said control_port mode runs an inbound onion service. It only adds
  control-port monitoring to SOCKS5 outbound; directory mode is the
  only inbound mode.
- UDP: the security reference said a UDP instance has no inbound
  exposure until bind_addr is set. A declared UDP instance listens on
  0.0.0.0:2121 by default unless outbound_only is set.

Correct the spanning tree docs on signatures, sequence, sizes, cache invalidation and flap dampening.

- The TreeAnnounce signature was described as covering the entire
  message. It covers SHA-256 of the 48-byte declaration (node_addr,
  parent, sequence, timestamp); version and ancestry are not signed.
- The sequence was said to increment on parent change. It also
  increments on becoming root and on an ancestry change under the same
  parent.
- The TreeAnnounce size table added msg_type twice in the link-overhead
  column. The measured sizes are 168/264/328/488 bytes; note the 36-byte
  link overhead under the table.
- Several design docs and a rate-limit comment said a parent change
  flushes the coordinate cache. The node drops only cached coordinates
  that route through it (parent switch or ancestry change) or sit under
  another root (becoming root), and both on parent loss or loop
  detection.
- Flap dampening was described as engaging after more than
  flap_threshold switches in a sliding window. It engages when the count
  reaches flap_threshold, within a fixed window opened by the first
  switch.

Correct the bloom filter frame size, triggers and propagation bound.

- The wire-formats reference gave the v1 FilterAnnounce with link
  overhead as 1,072 bytes. It is 1,071 (1,035 payload plus 16 header,
  4 timestamp and 16 tag), as the bloom design doc already says.
- The bloom design doc listed local state changes (new identity,
  leaf-only dependent changes) as a send trigger. The identity does not
  change at runtime and nothing outside the tests adds a leaf-only
  dependent, so drop it.
- The bloom and spanning tree docs bounded propagation at about 500 ms
  per hop. Announces leave only on the node's maintenance tick, so the
  bound is about one node.tick_interval_secs per hop (1 s by default);
  the 500 ms debounce is a floor below that.

Correct forwarding docs on ranking, loop freedom and the coordinate cache.

- The mesh-operation doc called link_cost an uncommon tie-breaker
  resolved by tree distance. Candidate ranking compares link cost first;
  tree distance and node_addr break ties.
- Several docs and comments said the strict-progress check prevents
  routing loops even with stale coordinates. Each hop judges progress on
  its own cached coordinates for the destination, so the check does not
  guarantee loop freedom when hops hold different coordinates. Say that,
  and that the TTL bounds any loop.
- The session-layer doc said FMP can fall back to bloom-only routing
  without cached coordinates. find_next_hop returns no next hop on a
  cache miss and the caller signals CoordsRequired.
- The insert_coord_hint doc said a foreign-root destination can never
  be selected by the bloom step. A peer advertising coordinates under
  that root can be; the refusal stands for the reflector reason given
  in the same paragraph.
- The find_next_hop and try_warm_coord_cache_ref doc blocks sat above
  the wrong functions, so rustdoc gave those two no docs and gave
  insert_coord_hint and warm_coord the wrong opening line. Move each
  block onto its function and fix the find_next_hop ranking wording.

Correct FSP restart handling, error datagram sizes and XK labels.

- The session-layer doc said an epoch mismatch on a later handshake
  marks a peer restart and triggers re-establishment. FSP exchanges the
  epoch but never reads it. A SessionSetup naming an established peer
  only arms a handshake beside the running session, and new keys are
  adopted at msg3 only when the authenticated static key matches.
  Describe that, and rename the status row accordingly.
- Wire-format sizes: SessionDatagram + CoordsRequired is 74 bytes, not
  70; SessionDatagram + PathBroken is 76 + 16n, not "70+"; PathBroken
  alone is 40 + 16n, not 35 + 16n; CoordsRequired with link overhead is
  110, not 111; and the CoordsWarmup example is 238, not 239. State in
  the summary table which rows include link overhead.
- Three FSP wire comments called the session handshake Noise IK. It is
  Noise XK, as the module's own phase table says.

Correct the rationale for dropping our own looped-back request.

The comment on the own-request check in classify_request, its test and
the handle_lookup_response doc said that without the check the answer to
our own lookup would be reverse-path forwarded to the peer that looped
the request, and that recent_requests decides originator status. That
stopped being true when classify_response began deciding originator
status from the pending lookup before it reads the transit record.

Say what the check still does: it stops the copy being forwarded a
second time and keeps our own id out of the transit record, so a
response after the lookup completes has nothing to be relayed by. Extend
the test to pin that: once the lookup is accepted, a later response for
the same id is unsolicited.
2026-10-23 04:48:35 +00:00

17 KiB

FIPS Prior Work and References

FIPS builds on proven designs rather than inventing new cryptography or routing algorithms. Nearly every major design decision has deployed precedent. This document collects the relevant prior art, organized by the FIPS subsystem that draws on it, and gathers the academic and standards references cited from the per-subsystem design docs.

Spanning Tree Self-Organization

The idea that distributed nodes can build a spanning tree through purely local decisions — each node selecting a parent based on announcements from its neighbors — dates to the IEEE 802.1D Spanning Tree Protocol (STP, 1985). STP demonstrated that a network-wide tree emerges from a simple deterministic rule (lowest bridge ID wins root election) applied independently at each node. FIPS uses the same principle — lowest node address determines the root — adapted from an Ethernet bridging context to a general-purpose overlay mesh.

Tree Coordinate Routing

The spanning tree coordinates, bloom filter candidate selection, and greedy routing algorithms are adapted from Yggdrasil v0.5 and its Ironwood routing library. Yggdrasil's key insight was using the tree path from root to node as a routable coordinate, enabling greedy forwarding without global routing tables. FIPS adapts these algorithms for multi-transport operation, Nostr identity integration, and constrained MTU environments.

The theoretical foundation for greedy routing on tree embeddings draws on Kleinberg's work on navigable small-world networks, which showed that greedy forwarding succeeds in O(log² n) steps when the network has hierarchical structure. Thorup-Zwick compact routing schemes separately demonstrated that sublinear routing state is achievable with bounded stretch, motivating the use of tree coordinates rather than full routing tables.

Split-Horizon Bloom Filter Propagation

FIPS distributes reachability information using bloom filters computed with a split-horizon rule: when advertising to a peer, exclude that peer's own contributions. This technique is borrowed from distance-vector routing protocols — RIP (1988) and Babel use split-horizon to prevent routing loops by not advertising a route back to the neighbor it was learned from. FIPS applies the same principle to probabilistic set advertisements rather than distance-vector tables.

Cryptographic Identity as Network Address

FIPS nodes are identified by their Nostr public keys (secp256k1). The network address is the cryptographic identity — there is no separate address assignment or registration step. CJDNS pioneered this approach in overlay meshes, deriving IPv6 addresses from the double-SHA-512 of each node's public key. Tor .onion addresses and the IETF Host Identity Protocol (HIP) follow the same principle. FIPS uses Nostr's existing key infrastructure rather than introducing a new identity scheme.

Dual-Layer Encryption

FIPS encrypts traffic twice: FMP provides hop-by-hop link encryption (protecting against transport-layer observers), while FSP provides independent end-to-end session encryption (protecting against intermediate FIPS nodes). This layered approach mirrors Tor, where each relay peels one layer of encryption (hop-by-hop) while the innermost layer protects end-to-end payload. I2P uses a similar garlic routing scheme with tunnel-layer and end-to-end encryption. Unlike Tor and I2P, FIPS does not provide anonymity — its dual encryption protects confidentiality and integrity rather than hiding traffic patterns.

Noise Protocol Framework

FIPS uses the Noise Protocol Framework at both protocol layers, with different handshake patterns chosen for each layer's threat model. FMP link encryption uses Noise IK, providing mutual authentication with a single round trip where the initiator knows the responder's static key in advance. WireGuard uses the same IK base pattern (extended with a pre-shared key as IKpsk2) for VPN tunnels. FSP session encryption uses Noise XK, the same pattern used by the Lightning Network, where the initiator's static key is transmitted in a third message rather than the first. XK provides stronger initiator identity hiding at the cost of an additional round trip — a worthwhile tradeoff for session-layer traffic that traverses untrusted intermediate nodes. At the link layer, where both peers are configured and directly connected, IK's single round trip is preferred.

Specific Noise references and adapted constructions:

  • Perrin, T. "The Noise Protocol Framework". Revision 34, 2018. Framework for building crypto protocols using Diffie-Hellman key agreement and AEAD ciphers. FSP uses the XK handshake pattern.

  • Donenfeld, J.A. "WireGuard: Next Generation Kernel Network Tunnel". NDSS 2017. Transport-independent cryptographic sessions bound to identity keys rather than network addresses; AEAD-only authentication model.

Index-Based Session Dispatch

FIPS uses locally-assigned 32-bit session indices to demultiplex incoming packets to the correct cryptographic session in O(1) time, without parsing source addresses or performing expensive lookups. This directly follows WireGuard's receiver index approach, where each peer assigns a random index during handshake and the remote side includes it in every packet header.

Replay Protection Over Unreliable Transports

FSP and FMP both use explicit per-packet counters with a sliding bitmap window for replay protection — the standard DTLS approach, chosen because implicit nonce counters desynchronize permanently under UDP packet loss or reordering.

  • Rescorla, E., Modadugu, N. RFC 6347: "Datagram Transport Layer Security Version 1.2". 2012. Explicit sequence numbers with sliding bitmap window for replay protection over unreliable transports.

Transport-Agnostic Overlay Mesh

FIPS is designed to operate over any datagram-capable transport — UDP, raw Ethernet, Bluetooth, radio, serial — through a uniform transport abstraction. Several mesh overlays have demonstrated transport-agnostic design: CJDNS runs over UDP and Ethernet, Yggdrasil supports TCP and TLS transports, and Tor can use pluggable transports to tunnel through various media. FIPS extends this pattern to shared-medium transports (radio, BLE) with per-transport MTU and discovery capabilities.

Metrics Measurement Protocol

MMP's design assembles well-established measurement techniques into a unified per-link protocol. The SenderReport/ReceiverReport exchange structure follows RTCP (RFC 3550), which uses the same report pairing for media stream quality monitoring in RTP sessions. MMP's jitter computation uses the RTCP interarrival jitter algorithm directly.

The smoothed RTT estimator uses the Jacobson/Karels algorithm (RFC 6298), the same SRTT computation used in TCP for retransmission timeout calculation since 1988. MMP derives RTT from timestamp-echo in ReceiverReports with dwell-time compensation, rather than from packet round-trips.

The spin bit in the FMP frame header follows the QUIC spin bit (RFC 9312) — a single bit that alternates each round trip, enabling passive latency measurement. FIPS implements the spin bit state machine but relies on timestamp-echo for SRTT, as irregular mesh traffic makes spin bit RTT unreliable.

The Expected Transmission Count (ETX) metric, computed from bidirectional delivery ratios, was introduced by De Couto et al. (2003) for wireless mesh routing and is used in protocols including OLSR and Babel. FIPS computes ETX per-link from MMP loss measurements and uses it for cost-based parent selection and as the primary key in next-hop candidate ranking.

The CE (Congestion Experienced) echo flag provides hop-by-hop ECN signaling, following the TCP/IP ECN echo pattern (RFC 3168). Transit nodes detect congestion via MMP loss/ETX metrics or kernel buffer drops and set the CE flag on forwarded frames; destination nodes mark ECN-capable IPv6 packets accordingly.

Path MTU Discovery

FSP adapts RFC 1191 Path MTU Discovery for overlay networks. The classic ICMP Packet Too Big mechanism is replaced by a transit-node min() propagation in SessionDatagram and LookupResponse plus an end-to-end PathMtuNotification echo back to the source.

  • Mogul, J., Deering, S. RFC 1191: "Path MTU Discovery". 1990. End-to-end path MTU discovery; FSP adapts this for overlay networks using transit-node min() propagation.

Session Restart and Simultaneous Initiation

FSP's epoch-based peer restart detection mirrors IKEv2's INITIAL_CONTACT notification, and its lowest-address-wins simultaneous-initiation tie-breaker mirrors IKEv2's resolution rule.

  • Kaufman, C., Hoffman, P., Nir, Y., Eronen, P., Kivinen, T. RFC 7296: "Internet Key Exchange Protocol Version 2 (IKEv2)". 2014. Simultaneous initiation resolution (§2.8) and INITIAL_CONTACT peer restart detection (§2.4).

Hybrid Coordinate Warmup

FSP's hybrid coordinate warmup (CP flag piggybacking + standalone CoordsWarmup) draws on Yggdrasil's approach of embedding coordinates in session traffic to keep transit caches populated.

  • Yggdrasil Network. Coordinate-based overlay routing with session traffic used to warm transit node coordinate caches.

Cryptographic Primitives

FIPS reuses Nostr's cryptographic stack — secp256k1 for identity keys, Schnorr signatures for authentication, SHA-256 for hashing, and ChaCha20-Poly1305 for authenticated encryption. This is the same primitive set used across Bitcoin, Nostr, and a growing ecosystem of self-sovereign identity systems. No novel cryptography is introduced.

Spanning-Tree Dynamics: Foundations

The CRDT framing, gossip dissemination, failure detection, link metrics, and route stability mechanisms in spanning-tree-dynamics.md draw on a body of academic and standards work, summarized below.

Virtual Coordinate Routing

Greedy Embedding Theory

  • De Couto, D., Aguayo, D., Bicket, J., Morris, R. "A High-Throughput Path Metric for Multi-Hop Wireless Routing". MobiCom 2003. Introduced ETX (Expected Transmission Count) as a link quality metric for wireless mesh networks.

Routing Protocol Stability

  • IEEE 802.1D. "IEEE Standard for Local and Metropolitan Area Networks: Media Access Control (MAC) Bridges". Spanning Tree Protocol (STP) — root election via bridge ID, BPDU exchange.

  • Moy, J. RFC 2328: "OSPF Version 2". 1998. Link-state routing with cumulative path costs and SPF computation. FIPS's local-only cost approach is contrasted with OSPF's cumulative model in spanning-tree-dynamics.md §8.

Distributed Systems Primitives

FIPS Contributions

The protocol builds on these foundations and adds several new elements:

  • Cost-aware parent selection using local-only link metrics (effective_depth = depth + link_cost), replacing Yggdrasil's depth-only selection
  • Combined ETX + SRTT link cost formula with MMP-measured components
  • Flap dampening with mandatory switch bypass
  • Announcement suppression for transient state changes
  • Tree-only bloom filter merge with split-horizon exclusion
  • Hybrid coordinate warmup (CP flag piggybacking plus standalone CoordsWarmup) layered on top of SessionSetup self-bootstrapping
  • Bloom-guided tree routing for discovery (vs. flooding)
  • Reverse-path routing for LookupResponse via recent_requests

External Reference Index

Reference Used by
IEEE 802.1D STP spanning tree, root election
Yggdrasil v0.5 tree coordinates, greedy routing
Ironwood tree coordinates, candidate ranking
Kleinberg, Small-world greedy routing on tree embeddings
CJDNS cryptographic-identity-as-address
Tor onion address scheme, dual-layer encryption
I2P dual-layer encryption (garlic routing)
HIP identity-as-address
Babel split-horizon, ETX
RIP split-horizon
Noise Framework FMP IK, FSP XK
WireGuard IK pattern, receiver-index dispatch, identity-bound sessions
Lightning BOLT #8 XK pattern
QUIC (RFC 9000) spin bit, transport design
QUIC Spin Bit (RFC 9312) passive RTT measurement
RTCP (RFC 3550) sender/receiver report structure, jitter algorithm
TCP SRTT/RTO (RFC 6298) Jacobson/Karels SRTT
ECN (RFC 3168) CE echo
DTLS 1.2 (RFC 6347) replay window
IKEv2 (RFC 7296) INITIAL_CONTACT, simultaneous-initiation tie-breaker
PMTUD (RFC 1191) adapted PMTUD
ETX paper, De Couto et al. ETX metric
OLSR ETX in mesh routing
Nostr identity stack