PBFT 核心概念以及基于 DPoS 的实现

众做周知, PBFT 是目前能够有效对抗拜占庭问题的算法之一, 使用 PBFT 意味着就算我们的系统中有 2/3 的节点有问题, 只要有 1/3 是好的, 那这个系统就依旧能正常运作. 最近需要在 DPoS 的基础上实现 PBFT 算法, 断断续续看了很久 PBFT 的论文, 提炼出在 DPoS 中需要注意的如下一些概念, 并分析在 DPoS 中如何实现 PBFT 的一些行为.

视图

整个分布式系统随时间往前推进, 每一个节点都可能成为主节点 (出块节点). 在 PBFT 中, 成为主节点的这段时间被称为视图, 视图是整数编号的, 每当发生主节点切换, 视图编号都会增一.

在 PBFT 的描述中, 主节点会发生切换是因为之前的主节点出问题, 而在 DPoS 中, 主节点总是变化的, 所以实际上视图也总是变化的. 实际上在我们的区块链实现中没有强调视图的存在, 主节点依靠 DPoS 协议, 在所有节点中随时间依次切换, 仅此而已.

三阶段提交

这是 PBFT 最重要的部分, 三个阶段分别称作: pre-prepare, prepare, commit.

在 pre-prepare 阶段中, 主节点会给要发出的消息 (区块) 分配一个编号 (hash 以及区块高度), 然后将消息广播给其它节点, 其它节点会根据情况决定要不要接受这个 pre-prepare 消息, PBFT 论文中对 pre-prepare 消息的接受提了四个条件, 我把这四个条件搬到我们的 DPoS 实现中, 可以转化成如下几条:

  1. pre-prepare 消息 (区块) 的发起节点是当前视图的主节点
    这一点是为了避免有非法节点冒充主节点出新块. DPoS 要想避免这个问题是很容易的, 由于 DPoS 机制规定了每一个区块的出块节点是确定的, 所以节点收到 pre-prepare 消息 (区块) 的节点只需要计算一下这个区块理应谁来出, 再用理应出块节点的公钥验证一下区块中的签名就知道真假了.
  2. 在同一个视图中, 收到相同高度, 不同哈希的区块的话, 只接受第一个
    这在 DPoS 中意味着见证人节点在瞎搞, 连续出了两个块, 高度还一样, 这样的见证人应当被踢掉.
  3. 在同一个视图中, 收到相同哈希的区块的话, 只接受第一个
    这里要说一下, 在我们的实现中, 区块高度也会被算进哈希里的, 所以哈希相同的话, 高度也是相同的, 所以这种情况的出现可能是 p2p 网络消息重复导致的. Anyway, 收到重复区块的节点, 忽略后收到的就好了.

PBFT 原文四个条件中的最后一个条件是对消息编号范围的规定, 原文称为高低水位, 其思想是说, 收到的消息编号不能比之前刚收到的消息的编号大太多也不能小太多. 这点我们在引入 PBFT 之前就加入了对区块高度的验证, 收到的区块的高度一定要比我们当前最新区块高度严格大一才会接受, 所以这点不是问题.

Ok, 只要上面的条件都能够满足, 节点就会广播对此区块的 prepare 消息给其他所有节点, 注意这个过程, 是所有收到 pre-prepare 消息并且验证上述条件都 ok 的节点, 都会广播 prepare 消息给其它所有节点, 所以这个过程的消息量是 n^2, 而前面 pre-prepare 的消息量只是 n.

这样一来, 每个节点都最多能够收到其它 n-1 个节点的 prepare 消息, PBFT 规定当节点收到 2f 条 prepare 消息 (包含自己一共 2f+1, 为什么是这个数后面再说) 时, 就说明这个区块被大部分节点认可了.

然后收到了 2f 条 prepare 消息的节点往外广播 commit 消息, 这个过程的消息量也是 n^2, 当节点收到 2f 条 commit 消息后, 就写区块.

Checkpoint 和 Stable Checkpoint

PBFT 中还提到了 checkpoint 和 stable checkpoint 的概念, 对应到 DPoS 区块链中, checkpoint 就是某个区块, stable checkpoint 实际上就是最后不可逆区块.

