今天我们来学习一下一个新的共识算法，他较以往有非常大的改变。雪崩算法如果在数学上可以给出更好地安全性证明以及活性证明，它可能在接下来一段时间大放异彩。
在 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。
（要出差，回来继续）
网友评论