We present a fast quantum Byzantine Agreement protocol that can reach agreement in O(1) expected communication rounds against a strong full information, dynamic adversary, tolerating up to the optimal t‹n3 faulty players in the synchronous setting, and up to t‹n4 faulty players for asynchronous systems. This should be contrasted with the known classical synchronous lower bound of Ω(√ nlog n) [3] when t=(n).
We present a fast quantum Byzantine Agreement protocol that can reach agreement in O(1) expected communication rounds against a strong full information, dynamic adversary, tolerating up to the optimal t‹n3 faulty players in the synchronous setting, and up to t‹n4 faulty players for asynchronous systems. This should be contrasted with the known classical synchronous lower bound of Ω(√ nlog n) [3] when t=(n).
Quantum entanglement can be employed in some distributed communication tasks to reduce computation and communication overheads, yielding speedups over their classical counterparts. However, existing quantum Byzantine protocols often entail excessive communication and entanglement resource consumption. Conversely, classical schemes face insecurity with the impending reality of quantum computers. To address these challenges, we present a novel quantum Detectable Weak Byzantine Agreement (DWBA) protocol with high practicability, security and optimal fault-tolerance bound. For all n players, our protocol can complete the consensus of infinite classical information via fixed n + 1 -entangled qubits and a digest function, which requires infinite entanglement resources in previous schemes. Moreover, our protocol can tolerate arbitrary t ( t < n ) faulty players without necessitating any additional initial setup information (e.g., digital signature, private random coins). In terms of efficiency, our protocol only requires O (1) rounds and O ( ( n − t ) 2 ) communication complexity, constituting an order of magnitude improvement over previous protocols. In addition, the DWBA problem solved by our protocol is inherently stronger than the 3-player Detectable Byzantine Agreement (DBA) problem solved by previous protocols, and in a weaker but sufficiently practical model, our protocol can achieve Weak Byzantine Agreement (WBA).
We exhibit that, when given a classical Byzantine agreement protocol designed in the private-channel model, it is feasible to construct a quantum agreement protocol that can effectively handle a full-information adversary. Notably, both protocols have equivalent levels of resilience, round complexity, and communication complexity. In the classical private-channel scenario, participating players are limited to exchanging classical bits, with the adversary lacking knowledge of the exchanged messages. In contrast, in the quantum full-information setting, participating players can exchange qubits, while the adversary possesses comprehensive and accurate visibility into the system's state and messages. By showcasing the reduction from quantum to classical frameworks, this paper demonstrates the strength and flexibility of quantum protocols in addressing security challenges posed by adversaries with increased visibility. It underscores the potential of leveraging quantum principles to improve security measures without compromising on efficiency or resilience. By applying our reduction, we demonstrate quantum advantages in the round complexity of asynchronous Byzantine agreement protocols in the full-information model. It is well known that in the full-information model, any classical protocol requires Ω(n) rounds to solve Byzantine agreement with probability one even against Fail-stop adversary when resilience t=Θ(n). We show that quantum protocols can achieve O(1) rounds (i) with resilience t0, therefore surpassing the classical lower bound.
Byzantine agreement, the underlying core of blockchain, aims to make every node in a decentralized network reach consensus. Classical Byzantine agreements unavoidably face two major problems. One is 1/3 fault-tolerance bound, which means that the system to tolerate f malicious players requires at least 3 f + 1 players. The other is the security loopholes from its classical cryptography methods. Here, we propose a Byzantine agreement framework with unconditional security to break this bound with nearly 1/2 fault tolerance due to multiparty correlation provided by quantum digital signatures. It is intriguing that quantum entanglement is not necessary to break the 1/3 fault-tolerance bound, and we show that weaker correlation, such as asymmetric relationship of quantum digital signature, can also work. Our work strictly obeys two Byzantine conditions and can be extended to any number of players without requirements for multiparticle entanglement. We experimentally demonstrate three-party and five-party consensus for a digital ledger. Our work indicates the quantum advantage in terms of consensus problems and suggests an important avenue for quantum blockchain and quantum consensus networks.
In this paper, we introduce a new quantum protocol for Detectable Byzantine Agreement. What distinguishes the proposed protocol among similar quantum protocols, is the fact that it uses only EPR pairs, and, in particular, |Ψ+⟩ pairs. There are many sophisticated quantum protocols that guarantee Detectable Byzantine Agreement, but they do not easily lend themselves to practical implementations, due to present-day technological limitations. For a large number n of players, |GHZ⟩n-tuples, or other more exotic entangled states, are not easy to produce, a fact which might complicate the scalability of such protocols. In contrast, Bell states are, undoubtedly, the easiest to generate among maximally entangled states. This will, hopefully, facilitate the scalability of the proposed protocol, as only EPR pairs are required, irrespective of the number n of players. Finally, we mention that, even for arbitrary many players n, our protocol always completes in a constant number of rounds, namely 4.
It is well-known that n players, connected only by pairwise secure channels, can achieve Byzantine agreement only if the number t of cheaters satisfies t < n/3, even with respect to computational security. However, for many applications it is sufficient to achieve detectable broadcast. With this primitive, broadcast is only guaranteed when all players are non-faulty ("honest"), but all non-faulty players always reach agreement on whether broadcast was achieved or not. We show that detectable broadcast can be achieved regardless of the number of faulty players (i.e., for all t < n). We give a protocol which is unconditionally secure, as well as two more efficient protocols which are secure with respect to computational assumptions, and the existence of quantum channels, respectively.These protocols allow for secure multi-party computation tolerating any t < n, assuming only pairwise authenticated channels. Moreover, they allow for the setup of public-key infrastructures that are consistent among all participants --- using neither a trusted party nor broadcast channels.Finally, we show that it is not even necessary for players to begin the protocol at the same time step. We give a "detectable Firing Squad" protocol which can be initiated by a single user at any time and such that either all honest players end up with synchronized clocks, or all honest players abort.
Fault-tolerant consensus is about reaching agreement on some of the input values in a limited time by non-faulty autonomous processes, despite of failures of processes or communication medium. This problem is particularly challenging and costly against an adaptive adversary with full information. Bar-Joseph and Ben-Or [7] (PODC'98) were the first who proved an absolute lower bound [EQUATION] on expected time complexity of consensus in any classic (i.e., randomized or deterministic) message-passing network with n processes succeeding with probability 1 against such a strong adaptive adversary crashing processes.