Linear Consistency for Proof-of-Stake Blockchains
Linear Consistency for Proof-of-Stake Blockchains
复制标题
权益证明区块链的线性一致性
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
A. Russell
中科院分区：
文献类型：
--
作者：
Erica Blum;A. Kiayias;Cristopher Moore;S. Quader;A. Russell
通过最长链规则（由比特币推广）维护的区块链数据结构是共识算法的强大算法工具。这样的算法实现了链中块的一致性，作为它们距离链末端深度的函数。虽然对比特币的分析保证了深度为$O(k)$的块的误差$2^{-k}$的一致性，但最先进的PoS （PoS）区块链对$k$的二次依赖：以Ouroboros (Crypto 2017), Ouroboros Praos （Eurocrypt 2018）和Sleepy Consensus （Asiacrypt 2017）为例，这些协议只能确定深度$\Theta(k^2)$是足够的。由于诸如无利害关系问题等问题，这种二次差距是否是PoS的内在限制一直是一个紧迫的开放性问题，因为部署的PoS区块链进一步依赖于协议正确性的一致性。
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.