Prefix Consensus For Censorship Resilient BFT

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 $v_i^{\sf low}\preceq v_j^{\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.