Multivalued Consensus: General Adversaries Require More Communication

Multivalued Consensus: General Adversaries Require More Communication Mose Mizrahi # ETH Zurich, Switzerland

Roger Wattenhofer # ETH Zurich, Switzerland

arXiv:2608.17998v1 [cs.DC] 18 Aug 2026

Abstract We study n-party fault-tolerant consensus against general (non-threshold) adversaries, which are characterized by adversary structures that enumerate every party set Z such that the adversary can corrupt every party in Z. An adversary structure Z satisfies the Qd condition if the complete party set [n] is not the union of d or fewer sets in Z. Adversaries characterized by Qd -satisfying adversary structures generalize threshold adversaries which can corrupt at most t < nd parties. n,d For every d ≥ 1, we describe an infinite family Zproj of Qd -satisfying n-party adversary structures based on finite projective geometry such that the byzantine adversaries characterized by this family cause error-free R-round protocols for interactive consistency on L-bit inputs (for agreement on every party’s L-bit input) to require Ω(Ln2+1/d ) bits of expected communication, if L = Ω(Rn−1/d + 1). n,d Likewise, Zproj causes byzantine agreement and broadcast to cost Ω(Ln1+1/d ) bits, if L = Ω(Rn1−1/d ). In every case, the lower bound is Ω(Lout · n1+1/d ) bits, where Lout is the length of the output. This is in contrast to the case of threshold adversaries, for which the baseline Ω(Lout · n) “every party must learn the output” lower bound is tight for all large Lout if the adversary can corrupt Θ(n) parties. n,d The adversary structure Zproj also makes Ω(Ln1+1/d ) bits of communication required for reliable broadcast and byzantine agreement in asynchronous networks, when L = Ω(n1−1/d ). Similarly, there n,d is a family Z2-proj of Qd -satisfying adversary structures that cause asynchronous core set agreement to 2+1/d cost Ω(Ln ) bits. These asynchronous complexity bounds hold against send-omission adversaries, even if the protocol uses cryptography. Their basis is that if a quorum of non-faulty parties agree on an output and terminate, then the messages they sent before terminating must suffice for the parties outside the quorum to also terminate with the same output. Surprisingly, if we do not require the parties to terminate (stop sending messages) after they output, then these lower bounds no longer hold. We show this by designing a non-terminating reliable broadcast protocol for general-omission 1 adversaries that can for any parameter δ > 1 be tuned to cost (1+ δ−1 )Ln+O(δn2 log(δn)) bits, which is of independent interest. Lastly, we show how to obtain termination with O(Ln1+1/d + n2 log n) bits (assuming the Qd condition), and thus prove our asynchronous lower bounds tight for large L. 2012 ACM Subject Classification Theory of computation → Communication complexity; Theory of computation → Distributed algorithms; Theory of computation → Cryptographic protocols; Security and privacy → Distributed systems security Keywords and phrases Communication Complexity, Lower Bounds, Consensus, Byzantine Agreement, Reliable Broadcast, General Adversary Structures, Byzantine Faults, Omission Faults

1

Introduction

We study agreement in a network of n message-passing parties, where an adversary causes some of the parties to fail. We show that against general Qd adversaries [29], agreement tasks often require Ω(n1/d ) times more communication than they do against threshold adversaries. For example, with L-bit inputs, error-free (perfectly secure) byzantine broadcast [32] costs Ω(Ln1+1/d ) bits. This exceeds the baseline Ω(Ln) “everyone must learn the sender’s input” lower bound, which is tight for all sufficiently large L against threshold adversaries [15]. The standard way to characterize the fault tolerance of an agreement protocol is to check how many faulty parties it can tolerate. That is, one considers a t-threshold adversary which

2

Multivalued Consensus: General Adversaries Require More Communication

can corrupt at most t parties, and asks if the protocol can tolerate all such adversaries. The optimal threshold fault tolerance for an agreement task is usually of the form t < nd , where d ≥ 1 is some integer. For example, the optimal fault tolerance for byzantine agreement (BA) [32] is t < n2 or t < n3 , depending on the setting [32, 21, 48]. The reason is that when t ≥ nd , there are d sets Z1 , . . . , Zd whose union is the full party set {1, . . . , n} = [n] such that any of the sets Zi could be the set of corrupt parties. For BA, such d sets must not exist. The literature captures this notion with (general) adversary structures [29]. An adversary structure Z is a down-closed family of subsets of [n], and Z satisfies the Qd condition if no d Sd sets in it cover [n]; that is, if i=1 Zi = ̸ [n] for all Z1 , . . . , Zd ∈ Z. We define a Z-adversary to be one characterized by Z, with the ability to corrupt a set of parties Z iff Z ∈ Z. For some intuition as to why the Qd condition is important, we consider a very simple synchronous protocol where 1) the parties (who all have inputs) send their inputs to everyone, and 2) each party i outputs yi if it has received yi from every party except for a set of parties Si ∈ Z (and outputs some default value ⊥ if there exists no such yi ). If Z satisfies the Q3 condition, then the following holds: If any two correct (non-faulty) parties i and j respectively output yi ̸= ⊥ and yj ̸= ⊥, then yi = yj . To see why, consider the following three sets in Z. Si : the set of parties who did not send i the input yi . This set is in Z since i output yi . Sj : the set of parties who did not send j the input yj . This set is in Z since j output yj . F : the set of faulty parties, also in Z. By the Q3 condition, there exists a party k outside Si ∪ Sj ∪ F . This is a correct party who sent yi to i and yj to j, which means that both yi and yj are equal to the input of party k. The protocol described can also be shown to guarantee that if the correct parties have a common input v, then they all output v; hence, it solves a task known as crusader agreement [22, 5]. It is a translation of a threshold-based protocol to the general adversary setting, where the change is that instead of checking if |Si | < n3 , the parties check if Si ∈ Z. Translations like this are often possible, but they are not always so simple or efficient. In this work, we study five fundamental agreement tasks: byzantine agreement & broadcast [32], interactive consistency [32], reliable broadcast [11] and core set agreement [7]. For all of these tasks, feasibility against general byzantine adversaries is well understood. Authenticated byzantine broadcast (and thus interactive consistency) is always possible thanks to the DolevStrong protocol [21]. For the remaining tasks, there is a correspondence: Each task we study optimally requires the Qd condition in the general adversary setting if and only if it optimally requires t < nd in the threshold adversary setting. This correspondence has been established in a series of works, for byzantine and omission faults [29, 31, 51, 17, 12, 4]. Intuitively, a protocol against t < nd faults can usually be translated into a protocol against Qd adversaries, and the impossibility of solving a task against t ≥ nd faults can usually be translated into the impossibility of solving the task against non-Qd adversaries. While feasibility is well-understood, efficiency is not. General adversary tolerant agreement protocols are often less efficient. For example, synchronous binary byzantine agreement admits a deterministic error-free solution against t < n3 that costs O(n2 ) bits of communication [9] based on a recursive divide-and-conquer construction which only works well against threshold adversaries, while against Q3 adversaries the most efficient deterministic error-free protocol we know of is the O(n3 )-bit one in [12] based on the phase king paradigm [8]. Hence, we ask: Does agreement against general adversaries require more communication? We are especially interested in how efficient general adversary tolerant agreement can be when the parties have long inputs. This question has not been studied much in the literature, perhaps since the traditional erasure/error correcting code techniques used to support long inputs efficiently (see for example [26, 43, 15, 3]) only work well against threshold adversaries.

M. Mizrahi and R. Wattenhofer

For instance, against t < n3 omission faults, if we have a publicly known set S of n − t parties (up to t faulty) who know of a common value v and wish to inform the remaining t parties of this value, then the following would be an efficient solution: 1. The parties in S encode v into n − t symbols s1 , . . . , sn−t with an (n − t, n − 2t)-erasure code, such that any n − 2t of these symbols can be decoded into v. With Reed-Solomon L erasure coding [45], each symbol is n−2t + O(log n) = O( L n + log n) bits long. th 2. For all (i, j) ∈ [n − t] × [t], the i party in S sends the symbol si to the j th party outside 2 S. In total, this costs t(n − t) · O( L n + log n) = O(Ln + n log n) bits. 3. Each party outside S receives at least n − 2t symbols, which is enough for it to learn v. If one translated this protocol to the general adversary setting, then the analogue of the value n − 2t would be “the minimum k such that S is guaranteed to contain at least k correct parties.” But unlike in the threshold adversary setting, where we always have k = n − 2t > n3 , we could have k = O(1) in the general adversary setting. Then, using an (|S|, k)-erasure code would result in symbols of size Lk + O(log n) and thus a total communication complexity of O(|S|(n − |S|)( Lk + log n)) = O(Ln2 + n2 log n) bits instead of O(Ln + n2 log n). This begs the question of whether general adversaries fundamentally cause such cost increases. Consider for instance byzantine broadcast, a standard primitive for synchronous networks where a sender party broadcasts its input in a way which guarantees that even if the sender is faulty, every correct party agrees on what the sender broadcast. If the sender has an L-bit input, then a byzantine broadcast protocol must (ignoring a technicality)1 involve Ω(Ln) bits of communication since each non-sender party must learn the sender’s L-bit input. Against byzantine threshold adversaries that can corrupt O(n) parties, the “O(n) parties might have to learn an L-bit output” Ω(Ln) lower bound is tight for all large L: See [15, 43, 1] for byzantine agreement2 and broadcast, and [3] for reliable broadcast. There are some tasks (interactive consistency and core set agreement) which require Ω(Ln2 ) bits of communication when the parties have L-bit inputs, but this is simply due to the fact that these tasks require each correct party must learn O(n) parties’ L-bit inputs. In other words, the lower bound is still Ω(Lout · n), where Lout is the size of the output that every party must learn. We show that some Qd adversaries cause this lower bound to go up to Ω(Lout · n1+1/d ). In other words, Qd adversaries can fundamentally cause multivalued agreement to cost Ω(n1/d ) times more bits of communication than threshold adversaries can. While we primarily study general adversaries, we also have results for reliable broadcast with L-bit inputs against up to t < n omission faults. We show that solving this task requires Ω(Ln2 ) bits of communication if the parties must terminate (stop sending messages) after they output, which means that the echo-based protocol in [28] is optimal, but the bit complexity 1 (1 + δ−1 )Ln + O(δn2 log(δn)) is feasible for any δ > 1 if the parties are allowed to run forever. This protocol shows that Locher’s (1.5 − o(1))Ln bit communication complexity lower bound for a class of reliable broadcast protocols [35] does not extend to all non-terminating protocols.

1.1

Contributions

We show that against Qd general adversaries, one can often improve the baseline Ω(Lout · n) lower bound to Ω(Lout · n1+1/d ). We consider five very traditional and fundamental agreement tasks, defined below. Note that each of these tasks is characterized by some Validity property

1

The technicality we are ignoring is the assumption that each party must receive Ω(L) bits in expectation to learn the sender’s L-bit input. This is only true under certain conditions. 2 The bound for byzantine agreement is actually Ω(Lt) [26], but this simplifies to Ω(Ln) when t = Θ(n).

3

4

Multivalued Consensus: General Adversaries Require More Communication

which relates the parties’ inputs with their outputs, the Agreement property which requires the correct parties’ outputs to match, and finally some Liveness property which (except for reliable broadcast) requires every correct party to output from the protocol. Byzantine Agreement. In byzantine agreement [32], each party has an input, and the correct parties must agree on an output. Validity requires that if the correct parties have a common input, then they agree on it. Byzantine Broadcast. In byzantine broadcast [32], there is a publicly known sender party with an input, and the correct parties wish to agree on what they believe the sender’s input is; correctly so if the sender is correct. That is, the correct parties must agree on an output y, and this output must be the sender’s input if the sender is correct. Interactive Consistency. In interactive consistency [32], each party has an input, and the correct parties must agree on what they believe each party’s input is. That is, they must agree on a vector Y = (y1 , . . . , yn ) such that if a party i is correct, then yi is its input. Interactive consistency is the parallel version of byzantine broadcast where everyone broadcasts an input. Reliable Broadcast. Reliable Broadcast [11] is a weakening of byzantine broadcast tailored for asynchronous networks, where byzantine broadcast is impossible because the parties cannot afford to wait indefinitely to learn the input of the sender whose messages might be arbitrarily delayed. Like byzantine broadcast, reliable broadcast requires that the correct parties’ outputs match (agreement) and that they equal the sender’s input when the sender is correct (validity). However, liveness for reliable broadcast only requires the correct parties to all output if either some correct party outputs (totality) or if the sender is correct.3 Core Set Agreement. Core Set agreement [7] is a weaker version of interactive consistency tailored for asynchronous networks, where interactive consistency is impossible due to the impossibility of waiting. Instead of a full vector that contains every party’s input, each party i must for a large core set of parties C = {c1 , . . . , c|C| } (whose complement is in the adversary structure Z characterizing the adversary) output a set Y = {(c1 , y1 ), . . . , (c|C| , y|C| )} thus indicating its belief that each party ci ∈ C has the input yi . Validity for core set agreement requires that no correct party’s output set Y contain any incorrect (sender, input) tuple for any correct sender j (a tuple (j, y) such that j is correct but its input is not y), and agreement requires both the core set C and the output set Y to be the same for every correct party. The Strength of the Guarantees. Against omission faults, one can often achieve stronger guarantees than what we list above. For example, since an omission-faulty sender never lies about its input, a reliable broadcast protocol for omission faults can ensure that both the correct and the faulty parties can only output the sender’s input from the protocol, no matter if the sender is correct or not. In Section 6.1, we give a general-omission tolerant reliable broadcast protocol that achieves this guarantee. However, our lower bounds for send-omission adversaries (the ones for the asynchronous setting) only require the definitions listed above.

3

In the literature, the guarantee that the correct parties all output if the sender is correct is sometimes bundled into validity. We separate this liveness guarantee from validity since validity being a pure safety property works better for our lower bounds.

M. Mizrahi and R. Wattenhofer

