区块链原理与应用 课件 第6章 联盟链共识协议

联盟链共识协议联盟链与公有链公有链（无许可链）以比特币为代表，只要遵循所采用的共识协议就能参与新区块的生成，这个过程

具有完全的开放性，参与者无需注册或者申请不能满足监管需求，同时性能较差，吞吐率较低、交易确认延迟较大联盟链（许可链）经过注册认证的节点才能参与共识过程、生成区块，一般用于特定行业或者领域联盟链支持更好的监管需求，一般可提供高的性能，包括更好的吞吐率和更低的确认延迟共识协议大多基于分布式领域的研究成果状态机复制协议（SMR）在分布式计算领域，通常将每个节点抽象为状态机，共识协议用于保证这些状态机的状态是一致的，因此也称为状态机复制协议状态机有一个唯一的初始状态，当状态机接收到一个输入后将依据状态转移函数从当前的状态转移到下一个状态状态机复制协议保证所有状态机所得到输入相同并且顺序一致安全性：所有状态机按照相同顺序执行请求，并得到相同的输出和新的状态活性：所有请求最终都会被所有正确的状态机执行

状态机复制协议与区块链状态机复制协议保证所有状态机的输入数据具有相同的序列，通常抽象为日志记录。如果将输入数据构建为哈希链式结构，则可转化为区块链系统。req1req2req3state1state2state3state4rep1rep2rep3req1req2req3state1state2state3state4rep1rep2rep3req1req2rep2rep1replica0replica1replica2clientclientreq1req2req3state1state2state3state4rep1rep2rep3req3rep3在状态机复制协议的执行角色客户端：普通的用户，产生原始的数据请求，将数据请求输入到所有的状态机共识节点：所有状态机副本都是共识节点，通过状态机复制协议获得相同的输入主节点：特殊的状态机副本，客户端产生的数据请求首先发送给主节点，主节点

将请求排序、打包后发送给其他所有的状态机副本执行过程通常将状态机复制协议的执行过程划分为相连的视图，在大多数协议的设计中，一个视图对应于一个主节点，视图的切换也意味着主节点的更换通常使用投票机制实现输入数据的共识，协议的执行过程遵循提案-投票的模式

法定多数证明（QC）法定多数证明是由一组节点的合法签名所组成的证明，表明该消息或区块已经获得了超过系统设定门槛的认可。QC要求的签名数量一般要求大于(N+f)/2，其中N是参与者总数量，f为拜占庭节点数量QC1QC2两个矛盾的提案不可能都拿到QCQC数量讨论为了保证安全性要求冲突的提案不能都获得QC，因此为了保证活性要求正确的节点就能够完成投票，因此联合上述两个条件，得到如果采用投票多数的模式设计共识协议并且同时保证协议的安全性和活性，则拜占庭节点的数量要少于节点总数的1/3

仅考虑失效节点的共识协议为了保证安全性要求冲突的提案不能都获得QC，因此为了保证活性要求正确的节点就能够完成投票，因此联合上述两个条件，得到如果采用投票多数的模式设计共识协议并且同时保证协议的安全性和活性，则失效节点的数量要少于节点总数的1/2

失效-停止敌手共识协议（Paxos）选出一个临时的主节点主节点负责提议请求，并发送到其他结点在收到#{QC}个确认后，可确定共识的结果（Quorum机制）Paxos更新主节点当主节点错误时选出新的主结点新的主节点需要确定系统当前的状态（是否有正在进行的共识）主结点从新的状态开始处理请求

Paxos协议的活性与安全性活性当主节点没有失效时，主节点总是提出正确的提案，主节点发出的消息总能收到超过一半的accept消息从而完成共识。当主节点失效时系统将会暂时失去活性，超过时间后将会更换新的主节点，新主节点将会读取尚未完成的提案并将其继续完成，此时系统将会恢复活性。安全性Paxos协议中没有恶意节点,因此同一个主节点对某个编号不会发出不同的提案。某个编号提案在执行过程中发生了主节点切换，如果这个提案能够被某个诚实节点完成共识，意味着超过一半的节点发出了accept消息，新主节点收到超过一半节点发出的gather消息，一定能够从某个节点收到包含这个编号的提案继续完成该编号已有提案的执行

