부산대학교 도서관

Summary: ``The blockchain data structure maintained via thelongest-chain rule---popularized by Bitcoin---is a powerful algorithmictool for consensus algorithms. Such algorithms achieve consistency forblocks in the chain as a function of their depth from the end of thechain. While the analysis of Bitcoin guarantees consistency with error$2^{-k}$ for blocks of depth $O(k)$, the state-of-the-art ofproof-of-stake (PoS) blockchains suffers from a quadratic dependence onk: these protocols, exemplified by Ouroboros (Crypto 2017), OuroborosPraos (Eurocrypt 2018) and Sleepy Consensus (Asiacrypt 2017), can onlyestablish that depth $\Theta(k^2)$ is sufficient. Whether thisquadratic gap is an intrinsic limitation of PoS---due to issues such asthe nothing-at-stake problem---has been an urgent open question, asdeployed PoS blockchains further rely on consistency for protocolcorrectnes.\par ``We give an axiomatic theory of blockchain dynamics that permitsrigorous reasoning about the longest-chain rule and achieve, in broadgenerality, $\Theta(k)$ dependence on depth in order to achieveconsistency error $2^{-k}$. In particular, for the first time we showthat PoS protocols can match proof-of-work protocols for linearconsistency.\par ``We analyze the associated stochastic process, give a recursiverelation for the critical functionals of this process, and derive tailbounds in both i.i.d. and martingale settings via associated generatingfunctions.''