共识算法基础

PoW #

概念 #

PoW（工作量证明，Proof of Work），比特币，俗称挖矿。Pow是指系统为达到某一目标而设置的度量方法。简单理解就是一份证明，用来确认你做过一定量的工作。监测工作的整个过程通常是极为低效的，而通过对工作的结果进行认证来证明完成了相应的工作量，则是一种非常高效的方式。

工作量证明（Pow）通过计算一个数值（nonce），使得拼凑上交易数据后内容的Hash值满足规定的上限。在结点成功找到满足的Hash值之后，会马上对全网进行广播打包区块，网络的结点收到广播打包区块，会立刻对其进行验证。

如何才能创建一个新区块呢？通过解决一个问题：即找到一个nonce值，使得新区块头的哈希值小于某个指定的值，即区块头结构中的“难度目标”。

如果验证通过，则表明已经有结点成功解谜，自己就不再竞争当前区块打包，而是选择接受这个区块，记录到自己的账本中，然后进行下一个区块的竞争。

假如结点有任何的作弊行为，都会导致网络的结点验证不通过，直接丢弃其打包的区块，这个区块就无法记录到总帐本中，作弊的节点耗费的成本就白费了，因此在巨大的挖矿成本下，也使得矿工自觉自愿的遵守比特币系统的共识协议，也就确保了整个系统的安全。

父区块头哈希值：前一区块的哈希值，使用SHA256(SHA256(父区块头))计算。占32字节 版本：区块版本号，表示本区块遵守的验证规则。占4字节 时间戳：该区块产生的近似时间，精确到秒的UNIX时间戳，必须严格大于前11个区块时间的中值，同时全节点也会拒绝那些超出自己2个小时时间戳的区块。占4字节 难度：该区块工作量证明算法的难度目标，已经使用特定算法编码。占4字节 随机数(Nonce)：为了找到满足难度目标所设定的随机数，为了解决32位随机数在算力飞升的情况下不够用的问题，规定时间戳和coinbase交易信息均可更改，以此扩展nonce的位数。占4字节 Merkle根：该区块中交易的Merkle树根的哈希值，同样采用SHA256(SHA256())计算。占32字节

如此，细心的同学会发现，区块头总共占了80字节。

区块体除了筹币交易记录（由一棵Merkle二叉树组成)外，还有一个交易计数。

Pow工作量证明的三要素 #

工作机制

为了使区块链交易数据记录在区块链上并在一定时间内达到一致（共识），Pow提供了一种思路，即所有区块链的网络节点参与者进行竞争记账，所谓竞争记账是指，如果想生成一个新的区块并写入区块链，必须解出比特币网络出的工作量证明谜题，谁先解出答案，谁就活的记账权利，然后开始记账并将解出的答案和交易记录广播给其他节点进行验证，自己则开始下一轮挖矿。如果区块的交易被其他节点参与者验证有效并且谜题的答案正确，就意味着这个答案是可信的，新的节点将被写入验证者的节点区块链，同时验证者进入下一轮竞争挖矿。

这道题关键的三个要素是工作量证明函数、区块及难度值。工作量证明函数是这道题的计算方法，区块决定了这道题的输入数据，难度决定了这道题所需要的计算量。

  • 工作量证明函数

    比特币中使用SHA256算法函数，是密码哈希函数家族中输出值为256位的哈希算法。

  • 区块

    Merkle树算法：

  • 难度值

    关于难度值，我们直接看公式：

    新难度值=旧难度值*（过去2016个区块花费时长/20160分钟）

    tips：难度值是随网络变动的，目的是为了在不同的网络环境下，确保每十分钟能生成一个块。

    新难度值解析：撇开旧难度值，按比特币理想情况每十分钟出块的速度，过去2016个块的总花费接近2016分钟，这样，这个值永远趋近于1。

    目标值=最大值/难度值,

    目标值解析：最大目标值为一个固定数，若过去2016个区块花费时长少于20160分，那么这个系数会小，目标值将会被调大些，反之，目标值会被调小，因此，比特币的难度和出块速度将成反比例适当调整出块速度。

    那如何计算呢？SHA256(SHA256(Block_Header))，即只需要对区块头进行两次SHA256运算即可，得到的值和目标值进行比较，小于目标值即可。

    区块头中有一个重要的东西叫MerkleRoot的hash值。这个东西的意义在于：为了使区块头能体现区块所包含的所有交易，在区块的构造过程中，需要将该区块要包含的交易列表，通过Merkle Tree算法生成Merkle Root Hash，并以此作为交易列表的摘要存到区块头中。

    至此，我们发现区块头中除过nonce(随机数)以外，其余的数据都是明确的，解题的核心就在于不停的调整nonce的值，对区块头进行双重SHA256运算。

