CITA系列之共识算法——BFT

考虑了挺久，最后还是决定先将 BFT 模块拿出来讲解，executor 和 chain 在 cita 的流程中都是在最后处理数据和落盘的模块，先讲解数据来源可能会更有利于理解整体思路。我看代码的顺序（chain->jsonrpc->network->executor->auth->bft）与文章的顺序不太一致，导致在看完第三个模块之后才开始有一个整体的概念。这系列文章的目的是帮助读者轻松（不大量阅读源码）的了解 cita 的工作流程，对 cita 有一个完整的整体认知。

BFT

分布式应用绕不过去的话题就是共识算法，甚至可以说，共识算法就是分布式的核心。经典的拜占庭问题、CAP 理论是分布式方面的阶段性总结。我在分布式领域还是个菜鸟， 对整个学术理论的理解几乎都来自于一些经典书籍，对共识算法的了解也仅限于 Raft、TenderMint 这几个比较有名的算法，并且也仅仅是了解流程，代码实现方面几乎没有什么实践性的操作。这一篇文章，仅仅是针对 cita-bft 代码的一些浅层次讲解，更深入的部分，实力有限，理论知识匮乏，就不献丑了。

cita-bft 总体来说是 TenderMint 算法的变种实现，两轮投票后达成共识、投票开始的时候锁住该高度的 block，一轮没有达成共识则进入下一轮（round）投票，直到完成该高度的共识，保证整个链不会分叉。下面这个结构体就是整个 bft 的状态机状态：

bft 的代码实现，就是一个大的状态机，以及一个定时器，状态由链上消息通信以及计时器 timeout 机制推动。

代码分享计时器

代码：https://github.com/cryptape/cita-bft/blob/develop/src/core/votetime.rs#L35

计时器，读写各一个 channel，加上一个线程池，它的任务很简单，接收状态机的计时命令，线程池计时完成后，将超时状态回复给 bft 状态机，bft 根据接收到的投票信息以及当前状态，决定是进入下一个状态还是回滚等操作。

MQ 监听转发

代码：https://github.com/cryptape/cita-bft/blob/develop/src/main.rs#L185

这个部分也很简单，监听消息，立刻转发给 bft 状态机。

状态机

代码：https://github.com/cryptape/cita-bft/blob/develop/src/core/cita_bft.rs#L108

这个结构体非常多 field，共识期间需要维护一堆状态，例如，当前节点是否有投票权利 ，接到投票后，需要先序列化在本地 ，整个链的共识节点列表，即公钥管理 ，当前投票的 block ，接到的prev_hash 验证完毕，until_block 验证完毕，交易信息未确认块 ，链上各个节点的状态 ，上一个高度的共识结果 ，以及每一次进入投票阶段后，每一轮投票收到的票的 collector。

从 MQ 消息的视角看状态机

代码：https://github.com/cryptape/cita-bft/blob/develop/src/core/cita_bft.rs#L1365

消息来源分为两大类：

来源于 Network，即其他节点消息：

SignedProposal，接到已经签名的 proposal ，判断自身是否有权利投票、判断高度、验证签名、验证该轮是否为此节点提出 proposal 、发送该 proposal 下的 block transaction 给 auth 验证交易是否正常等一系列验证操作，最后给 计时器发送一个计时消息，转至状态。

RawBytes，接到对 proposal 的投票消息，根据投票的轮数不同分别处理，如果数据正常，则分别进入和状态。

来源于本地其他模块:

RichStatus，消息来自于 chain ，根据传输过来的状态表达的含义有多种，如果高度等于上一次共识高度，则表明块落盘成功，bft 状态由更改为; 如果高度等于上一次共识高度 - 1，则说明落盘出现了异常，bft 重新将上一次的共识结果发送到 MQ（如果还保留着的话）。同时根据 Richstatus 中的共识列表、prev_hash 等重要信息更新自身的信息。

VerifyBlockResp，消息来自于 Auth，Auth 接到 bft 发的交易信息并验证后，返回结果，如果验证无误，移除待验证交易列表中对应的交易，并将该 proposal 序列化到磁盘，状态切换为， 检查投票信息，如果投票信息已经大于 2/3 了，那么随即转入状态；如果验证失败，清除待验证交易信息，并广播，投空票，转入状态，检查投票信息，如果投票信息已经大于 2/3 了，那么随即转入状态。

BlockTxs 消息来自于 Auth，chain 落盘成功后的 Richstatus 消息 Auth 接到后，清除交易池中对应的交易，并从交易池中按一定顺序打包一份新的交易，发送给 bft。bft 接到消息后，先序列化到本地，再判断这个高度和轮数是否是自己出块，如果是，验证必要信息后生成一个新的 proposal，广播给整个链，发送计时消息。

从计时器的角度看状态机

代码：https://github.com/cryptape/cita-bft/blob/develop/src/core/cita_bft.rs#L1261

一般在状态机进入 状态的时候，就会发一个计时消息给计时器，根据状态的不同有些是即刻返回超时消息，有些是等待一定时间后返回超时消息。

总体思路就是，在等待其他节点投票结果的过程中，给一个时间限制，在到达时间限定范围后，检查投票是否已经达到 2/3 ，即共识已经达成可以转入下一个状态，如果共识完成，则发送共识结果给 chain，如果没有，则或重发消息，或整体重新开始一轮投票，或当前 proposal 作废，重新开始。

总结

分布式应用的算法有两大类，拜占庭容错和非拜占庭容错，都挺复杂的，学术理论研究和工程实现也各不相同，我对这一块的了解相当匮乏，书也没看几本，论文就更不用说了，惭愧。

不管怎么说，目前 cita-bft 的代码实现讲解还是在磕磕绊绊中完成了，下一篇应该可以进入 executor 了，虽然本系列文章并没有打算深入讲 evm 虚拟机执行交易的过程，但是可以根据下一篇的讲解自行研究嘛。