Lower Bounds. We have five communication complexity lower bounds that use two adversary n,d n,d structure families Zproj and Z2-proj , which are based on d-dimensional finite projective geometry [10]. They are parametrized by the number of parties n and the least d ≥ 1 such that the Qd n,d n,d property is satisfied. For every d ≥ 1, each one of Zproj and Z2-proj exists for infinitely many n. Hence, for every d ≥ 1, our lower bounds hold for infinitely many n.4 Our results hold for all d ≥ 1; however, to prevent our lower bounds from being vacuous, we state them with the requirement (d ≥ 1, d ≥ 2 or d ≥ 3) which makes the studied task possible. We use expected communication complexity in our lower bounds. This expectation is over the parties’ inputs (which follows a distribution of our choice), plus the parties’ randomnesses assuming the protocol is randomized. We say that a protocol must involve Ω(f (L, n, d)) bits of expected communication if there is an input distribution which induces this requirement. ▶ Theorem 1. For all d ≥ 3, all R ≥ 1 and all L = Ω(Rn−1/d + 1), any R-round randomized error-free synchronous interactive consistency protocol for L-bit inputs that can tolerate all n,d byzantine Zproj -adversaries must involve Ω(Ln2+1/d ) bits of expected communication. Theorem 1 also implies the following lower bound for byzantine agreement and broadcast. ▶ Corollary 2. For all d ≥ 3, R ≥ 1 and L = Ω(Rn1−1/d ), any R-round randomized error-free synchronous byzantine agreement or broadcast protocol for L-bit inputs that can tolerate all n,d byzantine Zproj -adversaries must involve Ω(Ln1+1/d ) bits of expected communication. Note that the restriction to error-free protocols is essential. By [16], O(Ln+κ·poly(n)) bits and poly(n) rounds suffice for secure byzantine broadcast against any adversary structure if the protocol is allowed to fail with a probability negligible in κ, which means that Corollary 2 (and thus Theorem 1) does not hold without the restriction to error-free protocols. Intuitively, this is because the bottleneck that causes the lower bounds to hold in the synchronous setting is the correct parties checking if their inputs (or what they believe the broadcaster’s input is) are the same, and input hashing makes this cheap outside the error-free setting. For byzantine broadcast, we get the Ω(Ln1+1/d ) lower bound by just reducing interactive consistency to n parallel instances of byzantine broadcast (one for each party to broadcast its input), and thus showing that interactive consistency is at most n times more expensive than byzantine broadcast. In turn, the lower bound for byzantine broadcast implies the lower bound for byzantine agreement since one can reduce byzantine broadcast to byzantine agreement on what the sender’s input is, preceded by a single round where the sender sends its input to the other parties with L(n − 1) = o(Ln1+1/d ) bits. We discuss the technicalities in Section 5. Our next lower bounds are for asynchronous protocols. They only require send-omission faults, and hold even if the protocol can fail to achieve output safety (agreement and validity) with a constant probability. Moreover, these lower bounds hold even if the adversary must be efficient and explicitly constructed, which means that one cannot circumvent them by using cryptography. However, the protocol must be terminating. That is, liveness should hold with probability 1, and the correct parties must terminate (stop sending messages) upon outputting. ▶ Theorem 3. For all d ≥ 1 and L = Ω(n1−1/d ), a terminating reliable broadcast protocol n,d for L-bit inputs that can tolerate all efficient send-omission Zproj -adversaries must involve 1+1/d Ω(Ln ) bits of expected communication, if the protocol must achieve output safety with at least 0.5 + ε probability for any absolute constant ε > 0. 4

One can further prove that for every d ≥ 1 there is some Nd such that our bounds hold for all n ≥ Nd . This is because our lower bounds monotonically grow with n, and because the ratio of the consecutive values of n for which our adversary structures exist approaches 1 as n → ∞. We provide the details of this argument in the appendix.

5

6

Multivalued Consensus: General Adversaries Require More Communication

▶ Theorem 4. For all d ≥ 2 and L = Ω(n1−1/d ), a terminating asynchronous byzantine agreen,d ment protocol for L-bit inputs that can tolerate all efficient send-omission Zproj -adversaries 1+1/d must involve Ω(Ln ) bits of expected communication, if the protocol must achieve output safety with at least 0.75 + ε probability for any absolute constant ε > 0. ▶ Theorem 5. For all d ≥ 2 and all L ≥ 1, a terminating asynchronous core set agreement n,d protocol for L-bit inputs that can tolerate all efficient send-omission Z2-proj -adversaries must 2+1/d involve Ω(Ln ) bits of expected communication, if the protocol must achieve output safety with at least 0.875 + ε probability for any absolute constant ε > 0. The Importance of Termination. Our lower bounds for the asynchronous setting require termination. To show that this requirement is essential, in Section 6.1 we present an error-free reliable broadcast protocol for L-bit inputs which can for any parameter δ > 1 be tuned to cost 1 at most (1+ δ−1 )Ln+O(δn2 log(δn)) bits of communication and tolerates any general-omission adversary. The caveat is that the parties cannot terminate it after they output, as the protocol uses a pull-based approach where the parties who know the sender’s input v must stay alive to serve other parties’ dynamic requests for erasure-coded fragments of v.5 We then discuss how this approach can be extended for byzantine fault tolerance and why our other lower bounds for asynchronous byzantine agreement and core set agreement also require termination. In Section 7, we also give a simple crash fault tolerant terminating reliable broadcast protocol that costs L(n−1)+O(n2 ) bits to show that our lower bounds for asynchronous send-omission tolerant protocols do not extend to crash fault tolerant protocols.6 A consequence of our two reliable broadcast protocols is that Locher’s 1.5(1 − o(1))Ln bit communication complexity lower bound for a certain class of reliable broadcast protocols that can tolerate t < n3 crash faults [35] does not extend to all non-terminating reliable broadcast protocols: The bound does not apply to all non-terminating protocols in the omission/byzantine fault settings, and it does not apply to all terminating protocols in the crash fault setting. The Requirements on L. Most of our lower bounds require minimum input lengths. This is because the parties can (ab)use silence to encode information into metadata. For example, in a synchronous network, the party set [n − 1] can transmit a tuple (r, j) ∈ [R] × [n − 1] to the party n as follows: On round r ∈ [R], the party j ∈ [n − 1] sends a single bit to i. This way, i learns O(log R + log n) bits of information while receiving only one bit, breaking the assumption we would like to make that to learn L bits a party must receive Ω(L) bits in expectation. To make this assumption true, we lower bound L, and thus limit the effectiveness of silence. We note that this would not be required if we were to measure communication with entropy instead of bits sent. Less abstractly, we would not need lower bounds on L if we assumed that each message is tagged with the pertinent metadata (a sender ID and a receiver ID, plus a round number for synchronous protocols). Adopting this tagged model would also make our lower bounds for synchronous protocols hold no matter the protocol’s round complexity, even for Las Vegas style protocols with variable round complexities.

5

It is the impossibility of such a dynamic approach that makes our lower bounds hold against terminating protocols. In a terminating protocol, we can partition the parties into two sets U, U ′ such that U ′ ∈ Z, and force the parties in U to terminate without them ever receiving any messages from U ′ . The parties in U will then be forced to blindly send their common output to the parties in U ′ , with the redundancy required for everyone in U ′ to terminate. If on the other hand the protocol were non-terminating, then the parties in U could wait to hear from the parties in U ′ and reply to them dynamically. 6 In the crash fault setting we assume no message clawbacks, which means that if a party sends a message, then the adversary must eventually deliver the message even if the party later crashes.

M. Mizrahi and R. Wattenhofer

Tightness. When the adversary structure satisfies the Qd condition, our lower bounds are of the form Ω(Lout · n1+1/d ), where Lout is the output length. While we can only conjecture that this bound is tight in the synchronous setting, we know that it is tight in the asynchronous setting for all large L. We show this in Section 6.2 via an error-free general-omission tolerant termination protocol (inspired by the protocols in [43]) that lets any asynchronous agreement protocol terminate with O(Ln1+1/d + n2 log n) bits of additional communication, for any Qd -satisfying adversary structure Z. To obtain this result, we find some non-empty party set G ⊆ [n] such that |G \ Z| ≥ |G|n−1/d for all Z ∈ Z, which always exists by Proposition 9. Then, we task each party in G (which contains at least |G|n−1/d correct parties) with sending 1/d −1/d everyone an erasure code symbol of size O( Ln of the |G| |G| + log n) such that any |G|n symbols suffice for everyone to learn the output and terminate. Other Agreement Tasks. While we focus on five fundamental agreement tasks in the paper, our lower bounds generalize to other tasks, including ones with weaker agreement guarantees. In particular, our lower bounds for byzantine agreement also hold for a weaker variant of the task called adopt-commit [27].7 While for brevity we omit a formal proof of this, the intuitive reason is that an adopt-commit protocol must (like a byzantine agreement protocol) be such that if a quorum S of correct parties (whose complement the adversary could corrupt) have a common input v, then every correct party outside S learns v. This induces the same entropy lower bounds for adopt-commit and byzantine agreement. Alternatively, an easier argument that works for large L is that one can reduce multivalued byzantine agreement to an instance of multivalued adopt-commit followed by an instance of binary byzantine agreement (with a cost not dependent on L), as Turpin and Coan show in [49] with older terminology. For similar reasons, our bound for byzantine broadcast also holds for its weaker variant gradecast [25].

1.2

Technical Overview

Below, we sketch the proof of our simplest lower bound: the Ω(Ln1+1/d ) bit one for reliable broadcast (Theorem 3). Afterwards, we will explain how our other lower bound proofs differ. To keep the sketch simple, let us only consider deterministic and error-free reliable broadcast. For an adversary structure Z, let the corresponding quorum structure be S = {S ⊆ [n] : [n] \ S ∈ Z}. When we run a protocol against a Z-adversary, the guarantee we have is that the set of correct parties will always be in S. Note that the quorum structure S is up-closed (with the maximum element [n]) since Z is down-closed, and the Qd condition is equivalent to the statement that the intersection of any d sets in S must be non-empty. n,d We will define the adversary structure Zproj such that the corresponding quorum structure n,d ∗ Sproj has a subset S with the following properties: S ∗ S S (the union of all sets in S ∗ ) and [n] \ S ∗ both contain Θ(n) parties. S Every party in S ∗ belongs to Θ(n−1/d |S ∗ |) of the sets in S ∗ . Note that the properties above imply that the quorum sets in S ∗ are of size O(n−1/d |S ∗ |) on average. For our lower bounds, we will get S ∗ via d-dimensional finite projective geometry [10], and each quorum in S ∗ will be a hyperplane of points, with each point representing a party. To get such a quorum structure, we must let the adversary corrupt n(1 − o(1)) parties. This is why our lower bounds require general adversaries.

7

Adopt-commit is sometimes called graded consensus, but the latter can also refer to a slightly stronger primitive. We refer the reader to [5] for modern definitions and a discussion of the nuances.

7

8

Multivalued Consensus: General Adversaries Require More Communication

