Optimistic Reliable Broadcast in Three Steps

Optimistic Reliable Broadcast in Three Steps Nikita Polianskii IOTA Foundation nikita.polyansky@gmail.com

arXiv:2610.05445v1 [cs.DC] 4 Oct 2026

Abstract We study the latency tradeoffs of signature-free asynchronous reliable broadcast with optimistic two-step delivery. We consider 𝑛 parties, of which at most 𝑓 are Byzantine. An optimistic fault budget 𝑏 ≤ 𝑓 guarantees two-step delivery with an honest broadcaster and at most 𝑏 faults, while correctness tolerates 𝑓 faults. We write (𝑑𝑜 , 𝑑𝑠 , 𝑑𝑡 ) for optimistic latency, honest-broadcaster latency with up to 𝑓 faults, and totality delay—the elapsed time from first to last honest delivery. For 3𝑓 + 1 ≤ 𝑛 < 4𝑓 , our first construction improves Opt-RBC’s (2, 4, 4) guarantees to (2, 3, 4), preserving its maximal optimistic budget 𝑏 ∗ = ⌊𝑛/2⌋ − 𝑓 . Thus maximal optimism is compatible with the optimal three-step good case. We prove a complementary lower bound: for 3𝑓 + 1 ≤ 𝑛 < 4𝑓 , every deterministic reliable broadcast protocol in our asynchronous model with two-step optimistic budget 𝑏 ≥ 𝑛 − 3𝑓 has totality delay at least three, even when the broadcaster is honest. Our second construction achieves (2, 3, 3), matching this lower bound at maximal optimism when 𝑓 ≥ 2 and ⌈(10𝑓 − 3)/3⌉ ≤ 𝑛 < 4𝑓 . Both constructions use quadratic messages and tolerate adaptive corruption. In the matching range, maximal optimism therefore costs exactly one totality step relative to Bracha’s (3, 3, 2), without increasing good-case latency.

1

Introduction

Reliable broadcast lets a designated broadcaster send a value to 𝑛 parties, up to 𝑓 of which may be Byzantine. Honest parties must agree on the delivered value, must deliver an honest broadcaster’s value, and must all deliver if any one of them does. The last property, totality, is what makes a locally delivered value safe to act on inside a larger protocol. Its latency, the time by which the last honest party can lag behind the first, bounds how long a DAG-based consensus protocol must wait before a delivered block is usable at every party [17]. We measure latency in steps, where one step is the actual network delay bound between honest parties, and write (𝑑𝑜 , 𝑑𝑠 , 𝑑𝑡 ) for a protocol’s optimistic latency, good-case latency, and totality delay (Section 2). Bracha’s signature-free protocol is (3, 3, 2): it delivers an honest broadcaster’s value in three steps, and once an honest party delivers, every honest party delivers within two further steps [5, 20]. Two-step delivery under all 𝑓 faults requires 𝑛 ≥ 4𝑓 without signatures [2, Theorem 4]. Shrestha et al. therefore relax the requirement: two-step delivery is required only in executions in which at most 𝑏 parties are actually Byzantine, for an optimistic budget 𝑏 ≤ 𝑓 [17]. For 3𝑓 + 1 ≤ 𝑛 < 4𝑓 the largest feasible budget is 𝑏 ∗ = ⌊𝑛/2⌋ − 𝑓 . Their protocol, Opt-RBC,1 attains it, but at a price: it is (2, 4, 4), so good-case latency rises from three steps to four and totality delay from two to four. The superseded v2 claimed two-step optimism 1We use the corrected arXiv v4 of May 2026, which adds an ack layer to fix a termination

issue in the earlier version; its guarantees supersede those of the CCS 2025 version.

Table 1: Latency in steps for 3𝑓 +1 ≤ 𝑛 < 4𝑓 , with 𝑏 ∗ = ⌊𝑛/2⌋ − 𝑓 and 𝑠 = 𝑛 − 3𝑓 − 1. All protocols are signature-free with 𝑂 (𝑛 2 ) messages; types count the proposal as well as subsequent message types. Protocol

Budget 𝑏

Types 𝑑𝑜 𝑑𝑠 𝑑𝑡

Bracha – Opt-RBC 𝑏∗ Bracha + fast echo ⌊𝑠/2⌋ + 1 Confirm/ack 𝑏∗ Paired witness min{𝑏 ∗ , 2𝑠 + 3}

3 5 3 6 6

3 2 2 2 2

3 4 3 3 3

2 4 3 4 3

Lower bounds

– 2𝑎 3𝑏 3𝑐

Ref. [5] [17] App. B.1 App. E.1 Sec. 4

𝑎 Any budget (Lemma A.1). 𝑏 Under all 𝑓 faults [2, Theorem 4]. 𝑐 Deterministic

protocols with two-step budget 𝑏 ≥ 𝑛 − 3𝑓 (Theorem 1.1), witnessed with an honest broadcaster. The fast-echo baseline has Byzantine-broadcaster totality at most two (Proposition B.1). Confirm/ack and paired witnesses are our constructions; paired witnesses require 𝑓 ≥ 2.

with a three-step good case [18]. Confirm/ack establishes those two latency guarantees while retaining the ack layer of the corrected protocol. Opt-RBC’s reported bad-case latency five is measured from invocation, whereas totality four follows the elapsed convention of Yu et al. [20]. We ask whether this price is necessary: can maximal optimism coexist with Bracha’s good-case latency, and with his totality delay? Results. The confirm/ack protocol improves Opt-RBC’s (2, 4, 4) to (2, 3, 4) at the same maximal budget 𝑏 ∗ throughout 3𝑓 + 1 ≤ 𝑛 < 4𝑓 , with 𝑂 (𝑛 2 ) messages. Thus two-step optimism need not increase the optimal three-step good case. Paired witnesses achieve (2, 3, 3) over the range below. For 𝑓 ≥ 2 and 3𝑓 + 1 ≤ 𝑛 < 4𝑓 , our lower bound rules out totality below three whenever 𝑏 ≥ 𝑛 − 3𝑓 , in the deterministic model of Section 2. At 𝑛 = 3𝑓 + 1, even one-fault two-step optimism therefore costs an extra totality step. Our quadratic-message (2, 3, 3) protocol attains three at maximal optimism whenever 𝑛 ≥ ⌈(10𝑓 − 3)/3⌉, including the entire interval for 2 ≤ 𝑓 ≤ 6. Throughout this matching range, maximal optimism costs exactly one totality step and no good-case step relative to Bracha. Table 1 separates the construction’s budget from the lower bound’s premise. Full-range construction. Confirm/ack retains Opt-RBC’s fast echo delivery and vote–ack–ready recovery. It adds a confirm sent on a sufficiently large echo quorum, delivery on a confirm quorum, and an ack trigger on 𝑓 + 1 confirms. With an honest broadcaster, echoes arrive by step two and confirms by step three. The ack layer reconciles recovery from the echo and confirm delivery rules when the broadcaster equivocates. This gives (2, 3, 4) at budget 𝑏 ∗ throughout the interval; Theorem 5.2 and Appendix E give the thresholds and proof. We next ask whether its totality delay can be reduced.

Nikita Polianskii

Theorem 1.1 (Totality lower bound). Let 3𝑓 + 1 ≤ 𝑛 < 4𝑓 and 𝑛 − 3𝑓 ≤ 𝑏 ≤ ⌊𝑛/2⌋ − 𝑓 . In the deterministic model specified in Section 2, every reliable broadcast protocol with two-step honestbroadcaster delivery under at most 𝑏 faults has totality delay at least three. This holds already over executions with an honest broadcaster and at most 𝑓 faulty non-broadcasters. For 𝑛 ≤ 4𝑓 − 2, the same bound holds if only non-broadcasters are required to deliver and the totality clock counts only their deliveries. The theorem allows arbitrary messages, timers, and continued communication after delivery, and assumes neither threshold rules, nor bounded message complexity, nor three-step good-case latency. It does not cover randomized protocols or protocols supplied with the actual network delay bound. An early delivery within the source group imposes a totality deadline while some recipients are still waiting for messages. When that group contains an ordinary recipient, its delivery suffices; only the boundary 𝑛 = 4𝑓 − 1 needs the source-inclusive convention in this proof. The paired-witness construction attains this bound over the range below. Write 𝑠 = 𝑛 − 3𝑓 − 1 for the number of parties beyond minimum resilience. Theorem 1.2 (Paired-witness broadcast). Let 𝑓 ≥ 2, 𝑛 = 3𝑓 + 1 + 𝑠 with 𝑠 ≥ 0, and 1 ≤ 𝑏 ≤ min{𝑓 , ⌊𝑛/2⌋ − 𝑓 , 2𝑠 + 3}.

(1)

There is a signature-free asynchronous reliable broadcast protocol against adaptive corruption of at most 𝑓 parties with optimistic latency two under at most 𝑏 faults, good-case latency three, and totality delay at most three. At most 5(𝑛 − 1) 2 + 2(𝑛 − 1) messages are sent while their authors are uncorrupted, including after delivery, and local work is polynomial. For 𝑛 ≥ 4𝑓 it supports 𝑏 = 𝑓 . The full-fault specialization at 𝑛 ≥ 4𝑓 recovers the elapsedtotality guarantee already provided by Abraham, Ren, and Xiang’s protocol [2, Theorem 3]. Corollary 1.3 (Matching totality bounds). For 𝑓 ≥ 2 and 3𝑓 + 1 ≤ 𝑛 < 4𝑓 with 𝑏 ∗ ≤ 2𝑠 + 3, equivalently 𝑛 ≥ ⌈(10𝑓 − 3)/3⌉, the smallest totality delay of a deterministic protocol in the model of Section 2 with maximal two-step optimism is exactly three, and a quadratic-message protocol attains it together with the optimal good-case latency three. For every 𝑓 ≥ 2, at 𝑛 = 3𝑓 + 1 totality three is optimal for 1 ≤ 𝑏 ≤ min{3, 𝑏 ∗ }. The proof is at the end of Section 4. At minimum resilience the bounds match for every supported budget, and reach maximal optimism for 2 ≤ 𝑓 ≤ 6. The 𝑏 = 1 case, including (𝑛, 𝑓 ) = (7, 2), already follows from Bracha with fast echo delivery (Proposition B.1); paired witnesses extend the three-totality guarantee to budgets two and three at minimum resilience. The first missing maximal-budget case is (𝑛, 𝑓 , 𝑏 ∗ ) = (22, 7, 4), whereas adding one party gives the matching case (23, 7, 4). At the missing case the current rules actually lose totality; Proposition B.2 gives the general counterexecution beyond their budget range. In general the sufficient surplus is 𝑠 ≥ max{0, ⌈(𝑓 − 6)/3⌉}. The lower bound holds throughout 3𝑓 + 1 ≤ 𝑛 < 4𝑓 at budgets 𝑏 ≥ 𝑛 − 3𝑓 ; maximal optimism with three-step totality at minimum resilience for arbitrary 𝑓 remains open. The bound concerns honest-broadcaster delivery spread: it forces 𝑑𝑡H = 3 when 𝑑𝑠 = 3, but does not rule out 𝑑𝑡B = 2. At

𝑛 = 4𝑓 − 1, including (𝑛, 𝑓 ) = (7, 2), the lower bound uses the source-inclusive delivery convention. Techniques. The lower bound builds on the four-execution indistinguishability arguments of Abraham, Ren, and Xiang [2, Theorem 4] and of Shrestha et al. [17, Theorem 8]. The step from an early fast delivery to a deadline for other parties also appears in Abraham, Ren, and Xiang’s argument [2, Theorem 7]: their first bridge preserves a two-round delivery and invokes the assumed bad-case bound. Our elapsed-time argument preserves an early delivery under nonuniform larger delays, keeps the resulting deadline fixed across the required history comparisons, and uses eventual totality alone in the final bridges. A source group containing ordinary recipients is honest in the fast and forcing executions but faulty in the final bridges. It generalizes the padding set 𝐸, of size at most one, in Shrestha et al.’s proof of Theorem 8, which is honest in their two honest-broadcaster worlds and faulty together with the broadcaster in the other two [17, Section 4]. This reduces the fast executions’ fault count to 𝑛 − 3𝑓 , giving the smaller-budget bound. The protocol must reconcile recovery from an echo delivery with recovery from a confirm delivery. Votes propagate the former, but using confirms alone for the latter can produce conflicting ready messages. Our witness instead requires an echo and a confirm from each of the same authors. These paired observations occupy immutable echo slots: a witness quorum forces enough honest parties to be unable to vote for an opposite value, even earlier in the execution. This exclusion lets both recovery paths trigger ready directly, removing the acknowledgment round while preserving agreement (Section 4). Consequences for BFT consensus. In protocols that use reliable broadcast to disseminate blocks, good-case latency controls how quickly honest proposals become available, while totality controls how quickly other honest parties catch up once one party delivers. When the same RBC-delivered evidence suffices for round advancement at every party, this catch-up bound also limits roundentry skew. Our improvements can therefore shorten both proposal dissemination and the synchronization margins used for recovery. Section 5.1 instantiates these consequences for Sailfish++ and Simple-IT [17, 20]. Supporting results. For large values, a coded realization preserves the paired-witness protocol’s (2, 3, 3) guarantees and supported optimistic budgets with 𝑂 (𝑛𝐿 + 𝜅𝑛 2 log 𝑛) bits in every execution, where 𝐿 is the value length and 𝜅 is the hash length. It uses collisionresistant hashing as its only cryptographic assumption and retains security against adaptive corruption (Section 5). We also determine how the totality delay of our confirm/ack construction depends on the actual number of faults at 𝑛 = 3𝑓 + 1. Its exact worst-case delay is one step with no faults, two with one fault, three with two through 𝑓 − 𝑏 ∗ + 1 faults, and four above that threshold, omitting empty ranges (Proposition E.14). Thus our construction needs fourstep totality only when more than roughly half the fault tolerance is used. Organization. Section 2 fixes the model and the latency conventions. Section 3 proves the lower bound, with the complete joint

Optimistic Reliable Broadcast in Three Steps

schedule in Appendix A. Section 4 gives the paired-witness protocol and its proofs. Section 5 states the applications and extensions, Section 6 discusses related work, and Section 7 lists open problems.

2

Model and definitions

Parties and faults. There are 𝑛 ≥ 3𝑓 +1 parties, one of which is the designated broadcaster. An adaptive adversary may corrupt parties during the execution, at most 𝑓 in total; corruption is permanent, and a corrupted party may deviate arbitrarily. A party is honest if it is never corrupted. Validity assumes an honest broadcaster; agreement, totality, and all latency guarantees concern honest parties. If the broadcaster is Byzantine, at most 𝑓 − 1 of the 𝑛 − 1 non-broadcasters are, and fixing the eventual corrupted set gives the quorum arguments below. Inputs and initialization. The value domain V has at least two elements. Only the broadcaster initially knows its input. All other parties have public, input-independent initial states. Each instance starts without private correlated setup or transferable authentication from earlier instances. Channels. Parties are connected by pairwise authenticated channels: a receiver knows which party sent each message, and a Byzantine party cannot send messages in the name of another party. Every message sent between honest parties is eventually received. Channels need not preserve order. Authentication is not transferable: a party cannot prove to a third party what it received. These channels are the only authentication resource; no signatures or additional setup are provided. Messages. In our constructions, every message carries the instance identifier, a message type, and a value from a domain V with a fixed encoding of at most 𝐵 bits; a party ignores messages outside this format. A party sends each message type at most once per instance. When it does, it sends the message to all parties and counts its own message immediately if it is itself an eligible sender of that type. A receiver ignores a message whose type its sender is not eligible to send. For each message type and each eligible author, a receiver keeps a slot: a cell that is initially empty, is filled by the first message of that type it receives from that author, and is never changed afterwards; later messages of the same type from the same author are ignored. Consequently every quorum below is a set of distinct parties with one message each. A Byzantine party may appear in quorums for different values at different receivers, but cannot take the place of another party. Processing. Local processing is finite and instantaneous. Activity is locally finite: a party has finitely many local events in any bounded time interval. A party processes received messages one at a time and applies every rule that becomes enabled. Delivering a value does not stop a party from sending its remaining messages. Agreement, validity, and totality need only eventual receipt of messages and fair processing. Our guarantees do not include local termination at delivery: a party must retain the instance and process events that can enable its remaining one-shot sends. After it has delivered and sent every type for which it is eligible, it may discard the instance. An unsent type need not ever become enabled, so we give no bounded-time stopping guarantee after delivery.

