Asynchronous Byzantine fault-tolerant (BFT) protocols assuming no timing assumptions are inherently more robust than their partially synchronous counterparts, but typically have much weaker security guarantees.We design new and efficient asynchronous BFT protocols matching all security guarantees of partially synchronous protocols. To achieve the goal, we have developed the local coin based BFT approach–one long deemed as being inefficient–and designed more efficient asynchronous binary agreement (ABA) protocols and their reproposable ABA (RABA) versions from local coins. Notably, our techniques on ABA and RABA allow us to build more efficient ABA protocols from common coins.We implemented four BFT protocols in a new Golang library, including BEAT, two WaterBear protocols, and FlatWorm. The WaterBear protocols use the conventional BFT workflow, while FlatWorm leverages the framework separating message transmission from consensus and significantly improves the system throughput.Via extensive evaluation, we show that our WaterBear protocols and FlatWorm are efficient under both failure-free and failure scenarios. Notably, WaterBear-QS consistently outperforms BEAT across all metrics and FlatWorm significantly outpaces WaterBear-QS. For example, with 16 replicas, FlatWorm achieves a throughput of 213.04ktx/sec—5.63× that of BEAT and 3.43× that of WaterBear-QS.

With the growing number of decentralized finance (DeFi) applications, transaction fairness in blockchains has gained much research interest. As a broad concept in distributed systems and blockchains, fairness has been used in different contexts, varying from ones related to the liveness of the system to ones that focus on the received order of transactions. In this work, we revisit the fairness definitions and find that existing fairness definitions are not adapted to blockchains with multiple DApps. We then provide a more generic one calledverifiable fairness. Compared with prior definitions, our notion has two unique features: (i) it relaxes the ordering rules to apredicate; (ii) it enables users to independently verify if their transactions comply with the predicate for concrete applications. We also provide a scheme that achieves verifiable fairness, leveraging trusted hardware. Unlike prior works that usually design a dedicated consensus protocol to achieve fairness, our scheme can be integrated with any blockchain system. Our evaluation results on Amazon EC2 using up to 120 instances across different regions show that our construction imposes only minimal overhead on existing blockchain systems.

Large Vision-Language Models (LVLMs) signify a groundbreaking paradigm shift within the Artificial Intelligence (AI) community, extending beyond the capabilities of Large Language Models (LLMs) by assimilating additional modalities (e.g., images). Despite this advancement, the safety of LVLMs remains adequately underexplored, with a potential overreliance on the safety assurances purported by their underlying LLMs. In this paper, we propose FigStep, a straightforward yet effective black-box jailbreak algorithm against LVLMs. Instead of feeding textual harmful instructions directly, FigStep converts the prohibited content into images through typography to bypass the safety alignment. The experimental results indicate that FigStep can achieve an average attack success rate of 82.50% on six promising open-source LVLMs. Not merely to demonstrate the efficacy of FigStep, we conduct comprehensive ablation studies and analyze the distribution of the semantic embeddings to uncover that the reason behind the success of FigStep is the deficiency of safety alignment for visual embeddings. Moreover, we compare FigStep with five text-only jailbreaks and four image-based jailbreaks to demonstrate the superiority of FigStep, i.e., negligible attack costs and better attack performance. Above all, our work reveals that current LVLMs are vulnerable to jailbreak attacks, which highlights the necessity of novel cross-modality safety alignment techniques.

MPC-as-a-Service (MPCaaS) systems enable clients to outsource privacy-preserving computations to distributed servers, offering flexibility by adapting and configuring MPC protocols to meet diverse security requirements. However, traditional MPC protocols rely on a fixed set of servers for the entire computation process, limiting scalability. Dynamic MPC (DMPC) addresses this limitation by permitting participants to join or leave during the computation. Nevertheless, existing DMPC protocols assume synchronous networks, which can lead to failures under unbounded network delays. In this paper, we present AD-MPC, the first asynchronous dynamic MPC protocol. Our protocol ensures guaranteed output delivery under optimal resilience ((n = 3t + 1)). To achieve this, we introduce two critical components: an asynchronous dynamic preprocessing protocol that facilitates the on-demand generation of Beaver triples for secure multiplication, and an asynchronous transfer protocol that maintains consistency during party hand-offs. These components collectively ensure computation correctness and transfer consistency across participants. We implement AD-MPC and evaluate its performance across up to 20 geographically distributed nodes. Experimental results demonstrate that the protocol not only offers strong security guarantees in dynamic and asynchronous network environments but also achieves performance comparable to state-of-the-art DMPC protocols.

Layer 2 is one of the most promising approaches to improve the scalability of blockchains. The idea is to shift some tasks (e.g., ordering and execution of some transactions) off the mainchain (i.e., layer 1) to reduce the workload of the mainchain. In this work, we study the so-called committee-based layer 2 approaches. Being conceptually similar to sharding, committee-based layer 2 approaches allow committees to order and execute transactions in parallel to further improve the performance of the system. Different from existing committee-based layer 2 solutions that often prioritize low latency over high throughput, our solution strives to achieve both low latency and high throughput. The technical building blocks include a lightweight primary-backup design for off-chain committees, an efficient on-chain lease management design for managing the primaries, and a one-phase solution for cross-committee transactions (i.e., transactions that need to be processed by multiple committees). Experimental results show that our solution achieves both low latency and high throughput and can be deployed on even low-end machines.

