Amortized Asynchronous Byzantine Reliable Broadcast with Optimal Resilience

Amortized Asynchronous Byzantine Reliable Broadcast with Optimal Resilience

arXiv:2605.10372v1 [cs.DC] 11 May 2026

MICHAEL YIQING HU, National University of Singapore, Singapore HONG YAO ALVIN YAN, National University of Singapore, Singapore JIALIN LI, National University of Singapore, Singapore Byzantine Reliable Broadcast (BRB) is a fundamental primitive in distributed computing and cryptographic systems. Reducing the communication complexity of BRB protocols remains an important research direction. However, most work focuses on synchronous networks, with limited attention to the more challenging setting of network asynchrony. Achieving sub-quadratic communication for asynchronous BRB typically requires probabilistic approaches that sacrifice optimal 𝑓 = 𝑛3 resilience. In this work, we present a multi-shot BRB algorithm for asynchronous networks that maintains optimal resilience through an underutilized technique: amortization. Our protocol structures BRB across multiple rounds, where each round provides incremental additive guarantees. Once these initial rounds complete, each subsequent BRB instance requires only a single additional round. This amortization strategy achieves asymptotic optimal 𝑂 (𝑛|𝑚|) message complexity when messages are sufficiently large, with Ω(𝑛) round complexity in the worst case. Under favorable conditions, an optimistic delivery path reduces the round complexity to Ω(1).

1

Introduction

Byzantine Reliable Broadcast (BRB) serves as the cornerstone of many algorithms in distributed systems, spanning from Verifiable Secret Sharing (VSS) [7, 9, 10], Multi-Party Computation (MPC) [14, 25], and State Machine Replication (SMR) [15, 21, 26]. The BRB primitive ensures that any of the 𝑛 nodes may disseminate a message 𝑚 to the remainder of the nodes in the presence of 𝑓 corrupt/Byzantine nodes where Byzantine nodes may deviate arbitrarily from the protocol. BRB ensures that all honest (non-Byzantine) parties will agree on the sender’s message. Bracha’s BRB protocol [6] was the first algorithm that works in full asynchrony that tolerates 𝑓 < 𝑛/3 Byzantine faults. Bracha’s solution is information-theoretically secure (assuming signatures) with communication complexity of 𝑂 (𝑛 2 |𝑚|) where |𝑚| is the size of the message in bits. Dolev and Reischuk [17] also demonstrated that any deterministic BRB protocol requires at least Ω(𝑛 2 ) messages in the worst case. Various works [18, 28, 32] explore greater fault tolerance or improved message complexity in the synchronous setting. This work focuses on BRB in the asynchronous setting. Recent improvements to the communication complexity in the asynchronous setting typically involve capitalizing on one of the following: erasure codes and committee sampling. 1.1

Erasure Codes

AVID [8] demonstrated how erasure codes might improve communication complexity to 𝑂 (𝑛|𝑚| + 𝑘𝑛 2 log 𝑛) when utilized along with a collision-resistant hash function with an output size of 𝑂 (𝑘). These schemes typically decompose the original message into smaller fragments to reduce the total message cost to terminate. Nayak et al. [29] further improved the communication complexity to 𝑂 (𝑛|𝑀 | + 𝑛 2𝑘), terminating in 7 rounds. Those bounds were then improved by Alhaddad et al. [1], addressing the uneven distribution of load borne by Das et al. [16] to 𝑂 (𝑛|𝑚| + 𝑛𝑘 + 𝑛 2 log 𝑛). Notably, AVID[8] and Alhaddad et al. [1] all claim to be asymptotically optimal if |𝑚| > 𝑛 log 𝑛𝑘. Authors’ Contact Information: Michael Yiqing Hu, National University of Singapore, Singapore, [email protected]; Hong Yao Alvin Yan, National University of Singapore, Singapore, [email protected]; Jialin Li, National University of Singapore, Singapore, [email protected].

2

Michael Yiqing Hu, Hong Yao Alvin Yan, and Jialin Li

Although BRB optimizations utilizing coding schemes improve the worst-case communication complexity, the cost of all nodes fetching fragments in an attempt to reconstruct the message typically negates any cost savings [27]. Furthermore, overheads from encoding/decoding and verification degrade performance in real-world systems. As a result, many practical implementations [15, 16, 21] avoid coding schemes to optimize BRB communication. 1.2

Committee Sampling

An alternative line of work [2, 13, 20, 31, 33] takes the approach of uniformly sampling a committee 𝑁𝑐 of smaller size 𝑛𝑐 ≪ 𝑛 and performing consensus within this subset, after which the result is disseminated to the remaining nodes. However, these purely sample-based approaches [13, 33] face a fundamental trade-off between scalability and resilience. Because a small random sample is subject to statistical variance, maintaining a high probability of an honest majority within 𝑁𝑐 requires a larger margin of honest nodes in the global population. Consequently, protocols that achieve sub-quadratic communication via sampling typically forfeit optimal Byzantine resilience (𝑛 ≥ 3𝑓 + 1), while other sample-based approaches [2] revert to stronger forms of network synchrony, or both [22]. In this work we focus exclusively on achieving optimal resilience in network asynchrony. Recently, Shrestha and Kate [31] suggested a hybrid adaptation of Bracha’s two-phase BRB [6]. Their protocol first samples 𝑁𝑐 nodes while guaranteeing, with all but negligible probability 𝜀, that 𝑁𝑐 contains at least 𝑛2𝑐 honest nodes. The sender communicates 𝑚 to all nodes in 𝑁𝑐 , where a simple majority of confirmations ensures that some honest node in the system holds the message. Subsequently, an all-to-all communication phase involving all 𝑛 nodes is triggered to establish global agreement that the first phase has completed. Although this hybrid approach maintains optimal resilience and reduces the cost of the first phase, it does not address the quadratic bottleneck of the second phase, yielding a worst-case total communication cost of 𝑂 (𝑛𝑐2 |𝑚| + 𝑛 2𝑘 + 𝑛𝑐 𝑛|𝑚|). 1.3

Amortized Costs

As illustrated by Wan et al. [32], amortization remains a largely overlooked technique for improving multi-shot BRB, despite its potential to significantly reduce average system costs over sufficiently long protocol executions. Their work demonstrates that amortized 𝑂 (𝑘𝑛) communication complexity in 𝑂 (𝑛) rounds are achievable in the presence of an honest majority and network synchrony. Building on this foundation, Civit et al. [11] achieve similar bounds by leveraging a blacklisting approach that progressively excludes Byzantine behavior from the system. Notably, both [11, 32] techniques require network synchrony to operate. Further noted in [11, 12], amortization analysis for multi-shot tasks remains notably scarce in the literature, particularly in asynchronous settings. In this work, we apply an amortization approach in the asynchronous network model. 1.4

Our Contribution

In this work, we present an amortized probabilistic multi-shot Byzantine Reliable Broadcast algorithm with optimal resilience for the asynchronous network setting. Our algorithm uses another form of sampling to amortize the cost of the reliable broadcast to a single phase. This allows us to yield an amortized cost of 𝑂 (𝑛|𝑚| + 𝑛 2𝑘), where if |𝑚| > 𝑛𝑘, results in an asymptotic optimal complexity of 𝑂 (𝑛|𝑚|). To the best of our knowledge, our algorithm is the first asynchronous BRB algorithm utilizing sampling that achieves asymptotically optimal message complexity while having optimal resilience to Byzantine faults. Making it on par with prior works that utilize erasure codes [1, 16], while being more robust to network asynchrony.