Communication. Communication bounds count every message or bit that any party sends while it is uncorrupted, including messages sent after delivery and in executions in which no party delivers. Traffic sent after corruption is not charged. Definition 2.1 (Reliable broadcast). The broadcaster is invoked with a value 𝑣 ∈ V. Each honest party delivers at most one value. A protocol is a reliable broadcast protocol if every execution satisfies the following. Validity. If the broadcaster is honest, every honest party eventually delivers the broadcaster’s value, and no honest party delivers another value. Agreement. No two honest parties deliver different values. Totality. If an honest party delivers a value, every honest party eventually delivers a value. Definition 2.2 (Latency). For latency statements only, let 𝛿 > 0 be an actual network delay bound: every message between honest parties in the execution is received within 𝛿 time. One step is 𝛿 time. The protocol is not given 𝛿; its code and initial states do not depend on it. A bound of 𝑑 steps must hold for the same protocol for every 𝛿 > 0 and every execution satisfying that honest-link bound. We reserve Δ for the known upper bound that holds after stabilization in the consensus applications. Correctness of the broadcast protocols itself requires only eventual receipt. The good-case latency is the largest time from an honest broadcaster’s invocation until every honest party has delivered, over all executions with at most 𝑓 Byzantine parties [2]. The optimistic good-case latency with budget 𝑏 is the same quantity over executions with at most 𝑏 Byzantine parties [17]. The totality delay is the supremum, over all executions with any broadcaster, of the time between the first delivery by an honest party and the last [20, Definition 11]. We write (𝑑𝑜 , 𝑑𝑠 , 𝑑𝑡 ) for these bounds in steps, in the order optimistic, good-case, and totality. A totality lower bound of three means that every bound 𝐷 < 3 is violated by some execution; the supremum need not be attained by one execution. Write 𝑑𝑡H and 𝑑𝑡B for the same totality supremum restricted to honest and Byzantine broadcasters, respectively. Then 𝑑𝑡 = max{𝑑𝑡H, 𝑑𝑡B } and 𝑑𝑡H ≤ 𝑑𝑠 : with an honest broadcaster, every delivery occurs between invocation and the good-case deadline. Our lower bound concerns 𝑑𝑡H , and hence also 𝑑𝑡 ; it does not lowerbound 𝑑𝑡B . For protocols with 𝑑𝑠 = 3 it makes this elementary honest-broadcaster bound tight under the stated optimism premise. Latency conventions. Our triples always use elapsed totality as their third entry. Abraham, Ren, and Xiang report three good-case rounds and four bad-case rounds for Bracha, charging one extra round for totality [2, Definition 5]. Shrestha et al. report bad-case latency five measured from invocation, given that some honest party delivered within the good-case latency [17, Definition 6]; with a Byzantine broadcaster there may be no delivery at all, so we make no claim about the time from invocation in that case. Following Yu et al. [20, Table 3] we report elapsed totality delay: two for Bracha and four for Opt-RBC. In a nonuniform-delay execution, one party can receive a ready quorum early while the honest readies in that quorum take a full step to reach the others; their newly triggered readies can take a second step. Thus an early first delivery does not turn Bracha’s elapsed totality bound into one step. We use the

Nikita Polianskii

𝑓 −𝑠 −1

elapsed bounds directly, without assuming a general conversion from round-based bounds. Table 1 uses this convention. Scope of the lower bound. The lower bound concerns deterministic protocols in the model above, with latency measured against the unknown actual network delay bound. The default interface requires the honest broadcaster to deliver, and its delivery can start the totality clock. A party’s complete timed history is the timestamped sequence of its receipts, with sender identity and content, its timer events, state transitions, sends, and deliveries; its restriction to [0, 𝜏) is its history before 𝜏. All parties start the instance at time 0 and can read real time; this only strengthens the protocols quantified over. Arbitrary recipient-specific packets, repeated sends, reactive timers, and continued service after delivery are allowed. The one-shot conventions above restrict our constructions, not the protocols quantified over in the lower bound. The lower bound makes no claim for randomized protocols or for protocols supplied with the actual network delay bound. Theorem 1.1 additionally covers a recipient-only interface when 𝑛 ≤ 4𝑓 − 2: require validity, agreement, totality, and optimistic delivery for all honest non-broadcasters, and measure the first-to-last delivery gap only over them. The broadcaster remains one of the 𝑛 communicating parties and counts towards 𝑓 .

3

The totality lower bound

We prove Theorem 1.1 for arbitrary deterministic protocols in the model of Section 2, and also prove the stated extension in which only non-broadcasters must deliver. Denote the broadcaster by 0. All fault sets in the proof are static, so the bound also applies to protocols that tolerate adaptive corruption. Proof plan. The six executions serve three purposes. Fast executions force an honest party to deliver early. Forcing executions preserve that early delivery while delaying other parties, so a hypothetical bound 𝐷 < 3 imposes a deadline on those parties. Bridge executions inherit opposite deliveries but give their common honest parties identical histories forever, contradicting agreement through eventual totality. Only the forcing executions use the numeric deadline; the bridges use no latency bound. We now construct the histories that make these transfers possible. Partition and executions. Write 𝑠 = 𝑛 − 3𝑓 − 1, so 0 ≤ 𝑠 ≤ 𝑓 − 2 and 𝑠 + 1 ≤ 𝑏. Partition all parties into a source group S containing 0, two endpoint groups 𝐸𝐴 , 𝐸𝐵 , and two common groups 𝐾𝐴 , 𝐾𝐵 with |S| = 𝑓 − 𝑠 − 1,

|𝐸𝐴 | = |𝐸𝐵 | = 𝑠 + 1,

|𝐾𝐴 | = |𝐾𝐵 | = 𝑓 .

All five groups are nonempty and their sizes sum to 𝑛. Only 0 initially knows the input; S \ {0} consists of ordinary recipients with input-independent initial states. Choose an anchor ℎ ∈ S \ {0} if |S| ≥ 2; otherwise choose ℎ = 0. Only this last case, 𝑛 = 4𝑓 − 1, requires the broadcaster to deliver. Fix distinct inputs 𝐴, 𝐵. Table 3 in Appendix A lists six executions: two fast executions 𝐹𝐴 , 𝐹𝐵 forcing early anchor delivery; two honest-broadcaster forcing executions 𝑋𝐴 , 𝑋𝐵 ; and two Byzantine-broadcaster bridges 𝑊𝐴 ,𝑊𝐵 . Their faulty sets are 𝐸𝐵 , 𝐸𝐴 , 𝐾𝐵 , 𝐾𝐴 , S ∪ 𝐸𝐵 , S ∪ 𝐸𝐴 , respectively. Thus each fast execution has 𝑠 + 1 ≤ 𝑏 faults, and each forcing execution and bridge has exactly 𝑓 . The extra members of S are honest in the

S∋0 copy of 𝑋𝐴 𝑋𝐴 𝐸𝐴

𝑋𝐵 𝜂

𝐾𝐴

𝐾𝐵

𝐸𝐵

𝜂 𝑠 +1

𝑓 𝑓 copy of 𝑊𝐵 delay 𝐽 late 𝐸𝐵 of 𝑋𝐴

𝑠 +1

endpoint cut anchor delivers

late receipts

𝜀 2𝜀

𝜂

common forced delivery cut 2𝜂

𝐻

long-link delay 𝐽 = 4𝜂

3𝜂

Figure 1: Top: the bridge 𝑊𝐴 ; shaded parties are Byzantine. The members of S copy their 𝑋𝐴 streams towards the 𝐴 side and their 𝑋𝐵 streams towards 𝐾𝐵 . Only 0 ∈ S starts with an input. The Byzantine 𝐸𝐵 copies the stream of honest 𝐸𝐵 in 𝑊𝐵 towards the common groups, so its stream to 𝐾𝐴 inherits delay 𝐽 , and copies the late group’s stream of 𝑋𝐴 towards 𝐸𝐴 (dashed). Arrow delays apply to noninitial interparty packets: honest 𝐸𝐴 sends to 𝐾𝐵 with delay 𝐽 , and other honest links have delay 𝜂. Initial non-broadcaster packets arrive at 𝜀. 𝑊𝐵 is the mirror image. Bottom: the three time scales and the deadlines of the proof, with 2𝜀 < 𝜂 and 𝐻 = 2𝜀 + 𝐷𝜂 < 3𝜂.

fast and forcing executions but Byzantine in both bridges. Figure 1 shows 𝑊𝐴 . Three terms recur. The stream of a party 𝑞 to a party 𝑝 in an execution is the timed sequence of packets 𝑞 sends to 𝑝, with their arrival times; a Byzantine party copies a stream of another execution when it sends the same packets under its own identity with the same arrival times, which nontransferable authentication permits. An initial packet is one sent during zero-time initialization, before any external receipt. Non-broadcasters’ initial states, and hence their initial packets, are input-independent. All scheduled link delays below concern interparty packets; self-messages are local events. Complete timed histories are as defined in Section 2. Three scales, one elapsed deadline. Suppose a constant 𝐷 < 3 bounds totality delay in every honest-broadcaster execution with at most 𝑓 faulty non-broadcasters. Choose 𝜀, 𝜂 > 0 with 2𝜀 < 𝜂,

𝐻 := 2𝜀 + 𝐷𝜂 < 3𝜂,

𝐽 := 4𝜂.

The second condition holds once 𝜀 < (3 − 𝐷)𝜂/2. The protocol’s code and initial states are independent of the actual network delay bound (Definition 2.2). Its initialization is therefore fixed as we vary 𝜀 and 𝜂. We may take 𝜂 small enough that 3𝜂 precedes every positive expiration of a timer set during initialization. There are finitely many such timers by finite initialization and locally finite activity; if there are none, this condition is vacuous. For this cut, the noninitial packets in copied endpoint streams must reach the opposite common group no earlier than 2𝜂; the initial packets are matched separately. Thus any 𝐽 ≥ 2𝜂 suffices; 𝐽 = 4𝜂 keeps the deadlines distinct.

Optimistic Reliable Broadcast in Three Steps

In the fast executions every interparty message delay is 𝜀, and the Byzantine endpoint group sends only the initial packets its members would send and is then silent. Two-step optimistic delivery makes the honest anchor ℎ deliver 𝐴 in 𝐹𝐴 and 𝐵 in 𝐹𝐵 by 2𝜀. In 𝑋𝐴 the honest group 𝐸𝐵 , the late group, receives every initial interparty packet at time 𝜂, including on links within 𝐸𝐵 ; all other initial packets arrive at 𝜀; all later honest messages take 𝜂, except that messages sent to ℎ by time 𝜀 arrive with delay 𝜀 (the anchor exception). The Byzantine 𝐾𝐵 replays its 𝐹𝐴 packets to ℎ for sends through 𝜀 and otherwise copies the stream of honest 𝐾𝐵 in 𝑊𝐴 . Through time 𝜀 each party in S ∪ 𝐸𝐴 ∪ 𝐾𝐴 has received only initial interparty packets, exactly as in 𝐹𝐴 , so it sends the same packets, and the exception delivers them to ℎ by 2𝜀 as in 𝐹𝐴 ; any interparty packet sent after 𝜀 reaches ℎ after 2𝜀 in both executions, and the late group sends nothing noninitial before 𝜂 > 2𝜀. This includes source 0’s sends to ℎ: its input and its initial receipts match the seed. Hence ℎ’s history through 2𝜀 is the same in 𝑋𝐴 as in 𝐹𝐴 , and it delivers 𝐴 by 2𝜀 in 𝑋𝐴 as well. All honest delays in 𝑋𝐴 are at most 𝜂, the totality clock has started no later than ℎ’s delivery, and validity fixes the value, so every member of 𝐸𝐴 delivers 𝐴 by 2𝜀 + 𝐷𝜂 = 𝐻 . Symmetrically, 𝑋𝐵 delays 𝐸𝐴 , has 𝐾𝐴 Byzantine, and forces every member of 𝐸𝐵 to deliver 𝐵 by 𝐻 . In the bridges, initial non-broadcaster packets arrive at 𝜀. Noninitial honest interparty packets take 𝜂, except that the honest endpoint group sends to the opposite common group with delay 𝐽 . In both bridges every Byzantine member of S copies its own 𝑋𝐴 stream towards 𝐸𝐴 ∪ 𝐾𝐴 and its own 𝑋𝐵 stream towards 𝐸𝐵 ∪ 𝐾𝐵 . The Byzantine endpoint group copies the stream of its honest counterpart in the other bridge towards 𝐾𝐴 ∪ 𝐾𝐵 , and copies the late group’s stream of the forcing execution towards the opposite endpoint group (Figure 1). Its copied stream to the opposite common group therefore inherits delay 𝐽 and is silent before 𝐽 apart from initial packets, matching the late group’s silence in the forcing execution. The four executions 𝑋𝐴 , 𝑋𝐵 ,𝑊𝐴 ,𝑊𝐵 are constructed jointly by increasing time: every Byzantine packet copies an honest packet of another execution that was sent at least 𝜀 before its arrival, so at each instant honest processing in all four executions is determined before the copies are formed (Appendix A). Lemma 3.1 (Causal cut). Party by party, the complete timed histories satisfy 𝑋𝐴 |𝐾𝐴 = 𝑊𝐴 |𝐾𝐴 before 2𝜂,

𝑋𝐴 | 𝐸𝐴 = 𝑊𝐴 | 𝐸𝐴 before 3𝜂,

𝑋𝐵 |𝐾𝐵 = 𝑊𝐵 |𝐾𝐵 before 2𝜂,

𝑋𝐵 | 𝐸𝐵 = 𝑊𝐵 | 𝐸𝐵 before 3𝜂.

Proof sketch. Compare, sender by sender, the packets a member of 𝐾𝐴 receives before 2𝜂 in 𝑋𝐴 and in 𝑊𝐴 . From 𝐸𝐵 : in 𝑋𝐴 the late group receives nothing before 𝜂 and no initial timer fires before 3𝜂, so its first noninitial packet reaches 𝐾𝐴 no earlier than 2𝜂; in 𝑊𝐴 the copied stream is silent before 𝐽 apart from initial packets, which agree. From S and from 𝐾𝐵 : copied explicitly, from 𝑋𝐴 into 𝑊𝐴 by the Byzantine members of S and from 𝑊𝐴 into 𝑋𝐴 by the Byzantine 𝐾𝐵 . From 𝐸𝐴 and from within 𝐾𝐴 : a packet arriving before 2𝜂 was sent before 𝜂, from a history strictly earlier in the induction, which matches. Now compare the packets a member of 𝐸𝐴 receives before 3𝜂. From S, 𝐸𝐵 , and 𝐾𝐵 : copied explicitly. From 𝐾𝐴 : a packet arriving before 3𝜂 was sent before 2𝜂, inside the interval just established. From within 𝐸𝐴 : sent from a strictly earlier

matching history. Every nonlocal dependency is on a strictly earlier event, so the simultaneous induction over both cuts is well founded. The 𝐵 side is symmetric. Appendix A carries out the induction, including initialization traffic, reactive timers, and messages sent after delivery. □ Lemma 3.2 (Common indistinguishability). Every party in 𝐾𝐴 ∪ 𝐾𝐵 has the same complete timed history in 𝑊𝐴 and in 𝑊𝐵 , for all time. Proof sketch. Sender by sender: each member of S sends the same streams to the common groups in both bridges; each endpoint identity is honest in one bridge and an exact copy of that honest stream in the other; and common-to-common packets have identical schedules and, by induction on time, identical contents. The private 𝐸𝐴 –𝐸𝐵 streams differ, but each such channel has a Byzantine party at one end in each bridge, so no honest channel obligation is violated (Appendix A). □ Since 𝐻 < 3𝜂, Lemma 3.1 transfers the forced deliveries: 𝑊𝐴 contains an honest delivery of 𝐴 by 𝐸𝐴 , and 𝑊𝐵 an honest delivery of 𝐵 by 𝐸𝐵 . Honest delays in the bridges are at most 𝐽 , so both are fair asynchronous executions, in which agreement and eventual totality hold although the broadcaster is Byzantine and the hypothesis 𝐷 < 3 says nothing. Totality forces each party in 𝐾𝐴 ∪ 𝐾𝐵 to deliver in both bridges, agreement forces 𝐴 in 𝑊𝐴 and 𝐵 in 𝑊𝐵 , and Lemma 3.2 makes this impossible for a deterministic party. The numeric bound 𝐷 was used only in the honest-broadcaster executions 𝑋𝐴 , 𝑋𝐵 . This proves Theorem 1.1. Scope. At 𝑛 = 3𝑓 + 1 each endpoint is a singleton and |S| = 𝑓 − 1, so the proof needs only one optimistic fault, for every 𝑓 ≥ 2. At 𝑛 = 4𝑓 , S would be empty, although it must contain the broadcaster. More generally, this construction needs 𝑛 ≤ 3𝑓 + 𝑏: its common groups have total size at most 2𝑓 ; S ∪ 𝐸𝐴 is faulty in 𝑊𝐵 , so |S| + |𝐸𝐴 | ≤ 𝑓 ; and 𝐸𝐵 is faulty in 𝐹𝐴 , so |𝐸𝐵 | ≤ 𝑏. This is a limit of the partition, not an impossibility of proving a stronger bound for 𝑏 < 𝑛 − 3𝑓 .

4

Three-step totality with paired witnesses

Fix 𝑓 ≥ 2, 𝑛 = 3𝑓 + 1 + 𝑠, and a budget 𝑏 in the range (1), and let 𝑁 = 𝑛 − 1 = 3𝑓 + 𝑠 be the number of non-broadcasters. Only non-broadcasters send echoes, votes, confirms, and witnesses, and receivers ignore such messages from the broadcaster; every party, including the broadcaster, can send ready and deliver. When the broadcaster is Byzantine we write 𝑡 ≤ 𝑓 −1 for the number of Byzantine non-broadcasters, so that 𝑡 +1 ≤ 𝑓 parties are corrupted in total. Algorithm 1 is the complete protocol and Figure 2 in Appendix B shows its message flow. The thresholds are 𝑄 = 𝑁 − 𝑏 = 3𝑓 + 𝑠 − 𝑏,