S Let U = S ∗ . Consider the execution of a terminating reliable broadcast protocol where the sender s is in U ′ = [n] \ U and has some uniformly random L-bit input v. Every party is correct, including the sender. Let us say that this execution happens in the world Wv . In the world Wv , the adversary delays every message sent by the parties outside U ∪ {s}. This way, it forces the parties in U to terminate (with the output v since this is the sender’s input) without them ever receiving any message from the parties outside U ∪ {s}. The parties in U have to terminate without waiting to hear from the parties outside U ∪ {s} since as far as they know, the parties outside U ∪ {s} could all be silent faulty parties. We argue that for every S ∈ S ∗ and every i ∈ U ′ \{s}, the parties in S must in expectation send Ω(L) bits to i before terminating. This is because as far as the parties in S know, it is possible that every party outside S ∪ {i} is faulty, and if so, then i has to learn the uniformly random L-bit output v of the parties in S solely based on that messages that it receives from S. By an entropy argument, i must receive Ω(L) bits in expectation from S for this. P We have argued above that E[ j∈S Bj→i ] = Ω(L) for all S ∈ S ∗ and i ∈ U ′ \ {s}, where Bj→i is the number of bits that j sends to i in a random fault-free execution. Consequently, P P P E[ S∈S ∗ j∈S i∈U ′ \{s} Bj→i ] = Ω(|S ∗ |(|U ′ | − 1)L) = Ω(|S ∗ |Ln). Finally, we observe that a bit that a party in U sends can only contribute O(n−1/d |S ∗ |) to this Ω(|S ∗ |Ln) expectation since every party in U is in Θ(n−1/d |S ∗ |) of the sets S ∈ S ∗ , which means that the protocol |S ∗ |Ln ) = Ω(Ln1+1/d ) bits of communication in expectation. must involve Ω( n−1/d |S ∗ | Our Ω(Ln1+1/d ) lower bound for asynchronous byzantine agreement will involve a similar proof, with some more subtleties regarding the protocol’s safety probability. The other lower bounds (for core set agreement and interactive consistency) will be a bit harder to get. Core Set Agreement. For core set agreement, a similar proof is sufficient to show that one needs Ω(L|C|n1+1/d ) bits of expected communication, where C is the agreed upon core set. To get the lower bound Ω(Ln2+1/d ), we must also ensure that |C| = Ω(n). We will define n,d Sproj such that all of its minimal quorums (core set candidates) are of size Θ(n1−d ), which n,d means that Sproj will not suffice for the core set agreement lower bound. Hence, we will need n,d a more advanced quorum structure S2-proj which still contains many minimal quorums of 1−d size Θ(n ), but also some of size Θ(n). In our proof, the adversary will initially only allow a minimal party quorum C of size Θ(n) to communicate, and thus force C to be the core set. The remaining steps will be similar to what we sketched for reliable broadcast. Interactive Consistency. As we will study interactive consistency in synchronous networks, we cannot rely on termination. Instead, we will rely on the fact that if the parties do not communicate Ω(Ln2+1/d ) bits in expectation, then one can find two worlds WV and WV ′ S (both with no faults), a set S ∈ S ∗ and a party i ∈ [n] \ S ∗ such that the bidirectional communication between S and i is the same in both worlds even though some party j has a different input in the two worlds. Hence, by corrupting every party outside S ∪ {i}, the adversary can fool the parties in S into thinking they are in WV while fooling i into thinking it is in WV ′ , causing S and i to disagree on j’s input. Since this strategy requires the faulty parties to perfectly simulate how they would have behaved as correct parties in different worlds, the faulty parties must be byzantine and the protocol must be error-free.

2

Related Work

The literature on consensus is mostly centered around t-threshold adversaries that can corrupt t parties. In this setting, the communication complexity lower bounds for agreement on long inputs are usually simple, and the challenge lies in matching them with as little overhead as possible. This challenge began with [26], which proved the lower bounds Ω(Ln) for byzantine

M. Mizrahi and R. Wattenhofer

broadcast and Ω(Lt) for byzantine agreement, and solved these tasks with O(n3 κ) bits against t < n3 faults in a synchronous network (where κ is a security parameter). Later works have designed deterministic error-free protocols that cost O(Ln + n2 log n) bits for synchronous byzantine agreement and broadcast [15], for reliable broadcast [3], and for extending binary asynchronous byzantine agreement protocols into multivalued ones [1], all with the optimal byzantine fault tolerance t < n3 . Protocols that support long inputs efficiently also exist for core set agreement [38], as well as for authenticated byzantine agreement and interactive consistency against t < n2 faults [43]. It is also known that there exist authenticated byzantine broadcast protocols for t < n faults that cost O(Ln + κ · poly(n)) bits of communication [16]. The threshold adversary setting is well-known for its quadratic message complexity lower bounds, such as the ones in [23, 2]. Most famously, Dolev and Reischuk prove in their seminal work [23] that a synchronous deterministic byzantine broadcast protocol which can tolerate t byzantine faults must involve Ω(n + t2 ) messages. Informally, the Dolev-Reischuk argument [23] for deterministic protocols is that if a party i normally receives o(t) messages in fault-free executions, then, in an execution with faults, the adversary could corrupt every party who would normally send i a message, and thus force i to output without it receiving any messages. Curiously, the adversary structures we use in this work are not conducive to this argument, as they do not allow the adversary to corrupt any t parties it chooses. We suspect that these adversary structures thus admit byzantine broadcast protocols that cost o(n2 ) messages/bits, though we leave it for future work to show this. The lower bound most like ours is the one in [35] by Locher, which was influential for our 2 work. In [35], Locher proves a communication complexity lower bound of ( Ln n−t )(1 − o(1)) bits (or (1.5 − o(1))Ln bits when n = 3t + 1) for 3-round crash fault tolerant reliable broadcast protocols where the sender sends o(Ln) bits in the first round. The bound relies on a double counting argument comparable to the one we use, and it is tight for the considered class of protocols [36, 37]. Locher conjectured in [35] that his bound might extend to reliable broadcast protocols outside the class of protocols he considered. We show that it does not extend to all reliable broadcast protocols: The omission tolerant non-terminating reliable broadcast protocol in Section 6.1 is not subject to it, and neither is a crash fault tolerant terminating reliable broadcast protocol that we describe in Section 7. The fact that termination is the bottleneck in our asynchronous lower bounds rather than the rest of the protocol is noteworthy, given that termination is usually an easy-to-achieve goal handled with a simple protocol (e.g. by reliable agreement in [20]). And yet, with respect to the lower bound, it turns out that termination is the main challenge. This reminds us of a recent work on reliable broadcast [41], where the authors define a reliable broadcast variant with very strong termination guarantees that can to some extent tolerate the correct parties prematurely quitting the protocol, but then they fail to give a protocol which satisfies these guarantees with O(Ln + . . . ) bits of communication. We are also reminded of the recent work [34], which shows for synchronous binary byzantine agreement against t < n(1/3 − ε) byzantine faults that a deterministic protocol for this task can make all but εn of the correct parties learn the output (and thus achieve univalency) with O(n log n) bits of communication, and the part that costs Θ(n2 ) bits is making the remaining parties learn the output. Without faults, n parties can compute any function of their inputs with O(Ln2 ) bits of communication, since this is the complexity of a single all-to-all input exchange. With faults, O(Ln2 ) bits can be insufficient, as our work shows. To our knowledge, this was not known before for any task that does not require the parties to keep their inputs secret. A secrecy-involving task which can require a massive amount of communication is secret sharing, where each party acquires a share of a secret such that the parties can reconstruct

9

10

Multivalued Consensus: General Adversaries Require More Communication

the secret iff a sufficient quorum of parties combine their shares. It has been conjectured that general adversaries can require some parties to learn shares which are 2Θ(n) times larger than the secret [6].8 Accordingly, general adversary tolerant protocols based on secret sharing such as the Q3 adversary tolerant asynchronous byzantine agreement protocol in [17] can have exponential-in-n communication complexities. Note that secret sharing has efficient solutions against t-threshold adversaries, where any t + 1 shares suffice for secret reconstruction [47]. Another secrecy-involving task related to consensus is secure multi-party computation (MPC), where the parties must compute a function of their inputs while keeping their inputs secret. MPC’s input secrecy has been used to prove communication complexity lower bounds for it; see for example [19]. In this work, there is no input secrecy. Instead, we only use the idea that a party has to receive Ω(Lout ) bits from correct parties to learn an Lout -bit output. n,d n,d The adversary structures Zproj and Z2-proj we use in this paper are based on finite projective n,d geometry. In particular, for Zproj , the family of quorum sets S ∗ which we used in Section 1.2 S is such that each party in S ∗ is identified by a unique point in the d-dimensional projective geometry P G(d, q) of order q [10], where q = Θ(n1/d ) is a prime power, and each quorum set in S ∗ is a hyperplane of parties in P G(d, q). This quorum structure is inspired by Maekawa [39], who used the lines of P G(2, q) as quorums for distributed mutual exclusion. For all the facts about P G(d, q) we will use in this work, we refer the reader to the first chapter of [10].

3

Model

We assume a network of n parties with the IDs {1, . . . , n} = [n] which are pairwise connected to each other via reliable and authenticated channels. An adversary characterized by an adversary structure Z (a down-closed family of subsets of [n]) corrupts a set of parties Z ∈ Z, where Z satisfies the Qd condition for any d ≥ 1 if no d or fewer sets in Z have the union [n]. A corrupted party may be byzantine, and thus behave arbitrarily, or it may be omission faulty. An omission faulty party conforms to the prescribed protocol; however, the adversary can drop any message that the party sends (if the party is send-omission faulty), as well as any message sent to the party (if the party is general-omission faulty). Our lower bounds hold for static adversaries, which must choose the set Z ∈ Z of corrupt parties before the parties start running the protocol. However, our protocols in Section 6.1 and Section 6.2 can tolerate adaptive adversaries which can corrupt parties during protocol execution, depending on the information they gather while the protocol runs. The network may be synchronous or asynchronous. In a synchronous network, a protocol proceeds in synchronous rounds 1, 2, . . . . Each round consists of three steps where each party sends messages to the other parties, receives the messages from the other parties, and updates its state based on the messages it received. An R-round synchronous protocol consists of R rounds 1, 2, . . . , R, and it ends with each party outputting a value at the end of round R. In asynchronous networks, on the other hand, there are no rounds, and a party only sends messages in response to beginning a protocol or receiving a message. The adversary controls the message scheduling, which means that it can arbitrarily delay or reorder all sent messages; however, it is required to eventually deliver every message whose sender is correct. Our lower bounds apply to randomized protocols.9 We assume that there exists a vector of n randomness tapes R = (R1 , . . . , Rn ), and each party i has private access to Ri . Each

8 9

This conjecture has been proven for certain kinds of secret sharing schemes [46, 33]. We note that our lower bounds apply to deterministic protocols as well, since deterministic protocols are a special case of randomized ones.

M. Mizrahi and R. Wattenhofer

tape Ri ∈ {0, 1}ω is an infinite string of bits. In the synchronous setting, we assume that the tapes are mutually independent strings of i.i.d. uniformly random bits, while we allow the strings to be non-uniform and correlated in the asynchronous model. A correct party i acts deterministically based on its local view (on its input if it has any, on Ri and on the messages it has received so far). The tape vector R is independent of the parties’ inputs. To keep our model simple, we omit explicit setup parameters such as a PKI (public key infrastructure) or a CRS (common random string) from it. However, our lower bounds also hold for protocols that use finite setups. For error-free synchronous protocols, this is because the protocol must stay error-free for any fixing of the joint setup, and conditioning on a fixed setup reduces the analysis to the setup-free case. As for asynchronous protocols, the parties’ possibly non-uniform and correlated randomness tapes already subsume any joint setup. Our lower bounds are for the expected communication complexity of a protocol’s fault-free P P executions. We express this expected complexity by E[ i∈[n] j∈[n]\{i} Bi→j ], where Bi→j represents the total number of bits that the party i sends to the party j in a random execution. This expectation is over the input assignment distribution V (which assigns a private input to each party who should have one), plus the joint randomness tapes R of the parties.10 We say that an agreement protocol achieves output safety with probability p if it achieves validity and agreement with at least this probability. Formally, for any input distribution, the probability that either any party obtains an output which violates the protocol’s validity guarantees or any two correct parties obtain distinct outputs must be at most 1 − p. In our lower bounds, we use the variable TS→i to refer to the transcript of communication between a set of parties S to a party i. The arrow denotes the direction of communication: TS→i only records the communication that i receives from S (with all the pertinent metadata which i may use in the protocol), while TS↔i also records the communication that the parties in S receive from i (again with the pertinent metadata). The idea is that if the transcript T between S and i has a sufficiently large Shannon entropy H(T ), then we can transform the transcript entropy lower bound into a communication complexity one by doing the following: 1. encode T into an array A, such that the array’s cells are filled with the raw messages the parties send each other while the cell indices implicitly carry the metadata, 2. argue that the cross communication between S and i must be Ω(H(T )) bits in expectation because the array’s cells must in total contain Ω(H(T )) bits in expectation. With the transcript encoding schemes we choose, H(T ) is sufficiently large if H(T ) = Ω(R|S|) (for an R-round synchronous protocol), or if H(T ) = Ω(|S|) (for an asynchronous protocol).11 These lower bounds on H(T ) ensure that the information content of the bits sent dominate the information content of metadata. We discuss the technicalities in the appendix.

4

Adversary Structures

n,d n,d n,d Now, we define the adversary structure families Zproj and Z2-proj . The simpler structure Zproj Pd exists for any d ≥ 1 if n = 2 k=0 q k = 2(q d+1 −1)/(q −1) for a prime power q = Θ(n1/d ). To define it, we partition the parties into the sets U = [ n2 ] and U ′ = [n] \ U . We bijectively label each party i ∈ U with a point p(i) in the d-dimensional finite projective geometry P G(d, q) n,d n,d of order q. Finally, we define the quorum structure Sproj = {S ⊆ [n] : [n] \ S ∈ Zproj } that

10

In the terminology of communication complexity, our communication complexity model is known as the number-in-hand (NIH) message-passing model [44]. 11 If the protocol is asynchronous, then we make assumptions regarding the adversary’s message scheduling (which we respect in our lower bound proofs) to reduce the encoding overhead.

11

12

Multivalued Consensus: General Adversaries Require More Communication

3

2

4 7

1

6

5

Figure 1 Fano’s Plane, a depiction of P G(2, 2). The hyperplanes (lines) of P G(2, 2) are the circular arc {4, 6, 2} and the 6 collinearly drawn triples {1, 2, 3}, {3, 4, 5}, {5, 6, 1}, {2, 7, 5}, {4, 7, 1}, {6, 7, 3}. 14,2 In Zproj , the adversary can choose any of these 7 triples, and corrupt every party in [n] = {1, . . . , 14} excluding the parties in the triple. We note that the labels of the parties/nodes are arbitrary. n,d n,d corresponds to Zproj so that for any party set S ⊆ [n], S ∈ Sproj iff there exists a hyperplane H n,d of P G(d, q) such that S is a superset of the minimal quorum SH = {i ∈ U : p(i) ∈ H} ∈ Sproj . In other words, we allow the adversary to do the following: 1. pick any hyperplane H out of the (q d+1 − 1)/(q − 1) hyperplanes of P G(d, q), 2. corrupt any subset of the parties in {i ∈ U : p(i) ̸∈ H} ∪ U ′ .

This adversary structure satisfies the Qd condition since the intersection of d hyperplanes n,d is never empty. Moreover, for each party i ∈ U , the proportion of quorums in Sproj which contain i is exactly (q d − 1)/(q d+1 − 1) = Θ(n−1/d ), by the incidence structure of P G(d, q). n,d The adversary structure Z2-proj is somewhat more complicated. It exists for any d ≥ 1 if d+1 n = 3(q − 1)/(q − 1) for a prime power q. This time, we partition the party set [n] into 2n n ′ three sets: U1 = {1, . . . , n3 }, U2 = { n3 +1, . . . , 2n 3 } and U = { 3 +1, . . . , n}. For every i ∈ [ 3 ], n n we label the party i ∈ U1 and the party i + 3 ∈ U2 with some unique point p(i) = p(i + 3 ) in P G(d, q). The adversary can once again corrupt any of the parties in U ′ . Plus, it can do the following twice: pick a hyperplane, and corrupt every party in one of U1 or U2 whose label is not incident to this hyperplane. In other words, the adversary can pick any two (possibly identical) hyperplanes H, H′ of P G(d, q) and do one of the following: corrupt any subset of the parties in {i ∈ U1 : p(i) ̸∈ H ∩ H′ } ∪ U ′ , corrupt any subset of the parties in {i ∈ U1 : p(i) ̸∈ H} ∪ {i ∈ U2 : p(i) ̸∈ H′ } ∪ U ′ , corrupt any subset of the parties in {i ∈ U2 : p(i) ̸∈ H ∩ H′ } ∪ U ′ . Let us say that the adversary hits U1 or U2 if it picks a hyperplane H and corrupts some of the parties in U1 or U2 whose labels are not incident on H. The adversary can perform two n,d hits, either twice on one of U1 or U2 or once on each. The adversary structure Z2-proj satisfies d the Q condition because taking the union of d maximal adversary sets means performing 2d hits, which is not enough to corrupt every party. The reason for this is that the hyperplanes of P G(d, q) form a d-wise intersecting family, which means that the adversary must hit both U1 and U2 at least d + 1 times (i.e. perform 2d + 2 hits) to fully corrupt both U1 and U2 . n,d n,d The quorum structure S2-proj corresponding to Z2-proj has a substructure S ∗ which contains one quorum SH for each hyperplane H of P G(d, q), where SH = {i ∈ U1 ∪ U2 : p(i) ∈ H}. By the incidence structure of P G(d, q), the proportion of quorums in S ∗ that contain each party i ∈ U1 ∪ U2 is (q d − 1)/(q d+1 − 1) = Θ(n−1/d ). n,d The structure S2-proj also has a minimal quorum C of size at least (q d+1 − 1)/(q − 1) ≥ n3 , which can be obtained by choosing two distinct hyperplanes H and H′ of P G(d, q) and letting C = U1 ∪ {i ∈ U2 : p(i) ∈ H ∩ H′ }. If d = 1, then C = U1 , and otherwise, C is a collection of

M. Mizrahi and R. Wattenhofer

13

Pd−2 d−1 q d−1 −1 q d+1 −1 parties, where the latter term q q−1−1 = k=0 q k is the number of points q−1 + q−1 that any (d − 2)-dimensional subspace of P G(d, q) contains.

5

Synchronous Lower Bounds

We begin with a combinatorial lemma which relates the expected amount of communication that takes place between many (quorum, party) pairs in a protocol with the protocol’s total expected communication complexity. We will use this lemma throughout the paper. S ▶ Lemma 6. Let S be a family of party sets such that each party in U = S is in at most Q = O(n−1/d |S|) of the sets in S, for any d ≥ 1. Suppose there exists some E > 0 such that P a protocol’s random fault-free executions satisfy E[ j∈S (Bj→i + Bi→j )] ≥ E for all S ∈ S and all parties i in a set U ′ ⊆ [n] \ U of size Θ(n). Then, the random fault-free executions of the protocol involve Ω(En1+1/d ) bits of total expected communication. Proof. The proof is by double counting. The expected fault-free communication complexity P P P P of the protocol is E[ j∈[n] i∈[n]\{j} Bj→i ], which is at least E[ j∈U i∈U ′ (Bj→i + Bi→j )]. P Due to the linearity of expectation, summing E[ j∈S (Bj→i + Bi→j )] ≥ E up over every P P P S ∈ S and i ∈ U ′ results in E[ S∈S j∈S i∈U ′ (Bj→i +Bi→j )] ≥ E|S||U ′ | = Ω(En|S|). We P P P P P have S∈S j∈S i∈U ′ (Bj→i + Bi→j ) ≤ Q( j∈U i∈U ′ (Bj→i + Bi→j )) since for all j ∈ U and i ∈ U ′ , the term (Bj→i + Bi→j ) appears in the first sum at most Q times (once for each S ∈ S that contains j). Therefore, the expected communication complexity of the protocol is P P P P P 1 · E[ S∈S j∈S i∈U ′ (Bj→i + Bi→j )] lower bounded by E[ j∈U i∈U ′ (Bj→i + Bi→j )] ≥ Q En|S| 1+1/d = Ω( En|S| ). Q ) = Ω( n−1/d |S| ) = Ω(En

◀

Now, we are ready to prove the lower bound for interactive consistency. ▶ Theorem 1. For all d ≥ 3, all R ≥ 1 and all L = Ω(Rn−1/d + 1), any R-round randomized error-free synchronous interactive consistency protocol for L-bit inputs that can tolerate all n,d byzantine Zproj -adversaries must involve Ω(Ln2+1/d ) bits of expected communication. n,d Proof. Recall that Zproj partitions the parties into two sets U, U ′ of size n2 , where a quorum is a hyperplane of U . We consider the input distribution V which assigns every party an i.i.d. uniformly random L-bit input. This distribution has Ln bits of entropy. n,d Fix any minimal quorum SH of Sproj (obtained by picking the parties in U whose labels are incident to the hyperplane H of P G(d, q)), and fix a party i ∈ U ′ . Consider the random transcript TSH ↔i of the bidirectional communication between SH and i in a fault-free execution, which is randomized by the input distribution V and party randomnesses R. We claim that H(TSH ↔i ) ≥ H(V) = Ln. Assume this is correct for now. By the assumption L = Ω(Rn−1/d ), we have H(TSH ↔i ) = Ω(Rn1−1/d ), which means by Lemma 11 (proven P in the appendix) that EV,R [ j∈SH (Bj→i + Bi→j )] = Ω(H(TSH ↔i )) = Ω(Ln). Hence, by Lemma 6, the protocol involves Ω(Ln2+1/d ) bits of expected communication. What remains to prove is that the claim H(TSH ↔i ) ≥ H(V) is true. Suppose not. Then, since H(V) > H(TSH ↔i ), we have H(V | TSH ↔i ) ≥ H(V) − H(TSH ↔i ) > 0. The conditional P entropy H(V | TSH ↔i ) equals τS ↔i Pr[TSH ↔i = τSH ↔i ] · H(V | TSH ↔i = τSH ↔i ), where H τSH ↔i refers to any fixed finite R-round transcript which TSH ↔i might equal, and this sum is positive. So, there must be some τSH ↔i such that Pr[TSH ↔i = τSH ↔i ]·H(V | TSH ↔i = τSH ↔i ) is positive. In particular, the factor H(V | TSH ↔i = τSH ↔i ) must be positive. For this, there must exist two distinct V, V ′ in the support of V such that Pr[V = V | TSH ↔i = τSH ↔i ] > 0 and Pr[V = V ′ | TSH ↔i = τSH ↔i ] > 0. In the rest of our proof below, we use these two input

14

Multivalued Consensus: General Adversaries Require More Communication

assignments V, V ′ and the fixed transcript τSH ↔i to show that the protocol is not error-free. This contradiction means that the assumption H(TSH ↔i ) < H(V) must be false. Observe that Pr[V = V | TSH ↔i = τSH ↔i ] > 0 implies Pr[TSH ↔i = τSH ↔i | V = V ] = p for some p > 0 by the definition of conditional probability and by Bayes’ Theorem. Similarly, Pr[V = V ′ | TSH ↔i = τSH ↔i ] > 0 implies Pr[TSH ↔i = τSH ↔i | V = V ′ ] = q for some q > 0. Let WV (resp. WV ′ ) be the set of all worlds where a fault-free execution with the input assignment V (resp. V ′ ) takes place and the transcript between SH and i is τSH ↔i . Interactive consistency requires the parties to all output V in the worlds in WV and V ′ in the worlds in WV ′ . Let us define a hybrid world set WHyb where the parties in SH ∪{i} are correct while the rest of the parties are byzantine, i’s input is assigned in accordance with V , and the parties in SH have their inputs assigned in accordance with V ′ . Every fixed world WHyb ∈ WHyb is such that i’s randomness Ri in WHyb is the same as it is in some fixed world WV ∈ WV , and similarly the randomnesses {Rs : s ∈ SH } of the parties in SH are the same as they are in some fixed world WV ′ ∈ WV ′ . Below, we describe a cut-and-paste attack the adversary can perform in the world WHyb to cause i to output V in WHyb while causing the parties in SH to output V ′ , with this breaking the agreement property. Note that the adversary can perform this sort of attack with at least p · q > 0 probability because i has a randomness compatible with WV (a randomness that i has in some fault-free world with the input assignment V where TSH ↔i = τSH ↔i ) with at least p probability, and independently of this the parties in SH have a joint randomness compatible with WV ′ with at least q probability. In WHyb , the byzantine parties simulate WV towards i and simulate WV ′ towards SH . That is, each byzantine party j ̸∈ SH ∪ {i} acts towards i as if j were a correct party in the world WV (by sending messages it would have sent in WV on the same rounds), and likewise acts towards the parties in SH as if j were a correct party in the world WV ′ . Let Wj = WV ′ for all j ∈ SH and let Wi = WV . We claim that a correct party j ∈ SH ∪{i} can never distinguish WHyb from Wj . Since every correct party j has the same input in WHyb and Wj , our claim is false only if there exists some first round r ∈ [R] such that some correct party j can distinguish WHyb from Wj at the end of the round, even though no correct party j ′ could distinguish WHyb from Wj ′ at the beginning of the round. However, such a party j cannot exist: If it did, it would have to receive different messages from another party k in WHyb and Wj on round r, even though this other party k cannot exist. Finally, the reason why k cannot exist is it can be neither correct nor byzantine. We show this below. The party k cannot be byzantine because the byzantine parties behave identically towards j in WHyb and Wj on purpose. The party k cannot be correct either. If it were so, then it would send the same round r messages to j in the worlds WHyb and Wk since it would not have been able to distinguish the two worlds at the start of the round. If Wk = Wj , then k is eliminated. If Wk ̸= Wj , then either k = i and j ∈ SH , or k ∈ SH and j = i. Either way, k sends the same round r messages to j in the worlds Wk and Wj (since the transcript between k and j is described by τSH ↔i in both worlds), which again eliminates k. The indistinguishability above means that in the world WHyb the party i outputs V as it would in the world WV , while the parties in SH output V ′ as they would in WV ′ . ◀ ▶ Corollary 2. For all d ≥ 3, R ≥ 1 and L = Ω(Rn1−1/d ), any R-round randomized error-free synchronous byzantine agreement or broadcast protocol for L-bit inputs that can tolerate all n,d byzantine Zproj -adversaries must involve Ω(Ln1+1/d ) bits of expected communication. Proof. Suppose L = Ω(Rn), and suppose there is an R-round byzantine broadcast protocol BB for L-bit inputs. Using BB, the parties can achieve interactive consistency on L-bit inputs

M. Mizrahi and R. Wattenhofer

in Rn rounds as follows: On the rounds R(i − 1) + 1, . . . , Ri, the party i ∈ [n] broadcasts its input with BB.12 Observe that if BB violated the lower bound stated in Corollary 2, then this interactive consistency protocol would violate the lower bound of Theorem 1. As Theorem 1 is true, we conclude that the lower bound for byzantine broadcast holds. Next, let us consider byzantine agreement. Whenever byzantine agreement can be solved in R rounds, byzantine broadcast can be solved in R + 1 rounds as follows: The sender sends its input to every other party in the first round, and in the rounds 2, . . . , R + 1 the parties reach byzantine agreement on the sender’s input. Since the bit complexity of the first round is L(n − 1) = o(Ln1+1/d ) and the one additional round is asymptotically irrelevant, the lower bound for byzantine broadcast implies the lower bound for byzantine agreement. Note that the reduction for byzantine agreement relies requires n1/d = ω(1). For when n,d n1/d = O(1), we recall that Zproj partitions the parties into two sets U and U ′ of size n2 each, and assign the parties in U a common uniformly random L-bit input v while assigning the parties in U ′ the fixed input 0. By the validity of byzantine agreement, the parties in U must output v (since as far as they know, the parties in U ′ with inputs other than v could all be byzantine), and this ensures agreement on v. So, the parties in U ′ must learn v. In fault-free executions, for each party i ∈ U ′ the bidirectional transcript T([n]\{i})↔i between i and every other party must have at least L bits of entropy;13 hence, by Lemma 11, the communication between i and every other party must be at least Ω(L) bits in expectation. This implies an ′ | 1+1/d Ω( L|U ) total communication complexity bound if n1/d = O(1). ◀ 2 ) = Ω(Ln) = Ω(Ln

6

Asynchronous Lower Bounds

Now, we switch over to asynchronous networks. This time, we have three similar but separate lower bound theorems to prove, as the asynchronous setting is less amenable to reductions. The theorems will make use of Lemma 7 (stated below), which we prove in the appendix. Intuitively speaking, the lemma says that if the adversary uses a message scheduling strategy which forces a party i to learn the correct random output X of a protocol solely based on the messages it receives from a fixed set of parties S, then the transcript of the communication directed from S to i must have Ω(H(X)) bits of entropy for i to learn X. ▶ Lemma 7. Let X be some finite uniformly random variable. Suppose that in a randomized asynchronous n-party protocol, some party i must output a prediction Yi of X solely based on the messages it receives from some fixed set of parties S ⊆ [n] \ {i}, and this prediction must satisfy Pr[Yi = X] ≥ 0.5 + ε for some absolute constant ε > 0. If i’s initial knowledge prior to running the protocol (its randomness and its input if it has any) is independent of X, then the one-way transcript TS→i describing the communication directed from S to i must have at least ε′ H(X) bits of Shannon entropy for some absolute constant ε′ > 0. Our simplest lower bound in the asynchronous setting is the one for reliable broadcast. ▶ Theorem 3. For all d ≥ 1 and L = Ω(n1−1/d ), a terminating reliable broadcast protocol n,d for L-bit inputs that can tolerate all efficient send-omission Zproj -adversaries must involve

12

The reason why the parties do not broadcast their inputs in parallel is that if they were to do so, then it would no longer be clear to which byzantine broadcast instance each message belongs. 13 The transcript entropy H(T([n]\{i})↔i ) ≥ L is required for i to learn v. With less transcript entropy, it would not always be possible to deduce v from T([n]\{i})↔i ; however, such a deduction must always be possible since i must compute v based on T([n]\{i})↔i (and on its initial state, which is unrelated to v).

15

16

Multivalued Consensus: General Adversaries Require More Communication

Ω(Ln1+1/d ) bits of expected communication, if the protocol must achieve output safety with at least 0.5 + ε probability for any absolute constant ε > 0. n,d partitions the parties into two sets U, U ′ of size n2 , where a quorum is Proof. Recall that Zproj a hyperplane of U . For the reliable broadcast lower bound, we assume that the sender s is in U ′ . The input distribution V assigns a uniformly random L-bit input to s, which means that the correct parties must output V if s is correct. This distribution has L bits of entropy. Consider a fault-free protocol execution. We suppose that the send-omission adversary employs a message scheduling strategy where the traffic between the parties in U ∪ {s} always flows freely while all other communication is blocked until when the parties in U ∪ {s} all terminate. This is a permissible way for the adversary to schedule messages because the parties in U ∪ {s} will indeed all terminate solely based on the messages they send each other. This is because they will not be able to distinguish the fault-free setting from the setting where the parties in U ′ \ {s} are all silent faulty parties, while the remaining parties are correct. In this setting, the parties in U ∪ {s} would have to terminate due to the protocol’s liveness (since the sender s is correct); so, they must terminate in the fault-free setting too. n,d Fix a quorum SH ∈ Sproj and a party i ∈ U ′ \{s}. Consider the random one-way transcript variable TSH →i which describes the communication that the party i receives from the parties in SH in a random fault-free execution (where s’s input and the parties’ randomnesses are all random) where the adversary begins the message scheduling as described above. We claim that H(TSH →i ) ≥ ε′ H(V) = ε′ L for some absolute constant ε′ > 0. If this claim is true, then the parties in SH must in expectation send Ω(L) bits in total to i (by Lemma 12), and since n,d this is true for all SH ∈ Sproj and i ∈ U ′ \ {s} (where U ′ \ {s} is a set of n2 − 1 = Θ(n) parties), Lemma 6 implies that the protocol involves Ω(Ln1+1/d ) bits of expected communication. It remains to show that the claim H(TSH →i ) ≥ ε′ H(V) is true. Suppose otherwise, for the sake of contradiction. Then, the adversary (who has made the parties in U terminate before i receives any message) can continue its message scheduling strategy by first delivering the messages from SH to i, while delaying the other pending messages sent to i for later. If the adversary does this, then the party i will terminate solely based on the messages it receives from SH without waiting for any other parties’ messages, and its random output Y will have to equal the sender’s uniformly random L-bit input with at least 0.5+ε probability by the validity of the reliable broadcast protocol (which must hold with at least the same probability); hence, Lemma 7 requires H(TSH →i ) ≥ ε′ H(V) to hold. The reason i will not wait for any other parties’ inputs is that if it had a positive probability p of doing so, then the adversary could force it to wait forever with the probability p by causing the parties outside SH ∪ {i} to suffer from send-omission faults which prevent their messages from reaching the parties in U ′ , while keeping everything else the same. Then, i waiting forever as we have described would be a liveness violation because the parties in SH would be correct parties who have terminated. ◀

Theorem 3 implies an Ω(Ln2 ) bit expected communication complexity lower bound for any terminating reliable broadcast protocol for send-omission adversaries that can corrupt up n,d to n − 1 parties, because such an adversary is stronger than a send-omission Zproj -adversary. Note that omission-tolerant reliable broadcast is possible against up to t < n send-omission faults with a simple echo-based protocol [28], as long as uniformity (the additional guarantee that if a faulty party outputs, then every correct party outputs) is not required. Requiring uniformity against send-omission faults decreases the optimal fault tolerance to t < n2 [13]. Now, we are ready to prove the lower bound for asynchronous byzantine agreement. We would like to get this lower bound using the same broadcast-to-agreement reduction we used to prove Corollary 2. Sadly, we cannot do this, because if a faulty sender sends its input to

M. Mizrahi and R. Wattenhofer

only some of the correct parties, then only some of the correct parties will have asynchronous byzantine agreement inputs (the input they got from the sender), and this might lead to only some of the correct parties terminating the asynchronous byzantine agreement protocol. One way to solve this issue is to use an asynchronous byzantine agreement protocol that has the “strong termination” property defined in [41], which is comparable to the totality guarantee of reliable broadcast. However, we prefer to use standard termination guarantees and give a separate proof for the asynchronous byzantine agreement lower bound. Note that some parts of our proof of Theorem 4 below mirror our proof of Theorem 3. Hence, to avoid redundancy, we will treat these parts more concisely. ▶ Theorem 4. For all d ≥ 2 and L = Ω(n1−1/d ), a terminating asynchronous byzantine agreen,d ment protocol for L-bit inputs that can tolerate all efficient send-omission Zproj -adversaries 1+1/d must involve Ω(Ln ) bits of expected communication, if the protocol must achieve output safety with at least 0.75 + ε probability for any absolute constant ε > 0. n,d partitions the parties into two sets U, U ′ of size Proof. Again, the adversary structure Zproj n 2 . We choose an input distribution V that assigns a common uniformly random L-bit input v to the parties in U and the fixed input 0 to the parties in U ′ . As we did to prove Theorem 3, we will lower bound the communication complexity of fault-free executions. The adversary employs a scheduling strategy that causes fault-free executions to work as follows: 1. The adversary allows the traffic between the parties in U to flow freely, while blocking all other communication until the parties in U all terminate. The parties in U will terminate the protocol with the output v because as far as they are aware, the parties in U ′ could be faulty, and if this were the case, the validity and termination guarantees of the protocol would require the parties in U to terminate with the output v. 2. Now that the parties in U have terminated with the output v, the agreement property of the protocol requires the parties in U ′ to terminate with this output as well. Therefore, the transcript TSH →i for any SH and i ∈ U ′ must have at least ε′ L bits of entropy for some absolute constant ε′ > 0. This implies (by Lemmas 7 and 12) that SH has to send Ω(L) bits in expectation to i, and hence by Lemma 6 we conclude that the protocol must involve Ω(Ln1+1/d ) bits of expected communication. The reason why H(TSH →i ) ≥ ε′ L is that i must terminate the protocol with a prediction Yi of the uniformly random L-bit value v solely based on the messages it receives from SH , in case everyone outside SH ∪ {i} is faulty, and this prediction must be correct with at least 0.5 + 2ε probability. We explain below how we obtain the probability 0.5 + 2ε.

The new subtlety with asynchronous byzantine agreement that was not present for reliable broadcast is that on the last step, the protocol achieving output safety with at least 0.75 + ε probability only implies that i’s prediction Yi of v must equal v with 0.5 + 2ε probability. The reason is that there are two error events Eag and Eval this time, both of which can occur with up to 1−(0.75+ε) = 0.25−ε probability, and we have Pr[Yi = v] ≥ 1−Pr[Eag ∪Eval ] ≥ 0.5+2ε by the union bound. The first event Eag represents an agreement violation. This is the bad event that in the fault-free execution, i’s output Yi differs from the output of some party in U , and this error event must happen with at most 0.25 − ε probability. Meanwhile, the event Eval represents a validity violation: This is the bad event that there exists some party in U who does not output v in the fault-free execution. We have Pr[Eval ] ≤ 0.25 − ε because Eval corresponds to a validity violation in the alternate setting where only the parties in U are correct (with this making v the valid output they have to obtain) while the remaining parties are all silent faulty parties. The parties in U cannot distinguish this alternate setting

17

18

Multivalued Consensus: General Adversaries Require More Communication

from the fault-free setting until after they all output in the fault-free setting, which means that in both settings they must all output v except with probability at most 0.25 − ε. ◀ Finally, the proof of the core set agreement lower bound follows the template of the proof n,d above, but we use the adversary structure Z2-proj and add an extra scheduling step to ensure that the parties agree on a core set that contains Θ(n) parties (and thus learn Θ(Ln) bits). ▶ Theorem 5. For all d ≥ 2 and all L ≥ 1, a terminating asynchronous core set agreement n,d protocol for L-bit inputs that can tolerate all efficient send-omission Z2-proj -adversaries must 2+1/d involve Ω(Ln ) bits of expected communication, if the protocol must achieve output safety with at least 0.875 + ε probability for any absolute constant ε > 0. n,d Proof. Recall that Z2-proj partitions the parties into three sets U1 , U2 , U ′ of size n3 , and admits n,d a minimal quorum C ⊇ U1 such that [n] \ C is a maximal set in Z2-proj . We consider the input distribution V which assigns every party an i.i.d. uniformly random L-bit input. Once again, we want to lower bound the expected communication complexity of fault-free executions. In these executions, the adversary employs the scheduling strategy described below. Initially, the adversary lets the traffic between the parties in C flow freely, while blocking all other communication. The parties in C will all terminate since they cannot afford to wait to hear from the parties outside, who could all be faulty silent parties as far as the parties in C can tell. Moreover, each party i ∈ C will output Yi = {(c1 , y1 ), . . . , (c|C| , y|C| )}, where C = {c1 , . . . , c|C| } and yi is the input of the party ci for each ci ∈ C. We show below that this claim concerning Yi is true with at least 0.625 + 3ε probability, based on the fact that the probability of a validity violation is at most 0.125 − ε. To prove this claim, we define a validity violation event Eval , define the three error events Ea , Eb , Ec that could cause Yi to differ from {(c1 , y1 ), . . . , (c|C| , y|C| )}, and show that Pr[Ea ∪ Eb ∪ Ec ] ≤ 3 Pr[Eval ] ≤ 0.375 − 3ε. 1. Let Ea be the bad event that for some j ̸∈ C and any y the set Yi contains the tuple (j, y). The party i ∈ C decides on y before it learns anything about j’s uniformly random input v, which means that Pr[y = ̸ v] = 1 − 2−L ≥ 0.5. Hence, we have 0.125 − ε ≥ Pr[Eval ] ≥ Pr[Ea ∩ Eval ] ≥ 0.5 Pr[Ea ]. 2. Let Eb be the bad event that there is a party c ∈ C such that Yi does not contain a tuple of the form (c, y). Observe that Eb \ Ea is impossible. The reason is that if Eb happens but Ea does not, then for some proper subset C ′ of C, the set Yi only contains tuples of the form (c′ , y ′ ) when c′ ∈ C ′ . This is a contradiction because core set agreement requires n,d n,d [n] \ C ′ to be in Z2-proj , which contradicts the maximality of [n] \ C in Z2-proj . 3. Let Ec be the bad event that there exists any tuple (j, y) ∈ Yi such that j’s input is not y. This is a validity violation; hence, Pr[Ec ] ≤ Pr[Eval ] ≤ 0.125 − ε. Combining all of the inequalities above, we get Pr[Ea ∪ Eb ∪ Ec ] = Pr[Ea ] + Pr[Eb \ Ea ] + Pr[Ec \ (Ea ∪ Eb )] ≤ Pr[Ea ] + 0 + Pr[Ec ] ≤ 0.375 − 3ε. In the next message scheduling stage, the adversary allows the traffic between the parties in U = U1 ∪ U2 to flow freely, but it keeps delaying any messages whose senders or intended recipients are in U ′ . This will cause the parties in U to terminate. As usual, the quorum U cannot wait to hear from the parties in U ′ because the parties in U ′ could all be faulty. Now that the parties in U have terminated with the output, we are in a situation analogous to one we faced in our asynchronous byzantine agreement lower bound proof. That is, for each quorum SH ⊆ U (which consists of the parties in U1 and U2 whose labels in P G(d, q) are incident to the hyperplane H) and each party i ∈ U ′ , the one-way transcript TSH →i must have Ω(Ln) bits of entropy for i to terminate with the correct output Y = {(c1 , y1 ), . . . , (c|C| , y|C| )} (which is a uniformly random variable that has L|C| = Ω(Ln) bits of entropy) with at least 0.5 + 4ε probability, which implies (by Lemmas 7 and 12) that the parties in SH are required

M. Mizrahi and R. Wattenhofer

to send Ω(Ln) bits in expectation to i, and hence by Lemma 6 that the protocol must involve Ω(Ln2+1/d ) bits of expected communication. The reason for the 0.5 + 4ε probability here is that if i outputs anything but Y , then one (or both) of two error events must have happened: Either some party c ∈ C obtained some output other than Y from the protocol (which we argued must happen with at most 0.375 − 3ε probability), or i’s output disagrees with the output of some party c ∈ C (which can happen with at most 0.125 − ε probability). ◀

6.1

The Importance of Termination

In this section, we prove that our lower bound for terminating reliable broadcast no longer holds if we drop the termination requirement and allow the parties to run forever after they output. We will then discuss why this is also the case for the core set agreement and the asynchronous byzantine agreement lower bounds, and even if the adversary is byzantine. For our proof, we design a deterministic and error-free asynchronous protocol PullCast for reliable broadcast against any general-omission adversary. For any choice of a parameter δ > 1 (which is a multiple of n1 ), PullCast can support L-bit inputs with O(δn2 ) messages 2 and (1 + 1−1/n δ−1 )Ln + O(δn log(nδ)) bits of communication, albeit with the extremely high 14 latency 2(δ − 1)n − 1. This complexity does not violate our lower bounds as PullCast does not terminate. That is, the parties keep running even after they learn the sender’s input. To obtain PullCast, we need to use an (N, k)-erasure correcting code. Such a code encodes a string m into a vector of N symbols s = (s1 , . . . , sN ) such that any k of these symbols are enough to reconstruct m. Formally, we have two functions EncN,k (m) and DecN,k (s̃). The encoding function EncN,k (m) maps a string m into a vector of N symbols s = (s1 , . . . , sN ). The decoding function DecN,k (s̃) takes in an incomplete symbol vector s̃ = (s̃1 , . . . , s̃N ) with some missing symbols (represented by ⊥) and outputs the decoded string m, provided that s̃ contains at least k non-⊥ symbols and each non-⊥ symbol s̃j is the j th symbol of EncN,k (m). We use Reed-Solomon (N, k)-erasure codes [45], which encode L-bit strings into N symbols of size Θ( Lk + log N ) each. Given the parameter δ > 1 such that δn is an integer, PullCast uses the erasure code parameters (N, k) = (δn − 1, (δ − 1)n). In PullCast, a party i who knows the sender’s input v (initially only the sender s) computes (s1 , . . . , sδn−1 ) = Encδn−1,(δ−1)n (v), sends the message ⟨SYM, i, si ⟩ containing the ith symbol to every other party, and starts answering symbol requests. That is, if i receives (or has received before learning v) a symbol request message ⟨REQ, k⟩ from a party j for the k th symbol, then i replies to j with the answer ⟨SYM, k, sk ⟩. A party i outputs v when it knows v, which is when i begins the protocol if i is the sender and when i receives (δ − 1)n symbols otherwise. To support long inputs efficiently, PullCast uses a dynamic symbol request system. Unlike most other protocols based on Cachin and Tessaro’s seminal work on fault-tolerant information dispersal [14], PullCast does not fix in advance which party should send a symbol to whom. Instead, each party i maintains a counter ci of how many symbols it has received so far, so that whenever i receives any new symbol from any party j, it can increment ci and request the next symbol sn+ci from j. This way, i requests more symbols from the parties that reply quickly to i. We note that this kind of dynamic request pattern is well known and used in

14

The latency 2(δ − 1)n − 1 means that in a PullCast execution where the adversary delays the correct parties’ messages by at most 1 time unit, if a correct party outputs from the protocol (which is what the sender immediately does if it is correct) at some point in time T , then every correct party outputs from the protocol by the time T + 2(δ − 1)n − 1. So, if δ − 1 = Θ(1), which is required for PullCast to achieve the communication complexity O(Ln + n2 log n), then the latency is Θ(n).

19

20

Multivalued Consensus: General Adversaries Require More Communication

practice by peer-to-peer file sharing protocols like BitTorrent, even though it is uncommon in the fault-tolerant consensus literature. ▶ Theorem 8. PullCast is a non-terminating reliable broadcast protocol which can tolerate any general-omission adversary with perfect security.

PullCast Code for a party i with the parameter δ > 1 1: ci ← 0 and (s̃1 , . . . , s̃δn−1 ) ← (⊥, . . . , ⊥) 2: upon learning the sender’s input v (initially as the sender or via decoding) do 3: output v but do not terminate 4: (s1 , . . . , sδn−1 ) ← Encδn−1,(δ−1)n (v) 5: send ⟨SYM, i, si ⟩ to all parties i ∈ [n] 6: upon receiving a symbol request ⟨REQ, k⟩ from a party j do 7:

send ⟨SYM, k, sk ⟩ to j

8: upon receiving a symbol ⟨SYM, k, s⟩ from a party j do 9: 10: 11: 12: 13: 14: 15: 16:

if you do not know v then ci ← ci + 1 s̃k ← s if ci = (δ − 1)n then v ← Decδn−1,(δ−1)n (s̃1 , . . . , s̃δn−1 ) trigger the “learning the sender’s input v” block else send ⟨REQ, n + ci ⟩ to j

Proof. Suppose the sender’s input is v, with (s1 , . . . , sδn−1 ) = Encδn−1,(δ−1)n (v). The sender outputs v immediately when it acquires its input, and we claim that the other parties can also only output v. Suppose not, for the sake of contradiction. Then, there exists a first non-sender party i who obtains a different output v ′ by computing Decδn−1,(δ−1)n (s̃1 , . . . , s̃δn−1 ) on Line 13. At the moment when this happens, it cannot be true that s̃j ̸∈ {sj , ⊥} for any j, because if s̃j ̸= ⊥, then i has set s̃j ← s′j after receiving the message ⟨SYM, j, s′j ⟩ from some party k, and s′j = sj because k is a party who knows the correct output v. So, it must be the case that the vector (s̃1 , . . . , s̃δn−1 ) contains less than (δ − 1)n non-⊥ symbols. However, because i only reaches Line 13 after performing (δ − 1)n symbol updates and i never updates a symbol twice, this is also impossible; so, we reach the desired contradiction. The reason why i never updates the same symbol s̃k twice is that for each k ∈ [δn − 1], there can only be one party j who sends i the message ⟨SYM, k, sk ⟩. If k ≤ n, then this party j is k, and if k > n, then j is the party to whom i sent the message ⟨REQ, n + ci ⟩ on Line 16 when i had ci = k − n. It remains to prove liveness. We do so by showing that if there is any correct party i (the sender or not) who knows the sender’s input v, then every correct party learns v. Suppose such a party i exists, and consider any correct party j that does not know v. The party i sends j the symbol si , and this triggers a feedback loop where j can continually request a new symbol from i and receive it from i until when j acquires (δ − 1)n symbols (not necessarily all from i) and outputs v. Note that this argument also shows that the latency is 2(δ − 1)n − 1, as it takes one hop for i to send the symbol si to j, and then it takes (δ − 1)n − 1 round trips between j and i (each taking 2 hops) for j to receive (δ − 1)n − 1 more symbols. If j receives any symbols from parties other than i, then this will only reduce the number of round trips that must take place between j and i for v to output; therefore, the latency will not go up.

M. Mizrahi and R. Wattenhofer

Lastly, note that we do not have to worry about any correct party i failing to respond to a symbol request due to it not knowing the symbol. If any party j requests a symbol from i, then j must have received some symbol from i before doing so, and this means that i already knows v because the first time when i sends a symbol to j is when i learns v. ◀ The Complexity of PullCast. We have already looked at PullCast’s latency and shown that it is 2(δ − 1)n − 1. The communication in PullCast amounts to at most δn − 1 symbol (SYM) L messages of size (δ−1)n + O(log(δn)) in addition to at most (δ − 1)n request (REQ) messages of size O(log(δn)) per party; so, PullCast’s total communication complexity is O(δn2 ) messages L 2 and (δn − 1)( (δ−1)n )n + O(δn2 log(δn)) = (1 + 1−1/n δ−1 )Ln + O(δn log(δn)) bits. Byzantine Fault Tolerance. Since PullCast can only tolerate send-omission adversaries, a natural question is: Can it be made byzantine fault tolerant, assuming the adversary structure satisfies the necessary Q3 condition? While a formal treatment of byzantine fault tolerant reliable broadcast protocol is outside the scope of this paper (as we are more interested in the lower bounds), below we sketch how we believe one could harden PullCast against byzantine faults. Note that the changes which we propose increase the communication complexity to 2 3 (1 + 1−1/n δ−1 )Ln + O(δn κ log(δn) + δn log(δn)) bits, where κ is size of a cryptographic hash. Preventing Duplicated Requests. The first new challenge that emerges with byzantine faults is that a byzantine party can request a symbol from multiple correct parties, to waste communication by making multiple correct parties send it the symbol. To prevent this, we could replace each symbol request where a party i sends the message ⟨REQ, k⟩ to a party j with an O(n)-times costlier fault-tolerant request mechanism that prevents i (if it is byzantine) from requesting the k th symbol from two distinct parties.15 Unfortunately, this would increase the O(δn2 log(δn)) bit complexity of the requests to O(δn3 log(δn)). Handling Incorrect Symbols. The second challenge is that the byzantine parties can send the other parties incorrect or inconsistent symbols. To prevent this, we would require the parties who know the sender’s input v to send symbols together with cryptographic proofs which witness the correctness of the symbol. This can be implemented with Merkle tree proofs [40] of length O(κ log(δn)), where the Merkle tree is computed over the correct symbol list (s1 , . . . , sδn−1 ). To establish the basis for these proofs, the sender would also have to reliably broadcast a Merkle root hash for the proofs to be checked against. Finally, a non-sender party would obtain an output y from the protocol after it outputs some root hash h from the sender’s root hash reliable broadcast, it acquires (δ − 1)n symbols which are correct with respect to h, it decodes these symbols into the tentative output y, and it verifies that the sender computed h correctly by recomputing it based on y. We note that our suggestion of using Merkle tree proofs to handle incorrect or inconsistent erasure code symbols is very standard in the byzantine fault tolerance literature [14, 43]. Byzantine Agreement and Core Set Agreement. While PullCast only proves that our reliable broadcast lower bound requires termination, our bounds for asynchronous byzantine

15

In this mechanism, i would send everyone the message ⟨REQ, i, k, j⟩ to indicate that it requests the kth symbol from the party j, and everyone would relay this request to j. The party j would send the symbol upon hearing the request relayed from a quorum Si,k,j , where [n] \ Si,k,j ∈ Z. To prevent i from causing two distinct parties j and j ′ to send it the same symbol, we would make each correct party only relay the first request i makes for each symbol index k. This way, the quorums Si,k,j and Si,k,j ′ required for j and j ′ to both send i the same symbol cannot both form: Such two quorums would have to contain a common correct party by the Q3 condition, but a correct party does not relay duplicated requests.

21

22

Multivalued Consensus: General Adversaries Require More Communication

agreement and core set agreement also need termination. Below, we sketch the reasons why. Core Set Agreement. By [7], one can reduce core set agreement to n instances of reliable broadcast and n instances of binary byzantine agreement, and this reduction also works against general adversaries [4]. Therefore, one can compose n instances of PullCast with n instances of an asynchronous binary byzantine agreement protocol which has a complexity that does not depend on L (e.g. [17]) to get a core set agreement protocol that can support L-bit inputs with O(Ln2 ) bits of communication for all sufficiently large L. Byzantine Agreement. For byzantine agreement, we observe that PullCast can support multiple senders who have a common input v and behave as parties who know the correct output v, with the guarantee that if any sender is correct or some correct party outputs, then every correct party outputs. Hence, if the parties do not have to terminate, they can reach byzantine agreement on their L-bit inputs with O(Ln + . . . ) bits of communication by 1) running a byzantine agreement on their input’s cryptographic hashes and reaching intrusion-tolerant byzantine agreement on the hash h of a correct party’s input16 , and then 2) running a PullCast instance where the parties whose inputs have the hash h behave as the parties who know v to make sure that everyone learns v. This strategy will succeed unless a hash collision occurs, which is unlikely by the hash function’s collision resistance. We note that this sort of reduction (where PullCast serves as a reconstruction protocol) is standard in the literature [43].

