共识算法,区块链的引擎

英国23日的脱欧公投以51.9%的赞成票获得通过。但是全民投票的结果是否就是社会的最大共识?24日结果出来后的一系列变化除了让人大跌眼镜,也让我们对共识有了更深的理解。

首先结果一出来后,就有不少投了脱欧的英国民众表示后悔了,理由千奇百怪:比如觉得留欧肯定是大多数,所以投了脱欧的奇葩逻辑;也有因为朋友投了“留”,所以自己就得“脱”的二货。但这些不负责任投票的实实在在的后果却由全体成员承担:英镑暴跌9.4%。

脱欧结果出来后,苏格兰和北爱均声称,将考虑脱离英国,以独立身份加入欧盟。事实上,苏格兰2014年9月已经举行过一次独立公投,但被英首相以苏格兰独立后很难加入欧盟的理由给拦了下来。(苏格兰人民心里苦)所以全体投票是否能正确反映组织中不同利益群体的诉求?处理不好的结果就是:分叉

因不满脱欧结果,英国民众发起请愿,要求再给一次机会,并指出公投投票率只有72%,太低,不作数,应该进行第二次公投。合理么?站在区块链从业者的角度看,相当合理! 在重大决策中,比如修宪,比如区块链的重大升级,显然需要保证足够的投票率,在此基础的投票结果,才具有合法性。

以比特币4天前刚完成的隔离见证的升级方案为例,事实上是要求所有算力中的95%达成一致后才会正式生效,这样高的阈值使得达成共识的过程非常漫长,但也因此,一旦方案获得通过,就有极大的合法性。

对于某些场景阈值太高未必是好事,需要权衡,否则会出现少数人绑架多数人的情况;同样对于一个极度分散的群体也不适用于这样的标准,很难想像一个百万人的群体能就哪怕一个简单问题达成如此高的一致性。

说到这里,赞一下以太坊的此次针对TheDAO时间的软分叉方案:支持软分叉的矿工运行的软件会缓慢降低gas上限,如果到180万个块的时候,gas上限小于400万,软分叉成功。这相当于一个实时的动态投票机制,和英国脱欧公投最大的不同在于,在长达6天的投票期间,你可以反悔!这可以避免跟风乱投票的情况,在结果生效之前有时间调整自己的行为,真实表达自己的意见。

(技术人员强答政治话题的画风如上。)

问题背景

投票是某个具体事务的共识,法律是社会共识的集合体,宪法更是带时间跨度的社会最大公约数。而在技术人员眼中,共识不仅是人的共识,还可以是机器的共识,程序的共识。而共识算法,则是算法设计者给分布式系统中的程序或者节点设计的宪法,保证当出现任何状况的时候,各自为政的程序之间能够协作一致,对外做出正确响应,并不至于陷入分裂的境地。

至于程序员设计的程序,为何会出现分裂,不一致的情况,这就要从网络说起了。

真实的物理世界就是一个分布式的系统,比如太阳和三体人所在星系的恒星比邻星同时发生了爆炸,对于地球人而言,因为太阳爆炸的光子首先到达地球,所以观测结果是太阳先爆炸,但是对于三体人而言,则是比邻星先爆炸;也就是说,因为观测点的差异,对于同一个事件,观测结果是完全相反的。

而网络中的程序面对的情况则更加复杂,设想下,如果光子的传播速度不是常量,每个光子的速度都不一样,我们即便知道了太阳和比邻星的相对位置和距离,也完全无法判断一个事件发生的先后顺序。

对于分布式系统而言,情况是类似的,一个事件发生后,受制于信息的传递速度,到达分布式节点的先后次序是不同的。困难不仅如此,如果一个事件在传递的过程中可能丢失呢?还有更糟糕的情况,节点接受到的信息是错的,伪造的,又该如何处理?如果节点已经陷入了混乱的状态,能否通过一系列的步骤,让这些节点重新步调一致?

问题的背景介绍完毕,以下开始介绍这个领域的一些研究成果。

理论基础

