专注区块链信息及金融服务

“雪花”还是“雪崩?#22467;俊狝valanche能否成为下一代主流共识协议?

TLABResearch ·

03月28日

热度: 2377

Avalanche作为一种亚稳态的共识协议,通过多次重复抽样的方式来使节点之间达成共识。Avalanche具有高拓展性、静态绿色以及低通信成本的特点。由于Avalanche协议中引入了可信度,意味着可达成预共识,即有可能实现零确认交易。

00:00
--:--

摘要

分布式?#20302;?#20013;的共识问题一直是计算机科学领域中的重要问题。经典共识协议具?#26143;?#19968;致性、高效的特点,然而却存在通讯成本高,封闭性的问题;因比特币而为人所熟知的中本聪共识协议具有开放性,无权限的特性,却也存在成本高昂、浪费资源且性能有限的局限性。在2018年诞生的Avalanche共识协议则是结合了上述两类协议的优点,借鉴中本聪协议的类似设计,采用概率性的安全保证,使用可调的安全?#38382;?#26469;使共识失败的概率任意小;另外加入了BFT属性,增加?#20302;?#30340;效率和安全性。

Avalanche是一种基于亚稳态机制的分布式拜占庭容错协议,共由Slush,Snowflake,Snowball和Avalanche四个子协议组成:

(1)Slush协议是Avalanche协议系列中最基础的部分,该协议通过多次重复的随机抽样方式来使节点之间达成共识;

(2)尽管Slush协议是稳定的,但有拜占庭节点存在的情况下,该协议并不能提供强大的安全保证。为此,Rocket team在Slush协议的基础上增加了一个计数器(counter)来增加?#20302;?#30340;安全性,该协议即Snowflake协议;

(3)Snowflake协议要求每次颜色的翻转都会重置计数器,为了使?#20302;?#33719;得更高的安全性,在Snowflake协议的基础上引入了一个更加持久的可信度,这就是Snowball协议;

(4)Avalanche是亚稳态协议族的最后一个协议,它在Snowball协议的基础上增加了有向无循环图(DGA)来记录所有的交易状态。

在Avalanche协议的论文发布后,人们还没有发现Avalanche协议与零确认交易之间有什么关系。然而在2018年12月左右,BCH社区的技术人员认为可以使用Avalanche协议来保证零确认交易的安全性。然而,上述方案只是BCH技术人员的初步设想,目前BCH的Avalanche协议仍然在进行开发中,预计2019年底或2020年初进入主网测试阶段。

风险提示:数?#21482;?#24065;具有高风险性,区块链技术处于发展早期尚不成熟,政策监管态度不明。

报告正文

1.引言

在区块链领域,不是每天都会有人出来说“我有一个新的颠覆性突破?#20445;?#21363;便有,也更多地来源于广告营销。从十年前中本聪在比特币白皮书中提出的PoW机制,到五年前以太坊的智能合约,近几年能有上述这些如明星般璀璨的技术突破案例乏善可陈。然而,在2018年出现的Avalanche共识协议可能是其中的例外。

2018年5月, 一个名为“Rocket team”的匿名团队在星际文件?#20302;常↖PFS)上发表了一篇名为《从“雪花”到“雪崩?#20445;?#19968;种新型的亚稳态共识协议族》的论文,该论文立刻引起了人们巨大的关注。Avalanche是一种新型的区块链共识协议,由Rocket team从gossip协议中获得灵感,通过亚稳态机制来保证?#20302;?#30340;安全。相比于目前主流的共识算法,Avalanche具有许多优良特性,有望成为下一代区块链共识算法中的明珠。正如?#30340;味?#22823;学教授埃米·冈·瑟勒(Emin Gun Sirer)所言:“Avalanche描述了一种新的共识协议,它将中本聪共识协议与经典共识协议相结合,这是一次重大的突破。”

2.早期共识协议的发展

分布式?#20302;?#20013;的共识问题一直是计算机科学领域的一个重要问题。目前人们主要有两类共识协议来解决该问题:一类是经典共识协议,另一类是中本聪共识协议。

经典共识协议由图灵奖得主兰伯特提出,具有强一致性、高效的特点,然而它也存在一些缺点,首先是通信成本,在经典共识协议下,节点的个数不能超过1000个,因为?#20302;?#30340;通信成本会随着节点数量的增加?#35782;?#27425;指数?#38382;?#22686;长;其次是要求网络中所有的节点都是可信的,因此节点无法自由进出。

