DPOS共识算法-by BM

2017/6/4 posted in  项目

这是缺失的白皮书,关于DPOS,Delegated proof of stake,委托权益共识算法的解析1。本文将分析DPOS是如何工作的,以及说明算法的有效性。一份更早的关于DPOS的介绍可以在 https://bitshares.org/technology/delegated-proof-of-stake-consensus/ 找到。然而,文中的某些方面不是纯粹的实际共识流程。

所有区块链实际是建立交易之上的确定性状态机。共识是在确定交易顺序,过滤无效交易的一个达成一致意见的流程。当前存在许多的不同的共识算法可以做到打包交易,但DPOS被多个区块链多年的可靠操作证实为更加鲁棒,安全,效率高。

所有的共识算法,区块产生的最大瓶颈在于审查。所有的区块必须通过已知的确定性状态机的逻辑检查。

DPOS算法概述

DPOS算法被分为了两部分。选举一组区块生产者和调度生产。选举流程要尽量保证,权益所有者最终能控制整个网络,因为一旦网络出现问题,权益所有者损失的将会最大。如何选举恰当的人对共识能否最终达成几乎无影响。由此,本文着重介绍的是区块生产者选好后,如何达成共识。

为了说明算法,假设只有三个区块生产者,A,B,C。因为共识需要2/3 +1 个成员来应对所有场景,在现在这个简化的模型中,我们将认为区块生产者C是那个破局者。当然在实际场景中,也许会有21个或更多的区块生产者。另外,如同POW(工作量证明)共识一样,基本规则是我们总是应该选择最长的区块链。任何时候,一个诚实的节点看到另一个合法的且更长的区块链,它应该总是切换到那个更长的分支上。

下面将通过例子展示在各种各样网络情形下,DPOS算法将如何工作。这些例子将帮助你理解为什么DPOS是鲁棒的,且是很难被攻破的。

正常情形

在正常情况下,区块生产者轮流每3秒产生一个区块。假设没有生产者错过自己顺序,那么他们生产的链条势必是最长的链条。在区块生产者在非指定时间生产区块会被认为是无效的。

少数群体的分叉

可以允许最多1/3的节点是恶意或故障,从而导致出现分叉。在这种情形下,少数分支将只能在9秒内生产1个块,而大多数分支,由于数量多一倍,将预期能在9秒内生产2个块。再一次,诚实的2/3的大多数可以比小的那一部分创建一个更长的链条。

隔离环境下的重复块生产

少数群体可能尝试创建一个无限数量的分叉,但所有分支都将比主链短,因为少数群体在链的成长上更慢。

网络碎片

网络非常有可能碎片到,没有哪一个链上的区块生产者占到了所有区块生产者中的大多数。在此情景下,最长的那个链将变成最大的一个少数群体。当网络连接恢复正常后,相对较小的那些群体将自然的切换到最长的链,从而将恢复明确的共识。

还有一种非常可能的情况是,三个分支中,最大的两个分支一样大。此时,将由相对更小的第三个分支加入网络时来打破僵局。存在奇数个区块生产者,所以僵局一般不会持续很久。后面我们还将介绍区块生产者的清洗,会将生产者随机生成顺序,以确保即使两个分支具有相同数量的生产者,分支也将以不同的长度爆发增长,导致一个分支最终接管另一个分支。

少数群体重复生产

在这种情景下,少数群体B在自己可以生产的时间节点,同时创建两条,或多条的区块链。下一个执行的生产者C,将选择B创建的可选链中的任一条。C选中的这条链将成为最长的链,当这发生是,所以如下图所示的B1链条上的结点都会转过来。所以,无论少数做恶结点制造多少的链,他们在下一轮中,肯定不会是最长的那个链。

最后的不可逆区块(没看懂)

在网络碎片的情况下,多个分叉可能持续较长时间的隔离。长远来看,最长的链将最终受到认可。但观察者需要一种手段来确定某个块是否是在最长链条的一部分(确认共识)。这可以通过2/3 + 1个区块生产者是否对某个块有确认。

下图中,块B被A、C确认了,这意味着2/3 + 1都已经确认了。由此我们可以为不可能存在更长的链了,因为2/3的区块链是诚实。

