授权自适应拜占庭容错分布式共识算法

来自:jinse.com 归档时间:2018-08-06

授权自适应拜占庭容错(Delegated Adaptive Byzantine Fault Tolerance – DABFT)

虽然授权经济价值证明激励共识(DPoEV)算法提供应用层激励共识,但它需要使用一个高性能的基础层分布式共识协议,该协议提供区块链服务。这个底层共识是 “真正的” 区块链推动者。

因此,不同于大多数现有的公共链, 凌云链区块云建立双重共识做法:在应用程序层,DPoEV共识负责经济政策的实施,同时在基本层,授权适应性拜占庭容错分布式一致算法(DABFT)负责管理每一事务块生成,验证和分类帐记录。虽然DPoEV不需要实时性,因为大多数应用场景不需要实时的报酬分配,但DABFT必须是实时的,因为块验证和分类账记录需要快速而有力地完成。DABFT的目标是达到数十万到上百万TPS(每秒交易笔数)。

 

DABFT设计目标

DABFT在基本层上体现了上层的DPoEV经济政策,并提供了块生成、验证和分类记录的区块链服务。它着重于凌云链区块云的效率、公平和合法性目标。不像主流的共识算法(如PoW)为了获得分布账本记帐权而浪费大量的能量,DABFT只将资源用于有意义的、能产生经济价值的行为。

 

主流共识算法和DABFT

由于现有的所有区块链协商一致算法都不能充分满足凌云链区块云的目标并符合DPoEV经济模型,所以提出了DABFT。

 

PoW(Proof of Work)工作量证明共识

比特币背后的PoW共识体现的是SHA256哈希(SHA256 hash)零和游戏,矿工们借此获得分布账本记帐权。随着区块挖掘难度的增加,PoW浪费了大量的计算能力(电力),大大降低了吞吐量。更糟糕的是,矿工的数量越多,挖掘难度就越高,矿工获得分布账本记帐权的概率也越低,这就导致了更高程度的能源浪费和更长的延迟。这就是为什么Ethereum希望采用PoS算法而不是PoW的关键原因。因此,从开采速度和开采成本的角度来看,PoW不利于区块链为基础的生态体系的长期快速发展,不符合凌云链区块云的效率(高性能)目标和DPoEV的 “公平规则” 要求。

 

PoS (Proof of Stake) 股权证明共识和DPoS

PoS共识衡量的是生态体系中财富的数量和年龄,以授予分类帐记录特权(Buterin,2013)。PeerCoin (King and Nadal,2012),NXT (NXT,2015),以及Ethereum Casper(Buterin,2014), 均采用PoS。尽管PoS消耗较低水平的能源,可是它放大财富积累的影响。因此,在PoS生态体系中,更多财富的所有者很容易垄断分布帐本记录。此外,区块确认是概率的,而不是确定性的,因此在理论上,PoS生态体系可能会受到攻击。所以,从矿工构成的角度来看,PoS不利于生态体系参与者的利益,不符合凌云链区块云的公平目标和DPoEV的确定性要求,也不符合 “财富规则” 和 “公平规则”。

DPoS源自PoS, 目前阶段EOS正在使用它(EOS, 2018)。主要的不同之处在于,在DPoS机制中,所有的资产持有者都选择了一些代表,并将协商,构建共识的任务授权给他们。DPoS的法规遵从性、性能、资源消耗和容错与PoS相似,DPoS的关键优势是显著减少了块验证和分类记录的节点数量,能够在数秒内达成一致。

 

PoI(Proof of Importance)重要性证明共识

PoI引入了账户重要性的概念,它被用作分配分布账本记帐权的度量(NEM,2018)。PoI在一定程度上解决了PoS的财富垄断困境,但也暴露了一种无利害关系的情况,这使得欺骗的成本相当低。因此,PoI偏离了凌云链区块云合法性目标和DPoEV “关联规则” 的要求。

 

PoD(Proof of Devotion)贡献证明共识

PoD引入了基于账户贡献的贡献和奖励分布账本记帐权的概念(NAS,2018)。然而,PoD使用毫无意义的伪随机数来确定参与者之间的分类记录特权,这与只将资源用于有意义和有成效的工作的概念不一致。此外,由于设计的局限性,PoD无法达到凌云链区块云要求的效率水平。

 

PoA(Proof of Authority)身份证明共识

PoA类似于PoS(VET,2018)。然而,与POS不同的是,PoA节点不需要持有资产来竞争分类帐记录器特权,而是需要知晓身份并验证身份。这意味着节点没有动机按照自己的兴趣行事。PoA比PoS更便宜、更安全,并提供更高的TPS。

 

BFT (拜占庭式容错) 分布一致性共识和DBFT

BFT提供 

授权自适应拜占庭容错分布式共识算法

容错。拜占庭问题的可能解决办法是在

授权自适应拜占庭容错分布式共识算法

 情况下实现一致性,其中N为校验数,F为错误校验数。在验证节点之间交换信息之后,每个验证节点都获得一个信息列表,并且在三分之二的验证节点中存在信息。BFT的优势在于,可以在安全与稳定的前提下达成共识(Lamport,Shostak and Pease,1982;Driscoll et al.,2003)。

BFT的高性能变种PBFT(实用BFT)可以实现2 - 5秒的延迟,满足许多商业应用的实时处理需求(Castro and Liskov,2002)。PBFT的高共识效率使其能够满足高频交易的需要。

BFT的缺点是,当三分之一或更多的验证节点停止工作时,系统将无法提供服务;当三分之一或更多的验证节点表现出恶意行为,并且所有的节点被偶然地分割成两个孤岛时,恶意的验证节点可以将系统分离开来,但是它们会留下密码证据。BFT的分权级别没有其他共识高,因此更适合多中心应用程序场景。

DBFT将根据验证节点在生态体系中的地位来选择它们,然后通过BFT算法(NEO, 2018)对验证节点的选择达成一致。DBFT与BFT的关系类似于DPoS与PoS的关系。DBFT比BFT有很多改进。它将BFT的客户端/服务端体系结构改进为适合P2P网络的对等节点模式。它从静态一致发展为动态一致,验证节点可以动态地进入和退出。它对账本记录结合了基于验证者的股份的投票机制。它还提出了数字证书的使用,因此解决了验证节点身份验证的问题。

DBFT有许多可取的特性,如专门的簿记员、任何类型的错误的容忍度,以及没有分叉。就像BFT一样,当三分之一或更多的验证节点表现出恶意行为,并且所有的节点被偶然地分割成两个孤岛时,恶意验证节点可以对系统进行分叉,但是它们会留下密码证据。

 

DABFT – 一种自适应方法

因此,鉴于现有共识算法的优点和缺点,我们得出结论:尽管其中一些算法提供了有用的功能,它们中没有一个能够完全满足凌云链区块云的效率、公平性和合法性的目标。

因此,我们提出了DABFT,它结合了现有协商一致算法的一些最佳特性。从概念上说,DABFT采用了一定的PoS特征来加强PoI的合法性,采用一定的PoI特征来提高PoS的公平性,同时利用BFT算法改进PoD的选择机制。

此外,DABFT通过加入自适应性特性得到了进一步的加强。DABFT是一种具有更高效率的授权机制,本质上是一种更灵活的DBFT,它能够选择最适合动态(和并行)任务的BFT。这种适应性是通过深度学习技术实现的,对新任务的实时一致性算法的选择是根据以往任务的训练模型推导出来的。

因此,DABFT是构建高效、合法、公平的凌云链区块云生态体系的完美工具,它只进行有意义的、生产性的活动。

 

DABFT算法的设计

新区块提出

在新任务发布时,将选择与任务最相关的超节点子集作为代表(任务验证节点),然后由它们各自选择一个负责管理任务的任务处理节点。然后,任务处理几点选择与任务最相关的资源节点,并将任务分发给它们。在新任务成功发布后,任务处理节点将提出一个新的区块,然后由任务验证节点对其进行验证。一个新的区块由此诞生。

由于 “相关性规则”,每个新任务很可能被分配一组完全不同的任务验证节点和任务处理节点。但是,一旦选择了任务处理节点和验证节点,它们将负责从开始到完成(从根块到侧链的最后一个块)的所有管理任务。因此,不需要定期在全系统重新选举代表。这种安排的主要好处是不需要朝代管理,减少了系统的复杂性,提高了系统的效率。

基于 “相关性规则” 的任务验证节点和处理程序的实时选择意味着DABFT有一个内置的 “动态分片” 特性,这将在后面的小节中解释。

 

建立共识的过程

在任务处理节点提出一个新的块之后,任务验证程序将参与一轮BFT投票,以确定块的合法性。