𝐶 = 𝑁 − 𝑓 = 2𝑓 + 𝑠,

𝑀 = 𝑄 − 𝑓 + 1 = 2𝑓 + 𝑠 − 𝑏 + 1,

𝑃 = 𝐶 − 𝑓 + 1 = 𝑓 + 𝑠 + 1,

𝑅 = 𝑁 − 𝑓 + 1 = 2𝑓 + 𝑠 + 1,

𝑅w = 2𝑓 − 1,

(2) and Table 4 in Appendix B records the role of each. They count non-broadcasters, of whom at most 𝑡 are Byzantine. The ready thresholds 𝑓 + 1 and 2𝑓 + 1 count all parties, of whom at most 𝑓 are

Nikita Polianskii

Algorithm 1: Paired-witness broadcast; thresholds in (2). Broadcaster with input 𝑣: multicast ⟨propose, 𝑣⟩. Each non-broadcaster: On ⟨propose, 𝑣⟩ from the broadcaster, multicast ⟨echo, 𝑣⟩. On 𝑀 echoes of 𝑣, multicast ⟨vote, 𝑣⟩. On 𝐶 echoes of 𝑣, and having itself echoed 𝑣 (the own-echo guard), multicast ⟨confirm, 𝑣⟩. On an echo and a confirm of 𝑣 from each of the same 𝑃 authors, multicast ⟨witness, 𝑣⟩. Every party: On 𝑅 votes, or 𝑅w witnesses, or 𝑓 + 1 readies of 𝑣, multicast ⟨ready, 𝑣⟩. On 𝑄 echoes, or 𝐶 confirms, or 2𝑓 + 1 readies of 𝑣, deliver 𝑣. All multicasts and delivery are one-shot across values. Continue processing and sending after delivery.

Byzantine: 𝑓 +1 readies contain an honest one, and the 𝑛−𝑓 ≥ 2𝑓 +1 honest parties can always fill a ready delivery quorum. Slots (Section 2) are never overwritten: once an echo slot at an honest party holds 𝑣, it never held and will never hold another value. The witness rule counts paired authors, identities whose echo slot and confirm slot at the receiver both hold 𝑣; a claim by another party to have seen such a pair does not count. The own-echo guard applies only to confirms. It makes the honest confirmers behind a confirm delivery paired authors at every honest party, which drives the witness path; votes and witnesses carry no such guard, so a party that echoed another value can still help recovery. A ready sent on 𝑅 votes or on 𝑅w witnesses is a ready origin; one sent on 𝑓 + 1 readies is a relay. Deliveries on 𝑄 echoes or on 𝐶 confirms are delivery origins; a delivery on 2𝑓 + 1 readies contains an honest ready. Design rationale. After an echo delivery, 𝑀 honest echoes reach everyone and drive the vote/ready recovery path. After a confirm delivery, 𝑃 honest confirms reach everyone. Letting these 𝑃 confirms directly trigger ready is unsafe: for admissible 𝑏 ≥ 𝑠 + 2, an 𝑅-vote quorum for one value can coexist with 𝑃 confirms for another (Appendix B). Opt-RBC and our confirm/ack protocol reconcile the paths through an acknowledgment round. Paired witnesses instead bind each confirm to its author’s echo; Lemma 4.1 proves that a witness quorum excludes an opposite vote quorum, allowing both paths to trigger ready directly.

4.1

Compatibility of the recovery paths

Let the broadcaster be Byzantine, with 𝑡 ≤ 𝑓 − 1 Byzantine nonbroadcasters. For adaptive faults, take the eventual corrupted set; “honest” below means outside that set. Two sets of 𝑋 and 𝑌 distinct non-broadcasters share an honest party whenever 𝑋 + 𝑌 − 𝑁 > 𝑡.

Table 2: Compatibility of delivery origins (𝑄 echoes, 𝐶 confirms) and ready origins (𝑅 votes, 𝑅w witnesses). Entries are intersection sizes exceeding 𝑡, or Lemma 4.1; the 𝐶-confirm/𝑅vote case also uses 𝐶 + 𝑀 > 𝑁 . 𝑄-echo 𝐶-confirm 𝑅-vote 𝑄-echo 2𝑄 −𝑁 𝐶-confirm 𝑅-vote 𝑅w -witness

𝑄+𝐶 −𝑁 2𝐶 −𝑁

𝑅w -witness

𝑄+𝑀 −𝑁 𝑄+𝐶 −𝑁 𝐶+𝑅−𝑁 2𝐶 −𝑁 2𝑅−𝑁 Lemma 4.1 2𝐶 −𝑁

The budget range gives 2𝑄 − 𝑁 = 3𝑓 + 𝑠 − 2𝑏 > 𝑡,

2𝐶 − 𝑁 = 𝑓 + 𝑠 > 𝑡,

2𝑅 − 𝑁 = 𝑓 + 𝑠 + 2 > 𝑡,

𝑄 + 𝐶 − 𝑁 = 2𝑓 + 𝑠 − 𝑏 > 𝑡,

𝑄 + 𝑀 − 𝑁 = 2𝑓 + 𝑠 − 2𝑏 + 1 > 𝑡,

𝐶 + 𝑅 − 𝑁 = 𝑓 + 𝑠 + 1 > 𝑡, (3)

where 𝑄 + 𝑀 − 𝑁 > 𝑡 holds uniformly for 𝑡 ≤ 𝑓 − 1 exactly when 𝑏 ≤ ⌊𝑛/2⌋ − 𝑓 ; the others use 𝑏 ≤ 𝑓 . In particular, honest confirms have a unique value. One single-party fact is also used: 𝐶 + 𝑀 − 𝑁 = 𝑓 + 𝑠 − 𝑏 + 1 > 0, so a party whose 𝐶 echo slots hold one value never has 𝑀 slots for another and never votes for it, at any time. The following lemma is the additional compatibility that lets witnesses bypass the acknowledgment round. Lemma 4.1 (Witness/vote compatibility). With a Byzantine broadcaster, if 𝑅w witness slots at some honest party hold 𝑣, then at no time do 𝑅 vote slots at any honest party hold a value 𝑤 ≠ 𝑣. Proof. Let 𝑔 be the number of honest non-broadcasters that ever confirm 𝑣. At least 𝑅w −𝑡 ≥ 𝑓 of the witness authors are honest. The conclusions below are time-independent, so the order of events plays no role. If 𝑔 ≥ 𝑓 , any 𝑓 honest confirmers of 𝑣 hold 𝐶 echo slots for 𝑣 and, by the single-party fact, never vote for 𝑤; the witness quorum is not needed in this case. Only non-broadcasters vote, so at most 𝑁 − 𝑓 = 𝑅 − 1 distinct parties ever send a vote for 𝑤, and 𝑅 vote slots for 𝑤 cannot fill. Suppose 𝑔 ≤ 𝑓 −1 and fix an honest witness author 𝑖. Among its 𝑃 paired authors at most 𝑔 are honest, so at least 𝑃 −𝑔 ≥ 𝑃 −𝑓 +1 = 𝑠 +2 are Byzantine; each of their echo slots at 𝑖 holds 𝑣 by the pairing and is never overwritten. Since 𝑃 > 𝑡, at least one paired author is honest. That honest confirmer holds 𝐶 echo slots for 𝑣, at least 𝐶 − 𝑡 ≥ 𝐶 − 𝑓 + 1 = 𝑓 + 𝑠 + 1 of them from honest parties. Being honest, those parties echoed only 𝑣, so their echo slots at 𝑖 are empty or hold 𝑣, whether or not their echoes have reached 𝑖; being honest, they are distinct from the 𝑃 − 𝑔 Byzantine paired authors. Hence at least (𝐶 − 𝑡) + (𝑃 − 𝑔) ≥ (𝑓 + 𝑠 + 1) + (𝑠 + 2) = 𝑓 + 2𝑠 + 3 ≥ 𝑓 + 𝑏 echo slots at 𝑖 never hold 𝑤, using 𝑏 ≤ 2𝑠 + 3. At most 𝑁 − (𝑓 +𝑏) = 𝑀 − 1 slots at 𝑖 can hold 𝑤 at any time, so 𝑖 never votes for 𝑤. Applying this to the at least 𝑓 honest witness authors, again at most 𝑅 − 1 parties ever vote for 𝑤. □ Lemma 4.2 (Agreement and validity). Algorithm 1 satisfies agreement and validity.

Optimistic Reliable Broadcast in Three Steps

Proof. First let the broadcaster be Byzantine. Honest confirms have a unique value, since the echo quorums of two confirmers share an honest party by 2𝐶 − 𝑁 > 𝑡, and that party echoed once. Every honest witness has an honest confirmer among its 𝑃 > 𝑡 paired authors, so honest witnesses have that same value. Table 2 lists, for each pair of origins, the fact that forbids different values; all of them are intersection counts on immutable slots and do not depend on the order of events. Readies first. Two 𝑅-vote quorums share an honest party by 2𝑅 − 𝑁 > 𝑡, and that party voted once. An 𝑅w -witness quorum contains an honest witness, and Lemma 4.1 excludes an opposite vote quorum. Following relays backwards, each honest ready reaches in finitely many steps an honest origin ready for the same value, since a relay on 𝑓 + 1 readies contains an honest, strictly earlier ready; two honest readies for different values would give two honest origins for different values, which is excluded. Hence all honest readies carry one value. Deliveries next. A delivery on 𝑄 echoes excludes an opposite honest vote by 𝑄 + 𝑀 − 𝑁 > 𝑡 and an opposite honest confirm by 𝑄 + 𝐶 − 𝑁 > 𝑡; hence it agrees with every ready origin, through the honest voter or the honest paired confirmer that the origin contains, and with every confirm delivery; two echo deliveries share an honest party by 2𝑄 − 𝑁 > 𝑡. A delivery on 𝐶 confirms excludes an opposite 𝑅-vote quorum, since the two author sets share an honest party by 𝐶 + 𝑅 − 𝑁 > 𝑡 and an honest confirmer cannot vote oppositely by 𝐶 + 𝑀 > 𝑁 ; it agrees with every witness origin by confirm uniqueness. A delivery on 2𝑓 + 1 readies contains an honest ready and reduces to the ready case. These cases cover every pair of origins. Now let the broadcaster be honest, with at most 𝑓 Byzantine non-broadcasters. Every honest echo carries the broadcaster’s input. The thresholds 𝑀, 𝐶, 𝑃 exceed 𝑓 , and 𝑅w = 2𝑓 − 1 > 𝑓 for 𝑓 ≥ 2, so every vote, confirm, and witness quorum contains an honest author, whose message carries the input by induction along the message chain; the same holds for the delivery quorums 𝑄, 𝐶 > 𝑓 and for every ready origin. Relays and ready deliveries contain an honest ready and reduce to an honest origin. Hence every delivered value is the broadcaster’s input. □

4.2

Delivery and communication

Lemma 4.3 (Good case and totality). Algorithm 1 has the latency guarantees of Theorem 1.2 and satisfies eventual totality asynchronously. Proof. With an honest broadcaster, everyone receives the proposal by step one. At most 𝑏 faults leave 𝑄 honest echoes, giving delivery by step two; at most 𝑓 leave 𝐶 honest echoes and then 𝐶 honest confirms, giving delivery by step three. This also bounds honest-broadcaster totality. For a Byzantine broadcaster, let the first honest delivery of 𝑣 be at 𝑇 . Echo delivery leaves 𝑄 − 𝑡 ≥ 𝑀 honest echoes already sent. By 𝑇 + 𝛿 everyone receives them and votes 𝑣: the intersection 𝑄 +𝑀 − 𝑁 > 𝑡 excludes any earlier opposite vote. At least 𝑁 −𝑡 ≥ 𝑅 honest votes arrive by 𝑇 + 2𝛿, giving ready and delivery by 𝑇 + 3𝛿. Confirm delivery leaves 𝐶 − 𝑡 ≥ 𝑃 honest authors that sent both echo and confirm. Their paired messages reach everyone by 𝑇 + 𝛿, giving witness, ready, and delivery by 𝑇 + 3𝛿. Confirm uniqueness

excludes an earlier opposite witness; there is no own-echo guard on witnesses. Ready delivery leaves 𝑓 + 1 honest readies, which reach everyone within one step, giving relay and delivery within two. Safety excludes opposite readies in all cases. These finite chains also prove eventual totality without a delay bound. □ Proof of Theorem 1.2. Combine Lemmas 4.2 and 4.3. Each nonbroadcaster sends at most five multicasts and the broadcaster at most two: 5(𝑛 − 1) 2 + 2(𝑛 − 1) messages, including failed executions and service after delivery. Later corruptions do not increase pre-corruption sends. Full values cost 𝑂 (𝑛 2 𝐿) payload bits, in addition to message headers; slot and matched-author counters require polynomial work. For 𝑛 ≥ 4𝑓 , 𝑏 = 𝑓 satisfies (1), covering all honest-broadcaster executions. □ Proof of Corollary 1.3. For 𝑛 < 4𝑓 , 𝑛 − 3𝑓 ≤ 𝑏 ∗ . In the stated range 𝑏 ∗ ≤ min{𝑓 , 2𝑠 + 3}, so Theorems 1.2 and 1.1 give matching totality bounds at 𝑏 = 𝑏 ∗ . At 𝑛 = 3𝑓 + 1, the lower bound applies to every 𝑏 ≥ 1, and the construction supports 𝑏 ≤ min{3, 𝑏 ∗ }. Good-case latency three is optimal below 4𝑓 by [2, Theorem 4]. □

5 Applications and further results 5.1 Applications to BFT consensus BFT protocols that use reliable broadcast as a black box for block dissemination can use paired witnesses when their RBC interface and fault model match. This includes DAG-based protocols whose vertices are disseminated by RBC, as in Bullshark’s abstract construction [19, Sections 3–4]. Bullshark and Narwhal/Tusk [7] belong to the certified-DAG family surveyed by Raikwar et al. [16, Section III-D]. Replacing Opt-RBC’s (2, 4, 4) by (2, 3, 3) reduces goodcase latency and totality delay by one step each, with the optimistic budget of Theorem 1.2. At 𝑛 = 3𝑓 + 1 with 𝑓 ≥ 7 this budget is three, below 𝑏 ∗ : with between four and 𝑏 ∗ actual faults, Opt-RBC still guarantees two-step delivery and paired witnesses guarantee three steps. Confirm/ack keeps the budget 𝑏 ∗ . Dissemination on the commit path can therefore finish earlier, and recovery timers based on totality can be shorter; the resulting consensus bounds depend on the surrounding protocol. An interface that additionally requires transferable certificates needs a separate compatibility argument. For concrete consequences, consider Sailfish++ and Simple-IT. Let 𝛿 be the actual network delay bound after GST and Δ > 𝛿 its known bound. On honest-leader commit paths with resolved dependencies, replacing Opt-RBC by paired witnesses reduces commit latency from 5𝛿 to 4𝛿 in both the DAG-based Sailfish++ protocol [17, Section 7] and base Simple-IT [20, Lemmas 6–8]. Totality also bounds round-entry skew. In Simple-IT, if an honest party enters round 𝑟 at time 𝑡 ≥ GST, all honest parties have entered it by 𝑡 + 𝑑𝑡 𝛿 [20, Lemma 12]. Substituting paired witnesses reduces this bound from 4𝛿 to 3𝛿. Simple-IT sets its round timer to (𝑑𝑠 + 𝑑𝑡 )Δ and bounds eventual worst-case view duration by (𝑑𝑠 + 𝑑𝑡 )Δ + 𝑑𝑡 𝛿, including views with faulty leaders. Substituting the paired-witness triple (2, 3, 3) reduces these bounds from 8Δ to 6Δ and from 8Δ + 4𝛿 to 6Δ + 3𝛿, respectively [20, Lemma 8 and Corollary 5]. These are consequences of the source analyses under their stated conditions. Appendix D gives the complete comparison, the optimistic fault budgets and readiness premises, and the full-proposal requirement for Sailfish++’s first-message commit rule.

Nikita Polianskii

5.2

Further results

