Abstract scene, by Jay Meuser

上一篇简短地引入了共识机制,以及共识机制解决的两个主要问题:崩溃容错问题和拜占庭容错问题。第一类是处理在交易过程或计算机崩溃时造成的传递延迟问题,第二类则是真正处理关于信任的共识算法。下面介绍一些两类常见的共识算法。

一、拜占庭容错

1.  PoW共识机制

PoW机制在1998年在B-money设计中提出。在PoW机制下区块链中的节点需要牺牲算力来得出一个随机数(nonce),使得这个随机数与这个区块上的其他信息结合通过哈希运算得到的哈希值能够小于一个特定的哈希值,这个随机数就是满足条件的随机数。最先得到这个随机数的矿工向区块链网络中的其他节点广播,得到其他节点的验证之后这个区块就被写入了区块链中。PoW机制的缺陷比较明显,当恶意节点能够控制区块链中一半以上算力时就能实现改变区块链区块数据,实际上已经有黑客做到了这点。当然由于区块链中的节点是处于竞争关系,上述的情况,一般也很难出现。同时,区块链挖矿也带来了大量的电力损耗。

2.  PoS共识机制

PoS机制最早在2013年被提出,首次在Peercoin被实现。PoS机制根据拥有的数字货币的数量以及持有时间的长短来决定某个节点挖矿的难易度。掌握虚拟货币的量越多越容易挖矿也越有可能维护这个区块链网络,因为如果区块链网络被扰乱损失最大的也是这些节点。不同于PoW机制全网一半算力的攻击,要在PoS机制下控制最终的结果需要控制全网1/3的资源。这个可能要困难一些,这可能意味着要掌握全网1/3的虚拟货币。PoS机制有他的改进算法,其中较为常见的DPoS就是其中之一。通过选出一些节点进行记账,相当于现实中的董事会,在实践中也取得了不错的效果。

各种PoX系列算法思路基本都是采用经济上的惩罚来制约破坏者。

3.  BFT共识机制

CastroLiskov1999年提出的PBFT算法是第一个得到广泛应用的BFT算法。拜占庭容错最先被提出是作为用来解释一致性问题的虚构模型。拜占庭是古代东罗马帝国的首都,由于地域宽广,守卫边境的多个将军需要通过信使来传递消息,达成某些一致的决定。但由于将军中可能存在叛徒,这些叛徒将努力向不同的将军发送不同的消息,试图会干扰一致性的达成。对于拜占庭问题只有总结点数N与恶意节点数F满足的条件为N3F+1时问题才有解,只要系统中2/3的节点是正常工作的就可以保证一致性。

二、崩溃容错

1. Paxos算法

在不考虑可能出现拜占庭容错的情况,这个算法解决的问题是在一个可能发生进程缓慢、结束、重启和消息延迟、丢失、重复的的分布式系统中就某个值达成一致。首先将议员的角色分为proposersacceptors,和learners(允许身兼数职)。proposers提出提案,提案信息包括提案编号和提议的 valueacceptor收到提案后可以接受(accept)提案,若提案获得多数acceptors的接受,则称该提案被批准(chosen);learners 只能学习被批准的提案。划分角色后,就可以更精确的定义问题:

1. 决议(value)只有在被proposers提出后才能被批准(未经批准的决议称为提案(proposal);

2. 在一次Paxos算法的执行实例中,只批准(chosen)一个value;

3. learners只能获得被批准(chosen)的value

通过不断加强上述3个约束(主要是第二个)获得了Paxos算法,这保证了坏的情况不会发生,减少了区块链网络运作出错的情况。

2.  Raft算法

Raft是一个为了取代Paxos的共识算法。在提供相同容错性及性能的同时提供了更好理解的算法。每个参与者随机经过一定时间发起选举,选中一个节点为Leader,执行提案时会先同步Leader和其他节点。在处理请求时其他节点(follower)都会将请求发送给LeaderLeader会定时发送讯息以确认Leader是否还在工作,其他节点一段时间内没有接收到讯息时就会进入新的选举阶段。

在上述两个算法中都允许部分节点出现进程或消息传递的故障。还有更多例如2PC(二阶段提交)和3PC(三阶段提交)也都是处理崩溃容错的共识算法。在分布式系统中崩溃容错共识机制与拜占庭容错共识机制同样都是不可缺少的。



分享到: