Coinex连锁发展团队：tendermint共识协议详细解释（一）

这是一系列文章的第一部分，旨在解释tendermint共识协议

讨论了一致性协议的基本知识、一致性协议和pbft协议的安全模

详细解释tendermint共识协议，介绍两阶段投票协议和锁定解锁机制

投标项目中带权重的投标人轮换选择算法

任何协商一致的协议最终都会得到多数人的普遍同意，即多数人的意见。区块链系统运作的共识也不例外。作为一个分布式系统，区块链系统最基本的目标是保持系统的正确性。直观地说，区块链系统的正确性有两层含义：没有歧义，可以处理更新自身状态的请求

其中，前者对应于分布式系统的安全需求，后者对应于分布式系统的可用性需求。分布式系统的正确性主要由一致性协议来维护。由于分布式系统涉及多个节点和网络通信，可能会出现节点和网络通信不稳定的情况，这给一致性协议的设计带来了很大的挑战

半同步网络模与拜占庭容错

为了使所有可能出现的问题规范化，分布式系统的研究者利用节点失效模和网络模来描述节点和网络通信中可能出现的各种问题。节点故障模中的故障停止故障是指节点本身由于配置错误等原因而停止运行，因此无法继续参与一致性协议

这种故障不会对分布式系统的其他部分产生副作用，除非节点本身停止运行。然而，在公链的分布式系统中，在协商一致协议的设计中，除了考虑节点的失效外，还需要考虑节点主动作恶的情况，这就包含在拜占庭失效模中

拜占庭故障模包含了节点可能出现的所有意外情况，包括被动停机和偏离一致性协议的节点行为。为了便于描述，我们使用停机时间来表示被动节点停止运行的情况，使用拜占庭故障来表示主动节点偏离一致协议的情况

与节点失效模大致可分为被动模和主动模的情况相比，网络通信的建模相对比较困难。网络本身存在不稳定和通信延迟的问题，并且由于所有的网络通信最终都是由节点完成的，但是节点本身可能会出现停机或拜占庭式故障

因此，当一个节点没有从另一个节点接收到网络消息时，通常很难确定是由于节点的问题还是网络本身的问题。虽然网络通信可能受到多方面的影响，但研究人员发现，网络模可以根据通信延迟进行分类，例如，当一个节点无法从该节点发送数据包时，相应的通信延迟是未知的，可以是任意长的时间。基于通信延迟的概念，网络通信模可分为以下三类：

同步网络模：网络通信具有固定的已知时间上限

在这个模中，两个节点之间的网络通信的最大延迟是

即使存在恶意节点，恶意节点造成的通信延迟也不会超过

.

异步网络模：网络通信中存在一个未知的延迟，并且延迟的上限未知，但最终可以成功地传递消息。在该模中，网络中两个节点之间的网络通信延迟可以是任意可能的值，即如果存在恶意节点，恶意节点可以任意延长通信延迟

半同步网络模：假设存在全局稳定时间（GST），即GST之前的异步网络模和GST之后的同步网络模。也就是说，网络通信有一个固定的、已知的时间上限

网络中的恶意节点可以任意向后扩展时间点GST，没有GST时不通知。在这个模中，在时间点

消息传递的时间延迟为

.

同步网络模是网络环境下的第一个模拟考试。网络发送的每一条消息都能在预期的时间内收到。但该模不能反映真实的网络通信。因此，在实际网络中，往往会出现网络故障，这就导致了同步网络模失效的假设。

异步网络模走向了另一个极端，不能反映真实的网络情况。FLP（Fischer-Lynch-Paterson）定理指出，在该模中，只要一个节点失效，就没有在有限时间内达成一致的协议

相比之下，半同步网络模能更好地描述现实世界中的网络通信：网络通信通常是同步的，但也可能在短时间内出现问题，然后恢复正常。相信每个人在自己的网络体验中都有这样的体验。在一定的时间段内，网页打开缓慢，但通常网页打开的速度很快，而在网络恢复正常后，通常没有任何通知，只有在试图知道网络真正恢复正常后

在区块链项目中经常使用的P2P网络通信的实现，也使得节点能够从多个网络通道发送和接收信息。长期阻断节点的网络信息传输是不现实的。因此，本文后面讨论的内容默认在半同步网络模下进行

在协商一致协议的设计和选择中，当允许节点动态地加入和离开公链网络时，应考虑可能的拜占庭故障。因此，公链网络的一致性协议设计目标是在半同步网络模下容忍拜占庭式故障，保证网络的安全性和可用性，分布式系统的研究者指出，为了保证系统的安全性和可用性，一致性协议本身需要满足以下三点：

