【共识专栏】Quorum机制与PBFT-ODAILY

实用性拜占庭容错算法，是一种在信道可靠的情况下解决拜占庭将军问题的实用方法。拜占庭将军问题最早由LeslieLamport等人在1982年发表的论文提出，论文中证明了在将军总数n大于3f，背叛者为f或者更少时，忠诚的将军可以达成命令上的一致，即3f+1<=n，算法复杂度为O(n^(f+1))。随后MiguelCastro和BarbaraLiskov在1999年发表的论文中首次提出PBFT算法，该算法容错数量也满足3f+1<=n，算法复杂度降低到了O(n^2)。

如果对于PBFT共识算法有所了解，对节点总数n与容错上限f的关系可能会比较熟悉：在系统内最多存在f个错误节点的前提下，系统内总节点数量n应该满足n>3f，在推进共识过程中则需要收集一定数目的投票，才能完成认证过程。在本节当中，我们将首先讨论这些数值间关系该如何得出。

--Quorum机制--

在有冗余数据的分布式存储系统当中，冗余数据对象会在不同的机器之间存放多份拷贝。但是在同一时刻，一个数据对象的多份拷贝只能用于读或者写。为了保持数据冗余与一致性，需要对应的投票机制进行维持，这就是Quorum机制。区块链作为一种分布式系统，同样也需要该机制进行集群维护。

为了更好地理解Quorum机制，我们先来了解一种与之类似，但是更加极端的投票机制——WARO机制。使用WARO机制维护节点总数为n的集群时，节点执行写操作的“票数”应当为n，而读操作时的“票数”可以设置为1。也就是说，在执行写入时，需要保证全部节点完成写入操作才可视该操作为完成，否则会写入失败；相应地，在执行读操作时，只需要读取一个节点的状态，就可以对该系统状态进行确认。可以看到，在使用WARO机制的集群中，写操作的执行非常脆弱：只要有一个节点执行写入失败，那么这次操作就无法完成。不过，虽然牺牲了写操作健壮性，但是，在WARO机制下，对于该集群执行读操作会非常容易。

Quorum机制就是对读写操作的折衷考虑，对于同一份数据对象的每一份拷贝，不会被超过两个访问对象读写，并且权衡读写时的集合大小要求。在一个分布式集群当中，每一份数据拷贝对象都被赋予了一票。假设：

系统中有V票，这就意味着一个数据对象有V份冗余拷贝；

对于每一个读操作，获得的票数必须不小于最小读票数R才可以成功读取；

对于每个写操作，获得的票数必须不小于最小写票数W才可以成功写入。

此时，为了维持集群一致性，V、R、W应满足不等关系，R+W>V且W>V/2。其中，R+W>V保证了一个数据不会被同时读或写。当一个写操作请求传入，它必须要获得W票，而剩下的数量是V-W不足R，因此不会再处理读请求。同理，当读请求已经获得了R票，写请求就无法被处理。W>V/2，保证了数据的串行修改，也就是说，一份数据的冗余拷贝不可能同时被两个写请求修改。

美国德克萨斯州参议院已批准储备金证明法案:5月19日消息，美国德克萨斯州参议院于已通过HB1666法案，要求加密公司证明其有足够的资产储备，目前正等待州长的签署。此前报道，美国德克萨斯州众议院已于4月21日批准储备金证明法案。（Cointelegraph）[2023/5/19 15:13:48]

对于集群中的共识节点，在推进共识算法时，参与共识的节点会同时对集群进行读写操作。为了平衡读写操作对于集合大小的要求，每个节点的R与W取同样大小，记为Q。当集群中总共存在n个节点，并且其中最多出现f个错误节点的情况下，我们该如何计算n、f、Q之间的关系呢？接下来，我们将从最简单的CFT场景出发，逐步探索如何在BFT场景中得到这些数值取值之间的关系。

▲CFT

CFT，表示系统中的节点只会出现宕机这种错误行为，任何节点不会主动发出错误消息。当我们在讨论共识算法可靠性时，通常会关注算法两种基本性质：活性与安全性。在计算Q的大小时，同样也可以从这两个角度出发进行考虑。

对于活性与安全性，有一种比较直观的描述方式：

somethingeventuallyhappens，某个事件最终会发生

somethinggoodeventuallyhappens，这个最终会发生的事件合理

从活性角度出发，我们的集群需要能够持续运行下去，不会由于某些节点的错误导致无法继续共识。从安全性角度出发，我们的集群在共识推进的过程中，能够持续获得某个合理的结果，对于分布式系统来说，这种“合理”的结果，其最基本的要求就是集群整体状态的一致性。

于是，在CFT场景下，对于Q数值的确定就变得简单明确：

活性：由于我们需要保证集群能够持续运行，所以，在任何场景下都要保证有获取到Q票的可能性，从而为集合读写数据。由于集群中最多会有f个节点发生宕机，所以为了保证能获取到Q票，该值的大小需要满足：Q<=n-f。

安全性：由于我们需要保证集群不发生分歧，所以，按照Quorum机制的基本要求，需要满足在上一节当中提到的两个不等式，将Q作为最小读集合与最小写集合带入该组不等式，此时，Q满足不等关系，Q+Q>n且Q>n/2，因此，该值的大小需要满足：Q>n/2。

▲BFT

BFT，表示集群中的错误节点不仅可能会发生宕机，也可能存在恶意行为，即拜占庭行为，例如主动进行状态分叉。在这种情况下，对于集群整体而言，只有n-f个节点的状态可靠，当我们收集到Q个投票时，其中也只有Q-f个投票来自可靠的节点。因此，在安全性方面，BFT场景下需要保证状态可靠的节点之间不会发生分歧，因此得到以下两种关系：

SBF名下此前挂牌出售的华盛顿特区联排别墅已从市场下架:2月5日消息，此前以328万美元挂牌出售的Sam Bankman-Fried（SBF）名下位于华盛顿特区的联排别墅，因是挪用客户资金购买而被要求从市场上下架。

财产记录显示，该房产由SBF的兄弟Gabriel创立的非营利组织 Guarding Against Pandemics 持有，该组织使用该公司认为被挪用的客户资金购买了价值数百万美元的资产。该房产的销售代理人表示，目前该房产还未收到过任何的正式购买报价。（《华尔街日报》）[2023/2/5 11:48:29]

活性：依然只需要保证每时每刻都有获取Q票的可能性，因此，Q<=n-f。

安全性：对于全部保证正确的节点不会发生分歧，此时，应当满足不等关系，(Q-f)+(Q-f)>n-f且(Q-f)>(n-f)/2，因此，此时Q的大小需要满足的关系为，Q>(n+f)/2。

▲节点总数与容错上限

对于节点总数n与容错上限f，在PBFT论文当中给出的解释：由于存在f个节点可能发生宕机，因此我们至少需要在收到n-f条消息时进行响应，而对于我们收到的来自n-f个节点的消息，由于其中最多可能存在f条消息来自于不可靠的拜占庭节点，因此需要满足n-f-f>f，所以，n>3f。

简单来说，PBFT的作者从集群活性与安全性出发，得到了节点总数与容错上限之间的关系。上一节中，我们也是从活性与安全性角度，获得了n、f与Q的关系，在这里也可以用来推导n与f的关系：为了同时满足活性与安全性的要求，Q需要满足不等关系，Q<=n-f且Q>(n+f)/2，因此，可以得到n与f之间的不等关系，(n+f)/2<n-f，也就是n>3f。

(通过类似的方式，也可以得到CFT场景中n与f的关系，n>2f。)

--PBFT与RBFT--

在理解BFT场景中n、f、Q的关系后，接下来进入到PBFT的介绍。在此之前，简单提一下SMR复制状态机。在该模型当中，对于不同的状态机，如果从同样的初始状态出发，按照同样的顺序输入同样的指令集，那么它们得到的最终结果总会一致。对于共识算法而言，其只需要保证“按照同样的顺序输入同样的指令”，即可在各个状态机上获得同样的状态。而PBFT就是对指令执行顺序的共识。

那么，PBFT是如何保证指令执行顺序的一致性呢？PBFT集群为主从结构，由主节点提出提案，并通过集群中各个节点间的交互进行验证，从而使得每个正确节点遵循同样的顺序对指令集进行执行。在这个交互过程中，就需要使用Quorum机制保证集群整体状态的一致性。下面我们将对PBFT进行详细介绍。

Lido：正在就以太坊上海升级完成后允许ETH提款的提议征求社区意见:1 月 26 日消息，在以太坊社区为三月份即将启动上海硬分叉做准备的同时，流动性质押项目 Lido 开发团队也透露了创建协议内提款功能的计划，该团队正在就上海升级完成后允许提款的提议征求社区反馈。Lido 是目前质押 ETH 的最大持有者之一，控制者大约 29% 的 ETH 质押量，另据 defillama 数据显示，Lido 当前总锁仓量约为 80 亿美元，占到 DeFi 总锁仓量的 17%。

