Prefix Consensus For Censorship Resistant BFT
Session summary
The presenter introduces prefix consensus, a deterministic asynchronous primitive for reasoning about transaction inclusion in a multi-slot BFT setting. Each slot lets all validators submit proposals, and a slot is considered censored if it excludes any honest proposal or if it is skipped or empty. The protocol orders proposals per slot according to a validator ranking and commits only a prefix of this vector, limiting where malicious parties can cause truncation. Prefix consensus outputs “low” and “high” vectors that satisfy prefix and validity properties; the authors interpret lows as safe to commit immediately and highs as safe to extend later, without requiring full agreement.
Building on this primitive, the authors design a three-round, quadratic-communication construction with added verifiability and accountability, and argue that three rounds are necessary under their fault assumptions. They extend it to strong prefix consensus with agreement, then to a leaderless construction under partial synchrony using chained certificates across views. Finally, they derive a leaderless, multi-proposer blockchain-style protocol. By demoting accountable malicious parties to the end of the ranking rather than banning them, the authors claim the protocol achieves at most F censored slots after global stabilization, with amortized four-round commit latency.
Key takeaways
- The authors define per-slot censorship to include both exclusion of any honest proposal and skipped or empty slots, and target at most F censored slots after the network becomes synchronous.
- Prefix consensus provides low and high output vectors with prefix and validity properties, where lows are treated as immediately committable and highs as safe to extend, all without requiring agreement.
- Using accountable, verifiable prefix consensus and dynamic demotion in the validator ranking, the authors build a leaderless multi-proposer protocol that bounds censorship while maintaining amortized four-round commit latency.