另一类共识协议则是因比特币而被众人所熟知的中本聪共识协议,这类协议无法达到强一致性,但为?#20302;?#25552;供了一个安全的概率保证——在实?#35797;?#34892;中,只要达到一定的?#38382;?#26631;准,共识就是不可逆的。采用该协议的?#20302;?#20855;有开放性,无权限的特性,任何节点都可以随时加入网络,然而也存在成本高昂、浪费资源且性能有限的缺陷。

而Avalanche共识协议则是结合了上述两类协议的优点,借鉴中本聪协议的类似设计,采用概率性的安全保证,使用可调的安全?#38382;?#26469;使共识失败的概率任意小;另外加入了BFT属性,增加?#20302;?#30340;效率和安全性。


3.从“雪花”到“雪崩?#20445;篈valanche协议介绍

3.1.Avalanche基本原理

Avalanche是一种基于亚稳态机制的分布式拜占庭容错协议,可为?#20302;?#25552;供强大的安全保障,?#36865;猓?#20854;并发性的特征可实现高吞吐量和可扩展性。Avalanche一共由Slush、Snowflake、Snowball和Avalanche四个子协议组成:首先是最简单的Slush协议,随后在Slush的基础上,?#31181;?#27425;构建了Snowflake、Snowball 和 Avalanch三个BFT协议。

3.2.Slush 协议

Slush协议是Avalanche协议系列中最基础的部分,Slush协议的灵感来源于Gossip协议(又称八卦协议)。该协议通过多次重复的随机抽样方式来使节点之间达成共识。为了简单地理解该协议的基本原理,这里我们引用Avalanche白皮书里在一个无信任的分布式网络中,节点投票选择蓝色或红色作为最终颜色的例子(因为在共识协议中,无法在两种选择中做出唯一决定是最大的难题)。在Avalanche协议下,节点之间达成共识的步骤如下:

(1)所有的节点在初?#38469;?#37117;是未着色的状态;

(2)当节点从客户端接受到交易信息?#20445;?#26410;着色的节点A将?#32422;?#30340;颜色更新为交易所携带的颜色,并向其他节点发起询问。

(3)如果是未着色节点B收到询?#26159;?#27714;,那么该节点就会染成相同颜色,并对节点A进行相同颜色的回复,同时向另外的其他节点发起询问;如果是已经着色的节点C收到询?#26159;?#27714;,那么节点就对节点A发出?#32422;?#39068;色的回复;如果节点A没有在限定时间内收到 k 个响应,那么节点A就会从剩余节点中继续选择一些节点发出并发出请求,直到?#21344;?#21040; k 个响应;

(4)节点A?#21344;?#21040;K个响应后,就会检查是否存在相同颜色的样本数值/总样本数(x),使αk,这里α是协议的?#38382;?#24182;且α>0.5;如果x<αk,那么节点将会改变颜色;否则不改变颜色;

Slush协议有许多优良的特性:

(1)状态简单:在该协议下节点可以是无内存的。节点在每轮查询之间除了保留当前颜色之外不保留任何状态,特别是不保留与其他节点交互的历史记录;

(2)小样本:Slush协议与传统共识协议有显著的不同,传统共识协议要求对每个参与者进行查询,而Slush协议只是在每一?#31181;?#38543;机抽取网络中一个小的且大小固定的部分;

(3)重复抽样:Slush要求进行m?#31181;?#22797;抽样。此?#20445;?#21363;使网络一开?#21363;?#20110;50/50红蓝分割的亚稳态,采样过程中的随机扰动?#19981;?#23548;致一种颜色获得微弱的优势,之后的重复采样将建立并放大这种优势;

(4)通信成本低:每个节点每轮都有一个恒定的、可预测的通信成本,并且该成本随n?#35782;?#25968;型增长。


3.3.Snowflake协议

尽管Slush协议有许多优良的特性,但是当Slush协议部署在具有拜占庭节点的网络中?#20445;?#25915;击者可能会干扰决策。特别是如果诚实节点偏爱一种颜色,那么攻击者可以尝试将节点翻转到相反的颜色,以保持网络的平衡。Slush协议本身是稳定的,但有拜占庭节点存在的情况下,它本身并不能提供强大的安全保证。为此,Rocket team在Slush协议的基础上增加了一个计数器(counter)来增加?#20302;?#30340;安全性,该协议即Snowflake协议。

