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.

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.

In a non-synchronous system with n processes, no t0-resilient (deterministic or probabilistic) Byzantine consensus protocol can prevent a disagreement among correct processes if the number of faulty processes is ≥n−2t0. Therefore, the community defined the accountable Byzantine consensus problem: the problem of (i) solving Byzantine consensus whenever possible (e.g., when the number of faulty processes does not exceed t0), and (ii) allowing correct processes to obtain proofs of culpability of n−2t0 faulty processes whenever a disagreement occurs. This paper presents ABC, a simple yet efficient transformation of any non-synchronous t0-resilient (deterministic or probabilistic) Byzantine consensus protocol into its accountable counterpart. In the common case (up to t0 faults), ABC introduces an additive overhead of two communication rounds and O(n2) exchanged bits. Whenever they disagree, correct processes detect culprits by exchanging O(n3) messages, which we prove optimal. Lastly, ABC is not limited to Byzantine consensus: ABC provides accountability for other essential distributed problems (e.g., reliable and consistent broadcast).

A decision task is a distributed input-output problem in which each process starts with its input value and eventually produces its output value. Examples of such decision tasks are broad and range from consensus to reliable broadcast to lattice agreement. A distributed protocol solves a decision task if it enables processes to produce admissible output values despite arbitrary (Byzantine) failures. Unfortunately, it has been known for decades that many decision tasks cannot be solved if the system is overly corrupted, i.e., safety of distributed protocols solving such tasks can be violated in unlucky scenarios.By contrast, only recently did the community discover that some of these distributed protocols can be made accountable by ensuring that correct processes irrevocably detect some faulty processes responsible for any safety violation. This realization is particularly surprising (and positive) given that accountability is a powerful tool to mitigate safety violations in distributed protocols. Indeed, exposing crimes and introducing punishments naturally incentivize exemplarity.In this paper, we propose a generic transformation, called τscr, of any non-synchronous distributed protocol solving a decision task into its accountable version. Our τscrtransformation is built upon the well-studied simulation of crash failures on top of Byzantine failures and increases the communication complexity by a quadratic multiplicative factor in the worst case.

It is known that the agreement property of the Byzantine consensus problem among$n$processes can be violated in a non-synchronous system if the number of faulty processes exceeds$t_{0}$= ┌$n$/3┐ − 1 [10], [19]. In this paper, we investigate the accountable Byzantine consensus problem in non-synchronous systems: the problem of solving Byzantine consensus whenever possible (e.g., when the number of faulty processes does not exceed$t_{0}$) and allowing correct processes to obtain proof of culpability of (at least)$t_{0}+ 1$faulty processes whenever correct processes disagree. We present four complementary contributions: 1) We introduce ABC: a simple yet efficient transformation of any Byzantine consensus protocol to an accountable one. ABC introduces an overhead of only two all-to-all communication rounds and$O(n^{2})$additional bits in executions with up to$t_{0}$faults (i.e., in the common case). 2) We define the accountability complexity, a complex-ity metric representing the number of accountability-specific messages that correct processes must send. Fur-thermore, we prove a tight lower bound. In particular, we show that any accountable Byzantine consensus protocol incurs cubic accountability complexity. Moreover, we illustrate that the bound is tight by applying the ABC transformation to any Byzantine consensus protocol. 3) We demonstrate that, when applied to an optimal Byzan-tine consensus protocol, ABC constructs an accountable Byzantine consensus protocol that is (1) optimal with respect to the communication complexity in solving consensus whenever consensus is solvable, and (2) op-timal with respect to the accountability complexity in obtaining accountability whenever disagreement occurs. 4) We generalize ABC to other distributed computing prob-lems besides the classic consensus problem. We charac-terize a class of agreement tasks, including reliable and consistent broadcast [5], that ABC renders accountable.

