Negentropy Swift

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.

Description

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.

Features

• ✅ 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

Requirements

• iOS 16.0+ / macOS 13.0+ / tvOS 16.0+ / watchOS 9.0+
• Swift 5.9+
• Xcode 15.0+

Installation

Swift Package Manager

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:

1. File → Add Package Dependencies
2. Enter the repository URL
3. Select the version you want to use

Usage

Basic Example

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")
}

Creating IDs

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

Storage Implementation

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
}

Frame Size Limits

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)

API Reference

Core Types

Id

A 32-byte identifier used to uniquely identify items.

Item

Represents an item with a timestamp and ID. Items are sorted first by timestamp, then by ID.

Bound

Represents a range boundary with a partial or full item.

NegentropyStorageVector

In-memory storage implementation using an array.

Negentropy<Storage>

Main protocol implementation. Generic over the storage type.

Key Methods

Negentropy.initiate() -> [UInt8]

Creates the initial reconciliation message (client side).

Negentropy.reconcile(_ query: [UInt8]) -> [UInt8]

Processes a query and returns a response (server side).

Negentropy.reconcile(_ query: [UInt8], haveIds:needIds:) -> [UInt8]?

Processes a response and extracts IDs (client side). Returns nil when reconciliation is complete.

Error Handling

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
}

Testing

Run tests using Swift Package Manager:

swift test

Or through Xcode:

1. Open Package.swift in Xcode
2. Product → Test (⌘U)

Performance Considerations

• 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

License

This project is distributed under the MIT software license. See the LICENSE file for details.

Credits

• Original C++ implementation: Doug Hoyte
• Rust implementation: Yuki Kishimoto

Contributing

Contributions are welcome! Please feel free to submit issues or pull requests.

References

• Negentropy Protocol Specification
• Original Rust Implementation