Censorship Resistance vs Throughput in Multi-Proposer BFT Protocols

Censorship resistance and high throughput are two key benefits of modern multi-proposer BFT protocols. However, in existing designs these two properties are at odds: censorship resistance is typically achieved through duplicating transactions, which in turn harms throughput. This leaves open the question of whether it is possible to improve both properties simultaneously. In this paper, we formally study the trade-offs between censorship resistance and throughput in multi-proposer BFT protocols, where up to 𝑓 parties may be Byzantine. We present a model for the transaction assignment process, which allows us to classify assignment protocols into meaningful categories. Using this model, we establish fundamental tradeoffs between censorship resistance and throughput. We show that under welldefined conditions, any deterministic transaction assignment protocol that achieves optimal throughput must suffer from 𝑓 rounds of censorship delay; any deterministic assignment protocol that guarantees every transaction is committed within a constant number of rounds must suffer a factor of 𝑓 loss in throughput relative to the optimal baseline. On the positive side, we propose and analyze new transactionassignment protocols that enable flexible choices among throughput-censorship tradeoffs spanning the full spectrum dictated by our lower bounds. In particular, we give a protocol that achieves log 𝑓 censorship delay while paying only a factor-2 throughput loss relative to the state-of-the-art MirBFT (EuroSys'23), which incurs 𝑓 rounds of censorship delay. We further propose randomized assignment protocols that provably break both the deterministic lower bound for the censorship delay and throughput in expectation. All assignment protocols discussed can be integrated with existing multi-proposer protocols within our model as add-ons without modifying the consensus. CCS Concepts • Theory of computation → Distributed algorithms; Cryptographic protocols; • General and reference → Evaluation.