Byzantine atomic broadcast (ABC) is at the heart of permissioned blockchains and various multi-party computation protocols. We resolve a long-standing open problem in ABC, presenting the first signature-free asynchronous ABC protocol that achieves optimal$O(n^{2})$messages and$O(1)$expected time, where$n$is the total number of replicas. Our ABC protocol adopts a new design, relying on a reduction from-perhaps surprisingly-a somewhat neglected primitive called multivalued Byzantine agreement (MBA).

We revisit the concept of order fairness in blockchain systems. Order fairness imposes additional constraints on the actual order of the transactions, preventing adversaries from manipulating the order of transactions to gain undue advantages. While numerous notions of fairness and corresponding fair ordering protocols have been proposed, these efforts typically focus on designing a dedicated protocol tailored to each specific fairness notion. Consequently, it remains unclear whether multiple fairness notions can be realized simultaneously within a single framework. In this work, we propose “2-hop receiver fairness”, a new and unified fairness notion that simultaneously captures approximate sender fairness, block order fairness, and consequence transaction fairness. To achieve 2-hop receiver fairness, we propose TxSort, a generic framework that reduces the fair ordering problem to the asynchronous common subset (ACS), an extensively studied primitive for asynchronous consensus and multiparty computation. In this way, we can integrate the state-of-theart ACS protocols to provide a communication-efficient and round-optimal fair ordering protocol. Specifically, our protocol achieves an amortized communication complexity per transaction (CCpT) of$O\left(n^{2}\right)$, while existing state-of-the-art fair ordering protocols achieve$O\left(n^{3}\right)$CCpT. As a crucial building block of our framework, we introduce a novel and computation-efficient local algorithm called “pivot quick sort”, which might be of independent interest.

Most practical synchronous Byzantine fault-tolerant (BFT) protocols, such as Sync HotStuff (S&P 2020), follow the paradigm of partially synchronous BFT and adopt a deterministic design. While these protocols achieve$\mathbf{O}(\mathbf{n})$time complexity, they exhibit impressive performance in failure-free scenarios. This paper challenges this conventional wisdom, showing that a randomized paradigm terminating in expected$O(1)$time may well outperform prior ones even in the failure-free scenarios. Our framework reduces synchronous BFT to a new primitive called multi-valued Byzantine agreement with strong external validity (MBA-SEV). Inspired by the external validity property of multi-valued validated Byzantine agreement (MVBA), the additional validity properties allow us to build a BFT protocol where replicas agree on the hashes of the blocks. Our instantiation of the paradigm, Sonic, achieves$O(n)$amortized message complexity per block proposal, expected$O(1)$time, and enables a fast path of only two communication step. Our evaluation results using up to 91 instances on Amazon EC2 show that the peak throughput of Sonic and P-Sonic (a pipelining variant of Sonic) is$2.24 x-14.52 x$and$3.08 x-24.25 x$that of Sync HotStuff, respectively.

Smart contract vulnerabilities have led to significant economic losses, threatening blockchain security and development. Graph neural network (GNN)-based approaches, which capture the structural properties of contracts and leverage code dependencies to better understand contract behavior, have become widely used for vulnerability detection. However, these approaches face challenges in losing valuable information during graph construction and failing to capture rich semantic content, while traditional GNNs struggle with long-range dependencies and global context in complex contract graphs. To address these challenges, we propose ConSense, a GNN-based Contract Sensing Framework for Smart Contract Vulnerability Detection. ConSense comprises two core components: the smart contract graph generator, which constructs contract graphs while retaining both structural and semantic information, and ExploreFormer, which effectively integrates local and global context using advanced attention mechanisms for vulnerability detection. Comprehensive experimental evaluations were performed on the IR-ESCD and SCVHunter-SCD datasets. For instance, the IR-ESCD benchmark—which encompasses eight distinct vulnerability categories—demonstrates that ConSense attains an average detection accuracy of 97.74%, with a mean processing time of 0.648 seconds per contract. These results signify a statistically significant improvement over state-of-the-art methods in both precision and computational efficiency.

As the first Byzantine fault-tolerant (BFT) protocol with linear communication complexity, HotStuff (PODC 2019) has received significant attention. HotStuff has three round-trips for both normal case operations and view change protocols. Follow-up studies attempt to reduce the number of phases for HotStuff. However, most studies give up on one thing in return for another. This paper extends our previous work Marlin (DSN 2022) to Pike, another BFT protocol with two phases and linear communication complexity. Both Pike and Marlin use the same cryptographic tools as in HotStuff and introduce no additional assumptions. Marlin has a more efficient view change (i.e., leader election) protocol but a more complicated data structure. Pike further simplifies the data structure at the cost of longer view changes in extreme cases. We implement the Pike, Marlin, HotStuff, and HotStuff-2, showing that both Pike and Marlin outperform HotStuff in normal case operations.