Pow工作量证明流程 #

从流程图中看出，pow工作量证明的流程主要经历三步：

1.生成Merkle根哈希   生成Merkle根哈希，即节点自己生成一笔筹币交易，并且与其他所有即将打包的交易通过Merkle树算法生成Merkle根哈希，所以为什么说区块是工作量证明的三要素之一。

2.组装区块头   区块头将被作为计算出工作量证明输出的一个输入参数，因此第一步计算出来的Merkle根哈希和区块头的其他组成部分组装成区块头。

3.计算出工作量证明的输出   下面我们直接通过公式和一些伪代码去理解工作量证明的输出：

   i. 工作量证明的输出=SHA256(SHA256(区块头))

   ii. if（工作量证明的输出<目标值），证明工作量完成

  iii.if（工作量证明的输出>=目标值）,变更随机数，递归i的逻辑，继续与目标值比对。

Pow共识记账 #

在比特币平台中，中本聪就是运用的pow工作量证明来使全网节点达到51%及以上的共识记账，以下将介绍pow工作量证明共识是如何记账的？

首先，客户端产生新的交易，向全网广播

第二，每个节点收到请求，将交易纳入区块中

第三，每个节点通过上述中描述的进行pow工作量证明

第四，当某个节点找到了证明，向全网广播

第五，当且仅当该区块的交易是有效的且在之前中未存在的，其他节点才认同该区块的有效性

第六，接受该区块且在该区块的末尾制造新的区块

大概时序图如下：

Pow的优缺点 #

优点：

  • 完全去中心化（任何人都可以加入）
  • 结点自由进出，容易实现
  • 破坏系统花费成本巨大

关于破坏系统成本巨大可以分两层意思理解：

  1. 在指定时间内，给定一个难度，找到答案的概率唯一地由所有参与者能够迭代哈希的速度决定。与之前的历史无关，与数据无关，只跟算力有关。
  2. 掌握51%的算力对系统进行攻击所付出的代价远远大于作为一个系统的维护者和诚实参与者所得到的。

缺点：

  • 对节点的性能网络环境要求高：
  • 浪费资源,
  • 每秒钟最多只能做七笔交易，效率低下
  • 矿场的出现违背了去中心的初衷
  • 不能确保最终一致性
  • 比特币产量每四年减半，利益驱动性降低导致矿工数量减少从而导致比特币网络瘫痪。

网络攻击和链分叉 #

网络攻击 #

假定一个恶意节点试图双花之前的已花费的交易，攻击者需要重做包含这个交易的区块，以及这个区块之后的所有的区块，创建一个比目前诚实区块链更长的区块链。只有网络中的大多数节点都转向攻击者创建的区块链，攻击者的攻击才算成功了。由于每一个区块都包含了之前的所有区块的交易信息，所以随着块高的增加，之前的区块都会被再次确认一次，确认超过6次，可以理解为无法被修改。

考虑交易T包含在区块b1中。每个后续区块b2，b3，b4，……bn会降低交易T被修改的可能性，因为修改这些后续的区块需要更多的算力。中本聪用概率理论证明，六个区块后攻击者追赶上最长链的可能性降低到0.0002428%。在过4个或更多区块后这个可能行会降到0.0000012%。每新增一个区块bn，攻击的可能性就会以指数形式下降，很快整个攻击的可能性就会低到可以忽略的程度。

链分叉 #

所谓的链分叉，主要是由于在计算hash时，每个人拿到的区块内容是不同的，导致算出的区块结果也不同，但都是正确结果，于是，区块链在这个时刻，出现了两个都满足要求的不同区块，那旷工怎么办呢？由于距离远近、网络等原因，不同旷工看到这两个区块的先后顺序是不一样的，通常情况下，旷工会把自己先看到的区块链复制过来，然后接着在这个区块上开始新的挖矿工作，于是就出现了链分叉。

