区块链周周记：共识算法

胡键 Posted at — Aug 5, 2018 阅读

在区块链去中心化的环境里，共识算法起到了交易确认，避免“双花”的作用。在这个过程中，它需要解决：

交易的先后，即如何在去中心化的环境中建立时间序列的概念
当多个节点完成交易记录时，采用谁的记录放入共识账本

关于流行的共识算法，这篇文章给出了详尽的说明，本文的内容也主要依据它来整理，更确切的讲，本文相当于一篇关于共识算法的摘要。

POW，工作量证明

最出名同时也是最古老的共识算法，比特币和以太坊均采用了它。

优点：有效
缺点：慢的要死，能耗大
机制：
- 矿工通过解决问题来完成区块的创建，问题的难度会随着全网出块速度自动进行调整，以达到控制出块速度的要求。
- 其余矿工通过验证来证明结果的正确性，并接受这个区块。
- 若有两个矿工同时出块，则链最长的那一个胜出。

POW的特点在于解决问题需要付出工作量，而验证却能很快完成，保证了区块生成的正确性，避免了恶意生成区块，从而遏制双花问题的产生。理论上控制全网51%的算力将可以操纵区块的产生，但这样的付出远超老实挖矿获得收益。在这样的激励机制之下，促使矿工向善。

由于比特币的走高，导致一些硬件公司专门生产针对比特币挖坑的ASIC矿机，使得算力日益集中。为了避免这种不公平的竞争，以太坊实现了Ethash，其特点在于挖矿效率基本与CPU无关，而与内存和带宽正相关。其目的在于“抗ASIC”。

然而，道高一尺魔高一丈。2018年4月3日，北京时间22:00，比特大陆正式推出了以太坊ASIC矿机，蚂蚁E3。

不过，POW终究是一种高能耗算法，以太坊已经开始转向更节能的POS算法。

POS，权益证明

以太坊将在其最后一个里程碑（Serenity）由POW切换到POS。

优点：攻击成本更高，更去中心化，节能
缺点：权益粉碎攻击（Nothing at Stake）
机制：
- 持币量和持有时间为影响因子，每发现一个区块，则币龄清0，然后从区块中获得一定奖励（相当于“利息”）。
- 本质上是“虚拟挖矿”，任何拥有Token的用户都能参与，不像POW中那样必需购买所谓的“矿机”。
- 用户用其手中的Token投注哪些区块有效，若遇到分叉，则花Token来支持对应的分叉。若大多数人投票正确的分叉，则那些投注在错误分叉的用户将在正确的分叉上失去其押注（即Token）。

由于手中的Token越多，影响力越大，若这些大佬投注错误的分叉将导致其损失，故他们会选择不作恶。然而，对于那些“无产阶级”，情况就不一样了。

由于本身分叉在POS中并不需要算力，因此分叉在POS中是常态。并且在早期的POS实现中，只有奖励而没有惩罚，即使投注的分叉错误也没有损失，因此用户可以在多个分叉上同时投票，这就是所谓的“权益粉碎攻击”。鉴于此，以太坊的POS算法“Casper协议”中引入了保证金的概念，一旦被系统认定是“坏人”，保证金将被没收。

理论上，如果收集全网超过50%的Token将可以操纵区块产生，但这种情况极难出现。

DPOS，委托权益证明

目前大热的EOS采用的正是这个算法。

优点：交易成本低，伸缩性好，节能
缺点：部分中心化
机制：
- Token持有者选出委托人来代表他们投票，典型的委托人数量在21~100。委托人周期重选，负责出块。
- 在DPOS中，矿工协助出块，而非像POW/POS中那样相互竞争。
- 委托人越少，效率越高，并能保证每位委托人在指定时间内发布区块。若委托人不尽职（没有出块或发布无效区块），Token持有者可以让其出局，让更好的委托人替代他。

部分的中心化让DPOS的效率相当高。

POA，权威证明

以太坊Kovan测试网采用此算法。

优点：高吞吐量，性能好
缺点：中心化系统
机制：由系统认证过的账户（如Admin）来验证交易，此账户相当于其他节点的权威。

