区块链原理与应用 课件 第4章 分布式系统与共识协议

分布式系统与共识协议共识问题共识协议是指在分布式系统中，帮助参与的节点响应输入请求、维护一致的状态，并决定后续执行结果的数据处理过程。在分布式系统中，参与共识的节点可以用状态机描述，而共识协议用于保证状态机之间状态的一致性，因此共识协议也通常被称为状态机复制（StateMachineReplication,SMR）协议共识协议应满足：安全性：所有诚实节点应有相同的输出活性：共识过程应能够在相应的时间内结束有效性：

来自诚实用户的合法请求都应该能够被最终决定

共识协议参与者模型节点模型节点认证：身份注册、资源认证消息认证：口头消息、签名消息节点能力：概率多项式计算能力、平凡模型敌手模型敌手类型：失效停止敌手、拜占庭敌手敌手数量：常数数量、常数比例、任意数量敌手选择：静态控制、适应性控制共识协议网络模型网络结构构建P2P的去中心化网络消息传播通过消息转发模拟广播信道，保证诚实节点发出的消息不被阻断网络延迟异步网络：网络传输的最大延迟未知同步网络：网络传输的最大延迟已知半同步网络：正常运行不依赖于网络传输的最大延迟，极端情况的系统活性依赖于网络传输最大延迟已知FLP不可能定理[Fischer，Lynch，Paterson1985]提出，在异步网络中，如果有哪怕一个失效节点，诚实节点不可能确定性达成共识网络状态：异步网络异常节点：一个失效停止输出结果：确定性共识拜占庭将军问题首领节点(Leader)输入0/1每一轮每个节点可以给其他节点发送消息。消息在下一轮的开始被其他节点收到。协议结束时每个诚实节点输出一个bit或者退出执行。诚实节点遵守协议执行，恶意节点可以做任何操作。AttackAttack拜占庭将军问题一种简单的思路首领节点发送b到所有节点所有节点转发收到的b到其他节点（投票）每个节点统计投票结果，输出的票多的结果如果首领节点是恶意节点？口头消息不可能结果口头消息是指消息的接收者仅能验证直接的消息来源，而不能验证消息的最初来源，这种模型对应于可以验证消息发送者的身份而没有对消息使用数字签名。在口头模型下，如果诚实节点的数量不超过2/3，则不可能实现拜占庭容错协议简化场景：在三个节点的情况下，如果有一个拜占庭节点，则不可能实现容错协议构造下面两个场景，从节点1的角度看无法区分这两个场景，也就无法决定对两个场景都有效的输出三节点拜占庭容错场景1三节点拜占庭容错场景23f节点拜占庭容错将简化的3节点模型扩展为3f节点模型假设存在针对3f个节点的拜占庭容错协议（其中的节点称为阿尔巴尼将军)，则3个拜占庭将军分别模拟f个虚拟阿尔巴尼将军，则能够实现3节点拜占庭容错口头消息BFT协议OM(f)OM(f)协议以递归调用的方式定义基础协议OM(0)

主节点向所有普通节点发出消息。普通节点输出所收到的消息，如果没有收到消息则输出默认消息"0"。OM(f)协议主节点向所有普通节点发出消息。对于任意第i个节点Pi，假设其接收到的消息为vi，如果其没有接收到消息则使用默认消息0。Pi作为新的主节点执行协议OM(f-1)，将vi作为消息发送给其他n-2个节点(除去原主节点以及自身)。

任意第i个节点Pi

，采集在(2)中所收到的(n-1)个消息并将多数投票结果作为输出。OM(f)协议分析（活性）假设节点总数n=2f+m，其中f为恶意节点数量，m是任意整数，如果主节点是诚实节点，则OM(f)协议中的所有诚实节点输出相同的值v

如果f=0，按照算法OM(f)的定义，诚实的主节点将向所有节点发出相同的消息v，且所有诚实节点都将输出v

