Consensus in the Presence of Rational and Byzantine Participants.

Summary We study the behaviors of participants in a consensus protocol when they exhibit rational or Byzantine behaviors. We draw inspiration from Byzantine fault-tolerant blockchain protocols (such as Tendermint). In these protocols, participants propose blocks and exchange messages. A block is accepted if a majority of participants send the message corresponding to that block (a vote), and the voters are rewarded. In this work, we study the conditions under which this protocol satisfies the following two properties: termination (the system converges to a decision) and validity (any decision is valid), when some participants are rational and the others Byzantine. We assume that Byzantine participants have the most damaging behavior to the system, while the strategies of rational participants form a perfect Bayesian equilibrium. We consider the following parameters: (i) the number of votes needed, ν, for a block to be considered accepted, and (ii) the number of Byzantine participants, denoted f , in the system. We obtain the following results: When f ≥ ν, invalid blocks are accepted, and thus validity cannot be guaranteed . When f < ν, there is an equilibrium where both validity and termination are satisfied, on the other hand, there are other equilibria where termination, and in some cases validity, are not satisfied. This allows us to conclude that there are coordination problems in the studied protocols.