Amortized Asynchronous Byzantine Reliable Broadcast with Optimal Resilience

3

Our algorithm also has a similar 𝑂 (𝑛) expected round cost to [32]. We also provide an optimistic delivery condition that terminates in a single round whilst maintaining the same amortized cost. Overview of the Paper. We will state the system model and preliminaries in Section 2. We will provide full details of our algorithm in Section 3, and proving its properties in Section 4. Next, the analysis of the communication and round complexities is provided in Section 5. Finally, we conclude the paper in Section 6. 2 2.1

Preliminaries Model and Assumptions

We consider a set of 𝑛 nodes: Π = {𝑝 1, · · · , 𝑝𝑛 }, each attempting to reliably broadcast a stream of messages. A static adversary may corrupt 𝑓 < 𝑛3 nodes prior to protocol execution. A static adversary is conventional for BRB algorithms that utilize sampling. Anikina et al.[2] enhanced their fault model to one that tolerates a slowly adaptive adversary but relies heavily on network synchrony. Although no formal proofs exist, we conjecture that sampling techniques and optimal resilience cannot be safely combined in the presence of strong adaptive adversaries. A non-corrupted party abides by the protocol and is considered to be honest. Nodes communicate with each other through message passing via an asynchronous network, where messages may be reordered or arbitrarily delayed but will be delivered eventually. We also make the following assumptions: • A public-key infrastructure (PKI) that supports a digital signature scheme, where every signature can be authenticated. • A collision resistant hash function H (𝑥) that takes an input 𝑥 and generates a fixed sized digest of length 𝑘. • A (𝑡, 𝑁 ′ ) threshold signature scheme [4, 5] set up via a trusted dealer or distributed key generation [5]. Each node in 𝑁 ′ may generate a signature share ⟨𝑚⟩𝑖 on a message. A set of 𝑡 distinct signature shares on the same message 𝑚 can be merged to form 𝑐𝑒𝑟𝑡 (𝑚) : |𝑐𝑒𝑟𝑡 (𝑚)| = |⟨𝑚⟩∗ | = 𝑘. • The adversary is computationally-bounded and is unable to break the digital signature scheme nor the hash function. 2.2

Problem Definition

This work focuses on the problem of Probabilistic Multi-shot Byzantine Reliable Broadcast, which consists of a sequence of single-shot Byzantine reliable broadcasts [6] (each with a success probability at least 1 − 𝜀) from a given node. Definition 2.1 (Byzantine Reliable Broadcast (BRB)). A Byzantine Reliable Broadcast with a designated sender and input value 𝑚 must satisfy the following properties: • Agreement: If two distinct honest nodes call Deliver(𝑚 ′ ) and Deliver(𝑚 ′′ ), respectively, then 𝑚 ′ = 𝑚 ′′ . • Validity: If the designated sender is honest, then all honest nodes eventually call Deliver(𝑚). • Totality: If an honest node calls Deliver(𝑚), all honest nodes eventually call Deliver(𝑚). We now define our central goal, achieving a Probabilistic Multi-shot Byzantine Reliable Broadcast algorithm: Definition 2.2 (Probabilistic Multi-shot Byzantine Reliable Broadcast ). A Probabilistic Multi-shot Byzantine Reliable Broadcast with a designated sender 𝑃𝑖 with input value 𝑚 for some round 𝑟 ∈ N satisfies the following properties with probability at least 1 − 𝜀 (where 𝜀 is a negligible constant):

4

Michael Yiqing Hu, Hong Yao Alvin Yan, and Jialin Li

• Agreement: If two distinct honest nodes call Deliver𝑖 (𝑚 ′, 𝑟 ) and Deliver𝑖 (𝑚 ′′, 𝑟 ), respectively, then 𝑚 ′ = 𝑚 ′′ . • Validity: If the designated sender is honest, then all honest nodes eventually call Deliver𝑖 (𝑚, 𝑟 ). • Totality: If an honest node calls Deliver𝑖 (𝑚, 𝑟 ), all honest nodes eventually call Deliver𝑖 (𝑚, 𝑟 ). • Completion Sequentiality: If an honest node calls Deliver𝑖 (·, 𝑟 ) where 𝑟 > 1, then it must be able to call Deliver𝑖 (·, 𝑟 − 1) eventually. Note that our definition deviates slightly from the multi-shot BRB definition of Wan et al. [32]. Specifically, we define our broadcast protocol around a designated sender, whereas [32] declares a series of “slots” (analogous to our rounds) that may be filled by possibly distinct senders. However, to maintain the sequential and causal broadcast invocations required by many cryptographic protocols that assume a broadcast channel [3, 19, 30], we retain a slightly modified notion of Sequentiality [32]. In the original formulation, sequentiality ensures that a particular instance of BRB for a round must terminate before BRB for the next round may begin. We modify this property to ensure that broadcasts by a given node must terminate in strictly sequential rounds—that is, rounds 1, 2, 3, . . . in ascending order, with no reordering permitted. Amortized Measurement. Communication complexity is measured as the number of bits sent by honest nodes. In this work, we adapt the definition of amortized complexity from Wan et al. [32]. Definition 2.3 (Amortized Communication Complexity). Let 𝐶 (𝑟, 𝑛, 𝑓 ) be the communication complexity of a Probabilistic Multi-shot Byzantine Reliable Broadcast protocol where for a designated sender 𝑝𝑖 ∈ Π, |Π| = 𝑛, some honest node calls Deliver𝑖 (·, 𝑟 ) in the presence of 𝑓 Byzantine nodes. The amortized communication complexity of the protocol is 𝑂 (𝑔(𝑛)) for some 𝑟 : 𝐶 (𝑟, 𝑛, 𝑓 ) = 𝑂 (𝑔(𝑛)) 𝑟 The key distinction is that we require that 𝑟 = 𝑂 (𝑛𝛼 ) for some 𝛼 ≥ 1. Since we use a probabilistic approach, this bound is necessary to ensure correctness with high probability; otherwise, a probabilistic protocol that runs indefinitely will eventually experience a failure. 3

Breakdown of Bracha’s BRB

Bracha’s BRB [6] operates in two phases—a structure that is optimal and consistently utilized by subsequent works. Each phase serves a distinct purpose that cannot be eliminated. In the first phase, the designated sender broadcasts a message 𝑚 to all nodes, and each recipient responds by broadcasting an echo message. Once a node receives 𝑛 − 𝑓 echo messages, it can guarantee that at least a simple majority of honest nodes have seen the message. However, a single phase is insufficient: due to network asynchrony, only some honest nodes may receive 𝑛 − 𝑓 echo messages, leading to inconsistent delivery decisions. Crucially the first phase prevents equivocation—the quorum intersection property ensures that two distinct messages cannot both complete this phase. This inadequacy necessitates a second, near-identical phase. Once a node receives 𝑛 − 𝑓 echo messages or 𝑓 + 1 vote messages, it broadcasts a vote message. Upon receiving 𝑛 − 𝑓 vote messages, an honest node will deliver the originally broadcast message 𝑚. This ensures that 𝑓 + 1 honest nodes have already broadcasted a vote message, enabling all honest nodes to eventually deliver, ensuring totality.

Amortized Asynchronous Byzantine Reliable Broadcast with Optimal Resilience

3.1

5

Optimizing Each Phase

