1.PoW：
工作量证明的基本原理
工作量证明系统主要特征是客户端需要做一定难度的工作得出一个结果，验证方却很容易通过结果来检查出客户端是不是做了相应的工作。这种方案的一个核心特征是不对称性：工作对于请求方是适中的，对于验证方则是易于验证的。它与验证码不同，验证码的设计出发点是易于被人类解决而不易被计算机解决。
下图表示的是工作量证明的流程：
"Hello, world!1" => e9afc424b79e4f6ab42d99c81156d3a17228d6e1eef4139be78e948a9332a7d8 "Hello, world!2" => ae37343a357a8297591625e7134cbea22f5928be8ca2a32aa475cf05fd4266b7 ... "Hello, world!4248" => 6e110d98b388e77e9c6f042ac6b497cec46660deef75a55ebc7cfdf65cc0b965
"Hello, world!4249" => c004190b822f1669cac8dc37e761cb73652e7832fb814565702245cf26ebb9e6
"Hello, world!4250" => 0000c3af42fc31103f1fdc0151fa747ff87349a4714df7cc52ea464e12dcd4e9
通过这个示例我们对工作量证明机制有了一个初步的理解。有的人会认为如果工作量证明只是这样的一个过程，那是不是只需要记住nonce为4521计算能通过验证就行了？当然不是的，这只是一个个例。
下面，我们将输入简单的变更为"Hello, world+整数值"，整数值取1到1000，也就是说，将输入变成一个由1000个值组成的数组："Hello, world!1、Hello, world!2……Hello, world!1000"。然后对数组中的每一个输入依次进行上面例子中要求的工作量证明——找到前导为4个0的哈希散列。
容易算出，预期大概要进行2^16 次尝试（哈希值的伪随机特性使得我们可以做概率估算），才能得到4个前导0的哈希散列。而统计一下刚才进行的1000次计算的实际计算结果，我们会发现，进行计算的平均次数为66958次，十分接近2^16（65536）。在这个例子中，数学期望的计算次数，就是我们要求的“工作量”，重复多次进行的工作量证明会是一个符合统计学规律的概率事件。
统计输入的字符串与对应得到目标结果实际使用的计算次数列表如下：
Hello, world!1 => 42153 Hello, world!2 => 2643 Hello, world!3 => 32825 Hello, world!4 => 250 Hello, world!5 => 7300 ... Hello, world!995 => 164819 Hello, world!996 => 178486 Hello, world!997 => 22798 Hello, world!998 => 68868 Hello, world!999 => 46821
比特币体系里的工作量证明机制与上述示例类似，但要比它更复杂一些。
比特币中的工作量证明
比特币网络中任何一个节点，如果想生成一个新的区块并写入区块链，必须解出比特币网络出的工作量证明的迷题。这道题关键的三个要素是工作量证明函数、区块及难度值。工作量证明函数是这道题的计算方法，区块决定了这道题的输入数据，难度值决定了这道题的所需要的计算量。
1工作量证明函数
和我们上节例子中用到的哈希函数一样，比特币系统中使用的工作量证明函正是SHA256。
SHA是安全散列算法（Secure Hash Algorithm）的缩写，是一个密码散列函数家族。这一组函数是由美国国家安全局（NSA）设计，美国国家标准与技术研究院（NIST） 发布的，主要适用于数字签名标准。SHA256就是这个函数家族中的一个，是输出值为256位的哈希算法。到目前为止，还没有出现对SHA256算法的有效攻击。
2 区块
比特币的区块由区块头及该区块所包含的交易列表组成。区块头的大小为80字节，由4字节的版本号、32字节的上一个区块的散列值、32字节的Merkle Root Hash、4字节的时间缀（当前时间）、4字节的当前难度值、4字节的随机数组成。区块包含的交易列表则附加在区块头后面，其中的第一笔交易是coinbase交易，这是一笔为了让矿工获得奖励及手续费的特殊交易。
区块的大致结构如图所示：
3难度值
难度值（difficulty）是矿工们在挖矿时候的重要参考指标，它决定了矿工大约需要经过多少次哈希运算才能产生一个合法的区块。比特币的区块大约每10分钟生成一个，如果要在不同的全网算力条件下，新区块的产生保持都基本这个速率，难度值必须根据全网算力的变化进行调整。简单地说，难度值被设定在无论挖矿能力如何，新区块产生速率都保持在10分钟一个。
难度的调整是在每个完整节点中独立自动发生的。每2016个区块，所有节点都会按统一的公式自动调整难度，这个公式是由最新2016个区块的花费时长与期望时长（期望时长为20160分钟即两周，是按每10分钟一个区块的产生速率计算出的总时长）比较得出的，根据实际时长与期望时长的比值，进行相应调整（或变难或变易）。也就是说，如果区块产生的速率比10分钟快则增加难度，比10分钟慢则降低难度。
这个公式可以总结为如下形式：
新难度值 = 旧难度值 * ( 过去2016个区块花费时长 / 20160 分钟 )
工作量证明需要有一个目标值。比特币工作量证明的目标值（Target）的计算公式如下：
目标值 = 最大目标值 / 难度值
其中最大目标值为一个恒定值：
0x00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
目标值的大小与难度值成反比。比特币工作量证明的达成就是矿工计算出来的区块哈希值必须小于目标值。
与第3节所举的例子相类比，我们也可以简单理解成，比特币工作量证明的过程，就是通过不停的变换区块头（即尝试不同的nouce值）作为输入进行SHA256哈希运算，找出一个特定格式哈希值的过程（即要求有一定数量的前导0）。而要求的前导0的个数越多，代表难度越大。
4 工作量证明的过程
我们可以把比特币矿工解这道工作量证明迷题的步骤大致归纳如下：
生成Coinbase交易，并与其他所有准备打包进区块的交易组成交易列表，通过Merkle Tree算法生成Merkle Root Hash
把Merkle Root Hash及其他相关字段组装成区块头，将区块头的80字节数据（Block Header）作为工作量证明的输入
不停的变更区块头中的随机数即nonce的数值，并对每次变更后的的区块头做双重SHA256运算（即SHA256(SHA256(Block_Header))），将结果值与当前网络的目标值做对比，如果小于目标值，则解题成功，工作量证明完成。
该过程可以用下图表示：
作者：wycandyy
链接：https://www.jianshu.com/p/b23cbafbbad2
來源：简书
简书著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。
2.PoS
POS是一类共识算法，或者说是一类共识算法的设计思想，而不是一个，最早采用POS的是Peercoin。Peercoin是2012年8月，一个化名Sunny King的极客推出的一类加密货币，采用工作量证明机制+权益证明机制，首次将权益证明机制引入了加密货币。Peercoin引入了“币龄”的概念，每个币每天产生1币龄，比如你持有100个币，总共持有了30天，那么，此时你的币龄就为3000。当一个新的区块产生时，其他想获得记账权的节点同比特币也需要计算哈希值，得出满足条件哈希值的难易与难度值有关，这个难度值这里与币龄成反比，即你的币龄越大，得出符合条件的哈希值的概率就越大，同时你的币龄被清空，记账后系统会给予你相应“利息”，你每被清空365币龄，获得利息为：3000 * 利率 / 365，Peercoin的利率为1%，即0.08个币。
可以看出，在POS机制下，持有币越多，越容易获得记账权，接近于赢家通吃的感觉，但持有的币越多，越接近于一个诚实的节点，因为破坏整个网络带来的损失也越大。Peercoin的POS机制有一个漏洞，对于不持有币的人而言，他们本来就没什么收益，所以一些恶意攻击对于他们则是无损失的，这就是Nothing-at-stake attack（无利益攻击）。后续的比较成功的POS都引入了对付这种攻击的机制。
以太坊系统的目标是在今年引入权益证明，即Casper。在权益证明共识机制之下，用户将能够在以太坊网络拥有“币权”。用户如果诚实行事并确认了合法交易，将获得与其股权成比的利息；如果恶意行事并试图网络中作弊，就会失去其权益。
本质上，POW和POS都是一种随机选择下一个区块上传者的方式。然而，创建一个每个人被选中几率相等的算法其实是非常难的事情，同时，这种算法只是听上去很美，而在现实中这种算法却称不上公平——因为你怎么在虚拟世界里确定一个人的身份？你怎么知道一个ID背后的是真实的用户还是女巫攻击的脚本？
所以说，与其耐心去验证每一个人的身份，不如干脆根据某种无法伪造的东西进行随机，于是才有了工作证明和权益证明，以及许许多多的其他证明。
POW就是根据计算能力随机，POS根据拥有财产随机。
这就是这两个共识机制的本质。
但是，另一个问题是，POW是一个在比特币出现之前就有了的东西，而因为比特币的成功，POW基本上特指比特币的POW。但相反，POS是个新东西，目前并没有成熟的POS应用，所以，当提到POS的时候，并不是指某一个算法，而是一类，而且，这类算法目前各有优劣。并且，目前为止，没有一个算法的可靠性通过了实践的检验。所以，要对比POW和POS的优劣，我只能以POS这一大类为例。以上基本上所有其他的答案，其实都在说PPCoin的POS，也就是最早的POS，那个东西是有根本缺陷的，例如啥币龄攻击（save-up attack），都仅仅是对PPC适用，而并不是POS的问题。
下面说优劣。
POW：
优势：可靠（或者叫安全，我不喜欢用安全这个词），这就是它最大的优点，因为它是目前唯一接受了实践检验的公有链算法。
劣势：浪费算力，对于51%攻击有潜在隐患——攻击者并不需要拥有比特币，所以如果要做51%攻击，所需要的花费跟挖矿难度相关而不是直接跟比特币价格相关（虽然说挖矿难度会和比特币价格相关），所以，如果挖矿公司的市值不如比特币的价格的话，比特币面临51%攻击的风险就会变大。
POS：
优势：不需要浪费算力，同时，进行51%攻击的代价更高，因为想要进行51%攻击的话，你得拥有51%的货币。也就是说，这东西越值钱，攻击的成本就越高。
劣势：
1，权益粉碎攻击（nothing-at-the-stake attack），上面有人说POS是*，我是不赞同的。我觉得POS就是完全的资本主义——你钱越多，你拥有的权力就越大。当然，这个也并不是没有道理，因为在其中利益越多的人，就更愿意去维护这个币的系统，于是他们手中的币才能更有价值。因此，他们并不愿意去进行恶意攻击，因为那样实际上他们手中的币也会受害，这就是POS能够更有效地防御51%攻击的原因。换句话说，钱越多责任越大。
但反过来讲，钱越少责任越小。假设你只有1%的钱，你成功的概率只有1%，但是你尽可以去尝试分叉，因为这并不消耗任何资源。也就是你在最长链上挖矿的同时，也去创造一个只在自己的区块上挖矿的分支。放在POW里，创建这个分支完全得不偿失因为你浪费了大量的算力。然而在POS里，如果这个分支不被接收，实际上你什么都没损失。于是，即便是诚实的矿工也可能回去偷偷地进行这种分叉尝试。尽管他们知道这种尝试会造成整个币的价值降低，但是他们的钱很少，他们并不在乎，这就是所谓的平凡人悲剧（tragedy of the commons）。
对于这种攻击，基本上所有的新的POS算法都有应对的机制，例如以太坊的casper里的slasher，基本概念就是如果有人尝试了这种攻击，其他人发现了可以公布证据然后对这个人进行惩罚。
2，理性分叉。很多地方把这个合在权益粉碎攻击里了，但我觉得必须要分出来说。
权益粉碎攻击是主动的，而这个是被动的——假设有人做了权益粉碎攻击进行了分叉尝试，诚实节点理应不予理会，因为他们能看到这种分叉被接受的几率小。对于POW来说，你不会在被接收几率小的分叉（例如不是最长链的分叉）上挖矿，因为那样浪费算力。但对于POS来说，在那上面挖矿没任何损失，反而是不在那上面挖矿，万一这条链被接收了，你就会受到损失。
于是，即便是诚实节点，如果它足够理性，那么它也会在所有它收到的链上同时挖矿。POW里，没人挖的分支很快就会变成孤块被丢弃，但在POS里，如果整个网络足够理性，会出现的情况反而是每条分支都会永远存在因为理性的矿工会同时在所有分支上挖矿。这是我觉得POS最大的缺陷，就是如果只用最长链共识的话，POS本身是没法应对分叉的，必须通过惩罚。而这种惩罚不光是基于作恶，而是违反节点逐利本性的。
放在真实社会中的话，1就好比是抢劫，抓了判刑没有任何问题。可是2就像是投资，把他们也抓了判刑，这就有点过了。
POW：
我们熟悉的比特币的工作机制是POW，即Proof of work, 工作量证明机制。
POS:
POS就是“股权证明”,Proof of stake，即直接证明你持有的份额。除了混合性的PPC之外，真正的POS币是没有挖矿过程的，也就是在创世区块内就写明了股权证明，之后的股权证明只能转让，不能挖矿。
在现实世界中股权证明很普遍，最简单的就是股票。股票是用来记录股权的证明，同时代表着投票权和收益权。股票被创造出来以后，除了增发外，不能增加股权数量，要获得股票只能转让。
在纯POS体系中，如NXT，没有挖矿过程，初始的股权分配已经固定，之后只是股权在交易者之中流转，非常类似于现实世界的股票。股权从创世区块中流出，被交易者买卖而逐渐分散化。
POS的新增机制是“利息”，即持有一定的POS币一定时间，当然得开着客户端，将获得一定量的固定“利息”。这部分“利息”是新增的POS币。只要你持有POS币并开机，你就能获得一定比例的“利息”。
我们也应该看到，POW的安全性是不断积聚起来的(明智的攻击者仅仅会选择攻击最近产出的块)，而POS的攻击者可能轻易发起数百个块的攻击(成本低)。
POS币龄引起了以下的问题：
1. 攻击者可以把足够的币龄积攒起来, 从而成为网络上拥有最高权重的节点。如果攻击是恶意的，攻击者可以对区块链进行分叉并达成双花。一个占1%的币的用户，可以憋个两个月不挖矿，来攻击网络。
2. 另一种情况是这些币龄属于贪婪但却诚实的节点。有一些节点并没有恶意, 但是他们的钱包平时都是离线的, 只是偶尔进行同步以获得利息。币龄系统事实上鼓励了这些节点滥用这一机制，他们平时保持离线，只在累积了可观的币龄以后才连线以获得利息，然后再次关闭。而这样的化，马币钱包在线挖矿的币的数目就少，容易发生攻击，而且更加严重的是，由于节点缺乏，数据同步的速度，交易响应速度都会受到影响。
去除币龄，PoS虚拟币重获新生
PPC有币龄，BLK最新的改进协议貌似已经取消币龄限制，Blackcoin自2014年成立以来，已经实施了3个POS版本。版本2解决了许多潜在的安全问题，并阻截了网络滥用问题。版本3进行了一些更新，最显著的改变是从1%的年度POS奖励变为静态1.5BLK(黑币)，改成500确认提高安全性又兼顾了流动性，细节的改进很多很多，懂技术的可以自己研究。这意味着只有参与保护网络安全的Blackcoin所有者，通过让他们的钱包保持在线状态，才有机会获得一个区块。
这个挺有意思，大杂烩？过程挺详细。。。Qtum ICO信息跟踪:Qtum开发团队已将POS 3.0共识机制融合到Bitcoin Core V0.13版本
作者：菠菜philsong
链接：https://www.jianshu.com/p/85adfdaac203
來源：简书
简书著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。
PBFT是Practical Byzantine Fault Tolerance的缩写，意为实用拜占庭容错算法。该算法是Miguel Castro (卡斯特罗)和Barbara Liskov（利斯科夫）在1999年提出来的，解决了原始拜占庭容错算法效率不高的问题，将算法复杂度由指数级降低到多项式级，使得拜占庭容错算法在实际系统应用中变得可行。该论文发表在1999年的操作系统设计与实现国际会议上（OSDI99）。没错，这个Loskov就是提出著名的里氏替换原则（LSP）的人，2008年图灵奖得主。
摘要部分
OSDI99这篇论文描述了一种副本复制（replication）算法解决拜占庭容错问题。作者认为拜占庭容错算法将会变得更加重要，因为恶意攻击和软件错误的发生将会越来越多，并且导致失效的节点产生任意行为。（拜占庭节点的任意行为有可能误导其他副本节点产生更大的危害，而不仅仅是宕机失去响应。）而早期的拜占庭容错算法或者基于同步系统的假设，或者由于性能太低而不能在实际系统中运作。这篇论文中描述的算法是实用的，因为该算法可以工作在异步环境中，并且通过优化在早期算法的基础上把响应性能提升了一个数量级以上。作者使用这个算法实现了拜占庭容错的网络文件系统（NFS），性能测试证明了该系统仅比无副本复制的标准NFS慢了3%。
1.概要介绍
第一段大片废话就是说明拜占庭算法越来越重要了，然后说这篇论文提出解决拜占庭容错的状态机副本复制（state machine replication）算法。这个算法在保证活性和安全性（liveness & safety）的前提下提供了(n-1)/3的容错性。从Lamport教授在1982年提出拜占庭问题开始，已经有一大堆算法去解决拜占庭容错了。但是一句话概括：这些算法都是*！PBFT算法跟这些妖艳贱货完全不同，在只读操作中只使用1次消息往返（message round trip），在只写操作中只使用2次消息往返，并且在正常操作中使用了消息验证编码（Message Authentication Code,简称MAC），而造成妖艳贱货性能低下的公钥加密（public-key cryptography）只在发生失效的情况下使用。作者不仅提出算法，而且使用这个算法实现了一个牛逼的系统（拜占庭容错的NFS），反正性能杠杠的。
作者先炫耀一下这边论文的贡献亮瞎你们的狗眼：
1）首次提出在异步网络环境下使用状态机副本复制协议
2）使用多种优化使性能显著提升
3）实现了一种拜占庭容错的分布式文件系统
4）为副本复制的性能损耗提供试验数据支持
2.系统模型
这部分主要对节点行为和网络环境进行剧情设定，然后赋予了消息的加密属性，最后对大魔王的能力进行设定。
系统假设为异步分布式的，通过网络传输的消息可能丢失、延迟、重复或者乱序。作者假设节点的失效必须是独立发生的，也就是说代码、操作系统和管理员密码这些东西在各个节点上是不一样的。（那么如果节点失效不独立发生，PBFT算法就失效了吗？）
作者使用了加密技术来防止欺骗攻击和重播攻击，以及检测被破坏的消息。消息包含了公钥签名（其实就是RSA算法）、消息验证编码（MAC）和无碰撞哈希函数生成的消息摘要（message digest）。使用m表示消息，mi表示由节点i签名的消息，D(m)表示消息m的摘要。按照惯例，只对消息的摘要签名，并且附在消息文本的后面。并且假设所有的节点都知道其他节点的公钥以进行签名验证。
系统允许大魔王可以操纵多个失效节点、延迟通讯、甚至延迟正确节点来毁灭世界。但是作者限定大魔王不能无限期地延迟正确的节点，并且大魔王算力有限不能破解加密算法。例如，大魔王不能伪造正确节点的有效签名，不能从摘要数据反向计算出消息内容，或者找到两个有同样摘要的消息。
3.服务属性
这部分描述了副本复制服务的特性
针对安全性
针对活性
下面这段话是关键
本文的算法弹性是达到最优的：当存在f个失效节点时必须保证存在至少3f+1
个副本数量，这样才能保证在异步系统中提供安全性和活性。这么多数量的副本是需要的，因为在同n-f个节点通讯后系统必须做出正确判断，由于f个副本有可能失效而不发回响应。但是，有可能f个没有失效的副本不发回响应（是因为网络延迟吗？），因此f个发回响应的副本有可能是失效的。尽管如此，系统仍旧需要足够数量非失效节点的响应，并且这些非失效节点的响应数量必须超过失效节点的响应数量，即n-2f>f，因此得到n>3f。
算法不能解决信息保密的问题，失效的副本有可能将信息泄露给攻击者。在一般情况下不可能提供信息保密，因为服务操作需要使用参数和服务状态处理任意的计算，所有的副本都需要这些信息来有效执行操作。当然，还是有可能在存在恶意副本的情况下通过秘密分享模式（secret sharing scheme）来实现私密性，因为参数和部分状态对服务操作来说是不可见的。
4.算法
PBFT是一种状态机副本复制算法，即服务作为状态机进行建模，状态机在分布式系统的不同节点进行副本复制。每个状态机的副本都保存了服务的状态，同时也实现了服务的操作。将所有的副本组成的集合使用大写字母R表示，使用0到|R|-1的整数表示每一个副本。为了描述方便，假设|R|=3f+1，这里f是有可能失效的副本的最大个数。尽管可以存在多于3f+1个副本，但是额外的副本除了降低性能之外不能提高可靠性。
PBFT的剧情缓缓展开，首先介绍舞台（view）、演员（replica）和角色（primary、backups）
所有的副本在一个被称为视图（View）的轮换过程（succession of configuration）中运作。在某个视图中，一个副本作为主节点（primary），其他的副本作为备份（backups）。视图是连续编号的整数。主节点由公式p = v mod |R|计算得到，这里v是视图编号，p是副本编号，|R|是副本集合的个数。当主节点失效的时候就需要启动视图更换（view change）过程。Viewstamped Replication算法和Paxos算法就是使用类似方法解决良性容错的。
PBFT算法的狗血剧情如下：
1.客户端向主节点发送请求调用服务操作
2.主节点通过广播将请求发送给其他副本
3.所有副本都执行请求并将结果发回客户端
4.客户端需要等待f+1个不同副本节点发回相同的结果，作为整个操作的最终结果。
同所有的状态机副本复制技术一样，PBFT对每个副本节点提出了两个限定条件：（1）所有节点必须是确定性的。也就是说，在给定状态和参数相同的情况下，操作执行的结果必须相同；（2）所有节点必须从相同的状态开始执行。在这两个限定条件下，即使失效的副本节点存在，PBFT算法对所有非失效副本节点的请求执行总顺序达成一致，从而保证安全性。
接下去描述简化版本的PBFT算法，忽略磁盘空间不足和消息重传等细节内容。并且，本文假设消息验证过程是通过数字签名方法实现的，而不是更加高效的基于消息验证编码（MAC）的方法。
4.1客户端
客户端c向主节点发送<REQUEST,o,t,c>请求执行状态机操作o，这里时间戳t用来保证客户端请求只会执行一次。客户端c发出请求的时间戳是全序排列的，后续发出的请求比早先发出的请求拥有更高的时间戳。例如，请求发起时的本地时钟值可以作为时间戳。
每个由副本节点发给客户端的消息都包含了当前的视图编号，使得客户端能够跟踪视图编号，从而进一步推算出当前主节点的编号。客户端通过点对点消息向它自己认为的主节点发送请求，然后主节点自动将该请求向所有备份节点进行广播。
副本发给客户端的响应为<REPLY,v,t,c,i,r>，v是视图编号，t是时间戳，i是副本的编号，r是请求执行的结果。
客户端等待f+1个从不同副本得到的同样响应，同样响应需要保证签名正确，并且具有同样的时间戳t和执行结果r。这样客户端才能把r作为正确的执行结果，因为失效的副本节点不超过f个，所以f+1个副本的一致响应必定能够保证结果是正确有效的。
如果客户端没有在有限时间内收到回复，请求将向所有副本节点进行广播。如果请求已经在副本节点处理过了，副本就向客户端重发一遍执行结果。如果请求没有在副本节点处理过，该副本节点将把请求转发给主节点。如果主节点没有将该请求进行广播，那么就有认为主节点失效，如果有足够多的副本节点认为主节点失效，则会触发一次视图变更。
本文假设客户端会等待上一个请求完成才会发起下一个请求，但是只要能够保证请求顺序，可以允许请求是异步的。
4.2 PBFT算法主线流程（正常情况）
世界格局
每个副本节点的状态都包含了服务的整体状态，副本节点上的消息日志(message log)包含了该副本节点接受(accepted)的消息，并且使用一个整数表示副本节点的当前视图编号。
事件的导火索
当主节点p收到客户端的请求m，主节点将该请求向所有副本节点进行广播，由此一场轰轰烈烈的三阶段协议（three-phase protocol）拉开了序幕。在这里，至于什么消息过多需要缓存的情况我们就不管了，这不是重点。
三个阶段的任务
我们重点讨论预准备（pre-prepare）、准备(prepare)和确认(commit)这三个历史性阶段。预准备和准备两个阶段用来确保同一个视图中请求发送的时序性（即使对请求进行排序的主节点失效了），准备和确认两个阶段用来确保在不同的视图之间的确认请求是严格排序的。
预准备阶段
在预准备阶段，主节点分配一个序列号n给收到的请求，然后向所有备份节点群发预准备消息，预准备消息的格式为<<PRE-PREPARE,v,n,d>,m>，这里v是视图编号，m是客户端发送的请求消息，d是请求消息m的摘要。
请求本身是不包含在预准备的消息里面的，这样就能使预准备消息足够小，因为预准备消息的目的是作为一种证明，确定该请求是在视图v中被赋予了序号n，从而在视图变更的过程中可以追索。另外一个层面，将“请求排序协议”和“请求传输协议”进行解耦，有利于对消息传输的效率进行深度优化。
备份节点对预准备消息的态度
只有满足以下条件，各个备份节点才会接受一个预准备消息：
- 请求和预准备消息的签名正确，并且d与m的摘要一致。
- 当前视图编号是v。
- 该备份节点从未在视图v中接受过序号为n但是摘要d不同的消息m。（许仙在这辈子从未见过名字叫白素贞的美貌女子）
- 预准备消息的序号n必须在水线（watermark）上下限h和H之间。
水线存在的意义在于防止一个失效节点使用一个很大的序号消耗序号空间。
进入准备阶段
如果备份节点i接受了预准备消息<<PRE-PREPARE,v,n,d>,m>，则进入准备阶段。在准备阶段的同时，该节点向所有副本节点发送准备消息<PREPARE,v,n,d,i>，并且将预准备消息和准备消息写入自己的消息日志。如果看预准备消息不顺眼，就什么都不做。
接受准备消息需要满足的条件
包括主节点在内的所有副本节点在收到准备消息之后，对消息的签名是否正确，视图编号是否一致，以及消息序号是否满足水线限制这三个条件进行验证，如果验证通过则把这个准备消息写入消息日志中。
准备阶段完成的标志
我们定义准备阶段完成的标志为副本节点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,v,n,D(m),i>向其他副本节点广播，于是就进入了确认阶段。每个副本接受确认消息的条件是：1）签名正确；2）消息的视图编号与节点的当前视图编号一致；3）消息的序号n满足水线条件，在h和H之间。一旦确认消息的接受条件满足了，则该副本节点将确认消息写入消息日志中。（补充：需要将针对某个请求的所有接受的消息写入日志，这个日志可以是在内存中的）。接受确认消息需要满足的条件
确认被接受的形式化描述
故事的终结
每个副本节点i在committed-local(m,v,n,i)为真之后执行m的请求，并且i的状态反映了所有编号小于n的请求依次顺序执行。这就确保了所有正常节点以同样的顺序执行所有请求，这样就保证了算法的正确性（safety）。在完成请求的操作之后，每个副本节点都向客户端发送回复。副本节点会把时间戳比已回复时间戳更小的请求丢弃，以保证请求只会被执行一次。
我们不依赖于消息的顺序传递，因此某个副本节点可能乱序确认请求。因为每个副本节点在请求执行之前已经将预准备、准备和确认这三个消息记录到了日志中，这样乱序就不成问题了。（为什么？）
下图展示了在没有发生主节点失效的情况下算法的正常执行流程，其中副本0是主节点，副本3是失效节点，而C是客户端。
4.3 垃圾回收
为了节省内存，系统需要一种将日志中的无异议消息记录删除的机制。为了保证系统的安全性，副本节点在删除自己的消息日志前，需要确保至少f+1个正常副本节点执行了消息对应的请求，并且可以在视图变更时向其他副本节点证明。另外，如果一些副本节点错过部分消息，但是这些消息已经被所有正常副本节点删除了，这就需要通过传输部分或者全部服务状态实现该副本节点的同步。因此，副本节点同样需要证明状态的正确性。
在每一个操作执行后都生成这样的证明是非常消耗资源的。因此，证明过程只有在请求序号可以被某个常数（比如100）整除的时候才会周期性地进行。我们将这些请求执行后得到的状态称作检查点（checkpoint），并且将具有证明的检查点称作稳定检查点（stable checkpoint）。
副本节点保存了服务状态的多个逻辑拷贝，包括最新的稳定检查点，零个或者多个非稳定的检查点，以及一个当前状态。写时复制技术可以被用来减少存储额外状态拷贝的空间开销。
检查点的正确性证明的生成过程如下：当副本节点i生成一个检查点后，向其他副本节点广播检查点消息<CHECKPOINT,n,d,i>，这里n是最近一个影响状态的请求序号，d是状态的摘要。每个副本节点都默默地在各自的日志中收集并记录其他节点发过来的检查点消息，直到收到来自2f+1个不同副本节点的具有相同序号n和摘要d的检查点消息。这2f+1
个消息就是这个检查点的正确性证明。
具有证明的检查点成为稳定检查点，然后副本节点就可以将所有序号小于等于n的预准备、准备和确认消息从日志中删除。同时也可以将之前的检查点和检查点消息一并删除。
检查点协议可以用来更新水线（watermark）的高低值（h和H），这两个高低值限定了可以被接受的消息。水线的低值h与最近稳定检查点的序列号相同，而水线的高值H=h+k，k需要足够大才能使副本不至于为了等待稳定检查点而停顿。加入检查点每100个请求产生一次，k的取值可以是200。
4.4 视图变更，改朝换代
使用计时器的超时机制触发视图变更事件
链接：https://www.jianshu.com/p/fb5edf031afd
來源：简书
简书著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。
