How GossipSyncManager Uses GCS Filters for Bandwidth-Efficient Message Synchronization in BitChat

The GossipSyncManager exchanges compact Golomb-Coded Set (GCS) filters with peers to transmit only missing packets, reducing sync bandwidth by orders of magnitude compared to full ID enumeration.

The GossipSyncManager is the central orchestrator of BitChat's peer-to-peer gossip protocol, enabling decentralized nodes to stay synchronized without centralized coordination. By encoding known packet identifiers into probabilistic GCS filters, the manager performs on-demand, filter-based synchronization that scales efficiently across multiple data types.

Request-Sync Lifecycle

The synchronization flow consists of six coordinated stages triggered by periodic timers and inbound network events.

1. Periodic Scheduling and Dispatch

A repeating timer drives the sync process. Every periodicTimer interval, performPeriodicMaintenance iterates over registered syncSchedules and invokes sendPeriodicSync(for:) for each active type. This method either unicasts to known peers or broadcasts cluster-wide depending on connection state.

// Internal scheduling flow (GossipSyncManager.swift, lines 68-88)
periodicTimer → performPeriodicMaintenance()
    ↓
for schedule in syncSchedules {
    sendPeriodicSync(for: schedule.type)
}

2. GCS Filter Construction

The buildGcsPayload(for:types) method (lines 24-96 of GossipSyncManager.swift) assembles the outbound filter:

• Gathers newest packets matching requested types
• Derives filter parameters p (Golomb-Rice parameter) and target capacity
• Invokes GCSFilter.buildFilter to encode packet IDs
• Falls back to minimal filter (p with m=1) when no candidates exist

The filter construction respects both byte budget and recency priority: newer packets are encoded first, and oldest entries are trimmed if the encoded result exceeds TransportConfig.syncGCSMaxBytes.

3. Request Transmission

The completed RequestSyncPacket is signed via signPacketForBroadcast then dispatched through the delegate:

// Targeted unicast
delegate?.sendPacket(to: peerID, packet: signedPacket)

// Or broadcast
delegate?.sendPacket(packet: signedPacket)

4. Remote Peer Processing

Upon receiving a REQUEST_SYNC packet, _handleRequestSync (lines 91-105) executes on the recipient:

1. Rate limiting applied first to prevent spam
2. Filter decoding via GCSFilter.decodeToSortedSet(p:m:data:)
3. Membership testing with mightContain for each local packet
4. Cursor application — packets older than sinceTimestamp are skipped
5. Response marking — returned packets have isRSR = true flag set

Only packets whose IDs fail the filter membership test are transmitted back to the requester.

5. Incoming Packet Integration

Responses and unsolicited packets route through onPublicPacketSeen (lines 45-111), which:

• Validates freshness and cryptographic signatures
• Stores in type-appropriate PacketStore instances (messages, fragments, etc.)
• Maintains bounded LRU caches with automatic expiration per capacity limits

6. Periodic Cleanup

Each maintenance tick invokes cleanupExpiredMessages and cleanupStaleAnnouncementsIfNeeded (lines 99-112) to prune obsolete data and control memory growth.

GCS Filter Internals

The GCSFilter implementation in bitchat/Sync/GCSFilter.swift provides compact probabilistic set encoding with configurable false-positive rate.

Parameter Derivation

deriveP(targetFpr:) (lines 26-32) converts target false-positive rate to Golomb-Rice parameter:

P = ceil(log₂(1/FPR))  // Default FPR 0.01 → P = 7

The implementation clamps FPR to safe operational bounds and enforces P ≥ 1.

Capacity Estimation

estimateMaxElements(sizeBytes:p:) (lines 34-38) approximates element capacity:

bits ≈ sizeBytes × 8
bits per element ≈ P + 2
maxElements ≈ bits / (P + 2)

Filter Construction Pipeline

buildFilter(ids:maxBytes:targetFpr:) (lines 41-78) executes:

1. Derive P and capacity cap from parameters
2. Compute modulus M from candidate count (hashRange)
3. Map each 16-byte PacketID to 64-bit hash, then to [1, M) via mapHash
4. Sort mapped values and encode deltas with Golomb-Rice coding
5. Trim tail (oldest) if encoded size exceeds maxBytes
6. Return Params with actual includedCount

Decoding and Membership Testing

// Decode filter bytes back to sorted bucket set
let sortedBuckets = GCSFilter.decodeToSortedSet(
    p: request.p,
    m: request.m,
    data: request.data
)

