Game-Theoretic Fairness Meets Multi-Party Protocols: The Case of Leader Election
Kai-Min Chung, T-H. Hubert Chan, Ting Wen, and Elaine Shi
Abstract
Suppose that players
want to elect a random leader and they communicate by posting
messages to a common broadcast channel.
This problem is called leader election, and it is
fundamental to the distributed systems and cryptography literature.
Recently, it has attracted renewed interests
due to its promised applications in decentralized environments.
In a game theoretically fair leader election protocol, roughly speaking,
we want that even majority coalitions
cannot increase its own chance of getting
elected, nor hurt the chance of any honest individual.
The folklore tournament-tree
protocol, which completes in logarithmically many rounds,
can easily be shown to satisfy game theoretic security. To the best of our knowledge,
no sub-logarithmic round protocol was known in the setting that we consider.
We show that
by adopting an appropriate notion of approximate game-theoretic fairness,
and under standard cryptographic assumption,
we can achieve
-fairness in rounds for ,
where denotes the number of players. In particular, this means that we can approximately match the fairness of the tournament tree protocol using as few as rounds.
We also prove a lower bound showing that
logarithmically many rounds is necessary if we restrict ourselves
to ``perfect'' game-theoretic fairness
and protocols that are
``very similar in structure'' to the tournament-tree protocol.
Although leader election is a well-studied problem in other contexts in distributed
computing,
our work is the first exploration of the round complexity
of {\it game-theoretically
fair} leader election in the presence of a possibly majority coalition.
As a by-product of our exploration,
we suggest a new, approximate game-theoretic fairness
notion, called ``approximate sequential fairness'',
which provides a more desirable solution concept than some previously
studied approximate fairness notions.
@misc{cryptoeprint:2020/1591,
author = {Kai-Min Chung and T-H. Hubert Chan and Ting Wen and Elaine Shi},
title = {Game-Theoretic Fairness Meets Multi-Party Protocols: The Case of Leader Election},
howpublished = {Cryptology {ePrint} Archive, Paper 2020/1591},
year = {2020},
url = {https://eprint.iacr.org/2020/1591}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.