BFTree-Scaling HotStuff to Millions of Validators

A large selling point of Nakamoto consensus is that it can scale elastically with the number of untrusted participants working together to achieve consensus. This is a big advantage with regards to decentralization that has evaded many cryptocurrencies using proof-of-stake consensus protocols to-date, especially ones based on Byzantine Fault Tolerance (BFT) consensus. This paper outlines a novel modification to BFT consensus, named BFTree, that increases the practical number of validators that can be used in a BFT system from hundreds to millions of validators, without the use of sharding or subcommittee sampling. 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. 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.