本文讲的是区块链共识机制，

• 原文地址：Consensus
• 原文作者：The Neo Project
• 译文出自：掘金翻译计划
• 本文永久链接：https://github.com/xitu/gold-miner/blob/master/TODO/neo-project-docs-consensus.md
• 译者：王子建
• 校对者：faintz wild-flame

区块链共识机制

1 - 术语

• 权益证明机制 PoS - 一种使用网络共识来处理容错的算法
• 工作量证明机制 PoW - 一种使用计算力来处理容错的算法
• 拜占庭错误 BF - 节点可用，但由于其行为不可靠造成的失败
• 改进的拜占庭容错机制 DBFT - 在 NEO 区块链内部实现的保证容错的共识算法
• 视图 v - NEO DBFT 共识行为中使用的数据集

2 - 角色

在 NEO 共识算法中，共识节点由 NEO 持有者选出并对交易合法性进行投票，同时它们也被称作“账本”。但在下文中，它们将被统称为共识节点。

•  共识节点 - 参与共识行为的节点。在共识行为中，共识节点轮流扮演以下两个角色：
•  发言人（一个）- 发言人负责向系统发送区块提案。
•  议员（多个） - 议员负责达成交易共识。

3 - 简介

区块链之间的一个根本差异就是如何在有缺陷和不诚实行为的网络中保证容错。

使用 PoW 这种传统的实现方法可以保证容错，只要网络中的大部分计算力都是诚实的。然而，因为这种方案对于计算的依赖，使得其效率非常低（计算力耗费能源并且对硬件有一定要求）。这使得 PoW 网络受到很多限制，最主要的就是扩展成本。

DBFT 在 NEO 中的实现利用了一些类似 PoS 的特点（NEO 持有者投票产生共识节点），这能保护网络不受拜占庭错误干扰并将消耗的资源最小化，同时也能去其糟粕（指 PoS 实现中的问题，译者注）。这个方案在没有对容错机制造成显著影响的情况下，妥善处理了当下区块链实现中性能与扩展之间的问题。

4 - 理论

拜占庭将军问题是分布式计算中的一个经典问题。这个问题中定义多个议员必须在发言人的命令下达成共识，在整个系统中，发言人或某些议员可能会是叛徒，因此我们要小心行事。最糟糕的情况下，非诚实节点可能会向每个接收者发送不同的信息。该问题的解决办法要求议员们组团鉴定发言人是否诚实并且鉴别出真实的命令。

为了说明 DBFT 的工作机制，我们将在本部分着重论述为何要在第五部分用 66.6% 的共识率。要记住，非诚实节点并不总是会做出恶意行为，它也可能只是简单地失效了而已。

为了便于讨论，我们设想一些场景，在这些简单的例子中，我们假定每个节点都按照发言人的信息发送响应。这种机制也被用在 DBFT 中，并在系统中严格执行。我们只描述正常系统与失效系统之间的区别，若想获取更多内容，请查看参考文献。

诚实的发言人

图 1: 一个 n = 3 的例子，其中包含一个不诚实的议员.

在图 1中，我们只有一个诚实的议员（50%），每个议员都会从诚实的发言人那里获取到相同的信息。然而，因为其中一个议员是不诚实的，诚实的议员只能判断出存在一个不诚实的节点，但是并不能鉴别该不诚实节点是区块核心（即发言人）还是议员。因此，议员必须放弃投票，放弃改变视图。

图 2: 一个 n = 4 的例子，其中包含一个不诚实的议员.

在图 2中，我们有两个诚实的议员（66％），每个议员都会从诚实的发言人那里获取到相同的信息，并根据该信息向其它每个议员发送验证信息。基于两个诚实的议员达到的共识，我们能够判断出系统中的不诚实节点到底是发言人还是议员。

不诚实的发言人

图 3: 一个 n = 3 的例子，其中包含一个不诚实的发言人.

在图 3的例子中，由于存在这个不诚实的发言人，我们会得到跟图 1相同的结论，所有的议员都无法判断哪个节点是不诚实的。

图 4: 一个 n = 4 的例子，其中包含一个不诚实的发言人.

在图 4的例子中，区块从中间节点和右节点接收到了该验证不合法的结果，这将会使得它们首先创建一个新的视图来选择一个新的发言人，因为它们占 66% 的比例，属于多数。这个例子中，如果不诚实的发言人向其中两个议员发送了诚实的数据，区块将通过验证而不需更改视图。

