区块链笔记-番外算法Snowflake to Avalanche

今天我们来学习一下一个新的共识算法，他较以往有非常大的改变。雪崩算法如果在数学上可以给出更好地安全性证明以及活性证明，它可能在接下来一段时间大放异彩。

在 2018 年 5 月纽约举行的 Token Summit III 上，康奈尔教授埃米·冈·瑟勒（Emin Gun Sirer）发布了一个新型的区块链共识协议，它是由一组算法组成的家族，声称它是公式算法的重大突破和创新，这个算法家族集成了经典的 Non-Byzanting 共识算法和 Nakamoto 共识算法（即 POW） 两者的特点。用他们的话来说就是，简单而又强大无比。

亚稳态机制：

算法提出了一种基于亚稳态机制（metastable）的共识协议族。所谓亚稳态，是指系统在某段时间内处于稳定状态，但在另外一段时间内可能是不稳定的。稳态代表了系统的最低能量点，而亚稳态则是一个局部的而非全局的最低能量点。以下图中的小球为例，如果用比较小的力推小球，则会停留在位置1这个亚稳态上，而如果用比较大的力推，则会进入位置3这个真正的稳态上。

图 亚wen态示意图

那么这个新的共识协议族有什么特点呢？

绿色（Green）：消耗很少能源

安静（Quiescent）：没有交易时不需要工作（出块）

高效（Efficient）：节点交互复杂度O(knlogn) ~ O(kn)

如何实现以上目标？主要依赖以下几种措施：

并行共识模型：不使用单一复制状态机（RSM）模型，每个节点维护自己的RSM（可以互相转移所有权），系统对有关联的交易只维护偏序（partial order）

反复随机采样：引导诚实节点产生相同输出

亚稳态决策：亚稳态决策可以使得一个大网络快速推进到一个不可逆的状态（虽然不能100%保证）

既然是共识协议，必然绕不过安全性和活性的证明。我们先看一下这两个特性的定义：

安全性（Safety)：nothing bad happens

活性（Liveness）：something good eventually happens

该论文证明，文中提出的算法可以提供强概率安全性保证，并且保证诚实节点的活性。所谓“强概率安全保证”，是指共识被逆转的可能性小到可以被忽略（甚至小于哈希冲突的概率），实际上POW提供的也是强概率安全性保证。

另外，文中的理论分析是基于同步系统假设，而实验过程则是在部分同步系统中完成的，实验结果和理论分析基本吻合。

雪泥算法SLUSH：

图 雪泥算法实现过程

为了算法的通用性，这里是以颜色冲突为例：R表示红色，B表示蓝色，⊥表示没有颜色（初始状态）。

初始状态：没有颜色（⊥）

收到交易：染成交易中指定的颜色，同时发起查询

查询：在网络中随机选取k个节点，如果规定时间内没有收到k个回复，再多选一些节点，直到收到k个回复为止

收到查询：如果没有染色，染成查询中指定的颜色，并回复该颜色，同时自己也发起查询。否则直接回复自己当前的颜色

决策：收到k个回复后，如果某种颜色所占比例超过阈值α（0.5～1），则把自己染成那种颜色。然后继续进入下一轮查询，一共查询m轮，决定最终结果

可以证明，随着节点数n的增长，m呈对数级增长，因此可以有效控制通信量。

Slush算法是一种非拜占庭容错（BFT）算法，但却是后面三种BFT算法的基石。

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

（1）简单状态（simple state）

节点是 memoryless 的，在每一轮 query 之间，除了 color，不保存其他任何状态。

**（2）小样本（small sample） **

不像其他共识算法，每轮必须向所有节点发出请求。Slush 只需要向一个很小（常量 k）的随机样本集发出 query。

（3）反复抽样（repeated sampling）

通过反复抽样，可以放大随机扰动。比如，即使初始状态是一个 50/50 的对等分裂状态（收到了两种冲突的 color 响应 ，且他们数量相同），抽样过程中的随机扰动（perturbation) 也会导致一种 color 会获得轻微的优势，然而协议通过反复的抽样可以不断放大这种优势。

（4）抽样轮数或时间期限（用 m 表示）

如果 m 足够大，Slush 算法可以保证所有节点都有同等的机会被染色（colorized），每个节点每轮通信都会有一个常量的，可以预测的通信消耗。m 会随着 n 变大。 m 是指轮数或时间限制。 如果 Slush 被用在有 Byzantine 节点的网络中，那么由于 adversary 节点可以故意把自己翻转（flip）成一个与主流 color 不一样的 color 来打乱平衡，使得整个网络的安全性大大降低。 因此，我们把 Slush 协议作为 BFT 协议的原始状态，它不能提供完整的 BFT 保证。

雪花算法Snowflake：

Slush算法是无状态记忆的（memoryless），节点不保存和其他节点的交互历史。

Snowflake算法在该基础上，为每个节点增加了一个查询计数器，用于累积该节点对当前颜色的信任度。如果连续β轮都选择该颜色，则接受该颜色。

图 雪花算法实现

具体修改的部分：

每个节点维护一个计数器

每次颜色发生变化时，将该计数器清零

每次查询成功（收到αk个回复），并且颜色不变时，计数器加一

Snowflake 对 Slush 的改进非常简单，下面也做个总结：

（1）每个节点维护一个 counter 变量 。

（2）每当 color 进行改变，节点都会把 counter 值重置为 0。

（3）一旦 query 得到的响应结果中包含同一 color 的数量 ≥ αk，那么该节点就会把 counter 加 1。

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

论文在后面还介绍了一个 phase-shift 点，correct node 更倾向与做出一个决定而不是维持在一个 bivalent 状态。 并且，还会有一个叫做 point-of-no-return 的时间点，Byzantine node 在 phase-shift 之后失去控制，而 Correct node 则在 point-of-no-return 点之后开始 commit color。

（要出差，回来继续）