具体而言,在Snowflake协议里,计数器可以记录有多少个连续的样本都产生了同一个颜色(当节点A询问得到的响应结果为x≥αk,那么节点A的计数值cnt加1;每当节点A的颜色发生改变,节点A就会把cnt值重置为 0)。 如果一个节点的计数值cnt超过了某个阈值 β,它就会接受当前的颜色。这里的 β 是?#20302;?#30340;另外一个安全?#38382;?/p>

当该协议为拜占庭节点阈值?#36864;?#38656;的保证数设定?#38382;?#21518;,就可确保?#20302;?#30340;安全性(即没有诚实节点会接受发生冲突的交易)和活跃度(任何一笔由诚实节点发出的交易都会被其他节点接受)。

3.4.Snowball协议

在历史上,以太坊前?#26114;?#21518;共经过七次硬分叉,其中与本次“君?#21051;?#19969;堡?#23849;?#20284;的还有“?#20197;啊?#38454;段和“拜占庭”阶段的硬分叉,而其他的硬分或是是为了突发?#24405;?#25110;是在宣传和规模上较小,与本次硬分叉没有可比性。以太坊每次因技术升级带来的硬分叉都会给ETH带来巨大的?#26143;?#27874;动。基于这一现象,我们选取上述两次历史上的硬分叉进行分析。

Snowflake协议的状态是短暂的:每次颜色的翻转都会重置计数器。尽管从理论上将该协议能以最小的状态代价保证?#20302;?#30340;安全性,但是为了使?#20302;?#30340;安全性更高,Rocket team在Snowflake协议的基础上引入了一个更加持久的可信度,这就是Snowball协议。

具体而言,Snowflake协议和Snowball协议的区别如下:

(1)每成功查询一次,节点就为该颜色的信任度计数?#23548;?;

(2)在当前颜色的信任度计数值低于新颜色的信任度计数值?#20445;?#33410;点将切换颜色。

?#38142;耍琒nowball协议不仅比Snowflake更?#35328;?#21463;攻击,而且更容易推广到多命令协议。


3.5. Avalanche协议

Avalanche是亚稳态协议族的最后一个协议,它在Snowball协议的基础上增加了有向无循环图(DGA)来记录所有的交易状态。DGA只有一个点,即?#35789;?#28857;。引入DAG主要有两个?#20040;Γ?/p>

(1)高效性,给 DAG 中的某个节点投?#26412;?#24847;味着给从?#35789;?#28857;到该节点的路径上的所有节点都投?#20445;?#36825;提高了协议的效率;

(2)安全性,因为DAG里包含着交易信息,类似于区块链的链式结构特征。这使得在没有诚实节点的批准下,很难撤销过去的决策。

维护DAG的核心挑战是在冲突交易中进行选择,在加密货币的应用中,花费相同?#24335;?#30340;交易(双重支付)即冲突,这些冲突的交易形成一个冲突集,诚实节点只能接受冲突集中的一?#24335;?#26131;。需要注意的是,包含有效交易的冲突集总是一个单元素集合。

Avalanche协议实际上是一个体现了所有冲突集的Snowball协议。然而Snowball协议使用重复查询和多个计数器来获取在冲突交易中的信任值,而Avalanche协议则是利用DAG结?#20849;?#20351;用交易的子代来达到?#22235;?#30340;。具体流程如下所示:

(1)当节点A收到一个新交易 T?#20445;?#23427;?#22836;?#36215;一个的查询流程(随机抽样 k 个节点),启动查询的节点会把 T 加入?#32422;?#24050;知的交易集合;

(2)收到消息的其他节点会查询?#32422;?#30340;DAG交易集,看看是否存在T交易的父交易,如果存在,那么交易T就可以看成是非常可信的,即确认该交易;否则,只要T交易的任何一个祖先交易不满足条件,那么该?#24335;?#26131;就会被确认为非法;

(3)当节点A收到k个响应后,就会检查是否存在至少αk 个确认该?#24335;?#26131;的信息,如果是,那么T就会?#21344;?#21040;一个Chit值,记为CuT=1,否则CuT=0。;

