Prefix Consensus For Censorship Resistant BFT
For blockchain systems requiring censorship resistance, this work provides a novel theoretical foundation and practical protocols with concrete guarantees, though the incremental nature of combining known techniques limits its novelty.
The paper introduces Prefix Consensus, a new abstraction for censorship-resistant BFT consensus, and presents protocols achieving it with tight round-complexity bounds, enabling a leaderless BFT SMR protocol with amortized four-round commit latency and at most f censored slots after GST.
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 \emph{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 \emph{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.