# pbft **Repository Path**: bingoer/pbft ## Basic Information - **Project Name**: pbft - **Description**: pbft算法 - **Primary Language**: Go - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 7 - **Created**: 2020-03-13 - **Last Updated**: 2022-04-05 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README ## 什么是共识机制？ 区块链从本质上来说是一个分布式数据库，而在区块链的网络中，每个节点都会保有一份完整的账本，且所有节点的账本内容完全一致。当然，存在一些SPV等轻节点并不是保存完整的账本，每个节点都可以根据自己本地的账本去查找交易，也可以往账本中添加交易。 那么在这个分布式系统当中谁来更新数据，如果所有的节点都按照自己的方式更新数据，那么账本数据肯定会不一致。那么需要一种机制保证账本状态的更新，而且所有的节点都一致认同这种更新方式。那么这种机制就是共识机制 从单个数据来看，多个节点对某个数据达成一致共识。从多个数据来看，即多个节点对多个数据的顺序达成一致共识。 ## 拜占庭将军问题 拜占庭将军问题本质是一个解释一致性问题的一个虚构模型。 一组拜占庭将军分别各率领一支军队共同围困一座城市。为了简化问题，将各支军队的行动策略限定为进攻或撤离两种。因为部分军队进攻部分军队撤离可能会造成灾难性后果，因此各位将军必须通过投票来达成一致策略，即所有军队一起进攻或所有军队一起撤离。因为各位将军分处城市不同方向，他们只能通过信使互相联系。在投票过程中每位将军都将自己投票给进攻还是撤退的信息通过信使分别通知其他所有将军，这样一来每位将军根据自己的投票和其他所有将军送来的信息就可以知道共同的投票结果而决定行动策略。 系统的问题在于，将军中可能出现叛徒，他们不仅可能向较为糟糕的策略投票，还可能选择性地发送投票信息。假设有9位将军投票，其中1名叛徒。8名忠诚的将军中出现了4人投进攻，4人投撤离的情况。这时候叛徒可能故意给4名投进攻的将领送信表示投票进攻，而给4名投撤离的将领送信表示投撤离。这样一来在4名投进攻的将领看来，投票结果是5人投进攻，从而发起进攻；而在4名投撤离的将军看来则是5人投撤离。这样各支军队的一致协同就遭到了破坏。 由于将军之间需要通过信使通讯，叛变将军可能通过伪造信件来以其他将军的身份发送假投票。而即使在保证所有将军忠诚的情况下，也不能排除信使被敌人截杀，甚至被敌人间谍替换等情况。因此很难通过保证人员可靠性及通讯可靠性来解决问题。 假始那些忠诚（或是没有出错）的将军仍然能通过多数决定来决定他们的战略，便称达到了拜占庭容错。在此，票都会有一个默认值，若消息（票）没有被收到，则使用此默认值来投票。 上述的故事映射到计算机系统里，将军便成了计算机，而信差就是通信系统。虽然上述的问题涉及了电子化的决策支持与信息安全，却没办法单纯的用密码学与数字签名来解决。因为电路错误仍可能影响整个加密过程，这不是密码学与数字签名算法在解决的问题。因此计算机就有可能将错误的结果提交去，亦可能导致错误的决策 在分布式系统中，不是所有的缺陷或故障都能称作拜占庭缺陷或故障。像死机、丢消息等缺陷或故障不能算为拜占庭缺陷或故障。拜占庭缺陷或故障是最严重缺陷或故障，拜占庭缺陷有不可预测、任意性的缺陷，例如遭黑客破坏，中木马的服务器就是一个拜占庭服务器。 拜占庭问题之所以难解，在于任何时候系统中都可能存在多个提案（因为提案成本很低），并且在大规模场景下要完成最终确认的过程容易受干扰，难以达成共识。 比特币网络在设计时使用了 PoW（Proof of Work）的概率型算法思路，从如下两个角度解决大规模场景下的拜占庭容错问题。 ``` 首先，限制一段时间内整个网络中出现提案的个数（通过工作量证明来增加提案成本）； 其次是丢掉最终确认的约数，约定好始终沿着已知最长的链进行拓展。共识的最终确认是概率意义上的存在。 ``` ## CFT CFT是指只支持crash节点不支持容错节点。 ## PBFT算法原理 请求来了，先让系统中的主节点进行排序，分发给所有的从节点，保证至少f+1个正确节点达成一致，那么顺序执行该请求，结果返回给客户端。 ## N >= 3f + 1 谈到 N >= 3f+1 我们常说的就是当f个容错节点存在时，我们总共需要多少个节点才能确保达成共识。或者说当总节点数为N时，最多能容忍多少个错误节点 pbft算法的容错是指对作恶节点的容错。因为已经假设了f个故障，那么最好情况下是f=0,最坏情况是确实存在f（不等于0）个故障节点f个节点都是恶意节点，PBFT在保证安全性和可用性的前提下，提供了 (n-1)/3 的容错性 PBFT算法的共识也是少数服从多数，总共有n个节点，达成共识的依据也是正确的结果的个数大于错误的结果个数，f个错误的节点，那么可以接受到n-f个消息，因为我们在设计异步通信算法的时候，我们不知道那f个节点是恶意节点还是故障节点，这f个节点可以不发送消息，也可以发送错误的消息，所以在设计临界值的时候，我们要保证必须在n-f个状态复制机的沟通内，就要做出决定，因为如果阈值设置为需要n-f+1个消息，那么如果这f个作恶节点全部不回应，那这个系统根本无法运作下去） 但是当f个节点中有恶意节点,或者说是最坏情况下所有假设的f个故障节点都是恶意节点,接受到的n-f个消息之后可能最多包含有f个恶意节点发送的消息，因为f个恶意节点是墙头草，可能给你这个节点发送正确消息，给别的节点发送错误消息，那么他发送的消息不可靠，正确的消息个数大于错误的消息个数才能达成共识，n-f-f > f ，也就是n > 3f。 这也就是我们为什么在去确认消息的时候需要接受到2f+1个消息才能确保至少f+1个节点 ## 为什么通常假设系统中节点数 n = 3f + 1,而不是更多 因为假设系统中的数量为m,我们只需要3f + 1个总结点就能达成共识，我们可以有更多的正常节点，但是额外的副本除了降低性能之外不能提高可靠性。 ## 为什么有prepare阶段和commit阶段广播 primary发送一个区块，备份节点收到区块后，老大给我们发区块了，你们收到没有，如果收到了2f+1（包括自身）来自其他节点的区块，那么知道其他节点也收到了区块，因为每一次最终的上链不能只是单个节点的上链，最起码需要保证f+1个正确节点上链，也就是大于错误节点的个数，prepare阶段只能保证自己确认其他节点也收到老大发的区块，但是不能保证其他节点也确认了,我需要保证整个系统中不仅仅是我这个节点，总共还有f+1个节点确认了消息。所以需要再次广播一条commit消息。节点收到2f+1（包括自身）个commit节点就能确保至少f+1个正常节点收到区块，那么就可以执行交易上链了 ## PBFT对副本状态机的的条件限制 状态机的复制技术前提，副本必须满足两个条件，副本必须是确定性的， ``` 开始在相同的状态 收到相同参数及操作那么必须得到相同的结果。 ``` 这个确保了所有的节点在处理相同的请求时会获得一样的结果。 ## 谁是主节点 PBFT算法的主节点怎么产生，论文中 p = V mod 节点总数随机产生。 在raft算法中主要有leader和follower两种角色。当然还有投票者这个角色，这不是重点 对应的PBFT算法中也有主节点和备份节点两种模式，对于leader选举这块。 raft算法本质是谁快谁当选，详细可以参考 [raft动画](http://thesecretlivesofdata.com/raft/)。 pbft算法是按编号依次轮流做主节点。一个团队一定会有一个老大和普通成员。 对于raft算法，共识过程就是：只要老大还没挂，老大说什么，我们（团队普通成员）就做什么，坚决执行。那什么时候重新选老大呢？只有当老大挂了才重选老大，不然生是老大的人，死是老大的鬼。 对于pbft算法，共识过程就是：老大向我发送命令时，当我认为老大的命令是有问题时，我会拒绝执行。就算我认为老大的命令是对的，我还会问下团队的其它成员是否老大的命令是对的，只有大多数人（2f+1）包括自身都认为老大的命令是对的时候，我才会去执行命令。那什么时候重选老大呢？老大挂了当然要重选，如果大多数人都认为老大不称职或者有问题时，我们也会重新选择老大。 raft算法从节点不会拒绝主节点的请求，而pbft算法从节点在某些情况下会拒绝主节点的请求 ; raft算法只能容错故障节点，并且最大容错节点数为（n-1）/2，而pbft算法能容错故障节点和作恶节点，最大容错节点数为（n-1）/3。 ## PBFT算法整体思路 基本过程 ```go 客户端发送请求给主节点，这边可能会有一个服务器的中转负责接收消息和回复客户端消息，接受请求和接受处理都是现在本节点进行中转。 主节点广播请求给其它节点，节点执行 pbft 算法的三阶段共识流程。 节点处理完三阶段流程后，返回消息给客户端。 客户端收到来自 f+1 个节点的相同消息后，代表共识已经正确完成。 ``` ## 客户端 客户端的请求中的时间戳标记了每一次请求。时间戳是经常被用来排序的一个事物，后续的请求会有更高的时间戳。可以是当请求发生时的时间 ## REQUEST阶段： 客户端c向主节点p发送请求。 ```go o: 请求的具体操作， t: 请求时客户端追加的时间戳，用来保证客户端请求只会执行一次，客户端c发出请求的时间戳是全序排列的，后续发出的请求比早先发出的请求拥有更高的时间戳 c: 客户端标识。 REQUEST: 包含消息内容m，以及消息摘要d(m)。客户端对请求进行签名。 ``` 准备消息之前可能进行如下验证: ```js 维护一个请求序号，检查即将发出的请求的编号是不是在高低水线之间， 检查本节点是否已经收到过相同编号，但是摘要不同的pre-prepare请求，如果是则拒绝处理,主要目的是为了防止之前接受到过这个消息，虽然这个节点现在是主节点，但是之前可能不是，防止之前从其他的主节点接受到过相同的消息。 检查是不是即将进入viewchange状态，也就是是不是将要更换主节点 看图我们会发现只有主节点才会发送pre-prepare消息，从节点收到请求后只是将其存在本地， 主节点收到客户端请求消息后向其他节点发送PrePrepareMsg消息视为进入了PRE-PREPARE状态 ``` ## 三阶段流程 ## Pre-prepare阶段: 主节点接受到请求后会对消息进行验证。主节点在接受到客户端发送的一条消息之后(这条消息可能是从网络收集到需放在新区块内的多个交易排序后存入列表，并将该列表向全网广播)，会给备份节点发送pre-prepare消息。主节点内播预准备消息《pre-prepare,v,n,d>,m>, 我们需要把pre-prepare消息和message消息都发送过去，但是pre-prepare消息中不包括message消息，因为pre-prepare消息可能作为很多条件的对比，加入message会增大pre-pare消息大小。 如果备份节点接受一个预准备消息，《pre-prepare,v,n,d>,m>,则它通过将PREPARE消息《prepare,v,n,d,i>多播到所有其他副本进入准备阶段。 否则，它什么都不做。 备份节点怎么确认一个pre-prepare消息 ``` 请求中的签名和预准备消息是正确的，并且是m的摘要 在视图v中之前不能接受到相同的v,序号n,但是摘要不同的消息，为了保证唯一性 消息序号n位于低水线和高水线之间 ``` 当该备份节点之前已经接收到了一条在同一view下并且编号也是n，但是digest不同的PRE-PREPARE信息时，就会拒绝,副本节点拒绝的原因可能是请求的序号不在高低水位（高低水位的概念稍后说明）之间。 如果一个备份节点accept了这条PRE-PREPARE，并将其存在本地，Pre-prepare 阶段就会完成，它就会进入下面的prepare阶段。 pre-prepare消息和prepare消息保存可以按照自己的 ## Prepare阶段 如果节点进入到Prepare阶段，那么此时他就向全网广播消息，同时自己也接收其他节点广播的prepare消息，在指定的超时时间内，一旦节点收到2f+1（包括自身）个不同节点的prepare，就代表 prepare 阶段已经完成，进入commit阶段。 副本（包括主副本）接受准备消息并将其添加到其日志中， ``` 前提是它们的签名正确， 它们的视图编号等于副本的当前视图， 它们的序列号介于低水线h和高水线H之间。 ``` 所有的节点怎么判断prepared消息的真假?可能要做的验证: ``` 忽略主节点发送的prepare消息,主节点不会发送prepare消息 检查请求的编号是否在高低水位间 检查此前是否已经收到过来自同一节点的prepare消息，如果收到过则忽略掉 把收到的prepare消息保存到集合中 ``` 当节点接受到2f+1个这样的prepared类型消息，也就是m,v，序号n都相同的preepare消息之后，那么他会和自己之前的加入到自己的日志的pre-pare消息进行对比，是否v,n，d都相同。确认完成prepare阶段，还没有向其他节点发送commit消息，向其他节点广播commit消息，自己也处理自己发出的的commit。 算法的预准备和准备阶段保证了非故障副本在视图中就请求的总顺序达成一致。也就保证了不可能确认（m,v,n,j）和（m1,v,n,i）这样两种消息。 怎么确认已经完成prepare阶段？ ``` 需要完成prepare阶段 存储数据中可以根据v,n找到该条记录 在容错节点是f,总节点数为N的前提下，至少收到2f条相同的prepare消息才表明prepare阶段完成了 ``` 当确认消息准备是正确的，开始广播《commit,v,n,D(m),i》消息，启动提交阶段 ## Commit 阶段： 进入 commit 阶段。 向其它节点广播 commit 消息，同理，这个过程可能是有 n 个节点也在进行的。因此可能会收到其它节点发过来的 commit 消息，当收到 2f+1 个 commit 消息后（包括自己），代表大多数节点已经完成commit 阶段，这一阶段已经达成共识，于是节点就会执行请求，写入数据。客户端如果收到f+1条相同的消息，那么就认为是正确的。 ``` 检查请求的编号是否在高低水位之间 如果节点此前已经收到过同一节点发送的同一请求的commit消息，忽略掉 保存收到的commit消息 ``` 怎么确认一个节点完成commit请求 ``` 需要完成prepare阶段 统计收到的commit消息的数量需要大于规定的2f 那么执行请求，将结果发送给客户端 ``` ## 响应 副本发送给客户端的每条消息都包含当前视图编号，允许客户端跟踪视图，从而跟踪当前主视图。 客户端使用点对点消息向其认为是当前主节点的请求发送请求 响应包括消息 ``` reply是消息类型 v是当前视图编号 t是之前请求的时间戳，这里时间戳t用来保证客户端请求只会执行一次 i是响应编号 r是响应结果 ``` ## 不依赖请求达成共识的顺序 确定好了每个请求的处理顺序，怎么能保证按照顺序执行呢？网络消息都是无序到达的，每个节点达成一致的顺序也是不一样的，有可能在某个节点上n比n-1先达成一致。其实每个节点都会把PRE-PREPARE、PREPARE和COMMIT消息缓存起来，它们都会有一个状态来标识现在处理的情况，然后再按顺序处理。 而且序列号n在不同view中也是连续的，所以n-1处理完了，处理n就好了，这也就表明了在new-view中广播的消息可以是不同的视图相同的n. ## 什么是checkpoint,watermark checkoupoint 检查点，类似于一个系统还原点，就是我这个节点的世界状态已经得到至少f+1个正常节点认可了，那么需要进行一次状态同步。 watermark指的是两个值h,H,这个值决定了节点可以处理序号在 h<=n<=H的请求。 为了节省内存，系统需要一种将日志中的无异议消息记录删除的机制 ## view view可以简单理解主节点和副本之间编号的一次快照，一个稳定的状态。 客户端会给主节点发送消息，主节点如果是宕机或者是作恶节点的话，为了监听主节点是否出现问题，引入了view的概念。 视图可以理解成主节点的任期，如果超过规定时间还没有响应，则从节点将怀疑现任主节点可能出现了问题，备份节点应当有职责来主动检查这些序号的合法性。如果主节点掉线或者作恶不广播客户端的请求，通过设置超时机制，超时的话，向所有副本节点广播请求消息。副本节点检测出主节点作恶或者下线，发起View Change协议。 ## 实用拜占庭系统需要三个基本协议 一致性协议：解决如何达成共识 检查点协议：类似于操作系统的还原点 视图更换协议：系统的每个服务器节点在同样的配置信息下工作，该配置信息被称为“视图”。配置信息由主节点确定，主节点更换，视图也随之变化 ## PBFT 算法的主要优点 PBFT算法共识各节点由业务的参与方或者监管方组成，安全性与稳定性由业务相关方保证 共识的时延大约在2~5秒，基本达到商用实时处理的要求 共识效率高，可满足高频交易量的需求 ## fabric中的PBFT算法的实现参数 ```go n //是对应的多笔交易生成的一个排序序号，n保证请求的唯一性，不同的请求有不同的n,处于最小水位线和最大水位线之间 v //表示一个视图 cert变量 //对于验证通过的报文存储到临时变量cert中 Pset //存储pre-prepare报文 Qset //存储prepare报文 Check Point //检查点，是指当前节点处理的最新请求的编号,例如某个节点当前正在共识的请求的编号是666，那么对于该节点而言，其Check Point就是666 Stable check point //稳定检查点，是指多数节点（2f + 1）已经共识完成的请求的最大编号,主要作用是减少内存占用，因为PBFT要求节点记住之前已经共识过的请求， //随着时间推移，这些数据占用的内存会越来越多 watermark高低水位 //假设当前的稳定检查点是166，则低水位h即为166，而高水位H = h + L，L是一个可设定的值 cert //存储验证通过的报文 Pset //持久化存储pre-prepare报文 Qset //持久化存储prepare报文 replica //区块链节点，所有参与提供服务的节点。包含主节点，，PBFT解决的是多个节点之间状态同步的算法 backup //备份节点：主节点外的所有节点。 ``` ## 可能包含的数据结构 节点状态 ``` 世界状态（最新的区块链消息） 消息日志 当前视图 ``` 三阶段协议传输的数消息结构 ## PBFT 论文 4 算法 4.2 正常运行 ## 数字签名的作用: ``` 防抵耐，也就是保证信息是谁发出的 因为是对摘要进行加密形成数字签名，那么保证了信息发出之后没有被修改 ``` ## 接受到 pre-prepare消息后进入prepare阶段 节点的commit消息收到2f+1个提交。 每个节点按照本地维护的一个commit列表，返回请求的响应列表, 这可确保所有非故障副本按照提供安全属性所需的相同顺序执行请求。 执行请求的操作后，副本会向客户端发送回复。 副本丢弃其时间戳低于他们发送给客户端的最后一个回复中的时间戳的请求，以保证一次性语义 副本传递消息可能因为一些网络原因,传递消息的顺序可能不一致，不过这并不影响，因为它保留了预备份，准备和提交记录的消息，直到可以执行相应的请求 4.3 垃圾收集 主要讨论删除之前的日志的机制（之前的日志到底是记录在内存还是在数据库之中） 对于要保留的安全条件，消息必须保存在副本的日志中，直到它知道它们所关注的请求已由至少f + 1个非故障副本执行，并且它可以在视图更改中向其他人证明这一点。 此外，如果某些副本错过了所有非故障副本丢弃的消息，则需要通过传输全部或部分服务状态来更新这些消息。因此，副本还需要证明状态是正确的，那么缺失消息的副本才会接受。 在执行每个操作之后生成这些证明将是昂贵的。 相反，当执行具有可被某个常数（例如，100）整除的序列号的请求时，它们被周期性地生成。 我们将把执行这些请求所产生的状态称为检查点，我们会说带有证据的检查点是一个稳定的检查点。 ## checkout point怎么生成 因为当一些请求来之后我们可能会将该请求持久化或者内存中，那么当该请求完成之后我们需要删除数据，不然我们本地的数据越来越大，而且该交易数据已经上链了，我们可以从链上找打该数据。 但是我们每一次上链操作之后就执行删除操作，我们可以考虑在固定的完成多少次请求之后比如k次请求后执行一次状态同步后删除该数据， 什么是状态同步，就是当一个节点完成响应的k次请求后会广播，发送给其他节点， n是在状态中执行的最后一个请求的序列号，d是是状态的摘要，i是自身的接节点，该CheckPoint消息记录到log中，如果副本节点i收到了2f+1个验证过的CheckPoint消息（包括自身），那么这2f+1个消息是就是当前检查点的一个证明。可以认为完成一定的工作量的证明。 理想情况下所有的节点可能处理请求的速度快慢不是相差太多，那么如果当一个副本节点i向其他节点发出CheckPoint消息后，其他节点还没有完成K条请求，所以不会立即对i的请求作出响应，因为自己没有完成。它还会按照自己的节奏，向前行进，但此时发出的CheckPoint并未形成stable，为了防止i的处理请求过快，（处理请求快，节点的状态可能不一致差异比较大）设置一个上文提到的高低水位区间[h, H]来解决这个问题。低水位h等于上一个stable checkpoint的编号，高水位H = h + L，其中L是我们指定的数值，等于checkpoint周期处理请求数K的整数倍，论文中给的例子可以设置为L = 2K。当副本节点i处理请求超过高水位H时，此时就会停止脚步，等待stable checkpoint发生变化才有可能继续处理其他请求。 具有证明的checkout point就是一个稳定的检查点，副本会删除弃序列号小于或等于其日志的所有预备，准备和提交消息; 它还会丢弃所有早期检查点和检查点消息。 6.3中会详细介绍证明 检查点协议用于更新或者推进低水位h和高水位标记H（限制将接受哪些消息）。我们前面说过只能接受到低水线和高水线之间的消息。 低水位标记h等于最后一个稳定检查点的序列号，高水位线H = h + K，其中K足够大，以便复制品需要等待检查点变得稳定更新checkpoint而不能处理请求。论文中给的数据是如果每个检查点是100次请求后更新，那么 k等于200，在更新的时候仍旧可以处理请求 ## 为什么需要保存日志 一个是将接受到的消息和自身接受到的消息进行对比 确保在View Change的过程中，能够恢复先前的请求，每一个副本节点都记录一些消息到本地 ## view怎么确定 v第一次自己随机设置一个值，满足后续的加1就可以 ## 为什么需要高低水线 ``` 高低水线就是一个数值(n,N),水线存在的意义在于防止一个失效节点使用一个很大的序号消耗序号空间。 二者防止单个节点处理请求过快。防止view-change之后需要广播的消息太多 ``` ## 4.4 view-change 视图更改协议目的是在系统中主节点发生故障时能正常运行。 视图更改可能有很多种情况触发 ``` 由超时触发,比如prepare阶段发给主节点的请求没有响应，这些超时会阻止备份系统无限期地等待执行请求。 或者主节点广播一条消息 ``` 备份在收到请求并且计时器尚未运行时启动计时器。 它在不再需要等待执行请求时停止计时器，也就说如果在规定的时间内该请求没有处理完毕，就会启动view-change超时机制，停止之后徐如果又处理等待执行其他请求，将会重新启动计时器。 超时比如说客户端发送消息给节点,节点广播消息给其他节点，备份节点在超时时间内没有收到主节点发送的共识请求 如果触发view-change，那么它停止接受消息（检查点，视图更改和新视图消息除外），并向其他节点广播消息。视图证明会告诉别人自己这里有什么消息。 ``` v+1 当前视图+1 n是当前节点的最新的stable checkpoint的编号 C是2f+1验证过的稳定的CheckPoint消息集合也就是一个证明， P是一些包含序列号高于n的还没有给客户端回应的请求Pm集合的集合。每个Pm包含一个有效的pre-prepare消息（该消息没有回应给客户端），以及对应的2f个从不同的节点接收到的相同v,n,d并且签名验证正确的prepared消息什么 ``` 此时如果一个节点收到2f+1（包括自身）个有效的view-change消息，先计算一下自己是不是新的主节点，新节点根据 v+1 mod （总节点数）计算，如果是新节点，那么广播消息给所有的其他的节点。 ``` 大V 是收到的视图修改消息的集合 O 是一组预先准备的消息（不带附加请求） ``` O计算如下: ``` 因为收到消息大v中包含了所有的正确的view-change消息的集合，每个v中包含了各自节点的当前的checkpoint，那么从大V也就是从所有的小v中找打最新的checkpoint序号 min-s，找到包含的所有的prepare中消息最大的number号 max-s ，这里虽然我们说的一个是checkpoint号，一个是prepare消息的号，但是本质上来说都是水线。 主节点将会为处于min-s和max-s之间的消息创建新的在视图v+1中的pre-prepare消息 需要将最高的checkpoint以及已经确认的prepared的序列号n之间的消息进行重新广播。因为这些消息没有确认，这里为什么不是commit而是prepare消息 ``` 1.如果利用commit，可能会有一些之前的主节点发首先我们如果获取到最新checkpoint，说明所有序列号位于checkpoint以下的消息都达成共识了，请求已经处理完毕。送的pre-prepared消息已经被节点确认成prepared消息，但是还没做commit,那么就可能会有遗漏，而pre-parepard消息并不能保证请求消息的准准确性，因此我们使用prepared消息。 两种情况: 第一种情况:在最小值min-s 和最大值max-s中间有消息，比如说消息的序列号为n,那么新的主节点将发送一个消息， 《PRE-PREPARE，v+1,n,d》 ``` v+1就是最终所确认的视图 n就是之前的序列号 d是摘要 ``` 第二种情况: 如果都没有的话，也就是说所有节点的prepare状态的消息都还没有高于众多节点确认的水线。 那么它将广播一个空消息。其他节点接受到空消息并不会进行处理 ## 广播new-change消息之后 接下来，主节点将消息附加到其日志中。 如果min-s大于其最新稳定检查点的序列号，则主数据库还会在其日志中插入序列号为min-s的检查点的稳定性证明，并丢弃第4.3节中讨论的日志信息。 然后它进入视图1：此时它能够接受视图1的消息。 此后，协议按4.2节所述进行。 副本重做min-s和max-s之间的消息协议，但它们避免重新执行客户端请求（通过使用其存储的有关发送到每个客户端的最后一个回复的信息） 副本节点获得消息 < a new-view message > 之后，新节点对消息进行广播，那么其他节点接受到这个新的广播的消息后会对这个消息O进行验证。 根据最后一次回复客户端的消息来拒绝之前接受到的消息。 副本可能错过一些之前的消息或者检查点，那么他能从那些在之前的V中证明他的正确性的节点获取丢失的检查点，在V中已经证明过该检查点的正确性，我们可以通过对状态进行分区并使用修改它的最后一个请求的序列号标记每个分区来避免发送整个检查点。在实际中发送过时也就是需求节点没有的的检查点而不是整个检查点 ## 广播view-change到底发生了什么？ 当备份节点 i 怀疑 view v中的主节点出问题（比如是坏节点）后，并广播一条VIEW-CHANGE信息给所有的replicas，其中包含该replica i最新的stable checkpoint的编号，还有 replica i上存的每一个checkpoint的编号和digest的集合，还有上面所说的该replica的P和Q两个集合。 选取i最新的stable checkpoint的编号是因为stable checkpoint 以下的序列号失请求全部处理完毕 ## 4.5 正确性 ## 4.5.1 安全性 如前所述，如果所有非故障副本都同意本地提交的请求的序列号，则该算法可提供安全性，这意味着两个非故障副本在两个副本的同一视图中本地提交的请求的序列号一致 4.2中 我们保证了,正确的节点不会接受到大于当前节点视图V比如说v'的消息在还没有收到关于vi新的视图的new-view message,视图更改协议确保非故障副本也同意请求的序列数，这些请求可以在不同的特定情况下提供不同的视图。一个节点的m在本地被commit当且仅当提交的 commited（m,v，n）是正确的，这个意味着至少有 f+1 个 正常节点，这些正常接单每个节点中都保存了一个真的接受到的准备消息prepared（m,v,n,i）消息 当还没有接受到一个广播的v'（v'>v）的new-view消息时，所有的正常节点季都会拒绝一个大于当前v的消息。只有在接受到new-view消息之后才能进行v'这个视图。而且每个new-view 消息中都包括了 收集到的2f+1个正确的 ## 4.5 安全性 这意味着两个非故障副本在两个副本的同一视图中本地提交的请求的序列号一致。 视图更改协议确保正常节点同意请求的序列数，这些序列号相同的请求也包括那些不同节点和不同的视图中提供的 ## 为什么需要prepare阶段 malicious ## PBFT的优化措施 方向: 减少通信 我们可以考虑让一个节点来发送回复消息，其他节点发送回复消息的摘要，减少数据的传递 取消commit阶段，这样客户端就就需要接受2f+1个相同的消息。 数字