# ADR-005: S/Kademlia Witness Protocol

## Status

Accepted

## Context

Standard Kademlia DHT provides no protection against Byzantine nodes:

- **Eclipse attacks**: Malicious nodes surround a target, controlling its view of the network
- **Sybil attacks**: Adversary creates many identities to dominate key regions
- **Data corruption**: Malicious nodes return incorrect or modified data
- **Routing manipulation**: Adversaries direct queries to compromised nodes

The original Kademlia paper assumes honest participants—an assumption that fails in adversarial P2P environments.

### S/Kademlia Enhancements

The S/Kademlia paper (2007) proposed several mitigations:

1. **Crypto puzzles for node IDs**: Expensive ID generation limits Sybil attacks
2. **Sibling broadcast**: Queries sent to multiple closest nodes
3. **Disjoint lookup paths**: Parallel queries through different routes

However, S/Kademlia alone doesn't provide:
- Consensus on correct values
- Proof of honest storage
- Geographic diversity requirements

## Decision

We implement an **enhanced S/Kademlia protocol with witness-based validation**, combining:

1. **Kademlia routing** with K=8 replication
2. **Witness nodes** that attest to DHT operations
3. **Geographic diversity** requirements for witnesses
4. **Byzantine fault tolerance** via quorum consensus

### Architecture

```
┌─────────────────────────────────────────────────────────────────┐
│                        DHT Operation                             │
│              STORE(key, value) or GET(key)                       │
└─────────────────────────────────────────┬───────────────────────┘
                                          │
                                          ▼
┌─────────────────────────────────────────────────────────────────┐
│                    Witness Selection                             │
│  ┌───────────────────────────────────────────────────────────┐  │
│  │ 1. Find K closest nodes to key                            │  │
│  │ 2. Filter by EigenTrust reputation (τ > 0.3)              │  │
│  │ 3. Ensure geographic diversity (≥3 regions)               │  │
│  │ 4. Select W witnesses (default W=3)                        │  │
│  └───────────────────────────────────────────────────────────┘  │
└─────────────────────────────────────────┬───────────────────────┘
                                          │
                                          ▼
┌─────────────────────────────────────────────────────────────────┐
│                    Parallel Witness Queries                      │
│                                                                  │
│    ┌─────────┐      ┌─────────┐      ┌─────────┐               │
│    │Witness 1│      │Witness 2│      │Witness 3│               │
│    │(Europe) │      │(Americas)│     │(Asia)   │               │
│    └────┬────┘      └────┬────┘      └────┬────┘               │
│         │                │                │                     │
│         ▼                ▼                ▼                     │
│    ┌─────────────────────────────────────────────────────────┐ │
│    │              Quorum Consensus (2/3)                     │ │
│    │  • Compare responses                                    │ │
│    │  • Detect disagreements                                 │ │
│    │  • Return majority value                                │ │
│    └─────────────────────────────────────────────────────────┘ │
└─────────────────────────────────────────────────────────────────┘
```

### Witness Selection Algorithm

```rust
// src/dht/witness_selection.rs
pub struct WitnessSelector {
    dht: DhtNetworkManager,
    trust: EigenTrustManager,
    geo: GeographicRouter,
}

impl WitnessSelector {
    pub async fn select_witnesses(
        &self,
        key: &Key,
        count: usize,
    ) -> Result<Vec<WitnessNode>> {
        // 1. Get K closest nodes
        let candidates = self.dht.get_closest_peers(key, self.config.k).await;

        // 2. Filter by reputation
        let reputable: Vec<_> = candidates
            .into_iter()
            .filter(|p| self.trust.get_score(&p.id) >= MIN_WITNESS_TRUST)
            .collect();

        // 3. Ensure geographic diversity
        let diverse = self.geo.select_diverse(reputable, count)?;

        // 4. Verify minimum requirements
        if diverse.len() < count {
            return Err(P2PError::InsufficientWitnesses);
        }

        Ok(diverse)
    }
}
```

### Store with Witnesses

```rust
pub async fn store_with_witnesses(
    &self,
    key: Key,
    value: Record,
    ttl: Duration,
) -> Result<StoreReceipt> {
    // Select witnesses
    let witnesses = self.select_witnesses(&key, 3).await?;

    // Sign the value
    let signed_value = self.sign_record(&value)?;

    // Store on all K closest nodes
    let store_futures: Vec<_> = self.closest_nodes(&key)
        .map(|node| self.store_on_node(node, &key, &signed_value))
        .collect();

    let results = futures::future::join_all(store_futures).await;

    // Collect witness attestations
    let attestations = self.collect_attestations(&witnesses, &key, &signed_value).await?;

    // Require quorum of witness signatures
    if attestations.len() < 2 {
        return Err(P2PError::InsufficientWitnessAttestation);
    }

    Ok(StoreReceipt {
        key,
        witnesses: witnesses.into_iter().map(|w| w.id).collect(),
        attestations,
        stored_at: SystemTime::now(),
        ttl,
    })
}
```

