一种新的区块链共识算法：雪花到雪崩

------

------

本文介绍了一种最新的区块链共识算法，该算法于2018年5月首次发布，是由一组共识协议组成的共识家族。 与目前主流的共识算法相比，它有一些重大的创新和突破，值得探索。

1 简介

2018 年 5 月在纽约举行的 Token Summit III 上，康奈尔大学教授 Emin Gun Sirer 发布了一种新型的区块链共识协议，是一种算法家族，声称是公式算法的重大突破和创新，该算法family 融合了经典的非拜占庭共识算法和中本聪共识算法（即 POW）的特点。 用他们的话说，它简单而强大。

目前国内科技界对这个共识协议还知之甚少，所以决定对其进行详细介绍和分析。

ipfs讨论组发布了一篇关于该算法的论文，如下：

1 简介

本文主要介绍的 BFT 协议由一组基于亚稳态模型的协议（简称“协议族”，Consensus 族）组成，可以提供高概率的 BFT 安全保障。 作者声称这个协议可以达到 1300 tps，交易只需要 4 秒的确认延迟。

论文中提到，“协议族”的思想主要是受到Gossip协议的启发（关于Gossip的运行机制，我在另一篇文章中有）。

具体思路是，通过对网络中的节点进行反复采样（收集它们对某个提议的回应），最终可以将所有诚实节点引导到相同的共识结果（协议）。 这是一个关键参数，称为安全参数。 通过调整该参数，可以将共识失败的可能性降到最低。

作为与目前主流的中本聪共识（POW）算法的对比，作者指出“协议族”是一种更绿色、更安静、更高效的算法。

我们知道在 POW 中，有一个比较大的 tradeoff，就是用 Liveness 换取冲突的交易。 我们知道Liveness是指在有效时间内必须有一个确定的结果（也叫终止），而POW不对每笔交易（包括冲突交易）的最终性提供保证，而是提供概率机制来保证一定程度这个结果的确定性。

在“共识家庭”中，“良性交易”只保证安全和活跃。 也就是说，对于那些诚实的节点来说，他们之间的交易是不会发生冲突的，最终结果的确定性是可以得到保证的。

因为“共识家族”假设诚实的节点总是会按照规则做事（正确的客户端按照规定遵守协议），所以他们无法作弊。 另一方面，拜占庭节点可能会发出流氓交易（rogue transactin），“共识家族”不对拜占庭发出的交易做任何Liveness保证。 （协议不保证拜占庭客户提交的流氓交易的活性，这些交易相互冲突）

2 协议组成及特点

“协议族”一共由4个协议组成，从非拜占庭协议：Slush开始，逐步构建出3个BFT协议，Snowflake、Snowball和Avalanche。 它们都是基于亚稳态机制。

下面简单介绍一下这组协议的特点：

1）首先，与比特币类似，它也采用概率安全保障机制。 但不同的是，使用了一个合适的、很小的选择ε（采样参数），使得共识失败的可能性很小，几乎不可能。

2) 其次，它没有使用单一的 RSM（复制状态机）模型，而是使用了一种叫做“具有经过身份验证的客户端的并行共识模型”的东西。 简单来说，可信节点维护着自己独立的RSM，也可以转让自己RSM的所有权（Ownership）。 系统为相关交易维护一个Partial order（如果你不了解Partial Order的概念，可以查看Leslie Lamport的论文“Time, Clocks, and the Ordering of Events in a Distributed System”）。

3）最后，对于行为不端的客户，活性是无法保证的。 但对于诚实节点（Well-behaved clients）来说，他们的交易最终会被正确处理，保证安全性和活跃性。

整个系统实现了类似于比特币的机制，但其性能和可扩展性有了很大的提高。

这里需要注意的是：

“共识家族”事先就诚实节点（Correct nodes）和拜占庭节点（Byzanting nodes）的行为做了约定：诚实节点永远不会发出冲突交易，拜占庭节点不可能伪造冲突交易与诚实节点（也就是说，拜占庭节点发出的“伪造”交易只会与自己之前发出的交易发生冲突（如双花双花），而不会与诚实节点的交易发生冲突），拜占庭节点可以伪造许多相互冲突的交易交易，但诚实节点只会采纳其中一项交易。

也就是说，最终“共识家族协议”可以保证，在拜占庭交易的情况下，共识的最终结果只会是接受一组互不冲突的交易。

此外，“共识家族”还采用了UTXO模型。

安全与活力

安全：没有两个诚实的节点会接受冲突的交易

Liveness：诚实节点发送的任何交易都会被其他节点接受

安全系数：ε

概率保证：1 - ε

3Slush协议

Slush 是“协议家族”的第一个协议。 它是一个非拜占庭协议（Non-byzanting protocol，后面三个协议都是拜占庭协议）。 该协议的运行原理如下：

1）所有节点最初都是无色的

2）当节点收到客户端的交易请求后，立即将自身变为tx中设置的颜色，同时发起查询。

2.1) 节点在执行查询时，会随机选择一个相对较小的节点样本k，向它们发送查询。

