  The blockchain data structure maintained via the longest-chain
rule---popularized by Bitcoin---is a powerful algorithmic tool for consensus
algorithms. Such algorithms achieve consistency for blocks in the chain as a
function of their depth from the end of the chain. While the analysis of
Bitcoin guarantees consistency with error $2^{-k}$ for blocks of depth $O(k)$,
the state-of-the-art of proof-of-stake (PoS) blockchains suffers from a
quadratic dependence on $k$: these protocols, exemplified by Ouroboros (Crypto
2017), Ouroboros Praos (Eurocrypt 2018) and Sleepy Consensus (Asiacrypt 2017),
can only establish that depth $\Theta(k^2)$ is sufficient. Whether this
quadratic gap is an intrinsic limitation of PoS---due to issues such as the
nothing-at-stake problem---has been an urgent open question, as deployed PoS
blockchains further rely on consistency for protocol correctness.
  We give an axiomatic theory of blockchain dynamics that permits rigorous
reasoning about the longest-chain rule and achieve, in broad generality,
$\Theta(k)$ dependence on depth in order to achieve consistency error $2^{-k}$.
In particular, for the first time, we show that PoS protocols can match
proof-of-work protocols for linear consistency. We analyze the associated
stochastic process, give a recursive relation for the critical functionals of
this process, and derive tail bounds in both i.i.d. and martingale settings via
associated generating functions.

Cryptography and Security;Discrete Mathematics