共识机制,从拜占庭将军问题到DPOS算法

区块链的核心价值就在于实现了去中心化的价值传输。那么区块链是如何做到这种价值传输的呢,很显然共识机制起到了决定性作用,今天我们就来深入讲解共识机制背后的原理及其发展。

人们对共识机制的研究其实由来已久,从上世纪70年代就开始了相关研究,其目的是为了解决分布式系统中的一致性问题。Fischer,Lynch和Patterson在1985年发表的论文中提出了可以说是最重要的分布式系统定理:FLP不可能定理(在异步通信场景,即使只有一个进程失败,也没有任何算法能保证非失败进程达到一致性);2000年,EricBrewer教授又进一步提出了CAP猜想:一致性、可用性和分区容错性三者无法在分布式系统中被同时满足,并且最多只能满足其中两个;2002年,Lynch与其他人证明了Brewer的猜想,从而把CAP上升为一个定理。这期间和之后,涌现了一些著名的分布式一致性算法,如LeslieLamport在1989年提出的Paxos算法,1999年Castro和Liskov提出的PBFT算法等。直到比特币采用POW进行记账后,共识算法才真正进入到了大众的视野里。

一般来说根据处理的异常情况不同,可以把共识算法分为两种类型,一种是针对非拜占庭错误的,这类算法性能较高,但容错性较差,如Paxos、Raft等;另一种是针对拜占庭错误的,这类算法往往容错性较高,但是性能相对较差,包括工作量证明(POW)、权益证明(POS)、委托权益证明(DPOS)、实用拜占庭容错算法(PBFT)等。处理拜占庭错误的算法有两种思路,一种是通过提高作恶成本以降低作恶节点出现的概率,如工作量证明、权益证明等,其中工作量证明是通过算力,而权益证明则是通过持有权益。另外一种是在允许一定的作恶节点存在的前提下,依然使得各节点之间达成共识,如实用拜占庭容错算法等。下面我们就来讲讲目前存在的主流共识算法。

拜占庭容错

1982年,Leslie Lamport等科学家提出了著名的拜占庭将军问题(Byzantine failures),其讨论的是允许存在少数节点作恶场景下的一致性达成问题。简单描述下:国土辽阔的拜占庭帝国,基于防御目的,将每支军队分别部署在全国各地。因为距离遥远,将军们只能靠信差传递消息。战争爆发时,拜占庭帝国军队的将军们必须全体一致的决定是否攻击某一支敌军,以获取作战胜利。然而将军们无法确定他们中是否存在叛徒,叛徒可能擅自变更进攻意向或者进攻时间,以破坏进攻的一致性,致使作战失败。在这种状态下,拜占庭将军们该商定一种怎样的远程沟通办法,以达到一致呢?

论文中指出,对于拜占庭问题来说,假如节点总数为N,叛变将军数为F,则当N≥3F+1时,问题才有解,由拜占庭容错算法BFT进行保证。简单说一下论证过程:假设节点总数为N,作恶节点总数为F,有效的善良节点数为L1,无效(发生故障)的善良节点数为L2;那么系统要安全的达成一致则必须满足2点:有效的善良节点超过作恶节点,同时也必须超过故障的善良节点。转化为数学公式则:L1≥F+1,L1≥L2+1(L2=F),又L1=N-L2-F,即N-F-F≥F+1,得出N≥3F+1;因此当叛变者不超过1/3时,存在有效的拜占庭容错算法。但BFT一直存在复杂度过高的问题,并没有真正落地到实际场景中。

Miguel Castro和Barbara Liskov在1999年提出了实用拜占庭容错算法PBFT(Practical Byzantine Fault Tolerance),以解决原始拜占庭容错算法效率不高的问题,将算法复杂度大为降低,使得拜占庭容错算法在实际系统应用中变得可行。PBFT是针对状态机副本复制为主的分布式系统执行环境开发的算法,旨在让系统中大部分的诚实节点来覆盖恶意节点或无效节点的行为。其运作步骤为:(1)随机取一个副本作为主节点,其他的副本作为备份;(2)用户端向主节点发送使用服务操作的请求;(3)主节点通过广播将请求发送给其他副本;(4)所有副本执行请求并将结果发回用户端;(5)用户端需要等待F+1个不同副本节点发回相同的结果,作为整个操作的最终结果。PBFT算法要求系统的失效节点数量不得超过全网节点的1/3,容错率相对较低。

PoW:工作量证明机制

比特币的区块链网络在设计时,针对PBFT中同时存在多个提案和最终一致性确认的问题进行了创造性的改进,提出并采用了PoW算法。通过消耗大量能源来计算一个满足条件的Hash值来获得记账权(发起提案),某个节点成功找到满足条件的Hash值之后,会马上对全网进行广播打包区块,网络中的节点收到区块后,会立刻对其进行验证。如果验证通过,则表明已经有节点成功记账,自己就不再竞争当前的区块,而是选择接受这个区块,记录到自己的账本中,然后进行下一个区块的竞争记账。同时记账节点会得到代币奖励,进而吸引更多节点参与竞争。假如节点有任何的作弊行为,都会导致验证不通过,并直接丢弃其打包的区块,作弊的节点不但得不到奖励,还损失了巨大挖矿成本。这样全网节点始终维护着拥有最大工作量的链,从而保证整个账本的相对一致性。

PoW算法简单来说就是算力越大,记账成功率越高(干的越多,获得越多)。其实现了完全去中心化,节点可以自由进出且实现简单。同时其容错性方面得到了提升,允许全网50%的节点出错,破坏系统需要投入极大的成本。它的缺点也很明显,首当其冲便是浪费能源,其次是共识效率低下,并且存在算力集中的风险。目前很难满足商业化应用的需求,典型项目如比特币。

PoS:权益证明机制

PoS也称股权证明机制,其诞生的初衷是为了解决PoW带来的能耗问题。这种模式下持有币的数量越多、时间越长,记账成功率就越高(持有越多,获得越多),类似于利息制度。举例来说,PoS算法中有一个名词叫币龄,每个币每天产生1币龄,如果你持有100个币,总共持有了30天,那么此时你的币龄就为3000。这个时候如果你发现了一个PoS区块,你的币龄就会被清空为0。你每被清空365币龄,你将会从区块中获得0.05个币的奖励(相当于年利率5%),在这个案例中,奖励=3000*5%/365=0.41个币,即持币有利息