We give a coded realization of paired witnesses and a full-value fallback that retains maximal optimism throughout the resilience range. Linear-communication paired witnesses. Proposition 5.1 (Coded paired witnesses). For the parameters of Theorem 1.2, an MDS code and a collision-resistant hash function give a (2, 3, 3) reliable broadcast protocol for 𝐿-bit values, conditional on commitment binding. Against a computationally bounded adaptive adversary, binding fails only with negligible probability. Communication sent while its authors are uncorrupted is 𝑂 (𝑛𝐿 + 𝜅𝑛 2 log 𝑛) bits in every execution, where 𝜅 is the hash length. Its payload traffic has leading bounds 3𝑛𝐿 with an honest broadcaster and 6𝑛𝐿 in every execution. Appendix C gives the packet rules, the exact bounds, and the proof. Each recipient echoes its own indexed fragment; a voter reconstructs and supplies its own fragment if it has not already sent it; a confirm requires both reconstruction and the own-echo guard. Every possible first delivery therefore leaves enough honest fragments in transit to preserve the control protocol’s deadlines. Since Merkle membership alone does not certify a codeword, every reconstruction re-encodes the vector and checks the committed root. The bound charges pre-corruption sends and needs no staticfault assumption. Maximal optimism for every 𝑛, at four totality steps. Theorem 5.2 (Confirm/ack broadcast). Let 𝑓 ≥ 1, 𝑛 ≥ 3𝑓 + 1, and 𝑏 = min{𝑓 , ⌊𝑛/2⌋ − 𝑓 }. The confirm/ack protocol is a signaturefree asynchronous reliable broadcast protocol against adaptive corruption of at most 𝑓 parties. It guarantees (2, 3, 4) at budget 𝑏, and (2, 2, 4) when 𝑛 ≥ 4𝑓 , with 𝑂 (𝑛 2 ) messages sent while their authors are uncorrupted, including after delivery. The protocol and proof are in Appendix E. At 𝑛 = 3𝑓 + 1, Proposition E.14 gives its exact fault-dependent totality profile. The matching executions concern this protocol; four steps are not a lower bound for reliable broadcast in general.

6

Related work

Optimistic broadcast and latency. Shrestha et al. study optimistic reliable broadcast and use Opt-RBC in Sailfish++ [17]. We cite the corrected arXiv v4, not the superseded CCS 2025 protocol; theorem and figure numbers refer to v4. At 𝑛 = 3𝑓 + 1 we retain its fast echo threshold and its vote mechanism; paired witnesses replace its acknowledgment round. Its Theorem 8 bounds the optimistic budget by ⌊𝑛/2⌋ − 𝑓 below 4𝑓 , and Theorem 4 of Abraham, Ren, and Xiang (Theorem 10 at OPODIS 2021) requires 𝑛 ≥ 4𝑓 for two-step delivery under all 𝑓 faults [2]; Theorem 1.1 adds a totality bound already at budget 𝑛 − 3𝑓 , including budget one at minimum resilience. Both cited lower bounds use four-execution indistinguishability arguments. Our six-execution proof preserves an early honest-party delivery under nonuniform delays to force a relative totality deadline; its final bridges use eventual totality. Yu et al. define elapsed totality delay and tabulate it for existing protocols [20]. Abraham, Ren, and Xiang also study the cost of two-round delivery at 𝑛 ≥ 4𝑓 [2, Section 4]. Their Theorem 5 rules out a two-round

bad case for 𝑓 ≥ 2; Theorem 7 gives a four-round bad-case lower bound when 𝑓 ≥ 3 and 𝑛 ≤ 5𝑓 − 2, in their round convention. Their Theorem 3 supplies a two-round good-case protocol at 𝑛 ≥ 4𝑓 whose rules give elapsed totality at most three: after fast delivery, honest acks reach everyone, followed by vote-1 and vote-2; vote-2 delivery needs at most two further steps. This is a (2, 2, 3) upper bound at full budget in our convention. Thus our 𝑏 = 𝑓 specialization at 𝑛 ≥ 4𝑓 recovers an existing guarantee. Their Theorems 8 and 9 give the special 𝑓 = 2 construction and a three-round bad case at 𝑛 ≥ 5𝑓 − 1. These are the direct precedents for studying the totality cost of a fast path. We do not convert their lower bounds into elapsed-time bounds: our theorem concerns restricted optimistic budgets below 4𝑓 and is witnessed by honest-broadcaster spread, not by a lower bound on Byzantine-broadcaster recovery. Imbs and Raynal give a signature-free two-step protocol for 𝑛 > 5𝑓 ; the corrected archive states this resilience restriction explicitly [9]; ARX’s 𝑛 ≥ 5𝑓 − 1 construction improves that resilience for its fast bad-case guarantee. Abraham, Nayak, Ren, and Xiang’s good-case categorization treats authenticated broadcast with signatures [1]; it is distinct from the signature-free lower bounds used here. Communication and dispersal. Opt-RBC v4 already includes a balanced coded realization with 𝑂 (𝑛𝐿 + 𝜅𝑛 2 log 𝑛) bits [17, Section 5]. DXR [8] and CC-BRB [3] use hashing without trusted setup and have 𝑂 (𝑛𝐿 + 𝜅𝑛 2 ) bits; CC-BRB also has a three-step honest-broadcaster path. Appendix C compares their payload and metadata constants with ours. Unsigned OptMiniCast has leading payload 1.5𝑛𝐿 with an honest broadcaster and 2𝑛𝐿 universally [12], and MiniCast* reaches 1.5𝑛𝐿 universally with hash functions; its two-step variants use signatures [13]. Both beat the universal payload coefficient of our coded realization, which instead combines a two-step optimistic path with three-step totality. Our coefficients are upper bounds, not lower bounds. Merkle-authenticated fragments and reconstruction by re-encoding are established in dispersal [3, 4, 6, 11]. Our coded proof shows availability at each delivery deadline of the paired-witness protocol. Other termination models. Lewis-Pye and O’Grady study unconditional Byzantine broadcast termination under partial synchrony [10]; those bounds do not transfer directly to asynchronous reliable broadcast. Availability-graded broadcast omits totality and has a separate resolver [15]. Quit-resistant broadcast permits stopping behaviors [14] that our constructions do not support: parties complete their bounded sends after delivery.

7

Conclusion and open problems

For 3𝑓 + 1 ≤ 𝑛 < 4𝑓 , confirm/ack achieves (2, 3, 4) at maximal optimism, preserving the optimal three-step good case. Our lower bound shows that totality delay at least three is unavoidable for deterministic protocols in our model whenever 𝑏 ≥ 𝑛−3𝑓 , even with an honest broadcaster. Paired witnesses attain this bound in the matching parameter ranges established above, including maximal optimism. Both constructions use quadratic messages. Two directions remain. First, can a quadratic-message (2, 3, 3) protocol achieve maximal optimism throughout 3𝑓 + 1 ≤ 𝑛 < 4𝑓 ? The principal gap is at minimum resilience, 𝑛 = 3𝑓 +1, where paired

Optimistic Reliable Broadcast in Three Steps

witnesses support only 𝑏 ≤ min{3, 𝑏 ∗ }. Second, what is the optimal totality delay for smaller optimistic budgets 1 ≤ 𝑏 < 𝑛 − 3𝑓 , which our lower bound does not cover? In particular, which parameters permit (2, 3, 2)?

References [1] Ittai Abraham, Kartik Nayak, Ling Ren, and Zhuolun Xiang. 2021. Good-case Latency of Byzantine Broadcast: A Complete Categorization. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC). 331–341. https://arxiv.org/abs/2102.07240v1 Cited archive: arXiv:2102.07240v1, February 14, 2021. [2] Ittai Abraham, Ling Ren, and Zhuolun Xiang. 2021. Good-Case and BadCase Latency of Unauthenticated Byzantine Broadcast: A Complete Categorization. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 217). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 5:1– 5:20. https://doi.org/10.4230/LIPIcs.OPODIS.2021.5 arXiv:2109.12454v1 We cite arXiv:2109.12454v1 (2021-09-25); its Theorem 4 and Definition 5 are Theorem 10 and Definition 7 in the OPODIS version. [3] Nicolas Alhaddad, Sisi Duan, Mayank Varia, and Haibin Zhang. 2022. Practical and Improved Byzantine Reliable Broadcast and Asynchronous Verifiable Information Dispersal from Hash Functions. ePrint 2022/171. https: //eprint.iacr.org/2022/171 [4] Nicolas Alhaddad, Leonid Reyzin, and Mayank Varia. 2024. Committing AVID with Partial Retrieval and Optimal Storage. Cryptology ePrint Archive, Paper 2024/685. https://eprint.iacr.org/2024/685 May 4, 2024 submission. [5] Gabriel Bracha. 1987. Asynchronous Byzantine Agreement Protocols. Information and Computation 75, 2 (1987), 130–143. https://doi.org/10.1016/08905401(87)90054-X [6] Christian Cachin and Stefano Tessaro. 2005. Asynchronous Verifiable Information Dispersal. In Proceedings of the IEEE Symposium on Reliable Distributed Systems (SRDS). 191–202. https://people.csail.mit.edu/tessaro/papers/dds.pdf Cited archive: author-hosted full version dated November 15, 2004. [7] George Danezis, Lefteris Kokoris-Kogias, Alberto Sonnino, and Alexander Spiegelman. 2022. Narwhal and Tusk: A DAG-based Mempool and Efficient BFT Consensus. In Proceedings of the Seventeenth European Conference on Computer Systems (EuroSys). 34–50. https://doi.org/10.1145/3492321.3519594 [8] Sourav Das, Zhuolun Xiang, and Ling Ren. 2021. Asynchronous Data Dissemination and its Applications. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security (CCS). 2705–2721. https: //eprint.iacr.org/2021/777 Cited archive: ePrint 2021/777. [9] Damien Imbs and Michel Raynal. 2016. Trading off 𝑡 -Resilience for Efficiency in Asynchronous Byzantine Reliable Broadcast. Parallel Processing Letters 26, 4 (2016), 1650017. https://doi.org/10.1142/S0129626416500171 Cited archive: corrected arXiv:1510.06882v2, September 28, 2021; requires n > 5f. [10] Andrew Lewis-Pye and Patrick O’Grady. 2026. The Carnot Bound: Limits and Possibilities for Bandwidth-Efficient Consensus. arXiv:2603.11797v3 https: //arxiv.org/abs/2603.11797v3 arXiv:2603.11797v3; 2026-07-28. [11] Thomas Locher and Yvonne-Anne Pignolet. 2026. Asynchronous Verifiable Information Dispersal with Low Space and Communication Complexity. In Proceedings of the 38th ACM Symposium on Parallelism in Algorithms and Architectures. ACM, New York, NY, USA, 143–154. https://doi.org/10.1145/3816782.3819202 arXiv:2608.24636v2, August 26, 2026. [12] Thomas Locher and Victor Shoup. 2025. MiniCast: Minimizing the Communication Complexity of Reliable Broadcast. In Advances in Cryptology – EUROCRYPT 2025, Part V (Lecture Notes in Computer Science). Springer, Cham, 96–115. https://doi.org/10.1007/978-3-031-91092-0_4 We cite ePrint 2024/571 (last revised 2024-04-26); section and figure numbers refer to that version. [13] Thomas Locher and Victor Shoup. 2026. Towards Reliable Broadcast with Optimal Communication and Round Complexity. In Proceedings of the 38th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA ’26). ACM, New York, NY, USA, 155–166. https://doi.org/10.1145/3816782.3819206 We cite ePrint 2025/779, revision 2025-10-03; section, figure, and equation numbers refer to that version. [14] Mose Mizrahi Erbes and Roger Wattenhofer. 2024. Quit-Resistant Reliable Broadcast and Efficient Terminating Gather. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024) (Leibniz International Proceedings in Informatics, Vol. 324). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 15:1–15:22. https://doi.org/10.4230/LIPIcs.OPODIS.2024.15 [15] Nikita Polyanskii. 2026. Vantage: Availability-Graded Broadcast for SignatureFree BFT. arXiv:2608.16504v2 https://arxiv.org/abs/2608.16504v2 August 30, 2026. [16] Mayank Raikwar, Nikita Polyanskii, and Sebastian Müller. 2024. SoK: DAGbased Consensus Protocols. In IEEE International Conference on Blockchain and Cryptocurrency (ICBC). 1–18. https://doi.org/10.1109/ICBC59979.2024.10634358

Revised version: arXiv:2411.10026v2, April 22, 2025. [17] Nibesh Shrestha, Qianyu Yu, Aniket Kate, Giuliano Losa, Kartik Nayak, and Xuechao Wang. 2025. Optimistic, Signature-Free Reliable Broadcast and Its Applications. In Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security (CCS ’25). ACM, New York, NY, USA. https: //doi.org/10.1145/3719027.3765220 arXiv:2505.02761v4 Distinguished paper. We cite the revised arXiv version arXiv:2505.02761v4 (2026-05-24), which fixes a termination issue in the earlier design; theorem and definition numbers refer to v4. [18] Nibesh Shrestha, Qianyu Yu, Aniket Kate, Giuliano Losa, Kartik Nayak, and Xuechao Wang. 2025. Optimistic, Signature-Free Reliable Broadcast and Its Applications. arXiv:2505.02761v2 https://arxiv.org/abs/2505.02761v2 arXiv:2505.02761v2; 2025-08-29; SUPERSEDED. [19] Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, and Lefteris KokorisKogias. 2022. Bullshark: DAG BFT Protocols Made Practical. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security (CCS). 2705–2718. https://doi.org/10.1145/3548606.3559361 [20] Qianyu Yu, Juan Villacis, Giuliano Losa, Zhuolun Xiang, and Xuechao Wang. 2026. Simple-IT: Practical Low-Latency Signature-Free BFT Consensus. arXiv:2606.14404v1 https://arxiv.org/abs/2606.14404v1 June 12, 2026.

A Complete six-execution lower-bound proof A.1 Two steps are necessary Lemma A.1 (Folklore). In the model of Section 2, a reliable broadcast protocol tolerating one Byzantine broadcaster cannot have an optimistic good-case latency strictly below two steps, even if that latency is required only in fault-free executions. Proof. Take two fault-free executions with different broadcaster inputs 𝐴, 𝐵 and every interparty message delayed by exactly 𝛿. Before 2𝛿, a non-broadcaster receives no input-dependent message from another non-broadcaster: such a message cannot be sent before 𝛿. All other non-broadcaster traffic received before the cut is input-independent and identical in the two executions, including timer-driven traffic. A Byzantine broadcaster can therefore reproduce its 𝐴-execution stream to one nonempty group and its 𝐵-execution stream to another. Keep every honest interparty delay equal to 𝛿. Before 2𝛿, each recipient has precisely its local history from the corresponding fault-free execution. If all honest recipients had to deliver strictly before this cut, validity in the two fault-free executions would force different deliveries in the mixed execution, contradicting agreement. □

A.2

Setup

We give the joint schedule underlying Theorem 1.1 and prove Lemmas 3.1 and 3.2. The notation and partition are those of Section 3: endpoint groups 𝐸𝐴 , 𝐸𝐵 of size 𝑠 + 1, common groups 𝐾𝐴 , 𝐾𝐵 of size 𝑓 , and a source group S of size 𝑓 − 𝑠 − 1 containing broadcaster 0. Every member of S\{0} is an ordinary recipient. Choose the anchor ℎ ∈ S \ {0} if |S| ≥ 2, and ℎ = 0 otherwise. For the recipient-only interface, all occurrences of delivery and totality below concern non-broadcasters. The choice ℎ ≠ 0 is available precisely when 𝑛 ≤ 4𝑓 − 2; only ℎ = 0 requires the broadcaster to deliver. Suppose a constant 𝐷 < 3 bounds totality delay whenever the broadcaster is honest and at most 𝑓 non-broadcasters are faulty. Choose 𝜀, 𝜂 > 0 with 2𝜀 < 𝜂, 𝐻 = 2𝜀 + 𝐷𝜂 < 3𝜂, 𝐽 = 4𝜂. The code and initial states do not depend on the actual network delay bound. With these fixed for the two inputs 𝐴, 𝐵, we may take 𝜂 small enough that 3𝜂 precedes every positive expiration of a timer set during initialization. There are finitely many parties and finitely

Nikita Polianskii

Table 3: Executions in the totality lower bound. The last column gives the honest delivery forced by two-step optimism (fast executions), by the hypothetical totality bound (forcing executions), or by copied histories (bridges); “𝐸𝐴 :𝐴 by 𝐻 ” means every member of 𝐸𝐴 delivers 𝐴 by time 𝐻 . Execution

Byzantine set

Largest honest delay

Forced delivery

𝐹𝐴 (fast) 𝐹𝐵 (fast) 𝑋𝐴 (forcing) 𝑋𝐵 (forcing) 𝑊𝐴 (bridge) 𝑊𝐵 (bridge)

𝐸𝐵 𝐸𝐴 𝐾𝐵 𝐾𝐴 S ∪ 𝐸𝐵 S ∪ 𝐸𝐴

𝜀 𝜀 𝜂 𝜂 𝐽 𝐽

ℎ:𝐴 by 2𝜀 ℎ:𝐵 by 2𝜀 𝐸𝐴 :𝐴 by 𝐻 𝐸𝐵 :𝐵 by 𝐻 𝐸𝐴 :𝐴 by 𝐻 𝐸𝐵 :𝐵 by 𝐻

many initialization events; if no such timer exists, the condition is vacuous. The construction never discards a packet or a timer: initial packets and reactive timers are retained in every execution. Initial packets are those sent during finite zero-time initialization before any external receipt; non-broadcasters’ initial packets are inputindependent and may be recipient-specific. Self-messages are local events and are handled identically in compared histories. Simultaneous events are ordered by one deterministic rule, depending only on time, sender identity, and content, in all six executions. We call 𝐹𝐴 and 𝐹𝐵 the seeds of 𝑋𝐴 and 𝑋𝐵 : the forcing executions are built so that ℎ has its seed’s history through 2𝜀.

A.3

Fast seeds and forcing executions

