Multi-valued Validated Byzantine Agreement (MVBA) is vital for asynchronous distributed protocols like asynchronous BFT consensus and distributed key generation, making performance improvements a long-standing goal. Existing communication-optimal MVBA protocols rely on computationally intensive public-key cryptographic tools, such as non-interactive threshold signatures, which are also vulnerable to quantum attacks. While hash-based MVBA protocols have been proposed to address these challenges, their higher communication overhead has raised concerns about practical performance. We present a novel MVBA protocol with adaptive security, relying exclusively on hash functions to achieve post-quantum security. Our protocol delivers near-optimal communication, constant round complexity, and significantly reduced latency compared to existing schemes, though it has sub-optimal resilience, tolerating up to 20% Byzantine corruptions instead of the typical 33%. For example, with n = 201 and input size 1.75 MB, it reduces latency by 81% over previous hash-based approaches.

There is a recent surge of studies on dynamic-committee proactive secret sharing (DPSS), in which not only will the shares be periodically refreshed (proactive secret sharing), but also the parties who hold the shares will be dynamically changed. It has direct applications in blockchain systems that require committees to manage confidential information, as well as in decentralized storage networks with dynamic participant involvement. Despite substantial attention, DPSS still has high communication complexity, particularly with large-size input data. In this article, we initiate the study of dynamic-committee proactive information dispersal (DPID). From a conceptual perspective, we can regard DPID as DPSS without the requirement for confidentiality. We model and construct DPID schemes with significantly reduced complexity. To demonstrate its efficiency, we also present a general framework for compiling our DPID into DPSS. By integrating our DPID construction, we achieve the first DPSS with much lower communication complexity for large-size data, whose benefits can be clearly shown in our experiments.

