Achieving State Machine Replication without Honest Players

Existing standards for player characterization in tokenized state machine replication protocols depend on honest players who will always follow the protocol, regardless of possible token increases for deviating. Given the ever-increasing market capitalization of these tokenized protocols, honesty is becoming more expensive and more unrealistic. As such, this out-dated player characterization must be removed to provide true guarantees of safety and liveness in a major stride towards universal trust in state machine replication protocols and a new scale of adoption. As all current state machine replication protocols are built on these legacy standards, it is imperative that a new player model is identified and utilized to reflect the true nature of players in tokenized protocols, now and into the future. To this effect, we propose the ByRa player model for state machine replication protocols. In the ByRa model, players either attempt to maximize their tokenized rewards, or behave adversarially. This merges the fields of game theory and distributed systems, an intersection in which tokenized state machine replication protocols exist, but on which little formalization has been carried out. In the ByRa model, we identify the properties of strong incentive compatibility in expectation and fairness that all protocols must satisfy in order to achieve state machine replication. We then provide Tenderstake, a protocol which provably satisfies these properties, and by doing so, achieves state machine replication in the ByRa model.