雪崩协议（Avalanche）共识机制3.0探究

来源：共识未来作者：袁浩

在上周美国旧金山举行的 Blockchain Week 上，康奈尔教授埃米·冈·瑟勒（Emin Gun Sirer）对其领导的BloXroute及Avalanche项目进行宣讲，BloXroute是一个Layer0的底层协议，致力于开发跨链的区块支付网络。

而雪崩协议（Avalanche）则是一个新型的区块链共识协议，分布式系统领域中，不是每天都有人告诉你“我有一个新的突破”。但，Avalanche可以说是一个公式共识算法的重大突破和创新，这个算法家族集成了经典的 Non-Byzanting 共识算法和 Nakamoto 共识算法（即 POW）两者的特点，做到简单而又强大。

今年5月份，匿名团队Team Rocket同Sirer教授合作，在IPFS上发表了题为“Snowflake to Avalanche: A Novel Metastable Consensus Protocol Family for Cryptocurrencies”的论文。该论文关注于具体的细节和证明上，因此很难被非专业人士理解。而目前国内对这个共识协议还甚少了解，在此，我对它进行一个尽量简化和可视化的分析。

两类共识协议

当许多分布式计算机共享相同的任务和资源时，共识是最重要目标之一。

典型的例子是：在多个服务器上维护金融系统中的帐户余额。金融机构不依靠单一数据库来存储数据，而是利用分布在全球不同地理位置的机器来处理这些交易。他们需要一种方法来让所有这些机器数据是一致的，进而它们所反映的帐户余额也是一致的。

另一个例子是：保持对亚马逊在线购物服务的一致性。为了在全球范围内扩展服务，数据必须（在地理上）分布于不同的大型数据中心上。亚马逊需要定期查看其库存产品，否则可能会发生无法意料的事情。例如，库存的最后一件商品肯能会重复出售给两个不同的人。

共识机制一直是计算机科学中的一个重要问题。为此，学者和工程师们在过去40年中一直在努力寻找有效的解决方案。在分布式系统领域，目前只存在两组主要的共识协议族。我们接下来将会描述着两组协议族。

经典共识协议BFT

第一类协议被称为经典共识协议BFT，它是由两位伟大的计算机科学家Leslie Lamport和Barbara Liskov在1982年共同开发的。他们两人都是图灵奖获得者（相当于计算机科学家的诺贝尔奖）。我们熟知的国产公链代表小蚁NEO就是采用此共识机制。该协议采用“许可投票、少数服从多数”的记账机制，允许33%的容错，优点是可以快速结算和快速担保交易。

然而，这也是有代价的：

它们无法扩展到1000个节点以上。这是因为它们通信成本正比于节点个数的二次方，即O(n?)。
他们要求网络中的每个人都知道所有其他参与者。

本质上，他们的安全性取决于法定数量的节点所作出的一致判断，这些节点确认看到同样的事情并进行认定。在构建私链时，这种方法是合理的，但是，当您处于不受信任的节点的动态环境中时，这种方法并不适用。

因此，公链可能需要基于另一种不同的共识协议，当然也有针对经典共识协议作出的一些改进（诸如动态调节节点，修改底层网络拓扑等），但比较适合联盟链的应用场景。

中本聪共识协议POW

2009年，另一个类协议POW被提出来了。中本聪提出了他的新协议系列，并展示了它独特的稳健性：

我们不需要知道参与网络的所有节点。任何节点都可以在任何时间点离开或加入，任何矿工都可以提出一个区块并参与系统。
它可以扩展到分布在全世界的大量节点和参与者。

然而这些优点也是有代价的，特别是：

比特币非常慢，平均而言，用户必须等待大约10–60分钟才能确认他们的交易被存储在链上。
吞吐量也非常有限。比特币每秒可处理大约3–7笔交易，当然，这处理速度距离成为世界货币的处理量还相差甚远。
最后，比特币消耗了大量的能量；大约相当于4个切尔诺贝利核电站的能量为比特币供电。这些能量都花在了运算上了。

共识家族Consensus family

Emin教授在深入研究前述两种主流共识机制后，受 Gossip 协议的启发，提出了一组BFT协议（简称“共识家族”，Consensus family）。

“共识家族”对诚实节点（Correct nodes）和拜占庭节点（Byzanting nodes）的行为作了提前约定：诚实节点绝不会发出冲突交易，而拜占庭节点也不可能伪造一笔与诚实节点冲突的交易（也就是说，拜占庭节点发出的“伪造”交易，只会与自己以前发出过的交易冲突（比如双花 double spending），但是不可能与诚实节点的交易冲突），拜占庭节点可以伪造许多彼此冲突的交易，但是诚实节点只会采用其中一笔交易。

最终，“共识家族协议”可以保证在存在拜占庭交易的情况下，共识的最终结果只会是接受一组互不冲突的交易集合，“共识家族”也采用了 UTXO 模型。

“协议家族”一共是由 4 个协议构成的，先从 Non-Byzantine 协议开始：Slush，在其基础上逐渐构建?Snowflake，Snowball 和 Avalanche?这 3个 BFT 协议。

