arXiv CSopen access

Simple-IT: Practical Low-Latency Signature-Free BFT Consensus

arXiv:2606.14404v1 [cs.DC] 12 Jun 2026

Simple-IT: Practical Low-Latency Signature-Free BFT Consensus Qianyu Yu Juan Villacis The Hong Kong University of University of Bern Science and Technology [email protected] [email protected] Giuliano Losa Zhuolun Xiang Xuechao Wang* Stellar Development Foundation Aptos Labs The Hong Kong University of Science and Technology [email protected] [email protected] [email protected]

Abstract—Recent advances in quantum computing pose a looming threat to most current Byzantine fault-tolerant (BFT) consensus protocols, which rely on quantum-vulnerable publickey signature schemes such as Ed25519 and BLS12-381. Instead of switching to much more expensive post-quantum secure signature schemes, an alternative is to use signaturefree protocols, which rely only on cheap, post-quantum secure authenticated channels. In this paper, we ask whether signature-free BFT consensus protocols can match the performance of current state-ofthe-art, quantum-vulnerable BFT consensus protocols. While previous work on the Sailfish++ [35] protocol showed that stateof-the-art throughput is attainable signature-free, the question of latency is still open. Several recent signature-free protocols have low latency in theory, but they are all very intricate, and no practical implementation has so far been presented. In this work, we propose Simple-IT, a new leader-based, signature-free BFT consensus protocol that achieves a theoretical latency of 4 message delays (one more than the optimum), and only 3 on its optimistic path. Crucially, Simple-IT is simple enough to be amenable to implementation and to practical optimizations such as speculative pipelining, and, as we show experimentally in a geo-distributed testbed, it achieves both throughput and latency competitive with state-of-the-art quantum-vulnerable protocols.

1. Introduction Partially synchronous [17] Byzantine fault-tolerant consensus protocols (BFT protocols, for short) are at the core of many high-performance reliable replicated systems such as blockchains, and their security and performance are critical. However, progress in quantum computing poses a credible, near-term threat to their security. Virtually every deployed BFT protocol authenticates validators’ messages with public-key signatures such as Ed25519 signatures or other schemes based on discretelogarithm and factoring problems. However, a quantum *

Correspondence: Xuechao Wang.

computer running Shor’s algorithm can break such schemes and recover a validator’s secret key from its public key in polynomial time, allowing the attacker to forge messages and break both the safety and liveness of the protocol. Building a quantum computer capable of such an attack remains a major engineering challenge, but the estimated costs keep falling [5], and NIST and the EU have called for transitioning to post-quantum-secure systems by 2035 and 2030, respectively [24], [28]. One solution to secure BFT protocols is to adopt quantum-secure signatures. Unfortunately, signing and verifying signatures are on the critical path of BFT protocols, and quantum-secure signatures are much more expensive than their post-quantum-vulnerable counterparts. For example, the schemes standardized by NIST [25], [26] are at least one order of magnitude larger and slower to verify than the post-quantum-vulnerable Ed25519 signatures. Our experiments in Section 5 show that, in a state-of-the-art BFT protocol, switching to post-quantum-secure ML-DSA65 signatures [16], [25] doubles latency. Another solution is to design signature-free BFT protocols, which, after a setup phase, rely only on authenticated channels secured using fast and quantum-secure symmetric cryptography such as HMAC-SHA256 (HMAC-SHA256 is only vulnerable to Grover’s algorithm, whose quadratic speedup is offset by a modest increase in key size). However, with only authenticated channels, we lose the transferability property of signatures (i.e., a party p1 cannot prove to another party p2 that a third party p3 sent a given message), and we must instead rely on mechanisms like Bracha’s Reliable Broadcast [7] to ensure parties converge on the same view of the system’s execution. Naively applying such mechanisms adds latency and increases communication complexity, while trying to orchestrate them cleverly can lead to overly intricate algorithms that are hard to turn into practical BFT protocols. In this paper, we ask whether partially synchronous, signature-free BFT consensus protocols are nevertheless a practical solution to obtaining post-quantum security with optimal resilience (n > 3f ) while matching the performance of the best post-quantum-vulnerable BFT protocols.

TABLE 1. L EADER - BASED BFT PROTOCOLS ( WITHOUT BLOCK DISSEMINATION ) Good-case/optimistic Eventual worst-case Bits sent Signature-free commit latency view duration per view IT-HS [3] Alg. BFT [10, Ch. 3]† TetraBFT [42] Forget-IT [1]† Simplex [12]

6δ 3δ 5δ 3δ 3δ

11∆ + δ 7∆ + 5δ ‡ 8∆ + δ § 4∆ + 3δ 3∆ + δ

O(n2 ) O(n3 ) O(n2 ) O(n2 ) O(n2 )

✓ ✓ ✓ ✓ ✗

Simple-IT (Opt-RBC) Simple-IT (Bracha-RBC)

5δ /3δ 4δ

8∆ + 4δ 5∆ + 2δ

O(n2 ) O(n2 )

✓ ✓

†

No peer-reviewed versions are available. Our estimate, as the thesis does not specify timeouts in terms of ∆. § With the view timer set to 8∆, the minimum needed for liveness; the paper prescribes 9∆. ‡

TABLE 2. C ONSENSUS PROTOCOLS WITH PRACTICAL , HIGH - PERFORMANCE IMPLEMENTATIONS INCLUDING BLOCK DISSEMINATION

Autobahn [21] DispersedSimplex [31] Sailfish [34] Sailfish++ [36] (Bracha-RBC) Sailfish++ [36] (Opt-RBC) Dispersed-Simple-IT (Opt-RBC) Dispersed-Simple-IT (Bracha-RBC) Mempool-Simple-IT (Opt-RBC) Mempool-Simple-IT (Bracha-RBC)

Good-case /optimistic commit latency

Eventual worst-case view duration

View complexity (bits)

Optimistic block time

Signaturefree

8δ/6δ * 3δ 5.6δ † 7.9δ † 10.2δ/5.6δ †

10∆ + δ 3∆ + δ 4∆ + 2δ ‡ 5∆ + 4δ § 8∆ + 5δ ‡

O(n3 ) O(n2 ) O(n3 ) O(n3 ) O(n3 )

3δ 2δ 2δ 3δ 2δ

✗ ✗ ✗ ✓ ✓

5δ/3δ 4δ 7δ/5δ 6δ

8∆ + 4δ 5∆ + 2δ 8∆ + 4δ 5∆ + 2δ

O(n2 ) O(n2 ) O(n2 ) O(n2 )

1δ 1δ 2δ 3δ

✓ ✓ ✓ ✓

*

6δ/4δ with optimistic tips. Average over the vertices of a DAG round: the leader vertex commits in 1RBC + 1δ , n − f − 1 vertices in 2RBC + 1δ , and the remaining f vertices in 3RBC + 1δ . ‡ Our estimate, as the paper does not prescribe timeouts for this RBC instantiation. § Using the paper’s prescribed 5∆ timeout, which applies to views that follow a correct leader; views entered via timeout certificate use 8∆, giving 8∆ + 4δ . †

Recently, Shrestha et al. [35] showed that, if one is willing to compromise on latency and scalability for better throughput, the answer is yes. They propose Sailfish++, a DAG-based signature-free BFT protocol, and show on a geo-distributed testbed that Sailfish++ matches the throughput of Sailfish [34], which itself achieves state-of-the-art throughput among post-quantum-vulnerable BFT protocols. However, neither Sailfish++ nor Sailfish matches the latency or scalability of leader-based post-quantum-vulnerable BFT protocols. Sailfish++ has an average optimistic commit latency of roughly 5.6 message delays1 and sends O(n3 ) bits per view, whereas some leader-based BFT protocols, e.g. DispersedSimplex [31], achieve a good-case commit latency of only 3 message delays and send only O(n2 ) bits per view. We therefore focus on signature-free leader-based BFT protocols and ask whether they can reach the same throughput, latency, and scalability as their signature-based counterparts. Unfortunately, this is unclear. First, to our knowledge, no implementations exist, so performance in practice is an 1. Leader vertices commit in 3 message delays, n − f − 1 other vertices commit in 5, and the remaining f commit in 7 message delays.

open question. Second, even theoretically, the only two peerreviewed protocols are IT-HS [3] and TetraBFT [42], which have theoretical best-case latencies of 6 and 5 message delays, respectively, far from the optimal 3 message delays achieved by signature-based protocols. In non-peer-reviewed work, Abraham et al. [1] propose Forget-IT, a protocol with a claimed best-case commit latency of 3 message delays; however, Forget-IT is a single-shot protocol that relies on very intricate rules and sophisticated correctness arguments, making it harder to understand and non-trivial to apply optimizations needed in practice, such as pipelining [41] and speculation [15]. To answer this question, we present the Simple-IT protocol, a new partially synchronous, signature-free, leaderbased BFT consensus protocol with optimal resilience of n > 3f . At a high level, Simple-IT adapts the Simplex [12] protocol to the signature-free setting by replacing quorum certificates with convergence mechanisms that make them unnecessary. In Simplex’s parlance, Simple-IT uses Reliable Broadcast (RBC) to notarize blocks and then finalizes them in one more message delay, achieving a good-case commit

latency of 1RBC+1δ , and it uses Reliable Notification (RN), a novel abstraction introduced in this paper, to disable consensus rounds that have timed out. Both primitives guarantee that all correct parties converge on the same outcome, and thus parties do not need certificates to prove outcomes to each other. The first strength of Simple-IT is its latency. Paired with Bracha’s RBC protocol [7], which we call BrachaRBC, Simple-IT achieves a good-case latency of 4 message delays; paired with the optimistic reliable-broadcast protocol of Shrestha et al. [35], [36]2 , which we call Opt-RBC, Simple-IT achieves a latency of only 3 message delays if 3 at least approximately 5n 6 parties behave correctly (when n ≈ 3f ). Note that three message delays is the lower bound for tolerating more than one failure [22]4 , even for signature-based protocols, and Simple-IT achieves it at the cost of slightly bigger optimistic-path quorums (roughly 2n 5n 6 ) than signature-based protocols (roughly 3 ). A latency comparison with other leader-based BFT protocols appears in Table 1. Second, like Simplex, Simple-IT follows simple rules that make it easily amenable to practical optimizations such as pipelining and speculative proposals. These techniques allow Simple-IT to maximize network utilization by running different consensus stages in parallel, and they allow reducing Simple-IT’s optimistic block time, i.e. the interval between two consecutive blocks in the good case, to just one message delay. The latter is crucial to reducing the end-toend latency of transactions arriving between two blocks. To demonstrate the flexibility afforded by Simple-IT’s simple rules, we present four variants of Simple-IT, each corresponding to a choice of RBC algorithm (Bracha-RBC or Opt-RBC) and to whether to use a two-stage RBC/commit pipeline or to also speculatively pipeline proposals. To determine whether Simple-IT can reach performance competitive with post-quantum-vulnerable protocols in practice, we develop two implementations of Simple-IT: Mempool-Simple-IT and Dispersed-Simple-IT. MempoolSimple-IT implements the base protocol, without speculative proposals, and uses a signature-free variant of the Autobahn [21] mempool to disseminate blocks. DispersedSimple-IT implements the speculative variant of Simple-IT, but does not use a mempool; instead, leaders disseminate their blocks using an erasure-coded RBC protocol using well-known techniques proposed by Cachin and Tessaro for AVID protocols [9]. Both protocols can be configured with Bracha-RBC or Opt-RBC (both erasure coded in the case of Dispersed-Simple-IT). Together, these implementations cover two practical approaches to data dissemination in high-throughput, leader-based BFT consensus deployed in 2. The original version [35] contains an error in the RBC protocol which is fixed in the arXiv version [36, version v4]. 3. The exact number is ⌈ n ⌉ + f ; see Section 2.3. 2 4. Kuznetsov et al. [22] show that any protocol with a 2-message-delay fast path tolerating t crash failures must have Byzantine resilience of n ≥ max(3f + 1, 3f + 2t − 1); this implies that, in an optimally-resilient protocol (f = ⌊ n−1 ⌋), a 2-message-delay fast path cannot tolerate more 3 than 1 failure.

