Agreement in the presence of disagreeing rational players: The Huntsman Protocol

In this paper, a novel Byzantine consensus protocol among $n$ players is proposed for the partially synchronous model. In particular, by assuming that standard cryptography is unbreakable, and that $n>\max\bigl(\frac{3}{2}k+3t,2(k+t)\bigr)$, this protocol is an equilibrium where no coalition of $k$ rational players can coordinate to increase their expected utility regardless of the arbitrary behavior of up to $t$ Byzantine players. We show that a baiting strategy is necessary and sufficient to solve this, so-called rational agreement problem. First, we show that it is impossible to solve this rational agreement problem without implementing a baiting strategy, a strategy that rewards rational players for betraying its coalition, by exposing undeniable proofs of fraud. Second, we propose the Huntsman protocol that solves the rational agreement problem by building recent advances in the context of accountable Byzantine agreement in partial synchrony. This protocol finds applications in distributed ledgers where players are incentivized to steal assets by leading other players to a disagreement on two distinct decisions where they ``double spend''.