有效性：诚实节点的最终一致性值必须是诚实节点提出的值

协议：所有诚实的节点必须同意相同的值

终止：诚实的节点必须最终同意一个值

由此可见，正确性和一致性可以保证分布式系统的安全性，即诚实节点永远不会对随机值达成一致，一旦达成一致，所有诚实节点都会对随机值达成一致。虽然持久性保证了分布式系统的可用性，但无法达成一致意见的分布式系统是无用的

一般拜占庭问题与cap定理

在半同步网络下，我们能否设计出一个一致的拜占庭容错协议，以满足正确性、一致性和持久性的要求？这个协议能在系统中容忍多少拜占庭节点？Cap定理和拜占庭一般问题为这两个问题提供了答案，并成为拜占庭容错一致性协议设计的基本准则

1982年，Lamport、Shostak和pease将分布式系统中的一致机制设计问题抽象为拜占庭一般问题。这个问题可以说是许多将领带领自己的军队参战，军队驻扎在不同的地方

为了赢得战争，将军们必须制定一个统一的行动计划。但是，由于驻军之间的距离，将军们只能通过通信兵相互通信。也就是说，将军们不能同时出现在同一情况下，面对面达成共识

不幸的是，将军中有叛徒，叛逆的将军们想通过发送错误的信息来破坏忠诚将军的统一行动，而通信兵自己却不能将信息发送到目的地。这里，假设每个通信兵都能证明自己带来了某个将军的信息，在真实的BFT共识协议中，每个节点都有自己的公钥和私钥来相互建立加密的通信通道，以保证其在网络通信中的消息不会被篡改，消息接收者还可以验证消息的发送者

如前所述，任何协商一致的协议最终都会达成多数人的共识。在将领们相互沟通攻守的过程中，将领们也会根据收集到的情报中的多数意见做出自己的决定

兰波特等人对这一问题的研究表明，只要节点上有1/3以上的叛徒，将军们就无法达成统一的决策。例如，下图假设有三个将军，只有一个叛徒

在左边的图中，假设C将军是法官，a和B是忠诚的。如果a想发动攻击，他分别向B和C发出命令，叛徒C向B发出消息，说a给自己的消息是撤退，那么B在收到a和B的消息后不能做出自己的决定，因为B不知道叛徒是谁，根据收到的消息，B不能做出决定。如果a是叛徒，他可以向B和C发送不同的信息，此时C将收到的信息如实地报告给B。此时，B也看到了矛盾的信息，无法做出任何决定。在这两种情况下，B接收到相同的信息，无法区分a和C。因此，在下图所示的两种情况下，诚实的将军B无法做出决定

根据这个结论，我们可以看到

将军，最多

叛徒，如果

这时，将军们无法达成协议，而且

根据这个结论，我们可以知道拜占庭失败时的节点数

超过系统中的节点总数

三分之一

所有诚信节点之间无法达成共识

只有达成共识才有可能。因此，这并不少见。后续协商一致协议讨论违约

.

兰波特等人的结论。关于拜占庭故障的一般问题是，拜占庭容错协议的设计在拜占庭故障的容忍度上划出了可能和不可能的界限。在可能的范畴内，一致性协议的设计能达到什么样的效果，能否完全保证分布式系统的安全性和可用性？brewer在2000年提出的cap定理提供了答案。Cap定理指出，一个分布式系统需要三个基本属性，但任何一个分布式系统最多只能满足这三个属性中的两个

一。一致性：当发出相应的请求时，任何节点要么提供最新的状态信息，要么不提供状态信息

2。可用性：系统中的任何节点都必须能够连续读写

3分区容限：系统可以容忍两个节点之间任何数量的消息丢失，并且仍然正常运行

分布式系统的最终目的是提供类似于一致性的外部服务。因此，一致性属性要求系统中的两个节点不能提供相互矛盾的状态信息或过期信息，从而保证分布式系统的安全目标。可用性属性保证了系统能够不断地更新自身的状态，保证了分布式系统的可用性目标

网络划分的容忍度属性与网络通信的延迟有关。在半同步网络模下，它可以看作是GST时间之前的状态。此时，网络处于异步状态，网络通信延迟具有未知的延迟，并且通信节点可能无法接收彼此的信息，此时，网络被认为处于分区状态。网络分区的容限属性要求分布式系统在面对网络分区时仍能正常运行并及时提供外部功能

cap定理的证明可由下图完成，图中的曲线表示网络划分，每个网络有四个节点，分别用数字1、2、3和4来区分。分布式系统存储颜色信息，开始时所有节点存储的状态信息为蓝色

