A Swift implementation of the Negentropy set-reconciliation protocol.
This Swift implementation is a port of the negentropy Rust library, adapted to use idiomatic Swift patterns and APIs.
⚠️ Warning: This is experimental software. Furthermore, the initial port was done with extensive AI assistance and not yet extensively human-reviewed. The API and protocol implementation may change, and it has not been extensively tested in production environments. Use at your own risk.
Negentropy is a protocol for efficient set reconciliation. It allows two parties to synchronize their sets of items by exchanging minimal data. The protocol uses fingerprinting, range splitting, and differential updates to minimize bandwidth usage.
- ✅ Efficient set reconciliation with minimal data transfer
- ✅ Pure Swift implementation with no external dependencies (uses CryptoKit)
- ✅ Protocol version 1 (0x61) compatible
- ✅ Tests included
- ✅ Swift 6.2 compatible
- iOS 16.0+ / macOS 13.0+ / tvOS 16.0+ / watchOS 9.0+
- Swift 5.9+
- Xcode 15.0+
Add the following to your Package.swift file:
dependencies: [ .package(url: "https://github.com/damus-io/negentropy-swift.git", from: "0.1.0") ]Or add it through Xcode:
- File → Add Package Dependencies
- Enter the repository URL
- Select the version you want to use
import Negentropy // Client setup var clientStorage = NegentropyStorageVector() let id1 = try Id(slice: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa".data(using: .utf8)!) let id2 = try Id(slice: "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb".data(using: .utf8)!) try clientStorage.insert(timestamp: 0, id: id1) try clientStorage.insert(timestamp: 1, id: id2) try clientStorage.seal() // Server setup var serverStorage = NegentropyStorageVector() let id3 = try Id(slice: "cccccccccccccccccccccccccccccccc".data(using: .utf8)!) let id4 = try Id(slice: "11111111111111111111111111111111".data(using: .utf8)!) try serverStorage.insert(timestamp: 0, id: id1) // shared with client try serverStorage.insert(timestamp: 2, id: id3) try serverStorage.insert(timestamp: 3, id: id4) try serverStorage.seal() // Client initiates reconciliation var client = try Negentropy(storage: clientStorage, frameSizeLimit: 0) let initMessage = try client.initiate() // Server processes the message var server = try Negentropy(storage: serverStorage, frameSizeLimit: 0) let serverResponse = try server.reconcile(initMessage) // Client processes the response var haveIds: [Id] = [] // IDs client has that server needs var needIds: [Id] = [] // IDs client needs from server if let nextMessage = try client.reconcile(serverResponse, haveIds: &haveIds, needIds: &needIds) { // Continue reconciliation with nextMessage } else { // Reconciliation complete print("Client has \(haveIds.count) items server needs") print("Client needs \(needIds.count) items from server") }// From bytes let bytes = Array(repeating: UInt8(0xAA), count: 32) let id1 = Id(bytes: bytes) // From slice with validation let id2 = try Id(slice: bytes) // From Data let data = Data(repeating: 0xBB, count: 32) let id3 = try Id(data: data)The library provides NegentropyStorageVector for in-memory storage, but you can implement your own storage by conforming to NegentropyStorageBase:
public protocol NegentropyStorageBase { func size() throws -> Int func getItem(at index: Int) throws -> Item? func iterate(begin: Int, end: Int, callback: (Item, Int) throws -> Bool) throws func findLowerBound(first: Int, last: Int, value: Bound) -> Int func fingerprint(begin: Int, end: Int) throws -> Fingerprint }You can specify a frame size limit to control the maximum size of messages:
// No limit (default) let negentropy1 = try Negentropy(storage: storage, frameSizeLimit: 0) // With limit (must be >= 4096) let negentropy2 = try Negentropy(storage: storage, frameSizeLimit: 8192)A 32-byte identifier used to uniquely identify items.
Represents an item with a timestamp and ID. Items are sorted first by timestamp, then by ID.
Represents a range boundary with a partial or full item.
In-memory storage implementation using an array.
Main protocol implementation. Generic over the storage type.
Creates the initial reconciliation message (client side).
Processes a query and returns a response (server side).
Processes a response and extracts IDs (client side). Returns nil when reconciliation is complete.
The library uses Swift's typed error handling. All operations that can fail throw NegentropyError:
public enum NegentropyError: Error { case idTooBig case invalidIdSize case frameSizeLimitTooSmall case notSealed case alreadySealed case alreadyBuiltInitialMessage case initiator case nonInitiator case unexpectedMode(UInt64) case parseEndsPrematurely case protocolVersionNotFound case invalidProtocolVersion case unsupportedProtocolVersion case conversionError case badRange }Run tests using Swift Package Manager:
swift testOr through Xcode:
- Open Package.swift in Xcode
- Product → Test (⌘U)
- Items must be sorted by timestamp and ID for efficient reconciliation
- Always call
seal()on storage before using it with Negentropy - For large sets, consider using frame size limits to avoid large messages
- The protocol is most efficient when sets have significant overlap
This project is distributed under the MIT software license. See the LICENSE file for details.
- Original C++ implementation: Doug Hoyte
- Rust implementation: Yuki Kishimoto
Contributions are welcome! Please feel free to submit issues or pull requests.