6.2

Termination with O(Lout · n1+1/d + n2 log n) Bits

In the previous subsection, we showed that send-omission tolerant non-terminating reliable broadcast admits a solution that costs O(Lout · n) bits of communication whenever the output length Lout is sufficiently large, and sketched why this is also the case for core set agreement and asynchronous byzantine agreement. Now, we will show that using the Qd assumption alone, we can achieve termination with O(Lout · n1+1/d ) bits of further communication. Thus, we will show that our asynchronous lower bounds are tight, not just for the specific adversary n,d n,d structure families Zproj and Z2-proj but for send-omission adversaries that are characterized by d Q -satisfying adversary structures in general. To obtain this result, we design a termination protocol Term that can add termination to any general-omission tolerant agreement protocol with O(Lout · n1+1/d ) bits of further communication (where Lout is the length of the output the parties agreed on), assuming the adversary is characterized by a Qd -satisfying adversary structure Z. In particular, one can compose PullCast with Term to get a terminating reliable broadcast protocol for L-bit inputs which can tolerate any Qd general-omission adversary with O(Ln1+1/d + n2 log n) bits of communication. At the end of the section, we also sketch how Term can be made byzantine fault tolerant when d ≥ 3. ▶ Proposition 9. For every d ≥ 1 and every Qd -satisfying n-party adversary structure Z, there exists a non-empty party set G ⊆ [n] such that |G \ Z| ≥ |G|n−1/d for all Z ∈ Z. Proof. We prove the proposition with a greedy algorithm that finds the set G. Let S0 = [n]. For each i ∈ [d], we inductively define the sets Zi and Si as follows: Zi is any arbitrary set in Z which minimizes |Si−1 \ Zi |, and Si = Si−1 \ Zi . Observe that by the Qd condition we have Sd Sd = [n] \ ( i=1 Zi ) ̸= ∅. This means that there have to exist two successive terms |Si |, |Si+1 | in the sequence |S0 |, |S1 |, . . . , |Sd | such that |Si+1 | ≥ |Si |n−1/d , as otherwise we would have 16