PoW解决方案： 从分叉的区块起，由于不同的矿工跟从了不同的区块，在分叉出来的两条不同链上，算力是有差别的。由于解题能力和矿工的算力成正比，因此两条链的增长速度也是不一样的，在一段时间之后，总有一条链的长度要超过另一条。当矿工发现全网有一条更长的链时，他就会抛弃他当前的链，把新的更长的链全部复制回来，在这条链的基础上继续挖矿。所有矿工都这样操作，这条链就成为了主链，分叉出来被抛弃掉的链就消失了。

能够让区块链保证唯一性的前提是：所有矿工都遵从同样的机制。当旷工遵从不同的机制时，就会出现硬分叉，这种分叉会导致资产增加，且两条链同时存在，比如BBC。

Pos #

Pos（proof of stake)，即股权证明。简单来说，就是根据你持有货币的量和时间，给你发利息的一个制度。

运作模式 #

在股权证明Pos模式下，有一个名词叫币龄，每个币每天产生1币龄，比如你持有100个币，总共持有了30天，那么，此时你的币龄就为3000，这个时候，如果你发现了一个POS区块，你的币龄就会被清空为0。你每被清空365币龄，你将会从区块中获得0.05个币的利息(可理解为年利率5%)，那么在这个案例中，利息 = 3000 * 5% / 365 = 0.41个币。

一旦你发现了一个POS的区块，那么你的币龄就被清空，并且会根据币龄发出一笔利息（清零的话，可以降低中心化的风险，可以避免大股东囤币，从而轻易"持续的"获得记账权，因为即使超过51%币的大股东，也可能在下一个块的争夺中失败，因为20%币的庄家，币龄更长，币龄是币值*持币时间)

简单来说就是谁的权益大，谁说了算

利息 #

POS：也称股权证明，类似于财产储存在银行，这种模式会根据你持有数字货币的量和时间，分配给你相应的利息。 简单来说，就是一个根据你持有货币的量和时间，给你发利息的一个制度，在股权证明POS模式下，有一个名词叫币龄，每个币每天产生1币龄，比如你持有100个币，总共持有了30天，那么，此时你的币龄就为3000，这个时候，如果你发现了一个POS区块，你的币龄就会被清空为0。你每被清空365币龄，你将会从区块中获得0.05个币的利息(假定利息可理解为年利率5%)，那么在这个案例中，利息 = 3000 * 5% / 365 = 0.41个币，这下就很有意思了，持币有利息。

POS设计的理念以及初衷： #

首先，比特币的区块产量每4年会减半，在不久的未来，随着比特币区块包含的产量越来越低，大家挖矿的动力将会不断下降，矿工人数越来越 少，整个比特币网络有可能会逐渐陷入瘫痪(因为大家都减少了运行比特币客户端的时间，因此越来越难找到一个P2P节点去连接和同步网络数据)。

​ 在POS体系中，只有打开钱包客户端程序，才能发现POS区块，才会获得利息，这促使很多不想挖矿的人，也会常常打开自己的钱包客户端，这帮助了P2P货币网络的健壮。

​ 其次，若干年后，随着矿工人数的下降，比特币很有可能被一些高算力的人或团队进行51%攻击，导致整个比特币网络崩溃。

在POS体系中，即使你拥有了全球51%的算力，也未必能够进行51%攻击，因为，有一部分的货币并不是挖矿产生的，而是由利息产生(利息存放在POS区块中)，这要求攻击者还需要持有全球超过51%的货币量。这大大提高了51%攻击的难度。

原理 #

PoS共识机制（Proof of Stake 权益证明）通过权益记账的方式，解决效率低下、资源浪费、节点一致性等问题。

各个节点需要满足一定的条件（如抵押一定的代币）才能成为验证节点（权益提高），系统通过算法在其中选择一部分作为出块节点（矿工），每隔一段时间重新选择，算法会保证完全随机，不可被操控。只有出块节点才能进行数据处理，争夺记账权。

权益主要由权益因子决定，可以是持币数量，也可以是币龄及两者的结合。

优点 #

解决Pow的资源浪费，效率低下问题。是一个闭环机制，所有的stake都是基于区块链内货币的，而不是基于外界资源，这样攻击者想要达到50%以上算力必须购买大量货币赢得stake，所以更为安全。

