How GossipSyncManager and GCS Filters Enable Efficient Message Synchronization in BitChat

The GossipSyncManager orchestrates peer-to-peer message synchronization by periodically exchanging REQUEST_SYNC packets containing compressed Golomb-Coded Set (GCS) filters, allowing peers to transmit only missing packets rather than full message histories.

The permissionlesstech/bitchat repository implements a bandwidth-efficient gossip protocol for decentralized messaging. At its core, the GossipSyncManager coordinates synchronization between peers using compact GCS filters to advertise packet ownership, while the transport layer handles the actual exchange of missing messages.

Periodic Maintenance and REQUEST_SYNC Generation

The synchronization cycle begins with scheduled maintenance tasks in GossipSyncManager.swift. A repeating timer triggers performPeriodicMaintenance (lines 68-88), which iterates over active syncSchedules and invokes sendPeriodicSync(for:) for each registered packet type. This design ensures that message types—such as chat messages, file fragments, and cryptographic pre-keys—maintain independent sync cadences, preventing high-volume traffic from starving critical updates.

Building the GCS Payload

For each scheduled sync, the manager calls buildGcsPayload(for:types) (lines 24-96) to construct the filter payload. This method gathers the newest packets of the requested types, derives filter parameters p (Rice parameter) and m (modulus), and constructs the filter via GCSFilter.buildFilter. If no packets exist for synchronization, the system transmits a minimal filter with p and m=1 to signal awareness without data. The resulting RequestSyncPacket encapsulates the filter data alongside an optional sinceTimestamp cursor indicating the oldest packet included in the filter.

Dispatching Sync Requests

The sendRequestSync(to:…) method (lines 59-81) finalizes the packet by signing it via signPacketForBroadcast, then dispatches it either as a unicast to a specific peer through delegate?.sendPacket(to:peerID:…) or as a broadcast via delegate?.sendPacket. This delegate pattern, implemented by BLEService.swift, abstracts the underlying Bluetooth Low Energy transport from the synchronization logic.

GCS Filter Implementation and Mechanics

The GCSFilter.swift file implements a Golomb-Coded Set—a space-efficient probabilistic set that enables membership testing with a configurable false-positive rate. This allows requesters to compactly represent thousands of packet IDs in approximately 400 bytes.

Deriving Filter Parameters

The deriveP(targetFpr:) function (lines 26-32) converts the target false-positive rate (default 0.01 or 1%, defined in TransportConfig.syncGCSTargetFpr) into the Rice parameter P = ceil(log₂(1/FPR)). The implementation clamps the FPR to a safe range and guarantees P ≥ 1 to ensure valid encoding.

Encoding Packet IDs

The buildFilter(ids:maxBytes:targetFpr:) method (lines 41-78) executes the encoding pipeline:

1. Capacity estimation: estimateMaxElements(sizeBytes:p:) (lines 34-38) calculates the maximum encodable IDs using bits ≈ sizeBytes·8 and bits per element ≈ P+2.
2. Hash mapping: Each 16-byte packet ID maps to a 64-bit hash (h64), then to a bucket value in [1, M) via mapHash, where M derives from the candidate count.
3. Compression: The method sorts bucket values, computes deltas between consecutive values, and encodes these deltas using Golomb-Rice coding.
4. Size enforcement: If the encoded filter exceeds TransportConfig.syncGCSMaxBytes (400 bytes), the implementation trims the tail—removing the oldest packet IDs—until the payload fits. The returned Params struct records the actual includedCount.

Decoding and Membership Testing

Recipients decode filters using decodeToSortedSet(p:m:data:) (lines 80-96), which reverses the Golomb-Rice encoding to reconstruct the sorted bucket list. Invalid parameters return an empty set, interpreted as "nothing known." Membership testing occurs via contains(sortedValues:candidate:) (lines 98-107), which performs binary search on the decoded set. The mightContain wrapper combines bucket(for:modulus:) (lines 110-114) with the binary search to provide a fast probabilistic check.

Handling Synchronization Requests

When a peer receives a REQUEST_SYNC packet, the receiver-side logic minimizes bandwidth through selective transmission.

Remote Request Processing

The _handleRequestSync method (lines 91-105) first applies rate limiting to prevent sync flooding. It then decodes the incoming filter via GCSFilter.decodeToSortedSet and creates a membership test function. For each packet type specified in the request, the manager iterates over its local PacketStore, applying the sinceTimestamp cursor to skip outdated entries. It transmits only packets whose IDs are not present in the filter, marking transmitted packets with isRSR = true to indicate they are solicited responses rather than unsolicited broadcasts.

Packet Storage and Cleanup

