Paper 2020/1580

Achieving State Machine Replication without Honest Players

Conor McMenamin, Vanesa Daza, and Matteo Pontecorvi


Existing standards for player characterisation in tokenised 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 capitalisation of these tokenised protocols, honesty is becoming more expensive and more unrealistic. As such, this out-dated player characterisation 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 utilised to reflect the true nature of players in tokenised 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 maximise their tokenised rewards, or behave adversarially. This merges the fields of game theory and distributed systems, an intersection in which tokenised state machine replication protocols exist, but on which little formalisation 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.

Available format(s)
Publication info
Preprint. MINOR revision.
BlockchainState Machine ReplicationGame TheoryIncentivesDistributed Systems
Contact author(s)
conor mcmenamin @ upf edu
vanesa daza @ upf edu
matteo pontecorvi @ nokia com
2021-05-31: last of 2 revisions
2020-12-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Conor McMenamin and Vanesa Daza and Matteo Pontecorvi},
      title = {Achieving State Machine Replication without Honest Players},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1580},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.