Reverse (path) Bloom Filter (RBF) for routing packets

[h3lix1]

Reverse-Path Bloom Routing (RBF)

A single‑file, human‑sized guide to adding compact, multi‑path reply routing via Bloom filters.

TL;DR

• Each request carries a Route Bloom Filter (RBF). The origin inserts itself; on the way out, nodes not already in the filter insert themselves. Duplicates from alternate paths are unioned (bitwise‑OR)—but only if the duplicate does not already include the local node.
• The destination picks up to K “winning” request copies (usually the first 2), optionally unions them if density stays low, and sends replies back with that RBF. Nodes forward replies only if they both saw the original request and match the RBF membership test.
• This captures multiple return paths without storing per‑neighbor routes. Bit‑budget is 11–35 bytes depending on filter size.
• Keep the filter useful: limit unions, cap density, and bias toward earlier, lower‑p candidates. We like our bits like our coffee: not too dense.

---

ELI5

• The request is a note everyone passes along. Each person who touches it adds a tiny mark in a compact checklist (the Bloom filter). Duplicates from different streets merge checklists.
• The reply carries that same checklist. If your mark is on it—and you remember seeing the original note—you help it go back. No exact path memory needed.

---

Protocol at a glance

• Request path
  • Origin creates RBF with chosen size and salt, inserts origin NodeID, attaches TLV.
  • On receipt: if RBF present and local node is not a member, insert; cache best RBF per request_id.
  • On duplicates: only union if the incoming RBF does not contain the local node (indicates alternate ingress).
• Destination choice
  • Select up to K winners (default K=2) among early arrivals; estimate density/false positives; only union if still useful.
• Reply path
  • Forward reply only if: (a) this node saw the request recently (request‑ID gate) and (b) the RBF claims the node (membership test). Use jitter/backoff to reduce redundant transmissions.

---

Wire format (TLV)

• Type: a new TLV (choose next free ID in your registry).
• Value layout (LE unless your protocol states otherwise):

Byte 0  : FLAGS = [ size_idx:3 | k_hint:3 | reserved:2 ]
Byte 1-2: SALT16 (per-request salt)
Bytes N : BITSET (m bits, LSB-first within each byte)

• size_idx → m bits: 0→64, 1→96, 2→128, 3→192, 4→256
• Overhead (bytes): 64→11, 96→15, 128→19, 192→27, 256→35
• k_hint: 0=profile default; else clamp to [3..7]
• salt16: randomized per request to avoid trivial steering/forgery

---

Hashing and IDs

• Double hashing: indices i via idx_i = (h1 + i*h2) mod m from two 64‑bit bases.
• Hash: SipHash‑2‑4 (keyed) if available; XXH64 or FNV‑1a64 for tiny builds.
• Identity: hash a stable NodeID (64‑bit EUI/long address). Do not use ephemeral short IDs.

---

Why a salt

• Per‑request unpredictability: A 16‑bit salt changes the bit positions for every flow, so an attacker can’t precompute or reuse patterns to steer packets toward/away from specific nodes across different requests.
• Limits correlation: Without a salt, identical NodeIDs always flip the same bits across flows, making route “signatures” easier to correlate. A salt reduces fingerprinting across requests.
• Safer unions and duplicates: Nodes only union filters that share the same (m, salt), which prevents accidentally OR‑ing stale or unrelated flows together.
• Cheap and effective: 2 bytes buys 65k distinct hash mappings per flow. That’s a big decorrelation win for a tiny overhead in tight packets.
• Works with keyed hashing: Use salt plus a keyed hash (SipHash) to resist off‑path forgeries. Salt ≠ secrecy; it’s about per‑flow variation. The key provides authenticity/DoS resistance; the salt provides diversity.

Salt doesn’t anonymize NodeIDs by itself; it just makes membership mapping flow‑local. For stronger metadata protection, combine salted RBF with the anonymous variants described later.

---

Algorithms (pseudocode)

Request receive (with RBF):

if dedup_seen(request_id):
    if has_RBF and !incoming_rbf.contains(local_node_id):
        best_rbf = OR(best_rbf, incoming_rbf)  // alternate ingress only
    drop_or_forward_per_dup_policy()
