0 引入
区块链每个节点都有一份完整的账本,其面临的一大难题就是账本的更新,要保证区块链中各个节点的账本在更新后能保持一致。区块链的共识层就是解决上述问题的层级:在去中心化且存在恶意节点的场景下维护区块链的全局账本。1 一致性问题
一致性问题是分布式领域最为基础和最为重要的问题。系统间一致性程度的达成是不一样的,拜占庭容错算法达成的共识是确定性的,即共识生成高度为n的区块就是确定的;工作量证明达成的共识是概率确定的,即共识生成高度为n的区块是不确定的(分叉),随着区块链高度的增长,区块发生变化的概率越来越小。一致性要求:2 共识设计的理论限制
2.1 FLP不可能原理
在推广到任意情形时,分布式系统的共识问题是无通用解的:当分布式系统中多个节点之间的通信网络不可靠的情况下,无法确保实现共识。FLP不可能原理:在网络可靠,但允许节点失效(即便只有一个)的最小化异步模型系统中,不存在一个可以解决一致性问题的确定性算法。2.2 CAP原理
本质上描述的是分布式系统在应用过程中三个特性的取舍,即分布式计算系统不可能同时确保以下三个特性:一致性:每次读操作都能得到最近写的结果或者返回错误。
可用性:每次请求都能返回一个非错误的结果。
分区容忍性: 任意节点间的连接中断或大大延迟,系统仍能够工作。
3 区块链共识算法
本质上是为了解决拜占庭将军问题3.1 拜占庭问题
3.1.1 两将军问题
两个将军通过信使来达成进攻还是撤退的约定,信使可以被敌军阻拦或者迷路导致消息无法送达(或丢失或伪造)。根据FLP不可能定理,两将军问题是无通用解的。3.1.2 拜占庭将军问题
问题描述
拜占庭是古代东罗马帝国的首都,守卫边境的多个将军们(即分布式系统中的多个节点)需要通过信使来传递消息,以对军事活动(系统中的某个提案)达成一致的决定。将军中可能存在叛徒(系统中某些节点作恶),叛徒努力的向不同的将军传递不同的信息,目标是干扰共识的达成,使得某些将军做出错误的决定。拜占庭问题即,在上述情况下,如何让忠诚的将军们能达成行动的一致。
结论
加入节点总数为N,叛变将军数为F,则当N>=3F+1时,问题才有解,由BFT算法进行保证。即叛徒不超过1/3时,存在有效的拜占庭容错算法。
3.2 拜占庭容错算法
BFT(Byzantine Fault Tolerance)
拜占庭容错算法
主要用于解决在网络通信可靠但节点可能故障的情况下,如何达成共识。该算法存在复杂度过高的问题,后提出了实用拜占庭容错算法。
PBFT(Practical Byzantine Fault Tolerance)
实用拜占庭容错算法
给全网消息的顺序进行共识,得到一个全局的序。在恶意节点不高于总数的1/3并在一个比较弱的同步假设的情况下,该算法能够同时保证安全性和活性。PBFT应用于欧盟链的场景而不应用于公有链的原因: PBFT在网络不稳定的情况下延迟很高;基于投票机制,而投票集合是有限的,否则无法满足少数服从多数;通信复杂度O(N^2)过高,可拓展性较低,一般的系统在达到100左右的节点个数时,性能下降非常快。
3.2.1 PBFT的基本概念
客户端(Client)向主节点发起请求的客户端,在区块链中往往跟主节点合二为一。主节点(Primary)
提案发起者,在区块链中即为区块发起者,在收到客户端请求后生成新区块并广播。验证节点(Backup)
提案投票者,在区块链中即为区块验证者,在收到区块后进行验证,然后广播验证结果对区块进行投票和共识。视图(View)
一个主节点和多个备份形成一个视图,在该视图上对某个提案达成共识,在区块链中即为对某个区块达成共识。不同视图的主节点一般是不一样的,即所有节点轮流做主节点,每个视图都会重新选择一个主节点。编号(Sequence Number n)
在每个视图中由主节点指定的一个数字,即提案的编号,在区块链中可以理解为区块高度。检查点(Checkpoint)
如果某个编号n对应的提案(区块)收到了超过2/3的确认,则称为一个检查点。
3.2.2 PBFT的具体流程
PBFT的三个核心阶段:预准备阶段(PRE-PREPARE)、准备阶段(PREPARE)、提交阶段(COMMIT)
在该轮共识中,0是主节点,1~3是验证节点,收到客户端向主节点发起请求后,系统将进行PBFT核心的三阶段共识。
(1)预准备阶段
主节点收到客户端发来的请求之后,构造PRE-PREPARE消息结构体<< PRE-PREPARE,v,n,d>,m>,并签名后广播给其他节点。
其中,PRE-PREPARE代表当前消息所处的协议阶段;
v为当前视图的编号;
n为主节点广播消息的一个唯一递增编号;
d为消息m的摘要;
m为客户端发来的消息,在区块链中可以视为交易。验证节点收到主节点的PRE-PREPARE消息后,对消息进行检验,检验包括: 检查收到的消息摘要d与自己对m生成的摘要是否一致,确保消息的完整性。检查与当前视图编号是否一致。检查序号为n是否在高低水位区间[h,H],防止主节点恶意地快速消耗可用的序号。检查之前是否已经收到相同n和v,但不同摘要d的消息m,保证验证节点只处理具有相同n和v消息中的一个。 验证通过之后,验证节点会构造PREPARE消息结构体<< PREPARE,v,n,d,i>>,并在签名后广播给其他节点。
其中,v、n、d的含义与PRE-PREPARE消息中一致;
i为本节点的编号。 在这个过程中,节点会将PREPARE消息和PRE-PREPARE消息记录到本地的日志中,用于视图切换中恢复未完成的请求,并重播到网络中在新的视图中继续共识。
(2)准备阶段
当节点收到其他节点的PREPARE消息时,进行如下检验: 检验PREPARE消息的签名是否正确当前节点是否已经收到与PREPARE消息中v、n对应的PRE-PREPARE消息,且n在区间[h,H]d和当前已收到PRE-PREPARE消息中的d是否一致。 当节点在规定时间内收到2F+1(包括自己)个通过检验的PREPARE消息后,构造COMMIT消息结构体<< COMMIT,v,n,d,i>>,并签名后广播给其他节点。
其中,v、n、d、i的含义与PREPARE消息中一致。 在这个过程中,节点会将COMMIT消息和其他节点发送的PREPARE消息记录到本地的日志中,用于视图切换中恢复未完成的请求。此时,主节点发送的消息已经达到PREPARED状态,节点将进入提交阶段。
(3)提交阶段
当节点收到来自其他节点的COMMIT消息时,会对COMMIT消息进行检验,检验步骤与对PREPARE消息的相似。当节点在规定时间内收到2F+1个(包括自己)通过检验的COMMIT消息,说明当前网络中的大部分节点已经对当前视图内的请求达成共识。节点会处理消息m中包含的操作,如果有多个m,则按照序号n从小到大执行。执行完成后,节点会返回结果给客户端。同样,在该过程,节点会将其他节点发送的COMMIT消息记录到本地的日志中。
当客户端收到F+1个相同的结果(来自不同节点)时,说明已经在全网达成共识,否则客户端需要判断是否重新向主节点发起请求。
3.2.3 日志压缩(垃圾回收)
在PBFT核心的三个阶段过程中,为了确保视图切换能够恢复一些未完成的请求,每一个节点都会记录一些消息到本地的日志中。若不对其进行压缩或者回收,日志将会占用大量的磁盘空间。PBFT采用检查点(CHECKPOINT)的机制来实现日志压缩。 最简单的做法(理想情况):在节点处理完一个请求后并返回结果给客户端之后,再执行一次当前状态的同步。当这种状态同步得到全网的共识之后,节点可将该请求对应的日志清除。鉴于对每个请求作状态同步的成本太高,因此,可以在执行完多个请求(例如k个)之后执行一次状态同步,而状态同步消息便是在节点之间广播的检查点消息< CHECKPOINT,n,d,i >。每执行k个请求后,节点 i 会创建一个检查点并广播消息 < CHECKPOINT,n,d,i > 给其他的节点。其中,i 为本节点的编号;
n 是最后一次执行请求的序号;
d 为执行序号为n的请求后的状态机的状态摘要。 此外,该检查点消息同样会被记录到本地的日志中。同时检查点变成稳定检查点,高度为n。 (实际情况):节点 i 向其他的节点发出检查点消息后,其他节点并未处理完k个请求,不会立刻对节点i做出响应。而节点 i 不会等待其他节点的回复,而是继续按照自己的节奏向前处理请求,但是节点i创建的检查点在此时没有变成稳定检查点。如果节点 i 处理请求过快,其创建多个检查点一直无法变成稳定检查点,会造成日志积压。解决方法:PBFT设置了高低水位区间[h,H]
其中,低水位 h = 上一个稳定检查点的高度,高水位 H=h+L。
L是系统设定的数值,等于节点周期处理请求数值K的整数倍。
(例如设L=3K,当节点i处理的请求序号到达高水位 H=h+3K,便会暂停脚步,直到稳定检查点发生变化再继续向前,从而避免日志的积压。)
3.2.4 视图切换
保证系统的可用性:客户端发来的请求m由当前视图指定的主节点广播到网络中,但当主节点系统中断或者作恶,或者全网超过1/3的节点系统中断时,当前视图内的消息就无法在全网达成共识。此时,PBFT通过视图切换协议将全网的节点切换到新视图中, 对未完成的请求继续共识,避免节点无限期的等待,保证系统的可用性。每个视图开始或者节点收到消息时,
节点 i 会启动一个计时器,若此时有计时器在运行,则会重置计时器;
但是当主节点系统中断或者其他情况导致节点 i 在当前视图v超时的时候,节点会触发视图切换的操作,启动视图切换协议。 启动视图切换协议:
节点 i 向其他节点广播< VIEW-CHANGE,v+1,n,C,P,i >消息,
其中,n是最新的稳定检查点的高度;
C 是节点 i 保存的经过2F+1个(包括自己)节点确认稳定检查点消息的集合,表面该稳定检查点已经达到全网共识;
P 是当前节点保存的n之后所以已经达到PREPARED状态消息的集合,即已完成准备阶段的消息。 当新视图v+1中的主节点 i 收到2F+1个(包括自己)经过检验的VIEW-CHANGE消息后,将向其他节点广播< NEW-VIEW,v+1,V,O >消息。
其中,V是有效的VIEW-CHANGE消息集合;
O 是PRE-PREPARE消息集合,该集合是从已经达到PREPARED状态的消息中转换过来的。
关于O : 当主节点收到2F+1个VIEW-CHANGE消息,可以确认高度为n的稳定检查点之间的消息在视图切换的过程中不会丢失,但是当前检查点之后、下一个检查点之前的已经达到PREPARED状态的消息会丢失。因此,新视图的主节点会把旧视图中已经达到PREPARED状态的消息转换为PRE-PREPARE消息,重新广播到网络中。PRE-PREPARE消息集合的选取规则: 选取V中高度最低的稳定检查点的编号min,以及V中已达到PREPARED状态消息的最大编号max。对于min和max之间的每个序号n,如果存在某个P中,则创建<< PRE-PREPARE,v+1,n,d>,m>消息;否则,创建一个空的PRE-PREPARE消息<< PRE-PREPARE,v+1,n,d(null)>,m(null)>,其中d(null)为空消息摘要,m(null)为空消息。 其他验证节点收到主节点的 NEW-VIEW消息后,校验签名,V和O的消息是否合法,验证通过后,则主节点和新节点都进入新视图。总结:
在视图切换中,C、P、O是三个重要的消息集合,
C 确保了视图切换时,在最新稳定点之前的状态安全;
P 和O 确保了视图切换中达到PREPARED状态的消息能够得到重放,而不会丢失。 前文提到过,预准备阶段和准备阶段是为了确保同一视图下消息的一致性,而C、P、O三个集合就是解决这个问题的,确保在新视图中,主节点重放的旧视图中的消息依旧能保持顺序一致性。
3.2.5 PBFT中节点的状态
上述PBFT的核心流程中节点可能出现的状态如下:
等待请求 等待客户端的请求,所有节点都处于这个状态,主节点收到客户端请求之后,会切换到预准备状态;验证节点收到主节点消息后会切换到准备状态。预准备 该状态是主节点专属的,主节点处理客户端的请求并广播PRE-PREPARE消息,切换到准备状态。准备 节点进入这个状态后,验证主节点的PRE-PREPARE消息并生成和广播PREPARE消息,同时等待2F+1个(包括自己)节点的PREPARE确认。等待2F+1个PREPARE确认 如果在超时之前收到2F+1个PREPARE确认,则切换到提交状态;否则,切换到视图切换状态。视图切换 节点广播编号为v+1的VIEW-CHANGE消息,并等待2F+1个(包括自己)VIEW-CHANGE消息。等待2F+1个VIEW-CHANGE消息 当新视图的主节点收到2F+1个VIEW-CHANGE消息时,广播NEW-VIEW消息,并切换到预准备阶段,开始新视图的共识。当验证节点收到2F+1个VIEW-CHANGE消息,切换到等待请求状态;若在这之前收到主节点NEW-VIEW消息,则开始新视图的共识,切换至准备阶段。若超时,节点广播编号为v+1的VIEW-CHANGE消息,继续视图切换的协议,直到新视图切换成功。