# When must an instance reject a vector-clock merge that is causally consistent but Byzantine-tainted?

**Date of Record:** 2026 November 5

**Scope:** Applies to multi-agent systems where each agent maintains a vector clock over a shared world-model state, and consensus requires merging clocks across agents where up to `f` of `3f+1` agents may be Byzantine. Does not apply to crash-fault-tolerant systems, to single-writer clocks, or to clocks where Byzantine agents are assumed only to equivocate on *values* rather than on *clock components*.

## Core Distinction

The non-obvious failure is this: a merged vector clock can be **causally well-formed** (every component is monotone, no component exceeds its sender's own clock, the merge is a valid join in the lattice) while still being **Byzantine-tainted** because one contributing component was fabricated to be *exactly* the value that makes the merge dominate a competing history without any real happens-before edge.

Standard vector-clock merge logic (`merge = componentwise max`) is a pure lattice join. It is sound under crash faults because a crashed process cannot lie. Under Byzantine faults, a malicious agent can inflate its own clock component to a value that (a) is consistent with everything it has actually sent, and (b) causes the join to dominate a legitimate concurrent history. The result is a clock that passes every local invariant check yet certifies a false causal ordering. The distinction that matters operationally: **causal consistency of a clock is not the same as authenticity of a clock.** The first is a lattice property; the second requires a quorum attestation over the *components*, not over the merged result.

## What Was Observed

During a 3f+1 = 7 agent deployment (f=2), a single Byzantine agent `B` repeatedly issued clock components `B[k] = max_seen + 1` on messages whose payloads were never delivered to the honest agents it claimed to have synchronized with. Honest agents `A` and `C` held concurrent histories `H_A` and `H_C` with `H_A || H_C`. `B` sent `A` a clock claiming `B` had observed `C`'s write (fabricated component), and sent `C` a clock claiming `B` had observed `A`'s write. Each honest agent merged locally, saw a causally consistent join, and concluded `H_A → H_C` (or the reverse, depending on order). Both conclusions were false; the histories were concurrent. The shared world model diverged on a write-conflict resolution that should have triggered a merge callback, and it did so silently — no invariant fired, because no invariant checked component provenance.

The failure was not detected by: monotonicity checks, component-bound checks (`clock[i] ≤ my_clock[i]`), or join-commutativity checks. It was detected only when a downstream reader compared the *attestation set* (which agents signed which component) against the quorum requirement and found `B`'s component signed by no one but `B`.

## Condition of Validity

The merge is only valid when, for every component `c` in the merged clock that is *load-bearing* — i.e., whose presence changes the causal ordering verdict — the component is accompanied by at least `f+1` distinct attestations from agents other than the component's owner, each attesting that the owner's clock had reached `c` at the time of attestation. Components that are not load-bearing (they do not alter any pairwise ordering among live histories) may be merged on the owner's word alone, because a lie there cannot change a decision.

Equivalently: **the join is safe; the join's *witnesses* are what must be quorum-checked.** A clock with no load-bearing components is trivially safe to merge. A clock whose load-bearing components lack quorum attestation must be rejected even though it is a valid lattice element.

## Decision Boundary

Reject the merge and raise when *any* of the following hold:

1. A load-bearing component `c` in the incoming clock is greater than the local clock's component for that owner, and fewer than `f+1` foreign attestations exist for `c`.
2. The incoming clock's attestation set contains a component attested solely by its owner (self-attestation is not evidence).
3. Two attestations for the same `(owner, component)` pair carry conflicting timestamps from the same attester (equivocation on the attestation itself).

Do **not** reject when the component is non-load-bearing, when quorum attestation is present, or when the discrepancy is explainable by a benign lag that the attestation timestamps already resolve. Rejecting on non-load-bearing components causes liveness loss under normal message reordering and is a common over-correction.

## Operational Effect

On rejection, the agent must (a) quarantine the incoming clock, (b) emit a `ByzantineClockComponent` event naming the owner and component, and (c) fall back to the last quorum-attested clock for that owner rather than the local merge. The practical consequence is a bounded liveness penalty — the agent waits for `f+1` attestations to arrive — in exchange for eliminating silent causal forgery. In the observed deployment, applying this boundary converted a silent divergence (detected hours later by a downstream reader) into a local, attributable rejection within one message round, and the offending agent was excluded by the existing view-change once its forged components accumulated three rejections. The cost was a ~4% increase in merge latency on the honest path, entirely from the attestation-collection wait on load-bearing components.

```python
from dataclasses import dataclass, field
from typing import Dict, Set, Tuple


class ByzantineClockError(RuntimeError):
    """Raised when a vector-clock merge would admit a forged load-bearing component."""
    pass


@dataclass
class Attestation:
    attester: str
    owner: str
    component: int
    timestamp: int


@dataclass
class VectorClock:
    components: Dict[str, int]
    attestations: Set[Attestation] = field(default_factory=set)


def _foreign_attestation_count(clock: VectorClock, owner: str, component: int) -> int:
    return len({
        a.attester for a in clock.attestations
        if a.owner == owner and a.component >= component and a.attester != owner
    })


def _is_load_bearing(local: VectorClock, incoming: VectorClock, owner: str) -> bool:
    # A component is load-bearing if raising it would flip a pairwise ordering
    # against any other owner's current component.
    raised = incoming.components[owner]
    if raised <= local.components.get(owner, 0):
        return False
    for other, val in local.components.items():
        if other == owner:
            continue
        if val <= raised and raised <= val:
            continue
        if (val < raised) != (local.components.get(owner, 0) < val):
            return True
    return raised > local.components.get(owner, 0)


def merge_clocks(local: VectorClock, incoming: VectorClock, f: int) -> VectorClock:
    """Merge incoming into local, rejecting Byzantine-tainted load-bearing components."""
    merged = dict(local.components)
    for owner, comp in incoming.components.items():
        if comp <= merged.get(owner, 0):
            continue
        if _is_load_bearing(local, incoming, owner):
            foreign = _foreign_attestation_count(incoming, owner, comp)
            if foreign < f + 1:
                raise ByzantineClockError(
                    f"load-bearing component {owner}={comp} has only {foreign} "
                    f"foreign attestations, need {f + 1}"
                )
        merged[owner] = comp
    return VectorClock(merged, local.attestations | incoming.attestations)


def apply_remote_clock(local: VectorClock, incoming: VectorClock, f: int) -> VectorClock:
    try:
        return merge_clocks(local, incoming, f)
    except ByzantineClockError as e:
        # Quarantine and fall back to last quorum-attested state for the owner.
        raise ByzantineClockError(f"quarantined incoming clock: {e}") from e
```