Lido 开发人员表示，由于以太坊取款具有异步特性，因此提款过程必须是异步的，Lido 已在以太坊协议工程团队中提出通过协议内提款请求队列解决这些问题。[2023/1/27 11:31:28]

▲两阶段共识

相比较常见的“三阶段“概念，将PBFT视为一种两阶段共识协议或许更能体现每个阶段的目的：提案阶段和提交阶段。在每个阶段中，各个节点都需要收集来自Q个节点一致的投票后，才会进入到下一个阶段。为了更方便讨论，这里将讨论节点总数为3f+1时的场景，此时，读写集票数Q为2f+1。

1)提案阶段

在该阶段中，由主节点发送pre-prepare发起共识，由从节点发送prepare对主节点的提案进行确认。主节点在收到客户端的请求后，会主动向其它节点广播pre-prepare消息<pre-prepare,v,n,D(m)>

v为当前视图

n为主节点分配的请求序号

D(m)为消息摘要

m为消息本身

从节点在收到pre-prepare消息之后，会对该消息进行合法性验证，若通过验证，那么该节点就会进入pre-prepared状态，表示该请求在从节点处通过合法性验证。否则，从节点会拒绝该请求，并触发视图切换流程。当从节点进入到pre-prepared状态后，会向其它节点广播prepare消息<prepare,v,n,D(m),i>，

i为当前节点标识序号

其他节点收到消息后，如果该请求已经在当前节点进入pre-prepared状态，并且收到2f条来自不同节点对应的prepare消息，从而进入到prepared状态，提案阶段完成。此时，有2f+1个节点认可将序号n分配给消息m，这就意味着，该共识集群已经将序号n分配给消息m。

Acala正追踪剩余5100万枚错误铸造的aUSD，并将向归还者提供5%赏金:8月25日消息，Acala官方在推特上宣布，其已确定了在aUSD错误铸造事件中剩余的5100万枚aUSD，其中绝大多数仍留在Acala的相关地址中，约70%的相关交易仍需要追踪。Acala表示，将向归还本次事件涉及资金的地址（需归还95%的资金）提供5%的赏金。资金一旦归还，Acala将不会对这些地址采取其他行动。

此前消息，8月14日因iBTC/aUSD流动性池配置错误，导致aUSD异常增发。此次事件中，Acala共异常增发30.22亿枚aUSD，现已通过公投销毁异常增发的29.7亿枚aUSD。[2022/8/25 12:47:00]

2)提交阶段

当请求在当前节点进入prepared状态后，本节点会向其它节点广播commit消息<commit,v,n,i>。如果该请求已经在当前节点达到prepared状态，并且收到2f+1条来自不同节点对应的commit消息（包含自身)，那么该请求就会进入到committed状态，并可以进行执行。此时，有2f+1个节点已经得知共识集群已经将序号n分配给消息m。执行完毕后，节点会将执行结果反馈给客户端进行后续判断。

▲检查点机制

PBFT共识算法在运行过程中，会产生大量的共识数据，因此需要执行合理的垃圾回收机制，及时清理多余的共识数据。为了达成这个目的，PBFT算法设计了checkpoint流程，用于进行垃圾回收。

checkpoint即检查点，这是检查集群是否进入稳定状态的流程。在进行检查时，节点广播checkpoint消息<checkpoint,n,d,i>

n为当前请求序号

d为消息执行后获得的摘要

i为当前节点表示

当节点收到来自不同节点的2f+1条有相同<n,d>的checkpoint消息后，即可认为，当前集群对于序号n进入了稳定检查点。此时，将不再需要stablecheckpoint之前的共识数据，可以对其进行清理。不过，如果为了进行垃圾回收而频繁执行checkpoint，那么将会对系统运行带来明显负担。所以，PBFT为checkpoint流程设计了执行间隔，设定每执行k个请求后，节点就主动发起一次checkpoint，来获取最新的stablecheckpoint。

除此之外，PBFT引入了高低水位的概念，用于辅助进行垃圾回收。在共识进行的过程中，由于节点之间的性能差距，可能会出现节点间运行速率差异过大的情况。部分节点执行的序号可能会领先于其他节点，导致于领先节点的共识数据长时间得不到清理，造成内存占用过大的问题，而高低水位的作用就是对集群整体的运行速率进行限制，从而限制了节点的共识数据大小。