网络分区的容忍度和可用性意味着一致性的损失：在最左边的图中，当节点1接收到新的请求时，状态变为红色，节点1的状态转移信息被传输到节点3，节点3将状态信息更新为红色。但是，由于网络划分，节点3和节点4没有接收到相应的信息，状态信息仍然是蓝色的。如果通过节点2查询状态信息，则节点2返回的蓝色不是系统的最新状态，因此失去一致性

网络划分的容忍度和一致性意味着可用性的损失：在中间图中，所有节点的初始状态信息都是蓝色的。当节点1和节点3的更新状态信息为红色时，由于网络分区的原因，节点2和节点4的状态信息保持蓝色。类似地，当通过节点2查询状态信息时，由于节点2需要遵循一致性原则，因此需要在返回状态信息之前要求其他节点确认其状态是最新状态。但是，由于存在网络分区，节点2无法从节点1和节点3接收任何信息。此时，节点2无法确定其状态为最新状态，因此它选择不返回任何信息，从而丢失系统的可用性

一致性和可用性意味着失去了对网络分区的容忍度：在最右边的图中，系统最初没有网络分区，状态更新和查询可以顺利进行。然而，一旦发生网络划分，就会退化为前两种情况之一，因此证明任何分布式系统都不能同时保证这三种属性

cap定理的发现似乎宣告了上述协商一致协议的目标无法实现。然而，通过以上的证明，细心的读者可以发现，证明涉及到极端的情况，例如网络划分导致信息完全无法传输的情况，这在现实世界中是很少遇到的，特别是采用P2P网络通信的情况

在第二种情况下，实际系统很少不返回任何信息，如节点2。通常的方法是查询其他节点并等待合适的时间，然后返回他们认为是否真正获得了其他节点的请求信息的最新状态

因此，尽管cap定理指出任何分布式系统都不能同时满足这三个属性，但它不是一个非黑或白的二元选择。作为一致性协议的设计者，我们可以根据分布式系统的需求在三个属性之间进行权衡。然而，分布式系统往往涉及到通信延迟，因此，任何一个分布式系统都应该在保证一定的网络划分容忍度的前提下，在可用性和一致性上做出选择

具体来说，在第二种情况下，节点2返回一些可能过时的值，或者不直接返回任何值。返回可能过时的值可能会违反一致性属性，但它保证可用性，如果不返回任何值，则会失去系统的可用性，但它确保了系统的一致性。未来将引入的tendermint共识协议可被视为在这种权衡中选择一致性，即在某些情况下，它将失去可用性

Nakamoto的天才正是在cap定理的前提下，在不可靠的网络环境下，通过pow机制、Nakamoto共识协议、经济激励和适当的参数配置的结合，在大规模分布式网络中达成可靠的Byzantine共识

比特币的机制设计是否真的解决了拜占庭将军的问题一直是学术界争论的焦点。Garay，kiayias和leonardos详细分析了比特币机制设计与拜占庭共识之间的关系在他们的论文《比特币骨干协议：分析与应用》，简而言之，Nakamoto共识是拜占庭容错的概率共识协议，这取决于网络通信环境和恶意节点的算力比。当网络通信环境良好，恶意节点的算力比小于1/2时，Nakamoto共识能够可靠地解决分布式环境下的拜占庭共识问题。然而，当网络通信环境变差时，即使恶意节点的算力小于1/2，也会导致CBC共识无法对拜占庭共识做出可靠的结论

值得注意的是，网络环境质量与比特币的屏蔽区间有关。比特币选择的10分钟封锁区间，在大多数情况下都能保证系统的网络通信环境良好，因为根据比特币的实际运营经验，一个区块在分布式网络中的广播时间通常小于1秒，经济激励的设置也可以激励大多数节点积极遵守协议。因此，可以认为，在当前比特币网络参数配置和机制设计下，在当前的世界网络环境下，比特币机制设计可靠地解决了拜占庭共识问题

Pbft协议介绍

在半同步网络中设计拜占庭容错的一致性协议并不容易。1999年卡斯特罗和利斯科夫设计的第一个实用的拜占庭容错协议是实用的拜占庭容错协议（pbft）。Pbft是第一个具有多项式复杂度的拜占庭容错协议

分布式节点系统的通信复杂度为

本文中，Castro和Lisko报告说，使用pbft协议将中心化式文件系统转换为分布式文件系统后，总体性能损失仅为3%。本节简要介绍了pbft协议，为进一步解释tendermint协议和理解tendermint协议的改进铺平了道路