分布式系统的一致性算法是一个从上世纪70年代就开始研究的经典问题。在这个问题上,有两篇经典论文。一篇是《Impossibility of Distributed Consensuswith One Faulty Process》,由Fischer, Lynch 和 Patterson在1985年发表,论文中提出了可以说是最重要的分布式系统定理:FLP不可能性。

没有一个完全异步的共识协议可以容忍哪怕仅仅一个进程失效,即便没有拜占庭故障,即便消息系统足够可靠 - 所有的消息都可以被正确的送达刚好一次。


定义里有两个名词,异步和共识,我们分别解释:

首先是异步,这里的异步不同于通常技术术语中的异步调用的异步,而是指在一个分布式系统中,对消息的处理速度或者消息送达时间不做任何假设。

而共识则指互相独立的多个系统参与方(进程或者节点)间对某个问题达成一致的结果。引用 Pease,Shostak 和 Lamport 在论文《Reaching agreement in the presence of faults》中的定义:

容错系统通常要求提供一种手段,使得独立的处理器或者进程能够达成某种精确的相互一致。例如,一个冗余系统的多个处理器可能需要定期同步它们的内部时钟。或者每个处理器从某个时变的输入传感器读取的数值都有稍微不同,它们需要确定一个统一的值。


以汽车的ABS系统为例,汽车中有很多传感器,提供温度速度压力等信息。但是因为各自精度,测量条件不同,这些传感器的读数不可能一致,我们需要根据这些不同的数值达成一致,来决定给刹车施加多少压力,以提供最大的制动力。在这个问题中,每个传感器就是一个独立进程,各自独立提议了一些数值,算法要利用这些数值达到相互一致。

而在区块链中,共识则是在组成网络的分布式节点中达成。某个记账节点提议了一个区块应该包含哪些交易数据,然后把该区块广播给其他的参与节点,其他节点要就是否使用这个区块达成一致。

而异步共识,就是在这样的一个分布式系统中,一个消息发出后,发送方无法预期什么时候能够收到回应。带着这样的前提,系统的参与方如何就一个问题的取值达成一致。

在FLP定理中,我们假设了异步网络是可靠的, 即消息有延迟,但是所有的消息都会被且仅会被投递一次, 这是一个很强的假设, 现实中,很少有网络能达到这样的可靠性。 而且FLP也不要求所有非故障节点都达成一致, 只要有一个节点进入确定状态就算达成一致了, 并且需要达成的结果取值范围是{0, 1}, 加上前面提到的最多只有一个节点发生故障, 然而即便是这样的接近理想的情况,FLP定理还是指出了,不存在一个一致性算法能够保证节点达成共识,更不用说真实世界中存在的网络分区以及拜占庭节点了.

FLP定理限定了我们对分布式系统共识算法求解的上限,既然不存在完美解,那么退而求其次,是否能够放松要求,在这个不完美的世界获得一个够用的一致性呢?从NASA到Google,这样的需求一直存在。

实际应用

Leslie Lampor在1989年提出的Paxos就是这样一个被用于异步网络的具有容错能力的共识算法,广泛应用在Chubby这样的分布式系统中。Paxos算法在保证safety的同时放松了liveness,允许出现无限循环而无法达成一致,也就是使用Paxos共识算法的分布式系统有很小的概率出现系统不可用的状况。

计算机科学首先是应用科学,不追求绝对的正确,只要从概率角度足够低,工程上就可以采用。比如哈希函数,虽然存在一定的碰撞概率,但因为这个概率足够低,所以我们在设计系统的时候,就可以不考虑碰撞发生的情况。本能反应上,大多数人都觉得这样的方案不可接受,因为人缺少对“小概率事件”的直观感受。

举例来说,能够造成恐龙灭绝这样的小行星撞击地球事件平均3000万年一次,折算一下,下一秒你死于行星撞击的概率是10^-15。而现在给你全球所有的比特币矿机,用于寻找一个sha256的碰撞结果,你在一秒内找到的概率大概是10^-59,也就是说,你需要1050年才可能找到一个碰撞,这已经超出了宇宙的年龄。所以我们在区块链中广泛的使用哈希函数而不担心碰撞。

