Brief Announcement: From Few to Many Faults: Adaptive Byzantine Agreement with Optimal Communication

Achieving agreement in a distributed setting is fundamental to blockchain systems. Modern blockchains often comprise thousands of nodes attempting to reach consensus. Given the widely accepted resilience model where $t\approx n/3$ validators can be Byzantine, and considering the classical Dolev-Reischuk lower bound of $\mathrm{\Omega }(n^2)$ messages for agreement [11], such systems must exchange millions of messages. This communication overhead results in high latency and limited scalability. This work addresses this challenge through two key contributions:

We bypass the Dolev-Reischuk lower bound by introducing the first partial-synchrony algorithm for Byzantine Agreement that requires only $𝒪(n+t\cdot f)$ messages. This approach is significantly faster compared to the $𝒪(n^2)$ suggested by [11], since often in practice the actual number of misbehaving nodes is small. Our algorithm achieves asymptotically optimal communication complexity, as well as optimal resilience.

Furthermore, we highlight that system robustness is determined not by the relative fraction of possible corruptions but by the absolute number of failures it can tolerate. For instance, it’s easier for an adversary to corrupt a system with $3,001$ nodes that tolerates $1,000$ faults than one with $10,000$ nodes tolerating $2,000$ faults. Building on this insight, we design an algorithm that decouples $n$ and $t$, achieving superior performance when $t\ll n$. Specifically, instead of the known $𝒪(n\cdot t)$ communication complexity, in the asynchronous setting, we achieve agreement with a communication complexity of $𝒪((n+t^2)\cdot \log n)$. This allows system designers to first choose a maximal threshold $t$ of tolerated failures that would still allow for efficient dissemination of $t^2$ messages, and then scale $n$ up to $t^2$ without introducing additional latency. Notably, our algorithm is non-constructive, since it internally utilizes a bipartite expander whose existence has been proven, but no explicit construction is known; when restricted to explicit constructions, the best-known guarantees are slightly weaker.

Finally, we establish that achieving adaptive communication complexity is infeasible in asynchronous settings. Specifically, we prove a lower bound of $\mathrm{\Omega }(n+t^2)$ for any algorithm that guarantees almost-sure termination. This result demonstrates that our algorithm is optimal up to a logarithmic factor.

We consider a set of $n$ parties running a distributed protocol in a fully connected network. Channels are authenticated, meaning that when receiving a message, a party knows who sent it.

In this section, we formally state our results and describe the main components used to obtain them. On the feasibility side, we devise protocols with adaptive communication complexity for all major time models.

In partial synchrony, our algorithm achieves asymptotically optimal communication complexity.

In an asynchronous setting, we show the existence of an algorithm that achieves optimal resilience and a communication complexity that is asymptotically optimal up to a logarithmic factor.

In synchrony, our algorithm has asymptotically optimal adaptive communication and optimal resilience.

All of our results follow a common high-level strategy. First, we execute an adaptive Byzantine Agreement protocol on a subset of parties of size $\mathrm{\Theta }(t)$, which we refer to as the quorum. The communication complexity here only depends on $t$ and $f$. We note that for this step we rely on existing Byzantine Agreement protocols in the synchronous and asynchronous settings, specifically those of Civit et al.[5] and Cachin et al.[4]. In contrast, the $𝒪(n+n\cdot f)$ protocol we use for the partially synchronous setting is our own contribution, described in Section 5. While inspired by Spiegelman’s synchronous protocol for external validity [15], our algorithm advances it in two key ways: it operates in the partially synchronous setting and guarantees strong unanimity.

In the second step, we execute a Quorum-to-All Broadcast (QAB) – a communication primitive introduced in this work – where the quorum nodes disseminate the decided value to the rest of the network. We design QAB protocols for both partially synchronous and asynchronous settings. In particular, our asynchronous QAB leverages bipartite expander graphs to enable efficient communication, constituting one of the key technical contributions of this paper.

On the infeasibility side, we have the following versatile lower bound that shows the impossibility of achieving an adaptive communication complexity in the asynchronous setting.

