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

> Discover how GossipSyncManager efficiently synchronizes BitChat messages using GCS filters. Slash sync bandwidth by only sending missing packets.

- Repository: [permissionlesstech/bitchat](https://github.com/permissionlesstech/bitchat)
- Tags: deep-dive
- Published: 2026-08-04

---

**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.

```swift
// 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`](https://github.com/permissionlesstech/bitchat/blob/main/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:

```swift
// 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`](https://github.com/permissionlesstech/bitchat/blob/main/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:

```swift
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

```swift
// 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:

```swift
// 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:

```swift
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`](https://github.com/permissionlesstech/bitchat/blob/main/bitchat/Sync/GossipSyncManager.swift) — Core orchestration, scheduling, packet stores, persistence
- [`bitchat/Sync/GCSFilter.swift`](https://github.com/permissionlesstech/bitchat/blob/main/bitchat/Sync/GCSFilter.swift) — Complete GCS implementation: encoding, decoding, membership testing
- [`bitchat/Models/RequestSyncPacket.swift`](https://github.com/permissionlesstech/bitchat/blob/main/bitchat/Models/RequestSyncPacket.swift) — REQUEST_SYNC serialization with filter parameters and cursors
- [`bitchat/Services/TransportConfig.swift`](https://github.com/permissionlesstech/bitchat/blob/main/bitchat/Services/TransportConfig.swift) — Default constants: `syncGCSMaxBytes = 400`, `syncGCSTargetFpr = 0.01`
- [`bitchat/Services/BLE/BLEService.swift`](https://github.com/permissionlesstech/bitchat/blob/main/bitchat/Services/BLE/BLEService.swift) — Delegate implementation and BLE transport integration
- [`bitchatTests/GossipSyncManagerTests.swift`](https://github.com/permissionlesstech/bitchat/blob/main/bitchatTests/GossipSyncManagerTests.swift) — Schedule handling and request-response validation
- [`bitchatTests/GCSFilterTests.swift`](https://github.com/permissionlesstech/bitchat/blob/main/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.