else:
    if has_RBF:
        if !rbf.contains(local_node_id):
            rbf.insert(local_node_id)
        cache_best_rbf(request_id, rbf)
    forward_request()

Reply forward:

if !dedup_seen(request_id):
    drop
else if rbf.contains(local_node_id):
    jitter_backoff();
    forward_reply();
else:
    drop

Two‑tier fallback (optional):

• Tier 1: member AND saw request → short jitter
• Tier 2: not member but saw request → long jitter, cancel if Tier‑1 heard

---

Keeping n small in a flood

• Winner‑only reply: destination replies using just one RBF (the best). This keeps n ≈ hops on the used path.
• K winners with density guardrails: pick up to K∈{2,3} early arrivals. Estimate union fill fraction f_union ≈ 1 − ∏(1 − f_i) and p_union ≈ f_union^k. Union only if f_union ≤ f_max (e.g., 0.75) and p_union ≤ p_cap_union (e.g., 10%).
• Probabilistic insertion: insert with probability p_ins to target an expected n_target. If n_est is from max_hops × density, set p_ins = clamp(n_target / max(1, n_est), p_min, 1.0).
• Junction‑only insertion: insert only at merges (≥2 distinct ingress neighbors). Linear relays skip.
• Duplicate gating: only union duplicates that do not already include the local node bit.

---

Sizing

What's Actually Important

When you're building a Bloom filter for RBF, here’s what matters to get good reverse-path coverage and keep false-positives low:

False positive probability ("p"):

• This is the chance that a node who wasn't on the path accidentally passes the membership test.
• Lower p is better, but costs more bits.

Deciding on filter size ("m") and hash count ("k"):

• More bits (m) = fewer false positives, but bigger packets.
• More hashes (k) = fewer false positives, but more CPU (usually 3-7 is practical).

Quick Rules (Best Practices):

• For reliable RBF paths, you want at least 8 bits per hop:
  Keep m/n >= 8 (bits per expected participant, e.g. 128 bits for ~16 hops).

  • If you do this, false positive rate should be ~2% or better.

• Recommended hash count: k ≈ (m/n) * 0.693
  (0.693 is log2; just set k based on m and estimated n, then clamp to [3,7]).

Shortcut Table

Bits per node	False positive rate
4	14.6%
6	5.6%
8	2.1%
10	0.82%
12	0.31%
16	0.046%

Use at least 8 bits per expected hop (node) on the path if you want p under 2%.

Fast cheat sheet (realistic configs):

Below, left column is total bits, top is expected path length (number of hops or nodes).

m \ n	8	12	16	20	32	40	64
64	2.1%	7.7%	14.6%	21.4%	38.2%	46.3%	61.9%
96	0.31%	2.1%	5.6%	10.0%	23.6%	31.5%	48.6%
128	0.045%	0.59%	2.13%	4.6%	14.6%	21.4%	38.2%
192	0.001%	0.045%	0.31%	0.99%	5.6%	10.0%	23.6%
256	~0%	0.0035%	0.045%	0.21%	2.13%	4.6%	14.6%

Maths...

• The actual formula is p ≈ (1 - e^(-k·n/m))^k, but just use the table above or keep m/n ≥ 8.

---

Runtime/On-the-fly estimation

When receiving or building a filter, you can:

• Count set bits: f = popcount/m (fill fraction)
• Estimate how many nodes might have set bits:
  n_hat ≈ -(m/k) * ln(1 - f)
• Estimate false positive on-the-fly:
  p_hat ≈ f^k (if p_hat > 0.10, filter is probably "full"/useless)

Pro tip: If fill fraction f ≥ 0.75 or p_hat > 10%, stop unioning—just use the "best" filter.

---

"Sweet Spot" Sizing Algorithm (for the origin node)

How to choose m and k when you build an RBF at the origin:

1. Estimate how many hops the request might traverse:
   • n_est = round(alpha * max_hops * d_eff)
     • alpha is a fudge factor (~1.5), d_eff is a branching factor (1.0–2.5), max_hops is typical mesh max hop count (0–7)