In 𝐹𝐴 , the faulty group 𝐸𝐵 sends the initial packets its members would send, with delay 𝜀, and then remains silent. All honest messages have delay 𝜀. Define 𝐹𝐵 symmetrically, with 𝐸𝐴 faulty. The optimistic premise forces the honest anchor ℎ to deliver 𝐴 in 𝐹𝐴 and 𝐵 in 𝐹𝐵 by 2𝜀. In 𝑋𝐴 , delay all initial packets addressed to the honest group 𝐸𝐵 until 𝜂, including interparty links within 𝐸𝐵 . Initial packets to other honest parties arrive at 𝜀, processed in the same order as in 𝐹𝐴 . In particular, 𝐸𝐵 ’s outgoing initial packets arrive early at early recipients. All noninitial honest packets have delay 𝜂, except packets addressed to ℎ and sent by time 𝜀, which have delay 𝜀 (the anchor exception). Faulty members of 𝐾𝐵 replay their 𝐹𝐴 streams to ℎ for sends through 𝜀; honest 𝐾𝐵 in 𝑊𝐴 reacts to the broadcaster’s 𝐵 stream, so its early packets to ℎ would not match 𝐹𝐴 . Their other streams are fixed jointly with the bridges below. 𝑋𝐵 is symmetric, with 𝐸𝐴 late and 𝐾𝐴 faulty. Every honest party in S ∪ 𝐸𝐴 ∪ 𝐾𝐴 has its seed history on [0, 𝜀]: only initial packets have arrived. Its receipts after 𝜀 differ from 𝐹𝐴 , but any interparty packet it sends after 𝜀 reaches ℎ after 2𝜀 in both executions. When ℎ ≠ 0, this reasoning includes broadcaster 0, whose input and initial receipts are identical in the seed and forcing execution. The late group’s initial outward packets are preserved, and its noninitial packets cannot arrive at ℎ this early. The Byzantine seed copies supply the remaining identities. Thus ℎ has exactly its seed history on [0, 2𝜀], including zero-time reactions at the times 0 and 2𝜀 themselves. It delivers 𝐴 in 𝑋𝐴 and 𝐵 in 𝑋𝐵 by 2𝜀. The first honest delivery is no later than this. Validity and the

assumed totality bound therefore force every member of 𝐸𝐴 in 𝑋𝐴 to deliver 𝐴 by 𝐻 , and every member of 𝐸𝐵 in 𝑋𝐵 to deliver 𝐵 by 𝐻 .

A.4

The joint bridge schedule

The following rules complete 𝑋𝐴 , 𝑋𝐵 ,𝑊𝐴 ,𝑊𝐵 simultaneously. When copying a stream, a Byzantine party sends under its own identity and preserves arrival times; no honest direct channel is forged. All initial non-broadcaster packets arrive at 𝜀 at honest bridge recipients. (1) In both bridges, every faulty identity 𝑧 ∈ S copies its own 𝑋𝐴 stream to 𝐸𝐴 ∪ 𝐾𝐴 and its own 𝑋𝐵 stream to 𝐸𝐵 ∪ 𝐾𝐵 , preserving arrival times at honest recipients. This includes 0 and each ordinary recipient in S \ {0}. (2) Noninitial packets sent by common parties in 𝐾𝐴 ∪ 𝐾𝐵 have delay 𝜂 to honest recipients. In 𝑊𝐴 , honest members of 𝐸𝐴 send with delay 𝜂 to 𝐸𝐴 ∪ 𝐾𝐴 and with delay 𝐽 to 𝐾𝐵 . In 𝑊𝐵 , honest members of 𝐸𝐵 send with delay 𝜂 to 𝐸𝐵 ∪ 𝐾𝐵 and with delay 𝐽 to 𝐾𝐴 . Packets to faulty recipients may use delay 𝜂. (3) For each 𝑞 ∈ 𝐸𝐵 , its Byzantine copy in 𝑊𝐴 reproduces honest 𝑞’s 𝑊𝐵 stream towards every common recipient, with exactly the same arrival schedule. Towards each 𝑝 ∈ 𝐸𝐴 it instead reproduces that recipient’s private stream from the late helper 𝑞 in 𝑋𝐴 , again with the same arrival schedule. Each 𝑝 ∈ 𝐸𝐴 in 𝑊𝐵 does the symmetric copying from 𝑊𝐴 towards common recipients and from 𝑋𝐵 towards 𝐸𝐵 . (4) In 𝑋𝐴 , each faulty member of 𝐾𝐵 copies the stream of honest 𝐾𝐵 in 𝑊𝐴 towards the early honest parties (S \ {ℎ}) ∪ 𝐸𝐴 ∪ 𝐾𝐴 , with initial packets arriving at 𝜀 and later packets taking 𝜂. To late recipients in 𝐸𝐵 , its initial packets arrive at 𝜂 and its subsequent copied packets have delay 𝜂. To ℎ, retain the seed-prefix exception for sends through 𝜀; later sends copy the 𝑊𝐴 counterpart with delay 𝜂. These cases are disjoint: when ℎ ≠ 0, source 0 uses the ordinary copied stream, not the exception. The faulty 𝐾𝐴 in 𝑋𝐵 behaves symmetrically. All honest-to-honest delays in the forcing executions are at most 𝜂, and in the bridges at most 𝐽 . A copy depends on an honest send already determined at its send time. Every nonlocal delivery has a positive delay at least 𝜀. Fix initialization first and construct the worlds by increasing time, or in successive 𝜀-width intervals, retaining the locally finite timer events and local reactions. Thus the mutual copying has no dependence on a future receipt. The protocol may embed entire histories or destination-specific information in a packet: we copy complete packets and their event order, not summaries of them.

A.5

Proof of the causal-cut lemma

We prove simultaneously that 𝐾𝐴 has the same histories in 𝑋𝐴 ,𝑊𝐴 before 2𝜂, 𝐾𝐵 in 𝑋𝐵 ,𝑊𝐵 before 2𝜂, 𝐸𝐴 in 𝑋𝐴 ,𝑊𝐴 before 3𝜂, and 𝐸𝐵 in 𝑋𝐵 ,𝑊𝐵 before 3𝜂. We compare, sender identity by sender identity, the packets a party receives before the cut in the two executions. Consider 𝐾𝐴 . In 𝑋𝐴 , every initial interparty packet to the late group 𝐸𝐵 is delayed, including those on links within 𝐸𝐵 . No member of 𝐸𝐵 receives external information before 𝜂, and no initial positive timer expires before 3𝜂. Hence it sends no noninitial packet before

Optimistic Reliable Broadcast in Three Steps

𝜂, and its first such packet reaches 𝐾𝐴 no earlier than 2𝜂. In 𝑊𝐴 , the copied opposite-bridge stream from 𝐸𝐵 to 𝐾𝐴 has delay 𝐽 for noninitial packets. The initial packets match. Packets from every member of S to 𝐾𝐴 are copied from 𝑋𝐴 into 𝑊𝐴 by rule 1, and 𝐾𝐵 ’s packets from 𝑊𝐴 into 𝑋𝐴 by rule 4. A packet from 𝐸𝐴 arriving at 𝐾𝐴 before 2𝜂 depends on an 𝐸𝐴 history before 𝜂. Within-𝐾𝐴 packets depend on strictly earlier histories. The claim for 𝐾𝐵 is symmetric. At an endpoint 𝑝 ∈ 𝐸𝐴 , packets from S and the direct private 𝐸𝐵 stream are copied from 𝑋𝐴 into 𝑊𝐴 by rules 1 and 3, and packets from 𝐾𝐵 from 𝑊𝐴 into 𝑋𝐴 by rule 4. A packet from 𝐾𝐴 arriving before 3𝜂 was sent before 2𝜂, during the matching interval just established. A packet from another member of 𝐸𝐴 has delay 𝜂 and depends on that member’s strictly earlier history. Thus induction on causal events establishes the entire 𝐸𝐴 -group match; there is no instantaneous internal group communication. The 𝐸𝐵 argument is symmetric. These dependencies are all to strictly earlier events, so the simultaneous induction is well founded rather than circular. The statements concern complete timed histories. Determinism therefore preserves timer schedules, every local state transition, and messages triggered by delivery. A short reactive timer cannot precede its triggering receipt. The construction does not discard any packet or stop a party at delivery. The cut is strict: it makes no claim that endpoint histories still agree at 3𝜂. Since 𝐻 < 3𝜂, all forced 𝐸𝐴 deliveries are inherited in 𝑊𝐴 and all forced 𝐸𝐵 deliveries in 𝑊𝐵 . In particular, the bridges contain opposite honest deliveries.

A.6

Indefinite common histories

Every member of 𝐾𝐴 ∪ 𝐾𝐵 receives the same stream from each identity in S in both bridges. For each identity in 𝐸𝐴 , it receives an honest 𝑊𝐴 stream and its Byzantine 𝑊𝐵 copy; for each identity in 𝐸𝐵 , an honest 𝑊𝐵 stream and its Byzantine 𝑊𝐴 copy. Common-tocommon packets have identical schedules and, inductively, identical contents. Therefore the common parties have identical complete histories forever, identity by identity, which is Lemma 3.2. The differing private 𝐸𝐴 –𝐸𝐵 streams impose no conflicting channel obligation: every such channel has a Byzantine party at one end in each bridge. Continue the causal construction indefinitely, preserving every queued packet. Honest bridge delays remain at most 𝐽 , so the executions are fair. Agreement and eventual totality force each common honest party to deliver 𝐴 in 𝑊𝐴 and 𝐵 in 𝑊𝐵 . Identical deterministic histories make this impossible. We have contradicted every constant 𝐷 < 3 already on honest-broadcaster executions, proving Theorem 1.1.

B Paired-witness details and fast-echo baseline B.1 Bracha with fast echo delivery The following elementary baseline separates honest-broadcaster spread from Byzantine-broadcaster recovery; it is a modification of Bracha [5], not an additional paired-witness result. Let 𝑁 = 𝑛 − 1, 𝑄 = 𝑁 − 𝑏, and 𝐸 = ⌈(𝑁 + 𝑓 )/2⌉. Non-broadcasters echo the first proposal. Every party sends ready on 𝐸 echoes or 𝑓 + 1 readies, and delivers on 𝑄 echoes or 2𝑓 + 1 readies. Sends are one-shot across values, slots are immutable, and parties continue processing after delivery.

Table 4: Thresholds of Algorithm 1, with 𝑁 = 𝑛 − 1 and 𝑡 ≤ 𝑓 − 1 Byzantine non-broadcasters when the broadcaster is Byzantine. Threshold (use)

Why this value

𝑄 = 𝑁 − 𝑏 (echo delivery)

every honest echo has arrived after two steps when at most 𝑏 parties are faulty 𝐶 = 𝑁 − 𝑓 (confirm, its delivery) every honest echo, or confirm, has arrived when at most 𝑓 parties are faulty 𝑀 = 𝑄 − 𝑓 + 1 (vote) honest echoes guaranteed behind an echo delivery: 𝑄 − 𝑡 ≥ 𝑀 honest confirmers guaranteed be𝑃 = 𝐶 − 𝑓 + 1 (witness) hind a confirm delivery: 𝐶 − 𝑡 ≥ 𝑃 𝑅 = 𝑁 − 𝑓 + 1 (ready) votes of all honest nonbroadcasters: 𝑁 − 𝑡 ≥ 𝑅 𝑅w = 2𝑓 − 1 (ready) at least 𝑅w − 𝑡 ≥ 𝑓 honest witnesses; 𝑅w < 𝑅 ≤ 𝑁 − 𝑡 , so honest witnesses alone reach 𝑅w after a confirm delivery

Proposition B.1 (Fast-echo baseline). For 3𝑓 + 1 ≤ 𝑛 < 4𝑓 , 𝑠 = 𝑛 − 3𝑓 − 1, and 1 ≤ 𝑏 ≤ ⌊𝑠/2⌋ + 1, this protocol has quadratic messages and guarantees (2, 3, 3), with 𝑑𝑡B ≤ 2. At 𝑛 = 3𝑓 + 1, 𝑏 = 1, Theorem 1.1 gives 𝑑𝑡H = 𝑑𝑡 = 3. Proof. With a Byzantine broadcaster there are at most 𝑡 = 𝑓 − 1 faulty echo authors. The stated range gives 2𝑄 −𝑁 > 𝑡, 𝑄 +𝐸−𝑁 > 𝑡, and 2𝐸 − 𝑁 > 𝑡. Thus two fast quorums, a fast quorum and a readyorigin echo quorum, or two ready-origin echo quorums share an honest echo author. These intersections and the 𝑓 + 1 ready relay ensure agreement by the usual first-honest-ready argument. With an honest broadcaster, 𝐸, 𝑄 > 𝑓 ensure validity. The 𝑁 − 𝑏 honest echoes suffice for two-step delivery under 𝑏 faults; 𝐸 ≤ 𝑁 − 𝑓 gives ready and delivery by step three under all 𝑓 faults. After a fast delivery at 𝑇 with a Byzantine broadcaster, 𝑄 − 𝑡 ≥ 𝑁 −𝑏 − 𝑓 + 1 ≥ 𝐸 honest echoes are already sent; the last inequality is exactly 𝑏 ≤ ⌊𝑠/2⌋ + 1 at 𝑡 = 𝑓 − 1. They reach everyone by 𝑇 + 𝛿, causing ready, and delivery follows by 𝑇 + 2𝛿. A ready delivery leaves 𝑓 + 1 honest readies in transit and has the same bound by relay. Safety excludes earlier opposite readies. These arguments also give eventual totality. For an honest broadcaster, 𝑑𝑡H ≤ 𝑑𝑠 ≤ 3. Each party sends at most an echo and a ready multicast, besides the source proposal, proving the message bound, including precorruption and post-delivery sends. □ The baseline reaches the lower-bound premise 𝑏 ≥ 𝑠 + 1 only at 𝑠 = 0. Thus the seven-party matching instance already follows from this simple protocol. Paired witnesses support larger budgets, including two and three at minimum resilience when these are admissible.

B.2

Paired-witness thresholds and message flow

Design rationale. Suppose the broadcaster is Byzantine and an honest party delivers 𝑣. If it delivered on 𝑄 echoes, at least 𝑄 −𝑡 ≥ 𝑀 honest parties echoed 𝑣; within one step every honest party holds

Nikita Polianskii

deliver on

𝐶 confirms confirm

𝐶

2𝑓 +1 readies

echo and confirm propose

echo deliver on 𝑄 echoes

deliver on

witness

𝑃 authors with 𝑅w

ready

𝑓 +1

𝑀

𝑅 vote

Figure 2: Message flow of Algorithm 1. Arrow labels give the number of distinct authors that trigger the next message; the witness rule counts authors whose echo and confirm slots both hold 𝑣, so it reads echo slots as well as confirm slots. Confirm also requires the author’s own echo. With an honest broadcaster every honest party has 𝑄 echoes after two steps when at most 𝑏 parties are Byzantine, and 𝐶 confirms after three. After a first honest delivery, the vote path (behind an echo delivery) or the witness path (behind a confirm delivery) produces readies within two steps and delivery within three.

those echoes and votes, the votes trigger ready, and ready triggers delivery, three steps in all. If it delivered on 𝐶 confirms, at least 𝐶 − 𝑡 ≥ 𝑃 honest parties confirmed 𝑣, and the natural analogue would let 𝑃 confirms trigger ready. That rule is unsafe. Take 𝑡 = 𝑓 −1 and 𝑏 ≥ 𝑠 + 2. The 𝑀 − 𝑡 honest echoes behind a vote for 𝑣 and the 𝐶 − 𝑡 honest echoes behind a confirm for 𝑤 ≠ 𝑣 fit disjointly among the 𝑁 −𝑡 honest non-broadcasters, because (𝑀 −𝑡)+(𝐶−𝑡) ≤ 𝑁 −𝑡 is exactly 𝑏 ≥ 𝑠 + 2; Byzantine echo slots complete both quorums; and the 𝑃 − 𝑡 honest confirmers of 𝑤 leave 𝑁 − 𝑃 = 2𝑓 − 1 ≥ 𝑅 − 𝑡 other honest parties free to vote for 𝑣, since 𝑏 ≥ 𝑠 + 2 forces 𝑓 ≥ 𝑠 + 3. So 𝑅 votes for 𝑣 and 𝑃 confirms for 𝑤 can both be assembled before any delivery. Opt-RBC inserts an acknowledgment round between votes and ready [17], and our confirm/ack protocol (Appendix E) routes both paths through such a round; either way the acknowledgment costs a step. The witness message instead certifies, at its own author, 𝑃 identities that have both echoed and confirmed 𝑣. Lemma 4.1 shows that a quorum of such witnesses rules out any 𝑅-vote quorum for another value, so witnesses may trigger ready directly. The budget cap 𝑏 ≤ ⌊𝑛/2⌋ − 𝑓 , which Theorem 8 of Shrestha et al. shows necessary for two-step optimism, enters precisely in 𝑄 + 𝑀 − 𝑁 > 𝑡. The hypothesis 𝑏 ≤ 2𝑠 + 3 enters precisely in the displayed inequality of Lemma 4.1; it is a restriction of this construction, not an impossibility bound on optimistic broadcast. The lower endpoint 𝑓 = 2 is permitted throughout the construction. The validity argument requires 𝑅w = 2𝑓 − 1 > 𝑓 , which fails at 𝑓 = 1: one faulty non-broadcaster can send a witness for a value different from an honest broadcaster’s input and trigger honest readies for that value. Thus the present rules do not extend to 𝑓 = 1.