不过Paxos的容错不是拜占庭容错。拜占庭错误是指系统中的节点可能出现任何错误,包括有意的误导,故意破坏系统,当然也包括超时,重复发送消息,伪造签名等。拜占庭的提法是从经典的拜占庭将军问题而来,有兴趣的可以搜索相关资料。

但是在联盟链中,系统中的节点可能是利益对立方,节点完全有动机在一些不利于自己的情况下尝试作恶,破坏系统的一致性。因此,联盟链的共识算法必须要能够容忍拜占庭节点,不能使用Paxos这样的非BFT算法。

1999年Castro和Liskov提出的PBFT是第一个得到广泛应用的BFT算法,在PBFT算法中,至多可以容忍不超过系统全部节点数量的1/3的拜占庭节点,即如果有超过2/3的正常节点,整个系统就可以正常工作。

因为非常适合联盟链的应用场景,PBFT及其改进算法因此成为目前被使用最多的联盟链共识算法。改进主要集中在,修改底层网络拓扑的要求,使用p2p网络;可以动态的调整节点数量;减少协议使用的消息数量等。

不过PBFT仍然是依靠法定多数(quorum),一个节点一票,少数服从多数的方式,实现了拜占庭容错。对于联盟链而言,这个前提没问题,甚至于是优点所在。但是在公有链中,就有很大的问题。

比特币这样的公有链,是一个匿名系统,任何人都可以加入到网络中,竞争记账权。也就是说,系统中对加入的节点没有要求,也没有任何验证,如果是采用一个节点一票的方式,很容易遭受所谓女巫攻击(Sybil Attack):攻击者批量制造大量的节点加入系统,通过绝对多数的投票权发起攻击,对于一个节点而言,无从辨别其他节点是普通节点还是拜占庭节点,也可能其他节点就是普通节点,只是在一些有利益影响的事情上表现出拜占庭行为。所以基于IP或者CPU的投票制度在公有链上不能发挥应用的作用,因为这些不是稀缺资源,尤其是存在“僵尸网络”的情况下。

FLP定理堵死了我们在传统计算机算法体系下提出解决方案的可能性。

峰回路转

既然传统思路走不同,突破只能来自体系之外,中本聪说:“要有经济激励”,于是token被引入了共识;“还要有博弈”,于是奖励和惩罚机制也被创造出来。

首先我们假定节点背后的人都是经济理性人,不会做成本高于收益的事情。之所以拜占庭节点不遵守协议约定,无非是因为不遵守协议的利益更大,如果我们能够设计一种博弈机制,让遵守约定的行为的收益高于违反约定的收益,那么基于经济理性人假设,节点就不会表现出拜占庭行为,使得在公有链上,即便没有对加入节点的审查和监控,算法也可以认为没有拜占庭节点,简化了协议设计。

这就是比特币的工作量证明(PoW)算法。PoW算法中,要求记账节点花费一定的资源做一些计算,然后向网络其他节点提交计算的工作量证明,证明需要能够被快速验证,并且工作量要容易度量,然后我们根据工作量来分配记账权。

因为工作量证明无法伪造,有很高的成本,只有遵守协议约定,才能够收回成本,获得收益。

有没有缺点?

有。

第一个缺点是代价太高。比特币的挖矿已经是一个完整的产业,从芯片研发生产,到矿机矿场矿池,以及期货等相关的风险对冲的金融产品,每一个环节都是巨大的投入。目前比特币的主流芯片制程为28nm,最新制程已到16nm,一款芯片的前期投入上亿人民币,比特币所有矿机的总功耗估计已经超过200兆瓦,每年电费成本预计超10亿人民币。矿工是比特币的守护神,高昂的沉没成本,激励的竞争也让比特币更加安全,但面对无止境的军备升级很难说什么时候是个尽头。可以辩解说这些资源消耗是必要的代价,是比特币价格的基石,但代价高也是毋庸置疑的事实,是否有更好的方案可以在不降低安全性的前提下降低资源消耗?或者把资源消耗在更有意义的计算上,而不是白白浪费。

PoW的第二个缺点是缺乏确定性(Finality)。确定性是指:操作一旦完成,就永远完成了,系统永不可能再回退回去撤销这个操作。