Asynchronous common subset (ACS) is a powerful paradigm enabling applications such as Byzantine fault-tolerance (BFT) and multi-party computation (MPC). The most efficient ACS framework in the information-theoretic setting is due to Ben-Or, Kelmer, and Rabin (BKR, 1994). The BKR ACS protocol has been both theoretically and practically impactful. BKR ACS has an$O(\log n)$running time (where$n$is the number of replicas) due to the usage of$n$parallel asynchronous binary agreement (ABA) instances, impacting both performance and scalability. Indeed, for a network of 16$\sim$64 replicas, the parallel ABA phase occupies about 95%$\sim$97% of the total runtime. A long-standing open problem is whether we can build an ACS framework with$O(1)$time while not increasing the message or communication complexity of the BKR protocol. We resolve the open problem, presenting the first constant-time ACS protocol with$O(n^{3})$messages in the information-theoretic and signature-free settings. Our key ingredient is the first information-theoretic and constant-time multivalued validated Byzantine agreement (MVBA) protocol. Our results can improve—asymptotically and concretely—various applications using ACS and MVBA. As an example, we implement FIN, a BFT protocol instantiated using our framework. Via a 121-server deployment on Amazon EC2, we show FIN reduces the overhead of the ABA phase to as low as 1.23% of the total runtime.

State-of-the-art asynchronous Byzantine fault-tolerant (BFT) protocols, such as HoneyBadgerBFT, BEAT, and Dumbo, have shown performance comparable to partially synchronous BFT protocols. This paper studies two practical directions in asynchronous BFT. First, while all these asynchronous BFT protocols assume optimal resilience with$3f+1$replicas (where$f$is an upper bound on the number of Byzantine replicas), it is interesting to ask whether more efficient protocols are possible upon changing the resilience level. Second, these recent BFT protocols evaluate their performance under failure-free scenarios. It is unclear if these protocols indeed perform well during failures and attacks. This work first studies asynchronous BFT with suboptimal resilience using$5f+1$and$7f+1$replicas. We present MiB, a novel and efficient asynchronous BFT framework using new distributed system constructions as building blocks. MiB consists of two main BFT instances and five more variants. As another contribution, we systematically design experiments for asynchronous BFT protocols with failures and evaluate their performance in various failure scenarios. We report interesting findings, showing that asynchronous BFT performs consistently well during different failure scenarios. In particular, via a five-continent deployment on Amazon EC2 using 140 replicas, we show that the MiB instances have lower latency and much higher throughput than their asynchronous BFT counterparts.

Byzantine broadcast (BC) is a fundamental problem in distributed systems. To build communication-efficient BC protocols, erasure coding is a key tool. In systems under thefn/3 setting, wherenis the total number of parties (also called replicas) andfis the number of Byzantine failures, correct replicas can simply encode the data block through erasure coding, share data fragments, and interact to validate that the decoded data is consistent with the original data block. Such a paradigm is powerful in primitives such as BC, asynchronous verifiable information dispersal, and atomic broadcast. However, in systems with corrupt majority or even in thefn/2 setting, it becomes less straightforward to use erasure coding to build communication-efficient protocols. In this work, we introduce an erasure coding proof (ECP) system which allows the encoder to prove succinctly and non-interactively that an erasure-coded fragment is consistent with a constant-sized commitment to the original data block. Each fragment can be verified independently of the other fragments. We present two synchronous BC protocols from the ECP system, one under thefnassumption and one under thefn/2 assumption, where ϵ is a constant and ϵ ∈ (0, 1). Both protocols improve the communication complexity and time complexity compared to the state-of-the-art BC protocols.

The pseudonymity nature of Ethereum provides a protective umbrella for criminal activities, allowing criminals to develop a series of black industries such as phishing scams in unregulated areas. In order to exploit the relational inductive bias to discover the real identity of anonymous accounts, graph neural networks (GNNs) have been widely used in Ethereum fraud detection tasks as an effective and powerful framework. However, the expressive power of GNN’s 1-hop message passing mechanism is bounded by the Weisfeiler-Leman (1-WL) test, degrading the fraud detection performance on the Ethereum network. This paper proposes a structure-aware Mamba framework, named SAMamba. Specifically, SAMamba uses a subgraph encoding strategy to capture complex structural patterns and introduces Mamba’s exceptional sequence modeling capabilities to route global information. In order to filter task-relevant information from dense information, the attention mechanism and the selection mechanism are introduced from local and global perspectives, respectively. These tailor-made designs enable SAMamba to distinguish subtle differences in structural patterns and selectively aggregate task-oriented information, thereby demonstrating exceptional performance in fraud detection tasks. Extensive experiments on real-world Ethereum data demonstrate that SAMamba outperforms state-of-the-art methods. The codes are publicly available on Github: https://github.com/deepang-ai/SAMamba.

Conventional Byzantine fault tolerance (BFT) requires replicated state machines to execute deterministic operations only. In practice, numerous applications and scenarios, especially in the era of blockchains, contain various sources of non-determinism. Meanwhile, it is even sometimes desirable to support non-determinism, and replicas still agree on the execution results. Despite decades of research on BFT, we still lack an efficient and easy-to-deploy solution for BFT with non-determinism—BFT-ND, especially in the asynchronous setting. We revisit the problem of BFT-ND and provide a formal and asynchronous treatment of BFT-ND. In particular, we design and implement Block-ND that insightfully separates the task of agreeing on the order of transactions from the task of agreement on the state: Block-ND allows reusing existing BFT implementations; on top of BFT, we reduce the agreement on the state to multivalued Byzantine agreement (MBA), a somewhat neglected primitive by practical systems. Block-ND is completely asynchronous as long as the underlying BFT is asynchronous. We provide a new MBA construction that is significantly faster than existing MBA constructions. We instantiate Block-ND in both the partially synchronous setting (with PBFT, OSDI 1999) and the purely asynchronous setting (with PACE, CCS 2022). Via a 91-instance WAN deployment on Amazon EC2, we show that Block-ND has only marginal performance degradation compared to conventional BFT.