production: shared-mempool-style dissemination, as used in systems such as Aptos Quorum Store [13], and leader-driven erasure-coded block propagation, as used in systems such as Monad RaptorCast [23] and Solana Turbine [18]. Table 2 compares the theoretical characteristics of MempoolSimple-IT and Dispersed-Simple-IT with those of other protocols that have practical, high-performance implementations. We evaluate Mempool-Simple-IT and Dispersed-SimpleIT on a real-world testbed of 50 nodes spread across 5 regions over 3 continents, and we compare their throughput and latency against their post-quantum-vulnerable counterparts Autobahn and DispersedSimplex [31]. Both Autobahn and DispersedSimplex achieve state-of-the-art performance in their respective categories. The experimental results show that both MempoolSimple-IT and Dispersed-Simple-IT closely match or surpass their post-quantum-vulnerable counterparts. MempoolSimple-IT achieves better latency and throughput than Autobahn across the entire latency-throughput spectrum, peaking at 170,000 transactions per second (92 MB/s) at roughly 0.5 seconds of latency. Dispersed-Simple-IT achieves the same peak throughput as DispersedSimplex (roughly 120,000 transactions per second, or 61 MB/s), and its latency is at most 9 percent higher in the pre-saturation regime. The results show that we can answer our motivating question affirmatively: signature-free, leader-based BFT protocols can be simple enough to implement efficiently and closely match, in practice, the throughput and latency of the best post-quantum-vulnerable leader-based BFT protocols. Thus, post-quantum security for high-performance BFT protocols does not require expensive post-quantum secure signatures on the critical path. Roadmap. We first define the model, total-order broadcast, and the Reliable Broadcast and Reliable Notification abstractions that Simple-IT uses in Section 2. We then present the Simple-IT protocol, including its optimistic and speculative variants, in Section 3, and analyze its safety, liveness, latency, and block time in Section 4. Section 5 describes the Mempool-Simple-IT and Dispersed-SimpleIT implementations and evaluates them on a geo-distributed testbed. Finally, Section 6 discusses related work and Section 7 concludes.

2. Preliminaries 2.1. Distributed-Computing Model We consider a set of n parties P = {p1 , . . . , pn } subject to f < n3 Byzantine failures and executing a protocol in an eventually-synchronous message-passing system with reliable, authenticated channels. Each party is either correct or Byzantine, and there are f < n3 Byzantine parties.Correct parties follow the protocol; Byzantine parties may behave arbitrarily. Which parties are Byzantine is unknown to the protocol. As is customary, we say that a set of n − f parties is a quorum, noting the

quorum intersection property: every two quorums have a correct party in common. Parties communicate by message passing and we assume that there is an authenticated, reliable channel between every pair of parties. This means that every message sent by a correct party to a correct party is eventually received, and that if a party pi receives a message m on the authenticated channel established with a party pj , then pi can be sure that pj sent m. We also assume that the system is eventually synchronous [17]. This means that message delay is arbitrary and unpredictable until an unknown point in time, called the Global Stabilization Time (GST), after which each message sent by a correct party to a correct party is delivered in at most δ time (the actual message delay after GST); δ is an unknown constant that is smaller than a publiclyknown constant upper-bound ∆. Additionally, we assume that parties have local clocks which, after GST, have no clock drift.

2.2. Problem Definitions The Simple-IT protocol variants formally implement Total-Order Broadcast, as defined below. Definition 1 (Total-Order Broadcast). In a total-order broadcast (TOB) protocol, each party may submit (or tobsubmit) blocks (of transactions) by calling tob submit(b), where b is a block, and the TOB protocol may deliver (or tob-deliver) blocks by calling tob deliver(b). A total-order broadcast protocol must satisfy the following properties: - Total Order. If a correct party delivers block b before block b′ , then no correct party delivers b′ before b. - Totality. If a correct party delivers a block b, then every correct party eventually delivers b. - Liveness. If a correct party submits infinitely many blocks, then every correct party delivers infinitely many blocks submitted by that party. Note that Liveness is intentionally weaker than some textbook liveness properties (e.g. the validity property in [8, Chapter 6.1]); it rules out trivial protocols that do nothing or starve some correct parties, and allows abstracting over implementation details like whether to queue, re-try, or forward blocks to other parties. The protocols we present satisfy stronger progress properties that depend on the protocol. For example, protocol S ensures that, eventually, if a correct leader proposes a block then it is delivered by all correct parties; protocol S s ensures that, eventually, if a correct leader is preceded by a correct leader and it proposes a block, then the block is committed by all correct parties. Our protocols are leader-based, and we define latency metrics as follows. Definition 2 (Good-case Commit Latency). The good-case commit latency of a leader-based protocol is T if, when the leader is correct and GST = 0, all correct parties commit within time T of the leader’s proposal.

Definition 3 (Optimistic Commit Latency). The optimistic good-case commit latency of a leader-based protocol is T if, when the leader is correct, GST = 0 and at least no non-leader parties are correct, all correct parties commit within time T of the leader’s proposal. In this paper, no = ⌈ n2 ⌉ + f , the same as in [36]. Equivalently, when the leader is correct, the optimistic path tolerates at most fo = ⌊n/2⌋ − f Byzantine non-leaders; for example, when f ≈ n/3, we have fo ≈ n/6. Definition 4 (Good-Case Block Time). The good-case block time of a leader-based protocol is the worst-case time interval between the proposals of two consecutive correct leaders after GST. Definition 5 (Eventual Worst-Case View Duration). The view duration of a protocol is T if, in every execution and for every post-GST view V , t2 − t1 ≤ T , where t1 denotes the earliest time at which every correct party has entered view V or higher, and t2 denotes the earliest time at which every correct party has entered a view strictly greater than V . We also make use of two abstractions, Reliable Broadcast and Reliable Notification, in order to give modular protocol descriptions. The Reliable Notification problem is novel and may be of more general interest. Definition 6 (Reliable Broadcast [7]). In a reliable broadcast (RBC) protocol, a party p may broadcast (or rbbroadcast) a message m = ⟨p, r, d⟩, for some identifier r (in Simple-IT, a round number) and some payload d, by calling broadcast(m); the RBC protocol may deliver (or rbdeliver) messages of the form ⟨p, r, d⟩, where p is a party, r an identifier, and d the payload, by calling deliver(m). A reliable broadcast protocol must satisfy the following properties: - Uniqueness. If a correct party delivers a message m = ⟨p, r, d⟩, then it does not deliver any other message m′ = ⟨p, r, d′ ⟩ with the same sender and same identifier and does not deliver m again. - Validity. If a correct party p broadcasts a message m = ⟨p, r, d⟩, for some r and d, then every correct party eventually delivers m. - Totality. If a correct party delivers a message m, then every correct party eventually delivers m. Definition 7 (Reliable Notification). In a reliable notification (RN) protocol, each party may raise (or rn-raise) a flag e by calling rn raise(e) and the protocol may confirm (or rn-confirm) e by calling rn confirm(e). A reliable notification protocol must satisfy the following properties: - Unanimity. If every correct party raises e, then every correct party eventually confirms e. - Totality. If a correct party confirms e, then every correct party eventually confirms e. - Validity. If a correct party confirms e, then at least n−2f correct parties raised e.

2.3. Latency of RBC Implementations For the purpose of analyzing latency, several parameters of RBC protocols are important. Definition 8 (Optimistic RBC delay do ). The optimistic delay of a reliable broadcast protocol, denoted by do , is the minimum number of message delays between the moment at which a correct sender broadcasts a message and the moment at which it is delivered by all correct parties. Definition 9 (Optimistic resilience fo ). fo is the maximum number of Byzantine parties such that the protocol delivers to correct parties a correct sender’s message in the optimistic delay do . Definition 10 (Worst-case RBC delay ds ). The worst-case delay of a reliable broadcast protocol, denoted by ds , is the maximum number of message delays between the moment at which a correct sender broadcasts a value and the moment at which it is delivered by all correct parties. Definition 11 (RBC totality delay dt ). The totality delay of a reliable broadcast protocol, denoted by dt , is the maximum number of message delays between the first moment at which a correct party delivers a value and the moment at which it is delivered by all other correct parties. In this work, we make use of two reliable broadcast implementations: Bracha’s broadcast protocol [7], which we call Bracha-RBC, and the optimistic RBC protocol of Shrestha et al. [36], which we call Opt-RBC. Both implement Reliable Broadcast assuming n > 3f , and their latency characteristics appear in Table 3. TABLE 3. L ATENCY PARAMETERS OF THE RBC P ROTOCOLS . Broadcast protocol

Opt. resilience (fo )

Bracha-RBC [7] fo = f Opt-RBC [36] fo = ⌊n/2⌋ − f * *

Opt. Worst Totality delay (do ) delay (ds ) delay (dt ) 3 2

3 4

2 4

fo ≈ n/6 when f ≈ n/3.

2.4. Erasure-coded RBC for Long Messages Following standard techniques from prior work of Cachin and Tessaro [9] and Shrestha et al. [36], both Bracha-RBC and Opt-RBC can be made communicationefficient for long messages, without increasing latency, using Reed-Solomon erasure coding. For an L-bit input, the resulting protocols have communication complexity O(nL+ κn2 log n) per broadcast, where κ denotes the hash output length, and they have balanced communication, meaning that all parties send and receive approximately the same number of bits. In consensus protocols, having leaders use erasure-coded RBC to disseminate their blocks avoids the leader-bottleneck problem [14], [40] and, compared to using a separate mempool layer, does not increase the good-case commit latency.

The flip side is that total communication is inversely proportional to the rate of the erasure code used, and that encoding and decoding require CPU time. Both erasure-coded RBC protocols use Reed-Solomon codes parameterized to recover the data from ⌈(n − f + 1)/2⌉ out of n fragments (this is f + 1 when n = 3f + 1); with n ≈ 3f , this gives a rate of approximately 1/3, i.e., a 3× communication overhead due to erasure coding. It is also worth noting that the techniques of Cachin and Tessaro and Shrestha et al. rely only on authenticated channels and cryptographic hash functions like SHA256, which are post-quantum-secure.

3. The Simple-IT Protocol 3.1. High-Level Structure Simple-IT implements total-order broadcast as defined in Definition 1. In a nutshell, parties submit blocks that Simple-IT must deliver in the same order at all parties; moreover, Simple-IT must ensure that if a correct party keeps submitting blocks, then eventually some block submitted by that party is delivered by all correct parties. To order submitted blocks, Simple-IT executes an infinite sequence of rounds 1, 2, . . . . In each round r, a predetermined leader uses reliable broadcast to try to assign a block b and a parent r′ to round r, where r′ is a round r′ < r or r′ = 0, and then parties try to agree on one of two mutually exclusive outcomes: to commit round r (only if the leader’s RBC succeeded) or to disable round r. The parent relation forms a tree of rounds, and SimpleIT ensures that committed rounds are all in the same chain, starting at 0, by requiring that (a) the parent of a round be a round with an assigned parent and block (or round 0) and (b) that the parent relation only skip rounds that are confirmed disabled. Formally, if r′ is the parent of r, then r′ must be safe, where r′ is safe, recursively, when: 1) r′ = 0 or r′ has itself an assigned safe parent and block, and 2) all rounds strictly between r′ and r are disabled. Finally, because all committed rounds are in the same chain, parties can deliver all the blocks, in order, appearing in the chain starting at 0 and leading up to the largest committed round. An example appears in Figure 1. Note that the high-level structure of Simple-IT, as just described, is similar to that of the Simplex protocol [12].

3.2. The Concrete Simple-IT Protocol Figure 2 presents the concrete Simple-IT protocol in detail. It specifies the local state variables of a party and the atomic steps that the party may take (whenever several steps are enabled, the party may execute any of them). Each round, parties restart their round timer (set for ∆to = (ds + dt )∆ time) and a predetermined leader for the round proposes a block and a safe parent round (Steps Enter round and Propose). Simple-IT uses a pre-determined, fair

⊥

v

r=0

r=1

r=2

v′

w

v ′′

r=3

r=4

