# How the BitChat Gossip Sync Protocol Uses GCS Filters for Efficient P2P Synchronization

> Discover how BitChat's gossip sync protocol leverages GCS filters for efficient P2P synchronization. Save bandwidth by sending only missing messages within a 400-byte budget.

- Repository: [permissionlesstech/bitchat](https://github.com/permissionlesstech/bitchat)
- Tags: internals
- Published: 2026-08-02

---

**BitChat's gossip sync protocol uses compact Golomb-Coded Set (GCS) filters to advertise which packets a peer already possesses, enabling bandwidth-efficient synchronization where responders transmit only missing messages while staying within a 400-byte budget per sync round.**

BitChat is a peer-to-peer messaging application that implements a gossip-style synchronization protocol to converge message histories across mesh networks. According to the `permissionlesstech/bitchat` source code, the protocol leverages Golomb-Coded Set (GCS) filters to create compact "have-sets" that describe local packet collections without revealing full content lists, dramatically reducing bandwidth consumption compared to full inventory exchanges.

## How GCS Filters Power the Gossip Sync Protocol

The synchronization process centers on the `GossipSyncManager` in [`bitchat/Sync/GossipSyncManager.swift`](https://github.com/permissionlesstech/bitchat/blob/main/bitchat/Sync/GossipSyncManager.swift), which orchestrates periodic sync rounds. Each round constructs a GCS filter representing the peer's current packet inventory, using parameters defined in [`bitchat/Services/TransportConfig.swift`](https://github.com/permissionlesstech/bitchat/blob/main/bitchat/Services/TransportConfig.swift).

### Local Packet Collection and Age Windows

Before building a filter, the manager gathers candidate packets from bounded caches (`PacketStore`) maintained for each message type. Freshness windows enforce automatic expiration to keep filter sizes predictable:

- **Fragments**: 15-minute retention window
- **Public chat messages**: 6-hour retention window  
- **Announcements and file-transfer pieces**: Type-specific age limits

These windows ensure that the GCS filter only covers recent, relevant traffic, preventing unbounded growth of the synchronization set.

### Constructing the GCS Filter

When a sync round triggers (either periodically or on-demand), the manager calls filter construction methods implemented in [`bitchat/Sync/GCSFilter.swift`](https://github.com/permissionlesstech/bitchat/blob/main/bitchat/Sync/GCSFilter.swift). The process follows three deterministic steps:

1. **`GCSFilter.deriveP`** calculates the optimal bit-prefix length `p` based on the target false-positive rate (`config.gcsTargetFpr = 0.01` or 1%)
2. **`GCSFilter.estimateMaxElements`** predicts the maximum number of elements that fit within the byte budget (`config.gcsMaxBytes = 400`)
3. **`GCSFilter.buildFilter`** generates the final filter data containing the parameters `(p, m, data)` and the count of included elements

```swift
// Building a GCS payload for a sync round (excerpt from GossipSyncManager)
private func buildGcsPayload(for types: SyncTypeFlags,
                             fragmentIdFilter: String? = nil) -> Data {
    // Gather candidate packets for the requested types
    let candidates = // ... messages, fragments, announces, etc.
    
    // Derive filter params from TransportConfig
    let p = GCSFilter.deriveP(targetFpr: config.gcsTargetFpr)
    let nMax = GCSFilter.estimateMaxElements(sizeBytes: config.gcsMaxBytes, p: p)
    
    // Build the filter over newest-first packet IDs
    let params = GCSFilter.buildFilter(
        ids: ids,
        maxBytes: config.gcsMaxBytes,
        targetFpr: config.gcsTargetFpr
    )
    
    // Handle partial coverage with since-timestamp cursor...
}

```

### The Since-Timestamp Cursor

When the candidate set exceeds the filter capacity, the implementation attaches a **since-timestamp cursor** to the sync request. This cursor, implemented in lines 586-595 of [`GossipSyncManager.swift`](https://github.com/permissionlesstech/bitchat/blob/main/GossipSyncManager.swift), indicates the timestamp boundary of the newest packets included in the filter. The responder skips older packets when evaluating differences, ensuring that omitted packets are not re-transmitted unnecessarily while maintaining protocol correctness.

## The Sync Request and Response Flow

The complete synchronization cycle involves filter transmission, probabilistic membership testing, and selective packet relay.

### Broadcasting REQUEST_SYNC Packets

The constructed filter payload is encoded into a `RequestSyncPacket` (type `0x21) defined in [`bitchat/Nostr/RequestSyncPacket.swift`](https://github.com/permissionlesstech/bitchat/blob/main/bitchat/Nostr/RequestSyncPacket.swift). This packet contains:

- The GCS parameters (`p`, `m`, `data`)
- Sync type flags indicating which packet categories to compare
- Optional since-timestamp cursor
- Optional fragment-ID filter for stream-specific sync

The manager transmits this payload to peers via unicast or broadcast, registering the request with `RequestSyncManager` for replay-protected handling.

### Efficient Membership Testing on the Responder

Upon receiving a `REQUEST_SYNC`, the peer decodes the filter using `GCSFilter.decodeToSortedSet` to reconstruct a sorted array of hash buckets. The responder then performs cheap membership tests using `GCSFilter.bucket` and `GCSFilter.contains` to check each local packet:

```swift
// Responding to a REQUEST_SYNC (excerpt from _handleRequestSync)
private func _handleRequestSync(from peerID: PeerID,
                                request: RequestSyncPacket) {
    // Decode filter into sorted set for O(log n) lookups
    let sorted = GCSFilter.decodeToSortedSet(p: request.p,
                                             m: request.m,
                                             data: request.data)
    
    func mightContain(_ id: Data) -> Bool {
        let bucket = GCSFilter.bucket(for: id, modulus: request.m)
        return GCSFilter.contains(sortedValues: sorted, candidate: bucket)
    }
    
    // Iterate over locally stored packets
    for pkt in messages.allPackets(isFresh: isPacketFresh) {
        // Respect the requester's timestamp cursor
        if let since = request.sinceTimestamp, pkt.timestamp < since { continue }
        
        // Only send packets NOT advertised by the requester's filter
        if !mightContain(PacketIdUtil.computeId(pkt)) {
            var toSend = pkt
            toSend.ttl = 0
            toSend.isRSR = true  // Solicited response marker
            delegate?.sendPacket(to: peerID, packet: toSend)
        }
    }
}

```

Packets missing from the filter (indicating the requester lacks them) are transmitted as **Requested Solicited Responses (RSR)** with TTL set to 0, ensuring they propagate only to the requesting peer.

### Selective Sync for Fragments

For file-transfer fragments, the protocol supports a specialized **fragment-ID filter** that narrows the diff to specific fragment streams. This bypasses the standard since-timestamp cursor for those streams while still utilizing GCS membership tests to avoid sending already-received pieces, as implemented in lines 440-452 of [`GossipSyncManager.swift`](https://github.com/permissionlesstech/bitchat/blob/main/GossipSyncManager.swift).

## Bandwidth Optimization and Rate Limiting

The GCS filter design provides deterministic bandwidth characteristics. A 400-byte filter can represent thousands of packet IDs with a 1% false-positive rate, while the since-cursor mechanism prevents synchronization storms.

To prevent amplification attacks, the protocol implements rate limiting: each peer is constrained to `responseRateLimitMaxResponses = 8` responses per 30-second window. This limits the potential for malicious peers to force expensive set difference computations or traffic multiplication.

## Summary

- **GCS filters act as compact "have-sets"** in [`GossipSyncManager.swift`](https://github.com/permissionlesstech/bitchat/blob/main/GossipSyncManager.swift), advertising packet ownership using approximately 400 bytes per sync round.
- **Three-phase filter construction** involves `deriveP`, `estimateMaxElements`, and `buildFilter` from [`GCSFilter.swift`](https://github.com/permissionlesstech/bitchat/blob/main/GCSFilter.swift) to optimize for a 1% target false-positive rate.
- **Since-timestamp cursors** handle partial filter coverage gracefully, ensuring older omitted packets are not re-transmitted while maintaining sync correctness.
- **Probabilistic membership testing** using `decodeToSortedSet` and `bucket` allows responders to identify missing packets in O(log n) time.
- **Rate limiting** at 8 responses per 30 seconds prevents abuse while preserving mesh convergence properties.

## Frequently Asked Questions

### What is a GCS filter in the context of BitChat?

A **Golomb-Coded Set (GCS) filter** in BitChat is a compact probabilistic data structure used to represent a set of packet IDs that a peer already possesses. Implemented in [`bitchat/Sync/GCSFilter.swift`](https://github.com/permissionlesstech/bitchat/blob/main/bitchat/Sync/GCSFilter.swift), it uses Golomb coding to compress hash values with a tunable false-positive rate (default 1%), allowing a 400-byte filter to represent thousands of packet IDs efficiently.

### How does BitChat handle synchronization when there are too many packets for one filter?

When the packet collection exceeds filter capacity, BitChat attaches a **since-timestamp cursor** to the `REQUEST_SYNC` packet. This cursor indicates the timestamp of the oldest packet included in the filter. The responding peer skips any packets older than this cursor, ensuring the filter remains compact while preventing re-transmission of historical data the requester may already have.

### What prevents a malicious peer from flooding the network with sync requests?

BitChat implements rate limiting in [`GossipSyncManager.swift`](https://github.com/permissionlesstech/bitchat/blob/main/GossipSyncManager.swift) that restricts each peer to **8 solicited responses per 30-second window**. Additionally, the `RequestSyncManager` registers outgoing requests to validate incoming responses, providing replay protection against request spoofing and amplification attacks.

### Why does BitChat use different age windows for different packet types?

Different packet types have different **freshness windows** (15 minutes for fragments, 6 hours for public messages) to optimize bandwidth and storage. These windows, enforced in `PacketStore`, ensure that high-volume, ephemeral data like file fragments do not crowd out important public chat messages from the limited 400-byte GCS filter budget, maintaining synchronization efficiency across diverse traffic patterns.