一般用在私有网络。

PoWeight，权重证明

FileCoin采用此算法。

优点：可定制，性能好
缺点：激励机制有挑战
机制：
- 与POS基于Token数量为基准来决定发现下一区块的概率类似，PoWeight基于某种权重值为标准，比如FileCoin就是以节点存储的IPFS数据为权重。

BFT，拜占庭容错

优点：高吞吐量，低成本，性能好
缺点：半信任
解决问题：不可靠网络且存在恶意节点（如丢包或错误包）时，各节点达成状态的一致性。

实用拜占庭容错算法（PBFT），原始BFT的性能极低，后来出现PBFT，将算法复杂度由指数级降低到多项式级别，从而使得算法可以实际应用。节点3f+1可容错f个节点。超级账本目前采用此算法，<20个节点时，性能不错，再多节点时，性能会出现下降。优点：高交易吞吐量；缺点：中心化，需授权。

联邦拜占庭协议（FBA），Stellar和Ripple采用，每个节点负责自己的链，在消息到达时对它们进行排序，建立相应的事实（Truth）。Ripple中，节点有基金会预选，Stellar中由用户来决定相信哪个节点。

DAG，有向无环图

DAG又称“无块区块链（Blockless）”，它和区块链的差异：

单元：DAG是TX（交易），区块链是Block。
拓扑：
- DAG是交易单元组成的网络，可异步并发写入交易，相当于多核多线程CPU；
- 区块链是区块组成的单链，按时间依次同步写入，相当于单核单线程CPU。
粒度：DAG每个单元记录一个用户的交易，区块链每个单元记录多个用户的交易。

DAG有望成为新一代的区块链基础，最出名的三个项目：IOTA、Nano、ByteBall。

优点：网络性能高，低成本
缺点：依赖于具体实现

DAG不依赖于区块链数据结构，几乎完全用异步方式处理交易，最大的优点是理论上每秒可处理无限事务。算法变种：

Tangle，IOTA，要发送一个交易，必须先验证收到的两个历史交易（采用MCMC进行选择）。理论上，若有人能产生1/3的交易，它就可说服其余人它的无效交易是有效的（因为每个节点发送前需要先验证2个交易）。目前，在能有效防止某节点产生1/3的交易量之前，IOTA采用了“复检”的方式：在被称为“协调员”的中心节点上验证所有交易。这也是IOTA最为人诟病的地方。
HashGraph，一种gossip协议共识，节点随机地跟其他节点共享它们知道的交易，最终使得所有交易被全网知晓。虽然非常快，但无法阻止“女巫攻击”，故非常适合私有网络，但对于公有链，不适合。
Block-Lattice，Nano，每个用户一个链，只有它自己能够写入，所有人保留一份所有链的副本。每个交易被分拆成两部分：发送者链上的发送区块和接收者链上的接收区块。易受Penny-Spend Attack，攻击者向大批的空钱包发送数量极小的交易，迫使大量节点不得不跟踪交易。
Spectre，POW事件序列化（Serialization of Proof-of-work Events），通过递归选举来确认交易，利用POW和DAG相结合来提高比特币伸缩性的建议解决方案。被挖出来的区块指向多个父区块，而非一个。由此，比特币中“最长链胜出”在此背景下变成“最多孩子的区块胜出”，目前尚未大规模应用和测试。

其他共识算法

POI，重要性证明，既不需要强大的算力，也不需要雄厚的资产，只需向系统证明自己的重要性即可。比如，活跃度和交易量。
POB，烧毁证明，创建区块需要为创建的Token支付费用。
POA，此A为Asset，即资产证明。
……

区块链不可能三角形

与CAP原理类似，区块链中也同样存在不可能三角形，其形式如下：

即：在去中心化、性能和安全三个方面最多得其二，无法全部满足。

参考资料

觉得有帮助的话，不妨考虑购买付费文章来支持我们 🙂 ：

付费文章

DTeam 技术日志

Doer、Delivery、Dream