区块链共识算法中的共识机制：一致性与正确性

比特币的本质是一个分布式去中心化的数字货币,其愿景是该系统不会被任何国家的央行或者机构所控制。但是一个分布式系统,要想步调一致地完成工作任务,就一定要先解决分布式计算问题。

首先,一致性问题。在分布式系统中,一致性(Consistency,早期也称为Agreement)是指对于系统中的多个服务节点,给定一系列操作,在协议(往往通过某种共识算法)保障下,试图使它们对处理结果达成某种程度的一致。

如果分布式系统能实现“一致性”,那么对外就可以呈现出一个功能正常,而且性能和稳定性都要好很多的“虚拟处理系统”。

举个例子,某个电影公司旗下有西单和中关村的两个电影院,都出售某电影票,票一共只有一万张。那么,顾客到达某个电影院买票的时候,售票员该怎么决策是否该卖这张票,才能避免超售呢?当电影院个数更多的时候呢?

这个问题在人类社会中,看起来似乎没那么难,英国人不就是通过靠投票达成了“脱欧的一致性”吗?但好像很多人又不太认可这样的投票结果,导致在脱欧的具体细节上议会分歧很大。但如果是由机器来进行投票的话,那么如果结果一旦得出,就应该无条件服从才可以,这些都是由共识算法决定的。可能相对于机器来说,人类会更多地受情感因素影响,在某种情况下,机器会更加理性。

这里需要强调的是,一致性并不代表结果正确与否,而是系统对外呈现的状态一致与否,例如,所有节点都达成失败状态也是一种一致。

在分布式计算领域,一致性问题是最核心的问题。

“中本聪”的发明也是对之前未解决的分布式计算问题(“拜占庭将军问题”)的一个实用解决方案。其问题在于如何在一个不可靠且存在背叛风险的网络中进行信息和价值的交换,并最终达成“共识”。这里的共识是指数据层面的共识,只要最终网络中的参与方对数据能够做到完全一致,即做到了在数据层面“达成共识”,而对于共识的正确性与否不做判断。比特币利用所谓的工作量证明(Proof Of Work,POW)来达成共识是一种重大的创新和突破,它使原有的分布式计算网络能够适用到更广泛的领域,而不是简简单单地在计算领域。比特币可以在去中心化的网络里达成共识并完成转账、支付等交易,这鼓励了人们将从分布式计算衍生出来的分布式账本技术(Distributed Ledger Technology,DLT)应用到选举、博彩、资产登记、资产流转、数据公证等其他各种场景当中。

那么什么是“拜占庭将军问题”呢?

拜占庭将军问题是Leslie Lamport(2013年的图灵奖得主)用来为描述分布式系统一致性问题(Distributed Consensus)时在论文中抽象出来的一个著名例子。这个例子大意是这样的:

拜占庭帝国想要进攻一个强大的敌人,为此派出了10支军队去包围这个敌人。这个敌人虽不比拜占庭帝国,但也足以抵御5支常规拜占庭军队的同时袭击。他们任一支军队单独进攻都毫无胜算,除非有至少6支军队(一半以上)同时袭击才能攻下敌国。他们分散在敌国的四周,依靠通信兵骑马相互通信来协商进攻意向及进攻时间。困扰这些将军的问题是,他们不确定他们中是否有叛徒,叛徒可能擅自变更进攻意向或者进攻时间。由于10位将军都是战功赫赫,所以谁当总指挥都会有人不服从。谁都觉得自己的作战时间是最好的选择。而且,将军们中间,谁也没办法保证是否有将军已经叛国通敌了,所以也不敢随意去听从其他将军的命令。

在这种状态下,拜占庭将军们怎样才能保证有多于6支军队在同一时间一起发起进攻,从而赢取战斗?

除此之外,最关键的问题在于将军们之间距离很远,他们无法坐到一起开会讨论,因为一旦走出了军营,就有可能被叛军或者敌军谋害。而他们所拥有的唯一沟通手段就是通过通信兵来传递各自的信息,从而达到与其他将军之间沟通的目的。在这种情况下,这些将军怎么通过通信兵传递信息,最后达成共识一起行动的问题,就被称为“拜占庭将军问题”

(注:拜占庭将军问题中并不去考虑通信兵是否会被截获或无法传达信息等问题,即消息传递的信道绝无问题。Lamport已经证明了在消息可能丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。所以,在研究拜占庭将军问题的时候,已经假定了信道是没有问题的。)

拜占庭假设是对现实世界的模型化,由于硬件错误、网络拥塞或断开以及遭到恶意攻击,计算机和网络可能出现不可预料的行为。拜占庭容错协议必须处理这些失效,并且这些协议还要满足所要解决的问题要求的规范。这些算法通常以其弹性t作为特征,t表示算法可以应付的错误进程数。

