dBFT 2.0通过新增commit提交阶段 使用恢复消息增强共识算法

引言：共识问题的来源

区块链平台在设计和开发去中心化应用程序和系统方面取得了令人难以置信的进展，从加密货币到企业供应链等领域，都已被广泛应用。虽然应用非常广泛，但它们都是基于一组核心的设计模式，正是这些设计模式推动了分布式系统理论和实践的发展。

区块链是使用加密技术将记录(或区块)链接而成的单调递增的列表。区块由一组有效交易构成，其中交易通过默克尔树进行哈希与编码，且每个区块会记录其前一个区块的加密哈希值。这确保了区块链的完整性，同时允许对每个区块以及区块链中的交易进行相对低成本的验证和独立审计。区块链本质上是公开且防篡改的，这意味着任何方式都无法更改现有的区块。

区块链的核心是分类账本模型，分类账本是一个不可更改的、只可追加的、发生在不同实体间的交易日志。为了保持分类账本的完整性，各实体需要通过某种方式就是否将一组增量交易(或区块)附加到分类账本上达成协议或者共识。

共识问题是多实体系统协调与控制中的一个著名而基础的计算机科学问题。一种简单的方法当然是让所有实体就多数达成一致。然而，一个或多个故障实体可能会对结果造成影响，从而导致共识无法达成或不正确。

本文将探讨区块链共识这一主题，并分享一个真实的基于.NET Core平台的C#实现方案，C#是Neo区块链、币安交易所以及其他一些项目实体所使用的编程语言。

区块链平台&分布式系统

首先先了解一下区块链平台，它们是可编程的区块链，使开发人员能够构建真正去中心化的应用程序。其中可以涉及多种市场领域，包括金融市场、游戏、企业联盟、体育、医疗保健网络、主权身份、房地产和其他资产市场等等。以太坊和Neo等区块链平台作为去中心化的应用平台，为开发人员提供了新的应用模型基础。

区块链平台的核心是分布式系统，该技术建立在数十年计算机科学研究的理论和实践基础之上。虽然有许多重复出现的模式和原则，但区块链平台在我们如何处理信任方面彻底颠覆了分布式系统的理论。在下一节，我们将进一步深入研究分布式系统及其使用计算机科学中著名的状态机模型的相关实现。

分布式系统与状态机方法

通过对理论计算机科学领域的探索，我们发现各类分布式系统均共享以下核心特性：

并发 ：分布式系统中的多个活动可以同时独立地执行。这意味着需要在不同的执行流间进行协调。

独立故障模式 ：分布系统中的多个组件可能发生独立故障。

无全局时间 ：多个执行流可以与空间独立的本地时钟对齐。即使这些时钟最初是同步的，最后也会产生时钟偏差。这意味着时间和事件顺序是分布式系统的核心挑战。

通信延迟 ：事件及其影响在分布式系统中的传播存在固有延迟。

不一致状态 ：并发、独立故障模式和通信延迟的存在意味着任一状态的视图在整个分布式系统中会出现不一致。

总的来说，这些特性要求分布式系统具有容错性，以便在一个或多个子系统发生一个或多个故障(或完全故障)时能够继续运行。

状态机方法是通过复制服务和跨服务副本协调客户端交互来实现容错分布式系统的一般方法。复制状态机是确定性的，因为它由一组状态变量组成，这些变量会对其状态和交易进行编码。这些状态变量可能引起计算机从一个有效状态转换到下一个有效状态。每个交易都是确定执行的(即，交易具有原子性)。从本质上讲，复制状态机是一组分布式服务，其中所有服务都从相同的初始状态开始，然后在随后的每个状态转换上达成一致(即，达成共识)。

复制状态机之间的共识

正式而言，共识算法的目标是满足三个关键特性。分别是：

终止性 ：系统中的所有非故障服务最终会决定某些输出值。这通常被称为活性。

完整性 ：如果所有非故障服务都提出相同的输出值，那么任何非故障服务都必须决定相同的输出值。一种较弱的完整性形式是输出值必须等于某个非故障服务(不一定是所有服务)提出的值。

一致性 ：系统中所有非故障服务最终会决定相同的输出值。这通常被称为安全性。

分布式系统理论在共识算法的理解上已经取得了巨大的飞跃，但是在一个完全异步的分布式系统中，即使只存在单一的故障服务，共识也不可能实现。这被称为FLP不可能性，以研究人员(Michael J. Fischer, Nancy Lynch 和Mike Patterson)命名，他们对异步环境中分布式进程可能实现的目标设定了一个确定的上限。

FLP不可能性催生了针对两种创新方法的研究。一组算法依赖于所谓的中本共识。它采用了一种非传统的方法，这种方法依赖于非决定性来解决在分布式系统中试图产生共识时固有的规模挑战。中本共识的精髓在于，算法关注的不是每一个服务在某个值上达成一致，而是所有服务就该值正确的概率上形成共识。

然而，这会导致概率一致性，也就是说，在每一个状态转换时，无法确定性地得到一个最终值，这就造成了无法保证真正的终局性的情况。这会导致分布式系统中所谓的分叉场景。因此，在下文我们将不再讨论中本共识。

第二组实用的容错共识算法作了一定程度的同步性假设以取得进展。这意味着部分协议被设计成在不可靠的网络中运行，比如说，在因特网上发生丢包并可能导致任意延迟，而其他协议则是为高度可靠的网络信道而优化的。这些协议据说是在不同的同步假设下运行的。例如，通过依赖于领导人选举算法，同步假设可以是显式的，也可以是隐式的。基于领导人选举的共识算法称为Paxos算法。

拜占庭容错共识

拜占庭故障给基于领导人的共识算法带来了挑战。当分布式系统的组件或子组件发生故障时，就会出现这些故障，并且组件(或子组件)是否实际发生故障的信息是不完整的。现有的算法证明表明，恶意领导者不会导致不一致状态，但分布式系统理论尚未证明恶意领导者无法阻止算法进一步运作。

Castro 和Liskov 提出的所谓实用BFT(pBFT)算法是首次尝试描述一种算法，通过该算法，系统可以检测到进度停滞并选择出新的领导者。pBFT的设计是为了解决先前尝试中的两个缺陷，要么算法运行太慢而无法在实际中使用，要么必须假设同步性以满足“一致性”的属性。

pBFT算法证明，只要分布式系统中出现故障的服务数不超过(n-1)/3，pBFT算法就可以同时提供活性和安全性。pBFT通过一系列“视图”进行循环，每个视图都有一个主服务作为议长，其余服务作为备份(议员)。在概念层面，pBFT算法的工作原理如下：

1. 客户端向主(议长)服务发送请求。

2. 主(议长)服务将请求广播到所有备份服务。

3. 主服务和备份服务处理请求，然后将回复发送回客户端。

4. 当客户端从跨分布式系统的不同服务接收到m+1响应并得到相同的结果时，请求即被成功地得到处理，其中m是允许的最大故障服务数。

主(议长)服务在每一个视图(共识轮次)期间都会更改，并且如果议长没有在预定的时间阈值内向议员广播请求，则可以替换主(议长)服务。只要议长没有发生故障，pBFT就可以正常运作;但是，更换故障的议长这一过程的效率是很低的。

pBFT在现有理论的基础上进行了改进，但在实际应用中由于其固有的可扩展性挑战以及无法对恶意行为和瞬时通信故障进行区分，因此不适合于真实场景。

委托拜占庭容错

委托拜占庭容错(dBFT)是2014年NEO区块链创始人张铮文提出的。dBFT将pBFT的概念扩展到状态机复制场景，并提供了对快速单区块数据终局性(大约15秒)的第一个实用的公开访问。dBFT目前正被NEO区块链、币安交易所和全球其他主要平台所使用。

张铮文提案的关键创新在于区分共识节点(可以参与共识算法以提出新的状态更改和投票的服务)和普通节点(可以执行原子交易和状态转换的服务，但不参与共识算法，也不能发起新的状态变更)。通过这样做，dBFT成为第一个大规模运行的实用BFT算法，解决了pBFT固有的挑战。

dBFT的c#实现可在GitHub的bit.ly/2Zl1Sem上的公共域(MIT许可证)中获得。

dBFT算法包括三个不同的阶段：预准备、准备和持久化。在我们探索每个阶段之前，让我们花一点时间来澄清术语和涉及的算法步骤。