Incoming packets from successful syncs route through onPublicPacketSeen (lines 45-111), which validates freshness before insertion into type-specific PacketStore instances (e.g., messages, fragments). These stores maintain bounded LRU caches with configurable capacity and automatic expiration. The maintenance cycle also invokes cleanupExpiredMessages and cleanupStaleAnnouncementsIfNeeded (lines 99-112) to prune obsolete data and prevent unbounded storage growth.

Bandwidth Efficiency and Scalability Benefits

The GCS-based approach delivers substantial network efficiency improvements over naive synchronization:

• Compact representation: A typical filter occupies approximately 400 bytes regardless of set size, compared to kilobytes or megabytes required for raw ID lists.
• Type-isolated streams: Separate syncSchedules for messages, file fragments, board posts, and pre-key bundles ensure that heavy file transfers do not delay critical control messages.
• Precise incremental sync: Because buildGcsPayload constructs filters from newest-to-oldest packets, trimming affects only ancient history. The sinceTimestamp cursor allows responders to skip packets older than the filter's minimum, eliminating redundant transmission of already-known historical data.

Practical Implementation Example

To initiate synchronization programmatically:

// Initialize from BLEService or similar transport
let syncMgr = GossipSyncManager(
    myPeerID: myPeerID,
    requestSyncManager: requestSyncMgr,
    archive: messageArchive
)
syncMgr.delegate = bleService
syncMgr.start()

// Schedule targeted sync after connection
syncMgr.scheduleInitialSyncToPeer(peerID, delaySeconds: 5.0)

When processing incoming sync requests:

func handleIncoming(_ pkt: BitchatPacket, from sender: PeerID) {
    guard pkt.type == MessageType.requestSync.rawValue,
          let request = RequestSyncPacket.decode(pkt.payload) else { return }
    
    // Automatic filter decoding and missing packet transmission
    syncMgr.handleRequestSync(from: sender, request: request)
}

Building filters for custom packet sets:

let ids = recentPackets.map { PacketIdUtil.computeId($0) }
let params = GCSFilter.buildFilter(
    ids: ids,
    maxBytes: TransportConfig.syncGCSMaxBytes,   // 400 bytes
    targetFpr: TransportConfig.syncGCSTargetFpr  // 0.01
)
let filterData = params.data  // Embed in REQUEST_SYNC

Testing membership of candidate packets:

let sorted = GCSFilter.decodeToSortedSet(
    p: request.p, 
    m: request.m, 
    data: request.data
)
let bucket = GCSFilter.bucket(for: candidateId, modulus: request.m)
let isKnown = GCSFilter.contains(sortedValues: sorted, candidate: bucket)

Summary

• The GossipSyncManager schedules periodic synchronization via performPeriodicMaintenance, triggering sendPeriodicSync for each message type.
• GCS filters compactly represent packet ownership using Golomb-Rice coding, defaulting to 400-byte payloads with 1% false-positive rates as defined in TransportConfig.
• The buildGcsPayload method constructs filters newest-first, enabling precise sinceTimestamp cursors that prevent retransmission of old data.
• Upon receiving REQUEST_SYNC, peers decode filters via decodeToSortedSet and transmit only missing packets marked with isRSR=true.
• Implementation spans GossipSyncManager.swift, GCSFilter.swift, and BLEService.swift, utilizing delegate patterns for transport abstraction.

Frequently Asked Questions

What is the default false-positive rate for GCS filters in BitChat?

According to TransportConfig.swift, the default syncGCSTargetFpr is 0.01 (1%), meaning approximately 1% of membership queries for unseen packets may incorrectly return true. This balances filter size against sync accuracy, ensuring the ~400-byte payload remains practical for Bluetooth Low Energy MTU constraints.

How does GossipSyncManager handle packet trimming when filters exceed size limits?

During buildFilter (lines 41-78), if Golomb-Rice encoding produces data exceeding syncGCSMaxBytes (400 bytes), the implementation iteratively removes the oldest packet IDs from the tail of the sorted list. Because packets are processed newest-first, this trimming preserves recent messages while sacrificing older history, allowing the sinceTimestamp cursor to accurately reflect the filter's coverage window.

What is the purpose of the isRSR flag in sync responses?

The isRSR (Request-Solicited Response) boolean flag marks packets transmitted in response to a specific REQUEST_SYNC packet. This distinction allows receiving peers to distinguish between unsolicited gossip broadcasts and direct responses to their synchronization requests, facilitating accurate sync state tracking and preventing duplicate processing of the same packet through different pathways.

How does BitChat prevent synchronization flooding or resource exhaustion?

The _handleRequestSync method (lines 91-105) implements rate limiting on incoming sync requests to prevent malicious or malfunctioning peers from triggering excessive computational work. Additionally, PacketStore instances enforce bounded LRU caches with automatic expiration, while cleanupExpiredMessages and cleanupStaleAnnouncementsIfNeeded prune obsolete data during each periodic maintenance cycle, ensuring memory usage remains constrained regardless of sync frequency.

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