Recent progresses in asynchronous Byzantine fault-tolerant (BFT) consensus, e.g.$\mathsf {Dumbo}\textrm {-}\mathsf {NG}$(CCS' 22) and$\mathsf {Tusk}$(EuroSys' 22), show promising performance through decoupling transaction dissemination and block agreement. However, when executed with a larger number$n$of nodes, like several hundreds, they would suffer from significant degradation in performance. Their dominating scalability bottleneck is the huge authenticator complexity: each node has to multicast$\mathcal {O}(n)$quorum certificates (QCs) and subsequently verify them for each block. This paper systematically investigates and resolves the above scalability issue. We first propose a signature-free asynchronous BFT consensus$\mathsf {FIN}\textrm {-}\mathsf {NG}$that adapts a recent signature-free asynchronous common subset protocol FIN (CCS' 23) into the state-of-the-art framework of concurrent broadcast and agreement. The liveness of$\mathsf {FIN}\textrm {-}\mathsf {NG}$relies on our non-trivial redesign of FIN's multi-valued validated Byzantine agreement towards achieving optimal quality.$\mathsf {FIN}\textrm {-}\mathsf {NG}$greatly improves the performance of FIN and already outperforms$\mathsf {Dumbo}\textrm {-}\mathsf {NG}$in most deployment settings. To further overcome the scalability limit of$\mathsf {FIN}\textrm {-}\mathsf {NG}$due to$\mathcal {O}(n^{3})$messages, we propose$\mathsf {JUMBO}$, a scalable instantiation of$\mathsf {Dumbo}\textrm {-}\mathsf {NG}$, with only$\mathcal {O}(n^{2})$complexities for both authenticators and messages. We use various aggregation and dispersal techniques for QCs to significantly reduce the authenticator complexity of original$\mathsf {Dumbo}\textrm {-}\mathsf {NG}$implementations by up to$\mathcal {O}(n^{2})$orders. Finally, we implement our designs in Golang and experimentally demonstrated their enhanced scalability with hundreds of Amazon's AWS instances.$\mathsf {JUMBO}$and FIN-NG significantly outperform the state-of-the-art in (nearly) all deployment settings. Especially, when$n\ge$196,$\mathsf {JUMBO}$can attain a throughput that is more than 4× that of FIN and$\mathsf {Dumbo}\textrm {-}\mathsf {NG}$.

Recent progress of randomized fully asynchronous BFT consensus not only presents appealing performance but also ensures superior robustness against an asynchronous adversary that can arbitrarily delay network communication. But these results are mostly discussed in a static setting with fixed nodes. The root reason for the limit is the heavy dependence on a pre-configured threshold cryptosystem, which is critical to practically generate common randomness for overcoming FLP impossibility, but also fixes a designated set of participants. Even worse, most existing asynchronous BFT protocols rely on another strong assumption that messages sent among honest nodes must eventually be delivered, which could be plausible in the static setting (as all nodes can stay online forever to deliver messages) but becomes elusive in a dynamic blockchain, because a departing node might stop transmitting messages and subsequently cause inevitable message omissions as well as potential security violations To accommodate the enticing asynchronous BFT consensus into real-world blockchains where participating nodes are joining and leaving, we introduce Turritopsis, a novel dynamic asynchronous BFT framework that can (i) efficiently re-configure threshold cryptosystem to accommodate the change of consensus nodes and (ii) tolerate admissible message omissions caused by leaving participants. We first propose a dedicatedly optimized asynchronous distributed key refresh protocol that can quickly reset key materials of discrete logarithm threshold cryptosystem (e.g. BLS threshold signature), from which common randomness can be derived to ensure both safety and liveness despite the rotation of participating nodes. We then extend asynchronous BFT to tolerate a combination oftByzantine nodes andlhonest leaving nodes, where 3t+ 2lis smaller than the total numbernof currently participating nodes. This allows us to tolerate up tolleaving nodes that might behave like crashes due to their departures, while simultaneously preserving maximal resilience against ꜖(n– 2l)/3˩ malicious corruptions. We instantiated Turritopsis and implemented it in Python 3. Extensive experiments were conducted, spanning a network of up ton= 60 AWS EC2 nodes across 15 cities, revealing that Turritopsis exhibits performance closely comparable to its fixed-committee counterpart in both latency and throughput.

In recent years, opportunistic traders have extracted hundreds of millions of dollars from blockchains by reordering financial transactions. The problem stems from the fact that blockchains implement a state machine replication that orders transactions in any consistent order, regardless of the order in which these transactions were received. Existing attempts at enforcing the order perceived by honest participants suffer from cyclic dependencies or message delays. In this paper, we propose the Asynchronous Ordered Atomic Broadcast (AOAB) protocol. It does not suffer from cyclic dependencies or message delays because (i) it assigns an absolute timestamp to transactions, and (ii) it tolerates unbounded message delays. Besides being the first protocol to solve this problem, AOAB is communication-optimal and resilience-optimal. In particular, AOAB makes use of threshold signatures and information dissemination to reach a communication complexity of$\mathcal{O}(n\ell+\lambda n^{2})$, where$n$is the number of processes,$\ell$is the input (transaction) size and$\lambda$is the security parameter. This is optimal when$\ell\geq\lambda n$,

Several distributed protocols, including distributed key generation (DKG) and interactive consistency (IC), depend on O(n) instances of Byzantine Broadcast or Byzantine Agreement among n nodes, resulting in Θ(n3) communication overhead.

An urgent demand of deploying BFT consensus (e.g., atomic broadcast) over the Internet is raised for implementing (permissioned) blockchain services. The deterministic synchronous protocols can be simple and fast in good network conditions, but are subject to denial-of-service (or even safety vulnerability) when synchrony assumption fails. Asynchronous protocols, on the contrary, are robust against the adversarial network, but are substantially more complicated and slower for the inherent use of randomness.

Despite recent progresses of practical asynchronous Byzantine-fault tolerant (BFT) consensus, the state-of-the-art designs still suffer from suboptimal performance. Particularly, to obtain maximum throughput, most existing protocols \rev with guaranteed linear amortized communication complexity require each participating node to broadcast a huge batch of transactions, which dramatically sacrifices latency. Worse still, the ƒ slowest nodes' broadcasts might never be agreed to output and thus can be censored (where ƒ is the number of faults). Implementable mitigation to the threat either uses computationally costly threshold encryption or incurs communication blow-up by letting the honest nodes to broadcast redundant transactions, thus causing further efficiency issues.

Efficient asynchronous Byzantine agreement (BA) protocols were mostly studied with private setups, e.g., pre-setup threshold cryptosystem. Challenges remain to reduce the large communication in the absence of such setups. Recently, Abraham et al. (PODC’21) presented the first asynchronous validated BA (VBA) with expected $\mathcal{O}$(n3) messages and $\mathcal{O}$ (1) rounds, relying on only public key infrastructure (PKI) setup, but the design still costs $\mathcal{O}$ (λn3logn) bits. Here n is the number of parties, and λ is a cryptographic security parameter.In this paper, we reduce the communication of private-setup free asynchronous BA to expected $\mathcal{O}$(λn3) bits. At the core of our design, we give a systematic treatment of common randomness protocols in the asynchronous network, and proceed as:•We give an efficient reasonably fair common coin protocol in the asynchronous setting with only PKI setup. It costs only $\mathcal{O}$ (λn3) bit and $\mathcal{O}$(1) rounds, and ensures that with at least 1/3 probability, all honest parties can output a common bit that is as if randomly flipped. This directly renders more efficient private-setup free asynchronous binary agreement (ABA) with expected $\mathcal{O}$(λn3) bits and $\mathcal{O}$(1) rounds.•Then, we lift our common coin to attain perfect agreement by using a single ABA. This gives us a reasonably fair random leader election protocol with expected $\mathcal{O}$(λn3) communication and expected constant rounds. It is pluggable in all existing VBA protocols (e.g., Cachin et al., CRYPTO’01; Abraham et al., PODC’19; Lu et al., PODC’20) to remove the needed private setup or distributed key generation (DKG). As such, the communication of private-setup free VBA is reduced to expected $\mathcal{O}$(λn3) bits while preserving fast termination in expected $\mathcal{O}$(1) rounds. Moreover, our result paves a generic path to private-setup free asynchronous BA protocols, as it is not restricted to merely improve Abraham et al.’s specific VBA protocol (PODC’21).Our results and techniques could be found useful and interesting for a broad array of applications such as asynchronous DKG and DKG-free asynchronous random beacon that is friendly for dynamic participation and reconfiguration.

HoneyBadgerBFT, proposed by Miller et al. [34] as the first practical asynchronous atomic broadcast protocol, demonstrated impressive performance. The core of HoneyBadgerBFT (HB-BFT) is to achieve batching consensus using asynchronous common subset protocol (ACS) of Ben-Or et al., constituted with n reliable broadcast protocol (RBC) to have each node propose its input, followed by n asynchronous binary agreement protocol (ABA) to make a decision for each proposed value (n is the total number of nodes).

Multi-valued validated asynchronous Byzantine agreement (MVBA), proposed in the elegant work of Cachin et al. (CRYPTO '01), is fundamental for critical fault-tolerant services such as atomic broadcast in the asynchronous network. It was left as an open problem to asymptotically reduce the O(ℓn2 + λn2 + n3) communication (where n is the number of parties, ℓ is the input length, and λ is the security parameter). Recently, Abraham et al. (PODC '19) removed the n3 term to partially answer the question when input is small. However, in other typical cases, e.g., building atomic broadcast through MVBA, the input length ℓ ≥ λn, and thus the communication is dominated by the ℓn2 term and the problem raised by Cachin et al. remains open.