链客,专为开发者而生,有问必答!
此文章来自https://www.liankexing.com,未经允许拒绝转载。
笔者初学区块链,很多东西也是慢慢摸索,之所以写下这些基本概念一方面作为自己学习的整理,另一方面也希望更多交流学习的机会。
根据拜占庭问题演变而来的算法PBFT算法,无论执行流程的复杂度还是算法的效率来说,PBFT是效率最好的算法,其是1999年卡斯特罗和利斯科夫提出来的,将算法复杂度由指数级降低到多项式级,使拜占庭容错算法在实际系统中变得可行。
PBFT算法设定系统为异步分布式,单一节点失效的一个独立事件,作者使用加密技术来防止攻击,消息设定为:公钥签名+消息验证+消息摘要。并假设整个网络中,所有节点的公钥可以做签名认证,前提是:恶意节点的算力不能破坏加密算法,不然基本保障就不存在了,其不能无限延长节点通讯。
和之前拜占庭问题一样,网络中节点还是要求n个节点,恶意节点m,n>3m+1。在系统中要求整个系统有安全性和活性。整个系统通过状态机副本复制的特性来传递信息。
先谈论下安全性,在n>3m+1的情况下,安全性就是副本复制数量(<m)允许一定的失效,系统通过对这些失效节点控制改变访问全新来恢复恶意节点的攻击。
活性,同步的方式不提供安全性,但是提供活性,在异步系统中,通过同样受到请求后失效的副本不超过m,并且延时时间控制,那么最终这个消息会在异步模式中再次重新发送被接受,同样保证了系统的活性。
在现实的分布式系统中,在定义一个时间戳的概念T,在发送消息的时候通过V+T+请求+回复信息,客户端同样等待m+1个回复,同时保证签名+时间戳+回复信息来保证一致。这里存在两种情况,一种是客户端请求超时,那就再发送一次,如果是主节点P出故障,那就改变V状态,新选一个P节点。保证第二次的执行过程。
再应用到实际场景,现在PBFT算法定义三阶段任务:预准备(pre-prepare)、准备(prepare)、确认(commit)。
预准备:P分配一个系统序列号ID,发送给所有B节点。发送格式(V、ID、信息摘要、客户端请求)。B节点验证信息摘要和客户端请求一致,验证当前V编号。
准备:B节点在接收信息后加上自己的消息日志,发送至其余节点。P和B节点同时验证消息签名,如果一致,那么就把验证通过写入消息日志。每个节点在准备阶段对每个副本节点验证预准备的消息和准备消息一致性检查完毕。
确认:在前面两个极端一切正常的话,在同一系统环境中,所有请求序号一致,验证消息一致,简单理解就是确认m+1个节点发送了之前发送的序号和消息。每个节点接受确认消息,签名正确;消息的系统环境编号V与节点的环境编号V一致;消息的序号ID满足序列要求。节点通过确认至少m+1个副本信息,保证整个系统中算法的正确性。
结合区块链的角度来说明:
C我们认为是客户端,0、1、2、3是分布式系统中的节点成员,0是主节点、1、2是备份节点,3也是备份节点但已发生故障,默认3发送信息为无效。
1.C发起一笔请求到0号主节点。
2.主节点0开始对请求排序编号,并把请求序号发送到1、2、3节点。
3.1、2节点互相之间和0主节点之间发送消息。
4.0、1、2、之间确认0主节点的分配序号,互相确认。
5.0、1.、2、确认信息回复C。
6.客户端C判断收到确认是否在f+1内,确认结果。
三个阶段达成共识:Pre-Prepare、Prepare 和 Commit,整个流程如下:
1.从全网节点选举出一个主节点(Leader),新区块由主节点负责生成。
2.每个节点把客户端发来的交易向全网广播,主节点将从网络收集到需放在新区块内的多个交易排序后存入列表,并将该列表向全网广播。
3.每个节点接收到交易列表后,根据排序模拟执行这些交易。所有交易执行完后,基于交易结果计算新区块的哈希摘要,并向全网广播。
4.如果一个节点收到的2f(f为可容忍的拜占庭节点数)个其它节点发来的摘要都和自己相等,就向全网广播一条commit消息。
5.如果一个节点收到2f+1条commit消息,即可提交新区块及其交易到本地的区块链和状态数据库。