B.3

Failure beyond the paired-witness budget

Proposition B.2 (Boundary of the fixed rules). Keep Algorithm 1 and thresholds (2). For every 2𝑠 + 4 ≤ 𝑏 ≤ min{𝑓 , ⌊𝑛/2⌋ − 𝑓 }, these rules admit an execution violating totality. Thus increasing their budget beyond 2𝑠 + 3 requires changing the protocol, not only its proof.

Proof. The range implies 𝑓 ≥ 3𝑠+7. Corrupt the source and 𝑓 −1 non-broadcasters. Partition the 2𝑓 + 𝑠 + 1 honest non-broadcasters into 𝑈 of size 𝑓 + 𝑠 + 1 and 𝑉 of size 𝑓 , and choose 𝑈 0 ⊂ 𝑈 of size 𝑓 − 1. The source proposes 𝑣 to 𝑈 and 𝑤 ≠ 𝑣 to 𝑉 . Partition faulty non-broadcasters into 𝑌 of size 𝑠 + 2 and 𝑋 of size 𝑓 −𝑠 − 3. Authors in 𝑌 echo and confirm 𝑣 to everyone; authors in 𝑋 echo 𝑣 to 𝑈 0 and 𝑤 elsewhere. Delivering the echoes makes 𝑈 0 hold 𝐶 echoes for 𝑣, vote and confirm 𝑣. Outside 𝑈 0 , there are 𝑓 + |𝑋 | = 2𝑓 − 𝑠 − 3 ≥ 𝑀 echoes for 𝑤 and only 𝑓 + 2𝑠 + 3 < 𝐶 for 𝑣, so schedule their votes for 𝑤. There are 𝑓 +𝑠 + 2 such honest voters. Supply the 𝑓 − 1 Byzantine 𝑤-votes to them; they reach 𝑅 and send ready for 𝑤. Delay those readies towards 𝑈 0 . Next deliver the confirms: every honest party has 𝑃 paired authors in 𝑈 0 ∪ 𝑌 and witnesses 𝑣. These witnesses make 𝑈 0 send ready for 𝑣 before the delayed readies arrive. All honest parties have now spent their unique ready: 𝑓 − 1 for 𝑣 and 𝑓 + 𝑠 + 2 for 𝑤. Give Byzantine readies for 𝑤 to just one honest party outside 𝑈 0 ; it reaches 2𝑓 + 1 readies and delivers. Deliver all remaining honest traffic and let faulty parties remain silent. Other parties cannot reach 2𝑓 + 1 readies for either value, since 𝑓 + 𝑠 + 2 < 2𝑓 + 1. No other delivery rule applies: 𝑄 > 𝐶, every echo count is at most 𝐶, and every confirm count is at most 𝑃 < 𝐶. Exactly one honest party delivers. All delays used before draining can be finite, so this is an eventual-totality failure. The first instance is (22, 7, 4). □

C

Coded paired-witness broadcast

We prove Proposition 5.1. Use a deterministic [𝑁 , 𝑘] MDS encoder over GF(2𝜔 ), where 𝑘 = 𝑃 = 𝑛 − 2𝑓 and 2𝜔 > 𝑁 . Bind the instance identifier, payload length, code parameters, and padding rule into a domain-separated Merkle commitment to the ordered fragment vector. A fragment has 𝐹 = 𝑤 ⌈𝐿/(𝑘𝑤)⌉ bits. A successful reconstruction erasure-decodes 𝑘 valid distinct-index fragments, checks padding, re-encodes the complete vector, and rebuilds the received root. Individually valid Merkle paths do not establish that a vector is a codeword. All claims below are conditional on commitment binding. Algorithm 2 gives the event loop; the packet rules below define admission and reference resolution. Counters 𝑒, 𝑣, 𝑐, 𝑤, 𝑟 count distinct authors of the indicated message type and root, and 𝑝 counts matched echo/confirm authors. Only echoes with available fragments enter 𝑒 or 𝑝. Packet rules. Use Algorithm 1 with roots as control values. The broadcaster preloads each non-broadcaster with that recipient’s own-index fragment and proof. Keep only the first valid preload from the authenticated broadcaster. Echo only after validating this packet. An echo supplies its author’s own-index fragment and proof, or references the identical fragment already multicast with its vote. Reserve the first well-formed echo notice per author; count it only once its matching valid fragment is available. A conflicting later root never replaces the reserved notice. Vote requires 𝑀 counted echoes and successful reconstruction. It supplies the voter’s re-encoded own-index fragment and proof unless that exact fragment was already multicast in its echo. Confirm requires 𝐶 counted echoes, the own-echo guard, and successful reconstruction. Witness and ready retain their original rules and carry roots only; they need not wait for local reconstruction. Every

Optimistic Reliable Broadcast in Three Steps

Algorithm 2: Coded paired witnesses at party 𝑖. Thresholds are those of Algorithm 1. State: immutable per-author/type root slots; first valid source preload; fragment cache; tested roots and successful decodings; per-type sent flags; own-fragment multicast flags indexed by root. Source initialization: encode the value, commit to its fragment vector, and send each non-source 𝑗 its indexed fragment and proof. On a source preload: accept only the first valid packet for index 𝑖; cache it and, if 𝑖 is a non-source, emit echo for its root. On an eligible control packet: reserve its author’s first well-formed root for its type; ignore conflicting later roots. For echo/vote only, admit an attached fragment for this reserved root, at the author’s index, with a valid proof. Repeated matching packets can supply missing data. After either event: resolve references from the fragment cache and update counters. For each affected root 𝜌, apply the following enabled rules until none remain. Disable each send rule once its type was sent, and disable the delivery rule after delivery. If 𝜌 has 𝑘 distinct cached fragments and is untested, erasure-decode, check padding, re-encode and compare roots; cache success or failure. If 𝑖 is a non-source and 𝑒 (𝜌) ≥ 𝑀 and 𝜌 decoded successfully, emit vote for 𝜌. If 𝑖 is a non-source and 𝑒 (𝜌) ≥ 𝐶, its own echo is 𝜌, and 𝜌 decoded successfully, emit confirm for 𝜌. If 𝑖 is a non-source and 𝑝 (𝜌) ≥ 𝑃, emit witness for 𝜌. If 𝑣 (𝜌) ≥ 𝑅 or 𝑤 (𝜌) ≥ 𝑅w or 𝑟 (𝜌) ≥ 𝑓 + 1, emit ready for 𝜌. If 𝜌 decoded successfully and at least one of 𝑒 (𝜌) ≥ 𝑄, 𝑐 (𝜌) ≥ 𝐶, or 𝑟 (𝜌) ≥ 2𝑓 + 1 holds, deliver its payload once. Emit (𝜏, 𝜌): if type 𝜏 was already sent, do nothing. Otherwise mark it sent and multicast. Echo/vote attaches 𝑖’s fragment and proof unless already multicast for 𝜌, in which case it references that fragment. Confirm/witness/ready carries only the root. Count eligible self-messages immediately. Continue after delivery.

delivery additionally requires successful reconstruction and returns the resulting payload. Deduplication works in both directions: a party can vote before its broadcaster preload arrives and echo later. Keep a multicast-sent flag for each own-index/root pair, separately from the local cache. Buffer references that overtake their data and reconsider them when data arrives. An honest echo and its fragment were both sent by the echo’s send time, so both arrive within one delay of that time. Thus counted echo receipt preserves the full-value delay bound. A vote notice may be counted before its referenced fragment arrives. Reserve the first well-formed vote notice per author, as for echo. Admit a received fragment only for the retained broadcaster preload

or a reserved echo/vote root. A preload uses the recipient’s index; an echo/vote fragment uses its authenticated author’s index. Require fixed length, valid symbols, and a valid proof, and cache at most one fragment per index/root pair. A fragment-bearing echo/vote packet also supplies its notice, so data that overtakes a reference can reserve the corresponding slot. Use immutable first-root slots for the other message types as well. Safety and malformed codewords. The full-value safety proof applies to the root-level first-message ledgers; extra reconstruction guards restrict honest sends without enabling any new one. A noncodeword commitment cannot pass reconstruction and full root checking. It cannot obtain an honest vote or confirm. Every honest witness has an honest confirmer among its paired authors. Every honest ready origin has an honest vote or an honest witness behind it; ready relays preserve this fact by causal induction. Thus a noncodeword cannot originate honest ready, and it cannot be delivered on raw echoes because delivery checks reconstruction separately. For a valid root, binding and encoder injectivity make all successful decoders return the same payload. Root agreement therefore gives payload agreement. Availability at every deadline. Since 𝑀 −𝑘 = 𝑓 −𝑏 ≥ 0 and 𝐶, 𝑄 ≥ 𝑘, honest-broadcaster reconstruction requires no extra message step. The two- and three-step good cases follow as in Lemma 4.3. For a Byzantine broadcaster, let 𝑡 ≤ 𝑓 − 1 be the faulty nonbroadcaster count and 𝑇 the first honest delivery time. An echo delivery leaves 𝑄 − 𝑡 ≥ 𝑀 ≥ 𝑘 honest own-index fragments already multicast. By 𝑇 +𝛿 everyone has them, can reconstruct and vote, and the usual vote/ready chain completes by 𝑇 + 3𝛿. A confirm delivery leaves 𝐶 − 𝑡 ≥ 𝑃 = 𝑘 honest confirmers, each of whom already echoed its own fragment. Their fragments and paired messages reach everyone by 𝑇 + 𝛿, enabling reconstruction and witness; delivery follows by 𝑇 + 3𝛿. For a ready delivery, trace the first honest ready of its root to a nonrelay origin at time 𝑇orig ≤ 𝑇 . A vote origin has at least 𝑅 − 𝑡 ≥ 𝑘 + 1 honest vote authors, each of whom already multicast its own-index fragment. A witness origin has an honest witness and hence an honest confirmer; that confirmer’s 𝐶 echoes contain at least 𝐶 − 𝑡 ≥ 𝑘 honest own-index fragments already multicast. In either case 𝑘 honest fragments were sent before 𝑇orig . They reach every honest party by 𝑇orig + 𝛿 ≤ 𝑇 + 𝛿, so the ready-relay delivery by 𝑇 + 2𝛿 is not delayed by payload reconstruction. The argument also proves asynchronous eventual availability without a known delay bound. Accounting. There are 𝑁 broadcaster fragments. With an honest broadcaster, every honest echo and vote has the same root, so symmetric deduplication permits one fragment multicast per nonbroadcaster. Payload traffic is at most 𝑁 𝐹 +𝑁 2 𝐹 = 𝑛𝑁 𝐹 . Universally, each non-broadcaster can multicast at most two fragments, one for each of its one-shot echo/vote roots. Even charging an honest preload before a later broadcaster corruption gives 𝑁 (2𝑁 + 1)𝐹 . Since 𝑁 /𝑘 < 3, the leading coefficients are below 3𝑛𝐿 and 6𝑛𝐿. Merkle proofs, control roots, and 𝐹 − 𝐿/𝑘 < 𝜔 = 𝑂 (log 𝑛) padding add 𝑂 (𝜅𝑛 2 log 𝑛) bits. No repair message type is added; the message cap remains 5𝑁 2 + 2𝑁 and includes all post-delivery traffic.

Nikita Polianskii

First-root discipline permits at most 2𝑁 + 1 accepted distinct fragment entries at a receiver. Hence fewer than six roots can collect 𝑘 entries, since (2𝑁 + 1)/𝑘 < 6. Cache failed as well as successful reconstruction checks: a failure for a binding root cannot be repaired by receiving more fragments of that same root. At most five full decoding/re-encoding attempts per receiver suffice, in addition to per-packet proof checks. This bounds work on admitted records and the number of expensive reconstructions; proof validation is polynomial per packet. It does not bound total processing of an unbounded Byzantine packet stream or measure decoding time in practice. Communication baselines. The linear payload order is established prior work. Opt-RBC v4 already gives a balanced coded protocol with 𝑂 (𝑛𝐿+𝜅𝑛 2 log 𝑛) bits [17, Section 5 and Figure 3]. At 𝑛 = 3𝑓 +1, its outer dimension is 𝑓 + 1; counting both echo and vote fragment multicasts as written gives a leading upper bound 6𝑛𝐿 plus 𝑂 (𝐿) payload. Deduplicating identical echo/vote fragments reduces the honest-broadcaster leading bound to 3𝑛𝐿, while retaining the universal 6𝑛𝐿 upper bound. These are our direct counts of those rules, not communication lower bounds or additional source theorems. Our corresponding 3𝑛𝐿/6𝑛𝐿 bounds therefore do not improve that optimized payload comparison; the gain is preserving the pairedwitness latency guarantees. Other hash-only broadcasts have smaller metadata terms. Das, Xiang, and Ren report 7𝑛𝐿 + 2𝜅𝑛 2 + 2𝑛 2 bits for their RBC, including its four-round version [8, Section 8]. CC-BRB reports 3𝑛𝐿 + 9𝜅𝑛 2 , omitting lower-order terms, with a three-step honest-broadcaster path [3, Table I and Section V]. These source-reported constants use minimum resilience and their own accounting conventions; they are not claims of two-step optimistic delivery. Our 𝑂 (𝜅𝑛 2 log 𝑛) Merkle remainder is larger asymptotically. The purpose of this appendix is timely availability for (2, 3, 3), not an improvement to the communication frontier.

D

Consensus latency consequences

Reliable broadcast latency enters a consensus protocol in two ways: the good-case latency bounds how long an honest proposal takes to arrive, and the totality delay bounds how far honest parties can drift apart, which sizes timeouts. Two existing signature-free protocols state their latencies as functions of the broadcast they use, so the effect of substituting Algorithm 1 for Opt-RBC can be read off. Table 5 does so. The Sailfish++ formulas are from Section 7 of Shrestha et al. [17] and the two non-leader classes of Yu et al.’s Table 2; the Simple-IT formulas are from its Lemmas 6–8 and 12 and Corollaries 3–5 [20]. Following Simple-IT, 𝛿 is the actual network delay bound after GST and Δ > 𝛿 its known bound; the broadcast protocols use neither. The entries in the last column are our substitutions, not results reported by those authors, and every commit path assumes the required honest leaders, resolved dependencies, and no intervening timeout. Sailfish++. Sailfish++ commits the leader vertex of round 𝑟 under its first rule after one RBC plus one step, the step being the arrival of the first RBC message of 2𝑓 + 1 round-(𝑟 + 1) vertices, and under its second rule after two RBCs [17, Section 7]. Non-leader vertices referenced by the next committed leader need one further RBC,

and the remaining ones two [20, Table 2]. In this honest-broadcast commit path “one RBC” is the optimistic or good-case latency, not the totality delay, and in Algorithm 1 the first RBC message is the proposal itself, as in Opt-RBC. This first-message argument uses the full-proposal interface; a coded instantiation must additionally expose the DAG metadata required by the commit rule. Substituting (2, 3, 3) lowers good-case leader commit from five steps to four and the two non-leader paths from nine and thirteen steps to seven and ten, while the optimistic entries are unchanged. This is path accounting for honest broadcasts; it is not a bound for arbitrary Byzantine vertices. The source’s timeout remark and Claim 23 analyze Bracha explicitly: 5Δ suffices after entry via the preceding leader’s delivery, and 8Δ after timeout-based entry [17, Section 7 and Appendix F, Claims 19–23]. These constants include both round-entry skew and subsequent honest broadcasts. They are not generic timeout formulas for an arbitrary RBC. We therefore do not substitute our latency triple into those numerical constants or claim a Sailfish++ timeout improvement here; the timer and view-duration improvements in Table 5 concern Simple-IT, whose analysis explicitly parameterizes the RBC.

Simple-IT. Lemma 12 of Yu et al. [20] bounds round-entry skew: if an honest party enters round 𝑟 at time 𝑡 ≥ GST, every honest party has entered that round by 𝑡 + 𝑑𝑡 𝛿. Entry requires each preceding round to be marked safe through proposal delivery or disabled through timeout notification. The evidence already obtained by the first party reaches all others within the larger of the two totality delays. Timeout notification takes at most 2𝛿, so 𝑑𝑡 ≥ 2 makes RBC totality the controlling bound. With paired witnesses, this gives 3𝛿 in place of Opt-RBC’s 4𝛿. This bounds the time to reach the same round, not the difference in round numbers or an unconditional rate of DAG growth. Simple-IT’s base variant proposes upon delivery and sets its round timer to Δto = (𝑑𝑠 + 𝑑𝑡 )Δ, with eventual worst-case view duration Δto +𝑑𝑡 𝛿 [20, Lemma 8 and Corollary 5]. Substituting (2, 3, 3) gives 6Δ and 6Δ+3𝛿 in place of 8Δ and 8Δ+4𝛿; Bracha gives 5Δ and 5Δ +2𝛿. For the optimistic entries we state the premise under which we claim them: every honest party can validate the proposal’s predecessor chain within 2𝛿 of the honest proposal time, for instance because the chain is already resolved, and the round is eligible and has not timed out; block time additionally assumes consecutive honest leaders. Under this premise commit takes (𝑑𝑜 + 1)𝛿 = 3𝛿 and block time 𝑑𝑜 𝛿 = 2𝛿 [20, Lemma 6 and Corollary 4]. Without it, combining proposal delivery with predecessor propagation gives (max{𝑑𝑜 , 𝑑𝑡 } + 1)𝛿 = 4𝛿 for paired witnesses, which is also the good-case bound since 𝑑𝑠 = 𝑑𝑡 = 3. The same premise is marked for the Opt-RBC column. The two-step block time concerns the base variant, not the speculative pipelining of its Lemma 9.

