block chain/Basic/consensus.md
# 共识机制
## 分布式一致性与共识
区块链的本质就是一个分布式系统，而分布式系统通常面临了几个问题：一致性问题，可终止性问题、合法性问题。
可终止性可以理解为系统必须在有限的时间内给出一致性结果，合法性是指提案必须是系统内的节点提出。当然其中面对的最重要也是最基础的问题，就是我们常说的**一致性**问题。
一致性是指在某个分布式系统中，多个服务节点呈现相同的状态和数据。这里面可能是多个相同的服务提供同样的功能，那么这些服务中的状态和数据就应该保持一致，对外就好像一个服务一样；另一种情况是多个不同的服务在提供不同的功能，但他们的数据前后关联，那么这些服务所拥有的数据也应该保持一致。但是很多时候，我们不可能要求所有服务器100%都达成一致状态，只要超过半数的大多数服务器达成一致就可以了，假设有N台服务器，N/2 +1 就超过半数，代表大多数了。所以一致性也分严格一致性、最终一致性。
对应到区块链系统中就可以表示为：任意节点的提案能够在约定的协议下被其他所有节点所认可。因为区块链系统中不分服务端和客户端，所以这里强调任意节点，同时上文所说的一致性在这里就对应为区块链的共识机制。需要提醒你区分的一点是：这里的“认可”表示所有节点对外呈现的信息一致，而不是对信息的内容认可。
## 常见算法
常见的分布式一致性算法有[ref](https://github.com/yjjnls/Notes/blob/master/distribute/distribute.md)，其中paxos和raft协议是较为经典的算法，但是他们无法抵御节点恶意篡改数据的攻击，所以常用于节点能够完全信任的环境，比如各节点服务都是某公司统一部署控制的，节点完全私有。这种情况属于中心化的分布式系统，一般会有leader，系统可以容忍非恶意攻击，例如网络拥堵、数据丢失等等，但不能容忍恶意结点的攻击。
而区块链的应用环境恰恰是其他两种情况，第一种是完全公有的环境，也即公链，任何人都可以部署节点（准入门槛很低），常用PoW、PoS等共识算法；而第二种是属于私有链，只有获得许可的机构或者个人才能部署节点，参与的机构或者个人由于先获得了权限许可，所以可以看作“可信任”。这里的“可信任”是指受信程度高于完全陌生的公有节点，但也不是完全可以信任。这种情况通常用PBFT算法（拜占庭将军问题，在有恶意节点的情况下（精神分裂式投票），如何保证系统状态与数据的一致性）。
### CAP定理
CAP 定律（Consistency，Availability，Partition Tolerance theorem），说的是在一个分布式计算机系统中，**一致性，可用性和分区容错性`这三种保证无法同时得到满足，最多满足两个`**。其中，`分区容错性`指的是在网络中断，消息丢失的情况下，系统照样能够工作；`一致性`说的是分布式系统中，所有节点在同一时刻看到同一个值；`可用性`说的是每个请求都会收到一个应答，无论该应答是成功还是失败。
对CAP 定律做进一步分析，我们可以更加深入地了解各种公式算法的特性及其适用场景。
* 一致性决定了不同节点达成共识的时间长短
这里又分为概率一致性（最终一致性）算法和绝对一致性算法。概率一致性算法指在不同分布式节点之间，有较大概率保证节点间数据达到一致，但仍存在一定概率使得某些节点间数据不一致。对于某一个数据点而言，数据在节点间不一致的概率会随时间的推移逐渐降低至趋近于零，从而最终达到一致性。例如工作量证明算法（Proof of Work, PoW）、股份证明算法（Proof of Stake, PoS）和委托股权证明算法（Delegated Proof of Stake, DPoS）都属于概率一致性算法。而绝对一致性算法则指在任意时间点，不同分布式节点之间的数据都会保持绝对一致，不存在不同节点间数据不一致的情况。例如分布式系统中常用的 PAXOS 算法及其衍生出的 RAFT 算法等，以及拜占庭容错类算法（类 BFT 算法）。一致性决定了分布式系统中不同节点达成共识的时间长短，在区块链中也就是出块时间长短，**达成一致性所需的时间越短，系统的TPS越高**。
* 可用性是分布式系统必须的
使用分布式系统的一个重要原因就是为了避免单点系统宕机出现问题，提高系统可用性。而且这也是分布式系统的基础，如果做不到7 X 24 X 365 可用，那么区块链系统的可靠性就会大打折扣。
* 分区容忍性有两层含义
第一层是必须保证分区可容忍，也就是一旦出现因为网络分区而导致区块链分叉，**必须有一种机制可以合并区块链**；第二层含义是 **如果我们尽量避免出现网络分区，那么就可以避免 P 的出现，从而提升 C 的性能** 。
由以上特点我们可以知道，可用性A必须保证，而C 和 P 是可以相互调整的，又分为三种情况。
1. 如果我们选则调整 C，也就是拉长了最终一致性的确认时间，那么对 P 的要求就会减弱，也就是网络产生分区不要紧，反正区块链有足够的时间恢复最终一致性。这种系统 **舍弃了C，而追求A和P** ，其特点是抗干扰能力特别强，也即PoW和PoS的特点，适用于在完全公有的环境中抵抗各种干扰，保证区块链的稳定性，可以称之为 **去中心化的系统**。同时由于此系统降低了C的性能，所以达成共识的时间延长，系统的TPS就很低，这也符合PoW和PoS为代表的比特币和以太坊的特性。
2. 如果我们选则调整 P，也就是限制较少的记账节点的数量，并且对记账节点之间的带宽提出要求，降低出现网络分区的可能性，那么对 C 的要求就会减弱，就可以降低出块时间。这种系统的特点是提高了节点的准入门槛来减少系统受到的攻击，同时节点数量也大大减少，所以TPS会大大提高。**这种系统兼顾了C和P，可以称之为弱中心化的系统**。这也是DPoS和PBFT的特性，这里的代表是EOS和各种联盟链。
3. 而如果完全不考虑拜占庭容错等问题，也就是情况3，我们可以进一步追求C，这也是 **中心化分布式系统**的特点，其一致性算法常用PAXOS和RAFT。
以下是根据以上分析做出的CAP可视图以及各类公式算法的特性比较，同时也包含一些区块链项目的共识特性比较。
### PoW
#### PoW基本原理
PoW 全称 Proof of Work，也即工作量证明，由于比特币中所使用的共识机制就是PoW，因此PoW的概念传播最为广泛。但PoW机制最早在1977年就被提出应用在抵抗滥用软件服务的场景中，例如在抵抗垃圾邮件的场景中，接收者并不直接接受来自任意发送者的消息，发送者需要计算一个按照规则约定难题的答案，发送给接受者的同时，需要附带验证这个答案，如果这个答案被验证有效，那么接受者才会接受这个消息。而这个难题答案的验证过程是非常容易的，这种特性我们称之为计算不对称特性，即破解很难，但是验证很容易。通过这一例子说明也能让我们更好地理解PoW的设计思想。
在比特币系统中，会要求对每个区块头中的信息求哈希值，如果得到的哈希值前十位都为0，那么这个区块头才是有效的。而区块头中包含一个随机数，所谓挖矿就是不断探测这个随机值，使其计算得到的哈希值满足条件，找到满足条件的随机值之后再将区块广播出去。其他区块在收到这条广播信息之后，先验证这一哈希条件是否满足，如果不满足直接丢弃。PoW使得区块在验证的时候非常容易，而在寻找随机数时毫无规律，只能重复机械地尝试，且要求的哈希值的0开头的位数越多，随机数寻找难度越大。而这重复地寻找过程和实体电力成本又成正比。
#### PoW挖矿
PoW的过程就是计算一个难题解的过程，而在比特币中，解决了这个难题，就有一定概率获得一定量的比特币作为奖励，所以称之为挖矿。
中本聪设计比特币时，其愿景是1 CPU一票，也就相当于1个CPU等于一个矿工，这样比特币的记账就能平均分布到全世界。但是CPU着重控制逻辑，而挖矿过程是一种简单的重复计算，所以后面又发展出了GPU并行挖矿，效率能够提升几十倍甚至上百倍。后续又出现了FPGA挖矿，和专业的矿机挖矿，使得挖矿效率不断提高。
但是按照中本聪的设计，比特币应该是一个去中心化的分布式系统，但随着挖矿设备的不断进阶，挖矿门槛其实越来越高。CPU挖矿时代，只要你有一台电脑就可以挖；到了GPU挖矿，你得有好的显卡；而使用专业矿机，其购买、维护成本都大大提升，配置、使用门槛也不像使用PC那样低。此时如果再用CPU来挖矿，那么挖矿成功率简直可以忽略不计，而且专业矿机的电力损耗也非普通用户所能承受。**所以，比特币慢慢演化成了中心化的挖矿，出现了大的矿池。** 矿池对外依然是一个挖矿节点，但是集合了来自各方的算力（可以是不同矿机，或者不同用户的PC），由于算力的提升，其挖矿成功率大大提升，获取比特币后再根据算力贡献来分配比特币。
#### PoW优缺点
PoW的一个最大的缺点就是电力浪费，但也是这一特点，把经济博弈引入了区块链的防篡改机制，比如比特币会有 51% 算力攻击的问题，即攻击者只需要购买超过全网 51% 算力设备，即可发起“双花攻击”，甚至“重放攻击”等多种高收益攻击。这么做从技术角度来说篡改了区块链，但是从经济上来说确实无利可图，所以这反而使PoW反而成为一个可靠的共识机制。
除了 51% 攻击，PoW 共识还有自私挖矿的问题，自私挖矿是一种特殊的攻击类型，不会影响区块链正常运转，但是会形成矿霸，间接造成 51% 攻击。
（自私挖矿是指矿工先通过较大算力积累优势，挖出多的块的同时不广播，等别人广播一个新区块的时候，自己一下广播2个甚至更多区块，让别人一直处于被分分叉的状态，自己成为矿霸，可以形成100%出块率。）
PoW 共识机制是一种简单粗暴的共识算法，它不要求高质量的 P2P 网络资源，它可以为公链提供稳定有效的记账者筛选机制。同时它也面临了挖矿中心化严重的问题，这也促使人们研究出了新的共识机制。
### PoS
#### PoS基本原理
PoS 全称是 Proof of Stake，也即权益证明，最早出现在点点币的创始人 Sunny King 的白皮书中，它的目的就是为了解决使用 PoW 挖矿出现大量资源浪费的问题。
在讲 PoS 之前，我先来讲一个叫做币龄的概念，币龄这个概念其实很好理解，它的英文是 CoinAge，字面意思就是币数量乘以天数。
比如你有 100 个币，在某个地址上 9 天没有动，那么产生的币龄就是 900，如果你把这个地址上这 100 币转移到任意地址，包括你自己的地址，那么 900 个币龄就在转移过程中被花费了，你的币数量虽然还是 100 个，但是币龄变更为 0。币龄在数据链上就可以取到，任何人都可以验证。
我们回过头来看看 PoS 究竟是什么，区块链共识机制的第一步就是随机筛选一个记账者，PoW 是通过计算能力来获得记账权，计算能力越强，获得记账权的概率越大。
**PoS 则将此处的计算能力更换为财产证明，就是节点所拥有的币龄越多，获得的记账的概率就越大。** 这有点像公司的股权结构，股权占比大的合伙人话语权越重。
以上算是简述了 PoS 的概念，实际上，PoS 的发展经历了三个版本，第一个版本是以点点币为代币的 PoS1.0 版本，这个版本中使用的是币龄；第二个版本为代表的是黑币（blackcoin），它使用的为 PoS2.0 版本，对应这个版本使用的是币数量，相当于是财产证明，后面黑币又升级到 PoS3.0，这个版本又回到了币龄。
**PoW 早在比特币出现之前就已经应用了，而 PoS 是才是真正意义上为了区块链而创造出来的概念。**
#### PoS实现原理
对于PoW 挖矿的基本逻辑和步骤，我们先寻求一个 nonce小于目标值，这一步用公式可表示为：
```
Hash (block_header) < Target
```
从公式中我们可以看到，PoW 下所有矿工的目标值是一样的，只要计算结果哈希小于目标值即可，简化来看就是前导 0 的个数。
而在 PoS 系统中，这个公式变更为：
```
Hash (block_header) < Target * CoinAge
```
我们可以看出多引入了一个变量叫做 CoinAge，也就是币龄，这里就有意思了。
这个变量为会造成每个矿工看到的目标值不一样，如果你的币龄越大，也就意味着你的获得答案越容易。这里的 Target 与 PoW 一致，与全网难度成反比，用来控制出块速度的。
例如当前全网的目标是 4369，A 矿工的输入的币龄是 15，那么 A 矿工的目标值为 65535，换算成十六进制就是 0xFFFF，完整的哈希长度假设是 8 位，也就是 0x0000FFFF。
而 B 矿工比较有钱，他输入的币龄是 240，那么 B 矿工的目标值就是 0x000FFFFF。你如果仔细观察肯定会发现，相比 A 矿工的目标值，B 直接少了一个零。即如下：
* A 矿工 Hash( block_header ) < 0x0000FFFF
* B 矿工 Hash( block_header ) < 0x000FFFFF
所以 B矿工获得记账权的概率肯定要比 A 高。
#### PoS 的相关问题
PoS 似乎完美地解决了 PoW 挖矿资源浪费的问题，甚至还顺带解决了 51% 攻击的问题。矿工挖矿的成本不再是物理设备和电费，而是虚拟代币，它的边际成本几乎为零，本质上 PoS 让挖矿者和使用者合二为一了。
这也意味着如果挖矿者发起 51% 攻击，就需要拥有全网 51% 的币或币龄，这几乎不可能办到，即使你成功地实施了 51% 攻击，那么也意味着作为全网最大的持币大户的你，损失也会最大。
PoS 看起来相当完美，其实并不然，PoS 有很多缺陷。
PoS 遇到的第一个问题就是币发行的问题。一开始的时候，只有创始区块上有币，意味着只有这一个节点可以挖矿，所以让币分散出去才能让整个网络壮大，那么如何分散出去又是另外一个难题了。所以早期 PoS 币种基本都采用了分阶段挖矿，即第一阶段是 PoW 挖矿，到第二阶段才是 PoS 挖矿。
随着 `ERC20` 类型的标准合约`代币`的出现，这个问题被解决了，不再需要第一阶段改成 PoW，也可以将代币分散出去。
第二个问题是由于币龄是与时间挂钩的，这也意味着用户可以无限囤积一定的币，等过了很久再一次性挖矿发起攻击；所以解决方案是：PoS 机制需要引入一个时间上限来控制时间因素的自然增长。
第三个问题是虽然引入了时间上下限，用户还是倾向于囤积代币，这会造成币流通的不充分；基于此，所以瑞迪币引入了币龄按时间衰减，构造了权益速度证明，鼓励用户流动代币，而不是倾向于囤积代币。
第四个问题是离线攻击，即使引入了时间上下限，时间仍然是自然流动的，**也就是可以不需要求挖矿节点长时间在线**。挖矿是可以离线的，这简直是灾难，所以任意一个 PoS 机制的实践形式都必须避免这个问题，因为网络节点数量的多少直接关系到区块链网络的健壮性。
当然这些问题都不是致命问题，还记得我们一开始提到了 PoS 经历了三个版本，而第二个版本 PoS 2.0 使用的不是币龄，而直接是币的数量。这会造成完全不同的结果，上述第二、三、四问题都不存在了，似乎看起来直接使用币的数量会更好一些，但却出现了整个 PoS 机制的致命问题。这个问题叫做 Nothing at Stake，翻译过来叫做无成本利益问题。大体的意思在 PoS 系统中做任何事几乎没有成本，**比如在 PoS 系统上挖矿几乎没有成本，这也就意味着分叉非常方便**。方便到什么程度呢，每个诚实矿工在产生孤块的时候都可以继续挖下去，反正也没什么成本，反正分叉链和主链都可以同时挖，也就是任何持币较少的用户都可以尝试分叉，并且把分叉链广播出去。这个时候如果其他诚实矿工看到了，第一反应也是没有成本，那么咱们也来挖吧，说不定什么时候就值钱了，意思就是说任何逐利的矿工并不会使这个系统变得更强壮稳定，而是更加的混乱。
**`无成本利益问题`无论以币龄还是币数量作为 PoS 的参数，都无法避免。**
而 PoW 则没有这样的问题，我们回到 PoW 系统中来看，**因为任何的分叉都会造成挖矿成本直接变成负收益**，所以这会抵抗分叉的产生，矿工倾向于跟随“最长”的链。
由于以太坊部分采用了 PoS 共识，它的名字叫做 Casper，它必须解决上述无成本利益问题攻击。所以 Casper 协议要求PoS 矿工需通过抵押保证金的方法对共识结果进行下注，具体实践结果我们还需要拭目以待。
todo
- [ ] [pos](../Ethereum/docs/pos.md)
### DPoS
#### DPoS基本原理
DPoS (Delegated proof of stake) 共识算法， 也即委托权益证明，就是**将 PoS 共识算法中的记账者转换为指定节点数组成的小圈子，而不是所有人都可以参与记账**，这个圈子可能是 21 个节点，也有可能是 101 个节点，这一点取决于设计，只有这个圈子中的节点才能获得记账权。这将极大地提高系统的吞吐量，因为更少的节点也就意味着网络和节点的可控。
在 PoS 共识中，人们使用财产证明来“挖矿”，也就是说，这是任何人都可以参与的，只要你持有币，你就可以参与挖矿。那这会带来什么问题呢，首先无法确定记账节点的数量，其次无法确定记账节点之间的网络环境，记账节点数越多网络环境越复杂，这些不确定性会增大网络分区的概率，从而导致区块链分叉。
DPoS正是从减少记账结点入手来提高区块链性能的。它事先规定好记账节点的数量，接着让全网所有节点可以投票决定哪些节点可以成为记账节点，这样就限制并减小了记账结点数量，这个过程我们也称作**投票选举**。因为记账节点数量不多，那么我们可以在共识算法中可以规定出块时间为一个固定值，这个值可以很小，通过轮流出块的方式来进行记账。
以上思路基本就是 DPoS 的基本设计思路，BM 还为 DPoS 算法确立两个原则：
1. 投票选举过程一定要保证最大权益所有者最终能控制全网，因为一旦出了问题，他们的损失最大；
2. 与 PoW、PoS 一样，所有节点仅承认“最长”链。
这两个原则确立了 DPoS 共识的基本特性，第一条放大了 PoS 共识使用者就是记账者的优点，第二点则规定了分叉时系统应该表现的行为。
BM 认为所有区块链实际是建立交易之上的确定性状态机。共识是在确定交易顺序，过滤无效交易的一个达成一致意见的流程。
DPoS为了尽快确定交易顺序，过滤无效交易，所以规定了在正常情况下，所有记账节点轮流每 3 秒产生一个区块，轮到了某个记账节点出块时，必须在 2 秒内提交区块，否则就会错块。
假设一直没有记账节点错过自己顺序，那么他们生产的链条势必是最长的链条，如果记账节点在非指定时间生产区块被认为是无效的，每经过一轮，所有节点轮流出块的顺序就会发生重新洗牌。
下图就是一个理想的轮流记账状态。
DPoS 算法白皮书介绍了 7 种异常的情况会打破上面的正常情况。
例如少数记账节点发起恶意分叉或者发生故障，如下图。
在这种情形下，B 节点只能在 9 秒内生产 1 个块，而大多数分支，由于数量多一倍，将预期能在 9 秒内生产 2 个块，诚实的 2/3 的大多数可以比小的那一部分创建一个更长的链条，由于原则二，DPoS 可以抵御这种攻击。
在 [DPoS 白皮书](http://me.tryblockchain.org/blockchain-dpos-bm-eos.html)中介绍了少数记账节点恶意或故障造成的分叉、网络分区情况下重复出块、少数记账节点重复出块、记账节点数量不足、多数记账节点的联合腐败等各种情况。
在实际应用中，比特股中见证人是 101 人，EOS 里是 21 人。比特股中见证人们赚取手续费，EOS 里见证人们分享 EOS 的通胀收益。他们都是通过公开选举选出来的，选票就是大家手里的比特股或 EOS。
#### BFT-DPoS (EOS new)
https://zhuanlan.zhihu.com/p/35591268
#### DPoS的劣势
在PoW中，矿工、开发者、用户三权分立，而在DPoS中，少数超级结点拥有绝对的记账权利，使得达成共识所需的时间大大减少，系统吞吐率大大提高，这是 DPoS 算法的优势；但这也使得DPoS更像一个中心化的分布式系统，也是 DPoS 算法的劣势。
从某种角度来看，DPoS 是社区治理加上共识算法，不再是单纯的技术共识，这是与 PoW、PoS 算法最大的不同。
**DPoS 的基本假设是相信节点是好的，所以尽可能快速选择记账节点，而把问题发生后的修复过程推迟到投票中，可以说 DPoS 并不考虑拜占庭容错问题，把拜占庭容错推给了社区治理，而在社区治理上可归纳为一切皆投票。**
而现实生活中，很多情况下，投票并不能解决问题，比如投票人都是有惰性的，集齐所有人投票成本是很高的，如果记账节点没有上限，所有节点的投票都投给自己，DPoS 系统就会退化成 PoS 系统。
### PBFT
- [x] [PBFT算法](https://www.jianshu.com/p/2383c7841d41)
- [x] [区块链核心技术：拜占庭共识算法之PBFT](https://www.jianshu.com/p/fb5edf031afd)
拜占庭将军问题是指系统中除了网络延迟、系统宕机等问题外还存在恶意节点，会进行“精神分裂式”投票。BFT（Byzantine Fault Tolerance）系统是指能够容忍拜占庭将军问题的系统，而PBFT（Practical Byzantine Fault Tolerance）则是其具体实现算法。其主旨是：**当存在f个失效节点时必须保证存在至少3f+1个副本数量，这样才能保证在异步系统中提供安全性和活性**。这么多数量的副本是需要的，因为在同n-f个节点通讯后系统必须做出正确判断，由于f个副本有可能失效而不发回响应。但是，有可能f个没有失效的副本不发回响应（是因为网络延迟吗？），因此f个发回响应的副本有可能是失效的。尽管如此，系统仍旧需要足够数量非失效节点的响应，并且这些非失效节点的响应数量必须超过失效节点的响应数量，即n-2f>f，因此得到n>3f。
PBFT是一种状态机副本复制算法，即服务作为状态机进行建模，状态机在分布式系统的不同节点进行副本复制。每个状态机的副本都保存了服务的状态，同时也实现了服务的操作。将所有的副本组成的集合使用大写字母R表示，使用0到|R|-1的整数表示每一个副本。为了描述方便，假设|R|=3f+1，这里f是有可能失效的副本的最大个数。尽管可以存在多于3f+1个副本，但是额外的副本除了降低性能之外不能提高可靠性。
所有的副本在一个被称为视图（View）的轮换过程（succession of configuration）中运作。**在某个视图中，一个副本作为主节点（primary），其他的副本作为备份（backups）**。视图是连续编号的整数。主节点由公式p = v mod |R|计算得到，这里v是视图编号，p是副本编号，|R|是副本集合的个数。当主节点失效的时候就需要启动视图更换（view change）过程。Viewstamped Replication算法和Paxos算法就是使用类似方法解决良性容错的。
1. 客户端向主节点发送请求调用服务操作
2. 主节点通过广播将请求发送给其他副本（三阶段协议）
3. 所有副本都执行请求并将结果发回客户端
4. 客户端需要等待f+1个不同副本节点发回相同的结果，作为整个操作的最终结果。
三阶段协议分为预准备（pre-prepare）、准备(prepare)和确认(commit)这三个阶段。**预准备和准备两个阶段用来确保同一个视图中请求发送的时序性（即使对请求进行排序的主节点失效了），准备和确认两个阶段用来确保在不同的视图之间的确认请求是严格排序的。**
#### pre-prepare
在预准备阶段，主节点分配一个序列号n给收到的请求，然后向所有备份节点 **群发预准备消息**，预准备消息的格式为`<<PRE-PREPARE,v,n,d>`,m>，这里v是视图编号，m是客户端发送的请求消息，d是请求消息m的摘要。
请求本身是不包含在预准备的消息里面的，这样就能使预准备消息足够小，**因为预准备消息的目的是作为一种证明，确定该请求是在视图v中被赋予了序号n，从而在视图变更的过程中可以追索**。另外一个层面，将“请求排序协议”和“请求传输协议”进行解耦，有利于对消息传输的效率进行深度优化。
只有满足以下条件，各个备份节点才会接受一个预准备消息：
1. 请求和预准备消息的签名正确，并且d与m的摘要一致。
2. 当前视图编号是v。
3. 该备份节点从未在视图v中接受过序号为n但是摘要d不同的消息m。
4. 预准备消息的序号n必须在水线（watermark）上下限h和H之间。
watermark存在的意义在于防止一个失效节点使用一个很大的序号消耗序号空间。
#### prepare
**如果备份节点i接受了预准备消息`<<PRE-PREPARE,v,n,d>,m>`，则进入准备阶段**。在准备阶段的同时，**该节点向所有副本节点发送准备消息`<PREPARE,v,n,d,i>`，并且将预准备消息和准备消息写入自己的消息日志**。如果看预准备消息不顺眼，就什么都不做。
包括主节点在内的所有副本节点在收到准备消息之后，对消息的签名是否正确，视图编号是否一致，以及消息序号是否满足watermark限制这三个条件进行验证，如果验证通过则把这个准备消息写入消息日志中。
我们定义 **准备阶段完成的标志为副本节点i将(m,v,n,i)记入其消息日志**，其中m是请求内容，预准备消息m在视图v中的编号n，**以及`2f`个从不同副本节点收到的与预准备消息一致的准备消息**。每个副本节点验证预准备和准备消息的一致性主要检查：视图编号v、消息序号n和摘要d。
**预准备阶段和准备阶段确保所有正常节点对同一个视图中的请求序号达成一致。**接下去是对这个结论的形式化证明：如果prepared(m,v,n,i)为真，则prepared(m',v,n,j)必不成立，这就意味着至少f+1个正常节点在视图v的预准备或者准备阶段发送了序号为n的消息m。
#### commit
当(m,v,n,i)条件为真的时候，**副本i将`<COMMIT,v,n,D(m),i>`向其他副本节点广播，于是就进入了确认阶段**。每个副本接受确认消息的条件是：1）签名正确；2）消息的视图编号与节点的当前视图编号一致；3）消息的序号n满足watermark条件，在h和H之间。一旦确认消息的接受条件满足了，则该副本节点将确认消息写入消息日志中。
我们定义确认完成committed(m,v,n)为真得条件为：任意f+1个正常副本节点集合中的所有副本i其prepared(m,v,n,i)为真；**本地确认完成committed-local(m,v,n,i)为真的条件为：prepared(m,v,n,i)为真，并且i已经接受了2f+1个确认（包括自身在内）与预准备消息一致**。确认与预准备消息一致的条件是具有相同的视图编号、消息序号和消息摘要。
**每个副本节点i在committed-local(m,v,n,i)为真之后执行m的请求**，并且i的状态反映了所有编号小于n的请求依次顺序执行。这就确保了所有正常节点以同样的顺序执行所有请求，这样就保证了算法的正确性。**在完成请求的操作之后，每个副本节点都向客户端发送回复**。副本节点会把时间戳比已回复时间戳更小的请求丢弃，以保证请求只会被执行一次。
下图展示了在没有发生主节点失效的情况下算法的正常执行流程，其中副本0是主节点，副本3是失效节点，而C是客户端。