需要注意的是这个规则与比特币的6个区块确认类似。一些聪明的人可以设计一系列事件,其中两个节点可能会在不同的最后不可逆块上结束。这种极端情况需要一个攻击者,精确控制通信延迟,并需要在几分钟内实施不止一次,而是二次攻击。如果发生这种情况,那么最长链条这一长期规则仍然适用。 我们估计这种攻击的可能性足够接近0,经济后果也微不足道,不值得担心。

不足法定区块生产者

在一些不太可能的情况下,生产者没有明确达到法定人数,少数人可能继续生产块。在继续生产的区块中,利益相关者可以包含一些改变投票的交易。这些投票会选举一组新的区块生产者,并将区块生产参与度恢复到100%。一旦发生这种情况,少数人链最终会超过其它低于100%参与链。

在这个流程发生时,所有的观察者必须要明白整个网络处于不稳定的状态,直到多于67%参与者出现后才会稳定下来。哪些选择在这种情景下发起交易的,与那些在比特币中接受低于6块就确认交易成功那样,冒着类似的风险。他们必须明白,存在某些情况下,共识最终会以另一个链为准。在实践中,这种情形比在比特币中接受少于3个块就确认更加安全(证明?)。

大多数据区块生产者的腐败

如果大多数区块生产者合谋变得腐败,他们制造无限数量的分支,每一个分支都有多于2/3的大多数的签名。在这样的场景早,最后不可逆转块算法退化为最长链算法。此时最长的,获得了最大的群体认证的,将由少数的诚实节点的加入来确定。这样的情形不会持续很久,因为利益相关者会最终投票替换掉这些区块生产者。

交易即权益证明(TaPos,Transactions as Proof of Stake)

当用户对一个交易进行签名时,潜在假设是他们知道当前区块链的状态。如果关于最长链的共识发生了变化,那么对应当用户签发交易时所作的潜在假设也失去了基础。

TaPos,是指所有的交易,包括最近区块的哈希。如果它不存在于区块历史中,那么他就被认为是无效的。任何人在一个孤立的节点上签名交易,交易本身将不会得到承认,而且也不能被移植到主网络上。

这个流程带来的一个副作用是,为网络带来安全,可以抵挡长程攻击,试图生成一个替代链。个人利益相关者每次交易就是对区块链的一个投票。 随着时间的推移,所有的块都被所有利益相关者确认,这是一个不能在伪造链中复制的东西。

生产者的顺序是随机的

在所有的例子中,我们展示的是一个轮流选择区块生产者的方案。但在实际中,生产者集合是随机的,每N个块就将随机一次,其中N是生产者的数量。这种随机保证区块生产者B不能总是忽略区块生产者A,打破多个同样的分支等待。( This randomization ensures that block producer B doesn’t always ignore block producer A and that anytime there are multiple forks of identical producer counts that ties are eventually broken.)这段确实没有看懂。

结语

DPOS算法在任何可想到的自然网络中都是安全,甚至面对足够多的少数群体的勾结。与一些类似算法不同的是,DPOS可以在大多数生产者失败的情况下,继续工作。在这种情形下,社区可以投票来替换失效的生产者,直到恢复到100%的参与度。我知道现在没有其它的共识算法在这样的高失败或变动的网络情况下足够的健壮。

最终DPOS从选择区块生产者算法选择获取了显著的安全性,同时验证了高质量和唯一的节点(这是说共识的目的吧)。使用批准投票的程序保证了即使某人有50%的投票权,也没办法独自选择哪怕一个生产者。DPOS旨在优化在网络连接非常好,且诚实节点100%参与的条件下的交易的性能。这将允许DPOS能1.5秒出块的且能保证网络能达到99.9%的确定性,同时以优雅的方式,能在降级服务中恢复。

其它的共识算法设计来支持较差网络的,和面对非诚实的节点。这将导致最终的可选设计只能是更慢的网络性能,更高的延迟,高通信开销,并且在33%的节点故障时将导致整个网络挂掉。

在BitShares3年,Steem一年的成功运营中,我们经历了各种网络条件和软件bug。 DPOS已经成功地经历了这种环境,并展示了保持共识时,比任何其他链处理更多的交易时的能力。

关于作者

专注基于以太坊(Ethereum)的相关区块链(Blockchain)技术,了解以太坊,Solidity,Truffle,web3.js。

个人博客: http://tryblockchain.org
版权所有,转载注明出处

参考资料

原文来自这里 https://steemit.com/dpos/@dantheman/dpos-consensus-algorithm-this-missing-white-paper


友情链接: 区块链技术中文社区