2. Figure out how many bits you need for your target p:
   • m_req = ceil(1.44 * n_est * log2(1/p_target))
   • For most use, support only a few discrete sizes: 64, 96, 128, 192, or 256 bits. Pick the smallest that’s ≥ m_req.
3. Hash count k:
   • k = clamp(round((m / n_est) * ln2), 3, 7) unless the user specifically asks for something.

---

About "K-winners" and survivor bias

• When picking the best RBF(s) to reply to, prefer filters from the first few arrivals (“early K-winners”).
• The nodes included in these filters tend to be from faster or shorter branches; so your fill fraction (f) and estimated p (p_hat) might look better than the total flood population.
• To be fair, only sample filters/estimate density within a short arrival window (20–60 ms), and pick early arrivals with the lowest p_hat among those.

---

---

Roles: ROUTER vs CLIENT (and “routerified” clients)

Roles stay. RBF doesn’t cancel physics or battery chemistry.

• ROUTER (backbone)
  • Normal forwarding; standard insertion (p_ins); short jitter; can originate larger m for larger hop budgets.
• CLIENT (battery/handheld)
  • Probabilistic/junction‑only request forwarding; conservative insertion; longer jitter (cancel if a router forwards).
• Temporary elevation for sparse filters (per flow)
  • Elevate a CLIENT to act router‑like when: RBF valid; f ≤ 0.25; p_hat ≤ 2%; max_hops ≤ 7 (0‑based, 4‑bit) or at a junction; and token budget available. Use router jitter; keep standard “saw request” and membership gates for replies.
  • Safeguards: token bucket; hysteresis vs recent average f; per‑source rate limits.

Sweeping simplification for want_response traffic

When a packet explicitly requests a reply (want_response = true), treat CLIENT and ROUTER similarly for the parts that matter:

• Reply forwarding: identical behavior for both roles — must have seen the request and pass Bloom membership; use the same (short) jitter window to speed convergence.
• Request forwarding (path building): allow CLIENTs to temporarily use router‑like parameters within guardrails (token budget, max_hops cap, or junction detection). In practice, this makes the reverse path more reliable without materially increasing airtime.
• Defaults: for want_response flows, prefer the K‑winners union at the destination and enable duplicate‑union gating everywhere. Roles still matter for non‑reply traffic, rate limits, and energy policy, but for replies we largely level the playing field.

---

Security and abuse cases

• Crafted dense filters: degrades to flood, not worse; mitigate with request‑ID gate, density cap, and rate limits.
• Targeted filters: use per‑request salt and optionally keyed hashing.
• Replay: dedup caches with an expiration window and hop limits.
• Parser safety: strict length checks, clamp k, reject invalid sizes.
• Privacy: Bloom doesn’t list IDs, but patterns can be correlated; rotate salts and avoid exposing internal density.
• Sparse‑coercion of clients: require gate conditions and token budget; rate limit per source.

---

Integration notes (MeshPacketSerializer.cpp and friends)

• Add TLV type for RBF and parser support; unknown TLVs should be safely skipped.
• C++ skeleton (adapt naming to your codebase):

struct RbfView {
    const uint8_t* bits;  // bitset pointer
    uint16_t m_bits;      // 64/96/128/192/256
    uint8_t  k;           // 3..7
    uint16_t salt16;      // per-request
    bool contains(uint64_t node_id) const;
};

struct RbfBuilder {
    std::array<uint8_t, 32> buf{}; // up to 256 bits
    uint16_t m_bits{0};
    uint8_t  k{0};
    uint16_t salt16{0};
    void insert(uint64_t node_id);
    void or_inplace(const RbfView& other);
    size_t serialize(uint8_t* out, size_t out_len) const; // write FLAGS+SALT+BITSET
};

static inline void rbf_indices(uint64_t node_id, uint16_t salt, uint16_t m, uint8_t k, uint16_t* idx);

• Request send (origin): choose size/k via sweet‑spot; random salt16; insert origin; append TLV.
• Request receive: parse TLV; if first‑seen and not member, insert; cache best; duplicates only OR if incoming does not contain local node.
• Reply send: pick K winners and (optionally) union with density caps; copy RBF into reply.
• Reply receive: require seen request; require membership; role‑aware jitter (prefer routers).
• Popcount and thresholds: compute f=b/m; skip unions that exceed f_max or p_cap_union.

