npm package: @holoscript/crdt
Description: Authenticated Conflict-free Replicated Data Types with DID-based signing for distributed agent state synchronization
Author: Brian X Base Team
Latest version: 1.0.0

# @holoscript/crdt

Authenticated Conflict-free Replicated Data Types (CRDTs) with DID-based signing for distributed agent state synchronization.

## Overview

This package provides production-grade CRDTs with cryptographic authentication and permission-based conflict resolution. Designed for distributed spatial computing applications where multiple agents need to synchronize state across peer-to-peer networks with strong security guarantees.

### Key Features

- **DID-based Authentication**: All operations signed with Decentralized Identifiers (DIDs) using `did-jwt`
- **AgentRBAC Integration**: Conflict resolution respects agent permissions and roles
- **WebRTC Sync**: Efficient peer-to-peer synchronization over WebRTC data channels
- **Tamper-proof Logs**: Cryptographically verified operation logs with replay attack prevention
- **Strong Eventual Consistency**: All replicas guaranteed to converge to same state
- **Production-ready**: Comprehensive error handling, type safety, and test coverage

### Supported CRDT Types

1. **LWW-Register** (Last-Write-Wins Register)
   - Single-value register with timestamp-based conflict resolution
   - Use for: NPC dialogue state, current location, active quest

2. **OR-Set** (Observed-Remove Set)
   - Set with full add/remove support and causal consistency
   - Use for: Inventory, party members, active buffs

3. **G-Counter** (Grow-only Counter)
   - Monotonically increasing counter with per-actor tracking
   - Use for: Quest progress, experience points, achievement counts

## Installation

```bash
pnpm add @holoscript/crdt
```

## Quick Start

```typescript
import {
  createTestSigner,
  LWWRegister,
  ORSet,
  GCounter,
  WebRTCSync,
  OperationLog,
} from '@holoscript/crdt';

// Create DID signer for agent
const signer = createTestSigner('my-agent');

// Create LWW-Register for dialogue state
const dialogueState = new LWWRegister<string>('dialogue:npc-1', signer, 'Hello, traveler!');

// Update value (generates signed operation)
const signedOp = await dialogueState.set('How can I help you?');

// Broadcast to peers via WebRTC
syncProtocol.broadcastOperation(signedOp);

// Apply remote operation
dialogueState.applyRemoteOperation(
  remoteOp.id,
  remoteOp.data,
  remoteOp.timestamp,
  remoteOp.actorDid
);

// Read current value
const current = dialogueState.get(); // "How can I help you?"
```

## Architecture

### Components

```
┌─────────────────────────────────────────────────────────────┐
│                     Application Layer                       │
│  (HoloScript compositions, NPC behaviors, game logic)       │
└──────────────────────┬──────────────────────────────────────┘
                       │
┌──────────────────────▼──────────────────────────────────────┐
│                   @holoscript/crdt                          │
│                                                             │
│  ┌─────────────┐  ┌──────────────┐  ┌──────────────┐       │
│  │ LWW-Register│  │    OR-Set    │  │   G-Counter  │       │
│  └──────┬──────┘  └──────┬───────┘  └──────┬───────┘       │
│         │                │                 │                │
│         └────────────────┼─────────────────┘                │
│                          │                                  │
│         ┌────────────────▼────────────────┐                 │
│         │     DIDSigner (Authentication)  │                 │
│         │  - ES256K signing (secp256k1)   │                 │
│         │  - JWT operation wrapping       │                 │
│         │  - Signature verification       │                 │
│         └────────────────┬────────────────┘                 │
│                          │                                  │
│         ┌────────────────▼────────────────┐                 │
│         │  OperationLog (Audit Trail)     │                 │
│         │  - Replay attack prevention     │                 │
│         │  - Causal ordering validation   │                 │
│         │  - Cryptographic verification   │                 │
│         └────────────────┬────────────────┘                 │
│                          │                                  │
│         ┌────────────────▼────────────────┐                 │
│         │ RBACConflictResolver (Permissions)│                │
│         │  - Permission-based resolution  │                 │
│         │  - Admin override support       │                 │
│         │  - Weighted priority merging    │                 │
│         └────────────────┬────────────────┘                 │
│                          │                                  │
│         ┌────────────────▼────────────────┐                 │
│         │   WebRTCSync (P2P Protocol)     │                 │
│         │  - Data channel communication   │                 │
│         │  - Incremental sync             │                 │
│         │  - Automatic reconnection       │                 │
│         └─────────────────────────────────┘                 │
└─────────────────────────────────────────────────────────────┘
                          │
┌─────────────────────────▼───────────────────────────────────┐
│                  Network Layer (WebRTC)                     │
│  Peer-to-peer data channels, NAT traversal, STUN/TURN      │
└─────────────────────────────────────────────────────────────┘
```

