@toolkit-p2p/sync

CRDT-based synchronization primitives for toolkit-p2p mesh networks.

Features

• Vector Clocks - Track causality and detect concurrent events
• G-Counter CRDT - Conflict-free grow-only counter
• LWW-Map CRDT - Last-Writer-Wins map with automatic conflict resolution
• Merkle Trees - Efficient data synchronization
• TypeScript - Full type safety with strict mode
• Well-tested - 142 tests with 97.9% coverage

Installation

pnpm add @toolkit-p2p/sync

Usage

Vector Clocks

Track causality between distributed events:

import { createVectorClock, increment, compare } from '@toolkit-p2p/sync';

// peer1 performs an operation
let clock1 = createVectorClock();
clock1 = increment(clock1, 'peer1');
// { peer1: 1 }

// peer2 performs an operation
let clock2 = createVectorClock();
clock2 = increment(clock2, 'peer2');
// { peer2: 1 }

// Detect relationship
compare(clock1, clock2);
// 'concurrent' - these operations happened independently

G-Counter

A counter that only grows:

import { createGCounter, increment, value, merge } from '@toolkit-p2p/sync';

// Two peers count independently
let counter1 = createGCounter();
counter1 = increment(counter1, 'peer1', 5);

let counter2 = createGCounter();
counter2 = increment(counter2, 'peer2', 3);

// Merge counters
const merged = merge(counter1, counter2);
value(merged); // 8

// Merging is commutative, associative, and idempotent
merge(counter1, counter2) === merge(counter2, counter1);

LWW-Map

A distributed key-value map with conflict resolution:

import {
  createLWWMap,
  set,
  get,
  merge,
  createVectorClock,
  increment
} from '@toolkit-p2p/sync';

// peer1 writes
let clock1 = createVectorClock();
clock1 = increment(clock1, 'peer1');

let map1 = createLWWMap<string, string>();
map1 = set(map1, 'name', 'Alice', clock1, 'peer1');

// peer2 writes concurrently
let clock2 = createVectorClock();
clock2 = increment(clock2, 'peer2');

let map2 = createLWWMap<string, string>();
map2 = set(map2, 'name', 'Bob', clock2, 'peer2');

// Merge resolves conflict deterministically
const merged = merge(map1, map2);
get(merged, 'name'); // 'Bob' (peer2 > peer1 lexicographically)

Merkle Trees

Efficiently detect differences between datasets:

import {
  buildMerkleTree,
  getRootHash,
  findDifferences
} from '@toolkit-p2p/sync';

const encoder = new TextEncoder();

// Build tree from data
const data1 = [
  encoder.encode('item1'),
  encoder.encode('item2'),
  encoder.encode('item3'),
];
const tree1 = buildMerkleTree(data1);

// Build another tree with one change
const data2 = [
  encoder.encode('item1'),
  encoder.encode('item2'),
  encoder.encode('modified-item3'),
];
const tree2 = buildMerkleTree(data2);

// Quick comparison
if (getRootHash(tree1) !== getRootHash(tree2)) {
  // Find what changed
  const diffs = findDifferences(tree1, tree2);
  console.log(`${diffs.length} items differ`);
}

API Reference

Vector Clocks

createVectorClock(): VectorClock
increment(clock: VectorClock, peerId: PeerId): VectorClock
merge(clock1: VectorClock, clock2: VectorClock): VectorClock
compare(clock1: VectorClock, clock2: VectorClock):
  'before' | 'after' | 'concurrent' | 'equal'
happenedBefore(clock1: VectorClock, clock2: VectorClock): boolean
areConcurrent(clock1: VectorClock, clock2: VectorClock): boolean

G-Counter

createGCounter(): GCounter
increment(counter: GCounter, peerId: PeerId, amount?: number): GCounter
value(counter: GCounter): number
merge(counter1: GCounter, counter2: GCounter): GCounter
getPeerCount(counter: GCounter, peerId: PeerId): number

LWW-Map

createLWWMap<K, V>(): LWWMap<K, V>
set<K, V>(map: LWWMap<K, V>, key: K, value: V, timestamp: Timestamp, peerId: PeerId): LWWMap<K, V>
get<K, V>(map: LWWMap<K, V>, key: K): V | undefined
remove<K, V>(map: LWWMap<K, V>, key: K, timestamp: Timestamp, peerId: PeerId): LWWMap<K, V>
has<K, V>(map: LWWMap<K, V>, key: K): boolean
merge<K, V>(map1: LWWMap<K, V>, map2: LWWMap<K, V>): LWWMap<K, V>
keys<K, V>(map: LWWMap<K, V>): K[]
values<K, V>(map: LWWMap<K, V>): V[]
entries<K, V>(map: LWWMap<K, V>): Array<[K, V]>

Merkle Trees

buildMerkleTree(data: Uint8Array[]): MerkleNode | null
getRootHash(tree: MerkleNode | null): Hash | null
generateProof(tree: MerkleNode | null, data: Uint8Array): MerkleProof | null
verifyProof(proof: MerkleProof): boolean
findDifferences(tree1: MerkleNode | null, tree2: MerkleNode | null): Hash[]
getLeaves(tree: MerkleNode | null): Hash[]

CRDT Properties

All CRDTs in this package guarantee:

• Convergence: All peers eventually reach the same state
• Commutativity: Order of operations doesn't matter
• Associativity: Grouping of operations doesn't matter
• Idempotency: Applying the same operation multiple times has no extra effect

Performance

| Operation | Time Complexity | Space Complexity | |-----------|----------------|------------------| | Vector Clock increment | O(1) | O(n) peers | | Vector Clock merge | O(n) peers | O(n) peers | | G-Counter increment | O(1) | O(n) peers | | G-Counter value | O(n) peers | O(n) peers | | LWW-Map set | O(1) | O(k) keys | | LWW-Map get | O(1) | O(k) keys | | LWW-Map merge | O(k) keys | O(k) keys | | Merkle build | O(n log n) | O(n) items | | Merkle proof | O(log n) | O(log n) | | Merkle diff | O(n) worst | O(n) items |

Testing

# Run tests
pnpm test

# Run tests with UI
pnpm test:ui

# Build package
pnpm build

License

MIT

Related Packages

• @toolkit-p2p/identity - Cryptographic identity
• @toolkit-p2p/transport - WebRTC transport layer
• @toolkit-p2p/mesh-cache - Distributed caching