Formal Modeling and Verification of a Federated Byzantine Agreement Algorithm for Blockchain Platforms

Abstract

A blockchain is a type of distributed ledger that can record transactions between parties in a verifiable and permanent manner. Each node contains its ledger, and the contents of each ledger are maintained to be the same by a consensus algorithm. It is essential to ensure the safety and liveness of the consensus algorithms in blockchain platforms. The Stellar Consensus Protocol (SCP), which is a consensus algorithm for the Stellar cryptocurrency using the blockchain, is utilized for the federated Byzantine agreement. The quorum configuration is one of the essential factors for ensuring the safety and liveness of the SCP; however, it has been rarely studied. In this study, we model the SCP with timed automata and verify the model using a model checking technique, with the purpose of investigating and evaluating the SCP. Through the modeling and verification of the SCP, we could check whether a certain quorum configuration ensures consensus or not, before execution on an actual network. We present several abstraction techniques that help in coping with the extremely large state space of the SCP model in formal verification. The proposed modeling and verification techniques can be utilized for other consensus protocols of various blockchain platforms using the Byzantine agreement.