BFTree — Scaling HotStuff to Millions of Validators

Marek Olszewski
Jun 18 · 3 min read

At Celo, 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.

The Celo Blog

Celo is an open platform that makes financial tools accessible to anyone with a mobile phone. Visit celo.org for info on the community, team, and technology.

Marek Olszewski

Written by

Founder of Celo.org

The Celo Blog

Celo is an open platform that makes financial tools accessible to anyone with a mobile phone. Visit celo.org for info on the community, team, and technology.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade