背景图

共识算法概述

一开始就认为共识算法其实比较简单,但是一直没有认真地总结,导致这块知识一直都是短板。其实共识算法的本质是分布式一致性的问题,但是显然这和分布式一致性略有区别。有以下两个主要的区别:

  1. 传统的分布式一致性算法认为,每个节点都不会欺诈,如果出现问题一般都是网络分区,请求顺序的问题。但是共识算法不能保证每一个节点都是正常节点,可能就是欺诈节点。
  2. 传统的一致性算法只要有值就行,不太关心哪个节点写入数据。但是共识算法,必须公平地对待每一个节点,选取这个节点必须是公平的,于是就有了POW和POS机制的出现。这个就好像是选择值本来一个很纯粹的事情绑定了特定的业务,所以要处理的事情就变得很复杂了。所以在分析共识算法的时候要将这个点剥离出来,拨出来之后这就是一个分布式一致性的问题。

所以说共识算法,剥离了上面两个方面的因素就是一个纯粹的分布式一致性算法。其实说白了共识算法就是分布式一致性在P2P网络中的应用。

其他的分布式协议:PaxosRaft

从拜占庭将军问题谈起

这是一个很经典的分布式一致性问题的提出,这里我们就不做很多的说明。可以查看维基百科中关于这点的描述。

拜占庭容错 BFT

这是拜占庭将军问题的早期的解决方案。在1982年的论文中提过几个解决方案。方案中把问题往下拆解,认为在“拜占庭将军”的问题可以在“军官与士官的问题”里解决,以降低将军问题的发生。而所谓的“军官与士官的问题”,就是探讨军官与他的士官是否能忠实实行命令。

其中一个解决方案认为即使出现了伪造或错误的消息。只要有问题的将军的数量不到三分之一,仍可以达到“拜占庭容错”。原因是把同样的标准下放到“军官与士官的问题”时,在背叛的军士官不足三分之一的情况下,有问题的军士官可以很容易的被纠出来。比如有军官A,士官B与士官C。当A要求B进攻,却要求C撤退时只要B与C交换所收到的命令,就会立刻发现A有问题以函数来表示,将军的总数为n,n里面背叛者的数量为t,则只要n > 3t就可以容错。

另一个解决方案需要有无法消去的签名。在现今许多高度信息安全要求的关键系统里,数字签名就经常被用来实现拜占庭容错,找出有问题的将军。然而,在生命攸关系统里,使用 错误侦测码就可以大幅降低问题的发生。无论系统是否存在拜占庭将军问题。所以需要做密码军算的数字签名也不一定适合这类系统。

假如上述两个解决方案里,将军们无法直接通信时,该论文亦有进一步的解决方案。
此外,1980年代还有其他用来达到拜占庭容错的架构被提出,如:FTMP、MMFCS 与 SIFT。

使用拜占庭容错算法 PBFT

1999年,卡斯托(Miguel Castro)与李斯克夫(Barbara Liskov)提出了实用拜占庭容错(PBFT)算法。该算法能提供高性能的运算,使得系统可以每秒处理成千的请求,比起旧式系统快了一些。后来也有针对BFT算法的各种优化版,但是优化的方向不同,有的是为了加强健壮性,有的是为了加强网络速度等。下面来提一下这个PBFT算法的一些简要知识,具体请查看:实用拜占庭容错算法PBFT

PFBT流程图
上面是PBFT的图示,下面我们讲个上面流程的故事。

  1. 总司令给军长下命令向前行军500公里;
  2. 军长将消息(不只有命令)传递给所有师长;
  3. 1号2号师长又把消息传给其他师长,3号师长处于叛逃状态;
  4. 军长再次询问各位师长是否同意执行命令。
  5. 所有军官(包括军长和师长)向总司令汇报结果。

这个算法的实用性为何高于BFT呢?因为在BFT的描述中,我们可以发现每个节点都不知道其他节点的情况,都会去询问所有的人他们所获得情况,进而做出自己的判断(只要大多数人同意的就是正确的)。这个过程达成一致性的时间比较长,而且耗费大量的P2P网络资源,不适合共识算法(规模不大是可以的)PBFT算法就是校验放给一个人去校验就可以了,而不需要全体所有的人来进行校验,你也不知道进行校验的人是谁,所以是安全的,分布式一致性也很容易达成。

节点验证的机制