r=5

Figure 1. An example Simple-IT execution. Solid blue boxes are committed rounds (1, 5); dashed gray boxes are disabled rounds (2, 3, 4); ⊥ is the genesis. Arrows point from each round to its assigned parent, if it has one. Round 1 is committed and has value v and parent 0. Round 2 has no value or parent and is disabled. Round 3 is disabled too, but it has an assigned value v ′ and parent round 1; it skips the disabled round 2. Round 4 is also disabled but has value w and parent round 1; it forks off of the tobdelivered chain and will never be tob-delivered. Round 5 has parent 3 even though 3 is disabled; that is fine since round 3 has an assigned value and parent. Notice all parents are safe. The tob-delivered total order is given by the chain of rounds 1, 3, 5, namely v, v ′ , v ′′ .

leader schedule, so all parties know in advance who the leader of a round is and every party leads infinitely many rounds. Once parties have rb-delivered the proposal for their current round and they have determined that the parent is safe, and the round timer has not fired, they vote to commit their current round (Step Vote; note that including a block digest or parent is unnecessary because they are uniquely determined by RBC). However, should parties not rb-deliver a proposal for their current round before the timer expires, they rn-raise their timeout flags using the reliable notification protocol depicted in Figure 4 (Step Timeout), and forgo voting to commit it; then, should they rn-confirm the round as timed out, they record the round as disabled (Step Disable). Finally, parties finish their current round and enter the next round (Step Advance round) as soon as they have a safe proposal and have either voted to commit or raised their timeout flag, or as soon as the current round is disabled. Importantly, note that voting to commit a round r and raising the round-r timeout flag are mutually exclusive. By quorum intersection, this guarantees that no round is ever both committed and disabled. Note, however, that it is possible for a party to rb-deliver the leader’s proposal for a round r after enough parties have raised the round-r timeout flag for it to be eventually marked as disabled. Thus, a disabled round can still be safe (e.g., round 3 in Figure 1), and thus serve as a parent of a future round (e.g., round 5 in Figure 1). The rest of the protocol machinery is agnostic to the current round: parties keep participating in the Reliable Broadcast and Reliable Notification subprotocols for all rounds, and they keep tracking what proposals they rbdeliver in which round (Step RB-deliver), which proposals they know are safe (Step Mark safe), and which rounds they have disabled (Step Disable). This is important for liveness, as advancing rounds (Step Advance round) and making a proposal (Step Propose) depend on being able to assign previous rounds a safe proposal or to disable them, which in turn depend on Reliable Broadcast or Reliable Notification making progress for those rounds.

Finally, after parties have received n−f votes to commit for any round r they know is safe, they deliver the round-r proposal and the ancestors that they have not delivered yet (Step Deliver). Note that the protocol features a two-stage pipeline: in the good case, the proposal phase for a round r+1, in which the leader rb-broadcasts its proposal, starts as soon as the proposal phase of round r finishes, and the commit phase of round r, in which parties vote to commit the round, executes in parallel with the proposal phase of round r + 1. We will later present another version of the protocol (Figure 3) that uses speculation to achieve more aggressive pipelining.

3.3. Correctness Sketch As explained in Section 3.1, Simple-IT ensures that every round with an assigned parent is safe, which implies that all committed blocks are in the same chain of parents and therefore establishes the Total Order property of TOB. Two key design elements guarantee liveness. First, in each round, note that either all correct parties deliver the leader’s proposal or they all raise their round-r timeout flag (or both). Thus, every round is eventually resolved as having a safe proposal or as disabled, and correct parties never get stuck in a round. Second, setting the round timer to a duration of ∆to = (ds +dt )∆ time ensures that, after GST, every round that has a correct leader commits: in the worst case, the leader enters the round late by at most max(dt , 2) = dt (the maximum of the totality delay of the reliable broadcast used and the totality delay of reliable notification), and then its proposal is delivered in at most the worst-case delay ds of the reliable broadcast used; thus, if ∆to = (ds +dt )∆, all correct parties vote to commit the round before they time out. For BrachaRBC, we get ∆to = 5∆, and for Opt-RBC we get ∆to = 8∆. With the fact that every party leads infinitely many rounds, we obtain the liveness property of TOB. Finally, Simple-IT ensures Totality because, after GST, all correct parties commit all rounds led by correct leaders and deliver all their ancestors, and a correct party that missed delivering a block therefore delivers it upon committing the next round led by a correct leader.

3.4. Optimistic and Speculative Variants We propose four variants of the protocol: protocols S , s Sopt , S s , and Sopt ; each of them corresponds to a choice of RBC algorithm (Bracha-RBC or Opt-RBC, indicated by the opt subscript) and to a proposal rule (normal proposal or speculative proposal, indicated by the s superscript). Protocols S and Sopt are both instances of the protocol described in Figure 2 with different RBC implementations. Protocol S uses Bracha-RBC [7] and achieves a good-case latency of 4 message delays (3 message delays for BrachaRBC plus one message delay to commit). In the good case, each successive leader proposes as soon as it delivers the previous round’s RBC, and thus the good-case block time of S is the worst-case delay of Bracha-RBC, i.e. 3δ .

Protocol Sopt uses Opt-RBC [36] and achieves a goodcase latency of 5 message delays; however, if at least no = ⌈ n2 ⌉+f parties are correct (roughly 83 percent, or 5n 6 , when n ≈ 3f ), protocol Sopt achieves an optimistic latency of only 3 message delays. The optimistic-case block time of Sopt is equal to the optimistic latency of Opt-RBC, i.e. 2δ . s Protocols S s and Sopt are variants of S and Sopt , respectively, where leaders can speculatively propose before they determine that the previous round’s proposal is safe. Both follow the description in Figure 3, with RBC instantiated with Bracha-RBC and with Opt-RBC, respectively. In Figure 3, the differences from the non-speculative variants (Figure 2) are highlighted in blue. The main difference compared to the non-speculative protocol is that we add the Speculative propose step, in which the party pi makes a speculative proposal for a round r greater than its current round. This step is enabled for a round r > curr round as soon as (a) r − k > 0 and pi has marked round r − k safe, where k is the proposal-pipeline depth parameter of the protocol, and (b) pi has received, but not necessarily rb-delivered, the proposal for round r − 1 from the leader of r − 1. Party pi then picks a block b and proposes it for round r with parent r − 1 by rb-broadcasting ⟨pi , r, ⟨r − 1, b⟩⟩. To avoid proposing multiple times in the same round, we also add a boolean variable proposed[r] tracking whether pi has already proposed in round r, and we do not propose (speculatively or otherwise) if this variable is already set. Finally, to avoid incurring k timeouts in a row should a Byzantine leader cause k speculative proposals without completing its RBC, we modify the Disable step so that, upon rn-confirming a round r as timed out, a party whose own round-r timer expired immediately rn-raises the timeout flags of the rounds r′ with curr round < r′ ≤ r + k − 1, recording each raise in a new flag aborted[r′ ] and forgoing voting in those rounds (the voted and timed out variables accordingly become per-round maps). All correct parties that timed out in round r raise these flags in parallel, so rounds r + 1 to r + k − 1 are rn-confirmed as timed out, and thus disabled, roughly one reliable-notification latency after round r is disabled, and Step Advance round then carries parties to round r + k . Note that the Speculative propose step creates a proposal pipeline of depth k : it allows proposal RBCs for up to k consecutive rounds to be in flight at the same time, each (except the first) having started δ time after the previous. In the good case, Bracha-RBC takes 3δ , and thus setting the pipeline depth to at least 3 allows S s to achieve a goodcase block time of 1δ . Similarly, since Opt-RBC takes an optimistic 2δ , setting the pipeline depth to at least 2 allows s Sopt to achieve an optimistic block time of 1δ . The flip side is that the two protocols require k correct leaders in a row, after GST, to guarantee that the last commits. That is because a Byzantine leader in a round r can cause the next k − 1 leaders to speculatively propose and then fail to complete its round-r RBC, causing round r to time out and thus rounds r to r + k − 1 to be disabled. Also note that votes to commit do not participate in the proposal pipeline: the Vote step still requires having

determined the current round safe, which implies having rbdelivered the current round’s proposal and all its ancestors. Safety then rests, as in the non-speculative protocol, on the fact that a correct party never both votes to commit a round and raises its timeout flag: the Vote step is disabled by timed out and aborted, the Timeout step is disabled by voted, and the Disable step raises flags only for rounds strictly above curr round, in which the party cannot have voted (parties vote only in their current round, and rounds are entered in increasing order) and in which aborted bars it from voting later. By quorum intersection, no round is ever both committed and disabled, exactly as in the nonspeculative protocol. Finally, note that the Disable step only rn-raises in rounds up to r + k − 1 if the party really timed out in round r. This avoids a runaway chain reaction where we rn-raise in the next k rounds, which causes confirming those rounds as timed out, which in turn causes rn-raising in the k rounds after that, etc. and no rounds can ever commit anymore.

4. Security Analysis Throughout this section we reason about the state model of the Simple-IT protocol of Figure 2. Some proofs and auxiliary lemmas are deferred to Appendix A, which also proves that the protocol of Figure 4 implements reliable notification. Recall that each round r has at most one assigned proposal: when a party rb delivers the round-r proposal ⟨Lr , r, ⟨r′ , b⟩⟩, it sets proposal[r] ← ⟨r′ , b⟩, where r′ is the parent and b the block assigned to round r; by the Totality property of reliable broadcast all correct parties that set proposal[r] agree on the same ⟨r′ , b⟩. We say that round r is disabled when its timeout is rn-confirmed (i.e., a party sets disabled[r] ← true upon rn confirm(⟨timeout, r⟩)), and that a party commits round r when it applies the Commit rule after receiving n − f ⟨commit, r⟩ messages. Definition 12 (Parent round). A round r′ is the parent of a round r if and only if proposal[r] = ⟨r′ , b⟩ for some block b and safe[r] = true; that is, r′ is the safe parent assigned to round r. The genesis round 0 has no parent. Definition 13 (Ancestor round). A round r′ is an ancestor of a round r when any of the following conditions hold: ′ • r = r; ′ • r is the parent of round r ; ′ ′′ ′′ • r is the parent of a round r and r is an ancestor of round r.

4.1. Safety Lemma 1. If a correct party commits a round r, then no correct party ever disables round r. Proof. If a correct party pi commits round r, then pi must have received n−f ⟨commit, r⟩ messages. Voting to commit round r and raising the round-r timeout flag are mutually exclusive for a correct party: by the Vote rule, a correct