With the increasing scale and complexity of online activities, accountability, as an after-the-fact mechanism, has become an effective complementary approach to ensure system security. Decades of research have delved into the connotation of accountability. They fail, however, to achieve practical accountability of decryption. This paper seeks to address this gap. We consider the scenario where a client (called encryptor, her) encrypts her data and then chooses a delegate (a.k.a. decryptor, him) that stores data for her. If the decryptor initiates an illegitimate decryption on the encrypted data, there is a non-negligible probability that this behavior will be detected, thereby holding the decryptor accountable for his decryption. We make three contributions. First, we review key definitions of accountability known so far. Based on extensive investigations, we formalize new definitions of accountability specifically targeting the decryption process, denoted as accountable decryption, and discuss the (im)possibilities when capturing this concept. We also define the security goals in correspondence. Second, we present a novel Trusted Execution Environment(TEE)-assisted solution aligning with definitions. Instead of fully trusting TEE, we take a further step, making TEE work in the “trust, but verify” model where we trust TEE and use its service, but empower users (i.e., decryptors) to detect the potentially compromised state of TEEs. Third, we implement a full-fledged system and conduct a series of evaluations. The results demonstrate that our solution is efficient. Even in a scenario involving$300,000$log entries, the decryption process concludes in approximately 5.5ms, and malicious decryptors can be identified within 69ms.

Trusted Execution Environment (TEE)-assisted confidential smart contracts (TCSC) have attracted extensive attention from both academia and industry. Despite an enormous number of TCSC projects, the extent of confidentiality offered by them remains being questioned: the factual and fictional aspects are not well distinguished, which limits their adoption. In this paper, we provide a formal treatment of TCSC, endowing them with an expressive syntax and security definitions. Based on these definitions, we propose a provably secure TCSC instantiation. Then, we investigate each algorithm and identify the implementation flaws that may make a TCSC system violate its security properties. Our analysis reveals the gap between theoretical security models and real-world implementations: even assuming a TCSC is provably secure by design, it may still fail in practice. We further compare our TCSC instantiation with 16 representative TCSC systems. Our results show that, surprisingly, all these surveyed projects are subject to practical attacks. Finally, we implement a TCSC prototype and conduct a comprehensive evaluation, revealing the overheads of distributed key management and the performance challenges of executing complex contracts within TEEs.

Byzantine agreement is the most fundamental primitive in distributed computing. All known Byzantine agreement protocols achieve quadratic or sub-quadratic messages and communication. We show that surprisingly, by directly assuming a random leader election oracle (that can be built from the verifiable random function), threshold signatures, and the$1/3$corruption bound, we can build Linear-BA, a binary agreement (BA) that has linear message complexity, constant expected time complexity, and a normal case that has linear communication. We extend Linear-BA to construct Linear-MBA, a multi-valued Byzantine agreement (MBA) protocol also with$O(n)$messages and$O(1)$expected time. Finally, we present Linear-MBA-SV, an MBA protocol with the strong validity property via a no-cost transformation from Linear-MBA. All the protocols above are secure under a static adversary, where a static adversary corrupts a set of replicas at the beginning of the protocol. We go on and show an impossibility result that in the adaptive adversary model (in which the adversary can selectively corrupt the replicas while the protocol is running), one cannot build a Byzantine agreement protocol with$O(n)$messages and$O(1)$expected time. Accordingly, we revise our protocol to obtain Byzantine agreement protocols with$O(n)$messages per round and$O(n)$time. Our results offer a fresh view of what is needed for linear Byzantine agreement: by examining the “needed” assumptions, one can identify the performance bottlenecks for Byzantine agreement. Meanwhile, all our protocols are efficient, as all the building blocks have efficient instantiations.

A key management service (KMS) is vital to modern mission-critical systems. At the core of KMS are the key generation process and the key refresh process. In this paper, we design and implement a purely asynchronous system for completely distributed KMS supporting traditional applications such as threshold cryptosystems and multiparty computation (MPC) as well as emerging blockchains and Web3 applications. In this system, we have built a number of new asynchronous distributed key generation (ADKG) protocols and their corresponding asynchronous distributed key refresh (ADKR) protocols. We have demonstrated that our ADKG and ADKR protocols in the standard model outperform existing ones of the same kind, while our protocols in the random oracle model (ROM) are more efficient than other protocols with small and medium-sized networks.