---

Future ideas and variants

• Anonymous reverse path (no return address):

  • Origin omits an explicit return address and relies on the RBF as the sole breadcrumb trail. Use a per‑flow random salt and add a small amount of controlled noise (e.g., 1–2 decoy insertions) so the filter doesn’t trivially fingerprint a single node.
  • Trade‑off: improves metadata privacy (no explicit NodeID in headers), but side‑channels remain (timing, region participation). Consider bounding fill fraction to avoid easy correlation.

• Anonymous destination DMs:

  • Destination replies using the same RBF and the same salt, avoiding explicit IDs. Gated by “saw request” to stop far‑away leakage. Do not change salt mid‑flow; that would invalidate membership tests along the reverse path.
  • Add optional cover traffic (occasional decoy replies) to make traffic analysis harder in sensitive deployments.

• Channel delivery via Bloom sets:

  • Build a destination Bloom filter that encodes a set of intended recipients for a channel. Requests are forwarded broadly; only members (plus false positives) process payloads.
  • Combine with RBF reverse path for aggregated acks or replies. Guard against ack storms with K‑winner selection, jitter, and per‑node reply budgets.

• Layered filters (region → node):

  • Use a coarse region/cluster filter to steer inter‑city hops, then a finer per‑node filter inside the region. Keeps spill low across cities while preserving fidelity locally.

• Multi‑salt epochs:

  • Rotate the salt at hop or time intervals to reduce adversarial collisions and make forged unions harder; carry the current epoch in FLAGS.

• Counting/Stable Bloom variants:

  • If code/bytes allow, small counting filters can support limited deletions or better union introspection (e.g., estimating overlap) at the cost of a few bytes.

If any of these spark joy, we can sketch wire impacts and safety checks next.

Test plan (short)

• Unit: hash index bounds; insert/contains; union correctness; TLV parse/build; k clamps; popcount math.
• Integration: line and diamond topologies; duplicate gating (union only when local not set); reply gating; role‑aware jitter; client elevation triggers and denials.
• Simulation: measure p empirically vs tables; off‑path forwards; delivery ratio and latency vs baseline; abuse scenarios (dense/sparse crafted filters).
• KPIs: reply delivery +X% multi‑path; extra transmissions per reply hop ≤ Y at defaults; overhead ≤ 19B (128‑bit) for medium hop budgets; CPU cost k≤7 within MCU budget.

---

Diagrams

Sequence (forward then reply):

sequenceDiagram
    participant S as Source
    participant A as Node A
    participant B as Node B
    participant C as Node C
    participant D as Destination
    S->>A: Request + RBF{S}
    A->>B: Request + RBF{S,A}
    A->>C: (dup) union if local not in RBF
    B->>D: Request + RBF{S,A,B,C}
    D-->>B: Reply + RBF
    B-->>A: Member + saw request → forward
    A-->>S: Member + saw request → forward

Loading

Flow (request handling):

flowchart TD
  R[Recv Request] --> S{Seen request_id?}
  S -- yes --> U{Has RBF?}
  U -- no --> X[Drop/dup policy]
  U -- yes --> G{Local in incoming?}
  G -- no --> O[best_rbf = best_rbf OR incoming]
  G -- yes --> X
  S -- no --> H{Has RBF?}
  H -- no --> F[Forward normally]
  H -- yes --> M{Member?}
  M -- no --> I[Insert self]
  M -- yes --> C[Cache]
  I --> C
  C --> F

Loading

Bloom Filters Explained

This is a short, friendly primer for engineers on how Bloom filters differ from regular hash tables, and why “collisions” are a feature, not a bug, when you want tiny, fast membership tests.

---

Hash Tables: collisions are undesirable

• Goal: map each key to a bucket; avoid collisions to keep lookups O(1) and precise.
• When collisions happen, implementations use chaining or open addressing to still find the exact key.
• Hash tables answer: “Is X here?” with exact yes/no. No false positives.

Example (abbreviated, mod 8 table)

