The Celo Blog
Published in

The Celo Blog

BFTree — Scaling HotStuff to Millions of Validators

At cLabs, we are working towards a new financial system that creates the conditions for prosperity — for everyone. Today I wanted to share an early draft paper of the work Jason Ansel has been leading to make Celo, and other permissionless Proof-of-Stake (PoS) protocols, more inclusive by allowing them to scale to millions of validators.

Scaling Consensus

One of the big ideas that made Bitcoin so compelling when I first learned about it was that anyone could participate by running a miner on their home computer. This permissionless structure is a fundamental part of the cryptocurrency movement. As we transition to more environmentally sustainable proof-of-stake systems, there has been a growing number of cryptocurrencies using proof-of-stake consensus protocols such as Cosmos, Tezos, Algorand and Polkadot that are based on or are moving to use Byzantine Fault Tolerance (BFT) consensus. While these algorithms provide strong finality guarantees in that either all honest nodes will adopt a block or none will (thus eliminating the possibility of forks and rollbacks found in Bitcoin), existing BFT algorithms do not scale well. Most actively used implementations scale to 100’s of participants, with some upcoming systems aiming to scale to 1000’s of participants with some sacrifices (e.g. increased block times).

This has led to many modern cryptocurrencies adopting a two-class system where there is a smaller set of distinguished nodes that act as validators and participate in the BFT algorithm while the common node is merely an observer and does not participate. While some people might prefer to be delegators, we believe that a permissionless protocol is more resilient and inclusive if it allows anyone to join in the consensus protocol.

Introducing BFTree

This first draft of our new paper presents a novel modification to BFT algorithms called BFTree, designed with the goal to allow BFT consensus to scale to millions of validators. This change can enable a more decentralized proof-of-stake protocol by eliminating the need for two classes of nodes and delegation to a small number of validators. We view the goal of scaling to millions of validators as a forcing function to create a more scalable consensus algorithm where BFT is no longer the bottleneck in terms of making cryptocurrencies more decentralized. In practice, other bottlenecks, such as block sizes, may make the ideal number of validators be tens or hundreds of thousands of nodes for large cryptocurrencies.

BFTree arranges validators into a virtual tree, to parallelize signature aggregation between non-byzantine nodes working to achieve consensus. When byzantine nodes interfere with the aggregation, the roots of all subtrees that were able to achieve agreement perform BFT consensus to finish the round, frequently with fewer messages than if all validators participated. By thoughtfully reorganizing the tree such that nodes that have historically been reliable are paired with other reliable nodes, BFTree limits the impact that a byzantine node can have.

A step by step example of how BFTree achieves consensus in the presence of faulty validators.

This organization strategy allows an honest and reliable quorum of validators to quickly aggregate the required number of signatures in a distributed manner, allowing the algorithm to scale to large numbers of validators.

We’d love your feedback!

We wanted to share this early draft to get feedback from the community and hopefully spark a conversation on how it can be further improved. Please reach out if you share our passion for making consensus more inclusive.




Celo is a carbon-negative, L1 protocol with a rich ecosystem of global partners building Web3, mobile-first applications to create a more accessible and inclusive global financial system. Visit to learn more about the Celo community, contributors, and technology.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Marek | Celo

Marek | Celo

Partner at cLabs, working on @CeloOrg. Previously @LocuInc (founder), @MIT_CSAIL (PhD alumni), @Microsoft and @Google

More from Medium

How ZKasino will handle randomness on StarkNet

Blockchain Interoperability: State of Play

Muh Centralized Infra

Team Spotlight on Cairo Smith