Cryptology ePrint Archive: Report 2020/1580
Achieving State Machine Replication without Honesty Assumptions
Conor McMenamin and Vanesa Daza and Matteo Pontecorvi
Abstract: State machine replication protocols have reached a crucial juncture in their widespread
deployment. Tokenised state machine replication protocols, which utilise an internal token
for rewarding player participation, have brought about major advances in the areas of
finance, internet of things, supply chain, legal systems, and data storage, to name but
a few. However, the viability of these protocols as replacements for their centralised
alternatives requires guarantees of player actions at all times which at present do not
exist. Current standards for player characterisation in tokenised state machine replication
protocols allow for 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 FAIRSICAL, a protocol which
provably satisfies these properties, and by doing so, achieves state machine replication in
the ByRa model.
Category / Keywords: foundations / state machine replication, blockchain, distributed systems, game theory
Date: received 18 Dec 2020
Contact author: conor mcmenamin at upf edu,vanesa daza@upf edu,matteo pontecorvi@nokia com
Available format(s): PDF | BibTeX Citation
Version: 20201221:074245 (All versions of this report)
Short URL: ia.cr/2020/1580
[ Cryptology ePrint archive ]