State variables: • curr round: the current round, initialized to 1. • submitted: the set of blocks tob-submitted for ordering, initially empty. • delivered: the sequence of blocks tob-delivered so far, initially empty. ′ ′ • proposal[r]: the proposal ⟨r , b⟩ rb-delivered for round r from the leader of round r , or ⊥ if none was delivered so far; r is the parent round and b is the block; initially, proposal[0] = ⟨⊥, genesis⟩ and proposal[r] = ⊥ for r > 0. • safe[r]: a boolean map indicating whether round r has an assigned proposal with a safe parent; safe[0] = true and safe[r] = false for r > 0. safe[r] implies proposal[r] ̸= ⊥. • disabled[r]: a boolean map indicating whether the round-r timeout was rn-confirmed (so round r is disabled), initially everywhere false. • committed[r]: a boolean map indicating whether the round r was committed, initially false everywhere. • voted: boolean variable tracking whether the party has voted to commit the current round, reset to false each round. • timed out: boolean variable tracking whether the party has raised its timeout flag for the current round, reset to false each round. Helpers: ′ ′ ′ ′′ ′ ′′ • SafeParent(r, r ): Return true when 0 ≤ r < r , safe[r ] = true, and disabled[r ] = true for every round r < r < r . • Log(r): The sequence of blocks of the chain ending at round r , defined recursively: Log(0) is the empty sequence, and for r > 0 with proposal[r] = ⟨r′ , b⟩ and safe[r], Log(r) is Log(r′ ) followed by b. Protocol steps: • Init. Upon startup, enter round 1. • Submit. Upon a request to tob-submit a block b, add b to submitted. • Enter round. Upon entering a round r , set curr round ← r , reset the round timer to fire in ∆to = (ds + dt )∆ time, set voted ← false and timed out ← false, and, if pi is the leader of round r (Lr = pi ), propose. • Propose. Upon proposing, determine the highest round r such that SafeParent(curr round, r) and pick a block b ∈ submitted \ delivered where b ∈ / Log(r) (or b = ⊥ if no such block exists), and rb-broadcast the message ⟨pi , curr round, ⟨r, b⟩⟩. ′ ′ • RB-deliver. Upon rb deliver Lr ’s round-r proposal ⟨Lr , r, ⟨r , b⟩⟩ for some round r , set proposal[r] ← ⟨r , b⟩. ′ ′ • Mark safe. Upon proposal[r] = ⟨r , b⟩ and SafeParent(r, r ) for some round r , set safe[r] ← true. • Vote. Upon safe[curr round] = true, timed out = false, and voted = false, send ⟨commit, curr round⟩ to all parties and set voted ← true. • Timeout. Upon the round timer expiring, if voted = false then trigger rn raise(⟨timeout, curr round⟩) and set timed out ← true. • Disable. Upon rn confirm(⟨timeout, r⟩) for some round r , set disabled[r] ← true. • Commit. Upon receiving ⟨commit, r⟩ from n − f parties for some round r , set committed[r] ← true. • Deliver. Upon committed[r] = true, for some round r , and safe[r] = true, deliver proposal[r] and its parents: tob-deliver and append to delivered, in order, every non-⊥ block of Log(r) not previously delivered. • Advance round. Upon safe[curr round] = true and either voted = true or timed out = true, or upon disabled[curr round] = true, enter round curr round + 1. Figure 2. The Simple-IT protocol; code for party pi . A reliable-notification implementation appears in Figure 4.

party sends ⟨commit, r⟩ only while timed out = false, and by the Timeout rule it triggers rn raise(⟨timeout, r⟩) only while voted = false (after which it sets timed out = true). Hence, in round r, a correct party that has already raised its timeout flag will not subsequently vote (the Vote guard fails), and one that has already voted will not subsequently raise it (the Timeout guard fails); so it never does both. Now suppose toward a contradiction that some correct party disables round r, i.e., rn confirms the round-r timeout. By the Validity property of reliable notification (Definition 7), at least n − 2f correct parties called rn raise(⟨timeout, r⟩). Since (n − f ) + (n − 2f ) = n + (n − 3f ) > n, one of these correct parties also sent a ⟨commit, r⟩ message to pi , and thus both voted to commit round r and raised its roundr timeout flag. But we have previously established that no correct party does both — a contradiction.

once safe[r] = true, and a correct party sets safe[k] = true only when proposal[k] = ⟨k ′ , b⟩ and SafeParent(k, k ′ ) hold; that is, only once it has marked the parent of round k safe. Hence every ancestor k > 0 of round r has a parent that was marked safe by some correct party. Let r′ be the ancestor of r for the smallest r′ > 0, and let s be the parent of round r′ . There are three possibilities for s: either s > 0, s = 0, or s < 0. The first case is not possible, since then s would be an ancestor of r for a round smaller than r′ . The case s < 0 is not possible either, since SafeParent(r′ , s) requires 0 ≤ s. Thus the only possible value for s is 0, which proves the lemma.

Lemma 2. If a correct party commits a round r, then the genesis round 0 is an ancestor of it.

Proof. Suppose some correct party sets safe[r′ ] = true for a round r′ > r and, towards a contradiction, that round r is not an ancestor of r′ . By the reasoning of Lemma 2, every ancestor k > 0 of r′ has a parent that was marked safe by some correct party, and that parent is itself an ancestor of r′ lying strictly below k (since SafeParent requires a

Proof. For round r to be committed, it must have received ⟨commit, r⟩ messages from n − f parties, of which at least f + 1 are correct. A correct party sends ⟨commit, r⟩ only

Lemma 3. If a correct party commits a round r > 0, then round r is an ancestor of every round r′ > r for which some correct party sets safe[r′ ] = true.

Parameters: • k: the propose pipeline depth; k = 3 if using Bracha-RBC and k = 2 if using Opt-RBC. State variables: • curr round: the current round, initialized to 1. • submitted: the set of blocks tob-submitted for ordering, initially empty. • delivered: the sequence of blocks tob-delivered so far, initially empty. ′ ′ • proposal[r]: the proposal ⟨r , b⟩ rb-delivered for round r from the leader of round r , or ⊥ if none was delivered so far; r is the parent round and b is the block; initially, proposal[0] = ⟨⊥, genesis⟩ and proposal[r] = ⊥ for r > 0. • safe[r]: a boolean map indicating whether round r has an assigned proposal with a safe parent; safe[0] = true and safe[r] = false for r > 0. safe[r] implies proposal[r] ̸= ⊥. • disabled[r]: a boolean map indicating whether the round-r timeout was rn-confirmed (so round r is disabled), initially everywhere false. • committed[r]: a boolean map indicating whether the round r was committed, initially false everywhere. • voted[r]: a boolean map tracking whether the party has voted to commit round r , initially everywhere false. • timed out[r]: a boolean map tracking whether the party’s round-r timer expired and it raised the round-r timeout flag (Step Timeout), initially everywhere false. • aborted[r]: a boolean map tracking whether the party raised the round-r timeout flag to abort speculation in round r , without waiting for its round-r timer (Step Disable), initially everywhere false. • proposed[r]: a boolean map indicating whether this party has already rb-broadcast a proposal for round r , initially everywhere false. Helpers: ′ ′ ′ ′′ ′ ′′ • SafeParent(r, r ): Return true when 0 ≤ r < r , safe[r ] = true, and disabled[r ] = true for every round r < r < r . • Log(r): The sequence of blocks of the chain ending at round r , defined recursively: Log(0) is the empty sequence, and for r > 0 with proposal[r] = ⟨r′ , b⟩ and safe[r], Log(r) is Log(r′ ) followed by b. Protocol steps: • Init. Upon startup, enter round 1. • Submit. Upon a request to tob-submit a block b, add b to submitted. • Enter round. Upon entering a round r , set curr round ← r , reset the round timer to fire in ∆to = (ds + dt )∆ time, and, if pi is the leader of round r (Lr = pi ), propose. • Propose. Upon propose, if proposed[curr round] = false, determine the highest round r such that SafeParent(curr round, r) and pick a block b ∈ submitted \ delivered such that b ∈ / Log(r) (or b = ⊥ if no such block exists), and rb-broadcast the message ⟨pi , curr round, ⟨r, b⟩⟩. Set proposed[curr round] ← true. ′ ′ • Speculative propose. Upon receiving ⟨Lr−1 , r − 1, ⟨r , b ⟩⟩ directly from Lr−1 (the first message of its round-(r−1) RBC instance), for r > curr round: if pi is the leader of round r (Lr = pi ), proposed[r] = false, r − k > 0, and safe[r − k], then rb-broadcast a round-r proposal ⟨pi , r, ⟨r − 1, b⟩⟩ for some block b ∈ submitted \ delivered (or b = ⊥ if no such b exists), and set proposed[r] ← true. ′ ′ • RB-deliver. Upon rb deliver Lr ’s round-r proposal ⟨Lr , r, ⟨r , b⟩⟩ for some round r , set proposal[r] ← ⟨r , b⟩. ′ ′ • Mark safe. Upon proposal[r] = ⟨r , b⟩ and SafeParent(r, r ) for some round r , set safe[r] ← true. • Vote. Upon safe[curr round] = true, timed out[curr round] = false, aborted[curr round] = false, and voted[curr round] = false, send ⟨commit, curr round⟩ to all parties and set voted[curr round] ← true. • Timeout. Upon the round timer expiring, if voted[curr round] = false then trigger rn raise(⟨timeout, curr round⟩) and set timed out[curr round] ← true. • Disable. Upon rn confirm(⟨timeout, r⟩) for some round r , set disabled[r] ← true. Moreover, if timed out[r] = true, then, for every round r′ with curr round < r′ ≤ r+k−1 and aborted[r′ ] = false, trigger rn raise(⟨timeout, r′ ⟩) and set aborted[r′ ] ← true. • Commit. Upon receiving ⟨commit, r⟩ from n − f parties for some round r , set committed[r] ← true. • Deliver. Upon committed[r] = true, for some round r , and safe[r] = true, deliver proposal[r] and its parents: tob-deliver and append to delivered, in order, every non-⊥ block of Log(r) not previously delivered. • Advance round. Upon safe[curr round] = true and either voted[curr round] = true or timed out[curr round] = true or aborted[curr round] = true, or upon disabled[curr round] = true, enter round curr round + 1. Figure 3. The Simple-IT protocol with speculative pipelining; code for party pi . The differences with Figure 2 are highlighted in blue. A reliable-notification implementation appears in Figure 4.

parent to be a strictly smaller round); thus the ancestors of r′ form a descending chain from r′ down to 0. Consider the set of ancestors of r′ that exceed r. It is non-empty, since r′ is an ancestor of itself and r′ > r; let s be its smallest element, and let s′ be the parent of s (which exists because s > r ≥ 1, so s > 0). Now s′ is also an ancestor of r′ , and SafeParent(s, s′ ) forces s′ < s. By minimality of s, no ancestor of r′ lies in the interval (r, s), so s′ ≤ r. Moreover

s′ ̸= r: since s′ is an ancestor of r′ but r is not, we have s′ < r. Combining, s′ < r < s. For some correct party to set safe[s] = true, the predicate SafeParent(s, s′ ) must hold, which requires disabled[k ′′ ] = true for every round s′ < k ′′ < s, and in particular for round r (as s′ < r < s). But by Lemma 1, no correct party ever disables round r, so disabled[r] = true never holds for a correct party. This contradicts SafeParent(s, s′ ), and the lemma follows.

1) Vote. Upon invoking rn raise(e), pi broadcasts a ⟨vote, e⟩ message. 2) Accept. Upon receiving ⟨vote, e⟩ messages from n − f parties, pi broadcasts a ⟨accept, e⟩ message. 3) Confirm. Upon receiving ⟨accept, e⟩ messages from 2f + 1 parties, pi confirms e by invoking rn confirm(e). 4) Cascade. Upon receiving ⟨accept, e⟩ messages from f + 1 parties, and not having sent an ⟨accept, e⟩ message, pi broadcasts an ⟨accept, e⟩ message. Figure 4. Reliable notification protocol.

Lemma 4. If two correct parties pi and pj commit rounds r and r′ respectively, then either r is an ancestor of r′ , or r′ is an ancestor of r. Proof. Without loss of generality assume that r ≤ r′ ; if r = r′ the claim is immediate, so assume r < r′ . Since round r′ is committed, at least f +1 correct parties sent ⟨commit, r′ ⟩, and by the Vote rule each did so only after setting safe[r′ ] = true; hence some correct party set safe[r′ ] = true. As r′ > r and round r is committed, Lemma 3 shows that r is an ancestor of r′ . Theorem 1 (Total Order). If a correct party tob-delivers a block b before a block b′ , then no correct party tob-delivers b′ before b. Proof. A correct party tob-delivers blocks only through the Commit and Deliver rules: upon committing a round k , it sets delivered ← Log(k) and delivers, in order, the blocks of Log(k) it has not yet delivered. By the definition of Log, if k1 is an ancestor of k2 then Log(k1 ) is a prefix of Log(k2 ). By Lemma 4, the rounds committed by correct parties are totally ordered by the ancestor relation, so the sequences Log(k) over all committed rounds k form a chain under the prefix order. Consequently, the sequence of blocks tobdelivered by any correct party is always a prefix of the sequence tob-delivered by any other, and the relative order of any two blocks delivered by correct parties is the same at all of them.

