本篇博客将概述Lightcurve团队提出的Lisk拜占庭容错(BFT)共识算法,以及更改版BFT的重要性,主要特性和好处,并将其与其他共识算法进行比较。

拜占庭式容错解决了分布式系统中一个非常现实的问题——确保系统中的计算机能安全地就某些数据达成一致。共识算法的思想是,代表不仅锻造区块,而且在每个高度对正确的区块进行投票。因此需要将拜占庭容错(BFT)添加到Lisk中的共识算法中,并生成终结性区块,也就是说,只要有一定比例的诚实代表,区块永远不会被还原。在Lisk中引入侧链和在不同链之间的通信之前,一定要确保区块的终结性和共识的安全性。下面,我将更详细地解释这些属性的含义、它们为何有用以及提议的共识算法如何工作,并将其与其他行业方法进行比较。

Lightcurve的科学团队在推出Lisk改进提议(LIP)之后,继而在Lisk的研究论坛(Lisk上发布了该提议。去年年底推出的LIP以一种开源的方式讨论和推动Lisk平台的发展。我们的研究论坛上有许多LIP正在进行讨论。作为Lightcurve的一个科学团队,我们正在研究如何达成Lisk路线图中定义的所有LIP目标,鼓励Lisk社区以反馈、讨论提议和提出自己的想法来参与这项研究工作。

本文目录:

引入拜占庭容错的动机

提出了BFT共识算法

基本概念:区块投票、安全与活性

BFT算法的关键特性

与其他BFT共识算法的比较

比较Tendermint BFT相比:单独的消息会降低区块提议的速度

比较以太坊BFT:传播和存储投票消息需要开销

比较工作量证明区块链

比较比特币:概率担保取决于确认数

比较以太经典:被证明有可能发生市值5.5亿美元的51%攻击

下一步:社区评审和反馈

引入拜占庭容错的动机

现在我们已经了解了主要概念,现在来看看Lisk区块链当前的共识协议。在Lisk中,在每10秒,101个活跃代表(按投票权重排名前101的代表)中就有1个向Lisk区块链添加一个区块。如果网络通畅,并且活跃代表在线(大多数情况下都是这样),网络会一个接一个地出块,一直引用之前提出的区块,形成一个不断增长的链,即Lisk区块链。然而,有时可能会出现相同父区块的多个子区块和分离的增长链。如果两个区块都不是另一个的后代,我们称之为冲突区块。这种情况可能会发生,例如,由于网络延迟或攻击,并非所有节点都接收到一个区块,或代表在其10秒时间窗口中锻造了多个有效区块。

Lisk改进提案:引入拜占庭容错共识算法-LISK应用链

在这种情况下,网络中存在多个有效的链,节点需要一个公共规则来决定如何选择一条有效链。这个规则称为分叉选择规则。在Lisk中,如原始DPos白皮书中所述,节点选择最长的链,意味着是所有有效的链中最长的链。然而,还增加了一些附加规则,以防止攻击者使用无效高度的区块,或通过创建替代链,从而导致大量的区块被删除,轻松地破坏共识协议。例如,考虑要维持网络中相同链的节点数(也称为哈希广播共识)。当从一个链切换到另一个链时,节点也不会删除超过201个区块。删除的区块数基于以下经验:冲突区块的情况几乎总是在两轮内解决。

Lisk网络中当前的分叉选择规则实践地很好,但是没有提供最终性,这是在所有理论上可能的网络情况下,保证某个区块永远不会被还原。例如,一旦一个交易打包进Lisk区块链的一个区块中,并且这个区块后添加了201个区块,那么这个区块最终仍然有可能不属于Lisk区块链,即使没有代表恶意操作。例如,如果一个网络分裂了很长一段时间,少数群体的代表可以在一个链上锻造,多数群体的代表可以在另一个链上锻造,这两条链都包含201个以上的不同区块。

Lisk改进提案:引入拜占庭容错共识算法-LISK应用链

最终,所有的交易所和网络参与者都有可能转向更长的多数链。少数群体的代表现在必须还原201个以上区块(这将需要手动干预),来更改为多数链。

由于上面描述的场景,我们想在Lisk中引入一种基于理论分析的共识算法,它已被证明可在任意长周期恶劣网络中保持一致性。此外,我们的系统也默许拜占庭式错误,即代表通过发送相互矛盾的信息来恶意攻击网络,或者只是代表离线。共识算法只依赖于一个最小的假设,即一定比例的代表行为诚实(遵循共识规则),从而保证最终性,从而产生最高程度的确定性,即交易将不可逆转地打包进区块链。换句话说,这些最小的假设产生了最高程度的信任,即区块链的特定部分不可变,并且相应的区块不能被还原。这一点对于构建在区块链技术上的许多应用程序非常重要。例如,当交易所给你贷款LSK代币时,它们需要非常高的确定数,以确保该操作无法撤消。未来要在Lisk生态系统中实现链与链之间价值转移,还需要一条链具有非常高的确定数,从而确保另一条链启动的价值转移不可逆转。

BFT共识算法

既然确定了最终性的重要性,让我们更深入地看看提出的BFT共识算法将如何改进Lisk网络。

基本概念:区块投票、安全与活性

Lisk的共识算法的基本思想是,代表们不仅提出区块,而且在对每个他们认为正确高度的区块进行投票。让我们先假设一个简化模型,以便更好地理解。假设代表在给定的高度为他们认为正确的区块投一票(例如,通过向网络发送包含对区块投票的特定消息)。节点进一步敲定区块,这意味着一旦一个区块达到一定数量的选票,就不可撤销地认为它是区块链的一部分。

第一个问题将是如何为最终敲定一个区块选择合适的投票门槛。一种观点可能是占据多数选票就足够了。Lisk的101名代表中至少有51人投了赞成票。我们还希望共识算法能默许拜占庭式错误,特别是恶意代表,他们可能会发送相互矛盾的投票信息。例如,假设在不同的链中有两个区块,每个区块有50个代表投票。

Lisk改进提案:引入拜占庭容错共识算法-LISK应用链

一个恶意代表可以投票给这两条链中的区块,如果51票生效,那么这些区块将被视为最终区块。一种从不敲定冲突区块为最终区块的共识算法被称为满足安全性能。所以为了满足安全性,我们需要选择一个更高的投票门槛。

现在,假设我们非常保守,只有在得到所有101名代表的投票后才最终确定一个区块。在这种情况下,恶意代表永远不能投票,并且这个区块也永远不会最终确定,所以这也不是一个好主意。也就是说,共识算法要满足活性属性,这意味着在某一点新区块实际上已被最终确定。因此,投票门槛不能太高。

通过尝试不同的投票门槛,我们认为最终投票门槛为,101个代表中至少有68个代表参与投票,33名不参与,这样仍然可以确定一个新的区块。此外,如果等于或少于33位代表投票支持两个相互冲突的区块,那么区块在每个高度仍然会有获得68票。这个简化示例,意味着选择68为投票门槛,我们可以默许最多的拜占庭代表,即33个拜占庭代表。

Lisk改进提案:引入拜占庭容错共识算法-LISK应用链

实际的情况更复杂,一轮投票不足以满足安全属性,因为网络可能会出现延迟,投票消息可能会丢失。例如,68个代表在同一链上投票给一个区块,但是其他代表未参与投票,后来又为另一条链上的区块投票,那么两个冲突的区块可以得到68票。因此,有必要引入两轮投票,并且只有在两轮成功投票后才能最终确定一个区块,这将在下一节详细介绍。

Lisk改进提案:引入拜占庭容错共识算法-LISK应用链

该算法的关键特性

我们称第一轮为预投票,第二轮投票为预提交。只有在一个区块获得至少68个预投票之后,代表才能为执行预提交。此外,一个区块接收到68个预提交之后,该区块就最终确定了。在为区块执行预提交时,需要满足一些附件条件。例如,代表在为一个区块发送了预提交之后,将只对该区块的后代进行预投票(除非另一条链有一个更高高度的区块,拥有68个或以上的预投票)。在Lisk官网的Lisk-BFT部分,详细地描述了该算法,并给出了其正确性证明,以及在“ introduce BFT consenses(BFT共识介绍)”中描述了如何将这种共识引入Lisk。

Lisk-BFT共识算法的主要优点是,代表不会显式地发送单个消息。相反,预投票和预提交隐含代表在对每个区块添加更高的高度,这个高度是他们之前锻造的。此外,分叉选择规则要求代表,在拥有68或以上预选票的最大高度区块的链上进行投票和锻造。为了让代表有效地应用这个分叉选择规则,每个区块都包含至少68个预投票的区块高度。这意味着在区块中只有两个额外的整数,并且没有额外投票消息的开销,这使得Lisk具有安全的拜占庭容错共识算法。如果有68个或以上诚实代表,则共识算法则具备我们在上面介绍的安全性和活性特性。特别是,只要33名或以下的代表是拜占庭人,两个相互冲突的区块就永远得不到最终确定。

比较其他BFT共识算法

在制定这个LIP的过程中,我们考虑了其他多种拜占庭容错共识算法。下面是与其他两个流行BFT共识的比较。

比较Tendermint BFT:单个消息会降低区块提议的速度

Tendermint是区块链最早使用的BFT共识算法之一,最终确认区块需要两轮投票,但区块提议者将他们的投票发送到单独的消息中,只有在前一个区块最终确认后,才会提出一个新的区块。这意味着区块会很快得到最终确认,但区块提案会因为附加的两个投票轮而变慢,直到两轮必须成功完成,才能提出新区块。例如,如果有101个区块提议者以Tendermint共识参与投票,这意味着每个区块需要通过网络传播202条不同的消息,并且这些数据包括需要存储的签名。此外,在不使用聚合签名方案的情况下,目前这种开销会随着提议者参与数量增加而线性增长。对于Lisk-BFT,由于不需要单独的消息,并且区块链可以在未最后确定区块的情况下继续增长,所以Lisk的BFT速度与代表提议区块一样快。平均而言,必须在区块后添加大约150个区块,才能最终确定该区块。

比较以太坊 BFT:网络传播和存储投票消息需要开销

Casper友好终结小工具(Casper-FFG)是针对以太坊区块链提出的一种共识算法。在Casper-FFG中,区块的提议和对区块的共识各自独立进行,参与者不为每个区块发送单独的投票消息,而是只针对特定的检查点发送(例如,每50个区块)。取决于以太坊采用的具体参数,类似我们的BTF,直至区块被最终确认,但Casper-FFG需要网络传播和存储投票信息以证明违反协议的参与者,这需要额外的开销。未来,我们可能会探索通过使用独立的投票消息和适当的聚合签名方案来改进我们的BTF共识算法,以实现更快的最终性,同时降低投票信息开销,因为投票消息可以聚合。

比较工作量证明区块链

在本节中,我们想将我们提出的拜占庭容错共识算法给出的最终性与工作量证明(如比特币)中的最终性进行比较。工作量证明区块链,即参与者选择需要最多工作量的链,在假设大多数矿工(就哈希率而言)诚实的情况下,会产生概率最终性。概率最终性(probabilistic finality)意味着一个区块被还原的可能性越来越小,作为最终区块后代,添加的区块越多,就永远不能保证一个区块不能被还原。

与比特币相比:概率担保(probabilistic guarantee)取决于确认数

例如,在比特币中,一笔交易有6个确认(即,是在包含交易的区块之上构建的5个后续区块),直到它在未来被高度确定地视为比特币区块链的一部分。然而,即使大多数矿工是诚实的,一个哈希率相当低的矿工,可能仍然会极幸运地找到一个不包含该交易的更长替代链(具体概率见比特币白皮书第11节或https://people.xiorg/ ~greg/attack_success.html)。此外,大多数矿工都是诚实的假设,实际上并不适用于大多数工作量证明区块链。由于像NiceHash这样的挖矿市场,暂时获得一半以上的网络哈希率是可能的,而无需在挖矿硬件上进行大量投资。这可以用来执行51%的攻击,即还原大量网络参与者认为在将来不可撤销地成为区块链的部分区块。

Lisk改进提案:引入拜占庭容错共识算法-LISK应用链

比较以太经典:被证明有可能发生市值5.5亿美元的51%攻击

最近对以太经典51%的攻击表明,51%的攻击在实践中是可行的,即使对市值较大的加密货币也是如此。有关在不同的工作量证明区块链上执行1小时51%攻击的代价,请参见Crypto51。这表明,对于大多数工作量证明区块链来说,并不十分确定某些信息将来是否会不可逆转地成为区块链的一部分,比如代币转移。

下一步:社区评审和反馈

正如LIP目的和指南中所述,我们现在鼓励Lisk社区对Lightcurve提出的“引入BFT共识”LIP进行全面的审查并在我们的研究论坛中给出反馈。请注意,“改进区块验证”目标及其实现计划将在下一个路线图阶段“安全性和可靠性”中进行。与此同时,我们期待社会各界就这方面的改善提供意见。

——Jan Hackfeld博士,Lightcurve公司的密码学博士

关于Jan Hackfeld

Jan Hackfeld刚从分布式算法和优化博士学位毕业,Jan是一个敏锐的问题解决者。作为Lightcurve的密码学家,他负责研究如何改进当前Lisk协议的不同方面。工作之余,Jan喜欢户外运动、沙滩排球、自行车和徒步旅行。Jan于2018年在柏林理工大学成功地完成了博士学位的答辩,目前正在等待官方指定他的新头衔。他还拥有亚琛工业大学的数学硕士学位。

Lisk改进提案:引入拜占庭容错共识算法-LISK应用链