0_1554964111811_0.jpg

NEXT社区|小课堂

由于近期NEXT社区加入很多新的小伙伴,有在校大学生,有对区块链感兴趣的传统企业从业者。为了更方便、更系统的让NEXT社区的伙伴们了解NEO的技术知识,因此我们开设了小课堂,每周3节,向大家普及NEO相关的知识要点!

NEXT社区小课堂 | 第一课

NEO共识机制图解


一、术语说明

权益证明 PoS :一种利用网络协商一致来处理容错的算法。

工作量证明 PoW :一种利用计算能力来处理容错的算法。

拜占庭错误 BF: 一个节点保持功能,但以不诚实甚至是恶意的方式来工作。

dBFT(一种改进的拜占庭容错算法) dBFT :NEO 区块链中的共识算法,该算法通过多个共识节点的协商来达成共识,有良好的可用性和最终性。

视图 V :在 dBFT 算法中,一次共识从开始到结束所使用的数据集合,称为视图。

二、规则

在 NEO 的共识算法中,共识节点由 NEO 持有人投票选出,并对区块链中交易的有效性进行验证。过去这些节点被称作“记账人”,现在他们被称作”共识节点”。

共识节点:此节点参与共识行为。 在共识行为中, 共识节点轮流担任以下两个角色:

议长 (一人) :议长 负责向系统发送一个新的区块的提案。

议员 (多人) :议员 负责对议长的提案进行投票,大于等于2/3的议员投票时,提案通过。

三、介绍

众多区块链共识算法的根本区别是他们如何保障对系统中的故障节点、恶意节点的容错能力。传统的 PoW 方法可以提供这种容错能力,只要网络的大多数算力是诚实的。

然而,由于这种模式依赖于大量的计算,这种机制可能会非常低效且不环保(算力消耗能源,需要硬件)。 这些依赖就是 PoW 方法的限制所在,最主要的就是扩展的成本。

NEO实现了一种委托的拜占庭容错共识算法,它借鉴了一些 PoS 的特点(NEO持有人需要对共识节点进行投票) 利用最小的资源来保障网络免受拜占庭故障的影响,同时也弥补了 PoS 的一些问题。

该解决方案则解决了与当前块链实现相关的性能和可扩展性问题,而不会对容错产生重大影响。

四、理论

拜占庭位于如今的土耳其的伊斯坦布尔,是东罗马帝国的首都。由于当时拜占庭罗马帝国国土辽阔,为了防御目的,因此每个军队都分隔很远,将军与将军之间只能靠信差传消息。 在战争的时候,拜占庭军队内所有将军和副官必需达成一致的共识,决定是否有赢的机会才去攻打敌人的阵营。

但是,在军队内有可能存有叛徒和敌军的间谍,左右将军们的决定又扰乱整体军队的秩序。在进行共识时,结果并不代表大多数人的意见。这时候,在已知有成员谋反的情况下,其余忠诚的将军在不受叛徒的影响下如何达成一致的协议,拜占庭问题就此形成。

为了描述 DBFT 的工作原理,我们将本节重点放在第 5 部分中的证明 66.66% 的共识率的正确性。请记住,不诚实的节点不需要主动恶意,因为它根本不可能是按预期运作。

为了讨论,我们将描述一些情景。 在这些简单的例子中,我们假设每个节点沿着从 议长 发送过来的消息发送。 此技工也用于DBFT,对系统至关重要。 我们将仅描述功能系统与功能失效系统之间的区别。 有关更详细的说明,请参阅参考资料。

五、诚实的议长

0_1554973586168_1.jpg

图 1: 一个 n = 3 的例子中存在一个不诚实的 议员。

在图 1 中,我们有一个诚实的 议员 (50%)。两个 议员 从 议长 那里收到相同的消息,然而,由于其中一个 议员不是诚实的,诚实的议员只能确定有不诚实的节点,但无法识别它是 议长 还是 议员。因此 议员 必须弃票,改变视图。

0_1554973597888_2.jpg

图 2: 一个 n =4 的例子中存在一个不诚实的 议员。

在图 2 中,我们有两个诚实的 议员 (66%)。所有的 议员 从 议长 那里收到相同的消息,然后向其它 议员 发送消息和自己的验证结果。根据两位诚实 议员 的共识,我们可以确定 议长 或者右边的 议员 在系统中是不诚实的。

六、不诚实的议长

0_1554973684975_3.jpg

图 3: 一个 n = 3 的例子中存在一个不诚实的 议长。

在图 3 中,不诚实的是 议长,这和图 1 中描述的案例有同样的结论。议员 无法确定哪个节点是不诚实的。

0_1554973664623_4.jpg
图 4: 一个 n = 4 的例子中存在一个不诚实的 议长。

在图 4 所示的例子中,中间的节点和右边的节点接收的区块不可验证, 由于他们占到多数(66%),导致更换视图选举新议长。

在这个例子中,如果诚实的议长向三名议员中的两名发送了诚实的数据,那么它将被验证而不需要改变视图。

七、实际实施

DBFT 在 NEO 中的实际实现使用迭代共识方法来保证达成共识。算法的性能取决于系统中诚实节点的分数。图5描绘了作为不诚实节点的函数的期望迭代。

请注意,图5没有低于66.66%的共识节点诚信。在这个临界点和33.33%的共识节点诚信之间,有一个无人地带,那里无法达成共识。低于33.33%的共识节点诚信,不诚实的节点(假设它们达成共识)能够自己达成共识,并成为系统中新的真理点。

0_1554973658570_5.jpg

图5: DBFT算法 Monto-Carlo 模拟,描绘了达成共识所需的迭代。
{100 个节点;100,000 个模拟区块随机选择诚实节点}

八、定义

在算法中有如下定义:

  • t:分配给区块生成的时间总量,以秒为单位。
    当前时间: t = 15 秒
    这个值可以用来粗略估计单个视图迭代的持续时间,因为共识活动和通信事件相对于这个时间常数是快速的。
  • n: 有效的共识节点数量。
  • f:系统中故障共识节点的最小阈值。
    f = (n - 1) / 3
  • h : 在共识活动期间的当前块高度。
  • i : 共识节点索引。
  • v : 共识节点视图。该视图包含节点在一轮共识中收到的汇总信息。 这包括所有议员发起的投票(prepareResponse 或 ChangeView)。
  • k : 视图 v 的索引。共识活动可能需要多轮。在共识失败时,k值增加,新一轮的共识开始。
  • p : 选为议长的共识节点索引。这个索引的计算机制在共识节点间轮流,以防止单个节点成为系统内的指令器。
    p = (h - k) mod (n)
  • s: 安全共识的阈值。 低于这个阈值,表示网络故障。
    s = ((n - 1) - f)

九、要求

  • 在NEO中,共识容错有三项主要要求:
    · s 议员必须就一项交易达成共识,然后区块才可以实施。
    · 不诚实的共识节点不能说服故障交易的诚实共识节点。
    · 至少s Congressmen 处于同一状态 (h,k) ,开始达成共识。

十、算法

  • 该算法工作原理如下:
  1. 共识节点使用发送者的签名向全网广播一个交易。

0_1554973642040_6.jpg

图 6:一个 共识节点 收到交易并在系统中广播

  1. 共识节点将交易数据记录到本地存储器中。
  2. 共识活动的第一个视图 v 被初始化。
  3. 议长确定。

0_1554973637189_7.jpg

图 7: 议长 确定且设置好视图

等待 t 秒。

  1. 议长广播提案 <prepareRequest, h, k, p, bloc, [block]sigp>

0_1554973628144_8.jpg

图 8:议长 提出区块提案,由众议员审阅。

  1. 议员收到提案并验证:
  • 数据格式与系统规则是否一致?
  • 交易是否已经在链上?
  • 合同脚本是否正确执行?——交易是否只包含一笔开支(即交易是否避免了双重开支的情况?)
  • 如果是有效的提案广播: <prepareResponse, h, k, i, [block]sigi>如果是无效的提案 广播: <ChangeView, h,k,i,k+1> ‘

0_1554973618454_9.jpg

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

  1. 在收到 s 数量的 ‘prepareResponse’ 广播后,众议员达成共识并发布一个区块。
  2. 议员签名该区块。

0_1554973607306_10.jpg

图 10: 达成共识,获批议员签名区块,并将其绑定到链上。

  1. 当一个共识节点收到一个完整区块时,当前的视图数据被清除,并开始新一轮的共识。

k = 0
NOTE

如果 ( ) 秒后在同一视图没有达成共识:共识节点进行广播:<ChangeView, h,k,i,k+1>;一旦共识节点接收到至少 s 个表示相同视图改变的广播,就会增加视图 v, 并引发新一轮的共识。

十一、引用

  • A Byzantine Fault Tolerance Algorithm for Blockchain
  • Practical Byzantine Fault Tolerance
  • The Byzantine Generals Problem

本文来源:NEOFANS
原文链接:
http://docs.neo.org/zh-cn/basic/consensus/consensus.html


联系我们

微博:https://weibo.com/u/6724929880

官网: https://neonext.club/

QQ群:612334080

电报:https://t.me/neonextop

twitter:https://twitter.com/NE0NEXT

扫码关注NEO NEXT官方公众号

获取更多一手社区资讯


0_1554973898578_11.jpg