目前,没有一种主流的BFT算法对所有任务都是最优的。DABFT通过基于人工智能的深度学习,采用一套有效性评估算法,确定了当前任务的最优BFT模式。 DABFT可供选择的算法包括PBFT(Practical BFT)、Q/U(Abd-El-Malek,2005)、HQ(Cowling,2006)、Zyzzyva(Kotla et al .,2009)、Quorum(Guerraoui,2009)、Chain(Guerraoui,2009)、Ring(Guerraoui,2011)和RBFT(Redundant BFT)(Aublin, Mokhtar,and Quema, 2013)等。

DABFT在ADAPT(Bahsoun,Guerraoui,and Shoker,2015)的基础上进行了改进,而在几个方面与之相似。与ADAPT一样,DABFT是模块化设计,由三个重要模块组成:BFT系统(BFTS)、事件系统(ES)和质量控制系统(QCS)。BFTS本质上是一个将上述BFT算法模块化的算法引擎。ES收集对系统性能和安全性有重大影响的因素,如终端数量、请求、大小等,并将任务信息发送给QCS。QCS通过静态(Shoker and Bahsoun,2013)、动态或启发式模式来驱动系统,并对一组关键性能指标(KPI)和关键特征指标(KCI)进行评估,从而为当前任务选择最佳的BFT。

ADAPT算法设计中有一个主要缺点。ADAPT采用支持向量回归(Support Vector Regression,SVR)方法(Smola and Scholkopf,2004)进行了五次交叉验证,以预测矩阵中元素的KPI参数

授权自适应拜占庭容错分布式共识算法

。数据集中有6个字段:客户机数量、请求大小、响应大小、吞吐量、延迟和容量。虽然该方法在多种的容错设置中非常有用,但它并不是为高度复杂的区块链应用程序场景设计的,在这些场景中,参与者之间有很多交互及关联,而它对这些场景不是特别有效。例如,在凌云链区块云中,任何时候都有多个任务(由不同的处理程序处理)争夺资源。因此,不断增加的任务数量和它们之间的交互将持续地影响单个任务(时间序列)的关键KPI参数(吞吐量、延迟和容量),以实现系统级的最佳性能。因此,有必要引入一种机制,它包含跨任务的时变条件关联,以便动态调整KPI参数。使DABFT与ADAPT不同的是,DABFT内置了这样的功能。

此后,DABFT与ADAPT类似,根据公式(1a)和(1b)选择评价得分最高的BFT协议。对于任何BFT选择,DABFT提供了容错功能 。 对于由N个任务验证节点组成的一致集合。这种容错包括安全性和可用性,在任何网络环境中都能抵抗一般和拜占庭式的故障。DABFT提供了确定性。因此确认即是最终确认,链不能被分叉,事务不能被撤销或回滚。

在DABFT协商一致机制下,估计每0.1到0.5秒生成一个块。该系统具有30000 TPS的可持续性事务吞吐量,经过适当的优化,有可能达到1,000,000 TPS,使凌云链区块云生态体系能够支持高频大规模的商业应用。

DABFT有一个选项,可以将数字识别技术整合到凌云链区块云中,使其成为基于真实姓名的,从而使冻结、撤销、继承、检索和检索成为可能。因此支持在司法判决下资产转移。这一特性使得发行符合法规要求的金融产品成为可能。

 

分叉选择

DABFT为每个任务建立权威链,并在每个块的高度上设置区块分数。在公平、合法的原则下,选择经济价值最高的分块链加入权威链。每个分叉链的经济价值是其头分叉块及其后代的经济价值之和。这是可以实现的,因为所有任务都由它们相应的侧链跟踪,将达到最终结果。

 

投票规则

为了抵御对协商一致过程的恶意攻击,DABFT借鉴了Casper的最小惩罚机制的概念来约束任务验证者的行为。投票程序遵循以下基本规则:

1.     单个区块的一致过程有严格的顺序。只有在第一阶段的投票总数达到2/3多数后,才能开始下一阶段的协商一致。

2.     后续区块的协商一致不需要等到当前区块的协商一致意见结束。多个块的协商一致可以并发,但是不能完全打乱顺序。一般来说,在当前块的协商一致完成2/3之后,后续块的一致性就可以开始了。

激励分析

任务验证节点(包括任务处理节点)根据DPoEV激励共识机制协商一致意见,以CFTX令牌的形式接收任务的奖励。授予任务验证节点的令牌总数是分配给任务的令牌总数的一个百分比,并由所有参与的任务验证节点和处理节点共享。授予任务处理节点和每个任务验证节点的令牌数量取决于它对完成任务的贡献。这些数字由DPoEV动态决定,特别是它的EVG引擎。

 

作弊分析

分布式协商一致中有几种值得特别关注的攻击,其中分析最多的攻击有三种,分别是双重支付攻击、短程攻击和51%攻击。在具有DPoEV-DABFT的双共识的凌云链区块云生态体系中,我们的设计使得没有一种攻击有机会成功。

当恶意节点试图通过两个任务向两个不同的目的地发起相同的令牌交易时,就会发生双重支付攻击。在授权的验证机制(例如DPoS或DBFT)中,要使这样的攻击成功,恶意节点必须首先通过选举(并提供存款)成为验证节点,然后贿赂至少三分之一的其他验证节点,以使两个交易都达到最终状态。在DPoEV-DABFT的双共识的凌云链区块云生态体系中,不可能成功地实现双重支出。原因是验证节点(超级节点)是根据它们与任务的相关性而不是它们的存款来选择的,验证节点不允许启动任务,且验证节点是根据它们的贡献级别而不是其他校验节点来奖励的。因此,出现双重支付攻击的条件并不存在。

当H+1区块未过期时,恶意节点伪造链(A链)替换合法链(B链),从而发起短程攻击。在一个授权的机制中,为了使这个攻击成功,攻击者需要贿赂验证者,以使区块A1得分高于区块B1。因此,从本质上讲,短程攻击非常类似于在 A1/B1区块级别的双充支付攻击,由于同样的原因,这种攻击没有成功的机会。

在PoW中,51%的攻击需要一个恶意节点在系统中拥有51%的计算能力,在PoS 中,恶意节点在系统中拥有51%的存款,在POD中,恶意节点在系统中拥有认证账户的51%。在DPoEV-DABFT的双共识凌云链区块云生态体系中,在经济模型的约束下,任何节点都不可能拥有超过51%的经济价值。更重要的是,由于验证节点本身不允许启动任务,一个带有恶意的验证节点必须贿赂其它验证节点发起这样的攻击。然而,验证节点的奖励是基于他们的贡献水平,而不是其他验证节点。因此,发生51%攻击的条件也不存在。

有关于授权自适应拜占庭容错分布式共识算法

凌云链创新发布授权自适应拜占庭容错共识机制

授权自适应拜占庭容错(Delegated Adaptive Byzantine Fault Tolerance – DABFT) 虽然授权经济价值证明激励共识(DPoEV)算法提供应用层激励共识,但它需要使用一个高性能的基础层分布式共识协议,该协议提供区块链服务。这个底层共识是 “真正的” 区块链

Vitalik的“99%容错共识算法”解析

Vitalik近期在其博客上发布了一篇名为《一个99%容错共识的指南》让许多人以为诞生了一个“黑科技”般的新共识算法。然而正如Vitalik自己所说,这一共识算法仍是经典拜占庭将军问题的算法。通过解析,我们可以看到共识算法的研究与创新仍需要遵循CAP等已经被证明过的理论;在此基础上把各类经典分布式算

V神的“99%容错共识算法”解析

本文章由火币区块链研究院出品,作者:袁煜明,胡智威 Vitalik近期在其博客上发布了一篇名为《一个99%容错共识的指南》让许多人以为诞生了一个“黑科技”般的新共识算法。然而正如Vitalik自己所说,这一共识算法仍是经典拜占庭将军问题的算法。通过解析,我们可以看到共识算法的研究与创新仍需要遵循C

科普 | 分布式共识的工作原理,Part-1:分布式系统的定义及属性

分布式系统经常让人觉得云山雾罩,主要是因为相关知识点比较零散不成体系。但别担心,我很清楚这个有点尴尬的情况。我自学分布式计算的时候,就有很多次完全摸不着头脑。现在,经历过很多次尝试和死磕之后,我终于有信心可以跟大家分享一下有关分布式系统的基础知识了。 我还想讨论一下区块链技术给分布式相关的学术界和

【火线视点10】V神的“99%容错共识算法”解析 HuobiNews 刚刚

本文章由火币区块链研究院出品,作者:袁煜明,胡智威Vitalik近期在其博客上发布了一篇名为《一个99%容错共识的指南》让许多人以为诞生了一个“黑科技”般的新共识算法。然而正如Vitalik自己所说,这一共识算法仍是经典拜占庭将军问题的算法。通过解析,我们可以看到共识算法的研究与创新仍需要遵循CAP