共识算法

区块链架构是一种分布式的架构。其部署模式有

公共链 中心化分布式系统
联盟链 部分去中心化分布式系统
私有链 弱中心分布式系统

在分布式系统中,多个主机通过异步通信方式组成网络集群。在这样的一个异步系统中,需要主机之间进行状态复制,以保证每个主机达成一致的状态共识。然而,异步系统中,可能出现无法通信的故障主机,而主机的性能可能下降,网络可能拥塞,这些可能导致错误信息在系统内传播。因此需要在默认不可靠的异步网络中定义容错协议,以确保各主机达成安全可靠的状态共识。

所谓共识,简单理解就是指大家都达成一致的意思。其实在现实生活中,有很多需要达成共识的场景,比如开会讨论,双方或多方签订一份合作协议等。而在区块链系统中,每个节点必须要做的事情就是让自己的账本跟其他节点的账本保持一致。如果是在传统的软件结构中,这几乎就不是问题,因为有一个中心服务器存在,也就是所谓的主库,其他的从库向主库看齐就行了。在实际生活中,很多事情人们也都是按照这种思路来的,比如企业老板发布一个通知,员工照着做。但是区块链是一个分布式的对等网络结构,在这个结构中没有哪个节点是“老大”,一切都要商量着来。

所以在区块链系统中,如何让每个节点通过一个规则将各自的数据保持一致是一个很核心的问题,这个问题的解决方案就是制定一套共识算法,实现不同账本节点上的账本数据的一致性和正确性。这就需要借鉴已有的在分布式系统中实现状态共识的算法,确定网络中选择记账节点的机制,以及如何保障账本数据在全网中形成正确、一致的共识。

共识算法其实就是一个规则,每个节点都按照这个规则去确认各自的数据。我们暂且抛开算法的原理,先来想一想在生活中我们会如何解决这样一个问题:假设一群人开会,这群人中没有一个领导或者说老大,大家各抒己见,那么最后如何统一出一个决定出来呢?实际处理的时候,我们一般会在某一个时间段中选出一个人,那个人负责汇总大家的内容,然后发布完整的意见,其他人投票表决,每个人都有机会来做汇总发表,最后谁的支持者多就以谁的最终意见为准。这种思路其实就算是一种共识算法了。然而在实际过程中,如果人数不多并且数量是确定的,还好处理;如果人数很多且数量也不固定,那就很难通过这种方式投票决定了,效率太低。我们需要通过一种机制筛选出最有代表性的人,在共识算法中就是筛选出具有代表性的节点。

那如何筛选呢?其实就是设置一组条件,就像筛选尖子生一样,给一组指标让大家来完成,谁能更好地完成指标,谁就能有机会被选上。在区块链系统中,存在着多种这样的筛选方案,比如PBFT(Practical Byzantine Fault Tolerance,实用拜占庭容错算法)、PoW(Proof of Work,工作量证明)、PoS(Proof of Stake,权益证明)、DPoS(Delegate Proof of Stake,委托权益证明)、Ripple(瑞波)等,各种不同的算法,其实就是不同的游戏玩法。

一.拜占庭容错技术(Byzantine Fault Tolerance,BFT)

拜占庭容错技术(Byzantine Fault Tolerance,BFT)是一类分布式计算领域的容错技术。拜占庭假设是对现实世界的模型化,由于硬件错误、网络拥塞或中断以及遭到恶意攻击等原因,计算机和网络可能出现不可预料的行为。拜占庭容错技术被设计用来处理这些异常行为,并满足所要解决的问题的规范要求。

在分布式系统中,特别是在区块链网络环境中,也和拜占庭将军的环境类似,有运行正常的服务器(类似忠诚的拜占庭将军),有故障的服务器,还有破坏者的服务器(类似叛变的拜占庭将军)。共识算法的核心是在正常的节点间形成对网络状态的共识。

通常,这些发生故障节点被称为拜占庭节点,而正常的节点即为非拜占庭节点。

拜占庭容错系统是一个拥有n台节点的系统,整个系统对于每一个请求,满足以下条件:

  1. 所有非拜占庭节点使用相同的输入信息,产生同样的结果;
  2. 如果输入的信息正确,那么所有非拜占庭节点必须接收这个信息,并计算相应的结果。

拜占庭系统普遍采用的假设条件包括:

  1. 拜占庭节点的行为可以是任意的,拜占庭节点之间可以共谋;
  2. 节点之间的错误是不相关的;
  3. 节点之间通过异步网络连接,网络中的消息可能丢失、乱序并延时到达,但大部分协议假设消息在有限的时间里能传达到目的地;
  4. 服务器之间传递的信息,第三方可以嗅探到,但是不能篡改、伪造信息的内容和验证信息的完整性。

原始的拜占庭容错系统由于需要展示其理论上的可行性而缺乏实用性。另外,还需要额外的时钟同步机制支持,算法的复杂度也是随节点增加而指数级增加。

二.PBFT:Practical Byzantine Fault Tolerance,实用拜占庭容错算法。

实用拜占庭容错系统(PBFT)降低了拜占庭协议的运行复杂度,从指数级别降低到多项式级别(Polynomial),使拜占庭协议在分布式系统中应用成为可能。

PBFT是一种状态机副本复制算法,即服务作为状态机进行建模,状态机在分布式系统的不同节点进行副本复制。每个状态机的副本都保存了服务的状态,同时也实现了服务的操作。将所有的副本组成的集合使用大写字母R表示,使用0到|R|-1的整数表示每一个副本。为了描述方便,通常假设故障节点数为m个,整个服务节点数为|R|=3m+1个,这里m是有可能失效的副本的最大个数。尽管可以存在多于3m+1个副本,但是额外的副本除了降低性能之外不能提高可靠性。

PBFT要求共同维护一个状态,所有节点采取的行动一致。为此,需要运行三类基本协议,包括一致性协议、检查点协议和视图更换协议。我们主要关注支持系统日常运行的一致性协议。一致性协议至少包含若干个阶段:请求(request)、序号分配(pre-prepare)和响应(reply)。根据协议设计的不同,可能包含相互交互(prepare),序号确认(commit)等阶段。

上图为PBFT协议通信模式,每一个客户端的请求需要经过5个阶段,通过采用两次两两交互的方式在服务器达成一致之后再执行客户端的请求。由于客户端不能从服务器端获得任何服务器运行状态的信息,PBFT中主节点是否发生错误只能由服务器监测。如果服务器在一段时间内都不能完成客户端的请求,则会触发视图更换协议。其中C为客户端,N0~N3表示服务节点,特别的,N0为主节点,N3为故障节点。整个协议的基本过程如下:

1)客户端发送请求,激活主节点的服务操作。

2)当主节点接收请求后,启动三阶段的协议以向各从节点广播请求。

[2.1]序号分配阶段,主节点给请求赋值一个序列号n,广播序号分配消息和客户端的请求消息m,并将构造PRE-PREPARE消息给各从节点;

[2.2]交互阶段,从节点接收PRE-PREPARE消息,向其他服务节点广播PREPARE消息;

[2.3]序号确认阶段,各节点对视图内的请求和次序进行验证后,广播COMMIT消息,执行收到的客户端的请求并给客户端以响应。

3)客户端等待来自不同节点的响应,若有m+1个响应相同,则该响应即为运算的结果。

  PBFT在很多场景都有应用,在区块链场景中,一般适合于对强一致性有要求的私有链和联盟链场景。例如,在IBM主导的区块链超级账本项目中,PBFT是一个可选的共识协议。在Hyperledger的Fabric项目中,共识模块被设计成可插拔的模块,支持像PBFT、Raft等共识算法。