How MessageDeduplicator Prevents Duplicate Messages in BitChat's Mesh Network

The MessageDeduplicator uses a thread-safe LRU cache with time-based expiry to ensure every packet is processed exactly once, even when the same message arrives from multiple peers or is replayed after a network resend.

In decentralized mesh networks, packets can reach a node through multiple paths or be resent after a timeout, creating duplicate processing overhead. To solve this, the permissionlesstech/bitchat repository implements MessageDeduplicator, a Swift utility that combines O(1) lookup speed with automatic eviction of stale entries to keep the mesh efficient.

Thread-Safe LRU Cache Architecture

The deduplicator manages all state in bitchat/Utils/MessageDeduplicator.swift. It uses an NSLock instance to serialize every mutating operation, guaranteeing safe concurrent access when networking threads from BLE and Nostr protocols write simultaneously.

Initialization and Default Limits

When instantiated, the deduplicator reads configuration from TransportConfig, specifically the maxAge (time-to-live) and maxCount (capacity) parameters. These boundaries prevent unbounded memory growth during long-running mesh sessions.

// Create a deduplicator with the default mesh limits
let dedup = MessageDeduplicator()

Fast O(1) Lookup Table

At its core, the class maintains a dictionary lookup: [String: Date] that maps message IDs to timestamps. This structure provides constant-time checks when networking code queries whether a specific ID has been seen.

Duplicate Detection and Expiry Logic

The isDuplicate(_:) method serves as the primary gatekeeper for incoming packets in MessageDeduplicator.swift.

Stale Entry Cleanup

Before checking for duplicates, the method calls cleanupOldEntries(before:) to remove timestamps older than the configured maxAge. This time-based expiration runs synchronously on every check, ensuring old mesh packets naturally age out without manual intervention.

Duplicate Check and Recording

If the ID exists in lookup after cleanup, the function returns true (duplicate). For new IDs, it records the current timestamp and returns false, allowing the message to proceed through the processing pipeline.

func handleIncoming(message: BitchatMessage) {
    // Each message has a unique identifier (e.g., `message.id`)
    guard !dedup.isDuplicate(message.id) else {
        // Duplicate → ignore it
        return
    }
    // Process the new message normally
    process(message)
}

Memory Management and LRU Eviction

To respect the maxCount limit defined in TransportConfig, the deduplicator implements batched eviction rather than single-item removal.

Batch Eviction Strategy

After inserting a new entry, trimIfNeeded() checks the cache size. When the active count exceeds the limit, it evicts roughly 25% of the oldest entries in a single batch. This amortized cleanup prevents performance spikes during high-throughput mesh flooding while keeping memory usage bounded.

Advanced Operations

Beyond standard duplicate checking, the class provides specialized utilities for mesh protocol requirements.

Force-Marking Processed IDs

For protocol-level messages like ACKs that must be remembered without a prior duplicate check, markProcessed(_:) adds the ID directly to the lookup table. This ensures subsequent replays are still blocked, maintaining consistency even for administrative packets.

Full Session Reset

When the mesh tears down or a session ends, reset() clears all internal state by emptying the lookup dictionary and releasing the lock, preparing the deduplicator for a fresh connection.

Integration with BLE and Nostr Services

The deduplicator integrates throughout the BitChat networking stack. In bitchat/Services/BLE/BLEService.swift, incoming BLE packets pass through isDuplicate(_:) before processing. A higher-level wrapper, MessageDeduplicationService (defined in bitchat/Services/MessageDeduplicationService.swift), manages separate deduplication channels for content keys, Nostr event IDs, and acknowledgement packets.

// Using the higher‑level service that wraps the deduplicator
let dedupService = MessageDeduplicationService(
    contentCapacity: 100,
    nostrEventCapacity: 100
)

func ingest(publicMessage: PublicMessage) {
    // The service deduplicates both content keys and Nostr event IDs
    if dedupService.isContentDuplicate(publicMessage.contentKey) { return }
    if dedupService.isNostrEventDuplicate(publicMessage.eventID) { return }
    // store and display the message
}

Unit tests in bitchatTests/MessageDeduplicationServiceTests.swift validate the LRU eviction, time-based expiry, and thread-safety guarantees described above.

Summary

• Thread-safe design: An NSLock protects all mutations in bitchat/Utils/MessageDeduplicator.swift, enabling safe concurrent access from BLE and Nostr networking threads.
• O(1) performance: A dictionary-backed lookup table provides constant-time duplicate checks via isDuplicate(_:).
• Automatic expiry: cleanupOldEntries(before:) removes stale timestamps on every check, while trimIfNeeded() evicts 25% of old entries when capacity exceeds maxCount.
• Protocol flexibility: markProcessed(_:) allows ACKs and control messages to be cached without prior existence checks.
• Full lifecycle support: The reset() method clears state when mesh sessions terminate, and the service integrates directly into ChatViewModelBootstrapper.swift for dependency injection.

Frequently Asked Questions

How does MessageDeduplicator handle concurrent access from multiple network threads?

All mutating operations acquire an NSLock defined in bitchat/Utils/MessageDeduplicator.swift, ensuring that the internal lookup dictionary and timestamp arrays remain consistent even when BLE and mesh protocols write simultaneously from different threads.

What happens when the deduplication cache reaches its maximum size?

The trimIfNeeded() method removes approximately 25% of the oldest entries in a single batch. This amortized eviction strategy keeps the cache bounded to maxCount while avoiding performance spikes during message floods.

Can MessageDeduplicator prevent replay attacks from old messages?

Yes. The cleanupOldEntries(before:) function runs on every isDuplicate(_:) call, discarding any entry older than the configured maxAge. This time-based expiry ensures that packets replayed after the age window are treated as new messages.

Where is MessageDeduplicator instantiated in the BitChat architecture?

The class is initialized by MessageDeduplicationService and injected into the networking stack via ChatViewModelBootstrapper.swift. It is actively used in BLEService.swift to screen incoming Bluetooth Low Energy packets before they reach the chat UI.

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