从技术的观点看,工作量证明区块链上的交易永远也不会最终确定。对于任何一个区块,随时都存在着冒出一条更长的始于它的父块又不包含它的分叉的可能。当然在现实中,公有链上的金融服务已经演化出了一种非常实用的方法来判断一个交易是否足够近似确定:等6个确认。

这里的概率计算很简单:如果攻击者拥有的算力不到25%,我们便可以用随机漫步来描述双花攻击,随机漫步从-6开始(意味着攻击者的链比原来的链短了6个区块)。通过公式(0.25 / 0.75)^6 ~= 0.00137,我们可以计算出这个随机过程达到0的概率。如果你想要更高的确定性,可以等待13个确认让攻击者只有百万分之一的成功机会,或者等待162个确认使得攻击者的机会比直接猜出你的私钥还低。因此,即使在基于工作量证明的区块链上也存在一定程度的确定性。

但这里获得的确定性有个前提,不存在经济利益之外的其他动机。PoW提供的确定性不能避免非经济理性攻击行为的可能:投入巨量的金钱制造出比全网更高的算力进行简单碾压。

PoW的第三个缺点是出块间隔时间的不确定。比特币的10分钟出块间隔只是一个平均值,而不是一个恒定值,这也意味着,交易被提交给网络之后,下一个包含该笔交易的区块什么时候被挖出来,完全取决于运气。比如历史上,块#152217和块#152218之间的出块间隔为1小时39分钟7秒,也有几十个块的出块间隔少于1秒。这样的不确定性,会影响到最终用户的使用体验。

比特币在PoW中引入的经济激励和博弈机制给了社区非常大的启发。

挖矿的本质是让作恶的成本高于收益,如果一种机制,能够达到类似的效果,也能起到同样的作用。工作量证明只是手段,而非目的。

Proof of Stake由Quantum Mechanic 2011年在bitcointalk首先提出,后经Peercoin和NXT以不同思路实现。详细的工作原理不在这里描述,简单说就是用户持有系统的代币数量影响/决定打包出块的概率。PoS中的代币类似于公司的股权,大股东对系统有更大的发言权,有更多的责任,也有获得更多收益的权力。

PoW协议中,能够发起攻击的计算资源在比特币的体系之外,而在PoS中,若想攻击,必须要从系统中购买代币才能发起攻击,因此有人认为PoS更加安全。不过PoS最想解决的问题还是比特币的能源消耗,希望实现一个环保节能的共识协议。因为不是工作量证明,而是股权证明,所以PoS协议中,不需要专用的矿机,用户使用普通的钱包在个人电脑上就可以,挖矿的多少和持币多少有关,和算力无关。所以和PoW相比,PoS要省电得多。

除了PoS之外,BitShares社区还提出了一种新的协议:DPOS。如果说PoS是一币一票的直选制度,那么DPoS则是代议制,间接民主。BitShares的账本是由101个受托人轮流写入,而这101个受托人由BitShares的代币持有人一币一票的选举上去的。这101个受托人可以获得“工资”收入:区块的打包费奖励。

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

无论是Paxos, 还是PoW,抑或PoS, Casper, 引入算法是为了保证系统能够消除恶意行为,让分布式系统的各个节点能够达成一致,确保系统上承载的业务数据的安全。

比特币的系统中,矿工的权力很小,手握算力要发起攻击,可行的做法是构造一次双花攻击。如果比特币上一笔交易承载的价值小于双花攻击的成本,那么我们就可以认为这笔交易是安全的。因此,对于公有链而言,区块链的安全性可以由双花的攻击成本来衡量。假如比特币目前全网算力的硬件成本是10亿美元,那么双花攻击成本最高就是10亿美元。当然真正需要实施双花攻击,通常不会傻到从零开始部署这么高的算力。经济的办法是,攻击者可以贿赂矿工都选择攻击者的链,更实际的贿赂方式是运行一个负费率的矿池,或者名义上零费率另外补贴收益率来避免招人怀疑。攻击者还可以尝试黑进矿池或者破坏矿池基础设施,因为PoW矿池的安全保护缺少激励,实施成功的概率不小(如果矿工被黑,他们只会损失一段时间内的奖励,本金是安全的)。因此,实际的双花攻击成本要远远低于10亿美元。