(4)上述的过程会为 DAG 中的每个交易标记上 Chit 值以及它关联的可信度值的大小。需要注意的是,Chit是在一次抽样中产生的,是不可变的值,取值只能为0或1,而它的可信度值是可以累加的,该值会随着DAG的扩展而增加;

图7是一个交易被打上chit值和可信度值的 DAG 图,图中每个交易的查询结果用 来表示,颜色更深的方块表示 可信度更高。?#28909;紓琓2 的可信度是 5,它比 T3的可信度要高。这也就意味着,T2 的后代比 T3 的后代更容易?#21344;?#21040; Chit。


3.6. Avalanche协议的特性

从实?#26159;?#20917;看,在“?#20197;啊?#30828;分叉阶段,由于2015年下半年以太坊Frontier版本的发布,让人们看到了以太坊的技术实力和智能合约的潜力,为此市场对即将到来的“?#20197;啊?#29256;本普遍持乐观态度,因此以太坊在分叉前的几个月处于上涨通道,此过程中必然有泡沫的累积,在硬分叉结束后市场的乐观预期也随之结束,因此硬分叉后ETH价格的下跌成为必然。

在上文中我们介绍了Avalanche协议的基本原理,现在我们来具体分析Avalanche协议有什么优良特性。

(1)高效的可扩展性:因为协议是轻量级的,所以可以提供扩展性和低延迟;

(2)高拜占庭容错:即使网络中有超过50%的节点是拜占庭节点,网络依然是安全的;

(3)静态绿色:在Avalanche协议下,网络运行时可?#20013;?#30340;,与PoW机制不同,Avalanche协议不会浪费任何资源;

(4)低通信成本:传统共识协议的通信复杂度为O(n^2),而Avalanche协议的在O(kn logn)到 O(kn logn)之间。


4. 零确认交易与Avalanche协议

在Avalanche协议的论文发布后,人们还没有发现Avalanche协议与零确认交易之间有什么关系。然而在2018年12月左右,BCH社区的技术人员Chris Pacia发表一篇文章,认为可以使用Avalanche协议来保证零确认交易的安全性,?#38142;?#24341;起了市场的广泛兴趣。

在前文中我们提到,Avalanche协议要求经过m?#31181;?#22797;抽样后来达成共识,为了限制确认的时间,重复抽样的?#38382;?#24517;须受到限制,而这意味着,当网络中恶意节点的数量尝过一定比例后,在受限制的重复抽样轮次里,诚实节点之间无法达成共识。为此,Chris Pacia认为可以引入PoW机制作为反sybil机制来保护网络的安全,阻止黑客激活的攻击节点数量超过阈值。

具体而言,如果在网络上没有双重支付,那么矿工接收交易到他们的内存池中,选择要放入区块的交易,并将打包好的区块广播到网络。此?#20445;?#30719;工之间甚至没有发送avalanche消息。当双重支付进入矿工的内存池?#20445;?#23427;会触发avalanche过程。矿工开始向相互发送avalanche查询并执行n轮。最终,所有矿工都会决定交易A是有效的,B是无效的,或者A是无效的,B是有效的。

上述方案只是BCH技术人员的初步设想。目前,BCHAvalanche协议仍然在进行开发中,预计2019年底或2020年初进入主网测试阶段。


5. 结论

Avalanche作为一种亚稳态的共识协议,通过多次重复抽样的方式来使节点之间达成共识。为此,相较于经典共识协议和中本聪共识协议,Avalanche具有高拓展性、静态绿色以及低通信成本的特点。同?#20445;?#30001;于Avalanche协议中引入了可信度,而可信度会随着DGA的扩展而累加,这意味着可达成预共识,即采用Avalanche有可能实现零确认交易。目前BCH团队已经展开了相关技术的研发测试,一旦实现零确认交易,这将是对BCH的重大利好。


声明:本文为入驻“火星号”作者作品,不代表火星财经官方立场。转载请注明出处、作者和本文链接
提示?#21644;?#36164;有风险,入?#34892;?#35880;慎。本资讯不作为投资理财建议。
关键字: 共识 Avalanche 技术

推广
相关新闻

涨幅榜

你可能?#34892;?#36259;的内容
下一篇

路易威登所有者LVMH正在推出区块链来追踪奢侈品

新疆18选7开奖结果