缺点 #

容易形成强者恒强的局面，代币越多越容易操控全局。去中心化程度弱。

核心 #

  • 在Pow算法的基础上，Pos算法中争夺记账权的影响因子：算力、持币数量、持币时间。
  • Pos挖矿难度值=Target*币龄
  • Pos认为币龄更有决策权，所以币龄对挖矿难度值的影响权重特别高，就是让大股东来记账而不是大算力、大矿池负责记账。试图通过提升算力来竞争记账权很不划算。
  • Pow的记账权竞争是算力竞争，而Pos的记账权竞争主要是币龄竞争。
  • 因为算力不是唯一决定获取记账权的因子，从而增强了系统的安全性，也即是说即使几个大矿池联合欺诈，也不会轻易得逞，而持币大股东是直接利益者，他们拥有更多的记账权，他们更愿意整个pos系统稳定安全。
  • PoS的显著优点包括安全性、降低集中风险和能源效率（因为单纯通过投入算力很不划算)

Pos 引发的问题 #

1、挖矿因子持币时间：通过囤积很长一段时间的货币，然后就轻易的获得记账权，而且不利于电子货币的流通

  • 通过对持币时间做上限设置，比如上限15天，从而避免货币不流通，因为你一直囤着货币不流通，超过15天，你的币龄也不会继续增长
  • 通过每次挖矿成功后清零币龄，这样即使这次拿到了记账权，在下一个区块中仍然要重新计算，不会持续的获得记账权优势

2、挖矿因子持币数量：通过囤积大量货币获得记账权优势，从而导致货币不流通 你可以囤币，但是大股东必须保证货币的流通性，为了鼓励流通，币龄会随着持币时间增长而衰减，这样你要提高自己的币龄就不得不流通交易了

3、离线攻击：篡改交易的时间

  • 比如交易的时候篡改自己的系统时间，从而自己作为收款方的币龄就提升了
  • 比如挖矿的时候，修改自己的系统时间（延后自己的系统时间），从而使币龄处于最高值 这里就需要做感知监督了

4、无法发行新币：目前解决方案是先Pow，一段时间后再过度到Pos BlackChain:前5000个区块，使用纯POW机制，5001到10000使用POS和POW混合机制、10001之后采用纯POS机制

DPos #

委托股权证明（Delegated Proof of Stake,DPoS)是目前所有共识协议中最快、最有效、最分散、最灵活的共识模式。

DPos机制是通过资产占比（股权）来投票，更多的加入了社区人的力量，人们为了自身利益的最大化会投票选择相对可靠的节点，相比更加安全和去中心化。

基本原理 #

对于Pos机制的加密货币，每个节点都可以创建区块，并按照个人的持股比例获得“利息”。DPoS是由被社区选举的可信账户（受托人，得票数排行前101位）来创建区块。DPoS机制类似于股份制公司，普通股民进不了董事会，要投票选举代表（受托人）代他们做决策。网络中的所有节点依据他们所拥有的代币的量，分配对应的投票权重；网络中的所有节点进行投票，选出一定数量的区块生产者进行新区块的生产与协商。区块生产者通过某种方式（随机获者顺序）进行出块，且每个区块生产者通过出块来对应之前的块进行确认。一个交易在2/3的见证人确认后达到不可逆状态，区块生产者之间可建立直接连接从而保证通信的可靠及快速，DPoS能在较快的时间里达成共识。

DPoS机制中，不需要算力解决数学难题，而是由持币者选出谁是生产者，如果生产者不称职，就有随时又可能被投票出局，这也就解决了Pos的性能问题。

在DPoS机制下，算法要求系统做三件事：

  • 随机指定生产者出场顺序
  • 不按顺序生产的区块无效
  • 没过一个周期洗牌一次，打乱原有顺序

潜在问题 #

除了Pos有的问题外，还要考虑以下两个问题：

  • 传输速度问题：受制于节点间的物理性能
  • 持币人的投票进度非常缓慢，造成无法上线

1、相对于Pow和Pos，DPos的最大优点之一是达成共识的周期要短很多。

基于Pow的比特币每秒处理7笔交易；基于PoW和Pos的以太坊每秒处理15笔交易；而基于DPos的比特股每秒能处理超10万的交易量。

