The Combinatorics of the Longest-Chain Rule: Linear Consistency for Proof-of-Stake Blockchains
The Combinatorics of the Longest-Chain Rule: Linear Consistency for Proof-of-Stake Blockchains
复制标题
最长链规则的组合：权益证明区块链的线性一致性
DOI：
10.1137/1.9781611975994.69
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Russell, Alexander
中科院分区：
文献类型：
--
作者：
Blum, Erica;Kiayias, Aggelos;Moore, Cristopher;Quader, Saad;Russell, Alexander
通过最长链规则维护的区块链数据结构已经成为共识算法的强大算法工具。这项技术——由比特币协议推广开来——已被证明是非常灵活的，现在在各种各样的环境中支持共识算法。尽管有如此广泛的适用性和采用，但目前对该技术的分析理解高度依赖于协议领导者选举方案的细节。在权益证明设置中出现了一个特殊的挑战，其中现有的分析受到后缀长度的二次依赖。我们描述了一个区块链动力学的公理化理论，它允许在相当一般的情况下对最长链规则进行严格的推理，并建立了在一个常数内最优的一致性违反概率的边界。这解决了权益证明设置中的一个关键开放问题，我们首次实现了线性一致性。
Blockchain data structures maintained via the longest-chain rule have emerged as a powerful algorithmic tool for consensus algorithms. The technique—popularized by the Bitcoin protocol—has proven to be remarkably flexible and now supports consensus algorithms in a wide variety of settings. Despite such broad applicability and adoption, current analytic understanding of the technique is highly dependent on details of the protocol’s leader election scheme. A particular challenge appears in the proof-of-stake setting, where existing analyses suffer from quadratic dependence on suffix length.We describe an axiomatic theory of blockchain dynamics that permits rigorous reasoning about the longestchain rule in quite general circumstances and establish bounds—optimal to within a constant—on the probability of a consistency violation. This settles a critical open question in the proof-of-stake setting where we achieve linear consistency for the first time.