原创：隋笑 | THU学生区块链
点击“阅读全文”，观看完整视频
https://www.bilibili.com/video/BV14q4y1z7Hx?spm_id_from=333.999.0.0
本系列课程是清华大学学生区块链协会THUBA推出，由PlatON赞助的区块链课程，涵盖了从区块链基础学习到深度原理研究等方面。
前面的课程中我们提到过，在区块链网络中的各个节点都会保存一个账本，而节点之间并不能直接达成相互之间的信任，不同节点保存的账本数据可能也会有差别，那么到底哪些节点的账本数据会被采纳为合法的链上数据呢？这就需要有一种机制或者协议，来维护各个节点区块数据的一致性。这就是我们今天要学习的共识协议。
01 共识协议安全模型
区块链技术被视为共识协议与密码技术的交叉技术。2008年中本聪发明比特币之后，分布式系统共识协议，这一历史悠久的研究方向成为了新的热点。
根据参与共识的系统节点是否存在准入许可，可将共识协议分为有准入协议与无准入协议。
经典分布式共识协议的研究起于从上世纪80年代，典型协议如Paxos, PBFT等都得到了广泛的应用与不断的优化改进。这些协议在经典模型下是严格可证明安全的。而且在实际使用时，成熟的共识系统可以实现较高的吞吐量和较短的交易确认时间。有准入协议要求共识系统中每个节点彼此知道对方身份，这客观上也有利于监管。
无准入协议中，节点加入共识系统不需要准入审核，这类协议允许更大规模的共识参与节点，也现了更高的去中心化程度。共识节点的身份，隐私也得到了更大程度的保护。但是，以比特币使用的PoW协议为例，每个矿工在提出新区块时，都需要携带相应工作量证明，这一证明需要耗费大量计算资源。而且，无准入共识协议使用的技术、安全定义等都与经典协议有所不同，迄今为止，大量协议被提出，相当一部分学者仍然在探索针对这类协议有效的攻击、防御手段与安全模型。
1.1 共识网络模型
经典共识协议是根据不同网络模型假设进行设计的，常见的网络模型有同步网络、半同步网络、异步网络三类：
同步网络 (synchronous network) 中网络中诚实节点之间的消息传输延迟存在已知的上界。
半同步网络 (partially synchronous network) 中存在一个未知的网络稳定时间GST，GST后网络消息传输存在一定的上限 ∆, 能够确保诚实用户发出的消息在 ∆ 时间之后到达其他所有诚实用户。
部分同步网络模型的定义看似拗口，关键在于这一模型下虽然网络终将趋于稳定，但仍存在未知性和网络波动的情况。这也是区块链协议分析中常用的网络模型。
异步网络 (asynchronous network) 中敌手能够任意拖延诚实用户的消息或将其打乱顺序, 只要保证最终诚实用户的消息能够到达彼此。
说是最终，实际可以理解为永久丢失。这种模型下安全的共识协议也是最难设计的。
1.2 共识敌手模型
根据敌手的攻击方式手段，共识协议的敌手模型多种多样：
根据敌手攻击能力，可以分为宕机敌手、被动敌手、拜占庭敌手。
- 宕机敌手，因故障或网络原因离线
- 被动敌手，读取通信方之间私密消息
- 拜占庭敌手，实施任何行为破坏共识的达成
宕机敌手可以视为被拔了网线的诚实节点。被动敌手则主要致力于网络嗅探，获取不该知道的信息，拜占庭敌手则可以不按照共识协议，做任何想做的事来破坏共识。
此外，按照敌手适应性，可以分为静态敌手，弱适应性敌手，适应性敌手。
按照攻击方式……甚至按照敌手理性程度都存在不同的敌手模型。
有些学者用博弈论来分析比特币，基于理性敌手的模型，甚至得到了比特币安全与其市价的关系。
总而言之，任意一个安全的共识协议只能在一定的模型下保证安全。
02 共识协议的发展
2.1 拜占庭将军问题
现在我们来探索共识协议的发展。最早，可以追溯到80年代提出的拜占庭将军问题。拜占庭帝国国土辽阔，每支军队的驻地分隔很远，将军们只能靠信使传递消息。将军们通过进行集体投票决定选择进攻或者撤退。怎样使得将军们能在一个有叛徒的非信任环境中建立对战斗计划的共识呢？
图片上展示了一种叛徒策略，显然，少数服从多数投票是不可取的。
Leslie Lamport等人1982年提出了拜占庭将军问题，并给出了公式化的约束条件。从中可以提炼出经典共识的两大安全性质：安全性与活性。
用户将指令发送到共识系统，由共识系统运行共识协议并返回共识结果。
安全性侧重于一致，要求各节点不能存在分歧，活性则保证整个系统持续运行下去，不断达成新的共识。
2.2 异步二元拜占庭共识协议
得到了安全定义，网络与敌手模型，是不是可以开始设计安全的共识协议了呢？没那么简单。Fischer, Lynch and Patterson三位作者于1985年给出了一个严格证明的结果，又被称为FLP不可能定理。异步网络环境中，只要有一个恶意节点，就不存在安全的确定性共识算法。
1983年，Rabin和 Ben-Or 分别独立提出并实现了异步二元拜占庭共识协议 (ABA)。他们怎么做到的？他们牺牲了协议的确定性。他们的协议要么使用本地随机抛币（对半分的概率得到一个随机bit），要么使用密码技术（可验证秘密分享或者门限签名）获取一个公共随机抛币。简单说，他们的共识按轮进行，每一轮有一定概率结束，若是没能达成共识，则需要继续进行下去。
2.3 宕机容错协议
随后，1990年，Leslie Lamport 第一次给出了CFT协议Paxos。CFT协议可以容错不超过1/2的节点宕机，但对于拜占庭敌手则无能为力。Paxos协议非常复杂，每个共识节点可能同时以三种身份执行不同操作。
顺便的，又是Lamport，不也是他提出了拜占庭将军问题？正是，由于分布式系统领域的贡献，他获得了2013年的图灵奖。关于这位老爷子轶事很多，比如Paxos最早提出时，是借助小岛上议员选举投票的故事进行的协议说明，众多学者与工业界人士都抱怨读不懂。而Lamport则表示学界同仁“如此缺乏幽默感，实在令人生气”，拒绝修改论文。直到2001年，Lamport才终于重新描述了Paxos并进行发表。
言归正传，CFT 共识算法目前主要应用在企业内部的封闭式分布式系统或者私有链中。例如Chubby、ZooKeeper。
2.4 拜占庭容错协议
随后1999年，Miguel Castro与Barbara Liskov提出第一个异步网络下实用的BFT协议PBFT。PBFT实际上是一个半异步协议，基于一个领导人进行共识。领导人提出提议，共识节点们需要经过两轮广播才能确定达成共识，并返回结果。
总的来说，BFT共识算法适用于私有链或联盟链等有强一致性需求的场景。
2.5 PoW与PoS协议
1993年，工作量证明的概念最早由Dwork与Naor提出，当时是用来对抗服务资源滥用或拒绝服务攻击。简单来说，过滤垃圾邮件。
比特币使用的PoW主要借助了密码学hash函数。hash函数将任意长度的消息压缩为固定长度的电子指纹，具有抵抗原象攻击的特点。
“中本聪”于2009年提出去中心化的电子货币系统——比特币，创造性地解决了无准入系统共识的问题，实现了去中心化。比特币链上交易确认大概需要等待6个新块的形成：约60分钟。每个块的提出都需要通过大量计算解决一个hash难度问题。
为了解决工作量证明带来的巨大能源消耗问题, 2012年，King与Nadal提出了基于权益证明(PoS)的共识机制，并应用在了区块链项目PPCoin中 。PoS共识机制中引入了“币龄”的概念。币龄是指货币数量与货币持有时间的乘积。与比特币不同，PoS共识中每次提出区块，提出者消耗的是币龄。
然而，由于PoS协议中，节点提出新块的成本太低，几乎无法避免恶意节点同时提出多个区块，NAS攻击、长程攻击、打磨攻击等可以对共识系统安全性造成极大的破坏。
2.6 混合共识协议
随着区块链技术的发展，PoW协议交易确认慢、能耗大的缺陷和而PoS协议存在的安全问题越发受到重视。一些学者提出，将PoW或PoS协议与经典分布式一致性协议的优势结合，生成新一代混合共识协议。
典型代表就是2016年，Silvio Micali等人提出基于权益证明（PoS）的区块链协议Algorand。Algorand 将 PoS 与BFT算法结合, 敌手模型为适应性敌手，网络模型为同步网络。Algorand证明了在系统中超过2/3的钱掌握在诚实节点手中时，共识系统的安全性。
该共识主要思路分为三步：
1.利用密码学可验证伪随机函数(VRF)集合PoS共识选择委员会成员与领导人；VRF是一种特殊的密码学技术，可以计算得到一个公共可验证的伪随机数。由这一伪随机数指定的委员会成员是不可预测的，因此可以抵抗适应性敌手的攻击。
2.在委员会内运行BFT协议；
使用可证明安全的BFT共识，确保共识的安全性与活性。
3. 每一轮选用全新选择的委员会。
即使适应性最强的敌手也无法影响共识系统的运作。
2.7 典型CFT共识协议—Raft
本小节将向大家介绍经典的CFT共识协议。2014年，Diego Ongaro 与 John Ousterhout 提出了易于理解的CFT协议Raft。Raft简化了Paxos, 同样的网络模型下（半同步），实现了可证明安全。
如图所示，Raft系统中每个节点可能有三个身份：领导人负责同步记录、广播指令、收集节点响应信息并提交指令，跟随者负责接收记录，接收领导人指令并返回响应信息，候选人广播信息竞选成为领导人，只要收到超过半数投票就被认为当选，每次投票阶段都是一人一票，先到先得。
与Paxos相比，Raft还具有以下特点：
1.强力领导者
被选举的领导人将自己的指令log完全复制到其他follower上。
2.高效领导人选举
使用随机timeout，不同节点发生超时的时间不同，大概率有一个最早发生超时的节点得到超过一半的投票当选为领导人。3.允许成员变更
为了防止成员变更阶段，出现不相交的两个过半数投票集合，在发生成员变更时，无论数据提交或领导人选举都要在两种配置上获得超过半数的支持。
03 课程总结
本节课是THUBA推出的区块链系列课程第二章的第一节课，我们介绍了共识协议的安全模型，从BFT，CFT等经典分布式一致性协议到PoW,PoS等区块链共识协议以及结合两类协议优势的新一代混合共识协议的发展过程，并介绍了经典CFT协议-Raft。共识协议的安全模型和具体方案多种多样，但就像我们在开头所说的，没有最好的共识协议，只有最适合的共识协议，共识方案的选择应该结合具体应用场景。
接下来的课程将会更深入地介绍各种共识机制，欢迎大家继续关注。
参考文献
[1] 刘懿中, 刘建伟, 张宗洋,等. 区块链共识机制研究综述[J]. 密码学报, 2019(4).
[2] Leslie Lamport, Robert Shostak, and Marshall Pease. 1982. The Byzantine Generals Problem. ACM Trans. Program. Lang. Syst. 4, 3 (July 1982), 382–401. DOI:https://doi.org/10.1145/357172.357176
[3] Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. 1985. Impossibility of distributed consensus with one faulty process. J. ACM 32, 2 (April 1985), 374–382. DOI:https://doi.org/10.1145/3149.214121
[4] Leslie Lamport. 1998. The part-time parliament. ACM Trans. Comput. Syst. 16, 2 (May 1998), 133–169. DOI:https://doi.org/10.1145/279227.279229
[5] Miguel Castro and Barbara Liskov. Practical byzantine fault tolerance and proactive recovery. TOCS, 20(4):398–461, 2002.
[6] Chen, J. and Micali, S., “Algorand”, arXiv e-prints, 2016.
[7] Diego Ongaro and John Ousterhout. 2014. In search of an understandable consensus algorithm. In Proceedings of the 2014 USENIX conference on USENIX Annual Technical Conference (USENIX ATC’14). USENIX Association, USA, 305–320.
END
文稿&视频 | 隋笑
编辑 | 土BA
审核 | Zeo Celia
本文转载自https://mp.weixin.qq.com/s/r9PG_ga3jRVKWq516Z7lHg