2、DPos也会将一部分奖励分给网络维护节点和投票者，作为社区维护的奖励。

  • 持币人投票选举出块节点
  • 最大化持币人的利益
  • 最小化维护网络安全的费用
  • 最大化网络的效能
  • 最小化运行网络的成本

对恶意节点的惩罚 #

注册成为候选受托人需要支付一笔保证金，就像是参与民意代表选举前缴纳的保证金一样，一般来说担任受托人约两周后才可达到利益平衡，这促进了受托人的稳定性，确保至少会挖满两周的矿。

惩罚机制：不按排程产生区块的节点将在下一轮被投票踢出，也会被没收之前缴纳的保证金。

DPos是效率较Pos，Pow更高、产生区块的速度更快；

虽然恶意的节点将在下一轮投票被踢出，但单个恶意区块在短期仍有可能是最有效的状态。

短期虽然可能存在恶意区块，但长期下来，可以透过受托人的自主选择来回归链条的有效性。

比特币,以太坊：矿池垄断了记账机会， 名义上是人人平等，实际上只有少数人记账：3~5矿池 DPOS（Delegated Proof Of Stake， 委托权益证明），它的原理是让每一个持有币的人进行投票，由此产生n个代表 , 我们可以将其理解为n个超级节点或者矿池，这n个超级节点彼此的权利是完全相等的。从某种角度来看，DPOS有点像是议会制度或人民代表大会制度。如果代表不能履行他们的职责（当轮到他们时，没能生成区块），他们会被除名，网络会选出新的超级节点来取代他们。DPOS的出现最主要还是因为矿机的产生，大量的算力在不了解也不关心比特币的人身上，类似演唱会的黄牛，大量囤票而丝毫不关心演唱会的内容。 黄色节点：记账的节点（一把手） 绿色节点：备用节点（二把手，随时准备上位） 蓝色节点：散户，把票投给自己相信的节点（小弟） 当选节点如果作恶，未能履行记账职责，就会被踢掉。 当选的节点要记账，需要提供丰富的网络资源，计算资源。记账有奖励。 奖励来自于系统每年的增发。

特点

不挖矿，每年按比例增发代币，奖励超级节点。

优点

高效、扩展性强

缺点

21个节点太少，非去中心化，而是多中心化

项目

EOS

PBFT #

PBFT(Practical Byzantine Fault Tolerance,实用拜占庭容错)

拜占庭将军问题证明在将军总数大于3f，背叛者为f或者更少时，忠诚的将军可以达成命令上的一致，即3f+1<=n。该算法容错数量也满足3f+1<=n，也即最大的容错作恶节点数f=(n-1)/3。

拜占庭协定 #

假设节点总数为n,故障节点数为f，当n>3f时才能达成拜占庭协定。即算法在失效节点数量f<n/3时，可以保证集群的安全性和活跃性。

PBFT算法除了需要支持容错故障节点外，还需要支持容错作恶节点。假设集群节点数为N，有问题的节点为f。有问题的节点中，既可以是故障节点，也可以是作恶节点。那么会产生两种极端情况：

  • 这f个有问题节点即是故障节点，又是作恶节点，那么根据少数服从多数原则，集群正常节点只需比f个节点再多一个节点，即f+1个节点，正确节点的数量就会比故障节点数量多，那么集群就能达成共识，即总节点数为f+(f+1)=n,最大容错节点数量为（n-1）/2.
  • 故障节点和作恶节点都是不同多节点，那么就有f个作恶节点，和f个故障节点，当发现节点是恶意节点后，会被集群排除在外，剩下f个故障节点，那么根据少数服从多数的原则，集群里正常节点只需比f多一个节点，即f+1个节点，集群就能达成共识。所以，所有类型的节点加起来就是f+1 + f +f =3f+1=n.

综合两种情况，BPFT算法支持的最大容错节点数量为（n-1)/3

与公有共识算法的区别 #

公有区块链不可能同时共识区块1和区块2，但在PBFT中，交易1和交易2的共识是并行的。

  • 在公有区块链中，每一个区块串行进行共识，共识的对象是区块，区块包含一段时间收集的交易
  • 在PBFT中，共识的对象是每一个交易（可以说在PBFT中没有区块这个概念），交易共识的过程是并行的（限定在高低水位）。

PBFT的适用场景 #