4.2. Liveness Lemma 5. For each round r, either all correct parties rb-deliver the leader Lr ’s proposal, or all correct parties disable round r, or both. Proof. There are two possible cases for any given round r: either at least one correct party rb-delivers the leader’s proposal, or no correct party ever does so. In the first case, by the Totality property of reliable broadcast, all correct parties will eventually rb-deliver the leader’s proposal. Otherwise, no correct party ever sets safe[r] = true or votes to commit round r, so after their round timers expire all correct parties trigger rn raise(⟨timeout, r⟩). By the Unanimity property of reliable notification, since all correct parties raise the roundr timeout flag, all correct parties eventually rn confirm it and disable round r.

A consequence of the previous lemma is that all correct parties eventually satisfy the Advance round rule and progress to round r + 1. Corollary 1. All correct parties keep entering higher rounds. Theorem 2 (Liveness). With a round timeout larger than (dt + ds )δ , and a leader schedule that ensures that correct leaders are chosen infinitely often, the protocol guarantees that if a correct party submits infinitely many blocks, then all correct parties deliver infinitely many blocks submitted by that party. Theorem 3 (Totality). If a correct party tob-delivers a block b, then every correct party eventually tob-delivers b. 4.2.1. Latency Bounds. Lemma 6 (Optimistic latency). If at most fo parties are faulty, Lr is correct, and it entered round r at a time t ≥ GST, all correct parties commit round r within (do + 1)δ time of its proposal. Corollary 2 (Optimistic latency with Bracha-RBC). The optimistic latency of protocols S and S s is 4δ if at most fo parties are faulty. Corollary 3 (Optimistic latency with Opt-RBC). The optis is 3δ if at most fo mistic latency of protocols Sopt and Sopt parties are faulty. Lemma 7 (Optimistic block time). The optimistic block time of Simple-IT using propose-upon-delivery pipelining is do δ if at most fo parties are faulty. Corollary 4. The optimistic block time of Simple-IT variants S and Sopt is 3δ and 2δ respectively. Lemma 8. After GST, if all correct parties enter round r at the latest at time t, then all correct parties move to the next round at the latest at time t + ∆to + dt δ , where ∆to = (ds + dt )∆. Corollary 5 (Eventual worst-case view duration). The eventual worst-case view duration (Definition 5) of Simple-IT is ∆to +dt δ : 5∆+2δ for variant S (Bracha-RBC) and 8∆+4δ for variant Sopt (Opt-RBC).

4.3. Pipelined-Proposal Version We now turn to the version of Simple-IT appearing in Figure 3, which pipelines consecutive proposals. Since all rounds still progress only through the reliable broadcast or the reliable notification subprotocols, the safety analysis of the standard version holds also in the pipelined version. Theorem 4 (Liveness). With a round timeout larger than (dt +ds )δ , and a leader schedule that ensures that sequences of k correct leaders are chosen infinitely often, the protocol guarantees that if a correct party submits infinitely many blocks, then all correct parties deliver infinitely many blocks submitted by that party.

Theorem 5 (Totality). Under the assumptions of Theorem 4, if a correct party tob-delivers a block b, then every correct party eventually tob-delivers b. Lemma 9 (Optimistic block time). The optimistic block time s of Simple-IT variants S s and Sopt is δ . Lemma 10. In the pipelined-proposal version of Simple-IT, after GST, if all correct parties enter round r at the latest at time t, then all correct parties move to the next round at the latest at time t + ∆to + dt δ . Corollary 6 (Eventual worst-case view duration, pipelined). The eventual worst-case view duration (Definition 5) of the pipelined-proposal version of Simple-IT is ∆to +dt δ : 5∆+2δ s for variant S s (Bracha-RBC) and 8∆ + 4δ for variant Sopt (Opt-RBC).

5. Empirical Evaluation To evaluate Simple-IT in practice, we implement two versions of Simple-IT, Mempool-Simple-IT and DispersedSimple-IT, and we perform experiments on a realworld, geo-distributed testbed. Mempool-Simple-IT uses a signature-free version of Autobahn’s shared mempool for data dissemination, and Dispersed-Simple-IT uses leaderdriven erasure-coded dissemination. We compare each version against baselines using the same data-dissemination approach: Autobahn [21] and Sailfish++ [35] for MempoolSimple-IT, and DispersedSimplex [31] for DispersedSimple-IT. For each variant, we evaluate the performance with Bracha-RBC [7] and Opt-RBC [36]. We further include PQ-DispersedSimplex, which follows DispersedSimplex but replaces BLS signatures with quantum-secure signatures ML-DSA-65. Beyond throughput and latency, we measure the bandwidth usage of the Simple-IT variants and evaluate their recovery behavior after a leader crash. Before describing the results in detail, let us briefly state the key findings. The results show that both SimpleIT variants are highly competitive with their signaturebased, post-quantum-vulnerable counterparts. MempoolSimple-IT surpasses Autobahn on both latency and throughput axes. Dispersed-Simple-IT matches DispersedSimplex’s peak throughput with roughly 9 percent worse latency, whereas the obvious alternative of using post-quantumsecure signatures (PQ-DispersedSimplex) instead incurs a 2x latency cost. Moreover, we find that the bandwidth/CPU costs of signature-freedom are negligible relative to data dissemination for leader-based protocols. Implementation details. Mempool-Simple-IT5,6 is built by modifying the Autobahn codebase [20]. The original Autobahn’s mempool takes 3 message delays. Parties broadcast transaction batches. After gathering f +1 votes for the batch, they forward the batch digest along with the votes. Leaders 5. Opt-Mempool-Simple-IT implementation: https://github.com/qyu100/ Simple-IT/tree/Opt-Mempool-Simple-IT. 6. Bracha-Mempool-Simple-IT implementation: https://github.com/qyu 100/Simple-IT/tree/Bracha-Mempool-Simple-IT.

then propose the certified batch that has been seen by at least n−f parties, as consensus input. Mempool-Simple-IT reuses Autobahn’s dissemination layer in a signature-free form. The leader’s proposal includes a set of batches, each of which has received 2f + 1 votes (these votes are broadcast and are not embedded in the proposal). Upon receiving the proposal, a non-leader checks whether it has seen at least f + 1 votes for every batch in the proposal. If so, the non-leader casts its own consensus vote for the proposal. Thus MempoolSimple-IT’s mempool takes 2 message delays. The consensus protocol is replaced with Simple-IT, following Figure 2. For a fair comparison, because Autobahn does not pipeline, we compare Autobahn with a non-pipelined version. Dispersed-Simple-IT7,8 and DispersedSimplex9 are built by modifying the Sailfish codebase [32]. Our DispersedSimplex baseline implements only the failure-free path, which is sufficient for our fault-free performance comparison because its failure path does not affect the fault-free performance. PQ-DispersedSimplex10 is built on top of DispersedSimplex by replacing BLS signatures with ML-DSA-65 signatures [25] (implemented using the Rust ml-dsa crate [29]). Dispersed-Simple-IT follows the pipelined protocol in Figure 3, and all other dispersed baselines are pipelined. For both Mempool-Simple-IT and Dispersed-SimpleIT, we evaluate two RBC variants: Bracha-RBC [7] and Opt-RBC [36]. In the figures, these variants are labeled with the prefixes “Bracha-” and “Opt-”, respectively. In the Dispersed-Simple-IT implementations, leaders disseminate blocks using the erasure-coded RBC techniques of Cachin and Tessaro [9] and Shrestha et al. [36]. Experimental setup. We conducted our evaluations on the Google Cloud Platform (GCP), deploying nodes evenly across five distinct regions: us-east1-b (South Carolina), us-west1-a (Oregon), europe-west1-b (Belgium), europenorth1-b (Finland) and asia-northeast1-a (Japan). We employed c2-standard-16 instances [27], each featuring 16 vCPUs, 64 GB of memory, and up to 32 Gbps network bandwidth. All nodes ran on Ubuntu 22.04, and round-trip latencies between GCP regions range from roughly 30 ms to 260 ms (details appear in Table 4). In every experiment, each party generates a configurable number of transactions (512 random bytes each) for inclusion in the block. Blocks in the Dispersed variants contain up to 50 MB. Each experiment runs for 120 seconds with 50 nodes, or for 60 seconds with 10 nodes. In Dispersed variants, the leader generates the transactions when proposing. In all the experiments, latency is measured as the average time between the creation of a transaction and its commit by 50% of non-faulty nodes. Throughput is measured by the number of committed transactions per second. 7. Opt-Dispersed-Simple-IT implementation: https://github.com/qyu10 0/Simple-IT/tree/Opt-Dispersed-Simple-IT. 8. Bracha-Dispersed-Simple-IT implementation: https://github.com/qyu 100/Simple-IT/tree/Bracha-Dispersed-Simple-IT. 9. DispersedSimplex implementation: https://github.com/qyu100/Simple -IT/tree/DispersedSimplex. 10. PQ-DispersedSimplex implementation: https://github.com/qyu100/ Simple-IT/tree/PQ-DispersedSimplex.

Latency (s)

Latency (s)

1.5 1.0 0.5 0.00

50

100

150

Throughput (KTps)

200

Figure 5. Latency vs. throughput of MempoolSimple-IT and Autobahn with 50 nodes.

2.0 1.5

Opt-Dispersed-Simple-IT Bracha-Dispersed-Simple-IT Opt-Mempool-Simple-IT Bracha-Mempool-Simple-IT

1.0 0.5

20

40

60

80

100

Throughput (KTps)

120

Figure 6. Latency vs. throughput of Dispersed-Simple-IT, DispersedSimplex and PQ-DispersedSimplex with 50 nodes.

TABLE 4. P ING LATENCIES ( IN MS ) BETWEEN GCP REGIONS Destination* Source

us-e1

us-w1

eu-w1

eu-n1

as-n1

us-east1-b us-west1-a europe-west1-b europe-north1-b asia-northeast1-a

0.70 64.30 92.22 111.96 157.07

64.17 0.84 130.69 159.77 90.94

92.21 130.67 0.59 31.16 220.60

111.95 159.78 31.17 0.72 262.86

157.79 88.57 220.67 262.90 0.93

*

2.5

Opt-Dispersed-Simple-IT Bracha-Dispersed-Simple-IT DispersedSimplex PQ-DispersedSimplex

Bandwith (Gbps)

2.00 1.75 1.50 1.25 1.00 0.75 0.50 0.25 0.000

Opt-Mempool-Simple-IT Bracha-Mempool-Simple-IT Opt-Sailfish++ Autobahn

2.0

Region names are abbreviated versions of the source regions.

Methodology. In our evaluations, we gradually increased the input transactions. As depicted in Figure 5 and Figure 6, the throughput increases with increasing load without increasing latency up to a certain point before reaching saturation. After saturation, the latency starts to increase while the throughput either remains consistent or slightly increases. In the subsequent figures, we report the throughput and latency just before reaching this saturation point. Performance comparison under fault-free cases. Figure 5 compares Mempool-Simple-IT with Autobahn and with Opt-Sailfish++, a Sailfish++ baseline using Opt-RBC. In Opt-Sailfish++, a leader’s block commits in three message delays, whereas a non-leader block needs at least five. This gives an estimated average of about 5.6 message delays (see Footnote 1). Autobahn requires 3 message delays for its mempool phase and 5 message delays for consensus, for a total of 8 message delays. Mempool-Simple-IT needs only 2 message delays for its mempool phase. Consequently, Bracha-Mempool-Simple-IT takes 6 message delays in total and Opt-Mempool-Simple-IT takes 5 message delays. Thus, Mempool-Simple-IT still retains a latency advantage. Figure 6 compares the dispersed implementations, where in each round the leader disseminates its proposed block with erasure-coded RBC. Because Dispersed-Simple-IT and DispersedSimplex use the same dissemination path, their latency gap primarily reflects the consensus path. BrachaDispersed-Simple-IT has higher latency than Opt-DispersedSimple-IT because Bracha-RBC adds one message delay. Before saturation, DispersedSimplex has only a modest latency advantage over Opt-Dispersed-Simple-IT, about 35 ms on average. In the 50-node setting, this gap comes from two factors. First, Opt-Dispersed-Simple-IT waits for 40 votes

0.00

25

50

75

100 125 150 175

Throughput (KTps)

Figure 7. Outgoing bandwidth per node (Gbps/node) vs. throughput for the Simple-IT variants with 50 nodes.