拜占庭将军问题是分布式共识的基础,其必须有两个交互性的条件,即一致性和正确性。由于大多数情况下,正确性涉及人的主观价值判断,很难施加到分布式节点上,因此一般共识算法采用的是“降级的正确性”(Degraded correctness),即从“表达的内容是正确的”降级为“正确地表达”,这就导致区块链的拜占庭共识实际上是一种机器共识,其本身等价于分布式一致性+ 正确表达(不篡改消息)。与之相对的是决策共识,可以认为是人的共识,不仅要求一致性,而且要求所有节点相信“表达的内容是正确的”,因而决策共识不仅要求内容的客观一致性,而且还要求其在共识节点间的主观正确性。由此可见,算法共识处理的是客观的二值共识,即对(唯一正确的账本)和错(所有错误的账本),而决策共识处理的是主观的多值共识,即意见1(及其所属群体)、意见2(及其所属群体)、……、意见N(及其所属群体),各节点最终通过群体间的协调和协作过程收敛到唯一意见(共识),而此过程可能失败(不收敛)。因此,最早在《经济学人》杂志上刊登的文章称为“机器的信任”,其更多的是指机器与机器之间的信任,而不是指机器与人之间的信任。

早期的共识算法一般也称为分布式一致性算法。与目前主流的区块链共识算法相比,分布式一致性算法主要面向分布式数据库操作,且大多不考虑拜占庭容错问题,即假设系统节点只发生宕机和网络故障等非人为问题,而不考虑恶意节点篡改数据等问题。1988年,麻省理工学院的布莱恩·奥奇(Brian M.Oki)和芭芭拉·里斯科夫(Barbara H.Liskov,著名计算机专家、2008年图灵奖得主)提出了VR 一致性算法,采用主机-备份(Primary-Backup)模式,规定所有数据操作都必须通过主机进行,然后复制到各备份机器以保证一致性。1989年,莱斯利·兰伯特(Leslie Lamport)在工作论文“The part-time parliament”中提出Paxos算法,由于文章采用了讲故事的叙事风格且内容过于艰深晦涩,直到1998年才通过评审、发表在ACM transactions on computer systems期刊上。Paxos是基于消息传递的一致性算法,主要解决分布式系统如何就某个特定值达成一致的问题。随着分布式共识研究的深入,Paxos算法获得了学术界和工业界的广泛认可,并衍生出Abstract paxos,Classic paxos,Byzantine paxos和Disk paxos等变种算法,成为解决异步系统共识问题最重要的算法家族。实际上,Liskove等人提出的VR 算法本质上也是一类Paxos算法。需要说明的是,VR 和Paxos算法均假设系统中不存在拜占庭故障节点,因而是非拜占庭容错的共识算法。除以上共识算法外,获得较多研究关注的早期共识算法还有两阶段提交(Two-phase commit)算法、三阶段提交(Three-phase commit)算法、Zab、Zyzzyva、Kafka等各种一致性算法。

在“中本聪”看来,任何共识的达成都是要付出代价的,在所有的将军地位平等的情况下,不可能你说了,别人就都来听你了,无组织的低成本沟通最后的结果就是谁说的话都不会成为共识。

那么如何使将军能够达成所谓的“共识”呢。“中本聪”的方法是通过大家来争夺话语权的方式来达到脱颖而出,从而在一个周期内所有人服从具有话语权的一方。比如大家围成一圈,在10分钟之内,谁做的俯卧撑最多、谁吃的包子最多等,都算作一种所谓的“工作量”。在大家的鉴证下,10分钟之内,谁做得“工作量”最多,就听谁的。而在比特币当中,是让“将军”们做数学题,10分钟之内,谁做得最快最好,就由谁来当Leader,Leader把自己的命令发送给其他的将军,如:“凌晨5点,发起总攻,代码0501”,那么其他“将军”在收到这条信息后,会对信息的真伪进行验证,验证通过后就把自己的指纹签名信息带上并转发给所有其他将军。最后,大家都会拿到一张带有超过半数的将军指纹签名的信息,并对结果达成共识。(www.xing528.com)

可是为什么大家要验证Leader的计算结果并签名呢?这是因为事成之后,所有签过名的将军会瓜分城池内的所有财富,这就是比特币设计中的奖励机制。

这里面还有一个问题,就是怎么证明一条传过来的电报真的是出自某位将军的手笔呢?这就是指纹的作用,指纹是每个人的唯一标识,别人都无法伪造,也就防止别有用心的人伪造其他将军的手笔了。