The expansion of blockchain applications, particularly on platforms like Ethereum, brings escalating security challenges as account anonymity provides breeding grounds for criminals to commit crimes and cause significant economic losses. As the mainstream architecture of de-anonymization technology, graph neural networks (GNNs) provide empirical tools for law enforcement agencies to investigate illegal activities. However, the limited expressiveness of current GNNs leads to performance degradation for Ethereum account de-anonymization. To address this challenge, we propose an innovative Local-Global Awareness (LGA) framework, which consists of a Local Structure-Aware (LSA) module and a Global Information-Aware (GIA) module. LSA integrates subgraph-level encoding strategies with local attention to enhance the capture of microscopic interactions. As a complementary measure, GIA introduces global attention to facilitate the understanding of macroscopic information. The LGA framework meticulously captures subgraph-level account behavior patterns at a granular level while simultaneously incorporating global contextual insights, demonstrating higher-level expressive power and receptive fields over conventional GNN. The efficacy of the LGA framework is corroborated by experimental evaluations conducted on the lw-AIG dataset. Our framework achieves exceptional performance, significantly outstripping state-of-the-art GNN-based methods in terms of the micro F1 score metric, with relative improvements ranging from 0.14% to 6.63%. Through its detailed and comprehensive analysis of account interactions, the LGA framework aims to provide a potent solution to the complex security challenges faced in the expanding blockchain landscape. The code for LGA is available at https://github.com/deepang-ai/LGA.

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.

We design and implement PG, a Byzantine fault-tolerant and privacy-preserving multi-sensor fusion system. PG is flexible and extensible, supporting a variety of fusion algorithms and application scenarios.

State-of-the-art Byzantine fault-tolerant (BFT) protocols assuming partial synchrony such as SBFT and HotStuff use regular certificates obtained from 2f + 1 (partial) signatures. We show that one can use weak certificates obtained from only f + 1 signatures to assist in designing more robust and more efficient BFT protocols. We design and implement two BFT systems: Dashing (a family of two HotStuff-style BFT protocols) and Star (a parallel BFT framework).

We present FlexDID, a decentralized identity management system with flexible credential presentation and efficient revocation. FlexDID allows identity holders to perform both vertical disclosure and horizontal disclosure. Vertical disclosure allows an identity holder to derive a credential to prove only a subset of all attributes it holds. Meanwhile, horizontal disclosure allows multiple identity holders with the same attributes to aggregate their credentials for fast verification. We also introduce a three-layer architecture. Besides the roles of identity holders and issuers in conventional identity management systems, we introduce a layer of secondary brokers. The secondary brokers can be viewed as delegates for identity holders to perform flexible disclosure. Together with our system optimizations, such as batch verification, FlexDID is able to manage the credentials for a large number of identity holders, making it a perfect fit for applications, such as the Industrial Internet of Things. Our evaluation shows all the operations of FlexDID can complete in millisecond level and the most computationally extensive operation has a latency of up to 34% lower compared to existing identity management systems.

We provide an expressive framework that allows analyzing and generating provably secure, state-of-the-art Byzantine fault-tolerant (BFT) protocols over graph of nodes, a notion formalized in the HotStuff protocol. Our framework is hierarchical, including three layers. The top layer is used to model the message pattern and abstract core functions on which BFT algorithms can be built. The intermediate layer provides the core functions with high-level properties sufficient to prove the security of the top-layer algorithms. The bottom layer presents operational realizations for the core functions. Using our framework, designing a BFT protocol is reduced to instantiating two core functions together with their specific properties. Unlike prior BFT frameworks, our framework can analyze and recast BFT protocols in an exceedingly fine-grained manner. More importantly, our framework can readily generate new BFT protocols. In this paper, we show that the framework allows us to fully specify and formally prove the security for a family of BFT protocols, including known protocols such as HotStuff, Fast-HotStuff, and SBFT. Additionally, we show that our framework can generate four new protocols outperforming existing ones, including 1) two protocols with$5f+1$replicas achieving optimal message complexity; 2) the first BFT protocol achieving optimal message complexity with$4f+1$replicas; and 3) a two-phase protocol with$3f+1$replicas achieving linear authenticator complexity in the fast path.

Asynchronous common subset (ACS) is a powerful paradigm enabling applications such as Byzantine fault-tolerance (BFT) and multi-party computation (MPC). The most efficient ACS framework in the information-theoretic setting is due to Ben-Or, Kelmer, and Rabin (BKR, 1994). The BKR ACS protocol has been both theoretically and practically impactful. However, the BKR protocol has an O(log n) running time (where n is the number of replicas) due to the usage of n parallel asynchronous binary agreement (ABA) instances, impacting both performance and scalability. Indeed, for a network of 16 ~ 64 replicas, the parallel ABA phase occupies about 95% ~ 97% of the total runtime in BKR. A long-standing open problem is whether we can build an ACS framework with O(1) time while not increasing the message or communication complexity of the BKR protocol.

Distributed key generation (DKG) allows bootstrapping threshold cryptosystems without relying on a trusted party, nowadays enabling fully decentralized applications in blockchains and multiparty computation (MPC). While we have recently seen new advancements for asynchronous DKG (ADKG) protocols, their performance remains the bottleneck for many applications, with only one protocol being implemented (DYX+ ADKG, IEEE S&P 2022). DYX+ ADKG relies on the Decisional Composite Residuosity assumption (being expensive to instantiate) and the Decisional Diffie-Hellman assumption, incurring a high latency (more than 100s with a failure threshold of 16). Moreover, the security of DYX+ ADKG is based on the random oracle model (ROM) which takes hash function as an ideal function; assuming the existence of random oracle is a strong assumption, and up to now, we cannot find any theoretically-sound implementation. Furthermore, the ADKG protocol needs public key infrastructure (PKI) to support the trustworthiness of public keys. The strong models (ROM and PKI) further limit the applicability of DYX+ ADKG, as they would add extra and strong assumptions to underlying threshold cryptosystems. For instance, if the original threshold cryptosystem works in the standard model, then the system using DYX+ ADKG would need to use ROM and PKI. In this paper, we design and implement a modular ADKG protocol that offers improved efficiency and stronger security guarantees. We explore a novel and much more direct reduction from ADKG to the underlying blocks, reducing the computational overhead and communication rounds of ADKG in the normal case. Our protocol works for both the low-threshold and high-threshold scenarios, being secure under the standard assumption (the well-established discrete logarithm assumption only) in the standard model (no trusted setup, ROM, or PKI).