Node	Key	Hash32 (hex)	Slot = hash % 8	Table bucket
A	0xA1B2C3D4	0x5f83a1b2	2	[A]
B	0xDEADBEEF	0x1cc9f00d	5	[B]
C	0x01234567	0x7a10cafe	6	[C]
D	0xFACEFEED	0x33aa1177	1	[D]

• If another key also hashes to slot 2, that’s a collision; the table must store both and do extra work to retrieve the right one.

---

Bloom Filters: collisions are intentional (and cheap)

• Goal: track set membership using a tiny bit array of length m and k hash functions.
• To insert an item, you compute k indices and set those k bits to 1.
• To query, you compute the same k indices and check those bits. If any is 0 → definitely not present. If all are 1 → probably present (could be a false positive).
• Bloom filters answer: “Is X in the set?” with no false negatives and some controllable false positives.

Key differences vs hash tables

• We never store the actual items; only a bitset.
• Collisions don’t require extra data structures; they’re baked in.
• The more items you insert, the more bits turn to 1, increasing the chance of false positives.

---

A tiny worked example (m = 16 bits, k = 3)

Start with all zeros (bit 0 is the least significant bit of byte 0):

Bits: 0000 0000 0000 0000

Let’s say our k=3 indices come from good 64-bit hashes reduced mod 16.

Insert A (indices: 1, 7, 12)

• Set bits 1, 7, 12 →
• Bits: 1001 0000 1000 0010

Insert B (indices: 3, 7, 9)

• Set bits 3, 7, 9 →
• Bits: 1001 0101 1100 1010

Insert C (indices: 0, 12, 15)

• Set bits 0, 12, 15 →
• Bits: 1101 0101 1100 1011

Now query D (indices: 1, 9, 12)

• All three of those bits are already 1 → D “matches” even though it was never inserted. That’s a false positive by design.

Table (easier to scan)

Step	Indices set	Bits set to 1 (positions)	Bitset (m=16)
Start	—	—	0000 0000 0000 0000
Insert A	1, 7, 12	1, 7, 12	1001 0000 1000 0010
Insert B	3, 7, 9	1, 3, 7, 9, 12	1001 0101 1100 1010
Insert C	0, 12, 15	0, 1, 3, 7, 9, 12, 15	1101 0101 1100 1011
Query D	1, 9, 12	all 1? yes → “present”	(false positive)

Takeaway: collisions let us compress many items into a tiny bitset, at the cost of some “friendly lies” (false positives) but zero false negatives.

---

When “too many” match: additional nodes enter the mix

• As you insert more items, the fraction of bits set (fill fraction) increases.
• With a high fill fraction, many random queries happen to find all k bits already 1, and become false positives.

Back-of-envelope for m = 16, k = 3

• After n inserts, the false positive probability is roughly:
  p ≈ (1 − e^(−k·n/m))^k

n inserts	fill approx	p false positive (approx)
2	~0.31	~5%
4	~0.50	~15%
6	~0.63	~27%
8	~0.73	~38%

• In other words: more density → more “extra” nodes passing the test.
• In RBF usage we keep this in check by:
  • Choosing m and k sensibly (e.g., ≥ 8 bits per expected participant, k in 3–7).
  • Limiting unions and skipping duplicates that don’t add new paths.
  • Gating by “saw the original request” so off‑path regions don’t forward replies even when they hit a false positive.

---

Why this is useful for reverse-path routing

• We don’t need exact who‑handed‑to‑whom state—just a compact breadcrumb trail.
• False positives are acceptable because we layer gating (must have seen the request) and backoff; only a few extra nodes help forward a reply.
• Bit‑budget stays tiny (8–32 bytes), which matters on constrained links.

That’s the magic: hash tables avoid collisions to guarantee precision, while Bloom filters embrace controlled collisions to trade a few “maybe” answers for massive space savings and speed.

---

Final notes

• This is a drop‑in, bit‑budget‑aware way to get multi‑path replies without per‑neighbor state. If the filter turns into all ones, we've re-invented flood routing
• Start with 128‑bit filters and k=5 for medium hop budgets. Enable K=2 unions with f_max=0.75, p_cap_union=0.10. Tighten/loosen after field telemetry.
• Keep CLIENTs conservative; elevate to ROUTERs when sparse filters and budget permit.

