Byzantine Agreement (BA) allows n processes to propose input values to reach consensus on a common, valid Lo-bit value, even in the presence of up to t < n faulty processes that can deviate arbitrarily from the protocol. Although strategies like randomization, adaptiveness, and batching have been extensively explored to mitigate the inherent limitations of one-shot agreement tasks, there has been limited progress on achieving good amortized performance for multi-shot agreement, despite its obvious relevance to long-lived functionalities such as state machine replication.

Byzantine agreement allows n processes to decide on a common value, in spite of arbitrary failures. The seminal Dolev-Reischuk bound states that any deterministic solution to Byzantine agreement exchanges Ω(n2) bits. In synchronous networks, with a known upper bound on message delays, solutions with optimal O (n2) bit complexity, optimal fault tolerance, and no cryptography have been established for over three decades. However, these solutions lack robustness under adverse network conditions. Therefore, research has increasingly focused on Byzantine agreement for partially synchronous networks, which behave synchronously only eventually and are thus more reflective of real-world conditions. Numerous solutions have been proposed for the partially synchronous setting. However, these solutions are notoriously hard to prove correct, and the most efficient cryptography-free algorithms still require O (n3) exchanged bits in the worst case. Even with cryptography, the state-of-the-art remains a κ-bit factor away from the Ω(n2) lower bound (where κ is the security parameter). This discrepancy between synchronous and partially synchronous solutions has remained unresolved for decades.

This paper introduces Carbon, a high-throughput system enabling asynchronous (safe) and consensus-free (efficient) payments and votes within a dynamic set of clients. Carbon is operated by a dynamic set of validators that may be reconfigured asynchronously, offering its clients eclipse resistance as well as lightweight bootstrap. Carbon offers clients the ability to select validators by voting them in and out of the system thanks to its novel asynchronous and stake-less voting mechanism. Carbon relies on an asynchronous and deterministic implementation of Byzantine reliable broadcast that uniquely leverages a permissionless set of untrusted servers, brokers, to slash the cost of client authentication inherent to Byzantine fault tolerant systems. Carbon is able to sustain a throughput of one million payments per second in a geo-distributed environment, outperforming the state of the art by three orders of magnitude with equivalent latencies.

Byzantine Agreement (BA) enables n processes to reach consensus on a common valid Lo-bit value, even in the presence of up to t < n faulty processes that can deviate arbitrarily from their prescribed protocol. Despite its significance, the optimal communication complexity for key variations of BA has not been determined within the honest majority regime (n = 2t +1), for both the worst-case scenario and the adaptive scenario, which accounts for the actual number f ≤ t of failures. We introduce ada-Dare (Adaptively Disperse, Agree, Retrieve), a novel universal approach to solve BA efficiently. Let κ represent the size of the cryptographic objects required to solve BA when t > n/3. Different instantiations of ada-Dare achieve near-optimal adaptive bit complexity of O(nLo + n(f + 1)κ) for both strong multi-valued validated BA (SMVBA) and interactive consistency (IC). By definition, for IC, Lo = nLin where Lin is the size of an input value. These results achieve optimal O(n(Lo + f)) word complexity and significantly improve the previous best results by up to a linear factor, depending on Lo and f.

Byzantine agreement, arguably the most fundamental problem in distributed computing, operates among n processes, out of which t < n can exhibit arbitrary failures. The problem states that all correct (non-faulty) processes must eventually decide (termination) the same value (agreement) from a set of admissible values defined by the proposals of the processes (validity). Depending on the exact version of the validity property, Byzantine agreement comes in different forms, from Byzantine broadcast to strong and weak consensus, to modern variants of the problem introduced in today's blockchain systems. Regardless of the specific flavor of the agreement problem, its communication cost is a fundamental metric whose improvement has been the focus of decades of research. The Dolev-Reischuk bound, one of the most celebrated results in distributed computing, proved 40 years ago that, at least for Byzantine broadcast, no deterministic solution can do better than Ω(t2) exchanged messages in the worst case. Since then, it remained unknown whether the quadratic lower bound extends to all variants of Byzantine agreement. This paper answers the question in the affirmative, closing this long-standing open problem. Namely, we prove that any non-trivial agreement problem requires Ω(t2) messages to be exchanged in the worst case. To prove the general lower bound, we determine the weakest Byzantine agreement problem and show, via a novel indistinguishability argument, that it incurs Ω(t2) exchanged messages even in the general omission model.