BUSD平均交易量达20个月低点:金色财经消息，据Glassnode数据显示，BUSD平均交易量达到20个月低点，7日均值数额为244,505.23美元。上一次所观察到的20个月低点时间为2020年12月11日，7日均值数额为250,201.34美元。[2022/7/31 2:48:37]

高低水位系统中，低水位记为h，通常指的是最近一次的stablecheckpoint对应的高度。高水位记为H，计算方式为H=h+L，L代表了共识缓存数据的最大限度，通常为checkpoint间隔K的整数倍。当节点产生的checkpoint达到到stablecheckpoint状态时，节点将更新低水位h。在执行到最高水位H时，如果低水位h没有被更新，节点会暂停执行序号更大的请求，等待其他节点的执行，待低水位h更新后重新开始执行更大序号的请求。

▲视图变更

当主节点超时无响应或者从节点集体认为主节点是问题节点时，就会触发视图变更。视图变更完成后，视图编号将会加1，随之主节点也会切换到下一个节点。如图所示，节点0发生异常触发视图变更流程，变更完成后，节点1成为新的主节点。

当视图变更发生时，节点会主动进入到新视图v+1中，并广播view-change消息，请求进行主节点切换。此时，共识集群需要保证，在旧视图中已经完成共识的请求能够在新视图中得到保留。因此，在视图变更请求中，一般需要附加部分旧视图中的共识日志，节点广播的请求为<viewchange,v+1,h,C,P,Q,i>

i为发送者节点的身份标识

v+1表示请求进入的新视图

h为当前节点最近一次的稳定检查点的高度

C：当前节点已经执行过的检查点的集合，数据按照<n,d>的方式进行存储，表示当前节点已经执行过序号为n摘要为d的checkpoint检查，并发送过相应的共识消息。

P：在当前节点已经达成prepared状态的请求的集合，即，当前节点已经针对该请求收到了1条pre-prepare消息与2f条prepare消息。在集合P中，数据按照<n,d,v>的方式进行存储，表示在视图v中，摘要为d序号为n的请求已经进入了prepared状态。由于请求已经达成了prepared状态，说明至少有2f+1个节点拥有并且认可该请求，只差commit阶段即可完成一致性确认，因此，在新的视图中，这一部分消息可以直接使用原本的序号，无需分配新序号。

Q：在当前节点已经达成pre-prepared状态的请求的集合，即，当前节点已经针对该请求发送过对应的pre-prepare或prepare消息。在集合Q中，数据同样按照<n,d,v>的方式进行存储。由于请求已经进入pre-prepared状态，表示该请求已经被当前节点认可。

但是，视图v+1对应的新主节点P在收到其他节点发送的view-change消息后，无法确认view-change消息是否拜占庭节点发出的，也就无法保证一定使用正确的消息进行决策。PBFT通过view-change-ack消息让所有节点对所有它收到的view-change消息进行检查和确认，然后将确认的结果发送给P。主节点P统计view-change-ack消息，可以辨别哪些view-change是正确的，哪些是拜占庭节点发出的。

节点在对view-change消息进行确认时，会对其中的P、Q集合进行检查，要求集合中的请求消息小于等于视图v，若满足要求，就会发送view-change-ack消息<viewchange-ack,v+1,i,j,d>

i为发送ack消息的节点标识

j为要确认的view-change消息的发送者标识

d为要确认的view-change消息的摘要

不同于一般消息的广播，这里不再使用数字签名标识消息的发送方，而是采用会话密钥保证当前节点与主节点通信的可信，从而帮助主节点判定view-change消息的可信性。

新的主节点P维护了一个集合S，用来存放验证正确的view-change消息。当P获取到一条view-change消息以及合计2f-1条对应的view-change-ack消息时，就会将这条view-change消息加入到集合S。当集合S的大小达到2f+1时，证明有足够多的非拜占庭节点发起视图变更。主节点P会按照收到的view-change消息，产生new-view消息并广播，<new-view,v+1,V,X>

V：视图变更验证集合，按照<i,d>的方式进行存储，表示节点i发送的view-change消息摘要为d，均与集合S中的消息相对应，其他节点可以使用该集合中的摘要以及节点标识，确认本次视图变更的合法性。

X：包含稳定检查点以及选入新视图的请求。新的主节点P会按照集合中S的view-change消息进行计算，根据其中的C、P、Q集合，确定最大稳定检查点以及需要保留到新视图中的请求，并将其写入集合X中，具体选定过程相对繁琐，如果有兴趣，读者可以参阅原始论文。

▲改进空间与RBFT

