Abstract
This work 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.