不适合在公链，只适合在联盟链的场景：缺点：

  • PBFT在网络不稳定的情况夏延迟较高
  • 基于投票的，所以投票集合是有限的，不然怎么少数服从多数
  • 通信复杂度过高O(N^2),可扩展性较低，一般的系统在达到100左右的节点个数时，性能下降非常快

优点：

  • 通信复杂度O(n2)，解决了原始拜占庭容错(BFT)算法效率不高的问题，将算法复杂度由指数级降低到多项式级，使得拜占庭容错算法在实际系统应用中变得可行。
  • 首次提出在异步网络环境下使用状态机副本复制协议，该算法可以工作在异步环境中，并且通过优化在早期算法的基础上把响应性能提升了一个数量级以上。作者使用这个算法实现了拜占庭容错的网络文件系（NFS），性能测试证明了该系统仅比无副本复制的标准NFS慢了3%。
  • 使用了加密技术来防止欺骗攻击和重播攻击，以及检测被破坏的消息。消息包含了公钥签名（RSA算法）、消息验证编码（MAC）和无碰撞哈希函数生成的消息摘要（message digest）。

PBFT算法基础 #

算法设计的角色 #

  • 客户端：向主节点发送请求
  • 主节点：收到请求后，将交易打包成区块和区块共识并广播，每轮共识过程有且仅有一个主节点
  • 副节点：接收广播消息，验证请求合法性，投票，触发view change协议来推举新主节点
  • 视图：一个视图中存在一个主节点和多个副节点，它描述了一个多副本系统的当前状态。另外，节点是在同一个视图上对数据达成共识，不能跨view。

算法流程 #

简化逻辑 #
  • 客户端向主节点发送请求
  • 主节点通过广播将请求发送给其他副本，节点执行三节点共识流程
  • 所有副本都执行请求并将结果发回客户端
  • 客户端需要等待f+1个不同副本节点发回相同的结果，作为整个操作的最终结果
三阶段共识流程 #

三个阶段分别是 pre-prepare 阶段（预准备阶段），prepare 阶段（准备阶段）， commit 阶段（提交阶段）。图中的C代表客户端，0，1，2，3 代表节点的编号，其中0 是主节点primary，打×的3代表可能是故障节点或者是作恶节点，这里表现的行为就是对其它节点的请求无响应。整个过程大致是如下：