RBFT，是趣链科技基于PBFT为企业级联盟链平台研发的高鲁棒性共识算法。相比较PBFT来说，我们在共识消息处理、节点状态恢复、集群动态维护等多方面进行了优化改良，使得RBFT共识算法能够应对更复杂多样的实际场景。

1)交易池

包括RBFT在内，许多共识算法的工业实现中，都设计了独立的交易池模块。在收到交易后，将交易本身存放在交易池里，并通过交易池对交易进行共享，使得各个共识节点都能获得共享的交易。在共识的过程中，只需对交易哈希进行共识即可。

在处理较大交易时，交易池对于共识的稳定性有不错的提升。将交易池与共识算法本身进行解耦，也更方便通过交易池实现更多的功能特性，比如交易去重。

2)主动恢复

在PBFT中，当节点借由checkpoint或view-change发现自身的低水位落后，即稳定检查点落后时，落后节点就会触发相应的恢复过程，以拉取该稳定检查点之前的数据。这样的落后恢复机制有一些不足：一方面，该恢复流程的触发是被动的，需要在checkpoint过程或者触发view-change完成时才能触发落后恢复；另一方面，对于落后节点来说，如果通过checkpoint发现自身稳定检查点落后时，落后节点只能恢复到最新的稳定检查点，而无法获得该检查点后落后的共识消息，可能一直无法真正参与到共识当中。

在RBFT中，我们设计了主动的节点恢复机制：一方面，该恢复机制可以主动触发，更快地帮助落后节点进行恢复；另一方面，在恢复到最新的稳定检查点基础之上，我们设计了水位间的恢复机制，从而使得落后节点能够获取到最新的共识消息，更快地参与到正常共识流程。

3)集群动态维护

Raft作为一种广泛应用在工程中的共识算法，其重要优势之一，就是能够动态完成集群成员变更。而PBFT没有给出集群成员动态变更方案，在实际应用中存在不足。在RBFT中，我们设计了一种动态变更集群成员的方案，使得不需要停启集群整体的情况下，就可以对集群成员进行增删。

新增或删除节点时，由管理员向集群发交易创建操作节点的提案，并等待其他管理员投票，投票通过后由创建提案的管理员再次向集群发执行提案配置交易，执行时会更改集群配置。

对于共识部分，当处理执行提案配置交易时，集群中的节点将进入配置变更状态，不再打包其他交易。主节点将该交易单独打包生成配置包，并对该配置包进行共识。当该配置包完成共识，它将被执行并生成配置区块。为了保证改配置区块不可回滚，共识层将等待改配置包的执行结果，确定集群中已经对于该配置包所在高度形成稳定检查点，才会解除节点的配置状态，继续进行其他交易的打包。

对于集群不同的配置状态，我们通过世代进行区分。不同世代拥有其独立的编号，该编号为单调递增的，每次执行完成一笔执行提案配置交易，将会对世代编号进行更新。对于集群中不同的节点，如果它们处于同一个世代下，则可以进行正常的信息交互。否则，节点之间只能进行状态恢复相关消息的交互。由于配置变更的信息已经被写入链上，因此，我们可以通过直接同步区块的方式为落后节点进行配置更新。通过上一节所说的主动恢复协议，世代落后的节点可以获取到最新的状态，并通过直接同步区块的方式恢复至最新的稳定检查点，同时完成节点世代与配置状态的恢复。

通过这样的动态变更集群成员的方式，使得集群配置维护更加可靠与便捷，并且可以为动态修改更多配置信息提供了可能。

作者简介

王广任

趣链科技基础平台部共识算法研究小组

参考文献

LamportL,ShostakR,PeaseM.TheByzantinegeneralsproblem//Concurrency:theWorksofLeslieLamport.2019:203-226.

CastroM,LiskovB.PracticalByzantinefaulttolerance//OSDI.1999,99(1999):173-186.

https://en.wikipedia.org/wiki/Quorum_(distributed_computing)

OwickiS,LamportL.Provinglivenesspropertiesofconcurrentprograms.ACMTransactionsonProgrammingLanguagesandSystems(TOPLAS),1982,4(3):455-495.

FredB.Schneider.Implementingfault-tolerantservicesusingthestatemachineapproach:Atutorial.ACMComput.Surv.,22(4):299–319,1990.

CastroM,LiskovB.PracticalByzantinefaulttoleranceandproactiverecovery.ACMTransactionsonComputerSystems(TOCS),2002,20(4):398-461.

标签：PREBFTVIEVIEWCoinbase Pre-IPO tokenized stock FTXbft币卖多少钱一个VersoView

MANA热门资讯