We present probabilistic dynamic I/O automata, a framework to model dynamic probabilistic systems. Our work extends dynamic I/O Automata formalism of Attie & Lynch to probabilistic setting. The original dynamic I/O Automata formalism included operators for parallel composition, action hiding, action renaming, automaton creation, and behavioural sub-typing by means of trace inclusion. They can model mobility by using signature modification. They are also hierarchical: a dynamically changing system of interacting automata is itself modeled as a single automaton. Our work extends to probabilistic settings all these features. Furthermore, we prove necessary and sufficient conditions to obtain the implementation monotonicity with respect to automata creation and destruction. Our construction uses a novel proof technique based on homomorphism that can be of independent interest. Our work lays down the foundations for extending composable secure-emulation of Canetti et al. to dynamic settings, an important tool towards the formal verification of protocols combining probabilistic distributed systems and cryptography in dynamic settings (e.g. blockchains, secure distributed computation, cybersecure distributed protocols etc).

This work extends the composable secure-emulation of Canetti et al. to dynamic settings. Our work builds on top of dynamic probabilistic I/O automata, a recent framework introduced to model dynamic probabilistic systems. Our extension is an important tool towards the formal verification of protocols combining probabilistic distributed systems and cryptography in dynamic settings (e.g. blockchains, cybersecure distributed protocols etc).

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.

We present probabilistic dynamic I/O automata, a framework to model dynamic probabilistic systems. Our work extends dynamic I/O Automata formalism of Attie & Lynch [Paul C. Attie and Nancy A. Lynch, 2016] to the probabilistic setting. The original dynamic I/O Automata formalism included operators for parallel composition, action hiding, action renaming, automaton creation, and behavioral sub-typing by means of trace inclusion. They can model mobility by using signature modification. They are also hierarchical: a dynamically changing system of interacting automata is itself modeled as a single automaton. Our work extends all these features to the probabilistic setting. Furthermore, we prove necessary and sufficient conditions to obtain the monotonicity of automata creation/destruction with implementation preorder. Our construction uses a novel proof technique based on homomorphism that can be of independent interest. Our work lays down the foundations for extending composable secure-emulation of Canetti et al. [Ran Canetti et al., 2007] to dynamic settings, an important tool towards the formal verification of protocols combining probabilistic distributed systems and cryptography in dynamic settings (e.g. blockchains, secure distributed computation, cybersecure distributed protocols, etc).

In this paper, we introduce Polygraph, the first accountable Byzantine consensus algorithm. If among$n$users$t < n/3$are malicious then it ensures consensus; otherwise (if$t\geq n/3)$, it eventually detects malicious users that cause disagreement. Polygraph is appealing for blockchain applications as it allows them to totally order blocks in a chain whenever possible, hence avoiding forks and double spending and, otherwise, to punish (e.g., via slashing) at least$n/3$malicious users when a fork occurs. This problem is more difficult than perhaps it first appears. One could try identifying malicious senders by extending classic Byzantine consensus algorithms to piggyback signed messages. We show however that to achieve accountability the resulting algorithms would then need to exchange$\Omega(\kappa^{2}\cdot n^{5})$bits, where$\kappa$is the security parameter of the signature scheme. By contrast, Polygraph has communication complexity$O(\kappa\cdot n^{4})$. Finally, we implement Polygraph in a blockchain and compare it to the Red Belly Blockchain to show that it commits more than 10,000 Bitcoin-like transactions per second when deployed on 80 geodistributed machines.

In this paper, we introduce Polygraph, the first accountable Byzantine consensus algorithm. If among n users f < n/3 are malicious then it ensures consensus, otherwise it eventually detects malicious users that cause disagreement. Polygraph is appealing for blockchains as it allows to totally order blocks in a chain whenever possible, hence avoiding double spending and, otherwise, to punish at least n/3 malicious users when a fork occurs. This problem is more difficult than it first appears. Blockchains typically run in open networks whose delays are hard to predict, hence one cannot build upon synchronous techniques [Andreas Haeberlen et al., 2007; Vitalik Buterin and Virgil Griffith, 2019]. One may exploit cryptographic evidence of PBFT-like consensus [Miguel Castro and Barbara Liskov, 2002], however detecting equivocation would be insufficient. We show that it is impossible without extra logs of at least Ω(n) rounds [Pierre Civit et al., 2019]. Each round of Polygraph exchanges O(n²) messages.