Intrusion tolerance [42] means that the parties agree on either a correct party’s input or a safe default value ⊥. The latter can only happen if the correct parties have non-matching inputs. If the parties agree on ⊥ in our reduction, then they can output ⊥ from the whole protocol instead of running PullCast.

M. Mizrahi and R. Wattenhofer

23

|Sd | < |S0 |(n−1/d )d = 1. The set G we seek is the set Si such that |Si+1 | ≥ |Si |n−1/d , since we have |Si+1 | = minZ∈Z |Si \ Z| by definition. ◀ In Term, we use the set G from Proposition 9 by tasking the parties in G = {g1 , . . . , g|G| } with helping every party terminate. That is, we encode the agreed upon output v into |G| symbols (s1 , . . . , s|G| ) with a (|G|, ⌈|G|n−1/d ⌉)-erasure code, and require each party gi ∈ G to send everyone the symbol sgi . Because G contains at least ⌈|G|n−1/d ⌉ correct parties, this suffices for every party to receive at least ⌈|G|n−1/d ⌉ symbols and thus learn v. Finally, to obtain termination, we add totality: We make it so that before a party i terminates Term with the output v, i sends each symbol sgj to the respective party gj , and thus ensures that every correct party in G will be able to fulfill its duty. Formally, Term involves some other asynchronous protocol Π which the other parties run. Π here can be any protocol which guarantees that no two parties (correct or faulty) obtain distinct outputs from it.17 Term is sequentially composed with Π, and it ensures the following totality property: If any correct party outputs from Π, then every correct party terminates Term. Furthermore, there can be no spurious Term outputs: If a party outputs v from Term, then some party must have output v from Π earlier. Note that if any party terminates Term, then it also terminates Π (stops running it) whether or not it has output from Π, as this is the whole point of Term. Depending on Π (for example if Π is PullCast), this quitting can cause Π to lose its liveness, preventing the other correct parties from outputting from Π, but Term still ensures that every correct party terminates with the correct output.

