# How BitChat Implements Gossip-Based Synchronization: Protocol Deep Dive

> Explore how BitChat uses gossip-based synchronization with GCS filters for efficient decentralized mesh sync. Learn the protocol details and optimize message history diffing without full data transfers.

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

---

**BitChat achieves decentralized mesh synchronization by exchanging compact Golomb-Coded Set (GCS) filters containing deterministic packet IDs, allowing peers to efficiently diff their broadcast message histories without transmitting full datasets.**

BitChat (permissionlesstech/bitchat) is an open-source, peer-to-peer messaging system designed for offline-capable mesh networks. At the heart of its data propagation lies a **gossip-based synchronization** protocol that keeps distributed peers consistent while minimizing bandwidth consumption and storage overhead through probabilistic data structures and type-aware scheduling.

## Core Architecture of the Gossip Protocol

The implementation centers on [`GossipSyncManager.swift`](https://github.com/permissionlesstech/bitchat/blob/main/GossipSyncManager.swift), which orchestrates state reconciliation through three foundational pillars: deterministic packet identification, set compression via GCS filters, and independent sync schedules per data type.

### Deterministic Packet ID Generation

Every broadcast packet receives a unique 16-byte identifier computed by `PacketIdUtil.computeId(_:)` in [`Sync/PacketIdUtil.swift`](https://github.com/permissionlesstech/bitchat/blob/main/Sync/PacketIdUtil.swift). This function performs a SHA-256 hash over the packet's type, sender ID, timestamp, and payload, taking the first 16 bytes to produce a deterministic, collision-resistant ID. These IDs serve as the atomic units of set membership testing during gossip rounds.

### Golomb-Coded Set (GCS) Compression

Rather than transmitting raw packet lists, BitChat encodes the set of known packet IDs into a Golomb-Coded Set (GCS) filter. The `buildGcsPayload(for:fragmentIdFilter:)` method constructs this compact representation using parameters `p` (Golomb-Rice parameter) and `m` (modulus) derived from a target false-positive rate (`gcsTargetFpr`). This allows a node to share thousands of packet IDs within a strict byte budget (`gcsMaxBytes`), while enabling recipients to test membership locally without decompressing the full set.

### Typed Sync Schedules

Different packet categories—messages, fragments, file transfers, board posts, and pre-key bundles—maintain independent `SyncSchedule` configurations. The protocol enforces per-type capacity limits (`seenCapacity`, `fragmentCapacity`) and periodic intervals (`messageSyncIntervalSeconds`, `fragmentSyncIntervalSeconds`), ensuring high-volume traffic like file fragments cannot starve critical control messages such as pre-key bundles.

## The Packet Lifecycle: From Receipt to Gossip

### Ingestion via Packet Stores

Incoming broadcast packets enter the gossip system through `onPublicPacketSeen(_:)` in [`GossipSyncManager.swift`](https://github.com/permissionlesstech/bitchat/blob/main/GossipSyncManager.swift). The method inspects the `MessageType` and routes the packet to type-specific `PacketStore` instances:

```swift
case .message:
    guard isBroadcastRecipient, isPacketFresh(packet) else { return }
    let idHex = PacketIdUtil.computeId(packet).hexEncodedString()
    messages.insert(idHex: idHex, packet: packet, capacity: max(1, config.seenCapacity))
    archiveDirty = true

```

This switch block (lines 52-86) handles ingestion for `messages`, `fragments`, `fileTransfers`, `groupMessages`, and `latestPrekeyBundleByPeer` stores, immediately computing the packet ID and flagging the archive for persistence when modified.

### Capacity Management and Freshness

Each `PacketStore` enforces both size limits and temporal boundaries. Entries exceeding `maxMessageAgeSeconds` or `prekeyBundleMaxAgeSeconds` are pruned, while hard caps (`seenCapacity`, `fragmentCapacity`) trigger LRU eviction. This bounded storage model prevents unbounded memory growth in long-running mesh nodes.

## Constructing Sync Requests with GCS Filters

When a sync round triggers—either by periodic timer or explicit request—the `buildGcsPayload(for:fragmentIdFilter:)` method (lines 24-96) executes a five-phase pipeline:

1. **Candidate Collection**: Queries fresh packets from all requested types via `messages.allPackets(isFresh:)` and equivalent fragment/file transfer stores.
2. **Temporal Sorting**: Orders candidates newest-first while respecting per-type capacity constraints.
3. **Parameter Derivation**: Calculates GCS parameters `p` and `m` to satisfy the configured false-positive target.
4. **Filter Construction**: Creates the GCS filter over selected packet IDs using the `GCSFilter` type imported from `BitFoundation`.
5. **Metadata Attachment**: Appends a `sinceTimestamp` cursor indicating the oldest covered packet and optional fragment-specific filters for targeted recovery.

The resulting `Data` payload is wrapped in a `RequestSyncPacket`, signed, and transmitted via the `GossipSyncManager.Delegate` transport layer.

## The Two-Way Sync Exchange

### Requesting State with REQUEST_SYNC

Peers initiate reconciliation by transmitting a `RequestSyncPacket` defined in [`Models/RequestSyncPacket.swift`](https://github.com/permissionlesstech/bitchat/blob/main/Models/RequestSyncPacket.swift). This TLV-encoded structure carries the GCS filter, type flags (mapped via [`SyncTypeFlags.swift`](https://github.com/permissionlesstech/bitchat/blob/main/SyncTypeFlags.swift)), and optional cursors. The encoding supports version-compatible bitfield expansion, allowing future protocol extensions without breaking backward compatibility.

### Diffing and Selective Relay

Upon receiving a request, the recipient decodes the filter using `RequestSyncPacket.decode(from:)` and reconstructs the sorted value set:

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

```

The node iterates its local stores for the requested types. For each packet where `mightContain(id)` returns **false**, the node re-transmits that packet to the requester with the `isRSR` (Requested Solicited Response) flag set. This differential synchronization ensures only missing packets traverse the network, reducing bandwidth by orders of magnitude compared to full state transfers.

## Rate Limiting and Maintenance

The `SyncResponseRateLimiter` class guards against sync flooding by throttling how frequently a single peer can trigger full diff computations. Concurrently, `performPeriodicMaintenance()` handles background cleanup: expiring stale packets, persisting the public message archive when `archiveDirty` is true, and scheduling subsequent sync rounds according to the `SyncSchedule` configuration.

## Persistence Across Restarts

Public messages optionally survive application restarts through `GossipMessageArchive` ([`Sync/GossipMessageArchive.swift`](https://github.com/permissionlesstech/bitchat/blob/main/Sync/GossipMessageArchive.swift)). The manager calls `restoreArchivedMessages()` during initialization and `persistArchiveIfDirty()` following insertions, enabling devices to resume gossip participation with intact history after power cycles or app terminations.

## Summary

- **Deterministic IDs**: `PacketIdUtil.computeId(_:)` generates unique 16-byte identifiers via SHA-256 hashing of packet metadata and payload.
- **GCS Compression**: `buildGcsPayload` constructs bandwidth-efficient set representations using Golomb-Coded Sets with configurable false-positive rates.
- **Type Isolation**: Independent sync schedules and `PacketStore` instances prevent high-volume data types from monopolizing gossip bandwidth.
- **Differential Sync**: Peers exchange compact filters via `RequestSyncPacket` and relay only missing packets identified through local set difference calculations.
- **Resource Bounds**: Rate limiters, capacity caps, and periodic maintenance ensure the protocol remains viable on resource-constrained mobile devices.

## Frequently Asked Questions

### How does BitChat prevent duplicate messages during synchronization?

BitChat prevents duplicates through deterministic packet ID generation and set membership testing. When a peer receives a `RequestSyncPacket`, it checks each candidate packet's ID against the incoming GCS filter using `mightContain(_:)`. Only packets definitively absent from the requester's set (returning false) are retransmitted, ensuring each message propagates exactly once to nodes lacking it.

### What is the purpose of Golomb-Coded Sets in the gossip protocol?

Golomb-Coded Sets (GCS) compress the set of known packet IDs into a compact, probabilistic structure. This allows BitChat nodes to share their entire seen-message history within strict byte budgets (`gcsMaxBytes`) while enabling recipients to perform local membership tests without transferring the full ID list. The implementation leverages the `GCSFilter` type from BitFoundation to balance compression ratio against false-positive rates.

### How does BitChat handle different message types during synchronization?

The protocol uses `SyncTypeFlags` to encode requested message categories (messages, fragments, file transfers, etc.) as bitfields within `RequestSyncPacket`. Each type maintains independent `PacketStore` instances with dedicated capacity limits (`seenCapacity`, `fragmentCapacity`) and sync intervals (`messageSyncIntervalSeconds`, `fragmentSyncIntervalSeconds`), ensuring critical control traffic receives bandwidth guarantees regardless of bulk data transfer volumes.

### Can BitChat resume synchronization after an application restart?

Yes, through optional persistence via `GossipMessageArchive`. When configured, the `GossipSyncManager` restores previously seen public messages from disk during initialization using `restoreArchivedMessages()`, and persists new arrivals via `persistArchiveIfDirty()`. This allows nodes to rejoin the mesh with intact gossip state, avoiding costly full-state rebuilds after device reboots or app restarts.