Censorship Resistance vs Throughput in Multi-Proposer BFT Protocols
Fatima Elsheimy, Ioannis Kaklamanis, Sarisht Wadhwa, Charalampos Papamanthou, Fan Zhang
TL;DR by AI
Multi-proposer BFT systems cannot maximize both censorship resistance and throughput at the same time. This paper formalizes that tradeoff and gives assignment protocols that let designers choose better points on the spectrum.
Abstract
Censorship resistance and high throughput are two key benefits of modern multi-proposer BFT protocols (such as Aptos and Sui). 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 $f$ 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 well-defined conditions, any deterministic transaction assignment protocol that achieves optimal throughput must suffer from $f$ 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 $f$ loss in throughput relative to the optimal baseline.
On the positive side, we propose and analyze new transaction-assignment 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 f$ censorship delay while paying only a factor-2 throughput loss relative to the state-of-the-art MirBFT (EuroSys’23), which incurs $f$ 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 can be integrated with existing multi-proposer protocols as add-ons without modifying the consensus.
- Awarded Ethereum Academic Grant