As blockchain-based commercial projects and startups flourish, efficiency becomes one of the critical metrics in designing blockchain systems. Due to its high efficiency, Proof of Authority (PoA) Aura has become one of the most widely adopted consensus solutions for blockchains. Our research finds over 4,000 projects have used Aura and its variants. In this paper, we provide a rigorous analysis of Aura. We propose three types of time-manipulation attacks, where a malicious leader simply needs to modify the timestamp in its proposed block or delay it to extract extra benefits. These attacks can easily break the legal leader election, thus directly harming the fairness of the block proposal. We apply our attacks to a mature Aura project called OpenEthereum. By repeatedly conducting our attacks1 over 15 days, we find that an adversary can gain on average 200% mining rewards of their fair shares. Furthermore, such attacks can even indirectly break the finality of blocks and the safety of the system. Based on the deployment of Aura as of September 2022, the potentially affected market cap is up to 2.13 billion USD. As a by-product, we further discuss solutions to mitigate such issues and report our observations to official teams.

The classic asynchronous Byzantine fault tolerance (BFT) framework of Ben-Or, Kemler, and Rabin (BKR) and its descendants rely on reliable broadcast (RBC) and asynchronous binary agreement (ABA). However, BKR does not allow all ABA instances to run in parallel, a well-known performance bottleneck. We propose PACE, a generic framework that removes the bottleneck, allowing fully parallelizable ABA instances. PACE is built on RBC and reproposable ABA (RABA). Different from the conventional ABA, RABA allows a replica to change its mind and vote twice. We show how to efficiently build RABA protocols from existing ABA protocols and a new ABA protocol that we introduce.

As the first Byzantine fault-tolerant (BFT) protocol with linear communication complexity, HotStuff (PODC 2019) has received significant attention. HotStuff has three round-trips for both normal case operations and view change protocols. Follow-up studies attempt to reduce the number of phases for HotStuff. These protocols, however, all give up of one thing in return for another.This paper presents Marlin, a BFT protocol with linearity, having two phases for normal case operations and two or three phases for view changes. Marlin uses the same cryptographic tools as in HotStuff and introduces no additional assumptions. We implement a new and efficient Golang library for Marlin and HotStuff, showing Marlin outperforms HotStuff for both the common case and the view change.

This paper studies Byzantine reliable broadcast (BRB) under asynchronous networks, and improves the state-of-the-art protocols from the following aspects. Near-optimal communication cost: We propose two new BRB protocols for n nodes and input message M that has communication cost O(n|M|+n2 logn), which is nearoptimal due to the lower bound of Ω(n|M|+n2). The first RBC protocol assumes threshold signature but is easy to understand, while the second RBC protocol is error-free but less intuitive. Improved computation:We propose a newconstruction that improves the computation cost of the state-of-the-art BRB by avoiding the expensive online error correction on the input message, while achieving the same communication cost. Balanced communication: We propose a technique named balanced multicast that can balance the communication cost for BRB protocols where the broadcaster needs to multicast the message M while other nodes only needs to multicast coded fragments of size O(|M|/n + logn). The balanced multicast technique can be applied to many existing BRB protocols as well as all our new constructions in this paper, and can make every node incur about the same communication cost. Finally, we present a lower bound to show the near optimality of our protocol in terms of communication cost at each node.

We present a near-optimal asynchronous verifiable information dispersal (AVID) protocol. The total dispersal cost of our AVID protocol is O(|M| + κ n^2), and the retrieval cost per client is O(|M| + κ n). Unlike prior works, our AVID protocol only assumes the existence of collision-resistant hash functions. Also, in our AVID protocol, the dispersing client incurs a communication cost of O(|M|+κ n) in comparison to O(|M|+κ n łog n) of prior best. Moreover, each node in our AVID protocol incurs a storage cost of O(|M|/n + κ) bits, in comparison to O(|M|/n + κ łog n) bits of prior best. Finally, we present lower bound results on communication cost and show that our AVID protocol has near-optimal communication costs -- only a factor of O(κ) gap from the lower bounds.

This paper studies dynamic BFT, where replicas can join and leave the system dynamically, a primitive that is nowadays increasingly needed. We provide a formal treatment for dynamic BFT protocols, endowing them with a flexible syntax and various security definitions.We demonstrate the challenges of extending static BFT to dynamic BFT. Then we design and implement Dyno, a highly efficient dynamic BFT protocol under the partial synchrony model. We show that Dyno can seamlessly handle membership changes without incurring performance degradation.

