How the Spray-and-Wait Mechanism Works in BitChat: Binary Spray Routing Explained

BitChat's spray-and-wait mechanism attaches a decrementing spray budget to each message envelope, using binary spraying to halve the budget with every forward until it reaches 1 (carry-only), ensuring reliable delivery without network flooding.

BitChat implements a spray-and-wait routing protocol to solve message delivery in decentralized, peer-to-peer networks where nodes lack persistent connectivity. This mechanism, defined in the permissionlesstech/bitchat repository, allocates a finite spray budget to each CourierEnvelope that decrements through a binary spray algorithm until the message becomes carry-only and stops replicating.

Spray Budget Storage in CourierEnvelope

The spray budget lives inside the CourierEnvelope structure, which serves as the low-level representation of a message. According to the source, the field is encoded as a TLV (Type-Length-Value) that older clients ignore for backward compatibility.

In localPackages/BitFoundation/Sources/BitFoundation/CourierEnvelope.swift at line 29, the documentation states: "spray). 1 means carry-only — deliver to the recipient, never re-spray." This encoding ensures that even legacy nodes can receive and deliver messages without understanding the spray semantics, though they will not participate in the spraying process.

Initial Budget Configuration

Before an envelope enters the network, TransportConfig determines the default spray budget. The comment at line 391 in bitchat/Services/TransportConfig.swift specifies the "Initial spray-and-wait budget per deposited envelope," defining how many times a message may be split and forwarded by couriers before transitioning to carry-only state.

Binary Spray Implementation in CourierStore

The core logic resides in CourierStore.swift, which manages the state machine for message propagation. The implementation tracks two critical fields for every envelope: sprayBudget (remaining forwards allowed) and sprayedTo (the set of courier noise keys that have already received a copy).

Tracking Spray State

At line 41 of bitchat/Services/Courier/CourierStore.swift, the persistent state includes a comment explaining the budget field: "Remaining spray-and-wait budget (1 = carry-only)." Additionally, line 45 tracks the sprayedTo set to prevent duplicate transmissions: "Couriers this envelope was already sprayed to, so a repeat announce..."

The Binary Spray Algorithm

When a courier forwards a message, the takeSprayCopies method executes a binary spray at lines 356-368. The logic follows three strict rules:

1. Skip envelopes with a budget of 1 (carry-only) or already sprayed to the target courier
2. Halve the remaining budget using integer division (e.g., budget 4 becomes 2)
3. Create a new copy with the reduced budget and update the sprayedTo set

The Swift implementation simplifies to:

// CourierStore.swift – binary spray logic (lines 356-368)
if envelope.sprayBudget > 1 && !envelope.sprayedTo.contains(courierNoiseKey) {
    var copy = envelope
    copy.sprayBudget /= 2                // halve the budget
    copy.sprayedTo.insert(courierNoiseKey)
    sprayed.append(copy)
}

This exponential decay ensures the message propagates rapidly through the network initially, then naturally limits itself as the budget approaches 1.

Persistence and State Merging

When envelopes persist to disk, older versions may lack the sprayBudget and sprayedTo fields. Line 83 in CourierStore.swift handles this gracefully: "Files written before tiers/spray lack the newer fields; treat that..." The decoder defaults these values, ensuring backward compatibility.

During state reconciliation at line 564, the merge logic unions the sprayedTo sets: merged[index].sprayedTo = combinedSprayedTo. This guarantees that spray history survives application restarts without duplication.

Redelivery Windows and Cleanup

The spray-and-wait period defines how long a pre-key sealed ciphertext remains eligible for retransmission. Line 515 in bitchat/Services/NoiseEncryptionService.swift mentions the "window for spray-and-wait redeliveries, then is deleted for good," establishing a TTL that prevents indefinite storage of undelivered messages.

Practical Code Examples

Creating a Spray-Enabled Envelope

import BitFoundation

let recipientKey = Data(repeating: 0xB4, count: 32)          // Recipient's static noise key
let envelope = CourierEnvelope(
    noiseStaticKey: recipientKey,
    sprayBudget: 4,          // Start with budget 4 (halved to 2, then 1)
    sprayedTo: []            // No couriers sprayed yet
)

Spraying Copies to New Couriers

// Assume `store` is an instance of `CourierStore`
let courierNoiseKey = Data(repeating: 0xC1, count: 32)      // Target courier's noise key
let copies = store.takeSprayCopies(for: courierNoiseKey)

// Returns at most one envelope with halved budget
if let copy = copies.first {
    // Transmit `copy` over Bluetooth LE or IP to the courier
}

Handling Received Envelopes

func handleIncoming(_ envelope: CourierEnvelope) {
    // Forward only if budget permits
    if envelope.sprayBudget > 1 {
        let forwardCopies = store.takeSprayCopies(for: nextCourierKey)
        // Transmit to additional couriers
    }
    // Always deliver payload to intended recipient
}

Test Coverage

The CourierStoreTests.swift file at lines 340-365 verifies binary spray behavior, asserting that budgets halve correctly (sprayedToX.first?.copies == 2, sprayedToY.first?.copies == 1) and that duplicate sprays to the same courier are rejected. Integration testing in BLEServiceCoreTests.swift (lines 378-389) confirms the BLE transport layer respects spray-only semantics when forwarding via Bluetooth LE.

Summary

• Spray budget is stored in CourierEnvelope as a TLV field, defaulting to carry-only (1) for backward compatibility
• Binary spraying halves the budget at each hop, implemented in CourierStore.takeSprayCopies at lines 356-368
• Duplicate prevention uses the sprayedTo set tracked per envelope and merged during state reconciliation
• Carry-only state occurs when budget reaches 1, stopping further replication but allowing final delivery
• Redelivery windows in NoiseEncryptionService enforce TTL limits on spray-and-wait attempts

Frequently Asked Questions

What does a spray budget of 1 mean in BitChat?

A spray budget of 1 indicates carry-only mode. The courier delivers the message to the intended recipient but never sprays it to other couriers. This represents the terminal state of the spray-and-wait lifecycle, ensuring the message stops replicating while still allowing final delivery.

How does the binary spray algorithm prevent duplicate forwarding?

The algorithm checks the sprayedTo set (tracked in CourierStore.swift at line 45) before creating copies. If the target courier's noise key exists in the set, takeSprayCopies returns an empty array. During state merges at line 564, the implementation unions these sets to maintain accurate spray history across app restarts.

Where is the spray-and-wait budget initialized?

The initial budget is defined in TransportConfig.swift at line 391, which specifies the default allocation "per deposited envelope." This value is assigned when a user deposits a message into the BitChat network, before the first courier receives the envelope.

What happens when a courier receives a message with an exhausted spray budget?

When sprayBudget equals 1, the binary spray logic in CourierStore.swift skips the envelope completely. The courier treats the message as carry-only: it decrypts and delivers the payload to the recipient if possible, but never adds the envelope to its spray queue for forwarding to other nodes.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}