99%容错共识指南
每晚八点，我们在社区分享知识，等你。
NervosFans 微信公号：Nervosfans
入群请加乐乐微信：sensus113 美果大冰微信：xj73226
备注入群，谢谢！
特别感谢Emin Gun Sirer对本文的审阅。
我们一直都知道，诚实节点广播的消息在已知时间段内为其他诚实节点接收的同步网络中，共识可以通过50％容错实现。（掌握超过50%容错的攻击者可发动‘51%攻击’，同类型算法下都存在原理类似的攻击可能）。我们也知道，抛开同步假设，“异步安全”的算法也是有的，但是可实现的最大容错则降低至33％（PBFT，Casper FFG等都属于这种算法）。考虑个问题，姑且认为很多东西都为真，容错有无一路飙升至99%的可能？比方说吧，观察者本是不积极参与共识过程却关注共识结果的一撮人，现在要求他们积极的看着点共识过程，不要下载个共识结果就了事。
早在1982年，Leslie Lamport发表的著名文章“拜占庭将军问题（The Byzantine Generals Problem）”中就对这种算法做出过描述。 下面，让我试着简单的描述并重构一下。
设共识参与节点数量为N，且参与节点提前选出，选举过程视情形而定，共识节点可以是可信方；强去中心化背景下，可以走一把PoW 或 PoS路线。将共识节点标记为0至N-1。设网络时延加时钟差异的范围已知为D，比方说D=8秒。每个节点可在时间点T发布一个值；恶意节点可在时间T之前或之后发布值。
所有节点运行下个进程前的等待时间为（N-1）*D秒。 x：i定义为：节点i签名的值x；x：i：j定义为：i签名的值x，i、x由j签名。则首阶段发布的提议形式为v：i，包含提议节点的签名。
验证人i收到某消息v：i [1]：...：i [k]，其中i [1]... i [k]代表已签名消息（按顺序）的索引列表（单独的v视为k = 0， v：i视为k = 1），验证人确认两件事：
（i） 时间小于T + k*D；
（ii） 验证人尚未观察到包含v的有效消息。
确认无误，验证人发布v：i [1]：...：i [k]：i。
节点将于时间点T +（N-1）*D时停止收听。至此，可以保证全部诚实节点都“有效地观察到”同一组值。
节点1（红色）为恶意节点，节点0、节点2（灰色）为诚实节点。开始时，两个诚实节点先各自提出y、x，后来攻击者提出w和z。 w准时到达节点0，但未能准时到达节点2；z未能准时到达及节点0、节点2。节点0、节点2于时间点T+D重新广播自己观察到的但未广播的所有值，节点0在x、w上签名，节点2在y上签名。 两个诚实节点都观察到{x，y，w}。
必须选择一个值的话，节点可以使用“选择”函数从观察到的值中选出一个值，好比选哈希最低的那个值。 然后就此值达成一致。
下面，分析下这个算法的原理。这里要证明一下：若一个诚实节点（有效的）观察到某个值，则剩余诚实节点也都观察到这个值。证明成功，则说明全部诚实节点都会观察到相同的一组数值，那么，若全部诚实节点运行相同的选择函数，必选出相同的值。
假设诚实节点接收自己认为有效的消息v：i [1]：...：i [k]，比方说在时间点T + k*D之前到达的消息有效。设x为其他单个诚实节点的索引。x或是{i [1]
... i [k]}的一部分，或不是。
• 第一种情况下，比方说x = i[j]的消息，已知诚实节点x已广播此消息。节点响应时间点T +（j-1）*D之前接收的带有j-1个签名的消息，于时间点T +（j-1）*D广播了该消息，因此所有诚实节点必已在时间点T + j*D之前接收到该消息。
• 第二种情况下，由于诚实节点在时间点T + k*D之前观察到消息，因此会签名消息并广播，确保包括x在内的所有人能在时间点T +（k+1）*D之前观察到消息。
注意，该算法使用添加个人签名这个动作充当消息超时的“减速处理”，因此保证了若一个诚实节点准时观察到消息则其他人也能准时观察到消息，这个“准时”增量的定义代表除网络时延外，每增加一个签名在此基础上多了点时间。
那么，只有一个诚实节点的情况下，能否保证非共识参与但关注共识输出的被动观察者也可以看到结果，即使要求他们观察整个过程？ 按照上面的方案的话，就有问题了。假设有个指挥官和k（恶意）个验证人子集生成消息v：i [1]：....：i [k]，在时间点T + k*D之前将其直接广播给一些“受害人”。虽然受害者视消息为“准时”，但是等到他们重新广播的时候，消息只能在T + k*D之后到达所有诚实的共识参与节点，因此这个消息会被所有这些节点拒绝掉。
但是这个漏洞是可以堵上的。 规定D为网络时延加上时钟差异的两倍。 然后对观察者实施不同的超时：观察者在时间点T +（k-0.5）*D之前接受v：i [1]：....：i [k]。现在，假设观察者观察到一条消息并接受，因此能在时间点T + k*D之前将其广播至一个诚实节点，随后由该诚实节点签发这条消息，那么该消息能在时间点T +（k+0.5）*D之前到达其他观察者，这个消息超时就是k+1个签名。
整合至其他共识算法
上述内容可用作独立共识算法，也可以用于运行PoS区块链。第N+1轮共识的验证人集可以在第N轮共识中决定，好比，视每轮共识为“存款”和“提现”交易，运行顺利的话可以增减下一轮的验证人。同时，也必须引入用来决定区块提出人（block proposer）的机制，好比每轮有一个指定的提出人，这个很重要。PoW链的话，共识参与节点需要实时“声明自己”，实现方法就是签名消息时，除了公钥还需发布工作证明。
但是，这里的同步假设还是非常强，那么不谈同步，也不用必须超过33％或50％容错的情况下，有什么方法么?
有的。
假设有些其他的共识算法，比方说PBFT、Casper
FFG或者PoS，算法的输出可被偶尔在线的观察者观察到。姑且将这种算法称为阈值依赖共识算法（threshold-dependent consensus algorithm），对比的是上述的时延依赖共识算法（latency-dependent consensus algorithm）。假设阈值依赖算法以不断“结（finalize）”新区块上链的模式持续运行，好比每个最终值都指向先前的最终值为“父项”，或者假设有一系列A - > ... - > B的指针，其中A叫做B的后代。
可以将时延依赖算法整合到这个结构上，实现约95%的容错。具体而言，是在检查点上给予一直在线的观察者一种“强终结性”。增加验证人并延长共识过程的话，容错是能轻松到100%的。
时间点达到4096秒的倍数时，运行时延依赖算法，随机选取512个节点参与共识。而有效提议则是由阈值依赖算法最终确定的有效价值链。在时间点T + k*D（D = 8秒）之前观察到带k个签名的某个最终值的节点，接受该链至其已知链的集合中，添加签名并对其重新广播。观察者还是使用T +（k-0.5）*D这个阈值。
最后使用的“选择”函数也不复杂：
• 非上一轮共识最终值后代的最终值，则忽略。
• 无效最终值，则忽略
• 两个最终值选其一时，选取哈希较低的值
若5％的验证人诚实，则512个随机选取节点都不诚实的概率约1万亿分之一，且只要网络时延加上时钟差异小于D/2，则上述算法可用，且能够在单一或阈值依赖算法的容错被破坏而呈现多个冲突最终值的情形下正确协调节点。
若满足阈值依赖算法的容错（一般是50％或67％的诚实节点），那么阈值依赖算法要么不最终确定任何新检查点，要么最终确定相互兼容的新检查点，好比有一系列检查点，每个都指向前一个作父项，那么即使网络时延超过D/2亦或D，时延依赖共识算法参与节点就认可的值也达不成共识，而共识值仍是同一条链的一部分，因此不存在实际的分歧。 时延在未来某轮恢复正常后，时延依赖共识也将恢复“同步”。
若阈值依赖和时延依赖共识算法同时（或在连续轮次中）被破坏，则混合算法失败。比方说，假设一轮中，阈值依赖共识最终确定Z - > Y - > X，但是时延依赖共识不认可X、Y之间的关系，那么下一轮中，阈值依赖共识最终确定W为X的后代，而非Y；延迟依赖共识中，认可Y的节点不认可W，但是认可X的节点会认可W。 这个问题是不可避免的；拜占庭容错理论中有个非常著名的结论就是异步安全共识的容错不超过1/3。另外，带离线观察者的同步假设容错也不会超过1/2。
https://vitalik.ca/general/2018/08/07/99_fault_tolerant.html