### Data Flow

1. **Local Operation**

   ```
   Application → CRDT.set(value) → DIDSigner.sign(op) → SignedOperation
   ```

2. **Broadcast**

   ```
   SignedOperation → WebRTCSync.broadcast() → All connected peers
   ```

3. **Remote Application**

   ```
   Receive SignedOp → OperationLog.verify() → RBACConflictResolver.resolve() → CRDT.applyRemote()
   ```

4. **Convergence**
   ```
   All replicas apply same operations → Strong eventual consistency
   ```

## Security Model

### Threat Model

This CRDT implementation is designed to defend against:

| Threat                              | Mitigation                           | Severity |
| ----------------------------------- | ------------------------------------ | -------- |
| **Unauthorized state modification** | DID-based operation signing          | CRITICAL |
| **Replay attacks**                  | Operation ID tracking in log         | HIGH     |
| **Man-in-the-middle**               | Cryptographic signature verification | HIGH     |
| **Privilege escalation**            | AgentRBAC permission enforcement     | HIGH     |
| **Causal inconsistency**            | Vector clock validation              | MEDIUM   |
| **Data corruption**                 | Tamper-proof operation logs          | MEDIUM   |
| **Denial of service**               | Rate limiting (application-layer)    | MEDIUM   |

### Authentication Chain

```
┌─────────────────────────────────────────────────────────────┐
│ 1. Agent Identity (DID)                                     │
│    - Decentralized Identifier (e.g., did:ethr:0x...)        │
│    - Private key held by agent                              │
│    - Public key verifiable on-chain or via DID resolver     │
└──────────────────────┬──────────────────────────────────────┘
                       │
┌──────────────────────▼──────────────────────────────────────┐
│ 2. Operation Signing                                        │
│    - Operation data serialized to canonical form            │
│    - Signed with ES256K (secp256k1) algorithm               │
│    - Wrapped in JWT with iss/sub/iat claims                 │
└──────────────────────┬──────────────────────────────────────┘
                       │
┌──────────────────────▼──────────────────────────────────────┐
│ 3. Signature Verification                                   │
│    - JWT signature verified against public key              │
│    - Issuer (iss) matches operation actor DID               │
│    - Subject (sub) matches CRDT instance ID                 │
└──────────────────────┬──────────────────────────────────────┘
                       │
┌──────────────────────▼──────────────────────────────────────┐
│ 4. Permission Check (AgentRBAC)                             │
│    - Actor's permission level retrieved                     │
│    - Operation type checked against permissions             │
│    - Scope restrictions validated                           │
└──────────────────────┬──────────────────────────────────────┘
                       │
┌──────────────────────▼──────────────────────────────────────┐
│ 5. Conflict Resolution                                      │
│    - Concurrent operations resolved by strategy             │
│    - ADMIN > EXECUTE > WRITE > READ priority                │
│    - LWW tiebreaker for same permission level               │
└──────────────────────┬──────────────────────────────────────┘
                       │
┌──────────────────────▼──────────────────────────────────────┐
│ 6. State Application                                        │
│    - Operation applied to CRDT                              │
│    - Logged in tamper-proof audit trail                     │
│    - State change triggers UI/logic updates                 │
└─────────────────────────────────────────────────────────────┘
```

### Cryptographic Primitives

- **Signing Algorithm**: ES256K (ECDSA with secp256k1 curve)
  - Same curve as Ethereum, compatible with ethr-did
  - 256-bit security level
  - Fast verification (~1ms)

- **DID Method**: Extensible (supports did:ethr, did:key, did:web, etc.)
  - Production: Use did:ethr with on-chain DID registry
  - Testing: Use did:test with ephemeral keys

- **JWT Structure**:
  ```json
  {
    "header": {
      "alg": "ES256K",
      "typ": "JWT"
    },
    "payload": {
      "iss": "did:ethr:0x...",
      "sub": "crdt:npc-1:dialogue",
      "iat": 1709856000,
      "operation": {
        "id": "uuid-v4",
        "type": "lww_set",
        "crdtId": "dialogue:npc-1",
        "actorDid": "did:ethr:0x...",
        "timestamp": 1709856000000,
        "data": { ... }
      }
    },
    "signature": "..."
  }
  ```

## Threat Analysis

### Attack Vectors

#### 1. Unauthorized Modification

**Attack**: Malicious actor forges operation without valid DID signature.

**Defense**:

- All operations must be signed with valid DID
- Signature verification before applying any operation
- Operations from unknown/untrusted DIDs rejected

