“雪花”还是“雪崩“？——Avalanche能否成为下一代主流共识协议？
浪花财经摘要
分布式系统中的共识问题一直是计算机科学领域中的重要问题。经典共识协议具有强一致性、高效的特点，然而却存在通讯成本高，封闭性的问题；因比特币而为人所熟知的中本聪共识协议具有开放性，无权限的特性，却也存在成本高昂、浪费资源且性能有限的局限性。在2018年诞生的Avalanche共识协议则是结合了上述两类协议的优点，借鉴中本聪协议的类似设计，采用概率性的安全保证，使用可调的安全参数来使共识失败的概率任意小；另外加入了BFT属性，增加系统的效率和安全性。
Avalanche是一种基于亚稳态机制的分布式拜占庭容错协议，共由Slush，Snowflake，Snowball和Avalanche四个子协议组成：
（1）Slush协议是Avalanche协议系列中最基础的部分，该协议通过多次重复的随机抽样方式来使节点之间达成共识；
（2）尽管Slush协议是稳定的，但有拜占庭节点存在的情况下，该协议并不能提供强大的安全保证。为此，Rocket team在Slush协议的基础上增加了一个计数器（counter）来增加系统的安全性，该协议即Snowflake协议；
（3）Snowflake协议要求每次颜色的翻转都会重置计数器，为了使系统获得更高的安全性，在Snowflake协议的基础上引入了一个更加持久的可信度，这就是Snowball协议；
（4）Avalanche是亚稳态协议族的最后一个协议，它在Snowball协议的基础上增加了有向无循环图（DGA）来记录所有的交易状态。
在Avalanche协议的论文发布后，人们还没有发现Avalanche协议与零确认交易之间有什么关系。然而在2018年12月左右，BCH社区的技术人员认为可以使用Avalanche协议来保证零确认交易的安全性。然而，上述方案只是BCH技术人员的初步设想，目前BCH的Avalanche协议仍然在进行开发中，预计2019年底或2020年初进入主网测试阶段。
风险提示：数字货币具有高风险性，区块链技术处于发展早期尚不成熟，政策监管态度不明。
报告正文
1.引言
在区块链领域，不是每天都会有人出来说“我有一个新的颠覆性突破”，即便有，也更多地来源于广告营销。从十年前中本聪在比特币白皮书中提出的PoW机制，到五年前以太坊的智能合约，近几年能有上述这些如明星般璀璨的技术突破案例乏善可陈。然而，在2018年出现的Avalanche共识协议可能是其中的例外。
2018年5月， 一个名为“Rocket team”的匿名团队在星际文件系统（IPFS）上发表了一篇名为《从“雪花”到“雪崩”：一种新型的亚稳态共识协议族》的论文，该论文立刻引起了人们巨大的关注。Avalanche是一种新型的区块链共识协议，由Rocket team从gossip协议中获得灵感，通过亚稳态机制来保证系统的安全。相比于目前主流的共识算法，Avalanche具有许多优良特性，有望成为下一代区块链共识算法中的明珠。正如康奈尔大学教授埃米·冈·瑟勒（Emin Gun Sirer）所言：“Avalanche描述了一种新的共识协议，它将中本聪共识协议与经典共识协议相结合，这是一次重大的突破。”
2.早期共识协议的发展
分布式系统中的共识问题一直是计算机科学领域的一个重要问题。目前人们主要有两类共识协议来解决该问题：一类是经典共识协议，另一类是中本聪共识协议。
经典共识协议由图灵奖得主兰伯特提出，具有强一致性、高效的特点，然而它也存在一些缺点，首先是通信成本，在经典共识协议下，节点的个数不能超过1000个，因为系统的通信成本会随着节点数量的增加呈二次指数形式增长；其次是要求网络中所有的节点都是可信的，因此节点无法自由进出。
另一类共识协议则是因比特币而被众人所熟知的中本聪共识协议，这类协议无法达到强一致性，但为系统提供了一个安全的概率保证——在实际运行中，只要达到一定的参数标准，共识就是不可逆的。采用该协议的系统具有开放性，无权限的特性，任何节点都可以随时加入网络，然而也存在成本高昂、浪费资源且性能有限的缺陷。
而Avalanche共识协议则是结合了上述两类协议的优点，借鉴中本聪协议的类似设计，采用概率性的安全保证，使用可调的安全参数来使共识失败的概率任意小；另外加入了BFT属性，增加系统的效率和安全性。
3.从“雪花”到“雪崩”：Avalanche协议介绍
3.1.Avalanche基本原理
Avalanche是一种基于亚稳态机制的分布式拜占庭容错协议，可为系统提供强大的安全保障，此外，其并发性的特征可实现高吞吐量和可扩展性。Avalanche一共由Slush、Snowflake、Snowball和Avalanche四个子协议组成：首先是最简单的Slush协议，随后在Slush的基础上，又逐次构建了Snowflake、Snowball 和 Avalanch三个BFT协议。
3.2.Slush 协议
Slush协议是Avalanche协议系列中最基础的部分，Slush协议的灵感来源于Gossip协议（又称八卦协议）。该协议通过多次重复的随机抽样方式来使节点之间达成共识。为了简单地理解该协议的基本原理，这里我们引用Avalanche白皮书里在一个无信任的分布式网络中，节点投票选择蓝色或红色作为最终颜色的例子（因为在共识协议中，无法在两种选择中做出唯一决定是最大的难题）。在Avalanche协议下，节点之间达成共识的步骤如下：
（1）所有的节点在初始时都是未着色的状态；
（2）当节点从客户端接受到交易信息时，未着色的节点A将自己的颜色更新为交易所携带的颜色，并向其他节点发起询问。
（3）如果是未着色节点B收到询问请求，那么该节点就会染成相同颜色，并对节点A进行相同颜色的回复，同时向另外的其他节点发起询问；如果是已经着色的节点C收到询问请求，那么节点就对节点A发出自己颜色的回复；如果节点A没有在限定时间内收到 k 个响应，那么节点A就会从剩余节点中继续选择一些节点发出并发出请求，直到收集到 k 个响应；
（4）节点A收集到K个响应后，就会检查是否存在相同颜色的样本数值/总样本数（x），使αk，这里α是协议的参数，并且α>0.5；如果x<αk，那么节点将会改变颜色；否则不改变颜色；
Slush协议有许多优良的特性：
（1）状态简单：在该协议下节点可以是无内存的。节点在每轮查询之间除了保留当前颜色之外不保留任何状态，特别是不保留与其他节点交互的历史记录；
（2）小样本：Slush协议与传统共识协议有显著的不同，传统共识协议要求对每个参与者进行查询，而Slush协议只是在每一轮中随机抽取网络中一个小的且大小固定的部分；
（3）重复抽样：Slush要求进行m轮重复抽样。此时，即使网络一开始处于50/50红蓝分割的亚稳态，采样过程中的随机扰动也会导致一种颜色获得微弱的优势，之后的重复采样将建立并放大这种优势；
（4）通信成本低：每个节点每轮都有一个恒定的、可预测的通信成本，并且该成本随n呈对数型增长。
3.3.Snowflake协议
尽管Slush协议有许多优良的特性，但是当Slush协议部署在具有拜占庭节点的网络中时，攻击者可能会干扰决策。特别是如果诚实节点偏爱一种颜色，那么攻击者可以尝试将节点翻转到相反的颜色，以保持网络的平衡。Slush协议本身是稳定的，但有拜占庭节点存在的情况下，它本身并不能提供强大的安全保证。为此，Rocket team在Slush协议的基础上增加了一个计数器（counter）来增加系统的安全性，该协议即Snowflake协议。
具体而言，在Snowflake协议里，计数器可以记录有多少个连续的样本都产生了同一个颜色（当节点A询问得到的响应结果为x≥αk，那么节点A的计数值cnt加1；每当节点A的颜色发生改变，节点A就会把cnt值重置为 0）。 如果一个节点的计数值cnt超过了某个阈值 β，它就会接受当前的颜色。这里的 β 是系统的另外一个安全参数。
当该协议为拜占庭节点阈值和所需的保证数设定参数后，就可确保系统的安全性（即没有诚实节点会接受发生冲突的交易）和活跃度（任何一笔由诚实节点发出的交易都会被其他节点接受）。
3.4.Snowball协议
在历史上，以太坊前前后后共经过七次硬分叉，其中与本次“君士坦丁堡”类似的还有“家园”阶段和“拜占庭”阶段的硬分叉，而其他的硬分或是是为了突发事件，或是在宣传和规模上较小，与本次硬分叉没有可比性。以太坊每次因技术升级带来的硬分叉都会给ETH带来巨大的行情波动。基于这一现象，我们选取上述两次历史上的硬分叉进行分析。
Snowflake协议的状态是短暂的：每次颜色的翻转都会重置计数器。尽管从理论上将该协议能以最小的状态代价保证系统的安全性，但是为了使系统的安全性更高，Rocket team在Snowflake协议的基础上引入了一个更加持久的可信度，这就是Snowball协议。
具体而言，Snowflake协议和Snowball协议的区别如下：
（1）每成功查询一次，节点就为该颜色的信任度计数值加1；
（2）在当前颜色的信任度计数值低于新颜色的信任度计数值时，节点将切换颜色。
至此，Snowball协议不仅比Snowflake更难遭受攻击，而且更容易推广到多命令协议。
3.5. Avalanche协议
Avalanche是亚稳态协议族的最后一个协议，它在Snowball协议的基础上增加了有向无循环图（DGA）来记录所有的交易状态。DGA只有一个点，即创世点。引入DAG主要有两个好处：
（1）高效性，给 DAG 中的某个节点投票就意味着给从创世点到该节点的路径上的所有节点都投票，这提高了协议的效率；
（2）安全性，因为DAG里包含着交易信息，类似于区块链的链式结构特征。这使得在没有诚实节点的批准下，很难撤销过去的决策。
维护DAG的核心挑战是在冲突交易中进行选择，在加密货币的应用中，花费相同资金的交易（双重支付）即冲突，这些冲突的交易形成一个冲突集，诚实节点只能接受冲突集中的一笔交易。需要注意的是，包含有效交易的冲突集总是一个单元素集合。
Avalanche协议实际上是一个体现了所有冲突集的Snowball协议。然而Snowball协议使用重复查询和多个计数器来获取在冲突交易中的信任值，而Avalanche协议则是利用DAG结构并使用交易的子代来达到此目的。具体流程如下所示：
（1）当节点A收到一个新交易 T时，它就发起一个的查询流程（随机抽样 k 个节点），启动查询的节点会把 T 加入自己已知的交易集合；
（2）收到消息的其他节点会查询自己的DAG交易集，看看是否存在T交易的父交易，如果存在，那么交易T就可以看成是非常可信的，即确认该交易；否则，只要T交易的任何一个祖先交易不满足条件，那么该笔交易就会被确认为非法；
（3）当节点A收到k个响应后，就会检查是否存在至少αk 个确认该笔交易的信息，如果是，那么T就会收集到一个Chit值，记为CuT=1，否则CuT=0。；
（4）上述的过程会为 DAG 中的每个交易标记上 Chit 值以及它关联的可信度值的大小。需要注意的是，Chit是在一次抽样中产生的，是不可变的值，取值只能为0或1，而它的可信度值是可以累加的，该值会随着DAG的扩展而增加；
图7是一个交易被打上chit值和可信度值的 DAG 图，图中每个交易的查询结果用 来表示，颜色更深的方块表示 可信度更高。比如，T2 的可信度是 5，它比 T3的可信度要高。这也就意味着，T2 的后代比 T3 的后代更容易收集到 Chit。
3.6. Avalanche协议的特性
从实际情况看，在“家园”硬分叉阶段，由于2015年下半年以太坊Frontier版本的发布，让人们看到了以太坊的技术实力和智能合约的潜力，为此市场对即将到来的“家园”版本普遍持乐观态度，因此以太坊在分叉前的几个月处于上涨通道，此过程中必然有泡沫的累积，在硬分叉结束后市场的乐观预期也随之结束，因此硬分叉后ETH价格的下跌成为必然。
在上文中我们介绍了Avalanche协议的基本原理，现在我们来具体分析Avalanche协议有什么优良特性。
（1）高效的可扩展性：因为协议是轻量级的，所以可以提供扩展性和低延迟；
（2）高拜占庭容错：即使网络中有超过50%的节点是拜占庭节点，网络依然是安全的;
（3）静态绿色：在Avalanche协议下，网络运行时可持续的，与PoW机制不同，Avalanche协议不会浪费任何资源;
（4）低通信成本：传统共识协议的通信复杂度为O(n^2)，而Avalanche协议的在O（kn logn）到 O（kn logn）之间。
4. 零确认交易与Avalanche协议
在Avalanche协议的论文发布后，人们还没有发现Avalanche协议与零确认交易之间有什么关系。然而在2018年12月左右，BCH社区的技术人员Chris Pacia发表一篇文章，认为可以使用Avalanche协议来保证零确认交易的安全性，至此引起了市场的广泛兴趣。
在前文中我们提到，Avalanche协议要求经过m轮重复抽样后来达成共识，为了限制确认的时间，重复抽样的次数必须受到限制，而这意味着，当网络中恶意节点的数量尝过一定比例后，在受限制的重复抽样轮次里，诚实节点之间无法达成共识。为此，Chris Pacia认为可以引入PoW机制作为反sybil机制来保护网络的安全，阻止黑客激活的攻击节点数量超过阈值。
具体而言，如果在网络上没有双重支付，那么矿工接收交易到他们的内存池中，选择要放入区块的交易，并将打包好的区块广播到网络。此时，矿工之间甚至没有发送avalanche消息。当双重支付进入矿工的内存池时，它会触发avalanche过程。矿工开始向相互发送avalanche查询并执行n轮。最终，所有矿工都会决定交易A是有效的，B是无效的，或者A是无效的，B是有效的。
上述方案只是BCH技术人员的初步设想。目前，BCH的Avalanche协议仍然在进行开发中，预计2019年底或2020年初进入主网测试阶段。
5. 结论
Avalanche作为一种亚稳态的共识协议，通过多次重复抽样的方式来使节点之间达成共识。为此，相较于经典共识协议和中本聪共识协议，Avalanche具有高拓展性、静态绿色以及低通信成本的特点。同时，由于Avalanche协议中引入了可信度，而可信度会随着DGA的扩展而累加，这意味着可达成预共识，即采用Avalanche有可能实现零确认交易。目前BCH团队已经展开了相关技术的研发测试，一旦实现零确认交易，这将是对BCH的重大利好。