Term Code for a party i 1: (s̃1 , . . . , s̃|G| ) ← (⊥, . . . , ⊥) and relayed ← false 2: upon learning the output v (from Π or via decoding) do 3: (s1 , . . . , s|G| ) ← Enc|G|,⌈|G|n−1/d ⌉ (v) 4: for each gj ∈ G do 5: send ⟨SYM, gj , sj ⟩ to gj 6: if i ∈ G and relayed = false then 7: send ⟨SYM, i, si ⟩ to all parties 8: terminate Term with the output v and quit Π 9: upon receiving a message ⟨SYM, j, s⟩ do 10: if i ∈ G and j = i and relayed = false then 11: send ⟨SYM, i, s⟩ to all parties 12: relayed ← true 13: s̃j ← s 14: if the vector (s̃1 , . . . , s̃|G| ) contains exactly ⌈|G|n−1/d ⌉ non-⊥ symbols then 15: v ← Dec|G|,⌈|G|n−1/d ⌉ (s̃1 , . . . , s̃|G| ) 16: trigger the “learning the output v” block ▶ Theorem 10. Suppose Π is a protocol from which the parties can only obtain equal outputs. If a correct party outputs from Π, then every correct party terminates Term, and a party can only output any v from Term if some party (possibly the same party) output v from Π earlier. 17

To keep our lower bounds for asynchronous protocols general, we proved them using only the agreement property that the correct parties’ outputs match. However, for Term to work, we also need Π to achieve the uniform agreement guarantee that no two parties (correct or faulty) obtain non-matching outputs. Note that PullCast achieves this natural guarantee, as explained in its security proof.

24

Multivalued Consensus: General Adversaries Require More Communication