Slush 协议：是“协议家族”的第一个协议，它是一个非拜占庭协议（Non-byzanting protocol，后续三个协议都是 BFT 协议）。Slush协议的特点是：简单状态（simple state），小样本（small sample），反复抽样（repeated sampling），抽样轮数或时间期限（用 m 表示），Slush 协议作为 BFT 协议的原始状态，不能提供完整的 BFT 保证。
Snowflake 协议：也叫 “BFT Snowflake”，它是“协议家族”的第二个协议，在 Slush 的基础上扩展而来。Snowflake 为每个节点增加一个 counter，用来记录一个节点当前 color 的可信度。Snowflake 可以保证对最小的状态做出很强的保证。
Snowball 协议：Snowball 是共识家族中的第三个协议，它对 Snowflake 协议做了改进，添加一个更持久的可信度标志，使得协议安全性更高，进一步增加了共识结果的可靠性（confidence）。Snowball 不仅比 Snowflake 更难攻击，而且协议更加通用化了。
Avalanche 协议（DAG）：Avalanche 是“共识家族”中的第四个协议，也是最核心协议，它在 Snowball 的基础上添加一个动态的仅限追加（append-only）DAG 结构来记录所有的交易。DAG 结构给雪崩协议Avalanche?带来了两大优势：高效，安全。

共识家族的核心理念：Metastability

共识家族全都基于亚稳态模型（metastable mechenism）。雪崩协议的核心理念也是metastability。共识协议中最糟糕的事情是无法在两个选择之间做出决定，即你不希望它模糊地说两个事件中有一个发生了，实际你期望它能确定两个事件中到底哪个发生了哪个没发生。雪崩协议的matastable协议旨在倾向于选择于两个选项中的一个。

运行中的雪崩协议核心思想依赖于抽样投票。

为了直观解释该过程的核心思想，让我们看一个简化的例子，如上图所示。考虑一个想要投票给蓝色或红色的去信任节点网络。

网络的单个节点从选择少量随机对等节点（例如五个）开始，并要求他们选择颜色。
然后，每个对等节点以投票进行回应，发出请求节点使用该投票来形成所有投票的加权结果。在上图中（在第一帧中），从发起请求的节点角度来看，整个网络基于第一投票倾向于红色。
每个参与者都需要重复这一过程。

该协议类似于重复的二次抽样投票过程。这里发生的事情是，即使我们开始在红色和蓝色是一半一半的最糟糕的情况下，在一轮之后，很有可能结果不再是打平手了。此外，在两轮甚至在三轮之打平手的概率将会非常小，打平手的几率会以指数方式衰减。

该协议旨在于倾向某一结果而不是留在模棱两可的中间选项。随着它的倾向性越来越高，网络的感知的颜色将会转移到其中一种颜色。我们向一个结果方向移动的速度（节点对一种颜色投票比另一种颜色更多）将会不断加快，并且在某个时候我们达到不返回点，整个网络已就颜色达成一致。

Avalanche雪崩协议综述

雪崩协议（Avalanche）结合了两者的优点，特别是，

快速结算和低延迟：也就是说，在全球范围内实现结算需要大约2-4秒钟。这基本上意味着在4秒后，您的付款就已经处理和验证完成了。（下图Emin教授的ppt中指出：AVA的确认延迟时间只有4秒，相比比特币、以太坊及Alogrand均有大幅提高）
更高的吞吐量：每秒可处理1000–10,000个交易。（下图Emin教授的ppt中指出：AVA的TPS达到1300，相比比特币、以太坊及Alogrand均有大幅提高）
稳健：网络无需就参与者是谁达成一致。
静态协议：最重要的是，协议是绿色的。这意味着它是可持续的，它不会浪费任何能量，并且没有特殊的矿工生态系统，其中矿工的利益与用户的利益无关。

关于协议的一些补充说明：

高效的可扩展性：协议是轻量级的，因此提供可扩展性和低延迟。
拜占攻击庭容忍度：它可以容忍大量的拜占庭参与者，而不对安全性产生影响。特别地，它可以容忍多达50％的节点作为拜占庭节点（即尝试欺骗网络并保持整个网络不平衡的节点）。但是，它们无法让两个节点决定两种不同颜色。
平等主义生态系统：雪崩协议产生了一个平等主义的生态系统，即网络中的所有节点都是相同的。没有矿工，也没有特权。
冲突交易不受保护：如果攻击者试图在两次不同的交易中花费相同的钱两次（双重支出），那么雪崩协议将无法在这两种交易之间做出选择，导致这笔钱丢失。经典共识和中本聪协议将会选择其中一个交易，但是雪崩协议不会。这是雪崩协议的一个非常有趣的属性，它会隐式而又自然地惩罚坏的角色，而协议本身没有增加任何额外的复杂读。

结语：

共识机制是区块链的灵魂，共识机制的算法设计直接决定了区块链的交易速度，交易吞吐量TPS。人们经常谈论比特币中使用的共识协议，就好像它是一种纯粹的去中心化的方法，可以平等地对待所有网络参与者的意见。不幸的是，在比特币中决策主要是由矿工做出的。

相比之下，雪崩协议将共识问题与管理问题分开。每个都是模块化和独立化地处理。通过gossip协议与循环采样的智能组合形成共识。同时，通过抽样和投注股份实现公平治理，从而实现用户与其决策之间的直接联系。

我们注意到一些热门项目诸如Perlin已经开始搭建在雪崩协议Avalanche之上：https://medium.com/opentoken/perlins-implementation-of-avalanche-1cf7dceadd06

雪崩协议Avalanche目前尚未得到大规模应用，但考虑到其独特创新之处，我们认为其可以比肩Algorand项目值得重点关注。

参考文献：
-Cryptoconf 2018, Emin Gün Sirer talk?—?Snowflake to Avalanche
-Snowflake to Avalanche: A Novel Metastable Consensus Protocol Family for Cryptocurrencies, Team Rocket, 2018
-SFBWofficial 2018,?Emin Gün Sirer talk: ?Ava protocol with new consensus family