Building Regular Registers with Rational Malicious Servers and Anonymous Clients -- Extended Version

Abstract

The paper addresses the problem of emulating a regular register in a synchronous distributed system where clients invoking $\mathsf{read}()$ and $\mathsf{write}()$ operations are anonymous while server processes maintaining the state of the register may be compromised by rational adversaries (i.e., a server might behave as \emph{rational malicious Byzantine} process). We first model our problem as a Bayesian game between a client and a rational malicious server where the equilibrium depends on the decisions of the malicious server (behave correctly and not be detected by clients vs returning a wrong register value to clients with the risk of being detected and then excluded by the computation). We prove such equilibrium exists and finally we design a protocol implementing the regular register that forces the rational malicious server to behave correctly.

Extended version of paper accepted at 2017 International Symposium on Cyber Security Cryptography and Machine Learning (CSCML 2017)