Recent works [2, 13, 31, 33] have improved communication complexity by targeting the first (echo) phase. As described in Section 1.2, a smaller subset 𝑛𝑐 is sampled to provide a probabilistic guarantee that at least one honest node in the system will see the message, even under asynchrony. The responsibility for non-equivocation is then deferred to the subsequent phase. However, the second (vote) phase typically requires a 2𝑓 + 1 supermajority, and improving its communication complexity is non-trivial. Committee sampling techniques cannot be applied naively: a committee with an honest supermajority converges to size 𝑛 when operating with optimal resilience. Consequently, works [13, 33] that do improve this phase via committee sampling typically operate with suboptimal resilience. For example, Cohen et al. [13] was able to achieve 𝑂 (𝑛𝑙𝑜𝑔2𝑛) message complexity but required 𝑛 > 4𝑓 . 3.2

Our approach: Amortized Probabilistic Multi-shot Byzantine Reliable Broadcast

Our approach improves the communication complexity of BRB via amortization. More precisely, even under optimal resilience, it is possible to sample a subset 𝑁𝑐 of size 𝑛𝑐 that contains a ( 𝑛2𝑐 + 1) simple majority of honest nodes with probability at least 1 − 𝜀 (where 𝜀 is a negligible constant). Completing the first phase with 𝑁𝑐 ensures that, with the same probability, at least one honest node has witnessed the message. Our key insight is as follows: if we repeat the “first phase” with a different subset 𝑁𝑐′ on the 2𝑓 same message, there is a 2𝑓 +1 probability that 2 distinct nodes have witnessed and asserted that there exists a single unique message. By repeating this process sufficiently many times (𝜑), we can guarantee with probability at least 1 − 𝜀 that 𝑓 + 1 distinct honest nodes have made the same assertion, ensuring non-equivocation on the message. By allowing each repetition to be the start of another message broadcast, we can effectively amortize the cost of each instance to a single “first phase”. We dub our algorithm as Amortized Probabilistic Multi-shot BRB (APM-BRB), and describe it in parts: Algorithms 1 to 4. The algorithm progresses in rounds, where each node 𝑃𝑖 attempts to reliably broadcast their message 𝑚𝑖𝑟 to Π. Besides 𝑟 = 1, a designated sender 𝑃𝑖 sends a message 𝑚𝑖𝑟 for round 𝑟 > 1, once it has obtained 𝑛2𝑐 + 1 unique signature shares, it may generate a ( 𝑛2𝑐 + 1, 𝑁𝑐 ) threshold signature (or cert(𝑚𝑖𝑟 −1 )) for the message it has sent in the previous round (lines (1-10)). As a result, each honest node is creating a causal chain of messages. Each message also contains some additional metadata (prev{},triggers[]) of size 𝑛𝑘. When another honest node 𝑃 𝑗 receives a message (𝑚𝑖𝑟 , 𝑟, 𝑖), it checks whether it should participate in this committee by invoking the public sampleCommittee() function (Algorithm 1). A trusted dealer or DKG can be used to setup a threshold signature scheme for the committee. If neither is available, the certificate can be replaced with an non-aggregated multi-signature (note that the resultant metadata still remains as 𝑂 (𝑛𝑘)). If 𝑃 𝑗 has not already received another message from 𝑃𝑖 for the same round, it will perform another check utilizing the syncMsg() function (Algorithm 1). This function manipulates a memory object, promises[], which stores a list of messages for each node in Π. Most importantly, once an honest node writes a particular message into promises[𝑖] [𝑟 ], it is immutable. This immutability ensures that an honest node will not participate in a particular instance of the “first phase”, if the message’s chain equivocates with its own memory. In other words, Byzantine nodes might create distinct chains; however, each honest node will only aid in extending one of them.

6

Michael Yiqing Hu, Hong Yao Alvin Yan, and Jialin Li

Algorithm 1 Data structures and basic utilities for 𝑃𝑖 1: Local variables: 2: triggers[]: array of 𝑛 pairs of certificates and round numbers, initialized with null. 3: promises[][]: array of 𝑛 lists where promises[𝑗] is a sequential list of consecutive messages ordered by round from 𝑃 𝑗 . 4: seed0 : value provided by a trusted dealer at protocol start. 5: function sampleCommittee(node_id, 𝑟 ) 6: Input: Node identifier node_id, round 𝑟 Output: Subset 𝑁𝑐 ⊆ Π of size 𝑛𝑐 7: seed ← H (seed0 ∥𝑟 ∥node_id); 𝑁𝑐 ← ∅ 8: for 𝑘 = 1 to 𝑛𝑐 do 9: idx ← (seed mod 𝑛) + 1 ⊲ Map seed to node index in [1, 𝑛] 10: 𝑁𝑐 ← 𝑁𝑐 ∪ {𝑃 idx }; seed ← H (seed) ⊲ Hash seed for next selection 11: end for 12: return 𝑁𝑐 13: end function 14: function fetchMsg(𝑟, 𝑖, 𝑁𝑐 ) 15: Input: Round 𝑟 , node identifier 𝑖, source set 𝑁𝑐 ⊆ Π 16: Output: Message 𝑚𝑟𝑖 from party 𝑃𝑖 17: 𝑡 ← |promises[𝑖 ] | 18: if 𝑡 < 𝑟 then 19: for 𝑦 = 𝑡 + 1 to 𝑟 do 20: if 𝑦 = 1 then 21: request 𝑚𝑖𝑦 from 𝑁𝑐 22: else 23: request 𝑚𝑖𝑦 from 𝑁𝑐 with valid cert(𝑚𝑖𝑦−1 ) ∈ 𝑚𝑖𝑦 24: end if 25: wait until message 𝑚𝑖𝑦 is received 26: promises[𝑖 ] [𝑦 ] ← 𝑚𝑖𝑦 27: end for 28: end if 29: return promises[𝑖 ] [𝑟 ] 30: end function

⊲ Current number of messages from 𝑃𝑖

31: function syncMsg(𝑟, 𝑖) 32: return fetchMsg(𝑟, 𝑖, sampleCommittee(𝑖, 𝑟 ) ) 33: end function 34: function reqMsg(𝑟, 𝑖) 35: return fetchMsg(𝑟, 𝑖, {𝑃𝑖 } ) 36: end function

APM-BRB has 2 possible Deliver() conditions. The first condition describes the common case (Algorithm 3): once 𝑃 𝑗 receives a certificate (cert(𝑚𝑖𝑟 ) or 𝑛2𝑐 + 1 valid signature shares) for a message sent by 𝑃𝑖 in round 𝑟 : 𝑟 ≥ 𝜑, it works backwards to derive the message for 𝑚𝑖𝑟 −𝜑 . Regardless if this chain equivocates with 𝑃 𝑗 ’s promises[𝑖], since such a certificate exists, it indicates that with probability at least 1 − 𝜀, a set of 𝑓 + 1 unique honest nodes have endorsed 𝑚𝑖𝑟 −𝜑 by having it in their respective promises[𝑖] [𝑟 − 𝜑]. This is sufficient to deliver 𝑚𝑖𝑟 −𝜑 (more precisely to call Deliver𝑖 (𝑚𝑖𝑟 −𝜑 , 𝑟 − 𝜑)), as by the quorum intersection property, another set of 𝑓 + 1 honest nodes that endorses another message for round 𝑟 − 𝜑 and 𝑃𝑖 cannot exist. The second condition describes an optimistic case (Algorithm 4): when an honest node obtains 𝑛 messages from each node in a single round, and discovers that a particular message 𝑚𝑟𝑗 −1 is referenced in every set of prev{}. The node can be sure that no other message from 𝑃 𝑗 in round

Amortized Asynchronous Byzantine Reliable Broadcast with Optimal Resilience

7