包含

pbft协议可以容忍

拜占庭式节点，pbft原稿中要求

节点之间存在完全连接，即

在比特币网络中，任何节点都可以随时通过计算和挖矿参与协商一致或退出协商一致的过程，而PFBT协议需要在协议开始前确定所有参与节点，管理员负责管理节点的加入和退出

在pbft协议中，所有节点分为两类：主节点和从节点。任何时候只有一个主节点，所有节点轮流成为主节点。所有节点运行在一个称为视图的旋转过程中，主节点将在每个视图中被重新选择。pbft中的主节点选择算法非常简单，在每个视图中，所有节点都试图对系统状态达成一致。值得一提的是，pbft协议中的每个节点都有自己的数字签名密钥对，所有发送的消息（包括客户端的请求消息）都需要签名，以确保消息在网络传播中的完整性和消息本身的可追溯性（根据签名值，我们可以判断是谁发送的一条消息）

pbft共识协议的基本流程如下图所示。假设主节点是节点0。客户机c向主节点0发起请求，主节点在接收到请求后向所有从节点广播该请求。所有从节点处理客户机C的请求并将结果返回给客户机。客户端接收来自不同节点的请求（根据签名值）

在相同的结果之后，结果可以看作是整个操作的最终结果，因为

拜占庭节点，这意味着客户端接收

结果中至少有一个诚实节点，一致性协议的安全性保证了所有诚实节点在同一状态下都能达成一致，因此一个诚实节点的反馈足以确认系统已经处理了相应的请求

为了保证所有诚实节点的状态同步，pbft协议对每个节点都有两个约束，一个是所有节点必须从同一个状态开始，另一个是所有节点的状态转换必须是确定性的，即给定相同的状态和请求，操作执行的结果必须是相同的，只要整个系统对所有事务的处理顺序达成一致，保证了所有诚实节点的状态一致。这也是pbft协议的主要目的：对所有节点之间的事务顺序达成一致，从而保证整个分布式系统的安全。在可用性方面，pbft一致性协议依靠超时机制来发现一致性过程中的异常，并及时启动视图更改协议，试图再次达成一致

上图显示了简化的pbft协议的工作流程。C为客户端，0、1、2、3分别代表四个节点，其中0为当前视图主节点，1、2、3为从节点，3为故障节点。在正常情况下，pbft一致性协议通过三步协议实现节点间事务顺序的一致性，即：预准备、准备和提交：

预准备节点的主节点负责将序列号分配给接收到的客户端请求，并将lt；pre prepare，V，N，D，SIGgt；消息广播到从节点。消息包含客户端请求的哈希值D、当前视图的序列号V和主节点为请求分配的序列号n，pbft协议的方案设计将请求传输与请求排序过程分离。这里不讨论请求传输。接收消息的从节点将接受该消息，并在检查该消息是否合法后进入准备阶段。此步骤中的消息检查基本签名、哈希值和当前视图，最重要的检查是确定主节点是否为当前视图中的不同客户端请求消息提供了相同的序列号

在准备阶段，节点向所有节点（包括自身）广播消息lt；PREPARE，V，N，D，siggt；，表示同意将当前视图N中散列值为D的序列号V分配给客户端请求，并有自己的签名sig作为证明。接收到消息的节点将检查签名的正确性、视图序列号的匹配等，当节点接收到的预准备消息（来自主节点）和预准备消息（来自2F从节点）相互匹配时，表示系统已经就当前视图中的客户端请求。因为这意味着当前视图中的2F+1节点同意请求序列号的分配，因为它最多包含来自恶意节点的f信息，所以意味着至少f+1诚实节点同意请求序列号的分配。当有f个恶意节点时，共有2F+1个城市节点，那么f+1是大多数诚实节点，即大多数人的共识有前提

当节点（包括主节点和从节点）接收到客户端请求的预准备消息和2F准备消息时，整个网络广播消息lt；commit，V，N，D，SIGgt；将进入提交阶段。此消息用于指示节点已观察到整个网络已就客户端请求消息的序列号分配达成共识

当一个节点接收到2F+1提交消息时，这意味着至少有F+1个诚实的节点。也就是说，大多数诚实的节点观察到，整个网络已经就客户端请求消息的序列号分配达成了共识。此时，节点可以处理客户机请求并将执行结果返回给客户机

大致来说，主节点指定了在预准备阶段所有新客户机请求的序列号。在准备阶段，所有节点在此视图中对客户端请求编号达成一致，而提交阶段用于确保不同视图之间客户端请求序号的一致性