双花存在的可能性影响到区块链的确定性。

Casper尝试提供比工作量证明更高的确定性保证。首先Casper对“经济上完全确定”(total economic finality)有标准定义:当大于等于2/3的验证人以最大概率投注一个区块或者说状态会最终确定的时候。在这个定义下验证人有非常强的激励不去合谋推翻这个区块:一旦验证人作出了最大概率的投注,在任何一个不包含这个区块的分叉中验证人都会失去他们全部的保证金。你可以把Casper想象成一个参与51%的攻击会导致你的矿机被烧毁的工作量证明变种。

其次,由于成为验证人需要事先申请,这意味着不可能存在另外的验证人在悄悄的制造另一条更长的链。如果你看到2/3的验证人将他们的全部本钱压倒了某个块上,然后又发现有2/3的验证人对另一个矛盾的块做了相同的事,那么这只能说明这两组验证人的交集(即至少1/3的验证人)将失去他们的全部保证金。这便是所谓的“经济上的确定性”:我们无法保证“X永远不会被撤销”,但我们可以保证的是一个稍弱的说法,“X要么永远不被撤销,要么有一大群验证人自愿的销毁他们自己价值数百万美元的本金”。

最后,即使双重确定(double-finality)的事件真的发生了,用户也无需被迫接受有更多投注支持的分叉。相反,用户可以自行决定追随哪个分叉,一个完全可行的简单策略是接受“先来的那个”。Casper中的一次成功攻击更像是一次硬分叉而不是回退,而持有链上资产的用户社区可以自由的基于常识选择那条不是攻击者制造的,而是包含真正应该被确定的交易的分叉。

永不止步

区块链是台信任机器,而共识算法则是驱动这台机器运转的发动机。这台信任机器的性能和结构是由发动机决定的。

而什么是好的共识?这个问题没有标准答案,因为不同场景有不同的需求,4个轮子的汽车上安装喷气发动机可能是个糟糕的想法。但是在特定场景下,哪个方案更好则是有统一的评判标准的。

在Cyptape重点研究的联盟链场景中,对拜占庭节点的容错能力以及共识成本是最重要的指标。

什么是容错能力?举例来说,在一个节点说了算的场景中(没错,独裁也是一种共识,一切以独裁节点的结果为准,他还有个名字Proof of Authority),如果刚好这个独裁节点出了问题,那么整个系统就崩溃了,所以PoA的共识的容错能力为0。

而在PBFT算法中,只要系统中的坏人少于1/3,系统就不会出问题。但是如果超过1/3,系统就不能正常工作,也就是说,一个提案即便获得过半多数的支持,仍然可能无法获得通过, 似乎不太符合我们日常的生活经验。

一个只有两个节点的系统中,不存在拜占庭节点的说法:没有参照系,谁都可能是真理。但三个节点的系统就有应用共识算法的需求了,然而PBFT的算法却要求系统中至少有4个节点,也就是说,三个节点的系统目前没有共识算法可用!不合理!

共识是有成本的,就像民主投票一样,需要经过一轮又一轮的磋商,交换意见最后达成一致。如何降低民主的成本,如何用最少的磋商次数,最小的沟通成本达成共识是算法追求的目标,也是决定区块链这台机器是否跑得足够快的重要因素。

正如汽车发动机一样,时至今日,市面上的汽车发动机大同小异,能在漫长的淘汰赛中存活下来的这些发动机,虽各有所长,但结构高度类似。不过如果纵观历史,就会发现,今天的发动机和它的祖辈们性能上已是天壤之别,进化从未止步!

想要在区块链方程式大赛上脱颖而出,共识算法是个中关键。我们在对现有算法做了充分研究之后,惊喜的发现这个古老而又年轻的领域依然有太多可能。为了能在这个赛场上一骑绝尘,我们潜心打造了拥有Cryptape烙印的全新核心引擎。