Skip to main content

dBFT 2.0 算法

共识术语#

名称定义
共识节点具有发起新块提案和对提案投票权限的节点
普通节点具有转账、交易权限和全网账本，但不能发起区块提案与投票
议长负责向其他节点广播新块提案
议员参与共识出块的账户，负责对新块提案进行投票
候选人被提名有权参与共识节点竞选的账户
共识节点从候选人中被选出的，参与共识的账户
视图一轮共识从开始到结束所使用的数据集。视图编号v，从 0 开始，本轮共识失败时v 逐渐递增，直到新的提案通过后重置

共识消息#

dBFT 2.0算法包含6种共识消息：

名称描述
Prepare Request发起新一轮共识的信息
Prepare Response用来通知其他节点已获取构建区块的全部交易信息
Commit通知其他节点已获取了足够多的Prepare Response
Change View Request尝试改变视图的信息
Recovery Request同步共识状态的请求
Recovery Message对Recovery Request的响应信息

共识流程#

三阶段共识流程#

如图所示，一轮共识具有以下4个步骤：

  1. 议长发起共识，广播Prepare Request

  2. 接收到Prepare Request后，议员广播Prepare Response

  3. 接收到足够多的Prepare Response后，共识节点广播Commit

  4. 接收到足够多的Commit后，共识节点产生新块并广播

这里引入两个变量：

其中，N为共识节点的总数。

常规情况的算法流程如下图所示。

1) 初始化本地共识信息#

  1. 重置共识上下文

  2. 设置编号为 (h - v) mod N 的共识节点为本轮共识的议长，其中，h为区块高度，v为当前视图编号，N为共识节点数目

  3. 设置超时时间。对于议长，若正在处理其他节点的 RecoveryMessage，超时时间设置为 2v+1 Tblock ，其中 Tblock 为区块周期，当前为15s；否则，若上个高度没有参与出块，设置超时时间为 Tblock* ，而若上个高度参与过出块，则计算上次出块的时间和当前时间的时间差 D ，若 D < Tblock ，设置超时时间为 Tblock - D，否则设置为0。

  4. 若为刚启动共识，还会向其他节点发送 Recovery Request 获取当前共识状态

2) 各共识节点超时前监听网络，收集交易信息#
3) 发起共识#

  • 议长：

    1. 在超时时间后按照共识策略从内存池中选取交易，取哈希打包为Prepare Request并广播，发起新一轮共识

    2. 将选出的交易信息每500个打包并广播

    3. 将超时时间设置为 (2v+1 - k(v))*Tblock ，其中

  • 议员：

    • 若在超时前接收到议长发出的Prepare Request：

      1. 验证消息的合法性，以及是否符合本地共识状态

      2. 将本节点的超时时间延长

      3. 更新本地共识状态

      4. 对于消息包含的交易哈希，尝试从内存池或未确认的交易中获取相应交易，并添加至共识模块

      5. 向其他节点查询步骤4中未在本地找到的交易信息

    • 若没有在超时前接收到议长发出的Prepare Request，则会尝试改变视图

4) 广播Prepare Response#

  • 议员若在超时前收集到Prepare Request中全部交易信息:

    1. 对于每一条交易信息：若交易验证失败或不符合共识策略，尝试改变视图，否则将交易添加至共识模块

    2. 广播Prepare Response信息

    3. 将本节点的超时时间延长

  • 否则，尝试改变视图

5) 收集Prepare Response & 广播Commit#

  • 议长以及接收到Prepare Request的议员，若在超时前收集到至少M个议员的Prepare Response：

    • 对于每一条Prepare Response：

      1. 验证消息的合法性，以及是否符合本地共识状态

      2. 将本节点的超时时间延长

    • 广播 Commit 信息

  • 否则，尝试改变视图