Paxos协议分析执行过程需要主节点发出提案并经过所有共识节点1轮的投票过程，是常数轮次复杂度的共识协议一次共识中所有节点发出一个投票消息给主节点，消息数量的复杂度是O(n)。正常执行过程中，协议执行的推进依赖于主节点收到超过半数的投票信息而无需等待一个固定的最大网络延迟∆当主节点失效时，需要通过超时机制更新主节点而恢复活性，因此Paxos协议是一种半同步网络假设的共识协议

将Paxos协议用于拜占庭节点？Paxos协议不能容忍拜占庭节点，不能简单通过提高投票法定多数的数量而弥补。可构造攻击场景：主节点针对同一个编号可以构造两个不同的提案A、B，将A发送给f个诚实共识节点，将B发送给另外f+1个诚实共识节点主节点收到共识节点分别针对A和B的accept消息后停止发送消息等待超时更新的主节点通过read消息视图获取前一个提案的内容新主节点通过gather消息获得A与B两个不同的提案，此时新主节点无法决定是继续完成A还是B

实用拜占庭容错协议(PBFT)系统中一共有n个参与节点，最多有不超过f个恶意节点，并且满足n≥3f+1

协议执行分割为连续的视图（View），每个视图有唯一的编号v

每个提案有唯一的编号，视图编号v和提案编号k可以唯一确定一个位于视图v中的第k个提案普通用户的请求称为消息m，d为使用哈希函数H()生成的消息摘要，即d=H(m)系统每个参与共识过程的节点需要提前完成注册并拥有唯一的编号，使用Pi表示第i个节点，使用σi

表示第i个节点的数字签名

PBFT算法概述共识协议：在正常执行协议中主节点生成一个提案，其他节点执行该协议，如果协议能够在预期时间内正确结束，则在诚实节点之间完成对主节点所生成提案的共识。

视图更新协议：如果协议不能在预期时间内正确结束，则可能是主节点是恶意节点或者主

节点发生故障，则诚实节点发起视图更新协议以完成主节点的更新

PBFT共识过程通过增加一轮投票解决更新主节点时的提案选择问题Pre-Prepare阶段消息格式v是视图编号，k是主节点分配给该请求的序号，m是客户端发送的请求消息，d是请求消息m的哈希值主节点将PRE-PREPARE消息广播给所有共识节点，共识节点检查消息的有效性

C0123<<PRE-PREPARE,v,k,d>,m>Prepare阶段消息格式v是视图编号，k是主节点分配给该请求的序号，d是请求消息哈希值，i是共识节点编号共识节点如果收到的PRE-PREPARE消息有效，则其构造相应的PREPARE消息并广播给其他节点（主节点默认支持PREPARE消息）C0123<PREPARE,v,k,d,i>Commit阶段消息格式v是视图编号，k是主节点分配给该请求的序号，d是请求消息哈希值，i是共识节点编号共识节点如果收到2f+1个有效的PREPARE消息，则其构造相应的COMMIT消息并广播给其他节点主节点也需要显式构造并广播C0123<COMMIT,v,n,k,i>Decide阶段共识节点如果收到2f+1个有效的COMMIT消息，则该节点认为对应的消息以及完成共识，向客户端发送REPLY消息客户端收到f+1个REPLY消息后认为共识完成检查点更新为了减少后续视图更新过程中消息传输数量，PBFT协议对于以及完成共识的请求设置周期性的检查点当请求序号到达某一个检查点，且该检查点及之前的请求都以及完成共识，则发起检查点更新过程共识节点将检查点消息广播给其他所有节点，当节点收到2f+1个检查点消息后，则认为该检查点为稳定的检查点消息格式：k是检查点对于的序号，d是对应消息的摘要，i是生成该消息的副本节点序号<CHECKPOINT,n,d,i>视图更新过程—ViewChange如果共识节点发现系统长时间不产生新的共识，则认为可能是由于主节点失效或者恶意行为造成的，将会发起视图更新过程。当共识节点超时后进入到视图更新阶段，构造VIEW-CAHNGE消息，发送给视图v+1的主节点，不再接收共识协议流程的其他消息。k是最近的完成稳定检查点的序号，C是对应的2f+1个检查点消息P为在消息k之后并且已经进入prepared状态的消息以及证据集合，集合中的每个元素为Pm

