BigFooT: A robust optimal-latency BFT blockchain consensus protocol with dynamic validator membership

Permissioned blockchains are blockchains where only a finite and known subset of all the nodes, that we call validator set, is allowed to propose the next block to be added to the blockchain maintained by each node. In this work, we present BigFooT, a Byzantine fault-tolerant consensus protocol for permissioned blockchains that draws upon the State Machine Replication (SMR) protocols Zyzzyva and Spinning to ensure the following properties: (i) Correct operation under eventual synchrony provided that less than one third of the validators are Byzantine even if the maximum message latency of the network after reaching synchrony is unknown; (ii) Dynamic membership of the validator set; (iii) Latency of only two message delays for deciding on a block once the network reaches synchrony provided that the maximum message latency is known and all validators are honest; (iv) Resilience to Byzantine performance degradation; (v) Resilience to messages being lost before the network becomes synchronous. To the best of our knowledge, BigFooT is the first blockchain consensus protocol that ensures all these combined properties. Additionally, we show for the first time how a vanilla implementation of state machine reconfiguration protocols to achieve a dynamic validator set can produce a protocol that fails to guarantee liveness.