Algorithm 2 APM-BRB (Sending Routine) 1: For a sender 𝑃𝑖 with input 𝑚𝑟 for round 𝑟 : ⊲ Message sent by each node every round 2: if 𝑟 = 1 then 3: 𝑁𝑐 ← sampleCommittee(𝑖, 1) 4: 𝑚𝑖1 ← {message, 𝑖, ·, ·, triggers[ ] } 5: 6: send (𝑚𝑖1 , 𝑟, 𝑖 ) to all parties in 𝑁𝑐 7: else 8: 𝑁𝑐 ← sampleCommittee(𝑖, 𝑟 ) 9: invoke reqMsg(𝑟 − 1, 𝑗 ) for all 𝑗 ∈ [𝑛] concurrently; wait for 2𝑓 + 1 to complete 10: J ← the set of 2𝑓 + 1 nodes 𝑗 whose reqMsg(𝑟 − 1, 𝑗 ) completed first 11: prev{ } ← {cert(promises[ 𝑗 ] [𝑟 − 1] ) : 𝑗 ∈ J } ⊲ 2𝑓 + 1 certs from distinct nodes in promises[] 12: 𝑚𝑟𝑖 ← {message, 𝑖, cert(𝑚𝑟𝑖 −1 ), prev{ }, triggers[ ] } 13: send (𝑚𝑟𝑖 , 𝑟, 𝑖 ) to all parties in 𝑁𝑐 14: end if 15: 16: For a node 𝑃 𝑗 (each node in 𝑛): 17: upon receiving (𝑚𝑟𝑖 , 𝑟, 𝑖 ) do 18: 𝑁𝑐∗ ← sampleCommittee(𝑖, 𝑟 ) 19: if 𝑃 𝑗 ∉ 𝑁𝑐∗ or already received (𝑚𝑟′𝑖 , 𝑟 ) s.t. 𝑚𝑟′𝑖 ≠ 𝑚𝑟𝑖 then 20: ignore 21: else 22: if cert(𝑚𝑟𝑖 −1 ) is the ( 𝑛2𝑐 + 1, 𝑁𝑐 ) threshold signature of syncMsg(𝑟 − 1, 𝑖 ) then 23: send ( ⟨𝑚𝑟𝑖 ⟩ 𝑗 , 𝑟, 𝑖, 𝑗 ) to all nodes in 𝑛 24: else 25: ignore 26: end if 27: end if

𝑟 − 1 may receive the sufficient 𝜑 chain of certificates to be delivered, ensuring that if any node calls Deliver 𝑗 (𝑚 ′, 𝑟 − 1), then 𝑚 ′ = 𝑚𝑟𝑗 −1 . Upon witnessing these conditions, a node can simply call Deliver 𝑗 (𝑚𝑟𝑗 −1, 𝑟 − 1). Since every honest node’s messages will be delivered by all honest nodes eventually, all nodes will eventually witness 𝑚𝑟𝑗 −1 in the prev{} of at least 2𝑓 + 1 delivered messages from round 𝑟 . Therefore, if an honest node has delivered with lines (1-13) of Algorithm 4, then all honest nodes will eventually be able to deliver the message with lines (15-25). 4

Correctness of APM-BRB

In this section, we will formally prove that APM-BRB satisfies Definition 2.2, assuming that 𝜑 and 𝑛𝑐 are chosen sufficiently. We will demonstrate discrete pessimistic bounds for the values of 𝜑, 𝑛𝑐 in Theorem 5.1 and Lemmas 5.2 and 5.4. For brevity, we will assume, throughout the rest of this section, that for every round 𝑟 , the committee sampled has a majority of honest nodes. We also assume that for any round 𝑟 , for all rounds in between 𝑟 and 𝑟 + 𝜑, at least 𝑓 + 1 honest nodes sign at least one message in these 𝜑 rounds. We will prove later that these assumptions hold with probability at least 1 − 𝜀. Lemma 4.1. Deliver Condition 1 of APM-BRB satisfies Agreement with probability at least 1 − 𝜀. Proof. Suppose that for some round 𝑟 , an honest node calls Deliver𝑖 (𝑚𝑖𝑟 , 𝑟 ) when cert(𝑚𝑖𝑟 +𝜑 ) is received. From lines (1-5) of Algorithm 3, there must exist a chain of messages spanning from 𝑚𝑖𝑟 to 𝑚𝑖𝑟 +𝜑 where each message 𝑚𝑖𝑣 : 𝑣 ∈ (𝑟, 𝑟 + 𝜑] contains a valid certificate/threshold signature for 𝑚𝑖𝑣−1 . In each round, when an honest node in the committee signs the message, by the definition of

8

Michael Yiqing Hu, Hong Yao Alvin Yan, and Jialin Li

Algorithm 3 APM-BRB (Deliver Condition 1) 1: For each node in Π: 2: upon receiving ( ⟨𝑚𝑟𝑖 ⟩ 𝑗 , 𝑟, 𝑖, 𝑗 ) from 𝑛2𝑐 + 1 distinct nodes in 𝑁𝑐 ← sampleCommittee(𝑖, 𝑟 ) do 3: cert(𝑚𝑟𝑖 ) ← a ( 𝑛2𝑐 + 1, 𝑁𝑐 ) threshold signature for 𝑚𝑟𝑖 4: ProcessCertificate(𝑖, 𝑟, cert(𝑚𝑟𝑖 )) 5: upon Deliver𝑖 (𝑚, 𝑟 ) do 𝑗 6: for each (cert(𝑚𝑟 ′ ), 𝑟 ′ ) ∈ 𝑚.triggers[ 𝑗 ] that is not null do 𝑗 7: ProcessCertificate(𝑗, 𝑟 ′ , cert(𝑚𝑟 ′ )) 8: end for 9: 10: procedure ProcessCertificate(𝑖, 𝑟, 𝑐𝑒𝑟𝑡 ) 11: if 𝑟 ≥ 𝜑 then 12: 𝑣 ← 𝑟 ; 𝑡𝑒𝑚𝑝𝐶𝑒𝑟𝑡 ← 𝑐𝑒𝑟𝑡 13: if triggers[𝑖 ] = null or round in triggers[𝑖 ] < 𝑟 then 14: triggers[𝑖 ] ← (𝑐𝑒𝑟𝑡, 𝑟 ) 15: end if 16: while 𝑣 ≥ 𝑟 − 𝜑 do ⊲ Work backwards to get the certificate that should be delivered 17: 𝑁𝑐 ← sampleCommittee(𝑖, 𝑣) 18: obtain 𝑚𝑖𝑣 from 𝑁𝑐 s.t. 𝑡𝑒𝑚𝑝𝐶𝑒𝑟𝑡 is a ( 𝑛2𝑐 + 1, 𝑁𝑐 ) threshold signature for 𝑚𝑖𝑣 19: 𝑡𝑒𝑚𝑝𝐶𝑒𝑟𝑡 ← cert(𝑚𝑖𝑣−1 ) ∈ 𝑚𝑖𝑣 ; 𝑣 ← 𝑣 − 1 20: end while 21: for 𝑢 = 𝑟 − 𝜑 down to 1 do ⊲ Deliver everything that came before the certificate 22: 𝑁𝑐 ← sampleCommittee(𝑖, 𝑢 ) 23: obtain 𝑚𝑢𝑖 from 𝑁𝑐 s.t. 𝑡𝑒𝑚𝑝𝐶𝑒𝑟𝑡 is a ( 𝑛2𝑐 + 1, 𝑁𝑐 ) threshold signature for 𝑚𝑢𝑖 24: Deliver𝑖 (𝑚𝑢𝑖 , 𝑢 ) if not already delivered 25: 𝑡𝑒𝑚𝑝𝐶𝑒𝑟𝑡 ← cert(𝑚𝑢𝑖 −1 ) ∈ 𝑚𝑢𝑖 26: end for 27: end if 28: end procedure