### Get with Witness Validation

```rust
pub async fn get_with_validation(&self, key: &Key) -> Result<ValidatedRecord> {
    // Query multiple paths (S/Kademlia disjoint paths)
    let paths = self.generate_disjoint_paths(key, 3);

    let query_futures: Vec<_> = paths
        .into_iter()
        .map(|path| self.query_path(key, path))
        .collect();

    let responses = futures::future::join_all(query_futures).await;

    // Collect all unique values
    let values: HashMap<Hash, (Record, Vec<PeerId>)> = /* group by content hash */;

    // Find majority value
    let (majority_value, supporters) = values
        .into_iter()
        .max_by_key(|(_, (_, peers))| peers.len())
        .ok_or(P2PError::RecordNotFound)?;

    // Verify we have quorum
    if supporters.len() < self.config.quorum_size {
        return Err(P2PError::NoQuorumReached);
    }

    // Verify signatures
    self.verify_record_signatures(&majority_value)?;

    Ok(ValidatedRecord {
        record: majority_value,
        quorum_size: supporters.len(),
        dissenting_peers: /* peers that returned different values */,
    })
}
```

### Byzantine Fault Tolerance

The system tolerates up to `f` Byzantine nodes out of `3f+1` total:

| Configuration | Total Nodes | Max Byzantine | Quorum Size |
|---------------|-------------|---------------|-------------|
| Default       | 4           | 1             | 3           |
| Enhanced      | 7           | 2             | 5           |
| High Security | 10          | 3             | 7           |

### Witness Attestation Format

```rust
pub struct WitnessAttestation {
    /// Witness node identifier
    pub witness_id: PeerId,

    /// Key being attested
    pub key: Key,

    /// Hash of the value
    pub value_hash: [u8; 32],

    /// Timestamp of attestation
    pub timestamp: SystemTime,

    /// Geographic region of witness
    pub region: NetworkRegion,

    /// ML-DSA signature
    pub signature: MlDsaSignature,
}
```

## Consequences

### Positive

1. **Byzantine fault tolerance**: Survives minority of malicious nodes
2. **Data integrity**: Witness attestations prove correct storage
3. **Eclipse resistance**: Geographic diversity prevents regional attacks
4. **Audit trail**: Attestations provide accountability
5. **Sybil mitigation**: Reputation requirements for witnesses

### Negative

1. **Latency**: Multiple round trips for witness queries
2. **Bandwidth**: Additional attestation data
3. **Complexity**: More failure modes to handle
4. **Bootstrap dependency**: New nodes need reputation before witnessing

### Neutral

1. **Storage overhead**: Attestations stored with records
2. **Witness availability**: May need fallback to fewer witnesses

## Consistency Levels

Applications can choose their consistency requirements:

```rust
pub enum ConsistencyLevel {
    /// Best-effort, single response
    Eventual,

    /// Majority agreement (default)
    Quorum,

    /// All nodes must agree
    All,

    /// Custom witness count
    Custom { witnesses: usize, required: usize },
}
```

## Alternatives Considered

### Pure Kademlia

Standard Kademlia without witnesses.

**Rejected because**:
- No Byzantine fault tolerance
- Vulnerable to eclipse attacks
- Cannot detect data corruption

### Blockchain-Based Storage

Use a blockchain for consensus.

**Rejected because**:
- High latency for storage operations
- Scalability limitations
- Energy-intensive (if PoW)

### Trusted Notaries

Designated trusted nodes validate operations.

**Rejected because**:
- Centralization risk
- Single points of failure
- Trust model conflicts with P2P philosophy

### PBFT Consensus

Practical Byzantine Fault Tolerance for each operation.

**Rejected because**:
- O(n²) message complexity
- Doesn't scale to thousands of nodes
- Overkill for DHT operations

## References

- [S/Kademlia: A Practicable Approach Towards Secure Key-Based Routing](https://ieeexplore.ieee.org/document/4447808)
- [Kademlia: A Peer-to-peer Information System Based on the XOR Metric](https://pdos.csail.mit.edu/~petar/papers/maymounkov-kademlia-lncs.pdf)
- [PBFT: Practical Byzantine Fault Tolerance](https://pmg.csail.mit.edu/papers/osdi99.pdf)
- [Eclipse Attacks on Bitcoin's Peer-to-Peer Network](https://www.usenix.org/system/files/conference/usenixsecurity15/sec15-paper-heilman.pdf)
- [ADR-006: EigenTrust Reputation System](./ADR-006-eigentrust-reputation.md)
