An overview of the efficiency and censorship-resistance guarantees of widely-used consensus protocols
Orestis Alpos, Bernardo David, Nikolas Kamarinakis, Dionysis Zindros · 2025
Read An overview of the efficiency and censorship-resistance guarantees of widely-used consensus protocols by Orestis Alpos, Bernardo David, Nikolas Kamarinakis, Dionysis Zindros (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-03588.txt.
Introduction
Blocking unwanted records is a risk in shared ledgers, and a 2025 report by Orestis Alpos and co-authors reviews which designs resist it best. In leader-based systems, one party picks which records enter each block, which opens a path to censorship. Newer systems drop the leader role entirely and promise both speed and fairness.
The report compares widely used agreement protocols on speed, censorship resistance, and other traits. Formal work shows agreement itself is not needed for payments, which frees simpler designs. The authors also sketch a way to add short-term inclusion promises to leader-based designs. Builders of payment networks get a clear map of trade-offs between speed, cost, and open access.
Catalog record
| CREATOR | Orestis Alpos, Bernardo David, Nikolas Kamarinakis, Dionysis Zindros |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 44 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-03588
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An overview of the efficiency and censorship-resistance guarantees of widely-used consensus protocols Orestis Alpos, Bernardo David, Nikolas Kamarinakis, Dionysis Zindros Abstract Censorship resistance with short-term inclusion guarantees is an important feature of decentralized systems, missing from many state-of-the-art and even deployed consensus protocols. In leader-based protocols the leader arbitrarily selects the transactions to be included in the new block, and so does a block builder in protocols such as Bitcoin and Ethereum. In a different line of work, since the redundancy of consensus for implementing distributed payments was formally proven, consensusless protocols have been described in theory and deployed in the real world. This has resulted in blockchains and payment systems that are more efficient, and at the same time avoid the centralized role of a leader or block builder. In this report we review existing consensus and consensusless protocols with regard to their censorship-resistance, efficiency, and other properties. Moreover, we present an approach for new constructions with these properties in mind, building on existing leader-based protocols. This work was funded by Flashbots. 1 Model and preliminaries Censorship resistance has been studied in multiple works [ 17 , 27 , 26 ] . In this report we use the following definition of short-term censorship resistance . Definition 1 (Short-term censorship resistance) A protocol is short-term censorship resistant if malicious replicas cannot censor honest clients. Particularly, they cannot do so even for a short term, meaning that, if the system makes progress and creates an output, then a transaction submitted by an honest user appears in it. \dotparagraph Model We distinguish two types of parties, n replicas (also called validators in other works) and an unlimited number of clients . Replicas run the protocol and clients interact with it using its interface. We call a party – replica or client – honest , if it follows the protocol, and malicious otherwise. Notice that malicious parties can arbitrarily deviate from protocol specifications. \dotparagraph Network We review protocols modelled in the synchronous, partially synchronous, and asynchronous model. In the synchronous model, every message is delivered within a known finite delay of \Delta rounds. In the partially synchronous model, messages are delivered within a known finite delay of \Delta rounds only after an unknown but finite period of time called the Global Stabilization Time (GST). Finally, in the asynchronous model, messages are delivered within an unknown but finite delay. We denote by \delta the actual (but unknown) average network delay between two honest replicas. In synchrony it holds that \delta\leq\Delta . Protocols that proceed in the actual network speed without waiting for \Delta -timeouts are called responsive . \dotparagraph Structure In Section 2 we review existing consensus and consensusless protocols with regard to their censorship-resistance, efficiency, and other properties. In Section 3 we present a new approach for new constructions with these properties in mind, building on existing leader-based protocols. In section 4 we approach censorship-resistance based on rational and incentive-based arguments, and in Section 5 we summarize our findings and make our recommendations. Finally, Section 6 gives some links to existing implementations of the protocols we discuss. 2 Existing protocols 2.1 Metrics and comparison result In this section we review and compare existing protocols. Table 1 reports the following metrics. • Proposal latency measures the communication rounds from the proposal of a transaction (by one or more replicas) until it becomes committed by 2f+1 replicas. • Proposal period measures the communication rounds between consecutive proposals. • Max tx censorship reports the maximum number of rounds the adversary can delay a specific transaction, assuming the client sent it to all replicas, until it appears in a proposal, and while the rest of the system makes progress. • Communication complexity reports the exchanged number of messages in the happy path (column best ) and in the worst case (column worst ). • Throughput and latency report the throughput and latency for WAN deployments under no faults, as reported on the cited papers. Table 1 : Summary and comparison of various protocols. For leader-based protocols max tx censorship equals the proposal period times f , as up to f successive leaders can produce blocks without the censored transaction. For DAG-based protocols max tx censorship is 0 , because a transaction sent to sufficiently many replicas will be included in the output when the protocol commits the next round. IL stands for the inclusion lists approach ( Section 3 ). For these protocols, metrics that start with + indicate an incremental additive overhead to a leader-based protocol (the parameters are explained in the corresponding subsection). For IL constructions max tx censorship equals 0 , as the leader is limited by the ILs and cannot censor transactions. We denote by \txsize the transaction size. Protocol Theoretical efficiency Bench. (WAN, no faults) Proposal latency Proposal period Max tx censorship Com. compl. thr. lat. best worst #rep (tps) (sec) ref. Tendermint [ 7 ] 3\Delta 3\Delta 3\Delta f O(n^{2}) O(n^{2}) 32 520 2.83 [ 9 , Fig.6] 100 500 1–9 [ 11 ] HotStuff/DiemBFT [ 28 ] 7\delta 2\delta 2\Delta f O(n) O(n^{2}) 20 50K 1.7 [ 15 , Fig.5] Jolteon [ 15 ] 5\delta 2\delta 2\Delta f O(n) O(n^{2}) 20 50K 2 [ 15 , Fig.5] Ditto [ 15 ] 5\delta 2\delta 2\Delta f O(n) O(n^{2}) 20 50K 1.5 [ 15 , Fig.5] HotStuff-2 [ 18 ] 5\delta 2\delta 2\Delta f O(n) O(n^{2}) MoonShot [ 13 ] 5\delta \delta \Delta f O(n^{2}) O(n^{2}) IL (Sec. 3.1 ) +0 +0 0 +O(n^{2}|\inclist|) IL w. DA (Sec. 3.2 ) +\dadisp+\daretr +0 0 +\dacom IL w. b/cast (Sec. 3.3 ) +2\delta +0 0 +O(n^{2}\txsize) IL w. gossip (Sec. 3.4 ) +\gossipT +0 0 +O(n\gossipC\txsize) IL local (Sec. 3.5 ) +0 +0 0 +O(n|\inclist|) Narwhal/HotStuff [ 12 ] 8\delta 4\delta 0 O(n^{2}) O(n^{2}) 20 125K 1.8 [ 12 , Fig.6] 50 135K 1.8 [ 12 , Fig.6] Narwhal/Tusk [ 12 ] 6\delta 4\delta 0 O(n^{2}) O(n^{2}) 20 160K 3.2 [ 12 , Fig.6] 50 160K 3.2 [ 12 , Fig.6] psync-BullShark [ 22 ] 4\delta 4\delta 0 O(n^{2}) O(n^{2}) 20 110K 2.5 [ 22 , Fig.2] 50 130K 2.2 [ 22 , Fig.2] Mysticeti [ 3 ] 3\delta 3\delta 0 O(n^{2}) O(n^{2}) 10 300K <1 [ 3 , Fig.4] 50 100K <1 [ 3 , Fig.4] \oa 1. Aequitas, Themis [ 17 ] , QOF 2. Aleph 3. PaLa, Celestia, Thunderella, Hedera 4. FnF [ DBLP:conf/sirocco/AvarikiotiHSVWW23 ] 5. Economic rewards for producing blocks 6. Paradigm https://www.paradigm.xyz/2024/02/leaderless-auctions 7. BBCA [ DBLP:journals/corr/abs-2306-14757 ] 8. Mysticeti [ 3 ] 2.2 Single-leader protocols Tendermint [ 7 , 9 ] is a partially synchronous protocol that uses two rounds of voting and an all-to-all communication pattern. In the happy path, where no faults occur and the network is synchronous, it has a proposal latency of 3\delta . The proposal period is 3\delta . The leader is rotated after every epoch. HotStuff [ 28 ] is a partially synchronous protocol that uses three rounds of voting and an all-to-leader communication pattern. In the happy path, and assuming an implementation with threshold signatures, it achieves linear communication. The proposal latency to 7\delta , as every voting round contains an all-to-leader and a leader-to-all communication step. A module of the protocol