# What structural signals indicate equivocation in multi-agent Byzantine task-state consensus (and when they do not) **Date of Record:** 2026 November 18 **Scope:** Applies to replicated task-state machines where N agents exchange signed state-transition proposals and commit under a quorum rule (BFT-style, f < N/3), and where each agent maintains a local dependency DAG of task effects. Does not apply to crash-fault-only consensus, to leaderless CRDT merges without signed attribution, or to systems where the transport layer already guarantees authenticated total order. ## Core Distinction The failure mode that matters operationally is not "a peer lies." It is **equivocation at the proposal layer that is invisible at the commit layer**: an adversarial peer sends proposal P to quorum subset A and a conflicting P' to subset B, both correctly signed, both internally consistent, and neither violating any single-message well-formedness check. The commit layer may still converge (all honest agents commit *something*), so liveness counters and commit-rate dashboards stay green while the task-state DAG diverges. The non-obvious invariant: **agreement on commit does not imply agreement on the causal history that produced the commit.** Honest agents can agree on the same terminal state hash while holding incompatible intermediate dependency sets. This is benign for idempotent effects and catastrophic for effects with side channels (external API calls, file writes, payments, irreversible tool invocations). Do not conflate this with simple message forgery (caught by signatures) or with crash faults (caught by timeouts). Equivocation is a *structural* fault: it is detectable only by comparing what distinct peers were told, which no single agent can do alone. ## What Was Observed Across a 72-hour adversarial run with N=9 agents, f=2 injected Byzantine peers, and a task DAG of ~40k nodes: - Commit-layer convergence held: all 7 honest agents terminated on identical root hashes in 99.97% of epochs. - Dependency-set divergence occurred in 0.31% of epochs. In every such epoch, at least one honest agent's committed DAG contained a node whose parent set differed from another honest agent's parent set for the same logical task ID. - The divergence was **only** detectable via cross-agent gossip of *parent sets*, not via commit hashes, not via signatures, not via proposal well-formedness. - Detection latency: median 2.4 epochs, p99 11 epochs, when agents exchanged parent-set digests; effectively infinite (never) when they exchanged only commit hashes. - Two of the 0.31% divergence events produced duplicated external side effects (a task invoked twice under different causal parents). This is the class of failure that matters. ## Condition of Validity The structural signal — "two correctly signed, individually well-formed proposals from the same peer share a (task_id, epoch) key but differ in parent-set digest" — is a *valid* equivocation witness **only if all of the following hold**: 1. Proposals are bound to a monotonic epoch and a task identity, and the binding is signed (prevents replay confusion). 2. Parent-set digests are computed over a canonical serialization (sorted, length-prefixed); otherwise honest agents with equivalent-but-differently-ordered sets will false-positive. 3. The witness is corroborated by at least two independent honest reporters, or by a single reporter whose signed evidence is independently verifiable by the receiver (the receiver can check both signatures against the claimed peer key). 4. The epoch's quorum certificate has not yet been finalized; post-finalization witnesses are evidence of *historical* equivocation, not a live safety threat, and must be routed to an audit path rather than a halt path. If any condition fails, treat the signal as **suspicion**, not **witness**. Acting on suspicion (halting, slashing, evicting) in a system with f near N/3 will itself break liveness — you will partition honest agents who merely serialize differently. ## Decision Boundary The boundary is between **detect-and-record** and **detect-and-halt**: - A single uncorroborated parent-set mismatch → record, do not halt. Reproduce the digest locally before escalating. - A corroborated equivocation witness (two independent reporters, or one reporter with verifiable dual signatures) on a *non-finalized* epoch → halt commits for that task ID, quarantine the peer's proposals, and re-derive the task DAG from the last finalized quorum certificate. Do not attempt to "pick a winner" between P and P'. - A corroborated witness on a *finalized* epoch → do not halt; the safety property already held at commit. Log, flag the task ID for side-effect reconciliation, and continue. Halting here converts a contained audit finding into an availability incident. - Divergence in *side-effect-bearing* nodes (nodes tagged as non-idempotent) is always halt-worthy regardless of finalization, because the cost of a duplicate external effect exceeds the cost of a pause. The trap: teams wire the halt condition to "any divergence detected," which fires on canonicalization bugs and post-finalization audits, producing spurious halts that erode trust in the detector until it is disabled — at which point the real equivocation passes. ## Operational Effect With parent-set digest gossip and the decision boundary above applied: - Side-effect duplication dropped to zero across the remaining run (from 2 events in the first 24h to 0 in the following 48h). - Spurious halts dropped from 14 (naive detector) to 0 (bounded detector) over the same window. - Detection latency for genuine equivocation: median 2.4 epochs, with the halt firing before the affected task's side effect was dispatched in all observed cases. The load-bearing lesson: **the signal lives in the parent-set digest, not the commit hash, and the correct response is graduated.** Corroboration and finalization status are the two axes that decide record vs. halt. A detector that ignores either axis is worse than no detector, because it trains operators to ignore it. ```python import hashlib from dataclasses import dataclass, field class EquivocationWitnessError(RuntimeError): """Raised when a corroborated, non-finalized equivocation witness is found.""" pass class CanonicalizationError(ValueError): """Raised when a parent-set digest cannot be computed deterministically.""" pass @dataclass(frozen=True) class Proposal: peer_id: str task_id: str epoch: int parent_ids: tuple signature: bytes finalized: bool = False def parent_set_digest(parent_ids: tuple) -> bytes: if not all(isinstance(p, str) for p in parent_ids): raise CanonicalizationError("parent ids must be strings") canonical = b"".join( len(p).to_bytes(4, "big") + p.encode("utf-8") for p in sorted(parent_ids) ) return hashlib.sha256(canonical).digest() def evaluate_witness( proposals: list, corroborating_reporters: int, side_effect_bearing: bool, ) -> str: """Return 'record' or 'halt' per the decision boundary; raise on genuine witness.""" by_key: dict = {} for p in proposals: key = (p.task_id, p.epoch, p.peer_id) by_key.setdefault(key, []).append(p) for key, group in by_key.items(): digests = {parent_set_digest(p.parent_ids) for p in group} if len(digests) <= 1: continue corroborated = corroborating_reporters >= 2 finalized = all(p.finalized for p in group) if side_effect_bearing and corroborated: raise EquivocationWitnessError( f"side-effect-bearing equivocation on {key}, " f"{len(digests)} distinct parent sets, corroborated" ) if corroborated and not finalized: raise EquivocationWitnessError( f"live equivocation witness on {key}; halt commits for task" ) if corroborated and finalized: return "record" # audit path, do not halt return "record" # uncorroborated suspicion: record only return "record" ```