  An important feature of Proof-of-Work (PoW) blockchains is full dynamic
availability, allowing miners to go online and offline while requiring only 50%
of the online miners to be honest.
  Existing Proof-of-stake (PoS), Proof-of-Space and related protocols are able
to achieve this property only partially, either putting the additional
assumption that adversary nodes to be online from the beginning and no new
adversary nodes come online afterwards, or use additional trust assumptions for
newly joining nodes.We propose a new PoS protocol PoSAT which can provably
achieve dynamic availability fully without any additional assumptions. The
protocol is based on the longest chain and uses a Verifiable Delay Function for
the block proposal lottery to provide an arrow of time. The security analysis
of the protocol draws on the recently proposed technique of Nakamoto blocks as
well as the theory of branching random walks. An additional feature of PoSAT is
the complete unpredictability of who will get to propose a block next, even by
the winner itself. This unpredictability is at the same level of PoW protocols,
and is stronger than that of existing PoS protocols using Verifiable Random
Functions.