Abstract The Dolev-Reischuk bound says that any deterministic Byzantine consensus protocol has (at least) quadratic (in the number of processes) communication complexity in the worst case: given a system with n processes and at most $$f < n / 3$$ f < n / 3 failures, any solution to Byzantine consensus exchanges $$\Omega \big (n^2\big )$$ Ω ( n 2 ) words, where a word contains a constant number of values and signatures. While it has been shown that the bound is tight in synchronous environments, it is still unknown whether a consensus protocol with quadratic communication complexity can be obtained in partial synchrony where the network alternates between (1) asynchronous periods, with unbounded message delays, and (2) synchronous periods, with $$\delta $$ δ -bounded message delays. Until now, the most efficient known solutions for Byzantine consensus in partially synchronous settings had cubic communication complexity (e.g., HotStuff, binary DBFT). This paper closes the existing gap by introducing SQuad , a partially synchronous Byzantine consensus protocol with $$O\big (n^2\big )$$ O ( n 2 ) worst-case communication complexity. In addition, SQuad is optimally-resilient (tolerating up to $$f < n / 3$$ f < n / 3 failures) and achieves $$O(f \cdot \delta )$$ O ( f · δ ) worst-case latency complexity. The key technical contribution underlying SQuad lies in the way we solve view synchronization , the problem of bringing all correct processes to the same view with a correct leader for sufficiently long. Concretely, we present RareSync , a view synchronization protocol with $$O\big (n^2\big )$$ O ( n 2 ) communication complexity and $$O(f \cdot \delta )$$ O ( f · δ ) latency complexity, which we utilize in order to obtain SQuad .

The Byzantine consensus problem involves n processes, out of which t < n could be faulty and behave arbitrarily. Three properties characterize consensus: (1) termination, requiring correct (non-faulty) processes to eventually reach a decision, (2) agreement, preventing them from deciding different values, and (3) validity, precluding "unreasonable" decisions. But, what is a reasonable decision? Strong validity, a classical property, stipulates that, if all correct processes propose the same value, only that value can be decided. Weak validity, another established property, stipulates that, if all processes are correct and they propose the same value, that value must be decided. The space of possible validity properties is vast. Yet, their impact on consensus algorithms remains unclear.

Consensus enables n processes to agree on a common valid L-bit value, despite t < n/3 processes being faulty and acting arbitrarily. A long line of work has been dedicated to improving the worst-case communication complexity of consensus in partial synchrony. This has recently culminated in the worst-case word complexity of O(n^2). However, the worst-case bit complexity of the best solution is still O(n^2 L + n^2 kappa) (where kappa is the security parameter), far from the Ω(n L + n^2) lower bound. The gap is significant given the practical use of consensus primitives, where values typically consist of batches of large size (L > n). This paper shows how to narrow the aforementioned gap while achieving optimal linear latency. Namely, we present a new algorithm, DARE (Disperse, Agree, REtrieve), that improves upon the O(n^2 L) term via a novel dispersal primitive. DARE achieves O(n^{1.5} L + n^{2.5} kappa) bit complexity, an effective sqrt{n}-factor improvement over the state-of-the-art (when L > n kappa). Moreover, we show that employing heavier cryptographic primitives, namely STARK proofs, allows us to devise DARE-Stark, a version of DARE which achieves the near-optimal bit complexity of O(n L + n^2 poly(kappa)). Both DARE and DARE-Stark achieve optimal O(n) latency.

The Dolev-Reischuk bound says that any deterministic Byzantine consensus protocol has (at least) quadratic communication complexity in the worst case. While it has been shown that the bound is tight in synchronous environments, it is still unknown whether a consensus protocol with quadratic communication complexity can be obtained in partial synchrony. Until now, the most efficient known solutions for Byzantine consensus in partially synchronous settings had cubic communication complexity (e.g., HotStuff, binary DBFT). This paper closes the existing gap by introducing SQuad, a partially synchronous Byzantine consensus protocol with quadratic worst-case communication complexity. In addition, SQuad is optimally-resilient and achieves linear worst-case latency complexity. The key technical contribution underlying SQuad lies in the way we solve view synchronization, the problem of bringing all correct processes to the same view with a correct leader for sufficiently long. Concretely, we present RareSync, a view synchronization protocol with quadratic communication complexity and linear latency complexity, which we utilize in order to obtain SQuad.