Optimistic budgets. Simple-IT’s optimistic fault budget 𝑓𝑜 = ⌊𝑛/2⌋ − 𝑓 (its Definition 9 and Table 3) equals 𝑏 ∗ and corresponds to ⌈𝑛/2⌉ + 𝑓 correct parties including the leader. Paired witnesses keep this budget where 𝑏 ∗ ≤ 2𝑠 + 3 and reduce it otherwise.

Optimistic Reliable Broadcast in Three Steps

Table 5: Consensus latency with three reliable broadcast protocols. Commit and block-time rows are multiples of 𝛿; skew, timer, and view rows are as written. In an 𝑎/𝑏 entry, 𝑎 is the optimistic value with 𝑑 = 𝑑𝑜 and 𝑏 the good-case value with 𝑑 = 𝑑𝑠 . Starred optimistic entries assume the predecessor-readiness premise stated in the text. The paired-witness column requires 𝑓 ≥ 2 and has budget min{𝑏 ∗, 2𝑠 + 3} in place of Opt-RBC’s 𝑏 ∗ ; at 𝑛 = 3𝑓 + 1 this is at most min{3, ⌊(𝑓 + 1)/2⌋} faults.

E

Metric (formula)

Bracha

Opt-RBC

Paired witness

RBC (𝑑𝑜 , 𝑑𝑠 , 𝑑𝑡 )

(3, 3, 2)

(2, 4, 4)

(2, 3, 3)

Sailfish++ commit paths, 𝑛 = 3𝑓 + 1 Leader, rule 1 (𝑑 + 1) Leader, rule 2 (2𝑑) Non-leader, next-leader path (2𝑑 + 1) Non-leader, later-reference path (3𝑑 + 1)

4 6 7 10

3/5 4/8 5/9 7 / 13

3/4 4/6 5/7 7 / 10

Base Simple-IT (propose upon delivery) Commit (𝑑𝑜 + 1 / 𝑑𝑠 + 1) Optimistic block time (𝑑𝑜 ) Round-entry skew (𝑑𝑡 𝛿) Round timer ((𝑑𝑠 + 𝑑𝑡 )Δ) View duration (Δto + 𝑑𝑡 𝛿)

4 3 2𝛿 5Δ 5Δ + 2𝛿

3∗ /5 2∗ 4𝛿 8Δ 8Δ + 4𝛿

3∗ /4 2∗ 3𝛿 6Δ 6Δ + 3𝛿

Confirm/ack construction and analysis

This appendix gives our confirm/ack construction, which retains maximal optimism for every 𝑛 ≥ 3𝑓 + 1. It uses a separate ack layer and can require four steps after the first honest delivery. We give the construction, prove safety and latency, and then establish its exact fault-dependent totality profile at 𝑛 = 3𝑓 + 1, including smaller optimistic budgets.

E.1

Construction and thresholds

Let 𝑛 ≥ 3𝑓 + 1, 𝑓 ≥ 1, and 𝑁 = 𝑛 − 1. We describe one protocol with three thresholds: 𝑀 for votes, 𝐶 for confirms and for the ack and ready quorums, and 𝑄 for delivery on echoes. Fix an integer optimistic threshold 0 ≤ 𝑏 ≤ 𝑓 and assume 𝑓 < 𝑀 ≤𝐶 ≤ 𝑁 − 𝑓, 𝑄 +𝑀 ≥ 𝑁 + 𝑓, 𝐶 + 𝑀 > 𝑁,

2𝐶 ≥ 𝑁 + 𝑓 , 𝑄 − (𝑓 − 1) ≥ 𝑀,

𝑄 ≤ 𝑁 −𝑏. (4)

𝐶 − (𝑓 − 1) ≥ 𝑓 + 1,

These are the hypotheses of the safety and latency lemmas in Sections E.2–E.4; the last condition provides enough honest echoes for two-step delivery with at most 𝑏 Byzantine parties. They imply 𝑄 ≥ 𝑀 > 𝑓 and 2𝑄 ≥ 𝑄 + 𝑀 ≥ 𝑁 + 𝑓 . Table 6 says what each inequality is used for. Lemma E.1 (Admissible thresholds). For every 𝑓 ≥ 1, 𝑛 ≥ 3𝑓 + 1, and integer 0 ≤ 𝑏 ≤ min{𝑓 , ⌊𝑛/2⌋ − 𝑓 }, the thresholds   𝑁 +𝑓 , 𝑄 = 𝑁 − 𝑏, 𝑀 = min{𝐶, 𝑛 − 𝑓 − 𝑏} (5) 𝐶= 2 satisfy (4). At 𝑛 = 3𝑓 + 1 and 𝑏 = ⌊(𝑓 + 1)/2⌋ they equal 𝐶 = 2𝑓 , 𝑄 = 3𝑓 − 𝑏, and 𝑀 = 2𝑓 + 1 − 𝑏. Proof. By definition 𝑀 ≤ 𝐶, 2𝐶 ≥ 𝑁 + 𝑓 , and 𝑄 = 𝑁 − 𝑏. If 𝑁 = 3𝑓 then 𝐶 = 2𝑓 = 𝑁 − 𝑓 ; otherwise 𝐶 ≤ (𝑁 + 𝑓 + 1)/2 ≤ 𝑁 − 𝑓 because 𝑁 ≥ 3𝑓 + 1. Also 𝐶 ≥ 2𝑓 , hence 𝐶 − (𝑓 − 1) ≥ 𝑓 + 1. Since 𝐶 ≥ 2𝑓 > 𝑓 and 𝑛− 𝑓 −𝑏 ≥ 𝑛−2𝑓 ≥ 𝑓 +1, we have 𝑀 > 𝑓 , including when 𝑏 = 0. The bound on 𝑏 gives 𝐶 ≥ 𝑓 + 𝑏 and 𝑛 − 𝑓 − 𝑏 ≥ 𝑓 + 𝑏, so 𝑀 ≥ 𝑓 + 𝑏 and 𝑄 + 𝑀 ≥ (𝑁 − 𝑏) + (𝑓 + 𝑏) = 𝑁 + 𝑓 . Also

Algorithm 3: Reliable broadcast with thresholds satisfying (4). Broadcaster with input 𝑣: send ⟨propose, 𝑣⟩. Non-broadcaster: upon the first ⟨propose, 𝑣⟩ from the broadcaster: send ⟨echo, 𝑣⟩. 2 upon ⟨echo, 𝑣⟩ from 𝑀 non-broadcasters: send ⟨vote, 𝑣⟩. 3 upon ⟨echo, 𝑣⟩ from 𝐶 non-broadcasters: send ⟨confirm, 𝑣⟩. 4 upon ⟨vote, 𝑣⟩ from 𝐶 non-broadcasters, or ⟨confirm, 𝑣⟩ from 𝑓 +1 non-broadcasters: send ⟨ack, 𝑣⟩. 1

Every party: upon ⟨ack, 𝑣⟩ from 𝐶 non-broadcasters, or ⟨ready, 𝑣⟩ from 𝑓 +1 parties: send ⟨ready, 𝑣⟩. 6 upon ⟨echo, 𝑣⟩ from 𝑄 non-broadcasters, or ⟨confirm, 𝑣⟩ from 𝐶 non-broadcasters, or ⟨ready, 𝑣⟩ from 2𝑓 +1 parties: deliver 𝑣. 5

𝑀 ≤ 𝑛 − 𝑓 −𝑏 = 𝑄 − 𝑓 + 1. If 𝑀 = 𝐶 then 𝐶 + 𝑀 = 2𝐶 ≥ 𝑁 + 𝑓 > 𝑁 ; otherwise 𝑀 = 𝑛 − 𝑓 − 𝑏 and 𝐶 + 𝑀 − 𝑁 = 𝐶 − 𝑓 − 𝑏 + 1 ≥ 1. The values at 𝑛 = 3𝑓 + 1 follow by substitution. □ Algorithm 3 lists the rules and Figure 3 shows the message flow. Only non-broadcasters send echo, vote, confirm, and ack; these quorums count distinct non-broadcasters. Every party, including the broadcaster, sends ready and delivers; ready quorums count all 𝑛 parties. Each rule fires at most once per party, and “send” means send to all parties. The examples below use 𝑛 = 3𝑓 + 1 with the maximal 𝑏. Why an ack is triggered by 𝑓 +1 confirms. Two natural alternatives for the confirm trigger of the ack rule are the 2𝑓 echoes used by

Nikita Polianskii

deliver on 𝑄 echoes

deliver on

deliver on

𝐶 confirms

2𝑓 +1 readies 𝑓 +1

𝐶 propose

confirm

echo

𝐶 ack

ready

Algorithm 3 all seven honest non-broadcasters ack 𝐴 upon the four honest confirms, including the three that voted for 𝐵, and every honest party delivers within three further steps.

𝑓 +1 vote

𝑀

𝐶

Figure 3: Message flow of Algorithm 3. Arrow labels give the number of distinct senders that trigger the next message. The vote, ack, ready path is the recovery path of Shrestha et al.; confirm and delivery on 𝐶 confirms are new. With an honest broadcaster, every honest party has the echoes after two steps and the confirms after three, and delivers on the echoes already after two steps when at most 𝑏 parties are Byzantine.

Table 6: Roles of the threshold inequalities. When the broadcaster is Byzantine, any 𝑓 non-broadcasters include an honest party. Condition

Role in the proof

𝑓 <𝑀 ≤𝐶 ≤ 𝑁 −𝑓

Votes and confirms rest on an honest echo; honest echoes and confirms suffice in the good case.

2𝐶 ≥ 𝑁 + 𝑓

Two confirm quorums, or two ack quorums, share an honest party; a delivery on confirms excludes every conflicting vote quorum.

𝑄 +𝑀 ≥ 𝑁 +𝑓

A delivery on echoes excludes conflicting honest votes and confirms.

𝑄 − 𝑓 +1 ≥ 𝑀

A delivery on echoes leaves enough honest echoes to trigger votes everywhere.

𝐶 +𝑀 > 𝑁

Counting only the first echo from each party, no honest party can confirm one value and vote for another.

Why the ack layer cannot be bypassed. One might remove ack and send ready directly upon 2𝑓 votes or 𝑓 + 1 confirms, keeping ready amplification and the three delivery rules. This modification also fails at 𝑛 = 10, 𝑓 = 3. Let the broadcaster and two non-broadcasters be Byzantine, and split the honest echoes as four for 𝐴 and three for 𝐵. Choose two of the four 𝐴 echoers. To these two, the Byzantine non-broadcasters echo 𝐴; delivering six echoes for 𝐴 makes both vote and confirm 𝐴. To the other five honest parties, the Byzantine non-broadcasters echo 𝐵; delivering the three honest and two Byzantine echoes for 𝐵 makes all five vote 𝐵. Each receiver counts only the first echo from each sender, so delivering every remaining honest echo changes none of these choices. There are now two honest confirms for 𝐴 and five honest votes for 𝐵. The two Byzantine non-broadcasters send confirms for 𝐴, and one sends a vote for 𝐵. Selective scheduling gives four honest parties the four confirms for 𝐴 first, and the other three the six votes for 𝐵 first. In the modified protocol they respectively send ready for 𝐴 and 𝐵. The three Byzantine parties send ready for 𝐴 only to one of the four 𝐴-ready parties, which delivers on seven readies. They send nothing further. After all honest messages are delivered, the other parties have only four readies for 𝐴 and three for 𝐵, and each has already sent its one ready. No echo or confirm delivery quorum exists there. Totality fails. The ack layer permits these conflicting preliminary choices but requires a unique quorum of six acks before any ready is seeded. This example concerns that particular shortcut, not a lower bound on the number of message types of every reliable broadcast protocol.

E.2

𝐶 − 𝑓 +1 ≥ 𝑓 +1

A delivery on confirms leaves enough honest confirms to trigger acks everywhere.

𝑄 ≤ 𝑁 −𝑏

Honest echoes suffice for two-step delivery with at most 𝑏 Byzantine parties.

Shrestha et al. and the requirement that the ack sender itself voted for 𝑣. Both break totality. Let 𝑛 = 10 and 𝑓 = 3, so 𝑏 = 2 and the thresholds are 5 for vote, 6 for confirm, ack, and ready, and 7 for delivery on echoes. The broadcaster and two non-broadcasters are Byzantine. The broadcaster proposes 𝐴 to four honest parties and 𝐵 to the other three. The Byzantine non-broadcasters echo 𝐴 to the first group and 𝐵 to the second. The first group receives six echoes for 𝐴 and votes and confirms 𝐴. The second group receives five echoes for 𝐵 and votes for 𝐵, but has only four echoes for 𝐴 and never confirms. Deliver the four honest confirms for 𝐴 everywhere, and the two Byzantine confirms for 𝐴 to one party of the first group, which delivers 𝐴 on six confirms. The Byzantine parties now send nothing. Under either alternative rule only the four members of the first group can ack 𝐴, fewer than six, so no honest party ever sends ready, and the six other honest parties never deliver. In

Safety

Throughout this subsection, the thresholds satisfy the shared hypotheses of Section E.1. If the broadcaster is Byzantine, at most 𝑓 − 1 of the 𝑁 non-broadcasters are Byzantine. Thus the inequalities 2𝐶 ≥ 𝑁 + 𝑓 , 𝑄 + 𝑀 ≥ 𝑁 + 𝑓 , and 2𝑄 ≥ 𝑁 + 𝑓 make the corresponding quorums intersect in an honest party. Honest means never corrupted; Section 2 permits adaptive choice of the corrupted set. Lemma E.2 (Honest broadcaster). If the broadcaster is honest and invoked with 𝑣, every honest echo, vote, confirm, ack, and ready message is for 𝑣, no honest party delivers before the invocation, and every honest party that delivers delivers 𝑣. Proof. An honest echo answers the broadcaster’s proposal, so it is for 𝑣 and follows the invocation. Consider the honest messages in the order in which they are sent. A vote needs 𝑀 > 𝑓 echoes and a confirm needs 𝐶 > 𝑓 echoes, so each includes an honest echo, which is for 𝑣. An ack needs 𝐶 > 𝑓 votes or 𝑓 + 1 confirms, so it includes an honest vote or confirm. A ready needs 𝐶 acks, including an honest ack, or 𝑓 + 1 readies, including an earlier honest ready. By induction all these messages are for 𝑣 and follow the invocation. Each delivery rule needs more than 𝑓 messages of one type, hence an honest one, so every honest delivery is of 𝑣 and follows the invocation. □

Optimistic Reliable Broadcast in Three Steps

For the rest of this section the broadcaster is Byzantine. The lemmas concern the entire execution, not only the events after a delivery.

Table 7: Upper bounds after the first honest delivery at𝑇 , with a Byzantine broadcaster. “+𝑘” means by 𝑇 + 𝑘𝛿. All entries concern full-value delivery in the confirm/ack protocol.

Lemma E.3 (A confirm excludes a vote). An honest party that sends ⟨confirm, 𝑣⟩ never sends ⟨vote, 𝑤⟩ for 𝑤 ≠ 𝑣, whichever of the two messages it sends first.

First delivery

𝑄 echoes 𝑄 − 𝑓 + 1 ≥ 𝑀 echoes 𝐶 confirms 𝐶 − 𝑓 + 1 ≥ 𝑓 + 1 confirms 2𝑓 + 1 readies 𝑓 + 1 readies