<VIEW-CHANGE,v+1,k,C,P,i>视图更新过程—NewView当v+1视图的主节点P从其他的共识节点接收到2f个有效的VIEW-CHANGE消息后，进入到New-View阶段。视图v+1的主节点P构造NEW-VIEW消息，并广播给所有的节点消息格式：V包括2f+1个有效的VIEW-CHANGE消息O为一系列PRE-PREPARE消息的集合，这些消息是前一主节点发起已经完成prepared的消息，未完成的则用空消息取代所有共识节点首先完成O中携带的提案共识

<NEW-VIEW,v+1,V,O>PBFT协议的安全性与活性安全性：因为诚实节点不会为同一编号冲突的提案投票，因此不可能有冲突的提案同时获得2f+1的投票，因此不可能有冲突的提案完成共识活性：如果主节点是诚实节点，则其不会产生冲突的提案，其提案都是有效的，共识节点将会完成共识过程如果主节点是拜占庭节点，则提案可能共识失败从而引发视图切换如果一个提案可能完成共识，则至少2f+1个节点认为其完成了Prepare阶段的投票，这些节点至少包括f+1个诚实节点，因此至少有一个诚实节点将该提案包含在VIEW-CHANGE消息中。视图切换的主节点如果是诚实节点，将会继续完成该提案的共识。PBFT协议性能分析在正常共识过程中，每个共识节点对所有其他节点发起广播消息，因此总的消息数量为O(n2)在视图更新过程中每个节点需要将本身的状态证据发送给新的主节点，每个状态的证据需要包含达到该状态所需的2f+1个消息，状态证据的复杂度为O(n)新的主节点在NEW-VIEW消息中，包含了2f+1个有效的VIEW-CHANGE消息，因此NEW-VIEW消息的复杂度为O(n2)新主节点将该消息广播至所有n个节点，因此视图更新阶段整体通信复杂度为

O(n3)。

基于门限签名的拜占庭共识协议(SBFT)共识节点将投票发送给聚合节点，聚合节点将投票聚合后发送给其他节点，将n->n的广播转换为n->1->n，消息复杂度从O(n2)降低为O(n)SBFT协议分析SBFT协议的投票过程与PBFT类似，其活性和安全性继承自PBFT协议SBFT将投票过程的消息传播数量从O(n2)下降为O(n)，因此可以容纳更多节点参与共识，其代价是增加了消息交互轮次，可能带来共识时延的增加SBFT协议的ViewChange过程与PBFT类似，但是每个证据的数量从2f+1个投票签名变为一个门限签名，因此视图更新的消息数量复杂度降低为O(n2)能不能进一步降低视图更新的消息复杂度？线性消息复杂度共识协议HotStuffHotStuff的设计目标对某个提案达成共识的通信复杂度为𝑂(𝑛)，在更换视图时，其通信复杂度依然是𝑂(𝑛)HotStuff实现方法将PBFT的Prepare，Commit的两轮投票过程扩展到了Prepare，Pre-Commit，Commit三轮投票在达成共识的同时更换视图HotStuff共识协议HotStuff共识协议Prepare阶段：Leader选择最优的一个区块作为基础，并生成新的区块发给所有节点，所有节点如果支持该区块则发出PREPARE投票Pre-Commit阶段：Leader搜集（n-f）个PREPARE投票生成聚合签名(prepareQC)，

将聚合签名发送给所有节点，节点如果支持该签名则发出PRE-COMMIT投票Commit阶段：Leader收到个（n-f）PRE-COMMIT

投票后，生成聚合签名(lockedQC