2026/02/02 by Zhuolun Xiang, Andrei Tonkikh, Alexander Spiegelman
#cs.DC
Despite broad adoption of BFT consensus in blockchains, censorship resistance remains weak: existing designs offer limited inclusion guarantees and allow leaders to exclude transactions. We address this with a new abstraction and protocol stack. We define Prefix Consensus, where parties input vectors and output two consistent vectors (v\sf low,v\sf high) that extend the maximum common prefix of honest inputs and satisfy vi\sf low\preceq vj\sf high for all honest parties i,j. We show that Prefix Consensus is solvable asynchronously and establish tight round-complexity bounds. We then define Strong Prefix Consensus, which additionally requires agreement on the high output, and give a leaderless partially synchronous protocol. Using its accountable variant, we build a leaderless, multi-proposer, censorship-resistant BFT SMR protocol with amortized four-round commit latency under synchronized starts, while guaranteeing that after GST at most f slots can be censored. Finally, we connect Prefix Consensus to graded consensus, obtaining a matching lower bound and a 3-round protocol, and derive leaderless Binary Consensus with improved worst-case complexity.