ACFA Protocol Enables Byzantine-Robust Aggregation Without Consensus

Byzantine-robust aggregation rules like multi-Krum historically require a central coordinator because they are globally coupled, non-associative, and discontinuous—meaning a tiny perturbation can flip the selected subset and shift the output significantly. This has made decentralized replication difficult. However, Ryan Gillespie's new paper shows that coordinator-free replication is possible because robust rules need only an agreed set and exclusion predicate, both of which converge without consensus. The key insight decouples the aggregation function from the consensus mechanism, opening the door to fully decentralized systems.

ACFA achieves this using a content-addressed OR-Set of signed contributions and a grow-only set of self-authenticating equivocation proofs, both verifiable offline by anyone. Aggregation is a deterministic pure function over a converged product state using fixed-point integer arithmetic and hash-canonical ordering. The protocol proves that any pure function of a converged CRDT product inherits Strong Eventual Consistency. A prototype with 10 nodes (3 Byzantine) passed all 16/16 falsification checks, including byte-identical roots under adversarial gossip and deterministic re-convergence after late equivocation proofs. The guarantee is consistency, not accuracy—robustness is conditional on 2f+3 admitted contributions (at most f Byzantine) and a quantisation-margin condition.