N：活跃的共识节点数

f：拜占庭(即恶意)节点数，f不大于(N-1)/3

v:当前视图编号(每个视图都是新一轮或尝试达成共识)

b:包含原子交易的提案块，其执行将系统转换到下一个有效状态

P:议长索引，即该视图下发起提案块的节点。议长和其余议员一起构成N个共识节点。

在概念层次上，dBFT包括以下步骤：

1. 加密签名的交易由客户端“广播”到分布式系统中的节点。

2. N个共识节点接收交易并将其加入内存中的交易池中。

3. 对于当前视图，唯一的议长p将来自内存池的交易打包到新的提案块b中。图1说明了MakePrepareRequest 方法，图2说明了SendPrepareRequest 方法。

4. 剩余的N-1个议员接收新的提案块b，对其进行验证并对验证结果进行广播。为简洁起见，其余步骤的代码片段将不再列举，可访问前面所提供的GitHub的链接进行查看。

5. 任意共识节点在接收到至少(N-f)个验证后达成共识，然后发布新的区块。

6. 任意节点在接收到新的区块时，都会从内存池中删除所有交易，如果是共识节点，则开始下一个视图(一轮共识)。

所有这些都解决了，让我们回到dBFT算法的三个阶段。它们分别是：

预准备 ：本次视图的议长负责向议员广播Prepare-Request消息，并发起新的交易提案块。

准备 ：在接收到Prepare-Request消息时，如果成功验证了提案块，则议员广播Prepare-Response消息。当接收到(N-f)条区块成功验证的消息时，共识节点进入下一阶段。

持久化 ：节点发布新块并进入下一轮共识。

在某一轮(视图)未达成共识的情况下，共识节点可以发起视图更换提案，在收到至少(N-f)个具有完全相同视图编号的视图更改提案后，重新选举议长节点(领导者)并重启达成共识的活动。发起新一轮视图的等待时间呈指数增长，以避免频繁的视图变更，并确保在实际时间范围内达成共识。

由于在某些边缘情况下出现的网络延迟，dBFT的第一个版本存在单区块分叉的影响。实际上，节点在发送PrepareResponse 消息后可能超时，这意味着节点可能在稍有不同的时间发生超时和状态转换。如果只有一个共识节点没有超时，并且该节点已经收到2f条 PrepareResponse 消息，那么它将生成一个有效的区块，而其他共识节点将转移到下一个视图。在该视图上，这些共识节点理论上可以达成共识，并在同一高度对另一个交易区块进行签名。虽然该场景可以在不阻塞共识的情况下发生，但一个或多个节点可能会接受到分叉的区块而停止运行。

dBFT 2.0通过新增一个commit提交阶段解决了这个问题。为了防止可能出现的运作停止，dBFT 2.0还使用一个恢复消息实现方案来增强共识算法。这种恢复机制的另一个好处是，在由于网络受损而导致网络延迟降级的情况下，可以显著改善出块时间。

结语

分布式系统是改革计算行业的基础，也是我们如何在全球范围内进行商业活动，以及我们如何作为一个社区广泛参与的基础。区块链的出现促使开发人员研究和审查分布式系统中的既定原则和范例，并在这样做的过程中推动了一股创新浪潮，这股浪潮继续在开发人员如何构建下一代软件应用程序方面开辟新的天地。

本文我们重点讨论了共识问题，并用dBFT共识算法说明了一种开创性的新方法。当我们使用C#来说明dBFT共识算法时，我们也实现了c++、python、typescript和go的dBFT算法。我们希望本文能让开发人员更好地理解区块链共识，并使他们能够使用并基于领先的dBFT算法进行开发。

张铮文

张铮文是NEO的创始人和核心开发人员，dBFT共识机制的创作者，区块链技术和计算机安全专家，以及注册信息系统审计师(CISA)。此前，他在盛大游戏和火币工作，专门从事信息安全和数字货币研发。

John deVadoss

John deVadoss领导NGD在西雅图的开发。此前，他创建了Microsoft Digital、.NET 模式与实践和.NET体系结构战略。在微软工作时孵化了微软的Azure。最近，他创办了两家机器学习初创公司。deVadoss在机器学习方面取得了博士学位，专门研究递归神经网络。（NEO）