如果f>0，采用归纳法证明，假设OM(f-1)成立。在OM(f)中，主节点是诚实节点，向所有的节点发送相同的值v。其他n-f-1个诚实节点收到v后，作为主节点执行n-f-1个OM(f-1)协议，并使用v作为输入。根据归纳假设，这些OM(f-1)协议都将输出v，因此OM(f)的投票输出为v。

OM(f)协议分析（安全性）在OM(f)协议中，假设节点总数n>3f，其中f为恶意节点数量，则OM(f)协议中的所有诚实节点输出相同的值。如果f=0，没有拜占庭节点，通过OM(0)所有节点都将输出主节点的输入v。如果f>0，且主节点是诚实节点，由活性可直接得到安全性。如果f>0，且主节点是恶意节点，采用归纳法证明，假设OM(f-1)成立。假设主节点向n-1个节点发送任意值，

n-1个节点将执行n-1个OM(f-1)协议。

n-1>3(f-1)，满足节点总数相对于恶意节点数量的要求。根据归纳假设，在所有的OM(f-1)协议中，诚实节点的输出都是相同的（这些值可能不同)

，因此所有诚实节点的投票结果都相同。

OM(f)协议效率分析M(f)协议需要执行f轮，如果假设n=3f+1，则OM(f)协议的轮次复杂度为O(n)

OM(f)协议是通过f次递归调用完成共识的，因此OM(f)协议传输的消息数量是递归调用过程中的消息总数，为指数复杂度OM(f)协议效率很低，无法用于节点以及恶意节点较多的场景中

Dolev-Strong协议如果使用数字签名技术则不但可以完成对于直接消息来源的身份认证，还可以完成对于转发消息最初来源的验证，这为协议的设计提供了更强有力的工具，这种模型也称为签名消息模型。Dolev-Strong协议是一种基于签名消息模型设计的共识协议

敌手数量：任意数量n>f类型：拜占庭敌手网络同步网络，按照轮次执行Dolev-Strong协议描述假设最多有

f

个拜占庭节点，节点数量n>f，主节点输入消息为

m主节点将消息

m

发送给所有节点，任意节点P初始化集合𝑆为空并执行如下f+1轮，其中𝑟表示轮次for𝑟=1tof+1如果P收到一个新的消息m，并且有𝑟个不同节点的签名(含主节点)则对

m

签名并发送给所用节点，同时放入集合

𝑆←𝑆∪{m}否则什么都不做如果|𝑆|=1输出

m∈𝑆，否则输出“失败”DolevStrong协议执行例子Attack=11Caesar1Caesar1Caesar1Caesarf=2BrutusPompeiusAugustusMarcAnthony假设两个恶意节点，且主节点为诚实节点，协议一共执行3轮。DolevStrong协议执行例子Attack=11Caesar1Caesar1Caesar1Caesarf=2r=1BrutusPompeiusAugustusMarcAnthony假设两个恶意节点，且主节点为诚实节点，协议一共执行3轮。DolevStrong协议执行例子Attack=11Caesar,MA1Caesar,Augf=2r=2BrutusPompeiusAugustusMarcAnthony1Caesar,Aug1Caesar,Aug1Caesar,Aug1Caesar,Aug1Caesar,MA1Caesar,MA1Caesar,MA1Caesar,MADolevStrong协议执行例子Attack=11Caesar,MA1Caesar,Augf=2r=2BrutusPompeiusAugustusMarcAnthony0Brutus,PompeiusDolevStrong协议执行例子Attack=11Caesar,MA1Caesar,Augf=2r=3BrutusPompeiusAugustusMarcAnthony执行3轮后协议结束。DolevStrong协议执行例子1Caesar,MA1Caesar,Augf=2r=3BrutusPompeiusAugustusMarcAnthony0Caesar,Brutus,Pompeius假设3个恶意节点，且主节点为恶意。DolevStrong协议执行例子1Caesar,Aug,MA1Caesar,Aug,MAf=2r=3BrutusPompeiusAugustusMarcAnthony0Caesar,Brutus,PompeiusAttackConfused诚实节点输出结果可能不一致。Do