分布式系统我们最初了解区块链的时候很多人会形容这个区块链是一个“分布式的不可篡改账本”这是一个很形象的说法但是我认为更为准确的形容是“所有节点共同维护的状态机”。为什么分布式和区块链不能划等号呢两种常见的分布式模型中心化网络Client-Server去中心化网络P2P交互方式用户只能和服务器交互用户之间可以交互优缺点通讯速度快客户端需要存储的信息量少响应稳定相对垄断相对自由通讯难度随着用户数量成指数级上升涉及分布式问题非拜占庭问题只存在节点挂机情况拜占庭问题存在干扰一致性的恶意节点图例中心化网络的请求模型属于是网状模型并没有一个节点获取所有流量获取和自身不相干的流量也只用于校验或转发去中心化模型的请求模型有一个中心服务器集群承担所有流量的转发比较和联系对比上述两个图我们很容易发现——去中心化的通信方式每个节点需要保存的”通信信道“是超多的因此这种模型无法适应大量的节点参与我们拿”微信“来举一个例子。微信的交流虽然看起来是点对点的C2C结构但是实际上是用户请求云服务器来实现的信息交流的。以“种子网络“为例在其发展初期存在的节点到其后期均被暴风影音等节点垄断。可以看出去中心化向中心化演变是一个自然的趋势。所以我们通常的中心化分布式系统是一个”有超强中心节点的系统“在这个系统中只要服务器不挂机就是正常运行的不存在恶意节点破坏一致性问题因为只有服务器自己说了算而区块链涉及的分布式问题往往是有恶意节点存在的这样的问题被称为“拜占庭将军问题”拜占庭将军问题背景在网络上的节点分为恶意节点目的是扰乱一致性和故障节点挂机。拜占庭问题解决的是拥有恶意节点的问题拥有故障节点的成为“非拜问题”首先我们来补充一下分布式账本的节点问题。拜占庭问题是由兰波特提出的为了解决这个问题采用了从理想化的“口头协议”--解决网络延时的“PBFT算法”--区块链使用的“PoW机制”问题本身拜占庭帝国派出多支军队进攻一个城池这个城池十分坚固一支部队无法攻克但是多支军队一起攻打即可攻克。现在将军中有叛徒他的目的是使得忠诚的部队行动不一致叛徒的目的是为了扰乱系统的一致性。这个问题有解的前提是n(总节点个数)3m(恶意节点个数)。问题解法最初的解决方法——口头协议这个解法使用的模型叫做将军-副官模型在这个模型的要求下所有的节点都可以是将军也都可以是副官我们将第一个发送命令的节点叫做将军其余的叫做副官值得注意的是副官与副官之间也可以通信所有节点需要遵守两个规则忠诚的副官们会遵守同一个命令若将军忠诚则所有的副官会遵守他的命令下面我们看一下最基础m1、n4的情况副官中出现叛徒首先我们将“将军”发布的命令称为A即副官1副官2副官叛徒3收到的将军命令都是A这时副官1会询问另外两个副官得到副官2的“将军给的是命令A”以及叛徒3给的“将军给的命令是B”B是假消息的回答因此副官1按照少数服从多数原则推断出3是叛徒A是一致性命令。副官2同理将军是叛徒叛徒将军向副官1、2、3分别发送命令A、B、C叛徒是为了扰乱一致性的副官1接到A命令后会联系2、3得到副官2的“将军给的是命令B”以及副官3给的“将军给的命令是C”这时候副官1可以推断出将军是叛徒同时放弃这一轮的命令要求的第二条不成立副官2、3同理复杂情况以m2,n7为例这种方法要注意以下两点签名也就是一个人发布命令的时候需要加上自己的签名转述别人的信息的时候需要加上他的签名这是为了保证信息的唯一性比如上文情况中我使用的“副官说‘将军的命令是......’”这一说法每个节点使用表格进行决策这是一种递归嵌套的思想下面表格展示的每行指的是节点的决策信息纵列是节点给别人的应答,假设将军给出的命令是AV1给出的应答V2给出的应答V3给出的应答V4给出的应答V5给出的应答V6给出的应答V1AAAbfV2AAAcgV3AAAdhV4AAAei上述的小写字母指的是随即命令善意节点依照少数多数的原则可以推断出结果在这里不展开叙述通信次数我们简单的计算一下上面两种模型的通讯次数发现当存在四个节点中一个恶意节点时的通讯次数为9次七个节点中存在两个恶意节点的通讯次数为36次因此这种方法的算法复杂度随着节点数以指数级上升是一种很不明智的算法。而下面要介绍的PBFT算法就将这种复杂度降到了多项式级。用通讯次数换取安全性——PBFT算法和“口头协议”一样PBFT算法也是使用通讯次数换取安全性这样的原理也决定了它只能在小范围中使用实际生产中的应用场景往往是联盟链。简介PBFT算法中节点只有两种角色主节点primary和副本replica两种角色之间可以相互转换。两者之间的转换又引入了视图view的概念视图在PBFT算法中起到逻辑时钟的作用。算法实现流程算法开始的时候使用随机数或者一定的顺序得到主节点首先客户端发送消息m给主节点p主节点就开始了PBFT三阶段协议三个阶段分别是预准备pre-prepare准备prepare提交commit。其中pre-prepare和prepare阶段最重要的任务是保证同一个主节点发出的请求在同一个视图view中的顺序是一致的prepare和commit阶段最重要的任务是保证请求在不同视图之间的顺序是一致的。算法的流程图如下在这个周期中C指客户端节点0指主节点1、2指正常副本3指掉线副本主节点收到客户端发送来的消息后构造pre-prepare消息结构体 PRE-PREPARE, v, n, d, m 广播到集群中的其它节点。PRE-PREPARE标识当前消息所处的协议阶段v表示当前视图编号n为主节点广播消息的一个唯一递增序号d为m的消息摘要m为客户端发来的消息这里面的“摘要”也就是对于客户端消息进行的哈希压缩副本(backup)收到主节点请求后会对消息进行检查检查通过会存储在本节点。当节点收到2f1包括自己个相同的消息后会进入PREPARE状态广播消息 PREPARA, v, n, d, i 其中i是本节点的编号。对消息的有效性有如下检查也就是满足超2/3节点达成共识检查收到的消息体中摘要d是否和自己对m生成的摘要一致确保消息的完整性。检查v是否和当前视图v一致保证消息存在于同一周期。检查序号n是否在水线h和H之间避免快速消耗可用序号h是当前的安全水线safety waterline表示系统中可以接受的最低序号H是当前的高水线high waterline表示系统中可以接受的最高序号n需要在这两个水线之间即h n H主要是为了避免以下问题序号枯竭如果序号的使用没有控制在合理范围内系统可能会迅速消耗掉所有可用的序号这样会导致新的请求无法被处理因为没有足够的序号可用。性能问题不合适的序号管理可能会影响系统的性能特别是当系统需要频繁地调整这些水线时可能会造成额外的开销。检查之前是否接收过相同序号n和v但是不同摘要d的消息确保消息的唯一性。副本收到2f1包括自己个一致的PREPARE消息后会进入COMMIT阶段并且广播消息 COMMIT, v, n, D(m), i 给集群中的其它节点。在收到PREPARE消息后副本同样也会对消息进行有效性检查检查的内容是上条的1, 2, 3。副本收到2f1包括自己个一致的COMMIT个消息后执行m中包含的操作其中如果有多个m则按照序号n从小到大执行执行完毕后发送执行成功的消息给客户端。日志压缩解决内存问题这种压缩方式采用的是“快照”的方法。Pbft为常数个操作创建一次稳定检查点比如每100个操作创建一次检查点而这个检查点就是checkpoint当这个checkpoint得到集群中多数节点认可以后就变成了稳定检查点stable checkpoint。当节点i生成checkpoint后会广播消息CHECKPOINT, n, d, i其中n是最后一次执行的消息序号d是n执行后的状态机状态的摘要。每个节点收到2f1个相同n和d的checkpoint消息以后checkpoint就变成了stable checkpoint。同时删除本地序号小于等于n的消息。同时checkpoint还有一个提高水线water mark的作用当一个stable checkpoint被创建的时候水线h被修改为stable checkpoint的n水线H为h k而k就是之前用到创建checkpoint的那个常数。视图切换解决主机宕机view-change提供了一种当主节点宕机以后依然可以保证集群可用性的机制。view-change通过计时器来进行切换避免副本长时间的等待请求。当副本收到请求时就启动一个计时器如果这个时候刚好有定时器在运行就重置reset定时器但是主节点宕机的时候副本i就会在当前视图v中超时这个时候副本i就会触发view-change的操作将视图切换为v1。副本 i 会停止接收除了 checkpointview-change和new view-change以外的请求同时广播消息 VIEW-CHANGE, v1, n, C, P, i 的消息到集群。n是节点i知道的最后一个stable checkpoint的消息序号。C是节点i保存的经过2f1个节点确认stable checkpoint消息的集合。P是一个保存了n之后所有已经达到prepared状态消息的集合。当在视图( v1 )中的主节点p1接收到2f个有效的将视图变更为v1的消息以后p1就会广播一条消息NEW-VIEW, v1, V, QV是p1收到的包括自己发送的view-change的消息集合。Q是PRE-PREPARE状态的消息集合但是这个PRE-PREPARE消息是从PREPARE状态的消息转换过来的。从节点接收到NEW-VIEW消息后校验签名V和Q中的消息是否合法验证通过主节点和副本都 进入视图v1。当p1在接收到2f1个VIEW-CHANGE消息以后可以确定stable checkpoint之前的消息在视图切换的过程中不会丢但是当前检查点之后下一个检查点之前的已经PREPARE可能会被丢弃在视图切换到v1后Pbft会把旧视图中已经PREPARE的消息变为PRE-PREPARE然后新广播。如果集合P为空广播PRE-PREPARE, v1, n, null接收节点就什么也不做。如果集合P不为空广播PRE-PREPARE, v1, n,d总结一下在view-change中最为重要的就是CPQ三个消息的集合C确保了视图变更的时候stable checkpoint之前的状态安全。P确保了视图变更前已经PREPARE的消息的安全。Q确保了视图变更后P集合中的消息安全。回想一下pre-prepare和prepare阶段最重要的任务是保证同一个主节点发出的请求在同一个视图view中的顺序是一致的而在视图切换过程中的CPQ三个集合就是解决这个问题的。主动恢复集群在运行过程中可能出现网络抖动、磁盘故障等原因会导致部分节点的执行速度落后大多数节点而传统的PBFT拜占庭共识算法并没有实现主动恢复的功能因此需要添加主动恢复的功能才能参与后续的共识流程主动恢复会索取网络中其他节点的视图最新的区块高度等信息更新自身的状态最终与网络中其他节点的数据保持一致。在Raft中采用的方式是主节点记录每个跟随者提交的日志编号发送心跳包时携带额外信息的方式来保持同步在Pbft中采用了视图协商NegotiateView的机制来保持同步。一个节点落后太多这个时候它收到主节点发来的消息时对消息水线water mark的检查会失败这个时候计时器超时发送view-change的消息但是由于只有自己发起view-change达不到2f1个节点的数量本来正常运行的节点就退化为一个拜占庭节点尽管是非主观的原因为了尽可能保证集群的稳定性所以加入了视图协商NegotiateView机制。当一个节点多次view-change失败就触发NegotiateView同步集群数据流程如下新增节点Replica 4发起NegotiateView消息给其他节点其余节点收到消息以后返回自己的视图信息节点ID节点总数NReplica 4收到2f1个相同的消息后如果quorum个视图编号和自己不同则同步view和NReplica 4同步完视图后发送RevoeryToCheckpoint的消息其中包含自身的checkpoint信息其余节点收到RevoeryToCheckpoint后将自身最新的检查点信息返回给Replica 4;Replica 4收到quorum个消息后更新自己的检查点到最新更新完成以后向正常节点索要pset、qset和cset的信息即PBFT算法中pre-prepare阶段、prepare阶段和commit阶段的数据同步至全网最新状态增删节点解决成员加入或者删除的问题Replica 5新节点加入的流程如下图所示新节点启动以后向网络中其他节点建立连接并且发送AddNode消息当集群中的节点收到AddNode消息后会广播AgreeAdd的消息当一个节点收到2f1个AgreeAdd的消息后会发送AgreeAdd的消息给Replica 5Replica 5会从收到的消息中挑选一个节点同步数据具体的过程在主动恢复中有说明同步完成以后发送JoinNet当集群中其他节点收到JoinNet之后重新计算视图view节点总数N同时将PQC信息封装到AgreeJoinOrExit中广播当收到2f1个有效的AgreeJoinOrExit后新的主节点广播UpdateNet消息完成新增节点流程删除节点的流程和新增节点的过程类似问题Q为什么PBFT算法需要三个阶段 A假如简化为两个阶段pre-prepare和prepare当一个节点A收到2f1个相同的prepare后执行请求一部分节点B发生view-change在view-change的过程中是拒收prepare消息的所以这一部分节点的状态机会少执行一个请求当view-change切换成功后重放prepare消息在重放的过程中节点A也完成了view-change这个时候A就会面临重放的prepare已经执行过了是否需要再次执行会导致状态机出现二义性。Qview-change阶段集群会不可用么 Aview-change阶段集群会出现短暂的不可用一般在实践的时候都会实现一个缓冲区来减少影响实现参考 以太坊TXpool分析。QPbft算法的时间复杂度 APbft算法的时间复杂度O(n^2)在prepare和commit阶段会将消息广播两次一般而言Pbft集群中的节点都不会超过100。Pow算法———增加恶意节点的成本由于上面的PBFT算法在节点增多到一定程度时就很难继续维持系统的一致性因此在区块链网络的创建之初创建者创造性的提出了PoW算法。PoW算法使得每个需要广播公认信息的节点需要付出海量的代价因此其原始意愿上就不倾向于去破坏系统的安全性实现这个算法并不是依靠技术上的革新反而像是商业模式上的变化。PoW共识机制的特点维持PoW算法的三个闭环元素系统的安全性 获得奖励的激励 破坏系统的代价下图展示了为什么PoW算法能够使得更多的人投入挖矿这是一个由原始利益驱动的机制PoW算法必须与链式结构结合PoW算法使得共识达成只需要单轮通信大大节省了通信成本PoS算法从PoW到PoS以太坊在2014年开始了长达8年的pos研究之旅2020年以太坊上线了信标链 beacon chain并在这个链上尝试做一些pos的实验2022年9月15日将信标链与以太坊主链合并至此完成了以太坊的升级宣告了pow时代的结束。具体的流程分为三个阶段在主链之外独立建设一条信标链 beacon chain在这条链上进行PoS实验合并阶段1旧主链作为“执行层”信标链作为“共识层”融合之后进入以太坊PoS时代后续通过分片扩容提高rollup拓展性等等Gasper以下主要讨论信标链使用的共识和算法。以太坊选择的算法叫做Casper FFG在此基础上引入另一个规则LMD-GHOST他们共同组成了信标链的PoS算法Gasper其中前者是一种投票选择的规定后者用于分叉情况的处理。PoS共识算法有很多种以太坊选择的是Casper FFG投票过程用户通过质押32个eth成为一名验证者validator,相当于获得了投票的权利。为了解决节点通信量大的问题以太坊做了一些时间层次的划分。如图一个slot插槽代表一个出块时间这个时间是12秒32个slot组成一个Epoch纪元代表一个大周期时间为6m24s在这一点上pos的出块稳定程度是高于pow的。接下来将会随机选择一名验证者去发起一个区块提议propose由它去出块。同时其它的验证者会组成一个人数≥128委员会(committee),委员会通过投票来确认区块整个过程由一个伪随机算法RANDAO选出RANDAO算法比较复杂可以先简单理解为一个黑盒。Casper FFGCasper这种pos算法其实都是bft类型的容错算法它由pbft共识算法改进而来。因此我们根据上文“PBFT算法实现流程”可以得到——要实现一轮“视图”需要进行两轮投票分别在prepare和commit阶段。这个算法的优点是只要达成共识这个节点就是合法存在的不想BTC里面需要等待6个节点之后确认链不会出现分叉现象然而由于PBFT算法的局限性我们很难做到在大规模超多节点网络中应用这一共识机制。Casper算法就兼容优点并改善了缺点。在“投票过程”中我们将一个区块时间定为一个slot下图中的小块32个slot就是一个Epoch一个Epoch作为一个被投票的整体。最终的敲定分为两个阶段对于每一个Epoch而言会接受先后两次投票两次均通过才为通过我们以下图为例进行讲解上面的链是从下向上挖的对于Epoch0而言当链挖到第32个的时候大家投票认证 Epoch0如果这次通过被2/3以上的节点认可那么Epoch0将会从提交状态进入认证状态justified这次投票之后我们开挖的就是 Epoch1。当达到第64个区块时进入检查点节点将对 Epoch0和 Epoch1进行投票被2/3以上的节点认可如果通过Epoch1将会从提交状态进入认证状态justified而Epoch0将会从认证状态justified进入终局性状态finalized这时Epoch0就被达成了共识不需要之后参与讨论了。下面是一个正在讨论的Epoch分叉选择 LMD-GHOST由于网络延迟或者潜在攻击的问题新的区块产生可能会发生分叉这时我们选择的策略就叫LMD最新的消息驱动我们会选择票数最多权重的链作为权威链这一点区分于pow中的最长链原则。下图的一个笑脸代表一个验证者投票我们选择笑脸最多的链作为合法链虽然比上面的分叉少一个区块但它的票数多代表认可多。和Casper FFG看上去很相似。Casper FFG是以32个区块为单位进行的整体投票的是一个单纯的验证方案而LMD-GHOST算法是在“挖矿”过程中处理区块间分叉的方案。LMD-GHOST处理的是短时间局部分歧而Casper FFG处理的是长期共识问题。
区块链基础通识（1）——分布式系统的共识问题
分布式系统我们最初了解区块链的时候很多人会形容这个区块链是一个“分布式的不可篡改账本”这是一个很形象的说法但是我认为更为准确的形容是“所有节点共同维护的状态机”。为什么分布式和区块链不能划等号呢两种常见的分布式模型中心化网络Client-Server去中心化网络P2P交互方式用户只能和服务器交互用户之间可以交互优缺点通讯速度快客户端需要存储的信息量少响应稳定相对垄断相对自由通讯难度随着用户数量成指数级上升涉及分布式问题非拜占庭问题只存在节点挂机情况拜占庭问题存在干扰一致性的恶意节点图例中心化网络的请求模型属于是网状模型并没有一个节点获取所有流量获取和自身不相干的流量也只用于校验或转发去中心化模型的请求模型有一个中心服务器集群承担所有流量的转发比较和联系对比上述两个图我们很容易发现——去中心化的通信方式每个节点需要保存的”通信信道“是超多的因此这种模型无法适应大量的节点参与我们拿”微信“来举一个例子。微信的交流虽然看起来是点对点的C2C结构但是实际上是用户请求云服务器来实现的信息交流的。以“种子网络“为例在其发展初期存在的节点到其后期均被暴风影音等节点垄断。可以看出去中心化向中心化演变是一个自然的趋势。所以我们通常的中心化分布式系统是一个”有超强中心节点的系统“在这个系统中只要服务器不挂机就是正常运行的不存在恶意节点破坏一致性问题因为只有服务器自己说了算而区块链涉及的分布式问题往往是有恶意节点存在的这样的问题被称为“拜占庭将军问题”拜占庭将军问题背景在网络上的节点分为恶意节点目的是扰乱一致性和故障节点挂机。拜占庭问题解决的是拥有恶意节点的问题拥有故障节点的成为“非拜问题”首先我们来补充一下分布式账本的节点问题。拜占庭问题是由兰波特提出的为了解决这个问题采用了从理想化的“口头协议”--解决网络延时的“PBFT算法”--区块链使用的“PoW机制”问题本身拜占庭帝国派出多支军队进攻一个城池这个城池十分坚固一支部队无法攻克但是多支军队一起攻打即可攻克。现在将军中有叛徒他的目的是使得忠诚的部队行动不一致叛徒的目的是为了扰乱系统的一致性。这个问题有解的前提是n(总节点个数)3m(恶意节点个数)。问题解法最初的解决方法——口头协议这个解法使用的模型叫做将军-副官模型在这个模型的要求下所有的节点都可以是将军也都可以是副官我们将第一个发送命令的节点叫做将军其余的叫做副官值得注意的是副官与副官之间也可以通信所有节点需要遵守两个规则忠诚的副官们会遵守同一个命令若将军忠诚则所有的副官会遵守他的命令下面我们看一下最基础m1、n4的情况副官中出现叛徒首先我们将“将军”发布的命令称为A即副官1副官2副官叛徒3收到的将军命令都是A这时副官1会询问另外两个副官得到副官2的“将军给的是命令A”以及叛徒3给的“将军给的命令是B”B是假消息的回答因此副官1按照少数服从多数原则推断出3是叛徒A是一致性命令。副官2同理将军是叛徒叛徒将军向副官1、2、3分别发送命令A、B、C叛徒是为了扰乱一致性的副官1接到A命令后会联系2、3得到副官2的“将军给的是命令B”以及副官3给的“将军给的命令是C”这时候副官1可以推断出将军是叛徒同时放弃这一轮的命令要求的第二条不成立副官2、3同理复杂情况以m2,n7为例这种方法要注意以下两点签名也就是一个人发布命令的时候需要加上自己的签名转述别人的信息的时候需要加上他的签名这是为了保证信息的唯一性比如上文情况中我使用的“副官说‘将军的命令是......’”这一说法每个节点使用表格进行决策这是一种递归嵌套的思想下面表格展示的每行指的是节点的决策信息纵列是节点给别人的应答,假设将军给出的命令是AV1给出的应答V2给出的应答V3给出的应答V4给出的应答V5给出的应答V6给出的应答V1AAAbfV2AAAcgV3AAAdhV4AAAei上述的小写字母指的是随即命令善意节点依照少数多数的原则可以推断出结果在这里不展开叙述通信次数我们简单的计算一下上面两种模型的通讯次数发现当存在四个节点中一个恶意节点时的通讯次数为9次七个节点中存在两个恶意节点的通讯次数为36次因此这种方法的算法复杂度随着节点数以指数级上升是一种很不明智的算法。而下面要介绍的PBFT算法就将这种复杂度降到了多项式级。用通讯次数换取安全性——PBFT算法和“口头协议”一样PBFT算法也是使用通讯次数换取安全性这样的原理也决定了它只能在小范围中使用实际生产中的应用场景往往是联盟链。简介PBFT算法中节点只有两种角色主节点primary和副本replica两种角色之间可以相互转换。两者之间的转换又引入了视图view的概念视图在PBFT算法中起到逻辑时钟的作用。算法实现流程算法开始的时候使用随机数或者一定的顺序得到主节点首先客户端发送消息m给主节点p主节点就开始了PBFT三阶段协议三个阶段分别是预准备pre-prepare准备prepare提交commit。其中pre-prepare和prepare阶段最重要的任务是保证同一个主节点发出的请求在同一个视图view中的顺序是一致的prepare和commit阶段最重要的任务是保证请求在不同视图之间的顺序是一致的。算法的流程图如下在这个周期中C指客户端节点0指主节点1、2指正常副本3指掉线副本主节点收到客户端发送来的消息后构造pre-prepare消息结构体 PRE-PREPARE, v, n, d, m 广播到集群中的其它节点。PRE-PREPARE标识当前消息所处的协议阶段v表示当前视图编号n为主节点广播消息的一个唯一递增序号d为m的消息摘要m为客户端发来的消息这里面的“摘要”也就是对于客户端消息进行的哈希压缩副本(backup)收到主节点请求后会对消息进行检查检查通过会存储在本节点。当节点收到2f1包括自己个相同的消息后会进入PREPARE状态广播消息 PREPARA, v, n, d, i 其中i是本节点的编号。对消息的有效性有如下检查也就是满足超2/3节点达成共识检查收到的消息体中摘要d是否和自己对m生成的摘要一致确保消息的完整性。检查v是否和当前视图v一致保证消息存在于同一周期。检查序号n是否在水线h和H之间避免快速消耗可用序号h是当前的安全水线safety waterline表示系统中可以接受的最低序号H是当前的高水线high waterline表示系统中可以接受的最高序号n需要在这两个水线之间即h n H主要是为了避免以下问题序号枯竭如果序号的使用没有控制在合理范围内系统可能会迅速消耗掉所有可用的序号这样会导致新的请求无法被处理因为没有足够的序号可用。性能问题不合适的序号管理可能会影响系统的性能特别是当系统需要频繁地调整这些水线时可能会造成额外的开销。检查之前是否接收过相同序号n和v但是不同摘要d的消息确保消息的唯一性。副本收到2f1包括自己个一致的PREPARE消息后会进入COMMIT阶段并且广播消息 COMMIT, v, n, D(m), i 给集群中的其它节点。在收到PREPARE消息后副本同样也会对消息进行有效性检查检查的内容是上条的1, 2, 3。副本收到2f1包括自己个一致的COMMIT个消息后执行m中包含的操作其中如果有多个m则按照序号n从小到大执行执行完毕后发送执行成功的消息给客户端。日志压缩解决内存问题这种压缩方式采用的是“快照”的方法。Pbft为常数个操作创建一次稳定检查点比如每100个操作创建一次检查点而这个检查点就是checkpoint当这个checkpoint得到集群中多数节点认可以后就变成了稳定检查点stable checkpoint。当节点i生成checkpoint后会广播消息CHECKPOINT, n, d, i其中n是最后一次执行的消息序号d是n执行后的状态机状态的摘要。每个节点收到2f1个相同n和d的checkpoint消息以后checkpoint就变成了stable checkpoint。同时删除本地序号小于等于n的消息。同时checkpoint还有一个提高水线water mark的作用当一个stable checkpoint被创建的时候水线h被修改为stable checkpoint的n水线H为h k而k就是之前用到创建checkpoint的那个常数。视图切换解决主机宕机view-change提供了一种当主节点宕机以后依然可以保证集群可用性的机制。view-change通过计时器来进行切换避免副本长时间的等待请求。当副本收到请求时就启动一个计时器如果这个时候刚好有定时器在运行就重置reset定时器但是主节点宕机的时候副本i就会在当前视图v中超时这个时候副本i就会触发view-change的操作将视图切换为v1。副本 i 会停止接收除了 checkpointview-change和new view-change以外的请求同时广播消息 VIEW-CHANGE, v1, n, C, P, i 的消息到集群。n是节点i知道的最后一个stable checkpoint的消息序号。C是节点i保存的经过2f1个节点确认stable checkpoint消息的集合。P是一个保存了n之后所有已经达到prepared状态消息的集合。当在视图( v1 )中的主节点p1接收到2f个有效的将视图变更为v1的消息以后p1就会广播一条消息NEW-VIEW, v1, V, QV是p1收到的包括自己发送的view-change的消息集合。Q是PRE-PREPARE状态的消息集合但是这个PRE-PREPARE消息是从PREPARE状态的消息转换过来的。从节点接收到NEW-VIEW消息后校验签名V和Q中的消息是否合法验证通过主节点和副本都 进入视图v1。当p1在接收到2f1个VIEW-CHANGE消息以后可以确定stable checkpoint之前的消息在视图切换的过程中不会丢但是当前检查点之后下一个检查点之前的已经PREPARE可能会被丢弃在视图切换到v1后Pbft会把旧视图中已经PREPARE的消息变为PRE-PREPARE然后新广播。如果集合P为空广播PRE-PREPARE, v1, n, null接收节点就什么也不做。如果集合P不为空广播PRE-PREPARE, v1, n,d总结一下在view-change中最为重要的就是CPQ三个消息的集合C确保了视图变更的时候stable checkpoint之前的状态安全。P确保了视图变更前已经PREPARE的消息的安全。Q确保了视图变更后P集合中的消息安全。回想一下pre-prepare和prepare阶段最重要的任务是保证同一个主节点发出的请求在同一个视图view中的顺序是一致的而在视图切换过程中的CPQ三个集合就是解决这个问题的。主动恢复集群在运行过程中可能出现网络抖动、磁盘故障等原因会导致部分节点的执行速度落后大多数节点而传统的PBFT拜占庭共识算法并没有实现主动恢复的功能因此需要添加主动恢复的功能才能参与后续的共识流程主动恢复会索取网络中其他节点的视图最新的区块高度等信息更新自身的状态最终与网络中其他节点的数据保持一致。在Raft中采用的方式是主节点记录每个跟随者提交的日志编号发送心跳包时携带额外信息的方式来保持同步在Pbft中采用了视图协商NegotiateView的机制来保持同步。一个节点落后太多这个时候它收到主节点发来的消息时对消息水线water mark的检查会失败这个时候计时器超时发送view-change的消息但是由于只有自己发起view-change达不到2f1个节点的数量本来正常运行的节点就退化为一个拜占庭节点尽管是非主观的原因为了尽可能保证集群的稳定性所以加入了视图协商NegotiateView机制。当一个节点多次view-change失败就触发NegotiateView同步集群数据流程如下新增节点Replica 4发起NegotiateView消息给其他节点其余节点收到消息以后返回自己的视图信息节点ID节点总数NReplica 4收到2f1个相同的消息后如果quorum个视图编号和自己不同则同步view和NReplica 4同步完视图后发送RevoeryToCheckpoint的消息其中包含自身的checkpoint信息其余节点收到RevoeryToCheckpoint后将自身最新的检查点信息返回给Replica 4;Replica 4收到quorum个消息后更新自己的检查点到最新更新完成以后向正常节点索要pset、qset和cset的信息即PBFT算法中pre-prepare阶段、prepare阶段和commit阶段的数据同步至全网最新状态增删节点解决成员加入或者删除的问题Replica 5新节点加入的流程如下图所示新节点启动以后向网络中其他节点建立连接并且发送AddNode消息当集群中的节点收到AddNode消息后会广播AgreeAdd的消息当一个节点收到2f1个AgreeAdd的消息后会发送AgreeAdd的消息给Replica 5Replica 5会从收到的消息中挑选一个节点同步数据具体的过程在主动恢复中有说明同步完成以后发送JoinNet当集群中其他节点收到JoinNet之后重新计算视图view节点总数N同时将PQC信息封装到AgreeJoinOrExit中广播当收到2f1个有效的AgreeJoinOrExit后新的主节点广播UpdateNet消息完成新增节点流程删除节点的流程和新增节点的过程类似问题Q为什么PBFT算法需要三个阶段 A假如简化为两个阶段pre-prepare和prepare当一个节点A收到2f1个相同的prepare后执行请求一部分节点B发生view-change在view-change的过程中是拒收prepare消息的所以这一部分节点的状态机会少执行一个请求当view-change切换成功后重放prepare消息在重放的过程中节点A也完成了view-change这个时候A就会面临重放的prepare已经执行过了是否需要再次执行会导致状态机出现二义性。Qview-change阶段集群会不可用么 Aview-change阶段集群会出现短暂的不可用一般在实践的时候都会实现一个缓冲区来减少影响实现参考 以太坊TXpool分析。QPbft算法的时间复杂度 APbft算法的时间复杂度O(n^2)在prepare和commit阶段会将消息广播两次一般而言Pbft集群中的节点都不会超过100。Pow算法———增加恶意节点的成本由于上面的PBFT算法在节点增多到一定程度时就很难继续维持系统的一致性因此在区块链网络的创建之初创建者创造性的提出了PoW算法。PoW算法使得每个需要广播公认信息的节点需要付出海量的代价因此其原始意愿上就不倾向于去破坏系统的安全性实现这个算法并不是依靠技术上的革新反而像是商业模式上的变化。PoW共识机制的特点维持PoW算法的三个闭环元素系统的安全性 获得奖励的激励 破坏系统的代价下图展示了为什么PoW算法能够使得更多的人投入挖矿这是一个由原始利益驱动的机制PoW算法必须与链式结构结合PoW算法使得共识达成只需要单轮通信大大节省了通信成本PoS算法从PoW到PoS以太坊在2014年开始了长达8年的pos研究之旅2020年以太坊上线了信标链 beacon chain并在这个链上尝试做一些pos的实验2022年9月15日将信标链与以太坊主链合并至此完成了以太坊的升级宣告了pow时代的结束。具体的流程分为三个阶段在主链之外独立建设一条信标链 beacon chain在这条链上进行PoS实验合并阶段1旧主链作为“执行层”信标链作为“共识层”融合之后进入以太坊PoS时代后续通过分片扩容提高rollup拓展性等等Gasper以下主要讨论信标链使用的共识和算法。以太坊选择的算法叫做Casper FFG在此基础上引入另一个规则LMD-GHOST他们共同组成了信标链的PoS算法Gasper其中前者是一种投票选择的规定后者用于分叉情况的处理。PoS共识算法有很多种以太坊选择的是Casper FFG投票过程用户通过质押32个eth成为一名验证者validator,相当于获得了投票的权利。为了解决节点通信量大的问题以太坊做了一些时间层次的划分。如图一个slot插槽代表一个出块时间这个时间是12秒32个slot组成一个Epoch纪元代表一个大周期时间为6m24s在这一点上pos的出块稳定程度是高于pow的。接下来将会随机选择一名验证者去发起一个区块提议propose由它去出块。同时其它的验证者会组成一个人数≥128委员会(committee),委员会通过投票来确认区块整个过程由一个伪随机算法RANDAO选出RANDAO算法比较复杂可以先简单理解为一个黑盒。Casper FFGCasper这种pos算法其实都是bft类型的容错算法它由pbft共识算法改进而来。因此我们根据上文“PBFT算法实现流程”可以得到——要实现一轮“视图”需要进行两轮投票分别在prepare和commit阶段。这个算法的优点是只要达成共识这个节点就是合法存在的不想BTC里面需要等待6个节点之后确认链不会出现分叉现象然而由于PBFT算法的局限性我们很难做到在大规模超多节点网络中应用这一共识机制。Casper算法就兼容优点并改善了缺点。在“投票过程”中我们将一个区块时间定为一个slot下图中的小块32个slot就是一个Epoch一个Epoch作为一个被投票的整体。最终的敲定分为两个阶段对于每一个Epoch而言会接受先后两次投票两次均通过才为通过我们以下图为例进行讲解上面的链是从下向上挖的对于Epoch0而言当链挖到第32个的时候大家投票认证 Epoch0如果这次通过被2/3以上的节点认可那么Epoch0将会从提交状态进入认证状态justified这次投票之后我们开挖的就是 Epoch1。当达到第64个区块时进入检查点节点将对 Epoch0和 Epoch1进行投票被2/3以上的节点认可如果通过Epoch1将会从提交状态进入认证状态justified而Epoch0将会从认证状态justified进入终局性状态finalized这时Epoch0就被达成了共识不需要之后参与讨论了。下面是一个正在讨论的Epoch分叉选择 LMD-GHOST由于网络延迟或者潜在攻击的问题新的区块产生可能会发生分叉这时我们选择的策略就叫LMD最新的消息驱动我们会选择票数最多权重的链作为权威链这一点区分于pow中的最长链原则。下图的一个笑脸代表一个验证者投票我们选择笑脸最多的链作为合法链虽然比上面的分叉少一个区块但它的票数多代表认可多。和Casper FFG看上去很相似。Casper FFG是以32个区块为单位进行的整体投票的是一个单纯的验证方案而LMD-GHOST算法是在“挖矿”过程中处理区块间分叉的方案。LMD-GHOST处理的是短时间局部分歧而Casper FFG处理的是长期共识问题。
