Research and Advances
Artificial Intelligence and Machine Learning East Asia and Oceania Region Special Section: Hot Topics

The Future of Blockchain Consensus


The Byzantine consensus problem was originally defined in 1982. The idea is for correct machines (or nodes) to propose values and reach a consensus despite the presence of malicious (or Byzantine) ones. More precisely, three properties must be satisfied: these correct nodes must eventually decide (termination); their decision should be identical (agreement); and the value they decide should be one of the proposed values (validity). Since then, there have been many protocols for different models.

Most of the classical consensus solutions were unfortunately designed for local area networks and were typically illustrated with four well-connected nodes running a network file system. With the advent of blockchain technologies, the consensus problem became crucial for blockchain nodes to agree on the same blocks. But blockchains are deployed among many nodes spread across the open Internet, which naturally raises new challenges like making consensus protocols robust and efficient at large scale and in non-purely synchronous networks. As the classic consensus protocols were not designed for the qualitatively different large and open Internet, the blockchain consensus faced limitations and required new perspectives to address them.

The Redbelly Blockchain demonstrated that solving consensus did not prevent scaling to 1,000 machines geo-distributed worldwide.

Our recent work has led to significant advancements that push blockchain consensus to be truly scalable and robust, while preserving high performance.

The Redbelly path to making blockchain consensus truly scalable. The crux of the problem that prevented these recent blockchain systems from performing efficiently at large scale lies in the fact that these solutions typically solve the traditional validity guarantee from 1982, hence forcing blockchain nodes to decide a single block at each index, regardless of the number of proposed blocks. It is thus extremely difficult for the blockchain performance to increase with the amount of node resources.

Our new blockchain protocols emerged with the intent to solve consensus and to scale to large networks. The idea, illustrated by the Redbelly Blockchain2 from the Commonwealth Science Industry and Research Organisation (CSIRO) and The University of Sydney, consists of solving a slightly different variant of the consensus problem, deciding a superblock composed of multiple proposed blocks. This led to significant scalability improvements as the number of decided transactions could finally scale linearly with the number of participating nodes. As a result, the Redbelly Blockchain demonstrated that solving consensus did not prevent scaling to 1,000 machines geo-distributed worldwide.

The Australian federal government included the Redbelly Blockchain as part of its National Blockchain Roadmap. To strengthen security, the consensus protocol of Redbelly Blockchain was formally verified with model checking,1 which drastically reduces the risks of human errors that have been apparent in other blockchains. Some recent results demonstrate that, while modern blockchains could not execute real traces on decentralized applications,a Redbelly Blockchain could.5 The techniques to make blockchains scalable and solve consensus are now part of a book and taught online to thousands of students in the University of Sydney’s blockchain scalability MOOC on Coursera. More details can be found at

The Dumbo path to make asynchronous consensus real. Most of the consensus in use can guarantee to work only in synchronous networks (assuming all messages to be delivered within some time parameter). This makes them vulnerable in the open Internet, which is naturally asynchronous because of dynamic network conditions or even network attacks. The reason asynchronous consensus is not used yet is due to its complexity, as hinted by the famous FLP-impossibility that deterministic asynchronous consensus does not exist. Over the years, a great deal of effort has been devoted to design various randomized protocols to circumvent the impossibility. Unfortunately, most of them are theoretical in nature and not implemented, until the recent HoneyBadgerBFT, which essentially asked the community whether asynchronous consensus can ever be practical.

Our new blockchain protocols emerged with the intent to solve Internet consensus, that is, to scale to large networks and to be robust in the asynchronous network while preserving high performance.

Recent progress of the Dumbo protocol family affirmatively answers the question. Starting with DumboBFT,3 major bottlenecks of HoneyBadgerBFT (that makes it much slower when scales up) were identified, and a new design principle was proposed to use a different tool called multivalued validated Byzantine agreement (MVBA) to conquer the obstacle to achieve only a small constant number of rounds (no matter the scale). In Dumbo-MVBA,b a long-standing open problem of communication optimal MVBA was finally resolved. More importantly, the new design methodology further enables a more compact and even faster Speeding Dumbo,c and a tight broadcast-and-vote structure for asynchronous consensus to realize high throughput without sacrificing latency in Dumbo-NG,d which harvests most of the bandwidth.

Figure. The Redbelly Blockchain research team at the University of Sydney.

Considering deterministic synchronous consensus protocols are very fast (but may fail to work in the open Internet), while asynchronous consensus is robust (slower), the recent combination brought out the best of both. Specifically, a new practical framework for optimistic asynchronous consensus called Bolt-Dumbo-Transformer4 was proposed. When deployed and tested over 100 nodes spread across five continents, Dumbo protocols show orders of magnitude advantages over previous protocols and clear evidence for practical performance. Wide media coverage includes CoinDesk and multiple major media outlets covering Dumbo protocols. More details can be found at


    1. Bertrand, B., Gramoli, V., Lazić, M., Konnov, I., Tholoniat, P., and Widder, J. BA: Holistic verification of blockchain consensus. In Proceedings of the 2022 ACM Symp. Distributed Computing.

    2. Crain, T., Natoli, C., and Gramoli, V. Red Belly: A secure, fair and scalable open blockchain. IEEE Symposium on Security and Privacy (2021), 466–483.

    3. Guo, B., Lu, Z., Tang, Q., Xu, J., and Zhang, Z. Dumbo: Faster asynchronous BFT protocols. In Proceedings of the 2020 ACM Conf. Computer and Communications Security.

    4. Lu, Y., Lu, Z., and Tang, Q. Bolt-Dumbo transformer: Asynchronous consensus as fast as the pipelined BFT. In Proceedings of the 2022 ACM Conf. Computer and Communications Security.

    5. Tennakoon, D., Hua, Y., and Gramoli, V. Smart Red Belly blockchain: Reducing congestion for Web3. In Proceedings of the 37th IEEE Intern. Parallel & Distributed Processing Symp., 2023.

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More