Alea-BFT
Practical Asynchronous Byzantine Fault Tolerance

Do you need to order elements? Do you enjoy rolling the dice? Are you worried about bad/weird actors? Do you abhor fiddling with tunables? If the answer to one or more of these questions is yes, then Alea-BFT is for you!

What is Alea-BFT?

Alea-BFT is a BFT (Byzantine-fault tolerant) consensus protocol designed for performance and simplicity. Unlike partially-synchronous protocols such as PBFT or QBFT, which use timeouts to guarantee liveness, Alea is asynchronous, i.e., it does not use predefined timeouts to estimate when a machine might be unresponsive. Thus, Alea-BFT closely follows network performance while requiring no tuning of timeout values. Very importantly, Alea-BFT is able to make fast progress, even when the participants or the network are not behaving or performing as expected.

What is consensus?

Consensus is an important problem in distributed systems. It consists in having a set of processes propose values and and then agree on a single proposal.

This primitive can be leveraged to build solutions to two other important (and equivalent) problems: total-order broadcast and state machine replication. (Alea-BFT is designed as a total-order broadcast protocol, but can be easily adapted to the other, related problems.)

The focus of Alea is on BFT consensus, i.e., achieving consensus while tolerating Byzantine (arbitrary) faults. Concretely, we require that consensus is reached among the correct processes even if some (bounded) amount of processes fail arbitrarily. BFT consensus problems is very relevant because it is the core component of important classes of systems, namely blockchains and cryptocurrencies.

Wait, I thought consensus was impossible in asynchronous networks!

Yes, consensus is impossible in an asynchronous network if we admit the existence of even a single benign fault (a simple machine crash). (This result is known as the FLP impossibility.) However, this only holds if we restrict ourselves to deterministic protocols.

Asynchronous consensus protocols like Alea-BFT exploit randomization instead. Concretely, they reframe the termination property of consensus to be probabilistic: consensus terminates with a probability that approaches 1.

Randomized consensus has been studied for decades, and the initial solutions were very elegant, but incurred in a high communication cost. Alea-BFT integrates techniques from early solutions, modern asynchronous protocols, and partially-synchronous BFT protocols, combining them into an elegant and efficient protocol.

How Alea-BFT works

Alea-BFT brings from partially-synchronous consensus protocols the insight of centralizing work on a rotating leader node. However, it needs to address several challenges associated with this approach, namely the reliance on a single node, which must be replaced upon failure. This is achieved by rotating the leader after each consensus attempt, and only tasking the leaders with conveying their own (locally-ordered) proposals to the remaining processes, leaving the global ordering decision to a leaderless component.

In more detail, the protocol is divided into a broadcast component and an agreement component, connected by a set of FIFO queues. The broadcast component pushes new requests (depicted as fruits in the animation) to the queues using a consistent broadcast primitive. Then, each process appends requests to its respective queue. In parallel, the agreement component constantly tries to pop and deliver the heads of these queues. To this end, this component uses a randomized binary agreement primitive to decide if it is safe to conclude a higher-level consensus instance. Finally, a recovery protocol fetches missing requests in case the agreement succeeds at a node that did not receive the broadcast value.

Publications and theses

Main Alea-BFT paper

Alea-BFT: Practical Asynchronous Byzantine Fault Tolerance
Diogo S. Antunes, Afonso N. Oliveira, André Breda, Matheus Guilherme Franco, Henrique Moniz, and Rodrigo Rodrigues
USENIX Symposium on Networked Systems Design and Implementation, 2024
An extended version complete with correctness proofs is available on arXiv

Real-world adoption (blog posts)

Talks

Code

Name Description Language License
Alea-BFT Prototype Research prototype implementation. Java MIT
SSV + Alea-BFT Fork of the SSV distributed Ethereum validator, incorporating Alea-BFT for consensus. Go GPL 3.0
Mir + Alea-BFT Fork of the Mir Framework - Mir is expected to become a consensus layer for Filecoin, and now includes support for Alea-BFT consensus (in the process of being upstreamed). Go Apache 2.0

Contributors

Alea-BFT is the joint effort of the following students and faculty at IST - Lisbon and its computer science research lab, INESC-ID:

IST Logo INESC-ID Logo

This work is supported by the European Union's Horizon 2020 research and innovation programme under grant agreement No. 952226, project BIG, and the Portuguese Foundation for Science and Technology (FCT).

Project BIG Logo FCT Logo