节点验证的方式其实是两方面的,一是节点未篡改通讯协议,二是节点的选举极具公平意义。现在区块链上的实现主要是POW和POS两种方式。

工作量证明 POW

这是比特币使用的共识机制,主要是通过不停地hash计算,算出nonce已满足难度系数。这样请求不易伪造,而且谁先解决难题谁就有记账权,我觉得这个是不可被攻击的。要想攻击必须具有51%以上的算力。

权益证明 POS

这种安全的机制比较简单就是你持有币所获得的权限。

POS:也称股权证明,类似于财产储存在银行,这种模式会根据你持有数字货币的量和时间,分配给你相应的利息。

简单来说,就是一个根据你持有货币的量和时间,给你发利息的一个制度,在股权证明POS模式下,有一个名词叫币龄,每个币每天产生1币龄,比如你持有100个币,总共持有了30天,那么,此时你的币龄就为3000,这个时候,如果你发现了一个POS区块,你的币龄就会被清空为0。你每被清空365币龄,你将会从区块中获得0.05个币的利息(假定利息可理解为年利率5%),那么在这个案例中,利息 = 3000 * 5% / 365 = 0.41个币,这下就很有意思了,持币有利息。

委任权益证明 DPOS

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

Casper

这个协议也是POS,是以太坊正在开发的下一代以太坊共识协议。

以太坊社区提出的正在研发中的共识协议名为Casper。Casper的基本思路是,任何人抵押足够多的以太币到系统中就可以成为矿工参与到挖矿过程。共识算法要求所有的矿工诚实工作,如果一个矿工有意破坏,不遵守协议,系统就会对矿工做出惩罚:没收之前抵押的以太币。有人把Casper这样的挖矿机制称为“虚拟挖矿”,比特币的矿工要参与挖矿需要先购买矿机,Casper则要先抵押以太币到系统中;比特币的矿工如果不按规则挖矿,则会损失电费以及可能的挖矿收益,而Casper中,不守规则的惩罚更为严重,除了失去挖矿收益,还要销毁“矿机”:抵押的以太币会被系统没收!

有向无环图 DAG

DAG则采用异步机制替代链式检查点的同步策略,在优秀的软件实现中如果能够有效控制网络风暴带来的带宽需求指数增加,其不失为一种对最终一致性场景有较好应用前景的算法。但是DAG的局限性也极为明显,其体系无法被利用在需要进行同步操作或一致性要求较高的操作中(例如支付结算等)。

第一次提出DAG跟区块链结合是在Nxt社区,可以发现DAG最初出现就是为了解决区块链的效率问题。比特币的效率一直比较低,基于工作量证明共识下的出块机制是一个原因,由于链式的存储结构,整个网络中同时只能有一条链,导致出块无法并发执行。社区有人提出DAG的拓扑结构来存储区块,这个时候更多还是类似侧链的解决思路,不同的链条存储不同类型的交易,这样降低出现双花的可能,在之后某个节点需要合并的时候,几个分支再归并到一个区块。

共识规则和软分叉

共识规则决定着每个交易或每个区块的有效性。比特币网络上的每个用户和矿工都遵守着同一套共识规则,代表着他们都愿意接受和同意一个账本。

当大多数用户和/或矿工决定采用更严格的共识规则时,软分叉就可能出现,这使一些以前有效的交易/区块将变为无效,而不是相反。如果大多数人执行新的规则的话,其他任何违规分叉(统计上)都不会在工作量证明方面赶上新的更严格的共识分叉。遵守旧规则的少数人将始终遵循更长,更严格的分叉,使得网络上的每个人都会最终接受和同意一个账本。

关于分叉的更多知识,我觉得DPOS共识算法-by BM这篇文档讲得挺好的。

总结

共识算法的知识很多这里就不做更多地说明了。

参考和引用

拜占庭将军问题
实用拜占庭容错算法PBFT
区块链核心技术:拜占庭共识算法之PBFT
案例分析软分叉的艺术——政策规则保护
以太坊紫皮书(中文版)
[区块链]共识算法(POW,POS,DPOS,PBFT)介绍和心得
以太坊共识协议Casper原理是怎样的?
拜占庭容错(BFT)算法介绍
加密的钱包如何获得POS利息
深度教程:POS和POW全解析
盘点区块链共识机制——论PoW,PoS,DPos和DAG的优缺点对比分析
DAG也许是真正的区块链3.0
DPOS共识算法-by BM

0%