5 - 具体实现

NEO 中 DBFT 的具体实现用使用了一种迭代共识的方法来保证达到共识，这个算法的性能取决于诚实节点在系统中的比例。图 5中将预期迭代描述为不诚实节点所占比例的一个函数。

需要注意的是，图 5中共识节点的诚实度并没有低于 66.66%。当共识节点诚实度在 66% 和 33% 之间时，这种情况被称为无法达到共识的“无主之地”（No-Man's Land）。如果共识节点的诚实度低于 33.33%，不诚实节点（假设它们能够取得共识）就能够达到共识并成为系统中新的事实。

图 5： DBFT 算法的 Monto-Carlo 模拟图，描绘了达到共识所需的迭代次数，其中有 100 个节点，100,000 个模拟区块和随机选择的诚实节点。

5.1 - 定义

在本算法中，我们有如下定义：

• t : 区块生成的时间，以秒计。
  • 当前： t ＝ 15 秒
• 这个值可大致近似于单个视图迭代的时间，因为共识行为和通信事件对于该时间常量是非常迅速的。
• n : 活跃的共识节点数目。
• f : 系统中错误共识节点的最小阈值。
  • f = (n-1) / 3
• h : 共识行为中当前区块的高度
• i : 共识节点索引。
• v : 共识节点视图。视图包含了在一次共识回合中节点接受到的所有信息，包括所有议员发起的投票（prepareResponse或者 ChangeView）。
• k : 视图 v 的索引。一次共识行为可能会需要多个共识回合，共识失败时，k 会递增并开始一个新的共识回合。
• p : 被选为发言人的共识节点的索引。该索引的计算机制在共识节点中轮流执行，以防止某个节点在系统中产生独裁行为。
  • p = (h - k) mod (n)
• s : 安全共识阈值。低于这个阈值，网络将会出现错误。

5.2 - 要求

在 NEO 内部，有三个主要的共识容错要求：

1. s 个议员必须在区块被提交之前对某个交易达成共识。
2. 不诚实的共识节点必须不能说服诚实的共识节点接受一个错误的交易。
3. 至少有 s 个具有相同（h, k）状态的议员才能开始一个共识行为

5.3 - 算法

算法流程如下：

1. 一个共识节点在全网范围内广播一个被发送方签名过的交易。

   
   图 6: 一个共识节点接收到了一个交易并向全网进行广播

2. 其它共识节点在内存中记录交易信息。
3. 共识行为的第一个视图 v 被初始化。
4. 确定发言人。

   
   图 7:确定发言人并设置视图

等待 t 秒

1. 发言人广播提案：

   <prepareRequest, h, k, p, bloc, [block]sigp>

   
   图 8:发言人建立一个区块提案并由议员审查

2. 议员收到提案并进行验证：
   • 时间格式是否与系统规则保持一致？
   • 区块链中是否已存在该交易？
   • 合同脚本是否被正确执行？
   • 该交易是否只包单次支付？（也就是说，该交易是否能避免重复支付？）
   • 如果提案通过验证则广播:

     <prepareResponse, h, k, i, [block]sigi>

   • 如果提案未通过验证则广播：

     <ChangeView, h,k,i,k+1>

   
   图 9:议员审查区块链提案并响应

3. 在收到 s 个 'prepareResponse' 广播后，该议员就达成共识并发布一个区块。
4. 该议员对区块进行签名。

   
   图 10:达成共识，批准该交易的议员对区块签名，并将其绑定到区块链上

5. 当一个共识节点接收到整个区块的时候，当前视图的数据将被清除并开始新一轮的共识。

• k = 0

如果在 ( ) 秒之后，没有就该视图达成共识：

• 共识节点会广播：

  <ChangeView, h,k,i,k+1>

• 一旦某个共识节点收到了至少 s 个广播内容表示要改变该视图，它将会递增视图 v 并发起新一轮共识。

6 - 参考文献

1. A Byzantine Fault Tolerance Algorithm for Blockchain
2. Practical Byzantine Fault Tolerance
3. The Byzantine Generals Problem

原文发布时间为：2017年9月28日

本文来自合作伙伴掘金，了解相关信息可以关注掘金网站。