syncMsg (Algorithm 1), either of the following holds: it has 𝑚𝑖𝑟 in its variable promises[𝑖] [𝑟 ], or it adds 𝑚𝑖𝑟 to promises[𝑖] [𝑟 ] (at line 16). To see why the first holds, suppose it has another message (𝑚 ′ )𝑟𝑖 , then in syncMsg it must have a message (𝑚 ′ )𝑟𝑖 +1 in promises[𝑖] [𝑟 + 1], as 𝑚𝑖𝑟 +1 contains a certificate for 𝑚𝑖𝑟 and not (𝑚 ′ )𝑟𝑖 . This argument can be repeated until round 𝑣. As we have that at least 𝑓 + 1 unique honest nodes must participate in signing for at least one of these 𝜑 many rounds, that means that at least 𝑓 + 1 unique honest nodes have 𝑚𝑖𝑟 in their local memory, i.e. promises[𝑖] [𝑟 ]. Suppose then that a different honest node calls Deliver𝑖 ((𝑚 ′ )𝑟𝑖 , 𝑟 ) when cert((𝑚 ′ )𝑟𝑖 +𝜑 ) is received. Then by similar argument, there must exist chain of 𝜑 messages that spans from (𝑚 ′ )𝑟𝑖 to (𝑚 ′ )𝑟𝑖 +𝜑 where each (𝑚 ′ )𝑖𝑣 contains a threshold signature for (𝑚 ′ )𝑖𝑣 , and therefore there must exist at least 𝑓 + 1 honest nodes that have (𝑚 ′ )𝑟𝑖 in their local memory. By the quorum intersection property, it is impossible that 𝑓 + 1 unique honest nodes have 𝑚𝑖𝑟 in their promises[𝑖] [𝑟 ], and another disjoint set of 𝑓 + 1 unique honest nodes that have (𝑚 ′ )𝑟𝑖 in their promises[𝑖] [𝑟 ]. Therefore, for any round 𝑟 , for two different honest nodes that calls Deliver𝑖 (𝑚𝑖𝑟 , 𝑟 ) and Deliver𝑖 ((𝑚 ′ )𝑟𝑖 , 𝑟 ), it holds that (𝑚 ′ )𝑟𝑖 = 𝑚𝑖𝑟 , satisfying agreement. □ Lemma 4.2. Deliver Condition 2 of APM-BRB satisfies Agreement with probability at least 1 − 𝜀. Proof. Consider when an honest node has delivered a message due to lines (1-13) of Algorithm 4. It must have received 𝑛 messages, each with cert(𝑚𝑟𝑗 ) in the prev{} set. This implies that all honest

Amortized Asynchronous Byzantine Reliable Broadcast with Optimal Resilience

9

Algorithm 4 APM-BRB (Deliver Condition 2) 1: For each node in Π 2: M ← ∅ 𝑗 3: upon obtaining cert(𝑚𝑟 ) for each 𝑃 𝑗 ∈ Π do 4: 𝑁𝑐 ← sampleCommittee( 𝑗, 𝑟 ) 𝑗 𝑗 𝑗 5: Collect 𝑚𝑟 from 𝑁𝑐 s.t. cert(𝑚𝑟 ) is the ( 𝑛2𝑐 + 1, 𝑁𝑐 ) threshold signature for 𝑚𝑟 𝑗 6: M ← M ∪ {𝑚𝑟 } 7: if | M | = 𝑛 then 8: for each cert(𝑚𝑟𝑖 −1 ) that exists in prev{ } of all 𝑚 ∈ M do 9: Deliver every undelivered message from 𝑃𝑖 up to round 𝑟 − 1 in promises[𝑖] 10: end for 11: end if 12: 13: For each node in Π 𝑗 14: upon Deliver 𝑗 (𝑚𝑟 , 𝑟 ) for 2𝑓 + 1 unique nodes 𝑗 do 𝑗 𝑗 15: for each cert(𝑚𝑟𝑖 −1 ) that appears in prev{ } ∈ 𝑚𝑟 of all 2𝑓 + 1 messages 𝑚𝑟 do 𝑖 16: 𝑡𝑒𝑚𝑝𝐶𝑒𝑟𝑡 ← cert(𝑚𝑟 −1 ) 17: for 𝑢 = 𝑟 − 1 down to 1 do 18: 𝑁𝑐 ← sampleCommittee(𝑖, 𝑢 ) 19: obtain 𝑚𝑢𝑖 from 𝑁𝑐 s.t. 𝑡𝑒𝑚𝑝𝐶𝑒𝑟𝑡 is the ( 𝑛2𝑐 + 1, 𝑁𝑐 ) threshold signature for 𝑚𝑢𝑖 20: Deliver𝑖 (𝑚𝑢𝑖 , 𝑢 ) if not already delivered 21: 𝑡𝑒𝑚𝑝𝐶𝑒𝑟𝑡 ← cert(𝑚𝑢𝑖 −1 ) ∈ 𝑚𝑢𝑖 22: end for 23: end for

nodes must have 𝑚𝑟𝑗 in their respective promises[ 𝑗] [𝑟 ]. Consider any different message, (𝑚 ′ )𝑟𝑗 , for node 𝑗 in round 𝑟 . By similar argument as Lemma 4.1, any such message (𝑚 ′ )𝑟𝑗 may never meet the threshold to obtain a valid certificate. Therefore, (𝑚 ′ )𝑟𝑗 will not be delivered by any honest node. Additionally, observe that if all honest nodes have identical messages for a node 𝑗 contained in their local memory for some round 𝑟 (that is, in promises[ 𝑗] [𝑟 ]), it must hold that all promises[ 𝑗] [𝑟 ] to promises[ 𝑗] [1] are identical as well. Therefore, since no equivocating messages may exist, delivering promises[ 𝑗] [𝑟 ] to promises[ 𝑗] [1] is safe and no honest node can deliver a different message. □ Lemma 4.3. APM-BRB satisfies Validity with probability at least 1 − 𝜀. Proof. Firstly, each node will be able to send a message every round. Since all honest nodes must have sent a message for round 1, each node must be able to complete reqMsg() from by querying 2𝑓 + 1 honest nodes eventually. This holds for all rounds. Consider any honest node 𝑃𝑖 . Recall that we have assumed that each committee of size 𝑛𝑐 has at least ( 𝑛2𝑐 + 1) of honest nodes. In round 𝑟 , this party of honest nodes will sign 𝑚𝑖𝑟 and thus forms a sufficient threshold to generate cert(𝑚𝑖𝑟 ). Now, for round 2, 𝑃𝑖 has cert(𝑚𝑖1 ) and can thus include it in 𝑚𝑟2 as in Algorithm 2 and send it to the committee, which also has sufficient honest nodes which sign the message and thus cert(𝑚𝑖2 ) can be formed. This repeats for all rounds. Therefore for any round 𝑟 , eventually every honest node can form cert(𝑚𝑟 ′ ), for all 𝑟 ≤ 𝑟 ′ ≤ 𝑟 + 𝜑 and so all honest nodes will be able to call deliver𝑖 (𝑚, 𝑟 ) via Algorithm 3. □ Lemma 4.4. APM-BRB satisfies Totality with probability at least 1 − 𝜀.

10

Michael Yiqing Hu, Hong Yao Alvin Yan, and Jialin Li

