  It is impossible to solve the Byzantine consensus problem in an open network
of $n$ participants if only $2n/3$ or less of them are correct. As blockchains
need to solve consensus, one might think that blockchains need more than $2n/3$
correct participants. But it is yet unknown whether consensus can be solved
when less than $2n/3$ participants are correct and $k$ participants are
rational players, which misbehave if they can gain the loot. Trading correct
participants for rational players may not seem helpful to solve consensus since
rational players can misbehave whereas correct participants, by definition,
cannot.
  In this paper, we show that consensus is actually solvable in this model,
even with less than $2n/3$ correct participants. The key idea is a baiting
strategy that lets rational players pretend to misbehave in joining a coalition
but rewards them to betray this coalition before the loot gets stolen. We
propose TRAP, a protocol that builds upon recent advances in the theory of
accountability to solve consensus as soon as
$n>\max\bigl(\frac{3}{2}k+3t,2(k+t)\bigr)$: by assuming that private keys
cannot be forged, 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.
  Finally, 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. Second, the existence of TRAP demonstrates the sufficiency of
the baiting strategy. Our TRAP protocol finds applications in blockchains to
prevent players from disagreeing, that could otherwise lead to "double
spending".
