Byzantine consensus is a fundamental building block in distributed cryptographic problems. Despite decades of research, most existing asynchronous consensus protocols require a strong trusted setup and expensive public-key cryptography. In this paper, we study asynchronous Byzantine consensus protocols that do not rely on a trusted setup and do not use public-key cryptography such as digital signatures. We give an Asynchronous Common Subset (ACS) protocol whose security is only based on cryptographic hash functions modeled as a random oracle. Our protocol has O(κn3) total communication and runs in expected O(1) rounds. The fact that we use only cryptographic hash functions also means that our protocol is post-quantum secure. The minimal use of cryptography and the small number of rounds make our protocol practical. We implement our protocol and evaluate it in a geo-distributed setting with up to 128 machines. Our experimental evaluation shows that our protocol is more efficient than the only other setup-free consensus protocol that has been implemented to date. En route to our asynchronous consensus protocols, we also introduce new primitives called asynchronous secret key sharing and cover gather, which may be of independent interest.

Bitcoin's longest-chain protocol pioneered consensus under dynamic participation, also known as sleepy consensus, where nodes do not need to be permanently active. However, existing solutions for sleepy consensus still face two major issues, which we address in this work. First, existing sleepy consensus protocols have high latency (either asymptotically or concretely). We tackle this problem and achieve 4Δ latency (Δ is the bound on network delay) in the best case, which is comparable to classic BFT protocols without dynamic participation support. Second, existing protocols have to assume that the set of corrupt participants remains fixed throughout the lifetime of the protocol due to a problem we call costless simulation. We resolve this problem and support growing participation of corrupt nodes. Our new protocol also offers several other important advantages, including support for arbitrary fluctuation of honest participation as well as an efficient recovery mechanism for new active nodes.

The constant-sized polynomial commitment scheme by Kate, Zaverucha, and Goldberg (Asiscrypt 2010), also known as the KZG commitment, is an essential component in designing bandwidth-efficient verifiable secret-sharing (VSS) protocols. We point out, however, that the KZG commitment is missing two important properties that are crucial for VSS protocols.

Designing an efficient solution for Byzantine broadcast is an important problem for many distributed computing and cryptographic tasks. There have been many attempts to achieve sub-quadratic communication complexity in several directions, both in theory and practice, all with pros and cons. This paper initiates the study of another attempt: improving the amortized communication complexity of multi-shot Byzantine broadcast. Namely, we try to improve the average cost when we have sequential multiple broadcast instances. We present a protocol that achieves optimal amortized linear complexity under an honest majority. Our core technique is to efficiently form a network for disseminating the sender's message by keeping track of dishonest behaviors over multiple instances. We also generalize the technique for the dishonest majority to achieve amortized quadratic communication complexity.

Dynamic participation support is an important feature of Bitcoin's longest-chain protocol and its variants. But these protocols suffer from long latency as a fundamental trade-off. Specifically, the latency depends at least on the following two factors: 1) the desired security level of the protocol, and 2) the actual participation level of the network. Classic BFT protocols, on the other hand, can achieve constant latency but cannot make progress under dynamic participation. In this work, we present a protocol that simultaneously supports dynamic participation and achieves constant latency. Our core technique is to extend the classic BFT approach from static quorum size to dynamic quorum size, i.e., according to the current participation level, while preserving important properties of static quorum. We also present a recovery mechanism for rejoining nodes that is efficient in terms of both communication and storage. Our experimental evaluation shows our protocol has much lower latency than a longest-chain protocol, especially when there is a sudden decrease of participation.

Classic Byzantine fault tolerant (BFT) protocols are designed for a specific timing model, most often one of the following: synchronous, asynchronous or partially synchronous. It is well known that the timing model and fault tolerance threshold present inherent trade-offs. Synchronous protocols tolerate up to n/2 Byzantine faults, while asynchronous or partially synchronous protocols tolerate only up to n/3 Byzantine faults. In this work, we generalize the fault thresholds of BFT and introduce a new problem called multi-threshold BFT. Multi-threshold BFT has four separate fault thresholds for safety and liveness under synchrony and asynchrony (or partial-synchrony), respectively. Decomposing the fault thresholds in this way allows us to design protocols that provide meaningful fault tolerance under both synchrony and asynchrony (or partial synchrony). We establish tight fault thresholds bounds for multi-threshold BFT and present protocols achieving them. As an example, we show a BFT state machine replication (SMR) protocol that tolerates up to 2n/3 faults for safety under synchrony while tolerating up to n/3 faults for other scenarios (liveness under synchrony as well as safety and liveness under partial synchrony). This is strictly stronger than classic partially synchronous SMR protocols. We also present a general framework to transform known partially synchronous or asynchronous BFT SMR protocols to additionally enjoy the optimal 2n/3 fault tolerance for safety under synchrony.

Byzantine Agreement (BA) is one of the most fundamental problems in distributed computing, and its communication complexity is an important efficiency metric. It is well known that quadratic communication is necessary for BA in the worst case due to a lower bound by Dolev and Reischuk. This lower bound has been shown to be tight for the unauthenticated setting with f < n/3 by Berman et al. but a considerable gap remains for the authenticated setting with n/3 ≤ f < n/2. This paper provides two results towards closing this gap. Both protocols have a quadratic communication complexity and have different trade-offs in resilience and assumptions. The first protocol achieves the optimal resilience of f < n/2 but requires a trusted setup for threshold signature. The second protocol achieves near optimal resilience f ≤ (1/2 - ε)n in the standard PKI model.