  Cryptographic Self-Selection is a subroutine used to select a leader for
modern proof-of-stake consensus protocols, such as Algorand. In cryptographic
self-selection, each round $r$ has a seed $Q_r$. In round $r$, each account
owner is asked to digitally sign $Q_r$, hash their digital signature to produce
a credential, and then broadcast this credential to the entire network. A
publicly-known function scores each credential in a manner so that the
distribution of the lowest scoring credential is identical to the distribution
of stake owned by each account. The user who broadcasts the lowest-scoring
credential is the leader for round $r$, and their credential becomes the seed
$Q_{r+1}$. Such protocols leave open the possibility of a selfish-mining style
attack: a user who owns multiple accounts that each produce low-scoring
credentials in round $r$ can selectively choose which ones to broadcast in
order to influence the seed for round $r+1$. Indeed, the user can pre-compute
their credentials for round $r+1$ for each potential seed, and broadcast only
the credential (among those with a low enough score to be the leader) that
produces the most favorable seed.
  We consider an adversary who wishes to maximize the expected fraction of
rounds in which an account they own is the leader. We show such an adversary
always benefits from deviating from the intended protocol, regardless of the
fraction of the stake controlled. We characterize the optimal strategy; first
by proving the existence of optimal positive recurrent strategies whenever the
adversary owns last than $38\%$ of the stake. Then, we provide a Markov
Decision Process formulation to compute the optimal strategy.
