区块链周周记：共识算法
在区块链去中心化的环境里，共识算法起到了交易确认，避免“双花”的作用。在这个过程中，它需要解决：
- 交易的先后，即如何在去中心化的环境中建立时间序列的概念
- 当多个节点完成交易记录时，采用谁的记录放入共识账本
关于流行的共识算法，这篇文章给出了详尽的说明，本文的内容也主要依据它来整理，更确切的讲，本文相当于一篇关于共识算法的摘要。
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原理类似，区块链中也同样存在不可能三角形，其形式如下：
image
即：在去中心化、性能和安全三个方面最多得其二，无法全部满足。