Proof. Let v be the uniquely determined value such that the parties can only output v from Π. If v does not exist at some point in time (i.e. if Π has not reached univalency), then no one has output from Π. This prevents the parties from terminating Term. The reason is that the first SYM message in a Term execution must be sent by a party who already knows the output v it will terminate Term with, which means that if there is a first party who outputs some v from Term, then it decides on v not via decoding SYM messages but via outputting v from Π. Now, suppose that some correct party i outputs v from Π. Then, this party i will compute (s1 , . . . , s|G| ) ← Enc|G|,⌈|G|n−1/d ⌉ (v) and send each symbol sj to the party gj for all j ∈ [|G|], thus enabling the party gj ∈ G to send everyone the symbol sj . Each party gj sends everyone the symbol sj (either once it receives sj from another party or once it computes sj just before it outputs) and G contains at least ⌈|G|n−1/d ⌉ correct parties; consequently, everyone receives at least ⌈|G|n−1/d ⌉ symbols from the parties in G. This is enough for every party to receive ⌈|G|n−1/d ⌉ symbols, decode them into v and finally terminate Term with the output v, unless the party terminates Term with the output v earlier by outputting v from Π. ◀ The Complexity of Term. Let Lout be the length of the output v that the parties obtain from Π. The communication in Term consists of at most 2n|G| SYM messages: n|G| for each party i ∈ [n] to inform each party gj ∈ G of the symbol sj , and n|G| for each party gj ∈ G to inform everyone else of sj . With Reed-Solomon erasure coding, the symbols are of size Lout 1+1/d O( |G|n + n|G| log n) = −1/d + log n); so, the total communication complexity is O(Lout · n O(Lout · n1+1/d + n2 log n) bits. Finally, the latency is 2; that is, if a correct party i outputs from Π at some time T in an execution where the adversary delays each message by at most 1 time unit, then every correct party outputs by the time T + 2. This is because with one hop the party i informs every party gj ∈ G of the symbol sj , and with a second hop the correct parties in G all send everyone the symbols they need to learn the output and terminate. Byzantine Fault Tolerance. Term tolerates general-omission adversaries. While a formal treatment of byzantine fault tolerance is out of scope, we sketch how a byzantine fault tolerant version of Term could work, assuming the Qd condition for any d ≥ 3. For this, we only need to introduce some mechanism to protect the parties from any incorrect/inconsistent symbols that the byzantine parties might propose, and as we discussed in the previous subsection, this can be done by attaching a Merkle proof to each symbol to prove the symbol correct. These proofs would be relative to the Merkle tree computed on the vector (s1 , . . . , s|G| ). To unanimously establish the root hash, the parties would also run a simple quadratic-complexity reliable agreement protocol (with this requiring the Q3 condition) in parallel, and terminate it before they terminate Term. A party’s reliable agreement input would be the root hash h which it can compute upon outputting v from Π.18

7

Discussion & Future Work

In this work, we proved a general Ω(Lout · n1+1/d ) bit communication complexity lower bound against Qd adversaries for a variety of fundamental agreement tasks; assuming the requirement

18

Reliable agreement [20] is a termination protocol like Term. We would use it here to ensure that if some correct party terminates it with the root hash, then all of them terminate it with the root hash. While the reliable agreement protocol in [20] is for t < n/3 threshold byzantine adversaries, it is easy to adapt it to the Q3 setting with a standard transformation [31]: Replace any line which says “upon receiving a message m from k parties” with “upon receiving m from a set of S parties such that Pk (S) holds,” where Pk (S) is the predicate for whether S ̸∈ Z if k = t + 1, and for whether [n] \ S ∈ Z if k = n − t.

M. Mizrahi and R. Wattenhofer

of error-free security against byzantine adversaries in the synchronous setting and assuming termination against send-omission adversaries in the asynchronous setting. Synchronous Tightness. An open question we leave for future work is whether the lower bounds we have proven for error-free synchronous protocols are tight (not necessarily just for n,d Zproj but for Qd adversaries in general), and if so, to come up with protocols that match them. While the combination of byzantine faults and error-free security might make it quite difficult to design such protocols, we conjecture that our lower bounds for synchronous protocols are tight like their asynchronous counterparts. Las Vegas Protocols. To keep our proofs clear in the synchronous setting, we assumed a fixed round complexity of R. However, our entropy-based arguments extend to all error-free synchronous protocols no matter the input length L ≥ 1 or the round complexity, even for Las Vegas style protocols with variable round complexities. That is, one could by adapting Pn Pn our lower bound proofs show that the expected sum E[ i=1 j=i+1 H(Ti↔j )] (where Ti↔j is the transcript describing the communication between i and j) is Ω(Ln2+1/d ) for interactive consistency and Ω(Ln1+1/d ) for byzantine agreement/broadcast, no matter L or the round complexity.19 Less abstractly, these are the correct communication complexity lower bounds for any error-free synchronous protocol in a tagged communication model where each message is tagged with the pertinent metadata (sender/receiver IDs and a round number), no matter the round complexity. Intuitively speaking, the reason is that when these tags are included in the messages, a transcript TS↔i between a party set S and a party i becomes just a message sequence, and a lower bound of H(TS↔i ) ≥ h = Ω(1) for the transcript entropy also implies a lower bound of Ω(h) for the expected total length of the messages. Termination with High Probability. Another class of protocols which merit attention are asynchronous protocols that terminate with high probability, but not probability 1. While we chose not to formalize these protocols to avoid greatly complicating the math, we conjecture that our lower bounds for asynchronous protocols generalize to them. A way to adapt our proofs to show this formally could be to use events which track if some parties or party sets terminate as they should, and only lower bound the communication complexity of the good executions where the events all occur. One would also have to condition the input distribution on the events occurring and account for the resulting input distribution entropy loss, as the posterior distribution of the inputs when the parties terminate may be non-uniform. Balanced Communication. An exciting question which we did not consider in this work is how balanced the communication can be. In the threshold adversary setting, it is considered good for a protocol to be balanced. Such a protocol ensures that if there are c correct parties in an execution, then each of them shoulders a O( 1c ) proportion of the total communication complexity. In non-symmetric protocols (where the parties take on different roles), achieving balance can be quite challenging. For example, a balanced reliable broadcast protocol which costs O(Ln + n2 log n) bits [3] cannot allow the sender to just send its input to everyone else.

19

Note that the reduction from byzantine broadcast to interactive consistency (Corollary 2) breaks if the byzantine broadcast protocol does not have a fixed round complexity R, as our strategy to cleanly separate the broadcast instances was to allot a block of R rounds to each instance. To address this issue without needing protocol ID tags, we can instead employ a round-robin schedule, where for each k ∈ [n] the parties run the kth byzantine broadcast instance in a round r iff r ≡ k (mod n).

25

26

Multivalued Consensus: General Adversaries Require More Communication

We are curious about when general adversary tolerant protocols (and protocols like PullCast which can tolerate t < n faults) can be balanced. As far as we are aware, this question has not been studied before. The answer could depend on whether the network is synchronous or not, on the adversary, and on whether termination is required if the network is asynchronous. Crash Faults. A question one may ask is: Do our lower bounds for terminating asynchronous protocols also hold against crash faults? The answer is no, at least not for reliable broadcast, if the adversary must deliver the messages that a crashing party sent before crashing. To show this, we sketch a simple terminating reliable broadcast protocol that costs L(n − 1) + O(n2 ) bits and can tolerate any number of crash faults. The sender sends everyone its L-bit input, and after this it reliably broadcasts the string OK with a reliable broadcast instance RB ok (using the echo-based protocol in [28]) to signal to the other parties that it did not crash before it sent everyone its input. Then, a party can terminate the full protocol after terminating RB ok and receiving the sender’s message. If the sender is correct, then every correct party receives its input and terminates RB ok . If the sender crashes before it can send everyone its input, then it never initiates the broadcast RB ok , and therefore the parties never terminate RB ok . And finally, if the sender crashes after it sends everyone its input, then the correct parties either all terminate RB ok or all not terminate it, and in the former case they all receive the sender’s input. An implication of this protocol is that Locher’s communication complexity lower bound of (1.5 − o(1))Ln bits for 3-round reliable broadcast against t < n3 crash faults when the sender is only allowed to send o(Ln) bits in the first round20 [35] no longer holds if the last restriction is lifted. The 1.5Ln Bound. We showed in this work by designing PullCast that for any fixed ε > 0, one can solve non-terminating reliable broadcast with (1 + ε)Ln bits of communication when the input length L is sufficiently large. This is of interest in light of Locher’s O(1.5 − o(1))Ln bit lower bound [35], which he conjectured might extend beyond the class of reliable broadcast protocols for which he proved the bound. As we explained in the previous paragraph, the bound does not extend to all crash fault tolerant reliable broadcast protocols, and PullCast shows that non-terminating protocols can beat this bound even against stronger adversaries. So, the question is: To what protocols does this bound generalize? Based on the research we have done since this paper’s acceptance, we have come to believe that the lower bound holds for all well-balanced reliable broadcast protocols (e.g. Locher and Shoup’s MiniCast [36]), where the expected number of bits sent by each party is roughly equal across all n parties. We intend to formally address this question in future work, as there are subtleties regarding termination and whether crash faults suffice to induce the lower bound. References 1

2

20

Ittai Abraham and Gilad Asharov. ABEL: Perfect Asynchronous Byzantine Extension from List-Decoding. In Dariusz R. Kowalski, editor, 39th International Symposium on Distributed Computing (DISC 2025), volume 356 of Leibniz International Proceedings in Informatics (LIPIcs), pages 1:1–1:20, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.DISC.2025.1. Ittai Abraham, T-H. Hubert Chan, Danny Dolev, Kartik Nayak, Rafael Pass, Ling Ren, and Elaine Shi. Communication complexity of byzantine agreement, revisited. In Proceedings of the

The lower bound requires that when the sender is correct, a synchronous implementation of the protocol requires at most 3 rounds for the correct parties to output. The protocol we gave satisfies this guarantee.

M. Mizrahi and R. Wattenhofer

3

4

5

6

7

8

9 10 11 12

13 14

15

16

17

2019 ACM Symposium on Principles of Distributed Computing, PODC ’19, page 317–326, New York, NY, USA, 2019. Association for Computing Machinery. doi:10.1145/3293611.3331629. Nicolas Alhaddad, Sourav Das, Sisi Duan, Ling Ren, Mayank Varia, Zhuolun Xiang, and Haibin Zhang. Balanced byzantine reliable broadcast with near-optimal communication and improved computation. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, PODC ’22, page 399–417, New York, NY, USA, 2022. Association for Computing Machinery. doi:10.1145/3519270.3538475. Ananya Appan, Anirudh Chandramouli, and Ashish Choudhury. Network agnostic perfectly secure multiparty computation against general adversaries. IEEE Transactions on Information Theory, 71(1):644–682, 2025. doi:10.1109/TIT.2024.3470513. Hagit Attiya and Jennifer L. Welch. Multi-Valued Connected Consensus: A New Perspective on Crusader Agreement and Adopt-Commit. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023), volume 286 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1–6:23, Dagstuhl, Germany, 2024. Schloss Dagstuhl – LeibnizZentrum für Informatik. doi:10.4230/LIPIcs.OPODIS.2023.6. Amos Beimel. Secret-sharing schemes: A survey. In Yeow Meng Chee, Zhenbo Guo, San Ling, Fengjing Shao, Yuansheng Tang, Huaxiong Wang, and Chaoping Xing, editors, Coding and Cryptology, pages 11–46, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. doi: 10.1007/978-3-642-20901-7_2. Michael Ben-Or, Ran Canetti, and Oded Goldreich. Asynchronous secure computation. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’93, page 52–61, New York, NY, USA, 1993. Association for Computing Machinery. doi: 10.1145/167088.167109. P. Berman, J. A. Garay, and K. J. Perry. Towards optimal distributed consensus. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science, SFCS ’89, page 410–415, USA, 1989. IEEE Computer Society. doi:10.1109/SFCS.1989.63511. Piotr Berman, Juan A. Garay, and Kenneth J. Perry. Bit Optimal Distributed Consensus, pages 313–321. Springer US, Boston, MA, 1992. doi:10.1007/978-1-4615-3422-8_27. A. Beutelspacher and U. Rosenbaum. Projective Geometry: From Foundations to Applications. Projective Geometry: From Foundations to Applications. Cambridge University Press, 1998. Gabriel Bracha. Asynchronous byzantine agreement protocols. Information and Computation, 75(2):130–143, 1987. doi:10.1016/0890-5401(87)90054-X. Konstantinos Brazitikos and Vassilis Zikas. General adversary structures in byzantine agreement and multi-party computation with active and omission corruption. In Elette Boyle and Mohammad Mahmoody, editors, Theory of Cryptography, pages 200–233, Cham, 2025. Springer Nature Switzerland. doi:10.1007/978-3-031-78023-3_7. C. Cachin, R. Guerraoui, and L. Rodrigues. Introduction to Reliable and Secure Distributed Programming. Computer Science. Springer Berlin Heidelberg, 2011. C. Cachin and S. Tessaro. Asynchronous verifiable information dispersal. In 24th IEEE Symposium on Reliable Distributed Systems (SRDS’05), pages 191–201, 2005. doi:10.1109/ RELDIS.2005.9. Jinyuan Chen. Optimal Error-Free Multi-Valued Byzantine Agreement. In Seth Gilbert, editor, 35th International Symposium on Distributed Computing (DISC 2021), volume 209 of Leibniz International Proceedings in Informatics (LIPIcs), pages 17:1–17:19, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.DISC.2021.17. Wutichai Chongchitmate and Rafail Ostrovsky. Information-theoretic broadcast with dishonest majority for long messages. In Amos Beimel and Stefan Dziembowski, editors, Theory of Cryptography, pages 370–388, Cham, 2018. Springer International Publishing. doi:10.1007/ 978-3-030-03807-6_14. Ashish Choudhury. Almost-surely terminating asynchronous byzantine agreement against general adversaries with optimal resilience. In Proceedings of the 24th International Conference

27

28

Multivalued Consensus: General Adversaries Require More Communication

18 19

20

21 22 23 24 25

26

27

28 29 30 31

32 33

34

35

on Distributed Computing and Networking, ICDCN ’23, page 167–176, New York, NY, USA, 2023. Association for Computing Machinery. doi:10.1145/3571306.3571333. Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. John Wiley & Sons, Inc., second edition, 2006. doi:10.1002/047174882X. Ivan Bjerre Damgård, Boyang Li, and Nikolaj Ignatieff Schwartzbach. More Communication Lower Bounds for Information-Theoretic MPC. In Stefano Tessaro, editor, 2nd Conference on Information-Theoretic Cryptography (ITC 2021), volume 199 of Leibniz International Proceedings in Informatics (LIPIcs), pages 2:1–2:18, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITC.2021.2. Sourav Das, Sisi Duan, Shengqi Liu, Atsuki Momose, Ling Ren, and Victor Shoup. Asynchronous consensus without trusted setup or public-key cryptography. In Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security, CCS ’24, page 3242–3256, New York, NY, USA, 2024. Association for Computing Machinery. doi:10.1145/3658644.3670327. D. Dolev and H. R. Strong. Authenticated algorithms for byzantine agreement. SIAM Journal on Computing, 12(4):656–666, 1983. doi:10.1137/0212045. Danny Dolev. The byzantine generals strike again. Journal of Algorithms, 3(1):14–30, 1982. doi:10.1016/0196-6774(82)90004-9. Danny Dolev and Rüdiger Reischuk. Bounds on information exchange for byzantine agreement. J. ACM, 32(1):191–204, 1 1985. doi:10.1145/2455.214112. P. Elias. Universal codeword sets and representations of the integers. IEEE Transactions on Information Theory, 21(2):194–203, 1975. doi:10.1109/TIT.1975.1055349. Paul Feldman and Silvio Micali. Optimal algorithms for byzantine agreement. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC ’88, page 148–161, New York, NY, USA, 1988. Association for Computing Machinery. doi:10.1145/62212.62225. Matthias Fitzi and Martin Hirt. Optimally efficient multi-valued byzantine agreement. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, PODC ’06, page 163–168, New York, NY, USA, 2006. Association for Computing Machinery. doi:10.1145/1146381.1146407. Eli Gafni. Round-by-round fault detectors (extended abstract): unifying synchrony and asynchrony. In Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, PODC ’98, page 143–152, New York, NY, USA, 1998. Association for Computing Machinery. doi:10.1145/277697.277724. Vassos Hadzilacos and Sam Toueg. A modular approach to fault-tolerant broadcasts and related problems. Technical Report TR94-1425, Cornell University, Ithaca, NY, USA, 1994. Martin Hirt and Ueli Maurer. Player simulation and general adversary structures in perfect multiparty computation. Journal of Cryptology, 13(1):31–60, 2000. doi:10.1007/s001459910003. J.N. Kapur. Maximum-entropy Models in Science and Engineering. Wiley, 1989. Klaus Kursawe and Felix C. Freiling. Byzantine fault tolerance on general hybrid adversary structures. Technical Report AIB-2005-09, RWTH Aachen, 4 2005. URL: http://aib. informatik.rwth-aachen.de/2005/2005-09.ps.gz. Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. ACM Trans. Program. Lang. Syst., 4(3):382–401, 7 1982. doi:10.1145/357172.357176. Kasper Green Larsen and Mark Simkin. Secret sharing lower bound: Either reconstruction is hard or shares are long. In Clemente Galdi and Vladimir Kolesnikov, editors, Security and Cryptography for Networks, pages 566–578, Cham, 2020. Springer International Publishing. doi:10.1007/978-3-030-57990-6_28. Andrew Lewis-Pye. Reaching univalency with subquadratic communication. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’26, page 188–196, New York, NY, USA, 2026. Association for Computing Machinery. doi:10.1145/3796701.3815918. Thomas Locher. Byzantine Reliable Broadcast with Low Communication and Time Complexity. In Silvia Bonomi, Letterio Galletta, Etienne Rivière, and Valerio Schiavoni, editors, 28th

M. Mizrahi and R. Wattenhofer

International Conference on Principles of Distributed Systems (OPODIS 2024), volume 324 of Leibniz International Proceedings in Informatics (LIPIcs), pages 16:1–16:17, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs. OPODIS.2024.16. 36

Thomas Locher and Victor Shoup. Minicast: Minimizing the communication complexity of reliable broadcast. In Advances in Cryptology – EUROCRYPT 2025: 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Madrid, Spain, May 4–8, 2025, Proceedings, Part V, page 96–115, Berlin, Heidelberg, 2025. Springer-Verlag. doi:10.1007/978-3-031-91092-0_4.

37

Thomas Locher and Victor Shoup. Towards reliable broadcast with optimal communication and round complexity. In Proceedings of the 38th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’26, page 155–166, New York, NY, USA, 2026. Association for Computing Machinery. doi:10.1145/3816782.3819206.

38

Yuan Lu, Zhenliang Lu, Qiang Tang, and Guiling Wang. Dumbo-mvba: Optimal multi-valued validated asynchronous byzantine agreement, revisited. In Proceedings of the 39th Symposium on Principles of Distributed Computing, PODC ’20, page 129–138, New York, NY, USA, 2020. Association for Computing Machinery. doi:10.1145/3382734.3405707. √ Mamoru Maekawa. A N algorithm for mutual exclusion in decentralized systems. ACM Trans. Comput. Syst., 3(2):145–159, 5 1985. doi:10.1145/214438.214445.

39 40

Ralph C. Merkle. A digital signature based on a conventional encryption function. In Carl Pomerance, editor, Advances in Cryptology — CRYPTO ’87, pages 369–378, Berlin, Heidelberg, 1988. Springer Berlin Heidelberg. doi:10.1007/3-540-48184-2_32.

41

Mose Mizrahi Erbes and Roger Wattenhofer. Quit-Resistant Reliable Broadcast and Efficient Terminating Gather. In Silvia Bonomi, Letterio Galletta, Etienne Rivière, and Valerio Schiavoni, editors, 28th International Conference on Principles of Distributed Systems (OPODIS 2024), volume 324 of Leibniz International Proceedings in Informatics (LIPIcs), pages 15:1–15:22, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/ LIPIcs.OPODIS.2024.15.

42

Achour Mostéfaoui and Michel Raynal. Signature-free broadcast-based intrusion tolerance: Never decide a byzantine value. In Chenyang Lu, Toshimitsu Masuzawa, and Mohamed Mosbah, editors, Principles of Distributed Systems, pages 143–158, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. doi:10.1007/978-3-642-17653-1_13.

43

Kartik Nayak, Ling Ren, Elaine Shi, Nitin H. Vaidya, and Zhuolun Xiang. Improved Extension Protocols for Byzantine Broadcast and Agreement. In Hagit Attiya, editor, 34th International Symposium on Distributed Computing (DISC 2020), volume 179 of Leibniz International Proceedings in Informatics (LIPIcs), pages 28:1–28:17, Dagstuhl, Germany, 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.DISC.2020.28.

44

Jeff M. Phillips, Elad Verbin, and Qin Zhang. Lower bounds for number-in-hand multiparty communication complexity, made easy. SIAM Journal on Computing, 45(1):174–196, 2016. doi:10.1137/15M1007525.

45

I. S. Reed and G. Solomon. Polynomial codes over certain finite fields. Journal of the Society for Industrial and Applied Mathematics, 8(2):300–304, 1960. doi:10.1137/0108018.

46

Robert Robere, Toniann Pitassi, Benjamin Rossman, and Stephen A. Cook. Exponential lower bounds for monotone span programs. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 406–415, 2016. doi:10.1109/FOCS.2016.51.

47

Adi Shamir. How to share a secret. Commun. ACM, 22(11):612–613, 11 1979. doi:10.1145/ 359168.359176.

48

Sam Toueg. Randomized byzantine agreements. In Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing, PODC ’84, page 163–178, New York, NY, USA, 1984. Association for Computing Machinery. doi:10.1145/800222.806744.

29

30

Multivalued Consensus: General Adversaries Require More Communication

49

50 51

A