The main contribution of this result – beyond the fact that it holds under a very weak adversary and a strong algorithmic setting – is that, to the best of our knowledge, it establishes the first lower bound of $\mathrm{\Omega }(t^2)$, in contrast to the $\mathrm{\Omega }(f^2)$ bounds shown in [11, 1]. This bound allows us to claim that the algorithm stated by Theorem 2 has an almost optimal communication complexity, since $\mathrm{\Omega }(n)$ is a trivial lower bound.

In this section, we present a partially synchronous algorithm that achieves an adaptive communication complexity of $𝒪(n+n\cdot f)$. Our algorithm is based on a modified version of Spiegelman’s byzantine agreement protocol for external validity [15], which itself uses Hotstuff’s view synchronization [17] technique. While inspired by Spiegelman’s protocol for network-agnostic settings [15], our work departs significantly in both design and guarantees. We eliminate the asynchronous and randomized components of the original protocol and instead strengthen the synchronous part with additional checks, enabling it to function effectively in partial synchrony after GST. This modification allows us to achieve $𝒪(n\cdot f)$ message complexity for external validity without relying on full synchrony. Crucially, by allowing parties to selectively share their commit proofs upon request, we ensure termination without incurring additional message overhead. Moreover, we extend the protocol to achieve binary strong unanimity – rather than just external validity – by leveraging threshold signatures.

The protocol is organized in views. Each view has a leader, who is chosen in a round-robin way. In the full version of the paper [10], we show that the algorithm is guaranteed to succeed after at most $n$ views after GST. Moreover, if there are no byzantine parties, everyone is guaranteed to decide within constant time after GST.

The algorithm for a single view consists of $4$ phases of a leader asking and other parties responding. A leader proceeds to the next phase once they get $n-t$ responses. On each phase, the leader tries to acquire a new threshold signature, namely the key signature, then the lock and finally the commit signature, each with stronger properties than the other. After $4$ phases pass successfully, the leader obtains broadcasts his value and is guaranteed than only this value can be decided in the future (see Figure 1). We note that if the leader is byzantine or the network is not yet synchronous, the last phase may not be reached by the end of the view. Even then, the threshold values obtained so far are used in subsequent rounds to ensure agreement. A complete description of our protocol as well as a detailed proof for it is given in the full version of our paper [10].

This algorithm, coupled with the QAB primitive, solves Byzantine agreement while tolerating up to parties and using $𝒪(n+t\cdot f)$ messages. Therefore, it satisfies Theorem 1.

To decrease the message complexity, we will rely on a primitive which we call Quorum-to-All Broadcast (abbreviated QAB). Briefly, this primitive allows a small group (of size $\mathrm{\Theta }(t)$) of parties all having the same input value $v_{in}$ to broadcast it to everyone. QAB is defined by the following property that encapsulates classical Agreement, Termination, and Validity.

• $\mathrm{■}$

  Complete correctness: Every honest node eventually decides $v_{in}$.

We next describe our QAB for Asynchrony at a high level. For formal description, as well as the partial synchrony QAB, please refer to the full version of the paper [10].

In order to achieve the stated communication complexity, we restrict the communication between nodes to a specific graph, which we call a communication graph. There are three roles in the algorithm (one node can have multiple roles): quorum nodes - nodes that have a common value to broadcast, relayers - nodes that help quorum nodes disseminate the value and parties - all the nodes, those that need to learn the value. First, quorum nodes agree on a value based on their own proposals, then disseminate it through relayers. Parties then confirm that they have received the value by sending a signed confirmation to relayers who in turn aggregate these confirmations and relay them to quorum nodes. If a quorum node does not receive a confirmation from some party, it sends a value to it directly.

The crux of our result is the utilization of a bipartite (parties, relayers) graph that (I) has few edges (II) an adversary cannot disconnect many parties from the quorum. Please see the full paper [10] for a formal statement of its properties.

We remark that the existence of a bipartite expander with desired properties is only shown non-constructively in [16]. Known explicit bipartite expanders with polynomial time construction [13], when utilized instead, would imply a message complexity of $(n+t^{2+\epsilon })\cdot {\log }^{𝒪(1/\epsilon )}n$.