EOS的DPOS算法学习笔记

本文由币乎社区（bihu.com）内容支持计划赞助

DPOS又称为：委任权益证明算法，是常见的3种共识算法（pow,pos,dpos）中的一种，下面我们来学习下这个区块链中最重要的概念。

占庭将军问题

要学习共识算法，就不得不提拜占庭将军问题，这是学习比特币等区块链相关知识无法逾越的问题。该问题最早是由Leslie Lamport解决，为了提高宣传效果，老先生在研究论文里编造了这么一个故事，事实证明非常成功，这个故事被广泛传播。故事内容是这样的：

拜占庭帝国即中世纪的土耳其，拥有巨大的财富，周围10个邻邦垂诞已久，但拜占庭高墙耸立，固若金汤，没有一个单独的邻邦能够成功入侵。任何单个邻邦入侵的都会失败，同时也有可能自身被其他9个邻邦入侵。拜占庭帝国防御能力如此之强，至少要有十个邻邦中的一半以上同时进攻，才有可能攻破。
然而，如果其中的一个或者几个邻邦本身答应好一起进攻，但实际过程出现背叛，那么入侵者可能都会被歼灭。
于是每一方都小心行事，不敢轻易相信邻国。这就是拜占庭将军问题。

从技术上理解，拜占庭将军问题是分布式系统容错性问题。加密货币建立在P2P网络之上，是典型的分布式系统，类比一下，将军就是P2P网络中的节点，信使就是节点之间的通信，进攻还是撤退的决定就是需要达成的共识。如果某台独立的节点计算机拓机、掉线或攻击网络搞破坏，整个系统就要停止运行，那这样的系统将非常脆弱，所以容许部分节点出错或搞破坏而不影响整个系统运行是必要的，这就需要算法理论上的支撑，保证分布式系统在一定量的错误节点存在的情况下，仍然保持一致性和可用性。

DPOS是什么？

委任权益证明Delegated Proof of Stake（简称DPoS）是比特股BitShares采用的区块链共识算法。

它的中文名叫做股份授权证明机制（又称受托人机制），它的原理是让每一个持有比特股的人进行投票，由此产生101位代表 , 我们可以将其理解为101个超级节点或者矿池，而这101个超级节点彼此的权利是完全相等的。从某种角度来看，DPOS有点像是议会制度或人民代表大会制度。如果代表不能履行他们的职责（当轮到他们时，没能生成区块），他们会被除名，网络会选出新的超级节点来取代他们。DPOS的出现最主要还是因为矿机的产生，大量的算力在不了解也不关心比特币的人身上，类似演唱会的黄牛，大量囤票而丝毫不关心演唱会的内容。

DPOS解决了什么问题？

在加密货币技术中，使用共识算法来保证整个区块链网络的安全可靠，著名的共识算法包括比特币网络使用的工作量证明PoW，以及Peercoin和NXT使用的权益证明PoS。但是，这些共识算法都不能解决交易性能问题，尤其是PoW算法大量消耗计算所需的电力。而委任权益证明DPoS很好地解决了性能和能耗的问题。

DPOS有什么优点？

一是，能耗更低。DPoS机制将节点数量进一步减少到101个，在保证网络安全的前提下，整个网络的能耗进一步降低，网络运行成本最低。

二是，更加去中心化。目前，对于比特币而言，个人挖矿已经不现实了，比特币的算力都集中在几个大的矿池手里，每个矿池都是中心化的，就像DPoS的一个受托人，因此DPoS机制的加密货币更加去中心化。PoS机制的加密货币（比如未来币），要求用户开着客户端，事实上用户并不会天天开着电脑，因此真正的网络节点是由几个股东保持的，去中心化程度也不能与DPoS机制的加密货币相比。

三是，更快的确认速度。

DPOS有什么缺点？

比特股的作者曾发表了一篇被广泛认为很傻的文章，预言DAO（去中心化组织）和DAC（去中心化公司）都将失败。文中披露了大量实践经验，基本算是DPoS的问题。概括起来，主要是：

一是投票的积极性并不高。绝大多数持股人（90％+）从未参与投票。这是因为投票需要时间、精力以及技能，而这恰恰是大多数投资者所缺乏的。

二是对于坏节点的处理存在诸多困难。社区选举不能及时有效的阻止一些破坏节点的出现，给网络造成安全隐患。

EOS中DPOS算法是怎样的？

在EOS中，全网持有代币的人可以通过投票系统来选择区块生产者，一旦当选任何人都可以参与区块的生产。DPOS算法一般规定，区块生产者的个数为21个或101个，也可以是其他的数量。目前EOS使用的数量是21。由 21 名生产者轮流产生新的区块。

EOS里预计每3秒生产一个区块。任何时刻，只有一个生产者被授权产生区块。如果在某个时间内没有成功出块，则跳过该块。

EOS架构中区块产生是以21个区块为一个周期。在每个出块周期开始时，21个区块生产者会被投票选出。前20名出块者首选自动选出，第21个出块者按所得投票数目对应概率选出。所选择的生产者会根据从块时间导出的伪随机数进行混合。以便保证出块者之间的连接尽量平衡。

如果出块者错过了一个块，并且在最近24小时内没有产生任何块，则这个出块者将被删除。这确保了网络的顺利运行。

在正常情况下，DPOS块链不会经历任何叉，因为块生产者合作生产区块而不是竞争。如果有区块分叉，共识将自动切换到最长的链条。具有更多生产者的区块链长度将比具有较少生产者的区块链增长速度更快。此外，没有块生产者应该同时在两个区块链分叉上生产块。如果一个块生产者发现这么做了，就可能被投票出局。

交易确认
由DPOS共识算法维护的区块链一般出块者都是100％在线的。这就是说一个交易平均1.5秒后，会被写入区块链中，同时被所有出块节点知晓这笔交易。这就意味着只需要1.5秒，一笔交易可以认定为99.9％被区块链接收了。

有一些非常情况下例如，软件bug，Internet拥塞或恶意出块者出现，区块链可能出现分叉。为了确保一个交易是不可逆转的，可以等待15个区块确认。根据EOS软件的配置，在正常情况下15个区块确认平均需要45秒。

在分叉产生的9秒钟内，出块节点就可能发现这个分叉可能并警告用户。一个节点观察网络的时候如果发现连续2次的丢块事件，这意味着改节点由95%可能性在区块链的分叉分支上。有出现3个连续的丢块以后，该节点有99％的可能性在一条分叉出来的区块链上。可以生成一个预测模型，它将利用节点丢失的信息，最近的参与率以及其他因素来快速地警告用户出现什么问题。

对这种警告的反应完全取决于业务交易的性质，但最简单的反应是等待15/21确认，直到警告停止。

交易证明（TaPoS）
EOS软件要求每个交易都包括最近的区块头的哈西。 这个哈希有两个目的：

1.防止分叉区块链上出现大量交易记录;
2.使得系统能感知到用户是否在分叉出来的区块链上

随着时间的推移，所有用户最终直接确认块链，这使得难以伪造假冒链，因为假冒将无法从合法链路迁移交易。

总结

在每一个我们能想到的自然网络分裂的情况下，委托权益证明都是强健的，甚至在面对相当数量生产者舞弊的情形时也是安全的。不像其它共识算法，当大多数生产者不合格时，DPOS还是可以继续工作。在此过程中，社区可以投票替换掉不合格的生产者，直到恢复100％参与率。我还不知道有任何其它算法可以在如此高强度和变化多端的失败条件下依然保持强健。

本文首发于微信公众号：lin-mingtan 欢迎关注交流 ^.