就这样,在“中本聪”给出的方案下,通过签名机制保证了信息的真实归属;通过工作量机制,降低了无效的交流,选举出了一定周期内的意见领袖,同时发消息的人需要很大的代价来争夺话语权,也降低了叛徒发无效意见的概率;通过奖励机制,保证了大家都愿意参与到决策过程中,并把决策传给下一个人。困惑了计算机界30年的拜占庭问题,被解决了。

计算机科学领域的早期共识研究一般聚焦于分布式一致性,即如何保证分布式系统集群中所有节点的数据完全相同并且能够对某个提案达成一致的问题,是分布式计算的根本问题之一。虽然共识(Consensus)和一致性(Consistency)在很多文献和应用场景中被认为是近似等价和可互换使用的,但两者的含义存在着细微的差别:共识研究侧重于分布式节点达成一致的过程及其算法,而一致性研究则侧重于节点共识过程最终达成的稳定状态;此外,传统分布式一致性研究大多不考虑拜占庭容错问题,即假设不存在恶意篡改和伪造数据的拜占庭节点,因此在很长一段时间里,传统分布式一致性算法的应用场景大多是节点数量有限且相对可信的分布式数据库环境。与之相比,区块链系统的共识算法则必须运行于更为复杂、开放和缺乏信任的互联网环境下,节点数量更多且可能存在恶意拜占庭节点。因此,即使像各种基于Paxos的分布式一致性算法早在20世纪80年代就已经提出,但是如何跨越拜占庭容错这道鸿沟、设计简便易行的分布式共识算法,仍然是分布式计算领域的难题之一。

另外,在针对区块链技术的具体应用中,共识算法还被分类成两个部分,第一部分称为算法共识,第二部分称为决策共识。

算法共识主要指针对某一种应用场景所选用的计算方式。如:POW 算法中所采用的哈希算法等具体计算方法(比特币与以太坊所采用的哈希算法是不一样的)。

而决策共识主要包括如何选取共识节点、验证节点的轮换或者随机抽取,甚至有结合业务的情况根据所持有的代币多少来进行选取验证节点的方式。如:EOS就根据所持有的代币来竞选超级节点,并由超级节点作为共识的验证节点。

算法共识更贴近于经典的共识模型和理论,决策共识往往会更贴近于应用场景,强调节点之间的博弈与协作。

中国科学院自动化研究所,青岛智能产业技术研究院平行区块链技术创新中心团队在 《共识简史——区块链发展历程中的共识算法》一文中详细介绍了主流区块链共识算法,引述如下。

1993年,美国计算机科学家、哈佛大学教授辛西娅·德沃克(Cynthia Dwork)首次提出了工作量证明思想,用来解决垃圾邮件问题。该机制要求邮件发送者必须算出某个数学难题的答案来证明其确实执行了一定程度的计算工作,从而提高垃圾邮件发送者的成本。1997年,英国密码学家亚当·伯克(Adam Back)也独立地提出,并于2002年正式发表了用于哈希现金(Hash cash)的工作量证明机制。哈希现金也是致力于解决垃圾邮件问题,其数学难题是寻找包含邮件接受者地址和当前日期在内的特定数据的SHA-1哈希值,使其至少包含20个前导零。1999年,马库斯·雅各布松(Markus Jakobsson)正式提出了“工作量证明”概念。这些工作为后来“中本聪”设计比特币的共识机制奠定了基础。

1999年,Barbara Liskov 等提出了实用拜占庭容错算法(Practical Byzantine fault tolerance,PBFT),解决了原始拜占庭容错算法效率不高的问题,将算法复杂度由指数级降低到多项式级,使得拜占庭容错算法在实际系统应用中变得可行。PBFT 实际上是Paxos算法的变种,通过改进Paxos算法使其可以处理拜占庭错误,因而也称为Byzantine paxos算法,可以在保证活性(Liveness)和安全性(Safety)的前提下提供(n-1)/3 的容错性,其中n为节点总数。

2000年,加利福尼亚大学的埃里克·布鲁尔(Eric Brewer)教授在ACM symposium on principles of distributed computing研讨会的特邀报告中提出了一个猜想:分布式系统无法同时满足一致性(Consistency)、可用性(Availability)和分区容错性(Partition tolerance),最多只能同时满足其中两个。其中,一致性是指分布式系统中的所有数据备份在同一时刻保持同样的值;可用性是指集群中部分节点出现故障时,集群整体是否还能处理客户端的更新请求,分区容忍性则是指是否允许数据分区,不同分区的集群节点之间无法互相通信。2002年,塞斯·吉尔伯特(Seth Gilbert)和南希·林奇(Nancy Lynch)在异步网络模型中证明了这个猜想,使其成为CAP定理或布鲁尔定理。该定理使得分布式网络研究者不再追求同时满足三个特性的完美设计,而是不得不在其中做出取舍,这也为后来的区块链体系结构设计带来了影响和限制。