PBFT 中的 stable checkpoint 还是要靠节点之间发消息来确认, 在 DPoS 的最后不可逆区块机制中, 我们可以在每当有新区块产生时顺着往前找, 找到最新的被 2/3 的节点确认过 (指后面跟着 2/3 的见证人生产的区块) 的区块, 将其标记为最后不可逆区块.

垃圾收集

在 PBFT 中, 凡是在 stable checkpoint 之前的记录都说明已经有至少 f+1 的好节点执行过了, 因此 stable checkpoint 之前的记录可以删除以释放空间.

但是在实际实现中, 我想不会真的有人真的删除这些记录, 至少是会把这些记录落盘. 区块链就是这样. 比特币中每个区块的交易被执行后会算出一批新的 UTXO 维护在内存中, 但是原始区块一定也是要写入磁盘的, 只要有原始区块, 节点重启就能重放这些区块, 重新生成 UTXO 集合. 在我们的 DPoS 中也是如此.

但是在我们的实现中, 也确实存在 “垃圾” 需要收集, 就是那些未收到足够认可的 pre-prepare 区块, 这些区块在发起后, 由于没有足够认可, 被后续的新区块替代, 而这些区块会一直保存在各个节点的内存中等待着足够的 prepare/commit 消息. 这是需要被清理的.

为何 prepare 阶段需要收到 2f 条消息, 以及为何还需要 commit 阶段

PBFT 规定当节点收到 2f 条 prepare 消息 (包含自己一共 2f+1) 时, 就说明这个区块被大部分节点认可了, 为什么是 2f 条呢?

因为总共 3f+1 个节点中, 最多只有 f 个恶意节点, f 个故障节点, 如果我收到了 2f 条 prepare 消息, 那就说明这 2f 条消息中一定有至少 f 条消息是好节点发来的. 这里如果 “我” 也是恶意节点, 那 2f 中的好节点一定大于 f, 如果 “我” 是好节点, 2f 里的好节点加上我一定还是大于 f.

不论如何, 收到 2f 条 prepare 消息就说明整个系统中至少 f+1 数量的好节点都认可了这个区块.

所以现在这个区块是一个可写状态, 但是还不能写, 因为我收到了 2f 条 prepare 消息并不代表其它节点都收到了 2f 条 prepare, 虽然知道现在系统中有至少 f+1 的好节点认可了区块, 但是其他好节点可能会因为网络问题 (PBFT 基于异步网络, 不能保证有限时间内收到消息) 没有收够 2f 条 prepare, 万一只有我收够了 2f 然后我写区块了, 那岂不是只有我分叉了?

所以 PBFT 的做法是, 所有收到 2f 条 prepare 消息的节点, 继续向外广播 commit 消息, 然后再当节点收到 2f 条 commit 消息时, 再正式写区块. 和 2f 条 prepare 同样的道理, 当我收到 2f 条 commit 时, 就说明整个系统中至少 f+1 数量的好节点都收到了 2f 条 prepare 消息, 也就是至少 f+1 数量的好节点都准备要写这个区块了, 那我当然也可以放心大胆的写这个区块了.

然而, 这里实际上还存在问题, 那就是 commit 消息也未必被至少 f+1 个好节点收到 (异步网络问题), 可能只有少部分节点收到了 2f 条 commit 消息, 并执行了 commit 动作. 这种情况 PBFT 里有措施应对, 我没有仔细看, 但是在我们的设计中当然也有措施应对的, 其实这个情况无非就是导致两种后果:

  1. 未执行 commit 的节点成为下一个出块节点, 他会发起新的 pre-prepare, 前面少部分执行了 commit 的节点会拒绝这个 pre-prepare, 但是新的 pre-prepare 依然可能会进入 commit 阶段被 2f 以上的节点 commit. 结果就是产生分叉, 然后根据最长链准则决出胜负.
  2. 执行了 commit 的节点成为下一个出块节点, 在它发起新的 pre-prepare 后, 其他节点会过来请求同步区块信息, 不会产生分叉, 正常进行.
赞赏

微信赞赏支付宝赞赏

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据