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 实现中, 可以转化成如下几条:
- pre-prepare 消息 (区块) 的发起节点是当前视图的主节点
这一点是为了避免有非法节点冒充主节点出新块. DPoS 要想避免这个问题是很容易的, 由于 DPoS 机制规定了每一个区块的出块节点是确定的, 所以节点收到 pre-prepare 消息 (区块) 的节点只需要计算一下这个区块理应谁来出, 再用理应出块节点的公钥验证一下区块中的签名就知道真假了. - 在同一个视图中, 收到相同高度, 不同哈希的区块的话, 只接受第一个
这在 DPoS 中意味着见证人节点在瞎搞, 连续出了两个块, 高度还一样, 这样的见证人应当被踢掉. - 在同一个视图中, 收到相同哈希的区块的话, 只接受第一个
这里要说一下, 在我们的实现中, 区块高度也会被算进哈希里的, 所以哈希相同的话, 高度也是相同的, 所以这种情况的出现可能是 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 消息. 这是需要被清理的.
(原文: PBFT 核心概念以及基于 DPoS 的实现)