2.2) 如果uncolored节点收到query，它会被colored并用color回复。 同时会发起查询（即Gossip）。

2.3) 如果已经着色的节点收到查询，它会用自己着色的颜色回复。

2.4) 如果在限定时间内没有收到k个响应，则节点会继续从剩余节点中选择一些节点（在上一个样本之后）发出查询。 直到收集到所有 k 个响应。

2.5)一旦收集到k个响应，判断是否可以有一个比例分数≥αk的相同颜色/总颜色，α>0.5，这是一个协议参数。 如果满足αk阈值（threshold），采样的颜色与节点自身的颜色不同，则节点将自己的颜色变为采样的颜色。 然后，回到查询步骤，发起新一轮查询，共发起m轮。 最后，节点将在 m 时间段内决定最终的颜色。

下面总结了这个协议的特点：

(1)简单状态(simple state)

节点是无记忆的，并且在每轮查询之间不保存除颜色之外的任何其他状态。

(2)小样本(small sample)

与其他共识算法不同，每轮都必须向所有节点发出请求。 Slush 只需要向一个小的（常数 k）随机样本集发出查询。

(3)重复取样(repeated sampling)

随机扰动可以通过重复采样来放大。 例如，即使初始状态是 50/50 peer-split state（收到两个相互冲突的颜色响应，并且它们的编号相同），采样过程中的随机扰动（perturbation）也会导致一种颜色获得轻微的优势然而，该协议可以通过重复采样不断放大这一优势。

(4)采样轮数或时限(以m表示)

如果m足够大，Slush算法可以保证所有节点都有相同的机会被着色（colorized），每个节点在每一轮通信中都会有一个恒定的、可预测的通信消耗。 m 会随着 n 的增加而增加。 m 是轮数或时间限制。 如果在有拜占庭节点的网络中使用Slush，由于敌手节点可以故意将自己翻转成与主流颜色不同的颜色来破坏平衡，整个网络的安全性将大大降低。 因此，我们将 Slush 协议作为 BFT 协议的原始状态，不能提供完整的 BFT 保证。

3雪花协议

又称“BFT Snowflake”，是“协议族”的第二个协议，是在Slush的基础上扩展而来的。

Snowflake 为每个节点添加一个计数器，用于记录节点当前颜色的可信度。 具体来说，计数器记录有多少个连续样本产生了相同的颜色。 如果节点的计数器超过某个阈值 β，则它接受当前颜色。 这个 β 是另一个安全参数。

Snowflake对Slush的改进很简单，这里总结一下：

(1) 每个节点维护一个计数器变量。

(2) 每当颜色发生变化时，节点会将计数器值重置为0。

(3) 一旦查询得到的响应结果中相同颜色的个数≥αk，则节点将计数器加1。

当 Snowflake 选择合适的 β 参数和理想的 ε 安全系数时，它可以同时保证 Safty 和 Liveness。

论文后面还引入了一个相移点，正确的节点更倾向于做出决定而不是保持二价状态。 而且，还会有一个时间点叫不归路，拜占庭节点在相移后失去控制，Correct节点在不归路点之后开始commit color。

4滚雪球协议

Snowball 是共识家族中的第三个协议。 它改进了 Snowflake 协议，进一步提高了共识结果的可靠性（置信度）。

我们知道 Snowflake 中的状态标志是短暂的，每次颜色变化时计数器的值都会被重置。

虽然，理论上，Snowflake 可以保证对最小状态的有力保证。 但 Snowball 通过添加更持久的可信度令牌更进一步，使协议更加安全。

具体来说，Snowball 增加了一个 Confidence Counter 来记录可以生成指定颜色并达到阈值的查询次数。 节点对某种颜色进行一定次数的连续查询后，其对该颜色的置信度（信任度）将超过其他颜色。

总结一下，Snowball对Snowflake的主要改进如下：

(1) 每执行一次成功的查询，节点对该颜色的置信度计数器值加1。

(2)当节点当前颜色的置信度计数器值小于新颜色的置信度计数器值时，用新颜色替换当前颜色。

Snowball 不仅比 Snowflake 更难攻击，而且协议更通用。

下图是论文中Snowball执行过程的伪代码描述：

5雪崩协议（DAG）

Avalanche 是“共识家族”中的第四个也是最后一个协议，它在 Snowball 的基础上添加了一个动态的仅附加 DAG 结构来记录所有交易。

这个DAG只有一个sink节点，就是上图中的genesis vertex。

维护这样的 DAG 结构有两个主要优点：

1）高效

为 DAG 中的节点投票意味着为从创世顶点到该节点的路径上的所有节点投票。

2) 安全

混乱的交易，类似于比特币中区块的组合方式，使得过去的决定很难改变。 当节点创建交易时，它需要引用一个或多个父交易。 因此，新交易与父交易形成了 DAG 结构的边缘并且是不可分割的。 我们将后续发起的新事务称为子事务，过去的旧事务称为父事务，子与父之间不需要任何直接依赖。 同时，我们把直接父交易可以到达的所有祖先交易称为祖先交易集（ancestor set），所有可以引用的子交易称为子代交易。