6) 收集Commit信息 & 出块#

  • 每个已收集齐Prepare Request中交易信息的共识节点，若在超时前收集到至少M个共识节点的Commit：

    • 对于每一条Commit：

      1. 验证消息的合法性，以及是否符合本地共识状态

      2. 将本节点的超时时间延长

    • 生成并广播新块

  • 否则，广播Recovery Message，并将超时时间设置为 2*Tblock

7) 回到第1步，开始下一轮共识#

Change View Request 消息#

触发场景#

  • 议员在验证交易出现问题时，会广播Change View Request尝试更换议长

  • 议员等待议长的Prepare Request超时，或等待Prepare Response超时，广播Change View Request信息尝试更换议长

流程#

  1. 将超时时间设置为 2v+2 * Tblock

  2. 若已经发出Commit信息的节点和故障节点（超过一个区块高度没有收到过其共识信息的共识节点）数目之和大于F，则广播Recovery Request信息

  3. 否则，广播Change View Request信息，并检查已收到的Change View Request数目：若超过M个共识节点就更换视图达成共识，则改变本地视图，初始化本地共识信息，并根据新的视图编号确认下一轮议长

处理逻辑#

当共识节点收到Change View Request时：

  1. 若信息的视图不大于本地视图，该信息作为Recovery Request处理

  2. 验证消息的合法性

  3. 检查已收到的Change View Request数目：若超过M个共识节点就更换视图达成共识，则改变本地视图，初始化本地共识信息，并根据新的视图编号确认下一轮议长

Recovery Request 消息#

触发情景#

  • 开启共识节点会广播Recovery Request信息，以同步至最新共识状态

  • 发起Change View Request的时候，若缺少足够的活跃共识节点连接（已经发出Commit信息的节点和故障节点数目之和大于F）的时候，向网络广播Recovery Request消息，以将数据同步至最新共识状态

处理逻辑#

共识节点收到Recovery Request时，只有满足以下条件，才会生成并广播Recovery Message

  • 本节点在本轮共识发送过Commit信息

  • 或编号在议员列表中在以下范围内：，其中 j 为 Recovery Request 发起者的编号

Recovery Message 消息#

内容#

  • 不超过M个议员的上次Change View Request信息

  • 本节点和其他共识节点Prepare Request/Response信息

  • 各共识节点的Commit信息

触发情景#

  • 收到Recovery Request，且本节点发送过Commit信息，或编号在议员列表中在以下范围内：，其中 j 为Recovery Request发起者的编号

  • 收到Change View Request信息时，若信息的视图不大于本地视图，该信息作为Recovery Request处理

  • 等待Commit超时，通过发送Recovery Message，再次广播Commit信息（常见于网络问题）

处理逻辑#

  1. 验证消息的合法性，以及本地共识状态：消息的视图大于本地视图，且本节点已经在本轮发送过Commit，则忽略该消息

  2. 否则，若信息的视图大于本地视图：处理信息中包含的Change View Request

  3. 若信息的视图等于本地视图：

    • 处理信息中包含的Prepare Request：

      1. 若本地未发送或接受到Prepare Request，接收信息中包含的Prepare Request

      2. 否则，若本节点为议长，广播Prepare Request信息

    • 处理信息中包含的Prepare Response

  4. 若信息的视图小于等于本地视图：处理信息中包含的Commit

Change View Request，Recovery Request和Recovery Message机制能够避免网络原因导致的超时，异常节点（作恶节点，故障节点等非正常共识节点）等问题带来的影响。

共识策略#

共识流程中的以下场景会使用共识策略：

  • 当节点接收到来自其他节点的交易信息时，需要验证该交易是否满足现有共识策略的过滤条件，以便过滤掉不符合策略的交易

  • 共识模块接收到交易信息时，需要验证该交易是否满足共识策略，若不满足，则尝试改变视图

  • 启动共识时，需要使用共识策略对共识模块中的交易进行过滤，在将未确认的交易过滤后，才能将交易添加到内存池中

  • 议长在生成新的Prepare Request时，需要通过共识策略从当前内存池中筛选出可以上链的交易