[NomDeTom]

What is a token budget? It suddenly appears halfway down, without explanation.

What problem is this solving? Next-hop is much lower broadcast budget, even if the whole nodeID is included. I can't see how this is stored on a per-destination basis, and even if it were stored in a similar manner to next-hop (which is currently one byte per node in nodeDB), with a hop-limited mesh, the routing to the destination isn't usually the constraint.

Edit to add: the favouring of shorter response times only works in the router CW. For the client CW, that should be reversed.

[NomDeTom]

@h3lix1 I'm copy-pasting your response to me on Discord here for posterity:

It handles multiple paths. The winning packet to the destination includes the nodes it took to receive it, even if there were multiple paths and nodes. When it sends back a response each path along the way has its own filter to know how to reach the destination, even if it is multiple hops away
It handles async routing as if it takes ABCD to receive a packet, each one creates a union with the bloom filter (think of it as a hash you intentionally create collisions so it matches multiple desired nodes)

When returning the packet, it also sends back the filter saying ABCD should repeat this packet. If A has a direct path to D, it can skip B and C
Each node keeps this bloom filter for each destination, since each node has a different view of the network.

But In general, if a node receives a packet from two different locations that came two very distinct paths, it can union the bloom filter so it contains nodes from both paths. Obviously if too many nodes are in the bloom filter it will be like flood routing today and the packet will have no real directionality.
So the filter needs enough bits to be specific enough to exclude all the nodes you don't want. There are false positives here, and that is generally considered acceptable for bloom filters

Usually below 2%, but given the nature of RF it might be better to allow 5%
Either way, it sends the packet in the general direction in which it came using purposeful hash collisions to help know where that is.
So if there are 6 cities in a row connected by only a few nodes each, it will only send to the city that sent the packet.. the bigger downside is mobility in that nodes move.. at which point we'll need to resort to flood routing.

But that will only really be a problem if moving between metro areas.. and even then will update the bloom filters on the first packet received in the new location

[h3lix1]

One additional thing to add here is that this method of routing packets is exclusionary.

The benefit of bloom filters is that sometimes there are false positives, but as designed, there are no false negatives.

Due to this, the expectation is that nodes not in the bloom filter (including routers) will not forward the packet. This does not apply to flooded broadcast traffic (like channels) but it does apply to unicast traffic like DMs and traceroutes.

In future there could be a bloom filters used for concepts like multi-cast group chats where if everybody in the chat is local to an area, there is no need to send the message further. The concept of a channel becomes less network-wide if we want it to be.

Depending on how far we want to implement this, it would be a fundamental change to the protocol. For example, instead of "to" address that is directed to a single device, it will become a "bloom" address that will include the single device, but all other devices along the way.

This will partially obscure the destination and source of the packet to avoid easily tracking packet metadata. With enough logger nodes it might be easier to trace, but not as easy as today.

There is potential here for "virtual" IDs where the virtual ID can be associated with multiple physical devices to receive messages, as long as all the devices are in the same bloom address and broadcasted periodically, packets will be routed back to all/most of the devices.

Anyway, a lot of potential, probably more worthy of a 3.x release if this is something people are interested in. A lot of this can initially be implemented to be backward compatible with 2.x to not break existing nodes.

[h3lix1]

Ah, token buckets was a concept separate from this, but the idea is that clients can act as routers sometimes if the bloom filters show they are the best path. Basically, become a router for very specific packets, but don't make it a habit. (use tokens to keep track of this habit)

So something like this could replace CLIENT_BASE if the route back has been determined that the CLIENT is the best path back. There is a lot of work that can be done here. For example, if the bloom filter for receiving a packet is X and bloom filter for the destination is Y, and it's very significantly different, tell client can take the initiative and "please route this packet, because apparently there are only a few paths between the source and destination, and you're it"

[korbinianbauer]

Might have been me who brought up that term, I'm still working on a description of the concept. I want to get it right in simulation before wasting anyone else's time :)

That's fairly separate from this routing proposal though... would be compatible anyways.