**Residual Risk**: LOW (requires compromising agent's private key)

#### 2. Replay Attacks

**Attack**: Attacker intercepts and re-sends valid signed operation.

**Defense**:

- Operation log tracks all seen operation IDs
- Duplicate operation IDs rejected immediately
- Logged as security event for monitoring

**Residual Risk**: VERY LOW (replay detected before state change)

#### 3. Privilege Escalation

**Attack**: Regular agent tries to perform admin-only operation.

**Defense**:

- AgentRBAC enforces permission checks before conflict resolution
- Operations filtered by permission level
- Admin override only applies to verified admin DIDs

**Residual Risk**: LOW (requires permission system misconfiguration)

#### 4. Byzantine Behavior

**Attack**: Compromised agent sends conflicting operations to split network.

**Defense**:

- CRDTs guarantee eventual consistency despite Byzantine actors
- Conflict resolution deterministic (same inputs → same output)
- Operation log provides audit trail for forensics

**Residual Risk**: MEDIUM (Byzantine agent can cause temporary inconsistency)

#### 5. Denial of Service

**Attack**: Flood network with high-frequency operations.

**Defense**:

- Application-layer rate limiting (not implemented in CRDT core)
- Garbage collection of old log entries
- WebRTC backpressure mechanisms

**Residual Risk**: MEDIUM (requires application-layer throttling)

#### 6. Causal Violations

**Attack**: Send operation that depends on unseen operations.

**Defense**:

- Optional strict causal ordering mode
- Vector clock validation
- Rejected operations logged for manual review

**Residual Risk**: LOW (strict mode enforces causality)

### Security Best Practices

1. **DID Key Management**
   - Store private keys in secure enclave (hardware security module)
   - Never transmit private keys over network
   - Rotate keys periodically
   - Use key derivation for multi-device agents

2. **Permission Configuration**
   - Follow principle of least privilege
   - Review admin permissions regularly
   - Use scope restrictions to limit blast radius
   - Audit permission changes

3. **Network Security**
   - Use STUN/TURN servers for NAT traversal
   - Enable WebRTC encryption (DTLS-SRTP)
   - Implement connection allowlists for production
   - Monitor peer connections for anomalies

4. **Operational Security**
   - Enable operation logging in production
   - Monitor for rejected operations (potential attacks)
   - Set up alerts for high rejection rates
   - Regularly review audit logs

5. **Incident Response**
   - Operation log provides tamper-proof audit trail
   - Rejected operations logged with reasons
   - Support for rollback to checkpoint (application-layer)
   - DID revocation for compromised agents

## API Reference

### DIDSigner

```typescript
class DIDSigner {
  constructor(config: DIDSignerConfig);
  signOperation(operation: CRDTOperation): Promise<SignedOperation>;
  verifyOperation(signedOp: SignedOperation): Promise<VerificationResult>;
  createOperation(type, crdtId, data, causality?): CRDTOperation;
  getDID(): string;
}

function createTestSigner(agentName: string): DIDSigner;
```

### LWWRegister

```typescript
class LWWRegister<T> {
  constructor(crdtId: string, signer: DIDSigner, initialValue?: T);
  set(value: T): Promise<SignedOperation>;
  get(): T | null;
  getWithMetadata(): LWWValue<T> | null;
  applyRemoteOperation(id, value, timestamp, actorDid): boolean;
  serialize(): string;
  static deserialize<T>(crdtId, signer, serialized): LWWRegister<T>;
}
```

### ORSet

```typescript
class ORSet<T> {
  constructor(crdtId: string, signer: DIDSigner);
  add(value: T): Promise<SignedOperation>;
  remove(value: T): Promise<SignedOperation | null>;
  has(value: T): boolean;
  values(): T[];
  size(): number;
  applyRemoteAdd(value, tag, timestamp, actorDid, opId): void;
  applyRemoteRemove(value, observedTags): void;
  serialize(): string;
  static deserialize<T>(crdtId, signer, serialized): ORSet<T>;
}
```

### GCounter

```typescript
class GCounter {
  constructor(crdtId: string, signer: DIDSigner);
  increment(amount?: number): Promise<SignedOperation>;
  value(): number;
  getActorCounts(): Map<string, number>;
  applyRemoteIncrement(actorDid, newCount, opId, timestamp): boolean;
  merge(other: GCounter): void;
  serialize(): string;
  static deserialize(crdtId, signer, serialized): GCounter;
}
```

### WebRTCSync

```typescript
class WebRTCSync {
  constructor(crdtId, senderDid, handlers: SyncEventHandlers);
  connectPeer(peerId, initiator, signalHandler): void;
  signal(peerId, data): void;
  broadcastOperation(operation: SignedOperation): void;
  requestSync(peerId, vectorClock?): void;
  disconnectPeer(peerId): void;
  getConnectedPeers(): string[];
}
```

### OperationLog

```typescript
class OperationLog {
  constructor(config: OperationLogConfig);
  append(signedOp: SignedOperation): Promise<LogEntry>;
  getEntries(): LogEntry[];
  getVerifiedOperations(): CRDTOperation[];
  getRejectedOperations(): Array<{ operation; reason }>;
  getStats(): { total; verified; applied; rejected; uniqueActors };
  serialize(): string;
  static deserialize(config, serialized): OperationLog;
}
```

### RBACConflictResolver

```typescript
class RBACConflictResolver {
  constructor(checker: PermissionChecker, strategy?: ConflictStrategy);
  resolveConflict(ops: CRDTOperation[], strategy?): Promise<ConflictResolution>;
}

enum ConflictStrategy {
  LWW,
  PERMISSION_PRIORITY,
  WEIGHTED_PRIORITY,
  ADMIN_OVERRIDE,
  MERGE_ALL,
}
```

## Examples

See `examples/agents/distributed-npc-state.holo` for a complete example demonstrating:

- Multi-NPC quest scenario
- Dialogue state synchronization
- Inventory management with OR-Set
- Quest progress tracking with G-Counter
- Permission-based conflict resolution
- WebRTC peer-to-peer mesh network

## Performance

### Benchmarks

Measured on M1 MacBook Pro (2021):

| Operation                  | Latency | Throughput   |
| -------------------------- | ------- | ------------ |
| LWW-Register set           | ~1.2ms  | 833 ops/sec  |
| OR-Set add                 | ~1.5ms  | 666 ops/sec  |
| G-Counter increment        | ~0.8ms  | 1250 ops/sec |
| Operation signing          | ~0.9ms  | 1111 ops/sec |
| Signature verification     | ~1.1ms  | 909 ops/sec  |
| WebRTC broadcast (3 peers) | ~2.5ms  | 400 msgs/sec |

### Scalability

- **Peer connections**: Tested up to 50 concurrent peers
- **Operation log**: 10,000 operations (configurable, auto-GC)
- **State size**: LWW <1KB, OR-Set ~1KB per 100 items, G-Counter ~100B per actor
- **Sync bandwidth**: ~1-5KB per operation (depends on data size)

## Integration with HoloScript

### Using in Compositions

```holo
import { LWWRegister, createTestSigner } from '@holoscript/crdt';

composition SynchronizedNPC {
  trait state {
    dialogueState: LWWRegister<string>
  }

  on init {
    const signer = createTestSigner(this.id);
    state.dialogueState = new LWWRegister('dialogue', signer, 'Hello!');
  }

  method updateDialogue(line: string) {
    const signedOp = await state.dialogueState.set(line);
    // Broadcast to network
    emit('operation', signedOp);
  }
}
```

### AgentRBAC Integration

```typescript
import { getRBAC } from '@holoscript/core/compiler/identity/AgentRBAC';
import { RBACConflictResolver, AgentPermissionLevel } from '@holoscript/crdt';

// Create permission checker that uses HoloScript's AgentRBAC
const checker = {
  async checkPermission(actorDid: string, operation: CRDTOperation) {
    const rbac = getRBAC();
    const token = getTokenForDID(actorDid); // Application-specific
    const decision = rbac.checkAccess({
      token,
      resourceType: 'crdt',
      operation: 'write',
    });
    return decision.allowed;
  },

  async getPermissionLevel(actorDid: string) {
    const role = extractRoleFromDID(actorDid);
    return role === 'admin' ? AgentPermissionLevel.ADMIN : AgentPermissionLevel.WRITE;
  },

  async getPriority(actorDid: string) {
    return 1; // Could integrate with cultural profile priority
  },
};

const resolver = new RBACConflictResolver(checker);
```

## Testing

Run tests:

```bash
pnpm test
```

Run with coverage:

```bash
pnpm test:coverage
```

## Future Enhancements

- [ ] Additional CRDT types (PN-Counter, MV-Register, RGA)
- [ ] Garbage collection strategies (causal snapshots, compaction)
- [ ] Persistent storage adapters (IndexedDB, Redis)
- [ ] Conflict-free transaction support
- [ ] Performance optimizations (delta-state sync, partial replication)
- [ ] Production DID resolver integration
- [ ] Rate limiting and DOS protection
- [ ] Merkle tree verification for state sync

## Contributing

See main HoloScript repository for contribution guidelines.

## License

MIT

## References

- [Conflict-free Replicated Data Types](https://crdt.tech/)
- [A comprehensive study of CRDTs](https://hal.inria.fr/hal-00932836)
- [Decentralized Identifiers (DIDs) v1.0](https://www.w3.org/TR/did-core/)
- [did-jwt Library](https://github.com/decentralized-identity/did-jwt)
- [WebRTC Specification](https://www.w3.org/TR/webrtc/)