on its optimistic path, whereas DispersedSimplex needs a quorum of 34 votes. Second, DispersedSimplex’s signed quorum certificates can be forwarded directly. This could be beneficial under network congestion. With 10 nodes, this threshold gap disappears: both thresholds are 7, so Opt-Dispersed-Simple-IT performs similarly to DispersedSimplex. PQ-DispersedSimplex keeps the DispersedSimplex consensus path but replaces BLS signatures with ML-DSA, so its curve shows the post-quantum signature overhead in the same dispersed setting; we can see that, at about 1 second latency, PQ-DispersedSimplex has a latency roughly double that of even Dispersed-Simple-IT with Bracha-RBC (the slowest variant of Simple-IT in this figure). Figure 7 reports outgoing bandwidth per node, measured in Gbps/node. Bandwidth grows almost linearly with throughput, and variants using the same dissemination approach have nearly overlapping curves. This indicates that data dissemination dominates the network cost. At their respective high-throughput points, the mempool variants use about 0.6 Gbps/node near 170 KTps, whereas the dispersed variants use about 1.3 Gbps/node near 120 KTps. Thus, in our implementation, the shared-mempool design has a substantially lower outgoing-bandwidth cost per committed transaction than leader-driven erasure-coded RBC, since erasure-coded dispersal introduces a constant-factor communication overhead for each payload. Performance comparison under failures. We evaluate the performance of Opt-Mempool-Simple-IT11 and OptDispersed-Simple-IT12 under failures with 10 nodes. In this experiment, the proposal of a leader located in europewest1-b (Belgium) is skipped at approximately 20 seconds, simulating a leader crash for that round. After the timeout expires, the leader recovers and continues committing transactions. We set the timeout to 3 seconds and ran the experiment for 60 seconds. The x-axis shows the execution time, and the y-axis reports throughput computed over a 3-second sliding window. As shown in Figure 8, the throughput drops immediately when the leader’s proposal is skipped, and recovers to its 11. Opt-Mempool-Simple-IT failure implementation: https://github.com /qyu100/Simple-IT/tree/Opt-Mempool-Simple-IT-Failure. 12. Opt-Dispersed-Simple-IT failure implementation: https://github.com /qyu100/Simple-IT/tree/Opt-Dispersed-Simple-IT-Failure.

Throughput (KTps)

80 60

6. Related Work

Opt-Dispersed-Simple-IT Skipped Proposal

40 20 00

10

20

30

40

Execution Time (s)

50

60

Figure 8. Throughput vs. execution time of Opt-Dispersed-Simple-IT with 10 nodes.

Throughput (KTps)

120 100 80 60 40 20 00

Opt-Mempool-Simple-IT Skipped leader

10

20

30

40

Execution Time (s)

50

60

Figure 9. Throughput vs. execution time of Opt-Mempool-Simple-IT with 10 nodes.

pre-failure level after roughly 10 seconds. In Figure 9, the throughput also drops at the skipped-leader round, but it is followed by an immediate spike. This spike is caused by burst commits: although the crashed leader stops proposing for that round, the mempool continues producing blocks. As a result, leader in the next round can commit more pending blocks at once, leading to a temporary throughput peak. Discussion on erasure-coding costs. To evaluate the cost of erasure-coded dissemination, Table 5 reports the measured CPU-side cost of constructing and reconstructing erasurecoded proposals in the 50-node deployment. All runs use Reed-Solomon codes with 18 data shards and 32 parity shards. Proposal construction includes block serialization, Reed-Solomon encoding, and constructing a Merkle tree over the encoded shards. For reconstruction, we measure the time after a node has collected enough erasure-coded fragments to recover the block payload and verify that the recovered data matches the Merkle root in the header. The latency column reports the latency of Opt-Dispersed-SimpleIT with 50 nodes. These costs grow roughly linearly with the shard size. TABLE 5. E RASURE - CODING COSTS FOR D ISPERSED -S IMPLE -IT IN THE 50 - NODE DEPLOYMENT. Block size

Shard size

10 MB 0.56 MB 30 MB 1.69 MB 50 MB 2.82 MB

Proposal construction Reconstruction Latency p50/p95 p50/p95 50/54 ms 131/140 ms 212/227 ms

10/12 ms 26/31 ms 42/49 ms

460 ms 872 ms 1085 ms

Post-Quantum and Signature-Free BFT. A direct way to make BFT protocols quantum-secure is to replace classical digital signatures with post-quantum signatures. The natural candidates are the NIST-standardized ML-DSA [25], the likely default for performance-oriented systems, and the hash-based SLH-DSA [26], a more conservative but less efficient alternative. However, post-quantum signatures are larger and more expensive to verify than classical signatures, increasing the latency on the consensus critical path (as shown in Figure 6). This motivates removing public-key signatures from the BFT protocol entirely. Signature-free BFT protocols rely only on authenticated channels after setup and are closely related to unauthenticated and information-theoretic BFT. The earliest is Algorithm BFT from Castro’s thesis [10, Chapter 3], a PBFT variant that replaces signatures with MAC vectors, achieving 3δ good-case latency at the cost of O(n3 ) communication per view. IT-HS [3] achieves optimal resilience and responsiveness with O(n2 ) communication per view, but has 6δ good-case latency. TetraBFT [42] reduces this to 5δ , while Forget-IT [1] achieves the optimal 3δ latency. Shoup [30, Section 7] also sketches a signature-free variant of DispersedSimplex using Bracha-style echo/ready certification, roughly doubling latency to 6δ . However, these protocols have not been implemented or evaluated in highperformance settings, and their protocol complexity can make implementation and practical optimizations such as pipelining and speculation more challenging. Leader-Based BFT Consensus. Leader-based partially synchronous protocols [11], [12], [19], [21], [33], [39], [41] achieve low latency by leveraging signatures. In particular, PBFT [11], Simplex [12], Hydrangea [33] and Raptr [39] are protocols with optimal 3δ good-case latency. To improve throughput, many systems with leader-based protocols decouple data dissemination from ordering so that consensus runs on small digests rather than raw transaction data. Examples include Narwhal [14] and Autobahn [21]. Another approach, used by DispersedSimplex [31], employs leader-driven erasure-coded dissemination to balance bandwidth while preserving low latency. DAG-Based BFT Consensus. DAG-based protocols disseminate data in parallel and derive an ordering from the resulting DAG. Narwhal and Tusk [14] separate data availability from ordering, while Bullshark [38], Shoal [37], Shoal++ [4], Sailfish [34] and Mysticeti [6] further reduce latency. Sailfish++ [36] extends Sailfish to be signature-free and achieves 3δ latency under optimistic conditions, but incurs cubic message complexity per view. Reliable Broadcast. Bracha-RBC [7] tolerates optimal f < n/3 Byzantine faults and has 3δ good-case latency. For long messages, erasure coding yields communication-efficient RBC: Cachin and Tessaro [9] obtain O(nL + κn2 log n) communication for an L-bit input. Signature-free RBC can

complete in two steps under a stronger fault tolerance assumption of n ≥ 4f [2]. Shrestha et al. [36] give Opt-RBC, an optimistic signature-free RBC that completes in two steps under stronger honesty assumptions while preserving optimal resilience otherwise.

[8]

C. Cachin, R. Guerraoui, and L. Rodrigues, Introduction to Reliable and Secure Distributed Programming. Berlin, Heidelberg: Springer, 2011.

[9]

C. Cachin and S. Tessaro, “Asynchronous verifiable information dispersal,” in 24th IEEE Symposium on Reliable Distributed Systems (SRDS’05). IEEE, 2005, pp. 191–201.

7. Conclusion

[10] M. Castro, “Practical Byzantine Fault Tolerance,” Ph.D., MIT, Jan. 2001.

This paper presents Simple-IT, a signature-free, leaderbased BFT consensus protocol with optimal resilience that commits in 4 message delays in the good case (one more than the optimum) and 3 on its optimistic path. By replacing signature-based quorum certificates with Reliable Broadcast and a new Reliable Notification primitive, SimpleIT retains the simplicity of authenticated protocols such as Simplex, making it amenable to practical optimizations such as pipelining and speculative proposals that reduce its optimistic block time to a single message delay. We give the first practical implementation of a signature-free, leader-based BFT protocol, pairing it with the two blockdissemination approaches that dominate production systems. Our geo-distributed evaluation shows that both variants match or outperform their state-of-the-art, quantumvulnerable counterparts. These results demonstrate that postquantum security in BFT consensus need not come at the cost of performance, and that signature-free protocols are a practical path to quantum-safe, high-performance replicated systems.

[11] M. Castro, B. Liskov et al., “Practical byzantine fault tolerance,” in OSDI, ser. 99, no. 1999, 1999, pp. 173–186.

Acknowledgments We thank Nibesh Shrestha and Balaji Arun for helpful advice on the implementation.

References [1]

I. Abraham, S. Das, Y. Efron, and J. Komatovic, “Forget-IT: Optimal Good-Case Latency For Information-Theoretic BFT,” 2026.

[2]

I. Abraham, L. Ren, and Z. Xiang, “Good-case and bad-case latency of unauthenticated byzantine broadcast: A complete categorization,” in 25th International Conference on Principles of Distributed Systems, 2022.

[3]

I. Abraham and G. Stern, “Information Theoretic HotStuff,” in 24th International Conference on Principles of Distributed Systems (OPODIS 2020), ser. Leibniz International Proceedings in Informatics (LIPIcs), Q. Bramas, R. Oshman, and P. Romano, Eds., vol. 184. Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021, pp. 11:1–11:16.

[4]

B. Aurn, Z. Li, F. Suri-Payer, D. Sourva, and A. Spiegelman, “Shoal++: High throughput dag bft can be fast!” arXiv preprint 2405.20488, 2024.

[5]

R. Babbush, A. Zalcman, C. Gidney, M. Broughton, T. Khattar, H. Neven, T. Bergamaschi, J. Drake, and D. Boneh, “Securing elliptic curve cryptocurrencies against quantum vulnerabilities: Resource estimates and mitigations,” arXiv preprint arXiv:2603.28846, 2026.

[6]

[7]

K. Babel, A. Chursin, G. Danezis, L. Kokoris-Kogias, and A. Sonnino, “Mysticeti: Low-latency dag consensus with fast commit path,” in Network and Distributed System Security Symposium (NDSS), 2025 (To appear). G. Bracha, “Asynchronous byzantine agreement protocols,” Information and Computation, vol. 75, no. 2, pp. 130–143, 1987.

[12] B. Y. Chan and R. Pass, “Simplex Consensus: A Simple and Fast Consensus Protocol,” in Theory of Cryptography, G. Rothblum and H. Wee, Eds. Cham: Springer Nature Switzerland, 2023, pp. 452– 479. [13] B. Cho and A. Spiegelman, “Quorum store: How consensus horizontally scales on the aptos blockchain,” https://medium.com/aptoslabs /quorum-store-how-consensus-horizontally-scales-on-the-aptos-blo ckchain-988866f6d5b0. [14] G. Danezis, L. Kokoris-Kogias, A. Sonnino, and A. Spiegelman, “Narwhal and tusk: a dag-based mempool and efficient bft consensus,” in Proceedings of the Seventeenth European Conference on Computer Systems, 2022, pp. 34–50. [15] I. Doidge, R. Ramesh, N. Shrestha, and J. Tobkin, “Moonshot: Optimizing chain-based rotating leader bft via optimistic proposals,” in International Conference on Dependable Systems and Networks (DSN), 2024. [16] L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, P. Schwabe, G. Seiler, and D. Stehlé, “CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme,” IACR Transactions on Cryptographic Hardware and Embedded Systems, pp. 238–268, Feb. 2018. [17] C. Dwork, N. Lynch, and L. Stockmeyer, “Consensus in the presence of partial synchrony,” Journal of the ACM (JACM), vol. 35, no. 2, pp. 288–323, 1988. [18] S. Fundation, “Turbine - solana’s block propagation protocol solves the scalability trilemma,” 2019, accessed on Jun 8, 2026. [Online]. Available: https://solana.com/news/turbine---solana-s-block-propaga tion-protocol-solves-the-scalability-trilemma [19] R. Gelashvili, L. Kokoris-Kogias, A. Sonnino, A. Spiegelman, and Z. Xiang, “Jolteon and ditto: Network-adaptive efficient consensus with asynchronous fallback,” in International Conference on Financial Cryptography and Data Security. Springer, 2022, pp. 296–315. [20] N. Giridharan, “Autobahn artifact repository,” https://github.com/neilg iri/autobahn-artifact/tree/autobahn, [Online; accessed 10-June-2026]. [21] N. Giridharan, F. Suri-Payer, I. Abraham, L. Alvisi, and N. Crooks, “Autobahn: Seamless high speed BFT,” in Proceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles, ser. SOSP ’24. New York, NY, USA: Association for Computing Machinery, Nov. 2024, pp. 1–23. [22] P. Kuznetsov, A. Tonkikh, and Y. X. Zhang, “Revisiting Optimal Resilience of Fast Byzantine Consensus,” in Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, ser. PODC’21. New York, NY, USA: Association for Computing Machinery, Jul. 2021, pp. 343–353. [23] Monad, “Monad blockchain, raptorcast,” 2026, accessed on Jun 8, 2026. [Online]. Available: https://docs.monad.xyz/monad-arch/cons ensus/raptorcast [24] D. Moody, R. Perlner, A. Regenscheid, A. Robinson, and D. Cooper, “Transition to post-quantum cryptography standards,” National Institute of Standards and Technology, Tech. Rep., 2024. [25] National Institute of Standards and Technology, “Module-latticebased digital signature standard,” U.S. Department of Commerce, Tech. Rep. FIPS 204, 2024.

