区块链四:共识机制——PBFT算法深入讲解

区块链四:共识机制——PBFT算法深入讲解@TOC背景介绍共识机制是区块链一大知识领域,作用就是维持分布式节点间的一致性,从而支撑去中心化中心,早在区块链之前,分布式系统就存在各种分布式的共识机制,共识机制不是区块链所发明,但区块链却

@TOC

背景介绍

共识机制是区块链一大知识领域, 作用就是维持分布式节点间的一致性,从而支撑去中心化,早在区块链之前,就存在各种分布式的共识机制,共识机制不是因区块链所发明,但区块链却对共识机制推广和进步有着重要影响。

共识算法分类

按应用场景分,共识算法可以分成两大类, 1、有坏人节点, 2、无坏人节点。
1、 有坏人节点,典型拜占庭问题,即系统中可能出现故意传送假结果的节点导致分布式系统结果错误,这种场景重点是在存在坏人的情况下能达成大家认可的一致结果。 其中BFT,PBFT, POW,POS都属于这类。
2、 无坏人几点,此类分布式共识算法,只需要保证各节点行动一致,并在部分节点down后能继续工作,一般在封闭式的分布系统使用,其中有Raft,Paxos。

对几种常见共识算法,大都类似的思路, 就是 一个组长(primary)带着N个成员(backup)干活,由组长派活收集各节点的状态,再确定结果是否一致, 类似分布式事务的二段提交。

其中不同算法主要解决这几个问题思路不一样,

  1. 系统如何判断达成一致?
  2. 组长down了或部分节点down了怎样保持系统可用性?
  3. 出现分叉了怎样处理两边的结果?

PBFT

这部分就讲解PBFT算法,怎样解决以上几个问题。
PBFT的算法思想, 以状态机运作,包括节点状态,消息状态, 由组长带领大家统一步调处理消息,而消息的是否继续迁移下一个状态,则通过多少节点达成一致,最后消息达到处理完的状态。

消息处理:

消息状态迁移路径: request -> pre-prepare -> prepare-> commit -> reply
在这里插入图片描述

C 代表Client, 客户端向系统主节点(0:组长)发送一请求request, 请求开始进入处理阶段
pre-prepare : 主节点参与把request分配一个唯一的编号 request-number n, 并把request跟n一起组成pre-prepare消息广播给所有成员(backup节点)

prepare : 所有成员(backup节点),收到pre-prepare消息, 依靠签名字段检查消息是否来源于主节点,确认无误,将request编号和本节点签名组成prepare消息,广播给其他所有成员,表示自己认可这请求编号和准备好了。

Commit :所有节点,若收到的prepare消息,依靠签名检查是否正确,若prepare消息数量超过全部节点数量的3分之二, 则认为系统达成一致认可该请求和请求编号,对所有节点广播commit消息,表示该节点可以进行request的业务。

Reply : 所有节点, 若收到commit消息,依靠签名检查消息是否正确,若commit的消息数量超过所有节点的3分之一,则完成request要求的业务,并构建reply消息,直接回复给client。Client根据是否收到超过3分之1个节点的正确回复,判断系统是否完成了请求request。

上面的图及说明就是PBFT的请求处理过程,那么回到上面的问题,

问题一:系统判断达成一致?
这里分两个阶段,prepare, commit, 全网超过三分之二个prepare,则达成一致, commit超过三分之一则达成一致。

简单说就是坏几点要少于 三分之一。

灵魂拷问

1、为啥是少于三分之一,而不是少于二分之一?
如果是多数服从多数,二分之一确实能满足,但这里是有两个阶段 prepare, commit。
n个节点,设错误节点 f, 第1到f个是错误节点, f+1 到n 是好节点pre-prepare -prepare, n-f 个节点都正确广播 prepare消息,prepare-commit, 当收到n-f 确认消息时,节点是不能确认这里n-f个消息时有多少来源f节点的,最多可能是f个节点,也就是n-f个消息中最多有个f是假消息,也不能影影响共识结果,因此 n-f-f > f 因此 f< n/3。

另一种理解,n-f个正常节点中,如果出现分歧,也能达成一致性,那么
(n-f)/2 >f,得 n>3f, f<n/3。

从上面的说明也知道,如果对于请求request r1 若commit(m) 成功达成一致,则不可能存在 commit(m’) 也达成一致,因此不可能存在分叉的情况。这里也回答了第三个问题(问题三,出现分叉了怎样处理两边的结果,不存在的)。

追问

为啥要分开两阶段,一阶段就搞掂不香吗?
——这里是为了保证request的顺序,第一阶段分配顺序号,第二阶段才是做业务。

这里也提到commit阶段可能k节点做视图转换,这是什么?
——这就涉及第二个问题,下面分晓。

问题二: 组长down了或部分节点down了怎样保持系统可用性?

视图转换

上面保证分布式系统的正确性safety,做正确的事,而视图转换则是为了可用性liveness, 假如primary节点down了,系统怎样? 要保证系统继续可用,就要使用view-change。

PBFT有一个全局的视图编号view number: v,主节点primary是根据 v mod n =i 得到 节点i为主节点。视图转换,就是v递增,主节点primary也相应转移到另一个节点。

  1. 当client发送请求primary后,一定时间没收到回复,则会发送请求给其他backup节点, backup 节点收到request后,起一个timer,如果timer过期,还没执行这个request(commit还没达一致),则backup节点发起view-change

  2. Backup 节点会广播一个view-change 消息,包含原来视图编号 v 合下个视图编号v+1
    如果节点收到的view-change 消息多于三分之二,则说明view-change达成一致。

  3. 当 v+1 mod n = j , 新的primary节点j,收到足够的view-change消息后, 就广播new-view消息,告诉其他节点使用新视图。

  4. 其他节点收到new-view后,确认消息签名正确,进入新视图;

有了视图转换,如果主节点down了,就会触发视图转换更换另一个主节点,如果下一个主节点也是down的,则继续切换,直到找到可用的主节点。因此保证只有有超过三分二的节点是好的,系统就可用。

可用性liveness,还要保证当视1图转换时候,可能有节点已经commit序列n,而有的节点只commit到序列n-1.,转移视图后,怎样保证request在各节点都能正确一致执行。
这还要引出下问题,checkpoint 机制。

Checkpoint机制:

这里就需要checkpoint, 这里checkpoint跟其他系统日志checkpoint基本一样。系统定期创建checkpoint,记录最新稳定提交的操作,并广播checkpoint消息,当节点收到超过三分之二的创建checkpoint消息,该checkpoint达成一致。视图转换时候带上最新的checkpoint,在checkpoint以后的请求,视为不稳定的,需要重做。

总结

PBFT算法是通过节点消息状态机方式达成请求处理的一致性,再通过视图转换,checkpoint机制确保系统的可用性,而本文概要介绍了这几方面的原理,但也过滤具体算法细节,有兴趣建议查看论文【引用1】

1 PBFT算法论文 http://pmg.csail.mit.edu/papers/osdi99.pdf

历史

区块链三:深入解析比特币交易原理
区块链二:比特币的区块数据结构
区块链一 :区块链应用介绍和展望

今天的文章区块链四:共识机制——PBFT算法深入讲解分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/60808.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注