Proof. Consider the case that the sender 𝑖 is honest. Now, suppose some honest node calls deliver𝑖 (𝑚, 𝑟 ). This implies that this honest node has the message 𝑚 and the certificate cert(𝑚𝑖𝑟 +𝜑 ). Since messages are eventually delivered, all honest nodes will eventually also obtain all the certificates for messages between rounds 𝑟 and 𝑟 + 𝜑. By argument identical to Lemma 4.4, all honest nodes will eventually call deliver𝑖 (𝑚, 𝑟 ) and satisfying totality. Consider the case where the sender 𝑃𝑖 is Byzantine. Suppose some honest node calls deliver𝑖 (𝑚, 𝑟 ), it will also perform lines 13-14 of Algorithm 3 where it updates its own triggers[] with cert(𝑚𝑖𝑟 +𝜑 ) that caused it to perform deliver𝑖 (𝑚, 𝑟 ). By validity, the next message it sends (which will include cert(𝑚𝑖𝑟 +𝜑 ) as part of triggers[]) will eventually be delivered by all honest nodes. Therefore, all honest nodes will eventually perform lines 6-10 of Algorithm 3. Further, since at least one honest node must have received and signed the message sent by 𝑃𝑖 in each round between 𝑟 and 𝑟 + 𝜑, honest nodes can successfully retrieve the messages and eventually perform deliver𝑖 (𝑚, 𝑟 ). Therefore totality is satisfied. □ Lemma 4.5. APM-BRB satisfies Completion Sequentiality with probability at least 1 − 𝜀. Proof. When 𝑃 𝑗 calls deliver𝑖 (𝑚, 𝑟 ) for a message sent by 𝑃𝑖 where 𝑖 ≠ 𝑗, it recursively locates all messages previously sent by 𝑃𝑖 via the threshold signature embedded in 𝑚 (lines (21-25) of Algorithm 3 and lines (17-21) of Algorithm 4). Observe that for the certificate of the message for any round to exist, it must have been signed by at least one honest node in 𝑁𝑐 (for that round). Since sampleCommittee() is a public function, 𝑃 𝑗 can identify and query the nodes in 𝑁𝑐 , and is guaranteed to be able to eventually obtain the message 𝑚 ′ that 𝑃𝑖 sent in round 𝑟 − 1 from an honest node that participated in signing it. The authenticity of 𝑚 ′ can then be verified against the threshold signature contained in 𝑚. Consequently, 𝑃 𝑗 is able to invoke deliver𝑖 (𝑚 ′, 𝑟 − 1), thereby satisfying completion sequentiality. □ 5

Complexity Analysis of APM-BRB

In this section, we show that our choices of 𝑛𝑐 and 𝜑 are sufficient to give the probability of failure of our algorithm to be at most 𝜀. Namely, we prove the following. 𝑅 Theorem 5.1. Let 𝜑 = max(16𝑛, 16 ln( 2𝑅 𝜀 )) and 𝑛𝑐 = 18 ln 𝜀 . Then consider the execution of our protocol for a total of 𝑅 rounds. With probability at least 1 − 𝜀, for a designated sender 𝑃𝑖 , both the following holds. First, every committee has a majority of honest nodes. Second, for every selection of 𝜑 consecutive rounds, at least 𝑓 + 1 unique honest nodes must sign at least one message sent by 𝑃𝑖 among all of the rounds.

Throughout this section, for clarity, we denote the number of rounds our protocol runs as 𝑅. We first show that our choice of 𝑛𝑐 is sufficient, in particular, we ensure that the probability that any 𝜀 committee does not have a majority of honest nodes is at most 2𝑅 . Lemma 5.2. Consider an 𝜀 > 0. Let 𝑁 be a set of nodes sampled uniformly at random without 𝑛𝑐 replacement of size 𝑛𝑐 , where 𝑛𝑐 ≥ 18 ln( 2𝑅 𝜀 ). The probability that there are more than 2 byzantine 𝜀 nodes sampled in 𝑁 is at most 2𝑅 . Proof. Consider a uniform sample of 𝑛𝑐 nodes without replacement. Let 𝑋𝑖 be an indicator random variable that takes on 1 if the 𝑖th sampled node is honest, and 0 otherwise, and let 𝑋 = Í𝑛𝑐 𝑖=1 𝑋𝑖 .

Amortized Asynchronous Byzantine Reliable Broadcast with Optimal Resilience

11

As the number of honest nodes is 2𝑓 + 1 out of 3𝑓 total nodes, it holds that Pr[𝑋𝑖 = 1] ≥ 2/3. Therefore by linearity of expectation, 2𝑛𝑐 . 3 By applying the standard Hoeffding’s bound[23], which holds for sampling without replacement. E(𝑋 ) ≥

  𝑛𝑐 i 2(𝑛𝑐 /6) 2 Pr |𝑋 − E(𝑋 )| ≥ ≤ exp − 6 𝑛𝑐  𝑛  𝑐 ≤ exp − 18 Let 𝐵 be the event that at 𝑋 is less than 𝑛2𝑐 , that at least 𝑛2𝑐 byzantine nodes are sampled in the 𝜑 set 𝑁 . Then it is clear that Pr(𝐵) ≤ exp(− 𝑛18𝑐 ). As we have that 𝑛𝑐 ≥ 18 ln 2𝑅 , we have that h