[26] ——, “Stateless hash-based digital signature standard,” U.S. Department of Commerce, Tech. Rep. FIPS 205, 2024.

A.1. Liveness

[27] [n.d.], “Google cloud platform - general-purpose machine family for compute engine.” online; accessed 12-May-2026. [Online]. Available: https://docs.cloud.google.com/compute/docs/compute-optimized-mac hines?n#c2 series

Lemma 11. If a correct party rn confirms the round-r timeout at time t, then all correct parties rn confirm it by time max(GST, t) + 2δ .

[28] NIS Cooperation Group, “A coordinated implementation roadmap for the transition to post-quantum cryptography,” European Commission, Tech. Rep., Jun. 2025, part 1, version 1.1.

Proof. Suppose a party pi rn confirms the round-r timeout at time t. This happens after receiving 2f + 1 accept messages. At least 2f + 1 − f = f + 1 of those were sent by correct parties. As such, they will be received by all other correct parties at the latest at time max(GST, t) + δ . At this moment, these parties execute the Cascade rule of the reliable notification protocol and send an accept message. Therefore, at least n − f parties will send this type of message by time max(GST, t)+δ . One message delay later, at time max(GST, t) + 2δ , all correct parties receive these messages and rn confirm the round-r timeout.

[29] RustCrypto, “ML-DSA crate documentation,” https://docs.rs/ml-dsa /latest/ml dsa/, [Online; accessed 10-June-2026]. [30] V. Shoup, “Sing a song of Simplex,” Cryptology ePrint Archive, Paper 2023/1916, https://eprint.iacr.org/2023/1916, 2023, full version of [31]. [31] ——, “Sing a Song of Simplex,” in 38th International Symposium on Distributed Computing (DISC 2024), ser. Leibniz International Proceedings in Informatics (LIPIcs), D. Alistarh, Ed., vol. 319. Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024, pp. 37:1–37:22. [32] N. Shrestha, “Sailfish github repository,” https://github.com/nibeshr estha/sailfish, [Online; accessed 02-March-2025]. [33] N. Shrestha, A. Kate, and K. Nayak, “Hydrangea: Optimistic TwoRound Partial Synchrony,” 2025. [34] N. Shrestha, R. Shrothrium, A. Kate, and K. Nayak, “Sailfish: Towards improving the latency of dag-based bft,” in 2025 IEEE Symposium on Security and Privacy (SP). IEEE, 2025. [35] N. Shrestha, Q. Yu, A. Kate, G. Losa, K. Nayak, and X. Wang, “Optimistic, Signature-Free Reliable Broadcast and Its Applications,” in Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security, ser. CCS ’25. New York, NY, USA: Association for Computing Machinery, Nov. 2025, pp. 3780–3794. [36] ——, “Optimistic, signature-free reliable broadcast and its applications,” arXiv preprint arXiv:2505.02761, 2025. [37] A. Spiegelman, B. Aurn, R. Gelashvili, and Z. Li, “Shoal: Improving dag-bft latency and robustness,” in International Conference on Financial Cryptography and Data Security, 2024. [38] A. Spiegelman, N. Giridharan, A. Sonnino, and L. Kokoris-Kogias, “Bullshark: Dag bft protocols made practical,” in Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, 2022, pp. 2705–2718. [39] A. Tonkikh, B. Arun, Z. Xiang, Z. Li, and A. Spiegelman, “Raptr: Prefix consensus for robust high-performance bft,” arXiv preprint arXiv:2504.18649, 2025. [40] L. Yang, S. J. Park, M. Alizadeh, S. Kannan, and D. Tse, “DispersedLedger: High-Throughput Byzantine Consensus on Variable Bandwidth Networks,” in 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22), 2022, pp. 493–512. [41] M. Yin, D. Malkhi, M. K. Reiter, G. G. Gueta, and I. Abraham, “Hotstuff: Bft consensus with linearity and responsiveness,” in Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019, pp. 347–356. [42] Q. Yu, G. Losa, and X. Wang, “TetraBFT: Reducing Latency of Unauthenticated, Responsive BFT Consensus,” in Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, ser. PODC ’24. New York, NY, USA: Association for Computing Machinery, Jun. 2024, pp. 257–267.

Appendix A. Deferred Security Proofs This appendix gives the proofs deferred from Section 4; statements that also appear in the main body are restated with their original numbers.

Lemma 12. If a correct party enters a round r at time t ≥ GST, then all correct parties enter round r by t + dt δ . Proof. According to the protocol, each party enters round r after, for every preceding round, either marking it safe (which follows rb-delivering its proposal) or disabling it (which follows rn-confirming its timeout). Thus, once a correct party enters round r and the totality delay dt of the reliable broadcast used and the totality delay of the reliable notification protocol have elapsed, all correct parties have entered round r. By Lemma 11 and Table 3, the totality delay of reliable broadcast (dt = 2 or dt = 4 message delays, depending on the protocol used) is always greater than or equal to the totality delay of the reliable notification protocol (2 message delays). Thus, we conclude that all correct parties enter round r by time max(GST, t)+dt δ . Lemma 13. If a correct party rb-broadcasts a proposal for round r at time t ≥ GST whose parent is round r′ , then all correct parties will have rb-delivered the proposal of round r′ and disabled all rounds r′′ such that r′ < r′′ < r by time t + dt δ . Proof. A correct leader Lr rb-broadcasts its proposal for round r upon entering this round, which requires SafeParent(r, r′ ) to hold, and hence requires Lr to have set safe[r′ ] = true (after rb-delivering the proposal of round r′ ) and to have set disabled[r′′ ] = true for all rounds r′′ such that r′ < r′′ < r. If this happens at time t ≥ GST, the totality delay of reliable broadcast and Lemma 11 guarantee that all correct parties will have rb-delivered the proposal of round r′ and rn-confirmed the timeouts of all rounds r′′ such that r′ < r′′ < r by time t + dt δ . Lemma 14. If the first correct party to enter round r does so at time t such that t ≥ GST, the leader Lr is correct, and the round timeout is larger than (dt + ds )δ , then every correct party will commit round r. Proof. All actions in the round happen after the GST, so the maximum message delay is bounded by δ . The first correct

party to enter the round does so after marking round r − 1 safe (through reliable broadcast) or disabling round r − 1 (through the reliable notification protocol). By Lemma 12, all other correct parties will enter round r at the latest one totality delay later, by time t + dt δ . By Lemma 12, at the latest at time t+dt δ , correct parties will have rb-delivered all proposals and disabled all timedout rounds for all rounds previous to r. Consequently, at the latest at this moment, the leader Lr enters the round and rbbroadcasts its proposal for round r. It can do this since it must have marked safe or disabled all rounds previous to r by this point. All correct parties will rb-deliver the proposal at the latest by time (t + dt δ) + ds δ . Additionally, for a correct party to send a ⟨commit, r⟩ message, it must rb-deliver the proposal of round r and verify that its parent is safe (so that safe[r] = true) before its round timer expires. Lemma 13 guarantees that the parent’s proposal has been rb-delivered and the intervening rounds disabled by time t + dt δ ; since the round-r proposal itself is rb-delivered by time (t + dt δ) + ds δ , every correct party marks round r safe by that time. If the timeout is strictly larger than (dt +ds )δ , no correct party will have timed out by t + (dt + ds )δ . Therefore, by this point, all correct parties will have marked round r safe, sent a ⟨commit, r⟩ message, and advanced to round r + 1. Since δ is not known, the timeout has to be specified using the known upper bound on the message delay, ∆, which results in a timeout time of (dt + ds )∆. These commit messages will experience at most one message delay. Thus, by time t+dt δ +ds δ +δ , every correct party will have received at least n−f ⟨commit, r⟩ messages, which triggers the Commit rule causing every correct party to commit round r at this time, as long as the round timeout is strictly larger than (dt + ds )δ .

is an ancestor of k . Because correct leaders are scheduled infinitely often and, by Corollary 1, correct parties keep entering higher rounds, there is, after GST, a round k ′ ≥ k whose leader is correct and which is entered for the first time after GST; by Lemma 14, every correct party commits round k ′ . Since round k was committed and k ′ ≥ k , Lemma 4 (applied to k and k ′ ) shows that k is an ancestor of k ′ , and hence so is kb ; therefore b ∈ Log(k ′ ). When a correct party commits round k ′ it sets delivered ← Log(k ′ ) whenever Log(k ′ ) is longer than its current delivered, delivering every block of Log(k ′ ) it has not delivered yet; if instead its delivered is already at least as long as Log(k ′ ), then by Lemma 4 that longer sequence is Log(k ′′ ) for a committed round k ′′ of which k ′ is an ancestor, so it contains Log(k ′ ) as a prefix. In either case, every correct party has delivered every block of Log(k ′ ), and in particular b, as claimed.

Theorem 2 (Liveness). With a round timeout larger than (dt + ds )δ , and a leader schedule that ensures that correct leaders are chosen infinitely often, the protocol guarantees that if a correct party submits infinitely many blocks, then all correct parties deliver infinitely many blocks submitted by that party.

Corollary 3 (Optimistic latency with Opt-RBC). The s optimistic latency of protocols Sopt and Sopt is 3δ if at most fo parties are faulty.

Proof. By Corollary 1, correct parties do not get stuck and keep entering higher rounds. Therefore, there will eventually exist a round r1 such that the first correct party to enter it does so after GST and the round leader is correct. Then by Lemma 14, the block of round r1 will be committed. This holds for all rounds with a correct leader after GST. Since there should be infinitely many of these, and leader rotation is fair, then every party that submits infinitely many blocks gets infinitely many of them delivered. Theorem 3 (Totality). If a correct party tob-delivers a block b, then every correct party eventually tob-delivers b. Proof. A correct party tob-delivers b only through the Commit and Deliver rules, upon committing some round k with b ∈ Log(k); that is, b is the block of some round kb that

A.1.1. Latency Bounds. Lemma 6 (Optimistic latency). If at most fo parties are faulty, Lr is correct, and it entered round r at a time t ≥ GST, all correct parties commit round r within (do + 1)δ time of its proposal. Proof. By the definition of the optimistic RBC delay and Table 3, if the leader is correct, all correct parties will rbdeliver its proposal at time t+do δ . Similarly, by Lemma 13, all correct parties will be able to mark round r safe and send a ⟨commit, r⟩ message at this time. Then, by time t+do δ+δ , all correct parties will receive ⟨commit, r⟩ messages from n − f parties and commit round r. Corollary 2 (Optimistic latency with Bracha-RBC). The optimistic latency of protocols S and S s is 4δ if at most fo parties are faulty.