We present Poligraph, an intrusion-tolerant and decentralized fake news detection system. Poligraph aims to address architectural, system, technical, and social challenges of building a practical, long-term fake news detection platform. We first conduct a case study for fake news detection at authors’ institute, showing that machine learning-based reviews are less accurate but timely, while human reviews, in particular, experts reviews, are more accurate but time-consuming. This justifies the need for combining both approaches. At the core of Poligraph is two-layer consensus allowing seamlessly combining machine learning techniques and human expert determination. We construct the two-layer consensus using Byzantine fault-tolerant (BFT) and asynchronous threshold common coin protocols. We prove the correctness of our system in terms of conventional definitions of security in distributed systems (agreement, total order, and liveness) as well as new review validity (capturing the accuracy of news reviews). We also provide theoretical foundations on parameter selection for our system. We implement Poligraph and evaluate its performance on Amazon EC2 using a variety of news from online publications and social media. We demonstrate Poligraph achieves throughput of more than 5,000 transactions per second and latency as low as 0.05 second. The throughput of Poligraph is only marginally (${4\%}$–${7\%}$) slower than that of an unreplicated, single-server implementation. In addition, we conduct a real-world case study for the review of fake and real news among both experts and non-experts, which validates the practicality of our approach.

We present a framework for evaluating the performance of Byzantine fault-tolerant (BFT) protocols theoretically. Our motivation is to identify protocols suitable for a particular power grid application. In this application, replicas are located in a LAN network where latency is the priority. To fully understand the performance of BFT, we provide a generic approach that quantifies the performance of BFT protocols based on the number of cryptographic operations under five different scenarios (in the presence of failures and without failures). We present the performance of three representative BFT protocols: PBFT, Prime, and SBFT. To validate our framework, we also evaluate the protocols experimentally in the CloudLab testbed. Our experimental results match the findings predicted by the framework. Although a variety of factors may affect the performance of the protocols, our framework can be used as a valuable reference to understand the performance of BFT.

Asynchronous BFT protocols such as HoneyBadgerBFT and BEAT are inherently robust against timing, performance, and denial-of-service attacks. The protocols, however, achieve static security, where the adversary needs to choose the set of corrupted replicas before the execution of the protocol. The situation is in contrast to that of most of existing BFT protocols (e.g., PBFT) which achieve adaptive security, where the adversary can choose to corrupt replicas at any moment during the execution of the protocol. We present EPIC, a novel and efficient asynchronous BFT protocol with adaptive security. Via a five-continent deployment on Amazon EC2, we show that EPIC is slightly slower for small and medium-sized networks than the most efficient asynchronous BFT protocols with static security. We also find as the number of replicas is smaller than 46, EPIC's throughput is stable, achieving peak throughput of 8,000--12,500 tx/sec using t2.medium VMs. When the network size grows larger, EPIC is not as efficient as those with static security, with throughput of 4,000--6,300 tx/sec.

We present Chios, an intrusion-tolerant publish/subscribe system which protects against Byzantine failures. Chios is the first publish/subscribe system achieving decentralized confidentiality with fine-grained access control and strong publication order guarantees. This is in contrast to existing publish/subscribe systems achieving much weaker security and reliability properties. Chios is flexible and modular, consisting of four fully-fledged publish/subscribe configurations (each designed to meet different goals). We have deployed and evaluated our system on Amazon EC2. We compare Chios with various publish/subscribe systems. Chios is as efficient as an unreplicated, single-broker publish/subscribe implementation, only marginally slower than Kafka and Kafka with passive replication, and at least an order of magnitude faster than all Hyperledger Fabric modules and publish/subscribe systems using Fabric.

We present BEAT, a set of practical Byzantine fault-tolerant (BFT) protocols for completely asynchronous environments. BEAT is flexible, versatile, and extensible, consisting of five asynchronous BFT protocols that are designed to meet different goals (e.g., different performance metrics, different application scenarios). Due to modularity in its design, features of these protocols can be mixed to achieve even more meaningful trade-offs between functionality and performance for various applications. Through a 92-instance, five-continent deployment of BEAT on Amazon EC2, we show that BEAT is efficient: roughly, all our BEAT instances significantly outperform, in terms of both latency and throughput, HoneyBadgerBFT, the most efficient asynchronous BFT known.

We describe efficient path-based Byzantine routing protocols that are secure against fully Byzantine adversaries. Our work is in sharp contrast to prior works which handle a weaker subset of Byzantine attacks. We provide a formal proof of correctness of our protocols which, to our knowledge, is the first of its kind. We implement and evaluate our protocols using DeterLab, demonstrating that our protocols are as efficient as those secure against weaker adversaries and our protocols can efficiently and correctly detect routers that fail arbitrarily.

Critical Infrastructure Systems such as transportation, water and power grid systems are vital to our national security, economy, and public safety. Recent events, like the 2012 hurricane Sandy, show how the interdependencies among different CI networks lead to catastrophic failures among the whole system. Hence, analyzing these CI networks, and modeling failure cascades on them becomes a very important problem. However, traditional models either do not take multiple CIs or the dynamics of the system into account, or model it simplistically. In this paper, we study this problem using a heterogeneous network viewpoint. We first construct heterogeneous CI networks with multiple components using national-level datasets. Then we study novel failure maximization problems on these networks, to compute critical nodes in such systems. We then provide HotSpots, a scalable and effective algorithm for these problems, based on careful transformations. Finally, we conduct extensive experiments on real CIS data from multiple US states, and show that our method HotSpots outperforms non-trivial baselines, gives meaningful results and that our approach gives immediate benefits in providing situational-awareness during large-scale failures.