Russell Turpin and Brian A Coan. Extending binary byzantine agreement to multivalued byzantine agreement. Information Processing Letters, 18(2):73–76, 1984. doi:10.1016/ 0020-0190(84)90027-9. Song Y. Yan. Algorithmic Number Theory, pages 139–258. Springer Berlin Heidelberg, Berlin, Heidelberg, 2000. doi:10.1007/978-3-662-04053-9_2. Vassilis Zikas. Generalized corruption models in secure multi-party computation. PhD thesis, ETH Zurich, 2010. URL: https://d-nb.info/1005005729.

Information Theory Lemmas

In this section, we prove the information-theoretic lemmas we use to obtain our lower bounds. We begin with Lemma 7, which is about how much communication a party i must receive from a set of parties S to learn the output X of an asynchronous protocol from them. ▶ Lemma 7. Let X be some finite uniformly random variable. Suppose that in a randomized asynchronous n-party protocol, some party i must output a prediction Yi of X solely based on the messages it receives from some fixed set of parties S ⊆ [n] \ {i}, and this prediction must satisfy Pr[Yi = X] ≥ 0.5 + ε for some absolute constant ε > 0. If i’s initial knowledge prior to running the protocol (its randomness and its input if it has any) is independent of X, then the one-way transcript TS→i describing the communication directed from S to i must have at least ε′ H(X) bits of Shannon entropy for some absolute constant ε′ > 0. Proof. Firstly, we assume |supp(X)| ≥ 2. If not, then H(X) = 0, and the lemma is trivial. Let s = H(X). Since X is uniformly random, we have s = log2 (|supp(X)|) ≥ 1. Hence, the fact that Pr[Yi = X] ≥ 0.5+ε gives us H(X | Yi ) ≤ Hb (0.5−ε)+(0.5−ε) log2 (2s −1) by Fano’s inequality [18], where Hb (0.5 − ε) < 1 is the binary entropy of (0.5 − ε). Therefore, the mutual information I(X ; Yi ) is at least H(X) − H(X | Yi ) ≥ s − Hb (0.5 − ε) − (0.5 − ε) log2 (2s − 1) = Ω(s). This function is positive for all s ≥ 1 because it equals 1 − Hb (0.5 − ε) > 0 when s = 1 and has a positive derivative in [1, ∞), which means that it is lower bounded by ε′ s = ε′ H(X) for some absolute constant ε′ > 0. Observe that X → (TS→i , Wi ) → Yi is a Markov chain, where the variable Wi represents i’s initial state (its input if it has any, and its local randomness). The reason is that when i decides to output from the protocol, it computes its output Yi deterministically based on TS→i and Wi . So, the data processing inequality [18] gives us I(X ;TS→i , Wi ) ≥ I(X ;Yi ) ≥ ε′ H(X). Moreover, because X and Wi are independent, the chain rule for mutual information gives us I(X ; TS→i , Wi ) = I(X ; Wi ) + I(X ; TS→i | Wi ) = I(X ; TS→i | Wi ). Consequently, we have H(TS→i ) ≥ H(TS→i | Wi ) ≥ I(X ; TS→i | Wi ) ≥ ε′ H(X), as desired. ◀ Next, we have the lemmas regarding the conversion from transcript entropy to expected communication complexity. They are as follows. ▶ Lemma 11. Let i be any party, and let S be any non-empty set of parties excluding i. If a synchronous R-round protocol is such that in its random fault-free executions the bidirectional transcript TS↔i which describes the communication between S and i has at least εR|S| bits of entropy for some constant ε > 0, then for some constant ε′ > 0 these executions involve at least ε′ H(TS↔i ) bits of expected communication between S and i. ▶ Lemma 12. Let i be any party, and let S be any non-empty set of parties excluding i. If an asynchronous protocol is such that in its random fault-free executions the one-way transcript TS→i which describes the communication from S to i has at least ε|S| bits of entropy for some constant ε > 0, then in these executions the parties in S send at least ε′ H(TS→i ) bits to i in

M. Mizrahi and R. Wattenhofer

expectation for some constant ε′ > 0, assuming the adversary is such that for any two parties j < j ′ ∈ S it never delivers a message from j to i after delivering it a message from j ′ . Note the restriction to the adversary’s scheduling strategy in Lemma 12. This restriction will allow us to encode transcripts more efficiently. We can assume this restriction since in our asynchronous protocol lower bound proofs, the adversary always causes the parties in S to terminate before it delivers any of their messages to i. Hence, the adversary can abide by the restriction by sorting the messages before delivering them, and the parties in S will not later on break the assumption by sending more messages. To prove these lemmas, we first prove a technical proposition about the relation between the entropy of a random string and its expected length. ▶ Proposition 13. For any random bitstring M of a random length |M | ≥ 0, if H(M ) ≥ ε for some constant ε > 0, then E[|M |] ≥ ε′ H(M ) for some constant ε′ > 0. Proof. Firstly, note that E[|M |] > 0. Else, M would be the empty string, with H(M ) = 0. Let L = |M | (a random variable itself), let supp(L) = {ℓ ∈ N : Pr[L = ℓ] > 0}, and let µ = E[L] > 0. For any ℓ ∈ supp(L), we have H(M | L = ℓ) ≤ ℓ as the maximum-entropy way to choose an ℓ-bit string is to choose it uniformly at random, with ℓ bits of entropy. Hence, P P H(M | L) = ℓ∈supp(L) Pr[L = ℓ] · H(M | L = ℓ) ≤ ℓ∈supp(L) Pr[L = ℓ] · ℓ = µ. Finally, the chain rule gives us H(M ) ≤ H(M, L) = H(M | L) + H(L) ≤ µ + H(L). The maximum-entropy way to randomly choose L ∈ {0, 1, . . . } given its expected value µ µℓ is to choose L according to a geometric distribution with Pr[L = ℓ] = (µ+1) ℓ+1 for all ℓ ≥ 0 P∞ µℓ µℓ [30], which means that H(L) ≤ − ℓ=0 (µ+1)ℓ+1 log2 ( (µ+1)ℓ+1 ) = (µ+1) log2 (µ+1)−µ log2 µ. Hence, we have H(M ) ≤ µ + H(L) ≤ µ + (µ + 1) log2 (µ + 1) − µ log2 µ. x Let f (x) = x + (x + 1) log2 (x + 1) − x log2 x, and let g(x) = f (x) . What we would like ′ to show is that H(M ) ≥ ε =⇒ µ ≥ ε H(M ). We have H(M ) ≤ f (µ), which implies that µ = g(µ) · f (µ) ≥ g(µ) · H(M ). So, our goal is to find some ε′ > 0 which depends only on ε such that g(µ) ≥ ε′ . As f (x) is continuously and strictly increasing in (0, ∞) without an upper bound and limx→0+ f (x) = 0, f has an inverse f −1 : (0, ∞) → (0, ∞). Let µ0 = f −1 (ε). We have f (µ) ≥ H(M ) ≥ ε = f (µ0 ), which means that µ ≥ µ0 because f is increasing. We can thus set ε′ = g(µ0 ) = µε0 and conclude that µ ≥ ε′ H(M ). This choice works because g is also an increasing function in (0, ∞), which means that g(µ) ≥ g(µ0 ) = ε′ . −1 Note that the ε′ = f ε(ε) we get from this argument approaches 1 as ε → ∞, due to the fact that f (x) ≈ x ≈ f −1 (x) for large values of x. ◀ We use Proposition 13 to prove a generalization of it for arrays of random bitstrings. ▶ Lemma 14. For any N ≥ 1, let M1 , . . . , MN be any sequence of N variable-length random PN bitstrings (which are possibly empty) such that i=1 H(Mi ) ≥ εN for some constant ε > 0. PN PN Then E[ i=1 |Mi |] ≥ ε′ i=1 H(Mi ) for some constant ε′ > 0. Proof. Let Ismall = {i ∈ [N ] : H(Mi ) < 2ε }, and let Ilarge = [N ] \ Ismall . Observe that we have P P PN PN εN εN 1 i∈Ismall H(Mi ) ≤ 2 , which implies i∈Ilarge H(Mi ) ≥ i=1 H(Mi ) − 2 ≥ 2 i=1 H(Mi ). By Proposition 13, there is a constant ε′ > 0 such that E[|Mi |] ≥ ε′ H(Mi ) for all i ∈ Ilarge , PN P P ′ PN which gives us E[ i=1 |Mi |] ≥ E[ i∈Ilarge |Mi |] ≥ ε′ i∈Ilarge H(Mi ) ≥ ε2 i=1 H(Mi ). ◀ Finally, to prove Lemmas 11 and 12, we assume that the parties’ messages are encoded with a prefix-free code, so that the concatenation m1 ||m2 || . . . ||mk of any messages can be decoded into the vector (m1 , . . . , mk ). We can assume this without loss of generality since we can get prefix-free messages without an asymptotic cost via Elias delta encoding [24].

31

32

Multivalued Consensus: General Adversaries Require More Communication

Proof of Lemma 11. Suppose S = {s1 , . . . , s|S| }. As the protocol takes R rounds, we can represent TS↔i with an R × |S| × 2 multidimensional array A which is defined as follows: For all (r, j) ∈ [R] × [|S|], A[r][j][0] is filled with the concatenation of the messages i received in order from sj on round r (an empty string if i received no messages from sj ), and likewise A[r][j][1] is filled with the concatenation of the messages sj received from i on round r. Suppose we encode the transcript TS↔i into an array A via the encoding described above. For each c = (c1 , c2 , c3 ) ∈ [R]×[|S|]×[2], let Mc refer to random string in the cell A[c1 ][c2 ][c3 ]. P We want to lower bound the expected value of B = c |Mc |, as B is the number of bits sent. For this, we observe that the transcript TS↔i is fully described by the cells Mc , which means P that we have c H(Mc ) ≥ H(TS↔i ) ≥ εR|S| by the sub-additivity of entropy. By Lemma 14, P P this gives us E[B] = E[ c |Mc |] ≥ ε′ c H(Mc ) ≥ ε′ H(TS↔i ) for some constant ε′ > 0. ◀ Proof of Lemma 12. Suppose S = {s1 , . . . , s|S| }. We encode the transcript TS→i into an |S|-element array A as follows: For each j ∈ [|S|], we fill the cell A[j] with the concatenation of the messages i received from sj j, in the order i received them. Under the ordering assumption we made about how the adversary schedules messages, we know for all j < j ′ that i receives all of the messages represented by A[j] from sj before receiving any of the messages represented by A[j ′ ] from sj ′ ; hence, under this scheduling assumption, the array represents the transcript without any information loss. P|S| We want to lower bound the expected value of B = j=1 |A[j]|, since this is the number of bits that i receives from S. As the transcript TS→i is fully described by the array A, we have P|S| j=1 H(A[j]) ≥ H(TS→i ) ≥ ε|S| by the sub-additivity of entropy. Finally, by Lemma 14, we P|S| P|S| have E[B] = E[ j=1 |A[j]|] ≥ ε′ j=1 H(A[j]) ≥ ε′ H(TS→i ) for some constant ε′ > 0. ◀

B

Bounds for All Sufficiently Large n

In Sections 5 and 6, we prove communication complexity lower bounds that hold assuming certain adversary structures exist. That is, we prove that whenever n and d are such that n,d n,d the appropriate adversary structure Zproj or Z2-proj exists, the communication complexity of a task is lower bounded by Ω(Ln1+1/d ) or Ω(Ln2+1/d ). In this section, we extend our bounds by showing that they hold for all sufficiently large n, if d is any fixed constant. We n,d begin by showing this for the bounds that use the adversary structure family Zproj . Let p1 , p2 , p3 , . . . be the list of all prime powers in ascending order, let q(n, d) ≥ 1 be the Pd (p )d+1 −1 (p )d+1 −1 greatest integer such that k=0 (pq(n,d) )k = q(n,d) ≤ n2 , and let sn,d = q(n,d) . pq(n,d) −1 pq(n,d) −1 n,d The adversary structure Zproj exists for any d ≥ 1 if and only if n ≥ 2d+2 − 2 (so that q(n, d) n,d is well-defined) and n = 2sn,d . Recall that in Section 4 we construct Zproj by taking the union ′ of two party sets U and U of size sn,d , where the adversary can always corrupt any party in U ′ . To extend the construction so that it works for all n ≥ 2d+2 − 2, we could redefine U ′ so that it is a party set of size n − sn,d instead of sn,d while keeping the adversary’s ability to corrupt any party in U ′ . Our lower bounds hinge on the fact that |U ′ | = Θ(n), which still holds since we will now have |U ′ | = n − 2sn,d ≥ n2 , and on the fact that |U | = sn,d = Ω(n) (with this implying that each party in U belongs to a Θ(|U |−1/d ) = Θ(n−1/d ) fraction of the projective geometry quorums), which is no longer guaranteed. Below, we show that there exists some Nd ≥ 2d+2 − 2 such that n ≥ Nd =⇒ |U | = sn,d > n4 , which means that the guarantees we want hold for all n ≥ Nd . Observe that for any fixed d, we have limn→∞ q(n, d) = ∞. So, by the prime number theorem [50], which implies that the ratio of successive primes (and thus the ratio of successive p prime powers) tends to 1, we have limn→∞ q(n,d)+1 pq(n,d) = 1. This means that there exists some

M. Mizrahi and R. Wattenhofer

33

√ pq(n,d)+1 d+1 2. For all n ≥ Nd , this gives pq(n,d) ≤ (p )d+1 −1 2(pq(n,d) )d+1 −2 (pq(n,d)+1 )d+1 −2 (pq(n,d)+1 )d+1 −1 ≥ q(n,d)+1 us 2sn,d = ≥ > > n2 , where pq(n,d) −1 pq(n,d) −1 pq(n,d) pq(n,d)+1 −1 (p )d+1 −1 the last inequality holds due to q(n, d) being the greatest integer such that q(n,d) ≤ n2 . pq(n,d) −1 n In conclusion, we have n ≥ Nd =⇒ sn,d > 4 , as desired. n,d The calculations for Z2-proj (which our core set agreement lower bound uses) can be done Pd analogously, by redefining q(n, d) ≥ 1 to be the greatest integer such that k=0 (pq(n,d) )k = (pq(n,d) )d+1 −1 n,d ≤ n3 (well-defined when n ≥ 3(2d+1 − 1)), recalling that Z2-proj partitions the pq(n,d) −1 Nd ≥ 2d+2 − 2 such that for all n ≥ Nd we have

parties into three sets U1 , U2 , U ′ of size sn,d =

(pq(n,d) )d+1 −1 each, increasing the number of pq(n,d) −1 d+1

parties in U ′ from sn,d to n − 2sn,d to make the construction work whenever n ≥ 3(2 − 1), and using the same calculations as above to show that there is some Nd ≥ 3(2d+1 − 1) such that n ≥ Nd =⇒ 2sn,d > n3 . When n ≥ Nd , we would get |U1 | = |U2 | > n6 and |U ′ | ≥ n3 , and these suffice for our core set agreement lower bound (Theorem 5) to hold.

Related documents

• Artificial Minds, Human Disagreement: The Political Challenge of AI Consciousness#689170
• Consensus Formation and Change are Enhanced by Neutrality.#351734
• On the Compatibility of Rational Deliberation and Determinism: Why Deterministic Manipulation Is Not a Counterexample#708185
• Agentic-SecPBFT: Agentic AI-Driven Proactive Security Framework for Wireless PBFT Consensus in Mobile Ad-Hoc Networks#343417
• AI-Enhanced Deliberative Democracy and the Future of the Collective Will#238920