维护 DAG 结构的最大挑战之一是如何选择和处理冲突交易。 为简单起见，我们称事务为T。当查询一个T时，T可达的所有ancestry都是当前节点u将优先发送查询的选项（preferred options）。 如果超过一定阈值的响应者投赞成票。 那么我们就说这个交易T收了一个Chit。 表示 CuT = 1，否则 CuT = 0。节点 u 根据交易 T 的后代的筹码和计算置信度。

论文中Avalanche协议执行过程的伪代码描述如下：

雪崩演示和实现细节

Avalanche 是“共识家族”的核心协议。 下面介绍其演示和详细实现过程：

先来看一个T的生成过程：

我们用 Tu 表示节点 u 记录的所有交易的集合，可以拆分成两个互斥的冲突集合 PT，T ∈ Tu比特币采用了PoW共识算法，因为冲突是传递性的，所以如果 Ti 和 Tj 是相互冲突的交易，则 PTi=PTj .

如果T选择的Parent是T'，那么我们用T'←T来表示，用

表明存在从 T 到 T' 的路径。

那么节点u可以通过以下公式计算置信度值du(T)：

此外，节点 u 还维护着一组本地已知的节点 (Nu ⊆ N)。 为简单起见，我们可以假设 Nu = N，并且不同节点构建的 DAG 必须兼容。 具体来说，如果一个节点中存在T'←T，那么系统中的其他节点也必须满足T'←T，反之亦然。

每个节点都会实现一个事件驱动的状态机模型，主要围绕发送查询、收集选票、通知其他节点有新交易T存在三个过程。

具体过程是：

1）当节点u收到一笔新的交易T时，发起一次一次性（one-time）的查询过程（随机抽取k个节点），发起查询的节点将T添加到已知的总交易集合中

，将计数器 CT 设置为 0，然后向其他对等点发送消息。 节点u检查自己的DAG交易集，看是否有T'

T，并且对于所有∀T∈PT'，如果每个T'都满足这个要求，那么T就会被认为是非常可信的，也就是说，它会得到赞成票。 如果任何祖先不满意，T 将获得否决票。

当节点 u 收到 k 个响应时比特币采用了PoW共识算法，它检查其中是否至少有 αk 个赞成票。 如果有，则说明T收集到一个Chit，记为CT=1，否则，CT=0。

上述过程会为 DAG 结构中的每个元素（即交易）标记一个 Chit 值及其关联置信度值的大小。 Chit 值由样本过程生成，是一个不可变的值，而置信度会累积。 随着交易量的增加，DAG 图的膨胀会不断增加。

注意，之所以confidence会不断增加，是因为Chit值CT的取值只能是0或者1，所以confidence单调增加。

下面是论文中连续抽样查询后标记了chit值和confidence值的交易的DAG图：

在上图中，较暗的方块表示较高的置信度。 每个节点由一对表示。 例如T2的置信度为5，高于T3的置信度（0）。 这也意味着 T2 的后代比 T3 的后代更容易收集 Chits。

最后，与比特币一样，Avalanche 也将最终交易的接受点和决策权交给了应用层。 应用层通过自己定义的谓词来考虑接受交易的风险。

可以通过称为“安全早期承诺”的操作来确认交易。 对于一个诚实交易 T（良性交易），如果它是冲突交易集合 PT 中唯一包含它的交易，并且收到的 Chit 超过阈值 β1，则认为 T 是可接受的。 如果一个诚实的交易 T 由于活性问题而没有被接受，它仍然可以通过重新选择一个不同的父交易来被接受。

由于不同的交易只消费和产生自己的UTXO，彼此之间没有任何关系，因此任何交易都可以重新选择父节点。

网络建模和验证

为了验证“协议族”的可靠性（Safety & Liveness），对其网络模型和实现条件进行了一些约束。

1）网络模型（Network Model）

假设是一个同步网络，同时使用一个全局协调器（Scheduler）来随机选择发起节点。

2）参数和变量

用C表示正确节点（Correct Node），用B表示拜占庭节点（Byzanting Node，c=|C|，b=|B|。

样本量k∈N+，采样率α的取值设置为：0.5 < α ≤1。

红色和蓝色分别代表两个相互冲突的选择。

采样方式采用超几何采样，被采样的k个节点在完成前不会被替换。

使用随机变量

表示R在一个样本中获得的投票数，x表示R获得的总票数。

那么查询达到阈值αk或更多票数的概率可以用下面的公式表示：

3）尾部限制（tail bound）

上面的超几何分布公式太复杂了，我们可以给它引入一个尾部限制来降低复杂度。

假设p = x/c代表R在总票数中的支持率，则

的期望是kp，即它的概率最终会偏离样本中位数一个小常数ψ，由Hoeffding tail bound给出，如下：

公式中的 D(p − ψ, p) 是 Kullback-Leibler 散度，由下式给出：

全文完结！