How BitChat Implements Gossip-Based Synchronization: Protocol Deep Dive

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, 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. 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. The method inspects the MessageType and routes the packet to type-specific PacketStore instances:

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. This TLV-encoded structure carries the GCS filter, type flags (mapped via 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:

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

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