Proof. It holds ⟨echo, 𝑣⟩ from 𝐶 non-broadcasters and counts only the first echo from each party. A vote for 𝑤 would need ⟨echo, 𝑤⟩ from 𝑀 further non-broadcasters, and 𝐶 + 𝑀 > 𝑁 . □ Lemma E.4 (Confirms agree; delivery on echoes excludes conflicting votes). All honest confirms are for the same value. If some honest party has received ⟨echo, 𝑣⟩ from 𝑄 non-broadcasters, then no honest party sends ⟨vote, 𝑤⟩ or ⟨confirm, 𝑤⟩ for 𝑤 ≠ 𝑣. Proof. Two honest confirms rest on two sets of 𝐶 echo senders, which share at least 𝑓 non-broadcasters by (4), including an honest one. That party sends one echo, so the two confirms are for the same value. An echo quorum of 𝑄 for 𝑣 and a vote quorum of 𝑀 for 𝑤 likewise share at least 𝑓 non-broadcasters, including an honest one, so 𝑣 = 𝑤. A confirm for 𝑤 rests on 𝐶 ≥ 𝑀 echoes for 𝑤, so the same argument applies to it. □ Lemma E.5 (Early delivery excludes conflicting honest acks). Suppose some honest party has received ⟨echo, 𝑣⟩ from 𝑄 nonbroadcasters or ⟨confirm, 𝑣⟩ from 𝐶 non-broadcasters. Then every honest ack in the execution, whether sent before or after that event, is for 𝑣. Proof. In the echo case, Lemma E.4 excludes honest votes and confirms for other values. Both triggers of the ack rule contain an honest vote or confirm, so no honest party acks another value. In the confirm case, at least 𝐶 − (𝑓 − 1) of the confirm senders are honest. By Lemma E.3 none of them ever votes for 𝑤 ≠ 𝑣, so a vote quorum for 𝑤 would have to consist of 𝐶 of the remaining 𝑁 − (𝐶 − 𝑓 + 1) non-broadcasters. This is impossible because 𝑁 − (𝐶 − 𝑓 + 1) < 𝐶 follows from 2𝐶 ≥ 𝑁 + 𝑓 . A set of 𝑓 + 1 confirms for 𝑤 would contain an honest confirm for 𝑤, contradicting Lemma E.4. Hence neither trigger of the ack rule fires for 𝑤 at an honest party, at any time. □ Lemma E.6 (Ack qorums and readies agree). If honest parties receive ⟨ack, 𝑣⟩ from 𝐶 non-broadcasters and ⟨ack, 𝑤⟩ from 𝐶 nonbroadcasters, then 𝑣 = 𝑤. Every honest ready is for this value, and every honest ready is preceded, in causal order, by an honest ready sent upon 𝐶 acks. Proof. The two ack quorums share at least 𝑓 non-broadcasters, including an honest one, who sends a single ack. Now consider an honest ready. If it was sent upon 𝑓 + 1 readies, one of those is an honest ready sent earlier. Following such predecessors, which are strictly earlier in the execution, we reach an honest ready sent upon 𝐶 acks, and all readies along the way carry its value. Every such starting ready carries the unique ack-quorum value. □ Theorem E.7 (Agreement and validity of deliveries). Algorithm 3 satisfies agreement, and each honest party delivers at most

Honest messages sent by 𝑇

General 𝑡 = 1 +4 +3 +2

+1 +1 +2

once. If the broadcaster is honest, every honest delivery is of its input value and follows its invocation. Eventual delivery is proved in Section E.3. Proof. The delivery rule fires at most once per party. Lemma E.2 gives validity of deliveries and agreement with an honest broadcaster. Let the broadcaster be Byzantine and consider two honest deliveries, of 𝑣 and 𝑤. Two echo quorums share an honest party by (4), so two deliveries on echoes agree. A delivery on confirms includes an honest confirm, so two deliveries on confirms agree by Lemma E.4, and a delivery on echoes and one on confirms agree by the same lemma. Two deliveries on readies include honest readies and agree by Lemma E.6. Finally, let 𝑣 be delivered on echoes or confirms and 𝑤 on readies. By Lemma E.5 every honest ack is for 𝑣; an ack quorum contains an honest ack, so by Lemma E.6 every honest ready, including those in the ready quorum for 𝑤, is for 𝑣. Hence 𝑣 = 𝑤. □

E.3

Liveness, latency, and communication

Throughout this subsection the thresholds satisfy (4). The number 𝑡 of Byzantine parties counts every party corrupted during the execution. Lemma E.8 (Good case). If the broadcaster is honest and invoked at time 𝑆, every honest party delivers by 𝑆 + 3𝛿. If moreover at most 𝑏 parties are Byzantine, every honest party delivers by 𝑆 + 2𝛿. Proof. Every honest non-broadcaster receives the proposal and echoes by 𝑆+𝛿. There are at least 𝑁 −𝑓 ≥ 𝐶 honest non-broadcasters, and their echoes reach every party by 𝑆 + 2𝛿. By Lemma E.2 no honest party has voted or confirmed another value, so every honest non-broadcaster confirms 𝑣 by 𝑆 + 2𝛿. These at least 𝐶 confirms reach every party, including the broadcaster, by 𝑆 + 3𝛿, and the delivery rule on 𝐶 confirms fires. If at most 𝑏 parties are Byzantine, at least 𝑁 − 𝑏 ≥ 𝑄 honest echoes reach every party by 𝑆 + 2𝛿, and the delivery rule on echoes fires. □ Lemma E.9 (Totality delay). If the first honest delivery happens at time 𝑇 , every honest party delivers by 𝑇 + 4𝛿. Table 7 gives the bound for each delivery rule. Proof. With an honest broadcaster, 𝑇 ≥ 𝑆 by Lemma E.2 and every honest party delivers by 𝑆 + 3𝛿 ≤ 𝑇 + 3𝛿 by Lemma E.8. Let the broadcaster be Byzantine and let 𝑣 be the value delivered at 𝑇 . Delivery on echoes. At least 𝑄 − 𝑓 + 1 ≥ 𝑀 honest parties have echoed 𝑣 by 𝑇 , and these echoes reach every honest party by 𝑇 + 𝛿. By Lemma E.4 no honest party has voted for another value, so all honest non-broadcasters, at least 𝑛 − 𝑓 of them, vote for 𝑣 by 𝑇 + 𝛿.

Nikita Polianskii

Their votes reach everyone by 𝑇 + 2𝛿; by Lemma E.5 no honest ack went to another value, so all honest non-broadcasters ack 𝑣 by 𝑇 + 2𝛿. These at least 𝑛 − 𝑓 > 𝐶 acks reach everyone by 𝑇 + 3𝛿; by Lemma E.6 no honest ready went to another value, so every honest party sends ⟨ready, 𝑣⟩ by 𝑇 + 3𝛿, and at least 𝑛 − 𝑓 ≥ 2𝑓 + 1 honest readies reach every honest party by 𝑇 + 4𝛿. Delivery on confirms. At least 𝐶 − 𝑓 + 1 ≥ 𝑓 + 1 honest parties have confirmed 𝑣 by 𝑇 . Their confirms reach every honest nonbroadcaster by 𝑇 + 𝛿 and trigger ⟨ack, 𝑣⟩ there, whatever that party voted for; Lemma E.5 excludes an earlier ack for another value. All honest parties therefore send ready by 𝑇 + 2𝛿 and deliver by 𝑇 + 3𝛿. Delivery on readies. At least 𝑓 + 1 honest parties have sent ⟨ready, 𝑣⟩ by 𝑇 . These readies reach every honest party by 𝑇 + 𝛿 and trigger its ready if it has not sent one; by Lemma E.6 no honest ready went to another value. At least 𝑛 − 𝑓 ≥ 2𝑓 + 1 honest readies reach everyone by 𝑇 + 2𝛿. By Theorem E.7 all these deliveries are of 𝑣. If the first delivery satisfies several rules, each applicable bound holds. □ Theorem E.10 (Full-value protocol). Under (4), Algorithm 3 is an asynchronous reliable broadcast protocol against adaptive corruption of at most 𝑓 parties, and it uses no cryptography beyond authenticated channels. Its optimistic good-case latency is at most two steps with threshold 𝑏, its good-case latency at most three, and its totality delay at most four. The messages sent by parties while they follow the protocol number at most (5(𝑛 − 1) + 2)(𝑛 − 1) and carry 𝑂 (𝑛 2 (𝐵 + log 𝑛)) bits in every execution, including messages after delivery and executions without delivery. Proof. Agreement and the correctness of delivered values are Theorem E.7. The arguments of Lemmas E.8 and E.9 are chains of finitely many message transmissions between honest parties, each of which completes under eventual receipt and fair processing; they therefore prove eventual delivery for an honest broadcaster and totality for any broadcaster, and under the timing assumption of Definition 2.2 they give the stated bounds. For correctness and latency, fix the set of at most 𝑓 parties ever corrupted; their entire transcripts are admissible Byzantine behavior, and the other parties obey the rules throughout, so every quorum argument above applies unchanged. For the message bound, each non-broadcaster sends at most one message of each of five types to each of the 𝑛 − 1 other parties while it follows the protocol, and the broadcaster sends at most its proposal and one ready. A message has 𝐵 + 𝑂 (log 𝑛) bits: the value, the type, and the party and instance identifiers. Since each type is sent at most once, these bounds hold whether or not parties deliver. □

under all 𝑓 faults [2, Theorem 4], and Theorem 8 of Shrestha et al. excludes optimistic thresholds above ⌊(𝑛 − 2𝑓 )/2⌋ = ⌊𝑛/2⌋ − 𝑓 in this range [17]. Neither bound concerns the totality delay or communication. If 𝑛 ≥ 4𝑓 , then min{𝑓 , ⌊𝑛/2⌋ − 𝑓 } = 𝑓 , and the two-step guarantee of Theorem E.10 covers every fault pattern. □ Remark E.12. At 𝑛 = 3𝑓 + 1, 𝑓 = 1, the maximal threshold is 𝑏 = 1, and every threshold on non-broadcasters equals 2, so a party may deliver on echoes at the moment it votes and confirms. Continued processing after delivery is needed for totality already in this smallest case.

E.4

Exact fault-dependent totality

We first refine the upper bound in terms of the actual number of faults, then give matching executions at minimum resilience. Throughout this subsection the thresholds satisfy (4). Lemma E.13 (Fault-dependent totality). Assume 𝑏 ≥ 1, and let 𝑡 ≤ 𝑓 be the number of parties ever corrupted. If the first honest delivery is at 𝑇 , every honest party delivers by 𝑇 + 𝑈 (𝑡)𝛿, where  1, 𝑡 = 0,      2, 𝑡 = 1,  𝑈 (𝑡) =  3, 2 ≤ 𝑡 ≤ 𝑄 − 𝐶 + 1,     4, max{1, 𝑄 − 𝐶 + 1} < 𝑡 ≤ 𝑓 .  Empty ranges are omitted. These are upper bounds for this protocol. If the broadcaster is Byzantine and 𝑡 = 1, the echo and confirm branches each take at most one further step; only the ready branch uses the two-step bound.

Corollary E.11 (Maximal optimistic threshold). For 3𝑓 +1 ≤ 𝑛 ≤ 4𝑓 − 1, the thresholds of Lemma E.1 with 𝑏 = ⌊𝑛/2⌋ − 𝑓 give the optimal good-case latency three and two-step optimistic good-case latency under the largest 𝑏 that any signature-free protocol admits. For 𝑛 ≥ 4𝑓 , 𝑏 = 𝑓 is admissible and gives good-case latency two under all 𝑓 faults. Theorem 5.2 follows from Theorem E.10 with these thresholds.

Proof. If 𝑡 = 0, every message in the first delivery’s echo, confirm or ready quorum was sent by an honest party by 𝑇 . The same quorum reaches every party by 𝑇 + 𝛿, so all deliver on that rule. An honest broadcaster gives the absolute deadline 𝑆 + 2𝛿 when 𝑡 ≤ 𝑏, and 𝑆 + 3𝛿 otherwise. Since 𝑇 ≥ 𝑆 and 𝑏 ≥ 1, these imply the claimed relative bounds for 𝑡 ≥ 1. Suppose the broadcaster is Byzantine, so 𝑡 ≥ 1 and at most 𝑡 − 1 non-broadcasters are Byzantine. A first delivery on 𝑄 echoes contains at least 𝑄 − 𝑡 + 1 honest echoes, all received everywhere by 𝑇 + 𝛿. If 𝑡 ≤ 𝑄 − 𝐶 + 1, there are at least 𝐶 of them: every honest non-broadcaster confirms by 𝑇 + 𝛿, since by Lemma E.4 none has confirmed another value, and everyone delivers on confirms by 𝑇 + 2𝛿. Otherwise Lemma E.9 gives four steps. A first delivery on confirms always has the three-step bound, and one on readies the two-step bound. When 𝑡 = 1, every non-broadcaster is honest. All 𝑄 echoes, or all 𝐶 confirms, behind a delivery on echoes or confirms were therefore sent to everyone and arrive by 𝑇 + 𝛿, so everyone delivers on the same rule within one step. The ready branch keeps the bound two, which gives 𝑈 (1) = 2. □

Proof. In the first range 𝑏 < 𝑓 , so it is the largest value permitted by Lemma E.1; there 𝑀 = ⌈𝑛/2⌉. The good-case lower bound of Abraham, Ren, and Xiang requires 𝑛 ≥ 4𝑓 for two-step delivery

Proposition E.14 (Exact confirm/ack totality profile). For Algorithm 3 with the thresholds of Lemma E.1, at 𝑛 = 3𝑓 + 1, 𝑓 ≥ 1 and any 1 ≤ 𝑏 ≤ ⌊(𝑓 + 1)/2⌋, the supremum of the totality delay

Optimistic Reliable Broadcast in Three Steps

over executions with exactly 𝑡 Byzantine parties is  1, 𝑡 = 0,      2, 𝑡 = 1,  𝐷 𝑓 ,𝑏 (𝑡) =  3, 2 ≤ 𝑡 ≤ 𝑓 − 𝑏 + 1,     4, 𝑓 − 𝑏 + 2 ≤ 𝑡 ≤ 𝑓 .  Empty ranges are omitted. This statement does not assert optimality among reliable broadcast protocols. Proof. Lemma E.13 gives the upper bounds. We give matching executions with 𝛿 = 1, writing 𝐶 = 2𝑓 , 𝑄 = 3𝑓 − 𝑏 and 𝑀 = 2𝑓 + 1 − 𝑏. Except for the transmissions specified below, every honest message arrives after one time unit, including messages sent after delivery; self-messages are immediate. Byzantine parties send only the specified messages. Zero-delay transmissions can instead be arbitrarily short for the supremum claim. No faults. Invoke the broadcaster at zero. Give its proposal to 𝑄 non-broadcasters immediately and to the others at time one. Choose 𝑝 among the first group and deliver their echoes to 𝑝 immediately. Party 𝑝 delivers at zero, whereas the broadcaster receives its first echoes and delivers at one. One fault. Let one non-broadcaster be Byzantine. Give the honest proposal immediately to 𝑄 − 1 honest non-broadcasters and at time one to the other 𝑏 honest non-broadcasters. Deliver the first group’s echoes and the Byzantine party’s matching echo immediately to one of them, 𝑝. It delivers at zero. The broadcaster gets only 𝑄 − 1 echoes at time one and receives the remaining honest echoes at time two. Before time two it has only 𝑝’s confirm, insufficient for delivery; no earlier ready quorum exists. It therefore delivers at two. Three delays. Let 2 ≤ 𝑡 ≤ 𝑓 , including the broadcaster. Give a proposal only to a set 𝐼 of ℓ = 2𝑓 − 𝑡 + 1 honest parties, at zero. Deliver their echoes to every member of 𝐼 immediately, together with the 𝑡 − 1 Byzantine non-broadcasters’ matching echoes. Every member of 𝐼 has 𝐶 echoes, votes and confirms at zero. Choose 𝑝 ∈ 𝐼 ; deliver the ℓ honest confirms and 𝑡 − 1 Byzantine confirms to 𝑝 immediately; no other honest party receives Byzantine confirms. Party 𝑝 delivers and acks at zero. No fast delivery is possible, since only 𝐶 < 𝑄 matching echoes exist. At time one every honest party has the ℓ ≥ 𝑓 + 1 honest confirms and has sent its ack; these acks cause readies at two, and the readies cause delivery at three. Except at 𝑝, the ℓ < 𝐶 confirms never complete a direct-delivery quorum. Only 𝑝 acks before one, so no earlier ready quorum occurs. Four delays. Let 𝑓 − 𝑏 + 2 ≤ 𝑡 ≤ 𝑓 and fix 0 < 𝜀 < 1. The broadcaster and 𝑡 − 1 non-broadcasters are Byzantine. Put 𝑒 = 𝑄 − 𝑡 + 1, so 𝑀 ≤ 𝑒 < 𝐶. Give the proposal to one honest party 𝑝 at zero and to 𝑒 − 1 others at 1 − 𝜀. Deliver all their echoes to 𝑝 by 𝑇 = 1, together with the 𝑡 − 1 Byzantine echoes. It has 𝑄 echoes and delivers at 𝑇 , voting and confirming then. Everyone else completes the 𝑒 honest echoes at 2 − 𝜀 and votes then, but never confirms: 𝑒 < 𝐶. The single confirm from 𝑝 cannot trigger an ack. Before the other votes arrive, each such voter has at most its own vote and 𝑝’s, fewer than 𝐶 = 2𝑓 ; the nonempty four-delay range requires 𝑓 ≥ 3. The other votes complete the 𝐶-vote quorum at 3 − 𝜀, causing acks, then readies at 4 − 𝜀, and delivery at 5 − 𝜀. The gap is 4 − 𝜀. Every honest message has delay at most one in these executions. □

At maximal optimism, 𝑏 = 𝑏 ∗ = ⌊(𝑓 +1)/2⌋, four steps occur only above 𝑓 − 𝑏 ∗ + 1 faults. At 𝑛 = 7, 𝑓 = 2, 𝑏 = 1, the four-step range is empty. These matching executions establish tightness for our confirm/ack construction, not a lower bound for reliable broadcast in general.

Related documents

• Optimistic Reliable Broadcast in Three Steps#1201458
• Multi-network broadcasting within the Internet#208903
• Direct Broadcast Satellite-Radio, Space-Segment/Receiver Tradeoffs#499150
• From Bracha to Coded MBRB: Benchmarking Byzantine Reliable Broadcast Implementations#667992
• Strategic Information Transmission over Gossip Networks#997582