另外，pbft协议本身的设计不依赖于根据指定的序列号一次性提交请求消息，而是允许请求消息的无序提交，这可以提高协商一致协议的执行效率。然而，在执行结束时，根据一致性协议分配的序列号来执行消息，以实现分布式系统的一致性

在pbft的三阶段协议实现过程中，节点自身不仅要维护分布式系统自身的状态信息，还要记录接收到的各种一致性信息

日志的逐渐积累将消耗大量的系统资源，因此在pbft协议中，额外定义了检查点来帮助节点进行垃圾收集。根据请求序列号，可以每100或1000个序列号设置一个检查点。当检查点的客户端请求完成时，节点在整个网络中广播lt；checkpoint，n，D，SIGgt；消息，指示节点在完成序列号为n的客户端请求后，系统状态的哈希值为D，并通过签名SIG来保证

在接收到2F+1匹配的检查点消息（其中一个可以来自自身）后，意味着整个网络中的大多数诚实节点在执行序列号为n的客户端请求后已就系统状态达成一致，节点需要保存2F+1检查点消息作为状态在这一次，对应的检查点称为稳定检查点

pbft的三级协议保证了客户端请求处理序列的一致性。一方面，检查点机制帮助节点回收垃圾，进一步保证了分布式系统状态的一致性，保证了前面提到的分布式系统的安全性

如何确保分布式系统的另一个目标的可用性？在半同步网络模中，通常引入超时机制。超时时间窗口的设置将延迟网络环境

在半同步网络模中，假设网络延迟在GST之后

有一个已知的上限。在特定的系统实现中，通常根据系统部署的网络条件设置初始值。当发生超时事件时，除了触发相应的处理流外，还将使用其他机制重新调整等待时间。例如，超时事件后的等待时间可以通过类似于TCP的指数退避的算法进行调整

为了保证系统的可用性，pbft协议还引入了超时机制。此外，由于主节点本身可能存在拜占庭式故障，因此pbft协议还需要确保系统在这种情况下的安全性和可用性

当主节点出现拜占庭故障时，例如从节点在设置的等待时间内没有收到主节点的预准备消息，或者主节点发送的预准备消息被判定为非法，则从节点可以向整个网络广播lt；视图更改，V+1，N，C，P，SIGgt；，指示节点请求切换到序列号为V+1的新视图。N表示与节点的最新本地稳定检查点对应的请求序列号。C是用于证明稳定检查点的2F+1合法检查点消息

在最新的稳定检查点之后和启动iewchange消息之前，在前一个视图中，系统可能已经就一些请求消息的序列号达成了共识。为了确保视图切换期间这些请求序列号的一致性，iewchange消息需要将这部分信息传递给新视图，这也是消息中P字段的含义，P包含在节点收集的请求序列号大于n的所有客户端请求消息，并证明该序列号已在节点中达成一致：关于请求的合法预准备消息和2F匹配的预准备消息

当视图+1中的主节点收集2F+1视图更改消息时，它可以广播和发送新的视图消息，将整个系统带入一个新的视图。为了结合pbft协议的三级协议来保证系统的安全性，新视图信息的构造规则非常复杂，本文将不再详细介绍。感兴趣的读者可以参考pbft的原稿

我们可以看到iewchange包含了很多信息，例如C包含2F+1签名信息，P包含多个签名集，每个签名集都包含2F+1签名信息。因为至少2F+1节点需要发送iewchange消息来促使系统进入下一个新视图，我们可以看到，除了构造iewchange和新视图信息的复杂逻辑外，视图转换协议的通信复杂度是

这种复杂性也限制了pbft协议只支持几个节点。当有100个节点时，由于pbft的高度复杂性，在实际中无法部署。值得注意的是，在一些数据中

沟通的复杂性完全归因于

不适合连接所有节点

通过将全连接网络拓扑结构改为基于目前区块链项目中常用的分布式哈希表的P2P网络拓扑结构，全连接引入的通信复杂度可以显著提高。然而，在视图转换过程中很难提高通信的复杂度

近年来，研究人员提出采用聚合签名技术来减少这一步骤的流量。利用聚合签名技术，将2f+1签名信息压缩为一个签名信息，减少了视图转换过程的流量

*本文由coinex链开发团队成员longcpp撰写。Coinex链是第一个全球共识协议和cosmos，借助IBC，SDK开发的DEX私有公链可以实现DEX公链、智能合约链和隐私链的集成，解决不可能的可扩展性、去中心化和安全区块链三角问题。它可以支持数字资产的交易和基于智能合约的DeFi应用，具有较高的性能。