Resource-based consensus is the backbone of permissionless distributed ledger systems. The security of such protocols relies fundamentally on the level of resources actively engaged in the system. The variety of different resources (and related proof protocols, some times referred to as PoX in the literature) raises the fundamental question whether it is possible to utilize many of them in tandem and build multi-resource consensus protocols. The challenge in combining different resources is to achieve fungibility between them, in the sense that security would hold as long as the cumulative adversarial power across all resources is bounded.

Minimizing the round complexity of Byzantine Agreement (BA) protocols is a fundamental problem in distributed computing. The typical approach to achieve round efficient (randomized) BA is to have a weak form of BA, called graded consensus (GC), followed by a distributed coin, and to repeat this process until some termination condition is met---as introduced by Feldman and Micali (STOC'88).

A fundamental result in information-theoretic fault-tolerant distributed computing is that unconditionally secure broadcast (or Byzantine agreement) among three players is impossible if one player is misbehaving. In particular, imperfect broadcast with failure probability epsi is achievable if and only if epsi ges (3 - radic5)/2. In this paper, we examine to what extent the failure probability of imperfect broadcast can be reduced. As a main result, we show that, among three players, broadcast with failure probability epsi can be turned into broadcast with negligible failure probability if and only if epsi < 1/3. This result is finally extended to the more general case of n players and any number of misbehaving players

All known protocols for Byzantine agreement (BA) among n players require the message to be communicated at least Ω(n2) times, which results in an overall communication complexity of at least Ω(ln2) bits for an l-bit message. We present the first BA protocol in which the message is communicated only O(n) times (the hidden factor is less than 2). More concretely, for a given synchronous broadcast protocol which communicates B(b) bits for reaching agreement on a b-bit message with security parameter κ, our construction yields a synchronous BA protocol with communication complexity O(ln+nB(n+κ)) bits. Our reduction is information theoretically secure and tolerates up to t<n/2 corrupted players, which is optimal for the consensus variant of BA. Although this resilience is not optimal for the broadcast (Byzantine generals) variant, it is sufficient for most distributed applications that involve BA protocols since they typically require t

In this paper we consider the following two variants of the consensus problem. First, the strong consensus problem, where n players attempt to reach agreement on a value initially held by one of the correct players, despite the (malicious) behavior of up to t of them. (Recall that in the standard version of the problem, the players are also required to decide on one of the correct players' input values, but only when they all start with the same value; otherwise, they can decide on a default.) Although the problem is closely related to the standard problem, the only known solution with the optimal number of players requires exponential computation and communication in the unconditional setting.Even though the decision would be a value originally held by a correct player, strong consensus allows for a decision value that is the least common among the correct players. We also formulate the δ-differential consensus problem, which specifies that the value agreed on must be of a certain plurality among the correct players --- specifically, that the plurality of any other value cannot exceed the plurality of the decision value by more than δ.In this paper we study these problems, and present efficient protocols and tight lower bounds for several standard distributed computation models --- unconditional, computational, synchronous, and asynchronous.

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.

This paper considers unconditionally secure protocols for reliable broadcast among a set of n players, some of which may be corrupted by an active (Byzantine) adversary.In the standard model with a complete, synchronous network of pairwise authentic communication channels among the players, broadcast is achievable if and only if the number of corrupted players is less than n/3.We show that, by extending this model only by the existence of a broadcast channel among three players, global broadcast is achievable if and only if the number of corrupted players is less than n/2.Moreover, for this an even weaker primitive than broadcast among three players is sufficient.All protocols are efficient.