We revisit the problem of preserving causality in Byzantine fault-tolerant (BFT) atomic broadcast protocols, a requirement first proposed by Reiter and Birman (TOPLAS 1994). While over the past three decades, this requirement has been met through the deployment of expensive public-key threshold cryptosystems, we propose three novel, secure causal BFT protocols without using public-key cryptography. We implement and evaluate these protocols, showing that they significantly outperform existing constructions that use threshold cryptosystems.

Critical Infrastructures (CIs) such as energy, water, and transportation are complex networks that are crucial for sustaining day-to-day commodity flows vital to national security, economic stability, and public safety. The nature of these CIs is such that failures caused by an extreme weather event or a man-made incident can trigger widespread cascading failures, sending ripple effects at regional or even national scales. To minimize such effects, it is critical for emergency responders to identify existing or potential vulnerabilities within CIs during such stressor events in a systematic and quantifiable manner and take appropriate mitigating actions. We present here a novel critical infrastructure monitoring and analysis system named URBAN-NET. The system includes a software stack and tools for monitoring CIs, pre-processing data, interconnecting multiple CI datasets as a heterogeneous network, identifying vulnerabilities through graph-based topological analysis, and predicting consequences based on “what-if” simulations along with visualization. As a proof-of-concept, we present several case studies to show the capabilities of our system. We also discuss remaining challenges and future work.

Consensus is a fundamental approach to implementing fault-tolerant services through replication. It is well known that there exists a tradeoff between the cost and the resilience. For instance, Crash Fault Tolerant (CFT) protocols have a low cost but can only handle crash failures while Byzantine Fault Tolerant (BFT) protocols handle arbitrary failures but have a higher cost. Hybrid protocols enjoy the benefits of both high performance without failures and high resiliency under failures by switching among different subprotocols. However, it is challenging to determine which subprotocols should be used. We propose a moving target approach to switch among protocols according to the existing system and network vulnerability. At the core of our approach is a formalized cost model that evaluates the vulnerability and performance of consensus protocols based on real-time Intrusion Detection System (IDS) signals. Based on the evaluation results, we demonstrate that a safe, cheap, and unpredictable protocol is always used and a high IDS error rate can be tolerated.

Modern large-scale networks require the ability to withstand arbitrary failures (i.e., Byzantine failures). Byzantine reliable broadcast algorithms can be used to reliably disseminate information in the presence of Byzantine failures.We design a novel Byzantine reliable broadcast protocol for loosely connected and synchronous networks. While previous such protocols all assume correct senders, our protocol is the first to handle Byzantine senders. To achieve this goal, we have developed new techniques for fault detection and fault tolerance. Our protocol is efficient, and under normal circumstances, no expensive public-key cryptographic operations are used. We implement and evaluate our protocol, demonstrating that our protocol has high throughput and is superior to the existing protocols in uncivil executions.

We address the problem of how to store and process data privately in cloud environments that employ state machine replication. We show that the only known solution to the problem (Yin et al., SOSP '03) is potentially susceptible to attacks. We then present a new protocol that is secure in the stronger model we formalize. Our protocol uses only efficient symmetric cryptography, while Yin et al.'s uses costly threshold signatures. We implemented and evaluated our protocol. We show that our protocol is two to three orders of magnitude faster than Yin et al.'s, which is less secure than ours.

Routing in sensor networks with unpredictable network connections and node failures is challenging due to the lack of knowledge about network dynamics in decision making. We present a self-adaptive middleware for efficient routing in distributed sensor network. At the heart of the proposed approach is the design of a policy-driven language to control the relocation of software components between sensor nodes. Accordingly, various changes in sensor networks can be dynamically adapted. Based on such a middleware, we provide a few approaches in building a practical routing protocol. For instance, nodes can adaptively switch their routing strategies according to the network stability or migrate some tasks to other idle nodes to prevent from node failures.

We present hBFT, a hybrid, Byzantine fault-tolerant, replicated state machine protocol with optimal resilience. Under normal circumstances, hBFT uses speculation, i.e., replicas directly adopt the order from the primary and send replies to the clients. As in prior work such as Zyzzyva, when replicas are out of order, clients can detect the inconsistency and help replicas converge on the total ordering. However, we take a different approach than previous work that has four distinct benefits: it requires many fewer cryptographic operations, it moves critical jobs to the clients with no additional costs, faulty clients can be detected and identified, and performance in the presence of client participation will not degrade as long as the primary is correct. The correctness is guaranteed by a three-phase checkpoint subprotocol similar to PBFT, which is tailored to our needs. The protocol is triggered by the primary when a certain number of requests are executed or by clients when they detect an inconsistency.

Building robust network services that can withstand a wide range of failure types is a fundamental problem in distributed systems. The most general approach, called Byzantine fault tolerance, can mask arbitrary failures. Yet it is often considered too costly to deploy in practice, and many solutions are not resilient to performance attacks. To address this concern we leverage two key technologies already widely deployed in cloud computing infrastructures: replicated state machines and intrusion detection systems. First, we have designed a general framework for constructing Byzantine failure detectors based on an intrusion detection system. Based on such a failure detector, we have designed and built a practical Byzantine fault-tolerant protocol, which has costs comparable to crash-resilient protocols like Paxos. More importantly, our protocol is particularly robust against several key attacks such as flooding attacks, timing attacks, and fairness attacks, that are typically not handled well by Byzantine fault masking procedures.