Vitalik最近在其博客上发表了一篇名为《一个99%容错共识的指南》的文章，让很多人以为一种类似“黑科技”的新共识算法诞生了。然而，正如Vitalik自己所说，这个共识算法仍然是经典的拜占庭一般问题算法。通过分析可以看出，一致性算法的研究和创新仍然需要遵循CAP等已被证明的理论；在此基础上，将各种经典的分布式算法和加密算法进行修改，应用到区块链领域，大概会取得不错的效果。
1。新算法？
Vitalik在其博客上发布了一篇名为《一个99%容错共识的指南》的文章。一时间，各大媒体纷纷发布消息称“V神发布的新算法只需要1%节点不作恶”。区块链世界一夜之间进入了新的篇章吗？答案可能有些令人沮丧：这不是一个新开发的算法。
事实上，Vitalik在他的博客中已经明确表示“莱斯利兰波特(Leslie Lamport)在1982年的著名论文《拜占庭尚力财经小编2022将军问题》中已经包含了该算法(以提高容错率)。这里我将试着用一种简化的形式来描述和实现它”。随后他还在推特上强调“可99%容错的共识协议不是我发明的，是Leslie Lamport发明的。我只是做了一个解释，并把这个算法应用于区块链场”。
这到底是怎么回事？为了理解上下文，我们需要讨论一些理论问题，如共识和分布式系统。
2。分布式系统理论
事实上，在区块链诞生之前，计算机科学就已经对一致性做了大量的研究，形成了严格证明的分布式系统理论。经典理论包括FLP和卡普。
FLP不可能性原理是：“在网络可靠，甚至一个节点失效的最小化异步模型系统中，没有确定性算法可以解决一致性问题。”即一致性问题的理论下限是无解的。在异步系统中，没有可以在任何情况下实现的一致算法。
CAP的原理叫做CAP不可能三位一体，即一致性、可用性和分区容忍度不能同时满足，所以设计一个分布式系统需要削弱某个特性。因此，在FLP不可能原理的前提下，CAP原理为工程实践提供了理论指导。
比CAP更普遍的是，分布式系统理论中有网络环境特性的定义：包括通信的安全性、活性和不可靠性。通过这些特征，我们可以更普遍、更直观地定义CAP:
可以看出，一般来说，网络划分容忍度P不是一个选项，而是算法中必须考虑的因素。这就是为什么分布式系统通常在安全性和活性之间进行权衡。
其中，任何一种最后的错误都是最严重最难处理的。在这种情况下，任何类型的错误都可能发生，服务器可能会产生原本不应该输出的内容，因此系统应该为最坏的情况做好准备。例如，当一台服务器向另一台服务器发送相反的消息时。这种类型的错误，即拜占庭错误，最早是由Pease和Lamport在20世纪80年代初通过拜占庭一般问题描述和分析的。
因此，与分布式数据库相比，区块链的一致性问题的设计和实现更加复杂，这也是区块链不仅仅是一个简单的分布式数据库的原因之一。
3。拜占庭一般问题的经典解法
BFT问题本身的描述在此不再赘述。Lamport等人在其经典论文中提出了拜占庭一般问题，也提供了两种解决方案。
第一个OM(m)协议是“口头消息”，即不允许在链路上使用除加密安全以外的任何加密算法。该协议需要在两两之间递归传输大量消息，因此消息的复杂度非常高，呈指数级，不实用。 不过这个算法还是有其很高的价值的。首先，它为多项式级复杂度协议“实用拜占庭容错”的诞生铺平了道路。此外，1/3容错节点数也被证明是这类算法的理论上限。
第二个是“加密消息”的SM(m)协议。该算法与第一个算法的不同之处在于它使用了签名算法。每个节点可以生成不可伪造的签名，该签名可以被其他节点验证。当收到消息时，节点将对其进行签名，以判断和验证消息是否已收到。最终没再收到消息后，消息共识结束。
本文证明了第二种算法可以实现任意数量节点的容错(当然网络至少要包含两个正常节点，否则没有意义)。具体过程，请参考原论文。
然而，这种算法也有其局限性：与许多拜占庭算法在异步或半同步网络环境中的假设不同，它假设在“同步”网络中进行，忽略了网络节点之间的通信延迟；另外，网络运行前需要确定签名身份系统信息，难以扩展。因此，根据CAP理论，这种方法可以在不考虑网络划分容忍度(P)的情况下，实现较高的一致性(C)和可用性(A)。
4、“99%容错共识算法”及比较分析
为了比较，我们继续来看一下Vitalik说的共识算法，是Lamport发明的，是他自己描述和简化的(以下简称“实现版”)；Lamport论文中的版本成为“原始版本”)。
这个实现版本仍然保留了原有的数字签名体系，即每个节点可以产生一个不可伪造的签名，该签名可以被其他节点验证。
与原版本不同的是，为了实现节点间的消息传递，实现版本的算法规定了消息的超时时间，即节点收到消息后，消息检查不仅要检查签名是否已经收到且在集合中，还要检查收到消息的时间不能晚于签名对应的时间节点。
在确定的时间(按轮次计算)后，节点将停止监听，并根据某种确定的规则，从检查到的合法消息中选择一个值作为协商一致的结果。
尚力财经小编2022通过对比可以发现，两种算法没有本质区别。他们算法的本质是基于签名系统。但Vitalik实现版本的共识算法增加了延迟时间要求。这种设计和实现经常会在共识协议的具体编译和实现中遇到，它可以决定消息传播的轮次，并确保消息传播可以在指定的时间内完成。
此外，实现版本还讨论了观察者作为独立角色在网络中传递消息。作为网络中的被动观测者，观测者可以接收、检查和直接转发(无需签名)消息给其他节点。这就需要给观察者引入不同的延迟时间，从而解决恶意节点故意向观察者发送消息较晚，使正常消息超时的问题。
5。应用与启示
如上所述，这种共识方法的主要问题是对网络同步要求高，扩展性差。另一种实现版本的缺点是消息量也较大(N个节点向其他N-1个节点发送消息需要N-1轮，即消息复杂度为)，所以这种共识方式很难直接应用在实际场景中。
为了更适用于区块链领域，Vitalik在他的文章中还提到，这种方法可以与目前其他的共识算法(如PBFT、PoS等)相结合。).例如，算法可以在特定的时间间隔运行。通过采用上面讨论的观察者模式，随机选择一些节点来运行上述一致性以进行检查。但是，如果两个一致性算法的相关前提假设都不能满足，那么一致性算法也会失效，即这个改进的优化不能违背原来的理论体系。
但是，我们还是可以得到很多启发：充分挖掘分布式系统领域的经典理论，将其转化为适合区块链的共识算法，可以取得意想不到的效果。比如PBFT结合中本聪共识，维塔利克在BFT论文中提出的SM(m)算法结合现有的区块链共识等。
除此之外，尝试在安全领域应用各种尚力财经小编2022加密算法，也可能获得不错的效果。比如ByzCoin等人也在尝试使用聚合签名等加密算法优化共识机制，可以大大降低通信复杂度。
6。总结
共识算法的研究和创新仍然需要遵循CAP等已被证明的理论。
在这些理论的基础上，计算机分布式理论中的各种经典算法和安全领域中的各种加密算法都可以自适应地修改应用于区块链领域，将有可能获得良好的结果。
参考文献
99%容错共识指南，Vitalik，https://Vitalik . ca/general/2018/08/07/99 _ fault _ tolerant . html《分布式系统(第三版)3.01版》，Maarten van Steen，Andrew S. Tanenbaum。《拜占庭将军问题》，莱斯利兰波特、罗伯特肖斯塔克、马歇尔皮斯
https://people . eecs . Berkeley . edu/~ Luca/cs 174/Byzantine . pdf https://en . Wikipedia . org/wiki/Byzantine _ fault _ tolerance # Early _ solutions https://www . trust nodes . com/2018/08/10/vitalik-buter in-proposes-consensus-algorithm-requires-1-honest
微信咨询