// Test candidate membership
let bucket = GCSFilter.bucket(for: candidateId, modulus: request.m)
let isKnown = GCSFilter.contains(sortedValues: sortedBuckets, candidate: bucket)

Architectural Advantages

Benefit	Mechanism	Impact
Bandwidth reduction	~400-byte filter replaces full ID lists	50-100× reduction vs. naive enumeration
Type isolation	Separate syncSchedules per data type	Heavy traffic (file fragments) cannot starve critical types (pre-key bundles)
Precise cursors	Newest-first construction with sinceTimestamp	Responder skips guaranteed-unneeded historical data
Bounded resources	LRU caches with explicit capacity	Predictable memory regardless of network size

Practical Integration

Instantiating and operating the manager:

// From BLEService initialization
let syncMgr = GossipSyncManager(
    myPeerID: myPeerID,
    requestSyncManager: requestSyncMgr,
    archive: messageArchive
)
syncMgr.delegate = bleService  // Provides transport via GossipSyncManagerDelegate
syncMgr.start()

// Trigger peer-specific sync after connection
syncMgr.scheduleInitialSyncToPeer(peerID, delaySeconds: 5.0)

Manual filter construction for testing or custom protocols:

let packetIds = recentPackets.map { PacketIdUtil.computeId($0) }

let params = GCSFilter.buildFilter(
    ids: packetIds,
    maxBytes: TransportConfig.syncGCSMaxBytes,   // 400 bytes default
    targetFpr: TransportConfig.syncGCSTargetFpr  // 1% false positive rate
)

// params.data is embedded in RequestSyncPacket.payload
// params.p, params.m, params.includedCount available for metrics

Key Source Files

• bitchat/Sync/GossipSyncManager.swift — Core orchestration, scheduling, packet stores, persistence
• bitchat/Sync/GCSFilter.swift — Complete GCS implementation: encoding, decoding, membership testing
• bitchat/Models/RequestSyncPacket.swift — REQUEST_SYNC serialization with filter parameters and cursors
• bitchat/Services/TransportConfig.swift — Default constants: syncGCSMaxBytes = 400, syncGCSTargetFpr = 0.01
• bitchat/Services/BLE/BLEService.swift — Delegate implementation and BLE transport integration
• bitchatTests/GossipSyncManagerTests.swift — Schedule handling and request-response validation
• bitchatTests/GCSFilterTests.swift — Encoding correctness, edge cases, bucket mapping

Summary

• GossipSyncManager coordinates periodic, filter-based synchronization across multiple data types via pluggable schedules
• GCS filters compress known packet ID sets into ~400-byte payloads with 1% configurable false-positive rate
• Newest-first encoding with automatic tail-trimming ensures filters always cover the most valuable recent data
• Sparse sync responses — responders transmit only packets whose IDs are absent from the received filter
• Type-specific isolation prevents high-volume traffic categories from interfering with critical cryptographic material sync

Frequently Asked Questions

How does the GossipSyncManager decide which packets to include in a GCS filter?

The manager queries each relevant PacketStore for newest-first packets matching the requested types, up to the capacity estimated by GCSFilter.estimateMaxElements. If encoding exceeds maxBytes, it trims from the end (oldest entries), ensuring the filter always represents the most recent data. The includedCount and sinceTimestamp in the resulting RequestSyncPacket precisely indicate the filter's coverage window.

What happens when a GCS filter has false positives?

With default 1% FPR, there's a 1% chance a packet ID will incorrectly appear "known" to the recipient. This causes the responder to withhold that packet, forcing the requester to retrieve it on a subsequent sync cycle with a fresh filter. The protocol remains correct (eventual consistency) with minor latency increase, trading bandwidth for this probabilistic optimization.

Can sync schedules be customized per data type?

Yes. The syncSchedules dictionary maintains independent SyncSchedule instances for each MessageType category — messages, fragments, file transfers, pre-key bundles, and board posts. Each schedule carries its own interval, priority, and filter capacity allocation, allowing fine-grained control over synchronization behavior across traffic classes.

How does the manager handle peers that never respond to REQUEST_SYNC?

The GossipSyncManager does not implement explicit timeout/retry logic for individual peer responses. Instead, reliance on periodic scheduling ensures eventual retries: the next periodicTimer firing will generate fresh requests with updated GCS filters covering any newly received packets. Connection-layer failures are handled by the GossipSyncManagerDelegate implementation (typically BLEService), which manages peer liveness detection independently.

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