Lemma 7 (Optimistic block time). The optimistic block time of Simple-IT using propose-upon-delivery pipelining is do δ if at most fo parties are faulty. Proof. Consider any two consecutive rounds r, r + 1 with correct leaders Lr , Lr+1 such that Lr makes its proposal at a time t > GST. As this is the optimistic case, Definition 8 parametrizes the delay until Lr+1 rb-delivers Lr ’s proposal as do . Following the protocol, Lr+1 will propose its next block at this moment, at time t + do δ , resulting in a block time of do δ . Corollary 4. The optimistic block time of Simple-IT variants S and Sopt is 3δ and 2δ respectively. Lemma 8. After GST, if all correct parties enter round r at the latest at time t, then all correct parties move to the next round at the latest at time t + ∆to + dt δ , where ∆to = (ds + dt )∆.

Proof. Each correct party starts its round-r timer upon entering the round (Step Enter round), so the round-r timers of all correct parties expire by time t + ∆to , and, by Step Timeout, a correct party that is still in round r when its timer expires either has already voted to commit round r or raises its round-r timeout flag at that moment. Hence, by time t+∆to , every correct party has entered round r +1, voted to commit round r, or raised its round-r timeout flag. We distinguish two cases, depending on whether some correct party sets safe[r] = true by time t + ∆to . First suppose that no correct party sets safe[r] = true by time t + ∆to . Then no correct party votes to commit round r by that time (Step Vote), and a correct party can enter round r + 1 only after disabling round r (Step Advance round). If some correct party rn confirms the round-r timeout at a time τ ≤ t + ∆to , then, by Lemma 11, all correct parties rn confirm it by time τ + 2δ , disable the round, and enter round r +1 by time t+∆to +2δ . Otherwise, no correct party enters round r + 1 by time t + ∆to , and thus every correct party raises its round-r timeout flag by then, broadcasting a vote message of the reliable notification protocol. By time t + ∆to + δ , every correct party has received vote messages from n − f parties and has broadcast an accept message, and, by time t + ∆to + 2δ , every correct party has received accept messages from n − f ≥ 2f + 1 parties, rn confirms the round-r timeout, disables the round, and enters round r + 1 (Step Advance round). Otherwise, some correct party sets safe[r] = true at some time td ≤ t + ∆to . Note that, in this case, the reliable notification protocol is not guaranteed to confirm the round-r timeout, because the correct parties that voted to commit round r never raise their timeout flags; instead, correct parties advance thanks to the Totality properties of reliable broadcast and reliable notification, as follows. Every rb-delivery and rn-confirmation through which the party above established safe[r] = true (the round-r proposal, the proposals of its chain of ancestor rounds, and the timeouts of the skipped rounds) occurred by time td ; hence, by the Totality property of reliable broadcast and Lemma 11 (recall from Lemma 12 that dt ≥ 2, so the totality delay of reliable broadcast dominates that of reliable notification), every correct party rb-delivers the same proposals and rn-confirms the same timeouts by time td + dt δ , and thus sets safe[r] = true by that time. Since, by time t + ∆to , every correct party has entered round r + 1, voted, or raised its round-r timeout flag, Step Advance round makes every correct party enter round r + 1 by time max(t + ∆to , td + dt δ) ≤ t + ∆to + dt δ . In both cases, since dt ≥ 2, all correct parties enter round r + 1 by time t + ∆to + dt δ . Corollary 5 (Eventual worst-case view duration). The eventual worst-case view duration (Definition 5) of SimpleIT is ∆to + dt δ : 5∆ + 2δ for variant S (Bracha-RBC) and 8∆ + 4δ for variant Sopt (Opt-RBC). Proof. The views of Simple-IT are its rounds, and correct parties enter rounds in increasing order, one at a time (Step Advance round); hence the earliest time t1 at which every

correct party has entered round r or higher is the time at which the last correct party enters round r. For a round with t1 ≥ GST, Lemma 8 applied with t = t1 shows that every correct party enters a round strictly greater than r by time t1 + ∆to + dt δ . The claim follows by instantiating ds and dt according to Table 3: ∆to = 5∆ and dt = 2 for Bracha-RBC, and ∆to = 8∆ and dt = 4 for Opt-RBC.

A.2. Pipelined-Proposal Version We now prove the liveness properties of the pipelinedproposal version of Simple-IT (Figure 3); as noted in Section 4, its safety analysis is unchanged from the standard version. Lemma 15. If the first correct party to enter round s does so at time t such that t ≥ GST, the leaders of rounds s, . . . , s+ k −1 are correct, and the round timeout is larger than (dt + ds )δ , then every correct party will commit round s + k − 1. Proof. Since t happens after the GST, the maximum message delay in all rounds is bounded by δ . First consider the case in which the speculative chain starting at round s has a safe parent. Then Ls either makes a normal proposal when it enters round s, or it has already made a speculative proposal whose parent is round s − 1 and round s − 1 becomes safe. In both subcases, the same timing argument as in Lemma 14 applies to round s: by time t+(dt +ds )δ , all correct parties have rb-delivered Ls ’s proposal, marked round s safe, and voted to commit it before their round-s timers expire. Since the leaders of rounds s, . . . , s + k − 1 are correct, the proposal of each subsequent round is rb-delivered by all correct parties. Moreover, each such proposal either has the previous round as a safe parent, if it was made speculatively, or is made normally upon entering the round with a safe parent chosen by the Propose rule. Inductively, all rounds s, . . . , s + k − 1 are marked safe and voted for before their timers expire. Thus all correct parties commit round s + k − 1. It remains to consider the case in which the chain starting at round s is speculative on a round below the window that does not become safe in time. The worst case is that the failed round is s − 1: a failed round q < s can cause the Disable rule to raise timeout flags only for rounds q + 1, . . . , q + k − 1, so among rounds s, . . . , s + k − 1 its cascade reaches farthest when q = s − 1, and even then reaches only up to round s+k−2. The parties that genuinely timed out in round q issue these raises as soon as they confirm q ’s timeout. After GST, reliable notification makes the corresponding timeout flags confirm within one reliablenotification latency, before the affected rounds can produce another genuine timeout. Moreover, these cascaded raises are recorded by setting aborted[·], not timed out[·], and therefore their confirmations do not trigger another cascade. Consequently, correct parties may disable and skip rounds s, . . . , s + k − 2, but this process does not reach round s + k − 1. Finally, Ls+k−1 cannot have made a speculative proposal on top of the failed chain: the Speculative propose

rule for round s + k − 1 requires safe[s − 1] = true. Thus, when Ls+k−1 enters round s + k − 1, all previous rounds have been marked safe or disabled, and Ls+k−1 makes a normal proposal. Since Ls+k−1 is correct and this happens after GST, the timing argument of Lemma 14 applies, and every correct party commits round s + k − 1.

new block is proposed every δ time. Since all leaders are correct and all rounds occur after GST, all rounds will have the same duration D (which differs depending on the underlying broadcast protocol used). Then, since a block is proposed every δ time, a new block will be committed every δ time.

Theorem 4 (Liveness). With a round timeout larger than (dt +ds )δ , and a leader schedule that ensures that sequences of k correct leaders are chosen infinitely often, the protocol guarantees that if a correct party submits infinitely many blocks, then all correct parties deliver infinitely many blocks submitted by that party.

Lemma 10. In the pipelined-proposal version of Simple-IT, after GST, if all correct parties enter round r at the latest at time t, then all correct parties move to the next round at the latest at time t + ∆to + dt δ .

Proof. By Corollary 1, correct parties do not get stuck and keep entering higher rounds. Therefore, there will eventually exist a round s1 such that the first correct party to enter it does so after GST and the leaders of rounds s1 , . . . , s1 +k−1 are correct. Then by Lemma 15, at least round s1 + k − 1 will commit its block. This holds for all sequences of k correct leaders in rounds after GST. Since there should be infinitely many of these sequences, and leader rotation is fair, then every party that submits infinitely many blocks gets infinitely many of them delivered. Theorem 5 (Totality). Under the assumptions of Theorem 4, if a correct party tob-delivers a block b, then every correct party eventually tob-delivers b. Proof. The proof of Theorem 3 carries over, with windows of k consecutive correct leaders in place of single correctleader rounds. A correct party tob-delivers b only upon committing some round r with b ∈ Log(r). Because sequences of k correct leaders are scheduled infinitely often and, by Corollary 1, correct parties keep entering higher rounds, there is, after GST, a round s ≥ r which is entered for the first time after GST and such that the leaders of rounds s, . . . , s + k − 1 are correct; by Lemma 15, every correct party commits round r′ = s + k − 1 ≥ r. Since the safety analysis carries over to the pipelined version, Lemma 4 applies to r and r′ and shows that r is an ancestor of r′ , so Log(r) is a prefix of Log(r′ ) and b ∈ Log(r′ ). The delivery argument concluding the proof of Theorem 3 then shows that every correct party delivers every block of Log(r′ ), and in particular b. Lemma 9 (Optimistic block time). The optimistic block s time of Simple-IT variants S s and Sopt is δ . Proof. Consider an infinite sequence of rounds all with correct leaders and starting in round r that start at a time t > GST. Since all leaders are correct, they follow the protocol and all their broadcasts finish and their blocks are marked as safe. When using speculative proposing, a leader broadcasts a block for its round upon receiving the proposal of the previous round leader (rule Speculative propose). This takes one message delay, so after GST a

Proof. The proof of Lemma 8 carries over, as speculative proposals change how blocks are proposed but not how rounds are exited; we only account for the two differences relevant to the argument. First, a correct party may raise its round-r timeout flag not only through Step Timeout (setting timed out[r]) but also through Step Disable (setting aborted[r]), possibly before even entering round r; since Step Advance round treats aborted[r] exactly like timed out[r], and since raising earlier only anticipates the corresponding vote message of the reliable notification protocol, all the bounds of the proof still hold. Second, Step Vote is additionally guarded by aborted[curr round] = false, which only further restricts voting. It thus remains true that, by time t + ∆to , every correct party has entered round r + 1, voted to commit round r, or raised its round-r timeout flag, and both cases of the proof of Lemma 8 apply unchanged. Corollary 6 (Eventual worst-case view duration, pipelined). The eventual worst-case view duration (Definition 5) of the pipelined-proposal version of Simple-IT is ∆to +dt δ : 5∆+2δ for variant S s (Bracha-RBC) and 8∆+4δ s (Opt-RBC). for variant Sopt Proof. Identical to the proof of Corollary 5, using Lemma 10 in place of Lemma 8.

A.3. Reliable Notification Proofs Lemma 16. Figure 4 implements a reliable notification protocol. Proof. Unanimity. If all correct parties invoke rn raise(e), all of them will send a ⟨vote, e⟩ message. Since there are at most f faulty parties, all correct parties will eventually receive such messages from n − f parties, causing them to send an ⟨accept, e⟩ message. Similarly, all correct parties will receive such messages from at least n − f ≥ 2f + 1 parties, causing them to invoke rn confirm(e). Totality. Suppose that a correct party confirms e. For this to happen, it must have received 2f + 1 ⟨accept, e⟩ messages. Among all the parties that sent them, there are at least f + 1 that are correct, meaning that the ⟨accept, e⟩ messages they sent will eventually be received by all the other participants. This will trigger all correct parties to send an ⟨accept, e⟩ message, causing all of them to receive such

messages from n − f parties, triggering the confirmation of e. Validity. Suppose a correct party confirms e. For this to happen, it must have received ⟨accept, e⟩ messages from 2f + 1 parties, meaning that at least f + 1 correct parties sent this type of message. Consider the first correct party that sent such a message. Since ⟨accept, e⟩ messages are sent after receiving ⟨accept, e⟩ messages from f + 1 parties

or ⟨vote, e⟩ messages from n − f parties, and there are at most f faulty parties, the first correct party could not have received f + 1 ⟨accept, e⟩ messages. Thus, it must have sent the message after receiving ⟨vote, e⟩ messages from n − f parties. Among those, there must be at least n − 2f correct parties, which must have invoked rn raise(e).