2008年10月,“中本聪”发表的比特币创世论文催生了基于区块链的共识算法研究。前文所提到的传统分布式一致性算法大多应用于相对可信的联盟链和私有链,而面向比特币、以太坊等公有链环境则诞生了PoW、PoS等一系列新的拜占庭容错类共识算法。

比特币采用了PoW 共识算法来保证比特币网络分布式记账的一致性,这也是最早和迄今为止最安全可靠的公有链共识算法。PoW 的核心思想是通过分布式节点的算力竞争来保证数据的一致性和共识的安全性,比特币系统的各节点(即矿工)基于各自的计算机算力相互竞争来共同解决一个求解复杂但是验证容易的SHA256数学难题(即挖矿),最快解决该难题的节点将获得下一区块的记账权和系统自动生成的比特币奖励。Po W 共识在比特币中的应用具有重要意义,其近乎完美地整合了比特币系统的货币发行、流通和市场交换等功能,并保障了系统的安全性和去中心性。然而,PoW 共识同时存在着显著的缺陷,其强大算力造成的资源浪费(主要是电力消耗)历来为人们所诟病,而且长达10分钟的交易确认时间使其相对不适合小额交易的商业应用。

2011年7月,一位名为Quantum Mechanic的数字货币爱好者在比特币论坛(www.bitcointalk.org)首次提出了权益证明PoS 共识算法。随后,Sunny King在2012年8月发布的点点币(Peercoin,PPC)中首次实现。PoS由系统中具有最高权益而非最高算力的节点获得记账权,其中权益体现为节点对特定数量货币的所有权,称为币龄或币天数(Coin days)。PPC 将PoW 和PoS两种共识算法结合起来,初期采用PoW 挖矿方式以使得Token相对公平地分配给矿工,后期随着挖矿难度的增加,系统将主要PoS共识算法维护。PoS一定程度上解决了Po W 算力浪费的问题,并能够缩短达成共识的时间。因而比特币之后的许多竞争币都采用PoS共识算法。

2013年2月,以太坊创始人Vitalik Buterin在比特币杂志网站详细地介绍了Ripple(瑞波币)及其共识过程的思路。Ripple项目实际上早于比特币,2004年就由瑞安·福格尔(Ryan Fugger)实现,其初衷是创造一种能够有效支持个人和社区发行自己货币的去中心化货币系统。2014年,大卫·施瓦尔茨(David Schwartz)等提出了瑞波协议共识算(Ripple Protocol Consensus Algorithm,RPCA),该共识算法解决了异步网络节点通信时的高延迟问题,通过使用集体信任的子网络(Collectively-trusted subnetworks),在只需最小化信任和最小连通性的网络环境中实现了低延迟、高鲁棒性的拜占庭容错共识算法。目前,Ripple已经发展为基于区块链技术的全球金融结算网络。

2013年8月,比特股(Bitshares)项目提出了一种新的共识算法,即授权股份证明算法(Delegated Proof-of-Stake,DPoS)。DPoS共识的基本思路类似于“董事会决策”,即系统中每个节点可以将其持有的股份权益作为选票授予一个代表,获得票数最多且愿意成为代表的前N 个节点将进入“董事会”,按照既定的时间表轮流对交易进行打包结算、并且签署(即生产)新区块。如果说Po W 和PoS共识分别是“算力为王”和“权益为王”的记账方式的话,DPoS则可以认为是“民主集中式”的记账方式,其不仅能够很好地解决PoW 浪费能源和联合挖矿对系统的去中心化构成威胁的问题,也能够弥补PoS中拥有记账权益的参与者未必希望参与记账的缺点,其设计者认为DPoS是当时最快速、最高效、最去中心化和最灵活的共识算法。

2013年,斯坦福大学的迭戈·翁伽罗(Diego Ongaro)和约翰·奥斯特豪特(John Ousterhout)提出了Raft共识算法。正如其论文标题 《In search of an understandable consensus algorithm》所述,Raft的初衷是为设计一种比Paxos更易于理解和实现的共识算法。要知道,由于Paxos论文极少有人理解,Lamport于2001年曾专门写过一篇文章 《Paxos made simple》,试图简化描述Paxos算法但效果不好,这也直接导致了Raft的提出。目前,Raft已经在多个主流的开源语言中得以实现。