首先，客户端向主节点0发起请求<<REQUEST,o,t,c>> 其中t是时间戳，o表示操作，c是这个client，主节点收到客户端请求，会向其它节点发送 pre-prepare 消息，其它节点就收到了pre-prepare 消息，就开始了这个核心三阶段共识过程了。

  • Pre-prepare 阶段：副本节点replica收到 pre-prepare 消息后，会有两种选择，一种是接受，一种是不接受。**什么时候才不接受主节点发来的 pre-prepare 消息呢？**一种典型的情况就是如果一个replica节点接受到了一条 pre-prepare 消息<<PRE_PREPARE,v,n,d>,m>，其中，v 代表视图编号（视图的编号是什么意思呢？比如当前主节点为 A，视图编号为 1，如果主节点换成 B，那么视图编号就为 2），n代表序号（主节点收到客户端的每个请求都以一个编号来标记），d代表消息摘要，m代表原始消息数据。消息里的 v 和 n 在之前收到里的消息是曾经出现过的，但是 d 和 m 却和之前的消息不一致，或者请求编号n不在高低水位之间，这时候就会拒绝请求。拒绝的逻辑就是主节点不会发送两条具有相同的 v 和 n ，但 d 和 m 却不同的消息。

    Replia节点接收到pre-prepare消息，进行以下消息验证：

    1. 消息m的签名合法性，并且消息摘要d和消息m相匹配：d=hash(m)
    2. 节点当前处于视图v中
    3. 节点当前在同一个(view v ，sequence n)上没有其它pre-prepare消息，即不存在另外一个m’和对应的d’ ，d’=hash(m')
    4. h<=n<=H，H和h代表序号n的高低水位。

  • Prepare 阶段：当前节点同意请求后会向其它节点发送 prepare 消息<PREPARE,v,n,d,i>同时将消息记录到log中，其中i用于表示当前节点的身份。同一时刻不是只有一个节点在进行这个过程，可能有 n 个节点也在进行这个过程。因此节点是有可能收到其它节点发送的 prepare 消息的，当前节点i验证这些prepare消息和自己发出的prepare消息的v，n，d三个数据是否都是一致的。验证通过之后，当前节点i将prepared(m，v，n) 设置为true，prepared(m，v，n) 代表共识节点认为在(v，n)中针对消息m的Prepare阶段是否已经完成。在一定时间范围内，如果收到超过 2f 个其他节点的prepare 消息，就代表 prepare 阶段已经完成。最后共识节点i发送commit消息并进入Commit阶段。

  • Commit 阶段：当前节点i接收到2f个来自其他共识节点的commit消息<COMMIT,v,n,d,i>同时将该消息插入log中（算上自己的共有2f+1个），验证这些commit消息和自己发的commit消息的v，n，d三个数据都是一致后，共识节点将committed-local(m，v，n)设置为true，committed-local(m，v，n)代表共识节点确定消息m已经在整个系统中得到至少2f+1个节点的共识，而这保证了至少有f+1个non-faulty节点已经对消息m达成共识。于是节点就会执行请求，写入数据。

处理完毕后，节点会返回消息<<REPLY,v,t,c,i,r>>给客户端，当客户端收集到f+1个消息后，共识完成，这就是PBFT算法的全部流程。

View Change #

触发条件 #

视图改变由以下两个条件之一触发：

  • 副本从一个客户得知，主节点存在不正当行为
  • 副本不能接收到主节点发出的消息

View Change是由副节点发起，它们向其他副本发送IHatePrimary消息以启动一个视图改变。

View-Change的条件 #

副本持续接收IHatePrimary消息，直到遇到下面两个条件之一：

当接收到超过f+1个IHatePrimary消息 如果收到了其他节点的ViewChange消息。 当遇到这两个条件之一时，将会将广播一条<VIEW-CHANGE, v+1, n, C, P, i>消息，n是最新的stable CheckPoint的编号，C是2f+1验证过的CheckPoint消息集合，P是当前副本节点未完成的请求的PRE-PREPARE和PREPARE消息集合。

New-View的条件 #

当节点收到2f个有效的New-View消息后，向其他节点广播<NEW-VIEW, v+1, V, O>消息。V是有效的View-Change消息集合。O是主节点重新发起的未经完成的PRE-PREPARE消息集合。PRE-PREPARE消息集合的选取规则：

选取V中最小的stable CheckPoint编号min-s，选取V中prepare消息的最大编号max-s。 在min-s和max-s之间，如果存在P消息集合，则创建«PRE-PREPARE, v+1, n, d>, m>消息。否则创建一个空的PRE-PREPARE消息，即：«PRE-PREPARE, v+1, n, d(null)>, m(null)>, m(null)空消息，d(null)空消息摘要。 副本节点收到主节点的New-View消息，验证有效性，有效的话，进入v+1视图，并且开始O中的PRE-PREPARE消息处理流程。

Raft #

Raft共识算法

raft 和 pbft 算法有两点根本区别： #

  1. raft 算法从节点不会拒绝主节点的请求，而 pbft 算法从节点在某些情况下会拒绝主节点的请求 ;
  2. raft 算法只能容错故障节点，并且最大容错节点数为 （n-1）/2 ，而 pbft 算法能容错故障节点和作恶节点，最大容错节点数为 （n-1）/3 。

流程的对比上，对于 leader 选举这块， raft 算法本质是谁快谁当选，而 pbft 算法是按编号依次轮流做主节点。

对于共识过程和重选 leader 机制这块，一个团队一定会有一个老大和普通成员。对于 raft 算法，共识过程就是：只要老大还没挂，老大说什么，我们（团队普通成员）就做什么，坚决执行。那什么时候重新老大呢？只有当老大挂了才重选老大，不然生是老大的人，死是老大的鬼。

对于 pbft 算法，共识过程就是：老大向我发送命令时，当我认为老大的命令是有问题时，我会拒绝执行。就算我认为老大的命令是对的，我还会问下团队的其它成员老大的命令是否是对的，只有大多数人 （2f+1） 都认为老大的命令是对的时候，我才会去执行命令。那什么时候重选老大呢？老大挂了当然要重选，如果大多数人都认为老大不称职或者有问题时，我们也会重新选择老大。