𝑛𝑐 ) 18 2𝑅 ≤ exp(− ln ) 𝜀 𝜀 ≤ . 2𝑅 𝜀 Therefore, with probability at most 2𝑅 , we have that the sampled set consists of less than 𝑛2𝑐 𝜀 honest nodes. Thus with probability at least 1 − 2𝑅 , it has a simple majority of honest nodes. □ Pr(𝐵) ≤ exp(−

Now, suppose that every round indeed has a simple majority of honest nodes. We show that if we take a sufficient number of committees, we will have at least 𝑓 + 1 unique honest nodes whose signature of the message forms the threshold certificate in at least one of the rounds. Before we prove this, we will need a concentration bound on the sum of independent geometric random variables. Theorem 5.3 ([24]). Consider random variables 𝑋 1, ..., 𝑋𝑛 where 𝑋𝑖 is drawn from a geometric Í distribution with probability parameter 𝑝𝑖 and let 𝑋 = 𝑛𝑖=1 𝑋𝑖 . Then for any 𝜆 > 1, it holds that Pr(𝑋 ≥ 𝜆𝜇) ≤ exp(−𝑝 ∗ 𝜇 (𝜆 − 1 − ln 𝜆)) where 𝜇 := E(𝑋 ) and 𝑝 ∗ = min1≤𝑖 ≤𝑛 𝑝𝑖 . Now, we show that if 𝜑 = 𝑂 (𝑛), then the number of committees is indeed sufficient. Lemma 5.4. Consider an 𝜀 > 0 and let 𝜑 ≥ 𝑚𝑎𝑥 (14𝑛, 16 ln 2𝑅 𝜀 ). Fix an honest node 𝑖 and consider 𝜑 many rounds of the protocol, where each committee has a majority of honest nodes. Then with 𝜀 probability at least 1 − 2𝑅 , there are at least 𝑓 + 1 unique honest nodes which sign at least one message sent from 𝑖 throughout these 𝜑 rounds. Proof. Fix some round 𝑟 and honest node node 𝑖. For 1 ≤ 𝑎 ≤ 𝑓 + 1, let 𝑌𝑎 be a random variable that denotes the number of rounds needed before the 𝑎th new honest node signs a message sent by 𝑖 within these 𝜑 rounds. Observe that 𝑌𝑎 is a geometric random variable where Í 2𝑓 +2−𝑎 Pr(𝑌𝑎 = 𝑘) = 𝑝𝑎 (1 − 𝑝𝑎 )𝑘 −1 for 𝑝𝑎 = 2𝑓 +1 . Let 𝑌 = 𝑎≤ 𝑓 +1 𝑌𝑎 . We have that 𝑛2 ≤ E(𝑌 ) ≤ 2𝑛, where the lower bound follows from the fact that clearly E(𝑌𝑎 ) ≥ 1 for all 𝑎. The upper bound 𝑓 +1 comes from the fact that min 𝑝𝑎 = 2𝑓 +1 ≥ 0.5, and so E(𝑌𝑖 ) ≤ 2 for all 𝑎.

12

Michael Yiqing Hu, Hong Yao Alvin Yan, and Jialin Li

By Theorem 5.3, we have that Pr(𝑌 ≥ 𝜆𝜇) ≤ exp(−0.5𝜇 (𝜆 − 1 − ln 𝜆)) where 𝜇 := E(𝑌 ). 8 2𝑅 Now, if it holds that ln 2𝑅 𝜀 < 𝑛, then fix 𝜆 ≥ 𝑛 ln 𝜀 . This, along with the fact that 𝜇 ≤ 2𝑛 gives Pr(𝑌 ≥ 16 ln

2𝑅 ) ≤ exp(−0.5𝜇 (𝜆 − 1 − ln 𝜆)) 𝜀    𝜆 ≤ exp −0.5𝜇 2   𝑛 4 2𝑅 ≤ exp − · ln 4 𝑛 𝜀 𝜀 ≤ . 2𝑅

(For large enough 𝜆) (As 𝜇 > 0.5𝑛)

Otherwise, if ln 2𝑅 𝜀 ≤ 𝑛, then by setting 𝜆 = 8, Pr(𝑌 ≥ 16𝑛) ≤ exp(−0.5𝜇 (7 − ln 8)) ≤ exp(−𝑛) (As 𝜇 > 0.5𝑛)   2𝑅 2𝑅 ≤ exp − ln (As ln < 𝑛) 𝜀 𝜖 𝜀 ≤ . 2𝑅 As 𝑌 is a random variable that denotes the number of rounds before 𝑓 + 1 unique honest nodes sign at least one of the messages in the 𝜑 consecutive rounds, this completes the proof of the lemma. □ Now, we can complete the proof of Theorem 5.1. Proof of Theorem 5.1. Observe that by Lemma 5.2 and the selection of 𝑛𝑐 , each committee has 𝜖 probability at most 2𝑅 that it does not have a simple majority of honest nodes. Therefore by taking union bound across 𝑅 rounds, every committee in the execution of our protocol has a majority of honest nodes with probability at least 1 − 𝜀2 . By Lemma 5.4 and the selection of 𝜑, for some rounds 𝑟 to 𝑟 +𝜑, if every committee has a majority of honest nodes, then it must be that at least 𝑓 + 1 unique honest nodes signed at least one of the 𝜀 messages from the sender 𝑖 with probability at least 1 − 2𝑅 . Taking union bound over at most 𝑅 many possible such consecutive sequence of 𝜑 rounds in 𝑅 rounds of our protocol, it holds that every such sequence of 𝜑 rounds has at least 𝑓 + 1 unique honest nodes have signed a message sent by 𝑃𝑖 , with probability at least 1 − 𝜀2 . Taking a union bound over the failure probability of the two above events suffices to prove the statement of the theorem. □ 5.1

Communication Cost Breakdown for APM-BRB

Let us now compute the communication cost of APM-BRB. A designated sender performs 𝑛 instances of reqMsg() before constructing its message to send: where the sender will query 𝑛 nodes to obtain at least 2𝑓 + 1 messages from the previous round. This incurs a cost of 𝑛 + 𝑛(|𝑚| + 𝑛𝑘). The designated sender incurs a cost of 𝑛𝑐 (|𝑚| + 𝑛𝑘) when sending its message along with 𝑛𝑘 bits of metadata (triggers[], prev{}) to a committee (lines 1 to 17 of Algorithm 2).

Amortized Asynchronous Byzantine Reliable Broadcast with Optimal Resilience

13

Each node in 𝑁𝑐 then runs syncMsg() incurring a cost of 𝑛𝑐2 + 𝑛𝑐2 (|𝑚| + 𝑛𝑘) before broadcasting its signature share to all nodes, incurring a cost of 𝑛𝑛𝑐 𝑘. The total cost of each round is therefore 𝑛 +𝑛(|𝑚| +𝑛𝑘) +𝑛𝑐 (|𝑚| +𝑛𝑘) +𝑛𝑐2 +𝑛𝑐2 (|𝑚| +𝑛𝑘) +𝑛𝑛𝑐 𝑘, which can be bounded by 𝑂 (𝑛|𝑚| + 𝑛 2𝑘 + 𝑛𝑐2 |𝑚| + 𝑛𝑛𝑐2𝑘) Recall that from Lemma 5.2, we have set 𝑛𝑐 = 𝑂 (log 𝑛), therefore the cost of each round can be bounded by 𝑂 (𝑛|𝑚| + 𝑛 2𝑘) For brevity, let Δ denote the cost of one round. For a particular message to complete reliable broadcast, a chain of 𝜑 certificates must be constructed. Therefore, the total cost to reliably broadcast the first message using APM-BRB is 𝜑 · Δ. Each subsequent reliable broadcast incurs only Δ per round. By Definition 2.3, the cost to broadcast 𝑟 messages is: 𝐶 (𝑟, 𝑛, 𝑓 ) = 𝜑 · Δ + 𝑟 · Δ Our amortized cost can be bounded by 𝐶 (𝑟, 𝑛, 𝑓 ) 𝜑 = ·Δ+Δ 𝑟 𝑟 As 𝑟 = 𝑛𝛼 for 𝛼 ≥ 1, and 𝜑 = 𝑂 (𝑛), it holds that 𝜑/𝑟 = 𝑂 (1), and so 𝑂 (𝑛|𝑚| + 𝑛 2𝑘). And so we obtain:

𝐶 (𝑟,𝑛,𝑓 ) 𝑟

= 𝑂 (Δ) =

𝐶 (𝑟, 𝑛, 𝑓 ) = 𝑂 (𝑛|𝑚| + 𝑛 2𝑘). 𝑟 When the message size dominates the metadata, that is |𝑚| = Ω(𝑛𝑘), the amortized communication complexity simplifies to 𝑂 (𝑛|𝑚|). We also make the following remark on the latency. In the common case per Algorithm 3, delivery takes 𝜑 = 𝑂 (𝑛) rounds. Our optimistic delivery mechanism described in Algorithm 4 achieves 𝑂 (1) round latency in favorable conditions. 6

Conclusion and Open questions

In this paper, we present APM-BRB, a Byzantine Reliable Broadcast protocol that achieves optimal resilience under network asynchrony. By employing rotating committees and amortization across multiple broadcasts, APM-BRB achieves sub-quadratic amortized communication complexity of 𝑂 (𝑛|𝑚| + 𝑛 2𝑘). When the message size dominates the metadata, i.e., |𝑚| = Ω(𝑛𝑘), this simplifies to an optimal 𝑂 (𝑛|𝑚|). APM-BRB is the first BRB protocol to achieve this with optimal resilience under network asynchrony. In the common case, APM-BRB terminates in 𝑂 (𝑛) rounds, but our optimistic delivery mechanism enables termination in 𝑂 (1) rounds under favorable conditions. Michael: rewrite this We conclude this paper with an open question: whether it is possible to extend our BRB primitive to initialize a gather [9] protocol. An efficient gather protocol would allow us to easily construct a Directed Acyclic Graph (DAG)-based Byzantine Atomic Broadcast (BAB) protocol [15, 26]. In such protocols, every node completes a BRB instance in each logical round, and each instance must reference a threshold number of completed instances from the previous round. However, APM-BRB does not impose such termination requirements; while a completed instance may reference a threshold number of instances from the previous round, only a lower bound on the number that have completed (or will eventually complete) is guaranteed. Since this requirement is not explicitly stated for the BRB primitive in existing BAB protocols, it remains unclear what modifications would be necessary to substitute our algorithm for the standard BRB primitive (typically a variant of Bracha’s [6]) in DAG-BAB protocols.

14

Michael Yiqing Hu, Hong Yao Alvin Yan, and Jialin Li

References [1] Nicolas Alhaddad, Sourav Das, Sisi Duan, Ling Ren, Mayank Varia, Zhuolun Xiang, and Haibin Zhang. 2022. Balanced Byzantine Reliable Broadcast with Near-Optimal Communication and Improved Computation. Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing (2022). [2] Veronika Anikina, João Paulo Bezerra, Petr Kuznetsov, Liron Schiff, and Stefan Schmid. 2024. Dynamic Probabilistic Reliable Broadcast. International Conference on Principles of Distributed Systems (2024). [3] Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. 1988. Completeness theorems for non-cryptographic faulttolerant distributed computation. In Symposium on the Theory of Computing. [4] Alexandra Boldyreva. 2002. Efficient threshold signature, multisignature and blind signature schemes based on the Gap-Diffie-Hellman-group signature scheme. IACR Cryptol. ePrint Arch. 2002 (2002), 118. [5] Dan Boneh, Manu Drijvers, and Gregory Neven. 2018. Compact Multi-Signatures for Smaller Blockchains. In IACR Cryptology ePrint Archive. [6] Gabriel Bracha. 1987. Asynchronous Byzantine Agreement Protocols. Inf. Comput. 75 (1987), 130–143. [7] Christian Cachin, Klaus Kursawe, and Victor Shoup. 2000. Random Oracles in Constantinople: Practical Asynchronous Byzantine Agreement Using Cryptography. Journal of Cryptology 18 (2000), 219–246. [8] Christian Cachin and Stefano Tessaro. 2005. Asynchronous verifiable information dispersal. 24th IEEE Symposium on Reliable Distributed Systems (SRDS’05) (2005), 191–201. [9] Ran Canetti and Tal Rabin. 1993. Fast asynchronous Byzantine agreement with optimal resilience. Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing (1993). [10] Benny Chor, Shafi Goldwasser, Silvio Micali, and Baruch Awerbuch. 1985. Verifiable secret sharing and achieving simultaneity in the presence of faults. 26th Annual Symposium on Foundations of Computer Science (sfcs 1985) (1985), 383–395. [11] Pierre Civit, Muhammad Ayaz Dzulfikar, Seth Gilbert, Rachid Guerraoui, Jovan Komatovic, and Manuel Vidigueira. 2025. Repeated Agreement is Cheap! On Weak Accountability and Multishot Byzantine Agreement. Proceedings of the ACM Symposium on Principles of Distributed Computing (2025). [12] Pierre Civit, Seth Gilbert, Rachid Guerraoui, Jovan Komatovic, Matteo Monti, and Manuel Vidigueira. 2023. Every Bit Counts in Consensus. ArXiv abs/2306.00431 (2023). [13] Shir Cohen, Idit Keidar, and Alexander Spiegelman. 2020. Not a COINcidence: Sub-Quadratic Asynchronous Byzantine Agreement WHP. In International Symposium on Distributed Computing. [14] Ronald Cramer, Ivan Damgård, and Ueli Maurer. 2000. General Secure Multi-party Computation from any Linear Secret-Sharing Scheme. In International Conference on the Theory and Application of Cryptographic Techniques. [15] George Danezis, Eleftherios Kokoris-Kogias, Alberto Sonnino, and Alexander Spiegelman. 2021. Narwhal and Tusk: a DAG-based mempool and efficient BFT consensus. Proceedings of the Seventeenth European Conference on Computer Systems (2021). [16] Sourav Das, Zhuolun Xiang, and Ling Ren. 2021. Asynchronous Data Dissemination and its Applications. Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security (2021). [17] Danny Dolev and Rüdiger Reischuk. 1985. Bounds on information exchange for Byzantine agreement. J. ACM 32 (1985), 191–204. [18] Danny Dolev and H. Raymond Strong. 1983. Authenticated Algorithms for Byzantine Agreement. SIAM J. Comput. 12 (1983), 656–666. [19] Rosario Gennaro, Stanislaw Jarecki, Hugo Krawczyk, and Tal Rabin. 1999. Secure Distributed Key Generation for Discrete-Log Based Cryptosystems. Journal of Cryptology 20 (1999), 51–83. [20] Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich. 2017. Algorand: Scaling Byzantine Agreements for Cryptocurrencies. Proceedings of the 26th Symposium on Operating Systems Principles (2017). [21] Neil Giridharan, Lefteris Kokoris-Kogias, Alberto Sonnino, and Alexander Spiegelman. 2022. Bullshark: DAG BFT Protocols Made Practical. Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security (2022). [22] Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovic, and Dragos-Adrian Seredinschi. 2019. Scalable Byzantine Reliable Broadcast (Extended Version). In International Symposium on Distributed Computing. [23] Wassily Hoeffding. 1963. Probability inequalities for sum of bounded random variables. [24] Svante Janson. 2018. Tail bounds for sums of geometric and exponential variables. Statistics & Probability Letters 135 (2018), 1–6. [25] Jonathan Katz and Chiu-Yuen Koo. 2006. On expected constant-round protocols for Byzantine agreement. Electron. Colloquium Comput. Complex. TR06 (2006). [26] Idit Keidar, Eleftherios Kokoris-Kogias, Oded Naor, and Alexander Spiegelman. 2021. All You Need is DAG. Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (2021).

Amortized Asynchronous Byzantine Reliable Broadcast with Optimal Resilience

15

[27] Thomas Locher. 2024. Byzantine Reliable Broadcast with Low Communication and Time Complexity. In International Conference on Principles of Distributed Systems. [28] Atsuki Momose and Ling Ren. 2021. Optimal Communication Complexity of Authenticated Byzantine Agreement. In International Symposium on Distributed Computing. [29] Kartik Nayak, Ling Ren, Elaine Shi, Nitin H. Vaidya, and Zhuolun Xiang. 2020. Improved Extension Protocols for Byzantine Broadcast and Agreement. In International Symposium on Distributed Computing. [30] Torben P. Pedersen. 1991. A Threshold Cryptosystem without a Trusted Party (Extended Abstract). In International Conference on the Theory and Application of Cryptographic Techniques. [31] Nibesh Shrestha and Aniket Kate. 2025. Towards Improving Throughput and Scalability of DAG-based BFT SMR. IACR Cryptol. ePrint Arch. 2025 (2025), 877. [32] Jun Wan, Atsuki Momose, Ling Ren, Elaine Shi, and Zhuolun Xiang. 2023. On the Amortized Communication Complexity of Byzantine Broadcast. Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (2023). [33] Xin Wang, Haochen Wang, Haibin Zhang, and Sisi Duan. 2024. Pando: Extremely Scalable BFT Based on Committee Sampling. IACR Cryptol. ePrint Arch. 2024 (2024), 664.