Path-vector routing: from 7.8x to <1.5x

The problem

Campfire's original routing (v0.4.2) was flood-and-dedup: when a router received a message, it forwarded to every connected peer except the sender. Duplicates were dropped by an in-memory dedup table keyed on message ID. Simple, correct, and catastrophically expensive at scale.

The amplification factor on a network of N nodes with average degree D is O(D). At 50 instances with average degree 3, each message triggers ~7.8 forwarding operations per useful delivery. That's 7.8x amplification—and it grows as the network grows.

The dedup table doesn't help with amplification. It prevents infinite loops, but it can't prevent the initial burst. Every router still floods outward before its peers' dedup tables fire. The result is a wave of redundant sends that collapses only after traveling the diameter of the network.

An adversary sending M messages into a v0.4.2 network causes M × D × N network operations. At 50 instances and degree 3, that's 150x traffic amplification per message sent. Path-vector reduces this to M × N—the redundant wave disappears.

The design

Path-vector routing is the same mechanism BGP uses to prevent routing loops in the global Internet. Each route advertisement carries a list of the routers it has traversed. A router that sees its own ID in the path drops the advertisement. Loops are structurally impossible—not suppressed after the fact.

Applied to campfire, path-vector works at the beacon level. A routing:beacon carries a path field: an ordered list of router node IDs from origin to current node. When a router re-advertises a beacon, it appends its own ID. When a router sees its own ID in an incoming beacon's path, it drops the beacon.

The key insight: if beacons don't loop, routes don't loop, and messages following those routes don't loop. The forwarding problem reduces to "who is the next-hop for this campfire?"—a single-peer forward instead of a broadcast.

Beacon paths

A beacon originates with path: [node_A]. As it propagates through the network, each router appends its own ID and re-signs before re-advertising.

The path field is included in the inner_signature computation—signed by the campfire's own key. A router cannot remove itself from the path or reorder entries without invalidating the signature. Path tampering is cryptographically blocked.

Backward compatibility

A beacon without a path field is valid. v0.5.0 routers treat missing path as an empty path (legacy beacon) and fall back to flood-and-dedup behavior for that route. v0.4.2 routers ignore the path field per the protocol's forward-compatibility rule (unknown fields are passed through). The path-vector amendment is fully backward-compatible with existing deployments.

Routing table

The v0.5.0 routing table extends the v0.4.2 entry with two new fields:

// RouteEntry — one entry per campfire_id per gateway
type RouteEntry struct {
    CampfireID    string
    Endpoint      string
    Transport     string
    Gateway       string
    Received      time.Time
    Verified      bool
    InnerTimestamp int64
    Path          []string  // NEW: node_ids from origin to advertiser
    NextHop       string    // NEW: direct peer that delivered the beacon
}

When the routing table has multiple entries for the same campfire (multi-path), route selection uses:

1. Shortest path — fewer hops means fewer forwarding points, lower amplification, and faster delivery.
2. Freshest inner timestamp — among equal-length paths, prefer the most recent advertisement.
3. First received — tie-breaker: stability over churn.

Forwarding a message for campfire C: look up the best route's next_hop, send once. The campfire key signs a provenance hop. Done. No broadcast, no wave, no dedup race condition.

Loop detection

The BGP loop detection rule, directly applied: when a router receives a beacon, it checks whether its own node_id appears anywhere in the path field. If yes, this beacon has looped back—drop it.

// Loop check on beacon receipt (O(path_length), bounded by max_hops)
func (rt *RoutingTable) HasLoop(path []string, selfNodeID string) bool {
    for _, nodeID := range path {
        if nodeID == selfNodeID {
            return true
        }
    }
    return false
}

// On receipt:
if rt.HasLoop(beacon.Path, selfNodeID) {
    log.Debug("beacon loop detected, dropping", "campfire", beacon.CampfireID)
    return  // structural prevention, not dedup recovery
}

The loop check runs before the dedup check. A looping beacon is discarded without recording its ID in the dedup table—loop prevention is a routing-layer decision, not a dedup entry. The dedup table remains for transient duplicates during route convergence and for legacy nodes that don't carry path fields.

Defense-in-depth

Three layers of loop prevention, in order of precedence:

1. Path-vector loop rejection (primary) — structural, fires on every beacon, O(path_length). Prevents loops before they form.
2. Message ID dedup (secondary) — handles transient duplicates during route convergence, and legacy nodes without path fields.
3. Max hops (tertiary) — bounds the damage radius of misconfigured topologies. Default: 8 hops. A message exceeding max_hops is dropped.

Peer-needs-set

Path-vector tells a router where to send messages destined for a campfire. But campfire traffic is bidirectional—messages also flow from a campfire toward its subscribers. The peer-needs-set handles the reverse direction.

Each router maintains a peer-needs-set per campfire: the set of direct peers that have demonstrated interest in messages for campfire C. A peer is added to the set when it:

• Delivers a message for C to this router (it's clearly participating)
• Is a next_hop in the routing table for C (learned from beacon)
• Sent a routing:beacon for C through this router (re-advertiser)

The full forwarding set for campfire C is:

forwarding_set = (peer_needs_set[C] ∪ routing_next_hops[C]) - sender

This ensures traffic flows in both directions without requiring explicit subscribe messages. The peer-needs-set is populated as a side effect of normal operation—no additional protocol messages, no subscription handshake.

Amplification proof

The proof runs a 50-instance, 5-campfire simulation. Instances are connected in a ring with random skip links (average degree ~3). Each campfire has 3 members scattered across the ring.

Results

Why <1.5x and not 1.0x?

Perfect 1.0x would mean every message takes exactly one network path with no redundant sends. The 1.5x ceiling allows for:

• Multi-path redundancy — operators may configure k=2 paths for fault tolerance. With k=2, amplification is 2x per forward node, but recovery from peer failure is automatic.
• Route convergence — during beacon propagation, a node may not yet have learned the optimal next-hop. It forwards to the currently-known best peers, which may include one redundant send before the routing table stabilizes.
• Peer-needs-set overlap — a peer may appear in both the routing next-hops and the peer-needs-set for the same campfire, producing one extra send before the sets merge.

The 1.5x ceiling is the theoretical floor for fault-tolerant delivery in a ring topology. Degenerate single-path topologies achieve 1.0x; real deployments with redundancy land between 1.0x and 1.5x.

Implementation

Four changes to the campfire routing stack, shipped in a single swarm across 11 agents in 7 waves. All changes are backward-compatible.

1. BeaconDeclaration.Path

// Added to BeaconDeclaration in pkg/routing/beacon.go
type BeaconDeclaration struct {
    CampfireID        string   `json:"campfire_id"`
    Endpoint          string   `json:"endpoint"`
    // ... existing fields ...
    Path              []string `json:"path,omitempty"`     // NEW
    InnerSignature    string   `json:"inner_signature"`
}

// Signing input now includes path
func SignBeacon(b *BeaconDeclaration, key ed25519.PrivateKey) error {
    input := beaconSigningInput(b.CampfireID, b.Endpoint, b.Transport,
        b.Description, b.JoinProtocol, b.Timestamp,
        b.ConventionVersion, b.Path)  // path added
    // ...
}

2. RouteEntry Path and NextHop

// Extended in pkg/routing/table.go
type RouteEntry struct {
    // ... existing fields ...
    Path    []string `json:"path"`     // NEW: full path from origin
    NextHop string   `json:"next_hop"` // NEW: direct peer (first hop toward us)
}

// Route selection: shortest path first
func (rt *RoutingTable) BestRoute(campfireID string) *RouteEntry {
    entries := rt.entries[campfireID]
    sort.Slice(entries, func(i, j int) bool {
        if len(entries[i].Path) != len(entries[j].Path) {
            return len(entries[i].Path) < len(entries[j].Path)
        }
        return entries[i].InnerTimestamp > entries[j].InnerTimestamp
    })
    if len(entries) == 0 { return nil }
    return &entries[0]
}

3. Beacon re-advertisement

// In the router's beacon handler
func (r *Router) ReAdvertiseBeacon(b *BeaconDeclaration, fromPeer string) {
    // 1. Check for loop
    if hasLoop(b.Path, r.NodeID) {
        return
    }
    // 2. Append own node ID
    b2 := *b
    b2.Path = append(append([]string{}, b.Path...), r.NodeID)
    // 3. Re-sign (threshold=1; advisory for threshold>1)
    SignBeacon(&b2, r.CampfireKey)
    // 4. Advertise to own peers (except fromPeer)
    r.AdvertiseToPeers(&b2, fromPeer)
}

4. Peer-needs-set

// RoutingTable.peerNeeds tracks which peers need each campfire
peerNeeds map[string]map[string]struct{} // campfire_id -> {peer_id}

func (rt *RoutingTable) RecordPeerNeed(campfireID, peerID string) {
    if rt.peerNeeds[campfireID] == nil {
        rt.peerNeeds[campfireID] = make(map[string]struct{})
    }
    rt.peerNeeds[campfireID][peerID] = struct{}{}
}

// ForwardingSet combines next-hops and peer-needs-set
func (rt *RoutingTable) ForwardingSet(campfireID, exclude string) []string {
    seen := make(map[string]bool)
    var out []string
    for _, e := range rt.entries[campfireID] {
        if e.NextHop != "" && e.NextHop != exclude && !seen[e.NextHop] {
            seen[e.NextHop] = true
            out = append(out, e.NextHop)
        }
    }
    for peer := range rt.peerNeeds[campfireID] {
        if peer != exclude && !seen[peer] {
            seen[peer] = true
            out = append(out, peer)
        }
    }
    return out
}

$ cd campfire
$ go test -v -run TestPathVectorAmplification ./pkg/routing/
$ go test -v -run TestLoopDetection ./pkg/routing/
$ go test -v -run TestPeerNeedsSet ./pkg/routing/
$ go test -v ./pkg/routing/  # full suite